Design a chat system
How do you deliver messages in order, to people who are online and offline?
Why did the app write “yes” under the wrong question?
By winter, 2,000 home cooks sell through the platform, and customers have questions the menu cannot answer. Is the dal spicy? Can the roti be made without ghee? The operations team spent every lunch hour phoning cooks to relay them.
So the platform got chat. Each message went into a table with the time the sender’s phone said it was sent. Every phone asked the server every three seconds for messages newer than the last one it had, and showed them in time order. It worked in testing.
Then a customer who orders low-sugar meals asked a cook two questions a few seconds apart: “Is the payasam low-sugar?” and “And the dal, is it mild?” The cook answered both: “No, it has jaggery.” and “Yes, mild.”
On his screen the conversation read: “No, it has jaggery.” “Is the payasam low-sugar?” “Yes, mild.” He ordered the payasam. His daughter saw the word jaggery on the dish card and phoned the office. He trusts what is written, and the app had written “yes” under his question.
The database showed what happened. His phone’s clock was thirty seconds fast, so his questions were stamped later than the cook’s answers. One question was stored twice: his signal dropped as he pressed Send, so the app sent it again.
Before reading on, decide who should give a message its place in a conversation: the phone that sent it, the phone that shows it, or the server that stores it. Large chat services store messages in wide-column databases with ids that sort by time, and they still show answers under the right questions, because the server assigns those ids and the phone clocks play no part.
Pause and predict The customer’s phone clock was thirty seconds fast, and a resent question was stored twice. What should decide the order of messages in a conversation?
What must never go wrong?
The first requirement comes from the payasam mix-up: both people see the same conversation, and every answer appears below the question it answers.
Core entities, in two minutes
A Conversation between one customer and one cook; Messages in it, each with a number; each Member’s read position; and each user’s Devices with a push token.
The estimate that changes the design
| Quantity | Working | Result |
|---|---|---|
| Messages a day | 20,000 conversations x 10 messages | 200,000 |
| Peak send rate | half of them in the 90 minutes before lunch: 100,000 / 5,400 s | ≈ 18.5/s |
| Storage a year | 200,000 x 300 B x 365 | ≈ 21.9 GB |
| Open connections at 12:30 | 15% of customers with the app open + all cooks: 30,000 + 2,000 | 32,000 |
| Heartbeats | 32,000 / one every 30 s | ≈ 1,067/s |
Pause and predict 22 GB of messages a year, 18.5 sends a second at peak, 32,000 phones connected at 12:30. Where should the design effort go?
The obvious version, and how it breaks
The first version adds one table to the ordering app. Phones poll every three seconds with “give me messages since the newest time I have”, and sort by sent_at, the time the sender’s phone wrote on the message.
It breaks in three ways, and each one has a different fix:
- The order comes from clocks nobody controls. There is no sequence number, only timestamps. A phone whose clock is fast stamps its messages late, so answers jump above questions. A slow clock is worse in a quieter way: a message stamped earlier than the reader’s “since” is never fetched at all.
- A resend is a new message. Without a client message id the server cannot tell them apart. When an acknowledgement is lost, the app cannot tell “not stored” from “stored, reply lost”. Resending is correct; storing it twice is the bug.
- Polling costs more than chatting. 32,000 phones every 3 s is about 10,667 requests a second to deliver 18.5 messages a second. Nearly every answer is “nothing new” (lesson 4.2).
Recreate the payasam conversation, then fix it.
Pause and predict Order by the server sequence. Is there any phone clock setting that puts “Yes, mild.” under the payasam question?
A mental model
- Per-conversation sequence number
- A counter kept for each conversation. The server gives every message the next number when it stores it, and everyone shows messages in number order.
- For example: Conversation 88 holds messages 1 to 41. His question becomes 42 when it is stored; her reply becomes 43. A phone that has 41 and receives 43 knows 42 is missing and asks for it.
Who gives a message its place?
Two goals pull against each other: an exact order with no clock in it, and a send path with no shared row to lock.
Packing a clock, a machine number and a counter into one 64-bit id is bit arithmetic: bits in Coding Patterns.
The second path is right about large channels: a single counter row for a channel where thousands post at once would serialise every send, and server clocks are far better than phone clocks. But time-ordered ids have a quieter flaw for catching up: an id taken on one server a few milliseconds before another can be committed after it, so a phone that fetched “after the newest id I have” may skip it. Our conversations are two people, and a missed or misplaced answer is the one thing this feature must not do.
What to remember
- Never order messages by the sender’s clock. Give each message a sequence number where messages meet: one counter per conversation, taken in the transaction that stores it.
- A client message id made once per message turns resends after a lost acknowledgement into the same message, not a new one.
- Store first, then announce. Live delivery can be at-most-once (Redis pub/sub) because gaps in the numbers show what to fetch on reconnect.
- Split gateways (connections, cheap to lose) from the chat service (decisions, stateless). Size gateways by connections and heartbeats, not by messages.
- Presence is soft state with a TTL; read receipts are one position per person, which only moves forward.
Give each message its number in the transaction that stores it.
In the real world
Real chat systems add what this one leaves out: group channels with thousands of members (where fan-out and a single counter both become hard, and many systems switch to time-ordered ids and accept their limits), media uploads through object storage (lesson 1.3), search, moderation, end-to-end encryption (where the server stores messages it cannot read, and devices keep their own copies in sync), and multi-device read state.
The core you built stays: a number decided in one place, an id that makes resends harmless, and a store that is written before anything is announced. The notification system in lesson 4.5 takes over the push worker’s job and makes it reliable.