Design a chat system
Every other system in this course is request and response. The client asks, the server answers, and between requests the server has forgotten the client exists.
Chat is not that. The server has to push, which means it has to hold a connection open for every user who has the app in front of them, and it has to know which of a hundred servers is holding the connection for the person you are messaging. That one requirement, holding state per user, is what makes this question different from everything else.
A user is connected to server 12. Someone on server 47 sends them a message. How does server 47 find out where to deliver it?
What you are building
- One to one messaging. Delivered in near real time to a device that is online.
- Small group chats, up to about 500 members. The size cap is a design decision, not an accident.
- Message history, and delivery when the recipient was offline. A message must never be lost because nobody was listening.
- Sent, delivered and read receipts. Cheap to describe, surprisingly expensive in groups.
- 50 million concurrent connections at peak.
- Message delivered in under 500ms when both parties are online.
- Messages are never lost, never duplicated, and never shown out of order within a conversation.
- A server restart must not lose messages or drop users permanently.
- Voice and video calls. Different transport entirely, and the signalling is its own design question.
- End to end encryption. Worth one sentence: it makes server side search and moderation impossible, which is a product decision more than a technical one.
- Broadcast channels with millions of members. That is the news feed fan out problem wearing a different hat.
The numbers
Connections, not requests, are the resource that runs out.
23,148 messages a second is not a hard number on its own. The hard number is 1,000 stateful servers, because now every message needs to find the right one, and every deploy disconnects tens of thousands of users at once.
Choosing the transport
The design
Two things about Figure 1 are worth defending out loud. The connection servers hold no business logic, so they can be restarted and scaled independently of everything else. And the message is persisted before it is delivered, not after, because a message that was delivered but not stored disappears when the recipient reinstalls the app.
Deep dive one: finding the recipient
This is the question the whole design turns on, and it is the one the interviewer will ask first.
It will be wrong. A server dies and its entries linger until the TTL expires, so deliveries route to a machine that is gone. That has to be survivable: delivery failure means fall back to stored-and-offline, and the client picks the message up when it reconnects. A design that requires the registry to be correct is a design that breaks every time a server restarts.
Deep dive two: ordering and duplicates
“Messages must not arrive out of order” sounds like it needs a global clock. It does not, because ordering only has to hold within one conversation, and one conversation is small.
Give every conversation a sequence number, assigned by the message service when it persists. Clients render by sequence number, not by arrival time or by a client timestamp, which is untrustworthy because phone clocks are wrong and users travel through time zones.
Duplicates come from retries. A client sends, the network drops the acknowledgement, the client retries, and the message is now stored twice. Fix it the same way as everywhere else in this course: the client generates an id for the message, and the store has a unique constraint on it. A retry then collides and returns the original.
Gaps come from a client being offline briefly. Since the client knows the last sequence number it holds, it asks for everything after that on reconnect. A missing message is something the client can detect and repair on its own, which is much better than hoping the server noticed.
Deep dive three: groups, and the number that surprises people
A group of 500 members means one sent message becomes 500 deliveries and, if you are not careful, 500 read receipts each of which is itself a message to 500 people. That is 250,000 messages from one person typing “ok”, and it is how group chat features get quietly capped.
Three things keep it bounded. Cap group size, because the cost is quadratic and no amount of engineering changes that. Aggregate receipts rather than forwarding each one, so clients get a count and fetch details only when someone taps. And fan out to connection servers rather than to users: if 40 of the 500 members are on server 12, that is one message to server 12 with a list of recipients, not 40 messages.
That last one is the general trick. Deduplicate the fan out by destination, not by recipient.
The data model
| conversation_id | bigint | PK | Partition key. All of one conversation lives together, which is exactly how it is read. |
| seq | bigint | PK | Clustering key, ascending. Ordering within a conversation, assigned server side. |
| client_msg_id | char(32) | UQ | Generated by the sender. The unique constraint is the whole duplicate defence. |
| sender_id | bigint | ||
| body | varchar(4096) | ||
| created_at | timestamp | Server time. Client clocks are wrong often enough to matter. |
The API
{
"type": "send",
"conversationId": 9912,
"clientMsgId": "c_7f3a91b2",
"body": "on my way"
}Break it
Trade-offs
| Choice | What you gain | What you pay | Pick it when |
|---|---|---|---|
| WebSocket over long polling | Full duplex, low per message overhead, and no gap where the client is not listening. | Stateful servers, so deploys disconnect users and load balancing has to be connection aware. | Real time chat. Long polling stays as a fallback for networks that block upgrades. |
| Session registry over broadcasting to all servers | One small key read finds the recipient, and message traffic scales with messages rather than with server count. | Shared state in the delivery path, and it is stale for a few seconds after any server dies. | Any connection fleet past a handful of servers. Broadcasting is fine at ten and hopeless at a thousand. |
| Persist before deliver | A message can never be seen by a recipient and then vanish, which is the failure users never forgive. | A storage write in the delivery path, so latency depends on the store. | Always, for anything a person will look for again later. |
| Per conversation sequence numbers | Exact ordering and gap detection with no global clock and no coordination between conversations. | No total order across conversations, so a unified view of everything is only approximately ordered. | Always. Ordering across conversations is not something users can perceive anyway. |
Interview replay
Checkpoint
1. Why persist the message before delivering it rather than after?
2. What is the actual cause of a reconnect storm after a network blip?
3. A 500 member group generates far more traffic than expected. What is the biggest contributor?
The thing that makes chat different is that servers hold state: a WebSocket per online user, so a message has to find the one server holding the recipient's socket. I would keep a session registry, a small Redis mapping user id to connection server, written on connect and refreshed by heartbeat. Send goes to the message service, which looks up the recipient, persists the message, then pushes it to that server, and if there is no entry the recipient is offline so it is already stored and a push notification goes instead. The registry is a cache and it will be stale after a crash, so failed delivery has to fall back to the offline path rather than error. Ordering is per conversation with a server assigned sequence number, which also lets a reconnecting client detect and fetch gaps, and duplicates are handled by a client generated message id with a unique constraint. The failure I would design for is the reconnect storm: drain connections on deploy and randomised backoff on the client.
