Design a chat system
Route messages through stateful WebSocket gateways, size a wide-column message store, and defend presence and read receipts at 50M daily users.
Chat inverts the assumption the rest of this course rests on. Everywhere else the client asks and the server answers, which lets the server forget the client between requests. Here the server initiates: a message has to reach a specific device already connected, right now, to one specific machine in a fleet of hundreds. That reversal makes the connection tier stateful, forces a registry no other design here needs, and turns two apparently trivial features — presence and read receipts — into the two most expensive things in the system.
Step 1 — Requirements
In scope:
- 1:1 messaging with sub-second delivery when both parties are online.
- Group messaging, capped at 500 members.
- Online presence: whether a contact is reachable now.
- Delivery receipts: sent, delivered, read.
- Message history: scroll back through a conversation, newest first.
- Push notification when the recipient is offline.
Out of scope: voice and video, end-to-end encryption, media transcoding, search.
The 500-member cap is a design decision, and it belongs in Step 1 because it bounds two costs. One message to a group of N members costs N deliveries. One read receipt per member per message costs up to N × N broadcasts — 500 members reading one message, each read broadcast to 500 people, is 250,000 events for a single message. At 500 the worst case is survivable; at 5,000 it is 25M events per message and the group feature alone outweighs everything else. The cap also keeps a group's membership a single-partition read.
Non-functional targets:
- Delivery p99 under 500 ms when both parties are connected. The mean hides the tail; p99 is what users feel.
- Messages are never lost once acknowledged, and never shown twice.
- Per-conversation ordering is guaranteed. Global ordering across conversations is not, and nothing consumes it.
Step 2 — Estimates
Assume 50M daily active users, 40 messages sent per user per day, peak at 3× average, 20% of messages sent into groups, average group size 20, and peak connection concurrency of 20% of DAU.
Sends.
50M users × 40 messages = 2B messages/day
1B/day ≈ 12,000 QPS, so 2B/day ≈ 24,000 QPS average
peak ≈ 72,000 QPS
Deliveries. Sends are not the interesting number; the fan-out is.
1:1: 1.6B messages × 1 recipient = 1.6B deliveries
group: 0.4B messages × 19 others = 7.6B deliveries
total ≈ 9.2B deliveries/day ≈ 110,000/second average, ~330,000 peak
A delivery-to-send ratio of ~4.6:1 says the push path, not the write path, is what to size.
Connections. 20% of 50M = 10M concurrent WebSocket connections at peak. Budget ~10 KB per connection for kernel socket buffers plus per-session state, and hold ~100,000 connections per gateway node — 1 GB of connection state, leaving the rest of the box for heap and TLS.
10M ÷ 100,000 = 100 nodes, provision ~150 for headroom and rolling restarts
Storage. A stored message is ~100 bytes of text plus conversation ID, message ID, sender ID, timestamp and flags: ~500 bytes on disk with per-column overhead. Media never lives here — it goes to object storage behind a CDN and the message carries a reference.
2B messages/day × 500 bytes = 1 TB/day
1 TB/day × 365 × 5 years = 1,825 TB ≈ 1.8 PB
× replication factor 3 ≈ 5.5 PB
5.5 PB ÷ 10 TB usable/node ≈ 550 nodes
550 nodes to hold five years of text is the number that justifies tiering: keep 12 months hot (1 TB × 365 × 3 ≈ 1.1 PB, ~110 nodes) and age the rest into object storage, fetched on the rare deep scroll.
Step 3 — The connection layer
Polling means every client asks every few seconds whether anything happened. At 10M connected users polling every 3 seconds that is 3.3M requests/second, the answer is "no" for almost all of them, and a message still waits up to 3 seconds. Long-polling fixes the latency by holding the request open, but each delivery ends the request and the client immediately opens another, so a busy conversation degenerates into request-per-message with a full HTTP round trip of overhead each time.
WebSockets replace both with one TCP connection, upgraded once from HTTP, then full-duplex for its lifetime — mechanics in WebSockets. A server push costs a frame on an existing socket, so the 0.5 ms datacenter round trip is the whole budget instead of TLS negotiation plus headers.
The consequence is the design problem. An open connection is state, held in one process's memory on one machine. A stateless app server scales and restarts freely precisely because any node can serve any request. A chat gateway cannot: to deliver to Bob we must reach the one node holding Bob's socket. Two things follow.
A session registry. A key-value store mapping user_id to the gateway node holding the connection, plus device ID and expiry. 10M entries at ~100 bytes is 1 GB, trivially in memory. It is written on connect and disconnect — at an average connection lifetime of 30 minutes, 10M ÷ 1,800 s ≈ 5,500 writes/second — and read once per delivery, ~110,000 reads/second. Entries carry a TTL refreshed by the same heartbeat that drives presence, so a node that dies silently does not leave stale routes behind.
Sticky routing at the load balancer. Once the handshake completes, that TCP connection is pinned to a node for its lifetime, so stickiness is implicit — but the balancer must proxy the Upgrade handshake rather than terminate it, and its idle timeout must exceed the heartbeat interval or it reaps healthy connections. Keep a long-polling fallback for clients behind restrictive proxies and stickiness becomes explicit and mandatory: each poll is a separate HTTP request that must land on the node holding that session. Use least-connections, not round-robin — connections are long-lived, so a restarted node stays empty under round-robin while its peers stay full (load balancing covers the algorithms).
Deploys are the failure mode people forget. Restarting one node drops 100,000 connections at once, and if every client retries immediately you get a synchronised reconnect storm. Drain gradually and require jittered client backoff: 100,000 reconnects spread over 60 seconds is ~1,700 handshakes/second across the fleet, which the fleet absorbs.
The message flow
The send path acknowledges only after the message is durable. A client that gets an ack for a message the store never took would show it as sent and lose it, which is the one failure users never forgive.
The offline path matters more than it looks. The push notification is a wake-up, not a delivery channel — payloads are capped around 4 KB on APNs and neither APNs nor FCM guarantees delivery. Delivery happens when the client reconnects and sends the last message ID it holds per conversation; the server returns everything after it from the message store. That sync also covers a client that was online but missed a frame, so it is the correctness backstop for the whole system, and the reason the store is the source of truth rather than the socket.
The data model
The message store is the choice that carries this design, and the access pattern is narrow and stable. Writes are 24,000 QPS average, 72,000 at peak, 1 TB/day, and every write is an insert — messages are never updated in place. Reads are always "the last 50 messages of conversation X, newest first", occasionally "the 50 before this cursor". Nothing joins across conversations, aggregates, or filters ad hoc.
A wide-column store in the Cassandra family matches that shape directly:
TABLE messages
PARTITION KEY conversation_id
CLUSTERING KEY message_id DESC
columns sender_id, type, body, media_ref, created_at
The partition key puts a whole conversation on one set of replicas, so a history read is a single-node contiguous slice already in order — no secondary index, no sort, no scatter-gather. The clustering key makes recent-first the physical layout on disk. Writes land in an LSM tree, so they are sequential appends to a commit log and memtable rather than random insertions into a B-tree, and adding capacity means adding nodes rather than planning a shard split. Replication factor 3 with quorum reads and writes costs one extra round trip and survives one replica loss; when a partition isolates a replica we keep serving from the remaining two, and PACELC's Else branch — the no-partition case — is where that quorum setting knowingly trades latency for consistency.
A single relational table struggles for reasons that are all arithmetic. A commodity Postgres box handles roughly 5,000 simple QPS, so 72,000 peak writes needs 15 shards on write throughput alone, before replicas. Each insert also updates a B-tree index whose hot pages are scattered, and at 1 TB/day that index stops fitting in memory, putting a 10 ms disk seek on the write path. You end up hand-building the partitioning, rebalancing and cross-region replication the wide-column store ships with, in exchange for joins this workload never issues. Note that ACID's C and CAP's C are unrelated: choosing availability at partition time says nothing about whether a write preserves its own invariants.
Three supporting tables finish it: user_conversations, partitioned by user_id and clustered by last activity descending, which is the inbox list; group_members, partitioned by group_id and bounded at 500 rows by the cap; and read_state, keyed by conversation and user, holding one mutable last_read_message_id per member. The NoSQL lesson covers why modelling per query, not per entity, is the whole method here.
Message IDs
An auto-increment column fails three ways. It is a single sequence, so it is a coordination point capped at one node's throughput. It leaks volume — ID 4,812,003,117 tells anyone the total message count. And it imposes a global order nobody needs: whether a message in your work group precedes one in your family group is a question with no consumer.
Use a Snowflake-style 64-bit ID: 41 bits of millisecond timestamp (~69 years of range), 10 bits of node ID (1,024 generators), 12 bits of per-millisecond sequence (4,096 per node per ms, so 4.1M IDs/second per node against a 72,000 QPS peak). Generated locally, no coordination, sortable by time because the timestamp sits in the high bits — exactly what the clustering key needs.
State the ordering guarantee carefully. Two IDs minted on different nodes in the same millisecond order by node ID, which is arbitrary. Harmless across conversations, unacceptable within one — so route all writes for a given conversation_id through one partition owner, making that conversation's IDs come from a single generator with a monotonic sequence. Never let the client's clock assign the ID: a skewed device would insert messages into the past, where they are silently invisible below the reader's scroll position.
Step 4 — Deep dives
Delivery semantics and dedupe
Every hop retries, so the system is at-least-once end to end: at-least-once implies duplicates, and duplicates imply idempotency is required. The concrete case is a sender whose ack is lost retrying a message that was already persisted.
The fix is a client-generated client_msg_id, a UUID minted before the first attempt and reused on every retry. The message service treats (sender_id, client_msg_id) as an idempotency key and on a repeat returns the same server-assigned message ID instead of writing a second row; idempotency covers key design and retention. A 24-hour window suffices, since a client offline longer resyncs by message ID rather than retrying. On the receiving side, dedupe on message ID before rendering — a recipient may get the same message from the live push and again from the reconnect sync.
Presence
The tempting design is explicit events: the client announces "going offline" as it disconnects. It fails because the disconnections that matter never announce themselves — a killed process, a train tunnel, a flat battery. TCP will not tell you promptly either; a half-open socket can sit until keepalive fires, two hours on default Linux settings. Explicit offline events make "shown online but unreachable" the permanent state rather than a brief one.
Invert it. Presence is a lease: the client heartbeats every 30 seconds, the gateway writes presence:user_id with a 90-second TTL (three missed beats), and absence of the key means offline. Failure now expires by default instead of depending on a message that may never come.
The cost is worth quoting: 10M connections ÷ 30 s = 333,000 presence writes/second, more than ten times the message write rate. Two mitigations. Each gateway batches its own 100,000 heartbeats into pipelined bulk writes. And do not broadcast every transition — a user with 200 contacts flipping online would fan out 200 notifications on every subway exit. Push presence only to users with that conversation currently open; everyone else reads it when rendering a contact list.
Read-receipt fan-out in groups
Naively, each member reading each message emits a receipt to every other member: 0.4B group messages/day × 20 readers = 8B read events/day ≈ 92,000/second, and broadcasting each to the other 19 is 152B events/day ≈ 1.8M/second — sixteen times the entire message delivery load, for a feature that renders as a pair of ticks.
Three reductions, in order of value. Store read state as a watermark, one last_read_message_id per (conversation, user), so catching up on 100 messages is one write rather than 100. Coalesce on the client: send the watermark at most once every few seconds while the conversation is open. And above a group-size threshold — 20 is a reasonable start — stop pushing per-member receipts and show an aggregate "read by 12", computed on demand from the 500-row-max member table when someone taps it. 1:1 chats, where the receipt really is a per-message signal, keep the full behaviour.
Trade-offs
| Dimension | Long-polling + relational store | WebSocket gateways + wide-column store |
|---|---|---|
| Idle cost at 10M users | 3.3M requests/s of "nothing new" | 10M idle sockets, ~100 GB of buffers |
| Delivery latency | 1–3 s, or a round trip per message | ~0.5 ms datacenter hop, p99 under 500 ms |
| App tier | Stateless, any node serves any request | Stateful, a registry lookup per delivery |
| Deploys | Restart freely | Drain connections, jittered client reconnect |
| Write ceiling | ~5,000 QPS/box; 15+ shards hand-managed | Linear with nodes; 72,000 QPS peak absorbed |
| History read | Index lookup plus sort | One contiguous partition slice, pre-sorted |
| Ordering | Global sequence, a coordination point | Per-conversation, from one generator |
| Failure mode | Latency creeps up under load | Stale registry routes to a dead node |
In an interview
What is being tested is whether you recognise the connection tier is stateful and can say what that costs. Every other design in the loop lets you wave at "app servers behind a load balancer"; this one does not, and the interviewer is watching for the moment you notice.
Say it in this order:
- Establish the fan-out before drawing any boxes: "2B messages a day is 24,000 QPS, but 9.2B deliveries is 110,000 pushes a second — the delivery path is what I'm sizing."
- Choose WebSockets and name the consequence immediately: "which means the gateway holds state, so I need a registry from user to gateway node, hit once per delivery."
- Walk both paths — online push, and offline queue plus a wake-up, with sync-on-reconnect as the real delivery mechanism.
- Give the message store its primary key out loud: partition by
conversation_id, cluster bymessage_iddescending, and state the access pattern that earns it. - Volunteer the presence write rate. 333,000 writes/second for a green dot is what separates a considered design from a recited one.
The mistakes that lose points:
- Drawing stateless app servers and never explaining how a message finds Bob's socket. This is the question; a design without a session registry has not answered it.
- Choosing WebSockets on vibes. "It's real-time" is a preference. "Polling every 3 seconds is 3.3M requests/second of empty responses and still 3 seconds of latency" is an argument.
- Making push notifications the delivery mechanism. They are best-effort with a ~4 KB payload cap; delivery is the reconnect sync.
- A global auto-increment message ID, which is both a coordination point and a promise of ordering nothing consumes.
- Treating read receipts as free. Deriving 1.8M events/second and then reducing them to a watermark is a stronger answer than any box on the diagram.
If pushed on the group cap, do not defend 500 as a fact: "I'd start at 500 because it bounds receipt fan-out at 250,000 events per message and keeps membership a single-partition read. For 5,000, receipts go aggregate-only above a threshold and I'd re-derive."
Check yourself
1. Product wants an 8,000-member announcement group. What changes, and is raising the 500 cap the whole fix?
One message costs 8,000 deliveries instead of 500 — 16× the fan-out, but off the latency path on the push queue, so throughput is not what breaks. Receipts are: 8,000 readers × 8,000 recipients is 64M broadcast events for one message, 256× the cost at 500. Raising the cap alone makes that worse. Change the group's shape instead: announcements are write-restricted to a few admins, so treat it as a broadcast channel — aggregate receipts, no published presence, one fan-out job rather than a conversation. A size limit is enforcing an O(N²) feature; the alternative to a bigger limit is a cheaper feature.
2. A gateway holding 100,000 connections dies without closing them. Estimate how long those users appear online, and what the message service does with messages addressed to them meanwhile.
Registry and presence entries carry a 90-second TTL refreshed every 30 seconds, so they expire within 90 seconds of the last beat — that is the window in which those users still look online. During it, the service looks up the registry, gets a dead node, and its push fails; that failure must fall through to the offline path (already persisted, so enqueue and send a wake-up) rather than being retried at the dead address or dropped. Clients meanwhile detect the dead socket, reconnect to a live node and sync from their last message ID, so nothing is lost. A 30-second TTL narrows the window but triples presence writes from 333,000/s to 1M/s and starts marking flaky mobile users offline.
3. The team proposes a per-recipient delivery row for every message instead of a per-conversation watermark. Estimate the added storage and decide.
Deliveries run at 9.2B/day; at ~50 bytes per row that is 460 GB/day, or 460 GB × 365 × 5 × 3 ≈ 2.5 PB replicated — a 45% increase on the 5.5 PB baseline, plus 110,000 extra writes/second. The watermark alternative is one mutable row per (conversation, member): roughly 50M users × 50 conversations × 50 bytes ≈ 125 GB in total, four orders of magnitude smaller. Per-recipient rows earn their place only if the product must answer "did Bob receive message 4,192" for arbitrary history; for the ticks users actually see, the watermark answers every query for 0.005% of the storage.