Design a Chat System

1. The problemCopy Anchor Link

1:1 and group messaging (WhatsApp, Messenger, Slack, Discord). Three properties make it different from everything else in this notes set:

• The server must start the conversation. When a friend messages you, the server pushes to you unasked — inverts HTTP's request/response model.
• Connections make servers stateful. To push, a server holds your open connection; that server "owns" you while connected → scaling, deploys and recovery all change.
• Correctness is per conversation. No message lost, none duplicated, right order, on every device you own.

Chat is a delivery-and-sync system, not a "send over WebSocket" system.

2. Requirements (extract these)Copy Anchor Link

Book's scoped answers:

Senior questions to ask unprompted — each changes the design:

• E2EE or not? The biggest fork. Server holds only ciphertext → no server-side search, history sync or moderation (§13).
• Max group size? 100 (WhatsApp) vs 100,000 (Discord/Slack) → different fan-out (§11) — the news-feed push/pull question in real time.
• Guarantees? State the stance: at-least-once + dedup, ordering per conversation, eventual consistency for presence/typing.
• Read receipts in groups? Per-message-per-user status explodes → cursors (§7).

3. EstimationCopy Anchor Link

  Messages:     50M DAU × 40/day = 2×10⁹/day ÷ 10⁵   ≈ 20,000 msgs/sec avg, peak ×5 ≈ 100,000/sec
  Storage:      2×10⁹ × ~200 B (text + metadata)      ≈ 400 GB/day ≈ 150 TB/yr raw, ×3 replicas ≈ 450 TB/yr
  Connections:  50M DAU × ~20% online                 = 10M concurrent WebSockets
  Memory:       10M × ~10 KB/connection               = 100 GB total
  Fleet:        ~100K connections/box (planning)      ≈ 100 chat servers + failover headroom

• 20k–100k writes/sec growing forever → no single RDBMS; append-optimised store (§8).
• 10M connections sizes the fleet. ⚠️ Connections scale with concurrent users, not messages — a silent online user still costs a socket, heartbeats, memory.
• Read:write ≈ 1:1 for 1:1 chat (each message read ~once) → deliver, don't precompute.
• WhatsApp reported 2M+ connections on one server — a record, not a planning number.

4. The protocol problem: how does the server push?Copy Anchor Link

Sender side is easy (HTTP works). Receiver side needs server-initiated traffic.

SSE (Server-Sent Events) = one-way server→client stream; fine for notifications, chat needs two-way → WebSocket for both send and receive.

5. High-level designCopy Anchor Link

Split by how each part scales:

