Design a chat system

Users call it "one message." The system sees four separate contracts — send, store, deliver, read — and the box that quietly dominates the bill is not the database or the CPU. It's the open socket.

Source: Vol. 1 Ch. 12 Case drill Connection-bound

First principle — this is a memory/connection problem, not a QPS problem

Most systems in this track are bounded by request rate. Chat is bounded by how many simultaneous conversations you can hold open. A chat connection is "live" for hours while sending almost nothing. The cost is not the messages flowing through it — it's the millions of idle TCP/WebSocket sockets you must keep alive between messages. Get that one fact wrong and you size the database tier and starve the connection tier. The whole design follows from one number: bytes of RAM per idle socket.

0. The hinge

The hinge — the moment the architecture becomes forced — is this: delivery, storage, ordering, presence, and offline sync are four different problems wearing one UI. The forcing observation is that a persistent connection is cheap in CPU and expensive in memory and statefulness. That single asymmetry decides the whole topology: a fat stateful connection tier you scale by RAM, a thin stateless message tier you scale by QPS, and a durable log that is the actual source of truth because the connections are not.

Tempting but wrong

"Push the message over the WebSocket — if the client got the frame, it's delivered." A WebSocket write succeeding means the bytes left your kernel, not that they reached the phone. Mobile networks switch towers and Wi-Fi-to-LTE constantly, silently dropping the TCP connection without a FIN. Treat push as a latency optimization, never as the storage or delivery guarantee. The source of truth is the durable log plus the client's cursor — see the deep dive below.

1. Clarify the contract

Before drawing boxes, pin the product contract — and, just as important, what you explicitly do not owe.

1:1 and group conversations (say groups up to 500 members — that bound is load-bearing for fan-out math).
Near-real-time delivery when the recipient is online; reliable catch-up when they reconnect.
Durable history for offline and multi-device sync — a message survives any single device.
Per-conversation order — every member of a conversation sees messages in the same sequence.
Optional delivery/read receipts — flagged optional on purpose, because receipts are the volume multiplier (Section 2).

