Back to Notes

Design a Distributed Message Queue (Kafka-style)

1. Problem & Real-World Context

Design the message queue infrastructure itself — not a system that uses Kafka (that's every other problem in this KB touching [[Message Queues & Kafka]]), but Kafka-the-system: how partitions, replication, and consumer offset tracking actually work under the hood. This is a step below the usual "use a queue" HLD problems into "build the queue" territory — it tests whether a candidate understands the mechanics they've been treating as a black box everywhere else in this KB.

2. Requirements

Functional: producers publish messages to named topics; messages are durably stored and delivered to consumers; support multiple independent consumer groups reading the same topic; preserve ordering within a defined scope (per-partition, not global).

Non-functional: high throughput (millions of messages/sec); durability (a message, once acknowledged, must survive a broker crash); horizontally scalable (add brokers/partitions to increase capacity); configurable delivery guarantees (at-most-once / at-least-once / exactly-once, per [[Message Queues & Kafka]]'s general framing).

3. Capacity Estimation

  • At 1M messages/sec, average message size 1KB → ~1GB/sec of raw write throughput needing to be durably persisted — this single number is why the storage engine (§5) has to be a sequential-write-optimized log, not a general-purpose random-access database.
  • Partition count determines maximum parallelism: if a topic needs to sustain 1M messages/sec and a single partition (a single append-only log, inherently sequential) can sustain ~100K messages/sec, the topic needs at least 10 partitions just to keep up, before even considering consumer-side parallelism — this is the concrete mechanical link between partition count and achievable throughput.

4. Core Architecture

flowchart LR
    P[Producers] --> B1[Broker 1<br/>Partition 0]
    P --> B2[Broker 2<br/>Partition 1]
    P --> B3[Broker 3<br/>Partition 2]
    B1 -.replicates.-> B2
    B2 -.replicates.-> B3
    B3 -.replicates.-> B1
    B1 --> CG1[Consumer Group A]
    B2 --> CG1
    B3 --> CG1
    B1 --> CG2[Consumer Group B]

A topic is split into multiple partitions, each an independent, ordered, append-only log, hosted on a broker (with replicas on other brokers for durability). Producers write to a specific partition (chosen by a partitioning key, §6); each partition is consumed independently, and ordering is only guaranteed within a single partition, never across the whole topic — this is a deliberate, load-bearing design trade-off, not a limitation: it's exactly what makes horizontal scaling possible (independent partitions need no cross-partition coordination for either writes or reads).

5. The Log: Why Sequential Writes

Each partition is physically stored as an append-only log — new messages are always written at the end, never inserted or updated in place.

class PartitionLog:
    def __init__(self):
        self.segments: list[bytes] = []   # simplified — real systems use fixed-size segment files
        self.next_offset = 0

    def append(self, message: bytes) -> int:
        offset = self.next_offset
        self.segments.append(message)      # sequential write — no seek, no random I/O
        self.next_offset += 1
        return offset

    def read_from(self, offset: int, max_messages: int = 100) -> list[bytes]:
        return self.segments[offset : offset + max_messages]

Why this beats a general-purpose database for this workload: sequential disk writes are dramatically faster than random writes (even on SSDs, and especially on spinning disks, which many real Kafka deployments still use precisely because sequential throughput on disk is so cheap) — an append-only log never needs to seek to an arbitrary location to write or update a record, since nothing is ever updated in place. This single architectural decision is the foundation of Kafka's throughput characteristics, and naming it explicitly ("why not just use a database table as a queue") is a strong interview signal — see [[Message Queues & Kafka]]'s comparison table making this same point at a higher level.

6. Partitioning: How a Message Gets Assigned

import hashlib

def choose_partition(key: str | None, num_partitions: int, round_robin_counter: list[int]) -> int:
    if key is not None:
        # Key-based: same key always maps to the same partition, preserving per-key order
        return int(hashlib.md5(key.encode()).hexdigest(), 16) % num_partitions
    # No key: round-robin for even load distribution, no ordering guarantee needed/expected
    round_robin_counter[0] = (round_robin_counter[0] + 1) % num_partitions
    return round_robin_counter[0]

This is the exact mechanism behind "partition by entity key preserves per-entity ordering" — a concept used throughout this KB (News Feed's per-user post ordering, Ad-Click Aggregation's per-ad event ordering) without previously showing the underlying hash-to-partition mapping. All events for the same key deterministically land on the same partition, and within one partition, order is strictly preserved — that's the entire mechanism, not something more exotic layered on top.

7. Replication & Durability

Each partition is replicated across multiple brokers (a replication factor, e.g., 3) — one broker is the leader for that partition (handles all reads/writes), the others are followers that replicate the leader's log.

flowchart TD
    Producer --> Leader[Leader Broker<br/>Partition 0]
    Leader -->|replicate| F1[Follower Broker]
    Leader -->|replicate| F2[Follower Broker]
    Leader -->|ack after<br/>enough replicas confirm| Producer

acks configuration is the concrete durability/latency trade-off: acks=0 (fire-and-forget, fastest, no durability guarantee at all), acks=1 (leader confirms write to its own log, reasonably fast, but a leader crash before replication means the message is lost), acks=all/acks=-1 (wait for all in-sync replicas to confirm, slowest, strongest durability — a message survives even if the leader immediately crashes after acknowledging). This is the same latency-vs-durability axis that recurs throughout this KB (see [[CAP Theorem & Consistency Models]]'s PACELC framing) made completely concrete as a single config value.

Leader failure: if the leader broker for a partition dies, one of the in-sync followers (a replica that was fully caught up) is elected the new leader — "in-sync" is the crucial qualifier: promoting a follower that had fallen behind would silently lose the most recent messages, so only replicas that were provably caught up are eligible.

8. Consumer Offsets — How Consumers Track Progress

Each consumer (within a consumer group) tracks its own offset — the position up to which it has processed a partition's log. Critically, the offset is owned by the consumer, not pushed by the broker — this inversion of control is a deliberate design choice.

def consume_loop(partition: PartitionLog, consumer_offset_store: dict, group_id: str, partition_id: int):
    current_offset = consumer_offset_store.get((group_id, partition_id), 0)
    while True:
        messages = partition.read_from(current_offset, max_messages=100)
        if not messages:
            break
        for msg in messages:
            process(msg)
            current_offset += 1
            consumer_offset_store[(group_id, partition_id)] = current_offset   # commit progress

Why consumer-tracked offsets, not broker-pushed delivery: this is what makes replay possible — a consumer can reset its own offset backward and reprocess historical messages (useful for recovering from a bug, or backfilling a new consumer group) simply by changing where it reads from, with zero special support needed from the broker. A traditional message queue that deletes messages on consumption (point-to-point delivery) can't offer this at all — this offset model is the concrete mechanism behind Kafka's "log," not "queue," semantics, and behind the general at-least-once-plus-idempotent-consumer pattern used throughout [[Message Queues & Kafka]] (committing the offset only after successful processing, not before, is exactly the idempotent-consumer discipline referenced everywhere else in this KB).

Consumer group rebalancing: when a consumer joins or leaves a group, partitions are reassigned among the group's remaining/new members (each partition still owned by exactly one consumer within a group at a time) — this is what bounds a topic's maximum consumer-side parallelism to its partition count (§3's capacity math again: more consumers than partitions means some consumers sit idle).

9. Deep Dives / Follow-ups

  • Exactly-once semantics: achieved via idempotent producers (each message tagged with a producer ID + sequence number, so the broker can detect and discard a duplicate retry) combined with transactional writes spanning multiple partitions — a genuinely advanced feature layered on top of the base at-least-once log/offset model described above, not a redesign of it.
  • Log compaction: an alternative retention policy (instead of time/size-based deletion) that keeps only the latest value per key, deleting older values for the same key — useful for a "current state" topic (e.g., the latest known value of a user's profile) rather than a pure event stream where every historical event matters.
  • ISR (in-sync replica) set management: the pool of "fully caught up" replicas eligible for leader election shrinks and grows as followers fall behind or catch up — a slow follower can be temporarily removed from the ISR set (so it doesn't block acks=all writes waiting on it) and re-added once it catches up.

10. Interview Drill Questions

  1. Why is a message queue's log append-only instead of supporting in-place updates like a database? — Sequential writes are dramatically faster than random writes at the storage-hardware level, and this workload (write once, never update, read sequentially from some offset) never needs in-place updates — an append-only log is a direct match for the actual access pattern, trading away update capability the workload never needed in the first place.
  2. Why does partitioning by key guarantee per-entity ordering, but the whole topic has no global order? — All messages for the same key hash to the same partition deterministically, and a single partition's log preserves strict write order — but different keys can land on different partitions, which are consumed independently with no coordination between them, so there's no meaningful "global" order across keys, only within one.
  3. A consumer crashes after processing a message but before committing its offset. What happens on restart? — It resumes from the last committed offset, which is before the message it had already processed — that message gets reprocessed, which is exactly the at-least-once delivery guarantee, and is why the consumer's own processing logic must be idempotent (see [[Message Queues & Kafka]]'s general idempotent-consumer pattern) rather than assuming exactly-once by default.
  4. Why can a Kafka consumer "replay" old messages, while a traditional queue (SQS-style) generally can't? — Because offset tracking is consumer-owned and the log retains messages for a configured retention period regardless of consumption — resetting a consumer's offset backward and re-reading is just changing where it reads from; a point-to-point queue that deletes a message once consumed has nothing left to replay.
  5. What happens if a partition's leader broker crashes right after acknowledging a write with acks=1? — If the message hadn't yet been replicated to any follower before the crash, it's lost — acks=1 only guarantees the leader's own log had it, not that any replica did; this is precisely why acks=all exists for workloads that can't tolerate that risk, at the cost of higher write latency waiting for replica confirmation.

Cross-links

[[Message Queues & Kafka]] · [[CAP Theorem & Consistency Models]] · [[Ad-Click Aggregation]] · [[News Feed - Twitter Feed]] · [[Consistent Hashing]]