4. Chat System (WhatsApp) Advanced

A. Realistic Interview Prompt

Unlike the previous three problems, the core challenge here isn't a request/response API at all — it's maintaining long-lived, stateful connections for hundreds of millions of concurrent users, and routing a message to whichever specific server happens to hold the recipient's connection right now. That routing problem — "which of my N servers is this user actually connected to" — is the single idea that unlocks the rest of the design.

B. Difficulty

Advanced from the first sentence — there is no simple V1 that's merely "naive," because even the most basic version of this problem requires picking a connection model (polling vs. WebSockets) before anything else can be discussed. This problem is closer in spirit to Uber than to URL Shortener or Rate Limiter: the naive design is naive specifically because it picks the wrong transport, not because it skips a later optimization.

C. What This Problem Tests

• Understanding of persistent connections (WebSockets) versus request/response HTTP, and why real-time delivery structurally requires the former
• The "which server is this user connected to" routing problem — recognizing it as a distinct piece of state that must live somewhere shared, not on any one connection server
• Ordering and delivery-guarantee reasoning distinct from Rate Limiter's approximate-counting tolerance — a chat message silently dropped or duplicated is a much more visible bug than an off-by-one rate limit
• Group-chat fanout, which rhymes with the News Feed problem's fanout discussion but with much stricter latency and ordering requirements
• Awareness that end-to-end encryption changes what the server is even allowed to see — a constraint that reshapes storage, search, and multi-device sync simultaneously

D. Requirements

Functional

1. Users can send/receive 1:1 messages in real time when both are online
2. Messages sent while the recipient is offline are delivered once they reconnect (store-and-forward)
3. Users can create groups and send messages that fan out to all members
4. Delivery status is tracked and shown to the sender: sent → delivered → read

Non-Functional

• Low latency — a message should arrive at an online recipient in <100ms-class time; this is a "typing and seeing replies live" interaction
• Massive concurrent-connection scale — this document uses 500M DAU with ~150M concurrent connections at peak as the standard illustrative input
• Ordering guarantee — messages within one conversation must arrive in the order they were sent, even across server failovers
• No message loss — a message accepted by the server must eventually be delivered, even across recipient disconnects, reconnects, or server crashes
• Durability without server-side plaintext access (extension, S) — end-to-end encryption means the server must do all of the above (routing, ordering, storage) without being able to read message content

Out of scope: voice/video calls, status/stories, payments — each is its own design problem layered on the same connection infrastructure.

E. Clarifying Questions

F. Assumptions

• Confirmed: 1:1 and group real-time messaging, offline delivery, sent/delivered/read status.
• Assumption: WebSocket-based persistent connections, not HTTP polling — the only transport that meets the <100ms real-time NFR without wasteful constant re-polling.
• Assumption: strict per-conversation ordering is required — the more interesting, more commonly-asked version of this problem.
• Assumption: single primary device per user for the base design (J-R); multi-device sync is an explicit, clearly-flagged extension folded into the encryption deep dive (S), since real multi-device sync (as in WhatsApp/Signal) is inseparable from how encryption keys are distributed.
• Assumption: end-to-end encryption is in scope as the final deep dive (S) — it's the single hardest, most differentiating extension for this specific problem, the same way multi-region was for Rate Limiter.

G. Capacity Estimation

H. Core Entities

I. API Design

WebSocket events (bidirectional, over a persistent connection):
  CLIENT -> SERVER: send_message { conversation_id, client_msg_id, content }
  SERVER -> CLIENT: message_ack { client_msg_id, message_id, seq_num }
  SERVER -> CLIENT: new_message { message_id, conversation_id, sender_id, seq_num, content }
  CLIENT -> SERVER: ack_delivered { message_id }
  CLIENT -> SERVER: ack_read { message_id }
  SERVER -> CLIENT: status_update { message_id, status }

REST (non-real-time concerns):
  POST /v1/conversations           { member_ids } -> { conversation_id }
  GET  /v1/conversations/{id}/history?cursor=&limit=

Why a separate client_msg_id from the server-assigned message_id: the client generates its own ID before the network round-trip completes, so it can optimistically render the message as "sending" immediately and later reconcile it with the server's authoritative ID and sequence number — the same idempotency-key pattern used to make retries safe elsewhere in distributed systems (a client that doesn't hear back and retries the send won't create a duplicate message, because the server can dedupe on client_msg_id).

