How to design a chat system

In this lesson, we’ll build a real-time chat backend, following one message from the network connection a phone holds open down to the counter that decides which of two messages happened first. By the end you’ll be able to size the connection tier from first principles, say why a persistent connection beats polling, derive the exact group size at which the message-routing strategy has to change, and explain why no system can promise a message is delivered exactly once.

What goes in, and what comes out

The input is one small event: a client asks to put a piece of text into a conversation. The output is that same text appearing on every device belonging to every member of that conversation, in the same order for everybody. Within a second if they are online; on their next reconnect if they are not. Alongside it go the acknowledgements that report the message arrived and was read.

Nothing in that is computationally hard. There is no ranking model, no join across a billion rows, no search index. What is hard is that the output has to reach one specific open network connection on one specific machine, and that machine can die.

The one property that makes chat different

Every other system in this track is request/response: the client asks, the server answers, and the server forgets the client until the next question. Any server can answer any question, because no server is holding anything.

Chat is the first one where the server has to remember where you are. A long-lived, individually addressable connection makes the serving tier stateful: the server keeps per-user state in its own memory between messages, so the machine a client is talking to is not interchangeable with the other ninety-nine.

Most of what is difficult about chat descends from that one property:

• Finding which machine currently holds a given user’s connection.
• Keeping messages in a consistent order when they are written by many machines.
• Tracking who is online, cheaply enough that it does not cost more than the chat.
• A delivery guarantee that cannot be made exactly-once, no matter how much machinery you throw at it.

Two terms recur throughout, so fix them now.

A socket is one open, two-way network connection between a client and a server. While it is open, either side can write bytes to the other at any moment without asking first.

A shard is one slice of a dataset too big for a single machine. The data is split by some key (here, by conversation) and each slice lives on its own machine.

The three decisions that drive everything

Three decisions determine every other choice in this chapter:

1. What is the transport? This decides whether the serving tier is stateless (any machine can handle any request) or stateful, where one particular machine holds your connection and only it can reach you.
2. Where does a message get stored: once per conversation, or once per recipient? This decides the storage bill and the ceiling on how large a group can get.
3. What orders the messages? Wall-clock timestamps do not survive being written by several machines at once, and the fix is cheaper than it looks.

When each is made badly it produces a specific production failure. Two words first: presence is the online/offline/last-seen indicator next to a contact’s name, and fanout is the work of getting one message from one sender out to many recipients.

Three more terms, defined once and used everywhere after:

• Gateway: a server whose only job is to hold clients’ sockets open. It does no product logic.
• Clock skew: the difference between what two machines’ clocks say at the same real instant. Even synchronised over the network, they disagree by a handful of milliseconds.
• At-least-once: the sender keeps retrying until it is told the message arrived. That guarantees the message is never lost, and permits the same message to arrive twice.

In one sentence: chat is a routing problem, not a storage problem. The messages are small and the volume is ordinary; what is hard is that the destination is a socket on a specific box, and that box can die.

Requirements

Functional

• One-to-one messaging and group messaging.
• Delivery to online recipients in under a second; offline recipients get the message when they next reconnect.
• Receipts: status markers that tell a sender the message left their device (sent), reached the recipient’s device (delivered), and was displayed (read).
• Presence: whether a contact is online now, and when they were last seen if not.
• Message history that can be paged backwards, on every device the user owns.

Non-functional — these decide the design

p95 means the 95th percentile: the value 95 out of 100 requests come in under. Availability of 99.99% means the service may be unusable for at most about 52 minutes a year.

A total order within a conversation means every participant, on every device, sees the same messages in the identical sequence. Dedup (deduplication) is recognising that a message you already have has arrived again, and dropping the copy. A cursor is a single number recording how far through a conversation a device or account has got.

Assumptions, and which ones are load-bearing

A load-bearing assumption is one where being wrong gives you a different architecture, not a different machine count. A soft one changes only how much hardware you buy.

Daily active users (DAU) are distinct people who use the product on a given day. The single most load-bearing item is the second one: the entire ordering story is a consequence of a conversation having one owner. If conversations must accept writes in two regions at once, the sequence-number approach has to be replaced, not tuned.

Back of the envelope

Four numbers drive the rest of the chapter, all derived from the product assumptions.

Connections and message rate. 500 M DAU at a 4% concurrent share is 20 M concurrent connections. 40 messages per user per day is 20 B messages/day, which over 86,400 seconds is ~231,000 messages/s on average. Peak at the stated 2.5x is ~579,000/s, but nothing later depends on the peak. The mechanisms are sized from the average and from how many users a single machine failure takes down. The 20 M concurrent figure is the same one sized in the estimation chapter; this chapter extends it.

Deliveries, the number that actually matters. Messages sent is not the load. One group message must be handed to every member. Split traffic by type: a 1:1 message has 1 recipient; a mean group of 25 has 24. Weighted, 0.70 x 1 + 0.30 x 24 = 7.9 recipients per message. So 1.83 M deliveries/s, 7.9x the send rate. The session registry, the receipts system and the fanout path are all sized against this.

