Design a chat system
Design a chat app like WhatsApp. Start with one server and one database, let the numbers add gateways, a session registry, one owner per conversation, storage by conversation and offline sync, then stress it with lost acks, big groups, 200 million sockets, online status and encryption, with interview prompts and code.
“Design a chat app like WhatsApp or Messenger. One-to-one and group chats.”
A chat app looks like a table of messages with a send button. The hard part is what the table can’t do. It can’t keep a connection open to hundreds of millions of phones. It can’t find the one server holding the recipient, or notice that the phone is asleep. And it can’t show each conversation in the same order on every device, while the network drops, repeats and reorders what it carries.
So this page starts with one server and one database, and lets the numbers break it. Each step adds what the break needs. Then it tests the finished design against lost acks, millions of open connections, online status and encryption.
The answer in one minute
Section titled “The answer in one minute”If you only have a minute, this is the design. The rest of the page explains each part.
- Each phone keeps one WebSocket to a gateway. Gateways only hold connections. A session registry records which gateway holds each device, so any server can find any device.
- One owner per conversation sets the order. It gives each message the next sequence number: 1, 2, 3. Every device sorts by that number, never by clocks. A missing number shows a gap to fetch.
- The sender’s “sent” tick means the message is safely stored. It’s on 2 of 3 copies. After that, every failure is a delay that a retry or sync repairs, never a loss.
- Push is the doorbell; sync is the delivery. A sleeping phone gets a notification. When it wakes, it asks “what changed since my last position?” and fetches the gaps.
- Cheap features get rationed. Groups are capped at 1,024, receipts are “read up to here”, and online status is only sent to people looking at that contact.
Scope it
Section titled “Scope it”A few questions decide how much we store, and how messages travel.
Design a chat app like WhatsApp or Messenger. One-to-one and group chats.
Whether you ask about scale, group size, history and multiple devices, and name the three ticks.
These four questions matter most:
- How many users? 500 million a day, sending 40 messages each.
- How big can a group be? 1,024 members. Unlimited audiences, like channels, are a different product.
- Does the server keep history? Yes, so a new phone or the web app can load old messages. Classic WhatsApp kept messages only until delivered, which shrinks storage from petabytes to days.
- Several devices per user? Yes: a phone plus up to 4 linked devices. Each needs its own position in each chat.
We also want delivered and read ticks, in groups too, and “online” or “last seen”.
From these answers we make four promises:
- Fast. A message reaches an online friend in the same region in under 500 ms. The “sent” tick appears in under 200 ms.
- One order. Every device shows a conversation in the same order. Different conversations have no order between them.
- No loss, no duplicates. Once the sender sees “sent”, the message is never lost. A retry never shows a message twice.
- Always up. Sending and receiving work 99.99% of the time. Online status and ticks may lag first.
We leave out voice and video calls, stories, and the media upload pipeline.
Go deeperMore questions, and what each changes1 min
| Question | We assume | If the answer were different |
|---|---|---|
| End-to-end encryption? | Not in v1 | The server can’t read messages, so search and history move to devices |
| Message search? | On the device | Server search needs an index fed from the message log |
| Delivered and read ticks? | Yes, in groups too | No ticks removes about half of the small events the system carries |
| Ten times fewer users? | No | One region and fewer gateways; the design is the same |
The numbers that decide it
Section titled “The numbers that decide it”Now we work out the numbers. In chat, two numbers matter more than requests a second: open connections and stored history.
- Daily active users
- 500 million
- Messages sent per user a day
- 40
- Peak over average
- 3×
- Devices each message reaches
- 4
- Share of DAU connected at peak
- 40%
- Memory per idle connection
- 20 KB
- Connections planned per gateway
- 300,000
- Bytes per stored message
- 150 bytes
- Days in the hot store
- 90
- Years of history to keep
- 5 years
500 million users × 40 messages = 20 billion a day ÷ 86,400 s ≈ 230,000 a second. Evenings push that to about three times: 700,000 a second.
So we the store must take hundreds of thousands of writes a second, which rules out one relational database.
Counting group members, their devices and the sender’s own other devices, each message reaches about 4 devices: 2.8 million deliveries a second at peak.
So we scale delivery by deliveries, not by sends.
At peak about 40% of daily users are connected: 200 million open connections.
So we we need servers whose only job is holding sockets, and a way to find a user on them.
Mobile networks drop idle connections after a minute or so, so each phone pings about once a minute: 200 million ÷ 60 ≈ 3.3 million a second, more than the sends.
So we gateways answer pings themselves; pings never touch a database.
A message with its details is about 150 bytes: 20 billion × 150 B = 3 TB a day, 5.5 PB over 5 years before copies.
So we keep 90 days in a fast store (810 TB with 3 copies), and move older history to cheap object storage.
Memory is not the problem. An idle connection takes about 20 KB, so 200 million is 4 TB across the fleet, and one 64 GB server could hold 3 million by memory alone. Deep dive 3 shows what really limits a gateway.
- Messages sent, average
- 230,000/s
- Messages sent, peak
- 690,000/s
- Past the 10,000 writes/s of one relational primary: a store partitioned by conversation.
- Device deliveries, peak
- 2,800,000/s
- Fan-out workers and registry lookups scale with this number, not with sends.
- Open connections, peak
- 200 million
- Every one is a socket some gateway holds all day.
- Gateways
- 670
- A gateway tier that only holds sockets, and a registry to find a user on it.
- Gateway memory, whole fleet
- 4 TB
- Spread over the gateways this is a few GB each: memory is not what limits a gateway.
- Heartbeats, one a minute
- 3,300,000/s
- More than the send rate: heartbeats must end at the gateway and never touch the registry or the store.
- New message data a day
- 3 TB
- Hot store, 3 replicas
- 810 TB
- Hundreds of TB: at about 4 TB a node, disk alone needs a cluster of a hundred nodes or more.
- Full history over the plan
- 5.5 PB
- Petabytes: keep only a hot window in the wide-column store and move older history to object storage.
- Delivery bandwidth, peak
- 830 MB/s
- About 300 bytes a frame with TLS overhead. Not a design driver.
Build the design
Section titled “Build the design”We start with the simplest design that works. Then we let the numbers break it, one at a time. Each step fixes only what broke, adds only the boxes that fix needs, and says what the fix costs.
Step 1. One server, one database
Section titled “Step 1. One server, one database”The simplest chat app is one server and one database. Every phone keeps a connection open to the server. When Alice sends “on my way”, the server saves it and pushes it down Bob’s connection.
Stage 1: One server, one database
Stage 1 of 6
One server, one database
Why this stage
Nothing yet.
This is the smallest design that sends and stores a message.
What we add
A chat server that holds every WebSocket and a map from user to open connection, and a Postgres table of messages.
What it costs
One box holds about 500,000 connections and the peak needs 200 million.
The user map only works while there is one server.
At 700k messages sent per second, Gateways is 39900% busy. Stage 2 is the fix.
The numbers behind the busy bars
How busy it gets
- There are about 285 open connections for every message a second. At the 700k a second peak, that is 200 million connections.
- Each message reaches about 4 devices, and 30% of them are offline.
What one machine can do
- One gateway holds about 500,000 mostly idle WebSockets, about 20 KB each. We plan it at 60%.
- A message service instance handles about 20,000 operations a second.
- One Postgres primary takes about 10,000 writes a second.
How big the shared systems are
- The registry is a 40-node Redis cluster, about 100,000 operations a second per node.
- A Cassandra node takes about 30,000 replica operations a second. Every message is a conditional insert, a Paxos round that costs about 9 replica operations.
- The Kafka cluster takes about 2 million messages a second.
One socket per device
Section titled “One socket per device”The server must push to the phone many times a minute, with little overhead. A WebSocket does that: one long-lived, two-way connection on port 443, with just 2 to 14 bytes of framing per message. Messages travel as small binary frames:
→ { "type": "send", "conv": "c_81f", "clientMsgId": "01J9Z4K7Q2", "body": "on my way" }← { "type": "ack", "clientMsgId": "01J9Z4K7Q2", "seq": 4182 }← { "type": "msg", "conv": "c_81f", "seq": 4182, "from": "u_42", "body": "on my way" }→ { "type": "read", "conv": "c_81f", "upTo": 4182 }→ { "type": "sync" }The phone creates clientMsgId before the first attempt. If the ack is lost and the phone resends
with the same ID, it gets the original sequence number back, not a second copy. Receipts say “read
up to 4182”, which covers every earlier message too.
The numbers break this design at once. 200 million phones hold connections, and no single server can keep that many open. With many servers, Alice and Bob are usually connected to different ones. So the next question is how one server finds the server that holds Bob.
Step 2. Gateways and a session registry
Section titled “Step 2. Gateways and a session registry”We split the server in two. Gateways hold sockets and nothing else: check the login, answer pings, pass frames along. A message service behind them does the real work, and can deploy many times a day without dropping a single connection.
To deliver to Bob, the message service must know which of about 670 gateways holds each of his devices. Gateways write “device → gateway” into a session registry, a Redis cluster split by user, and senders look it up. That’s 200 million entries, only 20 GB.
Stage 2: Gateways and a session registry
Stage 2 of 6
Gateways and a session registry
Why this stage
200 million open connections at peak, and one box should hold about 300,000.
Once users sit on different boxes, something has to say which box holds whom.
What we add
An L4 load balancer, a gateway tier that only holds sockets, a stateless message service, and a session registry in Redis from device to gateway.
What it costs
Every delivery is a registry lookup and one more hop, and the registry can be a few seconds stale.
At 700k messages sent per second, Cassandra is 7000% busy. Stage 3 is the fix.
The numbers behind the busy bars
How busy it gets
- There are about 285 open connections for every message a second. At the 700k a second peak, that is 200 million connections.
- Each message reaches about 4 devices, and 30% of them are offline.
What one machine can do
- One gateway holds about 500,000 mostly idle WebSockets, about 20 KB each. We plan it at 60%.
- A message service instance handles about 20,000 operations a second.
- One Postgres primary takes about 10,000 writes a second.
How big the shared systems are
- The registry is a 40-node Redis cluster, about 100,000 operations a second per node.
- A Cassandra node takes about 30,000 replica operations a second. Every message is a conditional insert, a Paxos round that costs about 9 replica operations.
- The Kafka cluster takes about 2 million messages a second.
A wrong entry is never a correctness problem. If a gateway says “Bob isn’t here”, the device is treated as offline. The message is already stored, so push and sync deliver it.
Go deeperOther ways to find a device, and keeping the registry honest2 min
| Approach | How it works | Problem |
|---|---|---|
| Broadcast | Every message to every gateway | 2.8 million deliveries × 670 gateways |
| Hash the user to a gateway | Route Bob to gateway hash(Bob) mod N |
A plain load balancer can’t see the user; adding a gateway moves users |
| A pub/sub channel per user | Bob’s gateway subscribes to user:Bob |
200 million live subscriptions in the broker |
| Session registry | Gateways write where each device is | One more store; entries can be wrong for a moment |
Two details keep the registry honest. Each entry carries a connection number that rises with every reconnect. Writes only succeed for a newer number, so a slow disconnect from an old gateway can’t delete the entry a new gateway just wrote. And entries don’t expire one by one, which would mean 3.3 million refreshes a second. Instead each gateway holds one timed claim, and lookups ignore entries pointing at a gateway whose claim lapsed.
Step 3. One owner per conversation
Section titled “Step 3. One owner per conversation”Two people in a group send at the same moment. Who decides the order?
Not the phones’ clocks. Phones can be hours wrong, and two people can send in the same millisecond. Not server clocks either: servers differ by milliseconds, so close messages can flip. Instead, every conversation has one owner. Conversation IDs map onto partitions, and each message service instance holds a lease, a renewable claim, on a share of them.
The owner does three things for each send. It checks the client message ID against the last 1,000 it saw. It gives the message the next sequence number. And it writes the row only if that number is still free. Only after the write lands on 2 of 3 copies does it send the ack.
Sequence numbers have no gaps, so a device can spot a missing message: getting 4,183 after 4,181 means 4,182 is missing and should be fetched.
Go deeperHow busy is one owner?1 min
Owners sound like a bottleneck, so it is worth a quick count. 700,000 sends a second are spread across hundreds of millions of conversations, which map onto a few thousand partitions. If, say, 300 message service instances share those partitions, each one handles about 2,300 sends a second.
The work per send is small: a check in memory, adding one to a counter, and one write that waits for 2 of 3 copies, about 5 ms. Sends to different conversations don’t wait for each other, so an instance has hundreds in flight at once.
One very busy conversation can’t overload its owner either. Groups are capped at 1,024 members, and each device may send about 20 messages a second. When an instance dies, its leases expire in about 10 seconds, and other instances take over its partitions.
Step 4. Storage by conversation
Section titled “Step 4. Storage by conversation”Every busy query names one conversation: “append here”, “messages after number N”, “the newest 50”. None needs a transaction across conversations. That is exactly the shape of a wide-column store like
Cassandra. Each partition holds one conversation’s block of 10,000 sequence numbers, sorted by number.
CREATE TABLE messages ( conversation_id uuid, bucket int, -- seq / 10000: keeps a partition near 1.5 MB seq bigint, -- 1, 2, 3...; inserted only if absent sender_id bigint, client_msg_id text, -- the sender's retry key body blob, sent_at timestamp, -- for display only PRIMARY KEY ((conversation_id, bucket), seq)) WITH CLUSTERING ORDER BY (seq DESC);Stage 3: Ordered, partitioned storage
Stage 3 of 6
Ordered, partitioned storage
Why this stage
At 700,000 messages/s one Postgres primary is 70 times over its write capacity, and history grows by 3 TB a day.
What we add
Cassandra partitioned by conversation and time bucket, clustered by sequence number.
Each conversation has one owner in the message service that assigns sequence numbers.
Media and old history go to object storage.
What it costs
No transactions across conversations, ownership leases to run, and any query not by conversation (search) needs its own index.
At 700k messages sent per second, every part has headroom. Raise the traffic until something turns red.
The numbers behind the busy bars
How busy it gets
- There are about 285 open connections for every message a second. At the 700k a second peak, that is 200 million connections.
- Each message reaches about 4 devices, and 30% of them are offline.
What one machine can do
- One gateway holds about 500,000 mostly idle WebSockets, about 20 KB each. We plan it at 60%.
- A message service instance handles about 20,000 operations a second.
- One Postgres primary takes about 10,000 writes a second.
How big the shared systems are
- The registry is a 40-node Redis cluster, about 100,000 operations a second per node.
- A Cassandra node takes about 30,000 replica operations a second. Every message is a conditional insert, a Paxos round that costs about 9 replica operations.
- The Kafka cluster takes about 2 million messages a second.
Go deeperWhy buckets by number, and other stores that fit2 min
Buckets go by sequence number, not by time. A quiet chat with time buckets can leave its newest
messages several empty buckets back. With dense numbers, seq / 10000 names the right partition
directly. After 90 days, a job rewrites each full bucket as one compressed file in object storage.
| Store | Fits because | Costs | Pick when |
|---|---|---|---|
| Cassandra or ScyllaDB | Partition plus sort key is exactly “chat, by number” | Deletes leave markers that slow reads | The default here (Discord uses ScyllaDB) |
| DynamoDB | The same layout, fully managed | Cost at 700,000 writes a second | You’re on AWS and want no operations |
| Sharded MySQL | Familiar, transactions inside a shard | Resharding by hand | Much smaller scale |
Each device also has two small tables: its cursor per chat (delivered and read numbers), and its “news in this chat” markers while offline. A marker per offline device is far cheaper than copying each group message into 1,024 inboxes, and later messages to the same chat just overwrite it.
Membership changes are messages too. “Ana was removed” gets a sequence number like any message, so every device and the fan-out agree on who was a member at each point.
Step 5. Phones that are asleep
Section titled “Step 5. Phones that are asleep”iOS and Android suspend background apps within seconds. So most recipients aren’t connected at all. Two mechanisms cover them, and only one is a promise:
- Push is the doorbell. For each device without a connection, the message service writes a small “you have news in this chat” marker, and asks the push service to notify it through Apple or Google. Notifications can be throttled or lost, so they’re never the only copy.
- Sync is the delivery. When the phone reconnects, it asks “what changed?”. The server compares each chat’s newest number with the device’s own cursor, the last number it confirmed, and sends the gaps a page at a time. The device confirms, which moves its cursor and sends the “delivered” tick.
Stage 4: Offline devices and sync
Stage 4 of 6
Offline devices and sync
Why this stage
A requirement, not load: phones are offline most of the day, and the OS kills background sockets within seconds.
What we add
A push service that wakes offline devices through APNs and FCM, a delivered cursor per device and conversation, and a sync call on reconnect.
What it costs
Push is best effort and owned by Apple and Google.
Payloads are capped at 4 KB, and delivery is not guaranteed.
At 700k messages sent per second, every part has headroom. Raise the traffic until something turns red.
The numbers behind the busy bars
How busy it gets
- There are about 285 open connections for every message a second. At the 700k a second peak, that is 200 million connections.
- Each message reaches about 4 devices, and 30% of them are offline.
What one machine can do
- One gateway holds about 500,000 mostly idle WebSockets, about 20 KB each. We plan it at 60%.
- A message service instance handles about 20,000 operations a second.
- One Postgres primary takes about 10,000 writes a second.
How big the shared systems are
- The registry is a 40-node Redis cluster, about 100,000 operations a second per node.
- A Cassandra node takes about 30,000 replica operations a second. Every message is a conditional insert, a Paxos round that costs about 9 replica operations.
- The Kafka cluster takes about 2 million messages a second.
Follow a send to an online friend, then a phone reconnecting:
Trace a request: Send to an online friend
Send to an online friend: step 1 of 6
Devices to Load balancer
The phone already has an open WebSocket, so a send is one frame on it: no DNS, no TLS handshake. It carries a client message ID the phone generated, about 60 ms over a mobile network.
- Devices → Load balancer60 ms
- Load balancer → Gateways1 ms
- Gateways → Message service2 ms
- Message service → Cassandra10 ms
- Message service → Session registry1 ms
- Response
A send is mostly mobile network, about 60 ms each way, and only about 14 ms inside our servers. The whole life of a message, with its three ticks:
- Color key
- Service
This is enough for a mid-level answer. Gateways and a registry, sequence numbers from one owner, storage by conversation, and push plus sync. The stress tests are what make it a senior answer.
Go deeperWhy WebSocket, and what else the API needs1 min
| Transport | Wins | Loses |
|---|---|---|
| Long polling | Works through anything that speaks HTTP | Hundreds of bytes of headers per batch, gaps |
| Server-sent events | Plain HTTP, built-in reconnect | One direction only; a full request per send |
| WebSocket | Tiny framing, both directions, port 443 | Stateful servers; we build heartbeats and resume |
| MQTT | Smallest overhead, built for flaky links | Not native in browsers |
Messenger has used MQTT, and WhatsApp a custom protocol. Either works. What matters is one persistent, two-way connection. Long polling stays as a fallback.
Everything that isn’t real-time goes over plain HTTPS: scrolling back through history, creating a group, and getting an upload link for media. Sends are limited to about 20 a second per device.
Go deeperSyncing after a week offline1 min
A phone that was off for a week may have news in 200 chats and thousands of messages. Sync doesn’t download all of it at once.
First, it fetches the list of chats with news, from the markers, newest first. So the chat list is right in under a second. Then it fetches each chat’s missing messages a page at a time, starting with the chat the user opens. Older pages load in the background.
Photos and videos are not downloaded during sync. A message only holds a link, and the file loads when the message comes into view. A phone that was away longer than 90 days fetches its oldest messages from the compressed files in object storage. That is slower, but nothing is missing.
Stress it
Section titled “Stress it”The design is complete. Now we test it where chat is hard: a lost ack while an owner crashes, a thousand-person group, 200 million open sockets, online status, and ticks with encryption. Groups and online status each add boxes.
A lost ack and a crashed owner
Section titled “A lost ack and a crashed owner”Alice’s phone sends, the ack is lost, and the owner crashes. Walk me through exactly what Alice and Bob see.
Whether a message can be lost or doubled when an ack is lost and the owner fails over at the same time.
The owner keeps the next sequence number and the last 1,000 client message IDs in memory. A new owner rebuilds both with one read of the newest messages. Here is the send path:
// What the owner stores. seq is the conversation's order; clientMsgId is the sender's retry key.// sentAt is for display only. Nothing ever sorts by it.record Message(String conversationId, long seq, long senderDevice, String clientMsgId, String body, long sentAtMillis) {}
// The two store calls the owner needs. Cassandra in production: partition (conversation,// bucket), clustered by seq descending, so "newest N" is one sequential read.interface MessageStore { List<Message> newest(String conversationId, int limit); // only on takeover
// INSERT ... IF NOT EXISTS on (conversation, bucket, seq): a lightweight transaction, so the // replicas themselves refuse a second message for the same seq. Empty when this call took // the slot, otherwise the message already in it. Throws TimeoutException when the outcome // is unknown. Optional<Message> insertIfAbsent(Message m) throws TimeoutException;}
// The store will not answer. The caller gives up the conversation's lease.class OwnerUnhealthyException extends RuntimeException { OwnerUnhealthyException(String conversationId) { super("cannot write " + conversationId); }}
// Someone else wrote this seq: a paused former owner, or the new owner if this instance is the// one that was paused. The caller checks its lease. Still the owner: send again, and the// takeover read picks up the other writer's messages. Not the owner: forward the send.class SupersededException extends RuntimeException { SupersededException(String conversationId, long seq) { super("seq " + seq + " of " + conversationId + " belongs to another writer"); }}
// The writer for one conversation. A lease (etcd or ZooKeeper, left out) makes it the only one// almost always, which keeps the conditional inserts free of contention. Correctness does not// rest on the lease: a GC pause can outlive it, and the store's slot check is what stops two// messages from sharing a seq.final class ConversationOwner { private static final int DEDUPE_WINDOW = 1_000; // retries come within seconds; recent sends are enough private static final int MAX_ATTEMPTS = 5;
private final String conversationId; private final MessageStore store; // One send at a time. A busy group sends a few messages a second and an insert takes about // 10 ms, so this lock caps a conversation near 100 sends a second and never queues for long. private final ReentrantLock lock = new ReentrantLock(); private final LinkedHashMap<String, Message> recent = new LinkedHashMap<>() { @Override protected boolean removeEldestEntry(Map.Entry<String, Message> e) { return size() > DEDUPE_WINDOW; // forget the oldest send } }; private long nextSeq = -1; // unknown until this owner has read the head of the conversation
ConversationOwner(String conversationId, MessageStore store) { this.conversationId = conversationId; this.store = store; }
private static String keyOf(Message m) { return m.senderDevice() + ":" + m.clientMsgId(); }
Message send(long senderDevice, String clientMsgId, String body) { lock.lock(); try { if (nextSeq < 0) takeOver(); String key = senderDevice + ":" + clientMsgId; Message seen = recent.get(key); if (seen != null) return seen; // a retry after a lost ack: the same seq, no second copy
Message m = new Message(conversationId, nextSeq, senderDevice, clientMsgId, body, System.currentTimeMillis()); Optional<Message> holder = insertUntilAnswered(m); if (holder.isPresent() && !keyOf(holder.get()).equals(key)) { // Never overwrite it and never ack: forget what memory says and let the caller // decide who owns the conversation now. nextSeq = -1; throw new SupersededException(conversationId, m.seq()); } Message stored = holder.orElse(m); // our own earlier attempt that timed out but landed nextSeq = stored.seq() + 1; // advance only once the slot is filled: seqs stay dense recent.put(key, stored); return stored; // the caller acks the sender now: one tick means "durable" } finally { lock.unlock(); } }
// One read on takeover gives both the next seq and the dedupe window, so a retry that // reaches the new owner still finds the message the old owner stored. The read may miss a // write still in flight; then the next insert finds that slot taken instead. private void takeOver() { recent.clear(); List<Message> newest = store.newest(conversationId, DEDUPE_WINDOW); nextSeq = newest.isEmpty() ? 1 : newest.get(0).seq() + 1; for (int i = newest.size() - 1; i >= 0; i--) { // oldest first, so eviction order is right recent.put(keyOf(newest.get(i)), newest.get(i)); } }
// A timeout does not say whether the insert landed. Repeating the same insert settles it: // either it takes the slot now, or the slot comes back holding this very message. private Optional<Message> insertUntilAnswered(Message m) { for (int attempt = 1; attempt <= MAX_ATTEMPTS; attempt++) { try { return store.insertIfAbsent(m); } catch (TimeoutException e) { try { Thread.sleep(20L << attempt); // 40 ms to 640 ms of backoff } catch (InterruptedException ie) { Thread.currentThread().interrupt(); break; } } } nextSeq = -1; // never trust memory again; whoever writes next re-reads the head throw new OwnerUnhealthyException(conversationId); }}# What the owner stores. seq is the conversation's order; client_msg_id is the sender's# retry key. sent_at is for display only. Nothing ever sorts by it.@dataclass(frozen=True)class Message: conversation_id: str seq: int sender_device: int client_msg_id: str body: str sent_at: float
# The two store calls the owner needs. Cassandra in production: partition (conversation,# bucket), clustered by seq descending, so "newest N" is one sequential read.class MessageStore(Protocol): def newest(self, conversation_id: str, limit: int) -> list[Message]: ... # only on takeover
# INSERT ... IF NOT EXISTS on (conversation, bucket, seq): a lightweight transaction, # so the replicas themselves refuse a second message for the same seq. None when this # call took the slot, otherwise the message already in it. Raises TimeoutError when the # outcome is unknown. def insert_if_absent(self, m: Message) -> Message | None: ...
# The store will not answer. The caller gives up the conversation's lease.class OwnerUnhealthy(Exception): ...
# Someone else wrote this seq: a paused former owner, or the new owner if this instance is# the one that was paused. The caller checks its lease. Still the owner: send again, and the# takeover read picks up the other writer's messages. Not the owner: forward the send.class Superseded(Exception): ...
# The writer for one conversation. A lease (etcd or ZooKeeper, left out) makes it the only# one almost always, which keeps the conditional inserts free of contention. Correctness does# not rest on the lease: a GC pause can outlive it, and the store's slot check is what stops# two messages from sharing a seq.class ConversationOwner: DEDUPE_WINDOW = 1_000 # retries come within seconds; recent sends are enough MAX_ATTEMPTS = 5
def __init__(self, conversation_id: str, store: MessageStore): self._conversation_id = conversation_id self._store = store # One send at a time. A busy group sends a few messages a second and an insert takes # about 10 ms, so this lock caps a conversation near 100 sends a second. self._lock = threading.Lock() self._recent: OrderedDict[tuple[int, str], Message] = OrderedDict() self._next_seq = -1 # unknown until this owner has read the head of the conversation
def send(self, sender_device: int, client_msg_id: str, body: str) -> Message: with self._lock: if self._next_seq < 0: self._take_over() key = (sender_device, client_msg_id) seen = self._recent.get(key) if seen is not None: return seen # a retry after a lost ack: the same seq, no second copy
m = Message(self._conversation_id, self._next_seq, sender_device, client_msg_id, body, time.time()) holder = self._insert_until_answered(m) if holder is not None and (holder.sender_device, holder.client_msg_id) != key: # Never overwrite it and never ack: forget what memory says and let the caller # decide who owns the conversation now. self._next_seq = -1 raise Superseded(self._conversation_id, m.seq) stored = holder or m # holder is our own earlier attempt that timed out but landed self._next_seq = stored.seq + 1 # advance only once the slot is filled: seqs stay dense self._remember(key, stored) return stored # the caller acks the sender now: one tick means "durable"
def _take_over(self) -> None: # One read on takeover gives both the next seq and the dedupe window, so a retry that # reaches the new owner still finds the message the old owner stored. The read may # miss a write still in flight; then the next insert finds that slot taken instead. self._recent.clear() newest = self._store.newest(self._conversation_id, self.DEDUPE_WINDOW) self._next_seq = newest[0].seq + 1 if newest else 1 for m in reversed(newest): # oldest first, so eviction order is right self._remember((m.sender_device, m.client_msg_id), m)
def _remember(self, key: tuple[int, str], m: Message) -> None: self._recent[key] = m if len(self._recent) > self.DEDUPE_WINDOW: self._recent.popitem(last=False) # forget the oldest send
def _insert_until_answered(self, m: Message) -> Message | None: # A timeout does not say whether the insert landed. Repeating the same insert settles # it: either it takes the slot now, or the slot comes back holding this very message. for attempt in range(1, self.MAX_ATTEMPTS + 1): try: return self._store.insert_if_absent(m) except TimeoutError: time.sleep(0.02 * 2**attempt) # 40 ms to 640 ms of backoff self._next_seq = -1 # never trust memory again; whoever writes next re-reads the head raise OwnerUnhealthy(self._conversation_id)// What the owner stores. Seq is the conversation's order; ClientMsgId is the sender's retry key.// SentAt is for display only. Nothing ever sorts by it.record Message(string ConversationId, long Seq, long SenderDevice, string ClientMsgId, string Body, DateTimeOffset SentAt);
// The two store calls the owner needs. Cassandra in production: partition (conversation,// bucket), clustered by seq descending, so "newest N" is one sequential read.interface IMessageStore{ IReadOnlyList<Message> Newest(string conversationId, int limit); // only on takeover
// INSERT ... IF NOT EXISTS on (conversation, bucket, seq): a lightweight transaction, so the // replicas themselves refuse a second message for the same seq. Returns null when this call // took the slot, or the message already in it. Throws TimeoutException when the outcome is // unknown. Message? InsertIfAbsent(Message m);}
// The store will not answer. The caller gives up the conversation's lease.class OwnerUnhealthyException(string conversationId) : Exception($"cannot write {conversationId}");
// Someone else wrote this seq: a paused former owner, or the new owner if this instance is the// one that was paused. The caller checks its lease. Still the owner: send again, and the// takeover read picks up the other writer's messages. Not the owner: forward the send.class SupersededException(string conversationId, long seq) : Exception($"seq {seq} of {conversationId} belongs to another writer");
// The writer for one conversation. A lease (etcd or ZooKeeper, left out) makes it the only one// almost always, which keeps the conditional inserts free of contention. Correctness does not// rest on the lease: a GC pause can outlive it, and the store's slot check is what stops two// messages from sharing a seq.sealed class ConversationOwner(string conversationId, IMessageStore store){ const int DedupeWindow = 1_000; // retries come within seconds; recent sends are enough const int MaxAttempts = 5;
// One send at a time. A busy group sends a few messages a second and an insert takes about // 10 ms, so this lock caps a conversation near 100 sends a second and never queues for long. private readonly Lock _gate = new(); private readonly Dictionary<(long, string), Message> _recent = new(); private readonly Queue<(long, string)> _order = new(); // eviction order for _recent private long _nextSeq = -1; // unknown until this owner has read the head of the conversation
public Message Send(long senderDevice, string clientMsgId, string body) { lock (_gate) { if (_nextSeq < 0) TakeOver(); var key = (senderDevice, clientMsgId); if (_recent.TryGetValue(key, out var seen)) return seen; // a retry after a lost ack: the same seq, no second copy
var m = new Message(conversationId, _nextSeq, senderDevice, clientMsgId, body, DateTimeOffset.UtcNow); var holder = InsertUntilAnswered(m); if (holder is not null && (holder.SenderDevice, holder.ClientMsgId) != key) { // Never overwrite it and never ack: forget what memory says and let the caller // decide who owns the conversation now. _nextSeq = -1; throw new SupersededException(conversationId, m.Seq); } var stored = holder ?? m; // holder is our own earlier attempt that timed out but landed _nextSeq = stored.Seq + 1; // advance only once the slot is filled, so seqs stay dense Remember(key, stored); return stored; // the caller acks the sender now: one tick means "durable" } }
// One read on takeover gives both the next seq and the dedupe window, so a retry that // reaches the new owner still finds the message the old owner stored. The read may miss a // write still in flight; then the next insert finds that slot taken instead. private void TakeOver() { _recent.Clear(); _order.Clear(); var newest = store.Newest(conversationId, DedupeWindow); _nextSeq = newest.Count == 0 ? 1 : newest[0].Seq + 1; for (int i = newest.Count - 1; i >= 0; i--) // oldest first, so eviction order is right Remember((newest[i].SenderDevice, newest[i].ClientMsgId), newest[i]); }
private void Remember((long, string) key, Message m) { if (_recent.TryAdd(key, m)) _order.Enqueue(key); if (_order.Count > DedupeWindow) _recent.Remove(_order.Dequeue()); // forget the oldest send }
// A timeout does not say whether the insert landed. Repeating the same insert settles it: // either it takes the slot now, or the slot comes back holding this very message. private Message? InsertUntilAnswered(Message m) { for (int attempt = 1; attempt <= MaxAttempts; attempt++) { try { return store.InsertIfAbsent(m); } catch (TimeoutException) { Thread.Sleep(20 << attempt); // 40 ms to 640 ms of backoff } } _nextSeq = -1; // never trust memory again; whoever writes next re-reads the head throw new OwnerUnhealthyException(conversationId); }}// Message is what the owner stores. Seq is the conversation's order; ClientMsgID is the// sender's retry key. SentAt is for display only. Nothing ever sorts by it.type Message struct { ConversationID string Seq int64 SenderDevice int64 ClientMsgID string Body string SentAt time.Time}
// MessageStore is the two store calls the owner needs. Cassandra in production: partition// (conversation, bucket), clustered by seq descending, so "newest N" is one sequential read.type MessageStore interface { Newest(conversationID string, limit int) ([]Message, error) // only on takeover
// InsertIfAbsent is INSERT ... IF NOT EXISTS on (conversation, bucket, seq): a lightweight // transaction, so the replicas themselves refuse a second message for the same seq. It // returns nil when this call took the slot, otherwise the message already in it, and // ErrTimeout when the outcome is unknown. InsertIfAbsent(m Message) (*Message, error)}
var ( ErrTimeout = errors.New("store timeout, outcome unknown") // ErrOwnerUnhealthy means the store will not answer. The caller gives up the lease. ErrOwnerUnhealthy = errors.New("owner cannot write; release the lease") // ErrSuperseded means someone else wrote this seq: a paused former owner, or the new owner // if this instance is the one that was paused. The caller checks its lease. Still the // owner: send again, and the takeover read picks up the other writer's messages. Not the // owner: forward the send. ErrSuperseded = errors.New("seq belongs to another writer"))
const ( dedupeWindow = 1000 // retries come within seconds; recent sends are enough maxAttempts = 5)
type sendKey struct { device int64 clientMsgID string}
// ConversationOwner is the writer for one conversation. A lease (etcd or ZooKeeper, left out)// makes it the only one almost always, which keeps the conditional inserts free of contention.// Correctness does not rest on the lease: a GC pause can outlive it, and the store's slot// check is what stops two messages from sharing a seq.type ConversationOwner struct { conversationID string store MessageStore
// One send at a time. A busy group sends a few messages a second and an insert takes // about 10 ms, so this mutex caps a conversation near 100 sends a second. mu sync.Mutex recent map[sendKey]Message order []sendKey // eviction order for recent nextSeq int64 // 0: unknown until this owner has read the head of the conversation}
func NewConversationOwner(id string, store MessageStore) *ConversationOwner { return &ConversationOwner{conversationID: id, store: store}}
func (o *ConversationOwner) Send(senderDevice int64, clientMsgID, body string) (Message, error) { o.mu.Lock() defer o.mu.Unlock() if o.nextSeq == 0 { if err := o.takeOver(); err != nil { return Message{}, err } } key := sendKey{senderDevice, clientMsgID} if seen, ok := o.recent[key]; ok { return seen, nil // a retry after a lost ack: the same seq, no second copy }
m := Message{o.conversationID, o.nextSeq, senderDevice, clientMsgID, body, time.Now()} holder, err := o.insertUntilAnswered(m) if err != nil { return Message{}, err } stored := m if holder != nil { if (sendKey{holder.SenderDevice, holder.ClientMsgID}) != key { // Never overwrite it and never ack: forget what memory says and let the caller // decide who owns the conversation now. o.nextSeq = 0 return Message{}, fmt.Errorf("%w: seq %d of %s", ErrSuperseded, m.Seq, o.conversationID) } stored = *holder // our own earlier attempt that timed out but landed } o.nextSeq = stored.Seq + 1 // advance only once the slot is filled, so seqs stay dense o.remember(key, stored) return stored, nil // the caller acks the sender now: one tick means "durable"}
// takeOver does one read that gives both the next seq and the dedupe window, so a retry that// reaches the new owner still finds the message the old owner stored. The read may miss a// write still in flight; then the next insert finds that slot taken instead.func (o *ConversationOwner) takeOver() error { newest, err := o.store.Newest(o.conversationID, dedupeWindow) if err != nil { return err } o.recent, o.order = map[sendKey]Message{}, nil o.nextSeq = 1 if len(newest) > 0 { o.nextSeq = newest[0].Seq + 1 } for i := len(newest) - 1; i >= 0; i-- { // oldest first, so eviction order is right o.remember(sendKey{newest[i].SenderDevice, newest[i].ClientMsgID}, newest[i]) } return nil}
func (o *ConversationOwner) remember(key sendKey, m Message) { if _, ok := o.recent[key]; !ok { o.order = append(o.order, key) } o.recent[key] = m if len(o.order) > dedupeWindow { // forget the oldest send delete(o.recent, o.order[0]) o.order = o.order[1:] }}
// insertUntilAnswered repeats the same insert. A timeout does not say whether the insert// landed; repeating it settles that: either it takes the slot now, or the slot comes back// holding this very message.func (o *ConversationOwner) insertUntilAnswered(m Message) (*Message, error) { for attempt := 1; attempt <= maxAttempts; attempt++ { holder, err := o.store.InsertIfAbsent(m) if !errors.Is(err, ErrTimeout) { return holder, err } time.Sleep(time.Duration(20<<attempt) * time.Millisecond) // 40 ms to 640 ms of backoff } o.nextSeq = 0 // never trust memory again; whoever writes next re-reads the head return nil, ErrOwnerUnhealthy}// What the owner stores. seq is the conversation's order; clientMsgId is the sender's retry key.// sentAt is for display only. Nothing ever sorts by it.interface Message { conversationId: string; seq: number; senderDevice: number; clientMsgId: string; body: string; sentAt: number;}
// The two store calls the owner needs. Cassandra in production: partition (conversation,// bucket), clustered by seq descending, so "newest N" is one sequential read.interface MessageStore { newest(conversationId: string, limit: number): Promise<Message[]>; // only on takeover
// INSERT ... IF NOT EXISTS on (conversation, bucket, seq): a lightweight transaction, so the // replicas themselves refuse a second message for the same seq. Resolves to null when this // call took the slot, otherwise to the message already in it. Rejects with StoreTimeoutError // when the outcome is unknown. insertIfAbsent(m: Message): Promise<Message | null>;}
class StoreTimeoutError extends Error {}
// The store will not answer. The caller gives up the conversation's lease.class OwnerUnhealthyError extends Error {}
// Someone else wrote this seq: a paused former owner, or the new owner if this instance is the// one that was paused. The caller checks its lease. Still the owner: send again, and the// takeover read picks up the other writer's messages. Not the owner: forward the send.class SupersededError extends Error {}
const DEDUPE_WINDOW = 1_000; // retries come within seconds; recent sends are enoughconst MAX_ATTEMPTS = 5;const sleep = (ms: number) => new Promise((r) => setTimeout(r, ms));
// The writer for one conversation. A lease (etcd or ZooKeeper, left out) makes it the only one// almost always, which keeps the conditional inserts free of contention. Correctness does not// rest on the lease: a pause can outlive it, and the store's slot check is what stops two// messages from sharing a seq.class ConversationOwner { // A Map keeps insertion order, so its first key is always the oldest send. private readonly recent = new Map<string, Message>(); private nextSeq = -1; // unknown until this owner has read the head of the conversation // One send at a time: each send chains onto the previous one. Node runs one thread, but // awaits interleave, and two sends must never hold the same seq. A busy group sends a few // messages a second and an insert takes about 10 ms, so the chain never grows long. private tail: Promise<unknown> = Promise.resolve();
constructor( private readonly conversationId: string, private readonly store: MessageStore, ) {}
send(senderDevice: number, clientMsgId: string, body: string): Promise<Message> { const run = this.tail.then(() => this.sendNow(senderDevice, clientMsgId, body)); this.tail = run.catch(() => undefined); // one failed send must not block the next return run; }
private async sendNow(senderDevice: number, clientMsgId: string, body: string) { if (this.nextSeq < 0) await this.takeOver(); const key = `${senderDevice}:${clientMsgId}`; const seen = this.recent.get(key); if (seen) return seen; // a retry after a lost ack: the same seq, no second copy
const m: Message = { conversationId: this.conversationId, seq: this.nextSeq, senderDevice, clientMsgId, body, sentAt: Date.now(), }; const holder = await this.insertUntilAnswered(m); if (holder && `${holder.senderDevice}:${holder.clientMsgId}` !== key) { // Never overwrite it and never ack: forget what memory says and let the caller decide // who owns the conversation now. this.nextSeq = -1; throw new SupersededError(`seq ${m.seq} of ${this.conversationId} has another writer`); } const stored = holder ?? m; // holder is our own earlier attempt that timed out but landed this.nextSeq = stored.seq + 1; // advance only once the slot is filled, so seqs stay dense this.remember(key, stored); return stored; // the caller acks the sender now: one tick means "durable" }
// One read on takeover gives both the next seq and the dedupe window, so a retry that // reaches the new owner still finds the message the old owner stored. The read may miss a // write still in flight; then the next insert finds that slot taken instead. private async takeOver() { this.recent.clear(); const newest = await this.store.newest(this.conversationId, DEDUPE_WINDOW); this.nextSeq = newest.length ? newest[0].seq + 1 : 1; for (const m of [...newest].reverse()) this.remember(`${m.senderDevice}:${m.clientMsgId}`, m); }
private remember(key: string, m: Message) { this.recent.set(key, m); if (this.recent.size > DEDUPE_WINDOW) { this.recent.delete(this.recent.keys().next().value!); // forget the oldest send } }
// A timeout does not say whether the insert landed. Repeating the same insert settles it: // either it takes the slot now, or the slot comes back holding this very message. private async insertUntilAnswered(m: Message): Promise<Message | null> { for (let attempt = 1; attempt <= MAX_ATTEMPTS; attempt++) { try { return await this.store.insertIfAbsent(m); } catch (e) { if (!(e instanceof StoreTimeoutError)) throw e; await sleep(20 * 2 ** attempt); // 40 ms to 640 ms of backoff } } this.nextSeq = -1; // never trust memory again; whoever writes next re-reads the head throw new OwnerUnhealthyError(`cannot write ${this.conversationId}`); }}So the story goes like this. Alice sends, the row is stored as number 41, and the owner crashes before the ack reaches her. Ten seconds later the lease expires and another instance takes over. It reads the newest messages, including 41 with Alice’s ID. Alice’s phone retries with the same ID, and gets “41” back. No second copy.
- Color key
- Service
The phone is the other half of the promise. It shows messages only in number order, drops numbers it has already seen, and fetches holes:
record Message(String conversationId, long seq, String body) {}
// The calls a device makes back to the server for one conversation.interface SyncServer { // Ask for a hole. The answers come back through onMessage like any other message. void fetch(String conversationId, long fromSeq, long toSeq); // Moves this device's delivered cursor; the server turns it into the sender's second tick. void ackDelivered(String conversationId, long upToSeq);}
// One conversation on one device. Messages can arrive twice (fan-out is at-least-once), out of// order (a live push racing a sync page), or not at all (a delivery dropped with a gateway).// Contiguous sequence numbers make all three visible, which timestamps never could.final class ConversationReceiver { private final String conversationId; private final SyncServer server; private final Consumer<Message> show; private final TreeMap<Long, Message> early = new TreeMap<>(); // arrived ahead of a hole private long delivered; // highest seq with nothing missing below it; saved on the device private long requestedUpTo; // so a hole is fetched once, not again on every later message
ConversationReceiver(String conversationId, long delivered, SyncServer server, Consumer<Message> show) { this.conversationId = conversationId; this.delivered = delivered; this.requestedUpTo = delivered; this.server = server; this.show = show; }
void onMessage(Message m) { if (m.seq() <= delivered || early.containsKey(m.seq())) return; // a duplicate: drop it early.put(m.seq(), m);
// Release everything that is now contiguous, in order. This is the only place a message // reaches the screen, so every device shows the conversation in the same order. Message next; while ((next = early.remove(delivered + 1)) != null) { show.accept(next); delivered++; }
// Something is still waiting behind a hole: ask for exactly the missing range. // A real client also re-asks after a timeout, in case the fetch itself is lost. if (!early.isEmpty()) { long holeEnd = early.firstKey() - 1; if (holeEnd > requestedUpTo) { server.fetch(conversationId, delivered + 1, holeEnd); requestedUpTo = holeEnd; } }
// One watermark, not one ack per message. Real clients batch these for a few hundred ms. server.ackDelivered(conversationId, delivered); }}@dataclass(frozen=True)class Message: conversation_id: str seq: int body: str
# The calls a device makes back to the server for one conversation.class SyncServer(Protocol): # Ask for a hole. The answers come back through on_message like any other message. def fetch(self, conversation_id: str, from_seq: int, to_seq: int) -> None: ...
# Moves this device's delivered cursor; the server turns it into the sender's second tick. def ack_delivered(self, conversation_id: str, up_to_seq: int) -> None: ...
# One conversation on one device. Messages can arrive twice (fan-out is at-least-once),# out of order (a live push racing a sync page), or not at all (a delivery dropped with a# gateway). Contiguous sequence numbers make all three visible, which timestamps never could.class ConversationReceiver: def __init__(self, conversation_id: str, delivered: int, server: SyncServer, show: Callable[[Message], None]): self._conversation_id = conversation_id self._server = server self._show = show self._early: dict[int, Message] = {} # arrived ahead of a hole self._delivered = delivered # highest seq with nothing missing below it; saved on device self._requested_up_to = delivered # so a hole is fetched once, not on every later message
def on_message(self, m: Message) -> None: if m.seq <= self._delivered or m.seq in self._early: return # a duplicate: drop it self._early[m.seq] = m
# Release everything that is now contiguous, in order. This is the only place a message # reaches the screen, so every device shows the conversation in the same order. while (nxt := self._early.pop(self._delivered + 1, None)) is not None: self._show(nxt) self._delivered += 1
# Something is still waiting behind a hole: ask for exactly the missing range. # A real client also re-asks after a timeout, in case the fetch itself is lost. if self._early: hole_end = min(self._early) - 1 if hole_end > self._requested_up_to: self._server.fetch(self._conversation_id, self._delivered + 1, hole_end) self._requested_up_to = hole_end
# One watermark, not one ack per message. Real clients batch these for a few hundred ms. self._server.ack_delivered(self._conversation_id, self._delivered)record Message(string ConversationId, long Seq, string Body);
// The calls a device makes back to the server for one conversation.interface ISyncServer{ // Ask for a hole. The answers come back through OnMessage like any other message. void Fetch(string conversationId, long fromSeq, long toSeq); // Moves this device's delivered cursor; the server turns it into the sender's second tick. void AckDelivered(string conversationId, long upToSeq);}
// One conversation on one device. Messages can arrive twice (fan-out is at-least-once), out of// order (a live push racing a sync page), or not at all (a delivery dropped with a gateway).// Contiguous sequence numbers make all three visible, which timestamps never could.sealed class ConversationReceiver(string conversationId, long delivered, ISyncServer server, Action<Message> show){ private readonly SortedDictionary<long, Message> _early = new(); // arrived ahead of a hole private long _delivered = delivered; // highest seq with nothing missing below it; saved on the device private long _requestedUpTo = delivered; // so a hole is fetched once, not again on every later message
public void OnMessage(Message m) { if (m.Seq <= _delivered || !_early.TryAdd(m.Seq, m)) return; // a duplicate: drop it
// Release everything that is now contiguous, in order. This is the only place a message // reaches the screen, so every device shows the conversation in the same order. while (_early.Remove(_delivered + 1, out var next)) { show(next); _delivered++; }
// Something is still waiting behind a hole: ask for exactly the missing range. // A real client also re-asks after a timeout, in case the fetch itself is lost. if (_early.Count > 0) { long holeEnd = _early.Keys.First() - 1; if (holeEnd > _requestedUpTo) { server.Fetch(conversationId, _delivered + 1, holeEnd); _requestedUpTo = holeEnd; } }
// One watermark, not one ack per message. Real clients batch these for a few hundred ms. server.AckDelivered(conversationId, _delivered); }}type Message struct { ConversationID string Seq int64 Body string}
// SyncServer is the calls a device makes back to the server for one conversation.type SyncServer interface { // Fetch asks for a hole. The answers come back through OnMessage like any other message. Fetch(conversationID string, fromSeq, toSeq int64) // AckDelivered moves this device's delivered cursor; the server turns it into the // sender's second tick. AckDelivered(conversationID string, upToSeq int64)}
// ConversationReceiver is one conversation on one device. Messages can arrive twice (fan-out// is at-least-once), out of order (a live push racing a sync page), or not at all (a delivery// dropped with a gateway). Contiguous sequence numbers make all three visible, which// timestamps never could. Not safe for concurrent use: the app feeds it from one goroutine.type ConversationReceiver struct { conversationID string server SyncServer show func(Message) early map[int64]Message // arrived ahead of a hole delivered int64 // highest seq with nothing missing below it; saved on the device requestedUpTo int64 // so a hole is fetched once, not again on every later message}
func NewConversationReceiver(id string, delivered int64, server SyncServer, show func(Message)) *ConversationReceiver { return &ConversationReceiver{id, server, show, map[int64]Message{}, delivered, delivered}}
func (r *ConversationReceiver) OnMessage(m Message) { if _, dup := r.early[m.Seq]; dup || m.Seq <= r.delivered { return // a duplicate: drop it } r.early[m.Seq] = m
// Release everything that is now contiguous, in order. This is the only place a message // reaches the screen, so every device shows the conversation in the same order. for { next, ok := r.early[r.delivered+1] if !ok { break } delete(r.early, next.Seq) r.show(next) r.delivered++ }
// Something is still waiting behind a hole: ask for exactly the missing range. // A real client also re-asks after a timeout, in case the fetch itself is lost. if len(r.early) > 0 { first := int64(math.MaxInt64) for seq := range r.early { first = min(first, seq) } if holeEnd := first - 1; holeEnd > r.requestedUpTo { r.server.Fetch(r.conversationID, r.delivered+1, holeEnd) r.requestedUpTo = holeEnd } }
// One watermark, not one ack per message. Real clients batch these for a few hundred ms. r.server.AckDelivered(r.conversationID, r.delivered)}interface Message { conversationId: string; seq: number; body: string;}
// The calls a device makes back to the server for one conversation.interface SyncServer { // Ask for a hole. The answers come back through onMessage like any other message. fetch(conversationId: string, fromSeq: number, toSeq: number): void; // Moves this device's delivered cursor; the server turns it into the sender's second tick. ackDelivered(conversationId: string, upToSeq: number): void;}
// One conversation on one device. Messages can arrive twice (fan-out is at-least-once), out of// order (a live push racing a sync page), or not at all (a delivery dropped with a gateway).// Contiguous sequence numbers make all three visible, which timestamps never could.class ConversationReceiver { private readonly early = new Map<number, Message>(); // arrived ahead of a hole private requestedUpTo: number; // so a hole is fetched once, not again on every later message
constructor( private readonly conversationId: string, private delivered: number, // highest seq with nothing missing below it; saved on the device private readonly server: SyncServer, private readonly show: (m: Message) => void, ) { this.requestedUpTo = delivered; }
onMessage(m: Message): void { if (m.seq <= this.delivered || this.early.has(m.seq)) return; // a duplicate: drop it this.early.set(m.seq, m);
// Release everything that is now contiguous, in order. This is the only place a message // reaches the screen, so every device shows the conversation in the same order. let next: Message | undefined; while ((next = this.early.get(this.delivered + 1))) { this.early.delete(next.seq); this.show(next); this.delivered++; }
// Something is still waiting behind a hole: ask for exactly the missing range. // A real client also re-asks after a timeout, in case the fetch itself is lost. if (this.early.size > 0) { const holeEnd = Math.min(...this.early.keys()) - 1; if (holeEnd > this.requestedUpTo) { this.server.fetch(this.conversationId, this.delivered + 1, holeEnd); this.requestedUpTo = holeEnd; } }
// One watermark, not one ack per message. Real clients batch these for a few hundred ms. this.server.ackDelivered(this.conversationId, this.delivered); }}Why “only if free” matters. A lease alone isn’t safe. An owner can freeze, for a long garbage collection or a paused virtual machine, past its lease. A new owner takes over and writes number 42. Then the old one wakes up, still believing it’s the owner, and writes its own 42. Checking the lease just before writing doesn’t help, because the freeze can come between the check and the write.
A frozen owner like this is called a zombie. The fix is to make the store refuse the second writer. Each insert says “only if number 42 is empty”. Two writers can never both get 42. The loser reads back who did, sends no ack, and steps down.
- Color key
- Service
Go deeperWhat the conditional write costs, and the exact promise2 min
In Cassandra, “insert only if absent” is a lightweight transaction, a small consensus round among the 3 copies. It costs two to four round trips instead of one, a few milliseconds more per send, and about three times the work of a plain write. It’s what sizes the cluster: about 400 nodes for the conditional writes, against about 200 the disk alone would need. ScyllaDB does it more cheaply, and DynamoDB’s condition expression costs no more than a normal write. Any of these is a fair choice. A design that drops the check to save the round trips is not.
| Guard against a zombie | Verdict |
|---|---|
| Stop writing early, take over late | Unsafe: any freeze longer than the margin puts two writers on one number |
| A rising lease number checked by the store | Correct, but it’s its own transaction, and retries still rely on memory |
| Insert the number only if free | The number itself is the fence: the pick |
The promise, stated exactly. Whatever the leases and clocks do, no two messages share a number, a message that got an ack is never overwritten, and numbers have no holes. A retry gets its number back if it arrives within the chat’s last 1,000 messages. A later one can show twice.
A thousand-person group
Section titled “A thousand-person group”Someone posts in a 1,000-person group. What does the owner do, and what breaks?
In the core design, the owner delivers each message itself. For a 1,024-member group, that’s hundreds of gateway calls while the owner holds the conversation. One slow gateway stalls the whole group.
So the owner stops delivering. After storing the message, it appends one delivery event to
Kafka, split by conversation so deliveries stay in order. Fan-out workers turn members into devices, look them all up in one batched registry call, and send one batch per gateway. Offline devices go to the push service.
Stage 5: Fan-out through a log
Stage 5 of 6
Fan-out through a log
Why this stage
Groups of up to 1,024 members: one message becomes 1,024 deliveries.
Done inline, one slow gateway stalls the conversation, and a crash after the ack loses the delivery.
What we add
A Kafka delivery log partitioned by conversation, and fan-out workers that expand members to devices and send one batch per gateway.
What it costs
About 10 ms more per message, one more system to run, and at-least-once delivery, so devices must drop duplicates.
At 700k messages sent per second, every part has headroom. Raise the traffic until something turns red.
The numbers behind the busy bars
How busy it gets
- There are about 285 open connections for every message a second. At the 700k a second peak, that is 200 million connections.
- Each message reaches about 4 devices, and 30% of them are offline.
What one machine can do
- One gateway holds about 500,000 mostly idle WebSockets, about 20 KB each. We plan it at 60%.
- A message service instance handles about 20,000 operations a second.
- One Postgres primary takes about 10,000 writes a second.
How big the shared systems are
- The registry is a 40-node Redis cluster, about 100,000 operations a second per node.
- A Cassandra node takes about 30,000 replica operations a second. Every message is a conditional insert, a Paxos round that costs about 9 replica operations.
- The Kafka cluster takes about 2 million messages a second.
// One event from the delivery log: a message that is already stored, so every step below may// fail and be retried without losing it.record Delivery(String conversationId, long seq, long senderDevice, byte[] frame) {}
interface Members { // Cached in the worker. Membership changes are messages in the conversation's own log, // so the cache is refreshed in sequence order and a removed member gets nothing after it. List<Long> devicesOf(String conversationId);}
interface Registry { // One batched lookup (MGET per shard). A device with no entry is offline. Map<Long, String> gatewayOf(Collection<Long> devices);}
interface Gateways { // One call per gateway for all its recipients. Returns the devices it no longer holds: // the registry was stale because the device dropped or moved a moment ago. Set<Long> deliver(String gatewayId, List<Long> devices, Delivery d);}
interface Push { void wake(List<Long> devices, Delivery d); // queued; mutes and collapse keys handled there}
final class FanoutWorker { static final int MAX_GROUP_DEVICES = 5_000; // 1,024 members, a few devices each
private final Members members; private final Registry registry; private final Gateways gateways; private final Push push;
FanoutWorker(Members members, Registry registry, Gateways gateways, Push push) { this.members = members; this.registry = registry; this.gateways = gateways; this.push = push; }
// The caller commits the Kafka offset only after this returns. A crash before that replays // the event, and devices drop the repeat by sequence number. void handle(Delivery d) { List<Long> targets = new ArrayList<>(members.devicesOf(d.conversationId())); targets.removeIf(x -> x == d.senderDevice()); // the sender's other devices still get it, to stay in sync if (targets.size() > MAX_GROUP_DEVICES) throw new IllegalStateException("group over the size limit: " + d.conversationId());
Map<Long, String> where = registry.gatewayOf(targets); Map<String, List<Long>> byGateway = new HashMap<>(); List<Long> offline = new ArrayList<>(); for (long device : targets) { String gw = where.get(device); if (gw == null) offline.add(device); else byGateway.computeIfAbsent(gw, k -> new ArrayList<>()).add(device); }
// 650 devices across 300 gateways is 300 calls, not 650. In production these run in // parallel with a short timeout, so one slow gateway delays only its own users. for (var e : byGateway.entrySet()) { offline.addAll(gateways.deliver(e.getKey(), e.getValue(), d)); }
// Push is the doorbell, not the delivery: the message already waits in the store for // the device's next sync, whether or not the notification arrives. if (!offline.isEmpty()) push.wake(offline, d); }}# One event from the delivery log: a message that is already stored, so every step# below may fail and be retried without losing it.@dataclass(frozen=True)class Delivery: conversation_id: str seq: int sender_device: int frame: bytes
class Members(Protocol): # Cached in the worker. Membership changes are messages in the conversation's own log, # so the cache is refreshed in sequence order and a removed member gets nothing after it. def devices_of(self, conversation_id: str) -> list[int]: ...
class Registry(Protocol): # One batched lookup (MGET per shard). A device with no entry is offline. def gateway_of(self, devices: list[int]) -> dict[int, str]: ...
class Gateways(Protocol): # One call per gateway for all its recipients. Returns the devices it no longer holds: # the registry was stale because the device dropped or moved a moment ago. def deliver(self, gateway_id: str, devices: list[int], d: Delivery) -> set[int]: ...
class Push(Protocol): def wake(self, devices: list[int], d: Delivery) -> None: ... # mutes, collapse keys there
class FanoutWorker: MAX_GROUP_DEVICES = 5_000 # 1,024 members, a few devices each
def __init__(self, members: Members, registry: Registry, gateways: Gateways, push: Push): self._members = members self._registry = registry self._gateways = gateways self._push = push
# The caller commits the Kafka offset only after this returns. A crash before that # replays the event, and devices drop the repeat by sequence number. def handle(self, d: Delivery) -> None: # The sender's other devices still get it, so they stay in sync. targets = [x for x in self._members.devices_of(d.conversation_id) if x != d.sender_device] if len(targets) > self.MAX_GROUP_DEVICES: raise ValueError(f"group over the size limit: {d.conversation_id}")
where = self._registry.gateway_of(targets) by_gateway: dict[str, list[int]] = defaultdict(list) offline: list[int] = [] for device in targets: gw = where.get(device) if gw is None: offline.append(device) else: by_gateway[gw].append(device)
# 650 devices across 300 gateways is 300 calls, not 650. In production these run in # parallel with a short timeout, so one slow gateway delays only its own users. for gw, devices in by_gateway.items(): offline.extend(self._gateways.deliver(gw, devices, d))
# Push is the doorbell, not the delivery: the message already waits in the store for # the device's next sync, whether or not the notification arrives. if offline: self._push.wake(offline, d)// One event from the delivery log: a message that is already stored, so every step below may// fail and be retried without losing it.record Delivery(string ConversationId, long Seq, long SenderDevice, byte[] Frame);
interface IMembers{ // Cached in the worker. Membership changes are messages in the conversation's own log, // so the cache is refreshed in sequence order and a removed member gets nothing after it. IReadOnlyList<long> DevicesOf(string conversationId);}
interface IRegistry{ // One batched lookup (MGET per shard). A device with no entry is offline. IReadOnlyDictionary<long, string> GatewayOf(IReadOnlyCollection<long> devices);}
interface IGateways{ // One call per gateway for all its recipients. Returns the devices it no longer holds: // the registry was stale because the device dropped or moved a moment ago. IReadOnlySet<long> Deliver(string gatewayId, IReadOnlyList<long> devices, Delivery d);}
interface IPush{ void Wake(IReadOnlyList<long> devices, Delivery d); // queued; mutes and collapse keys handled there}
sealed class FanoutWorker(IMembers members, IRegistry registry, IGateways gateways, IPush push){ const int MaxGroupDevices = 5_000; // 1,024 members, a few devices each
// The caller commits the Kafka offset only after this returns. A crash before that replays // the event, and devices drop the repeat by sequence number. public void Handle(Delivery d) { // The sender's other devices still get it, so they stay in sync. var targets = members.DevicesOf(d.ConversationId).Where(x => x != d.SenderDevice).ToList(); if (targets.Count > MaxGroupDevices) throw new InvalidOperationException($"group over the size limit: {d.ConversationId}");
var where = registry.GatewayOf(targets); var byGateway = new Dictionary<string, List<long>>(); var offline = new List<long>(); foreach (var device in targets) { if (!where.TryGetValue(device, out var gw)) offline.Add(device); else if (byGateway.TryGetValue(gw, out var list)) list.Add(device); else byGateway[gw] = [device]; }
// 650 devices across 300 gateways is 300 calls, not 650. In production these run in // parallel with a short timeout, so one slow gateway delays only its own users. foreach (var (gw, devices) in byGateway) offline.AddRange(gateways.Deliver(gw, devices, d));
// Push is the doorbell, not the delivery: the message already waits in the store for // the device's next sync, whether or not the notification arrives. if (offline.Count > 0) push.Wake(offline, d); }}// Delivery is one event from the delivery log: a message that is already stored, so every// step below may fail and be retried without losing it.type Delivery struct { ConversationID string Seq int64 SenderDevice int64 Frame []byte}
// Members is cached in the worker. Membership changes are messages in the conversation's own// log, so the cache is refreshed in sequence order and a removed member gets nothing after it.type Members interface { DevicesOf(conversationID string) ([]int64, error)}
// Registry does one batched lookup (MGET per shard). A device with no entry is offline.type Registry interface { GatewayOf(devices []int64) (map[int64]string, error)}
// Gateways takes one call per gateway for all its recipients. It returns the devices it no// longer holds: the registry was stale because the device dropped or moved a moment ago.type Gateways interface { Deliver(gatewayID string, devices []int64, d Delivery) []int64}
// Push queues wake-ups; mutes and collapse keys are handled there.type Push interface { Wake(devices []int64, d Delivery)}
const maxGroupDevices = 5000 // 1,024 members, a few devices each
type FanoutWorker struct { members Members registry Registry gateways Gateways push Push}
// Handle delivers one event. The caller commits the Kafka offset only after it returns nil.// A crash before that replays the event, and devices drop the repeat by sequence number.func (w *FanoutWorker) Handle(d Delivery) error { all, err := w.members.DevicesOf(d.ConversationID) if err != nil { return err } targets := make([]int64, 0, len(all)) for _, x := range all { if x != d.SenderDevice { // the sender's other devices still get it, to stay in sync targets = append(targets, x) } } if len(targets) > maxGroupDevices { return fmt.Errorf("group over the size limit: %s", d.ConversationID) }
where, err := w.registry.GatewayOf(targets) if err != nil { return err // retried; nothing was sent yet } byGateway := map[string][]int64{} var offline []int64 for _, device := range targets { if gw, ok := where[device]; ok { byGateway[gw] = append(byGateway[gw], device) } else { offline = append(offline, device) } }
// 650 devices across 300 gateways is 300 calls, not 650. In production these run in // parallel with a short timeout, so one slow gateway delays only its own users. for gw, devices := range byGateway { offline = append(offline, w.gateways.Deliver(gw, devices, d)...) }
// Push is the doorbell, not the delivery: the message already waits in the store for the // device's next sync, whether or not the notification arrives. if len(offline) > 0 { w.push.Wake(offline, d) } return nil}// One event from the delivery log: a message that is already stored, so every step below may// fail and be retried without losing it.interface Delivery { conversationId: string; seq: number; senderDevice: number; frame: Uint8Array;}
interface Members { // Cached in the worker. Membership changes are messages in the conversation's own log, // so the cache is refreshed in sequence order and a removed member gets nothing after it. devicesOf(conversationId: string): Promise<number[]>;}
interface Registry { // One batched lookup (MGET per shard). A device with no entry is offline. gatewayOf(devices: number[]): Promise<Map<number, string>>;}
interface Gateways { // One call per gateway for all its recipients. Resolves to the devices it no longer holds: // the registry was stale because the device dropped or moved a moment ago. deliver(gatewayId: string, devices: number[], d: Delivery): Promise<number[]>;}
interface Push { wake(devices: number[], d: Delivery): Promise<void>; // queued; mutes and collapse keys there}
const MAX_GROUP_DEVICES = 5_000; // 1,024 members, a few devices each
class FanoutWorker { constructor( private readonly members: Members, private readonly registry: Registry, private readonly gateways: Gateways, private readonly push: Push, ) {}
// The caller commits the Kafka offset only after this resolves. A crash before that replays // the event, and devices drop the repeat by sequence number. async handle(d: Delivery): Promise<void> { // The sender's other devices still get it, so they stay in sync. const targets = (await this.members.devicesOf(d.conversationId)).filter( (x) => x !== d.senderDevice, ); if (targets.length > MAX_GROUP_DEVICES) { throw new Error(`group over the size limit: ${d.conversationId}`); }
const where = await this.registry.gatewayOf(targets); const byGateway = new Map<string, number[]>(); const offline: number[] = []; for (const device of targets) { const gw = where.get(device); if (gw === undefined) offline.push(device); else byGateway.set(gw, [...(byGateway.get(gw) ?? []), device]); }
// 650 devices across 300 gateways is 300 calls, not 650, all in flight at once, so one // slow gateway delays only its own users. Production adds a short timeout per call. const gone = await Promise.all( [...byGateway].map(([gw, devices]) => this.gateways.deliver(gw, devices, d)), ); offline.push(...gone.flat());
// Push is the doorbell, not the delivery: the message already waits in the store for the // device's next sync, whether or not the notification arrives. if (offline.length > 0) await this.push.wake(offline, d); }}Follow a message to a 500-member group:
Trace a request: Message to a 500-member group
Message to a 500-member group: step 1 of 9
Gateways to Message service
Same as a 1:1 send: the owner of this group dedupes, assigns the sequence number and stores it once. A group message is stored once, not once per member.
- Gateways → Message service2 ms
- Message service → Cassandra10 ms
- Message service → Kafka5 ms
- Kafka → Fan-out workers5 ms
- Fan-out workers → Session registry3 ms
- Fan-out workers → Gateways5 ms
- Fan-out workers → Push serviceasync
- Push service → APNs / FCMasync
- Response
The 1,024 cap is a cost decision. A message to N members costs N deliveries. And busier groups have more members sending, so a group’s traffic grows with N squared. Bigger audiences are a different product, channels: a few writers, no ticks, and followers fetch new posts when they open the channel instead of having them pushed.
Go deeperAn owner that crashes between storing and logging1 min
If the owner stores a message and crashes before logging the delivery event, the message has no event. So a new owner republishes the tail it read on takeover. Devices drop the repeats by sequence number. The log adds about 10 ms per message and one more system to run, at 700,000 events a second. In return, a slow gateway delays only its own users, and a crashed worker resumes from its position.
| Delivery | Cost per message | Fits |
|---|---|---|
| Inside the owner | N calls during the send | One-to-one only |
| Log plus workers | N deliveries, batched | Chats and groups up to about 1,000 |
| Fetch on read | 1 write; each reader fetches | Channels with 100,000 followers |
Two hundred million open sockets
Section titled “Two hundred million open sockets”How many connections can one gateway hold, and what happens when one dies or we deploy?
Per connection, a gateway does very little: hold the socket, answer a ping a minute, pass on a few messages. WhatsApp held over a million connections on one server back in 2011. So what limits a box?
| Limit | At 300,000 per box | At 2,000,000 per box |
|---|---|---|
| Memory at 20 KB each | 6 GB | 40 GB, still fine |
| Pings, one a minute | 5,000 a second | 33,000 a second, fine |
| One box dies | 300,000 reconnects, 0.15% of users | 2,000,000 reconnects, 1% of users at once |
The limit is not memory. It’s blast radius: how many users one failure throws off at once. Every one of them reconnects, and each new secure connection costs CPU on the neighbors. So we run about 300,000 per box, 60% of what a box can take, so each box can absorb its share of a dead neighbor’s users. That’s about 670 gateways instead of 100.
Three habits make gateway churn invisible:
- Random reconnect delay. A phone waits a random 0 to 5 seconds, then backs off. Without it, 300,000 phones retry in the same second, a reconnect storm.
- Cheap reconnects. Resuming a secure session skips most of the handshake. Sync restores state from the cursors, so nothing is rebuilt in memory.
- Draining on deploy. A leaving gateway stops taking new sockets and closes its old ones over several minutes, with a “reconnect elsewhere” message. Gateways carry little logic, so they rarely deploy.
Online status
Section titled “Online status”Now product wants a green dot when a contact is online, and “last seen” otherwise.
The obvious design tells all of a user’s contacts whenever they connect or disconnect. Users do that about 40 times a day, 700,000 changes a second at peak. With 200 contacts each, that’s 140 million updates a second, 50 times the messages, for a green dot almost nobody is looking at.
So status goes only to people who are looking. Gateways report connects and disconnects to a presence service kept in memory. A device subscribes only to the users on its screen: the open chat, or the visible rows of the chat list. Everyone else reads “last seen” when they open a chat. That drops updates to about a million a second.
Stage 6: Presence on demand
Stage 6 of 6
Presence on demand
Why this stage
Product wants "online" and "last seen".
Broadcasting every status change to about 200 contacts would be 140 million pushes/s at peak, 50 times the message deliveries.
What we add
A presence service.
Gateways report connects and disconnects; a device subscribes only to the contacts on its screen.
What it costs
Presence lags by seconds, and a short grace period hides flapping connections.
At 700k messages sent per second, every part has headroom. Raise the traffic until something turns red.
The numbers behind the busy bars
How busy it gets
- There are about 285 open connections for every message a second. At the 700k a second peak, that is 200 million connections.
- Each message reaches about 4 devices, and 30% of them are offline.
What one machine can do
- One gateway holds about 500,000 mostly idle WebSockets, about 20 KB each. We plan it at 60%.
- A message service instance handles about 20,000 operations a second.
- One Postgres primary takes about 10,000 writes a second.
How big the shared systems are
- The registry is a 40-node Redis cluster, about 100,000 operations a second per node.
- A Cassandra node takes about 30,000 replica operations a second. Every message is a conditional insert, a Paxos round that costs about 9 replica operations.
- The Kafka cluster takes about 2 million messages a second.
A grace period of about 20 seconds before showing “offline” hides a phone switching networks. Typing indicators use the same subscriptions, are never stored, and are the first thing dropped under load. None of this touches the database.
Ticks in groups, and encryption
Section titled “Ticks in groups, and encryption”In a 1,000-person group, how do the ticks work? And what changes with end-to-end encryption?
Counted per member and per message, a 1,000-member group makes 2,000 receipts for every message. Three ideas make it cheap. Watermarks: “read up to 4182” replaces one receipt per message. Totals for the sender: the owner tracks the lowest read number across members, and tells the sender only when “read by all” moves. Derive the rest: unread count is the newest number minus the device’s read number, so there’s no counter to drift.
With end-to-end encryption, the server can’t read message bodies. The skeleton survives: gateways, registry, owners, sequence numbers and sync never needed to read a body. What changes is who copies the message, and what the server can keep.
Go deeperWhat end-to-end encryption changes2 min
| Area | Today | With end-to-end encryption |
|---|---|---|
| Fan-out | Server copies one message to N devices | The sender encrypts per device; groups share a sender key |
| New services | None | A key directory, as critical as the registry |
| History | Stored readable on the server | Kept only until every device has it; encrypted backups |
| Storage | 5.5 PB over 5 years | Undelivered messages only: tens of TB |
| Push | Preview text in the notification | An encrypted payload the phone decrypts |
| Search, spam | Server can index and scan | On the device; abuse detection uses metadata and reports |
Multiple devices come first, because encryption builds on them. Each device has its own socket, cursors and registry entry. A message goes to every device of every member, including the sender’s other devices. When Bob reads on his laptop, the “read up to” message also reaches his phone, which clears its badge.
When things break
Section titled “When things break”A gateway with 300,000 users dies. Then a Cassandra node. What do users see?
Whether each failure has a small blast radius, and a recovery that loses no acked message.
One rule keeps this short: the “sent” tick means the message is on 2 copies. Everything after that can fail and be retried. A dead gateway means 300,000 users see “connecting” for a few seconds, reconnect to neighbors, and sync. A dead owner stalls sends in its chats for about 10 seconds, until the lease moves. A lost Cassandra node changes nothing, because 2 of 3 copies still answer.
Under stress, shed in a fixed order: typing first, then online status, then read ticks, then push previews. Sends and deliveries go last.
Click any box to break it and see what users would notice:
Break it: what fails, who notices, what users see
Failure: click any box to break it
A gateway goes down
What breaks
Its 300,000 sockets close.
How we notice
Load balancer health check fails; the registry sees the gateway lease lapse in about 10 seconds.
What users see
Those users reconnect to other gateways within seconds, with jitter.
Nothing acked is lost: messages sent to them during the gap are in the store and arrive by sync.
What we do
Registry entries pointing at the dead gateway are ignored once its lease lapses.
Each gateway runs at 60%, so the rest absorb the reconnects.
Regions. Users are global, and a secure connection from Mumbai to Virginia takes about 400 ms to set up. So gateways run in every region. Each conversation has a home region, near most of its members, where its owner and its stored copies live. A send from elsewhere makes one cross-region hop to the owner, 100 to 200 ms. Only one region decides each chat’s order, because two regions handing out numbers would need a merge, and devices could disagree.
Go deeperEvery failure, and what users see2 min
| Part | Failure | What users see | What we do |
|---|---|---|---|
| Gateway | Crash | 300,000 users reconnect within seconds | Random delays, spare room, sync from cursors |
| Message service | Owner crash | Sends in its chats stall about 10 s | Takeover read; clients retry with the same ID |
| Session registry | Shard down | No live delivery for those devices | Replica takes over; push and sync cover |
| Cassandra | Node down | Nothing; two down blocks those chats’ sends | Replace it; phones keep sends pending and retry |
| Kafka | Down | Messages stored but not delivered live | Owner republishes later; phones fetch gaps |
| Apple or Google push | Throttling | Late notifications | Retry; sync on open |
| Region | Outage | 30 to 60 s of “connecting” | Move traffic; promote copies of chats homed there |
Copies to other regions are made in the background, so a region outage can lose the last second of messages homed there. The senders’ phones still hold those as pending and resend them.
Go deeperRunning it: alerts and abuse1 min
Wake someone up when: test clients that message each other in every region see p99 over 1 second for 5 minutes; fewer than 99.95% of sends get acks; connected devices drop more than 5% against the same hour last week, which catches failures health checks miss; or fan-out falls more than 5 seconds behind.
Abuse. Spam looks like a new account messaging many strangers. So limit new conversations a day, more strictly for new accounts, cap forwarding to many chats, and feed reports into a classifier that works on metadata, which still works with encryption.
Wrap up
Section titled “Wrap up”The whole design
Section titled “The whole design”Here is everything we built, in the order we built it. Use the buttons to step through it.
The full design, stage by stage
Stage 6 of 6
Presence on demand
Why this stage
Product wants "online" and "last seen".
Broadcasting every status change to about 200 contacts would be 140 million pushes/s at peak, 50 times the message deliveries.
What we add
A presence service.
Gateways report connects and disconnects; a device subscribes only to the contacts on its screen.
What it costs
Presence lags by seconds, and a short grace period hides flapping connections.
At 700k messages sent per second, every part has headroom. Raise the traffic until something turns red.
The numbers behind the busy bars
How busy it gets
- There are about 285 open connections for every message a second. At the 700k a second peak, that is 200 million connections.
- Each message reaches about 4 devices, and 30% of them are offline.
What one machine can do
- One gateway holds about 500,000 mostly idle WebSockets, about 20 KB each. We plan it at 60%.
- A message service instance handles about 20,000 operations a second.
- One Postgres primary takes about 10,000 writes a second.
How big the shared systems are
- The registry is a 40-node Redis cluster, about 100,000 operations a second per node.
- A Cassandra node takes about 30,000 replica operations a second. Every message is a conditional insert, a Paxos round that costs about 9 replica operations.
- The Kafka cluster takes about 2 million messages a second.
The decisions, and what each one costs
Section titled “The decisions, and what each one costs”| Decision | We chose | We gave up | We’d choose differently if |
|---|---|---|---|
| Connection | WebSocket, binary frames | Stateless servers | Updates were rare (polling would do) |
| Finding a device | Session registry | A lookup per delivery | Users could be routed by hash at the edge |
| Order | One owner per chat, insert only if free | 10 s of stalled sends after a crash | Order didn’t matter |
| Storage | Cassandra by conversation, 90 days hot | Queries across conversations | We were 100 times smaller (sharded MySQL) |
| Groups | Kafka plus workers, batched, 1,024 cap | 10 ms and one more system | Audiences were huge (fetch on read) |
| Online status | Only to people looking, 20 s grace | Exact, instant status | Contact lists were tiny |
| Regions | Gateways everywhere, owner in a home region | One extra hop for distant members | Every chat’s members lived in one region |
How to spend 45 minutes
Section titled “How to spend 45 minutes”- 0 to 4. Scale, group size, history and multiple devices. Name the three ticks.
- 4 to 9. 700,000 sends a second, 4 deliveries each, 200 million connections, 3 TB a day. Say why heartbeats matter and bandwidth doesn’t.
- 9 to 20. Build it: one server, then gateways and the registry, the owner and sequence numbers, storage by conversation, push and sync. Draw the three ticks. A mid-level answer can stop here.
- 20 to 30. The stress tests: the lost ack and the zombie owner, then groups.
- 30 to 40. Gateway sizing, then status or encryption, whichever the interviewer leans toward.
- 40 to 45. A gateway dying, then your own questions.
Never skip sequence numbers, the meaning of the “sent” tick, or offline sync.
Follow-up questions
Section titled “Follow-up questions”Interviewer asksA message is deleted for everyone. How does that work with sequence numbers?
The delete is a new event with its own number that points at the original. Devices apply it in order and show “message deleted”. Offline devices see the delete after the original on sync, so the order holds.
Interviewer asksNew Year's Eve: traffic is 5 times the normal peak for an hour. What do you do?
Add capacity ahead of time to the message service, workers and Kafka. Connections rise less than messages. During the hour, shed typing, online status, read ticks and push previews in that order. Ticks catch up after midnight, because they’re watermarks.
Go deeperMore follow-up questions1 min
How would you cut storage cost in half? Shorten the fast window from 90 to 30 days, which cuts it by two thirds. Compress old buckets harder, and use 2 copies plus erasure coding in cold storage instead of 3 full copies. Or keep messages only until delivered, which is the encrypted design anyway.
How would you add channels with a million followers? Not as a big group. A channel has a few writers, no ticks and no delivery per follower. Posts are stored once, followers get at most one combined notification, and each device fetches new posts when it opens the channel.
Product wants server-side message search. What changes? A reader on the delivery log indexes messages into a search cluster split by conversation, and queries are filtered by membership. It lags by seconds, and it’s impossible with end-to-end encryption, where search stays on the device.
Further reading
Section titled “Further reading”- Load balancing, partitioning, message queues and consistency models on this site, and the notification system problem for the push side.
- How Discord Stores Trillions of Messages, Discord engineering: a chat message store partitioned by channel and time bucket, and its move from Cassandra to ScyllaDB.
- ONE MILLION!, WhatsApp, 2011: a million established TCP sessions on one machine, with room to spare.
- How to do distributed locking, Martin Kleppmann: why a lease without a fencing check in the store fails under process pauses, the reason every insert here is conditional.
The designbeyondcode digest, every Saturday
New deep dives, interview tips and site news in one short email. Free. Leave with one click.
We never sell or share your email. We only use it to send this newsletter.