J. Basic / Naive High-Level Design (V1)

The simplest thing that satisfies real-time delivery in isolation: clients hold a persistent WebSocket to a single connection server; that server looks up the recipient's connection on itself and pushes the message directly.

V1 — works only when sender and recipient happen to be connected to the exact same server.

Why this breaks immediately, not eventually: at any real scale there are ~150 connection servers (G), and a message's sender and recipient are connected to two different servers almost every single time — there is no shared state telling Server 1 that User B is actually attached to Server 47. This is the WhatsApp-specific version of Rate Limiter's V1 problem: correctness that silently depends on "only one server exists" is not a simplification, it's a design that doesn't function at all once a second server is added — the exact motivation for the routing layer in N.

K. Data Model & Store Choice

Messages/conversations: a wide-column store (Cassandra-class), partitioned by conversation_id and clustered by seq_num/timestamp — this access pattern ("give me this conversation's messages in order") is exactly what a wide-column store's partition+clustering-key model is built for, at the write throughput (G) a relational single-instance store would struggle to sustain.

Session/routing state (Session): Redis or ZooKeeper — small, ephemeral, extremely hot-path data (looked up on every single message send) that must be shared across every connection server; losing it on a restart is recoverable (the client simply reconnects and re-registers), so it doesn't need durability guarantees, mirroring the ephemeral Counter reasoning from Rate Limiter's data model.

L. End-to-End Flow — 1:1 Message, Both Users Online

M. Deep Dive 1 — Connection Management at Scale

Requirement this addresses: the concurrent-connection NFR from D and G — 150M simultaneous long-lived connections is the foundational constraint everything else builds on.

Why WebSockets, not HTTP polling or long-polling: polling means every idle client repeatedly asks "anything new?", burning connections and server cycles on empty answers — the inverse of what a <100ms real-time NFR needs. A WebSocket is a single persistent, bidirectional connection: the server can push the instant a message arrives, with zero polling overhead. Long-polling is a middle ground (better than plain polling) but still re-establishes a connection per round-trip; a full WebSocket avoids that entirely.

Why connection servers must be a distinct tier from stateless API/business-logic servers: a WebSocket connection is stateful — it lives on one specific machine for its entire duration, unlike a stateless HTTP request that any server can handle. This single fact is why a load balancer in front of connection servers must support sticky sessions or connection-aware routing (a plain round-robin LB would silently break an in-progress WebSocket), and it's why connection servers are event-loop-based (handling many thousands of idle connections cheaply) rather than thread-per-connection.

N. Deep Dive 2 — The Routing Problem

Requirement this addresses: directly fixes V1's fatal flaw (J) — this is the single idea that makes the whole system work past one server.

Every connection server registers/deregisters itself in the shared Session Store on connect/disconnect — the routing layer is what V1 was missing entirely.

Why a shared session store, not server-to-server broadcast: the naive alternative to a lookup table is for Server 1 to ask every other server "do you have User B?" — an O(N) broadcast per message that gets worse as the fleet grows, exactly backwards. A shared, fast key-value lookup (user_id → server_id) turns routing into O(1) regardless of fleet size — the same "look it up, don't ask everyone" principle behind consistent hashing in Rate Limiter, just for connection ownership instead of counter shards.

Why a message broker/pub-sub layer between connection servers, not a direct server-to-server call: connection servers come and go (deploys, crashes, scaling events); a pub-sub layer (Redis Pub/Sub, or Kafka for durability) decouples "which server has User B right now" from "how do I get a message to that server," and gives the delivery attempt a natural retry/redelivery point if the target server was mid-restart.

O. Deep Dive 3 — Message Ordering

Requirement this addresses: the strict per-conversation ordering NFR (D) — network delivery alone gives no ordering guarantee once messages can take different paths through different servers.

Why wall-clock timestamps aren't sufficient on their own: clock drift between servers (the identical problem named in Rate Limiter's atomicity deep dive) can make two messages sent moments apart appear out of order if each is timestamped by a different connection server's local clock.

The fix — a per-conversation monotonic sequence number, assigned at the point of persistence (not by the sending client): when a message is written to the source-of-truth store (K), it's assigned the next seq_num for that conversation_id, atomically (an auto-incrementing counter scoped to the conversation, analogous to the atomic counter reasoning in URL Shortener's ID-generation deep dive). Clients then order and render messages by seq_num, never by arrival time or local timestamp — arrival order across a distributed system is not delivery order, and delivery order is not send order, but seq_num pins down a single authoritative order regardless of network path.

