Chapter 20: Design a Real-Time Messaging System

Curriculum: Distributed Systems from First Principles Chapter: 20 of 24 Part: 10 — Synthesis Design Problems Framework: Apply Chapter 19's six-step process in full Chapters exercised: 1 (latency), 2–3 (storage internals), 4–5 (replication), 6 (consistency), 7–8 (sharding, consistent hashing), 9 (caching), 10 (LSM trees), 11–12 (consensus, Raft), 13 (distributed transactions), 14–15 (queues, Kafka), 16 (load balancing), 17 (rate limiting), 18 (observability), 19 (design framework) Estimated reading time: 80–90 minutes

The Problem Statement

Design a real-time messaging system supporting 1:1 private chats and group chats with up to 500 members. Users must receive messages within 2 seconds of sending. The system must show delivery receipts (sent → delivered → read) and online presence (who is currently active). Design for WhatsApp scale.

Step 1: Requirements Clarification

Functional Requirements

Write these down explicitly before touching architecture:

1. Send a message: A user sends a text message to another user (1:1) or a group. Message is delivered to all online recipients in real time. Offline recipients receive it when they next come online.
2. Receive messages: Recipients receive new messages without polling — the server pushes them.
3. Delivery receipts: Three states: sent (server received it), delivered (recipient's device received it), read (recipient opened the conversation). The sender sees these states update in real time.
4. Online presence: Users can see whether contacts are online, and their last-seen timestamp.
5. Message history: A user opening a conversation sees the last N messages. Scrolling up loads older messages (pagination).
6. Group messaging: Messages in a group with G members are delivered to all G members. Max group size: 500.

Scope out for this design: voice/video calls, end-to-end encryption key exchange (architectural implication: metadata still flows through servers), file/image attachments beyond text (covered as an extension at the end).

Non-Functional Requirements

• Scale: 2 billion registered users, 100 million DAU. Each DAU sends approximately 40 messages/day. 50% of messages are in group chats (average group size: 30 members).
• Latency: Message delivered to online recipients within 2 seconds P99. Message storage acknowledged within 500ms.
• Availability: 99.99% (52 minutes downtime/year). Messages must never be lost.
• Ordering: Messages within a conversation must be delivered in order. Cross-conversation ordering is irrelevant.
• Consistency: Eventual consistency for delivery receipts is acceptable (reading "delivered" 0.5 seconds before the tick appears is fine). Message content itself must be durable — once the server acknowledges a message as "sent," it must not be lost.
• Durability: Stronger than typical — messages are personal communications. Zero data loss once acknowledged.

Step 2: Estimate Scale

Work through the numbers before any architecture decisions.

Messages per second:
  100M DAU × 40 messages/day / 86,400 seconds = ~46,000 messages/second
  Peak (3× average): ~138,000 messages/second

Group message fan-out:
  50% group messages × 46,000/s = 23,000 group messages/second
  Average group size: 30 members → 23,000 × 30 = 690,000 delivery events/second
  Total delivery events: 23,000 (1:1) + 690,000 (group) = ~713,000 deliveries/second

Active WebSocket connections:
  100M DAU × fraction online simultaneously ≈ 30M concurrent connections
  (Users keep the app open; connections persist for the session)

Message storage:
  Average message: 100 bytes (short text)
  46,000 messages/s × 100 bytes = 4.6 MB/s = ~146 TB/year
  With 5-year retention: ~730 TB of message data (hot + warm storage)

Delivery receipt writes:
  Each message triggers 3 state transitions (sent → delivered → read)
  46,000 × 3 = ~138,000 receipt writes/second

Presence updates:
  30M online users × heartbeat every 30 seconds = 1M presence writes/second

Key observations from the numbers:

• 30M concurrent WebSocket connections — this is the hardest infrastructure challenge. At ~64KB memory per TCP connection, that's ~1.9 TB of connection state. Needs hundreds of connection servers.
• 713,000 delivery events/second — primarily driven by group fan-out. Needs async pipeline.
• 138,000 receipt writes/second — high write throughput for a relational model. Points toward a write-optimised store (LSM trees — Chapter 10).
• 1M presence writes/second — must be in-memory only (Redis). Cannot touch disk.

Step 3: Core Entities and Data Model

Define what's stored before choosing how.

Composite primary keys: ConversationMember (conversation_id, user_id), Message (conversation_id, message_id) — partition by conversation — and MessageReceipt (message_id, recipient_id).

Critical design decision in the data model: Message is partitioned by conversation_id. All messages in a conversation live together on the same storage partition — this enables efficient "fetch last 50 messages for conversation X" queries (sequential scan within partition). Spreading messages randomly by message_id would require scanning across partitions to reconstruct a conversation.

message_id ordering within a conversation: Use a per-conversation sequence number or a time-based ID (Snowflake — Chapter 7's shard key discussion). If two messages in the same conversation have the same millisecond timestamp, the sequence number breaks the tie and establishes ordering. Globally, message IDs need not be ordered — only within a conversation.

Step 4: Core Architecture — The Connection Layer

The fundamental problem is: how does the server push a message to a specific user in real time?

HTTP is request-response — the client asks, the server responds. Real-time push requires the connection to remain open so the server can initiate delivery. Three options:

Short polling: Client polls GET /messages?since=T every few seconds. Simple. High latency (up to polling interval). Massive wasted load (100M users × 1 request/2s = 50M requests/second just for polling, 99% returning nothing). Eliminated.

Long polling: Client sends a request; server holds it open until a message arrives or a timeout (30s). Client immediately re-polls after receiving a response. Better than short polling — fewer wasted requests. Still inefficient: every message delivery requires a new HTTP connection establishment (~50ms for TLS handshake — Chapter 1).

WebSocket: Client and server establish a TCP connection with a WebSocket upgrade handshake. The connection stays open indefinitely — both sides can send data at any time. Server pushes messages directly. Zero setup latency per message after initial connection. The correct choice for real-time messaging.

Connection Server Architecture

When user Alice connects via WebSocket to Connection Server 7:

1. Connection Server 7 registers: SET presence:alice {"status":"online","server":"cs-007"} in Redis
2. Alice's WebSocket handle is stored in Connection Server 7's local memory

When Bob sends Alice a message:

1. Message Service looks up Alice's presence in Redis: GET presence:alice → {"server":"cs-007"}
2. Message Service calls Connection Server 7 via gRPC: deliver(user_id=alice, message=...)
3. Connection Server 7 looks up Alice's WebSocket in its local routing table and pushes the message

This is the core routing mechanism. Each message delivery requires one Redis lookup (O(1), ~0.5ms) and one gRPC call to the correct connection server (~0.5ms within the datacenter). Total real-time delivery path: ~1ms — well under the 2-second requirement.

The load balancer (Chapter 16) in front of the connection server fleet must use sticky sessions or, better, consistent hashing on user_id so that reconnecting users tend to land on the same server. This reduces presence re-registration overhead but is not required for correctness — the Redis presence store is the authoritative routing table.

Step 5: The Message Send Flow — Write Path

A user sends a message. Trace the complete write path:

Why Cassandra for message storage? Chapter 10's LSM tree analysis applies directly: 138,000 writes/second (messages + receipts) with simple key lookups and range scans within a partition. Cassandra's LSM-tree storage engine (identical to LevelDB/RocksDB architecture) handles this write throughput on a modest cluster. The access pattern — write once, read sequentially within a conversation — is exactly what LSM trees optimise for. PostgreSQL with B-Trees would need significant sharding to handle this write rate (Chapter 10's "write amplification" analysis shows B-Trees pay a higher cost per write).

Why Kafka for the fan-out pipeline? The Message Service's job is to acknowledge the write quickly. Fan-out — delivering to all recipients — is done asynchronously by Kafka consumers. Partitioning Kafka by conversation_id (Chapter 15's partition key design) ensures messages in a conversation are always processed in order by the same consumer. This is essential: if two messages in a conversation are processed by different consumers in parallel, they might be delivered out of order.

Step 6: Message Delivery — The Fan-out Flow

After the message is stored and ACK'd, Kafka consumers handle delivery:

Fan-out performance math:

• Average group size: 30 members
• Fan-out workers process 23,000 group messages/second
• Each fan-out: 30 Redis lookups + 30 gRPC calls (for online members) or 30 push notifications (for offline)
• At 30M online users / 2B total users = 1.5% online rate: most group members are offline
• Real delivery events (online): 23,000 × 30 × 0.015 = ~10,350 gRPC deliveries/second
• Push notifications (offline): 23,000 × 30 × 0.985 = ~680,000 push notifications/second

680,000 push notifications/second is substantial. APNs and FCM have rate limits per application (Chapter 17). The Push Notification Service maintains token bucket rate limiters per provider and uses a dedicated Kafka topic to queue outbound notifications, consuming at the provider's rate limit. This is leaky bucket applied to external API calls — exactly Chapter 17's outbound rate limiting pattern.

Delivery ordering guarantee: Because the Kafka fan-out topic is partitioned by conversation_id, all messages in one conversation are processed by the same fan-out worker in partition order. Delivery to each recipient preserves the same sequence as the Kafka partition. Per-conversation ordering is guaranteed. Cross-conversation ordering is not (different partitions, different workers) — which is correct per requirements.

Step 7: Delivery Receipts — The Feedback Path

When Alice receives a message on her device, her app sends a delivery receipt back:

When Alice opens the conversation (read receipt):

App sends: { "type": "receipt", "conversation_id": 9021, "status": "read", "up_to_message_id": 12350 }
→ Marks all messages up to message_id 12350 as "read" by Alice in one write.
   (Batch receipt, not per-message, to reduce write load)

Idempotency: Receipt writes use INSERT ... ON CONFLICT DO UPDATE (Cassandra's IF NOT EXISTS or upsert). Receipts can be delivered more than once (network retry), and the result must be the same. This is exactly Chapter 13's idempotent operation requirement.

Step 8: Offline Message Sync — Reconnection Flow

A user who was offline comes back online:

Why Cassandra's clustering key ordering makes this fast: The Message table's primary key is (conversation_id, message_id) — conversation_id is the partition key, message_id is the clustering key. In Cassandra's SSTable files (Chapter 10), rows within a partition are stored in clustering key order. WHERE conversation_id = X AND message_id > Y is a sequential range scan within one SSTable partition — O(messages_since_Y) with minimal I/O. This is the same B-Tree range scan efficiency (Chapter 2) but at LSM-tree write throughput.

Step 9: Presence — The High-Frequency Heartbeat

Online presence is the hardest part to implement correctly at scale. 30M concurrent connections, each sending a heartbeat every 30 seconds = 1M presence writes/second. This cannot touch disk.

Heartbeat mechanism:

Client → Connection Server: WebSocket ping (every 30 seconds)
Connection Server → Redis: EXPIRE presence:{user_id} 60
  (Extend TTL by 60 seconds. If no heartbeat arrives in 60s, key expires → user "offline")

The EXPIRE command refreshes the key's TTL without writing new data. In Redis, EXPIRE on an existing key is O(1). 1M EXPIRE commands/second is within a Redis cluster's throughput (100K ops/second per node × 10 nodes = 1M ops/second).

Last-seen timestamp: Updated only when a user goes offline (WebSocket closes or heartbeat times out), not on every heartbeat. This reduces writes from 1M/second to the offline event rate (far lower).

Connection Server disconnection detection: When a WebSocket closes:

Presence subscription: User A wants to see User B's online status. When A opens a chat with B, A's app subscribes to B's presence via their Connection Server. The Connection Server subscribes to the Redis pub/sub channel for B's presence changes. When B goes offline, Redis pub/sub delivers the event to all Connection Servers that have subscribers for B, who then push the update to those users' WebSockets.

Redis pub/sub (Chapter 9's data structures) is not persistent — messages are fire-and-forget. If a Connection Server is momentarily disconnected when a presence change fires, it misses it. Acceptable: presence is soft state. The next heartbeat (30s) will reconcile the state. Missing a single presence event for 30 seconds is not a correctness problem.

Step 10: Group Chat — The Fan-out Bottleneck and Its Limits

Groups with 500 members at 46,000 messages/second would produce 46,000 × 500 = 23M delivery events/second — unsustainable. But the 500-member limit and the 50% group message fraction moderate this in practice.

The celebrity problem revisited (Chapter 19): A 500-member group with a very active conversation sends 10 messages/minute → 5,000 delivery events/minute for that group. With thousands of such groups simultaneously, the fan-out workers must process the deliveries without a single group monopolising the queue. Each conversation_id lands on a fixed Kafka partition (Chapter 15), so one extremely active group monopolises one partition but not others. Horizontal scaling of fan-out workers (adding more Kafka consumer instances) adds more partitions and more parallelism.

Group member list caching: For a 500-member group, fetching the member list from Cassandra for every message (every 30 seconds if the group is active) is wasteful. Cache group member lists in Redis with a 5-minute TTL. Cache invalidation: when a member joins or leaves, the write path invalidates the cache entry for that conversation_id. Since membership changes are rare compared to messages, cache hit rate is high (~99.9%).

Large group optimisation: For groups with > 100 members, do not deliver via individual gRPC calls to connection servers. Instead, publish the message to a dedicated Kafka topic partitioned by recipient shard. Connection servers consume from this topic for their assigned user shards. This inverts the delivery model: instead of the fan-out worker pushing to each connection server, connection servers pull from the delivery queue. This is the difference between push-based and pull-based consumer architecture (Chapter 14's push vs pull analysis) — pull is better for high-fan-out scenarios because it avoids the N×M gRPC call matrix.

Step 11: The Complete Architecture Diagram

Step 12: Failure Modes and Trade-Offs

Every component fails. Design the degraded states explicitly.

Connection Server failure (one of 300 crashes):

• Impact: ~100,000 users lose their WebSocket connection.
• Recovery: Clients detect disconnect (WebSocket close event) within 2–10 seconds. They reconnect to any available Connection Server (load balancer removes failed server from pool within 30 seconds — Chapter 16's health checking).
• Messages sent to the offline users during the reconnect window: stored in Cassandra, delivered via sync on reconnect.
• Presence entries in Redis: they expire after 60 seconds (their TTL). No cleanup needed.
• Verdict: transient outage for affected users, fully self-healing within 60 seconds.

Cassandra node failure:

• Cassandra replicates with replication factor 3 (RF=3) — each partition's data lives on 3 nodes (Chapter 4's replication). A single node failure loses no data.
• Writes continue to 2 surviving replicas (quorum writes: write to majority = 2 of 3). Write latency increases slightly (must wait for 2 instead of typically the fastest 1).
• Chapter 10's compaction: during node failure recovery, the rejoining node streams data from peers and compacts. Service remains available throughout.
• Verdict: zero data loss, negligible availability impact.

Redis cluster failure (presence service):

• Writes: new WebSocket connections cannot register presence. Fan-out workers cannot look up recipient connection servers.
• Degraded mode: fan-out workers fall back to push notifications for all recipients (treating everyone as offline). Messages still delivered — just via push notification rather than real-time WebSocket push. Latency increases (push notifications take 1–10 seconds vs < 1 second for WebSocket delivery).
• 2-second P99 requirement may be temporarily violated. Acceptable as a rare degraded mode.
• Redis Cluster with 6+ shards using consistent hashing (Chapter 8): a single shard failure impacts only the users hashed to that shard (1/6 ≈ 16%), not all users.

Kafka cluster failure:

• Messages already stored in Cassandra are safe. The fan-out pipeline stalls — no deliveries until Kafka recovers.
• Kafka's ISR (Chapter 15's min.insync.replicas=2) ensures no message loss. Recovery time: minutes.
• During Kafka outage: Message Service still accepts writes (store to Cassandra + local queue in memory up to a limit). After recovery, replay from stored offset.
• Verdict: delivery delayed but not lost.

The split-brain scenario (network partition — Chapter 6): Two datacenters in active-active configuration. A network partition separates them. Alice (in DC1) sends a message to Bob (in DC2). DC1's Kafka and Cassandra cannot see DC2's.

• Chapter 6's CAP theorem: under partition, choose availability (keep accepting writes) or consistency (refuse writes until partition heals).
• For messaging: choose availability. Alice's message is stored in DC1. When the partition heals, the message is replicated to DC2 and delivered to Bob.
• Conflict resolution: two messages sent simultaneously from different DCs with the same (conversation_id, timestamp) — use Snowflake message IDs (contain datacenter bits — Chapter 7). The datacenter bits break ties deterministically. Message ordering converges after partition heals.

Step 13: The Message Ordering Guarantee — Formally

The ordering guarantee needs precise statement, because it's weaker than it might appear:

What is guaranteed: Within a single conversation, messages are delivered to all recipients in the same order. If Alice sends message A, then message B (in the same conversation), all recipients see A before B.

What is not guaranteed: If Alice sends message A and Carol (in the same group) sends message B simultaneously (within milliseconds of each other), the ordering between A and B is determined by Kafka partition ordering — whichever arrives at the Kafka broker first becomes "earlier." Different recipients might briefly see different orderings during delivery, but after all fan-out events are processed, everyone converges on the same ordering (the Kafka partition order).

Implementation: The Kafka partition for a conversation is totally ordered (Chapter 15 — partition-level ordering guarantee). The fan-out consumer processes messages from this partition sequentially. All delivery events for a conversation are produced to recipients in partition order. Recipients therefore see messages in the same sequence.

Clock skew: Chapter 1's physical reality — clocks drift. If Alice's phone clock is 2 seconds ahead, her message gets a Snowflake ID with a future timestamp. The Kafka partition still orders by arrival time (insertion order), not timestamp. The timestamp in the message is metadata for display ("sent at 3:04pm") — it does not affect delivery order. Ordering is determined by the Kafka offset, not the message timestamp. This decouples ordering correctness from clock correctness.

Step 14: Observability — What to Instrument (Chapter 18 Applied)

Define the SLOs and the metrics that measure them:

SLO 1: 99.9% of messages delivered to online recipients within 2 seconds.

SLI: (messages delivered within 2s) / (total messages sent to online recipients)
Metric: histogram message_delivery_latency_seconds{recipient_status="online"}
Alert: rate(message_delivery_latency_seconds_bucket{le="2.0"}[5m])
       / rate(message_delivery_latency_seconds_count[5m]) < 0.999
Burn rate alert: if burn rate > 14×, page immediately.

SLO 2: 99.99% of stored messages never lost (durability).

SLI: messages acknowledged - messages lost / messages acknowledged
Metric: counter messages_acknowledged_total, counter messages_lost_total
  (messages_lost is detected by reconciliation job — see below)

Key metrics per component:

Connection Server fleet:

websocket_connections_active (gauge, per server)
websocket_messages_received_total (counter)
websocket_delivery_latency_seconds (histogram)

Fan-out workers:

fanout_events_total{result="delivered_realtime"|"sent_push"} (counter)
fanout_processing_latency_seconds (histogram)
fanout_kafka_consumer_lag{topic="new_messages", partition=N} (gauge) ← Chapter 15's consumer lag

Kafka consumer lag is the most critical fan-out metric: if consumer lag grows (the worker is falling behind the producer), deliveries are delayed. Alert when lag exceeds 10,000 messages on any partition.

Presence service:

presence_redis_latency_seconds (histogram)
presence_lookups_total{result="online"|"offline"} (counter)
presence_updates_per_second (gauge)

The reconciliation job: Durability SLO requires detecting lost messages. A background job runs hourly, sampling 0.01% of recent messages by reading from Cassandra and verifying they appear in delivery receipts. If a message has no receipt after 2 minutes (online recipient) or 24 hours (offline recipient, allowing time for notification), log a message_lost metric. In practice, this detects bugs in the write path before they accumulate.

Extensions: Media, Search, End-to-End Encryption

Media (Images, Video)

Text messages stay in Cassandra (small, fast). Media lives in S3 + CDN (large, separate tier). The message in Cassandra contains only a URL. This keeps Cassandra row sizes small (~100 bytes for text vs ~1MB for images) and separates the throughput characteristics of the two tiers.

Message Search

Text messages are written to Cassandra (primary store). Asynchronously indexed into Elasticsearch via a Kafka consumer. Elasticsearch provides full-text search within a conversation. The indexing lag is acceptable — users don't expect real-time search of a message they sent 1 second ago.

End-to-End Encryption

E2EE means message content is encrypted on the sender's device and decrypted only on the recipient's device. The server stores and delivers ciphertext — it cannot read the content. This changes the architecture in one way: delivery receipts must be sent by the recipient's device (not inferred from server delivery), since the server cannot verify decryption. The receipt flow described above already matches this model — receipt events come from the recipient's app.

Vocabulary Map

Practice Problems

Problem 1 — Failure Analysis

A Connection Server (CS-007) crashes while holding 100,000 WebSocket connections. All 100,000 users lose connectivity simultaneously. Trace the exact sequence of events:

(a) Within 5 seconds: what does the load balancer do? What do clients' apps do? What happens to the 47 messages that were in-flight (sent by users to CS-007 but not yet forwarded to Message Service) at the moment of crash?

(b) Within 60 seconds: what happens to the 100,000 users' presence entries in Redis (TTL = 60s)? What do the fan-out workers do when they try to deliver to users whose connection_server_id is "cs-007" but CS-007 is down?

(c) When the 100,000 users reconnect to new Connection Servers: they send a sync request with their last_seen_message_ids. Some missed messages arrived while they were disconnected. Trace the sync flow: Cassandra query, message delivery, bulk receipt. What is the maximum number of messages a user might have missed, and how does the system bound this?

(d) Design an improvement: a "shadow registry" where each Connection Server's assigned users are tracked in Redis (a Redis Set per CS server). When a CS server goes down, the health checker publishes the crash event to a Kafka topic. A cleanup worker reads the event and immediately marks all users in that CS's shadow registry as offline (instead of waiting 60 seconds for TTL expiry). What is the trade-off of this approach vs. the TTL approach?

Problem 2 — Design from Scratch

The current design delivers messages to group members via individual gRPC calls from the fan-out worker to each recipient's Connection Server. For a 500-member group, one message triggers up to 500 gRPC calls (one per online member). At peak with many active large groups, this creates a gRPC call storm.

Redesign the delivery for large groups (> 100 members) using a pull-based model: Connection Servers subscribe to a Kafka topic partitioned by user shard, and fan-out workers write delivery events to the topic instead of making gRPC calls.

Specify: (a) how the Kafka topic is partitioned (what is the key, how many partitions, how many Connection Servers consume), (b) how a Connection Server knows which delivery events are for its users (filtering), (c) latency implications compared to the gRPC push model (add the extra Kafka produce + consume step latency from Chapter 1's numbers), (d) what happens when a Connection Server crashes — how does its Kafka consumer group handle the failover (Chapter 15's consumer group rebalancing), and (e) at what group size does pull become preferable to push? Derive the crossover point based on gRPC call overhead vs. Kafka produce overhead.

Problem 3 — Synthesis

Connect the messaging system to Chapter 13's distributed transactions and Chapter 12's consensus.

(a) The message send operation involves two writes: Cassandra (message storage) and Kafka (fan-out event). These are two separate systems with no shared transaction coordinator. What happens if the Cassandra write succeeds but the Kafka produce fails? Is the message lost? Is it duplicated? The Message Service retries the Kafka produce — is this safe (idempotent)? Reference Chapter 15's idempotent producer design.

(b) Delivery receipts require two causally linked operations: "mark as delivered in Cassandra" and "notify sender via Kafka." If Cassandra succeeds but Kafka fails, the sender never sees the delivery tick — but the receipt is stored. On Kafka retry, the receipt event is re-produced. The fan-out consumer delivers the receipt to the sender again. The sender's app receives two "delivered" events for the same (message_id, recipient_id). Is this a problem? How does the app handle duplicate receipt events? What idempotency key prevents the duplicate from showing double-tick twice?

(c) Presence is stored in Redis (volatile, no persistence) and the message store is Cassandra (durable). A message is sent to a user who appears online (Redis says status="online", server="cs-007"). The fan-out worker calls CS-007 to deliver. CS-007 responds "user not found" (the user disconnected 1 second ago, Redis entry hasn't expired yet). The fan-out worker falls back to push notification. Now the user reconnects and syncs — they get the message via sync AND a push notification arrives on their device. How does the app deduplicate? What field is the deduplication key? Connect this to Chapter 6's eventual consistency — the Redis presence state is eventually consistent with the true connection state. How long is the staleness window, and what are its consequences?

Problem 4 — Go Deeper

Analyse the ordering guarantee formally under concurrent sends.

Alice and Carol are both in a group chat. Alice sends message A at T=1000ms. Carol sends message B at T=1001ms. Both messages arrive at the same Kafka broker at approximately the same time.

(a) The Kafka partition for this conversation is hosted on Broker 3. Alice's message lands on the Message Service instance running on Server A; Carol's on Server B. Both produce to the same Kafka partition on Broker 3. Kafka guarantees ordering within a partition by offset. If Server A's produce request arrives at Broker 3 at T=1002ms and Server B's at T=1003ms, what is the partition order? Is this the "correct" ordering from the users' perspective?

(b) Now Server A's produce request experiences a network delay and arrives at T=1005ms, after Server B's at T=1003ms. What is the partition order now? Does this "feel wrong" to Alice (her message appears after Carol's even though she sent it first by clock time)? Is this actually a correctness violation or just a perception issue? How does WhatsApp/iMessage handle the UX of out-of-perceived-order messages?

(c) Design a stronger ordering guarantee: per-conversation sequence numbers. A Redis counter conv_seq:{conversation_id} is atomically incremented (INCR) for each new message, and the sequence number is stored with the message. The Kafka partition now orders by this sequence number instead of arrival time. Trace the write path with sequence number assignment. What happens if two Message Service instances try to INCR the same counter simultaneously? Is the Redis INCR atomic? Does this solve the ordering perception problem from (b)? What new failure mode does this introduce (hint: what if the Redis INCR succeeds but the Cassandra write fails)?

Problem 5 — Connect to Previous Chapters

This problem synthesises the entire curriculum through the lens of the messaging system.

You are preparing for an incident post-mortem. Last Tuesday at 2:47pm, message delivery latency spiked to P99 = 45 seconds for 8 minutes before self-resolving. Your task is to reconstruct what happened using observability data and your knowledge of the system's components.

The following metrics spiked at 2:47pm:

• fanout_kafka_consumer_lag{topic="new_messages"} grew from 0 to 840,000 (all partitions)
• cassandra_write_latency_seconds{quantile="0.99"} grew from 8ms to 1,200ms
• cassandra_compaction_pending_tasks was 4,200 (normally < 10)

(a) Diagnose the root cause: Which Chapter 10 concept explains 4,200 pending compaction tasks and how does compaction backlog cause write latency to spike to 1,200ms? Draw the causal chain: compaction backlog → write path → Kafka producer → fan-out lag → delivery latency.

(b) Reconstruct the trigger: Cassandra compaction backlog doesn't appear from nowhere. The cluster was receiving 138,000 writes/second (normal). At 2:45pm, a new Cassandra node was added to the cluster (routine scaling operation). What does Cassandra do when a new node joins? (Chapter 7 and 8: token ring rebalancing, streaming data to the new node.) How does this streaming compete with compaction for disk I/O? How does disk I/O contention cause write latency to spike?

(c) Design the fix: Two approaches — (i) rate-limit the streaming throughput when adding a new Cassandra node so it doesn't compete with live traffic writes, (ii) add a circuit breaker in the Message Service: if Cassandra write latency exceeds 500ms, shed write load (reject new message stores) and queue them in memory for retry. For each approach, state: what Chapter it connects to (Chapter 10 for compaction, Chapter 17 for rate limiting, Chapter 14 for queuing), the trade-off, and which you'd implement first.

(d) Add the observability: Define the specific metric, alert expression, and runbook entry (Chapter 18) that would have detected this incident 5 minutes earlier — before user-visible degradation. The alert must fire before P99 delivery latency crosses 2 seconds but after the compaction backlog starts growing. What is the exact PromQL expression?

What's Coming Next

Chapter 21 designs a globally distributed key-value store — the infrastructure layer beneath everything you've built. A key-value store sounds simple: get(key) and put(key, value). But building one that serves millions of operations per second, replicates across 5 datacenters, tolerates network partitions, and provides tunable consistency (from eventual to linearizable) requires synthesising consensus (Chapters 11–12), replication (Chapters 4–5), sharding (Chapters 7–8), and LSM storage (Chapter 10) into a single coherent system. It's DynamoDB from first principles.

Chapter 20 complete. This is the first full synthesis design problem — every architectural decision in this chapter traces back to a specific chapter in the curriculum. If any component choice feels arbitrary (why Cassandra? why Kafka partition by conversation_id? why Redis TTL for presence?), trace it to its chapter and re-read the relevant section. That connection between first-principles analysis and architecture decision is the skill being built. Problem 5 is the hardest in the curriculum so far: it asks you to diagnose an incident using observability data and reconstruct the causal chain from Chapter 10 through Chapter 18. Work it on paper before reading ahead.