ADR-019: Queue Storage Engine¶

Status¶

Accepted. The receipt-plane portion of this design (open_receipt_claims as a bounded live-frontier table) is superseded by ADR-023: Receipt Plane Ring Partitioning, which replaces the flat open_receipt_claims table with partitioned lease_claims, lease_claim_closures, and lease_claim_closure_batches reclaimed by ring rotation + TRUNCATE. The rest of ADR-019 (queue plane, lease ring, ready/done partitioning) is unchanged. References to open_receipt_claims below are kept verbatim as historical context — read them as "the live frontier", which is now derived from the anti-join.

Context¶

The canonical Awa storage model keeps the queue row and the lifecycle state machine in the same mutable heap row. Claim, heartbeat, callback wait, retry, completion, and cleanup all update or delete that row. Under overlapping readers, that shape produces avoidable MVCC churn and dead tuples on the hot path.

ADR-012 reduced the problem by splitting hot and deferred storage, but it did not remove the core issue: the dispatch path still mutates the same execution rows repeatedly. Benchmarking showed that this leaves a persistent gap to append-only queue designs on dead tuples, and eventually on throughput under overlap.

Design goals and non-goals¶

This ADR is guided by the following 0.6 priorities:

Preserve Postgres-native transactional enqueue. A job created alongside application data must commit or roll back with that data, with no outbox gap.
Prefer no lost work under failure over benchmark wins. Crashes, restarts, network partitions, and worker death must not silently drop runnable jobs.
State the delivery contract honestly: at-least-once, not marketing “exactly once”. Retries must be safe, idempotency should be encouraged, and stale writers must be rejected by (job_id, run_lease).
Keep the claim path fast under contention with short transactions, queue-local cursors, and SKIP LOCKED-style claiming rather than global head-of-line blocking.
Keep lease / heartbeat recovery, retry discipline, and observability as first-class runtime concerns rather than operational afterthoughts.
Remain vacuum-friendly by keeping historical state out of the hot claim path and avoiding row-rewrite-heavy designs.

Non-goals and filters:

Do not claim “exactly once”.
Do not turn Awa into a replayable event log or Kafka replacement; the design remains a job queue with one active attempt owner at a time.
Do not introduce optimizations that weaken “no lost work under failure”, even if they benchmark well.
Do not solve contention by moving back to a single hot mutable jobs table or by holding long-lived transactions around claim/execute/ack.

Decision¶

Adopt a single queue storage engine built around append-only queue records, a small ready-tombstone ledger for rare out-of-band ready mutations, a narrow fast-rotating execution lease table, and an optional per-attempt attempt_state row for mutable runtime data that cannot stay in the immutable queue record.

Terminology¶

This ADR uses the following storage vocabulary:

Queue plane: ready_entries, ready_tombstones, terminal_entries
Execution plane: active_leases, attempt_state
Control plane: lane_state, ready_segments, ready_segment_cursor, lease_segments, lease_segment_cursor

The implementation and migrations use these physical names:

terminal_entries maps to {schema}.done_entries
active_leases maps to {schema}.leases
lane_state maps to {schema}.queue_lanes
enqueue heads map to {schema}.queue_enqueue_heads
claim heads map to {schema}.queue_claim_heads
ready_segments maps to {schema}.ready_segments

Physical layout¶