P. Deep Dive 4 — Delivery Guarantees (Sent / Delivered / Read)

Requirement this addresses: the "no message loss" NFR (D) plus the specific three-state status UX in the functional requirements.

Why explicit client acks, not server-side inference: the server pushing a message is not proof the client received it — the WebSocket could close in the exact window between the server's write and the client's actual receipt. Each status transition requires an explicit signal from the receiving side, the only party that actually knows the true state — the same "don't infer completion, confirm it" principle behind any at-least-once delivery system's ack protocol.

Q. Deep Dive 5 — Group Chat Fanout

Requirement this addresses: the group-messaging functional requirement (D) — structurally similar to the News Feed problem's fanout question, but under much stricter latency/ordering constraints.

Why fanout-on-write is the only real option here (unlike News Feed's hybrid): News Feed could defer celebrity fanout to read time because a feed read tolerates a live merge; a group chat message must be pushed to every member's active connection immediately to hit the <100ms real-time NFR — there's no equivalent of "read-time merge" for a live conversation. On send, the message is persisted once (K), then the routing lookup (N) is repeated once per group member, each resolved to its own connection server independently.

Why this doesn't need News Feed's celebrity carve-out: group sizes are bounded (E's clarifying question 2 — typically capped in the hundreds, not millions of members), so the fanout width is naturally small; the unbounded-fanout problem that forced News Feed's hybrid design simply doesn't arise here at realistic group sizes. A group with an unusually large member cap would reintroduce that exact problem and warrant revisiting the same hybrid pattern.

R. Deep Dive 6 — Offline Delivery (Store-and-Forward)

Requirement this addresses: the offline-delivery functional requirement (D) — the routing lookup in N fails cleanly (no session found) when the recipient isn't connected at all, and this deep dive is what happens next.

Why a per-recipient queue, not just relying on the message store (K) alone: the message table already durably has every message (K) — but "durably stored somewhere" and "the client knows to fetch it" are different problems. On reconnect, the client (or server, on its behalf) needs an efficient way to ask "what's new since I was last online," which a per-recipient offline/undelivered-message index answers directly, without scanning every conversation's full history.

Bounding retention: undelivered messages are retained for a finite window (E's clarifying question 5 — WhatsApp's own real-world limit is illustrative here, on the order of weeks) before being dropped from the offline queue, bounding its storage; the message itself may still exist in the durable store for the sender's own history even after the offline-delivery attempt is abandoned.

S. Deep Dive 7 — End-to-End Encryption & Multi-Device

This is the hardest, most differentiating extension in this problem — analogous to Rate Limiter's multi-region deep dive in that it's genuinely open-ended and worth reasoning through explicitly rather than asserting a pat answer.

What E2E encryption changes structurally: once content is encrypted client-side before it ever reaches the server, the server can route, order, and store ciphertext — but can no longer read content, meaning server-side search, content-based moderation, and rich previews all become impossible or must move entirely to the client. This is a direct trade-off against product features, not a pure security upgrade with no cost.

The Signal Protocol, at a level relevant to this interview:

• X3DH (Extended Triple Diffie-Hellman) — establishes an initial shared secret between two users' devices without requiring both to be online at the same time, using pre-published one-time and signed pre-keys — directly solves "how do I encrypt a message to someone who's currently offline," which is essential given R's store-and-forward requirement.
• Double Ratchet — derives a new encryption key for every single message from the previous one, so compromising one message's key doesn't expose past or future messages (forward secrecy) — the server never sees any of this key material; it only ever transports ciphertext.
• Sesame (multi-device session management) — since each of a user's devices has its own identity keys, a sender must actually encrypt a separate copy of the message per recipient device, not one ciphertext that magically works everywhere. This directly means multi-device support multiplies fanout width by the recipient's device count, on top of Q's group fanout — a very concrete architectural cost of the encryption decision.

Why this belongs in the deep dive and not the base design (F): designing this correctly from scratch in an interview is unrealistic in the time available; the strong signal is knowing that this is what real systems (WhatsApp/Signal) actually do, why store-and-forward (R) and multi-device both get materially harder under E2E, and being able to reason about the trade-off — not deriving the Double Ratchet algorithm live.

T. Full Solution at Scale — Final Architecture

Everything above is the composition of M through S — no new component introduced here.

U. Design Evolution

• V1 — single connection server, direct local lookup (J): broken the moment a second server exists.
• V2 — shared session/routing store + pub-sub broker: fixes cross-server delivery (N).
• V3 — per-conversation seq_num assigned at persistence: fixes ordering across arbitrary network paths (O).
• V4 — explicit client-side acks for delivered/read: makes the three-state status trustworthy (P).
• V5 — per-member fanout for groups: extends delivery to group conversations (Q).
• V6 — per-recipient offline queue: handles the disconnected-recipient case without message loss (R).
• V7 — client-side E2E encryption + per-device fanout: the final, hardest layer, changing what the server is even allowed to see (S).

What stays stable throughout: the WebSocket event contract from I (send_message/new_message/status events) — every version underneath changes without the client protocol needing to change.

V. Consistency Model

Ordering (O) and delivery (P/R) require much stronger guarantees than either previous problem's "approximate is fine" stance — a chat message that's silently dropped, duplicated, or shown out of order is immediately visible and confusing to the user, unlike a rate limiter briefly over-counting or a feed appearing a few seconds late. The per-conversation seq_num is a genuine strong-ordering guarantee, not an approximation; delivery is effectively at-least-once with client-side dedup (via client_msg_id, I) rather than exactly-once, which is the pragmatic, honest target — true exactly-once delivery across an unreliable network is not achievable without the receiver doing dedup work regardless, so the design leans into that instead of chasing an unachievable guarantee.

W. Failure Scenarios

• A connection server crashes: all its connected clients get dropped and reconnect (typically to a different server via the LB); each client's session re-registers in the shared store on reconnect (N); any messages sent to that user in the gap are queued (R) until the new registration lands.
• The message broker/pub-sub layer is briefly unavailable: sender-side persistence (K) already succeeded and was acked as "sent" — delivery is simply delayed, not lost, since the offline-queue path (R) acts as a natural fallback once the recipient's session re-resolves.
• Two messages in the same conversation are persisted by two different servers concurrently: the atomic per-conversation sequence assignment (O) — not the sending server's local view — is what prevents a race from producing two messages with the same or out-of-order seq_num.
• A client retries a send after not hearing an ack in time: the server dedups on client_msg_id (I), so the retry doesn't create a duplicate visible message.
• A recipient's device count grows (multi-device) mid-conversation: new device registration under Sesame (S) requires re-establishing per-device encrypted sessions — a real operational event, not a silent no-op.

X. Bottlenecks & Scaling Boundary

Y. Design Trade-Offs

Z. Common Bad Designs

• HTTP polling for "real-time" messaging. Technically delivers messages eventually, but fails the actual latency NFR and wastes enormous server capacity on empty poll responses — the most common mistake specifically on this problem.
• No shared routing/session state — assuming a message can just be delivered directly by whichever server received it, with no lookup for where the recipient actually is (V1's exact flaw, J).
• Relying on arrival timestamps for ordering instead of a per-conversation authoritative sequence number — silently breaks under clock drift or out-of-order network delivery (O).
• Treating "delivered" as inferred from "server sent it" rather than an explicit client acknowledgment — produces a status that's wrong exactly in the failure cases it exists to report on (P).
• Designing E2E encryption as an afterthought bolted onto a plaintext design — multi-device and store-and-forward both need to be designed with encryption's constraints in mind from the start, not patched in later (S).

AA. Interviewer Follow-Ups

AB. Interviewer Evaluation Rubric

• Weak candidate: proposes HTTP polling or a single-server design with no routing/session concept; no mention of ordering or delivery guarantees at all.
• Mid-level: correctly picks WebSockets and identifies that messages need to be routed across servers, but hand-waves the routing mechanism itself.
• Senior: proactively designs the shared session/routing store and pub-sub broker; introduces a server-assigned sequence number unprompted; distinguishes sent/delivered/read as three genuinely separate, explicitly-acked events.
• Staff+: reasons about offline delivery and group fanout as related-but-distinct problems from 1:1 delivery; discusses E2E encryption's real structural impact (search/moderation loss, multi-device fanout cost) rather than treating "add encryption" as a checkbox.

AC. Interview Simulation

AD. Online Solution Comparison

AE. Interview Cheat Sheet