Storage. One stored message row is about 100 B:

msg_id 8 · conv_id 8 · sender_id 8 · seq 8 · created_at 8 · flags 4 · body 56  =  100 B

The body is 56 B because most messages are one short line and a photo is stored elsewhere, appearing only as a URL, the “small text messages” assumption doing its work. Multiply out: 20 B messages/day x 100 B = 2 TB/day, x 3 replicas x 5 years ≈ 11 PB. That is a rack of disks, not a research project; chat is not storage-bound.

The per-recipient alternative writes a separate copy for each recipient instead of one per conversation. That multiplies the daily bytes by 7.9, giving 86.5 PB, 75 extra petabytes to buy a query a cursor already answers. Write the message once, into the conversation.

API sketch

Here are the exact frames a client sends and receives. The first block is the persistent connection; the rest are ordinary REST requests (REST is the style where each URL names a resource and the HTTP verb names the action) used for history and as a fallback when the socket is unavailable.

WS marks the WebSocket endpoint, the protocol that upgrades an ordinary web request into a permanently open two-way socket. -> is a frame the client sends; <- a frame the server pushes down; hb is a heartbeat, a tiny frame on a timer that proves the connection is alive.

WS   /v1/connect                     upgrade; auth in the first frame; heartbeat on the socket

  -> {"t":"send",     "conv_id":..., "client_msg_id":"01H...", "body":"..."}
  <- {"t":"ack",      "client_msg_id":"01H...", "seq": 4812}
  <- {"t":"msg",      "conv_id":..., "seq":4812, "sender":..., "ts":..., "body":"..."}
  <- {"t":"receipt",  "conv_id":..., "user":..., "kind":"delivered|read", "seq":4812}
  <- {"t":"presence", "user":..., "state":"online|offline", "last_seen":...}
  -> {"t":"hb"}

POST /v1/conversations/{id}/messages   REST fallback when the socket is unavailable
GET  /v1/conversations/{id}/messages?before_seq=4812&limit=50
POST /v1/conversations/{id}/read       {"seq": 4812}
GET  /v1/sync?cursors={conv_id:seq}    catch-up after reconnect, one round trip

The WebSocket frames form one conversation: send is the only thing the client pushes up; ack returns to the sender alone with the sequence number the server assigned; msg is the same message arriving at everyone else; receipt reports a user reached delivered or read up to some sequence; presence reports someone going online or offline; hb goes up on a timer regardless.

Three details that make retries safe

1. client_msg_id is generated by the client, before the send. It is the idempotency key. Idempotent means an operation applied twice changes nothing the second time; the key is what lets the server recognise a second copy as a copy. Without it, at-least-once delivery is unimplementable. The server could not tell a retry from a genuine second message with the same text. A ULID (Universally Unique Lexicographically Sortable Identifier) or a UUIDv7 is the right shape: a 128-bit id with a timestamp in the high bits, unique without coordination and roughly time-sortable.

2. read takes a seq, not a message id. Because the per-conversation sequence number counts upward, one call marks everything up to that point as read. The message-id version needs one call per message.

3. /sync takes a map of cursors, one per conversation, so a reconnecting client asks a single question instead of one per conversation. At 50 conversations that is 50 mobile round trips of ~50 ms each that never happen. A round trip (RTT) is one message out and its answer back.

Data model

Five tables. PK marks the primary key (the columns that uniquely identify a row); TTL is time-to-live, an expiry after which a row deletes itself.

conversations   conv_id PK · type · member_count · last_seq · created_at
messages        (conv_id, seq) PK · msg_id · sender_id · created_at · flags · body
                sharded by conv_id, clustered by seq  -- the ONLY copy of the body
members         (conv_id, user_id) PK · joined_seq · role · notify_pref
user_index      (user_id, conv_id) PK · last_read_seq · last_delivered_seq · muted
                sharded by user_id  -- one row per membership, NOT per message
sessions        user_id -> [(gateway_id, device_id, expires_at)]   TTL = 2 x heartbeat

• conversations is one row per thread. last_seq is the highest sequence number handed out so far, the counter the ordering scheme is built around.
• messages holds the bodies, and is the only place a body exists. Its key (conv_id, seq) addresses a message by which conversation and how far along, not by a global id.
• members says who is in a thread. joined_seq records where they joined, which stops a new member from reading history that predates them.
• user_index is the same membership from the user’s side, holding the two cursors: last_read_seq (how far this account has read) and last_delivered_seq (how far this device was handed). Sharded by user_id, so “everything about me” is one machine’s rows.
• sessions is the session registry, which gateway holds which of your devices. Its TTL is twice the heartbeat interval, so a row belonging to a dead machine expires by itself.

Why one row per membership is the whole trick

The design is in the shape of user_index: one row per membership, not one per message. A user in 50 conversations has 50 rows forever, no matter how many messages arrive. The whole table is 500 M users x 50 x 64 B ≈ 1.6 TB, every unread state on the platform.

