Walkthrough: Designing a Distributed Queue

The problem

You’re asked to design a distributed message queue — the system underneath Kafka, SQS, or Pulsar. The interviewer says something like: “Design a system where producers publish messages and consumers process them asynchronously. It should handle producer bursts, slow consumers, and consumer crashes without losing messages.”

Sounds like a buffer. It isn’t. The trap is designing a literal queue — FIFO in, FIFO out, delete on consume — when the requirements (replay, multiple independent consumers, per-key ordering) quietly demand a different data structure: a replicated, partitioned log. Candidates who notice that the question is “queue or log?” and answer it deliberately are answering the real question.

Below is how I’d walk through this, start to finish.

1. Requirements

First 3–5 minutes. Questions I’d ask to pin down what we’re building:

Functional requirements

• R1. Producers publish messages to named topics.
• R2. Consumers subscribe and process messages; a consumer group processes each message once per group, with multiple groups consuming independently.
• R3. Ordering — messages with the same key are processed in publish order.
• R4. Replay — a consumer can re-read messages from an earlier point.
• R5. Durability — an acknowledged publish survives broker failures; messages are retained for a configured window (not just until consumed).

Scope

This design covers the broker system. Explicitly out of scope:

• Exactly-once end-to-end semantics (covered as a delivery-semantics discussion; the full transactional story is its own question)
• Stream-processing frameworks on top (windowing, joins — that’s the ad-click aggregation question)
• Multi-region replication (named in the evolution table)
• Schema registry and message validation (real deployments need it; not a design driver)

Non-functional requirements

• Throughput. Peak publish rate and message size? This decides whether the design is I/O-bound or coordination-bound.
• Ordering scope. Global FIFO, or per-key? Global ordering caps throughput at one node’s sequential write speed — worth surfacing early.
• Consumer lag tolerance. Can consumers fall hours behind? That turns the queue into a storage system with a streaming interface.
• Delivery guarantee. At-least-once as the floor? Exactly-once costs coordination; at-most-once loses data.
• Latency. Publish-to-consume p99 — milliseconds (messaging) or seconds (batch)?

Say the interviewer confirms: 1M messages/sec peak, ~1 KB average message, per-key ordering (not global), 7-day retention, consumers may lag hours, at-least-once delivery, publish ack p99 < 10 ms.

2. Capacity estimate

• Ingest: 1M msg/sec × 1 KB = 1 GB/sec at peak, ~86 TB/day.
• Retention: 86 TB/day × 7 days ≈ 600 TB live, ×3 replication ≈ 1.8 PB on disk.
• Per-partition ceiling: a single partition is one node’s sequential append stream — realistically ~50–100 MB/sec. At 1 GB/sec ingest, that’s a minimum of 10–20 partitions for the hottest topic, and hundreds across the cluster.

I’d say out loud: “Retention changes what this system is. 1.8 PB means this is a storage system that happens to stream, not a router that happens to buffer. Two consequences: sequential disk I/O is the whole performance story, and ‘a slow consumer’ is a storage-capacity question — the log is the buffer, and it’s seven days deep.”

3. High-level architecture

Three logical subsystems:

1. Brokers — own partitions (append-only logs), accept publishes, serve fetches, replicate to each other.
2. Cluster metadata — which partitions exist, which broker leads each, which replicas are in sync. Small, consensus-backed, changes rarely.
3. Clients — producers (choose a partition, batch, retry) and consumer groups (divide partitions among members, track offsets). Deliberately thick: the brokers stay simple because the clients carry coordination logic.

flowchart TD
  Producer[Producer] --> Leader[Broker 1 · partition leader]
  Leader --> Log[(Partition log)]
  Consumer[Consumer group] -->|fetch from offset| Leader

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class Log store

The brokers decide the system’s character: they are dumb, fast, and sequential — every clever feature (groups, replay, delivery semantics) lives in client protocol, not broker state.

4. Architecture evolution

A queue in production evolves through recognizable levels:

