task-queue

How it is built

Architecture overview

A task queue decouples the code that asks for work from the code that does it. Producers put a message (a job description, an event) into a broker and move on; workers take messages out, do the work and acknowledge. The system exists to make three promises that a plain in-memory list cannot: a message that was accepted is not lost when a process or machine dies, a message is handed to one worker at a time and comes back if that worker disappears, and a slow or failing consumer does not take the producers down with it. The price is the usual one for distributed delivery: after a failure a message may be delivered twice, so the safe contract is at-least-once delivery plus idempotent handlers. RabbitMQ and Amazon SQS are the general-purpose brokers; Celery, Sidekiq, asynq and BullMQ are job-queue frameworks that wrap a broker (often Redis) with retries, scheduling and priorities.

Parts:

• Durable store — accepted messages are on disk before the producer hears "ok" — Write-ahead log, built on Group commit for throughput
• Replication — the queue survives the loss of a node — Raft, built on Leases, Exponential backoff with jitter and State-machine snapshots
• Ready and delayed ordering — which message is next, and when does a delayed one become due — d-ary heap for priorities, Hierarchical timing wheel for timers
• In-memory hand-off — producers and consumer threads exchange messages without locks — MPMC bounded queue
• Routing — decides which queues a published message goes to — topic-matching-trie (no page yet)
• Fairness and back-pressure — no tenant starves the others, no consumer drowns — fair-queuing (no page yet), credit-based-flow-control (no page yet)
• Delivery semantics — retries, duplicates and poison messages — Idempotency keys, Exponential backoff with jitter, Dead-letter queue

 producer ──publish──► router ──► queue (leader) ──replicate──► followers (Raft, majority)
   ▲   ◄─confirm after   (topic     │  ▲   WAL + group commit
   │     quorum write)    trie)     │  └─ ready heap / timer wheel (priority, delay)
   │                                ▼
   │              credit window ──► worker 1..n ──ack──► queue deletes
   │                                   │
   └── idempotency key ◄── result      └─ no ack before timeout ─► redelivery (backoff)
                                                      │ after N attempts
                                                      ▼
                                              dead-letter queue

There are two products of one design: the broker (one logical service, correctness of storage and ordering matters) and the worker fleet (many processes, throughput and idempotency matter). The broker owns delivery state; the workers own side effects, and that is why side effects must tolerate repeats.

How the parts fit together

Durable store

The unit of durability is the Write-ahead log: a message is appended to a checksummed sequential log and flushed before the producer is told it was accepted. After a crash the broker replays the log to rebuild the queue contents and the set of messages already acknowledged. Because a flush per message would cap throughput at the disk's flush rate, brokers use Group commit: all messages that arrived while the last flush was running share the next one, so throughput grows with concurrency while each producer still waits about one flush. This is also the main latency knob: a broker that acknowledges before the flush is faster and can lose the most recent messages on a power failure; the choice is a per-queue setting in most systems.

Replication

One disk is not enough for a queue that should survive a machine. RabbitMQ's quorum queues replicate each queue with Raft: the leader appends to its log, followers copy, and an entry is committed once a majority has it. The effects on the contract are concrete: publisher confirms are issued only after a message has been replicated to a quorum of members (source: RabbitMQ quorum queues documentation), so "confirmed" means "survives the loss of a minority of nodes". Raft elects one leader per term and followers notice a dead leader by missing heartbeats; a leader's authority behaves like a Lease, bounded in time. Followers and clients retry with Exponential backoff with jitter so that they do not stampede a recovering node. The log cannot grow forever: State-machine snapshots save the queue state at a log index so the older prefix can be deleted. The cost of replication is write amplification and extra latency per message, which is why RabbitMQ's documentation advises against quorum queues for short-lived, high-churn queues and suggests reviewing the topology above roughly 5,000 quorum queues (source: same page).

Ready and delayed ordering

A queue needs to answer "which message next" fast. Plain FIFO is a log with a head pointer. Priority queues need a heap: a d-ary heap with d = 4 halves the depth of a binary heap and keeps siblings in one cache line, which matters when the heap holds millions of ready messages. Delayed delivery ("run this in 10 minutes"), retry timers and visibility timeouts are all timers, and a queue can hold millions of them. A Hierarchical timing wheel buckets timers by expiry in a few wheels of slots, so insert and cancel cost O(1) and expiry work is proportional to the timers that really fire. Retry delays are the heaviest user: every failed message creates a timer that is usually cancelled or replaced.

In-memory hand-off

Inside the broker process, publisher threads, the log writer and the consumer-delivery threads exchange messages through queues. A lock per message would make the lock the bottleneck, so the hot path uses a MPMC bounded queue: an array ring in which every slot carries a sequence number and each enqueue or dequeue takes one compare-and-swap. Bounded matters: a full ring is a signal to slow the producers down, not a reason to grow memory. This is an in-process structure only. It does not replace the durable store; it feeds it.

Routing