That works because an unread count is last_seq - last_read_seq: a subtraction between two integers, not a count over a set of rows. Its cost does not grow with the number of messages, which is what O(1), constant time, means. Designs that materialize per-recipient message rows usually do it to make this one query fast, but it is already constant-time, and the alternative was priced at 86.5 PB above.

Why the clustering matters

Clustering messages by (conv_id, seq) means the rows of one conversation sit physically next to each other on disk, in sequence order. Paging back through history is then a single contiguous range scan. The disk reads one unbroken run of bytes instead of hunting for scattered rows one seek at a time. That is the same reason a composite index beats a filter-then-sort (the database-internals chapter).

High-level architecture

The message flows top to bottom, from Client A down to a socket somewhere. The two diamonds are the only branches, and they ask two unrelated questions: one about the conversation, one about a single recipient. The 458 in the first diamond is derived later, in the group-routing deep dive. The dotted lines are presence, which runs independently of message flow.

flowchart TD
    C1(["Client A"]) -->|WebSocket| LB["L4 load balancer<br/>sticky by connection, not by user"]
    C2(["Client B"]) -->|WebSocket| LB
    LB --> GW1["Gateway 1<br/>200 k sockets"]
    LB --> GW2["Gateway 2 ... 100<br/>stateful tier"]

    GW1 -->|"on connect"| REG[("Session registry<br/>user -> gateway<br/>20 M rows · 1.28 GB")]
    GW2 -->|"on connect"| REG

    GW1 --> CS["Chat service<br/>auth · membership check"]
    CS --> SEQ["Sequencer (orders messages)<br/>one owner per conv_id<br/>seq = last_seq + 1"]
    SEQ --> MSG[("Message store: only authoritative copy<br/>sharded by conv_id<br/>clustered by seq")]
    SEQ --> ROUT{"Routing decision:<br/>member_count<br/>above 458?"}

    ROUT -->|"no · direct routing"| REG
    ROUT -->|"yes · broadcast"| BUS["Per-conversation topic<br/>one copy per gateway"]
    REG --> SOCK{"Reachability:<br/>recipient socket<br/>open right now?"}
    BUS --> SOCK

    SOCK -->|"yes"| DEL["Deliver to socket"]
    SOCK -->|"no"| PUSH["APNs / FCM<br/>notification only"]
    DEL --> GW2
    DEL --> IDX[("user_index<br/>last_delivered_seq")]

    GW1 -.->|"heartbeat every 180 s"| PRES["Presence service<br/>token-bucket rate limited"]
    PRES -.-> SUB["Fan out only to<br/>watchers with the<br/>conversation open"]

Following one message from A to B

Step 1: the connection lands. Client A’s WebSocket arrives at an L4 load balancer. “L4” means layer 4: it forwards raw TCP connections without reading the HTTP inside them. It is sticky by connection, not by user. Once a connection is pinned to a machine it stays there for life, but the same user’s second device may land anywhere. The balancer spreads sockets across the ~100 gateways. On connect, each gateway writes a row into the session registry mapping the user to the gateway holding their socket.

Step 2: the message is checked and numbered. The send frame reaches the chat service, which authenticates the sender and checks that the user is a member of the conversation. From there it goes to the sequencer, the single owner of that conv_id, which stamps the message with seq = last_seq + 1 and writes it to the message store.

Step 3, the first diamond: how should this be routed? This is about the conversation and has two answers. Above 458 members, publish one copy to a per-conversation topic and let every gateway holding a member pick it up. At or below 458, the sequencer looks each member up in the registry and sends directly.

Step 4, the second diamond: is this recipient reachable now? This is about one member at one instant, which is why it is a separate box. Socket open: write the bytes onto B’s connection, then advance last_delivered_seq in user_index. Socket closed: ask the platform push service to wake the device: APNs (Apple Push Notification service) on iOS, FCM (Firebase Cloud Messaging) on Android. That push is a notification only and carries no message content.

The two diamonds are kept apart on purpose. “Is this member offline?” is not a verdict a member count can return, so it cannot live in the first diamond. Conflating them is the most common way this diagram gets drawn wrong.

Running alongside all of that, each gateway sends a heartbeat every 180 s per idle connection to the presence service, which is rate-limited by a token bucket (a counter that refills at a fixed rate and lets an event through only if a token is available) and pushes online/offline transitions only to watchers who have the conversation open on screen.

The message store is deliberately plain, and it is the only authoritative copy in the system, the reason every failure below degrades to “late”, not “lost”. The difficulty this chapter exists to teach is entirely upstream of it, in getting the bytes onto one particular socket.

Deep dive 1: the connection tier, and why 3 boxes is 100

Sizing a fleet that holds open connections carries one lesson: the resource you instinctively count, memory, is not the one that decides. Four resources each impose a floor on the machine count, they disagree by a factor of five, and the largest floor wins because the fleet must satisfy all four at once.