ready_entries
Immediate jobs are appended to rotating ready partitions.
Ready rows are immutable once written.
Claim order is driven by queue-local lane metadata and the compact {schema}.ready_segments map rather than scanning a large mutable heap.
ready_tombstones
Unclaimed cancellation, priority aging, and similar ready-lane mutations append a tombstone keyed by ready segment generation and lane identity.
Claim treats tombstones as committed spent evidence for safe claim-cursor advancement; exact-count paths skip tombstoned lanes.
Tombstones are reclaimed by truncating the matching ready segment; they do not create row-vacuum work on the hot ready table.
active_leases
The common path still records every claim, but the implementation can now do that in two stages:
append-only lease_claims receipts for every claim (the receipt path is now the default, not a zero-deadline-only short cut)
historical: a bounded open_receipt_claims frontier for currently-live receipt-backed attempts. ADR-023 replaces this with partitioned lease_claims plus explicit and compact closure evidence; "currently open" is derived as an anti-join over the active claim partitions.
lazy materialization into active_leases when the attempt needs the mutable execution path
Leases keep only dispatch and rescue-critical fields: ready reference, attempt identity, lane ordering, heartbeat/deadline state, and callback token/timeout.
Lease partitions rotate much faster than queue partitions and are pruned independently.
attempt_state
attempt_state is optional and keyed by (job_id, run_lease).
It exists only for mutable per-attempt data that cannot remain in the immutable queue row: current progress, callback expressions, and a temporary callback result for resumed handlers.
Short jobs must be able to claim and complete without touching attempt_state at all.
Transition paths delete attempt_state immediately when an attempt leaves running or waiting_external.
deferred_jobs
Scheduled and retryable jobs live outside the ready ring.
Promotion appends them back into ready_entries when due.
Deferred rows stay out of the hot claim path until they are runnable.
terminal_entries
Completion appends a terminal history row.
Done partitions are append-only and are pruned with their ready segment once the segment is sealed and no active lease or pending ready row still references it.
dlq_entries
Dead-letter handling is part of the storage engine, not an add-on.
Terminal failures can move directly into the DLQ instead of the main done history.
Operators can inspect, retry, and purge DLQ rows through the model/admin surface.
lane_state and segment cursor tables
Queue-local lane metadata is intentionally split so one row family does not absorb every enqueue and claim mutation.
lane_state itself is reduced to stable per-lane identity and legacy fallback fields. queue_enqueue_heads and queue_claim_heads remain as stable lane registries. The mutable enqueue and claim cursors live in PostgreSQL sequences referenced by those rows; enqueue reserves sequence ranges under a transaction-scoped lane advisory lock, while claim still locks queue_claim_heads to choose and emit work.
Availability counts have two grades. The dispatcher hot path and high-cadence worker metrics read sum(enqueue_sequence_cursor - claim_sequence_cursor) from the lane heads — two PK reads plus sequence state reads per lane, no scan over ready_entries. Admin calls that need exact availability (queue_counts) scan ready_entries WHERE lane_seq >= claim_sequence_cursor anti-joined with ready_tombstones. The dispatcher and metrics tolerate transient over-count from committed gaps, uncommitted sequence reservations, and tombstoned unclaimed rows; the cursor is only advanced after committed claims/cancels and only across committed spent/tombstoned prefixes, so it can lag but cannot skip visible ready work. historical: earlier iterations cached this as queue_lanes.available_count (a third counter mutated on every enqueue / claim / completion); long-horizon profiling under pinned xmin showed the cache was the dominant dead-tuple source, so v016 removed it in favour of the head-difference derivation.
Completed-history rollups live in a separate cold cache table so prune can preserve queue counts without serializing on the hot lane_state rows.
Completion must not update lane_state on every terminal transition; the hot path only mutates claim/enqueue control state. running is derived from active leases/receipts. ADR-026 terminal counts use append-only queue_terminal_count_deltas for done_entries terminal mutations, retained compact receipt batches for compact successes, folded queue_terminal_live_counts for sealed retained segments, and the post-prune queue_terminal_rollups cache. The permanent rollup is written in the prune transaction to a separate cold table rather than to lane_state, so prune does not serialize on the same hot rows as claim and enqueue.
Ready and lease segment cursor tables tell dispatch and maintenance which physical segment is active, claimable, or prunable.
Lease prune order is derived from lease_ring_state(current_slot, generation, slot_count). The older {schema}.lease_ring_slots table remains as transitional compatibility/inspection state, but it is no longer updated on every rotation and is not the authoritative ordering source.
Rotation state for queue and lease segments is owned by the maintenance leader.
This split is an explicit response to the remaining MVCC hotspot discovered during long-horizon event benchmarks: a single hot queue_lanes row per (queue, priority) recreated dead-tuple pressure under pinned-reader workloads even after the rest of the storage engine moved to append-only structures. Separate enqueue/claim heads reduce that mutation frequency and leave lane_state cold enough to survive long-running readers.

Lifecycle mapping¶

Enqueue immediate job: reserve a lane sequence range under the lane advisory lock, append to ready_entries, and append compact ready_segments metadata in the same transaction.
Claim: lock the queue's queue_claim_heads row, join the matching queue_enqueue_heads row, resolve the ready slot from ready_segments (ordered by next_lane_seq; historical: earlier iterations cached this ready-slot hint on queue_claim_heads.ready_segment_*, removed as a dead-tuple source under pinned xmin — the columns remain but are unused), select the next ready entries, treat any matching ready_tombstones rows as spent lane evidence, increment run_lease, append a receipt into lease_claims by default, and advance the claim cursor based on committed spent evidence plus the rows actually selected after commit.
Receipt-backed deadlines: per-queue deadlines live on lease_claims.deadline_at until the attempt materializes into the lease plane for callbacks, progress, or other mutable state.
Receipt rescue before materialization: close the stale receipt append-only and requeue it without first materializing a mutable leases row.
Runtime reads that need the current live receipt-backed set (queue_counts, receipt rescue, and receipt-backed load_job) consult only the active claim-ring partitions, not the full append-only claim history. historical: ADR-019 used a bounded open_receipt_claims table for this; ADR-023 derives the same set as an anti-join over partitioned lease_claims, lease_claim_closures, and lease_claim_closure_batches.
First heartbeat or progress flush for a receipt-backed attempt: lazily materialize the claim into attempt_state while keeping the claim on the append-only receipt path.
Callback registration or other lease-specific mutation for a receipt-backed attempt: lazily materialize the claim into active_leases.
Heartbeat after lease materialization / callback wait: update the active lease row only.
Progress flush / callback expressions / callback result: create or update attempt_state only when needed.
Retry or snooze: delete the active lease row, merge any attempt_state, append to deferred_jobs.
Complete: delete the active lease row, ignore or merge any attempt_state as needed, append to terminal_entries.
Terminal failure with DLQ enabled: delete the active lease row, merge any attempt_state, append to dlq_entries.

