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. That means holding a connection open for every user who has the app in front of them, and knowing which of a hundred servers holds the connection for the person you are messaging. One requirement, holding state per user, is what makes this question different from everything else.
Step 1: Understand the problem
Chat questions go wrong in the first five minutes, when a candidate starts drawing WebSockets before anyone has agreed how big a group is or whether messages can be lost.
| You ask | They say | What it settles |
|---|---|---|
| One to one, groups, or both? How big can a group be? | Both, and groups cap at about 500. | The delivery cost of one message. At 500 members a send becomes 500 deliveries, which is fine. At 500,000 it is a broadcast problem and a completely different design. |
| How many people are connected at once? | About 50 million at peak. | The resource that runs out. Connections, not requests. That single number is why the design has a tier whose only job is holding sockets. |
| Can a message ever be lost? | Never. Duplicated is annoying, lost is unacceptable. | Persist before delivering, and give the client a way to detect gaps. It also tells you which side of the at-least-once trade to land on. |
| Does order have to hold across conversations? | Only within a conversation. | A per conversation sequence number, assigned by the server. Global ordering would need consensus and nobody would notice the difference. |
| What happens to a message for someone who is offline? | They get it when they come back, on any device. | The store is the source of truth and delivery is a push on top of it. Clients sync by sequence number rather than replaying a queue. |
| Do we need end to end encryption? | Not today. | A large cut, and worth naming: with E2E the server cannot search, moderate or generate previews, and group key management becomes its own design question. |
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.
Back of the envelope
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.
Step 2: Propose the high level design
Choosing the transport
The API
{
"type": "send",
"conversationId": 9912,
"clientMsgId": "c_7f3a91b2",
"body": "on my way"
}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 whole system on one whiteboard
Walking Figure 1:
- The sender already has a socket open to connection server 47. Which server that is was decided once, at connect time, by the discovery service.
- The message arrives over that socket. The connection server does no thinking: it hands the message to the message service and goes back to reading sockets.
- The message service asks the session registry where the recipient is connected, if they are connected at all. For a group it asks the group service for the member list first and then does this once per member.
- It writes the message to the store before delivering it. This ordering is the whole durability story and it is worth saying out loud.
- Delivery is a direct call to the connection server holding the recipient, which pushes it down the socket.
- If nobody is connected, the message is already safe in the store, and a push notification nudges the device instead. The client will pull what it missed by sequence number when it opens.
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.
Step 3 in Figure 1 is a lookup that has to answer in about a millisecond, for 50 million connected users, and be correct the instant someone's phone loses signal. How would you build the session registry?
Step 3: Design deep dive
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.
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.
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.
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?
- 50 million concurrent connections. Connections, not requests, are the resource that runs out.
- About 100,000 sockets per connection server, so a few hundred servers exist only to hold them open.
- A 500 member group turns one send into 500 deliveries. The size cap is a design decision.
- Persist before delivering. A message delivered but not stored disappears when the app is reinstalled.
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.