• Stateless (HTTP behind LB): login, signup, profile, groups, history fetch, service discovery. Add boxes freely.
• Stateful (WebSocket): chat servers (send/receive), presence servers (who's online). A client sticks to one server for the life of the connection.
• Third-party: push notifications for offline recipients — the notification-system lecture (idempotency keys, collapse IDs, no content in payload).
• Storage: user DB (relational) · chat history (KV / wide-column) · presence + sessions (cache with TTL keys).

5.1 Service discovery — how a client gets its chat serverCopy Anchor Link

1. Client logs in over HTTP → LB → API servers.
2. API server authenticates.
3. Service discovery (ZooKeeper in the book) picks the best chat server by region + current load.
4. API returns {token, ws_url}.
5. Client opens the WebSocket to that server and keeps it.
6. Chat server records user:device → server_id in the session registry (§6).

5.2 Operational cost of statefulness (raise unprompted)Copy Anchor Link

• Reconnect storm: a chat server dies → ~100K clients reconnect in the same second → overloads discovery + survivors. Fix: client exponential backoff with jitter (same rule as notification retries).
• Deploys: never hard-restart. Drain: stop accepting new connections, ask existing clients to reconnect elsewhere over minutes.

6. Cross-server routing — how server A reaches user B on server BCopy Anchor Link

Two levels of lookup + a carrier:

A socket is a file descriptor inside one process — it can't live in Redis. That's why there are two levels.

# 0. server B, on connect
local_sockets["B:phone"] = <socket>                 # process memory
HSET session:B phone server-B ; EXPIRE session:B 120 # shared registry

# 1. server A: persist, ack A (one tick)
# 2. server A: HGETALL session:B → {phone: server-B}   (~0.5 ms)
#      empty → B offline → push notification, stop; B syncs on reconnect
#      several devices → forward to each
# 3. server A → server B: deliver(B, msg)
# 4. server B: local_sockets["B:phone"].send(msg) → wait for delivered-ack

Carrier choicesCopy Anchor Link

When the registry is wrongCopy Anchor Link

Keep staleness short:

• registry TTL refreshed every ~minute while connected — not on every 5 s heartbeat (10M users ÷ 5 s = 2M writes/s for nothing),
• better: each chat server holds an ephemeral node in service discovery; before forwarding, check server B is alive — entries pointing at a dead server are stale immediately.

Routing is the fast path, not the guarantee. Persist-before-ack + per-device cursor sync make a message late, never lost.

7. Sending a message — the 1:1 flow and acknowledgementsCopy Anchor Link

1. A's client sends {client_msg_id, conversation_id, body} — client_msg_id is a UUID made on the device before sending (dedup key).
2. Chat server 1 assigns order — server-side ID / seq; the single ordering point for the conversation (§9).
3. Persist, then ack A. One tick = "server has it stored." If the server acked first and crashed before the write, A would believe a vanished message was safe.
4. Queue for delivery — sender's server doesn't block on the recipient.
5. Registry lookup — which servers hold B's devices (§6).
6. Online → chat server 2 pushes over B's WebSocket. Offline → push notification (message is already stored; push is just a nudge).
7. B reconnects later → syncs from cursor (§10).

The three ticks — three promises, three different confirmersCopy Anchor Link

Duplicates (ambiguous timeout again): ack to A lost → A retries the same client_msg_id → UNIQUE(sender_id, client_msg_id) returns the existing message instead of inserting a second. Receiver side: delivered-ack lost → server redelivers → client drops any message ID it already has. → at-least-once + dedup at both ends.

Receipts are cursors, not per-message rows.

• Client sends one "read up to message X", debounced — not one event per message.
• Server stores last_read_msg_id per (user, conversation) and last_delivered_msg_id per (user, device, conversation).
• Per-message-per-recipient status in a 100-member group = 100 writes per message → the classic pitfall.

Multi-device rule (pick and state one): delivered when any device has it; read when any device has read it.

8. StorageCopy Anchor Link

8.1 Two kinds of dataCopy Anchor Link

Facebook Messenger: HBase. Discord: Cassandra → ScyllaDB.

8.2 Schema — every chat is a conversationCopy Anchor Link

A 1:1 chat is a conversation with two members → one table for both. Discord's real schema:

CREATE TABLE messages (
  channel_id  bigint,
  bucket      int,          -- static time window
  message_id  bigint,       -- Snowflake: sorted by time
  author_id   bigint,
  content     text,
  PRIMARY KEY ((channel_id, bucket), message_id)
) WITH CLUSTERING ORDER BY (message_id DESC);

• Open a chat = one partition read — latest 50 are contiguous, newest first.
• Bucket caps partition size — a 10-year busy chat isn't one giant partition; scrolling back moves to the previous bucket.
• Partitioning by conversation spreads load (consistent hashing).

8.3 Hot partitions (senior follow-up)Copy Anchor Link

Busy channels concentrate traffic on their current bucket; one hot partition slowed Discord's whole cluster. Reusable fixes:

• Request coalescing — 1,000 identical in-flight reads → one DB query, result shared (same idea as the cache-stampede guard).
• Data-services layer routing by channel_id → identical requests land on one instance and can be coalesced there.
• Cassandra → ScyllaDB (same model, C++, no GC): historical-read p99 40–125 ms → ~15 ms; insert p99 5–70 ms → ~5 ms.

9. Message IDs and orderingCopy Anchor Link

Requirements: unique and sortable by time (newer = larger). Client timestamps are useless — device clocks disagree by seconds to minutes.

• You only need order within a conversation, never across. So the "bottleneck" is millions of independent counters spread over the cluster — cheap. The book recommends this local sequence.
• Common combo: Snowflake as storage key + per-conversation seq for display order.
• Gap detection (bonus of seq): receive 41 then 43 → fetch 42. Snowflakes can't reveal a missing message.

10. Multi-device sync and offline deliveryCopy Anchor Link

Each device keeps its own cur_max_message_id (cursor) per conversation. On connect/reconnect it asks for everything newer.

  1. reconnect via service discovery (maybe a different chat server)
  2. send cursors: conv 42 → seq 40, conv 99 → seq 1,203 …
  3. server returns everything newer, in order
  4. device dedups by message ID (some arrived live just before the drop) → delivered-acks
  5. acks reach senders → their messages flip ✓ → ✓✓

History + per-device cursors define correctness. The live push only makes it fast. A lost push is picked up by the next sync.

11. Group chat — the news-feed fan-out in real timeCopy Anchor Link

Slack's model:

• Channel servers (stateful) each own a subset of channels via consistent hashing.
• Gateway servers (stateful, per region) hold WebSockets + each user's channel subscriptions.
• On connect, the gateway subscribes to the channel servers owning the user's channels.
• A message is routed by hashing the channel ID → owning channel server → pushed to every subscribed gateway → each gateway delivers locally.
• 100,000 members across 200 gateways = 200 server messages, not 100,000.

"Group chat is the news-feed fan-out decision in real time: small groups copy into inboxes, large channels store once and publish to the servers holding subscribers. Member count is the threshold, like follower count."

12. Online presenceCopy Anchor Link

• Client heartbeats every 5 s; offline only after 30 s with none → tunnels and Wi-Fi→LTE switches don't flicker the dot.
• Implementation: SET presence:B online EX 30, refreshed by each heartbeat. Expiry IS offline detection — no sweeper job.
• Never write heartbeats to the durable DB (10M ÷ 5 s = 2M writes/s of disposable data).
• Fan-out: book uses a pub/sub channel per friend pair (A–B, A–C…) — fine for small lists. Large groups: don't push presence; fetch on demand when the group or member list opens. Best-effort, eventually consistent — a 10 s-stale dot harms nobody.
• Typing indicators: over the WebSocket only, never stored, client throttled (once every few seconds), auto-expire if "stopped" is lost.

13. End-to-end encryption — what changesCopy Anchor Link

Ask: what disappears once the server only holds ciphertext?

Server still: routes ciphertext, holds it until delivery, distributes public key material. Signal protocol (WhatsApp): devices upload public prekeys; a sender fetches them to set up a session; private keys never leave devices.

"E2EE barely changes delivery — the server still routes and fans out. It removes server-side search, history sync and moderation, and moves multi-device fan-out to the sender's client."

14. FailuresCopy Anchor Link

Message store + per-device cursors = system of record. Sockets, registry, presence and the live push are all rebuildable. (Same cache-vs-truth split as the KV-store and news-feed notes.)

15. End-to-end trace (narrate, then break)Copy Anchor Link

  A → "hi" → B   (B: phone online on server 2, laptop asleep)
  A's client: client_msg_id=u-77, show greyed, send over WebSocket → server 1
  server 1:  (A,u-77) new → conv 42 seq 41 → write (conv 42, bucket 7) → ack A  ✓
             → delivery queue → registry: phone@server-2, laptop: none
  server 2:  local map → push {seq 41,"hi"} to phone → phone acks
             → last_delivered(B:phone) = 41 → tell A                           ✓✓
  B opens chat: "read up to 41" (debounced) → last_read(B, conv 42)=41 → tell A  blue
  evening: laptop reconnects → cursor "conv 42 up to 38" → receives 39, 40, 41

  BREAK 1  ack to A lost → A resends u-77 → unique constraint → existing seq 41 returned
           → one message, A gets its tick
  BREAK 2  server 2 crashes after pushing, before the phone's ack
           → phone reconnects to server 3 (backoff) → syncs from cursor
           → (if the push was lost, cursor 40 brings 41 back) → late ✓✓, nothing lost or doubled

16. Interview scriptCopy Anchor Link

  1. clarify     1:1 + group (cap?) · mobile + web · 50M DAU · presence · multi-device · history
                 E2EE? MAX GROUP SIZE? state guarantees: at-least-once+dedup,
                 per-conversation order, eventual presence                      ← unprompted
  2. estimate    20k–100k msgs/s · ~150 TB/yr · 10M concurrent sockets → ~100 servers
  3. protocol    polling → long polling → WebSocket; cost = stateful servers
  4. high level  stateless (API, discovery) · stateful (chat, presence) · third-party (push)
  5. discovery   login → pick server by region + load → ws_url; reconnect storm, draining ← unprompted
  6. routing     session registry + RPC/queue + local socket map; pub/sub alternative;
                 stale registry is safe because routing ≠ guarantee
  7. send flow   order → persist → ack → queue → lookup → push or notify
  8. acks        three ticks, three confirmers; client_msg_id dedup; receipts as cursors
  9. storage     RDBMS for users; wide-column (conversation, bucket) DESC for messages;
                 hot partitions + request coalescing                              ← senior
 10. ordering    server-assigned; per-conversation seq; gap detection
 11. sync        per-device cursors = correctness; push = speed
 12. groups      inbox copies ≤ ~100–500; store once + publish to gateways for big channels
 13. presence    5 s heartbeat, 30 s TTL key, push small / fetch on demand large; typing
 14. E2EE        Sender Keys, client fan-out per device, what's lost
 15. walk it     trace A → B, then kill the ack and the server yourself

Steps 1, 5, 6 and 9 separate a pass from a strong pass.

17. The lines that earn the mostCopy Anchor Link

1. "Chat is delivery plus sync: history plus per-device cursors is the correctness mechanism; the WebSocket push only makes it fast."
2. "WebSocket wins by elimination, and its cost is stateful servers — reconnect storms and draining are the price."
3. "Persist before ack. One tick means stored, two means the device confirmed, blue means the app reported it read — three promises, three different confirmers."
4. "Retries are inevitable, so the client generates a client_msg_id and the server enforces uniqueness on (sender, client_msg_id)."
5. "The registry says where, RPC or a queue carries the bytes, and the local socket map finds the connection — and a stale registry is safe because routing isn't the guarantee."
6. "I only need order within a conversation, so a per-conversation sequence is millions of independent counters, not a bottleneck — and it gives me gap detection."
7. "Receipts are cursors — 'read up to X' — never per-message rows per recipient."
8. "Group chat is the news-feed fan-out in real time: inboxes for small groups, store once and publish to gateways for big channels."
9. "Presence is a TTL key refreshed by heartbeats — expiry is the offline detection, and it never touches the durable store."
10. "E2EE keeps the routing but removes server-side search, history sync and moderation."

18. Numbers to rememberCopy Anchor Link

19. Common follow-upsCopy Anchor Link

20. When NOT to go deepCopy Anchor Link

Inside a bigger question ("design Uber" needing in-app chat), one sentence:

"Clients hold WebSockets to stateful chat servers chosen by service discovery; messages get a per-conversation sequence, are persisted to a wide-column store before acking, and are routed via a session registry — with per-device cursors syncing anything missed."

Go deep only when chat IS the question, or the interviewer pushes on delivery guarantees, groups or presence.

21. Glossary (A–Z, one line each)Copy Anchor Link