Producers rarely name the final queue. In AMQP-style brokers a message carries a routing key such as orders.eu.created, and consumers bind queues with patterns where * matches one word and # matches any number. Matching a key against thousands of bindings by scanning is too slow, so brokers keep a topic-matching-trie (no page yet): a trie over the dot-separated levels with wildcard edges, giving a lookup cost that depends on the key length and the matching branches, not on the number of bindings. Systems that only have named queues (SQS, Celery over Redis) skip this part, which is one reason they are simpler.

Fairness and back-pressure

Two different protections share this part. Fairness keeps one tenant or one queue from using all workers: fair-queuing (no page yet), such as deficit round robin, serves queues in turn with weights, so a flood of low-priority jobs from one customer cannot delay everyone else. Flow control keeps a fast sender from burying a slow receiver: with credit-based-flow-control (no page yet) the receiver grants a window, and the sender stops when it is used up. In a queue this appears as the consumer prefetch count: a worker is sent at most N unacknowledged messages. A prefetch of 1 gives perfectly even work for uneven tasks but wastes a round trip per message; a large prefetch hides latency but lets one slow worker hold messages that idle workers could have processed.

Delivery semantics

The broker hands a message to a worker and starts a clock. If the worker acknowledges, the message is deleted. If the clock runs out first, the message returns to the queue. Amazon SQS calls this the visibility timeout: a received message stays in the queue but is hidden from other consumers, 30 seconds by default, extendable per message with ChangeMessageVisibility (source: SQS developer guide). Celery's Redis transport does the same with a default visibility timeout of one hour (source: Celery documentation). Consequences:

• A worker that crashes after doing the work but before acknowledging causes a second run. Celery states this trade-off directly: by default it acknowledges before running the task so a started task is never run again, and with acks_late it acknowledges after, which is only safe for idempotent tasks (source: Celery task documentation).
• Therefore the handler must be repeatable: an Idempotency key stored with the result lets the second run return the first run's outcome instead of charging a card twice.
• Failed jobs are retried with Exponential backoff with jitter. Sidekiq retries 25 times over about 21 days, then moves the job to a Dead set where it stays for 6 months before being discarded (source: Sidekiq wiki, Error Handling).
• A message that keeps failing is a poison message. After a bounded number of deliveries it moves to a Dead-letter queue; SQS does this through a redrive policy with maxReceiveCount, and the message keeps its original enqueue timestamp so the dead-letter queue's retention period should be longer than the source queue's (source: SQS developer guide, dead-letter queues).

Data and control flow

One job from submit to done:

1. The producer publishes with a routing key (or to a named queue) and, if the job must not run twice, an idempotency key.
2. The router picks the queues; the leader appends the message to its log. Group commit batches it with others.
3. Followers acknowledge the entry; once a majority has it, the leader confirms to the producer.
4. The message enters the ready heap (or the timer wheel if it has a delay).
5. A worker with free credit (prefetch slot) is chosen, the message is sent and a visibility clock starts.
6. The worker runs the handler, checks the idempotency key, performs the side effect and acknowledges.
7. The queue marks the message done; the log prefix is later truncated after a snapshot.

When the worker dies after step 5:

1. No acknowledgement arrives before the timeout.
2. The message becomes ready again with an incremented delivery count, delayed by a backoff timer.
3. Another worker runs it; the idempotency key makes a repeated side effect harmless.
4. After the maximum delivery count the message goes to the dead-letter queue with the failure reason, and an alert fires.

Scaling

Limits, in the order they bite, and the lever for each:

1. Flush rate of one log. One partition or queue is bounded by one leader's sequential write path. Levers: group commit, batching on the publisher side, fast local SSDs, shard work over many queues.
2. Number of queues. Per-queue overhead (a log, a Raft group, timers) limits how many queues one cluster carries; RabbitMQ's documentation suggests reviewing the topology above roughly 5,000 quorum queues. Lever: fewer, larger queues with a priority or tenant field, or streams.
3. In-flight messages. Unacknowledged messages are state the broker must remember. SQS limits a standard queue to about 120,000 in-flight messages (source: SQS developer guide); beyond that, receives fail or return nothing. Levers: smaller prefetch, delete promptly, spread over several queues.
4. Worker throughput. Workers scale out by adding processes, as long as handlers are idempotent and do not share a hot row. Lever: autoscale on queue depth and age of the oldest message, not on CPU.
5. Hot tenants. One tenant's burst fills the queue. Levers: per-tenant queues with fair scheduling, rate limits at publish time, separate priority classes.
6. Timers. Millions of retry and delay timers cost memory; a timing wheel keeps insert and cancel O(1), and a cap on retry attempts bounds the total.

Failure modes

Real implementations

Sources

• RabbitMQ: Quorum queues (Raft replication, publisher confirms after quorum, about 5,000 queue guidance).
• Amazon SQS developer guide: Visibility timeout (30 s default, about 120,000 in-flight), Dead-letter queues (redrive policy, maxReceiveCount, retention).
• Celery: Tasks (acks_late and idempotency), Redis broker (default visibility timeout 1 hour).
• Sidekiq wiki: Error Handling (25 retries, Dead set).
• asynq: README (feature list).
• NATS: JetStream (at-least-once delivery by acknowledgement).