RunQueue

The durable run queue (Stage 5 W1, design 4.55): submitted runs, one entry each, that workers on any machine take, run and close. A store's queue lives in the same database as its checkpoints - InMemoryCheckpointer.runQueue, SqliteCheckpointer.runQueue, PostgresCheckpointer.runQueue - but is a separate SPI: no transaction spans an entry and a commit. Correctness rests on rule 4 instead - every attempt has its own RunId, recorded here before the attempt touches the thread, and an attempt classifies the thread by those ids (Checkpointer.latestOfRuns, AttemptPlan) - so an input is applied at most once however many attempts run.

Implementations must be safe to call from several threads and processes, and must:

• '''submit''' an entry atomically: look up its SubmissionKey, if any, among the tenant's entries and insert only if there is none, so a retried submit gets the first one's ticket (Ticket.existing) and a different submission under a held key is refused (QueueError.SubmissionKeyReused); refuse a Reject submission to a thread with an open entry with GraphError.ThreadBusy naming no holder; close every queued Interrupt entry of the thread that has recorded no attempt Interrupted(by = the new entry) when an Interrupt entry is submitted; and issue entry ids in submission order, never reused;
• '''order''' each thread's open entries (rule 5): an entry that has recorded an attempt first, then Interrupt entries, then the rest, each by id; only a thread's first entry in that order - its head - is ever taken, and only while no other entry of the thread holds a live lease;
• '''lease''' like a claim: take leases a head whose lease is absent or expired, by the store's clock, with a new LeaseToken greater than every one issued for the entry, and ends the expired lease of every other entry of the thread (a head an Interrupt entry displaced), so two workers never hold an actionable lease on one thread; a lease may be renewed, released, have attempts recorded under it and close its entry for as long as it is the entry's current one, expired or not, and every such call under another token is refused (QueueError.LeaseLost), as is any on a closed entry (QueueError.EntryClosed); taking is skip-locked where the store can, so workers do not contend for one entry;
• '''record attempts''' durably before answering (recordAttempt): an attempt's RunId naming no other run on the thread - no checkpoint of the thread's history and no attempt of any entry of the thread has it - so the run-id lookup finds only the attempt's own run; no attempt past maxAttempts (AttemptStart.Exhausted); and none once the thread was deleted while the entry was open, closing the entry Cancelled(ThreadDeleted) instead (AttemptStart.ThreadDeleted);
• '''learn of deletes''': the store's Checkpointer.deleteThread marks every open entry of the thread in the delete's own transaction (or under its lock), whatever the deleted thread numbered, so no such entry runs on a new thread of the id; an entry submitted after the delete is not marked. The store's Checkpointer.commit refuses a checkpoint whose run is an attempt a marked entry recorded - while the entry is open and after it closes, until it is reclaimed - so a worker whose claim outlived its lease never writes the deleted thread's input;
• '''learn of admissions''': the store's Checkpointer.commit of a checkpoint whose run is an attempt of an open entry marks the entry QueueEntry.admitted in the commit's own transaction (or under its lock), and the mark stays when a later retraction removes the checkpoint, so AttemptPlan never starts an admitted input again;
• '''keep the evidence''': while an entry is open, its store's Checkpointer.prune keeps the newest checkpoint each of the entry's recorded runs committed on its thread, so latestOfRuns never loses an admitted run;
• '''close''' an entry once, with its EntryOutcome, the store's time and the thread's last event number then (QueueEntry.closedAtSeq), and keep it for the ticket lifetime; reclaim removes closed entries older than that, oldest first, and never an open one;
• '''scope by tenant''' (rule 9): entry, awaitClosed and openEntries answer for the caller's tenant's entries only (None and Some differ), another tenant's being as unknown as a reclaimed one;
• return from every call within a bound it documents, as Checkpointer does.

RunQueueContract in llm4s-agent-testkit is the executable form of this contract.