rustdistributed systemssystems

Building a Reliable Job Queue in Rust: Leases, Idempotency, Retries, and the Limits of Exactly-Once

Leases, idempotency, retries, and why “exactly once” is the wrong promise

Chaitanya

A background-job queue looks simple when nothing fails.

A client submits a job. An API stores it. A worker picks it up, performs the operation, and marks it complete.

Client → API → Database → Worker → External serviceplain text

That description hides almost every interesting engineering problem.

What if the worker dies after claiming a job? What if the external operation succeeds, but the worker crashes before recording success? What if an expired worker resumes after another worker has taken ownership?

And what stops retries—or async concurrency itself—from overwhelming the system?

I built ReliableQ to explore those questions.

ReliableQ is a PostgreSQL-backed job system written in Rust. The finished system uses transactional claims, expiring leases, token-fenced ownership, idempotent downstream effects, bounded retries, dead-job handling, bounded concurrency, and graceful shutdown.

But I did not begin with that feature list.

I began with a deliberately naive queue. Then I reproduced one failure at a time and added the smallest mechanism that addressed it.

Reliability mechanisms make more sense as answers to demonstrated failures than as items on an architecture checklist.

The final guarantee is deliberately narrow:

Durable submission
+ at-least-once execution
+ token-fenced leases
+ a stable idempotency key
= recoverable jobs with one committed charge per jobplain text

That is not universal exactly-once execution. It is a guarantee with a boundary—and one that can be tested.

TL;DR

Once ReliableQ returns 202 Accepted, the job has committed to PostgreSQL.

Workers claim due jobs with FOR UPDATE SKIP LOCKED. Every running job has an expiring lease, so another worker can recover it if its owner disappears. Lease tokens prevent stale workers from renewing or finalizing after ownership changes.

Leases do not prevent a handler from running twice. If a charge succeeds and the worker crashes before recording success, the job must be retried. ReliableQ reuses a stable idempotency key so that both requests represent the same logical operation.

Transient failures retry with exponential backoff and jitter. Permanent failures and exhausted retries enter an inspectable DEAD state. A semaphore bounds in-flight work inside each worker process.

The job may execute more than once. The bundled charge operation commits once.

Start with counts, not slogans

Let j represent one logical job.

A(j) = number of attempts
H(j) = number of handler executions
C(j) = number of committed charges
F(j) = number of successful finalizationsplain text

During an ordinary execution, every count is one.

After a crash, the result may instead be:

A(j) = 2
H(j) = 2
C(j) = 1
F(j) = 1plain text

The handler ran twice. Only one charge was committed, and the job reached SUCCEEDED once.

This is what phrases such as “exactly once” often blur. Delivery, execution, finalization, and externally visible effects are different events.

ReliableQ does not attempt to guarantee that the handler runs once. That promise becomes impossible to defend as soon as a worker can crash after contacting another service.

Instead, ReliableQ permits repeated execution and controls the durable effect:

C(j) = 1plain text

That guarantee applies within the bundled charge service’s idempotency boundary.

The naive queue

The first version contained four runtime components:

Client → API → PostgreSQL ← Worker → Charge serviceplain text

The API inserted a PENDING job. A worker changed it to RUNNING, called the charge service, and then changed it to SUCCEEDED.

Under normal conditions, it worked.

Then I started terminating processes between those steps.

Commit before acknowledging

The first contract was:

Once `POST /v1/jobs` returns `202 Accepted`, the job has committed and will not silently disappear.

The order is therefore:

Validate → Insert → Commit → Return 202plain text

Returning 202 before the commit would let the API acknowledge a job that never became durable.

This guarantees acceptance, not success. PostgreSQL and workers must eventually recover, and a permanently invalid job may finish in DEAD.

Claim jobs transactionally

A separate read followed by an update creates a race:

Worker A reads job 42 as PENDING
Worker B reads job 42 as PENDING
Worker A sets it to RUNNING
Worker B sets it to RUNNINGplain text

ReliableQ claims jobs inside a short PostgreSQL transaction using:

FOR UPDATE SKIP LOCKEDplain text

The transaction selects due jobs, locks them, changes their state, increments their attempts, assigns ownership, and records the attempts. Other workers skip locked rows and continue looking for work.

The transaction commits before any network call. A database lock should not be held while waiting on an unpredictable dependency.

Transactional claiming prevents competing claims during the transaction.

It does not recover a job after its owner disappears.

Failure one: the worker dies

The first deliberate crash produced this state:

Worker claims job
Job becomes RUNNING
Worker crashesplain text

The job still existed, but no worker considered it eligible. Durability without recovery had created permanently stranded work.

A flag such as is_processing = true cannot distinguish a healthy worker from one that disappeared yesterday.

ReliableQ therefore represents ownership as a lease.

Every claim records a lease token, expiration time, worker ID, and attempt number. The worker renews the lease while processing. If it dies, renewal stops, the lease expires, and another worker can reclaim the job.