Each level keeps the previous one’s contract: a Level 3 log still behaves like a work queue to any single consumer group — it just stops being only that.

The design in this walkthrough is Level 3, with Level 4 named as the answer to “doesn’t 1.8 PB of broker disk hurt?”

I’d say out loud: “I’m designing the partitioned log — Level 3. If the interviewer pushes on storage cost, the evolution is tiering cold segments to object storage, which works precisely because segments are immutable.”

Target architecture (Level 3)

Every section that follows explains one part of this diagram:

flowchart TD
  Producer[Producer] --> Leader[Broker 1 · partition leader]
  Leader --> Log[(Partition log)]
  Leader -->|replicate| F1[Broker 2 · follower]
  Leader -->|replicate| F2[Broker 3 · follower]
  F1 --> Log2[(Replica log)]
  F2 --> Log3[(Replica log)]

  Meta[Metadata · consensus] -.-> Leader
  Meta -.-> F1
  Meta -.-> F2

  CG[Consumer group] -->|fetch from offset| Leader
  CG --> Offsets[(Committed offsets)]

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class Log,Log2,Log3,Offsets store

5. Core design choice: queue or log

This is the question. Three options:

(a) Broker-managed work queue. The broker tracks per-message state (delivered, acked, visible-again-at). Consumers ack each message; acked messages are deleted. SQS and classic RabbitMQ work this way.

(b) Partitioned append-only log. Brokers only append and serve reads. Consumers remember their own position (offset) per partition. Nothing is deleted on consumption — retention is time/size-based. Kafka’s model.

(c) Database table as queue. SELECT ... WHERE status='pending' FOR UPDATE SKIP LOCKED. Honest answer: works fine to ~1K msg/sec and is the right call at small scale — and named as such, it’s a credibility point, not a mistake.

Why the log wins here

The requirements decide it, one by one. R4 (replay) is impossible in a work queue — delivered messages are gone; in a log, replay is “set your offset back.” R2 (independent consumer groups) costs a duplicated queue per group in model (a) — the broker writes every message G times; in a log, every group reads the same bytes and just tracks its own offsets. Throughput: per-message broker state means random I/O and bookkeeping proportional to message count; an append-only log is pure sequential I/O — the disk’s best case — and serving consumers is sequential reads that the OS page cache amortizes. At 1 GB/sec, that difference is the whole game.

The cost, stated honestly: a log pushes complexity to consumers. “Which messages have I processed?” becomes the consumer’s problem (offset management), and work distribution requires the consumer-group protocol instead of broker dispatch.

Tradeoff matrix

Architecture decisions

Core data structures

What matters now: a consumer group’s entire state is a map of partition → offset. That’s why fan-out is free and replay is trivial.

6. Write path: publish [R1, R3, R5]

The slice of the target architecture a publish touches:

flowchart TD
  Producer[Producer] -->|batch per partition| Leader[Broker 1 · partition leader]
  Leader --> Log[(Partition log · append)]
  Leader -->|replicate| F1[Broker 2 · follower]
  Leader -->|replicate| F2[Broker 3 · follower]

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class Log store

Step by step:

1. Producer computes the partition: hash(key) mod partition_count. Same key → same partition → same append order — this is where R3’s per-key ordering comes from, and all it comes from.
2. Producer batches messages per partition (linger a few ms, compress the batch). Batching is why 1M small messages/sec is feasible: the broker sees thousands of large sequential writes, not a million tiny ones.
3. Leader appends the batch to the active segment file and assigns each message a monotonically increasing offset — the message’s permanent identity in the partition.
4. Followers fetch the new bytes (replication is just consumers with a different hat), append, and report their position.
5. With acks=all, the leader responds once every in-sync replica has the batch. The ISR set is the durability contract: an acknowledged write exists on every broker the metadata service currently considers caught-up.
6. On retry after a timeout, the producer’s sequence number (per producer, per partition) lets the leader discard duplicates — publish-side idempotence, so retries don’t double-append.

7. Read path: consume [R2, R3, R4]

