Two phones sit on a table. One types “On my way”, presses send, and the other buzzes before the thumb has left the screen. It feels like nothing happened in between.
Now the interviewer says: “Design that.” Behind it, millions of phones hold a connection open at once. A message must survive a dropped signal in a lift, never show twice on a retry, and reach a friend who switched their phone off for the weekend, in order, on Monday.
The whole design comes down to one habit: store the message first, then push it. This lesson shows why, and what the rest of the system needs to make that safe.
- The system design interview framework and back-of-envelope estimation.
- Message delivery guarantees, because a chat send is that lesson with a human on both ends, and the news feed lesson for sending one item to many readers.
Why is “at-least-once delivery plus an idempotent receiver” the usual answer instead of “exactly once”? Because networks fail between the work and the acknowledgement, so retries are unavoidable, and a receiver that can recognise a repeat makes retries harmless.
- Store a message durably before pushing it, so a missed push loses nothing.
- Make sending idempotent: the client attaches its own id and a retry never creates a second message.
- Let the server number messages per conversation, because client clocks cannot order them.
- A device keeps a cursor, the last sequence number it saw, and resumes from it after any gap.
- Messages are durable and typing is ephemeral. Keep them in separate lanes.
Design a chat system end to end in 45 minutes: choose how connections are held, make sends safe to retry, keep messages in order, catch up offline devices, and handle groups, receipts and typing.
Step 1: Pin Down the Problem#
Ask first, then state your assumptions out loud: one-to-one or groups too, how big a group gets, one device or several, how long history lives, what “delivered” means, and whether messages are end-to-end encrypted. Here: both, up to 100,000 members (assumed), several devices, kept forever (assumed), “delivered” means a device of the receiver has it, and encryption is a follow-up.
Functional requirements:
- Send a message in a one-to-one chat or a group.
- Receive messages in real time while online.
- See history, and catch up on everything missed while offline.
- See whether a message was sent, delivered and read.
- Attach photos and short videos. The upload design is in the companion lesson; here a message carries only a reference.
Out of scope (say these out loud):
- Voice and video calls, search and reactions. Each is its own problem. End-to-end encryption is a follow-up in the companion lesson.
- Push notifications as a service, the next problem. Here a notification only wakes a device.
Non-functional requirements, each with a number. These are assumptions you announce:
- Fast: a few hundred milliseconds to an online friend.
- Durable: an acknowledged message is never lost.
- Ordered: every member of a conversation sees messages in the same order.
- Available: sending still works if one server dies.
- Consistent where it counts: per conversation, order beats availability. In CAP terms the log leans consistent, so if a conversation’s owner is unreachable, its sends wait for a standby rather than risk two orders. In PACELC terms (the trade-off with no split), the ack waits for the durable write, paying latency for order. Presence and typing lean available and may be stale.
- Scale: assume 10 million daily users. Step 4 turns that into numbers.
Step 2: Entities and API#
User id
Conversation id, members
Message conv_id, seq,
sender, text,
client_msg_id
Over the connection:
send {conv, client_msg_id, text}
-> ack {client_msg_id, seq}
-> or 403 not a member,
413 too large, 429 slow down
message {conv, seq, sender, text}
GET /sync?since=<cursor>&limit=50
-> messages, next_cursor, more
POST /uploads -> presigned URLEvery call carries a per-device token, and the server checks membership on each send. Pages use the cursor, never offsets, because new messages shift offsets. Two fields do the heavy lifting. client_msg_id is made by the sender, so a retry can be recognised. seq is made by the server, so every member agrees on the order.
Matrix’s send call is PUT /rooms/{roomId}/send/{eventType}/{txnId}. The client-made transaction id lets the server recognise a retransmission and return the same response, including the original event id. Reading uses /sync, whose next_batch token the client passes as since next time.
Step 3: A Design That Works#
Start with the simplest thing. Every online client asks the server every two seconds: “any new messages since the last one I have?”
This is polling. It is correct, and where many candidates stop.
Assume 2 million clients are online at the same time and each asks every two seconds. How many requests a second is that, and what does the typical answer say?
Call it 1,000,000 requests a second (2,000,000 clients × 0.5), almost all answered “nothing new”, and a message can wait two seconds. The fix is to let the server speak first.
Step 4: Estimate What Matters#
Assume 10M daily users
40 messages sent each a day
Messages: 400M / 86,400
≈ 4,600/s
Peak (assume 5x): 23,000/s
Online at peak: 20% = 2M
Per gateway: 100,000 connections
-> 20 gateways, plus sparesThen storage and upkeep:
Storage: 400M x 200 B
= 80 GB a day (≈ 29 TB a year)
Heartbeats: 2M / 30 s
(assume a ping every 30 s)
≈ 67,000 pings/sEach line decides something:
- 20 gateways means connections, not messages, size the front of the system.
- Assume 100,000 connections per gateway; it depends on hardware and software, so measure yours. Exactly 20 leaves no room: if one dies, its devices must fit on the other 19. Run a few spares.
- 67,000 pings a second is the quiet cost of keeping connections alive. Zulip’s queue servers send a heartbeat at least every 45 seconds or so because some NAT servers kill connections idle for over 60 seconds.
- 29 TB a year is the reason messages need a store built for appends, and a plan for old data (text only: media would dwarf it).
- ≈ 4.6 MB a second of message text at peak (23,000 × 200 B) means bandwidth is not the constraint. Copying to group members and media are what multiply it.
Step 5: Deep Dives#
Six questions decide this design. Follow the interviewer if they jump ahead.
How Does a Message Reach an Online Friend?#
A chat is events flowing to subscribers. The question here is the last hop, down to one phone.
As in step 3. No special server, and it works behind any proxy.
The server answers the moment something arrives. In long polling, that is an HTTP request held open. A WebSocket is a connection both sides can use at any time.
Real systems choose differently. Zulip’s documentation says long polling works everywhere, unlike WebSockets, which have a decreasing but nonzero level of client compatibility problems. Mastodon’s streaming server accepts WebSockets and HTTP event streams.
Put the connections in their own layer of gateways. A chat service does the thinking and a route table says which gateway holds each device. A load balancer or small discovery service picks a gateway with spare room, and that gateway writes the device’s route with an expiry its heartbeat keeps refreshing. If the gateway dies, its routes vanish on their own and the next connection overwrites them. To deliver, the service looks up the receiver’s gateways and hands them the message to push down the open connections.
Is There a Version Without a Route Table?#
Yes. Let a Pub/Sub system do the routing. Gateways subscribe to channels for what they hold, and the chat service publishes instead of looking up routes. Since Redis 7.0 sharded Pub/Sub keeps a message inside the shard that owns the channel instead of sending it to every node. It is at-most-once, so it can only be the fast path. The real decision is what a channel is named after:
| Channel per user | Channel per chat | |
|---|---|---|
| Gateway subscribes to | each user it holds | each chat its users are in |
| Publishes per message | one per member | one |
| Join or leave a chat | nothing to change | resubscribe |
| Fits | one-to-one and small groups | big groups |
A 500-member group costs 500 publishes per user channel but one per chat channel, at the price of every gateway tracking each chat its users are in. A common hybrid: per user by default, per chat once a group passes a size you pick and measure.
What Happens When a Gateway Dies?#
Assume a gateway holding 100,000 connections fails and every device reconnects and reads from its cursor.
100,000 devices reconnect
all at once: 100,000 in 1 s
spread over 30 s:
100,000 / 30 ≈ 3,300/s
peak messages: 23,000/sAll at once is about four times the assumed peak message rate (100,000 ÷ 23,000 ≈ 4.3). A random wait before each retry turns it into ≈ 3,300 reads a second.
Why Store Before You Push?#
The push can miss, for example when the receiver’s connection drops at the wrong moment. Redis documents Pub/Sub as at-most-once, so a message missed during a disconnect is lost for good. If your push path is Pub/Sub, the durable log underneath is what saves you.
How Do You Send Safely and Keep Order?#
The sender cannot tell “message lost” from “ack lost”, so it must be able to retry, and the receiver must recognise a retry.
Sort by the time on the sender’s device.
The server stamps each message when it arrives.
Route every send for a conversation to the one server that owns it, chosen by sharding on the conversation id. That owner hands out 1, 2, 3 in the order it saves messages. Redis Streams show the idea: an entry id is <ms>-<seq> and an explicit id must be greater than every id already in the stream.
Pair it with an idempotent send. The client puts its own id on the message. The server keeps a record of ids it has seen.
client_msg_id = abc
seen abc?
no: seq = 58, save, ack(58)
yes: ack(58) again, no saveA Redis Stream log can do the dedupe for you. From Redis 8.6, XADD accepts IDMP with a producer id and an idempotent id, and a repeat of the same pair returns the original entry instead of adding a second one.
The memory is short: by default Redis keeps 100 ids per producer for 100 seconds, tunable with XCFGSET. Size it to how long clients keep retrying, and check your version first.
Where Does the Log Live?#
Key the log by conversation id and sort it by sequence number. One conversation’s messages then sit together and read back in order, and the conversation id is also the shard key that picks the owner. Any store with a partition key and a sort key fits; the access pattern matters more than the product.
Watch hot partitions. Discord’s engineering post partitions messages by channel plus a bucket, a static time window, describes busy channels becoming “hot partitions” that slowed whole clusters, and a data service in front queries the database once when many users ask for the same row. Bucketing a huge channel by time is our reading of the idea.
The server numbers, the client retries, the cursor resumes. The server decides the order. The client may retry as often as it likes. The cursor is how a device picks up again after any gap.
What About Devices That Were Offline?#
The log is the source of truth; a device that missed a push rebuilds from it.
Keep a queue of undelivered messages for each user. Push each new message into the queue of every member who is offline, and flush the queue in order when they reconnect.
The device keeps the last sequence number it saw. On reconnect it asks for everything after that, in pages. Matrix does this with /sync and a since token. When too many events arrived, it returns a “limited” timeline with a gap, and the client pages back to fill it.
Let the server forget cursor state it cannot afford to keep. Zulip’s clients send last_event_id as an acknowledgement, so the server can delete older events. Idle queues are garbage-collected after 10 minutes by default, and a returning client that gets “queue not found” simply reloads its state.
A push notification only wakes a device. It tells the phone to reconnect and resume, and it carries no guarantee that the message arrives.
How Does an Online Device Notice a Missed Push?#
Numbers in a conversation go up by one, so a gap is visible. The device does not need to know why 58 went missing. It treats the gap like a short offline spell and reads from its cursor.
Two backstops catch what a gap cannot show:
- The lost last message. If the final message of a quiet chat goes missing, no later number reveals it. So a device syncs from its cursor on every reconnect, and now and then while open.
- The silent dead connection. A socket can die unnoticed. The gateway closes a connection that misses a few heartbeats, so the device reconnects and resumes.
What About a User With Several Devices?#
Matrix treats each desktop client, browser and phone as its own device with a device_id, which shapes three decisions:
- Connections, routes and cursors are per device. One message may need pushes to several gateways, and a phone off all weekend and a laptop open all day hold different cursors.
- The sender’s other devices get the message too. Zulip sends an event to every client the sender controls as well as the recipients, so the sending device can run the same code as every other client.
- The read marker belongs to the user, not the device. Matrix allows only one receipt per user and receipt type (per thread), so reading on the laptop clears the unread count on the phone.
“Delivered” needs a definition. “Any device of the receiver got it” is a common, simple choice. It is a judgement, so say it out loud.
How Do Groups, Receipts and Typing Fit?#
A group is the news feed problem again: copy each message into every member’s inbox, or store it once and let members read it. For chat, store it once, in the conversation log. Members hold a cursor into that one log, which is why a group of 500 costs one write, not 500.
A receipt per message is a lot of traffic, so Matrix uses “read up to here” markers: one marker means every earlier message is read.
A common way to show status is three states. This is a design choice, not a standard:
- Sent: the server saved it and returned the ack with its
seq. - Delivered: a device of the receiver got it.
- Read: the receiver’s read marker passed its
seq.
Typing and presence take a different lane:
-
Typing is ephemeral. Matrix says typing notifications are not part of the room’s event history, that the server keeps no list of users who are not typing, and that clients keep re-sending while the user types, every ≈ 20 to 30 seconds at most.
-
Presence (who is online) is a judgement call. Broadcasting every change is expensive, so limit it to people looking at that person, and fetch it when a big group opens instead of pushing. For “last seen”, write the time when a connection closes, not on every heartbeat.
The building block is a heartbeat that keeps refreshing a key that expires on its own. Mastodon’s streaming server does this for subscribed channels, every 6 minutes with an expiry of three times that. It tracks subscriptions, not who is online, but if the pings stop, the key expires.
The Final Design in One Picture#
Follow one message:
- Device A sends it with a
client_msg_idto a gateway. - The chat service checks the id, assigns the next sequence number, saves it to the log and acknowledges.
- It looks up each member’s devices in the route table and hands the message to their gateways to push.
- A member with no connection gets a notification that wakes the device, which later asks for everything after its cursor.
Photos and videos travel beside this path, with only a reference in the message.
Where the Production Detail Lives#
The core answer ends here. What interviewers probe once it stands up is in the companion lesson, Design a Chat System: Media, Failure Modes and Follow-Ups:
| If you are asked | The companion covers |
|---|---|
| ”What happens when X dies?” | A failure table, component by component, with why each is safe |
| ”What about encryption, abuse, regions, cost?” | Short answers to eight follow-ups, plus a 45-minute plan |
| ”How do photos and videos work?” | Three upload designs, from the chat path to resumable uploads and cached delivery |
What Each Level Should Show#
| Level | Expected in the room |
|---|---|
| Mid-level | WebSocket or long polling, a store for messages, a rough scale estimate. Needs a hint about retries and ordering. |
| Senior | Gateways and a route table, an idempotent send, per-conversation sequence numbers, a cursor for offline catch-up. |
| Staff+ | Store-then-push reasoning, reconnect storms, safe resets, ephemeral versus durable lanes, owner takeover, failure and consistency trade-offs stated, and what to build first. |
Red Flags and Green Flags#
“Use WebSockets and Redis Pub/Sub to forward messages to the receiver.” Nothing about retries, order, or a friend who is offline.
“I’ll store each message in a per-conversation log first, then push it as a fast path. The client sends its own id so retries are safe, the server numbers messages, and each device resumes from a cursor, so a missed push loses nothing.”
Spending the time on WebSocket versus long polling and never reaching “what if the message is sent twice, or the receiver is offline?”. Transport is one deep dive; durability and order are the rest.
Try It: A Channel With 100,000 Members#
Change one variable. A channel has 100,000 members. Assume 20% are online and the channel sees 10 messages a second.
- How many live pushes does one message cause?
- How many a second at that rate?
- How do you change the design?
Hint
Multiply the members by the share online, then by the message rate. Then ask what you must store per member.
One reasonable answer
100,000 x 20% = 20,000 pushes
x 10 msgs/s = 200,000/sOne message causes 20,000 live pushes, and the channel makes 200,000 a second. The gateways can take it only if each message is stored once. Do not copy the message into 100,000 inboxes. Keep one log, give each member a cursor, publish once to a channel per chat, and push a small nudge that members fetch from. Drop typing and presence for channels this big.
Expect: “What if the same message is sent twice?”, “How do you keep order?”, “What if the receiver is offline?”, then the group of 100,000. Give each answer a trade-off and a number.
Check Yourself#
1.Why store a message before pushing it?
The push can miss. If the message is already in a durable log, the device picks it up from its cursor later.
2.A phone sends a message, the connection drops before the ack arrives, and the phone retries. How do you avoid a duplicate?
The client attached its own id to the message. The server has already seen that id, so it returns the original acknowledgement instead of saving a second message.
3.Why not order messages by the time on the sender's phone?
Clocks disagree, so messages can reorder or tie. The server assigns an increasing sequence number per conversation, through one writer.
4.An online phone holds seq 57 and the next push is seq 59. What does it do?
58 is missing, because numbers go up by one. It asks the log for everything after 57, as after being offline, then moves its cursor.
Tomorrow, draw the final design from memory and trace a message through one failure at a time: receiver offline, ack lost, gateway dead.
In One Picture#
Requirements
send, read, catch up, receipts
Scale
≈ 23,000 msgs/s peak, 2M conns
Connections
gateways + route table
Send
client id, server seq number
Offline
log + cursor per device
Lanes
durable messages, live typing
Rule
store first, then pushConclusion#
The 60-second answer: a chat system is a durable log with a fast path in front. Devices hold connections to gateways; the chat service dedupes by client id, numbers each conversation through one owner, stores the message, acks, then pushes. Offline or gapped devices resume from a per-device cursor. Typing and presence stay out of the log, and media goes to blob storage with a reference.
Which failure would you walk through first in the room? Tell us in the comments.
- The delivery guarantees behind a send: message delivery guarantees.
- One item to many readers: design a news feed.
- The production side of this answer: media, failure modes and follow-ups.
- Next in Module 4: design a notification service, where the device is asleep and a message must still reach it once.