(a) Memory. Holding 20 M connections at ~10 KB of kernel state each is 200 GB, about three machines’ worth, the memory answer, and the wrong one. That 10 KB is the steady state for an autotuned socket, one whose buffers the kernel shrinks to fit the traffic. The kernel’s ceilings are much larger: a 128 KiB receive buffer plus a 16 KiB send buffer is 144 KiB. Untuned, a burst can drive every socket toward those ceilings: 20 M x 144 KiB ≈ 2.95 TB, which over 64 GB boxes is 47 boxes. Tuning tcp_rmem and tcp_wmem down is what makes the 10 KB figure true. The number to remember is not 10 KB but that the per-connection footprint spans ~14x and is a configuration decision.

(b) File descriptors. A file descriptor is the small integer the OS gives a process for each open thing, including every socket. The kernel caps how many one process may hold: fs.nr_open, practically 1,048,576. So 20 M / 1.05 M ≈ 20 boxes is a hard floor, assuming one process per box.

(c) Proxy port exhaustion. A TCP connection is identified by a 4-tuple: source address, source port, destination address, destination port. No two live connections may share all four. An L4 proxy that source-NATs toward a backend (NAT is Network Address Translation, rewriting addresses as packets pass through) gives every forwarded connection the same source address, leaving only 65,535 source ports to tell them apart, per (proxy IP, backend IP, backend port) combination. So 20 M / 65,535 ≈ 306 distinct tuples are needed. This is easy to miss: it shows up as connection failures at exactly 65 k on one proxy while every dashboard says the fleet is idle. Any of three fixes multiplies the tuple count: multiple backend listen ports, multiple proxy IPs, or direct server return, where the backend replies straight to the client instead of routing back through the proxy.

(d) Blast radius, the one that decides. The blast radius of a failure is how many users it takes down. Pick 200,000 connections per box and the fleet is 100 boxes; a box dying orphans 200,000 clients that all reconnect at once. The cost you would expect to dominate, the TLS handshake (Transport Layer Security, performed before any data flows), turns out to be cheap: ~1.5 ms of one core, so a 32-core box does ~21,000/s, and 200,000 handshakes spread over the 99 survivors is ~2,020 each, about a tenth of a second. Handshake CPU is not the problem; the session registry is. Every reconnect writes a registry row and triggers a presence transition, both far more expensive:

registry capacity                 100,000  ops/s   [assumed]
budget for reconnects, 10%        10,000   ops/s   [assumed]
jitter window needed              200,000 / 10,000   =  20  s

Reconnect jitter is not a guess; it is blast radius / op budget. 200,000 clients at 10,000 registry ops/s takes 20 seconds, so spread the reconnects over a 20-second window and the registry never notices. The form is derived; the magnitude is only as good as its two stated inputs. Halve the budget and the window doubles to 40 s. Jitter means each client waits a random delay drawn from that window before retrying; without it the whole herd retries in lockstep and one box’s death becomes a registry outage (the rate-limiter chapter derives that retry storm).

Landing the number: 100 boxes at 200 k connections each, reached from the failure domain, not from RAM. Everyday load is undramatic: at a mean connection lifetime of 1,800 s, 20 M / 1,800 ≈ 11,111 connects/s, and 11,111 x 1.5 ms ≈ 16.7 cores of handshake work across the whole fleet. Idle in steady state and saturated in a storm, the signature of a system sized by its failure mode.

Deep dive 2: transport — WebSocket, long polling, SSE

How bytes travel is a choice with one consequence that reshapes the design: a persistent connection makes the serving tier stateful, which creates the problem of finding which machine holds a given user’s socket.

• Long polling makes request/response imitate push. The client sends an ordinary request; the server holds it open without answering until it has something to say or a timeout expires; then it answers, and the client immediately sends another.
• SSE (Server-Sent Events) keeps one HTTP response open forever and streams text events down it. One-directional, server to client.
• WebSocket upgrades an HTTP request into a raw two-way socket both sides can write to at will (full duplex).

Why long polling loses. Every request carries a fresh set of HTTP headers (cookies, user agent, auth token) costing ~800 B, re-issued every 30 s. With 20 M clients that is 20 M / 30 ≈ 667,000 requests/s at 800 B, or ~533 MB/s of headers, against ~183 MB/s of actual message payload (1.83 M deliveries/s at 100 B). The headers cost 2.9x the messages they carry. Worse, between one poll completing and the next being established there is a ~50 ms gap with nowhere to write. At 667,000 new polls/s each lasting 0.05 s, ~33,000 clients are inside that gap at any instant. 0.17% of all clients are unreachable at any moment, by construction. WebSocket’s equivalent is zero, because the socket is always there.

Why SSE loses: it is one-directional. A chat client sends as often as it receives, so SSE needs a second channel (POST) for the send path, two transports and two failure modes adopted to avoid maintaining one.

The consequence: the serving tier becomes stateful

A stateless web tier lets any box serve any request (the scaling-up chapter). Here the socket for user B exists on exactly one box out of a hundred, so delivering to B means finding that box first, an instance of service discovery, the general problem of looking up where something currently lives.