flowchart TD
  C1[Consumer 1] -->|fetch p0, p1 from offset| Leader[Broker 1 · partition leader]
  C2[Consumer 2] -->|fetch p2, p3 from offset| Leader
  Coord[Group coordinator] -.->|assigns partitions| C1
  Coord -.->|assigns partitions| C2
  C1 -->|commit offsets| Offsets[(Committed offsets)]
  C2 -->|commit offsets| Offsets

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class Offsets store

Step by step, for a group of 2 consumers on a 4-partition topic:

1. Each consumer joins the group via the group coordinator (a broker chosen per group). The coordinator assigns partitions: consumer 1 gets p0+p1, consumer 2 gets p2+p3. One partition belongs to exactly one consumer per group — that invariant is what preserves per-key ordering through consumption (R3): no two workers ever race on the same key’s messages.
2. Each consumer pulls: fetch(partition, my_offset, max_bytes). The broker returns a contiguous chunk of log. Long-poll (wait up to N ms if no data) gives push-like latency without push’s problems.
3. Consumer processes the batch, then commits its new offset to the offsets store. Commit-after-process is what makes delivery at-least-once: crash between process and commit, and the batch is re-fetched and re-processed — duplicates, not loss.
4. Replay (R4) is a client-side act: reset the committed offset to an earlier value (or a timestamp lookup) and consume forward. The broker doesn’t participate; the bytes were always there.
5. When a consumer joins or dies (missed heartbeats), the coordinator rebalances — reassigns partitions among surviving members. The new owner of p1 starts from p1’s last committed offset.

8. Deep dives

Backpressure [R5]

The pull model makes backpressure structural rather than protocol. A slow consumer fetches less often; nothing piles up in broker memory — the unread messages simply remain in the log, where they were going to be anyway. The “buffer” is 7 days deep and made of disk.

What still needs managing is lag — the gap between the log head and the group’s committed offset. Lag is the system’s single most important health metric, because it has a hard deadline: if lag exceeds retention, the tail of the log is deleted before the consumer reads it. At that point the slow consumer hasn’t just fallen behind; it has lost data, silently, while every broker was healthy.

Mitigations, in the order I’d name them: alert on lag-vs-retention ratio (not absolute lag); scale the group to the partition ceiling; if the ceiling itself is the problem, the answer was a higher partition count last month — say so.

Hot partitions [R3]

hash(key) spreads keys evenly, not load: one chatty key (a celebrity account, a tenant emitting 30% of events) concentrates on one partition, capping that key’s throughput at a single broker’s append rate and stalling its consumer. Options worth naming: widen the key (user_id → user_id:session_id) where ordering is only needed within the finer grain; route the known-hot key to a dedicated partition set; or accept it and provision the partition’s broker for the hot key — sometimes a key’s ordering genuinely can’t be split, and honesty beats cleverness.

Retention and compaction [R4, R5]

Two retention models, two different products. Time/size retention (delete segments older than 7 days) serves event streams — replay bounded by the window. Log compaction keeps the latest message per key forever and deletes superseded ones — which turns the topic into a durable changelog: replay it from offset zero and you reconstruct current state per key. Compacted topics are how the offsets store itself works, and the bridge to “the log as a database” — worth one sentence in an interview, because it shows you see what the structure is capable of beyond messaging.

9. API design [R1, R2, R4]

POST /topics/{topic}/messages                      [R1]
  body:    { key, value, producer_id, sequence }
  returns: { partition, offset }

GET /topics/{topic}/partitions/{p}/messages        [R2]
    ?offset=12345&max_bytes=1048576&wait_ms=500
  returns: { messages: [...], next_offset, high_watermark }

POST /groups/{group}/offsets                       [R2]
  body:    { topic, partition, offset }

GET /topics/{topic}/offsets?timestamp=...          [R4]
  returns: { partition_offsets: [...] }            # entry point for replay

Two non-obvious decisions:

The fetch response includes the high watermark — the latest replicated offset. Consumers only ever see messages the ISR has; an acknowledged-but- unreplicated message is invisible until it’s durable. This is what keeps a leader crash from showing consumers messages that then un-happen.

