system-design

Design a Distributed Message Queue (like Kafka / SQS)

Difficulty: Tier 3 Asked at: Amazon, Confluent, LinkedIn, senior loops Time budget: 45–60 min

You’ve used a queue in half the designs in this repo. Now build one. This question tests whether you understand the machinery behind “just put it on a queue”: how messages are durably stored and partitioned, how delivery guarantees actually work, and how consumers scale. The signature ideas are the partitioned, append-only commit log, consumer offsets, and the delivery-semantics spectrum.

Prerequisites: Message Queues, Kafka, Replication, Idempotency

1. Requirements

Functional:

Producers publish messages to a topic; consumers subscribe and receive them.
Durable — messages aren’t lost once acknowledged.
Ordered (at least within a partition).
Support many producers/consumers; consumer groups for parallel consumption.
Configurable retention (keep messages N days / until consumed).

Non-functional:

High throughput — millions of messages/sec.
Durable & replicated — survive broker failures.
Scalable — add brokers/partitions to grow.
Tunable delivery guarantees (at-most-once / at-least-once / exactly-once-ish).

Out of scope: the specific wire protocol; exact Kafka internals (use them as reference).

2. Estimation

1M messages/sec, avg 1 KB → 1 GB/sec ingest. Over days of retention → hundreds of TB → must partition across brokers and store on disk (sequential writes are cheap).
Consumers must keep up; parallelism comes from partitions (the unit of parallelism).

3. The core: a partitioned commit log

🚨 A topic is an append-only log, split into partitions. Each partition is an ordered, immutable sequence of messages, each with an offset (its position). Producers append to the end; consumers read forward from an offset.

Topic "orders", partition 0:  [msg0][msg1][msg2][msg3] ...  (append only, ordered)
                offset:          0     1     2     3
Consumer reads from offset N, advances as it processes.

Why a log? Append-only sequential writes are extremely fast (disk loves sequential I/O), and an immutable log lets many consumers read independently at their own offsets. 🚨 The commit-log abstraction is the whole trick — it’s not a “delete on read” queue; messages persist and consumers track position.
Partitions = parallelism + ordering unit. Order is guaranteed within a partition, not across. A message’s partition is chosen by key (hash) or round-robin. (Kafka)

4. High-level design

flowchart TB
    P[Producers] -->|publish to topic/partition| B1[Broker 1<br/>partitions + replicas]
    P --> B2[Broker 2]
    P --> B3[Broker 3]
    B1 <-->|replicate| B2
    B2 <-->|replicate| B3
    C[Consumer group] -->|read from offset| B1
    C --> B2
    Coord[Coordination<br/>ZooKeeper/KRaft] -.metadata, leader.-> B1

Brokers store partitions (and replicas of other brokers’ partitions). Producers append to the leader replica of a partition. Consumers in a group split the partitions among themselves and read forward, committing offsets. Coordination (ZooKeeper/KRaft) tracks metadata, partition leaders, and group membership.

5. Deep dives

5a. Durability & replication

Each partition is replicated across brokers (leader + followers). Producers write to the leader; the leader replicates to followers. A message is acknowledged once enough replicas have it (the acks setting: leader-only = fast but risky; all in-sync-replicas = durable). On leader failure, a follower is promoted → no data loss if it was in sync. 🚨 Replication factor + in-sync-replica acks = the durability knob. (Replication, Quorums)

5b. Consumer offsets & groups

Consumers track their position with an offset (stored durably, e.g. in a special topic). A consumer group divides a topic’s partitions among its members so each partition is consumed by exactly one member — scaling consumption by adding members (up to the partition count). 🚨 Because offsets are consumer-managed and messages persist, a consumer can replay (rewind its offset) or catch up after downtime — a superpower over delete-on-read queues.

5c. Delivery semantics (the spectrum)

🚨 Three levels — know the trade-offs:

At-most-once: commit offset before processing → if you crash mid-process, the message is lost, never redelivered. Fast, lossy.
At-least-once: process then commit offset → a crash after processing but before committing means redelivery → possible duplicates. The common default; pair with idempotent consumers.
Exactly-once: achievable within the system via idempotent producers (dedup by producer+sequence) and transactional writes, but end-to-end exactly-once with external side effects still needs idempotency. Costly; use only when required.

5d. Scaling & ordering trade-off

Throughput scales by adding partitions (more parallelism). But ordering is only within a partition, so you trade global ordering for parallelism. If you need per-entity order, partition by that entity’s key (all of a user’s events land in one partition, ordered). 🚨 This key-based partitioning is how you get “ordered where it matters” while still scaling.

5e. Retention

Messages persist for a configured time or size (not deleted on consumption) → multiple consumer groups read the same data independently, and consumers can replay. Old segments are deleted/compacted by retention policy. Log compaction (keep only the latest value per key) supports changelog use cases.

5f. Push vs pull

Most log-based queues use pull (consumers fetch at their own pace) — naturally handles slow consumers and backpressure, and lets consumers batch. Push can overwhelm slow consumers. State the trade-off.