The answer is a session registry: a table of user_id -> (gateway_id, device_id, expires_at). Each gateway writes a row on connect, with a TTL of twice the heartbeat so a dead machine’s row expires by itself. At 20 M x 64 B ≈ 1.28 GB and 1.83 M lookups/s (one per delivery) sharded 16 ways for ~114 k/s per shard, it is small and hot, a Redis-shaped problem (an in-memory key-value store whose contents can be rebuilt from the gateways if lost).

Two tempting alternatives fail:

• Every gateway subscribes to a message bus for every conversation. Then nobody has to ask where anybody is. But 200,000 users/gateway x 50 conversations = 10 M subscriptions/gateway, a billion fleet-wide, torn down and rebuilt on every redeploy. Rejected.
• Consistent hashing instead of a registry. Consistent hashing hashes both keys and machines onto one circular number line, so each key belongs to the machine next to it and adding a machine moves only a small slice (the consistent-hashing chapter). It answers where a user should be, not where they are, and the load balancer already chose the box at connect time. You can force them to agree by redirecting each connect to the machine the ring names, but that costs a round trip on every connect and creates hot spots.

Registry for locating sockets, consistent hashing for owning conversations. Different questions; giving the same answer to both is a mistake.

Deep dive 3: ordering, and what a sequence number buys

The obvious way to order messages (stamp each with the server’s clock and sort) fails at a measurable rate, and the per-conversation counter that replaces it buys more than ordering.

Why server timestamps fail. Clocks are read to the millisecond, so two messages in one conversation can land in the same millisecond and tie. Breaking ties by msg_id gives an order, deterministic but not necessarily the one anyone observed. The real problem is clock skew across gateways: two messages can arrive at two boxes, each stamping from its own clock. Those clocks are NTP-disciplined (the Network Time Protocol nudges each toward a reference) but not equal. A few milliseconds of residual disagreement is normal.

How often does that flip the order? With each host’s clock error about 10 ms, the error that matters is the difference of two clocks, whose standard deviation is 10 x sqrt(2) = 14.14 ms (variances add). A true 50 ms gap is then 50 / 14.14 = 3.5 standard deviations wide, and the normal distribution puts the chance of an inversion at that distance at ~0.0002, about 1 in 4,900. Scaled up, if 5% of messages arrive within 100 ms of the previous one in the same conversation (the rapid back-and-forth people actually notice), that is 1 B burst messages/day x 0.0002 = ~203,000 inverted message pairs a day, every one a bug report that cannot be reproduced. Tighter NTP shrinks the tail but never removes it, and the platform is large enough to find whatever is left.

Sorting by msg_id does not save you: a Snowflake-style id (a 64-bit id packing a timestamp, a machine number and a counter) puts the local clock in its high bits (the ID-generator chapter), so ordering by id reproduces exactly the skew you were escaping, in a form harder to see.

What seq buys

The fix is one monotonic counter per conversation (only ever increasing, never repeating) assigned by a single owner, the shard that owns that conv_id. Four things fall out, and only the first is ordering:

Gap detection is the underrated one. Without seq a client cannot distinguish “no new messages” from “a message was lost”, so its only recourse is to periodically re-download everything; with seq it notices the hole immediately and asks for exactly the hole.

Is the counter a bottleneck?

A per-conversation counter is a serialization point, operations handled strictly one at a time, normally where throughput dies. So price it: how many messages per second does a single conversation’s counter see?

The platform has 25 B memberships (500 M users x 50). Dividing by the mean members per conversation gives the conversation count. That mean is 4, not the 8.9 you get by splitting conversations 70/30, because the 70/30 is a split of traffic, and group threads are ~4.5x busier per thread, so 70% of the messages fit into ~91% of the conversations. That gives 6.25 B conversations, and 231,000 messages/s spread across them is 231,481 / 6.25e9 ≈ 0.000037 messages/s per conversation. Inverted, the average conversation gets one message every ~8 hours. The busiest realistic conversation is a few messages per second. The activity ratio is soft; the conclusion survives an order of magnitude either way (even the 8.9-member reading leaves the sequencer at 0.00008/s).

The serialization point is idle by construction. The contention it can face is bounded by one conversation’s traffic, never the platform’s, which is exactly why per-conversation is the right granularity to put a counter on.

Two alternatives lose. A global sequencer handles the throughput fine (the ID-generator chapter derives billions of ids per second) but imposes an order across conversations no one can perceive, and destroys gap detection because every client sees enormous holes where numbers went to other people’s conversations. Vector clocks (each participant keeps a counter, every message carries the full set, and comparing sets tells you which event came first; see the key-value store chapter) exist for the case where no single writer exists; a conversation has an obvious one.

Deep dive 4: 1:1 versus groups, and where the design changes

There is an exact group size at which the routing strategy must change, and the number comes from the size of the server fleet, not from anything about groups. Two questions get confused; separate them.

Storage fanout: never. One copy per recipient is 7.9x the bytes and 86.5 PB, to answer a query last_seq - last_read_seq already answers in constant time. Store the message once.

Socket fanout: always, but the strategy flips at a threshold. For a group of M members the sender’s gateway must get the message onto M-1 sockets. Two ways:

• Direct routing. Look each member up in the registry and send to their gateway. Cost per message: M lookups and up to M cross-gateway sends. No per-conversation infrastructure.
• Broadcast. Publish once to a per-conversation topic; every gateway holding at least one member gets one copy and fans out locally. Cost: G sends, where G is the number of gateways holding a member. Needs a live topic and a subscription per (gateway, conversation).

So the comparison turns on G. Members land on gateways independently (the balancer knows nothing about conversations), so with N = 100 gateways the expected number holding at least one member is:

G  =  N x (1 - (1 - 1/N)^M)

M = 25      100 x (1 - 0.99^25)    =  22.2    vs 25 direct    ->  1.1x
M = 100     100 x (1 - 0.99^100)   =  63.4    vs 100          ->  1.6x
M = 500     100 x (1 - 0.99^500)   =  99.3    vs 500          ->  5.0x
M = 5,000   100 x (1 - 0.99^5000)  =  100.0   vs 5,000        ->  50x

G can never exceed N. With only 100 gateways, a 5,000-member group is still only 100 gateways, so broadcast’s cost stops growing at 100 while direct routing keeps climbing with M. Below saturation the advantage is a small constant (1.1x at 25, 1.6x at 100), not enough to pay for a live topic and a subscription per (gateway, conversation) across 6.25 B conversations, the billion-subscription bill already rejected. Above saturation the advantage is M/N and grows without bound (5x at 500, 50x at 5,000). So the threshold is where G stops growing, where (1 - 1/N)^M falls to 0.01:

(1 - 1/100)^M  =  0.01     ->     M  =  ln(0.01) / ln(0.99)  =  458

The threshold is 458 members, set by the gateway count, not by groups. Halve the fleet to 50 and the threshold halves to ln(0.01)/ln(0.98) = 228.

What else changes above the threshold

Three things, all about work that scales with M:

• Receipts must be suppressed. In a 100 k-member channel where every member acks delivered and read, one message produces 200,000 return events. Collapse them into an aggregate (“seen by 4.2 k”) or turn them off.
• Presence must be suppressed, and worse: presence changes are continuous where messages are discrete, so there is no upper bound on how often they fire.
• Membership stops being a list you read. At 100 k members the broadcast topic is the member list.

Together these say something the routing math alone does not: a “group” and a “channel” are different systems that share an API, and the boundary is 458 members for this fleet. Product usually rounds it to 500 or 1,000 and caps groups there.

Deep dive 5: delivery semantics

What can “the message was delivered” mean? The appealing answer is provably unavailable, and the honest alternative has costs in duplicate messages, memory, and client code.

Exactly-once is not achievable

The protocol is three steps: the sender transmits, the receiver stores, the receiver sends back an ack. Now suppose the ack never arrives. The sender cannot distinguish two situations:

sequenceDiagram
    participant S as Sender
    participant R as Receiver
    S->>R: message
    Note over R: (a) lost before store, or<br/>(b) stored, then ack lost
    R--xS: ack never arrives
    Note over S: cannot tell (a) from (b),<br/>so must retry (at-least-once)

In (a) the sender must resend or the message is lost; in (b) resending creates a duplicate. Nothing the sender can observe tells it which world it is in, and adding another round trip only moves the ambiguity one step later. This is the two-generals problem: two armies who can only communicate by messengers that may be captured can never both become certain they agree. It is a theorem, not an engineering gap.

So there are two implementable choices: at-most-once (never retry, silent loss, unacceptable for chat) and at-least-once (retry until acked, duplicates, which the receiver can remove). Exactly-once is at-least-once plus deduplication at the receiver. Anyone who says “we do exactly-once” is describing at-least-once transport plus idempotent processing.

How many duplicates that means. The ack path is three hops (device -> gateway -> store -> back). At a 0.1% per-hop failure rate, the chance the ack is lost after the message was stored is ~0.3%, applied to all 1.58e11 daily deliveries: ~474 million duplicate deliveries a day. Dedup is not a refinement.

The dedup mechanism, both ends

Deduplication happens twice, and both ends have a price:

• Sender side, keyed on client_msg_id. The client generates a ULID before sending and reuses it on every retry. The server remembers (sender_id, client_msg_id) pairs it has seen; on a repeat it returns the original seq instead of assigning a new one, so a retry is indistinguishable from a first success. It only has to remember for as long as retries can arrive, a 300 s window at 231,000 sends/s and 24 B/entry is ~69 M x 24 B ≈ 1.67 GB of Redis, buying server-side idempotency for the whole platform.

• Receiver side, keyed on (conv_id, seq). The client keeps the last 1,000 sequence numbers per conversation. Holding one costs ~16 B (the 8 B seq plus the hash slot and pointer), so 50 conversations is 50 x 1,000 x 16 B = 800 KB, nothing on a phone, and it answers both of the client’s questions: have I already applied this? and am I missing anything?

