Infrastructure
Design Distributed Priority Queue
01
What we are building
What we are building
Teams across a platform push work into a shared queue service: fraud checks on payments, password-reset emails, thumbnail generation, nightly re-index jobs. All of it is queued, but it is not equally urgent. A fraud check that blocks a checkout should be picked up in milliseconds, while a re-index job can wait an hour. Producers tag each message with one of five priority levels, and consumers expect to receive the most urgent available message every time they ask, with first-in first-out order among messages of the same priority.
On one machine this is a heap. The difficulty is that one machine cannot carry the load or survive a crash, and splitting the heap across shards means no single place knows which message is globally most urgent. The service also needs the usual queue features: delivery that survives consumer crashes, messages that become visible only at a future time, retries with a limit, and a place for messages that keep failing.
One heap gives perfect order and no scale. Many shards give scale and no single source of truth about what is most urgent. The design lives in the space between.
If high-priority traffic never stops, a strict scheduler never serves anything else. Bulk work needs a guaranteed minimum share or a rising priority as it ages.
A consumer that takes a message might crash. The message must come back after a timeout, which means it is invisible while leased but not gone.
02
What the queue promises
What the queue promises
- Enqueue a message with a priority from P0 (most urgent) to P4 (bulk), a payload up to 128 KB, and optional delay, dedup key and expiry.
- Receive up to N messages, most urgent first, FIFO within a priority, with long polling up to 20 seconds.
- A received message is leased for a visibility timeout; the consumer acks to delete it, extends the lease, or nacks to release it early.
- Delayed messages become visible at their
deliver_attime. - After a configurable number of failed deliveries, a message moves to a dead-letter queue that can be inspected and redriven.
- Consumers may filter by minimum priority, so a dedicated pool can serve only P0 and P1.
- P0 messages are delivered within 50 ms of being enqueued when consumers are waiting.
- Ordering is near-strict: a message is never delivered while a message two or more levels more urgent has been visible for over 100 ms.
- Acknowledged enqueues survive the loss of any single node or availability zone.
- At-least-once delivery; duplicates are rare and carry the same message ID.
- Bulk work always makes progress, with at least 5% of throughput reserved for P3 and P4.
Does "priority" mean strict order across the whole system, or only that urgent work is not stuck behind bulk work? Almost every real user wants the second, and it is far cheaper. Also ask how many priority levels there are. Five levels behave very differently from a continuous score, which forces sorted structures everywhere.
03
Load estimates
Load estimates
Assume 1.2 billion messages a day across all tenants, an average payload of 1 KB, and a skewed mix: P0 is 2% of traffic, P1 8%, P2 20%, P3 30% and P4 40%. Messages stay at most 4 days before expiring.
| Quantity | Working | Result |
|---|---|---|
| Average enqueue rate | 1.2B / 86,400 s | about 13,900 / s |
| Peak enqueue rate | 4x average during batch kick-offs | about 56,000 / s |
| Operations per message | enqueue, receive, ack, plus about 0.1 retries | about 3.2 |
| Peak broker operations | 56,000 x 3.2 | about 180,000 / s |
| P0 peak rate | 2% of 56,000 | about 1,100 / s |
| Ingest bandwidth at peak | 56,000 x 1 KB | about 56 MB / s |
| Normal backlog | mostly P4, drained within an hour | about 40M messages, 40 GB |
| Worst-case backlog | consumers down 1 day: 1.2B x 1 KB | about 1.2 TB, 3.6 TB with 3 replicas |
| Shards | about 6,000 ops / s per shard leader on NVMe | 32 shards, room to double |
Urgent traffic is small: 1,100 P0 messages a second fit on a single shard. The volume lives in the bulk levels. That observation is why the expensive ordering work only has to be precise at the top, and why a backlog of bulk work is normal rather than an emergency.
04
API
API
05
System layout
System layout
flowchart LR
P["Producers"] --> FE["Front-end API, stateless"]
FE -->|hash of message id| SH["Shard leader, 5 priority lanes"]
SH --> R1["Replica"]
SH --> R2["Replica"]
SH --> DL[("Delay index per shard")]
SH -. "head summary every 20 ms" .-> HS[("Head summary map")]
C["Consumers, long poll"] --> FE
FE --> HS
FE -->|receive from best shards| SH
SH --> DLQ[["Dead-letter queue"]]
CTL["Control plane, Raft"] -. "shard map and leaders" .-> FEEach queue is spread across a set of shards, 32 at our scale. A shard is a small replicated log with one leader and two followers. Inside a shard, messages are not kept in one sorted structure. Instead there are five FIFO lanes, one per priority, each an append-only segment with an in-memory pointer to its head. Enqueue appends to the right lane; receive pops from the most urgent non-empty lane. With a fixed small number of levels, this is constant time and keeps FIFO order within a level for free, which a sorted set only gives you with a composite score.
Producers hash the message ID to pick a shard, so load is even and no shard is special. That choice means urgent messages are scattered across all 32 shards, and the receive path has to find them. Each shard leader publishes a tiny head summary every 20 ms: for each lane, the number of visible messages and the enqueue time of the head. The front-end nodes keep the latest summary of every shard in memory. A receive call reads the summaries, picks the shards with the most urgent and oldest heads, and pulls from those. Because the summary is about 200 bytes per shard, the whole map for a queue fits in a few kilobytes and refreshes fifty times a second.
A control plane, a small Raft group, owns the shard map, leader assignments and queue configuration. It is not on the data path. Front ends cache the map and refresh it when a shard returns "not leader".
Five append-only logs per shard. Acked messages are tombstoned and segments are deleted when fully acknowledged, the same way log-structured brokers reclaim space.
Per shard, a map from message to lease expiry plus a timer wheel. When a lease expires, the message goes back to the front of its lane, not the back, so a retry does not lose its place.
Delayed messages sit in a time-ordered index per shard. A ticker moves due entries into their lane each second, the same pattern a job scheduler uses.
A per-shard map of recent dedup keys with a 10-minute window. Hashing by dedup key when present makes repeats land on the same shard.
06
Deep dive: urgent-first across 32 shards
Deep dive: urgent-first across 32 shards
Sharding for throughput scatters the most urgent messages; finding them again without a global bottleneck is the whole problem.
Three ways to keep order
| Approach | Ordering | Bottleneck | Fits |
|---|---|---|---|
| One global heap on one node | Perfect | The node, around 20,000 ops / s | Small queues |
| Shard by priority level | Strict between levels | The busiest level's shard; P4 is 40% of traffic | Few levels, even traffic |
| Hash shards plus head summaries | Near-strict, bounded by summary age | None central; summaries are tiny | Our scale |
Sharding by priority level is a tempting middle ground: put P0 on its own shard and consumers check that shard first. It works until one level is hot. Here P4 alone carries 40% of the load, so its shard would need splitting, and then you have the same ordering problem within P4. Hash sharding with summaries treats every level the same way and scales by adding shards.
flowchart TD
R["Consumer asks for 10 messages"] --> M["Front end reads head summary map"]
M --> T["Find most urgent level with visible messages"]
T --> P["Rank shards by that level's head age"]
P --> Q["Pop from top 3 shards in parallel"]
Q --> E{"Got 10?"}
E -->|no, a shard was stale| N["Try next shards, then next level"]
N --> E
E -->|yes| L["Record leases, return batch"]How precise is near-strict?
The summary can be up to 20 ms old, plus network delay. So a P0 message enqueued on shard 7 might be invisible to a front end for about 30 ms, during which that front end serves a P1 from shard 12. That is the whole error: a bounded, short inversion that never lasts longer than one summary interval. For fraud checks and password resets, 30 ms of imprecision is invisible. If a tenant truly needs strict global order, give that queue a single shard and accept its throughput ceiling.
Two refinements matter in practice. First, a shard that receives a P0 or P1 pushes an immediate summary update instead of waiting for the next tick, which brings the urgent-path inversion close to one network round trip. Second, front ends pop from the top three candidate shards in parallel and keep any surplus in a tiny local buffer for the next caller, which hides the cost of a shard turning out to be empty.
Stopping starvation
Strict priority means P4 is served only when P0 to P3 are all empty. During a busy afternoon that may never happen, and a re-index job enqueued at noon is still waiting at midnight. Two standard fixes exist. Weighted fair dequeue gives each level a share of receive calls, for example 50, 25, 13, 7 and 5 percent, used only when several levels have work. Aging raises a message's effective priority by one level for each fixed period it waits, so a P4 message becomes P3 after 30 minutes. We use weights, because they are predictable and easy to explain on a dashboard, and keep aging as a per-queue option.
Leases and retries
Receiving a message writes a lease into the shard's replicated log with an expiry and a delivery count, and returns a receipt containing that count. An ack must present the current receipt, so a consumer that stalled past its lease and wakes up cannot delete a message that is now leased to someone else. When a lease expires the message returns to the head of its lane with the delivery count incremented. After five deliveries it moves to the dead-letter queue with its last error attached.
Delays and duplicates
A delayed message is written to the shard's log like any other, but its index entry goes into a time-bucketed delay index instead of a lane. Once a second, the shard moves every entry whose deliver_at has passed into the tail of its lane and updates the head summary. Because the move is a log entry, a leader change cannot lose or double it. A message delayed by a week costs only its bytes on disk and one index row.
Producer retries are the main source of duplicates on the way in. When a dedup key is present, the front end hashes the key rather than the message ID, so every retry lands on the same shard, where a ten-minute window of recent keys returns the original ID instead of appending again. Duplicates on the way out, from expired leases, are handled by consumers using the message ID. Neither side gets exactly-once, but each duplicate is cheap to recognise.
07
Decisions and their costs
Decisions and their costs
Every shard carries its share of every level, so load is even and scaling is adding shards. You accept an ordering error bounded by summary age, a few tens of milliseconds.
Scales evenlyGives strict order between bands and a quiet, fast shard for urgent work. It concentrates the busiest band on too few nodes and needs re-partitioning when the mix changes.
Good at modest scaleConstant-time enqueue and dequeue, natural FIFO within a level, and append-only storage. Priorities are limited to a small set of integers.
Simple and fastSupports continuous priorities and deadlines as scores, at logarithmic cost per operation and with random writes that are harder to persist. Choose it when callers need fine-grained ranking, such as an auction.
When scores are continuousConsumers ask when they have capacity, which gives natural backpressure and keeps the broker unaware of worker health. Empty polls cost a held connection, not CPU.
Backpressure for freeSlightly lower latency, but the broker must track each consumer's capacity and failures. A slow consumer collects a pile of leased messages it cannot process, which delays urgent work.
Worse under loadEvery level makes progress and the shares are easy to reason about. Urgent levels lose a sliver of throughput when bulk work is waiting.
No starvationMaximum responsiveness for urgent work and trivially correct ordering. A steady stream of urgent traffic stops bulk work indefinitely, which turns into an incident of its own.
Starves the bottom08
Failure scenarios
Failure scenarios
The leader for shard 19 dies with 4,000 visible messages and 600 active leases. Until a follower takes over, those messages cannot be received, and front ends see the shard's summary go stale.
Followers hold every committed enqueue and lease, so the new leader, elected in about 2 seconds, resumes with nothing lost. Front ends treat a stale summary as "unknown" and route around the shard meanwhile.Workers have each taken a batch of ten P3 messages that take a minute apiece. A burst of P0 work arrives and waits, because every worker is busy with bulk work it already holds.
Run a dedicated consumer pool that only receives P0 and P1, keep batch sizes small for slow work, and let consumers nack unstarted messages when a higher-priority receive succeeds.A malformed payload crashes the consumer before it can ack. The lease expires, the message returns to the head of its lane, and the next consumer crashes too.
Count deliveries in the lease record and move the message to the dead-letter queue after five attempts. Alert on dead-letter growth and offer a redrive button after the bug is fixed.A downstream outage stops all consumers for six hours. The backlog grows to 300 million messages and shard disks start filling.
Size disks for a full day of backlog, enforce per-queue depth limits with 429 responses to producers, and drop expired messages during compaction so the backlog does not include work nobody wants.A consumer takes 45 seconds on a message with a 30-second lease. Another consumer receives it, both finish, and the side effect happens twice.
SDK heartbeats extend leases while work is in progress, receipts prevent the stale consumer's ack from counting, and handlers use the message ID for idempotency.09
Interview advice
Interview advice
Start with one heap. Draw enqueue and pop on a single node, then say why it is not enough. Building up from there keeps the design honest.
Name the tension early. "Sharding gives throughput and breaks global order" frames every later choice. Interviewers want to hear it said plainly.
Ask what precision is needed. Most systems only need urgent work to skip the line, not a mathematically strict order. Bounded inversion is a feature you can quantify.
Raise starvation yourself. Describe weights or aging and say which you picked. Candidates who forget it are designing a queue where bulk work never runs.
Treat delivery as a lease. Visibility timeouts, receipts, delivery counts and a dead-letter queue are the vocabulary of a production queue.
Separate a priority queue from a log. Kafka-style logs keep order by offset and cannot reorder by urgency. Explain why you would not just add a priority header to a topic.
10
Evolution of the queue
Evolution of the queue
A list per priority level, a sorted set for leases keyed by expiry, and a Lua script for receive. Simple, fast and good enough for a single product.
Move to a replicated log with five lanes, quorum acknowledgement, a lease table, delays and a dead-letter queue. Still one shard per queue, so ordering is exact.
Spread each queue over many shards and add the head summary map to front ends. Introduce weighted fair dequeue and dedicated urgent consumer pools.
Per-tenant rate and depth limits, noisy tenants moved to their own shard sets, and per-queue dashboards of depth and head age by level.
Each queue lives in one home region with asynchronous replication for disaster recovery. Cross-region priority ordering is not attempted; producers enqueue where the consumers run.
Watch and read
Further watching and reading
Try next
Free to read · better with landed
Whiteboard this with landed
landed runs it as a live system design round on the whiteboard and grades your trade-offs.