Worker A claims with token α
Worker A crashes
Lease α expires
Worker B reclaims with token βplain text

This turns permanent ownership into temporary ownership.

It also creates a harder problem: an expired worker may not actually be dead.

Failure two: the stale worker returns

A worker can stop renewing because it was paused, suspended, starved of CPU, or isolated from PostgreSQL.

Worker A owns token α
Worker A pauses
Lease α expires
Worker B reclaims with token β
Worker A resumesplain text

Worker A still has the job in memory. Without another safeguard, it may overwrite state produced by worker B.

ReliableQ fences every ownership-sensitive update with the current token:

UPDATE jobs
SET status = 'SUCCEEDED',
    lease_token = NULL,
    lease_expires_at = NULL
WHERE id = $1
  AND status = 'RUNNING'
  AND lease_token = $2;plain text

Worker A submits token α, but the row now contains β. Its update affects zero rows.

The same guard protects renewal, successful finalization, retry scheduling, and transition to DEAD.

But this token only fences ReliableQ’s PostgreSQL row. It cannot undo a request that worker A already sent elsewhere.

Failure three: the charge succeeded, but nobody knows

This is the most important failure window in the project:

Worker sends charge request
Charge service commits
Worker crashes
Job is never marked SUCCEEDED
Lease expires
Another worker retriesplain text

The second worker cannot know whether the charge happened.

If it does not retry, it may lose the operation. If it retries, it may create a duplicate charge.

A longer lease only delays the decision. Marking the job successful before charging creates the opposite failure: a crash would permanently skip the charge.

A local PostgreSQL transaction also cannot atomically include an unrelated HTTP service.

The system must retry, but the receiver needs to recognize the retry as the same logical operation.

Make the operation identifiable

ReliableQ derives an idempotency key from the job ID:

reliableq:charge:<job_uuid>plain text

Every attempt sends the same key.

The charge service stores it under a unique constraint:

idempotency_key TEXT NOT NULL UNIQUEplain text

A new key creates the charge. The same key and payload return the original charge. The same key with a different payload returns a conflict. Concurrent requests using one key create one row.

The database constraint is the enforcement mechanism. A SELECT followed by an INSERT would leave a race in which two requests both observe that no row exists.

Now the ambiguous execution is safe:

Attempt 1 commits the charge and crashes
Attempt 2 sends the same key
The service returns the original charge
Attempt 2 finalizes the jobplain text

The result is:

A(j) = 2
H(j) = 2
C(j) = 1
F(j) = 1plain text

The job ran twice. The charge did not.

This guarantee is intentionally scoped. ReliableQ cannot automatically make an arbitrary payment provider, email API, or legacy service idempotent.

Retries are a scheduling policy

Once a retry is safe, the next question is when it should happen.

ReliableQ separates failures into three groups:

Transient: connection failures, timeouts, 408, 429, and 5xx responses.
Permanent: invalid business input, unsupported operations, and definitive rejection.
Ambiguous: the worker cannot determine whether the effect committed.

Ambiguous failures must be retried because the operation may not have happened. They must use the same idempotency key because it may have happened.

Immediate retries create a feedback loop during an outage. ReliableQ instead uses capped exponential backoff with full jitter:

cap(n) = min(max_delay, base_delay × 2^(n − 1))
delay  = Uniform(0, cap(n))plain text

The delay is persisted, and PostgreSQL time determines when the job becomes eligible again. Jitter keeps multiple workers from synchronizing their retries.

Backoff does not make a failing operation succeed. It controls how aggressively the system asks again.

Know when to stop

Infinite retry is not reliability.

A permanent failure or exhausted retry budget sends a job to DEAD. ReliableQ retains its payload, sanitized error, timestamps, and attempt history.

Dead jobs are never claimed automatically. An operator can inspect and explicitly replay one after correcting the underlying problem. Replay preserves the job ID and idempotency key.

DEAD is an operational boundary:

Automatic recovery has stopped. Intervention is now required.

Bound the work before it bounds you

Async code makes it easy to create more work than a process can safely execute.

If a worker claims 1,000 jobs and spawns 1,000 tasks against a service that can handle 20 requests, it has copied the durable queue into memory.

ReliableQ uses a Tokio semaphore to bound active handlers. The worker only claims as many jobs as it has available permits.

in_flight_jobs ≤ configured_concurrencyplain text

That is a per-process limit, not a fleet-wide limit.

Shutdown follows the same ownership discipline. The worker stops claiming, continues lease renewal during a grace period, finalizes completed work, and then lets unfinished leases expire for recovery elsewhere.

It never marks unfinished work successful merely to exit cleanly.

Test the gaps, not only the functions

ReliableQ’s seeded chaos suite processes 120 jobs using three concurrent workers while injecting crashes at three named points:

after_claim_before_effect
after_effect_before_finalize
during_finalizeplain text