6. Bottlenecks & scaling further

Throughput → partitions (parallelism), sequential disk writes, batching, zero-copy transfer.
Durability → replication factor + in-sync-replica acks; leader failover.
Consumer scaling → consumer groups up to partition count; add partitions to go wider.
Ordering vs parallelism → key-based partitioning for per-entity order.
Storage → retention policies + compaction; cheap sequential disk.

7. Trade-off summary

Decision	Chosen	Alternative	Why
Storage	Append-only partitioned log	Delete-on-read queue	Sequential speed, replay, multi-consumer
Ordering	Per-partition	Global	Global ordering can’t scale; partition by key
Durability	Replicas + ISR acks	Single copy	Survive broker failure without loss
Delivery	At-least-once + idempotency	Exactly-once everywhere	Simpler; dedup gives the effect
Delivery model	Pull	Push	Backpressure, batching, slow-consumer safe

8. Follow-up questions

Why store messages as an append-only log instead of deleting them when consumed?

Because the append-only log gives you speed, multiple independent consumers, and replay — capabilities a delete-on-read queue lacks. Appending to the end of a log is sequential disk I/O, which is dramatically faster than the random I/O of tracking and deleting individual messages, so it sustains very high throughput. Because messages persist and each consumer tracks its own read position (offset) rather than the queue removing messages, many different consumer groups can read the same stream independently at their own pace, and any consumer can rewind its offset to replay history — invaluable for reprocessing after a bug, seeding a new consumer, or recovering from downtime. A traditional queue that deletes on acknowledgment couples the message's lifetime to a single consumer and loses the data once consumed, forfeiting replay and multi- consumer fan-out. The log's immutability and consumer-managed offsets are precisely what make it more powerful and scalable, at the cost of needing retention policies to eventually reclaim space.

Explain at-most-once vs at-least-once vs exactly-once delivery.

They differ in what happens around a consumer crash, and the difference is essentially *when you commit the offset relative to processing*. At-most-once commits the offset before processing the message, so if the consumer crashes mid-processing, the message is never redelivered — you never get duplicates but you can lose messages; it's fast and suitable when occasional loss is acceptable. At-least-once processes the message first and commits the offset only after success, so a crash after processing but before committing causes the message to be redelivered on restart — you never lose a message but can process it more than once; it's the common default and is paired with idempotent consumers so duplicates are harmless. Exactly-once means each message affects the system's state once and only once; within a single system it's approximated via idempotent producers (deduplicating by producer ID + sequence number) and transactional writes that couple message consumption and output atomically, but end-to-end exactly-once involving external side effects still ultimately relies on idempotency, and it's costly, so you use it only when duplicates are genuinely intolerable. The practical sweet spot is at-least-once plus idempotency, which yields the exactly-once effect without the cost.

How do partitions let you scale throughput, and what do you give up?

Partitions are the unit of parallelism: a topic is split into multiple partitions spread across brokers, and each partition can be produced to and consumed independently, so total throughput scales with the number of partitions — and within a consumer group, each partition is handled by a different consumer, so you scale consumption by adding partitions and consumers together. What you give up is global ordering. Order is only guaranteed *within* a partition, not across partitions, because the partitions are read in parallel with no coordination between them. If you need ordering for a particular entity (all events for one user in order), you partition by that entity's key so all its messages land in the same partition and stay ordered, while different entities spread across partitions for parallelism. So the design trades total ordering for scalability, and key-based partitioning recovers ordering exactly where it matters while preserving the parallelism everywhere else.

How is a message guaranteed durable once acknowledged?

Through replication plus an acknowledgment policy that waits for enough replicas. Each partition is replicated across several brokers as a leader and followers; producers write to the leader, which replicates the message to the followers. The producer's acknowledgment setting controls durability: acknowledging after only the leader has the message is fast but risks loss if the leader dies before replicating, whereas acknowledging only after all in-sync replicas have the message guarantees the message survives the loss of any single broker, because a fully-caught-up follower can be promoted to leader without losing it. So "once acknowledged, not lost" is delivered by requiring the message to be safely on multiple replicas before the ack returns, combined with leader failover that promotes an in-sync replica. The replication factor and the in-sync-replica acknowledgment requirement together form the durability knob — higher settings trade a little latency for stronger guarantees.

9. What junior / mid / senior answers look like

Junior: models a queue as a list with push/pop and delete-on-read. Works conceptually; misses durability, partitioning, ordering, and delivery semantics.
Mid: partitioned append-only log with offsets, replication for durability, consumer groups for parallelism, at-least-once + idempotency.
Senior: all that plus the commit-log rationale (sequential I/O, replay, multi-consumer), the full delivery-semantics spectrum with trade-offs, the ordering-vs-parallelism trade resolved by key-based partitioning, ISR-acks durability knob and leader failover, retention/compaction, and pull-vs-push backpressure reasoning.