Distributed job queue

intermediateCommon atAnthropicStripeAmazonShopifyGitHubRead firstSchedulingConcurrencyIdempotencyPractise in the Sandbox →

A job queue lets a web request say “do this later” and return. The core mechanism is the lease (SQS calls it a visibility timeout): a worker claims a job, and the job is hidden from everyone else until the worker acks it or the lease expires. Expiry is how crashed workers are detected, so delivery is at least once and every job must be idempotent. Around that sit retries with exponential backoff and jitter, a dead-letter queue for jobs that never succeed, per-tenant fairness, and a scheduler for delayed and cron jobs. Each job costs a constant three store operations (enqueue, claim, ack), so the store’s write throughput is the design constraint.

The problem

Sending a receipt email, resizing an upload, generating a PDF, calling a slow partner API, running a nightly report. None of these should happen inside the user’s request: they’re slow, they fail transiently, and they can be retried. Sidekiq, Celery, SQS + Lambda, Google Cloud Tasks and GitHub’s and Shopify’s in-house systems all solve the same problem.

The jobs themselves are easy. The hard part is that workers die mid-job and dependencies fail in bursts. A job queue is mostly a set of answers to “what happens when that goes wrong”:

Goal	What it means	Pulls toward
Never lose a job	Once enqueue returns, the job runs eventually, through crashes and deploys	Durable store, leases, at-least-once
Don’t run it twice (or make twice harmless)	One charge, one email	Idempotency keys, conditional acks, dedupe on enqueue
Don’t make outages worse	Failures retry without stampeding the thing that failed	Backoff, jitter, retry budgets, DLQ
Be fair and timely	One tenant’s 1M-job backfill doesn’t delay everyone’s password resets	Priorities, per-tenant queues, concurrency caps

Requirements and scope

	In scope (typical)	Ask about
Functional	Enqueue a job (type, payload, queue, priority); run now, after a delay, or on a cron schedule. Retries, DLQ, cancel, inspect status.	Do callers need the result? Can jobs depend on other jobs? Do some jobs need ordering (per user)?
Delivery	At least once. Idempotent handlers. Optional dedupe key on enqueue.	Is there any job where a duplicate run is unacceptable, not just undesirable?
Scale	~50M jobs/day, 4× peaks, thousands of workers, many tenants.	Job duration range? Seconds, or hours?
Latency	Ready jobs start within ~1 s at p99; scheduled jobs within a few seconds of run_at.	Is there a priority class that must start in under 100 ms?
Availability	Enqueue must keep working when workers or downstream APIs are down.	Can enqueue be async (buffer in the app) if the store is down?
Out of scope	Workflow engines with DAGs and human steps (Temporal, Step Functions), stream processing.

The clarifying question that changes the most

“How long can a job run, and what does a duplicate run cost?” Jobs that take seconds and are naturally idempotent (resize this image to this key) can use a simple queue with a fixed visibility timeout. Jobs that take minutes to hours need heartbeats, and jobs with external side effects need idempotency keys passed to the external system. If the answer is “hours, with steps”, you are designing a workflow engine with checkpoints, not a job queue.

Back of the envelope

Back of the envelope

drag the assumptions

assumptions

jobs per day50Mpeak-to-average ratio4.00×average job duration (s)2.0 sconcurrent jobs per worker10fraction of attempts that fail2.00%job row size (bytes)1 KB

so you need

peak enqueues/s2.31K/s

store ops/s (enqueue + claim + ack, plus retries)7.08K/sone Postgres primary handles low thousands of these comfortably

