BOOKS DEEP-READ · SYSTEM DESIGN INTERVIEW VOL 1 · CH 12
System Design Interview Vol 1 · Ch 12 · Alex Xu · 2020
You send someone a message on WhatsApp and it lands with a ping. This chapter is about building that ping. It looks simpler than the news feed — surely it is just carrying one sentence from A to B — but underneath sits a more basic obstacle: under the rules the web actually runs on, a server has no way to come find you.
Think of the server as a post office with one rigid rule: it answers only when you walk in and ask "is there anything for me?" It will never knock on your door. So sending is no trouble at all — walk in, hand the letter over. Receiving is the hard part: how do you know when something has arrived?
The crudest approach is walking to the post office every few seconds to ask. It doesn't tire you; it tires the post office. With tens of millions of people asking, it fields tens of millions of questions a second, and ninety-nine times out of a hundred the answer is "nothing". A slight improvement is to ask and then refuse to leave — stand at the counter and wait, get your letter the moment it arrives, and if nothing comes, be sent home after a while so you can walk back. Fewer wasted trips, but you still shuttle back and forth constantly — and the clerk still cannot tell whether you went home or collapsed on the way.
The modern answer is a third one: run a line between you and the post office that is never hung up. You still place the call (the rule is not broken), but once the line is open, either end can simply start talking — the post office can finally speak first. Messages arrive with a ping because that line is always open, so nothing has to be dialled again.
One: what if you're not there. The line drops, so the message is kept on the server in an inbox that belongs to you; you collect it whenever you next come online. If it really can't wait, it goes out as a phone push notification — and that road belongs to somebody else.
Two: group chat. For a small group, the cheapest thing is to make N copies: one message, one copy dropped into every member's inbox. With few members the arithmetic is fine. With many, it collapses completely.
Three: knowing who is still there. You cannot call someone offline the instant their line drops — one wobble in a subway tunnel and their avatar goes grey, comes back, and flickers the whole way. So real systems use a heartbeat: whoever is online chirps every few seconds, and only after tens of seconds of silence are they treated as gone.
The honest cost: that always-open line is not free. The server must hold memory for every person online, one machine tops out at a few million lines — and when that machine needs a restart, everyone on it turns around and reconnects in the same second.
The hard part of a chat system is never sending, it is receiving. Sending is no different from loading a web page; but to let the server reach you first, you must first run it a line that never hangs up — and everything that follows (which machine that line lands on, where messages go while it is down, how a group copies them, how you tell someone is still there) is cleanup after that one line.
Want the stateful edge layer, message-ID ordering and the real numbers? → Switch to the deep read
The protagonist of this chapter is not the message, it is the connection. It starts from one fact about the protocol — HTTP can only be opened by the client, a server cannot go and find you — and derives the shape of the whole architecture: the edge layer must hold a long-lived WebSocket, which makes it stateful, and stateful drags in the entire chain of consequences: service discovery (which box do I connect to), heartbeats (is it still there), inboxes (where messages sit while it isn't), and a message ID that rises monotonically within a conversation (how you order what arrives). The hard part of a chat system is never "send", it is "receive".
The ninth case study in Part II of Volume 1. It follows Ch11, the news feed — both distribute content to many people, but a feed is one-to-many broadcast that tolerates minutes of skew, while chat is bidirectional, expected within a second, and not allowed to drop anything. It also follows Ch10, notifications: the moment a user goes offline, chat degrades into a notification problem. It leads into Ch13, search autocomplete. In the wild it is WhatsApp, Messenger, Slack, Discord, WeChat, and every product with a support window in the corner.
The chapter's scenario: 50 million daily active users, 1-on-1 and group chat, a cap of 100 members per group, text only, 100,000 characters per message, chat history kept forever, one account signed in on several devices at once, plus presence and offline push.
Start with message volume (what follows is derived from that scenario, not quoted from the book). At 20 messages per user per day that is 1 billion messages/day ≈ 11,600/s, peaking near 35,000/s at 3× — unremarkable for modern storage.
The pressure is not in the messages, it is in the connections. If 10% of the daily actives are online at once, that is 5 million concurrent long-lived connections. The book puts a single connection at roughly 10 KB of memory — a million connections is about 10 GB of pure connection overhead, five million is 50 GB, before a single byte of business data. A chat system's unit of capacity is "connections currently held open", not QPS, and that is the first instinct this chapter replaces.
What happens if you don't solve it? Fall back to polling and 50 million users asking every 5 seconds is a standing 10 million requests/s, nearly all of them answered "nothing new" — and the latency is still one polling interval.
The judgement worth keeping sits in the opening pages: sender and receiver are not symmetric. Sending is client-initiated, so an ordinary HTTP request suffices and nothing new appears. Receiving is not — HTTP's whole model is client asks, server answers, and the server has no legitimate way to knock first. Every structure in the rest of the chapter exists to route around that one fact.
The book lays out three routes: polling (ask periodically; simple, but latency equals the interval and almost every answer is empty), long polling (ask, then let the server hold the request), and WebSocket (one HTTP handshake upgraded into a bidirectional persistent channel either end can write into). Long polling looks like the cheap compromise, but the book names three specific defects: sender and receiver may land on different servers (HTTP servers are usually stateless behind round-robin balancing, so the server does not know who to hand the message to), there is no good way to tell whether a client has disconnected, and users who never chat still reconnect periodically as requests time out. The table below lays all three side by side.
Choosing WebSocket bills you immediately: the machine holding the connection becomes the only machine this client can use. So the book sorts services into three kinds: stateless services (signup, login, profile — behind a load balancer, any box will do), stateful services (the chat service, where each client holds a persistent connection on some box and does not move while that box lives), and third-party integration (push notifications).
The first new component statefulness drags in is service discovery: a client coming online must first ask which box to connect to. The chapter registers every available chat server in ZooKeeper and picks one by geography and capacity. Without that layer, clients connect blind and load skews onto a few machines.
Worse, the operational assumptions all change: restarting one stateless box goes unnoticed; restarting one stateful edge box means every connection on it drops, reconnects, re-authenticates and re-pulls history at the same instant. That is the reconnect storm — this layer's characteristic death is not being crushed by outside traffic, it is being crushed by its own recovery.
The book splits data in two. Generic data (profiles, settings, friend lists) is small and wants transactions, so it goes in a relational database. Chat history is enormous, so it goes in a key-value store. Three reasons: KV stores scale out easily, offer very low random-access latency, and relational databases handle the long tail badly — once indexes and data sets grow, random access gets expensive. The book names names: Messenger on HBase, Discord on Cassandra.
The data model is the hard core of this section. One-on-one chat uses a message table whose primary key is message_id — and created_at cannot be the ordering key, because two messages can perfectly well land in the same millisecond. Group chat uses a composite key (channel_id, message_id), with channel_id as the partition key, because every query in a group chat happens inside one channel — all of a group's messages sit on one shard, and scrolling history touches one shard.
A message ID must be both unique and time-sortable. Two ways: a global 64-bit sequence generator (Snowflake), or a local one guaranteeing monotonicity only within a single conversation. The book judges the second sufficient — a chat system does not need global ordering, only per-conversation ordering. This is the chapter's cheapest win: it shrinks "distributed global ordering", a genuinely hard problem, back into an increment inside one partition — and the partition key was already there, channel_id.
The full one-on-one flow: A sends to chat server 1 → the server obtains a message ID → the message goes into the message sync queue → it is written to the key-value store → if B is online it is forwarded to B's chat server 2 and pushed down; if B is offline it goes to the push notification service. Storage happens before delivery, and that order cannot be flipped: only durability first makes "not dropped" meaningful.
Multi-device sync is the prettiest design here. Each device keeps a cur_max_message_id, the highest ID it has seen; to fetch what's new, it queries for messages whose recipient is this user and whose ID is greater than cur_max_message_id. It is worth studying because it moves the bookkeeping of "how far did delivery get" off the server and onto the device. The server keeps no per-device cursor, so it never has to answer "where should a freshly installed device start"; reconnects, a new phone, several devices in parallel are all the same query. This is the real purpose of a monotonic message ID — not tidy sorting, but turning "what am I missing" into one range query.
Group chat here uses fan-out on write: a group message is copied into every member's sync queue. Clients then read only their own inbox and the sync logic is identical to 1-on-1, and while groups are small, copying 100 times is negligible. The book draws the line itself: 100 members per group, noting that WeChat caps groups at 500. This is the same accounting as Ch11's fan-out on write — cost is proportional to the number of recipients and collapses as that grows; a chat system simply gets to pin the number down with a product rule, which a news feed cannot, so a feed has to go hybrid instead.
Presence is maintained separately by presence servers over WebSocket: on login, status and last_active_at are written to the key-value store; on logout they flip back. The awkward case is an abnormal disconnect — networks are unreliable by nature, and declaring someone offline the instant their link drops makes avatars flicker for a whole commute. The fix is a heartbeat: online clients emit a periodic event (the book's example is every 5 seconds, offline after 30 seconds of silence).
How does that status reach others? The book uses publish-subscribe: a channel per pair of friends, so when A's status changes it publishes into A-B, A-C, A-D. Clean at small scale, but the cost hides in the count — the number of channels is proportional to the number of friend pairs, an N² quantity, which is directly related to WeChat capping friends at 5,000. So the book leaves an escape hatch: above some group size, stop broadcasting and fetch presence only when a user enters the group or refreshes manually. That is the second time this chapter converts a push into a pull, for exactly the reason a feed pulls for celebrities.
One more thing worth noting: the heartbeat is itself a sizeable system. Five million connections at one heartbeat every 5 seconds is 1 million events/s — nearly two orders of magnitude above the real message rate of roughly 11,600/s. The biggest traffic in a chat system is often not the messages.
Table 1 · Three ways to let the server speak first
| Option | Mechanism | Latency | Server cost | Fatal flaw | Still good for |
|---|---|---|---|---|---|
| Polling | client asks on a timer | equals the interval | 50M DAU / 5s ≈ 10M requests/s | ten million empty answers to serve ~11.6K real messages/s | status checks tolerating minutes of lag |
| Long polling | ask, held open until a message or timeout | near real time | connections rebuilt constantly; each held request occupies one too | sender and receiver may land on different servers; no way to detect a dead client; non-chatters still reconnect on timeout | environments where WebSocket is unavailable |
| WebSocket (the chapter's pick) | HTTP handshake upgraded to a bidirectional channel | lowest: nothing re-dialled | ~10 KB per connection; 5M connections ≈ 50 GB | the edge layer becomes stateful: service discovery, heartbeats, and a reconnect storm on every restart | anything needing server-initiated push |
Table 2 · Four forks you must answer yourself after this chapter
| Fork | This chapter's pick | Cost / when to switch |
|---|---|---|
| Message ID ordering | monotonic within a conversation, no global order | skips global coordination; IDs are incomparable across conversations, so global search or a cross-group timeline needs Snowflake as well |
| Group fan-out | fan-out on write: a copy per member, capped at 100 | cost scales with membership. Channels of tens of thousands must move to fan-out on read (fetch on entry), which makes reads expensive |
| Presence propagation | push via per-pair pub/sub; pull on entry inside groups | push means an N² number of channels; pull means status can be tens of seconds stale. Related to WeChat's 5,000-friend cap |
| Where history lives | key-value store (HBase / Cassandra) | buys horizontal scale and fast random reads; costs cross-row transactions, and complex queries and full-text search need separate systems |
One more frequent follow-up: how are connections assigned to machines? On the way in, service discovery picks by capacity and geography — but the real trap is on the way out. Removing a box means first refusing new connections, then draining the old ones gradually, with randomised backoff on client reconnects; skip that and you manufacture a reconnect storm yourself.
Asked to design a chat system in an interview, laying out this chain is essentially the whole answer: send and receive are asymmetric → receiving needs a long-lived connection → the edge layer is therefore stateful → hence service discovery, heartbeats, inboxes and per-conversation monotonic IDs. Conversely, opening with "use WebSocket" and being unable to name the statefulness it buys is no answer at all.
((channel_id, bucket), message_id), where bucket is a static time window of about 10 days, and every ID is a Snowflake, hence chronologically sortable by construction. That is this chapter's composite key in the wild, with one extra layer of bucketing so a single busy channel cannot blow out a partition. In 2017 twelve Cassandra nodes held billions of messages; by 2022 it was 177 nodes and trillions. Discord Engineering, "How Discord Stores Billions of Messages", 2017 ↗ · "How Discord Stores Trillions of Messages", 2022 ↗11,600 messages/s sounds easy, yet 5 million concurrent connections is 50 GB of memory and heartbeats add 1 million events/s. Capacity must be planned against connections and heartbeats.created_at, or chasing global order: same-millisecond collisions are ordinary and client clocks are worse, so ordering can only rest on a monotonic message_id; and since chat needs order only within a conversation, promoting it to global ordering adds a distributed problem for nothing.message_id.① The core claim: a chat system's shape is dictated by one protocol fact — only the client can open an HTTP conversation. Sending is trivial; the entire backend is rebuilt for receiving.
② Three ways round it: polling (latency equals the interval, drowning in empty answers), long polling (sender and receiver may differ, dead clients undetectable, still reconnecting), and WebSocket (one bidirectional persistent channel).
③ Choosing WebSocket splits the architecture in three: stateless services, the stateful chat server, and third-party push. Statefulness is the source of everything that follows, including service discovery and reconnect storms.
④ Capacity is measured in connections, not QPS: ~10 KB each, 5 million concurrent ≈ 50 GB; heartbeats run ~1 million/s, nearly two orders of magnitude above the real message rate.
⑤ Generic data goes relational, chat history goes into a key-value store; group chat uses the composite key (channel_id, message_id) with channel_id as partition key.
⑥ Message IDs need only be monotonic within a conversation, never globally ordered — the chapter's cheapest downgrade of a hard problem. created_at cannot be the ordering key.
⑦ Multi-device sync has each device pull its delta with its own cur_max_message_id, moving delivery bookkeeping onto the device; reconnects, new phones and new devices share one query.
⑧ Presence uses a heartbeat (every 5s, offline after 30s) to avoid false negatives; per-pair pub/sub is an N² quantity, so groups switch to fetch on entry — the same move a feed makes for celebrity accounts.