System Design Primer · llms.txt
Beyond the primer: design questions
Written for this site, not part of The System Design Primer. The sources it draws on are listed under Further reading.
A chat system lets people exchange short messages in near real time, one to one or in groups, across several devices each. It looks simple until you list what users take for granted: messages show up in the same order for everyone, nothing is lost when a phone goes through a tunnel, the laptop knows what you read on your phone, and the little "delivered" and "read" marks are accurate.
This question comes up often because it touches long-lived connections, ordering, storage design for an append-heavy workload, and fan-out. The primer's object-oriented chat server covers the class structure. This chapter is about the distributed system underneath. It assumes you've read real-time communication and unique ID generation.
Start by pinning down scope with the interviewer. A reasonable set:
Then size it. These numbers are assumptions for a large consumer app, not figures from any real product:
Two things stand out. The write rate is high and append-only, which shapes storage. And the connection count, not the message rate, sizes the front tier. See estimation for more on this kind of arithmetic.
Clients talk to the system over two channels.
A WebSocket to a connection server carries everything real time, in both directions. A small set of frame types is enough:
client -> server send {conv_id, client_msg_id, body}
server -> client ack {client_msg_id, msg_id, seq}
server -> client message {conv_id, msg_id, seq, sender_id, body, sent_at}
client -> server delivered {conv_id, up_to_seq}
client -> server read {conv_id, up_to_seq}
client -> server sync {cursor}client_msg_id is a random ID the client picks before sending. If the connection drops before the ack arrives, the client resends with the same ID, and the server uses it to drop the duplicate. That gives you at-least-once delivery on the wire with exactly-once storage.
Plain HTTPS handles everything that isn't latency sensitive: creating groups, changing membership, uploading attachments, and fetching older history page by page.
The core tables:
| Table | Key | Holds |
|---|---|---|
messages | partition: (conv_id, bucket); sort: seq descending | sender, body, msg_id, timestamp |
conversations | conv_id | type (1:1 or group), member list, last_seq |
user_conversations | partition: user_id; sort: updated_at | per-user view: last_read_seq, muted, preview |
devices | user_id, device_id | push token, sync cursor |
Unread counts fall out for free: last_seq − last_read_seq. You never count rows.
The path of one message:
send frame on its WebSocket. Connection server A is stateless apart from its sockets. It forwards the frame to the chat service.client_msg_id.user_id to a list of (device_id, connection_server). Connection servers write to it when a socket opens and delete on close, with a TTL so entries from crashed servers expire.Connection servers often sit behind a layer 4 load balancer, because WebSockets are long-lived TCP connections and there's little for the balancer to do with the payload. A layer 7 balancer works too, as long as its idle timeouts allow long-lived connections (see real-time updates). When one of them dies, its 250,000 clients all reconnect at once. Clients must back off with random jitter, or the reconnect storm takes down the next server. See reliability patterns.
Presence is the "online" dot. The connection server already knows when a socket is alive, so presence is a by-product: the client sends a heartbeat every 20–30 seconds, and the presence store keeps user_id → last_seen with a TTL a bit longer than that. No heartbeat, the key expires, the user shows as offline.
The expensive part is telling others. If a user with 300 contacts flips state 20 times a day, and you push every flip to every contact, that's 6,000 presence messages a day from one person. Most products cut this down by only pushing presence to people who currently have a chat with that user open, by fetching it lazily when a chat screen loads, by delaying "offline" by a few seconds to absorb network flaps, and by not showing it at all in large groups.
Users only care about order within a conversation. Nobody can tell whether a message in one chat was stored before a message in another. That lets you pick the conversation as the unit of ordering.
The server, not the client, decides the order. Phone clocks drift and can be set by hand, so sent_at from the device is only for display.
There are two common ways to do it:
last_seq for each message. The result is gap-free: 41, 42, 43. A client holding 41 that receives 43 knows it missed one. The cost is that every message in a conversation goes through one serialization point, which caps the throughput of a single very busy group. That cap is far above anything a human group produces.A good answer uses both: a globally unique msg_id for references (replies, reactions, deletion), and a per-conversation seq for ordering and gap detection. When two people send at the same instant, whichever reaches the sequencer first is first. That's fine, because there was no "real" order between them anyway. What matters is that everyone sees the same one.
The access patterns are narrow:
seq S.There are no joins and no cross-conversation transactions. That points to a wide-column store such as Cassandra, ScyllaDB or HBase, or a key-value store with sorted keys:
CREATE TABLE messages (
conv_id bigint,
bucket int, -- e.g. days since epoch / 7
seq bigint,
msg_id bigint,
sender_id bigint,
body text,
PRIMARY KEY ((conv_id, bucket), seq)
) WITH CLUSTERING ORDER BY (seq DESC);Why this shape works:
seq order. "Latest 50" and "everything after 1,042" are single sequential reads.conv_id spreads load across nodes with no hot spot other than very busy conversations (sharding and consistent hashing).bucket caps partition size. Without it, a group that has been active for five years becomes one enormous partition. Discord's engineering blog describes exactly this pattern: partition by channel plus a fixed time window.A relational database can work at smaller scale, and it's easier to reason about. At 300,000 appends a second you would be sharding it by conv_id and avoiding joins anyway, which leaves you with a hand-built version of the same thing.
There are three states, and each has a clear owner:
| State | Meaning | Who records it |
|---|---|---|
| Sent | The server stored it durably | Chat service, when it acks the sender |
| Delivered | A recipient device received it | The device sends delivered |
| Read | The recipient saw it on screen | The device sends read |
Don't store a receipt row per message per reader. Store a high-water mark per member per conversation: "user 7 has read up to seq 1,042". One small update covers any number of messages, because reading message 1,042 implies reading everything before it. The sender's app compares each message's seq with the other members' marks to draw the ticks.
In a group, "read by 14 of 30" is a count of members whose mark is at or past that seq. That's cheap for 30 members and wasteful for 5,000, which is one reason large groups often drop read receipts.
A user has a phone, a laptop and a tablet. Each needs every message, including the ones the user sent from another device, plus read state.
Treat the sender's own other devices as recipients, so they get new messages through the same path. Then give each device a cursor that records how far it has synced. Two designs are common:
seq it has for each conversation. On reconnect it asks "which conversations changed since time T?", then fetches each one after its stored seq. That's simple, but a user in 400 chats means many small requests.Either way, the device advances its cursor only after it has saved the events locally, so a crash mid-sync just repeats some work. If a device has been offline so long that its cursor points past the log's retention, the server tells it to do a full resync of recent conversations.
When the user reads a chat on their phone, the phone sends read up_to_seq. That updates last_read_seq and becomes an event in the change log, so the laptop clears its unread badge too.
A message to a group is written once to storage, then delivered to every member's online devices. That's the same split the primer's Twitter design makes between storing a tweet and fanning it out, with a much smaller fan-out per message.
The delivery cost is linear in group size. A message in a 500-member group, with an average of 1.5 online devices per member, is 750 socket writes. Group size limits exist for this reason, and so does the fact that big groups behave differently. Reasonable rules:
Fan-out happens off the sender's critical path. The sender is acked as soon as the message is stored. Delivery work goes onto a queue partitioned by conv_id, which keeps each conversation's deliveries in order and absorbs bursts.
user_id, keep it in memory, and accept that it's slightly stale. A message sent to a dead connection server fails, and the device catches up through sync when it reconnects.seq vs time-ordered IDs. Gap detection and simple sync, at the cost of a serialization point per conversation.The client is probably ordering by device timestamp, or by arrival order over two different connections. In this design the chat service assigns a per-conversation seq when it stores each message, and every client sorts by seq. Two messages from the same sender over the same socket reach the sequencer in the order they were sent, as long as the connection server forwards each conversation's frames in order, so they get increasing seq values and display correctly everywhere. A retry is the exception: if the first send times out and is resent after the second went through, it gets the later seq. Clients that need strict order hold later sends until earlier ones are acked.
It opens a WebSocket, registers in the session registry, and sends sync with its stored cursor. The server returns the events after that cursor in pages: new messages, read marks set from other devices, membership changes. The laptop saves each page locally before advancing its cursor. If the cursor is older than the change log's retention, the server replies "resync", and the laptop instead fetches the latest messages of each recent conversation and starts a fresh cursor.
Reading is monotonic: if you've read message 1,042 you've read everything before it, so one number captures it and one small write updates it no matter how many messages you just scrolled past. Per-message flags would cost a write per message per reader. It gets expensive in very large groups, because every read mark is an event other members' devices may need, and showing "read by" counts means comparing thousands of marks. That's why large groups usually turn receipts off.
Messages being forwarded to that server fail, and its session registry entries are stale until their TTL expires. No messages are lost, because they were stored before fan-out; affected devices catch up through sync when they reconnect. The danger is 250,000 clients reconnecting in the same second, so clients use exponential backoff with random jitter, and the load balancer spreads them over the remaining servers. You also need enough spare capacity for those servers to absorb the extra connections.
With E2EE the server only holds ciphertext, so it can't build a search index. You either search on the device, over its local copy of history (limited to what that device has synced), or you give up E2EE for the conversations that need server search. That trade-off is a product decision, not just a technical one, so it's worth naming it in the interview rather than quietly picking one side.
Previous: Design a notification system · Next: Design search autocomplete (typeahead)