Chat system
A chat system delivers messages between people in real time, keeps them forever, and catches up devices that were offline. The core design is a per-conversation log: one owner assigns each message the next sequence number in its conversation and persists it before delivering it. Everything else follows. Devices hold long-lived WebSocket connections to stateless gateways; a session registry says which gateway holds whom; ordering, gap detection, receipts and sync are all “compare sequence numbers”. Send is O(1) plus O(online recipients) pushes; storage is a wide-column table keyed by (conversation, seq), about 4 TB a day at 20 billion messages.
The problem
Section titled “The problem”WhatsApp, Messenger, Slack, Discord, iMessage: two or more people exchange short messages, and each expects them to arrive instantly, once, in order, on every device, including the phone that was in a tunnel for ten minutes.
The goals pull apart:
| Goal | What it means | Pulls toward |
|---|---|---|
| Low latency | A message appears for the recipient in ~100-300 ms | Persistent connections, push not poll |
| Never lose a message | Once the sender sees “sent”, it survives any crash | Durable write before ack |
| Order within a conversation | Replies never appear above what they reply to | A single sequencer per conversation |
| Work offline and on many devices | Catch up after hours away; phone and laptop agree | Sync by cursor, server-side state per device |
| Huge scale of idle connections | Hundreds of millions of sockets, mostly quiet | Cheap, stateless connection servers |
Requirements and scope
Section titled “Requirements and scope”| In scope (typical) | Ask about | |
|---|---|---|
| Functional | 1:1 and group chat (up to a few hundred members), text, sent / delivered / read receipts, online presence, history on all devices. | Group size limit? Channels with 100K members (that’s a broadcast problem)? Edits, deletes, reactions? |
| Scale | 500M DAU, 40 messages per user per day, 20% connected at peak. | Peak hour vs average? Are there huge groups? |
| Latency | p99 send-to-deliver under ~500 ms when both are online. | Global users? Cross-region conversations? |
| Consistency | Total order within a conversation. No order across conversations. At-least-once on the wire, exactly-once on screen. | Is it OK for a recipient to briefly see a gap? |
| Durability | A message acked as sent is never lost. Kept indefinitely. | Retention policy? End-to-end encryption (then the server stores ciphertext)? |
| Out of scope | Voice and video, media storage pipeline, search, spam. |
Back of the envelope
Section titled “Back of the envelope”Drag the assumptions. Throughput and storage are big but ordinary. The unusual number is concurrent connections, which sets the size of the gateway fleet.
What to say out loud: “About 230K messages a second, 700K at peak, and 4 TB a day, so the store is a wide-column database partitioned by conversation. 100 million open WebSockets need a fleet of hundreds of gateway servers, which must be stateless so a crash only means reconnects.”
API and data model
Section titled “API and data model”The client speaks a small protocol over one WebSocket. HTTP is only for history pages and media.
client -> server send { conv_id, client_msg_id, body } -- client_msg_id: UUID, makes retries safe ack { conv_id, seq } -- "delivered up to seq" on this device read { conv_id, seq } -- "read up to seq" sync { cursors: { conv_id: last_seq, ... } } -- or one per-user cursor, see below ping {} -- heartbeat, every ~30 sserver -> client sent { client_msg_id, conv_id, seq, ts } -- stored; here is its seq message { conv_id, seq, sender, body, ts } receipt { conv_id, user, delivered_upto, read_upto } presence { user, status, last_seen }
Message key (conv_id, bucket) cluster seq desc { seq, sender, client_msg_id, body, ts }Membership key conv_id { user_id, joined_at, role }Cursor key (user_id, device_id) { conv_id -> delivered_upto, read_upto }Two decisions hide in that sketch:
- Sequence numbers are per conversation, not global and not by timestamp. Client clocks are wrong, server clocks differ by milliseconds, and two messages in the same millisecond still need an order. A counter owned by one process per conversation gives a total order inside the conversation and nothing more, which is all chat needs.
- Receipts are watermarks, not per-message flags. “Bob has read up to 1042” is one number per member per conversation. It covers every message at or below 1042, so a read receipt costs O(1) no matter how many messages it covers.
High-level design
Section titled “High-level design”Step through the flows. Watch the order in the send flow: persist, ack the sender, then deliver.
| Component | Role | Why it’s there |
|---|---|---|
| Gateways (×N) | Terminate WebSockets (TLS, auth, heartbeats). Forward frames; hold no message state. | Millions of idle sockets on cheap boxes; a crash just causes reconnects. |
| Session registry | user → [(device, gateway)], written on connect, expired by TTL. |
Routing: which gateway holds Bob’s sockets right now. |
| Chat service | Owns conversations (by consistent hashing on conv_id): assigns seq, persists, dedupes, routes. | One owner per conversation = one sequencer, no distributed lock. |
| Message store | Wide-column (Cassandra, ScyllaDB, HBase), partitioned by conversation and time bucket. | Append-heavy, range reads by (conv, seq), linear scale-out. |
| Presence | Online status from heartbeats with a TTL. | Cheap, approximate, eventually consistent on purpose. |
| Push service | Apple Push Notification service, Firebase Cloud Messaging. | Wakes offline phones. Best effort; never the source of truth. |
Deep dive: ordering, gaps and duplicates
Section titled “Deep dive: ordering, gaps and duplicates”The network between server and device reorders and drops. Choose how the client displays messages, then raise jitter and loss and run the clock.
What the simulator shows:
- Arrival order is wrong order. With any jitter, replies land above the message they answer, and a lost message is invisible: the client cannot tell anything is missing.
- A sequence number turns “missing” into a fact. The client keeps a watermark (everything up to N is here) and a small buffer for early arrivals. A gap is “I have N, I’ve seen N + 3”. A heartbeat that carries the head seq catches a lost last message too.
- Repair is a range read, not a retransmit protocol: ask the store for
seq N+1 … N+2of this conversation. Duplicates from the race between a late original and the repair are dropped by seq.
The other half of exactly-once-on-screen is on the send side. The sender may resend after a timeout, a dropped socket or an app restart, so the server must recognise a retry:
on send(conv, sender, client_msg_id, body): if dedupe.get(conv, client_msg_id) is seq: -- retry of something already stored return sent(client_msg_id, seq) -- same answer as the first time seq <- conv.next_seq; conv.next_seq <- seq + 1 -- single owner: no lock, no race store.write((conv, bucket(seq)), seq, msg) -- durable (quorum) before anything else dedupe.put(conv, client_msg_id -> seq, ttl = 1 day) reply sent(client_msg_id, seq) to sender for (device, gateway) in registry.devices(members(conv) - sender), grouped by gateway: send to gateway: message(conv, seq, ...) for its local devices for member with no live device: push_notify(member) -- best effortThe single owner matters. If two chat-service nodes both accept writes for one conversation (during a failover, say), they can hand out the same seq. Ownership needs a lease or fencing token, or the seq can come from a conditional write in the store (insert seq only if it doesn’t exist). See distributed thinking for leases and fencing.
Deep dive: offline delivery, sync and multiple devices
Section titled “Deep dive: offline delivery, sync and multiple devices”A phone that was offline for an hour must catch up quickly and exactly. Step through a reconnect, then switch the cursor strategy and set “conversations joined” to 500.
There are two common shapes:
| Cursor per conversation | Cursor per user (inbox log) | |
|---|---|---|
| Client sends | {conv: last_seq} for every conversation |
One number |
| Server work to find changes | O(conversations joined) head lookups | One range read of the user’s log |
| Extra write cost | None | One inbox entry per message per member |
| Good for | Few conversations, small groups | Many conversations; mobile clients that want one cheap “what’s new?” |
Multi-device is mostly bookkeeping on top of that:
- Each device has its own cursor. Phone and laptop are separate sessions in the registry and separate rows in the cursor table. A message is “delivered” to a user when at least one device acks it; the sender sees ✓✓ then.
- Your own messages sync too. A message Alice sends from her phone must appear on her laptop: the sender’s other devices are recipients like everyone else.
- Read state is shared. “Read up to 1042” set on the phone is pushed to the laptop so its badge clears. It’s a watermark, so applying it twice is harmless.
- Out-of-date devices page backwards. A device returning after months doesn’t fetch everything; it fetches the newest page per conversation and loads older history on scroll.
Presence (“online”, “last seen 5 min ago”) is deliberately weak. Each gateway refreshes presence:{user} with a 30-60 s TTL on heartbeat. Subscribers (people with that chat open) get changes pushed, batched and rate limited. A user who drops off shows as online until the TTL runs out, which everyone accepts. Fanning out every presence flip to every contact is one of the biggest load sources in chat, so large systems only push presence for conversations currently on screen.
Deep dive: storage, groups and scale
Section titled “Deep dive: storage, groups and scale”Storage. Messages are written once, read mostly as “the latest page of this conversation” or “everything after seq N”, and almost never updated. That is the profile of a wide-column store. Discord’s well-known schema partitions by (channel_id, bucket), where the bucket is a fixed time window, and clusters by message id inside the partition, so a hot or ancient channel never becomes one unbounded partition. Discord later moved this data from Cassandra to ScyllaDB and added a request-coalescing layer for hot channels.
Group fan-out. Store once, deliver many. For a 50-member group, the chat service looks up online members and sends one frame per gateway, not per member. For very large groups, delivery goes through a queue and workers, member lists are paged, and per-member read receipts are replaced by counts or dropped.
Gateways at scale. A WebSocket is a long-lived TCP connection, so a gateway’s limits are memory per connection, file descriptors and TLS handshakes, not CPU. Well-tuned servers hold hundreds of thousands to millions of mostly idle connections. Deploys are the hard part: draining a gateway means telling its clients to reconnect elsewhere gradually, with jitter, not all at once.
Multiple regions. Each conversation has a home region that owns its sequencer; gateways in every region forward to it. A cross-region 1:1 chat pays one inter-region hop for ordering. Slack’s architecture is similar in spirit: gateway servers in many regions, channel servers that own channels by consistent hashing.
Failure modes
Section titled “Failure modes”| What breaks | What you see | Design response |
|---|---|---|
| Gateway crash | Thousands of sockets drop at once | Stateless gateways; clients reconnect with jittered backoff; resend unacked sends with the same client_msg_id |
| Chat-service owner fails over | Brief send errors for its conversations | Lease-based ownership with fencing; next_seq recovered from the store’s max seq |
| Message lost between server and device | A gap on the client | Seq watermark + heartbeat head seq; client range-fetches the gap |
| Sender retries after timeout | Duplicate message risk | Dedupe on (conv, client_msg_id) for a day |
| Store slow | Sends slow (persist before ack) | Quorum writes to nearest replicas; shed load on sends before reads |
| Push notifications dropped | Offline user isn’t woken | Push is a hint only; sync on next open catches everything |
| Reconnect storm after a deploy or outage | Gateways and sync service overloaded | Gradual drains, jitter, sync rate limits, paginate sync newest-first |
| Hot group (everyone posts at once) | One conversation owner saturated | Per-conversation rate limits; batch deliveries per gateway |
What it costs
Section titled “What it costs”| Operation | Time | Space |
|---|---|---|
| Send (sequence + persist + ack) | O(1); one quorum write ≈ 5-10 ms | ≈200 B per message, ×3 replicas |
| Deliver | O(online recipient devices), grouped by gateway | — |
| Receipt (delivered / read) | O(1): one watermark write | O(members) watermarks per conversation |
| Sync after offline | O(missed / page) range reads; + O(conversations) compares with per-conversation cursors | — |
| Gap repair | One range read | Client buffer O(gap) |
| Storage | — | 20B msgs/day × 200 B ≈ 4 TB/day, ≈4.4 PB/year with 3 replicas |
| Connections | — | Tens of KB per idle socket ⇒ 100M sockets ≈ a few TB of RAM across the fleet |
In the interview
Section titled “In the interview”A good 45-minute arc:
- Clarify (5 min). 1:1 and groups, max group size, receipts, multi-device, offline, history retention, E2E encryption.
- Estimate (5 min). Messages/s, storage/day, concurrent sockets and gateway count.
- Connections (5 min). WebSockets over gateways; why not polling (latency, wasted requests); the session registry.
- Send path (10 min). Per-conversation sequencer, persist-then-ack, client_msg_id dedupe, delivery via registry, push for offline.
- Ordering and sync (10 min). Watermarks, gaps, heartbeat head seq, reconnect sync with cursors, multi-device cursors and read state.
- Scale and failure (5-10 min). Wide-column schema with buckets, group fan-out, gateway crashes and reconnect storms, multi-region home for conversations.
Follow-ups to expect: “Why not order by timestamp?” Clocks differ across devices and servers, and two messages can share a millisecond; a per-conversation counter has neither problem. “End-to-end encryption?” The server routes and stores ciphertext it can’t read; sequencing, receipts and sync work unchanged because they only touch metadata. “Message edits and deletes?” Append an edit or tombstone event with its own seq that refers to the original; clients apply it on sync.
Check yourself
Section titled “Check yourself”Go deeper
Section titled “Go deeper”- Discord: How Discord stores billions of messages: the
(channel_id, bucket)partition key, Snowflake message ids, and why they chose Cassandra. - Discord: How Discord stores trillions of messages: the move to ScyllaDB and request coalescing for hot channels.
- Slack Engineering: Real-time messaging: gateway, channel and presence servers, and consistent hashing of channels.
- RFC 6455: The WebSocket Protocol: the handshake, framing, and ping/pong frames used for heartbeats.
Concept pages to drill: Event-driven systems · Idempotency · Concurrency · Distributed thinking · Load balancing · Streaming