What we deliberately do not promise: a global order across unrelated conversations (nobody can observe it, so don't pay for it), sub-50ms delivery guarantees (best-effort latency, guaranteed eventual delivery), or end-to-end encryption (orthogonal; it changes the server from "reads bodies" to "routes opaque blobs" but not the topology).

2. Put numbers on it

The estimate that steers everything is the connection tier, so derive it first. Say 50M daily users, and at peak 10M concurrent live connections. The CPU to hold an idle socket is negligible; the memory is not. Budget the kernel socket buffers (send + receive) plus per-connection application state (auth identity, subscription set, write buffer) at a conservative ~10 KB per idle connection.

10,000,000 conns × 10 KB = 100 GB of RAM just to hold connections open

That is RAM doing nothing but waiting. Now size the tier. If one gateway box comfortably holds 250K connections (a realistic figure once you've tuned file-descriptor limits and epoll), then:

#gateways = concurrent_conns / conns_per_gateway = 10,000,000 / 250,000 = 40 gateways

Forty boxes whose job is almost entirely to sit there holding sockets and forwarding frames. Contrast that with message rate: even at 10M concurrent users, a person sends maybe one message per 10 seconds when active, and most are idle. Call it 1M messages/s at a generous peak — fan-out, not ingest, is the cost. A 1:1 message is one stored body and one delivery event; a 500-person group message is one stored body and 499 delivery events. And read receipts invert the ratio entirely:

The receipt amplification trap

In a 500-person group, one message body triggers up to 500 read events (one per member who opens it), each of which may itself fan out a "seen by X" update to the other 499 viewers. Naively, a single message can generate 500 × 500 = 250,000 receipt-delivery events — receipts can dwarf your message volume by orders of magnitude (≈N² in an N-member group). This is why read receipts are aggregated (batched, debounced, sent as counts not per-user pings) in large groups, and often disabled past a threshold.

Concurrent connections (peak)

10 M

RAM to hold them (≈10 KB ea)

100 GB

Gateways @ 250K conns each

Group msg → delivery events

1 store : 499 deliver

3. Data model & API

Keep the surface small; it should express the product operation, not leak the queue, shard, or cursor mechanics underneath. Note the client-generated client_msg_id in send — that field is the idempotency key the whole retry story hangs on (deep dive 4).

API / operation	Why it exists
`send(conversation_id, client_msg_id, body)`	Submit a message; `client_msg_id` dedupes retries.
`sync(conversation_id, since_seq)`	Pull everything after the client's last-seen sequence — the catch-up path.
`connect() → WebSocket`	Open the persistent channel for live push events.
`ack(conversation_id, up_to_seq)`	Advance this device's delivery/read cursor.

The core entities and who owns them:

conversation (members, settings)message (conv_id, seq, sender, body)membershipcursor (per device: last_delivered, last_read)presence session (soft, TTL'd)

The shape that matters: message is keyed by (conversation_id, seq) — a per-conversation monotonic sequence number, not a wall-clock timestamp and not a global ID. That choice is Section 6's first deep dive, and partitioning the message store by conversation_id falls straight out of it (see lesson 07's sharding).

4. Linearized design

Follow one message from the sender's thumb to every recipient's screen. The tiers split cleanly along the cost asymmetry: stateful connections out front, stateless logic in the middle, durable log behind.

1. Sender's app writes over its open WebSocket to whichever gateway it's pinned to. The gateway is dumb on purpose: it holds the socket and forwards.
2. Gateway forwards the frame to the stateless message service, which routes by conversation_id to that conversation's sequencer (the owner of its seq counter).
3. The sequencer assigns the next monotonic seq and persists the message to the durable log first (store-before-fanout — so it survives even if every push below fails).
4. Look up the conversation's members and their presence: for each online recipient, find which gateway holds their connection and push the delivery event there; for each offline recipient, enqueue an offline push (APNs/FCM).
5. Each recipient gateway writes the frame down the recipient's socket. The client renders it and later acks, advancing its cursor.
6. On reconnect, a client does not trust that it received every push — it calls sync(conv, since_seq) and pulls any gap from the log. Push is the fast path; the log + cursor is the correct path.

sender CONNECTION TIER (stateful, RAM-bound) LOGIC + STORAGE ──────── ┌──────────────────────────────────────────┐ app ──WS────▶ │ gateway G1 (≈250K sockets, ~2.5GB RAM) │ └───────────────────┬──────────────────────────┘ │ forward frame ▼ ┌──────────────────────────────┐ │ message service (stateless) │ └───────────────┬───────────────┘ ▼ route by conversation_id ┌──────────────────────────────┐ ┌──────────────────────┐ │ per-conversation SEQUENCER │────▶│ durable message LOG │ │ assign monotonic seq │store│ (conv_id, seq, body) │ ◀── source of truth └───────────────┬───────────────┘first └──────────────────────┘ fanout to members' gateways ┌──────────────────────┼──────────────────────┐ ▼ online ▼ online ▼ OFFLINE gateway G7 ──WS▶ Bob gateway G7 ──WS▶ Cara push service ─▶ APNs/FCM ─▶ Dia's phone (best-effort, may drop silently) (wakes app → it calls sync(cursor))

The first bottleneck this exposes is not ingest QPS — it's the fan-out × presence-lookup step (4). A message to a 500-person group fires up to 499 gateway lookups + writes. That's why presence and the "which gateway holds whom" routing table must be a fast in-memory store (Redis-class), and why group fan-out is the thing you batch and cap. The sequencer in (3) is the second pressure point — a single per-conversation writer is a hot shard for a viral group (lesson 07's hot-partition problem); you mitigate by keeping the sequencer's critical section to "assign seq + append," nothing more.

5. Deep dives

5.1 Ordering — per-conversation monotonic seq beats global order, and beats timestamps

Users need to agree on the order of messages within a conversation. They have no way to observe the relative order of messages in two different conversations, so a global total order is something nobody can see and everybody pays for — it forces all writes through one coordinator. The right contract is a per-conversation monotonic sequence number: cheap (one counter per conversation, owned by that conversation's partition), sufficient (every member sorts by seq and sees the identical order), and naturally sharded (independent conversations never contend).

Why not wall-clock timestamps? Because clocks lie. This is DDIA Ch. 8's unreliable-clocks problem made concrete: two messages sent 5 ms apart from two servers whose clocks differ by 50 ms will sort in the wrong order, and worse, different readers can disagree depending on whose timestamp they trust. A monotonic seq assigned by a single owner is DDIA Ch. 9's lighter-weight cousin of total-order broadcast — total order, but scoped to one conversation so it costs one counter instead of consensus. The client uses the gaps in seq to detect loss: if it holds seq 1,2,3,7 it knows 4–6 are missing and calls sync for the range.

5.2 Push is not storage — delivery fails silently, so the log is the truth

The single most common chat-design mistake is conflating "I wrote the frame to the socket" with "the user has the message." On mobile, the OS hands you a TCP connection that looks alive but is dead — the phone moved from Wi-Fi to LTE, the NAT mapping expired, the radio slept. Your write succeeds into a buffer that never drains, and no error comes back for tens of seconds. If push were your delivery guarantee, that message is silently lost.

So the architecture inverts: persist to the durable log before fanout (step 3), and make the client responsible for closing the gap. Every device tracks a cursor (last seq it has). Push is a hint that says "there's something new, come pull." On every reconnect — and they reconnect constantly — the client calls sync(conv, since_seq) and the log replays anything it missed. This is exactly DDIA Ch. 11's log-as-source-of-truth with a consumer cursor: the broker (here, the per-conversation log) is durable and replayable; delivery is an at-least-once push over an unreliable channel, made effectively reliable by the pull-on-reconnect reconciliation. Lose every push and you lose nothing — the next sync recovers it.

device cursor reconciliation (why push loss is harmless) ─────────────────────────────────────────────────────── log: [ seq1 ][ seq2 ][ seq3 ][ seq4 ][ seq5 ] ◀ durable, source of truth pushed: ✓1 ✓2 ✗3 ✗4 ✓5 ◀ 3,4 dropped on tower switch client holds: 1,2, __ , __ ,5 → sees gap after seq2 │ ▼ on reconnect: sync(conv, since_seq=2) log replays: seq3, seq4, seq5 → client cursor advances to 5, nothing lost

5.3 Presence is soft state — heartbeats and TTL, never consensus

"Is Bob online?" is allowed to be slightly wrong. Showing a green dot for someone who disconnected 8 seconds ago harms nothing, and the cost of being exactly right is enormous. The wrong instinct is to treat presence as a consistency problem — to coordinate so every node agrees on the exact online set. That's spending consensus (lesson 10) on data with no integrity requirement.

The right model: each connection emits a heartbeat every ~30 s into a fast key-value store with a TTL (say 45 s). Online = "key exists." If the connection dies, the heartbeats stop, the key expires, and presence flips to offline automatically — no cleanup logic, no distributed agreement, no leader. Flapping (a brief drop showing offline-then-online) is damped by the TTL margin and a small client-side grace period. Presence is the textbook case for choosing availability over consistency (lesson 09): it must be cheap and always answerable, and it's allowed to be a few seconds stale.

6. Trade-offs

Choice	Buys	Costs	Choose when
WebSocket vs polling	Low-latency push, no poll overhead	Stateful connections; sticky routing; RAM-bound tier	Active conversations with live delivery
Per-conversation seq vs timestamp order	Deterministic, shardable order; clock-immune	A per-conversation owner (hot shard for viral groups)	Always — both 1:1 and group
Store-before-fanout vs fanout-first	Survives total push failure; clean sync	One log write on the send latency path	Always for durable messaging
Rich per-user receipts vs aggregated counts	"Seen by Bob" precision	Up to ~N² fan-out in large groups	Per-user only in small groups; aggregate/cap in large

The sharpest trade-off is the last one, because it's where naive designs quietly explode. Per-user read receipts are delightful in a 4-person chat and catastrophic in a 500-person one — the N × N receipt fan-out derived in Section 2 dwarfs the actual message traffic. The senior move is to make the receipt model a function of group size: precise per-user receipts below a threshold, debounced aggregate counts ("Seen by 312") above it, and an option to disable entirely. The body fan-out (1 store : 499 deliver) is unavoidable; the receipt fan-out is a product choice, so make it one.

7. Failure modes

Failure	Mitigation
Client retries a send after a timeout	Client-generated `client_msg_id` as idempotency key; sequencer dedupes on it (DDIA Ch. 12).
Gateway dies holding 250K connections	Clients detect the drop, reconnect to another gateway, and resume via `sync` from their cursor. Connections are disposable; the log isn't.
Push silently lost (network switch)	Reconcile from the log on reconnect — gaps in `seq` trigger a range sync (deep dive 5.2).
Out-of-order delivery	Client buffers and orders by `seq`, requests missing ranges before rendering.
Presence flapping	TTL margin + client grace period damp transient drops (deep dive 5.3).
Viral group sequencer hot shard	Keep the critical section to assign-seq-and-append only; batch fan-out downstream of it (lesson 07).

8. Interview Q&A

A client sends a message, times out waiting for the ack, and retries. How do you avoid storing it twice? (senior answer) The client generates a client_msg_id (a UUID) before the first attempt and reuses it on every retry. The sequencer treats it as an idempotency key: insert-if-absent on (conversation_id, client_msg_id). The first write assigns a seq; the retry finds the existing row and returns its seq instead of creating a new one. This is DDIA Ch. 12's idempotency-key pattern — the client owns the key so the dedupe survives a server that crashed mid-write.
Why not a global total order on all messages? (senior answer) Nobody can observe it — users only ever compare messages within a conversation. A global order forces every send through one coordinator (DDIA Ch. 9 total-order broadcast), which is expensive and a bottleneck. A per-conversation monotonic seq gives the only order anyone can see, costs one counter, and shards perfectly because conversations are independent.
Why store before you push, instead of pushing first for lower latency? (senior answer) Because push is best-effort over an unreliable channel and can fail silently (mobile network switches). If the store is downstream of fanout and the process dies after pushing, the message exists nowhere durable. Store-first costs one log write on the send path and guarantees the message survives total delivery failure — clients reconcile from the log on reconnect (DDIA Ch. 11, log + consumer cursor).
How do you know a delivered message actually reached the phone? (senior answer) You don't, from the socket write — it only confirms bytes left your kernel. You rely on the client's ack advancing its cursor, and on the client pulling via sync on every reconnect. Delivery is at-least-once push made effectively-reliable by pull-on-reconnect reconciliation against the durable log.
What dominates the cost of this system — and what does that imply for sizing? (senior answer) Memory for idle connections, not message QPS. 10M concurrent sockets at ~10 KB each is ~100 GB of RAM doing nothing but waiting, which sets the gateway count (≈40 boxes at 250K each). You scale the connection tier by RAM and the message tier by QPS — they're separate problems, and conflating them is the classic mistake.
Read receipts in a 500-person group — what's the catch? (senior answer) Amplification. One message can trigger up to 500 read events, each fanning out a "seen by" update to ~499 others — order N², up to 250K receipt events from one message. Make the receipt model a function of group size: precise below a threshold, debounced aggregate counts above it, disable-able. The body fan-out is unavoidable; the receipt fan-out is a product knob.
How do you represent presence without it becoming a consistency nightmare? (senior answer) As soft state. Heartbeats every ~30 s into a TTL'd key-value store; online = key exists, offline = key expired. No consensus, no cleanup job, no leader. Presence may be a few seconds stale and that's fine — it's an availability-over-consistency choice (lesson 09).
A gateway holding 250K connections crashes. What happens? (senior answer) Nothing is lost. Connections are disposable; the durable log is the source of truth. Affected clients detect the dropped socket, reconnect to another gateway, and resume from their cursor via sync. This is why the connection tier is deliberately dumb and stateless beyond the socket itself — recovery is just "reconnect and pull."

Related foundation lessons

This case is a tour through the messaging foundations. Lesson 11 (async messaging) is the spine: the durable per-conversation log with consumer cursors is exactly its broker-and-offset model, and it's what makes "push is just a hint" work. The retry-dedup story leans on lesson 12 (idempotency) — the client_msg_id is its idempotency key applied to sends. The ordering and presence decisions both invoke lesson 09 (consistency / CAP): per-conversation order is the minimum total order anyone can observe, while presence is the textbook availability-over-consistency choice. And the 40-gateway connection tier is lesson 05 (scaling & load balancing) in stateful form — you can't scale sticky WebSocket connections the way you scale a stateless HTTP fleet, which is precisely why the connection tier and message tier are separated.

Async messaging Transactions and idempotency Consistency Scaling and load balancing Partitioning

Takeaway

Chat is a memory problem disguised as a messaging problem. Size the connection tier from one number — bytes per idle socket — and 10M concurrent users becomes 100 GB of RAM and 40 gateways before you've sent a single byte. Then keep the four contracts separate: order by a per-conversation monotonic seq (cheap, shardable, clock-immune), treat push as a best-effort hint over a durable log that clients reconcile against on reconnect, make presence soft state with heartbeats and TTL, and dedupe retried sends with a client-generated message ID. Every one of those is a deliberate refusal to over-pay: no global order, no delivery-equals-push, no consensus for green dots.