jobs running at once (Little's law)4.63Karrival rate × time in system

workers needed at peak60230% headroom for retries and drains

storage for 7 days of job history350 GB

50M jobs/day is ~580/s on average, ~2,300/s at a 4× peak, which means ~7,000 store writes per second for enqueue, claim and ack. That is past what one Postgres primary does comfortably with the index churn of a hot jobs table, so you either shard queues across databases, or use a store built for it (Redis, SQS, Kafka-backed). Worker count comes from Little's law: concurrent jobs = arrival rate × duration.

What to say out loud: “Each job is three writes minimum, plus one per retry and heartbeat. At a few thousand jobs per second I’ll partition queues across store shards. Workers are sized by Little’s law: 2,300 jobs/s × 2 s means about 4,600 jobs in flight, so ~600 worker processes at 10 concurrent each, with headroom.”

API and data model

pseudocode: the contract

enqueue(queue, type, payload, opts) -> job_id
    opts = { run_at?, priority?, dedupe_key?, max_attempts = 8, timeout_s = 30, tenant_id }
claim(queue, worker_id, max_jobs) -> [ { job_id, payload, attempt, lease_token, lease_until } ]
heartbeat(job_id, lease_token) -> new lease_until      -- fails if the lease was lost
ack(job_id, lease_token)                               -- succeeded
nack(job_id, lease_token, error, retry_at?)            -- failed; queue decides retry or dead
schedule(name, cron_expr, queue, type, payload)        -- recurring

jobs(
    id, queue, tenant_id, type, payload, priority,
    state        ready | leased | scheduled | succeeded | dead | cancelled,
    run_at       -- next time it may be claimed
    attempts, max_attempts,
    lease_token, lease_until, leased_by,
    dedupe_key   UNIQUE per queue while not finished,
    last_error, created_at, finished_at
)
index (queue, state, priority, run_at)   -- the claim query reads only this

Two decisions hide in that sketch:

• state + run_at unify ready, delayed and retrying jobs. A retry is “set run_at to later”. A delayed job is “inserted with run_at in the future”. One index serves all of them, and the claim query is the same.
• The lease token. Every claim mints a new token. Heartbeat and ack must present it, so a worker whose lease expired (a “zombie” that’s still running) can’t extend or ack a job someone else now owns.

High-level design

Job queue: lifecycle of a job

step through

flowRun a jobWorker crashRetry → DLQScheduled + cron

Enqueue is a durable insert; a worker claims with a lease, runs, and acks.

queueemails

jobsend_receipt(order 42)

dedupe_keyreceipt:42

A web request enqueues a job instead of doing slow work inline. The dedupe key stops a retried web request from enqueuing it twice.

↺◀▶ Play▶1 / 5

Component	Role	Why it’s there
Queue API	Enqueue, claim, heartbeat, ack. Thin, stateless.	Keeps workers and producers ignorant of the store; lets you swap or shard it.
Job store	Durable job rows, indexed by (queue, state, run_at). Postgres, Redis, or a managed queue (SQS).	Durability is the product. Its write rate is the scaling limit.
Workers (×N)	Long-running processes that claim, run, heartbeat and ack. A pool per queue.	Scale per queue independently; isolate slow job types from fast ones.
Scheduler	Turns cron entries into jobs; one leader at a time.	Recurring work without every app server running its own timer.
Lease reaper	Returns expired leases to ready (or the claim query does it inline).	How a crashed worker’s job comes back.
Dead-letter queue	Jobs that exhausted retries, with error history.	Stops infinite retry loops; gives humans a place to look.

Deep dive: leases, heartbeats and redelivery

A queue can’t ask a worker “are you still alive?” It only knows when it last heard from it. So a claim is a lease with an expiry: if the worker doesn’t ack (or heartbeat) by then, the queue assumes it died and makes the job visible again. That one rule gives you crash recovery and also causes most of the bugs.

Play with the lease length. Start without heartbeats and a 6-tick timeout, then fix it two different ways.

Leases, crashes and redelivery

simulator

new jobs

workers = 3visibility timeout = 6 ticks

worker 1

worker 2

worker 3

visible (ready)nonebacking offnonedead lettersnone

completed: 0 / 12lease expiries: 0ran twice: 0stale acks rejected: 0

running (leased)ackedfinished after its lease expiredcrashed / failed

j3 takes 11 ticks but the lease is 6. The queue assumes the worker died, makes j3 visible again, and a second worker starts it while the first is still running. The job runs twice, and the first worker's late ack is rejected. Every attempt times out the same way, so j3 burns its attempts and lands in the dead-letter queue even though it never actually failed. Turn heartbeats on, or raise the timeout above the longest job. Worker 1 dies at t=14. Its job is not lost: when the lease runs out, it is redelivered to another worker.

↺◀▶ Run▶t = 0 / 60

The tension the sim shows:

Lease setting	A worker crashes	A job runs long
Short timeout, no heartbeat	Recovered fast	Redelivered while still running: runs twice, and may never ack
Long timeout, no heartbeat	Job stuck until the timeout (minutes)	Fine
Short timeout + heartbeat	Recovered within one timeout	Fine: the lease keeps extending

That’s why mature queues heartbeat: SQS’s ChangeMessageVisibility (default timeout 30 s, max 12 h), Cloud Tasks’ dispatch deadlines, Temporal’s activity heartbeats. A worker’s run loop looks like this:

pseudocode: run one claimed job with a heartbeat

run(job):
    start background timer every lease_s / 3:
        ok <- queue.heartbeat(job.id, job.lease_token)
        if not ok: cancel the job's work          -- lease lost: someone else may own it now
    try:
        result <- handler(job.payload, idempotency_key = job.id)
        queue.ack(job.id, job.lease_token)         -- rejected if the token is stale
    catch error:
        queue.nack(job.id, job.lease_token, error)
    finally:
        stop timer

Two subtleties:

• A heartbeat is not proof of progress. A worker stuck in an infinite loop heartbeats forever. Add a hard timeout_s per job type, enforced by the worker and checked by the reaper (started_at + timeout_s).
• Losing a lease doesn’t stop the old worker. A GC pause or network partition can make a healthy worker look dead. Its work may still land. That’s the fencing token problem: the lease token must be checked by whatever the job writes to, or the job must be idempotent. Usually the second.

Claiming without contention

In Postgres, the claim is one statement. FOR UPDATE SKIP LOCKED (Postgres 9.5+, also MySQL 8) makes each worker skip rows another worker is claiming, instead of queuing behind its lock:

pseudocode: claim up to N jobs atomically (SQL)

UPDATE jobs SET state = 'leased', attempts = attempts + 1,
       lease_token = gen_random_uuid(), lease_until = now() + interval '30 s', leased_by = :worker
WHERE id IN (
    SELECT id FROM jobs
    WHERE queue = :q
      AND ( (state IN ('ready', 'scheduled') AND run_at <= now())
         OR (state = 'leased' AND lease_until < now()) )      -- expired leases count as ready
    ORDER BY priority DESC, run_at
    LIMIT :n
    FOR UPDATE SKIP LOCKED
)
RETURNING id, payload, attempts, lease_token, lease_until;

Without SKIP LOCKED, a hundred workers polling the same queue all block on the same first row. With Redis, the equivalent is moving an id from a ready list to an in-flight sorted set scored by lease expiry, atomically (LMOVE plus a script); with SQS, ReceiveMessage does it for you.

Exactly once is an illusion. A job can always run, have its effect, then crash before the ack. What you can build is at-least-once delivery + idempotent effect: pass job.id (or a business key) as an idempotency key to anything external, and write “done” markers in the same transaction as local effects. For the enqueue side, the same dual-write problem as in event-driven systems applies: if the job row lives in the same database as the business data, insert it in the same transaction (“transactionally staged jobs”), so a rolled-back order never sends a receipt.

Deep dive: retries, backoff and jitter

When a dependency fails, every job that touches it fails at about the same time. If they all retry on the same schedule, they hit the dependency in synchronized waves just as it’s trying to recover. Compare the policies below. Watch the “peak after recovery” and “still failing” columns.

Retry storms: backoff with and without jitter

simulator

reshuffle

failing jobs = 300outage = 6 scapacity = 40 /s

peak after recovery: 156 / 0.5 stotal calls: 2040wasted (failed) calls: 2000260 still failing at 60 s

policy	peak after recovery	calls	all done
fixed 1 s interval	156	6154	30.5 s
exponential, no jitter	156	2040	260 left
exponential + full jitter	44	1654	27.5 s
exponential + equal jitter	60	1598	29.5 s
decorrelated jitter	53	1797	28.5 s

retry calls in a 0.5 s bucketover capacity / outagewhat the server can serve

Exponential backoff reduces how often each client retries, but every client failed at the same moment, so they all wake at the same moment too: synchronized spikes far above capacity, with mostly empty time between them.

The formulas, from AWS’s backoff analysis:

pseudocode: next retry time

exp       = min(cap, base * 2 ^ attempt)
none      : sleep = exp                                  -- synchronized waves
full      : sleep = random(0, exp)                       -- spreads evenly; least total work
equal     : sleep = exp / 2 + random(0, exp / 2)         -- guaranteed minimum wait
decorr    : sleep = min(cap, random(base, prev_sleep * 3))

run_at <- now + sleep
if attempts >= max_attempts or error is permanent (400, validation): state <- dead

Retry policy is more than a formula:

• Classify errors. Retry timeouts, 429s and 5xx. Don’t retry a 400 or a deserialization error: dead-letter it immediately. Honor Retry-After when the dependency sends one.
• Bound the total. Sidekiq’s default is 25 retries over about 20 days; most queues should give up much sooner (8 attempts over an hour) and dead-letter.
• Retry budgets. Cap retries to, say, 10% of a queue’s throughput, so a dependency outage can’t turn your queue into 10× the normal load. Pair with a circuit breaker per dependency so workers stop calling something that’s down.
• Poison jobs. A job that crashes the worker process (OOM on a huge input) never even reaches nack. Count attempts at claim time, not at failure time, or it loops forever.

Deep dive: priorities, fairness and scheduling

Priorities. Separate queues per class (critical, default, bulk) with dedicated worker pools are simpler and more predictable than one queue with a priority column. A priority column with strict ordering starves low priorities under sustained load; weighted polling (Sidekiq’s queue weights: check critical 6× as often as bulk) avoids that.

Fairness across tenants. One customer enqueues a million-row export; everyone else’s jobs wait behind it in FIFO order. Options, from simple to strong:

Technique	How	Trade-off
Per-tenant concurrency cap	At claim time, skip tenants already running ≥ k jobs	Simple; needs a running count per tenant
Round-robin across tenants	Claim from a rotating list of tenants with ready jobs	Fair by count, not by cost
Weighted fair queuing	Each tenant has a virtual clock advanced by job cost ÷ weight; claim the lowest	Fair by cost and tier; more state
Shuffle sharding	Each tenant maps to a few of many worker pools	A noisy tenant can only hurt the few pools it shares

Delayed jobs and timing wheels. A delayed job in a database is a row with a future run_at; the index makes “what’s due?” a range scan. In memory, a scheduler that holds millions of timers uses either a heap (O(log n) insert and pop) or a timing wheel: a circular array of buckets, one per tick, where a timer due in k ticks goes in bucket (now + k) mod size. Insert and expire are O(1); hierarchical wheels (seconds, minutes, hours) cover long delays. Kafka uses hierarchical timing wheels for request timeouts, and Netty’s HashedWheelTimer is the same idea. SQS supports per-message delays up to 15 minutes; longer delays need your own scheduler.

Cron without duplicates. Every scheduler instance could fire 0 2 * * *, so only one may. Two standard approaches, often combined:

pseudocode: one cron tick, safe with several scheduler instances

every second:
    if not holds_leader_lease("cron"):           -- advisory lock, or a lease row renewed every 5 s
        try_acquire_leader_lease("cron"); continue
    for entry in cron_entries where entry.next_fire <= now:
        INSERT INTO jobs (queue, type, payload, dedupe_key)
            VALUES (entry.queue, entry.type, entry.payload, entry.name + "@" + entry.next_fire)
            ON CONFLICT (dedupe_key) DO NOTHING  -- a second leader during failover is harmless
        entry.next_fire <- next occurrence after entry.next_fire   -- in the entry's time zone

The unique key on (name, scheduled time) is what makes leader election safe; the lease only makes it efficient. Decide what happens to runs missed during downtime (run once to catch up, or skip) and how daylight saving affects “2:30 AM daily” (see Time handling).

Failure modes

What breaks	What you see	Design response
Worker crash / OOM / deploy	Job stuck as leased	Lease expiry → redelivery; count attempts at claim; graceful shutdown drains or releases leases
Job longer than lease	Same job running on two workers	Heartbeats; per-type timeouts; lease token checked on ack
Dependency outage	Failure spike, then retry waves	Exponential backoff + full jitter; retry budget; circuit breaker; honor Retry-After
Poison job	Same job failing every attempt	Max attempts → DLQ; classify permanent errors; alert on DLQ depth
Noisy tenant	Other tenants’ jobs delayed	Per-tenant concurrency caps, fair claiming, separate pools
Store hot spot	Claim latency rises, lock contention	SKIP LOCKED, batch claims, partition queues across shards, prune finished rows
Table bloat (Postgres)	Index scans slow over time	Move finished jobs to a history table; partition by day; autovacuum tuning
Scheduler split-brain	Cron job runs twice	Unique (name, fire time) key; leader lease with fencing
Enqueue in a rolled-back transaction	Email for an order that doesn’t exist	Enqueue in the same DB transaction, or via an outbox

What it costs

Operation	Time	Space
Enqueue	O(log n) index insert; one durable write	O(payload) per job
Claim (SKIP LOCKED, indexed)	O(log n + k) for k jobs	—
Heartbeat / ack	O(1) by primary key; one write each	—
Retry	One update setting run_at	Error history per attempt
Delayed timers in memory	Heap O(log n); timing wheel O(1) insert/expire	O(timers) (+ O(wheel size))
Total store load	≈ 3 writes/job + retries + heartbeats/(lease/3)	O(jobs retained) ≈ 350 GB for 7 days at 50M/day × 1 KB
Workers	Little’s law: rate × duration ÷ concurrency per worker	—

In the interview

A good 45-minute arc:

1. Clarify (5 min). Job duration range, duplicate cost, priorities, multi-tenancy, delayed/cron needs, throughput.
2. The core loop (10 min). Durable enqueue, claim with a lease, ack. Draw the job state machine (ready → leased → succeeded / scheduled / dead). Say “at least once” and “idempotent” early.
3. Failures (10 min). Worker crash → lease expiry. Long jobs → heartbeats + lease token. Retries with backoff and jitter; DLQ; permanent vs transient errors.
4. Scale and fairness (10 min). Claim contention (SKIP LOCKED, batching), sharding queues, per-tenant fairness, priority pools.
5. Scheduling (5-10 min). Delayed jobs via run_at; cron with a leader lease plus a unique key; timing wheels if they push on in-memory timers.

Follow-ups to expect: “Guarantee a job runs exactly once.” You can’t across a crash; make it idempotent and dedupe. “Jobs for one user must run in order.” Per-key serialization: a lock or a per-key queue (SQS FIFO message groups), at the cost of parallelism for that key. “A job takes 6 hours.” Heartbeats and checkpoints, or break it into a chain of smaller jobs. “How do you deploy workers without killing jobs?” Stop claiming on SIGTERM, finish or release leases within a grace period.

Check yourself

Check yourself

pick one

Workers lease jobs for 30 seconds with no heartbeat. A report job normally takes 10 s but sometimes 45 s. What happens on a slow run?

AThe job fails with a timeout errorBAt 30 s the job becomes visible again and a second worker starts it while the first is still runningCThe queue waits for the first worker since it has not acked or nackedDThe job moves straight to the DLQ

Check yourself

pick one

An email provider is down for 2 minutes. 50,000 email jobs fail and each retries with pure exponential backoff (1 s, 2 s, 4 s ...). What goes wrong when the provider recovers?

ANothing; exponential backoff is the standard fixBAll 50,000 retry at nearly the same instants, so the provider gets synchronized spikes and may fall over againCJobs retry too slowly and miss their deadlineDThe jobs are dead-lettered

Check yourself

pick one

Three scheduler instances run for availability. During a network blip two of them both believe they hold the leader lease at 02:00. How do you prevent the nightly billing job from running twice?

AShorter lease durationsBRun only one scheduler instanceCInsert the cron run with a unique key of (job name, scheduled time) so the second insert is a no-opDCheck the clock on both instances

Go deeper

• AWS Builders’ Library: Timeouts, retries, and backoff with jitter and Exponential backoff and jitter: the analysis behind full and decorrelated jitter, plus retry budgets.
• Amazon SQS: Visibility timeout: leases as a managed service, with limits and the heartbeat API.
• PostgreSQL: SELECT, the locking clause: FOR UPDATE SKIP LOCKED and why it suits queue tables. Brandur’s Transactionally staged job drains covers enqueueing safely inside a transaction.
• Varghese & Lauck’s timing wheels, summarized: O(1) timers for millions of delayed tasks. Also Sidekiq: Error handling for a real retry schedule.

Concept pages to drill: Scheduling · Concurrency · Idempotency · Heap · State machines · TTL and expiry

Related

Scheduling (concept)Priority queues, timers and fair scheduling.

Event-driven order pipelineLogs, consumer groups, the outbox and sagas.

Webhook deliveryA job queue whose jobs are HTTP calls to strangers.

Notification systemPer-channel queues, provider failover and rate caps.