Attempt state invariants¶

There is at most one live attempt_state row per active attempt.
attempt_state is guarded by (job_id, run_lease) so stale writers from a rescued or retried attempt cannot mutate the next attempt.
Dispatch must not join attempt_state; claim performance should be insensitive to attempt_state size.
attempt_state must not store history arrays or long-retention terminal state. Error history remains in immutable queue payload.
Rescue scans inspect lease and attempt_state tables, not queue history.

Healthy operating signals for this design are:

attempt_state row count roughly tracks active long-running attempts, not total queue depth or total completions.
short jobs complete without creating an attempt_state row.
short zero-deadline jobs can also complete without ever creating a mutable active_leases row.
the live receipt frontier stays bounded to open receipt-backed attempts rather than growing with total claims and closures.
short zero-deadline jobs that never heartbeat can be rescued from lease_claims after the grace window without first creating active_leases.
heartbeat/progress-only long attempts can stay on lease_claims plus attempt_state without creating active_leases.
prune and cleanup horizons for attempt_state are immediate or very short.

Maintenance ownership¶

The leader-elected maintenance service owns:

promoting due deferred jobs
rescuing stale heartbeats, deadlines, and callback timeouts
rotating and pruning queue partitions
rotating and pruning lease partitions
rotating and pruning claim-ring partitions (added by ADR-023; replaces the ADR-019 open_receipt_claims cleanup path)
queue depth publication
DLQ retention cleanup

All prune paths remain best-effort and take their child-table locks with a short transaction-local lock_timeout. The explicit lock contract is:

claim takes FOR UPDATE OF claims SKIP LOCKED on queue_claim_heads while it advances the claim cursor and inserts the claim
rotate publishes the next lease slot with a compare-and-swap update on lease_ring_state
prune-ready takes FOR UPDATE on queue_ring_state and on the target queue_ring_slots row, proves the sealed slot has no active leases, no receipt claims without durable closure evidence, and no retained ready rows still at or ahead of their lane cursor, then takes bounded ACCESS EXCLUSIVE on the child partitions, rechecks those gates, and only then truncates
prune-leases derives the oldest initialized slot from lease_ring_state, locks the child partition with bounded ACCESS EXCLUSIVE, rechecks that the slot is not current, then truncates if it is empty
prune-claim-ring (added by ADR-023) takes FOR UPDATE on claim_ring_state and on the target claim_ring_slots row, proves every visible claim in the sealed slot has durable closure evidence, then takes bounded ACCESS EXCLUSIVE on the matching lease_claims_*, lease_claim_closures_*, and lease_claim_closure_batches_* partitions, rechecks for open claims, and only then TRUNCATEs them in lockstep. Open claims make prune skip until normal completion, normal non-success closure, or the separate receipt-rescue scans close them.

That order is deliberate. The TLA+ storage race / lock-order models cross-check the abstract claim, rotate, and prune ordering. The Rust prune paths also recheck their liveness gates after taking partition locks, which covers the MVCC visibility window that the lock-order model abstracts away.

Rotation and prune policy is also part of this decision:

lease and claim-ring segments rotate quickly because their churn is the remaining hot-path source
ready / terminal segments rotate more slowly than the lease and claim rings; deferred and DLQ rows are plain backlog/hold tables with their own promotion, retry, purge, and retention cleanup paths
prune walks sealed segments oldest-first
prune returns gracefully when a reader or writer still holds the segment beyond the short lock-timeout window, but it may queue briefly to avoid starvation under continuous parent-partition readers
long-lived readers can still pin a segment horizon, so operators are expected to run analytical reads on replicas and keep primary-side statement_timeout discipline

Ordinary queue-storage terminal history is therefore a rotation-and-prune story, not a row-by-row delete story. DLQ retention remains a bounded cleanup pass against the separate dlq_entries hold table, and the canonical compatibility path still has row-retention cleanup.

Hot-path requirements¶

The decision above pins two hot-path requirements that surface repeatedly in implementation:

Claim runs as a single server-side step: one SQL function locks queue_claim_heads, selects the oldest runnable segment-local entry for the shard-qualified lane, and appends either a lease_claims receipt or a materialized leases row. Dispatch must not round-trip between the cursor read and the claim insert.
Short successful completion carries the immutable claim-time job snapshot through the completion batcher so the terminal append does not reload ready_entries.
The completion batcher therefore owns a claim-time snapshot pass-through path: short completions append terminal rows from the already-carried immutable claim snapshot, while stale completions still lose via the (job_id, run_lease) guarded delete against the live execution row.
Local worker capacity is released when handler execution ends and the progress snapshot is captured; durable completion then continues through the detached completion batcher path. This keeps execution capacity tied to active handler work rather than to completion flush latency while leaving the run_lease-guarded rescue boundary unchanged.
Crash safety for the batcher relies on the normal rescue path, not an auxiliary replay log. If an in-memory completion batch is lost with the worker process, the live attempt remains visible to heartbeat/deadline rescue and is reclaimed that way.

Validation¶

Recorded local 5k-job runtime soak: 9,537 jobs/s, 3.671 ms pickup p50, 22.013 ms pickup p95, 417 exact final dead tuples (canonical runtime under the same workload: 9,686 jobs/s, 38.998 ms p95, dead tuples not sampled). The full validation record contains the command log, raw output, and per-table dead-tuple breakdown.

The phase-driven portable comparison harness lives in a separate repo: postgresql-job-queue-benchmarking. That harness records producer, subscriber, and end-to-end latency on a shared timebase while also sampling throughput, queue depth, and dead tuples over time. Recent runs place Awa ahead of pgque on end-to-end latency and on sustained throughput in clean-phase scenarios, while pgque holds a comparable dead-tuple profile (both are append-only / partition-rotated). See the cross-system comparison for the per-system architectural notes and AWA benchmarking for awa's own regression methodology.

The current pressure frontier after the split-head change is the lease plane: queue_lanes is no longer the dominant MVCC hotspot, but the mutable active_leases family still absorbs steady insert/delete churn and heartbeat updates. The current implementation now includes a short-job receipt path (lease_claims plus lazy materialization) that substantially reduces dead tuples for zero-deadline short jobs. Long-horizon profiling also showed that the append-only history alone was not enough: open-claim reads and rescue scans needed bounded access paths so they would not degrade into history scans. The original ADR-019 design used a bounded open_receipt_claims table for this; ADR-023 replaces it with partitioned lease_claims, explicit lease_claim_closures, compact lease_claim_closure_batches, live-set anti-joins over active partitions, and tiny per-slot rescue cursors in claim_ring_slots, eliminating the last per-claim MVCC churn source on the receipt plane. Further lease-plane work is still tracked in the lease-plane redesign spike. The remaining queue-level coordination controls are implemented as bounded claimers, queue striping (queue_stripe_count), and per-queue enqueue-head sharding (queue_meta.enqueue_shards). The archived bounded-claimers plan and queue-striping plan capture design history; current operator guidance lives in Queue storage tuning.

Spec-level safety is checked by the segmented-storage TLA+ family — AwaSegmentedStorage, AwaSegmentedStorageRaces, AwaStorageLockOrder, AwaSegmentedStorageTrace — under the storage correctness models. The TLA+ action → Rust function mapping records the correspondence.

Consequences¶

Positive¶

Dead tuples are bounded by the lease rotation window and the tiny lane_state cache, not by total queue history.
Queue throughput is now near-parity with the canonical runtime while still substantially reducing claim-tail latency under the benchmark workload.
DLQ becomes a first-class storage concern instead of an afterthought bolted onto the hot table model.
Retention moves from row-by-row cleanup toward partition rotation and prune.

Negative¶

This is a breaking storage redesign rather than an incremental tweak.
Admin and producer paths must become backend-aware instead of assuming the canonical hot/deferred tables are the only physical layout.
Queue storage has to replace some old row-rewrite maintenance patterns with storage-specific equivalents, such as claim-time effective priority aging instead of physically rewriting ready rows.
Long-running readers can still delay best-effort partition prune.

Alternatives Considered¶

Keep the canonical hot/deferred split¶

Rejected. It helps planner shape, but it does not remove the lifecycle-row MVCC churn that causes dead tuples on the hot path.

Rotate mutable canonical rows directly¶

Rejected. Rotating the same mutable state-machine rows preserves the core problem; it only spreads churn across more tables.

Append-only history plus a single global lease heap¶

Rejected. This improves queue-row churn, but the lease heap still bloats in proportion to total runtime churn.

Two user-facing storage modes¶

Rejected. The storage engine can use multiple physical table families without exposing multiple public queue models.

Relationship to Earlier ADRs¶

ADR-012 becomes historical background rather than the target architecture.
ADR-003 still defines the heartbeat/deadline rescue policy; queue storage only changes where those timestamps live.
ADR-014 still defines the user-facing progress model; queue storage changes the physical persistence path from dedicated columns to attempt_state and active_leases.