The client-side inbox is one structure. Two lines in it are guards worth reading closely: highest starts at None, not 0, because 0 is a real sequence number and a truthiness test cannot tell “nothing applied yet” from “applied seq 0”; and applied is an OrderedDict, not a set, because the 1,000 is a bound and a set cannot evict its oldest member.

from collections import OrderedDict


class Inbox:
    """Client-side: idempotent apply, plus gap detection from the same state."""

    KEEP = 1_000

    def __init__(self) -> None:
        self.applied = OrderedDict()      # seq -> None, oldest first
        self.highest = None               # None, NOT 0 -- seq 0 is a real seq

    def apply(self, seq: int, body: str) -> str:
        if seq in self.applied:
            return "duplicate"                  # at-least-once made this common
        self.applied[seq] = None
        if len(self.applied) > self.KEEP:
            self.applied.popitem(last=False)    # evict the oldest, keep 1,000
        if self.highest is not None and seq > self.highest + 1:
            missing = list(range(self.highest + 1, seq))
            self.highest = seq
            return f"gap:{missing}"             # fetch exactly the hole
        self.highest = seq if self.highest is None else max(self.highest, seq)
        return "applied"


box = Inbox()
assert box.apply(41, "a") == "applied"
assert box.apply(41, "a") == "duplicate"      # dedup
assert box.apply(43, "c") == "gap:[42]"       # notices the hole
assert box.apply(42, "b") == "applied"        # fills it, no complaint

Applying 43 after 41 returns gap:[42], so the client fetches exactly the missing message; it then applies 42 without complaint, because gap detection is about noticing holes, not refusing out-of-order arrivals. The bound is real: after many applies the structure holds exactly 1,000 entries, and the cost of that is stated, not hidden. A redelivery older than 1,000 sequence numbers is applied twice. In the busiest realistic conversation (a few messages/s) 1,000 sequence numbers is ~333 seconds of history, just past the 300 s sender retry window, so retries expire before the memory does; in an ordinary conversation it covers years. KEEP is the dial.

Receipts, and why read must be a cursor

Implemented naively, each delivery generates a delivered and a read event, doubling 1.58e11 deliveries/day to 3.16e11 events, or ~3.66 M/s, 16x the message send rate, for two grey ticks. The fix is to make a receipt cover a range: one read event each time a conversation is opened, carrying the highest sequence seen, which implies everything below it is read. Users open the app ~15 times a day, so receipts drop from 3.66 M/s to the ~87,000 opens/s, a 42x reduction across both halves. delivered gets the same treatment: one acknowledgement per socket flush, covering a range. Read receipts are cursors, not events.

The offline queue that is not a queue

Most designs include a per-user mailbox holding messages that arrived while the user was disconnected. Price it: each user gets 316 deliveries/day and opens the app 15 times, so ~21 messages wait at a typical open, and 500 M x 21 x 100 B ≈ 1.05 TB if you assume everyone is sitting on a backlog at once, the honest worst case for a store you keep hot.

You should not build it. You already have a per-conversation log and a per-user cursor, so “what did I miss?” is a range scan from last_delivered_seq. The offline queue is a query, not a store, and it is the same query that powers scrolling back through history, so it is already written and tested. The one thing offline users genuinely need in addition is a wake-up, which goes out through the push services carrying no content.

Deep dive 6: presence, where the heartbeat interval comes from

One constant decides how expensive the online/offline indicator is (the heartbeat interval), and it is set by phone batteries and carrier equipment, not by how fresh the indicator needs to be. There are two costs: heartbeats coming in, and notifications going out when state changes.

Heartbeat cost is connections / interval, and connections is 20 M. Each connection sends one frame every h seconds purely to prove it is alive, so the rate is fixed by arithmetic, not user behaviour:

h = 30 s     20 M / 30    =  667,000  /s     ->  2.88x the entire chat write load
h = 180 s    20 M / 180   =  111,000  /s     ->  0.48x

At a 30-second heartbeat, presence is nearly three times the traffic of chat itself. The other side of the tradeoff is staleness: how long the indicator can keep claiming someone is online after they have gone. Do not declare a user offline on the first missed beat; wait for 2 consecutive misses. Since a user vanishes at a random point in the interval, detection averages 1.5h (45 s at h=30, 270 s at h=180).

QPS is queries per second. Duty cycle is the fraction of time the phone’s radio is powered up. A radio does not switch off the instant it finishes sending; it stays in a high-power state for a tail of ~10 seconds. So the duty cycle is that tail over the interval: 10/30 = 33% versus 10/180 = 5.6%. At h=10 the tail fills the interval and the radio never sleeps.

h is chosen by battery at one end and NAT at the other, not by staleness. The lower bound is battery: each heartbeat drags the radio awake, and h=30 keeps it awake a third of the time, arriving as one-star reviews, not a metric on any dashboard you own. The upper bound is the carrier’s NAT timeout: the same address translation the proxy performs above is what lets an operator put many subscribers behind one address, and it discards any mapping idle longer than some timeout, commonly 300 s. Past that the connection is silently half-open. Both sides believe they are connected and no bytes pass. So any interval near 300 s risks this, and you need real margin under it. Battery pushes up, NAT pushes down, and the window is roughly 120-240 s; 180 s sits in the middle.