Offsets commit through an API, not automatically on fetch. The gap between “fetched” and “committed” is where the delivery guarantee lives: commit after processing → at-least-once; commit before → at-most-once. The API makes the choice explicit and per-group.

The API hides broker topology, replication, and segment layout. A consumer never knows a partition’s leader moved — the client library refreshes metadata and refetches. That boundary is what lets brokers fail, rebalance, and tier to object storage without breaking a caller.

10. Data model and storage

Requirements → components

Access frequency

Storage technology choices

Access pattern matrix

Schemas

Segment file [R1, R5] — the on-disk unit of a partition:

segment (broker filesystem):
  filename:    {base_offset}.log          # e.g. 00000000000012345678.log
  record:      offset | timestamp | key_len | key | value_len | value | crc
  companion:   .index (sparse offset→position), .timeindex (timestamp→offset)
  lifecycle:   active (appending) → sealed (immutable) → deleted/tiered

Immutability after sealing is the load-bearing property: sealed segments can be checksummed, tiered to object storage, and served concurrently without locks.

Committed offsets [R2] — one record per (group, topic, partition), in a compacted topic:

offset_commit:
  key:    (group_id, topic, partition)
  value:  { offset, committed_at, metadata }

11. Failure modes

Grouped by what they threaten. The pattern: name what fails, name what degrades, name what doesn’t.

Durability failures

Partition leader crashes

Fails: one partition’s write availability for seconds. Degrades: the metadata service elects a new leader from the ISR — every acked message is on it by the ISR contract, so nothing acked is lost; producers pause and retry into the new leader. Doesn’t degrade: other partitions; consumers of the high watermark. The trap to name: unclean leader election — promoting an out-of-sync replica because the whole ISR is down restores availability by silently truncating acked messages. It’s a config flag, and the default should be off.

All replicas of a partition lost

Fails: that partition’s data inside the retention window. Degrades: nothing — this is the disaster case; RF=3 across racks is the defense, tiered segments in object storage the backstop. What doesn’t degrade: the producers’ upstream source, if publishes are recorded transactionally there — worth one sentence (“the log is rebuildable if upstream keeps its source of truth”).

Delivery failures

Consumer crashes mid-batch

Fails: in-flight processing. Degrades: rebalance hands its partitions to survivors, who resume from the last committed offset — the crashed batch is reprocessed. Duplicates, not loss: that’s at-least-once working as designed, and downstream idempotence (covered in the delivery-semantics reference) is the other half of the contract. Doesn’t degrade: ordering — the new owner reads the partition in the same order.

Rebalance storms

Fails: group throughput during repeated rebalances (a flapping consumer, slow processing mistaken for death). Degrades: with naive stop-the-world rebalancing, every member pauses on any membership change — one bad pod stalls the whole group. Mitigations: incremental/cooperative rebalancing (only moved partitions pause), static membership (a restarted pod reclaims its old assignment without triggering a rebalance), and separating poll-liveness from processing-liveness timeouts. Doesn’t degrade: the log itself — brokers are oblivious to all of it.

Capacity failures

Consumer lag exceeds retention

Fails: the slow group’s data — segments age out unread. Degrades: nothing visibly, which is the danger; every component is green while data is deleted. The fix is operational, not architectural: alert on lag_seconds / retention_seconds, and treat 0.5 as an incident. Doesn’t degrade: other groups — lag is per-group state, one slow team can’t hurt another’s consumption.

Producer burst beyond cluster capacity

Fails: publish latency SLO. Degrades: producer-side buffering absorbs seconds of burst; beyond that, producers must block or shed — and which is a product decision to surface (“for clickstream, drop; for orders, block”). Doesn’t degrade: already-appended data or consumers; the log keeps serving.

12. What I’d skip, and say I’m skipping

Time check — five minutes left. Things I’d explicitly defer:

• End-to-end exactly-once. Producer idempotence I’ve covered; transactional consume-process-produce across topics is a separate protocol (and a separate question). I’d name the boundary: the queue gives at-least-once; dedup belongs to consumers.
• Stream processing. Windows, joins, watermarks — that’s the system on top of this one (the ad-click aggregation question).
• Multi-region. Async cross-cluster replication with per-region offsets; the Level 5 evolution. Name MirrorMaker-style topology and stop.
• Quotas and multi-tenancy. Per-client throttling matters in shared clusters; it’s rate limiting applied at the broker, not new architecture.
• Tiered-storage mechanics. I’ve claimed sealed segments make it possible; the fetch-path plumbing is detail.

Saying “I’d skip this, and here’s why” is a strong signal. It shows you know the full surface and are making deliberate scoping choices.

Interview flow summary

Architecture at a glance

PUBLISH PATH                            CONSUME PATH

Producer                                Consumer group
 ↓ hash(key) → partition                 ↓ coordinator assigns partitions
Batch per partition                     Pull: fetch(partition, offset)
 ↓                                       ↓
Partition leader · append               Process batch
 ↓                                       ↓
ISR replication                         Commit offset (after processing)
 ↓                                       ↓
ack (acks=all)                          (crash → resume from committed offset)

The walkthrough order for your whiteboard

1. Requirements & ordering scope  — per-key, not global; it changes everything
2. Capacity estimate              — 1 GB/sec, 1.8 PB: a storage system that streams
3. Architecture evolution         — queue (L2) vs log (L3); commit to log
4. Core choice                    — who tracks consumption; broker vs consumer
5. Publish path                   — partitioning, batching, ISR acks, idempotence
6. Consume path                   — groups, pull, commit-after-process, rebalance
7. Deep dives                     — backpressure/lag, hot partitions, compaction
8. API                            — high watermark, explicit commits
9. Data model                     — segments, sparse indexes, offsets topic
10. Failure modes                 — durability / delivery / capacity groups

If the interviewer pushes deeper

13. Wrap-up

One crisp sentence before the interviewer’s next question:

This design gets its throughput, replay, and fan-out from one decision — the broker stores an immutable partitioned log and consumers track their own positions — so the broker’s job stays sequential I/O, and every delivery guarantee becomes an explicit client-side choice about when to commit an offset.

What separates levels on this question

• SDE II names Kafka, draws producers/brokers/consumers, and describes topics and partitions. Often designs a work queue with Kafka vocabulary — the tell is “the broker deletes messages after all consumers ack.”
• SDE III chooses log over queue from the requirements (replay and fan-out), traces per-key ordering end-to-end (hash → partition → single group member), places the delivery guarantee in commit timing, and names lag-vs-retention as the failure that loses data while everything is green.
• Staff/Principal keeps the broker dumb on purpose and can say why (coordination lives in client protocol, so brokers scale on I/O alone); names where the model doesn’t fit (per-message job semantics want SQS); treats partition count as an irreversible capacity decision and plans key growth; and sees compacted topics as the bridge from messaging to state — the log as the database’s first principle, not its accessory.

The difference isn’t knowledge. It’s deriving the data structure from the requirements — weaker candidates pick a technology and describe it; stronger ones show why replay plus fan-out plus throughput leaves only one shape.

Further reading

• The Log: What every software engineer should know about real-time data’s unifying abstraction — Jay Kreps. The essay behind Kafka’s design; the single best explanation of why the log is the primitive.
• Kafka: a Distributed Messaging System for Log Processing — the original paper: design goals, sequential I/O argument, consumer-tracked state.
• Designing Data-Intensive Applications — Kleppmann. Chapter 11 (stream processing) covers logs vs queues, offsets, and delivery semantics with exactly this question’s framing.
• System Design Interview Vol. 2 — Alex Xu. The distributed message queue chapter is the interview-prep treatment of this question.
• Kafka documentation: consumer groups and rebalancing — the production reference for group coordination, static membership, and cooperative rebalancing.
• Amazon SQS documentation — the work-queue model done well; read it to know precisely what the log model trades away.