After the system settles, the suite checks PostgreSQL directly:

Every job reaches SUCCEEDED or DEAD.
No stale owner finalizes a reclaimed job.
Attempt budgets remain valid.
At most one charge exists per idempotency key.
In-flight work stays within configured capacity.

The project currently has 110 passing tests across unit, repository, API, integration, and chaos suites.

The repository also contains a reproducible demo that kills a real worker with kill -9, waits for another worker to reclaim the job, and proves that two attempts created exactly one charge.

A failure-handling mechanism is not complete merely because its success path compiles.

What the benchmarks revealed

After the correctness work was complete, I built a separate benchmark harness around the release binaries.

The published quick profile contains 126 runs across ten scenarios. Every run passed its correctness gate.

On an Apple M3 laptop with eight logical CPUs and 16 GB of memory:

Durable ingestion peaked at approximately 4,770 committed submissions per second.
Zero-latency execution peaked at approximately 493 completed jobs per second at worker concurrency 8.
Raising the same process to concurrency 16 reduced throughput to approximately 369 jobs per second.
A real worker killed with kill -9 recovered in approximately 5.5 seconds with a five-second lease.
At a 50% transient-failure rate, retry amplification reached approximately 1.93 attempts per job.
Concurrent idempotency tests committed exactly one charge per key in every run.

These are local quick-profile measurements, not universal capacity claims. The sample sizes are modest, Docker Desktop introduces noise, and the full benchmark profile has not been published.

The useful result is not just the largest number. It is the shape of the system under pressure.

Throughput improved as concurrency increased from 1 to 8, then regressed at 16. That creates a concrete next investigation: measure database-pool acquisition time and claim/finalize contention before changing defaults.

The harness also found an unexpected measurement bug. The laptop slept during an early run. PostgreSQL wall-clock timestamps included the sleep interval, while the harness’s monotonic timer did not, producing impossible multi-hour tail latencies.

A new correctness check now rejects latency samples that exceed their run’s monotonic window.

Even the benchmark needed failure detection.

Every guarantee has a boundary

ReliableQ’s guarantees can be stated without pretending their boundaries disappear.

Durable acceptance

Commit before returning 202 ensures an acknowledged job remains stored. The boundary is PostgreSQL durability.

Exclusive claims

Row locks and SKIP LOCKED prevent simultaneous claims during the claim transaction. The boundary is that PostgreSQL transaction.

Recovery after worker failure

Expiring leases make abandoned jobs eligible for another worker. The guarantee assumes database availability and worker liveness.

Safe finalization

Lease-token predicates prevent stale owners from updating ReliableQ’s job row. They do not fence unrelated external systems.

One committed charge

A stable key and unique constraint prevent retried attempts from creating another bundled charge. The boundary is the charge service’s database.

Controlled retry pressure

Attempt budgets, backoff, and jitter prevent infinite or immediate retries. The boundary is the configured retry policy.

Bounded local execution

A semaphore bounds active handlers. The boundary is one worker process.

A mechanism without its boundary is easy to overstate.

What ReliableQ does not guarantee

ReliableQ does not provide:

Exactly-once handler execution.
Exactly-once HTTP delivery.
Automatic idempotency for arbitrary external systems.
Atomic commits across PostgreSQL and an unrelated service.
A global concurrency limit across the worker fleet.
Multi-region ordering or failover.
Priorities, fairness, workflows, or job dependencies.
Eventual success for a permanently invalid operation.

It also does not claim that leases prevent all overlapping execution.

A paused worker can resume after its lease expires. Fencing rejects its stale database mutation. Idempotency protects the bundled external effect. Those are separate mechanisms protecting separate boundaries.

Conclusion

ReliableQ began as a database row and a polling loop.

Every major mechanism entered the design because a failure violated an invariant:

Uncommitted acknowledgement     → commit before 202
Competing claims                → row locks and SKIP LOCKED
Stranded RUNNING job            → expiring lease
Paused stale worker             → token fencing
Committed charge followed by crash → idempotency
Dependency outage              → backoff and jitter
Permanent failure              → DEAD state
Slow dependency                → bounded concurrency
Mechanism interaction          → seeded chaos testingplain text

The method is repeatable:

State the invariant.
Identify the vulnerable boundary.
Reproduce the failure.
Add the smallest mechanism that addresses it.
State what the mechanism still cannot guarantee.
Test the complete system under failure again.

ReliableQ does not claim exactly-once execution.

It makes a narrower statement:

Once a job is accepted, it remains durable. Workers may attempt it more than once. Expiring token-fenced leases make abandoned work recoverable, and the bundled idempotent charge service ensures repeated attempts produce one committed charge.

That statement is less impressive than “exactly once.”

It is also defensible.

The complete implementation, failure lab, benchmark report, architecture decisions, chaos suite, and terminal demo are available in the ReliableQ repository.