So where does the green dot come from? Not heartbeats. At 180 s an indicator driven by heartbeats would be minutes behind. It comes from activity: any frame at all (a message, a receipt, a typing notification) refreshes presence, and the heartbeat is merely the floor for a client connected but doing nothing. Publish last_seen in coarse buckets (“active now”, “5 min ago”) so a slow-timer indicator never visibly contradicts itself.

Presence fanout is the larger half. Every transition must reach everyone watching that user. Naively, 500 M users flipping 10 times a day, each flip told to 20 contacts, is 1e11/day or ~1.16 M/s, 5x the message traffic. The fix is subscribe-on-view: send a transition only to the ~1.5 people who currently have that conversation open, dropping it to ~87,000/s, a 13x reduction that costs nothing because a presence indicator nobody is looking at has no value. On top of that, rate-limit transitions per user with a token bucket (one per 60 s, see the rate-limiter chapter) so a flapping connection (one repeatedly dropping as a phone moves between cell towers) cannot emit a hundred transitions a minute.

Bottlenecks and scaling

Every limit derived above lands in one table. Read it as an escalation path: “Binds at” is where the component stops coping, “First fix” is what you reach for, and “Then” is what you do when the first fix runs out.

LSM is a log-structured merge tree, a storage engine that turns random writes into sequential ones by buffering in memory and periodically merging sorted files to disk, which is why it suits a write-heavy message log (the database-internals chapter). Cold storage is cheaper, slower storage for data that is rarely read.

Geography. A conversation is owned by exactly one region, the region of the conversation, not the user. This follows directly from ordering: the sequencer must have a single owner, and an owner lives somewhere. A cross-region round trip is 70-150 ms, so a user travelling abroad pays it on every send. The alternative, multi-master sequencing where several regions assign numbers at once, requires a consensus protocol (an algorithm by which machines agree on one value despite failures) added to a problem that already has an obvious single writer. Pay the round trip instead.

Failure modes

For each row, “Blast radius” is how much of the platform notices, “Detection” is the signal, and “Mitigation” is what the design already does. No row introduces a new component.

The last row generalises to all eight. The message store is the single authoritative copy, and every client holds a cursor into it. So when a gateway dies, when the registry is lost, when the push provider is down, the message is still in the log and the cursor still says where the client got to. Every failure degrades to “delivered late”, not “lost”. Design the system so the only permanent failure mode is a lost socket, because a lost socket is just a reconnect.

Alternatives rejected

Conclusion

Chat is a routing problem wearing the costume of a storage problem. The messages are small and the volume is ordinary; the whole difficulty is that the destination is one socket on one machine, and that machine can die. Three decisions carry the design:

• A persistent WebSocket makes the serving tier stateful. That forces a session registry to find which gateway holds a user’s socket, and it is what separates chat from every request/response system.
• Write the message once, into the conversation, and order it with a per-conversation counter. The counter is idle by construction (one message every ~8 hours on average), and it buys total order, gap detection, idempotency, and O(1) read cursors, none of which timestamps can give.
• At-least-once delivery plus receiver dedup on (conv_id, seq) is the only honest guarantee. Exactly-once is a theorem away, and this system produces hundreds of millions of duplicates a day, so dedup is a mainline path.

Two subsystems that look trivial dominate the cost if you get one constant wrong: the connection tier is sized by its blast radius (100 boxes, not the 3 that memory suggests), and presence is sized by the heartbeat interval (180 s, set by battery and the carrier NAT timeout). Both are examples of the same lesson: the resource you instinctively count is rarely the one that binds.

One line to remember: chat is a routing problem, so build for the destination being a single socket on a machine that can die, and let one authoritative log plus one cursor per client turn every failure into a reconnect.

Further reading

• RFC 6455, The WebSocket Protocol: the framing and upgrade handshake behind the transport chosen here.
• RFC 9562, Universally Unique IDentifiers (UUIDs): defines UUIDv7, the time-sortable id used for client_msg_id; the ULID spec (github.com/ulid/spec) is the closely related alternative.
• Martin Kleppmann, Designing Data-Intensive Applications: ordering, exactly-once semantics, and consensus, treated at length in chapters 8 and 9.
• The Two Generals Problem: the classic impossibility result behind at-least-once delivery.
• Rick Reed, “Scaling to Millions of Simultaneous Connections” (Erlang Factory, 2012): a production account of the connection-tier problem at WhatsApp scale.
• Discord Engineering, “How Discord Stores Trillions of Messages”: a real per-conversation, shard-by-channel message store in production.

Summary

Related: the news-feed chapter is the same push/pull question without a real-time deadline; the estimation chapter is where the 20 M connection estimate and its trap come from; the rate-limiter chapter supplies the retry-storm and token-bucket machinery; the consistent-hashing chapter owns conversations for the sequencer; the ID-generator chapter supplies client_msg_id.