12 — Design A Chat System

A real-time chat backend runs from the network connection a phone holds open down to the counter that decides which of two messages happened first.

This chapter covers how to size the connection tier from first principles, why a persistent connection beats polling, the exact group size at which the message-routing strategy has to change, and 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 a question, the server answers it, and the server then forgets the client completely until the next question. Any server can answer any question, because no server is holding anything.

A chat system is the first one where the server has to remember where you are.

That single property is a long-lived, individually addressable connection that makes the serving tier stateful: the server keeps per-user information 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 from here to the end, so fix them now.

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

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

1. Framing: what decision, and what breaks

Three decisions determine every other choice in this chapter, and five production failures follow when they are made badly. Here are the three, in the order they constrain each other:

1. What is the transport? The transport is the mechanism by which bytes travel between client and server. It decides whether the serving tier is stateless — any machine can handle any request, because none of them remembers anything — or stateful, where one particular machine holds your connection and only that machine can reach you. Everything downstream depends on this answer (Deep dive 2 transport websocket long polling sse).
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 (Back of the envelope).
3. What orders the messages? Wall-clock timestamps do not survive being written by several machines at once, and the fix is cheaper than candidates expect (Deep dive 3 ordering and what a sequence number buys).

What each decision breaks when you get it wrong

The table below is the failure list. Read it as five bug reports and their causes: the first row and the last two come from decision 1 (a stateful tier you then have to search), the second from decision 3, and the fifth from decision 2.

Two words in it need definitions first. Presence means the online/offline/last-seen indicator next to a contact’s name. Fanout means the work of getting one message from one sender out to many recipients.

Three terms from that table, defined once and used everywhere after:

• Gateway — a server machine 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 with clocks 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.

2. Requirements

Three things need pinning down before any arithmetic: what the system must do, what performance it must hit, and the assumptions underneath both, separating those that merely change the machine count from those that would force a different architecture entirely.

Functional

The product features the system owes its users are:

• 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 — the small status markers that tell a sender the message left their device (sent), reached the recipient’s device (delivered), and was displayed to the recipient (read).
• Presence: whether a contact is online right now, and when they were last seen if not.
• Message history that can be scrolled backwards in pages, on every device the user owns.

Non-functional — these decide the design

These are the performance and correctness targets. Two pieces of shorthand appear in the table. p95 means the 95th percentile: the value that 95 out of every 100 requests come in under, so “p95 < 500 ms” allows the slowest 5% to be worse. 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 same sequence — not merely a sequence that is plausible, but the identical one. Dedup is short for deduplication: recognising that a message you already have has arrived a second time, and dropping the copy. A cursor is a single number that records how far through a conversation a device or an account has got.

Assumptions, and which ones are load-bearing

Every number in this chapter rests on assumptions, and it is worth separating the two kinds.

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

The table lists them in that order: load-bearing first, then soft. The third column is the test — it says what you would have to redesign if the assumption turned out to be false. If the answer is “buy more machines”, the assumption is soft.

Daily active users (DAU) means distinct people who use the product on a given day. The single most load-bearing item is the second one: the entire chapter’s ordering story is a consequence of a conversation having one owner, and if conversations must accept writes in two regions at once, Deep dive 3 ordering and what a sequence number buys has to be replaced rather than tuned.

3. Back of the envelope

The rest of the chapter uses four numbers, all derived from the product assumptions:

1. How many connections are open at once.
2. How many messages per second arrive.
3. How many individual deliveries those messages generate.
4. How many bytes they occupy.

Connections and message rate

Two inputs come straight from the assumptions table: 500 M daily active users, and 40 messages sent per user per day. Everything below is those two numbers multiplied and divided.

The constant 86,400 on the third line is the number of seconds in a day — 60 x 60 x 24 — and it is how any per-day figure becomes a per-second one.

DAU                        500,000,000
concurrent share           4 %
concurrent connections     500,000,000 x 0.04       =  20,000,000
messages sent/user/day     40
messages/day               500,000,000 x 40         =  20,000,000,000
per second                 20,000,000,000 / 86,400  =  231,481
peak at 2.5x               231,481 x 2.5            =  578,703

Two lines in that block need comment.

The 20 M concurrent connections is the same figure Six worked estimations sizes, so its conclusion carries over unchanged; Deep dive 1 the connection tier and why 3 boxes is 100 extends it rather than restating it.

The 2.5x on the last line is a stated peak multiplier, not a derived one. 231,481/s is the average second. Traffic is not flat across a day, so the busiest second carries more, and 2.5x is the assumption about how much more (The estimation checklist). Nothing later in this chapter depends on the peak figure; the mechanisms are sized from the average, and from how many users a single machine failure takes down (Deep dive 1 the connection tier and why 3 boxes is 100).

Deliveries, which is the number that actually matters

Messages sent is not the load. One message sent into a group has to be handed to every member, so deliveries — individual handoffs to individual recipients — outnumber sends by whatever the mean recipient count is.

To find that multiplier, split traffic by conversation type. A 1:1 message has exactly 1 recipient. A group message goes to everyone except the sender, so a mean group of 25 members means 24 recipients. Weight each by its share of traffic:

1:1 share      70 %,  1 recipient
group share    30 %,  mean 25 members  ->  24 recipients
recipients per message   0.70 x 1 + 0.30 x 24   =  7.9
deliveries/day           20,000,000,000 x 7.9   =  158,000,000,000
per second               158,000,000,000 / 86,400  =  1,828,704

1.83 M deliveries/s is the number to carry forward. It is 7.9x the send rate, and it is what the session registry, the receipts system and the fanout path are all sized against.

Storage, and the alternative that costs 7.9x

Now price the bytes. Add up one stored message row, field by field, then multiply out by messages per day, by copies, and by retention.

A replica is a complete additional copy of the data on another machine, kept so that losing a machine does not lose the data. Three replicas is the standard default, so the byte total is three times the raw one.

msg_id       8 B     (ch 07 k-sortable id)
conv_id      8 B
sender_id    8 B
seq          8 B     (per-conversation sequence number, §9)
created_at   8 B     (server receive time, ms)
flags        4 B     (type, edited, deleted, encryption scheme)
body        56 B     (mean; short messages dominate, media is a URL)
                  ------
                   100 B

20,000,000,000 x 100                 =  2,000,000,000,000    B  =  2 TB/day
x 3 replicas                         =  6,000,000,000,000    B  =  6 TB/day
x 1,825 days (5 years)               =  10,950,000,000,000,000 B  =  11.0 PB

The 1,825 is five years in days: 365 x 5. The body field is 56 B because most messages are one short line of text, and a photo is stored elsewhere and appears in the row only as a URL — that is the load-bearing “small text messages” assumption from Assumptions and which ones are load bearing doing its work.

Eleven petabytes is a large but entirely ordinary number, and that is the finding. A petabyte (PB) is a thousand terabytes. Eleven of them is a rack of disks, not a research project. Chat is not a storage-bound system.

Now price the alternative, in which the server writes a separate copy of the message for each recipient rather than one copy in the conversation. The only change is multiplying the daily bytes by the 7.9 recipients per message computed above:

2,000,000,000,000 x 7.9              =  15,800,000,000,000  B/day
x 3 x 1,825                          =  86,505,000,000,000,000  B  =  86.5 PB

Storing per-recipient costs 7.9x, 75 extra petabytes, to buy a query a cursor already answers (Data model). Write the message once, into the conversation.

4. API sketch

Here are the exact frames a client sends and receives, so the input and output of the system are concrete. An API (application programming interface) is the set of calls one program offers to another. The first block below is the persistent connection; the rest are ordinary web requests (REST is the conventional style in which each URL names a resource and the HTTP verb names the action) used for history and as a fallback when the socket is unavailable.

A note on notation. WS marks the WebSocket endpoint — WebSocket is the protocol that upgrades an ordinary web request into a permanently open two-way socket, and it is the subject of Deep dive 2 transport websocket long polling sse. -> marks a frame the client sends; <- marks a frame the server pushes down. hb is a heartbeat, a tiny frame sent on a timer purely to prove the connection is still 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

Read the six WebSocket frames as one conversation:

• send is the only thing the client pushes up. It carries the conversation, the body, and an id the client made up.
• ack — short for acknowledgement — comes back to the sender alone. It says “stored, and here is the sequence number I gave it” — the sender matches it to its own client_msg_id.
• msg is the same message arriving at everyone else.
• receipt reports that some user reached delivered or read up to sequence 4812.
• presence reports someone going online or offline.
• hb is the heartbeat, going up on a timer whether or not anything else is happening.

The three details a reviewer looks for

All three are about making a retry safe.

1. client_msg_id is generated by the client, before the send. It is the idempotency key. Idempotent means an operation can be applied twice and the second application changes nothing; the key is what lets the server recognise a second copy as a copy. Without it, at-least-once delivery is unimplementable (Deep dive 5 delivery semantics) — the server would have no way to tell a retry from a genuine second message with the same text.

A ULID — a Universally Unique Lexicographically Sortable Identifier — or a UUIDv7 (Uuidv7 and ulid the modern answer priced) is the right shape of identifier. Both are 128-bit random-looking ids with a timestamp in the high bits, so they are unique without any coordination between clients and sort into roughly the order they were created.

2. read takes a seq, not a message id. seq is the per-conversation sequence number introduced in Deep dive 3 ordering and what a sequence number buys. Because it counts upwards, 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 rather than one question per conversation. At 50 conversations that is 50 mobile round trips of about 50 ms each that never happen. A round trip (RTT, round-trip time) is one message out to the server and its answer back.

5. Data model

The system stores five tables, and the one shaped one row per membership is what makes unread counts free.

Two pieces of notation in the block below. PK marks the primary key, the column or columns that uniquely identify a row. TTL is time-to-live, an expiry after which a row deletes itself with no one having to remember to delete it.

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

Taking them one at a time:

• conversations is one row per chat thread. last_seq is the highest sequence number handed out in that thread so far — the counter Deep dive 3 ordering and what a sequence number buys is built around.
• messages holds the bodies, and it is the only place a body exists. Its key is (conv_id, seq), so a message is addressed by which conversation and how far along rather than by a global id.
• members says who is in a thread. joined_seq records where they joined, which is what stops a new member from reading history that predates them; notify_pref is their per-thread notification setting.
• user_index is the same membership seen from the user’s side, and it holds the two cursors: last_read_seq (how far this account has read) and last_delivered_seq (how far this device has been handed). It is sharded by user_id, so “everything about me” is one machine’s worth of rows.
• sessions is the session registry — which gateway is currently holding 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 whole 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. Price the entire table:

500,000,000 users x 50 conversations x 64 B  =  1,600,000,000,000  B  =  1.6 TB

1.6 TB holds 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.

That matters because it removes the usual reason to build the expensive thing. Designs that materialize per-recipient message rows — that is, write out the answer in advance as real stored rows rather than compute it on demand — are usually doing it to make this one query fast. It was already constant-time, and Back of the envelope priced the alternative at 86.5 PB.

Why the clustering matters

Clustering messages by (conv_id, seq) means the rows of one conversation are physically stored next to each other on disk, in sequence order.

So paging back through history is 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 (Composite covering and hash indexes).

6. High-level architecture

The whole system fits on one page, followed by the path of a single message through it, so that every box and arrow has a sentence attached before the deep dives start.

In the diagram, the message flows top to bottom, from Client A down to a socket somewhere. The two orange diamonds are the only branches, and they ask two unrelated questions: one about the conversation, one about a single recipient. The number 458 inside the first diamond is derived in Deep dive 4 11 versus groups and where the design changes. The dotted lines at the bottom 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<br/>one owner per conv_id<br/>seq = last_seq + 1"]
    SEQ --> MSG[("Message store<br/>sharded by conv_id<br/>clustered by seq")]
    SEQ --> ROUT{"member_count<br/>above 458?"}

    ROUT -->|"no · direct routing"| REG
    ROUT -->|"yes · broadcast"| BUS["Per-conversation topic<br/>one copy per gateway"]
    REG --> SOCK{"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"]

    style SEQ fill:#1d3557,color:#fff
    style ROUT fill:#bc6c25,color:#fff
    style SOCK fill:#bc6c25,color:#fff
    style REG fill:#2d6a4f,color:#fff
    style PRES fill:#9d0208,color:#fff

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 its whole life, but the same user’s second device may land on any other machine.

The load balancer spreads sockets across the gateway fleet. Gateway 1 in the picture is one such box holding 200 k sockets; Gateway 2 … 100 are the rest of the stateful tier. On connect, each gateway writes a row into the session registry — the table that maps a user to the gateway currently holding their socket.

Step 2 — the message is checked and numbered. The send frame reaches the chat service, which authenticates the sender and performs a membership check: is this user actually a member of this conversation?

From there it goes to the sequencer, the single owner of that conv_id. The sequencer stamps the message with seq = last_seq + 1 and writes it to the message store, sharded by conv_id and clustered by seq.

Step 3 — the first diamond: how should this be routed? This question is about the conversation, and it has exactly two answers.

• member_count above 458: publish one copy to a per-conversation topic and let every gateway holding a member pick it up.
• member_count at or below 458: the sequencer looks each member up in the session registry and sends to them directly.

Step 4 — the second diamond: is this one recipient reachable right now? This question is about one member at one instant, which is why it is a separate box.

• Socket open: write the bytes onto B’s open connection, then record that it happened by advancing last_delivered_seq in user_index for that member.
• Socket closed: there is nothing to write to, so 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. That service is rate limited by a token bucket — a counter that refills at a fixed rate and only lets an event through if a token is available — and it pushes the resulting online/offline transitions out only to watchers who have the conversation open on screen.

A note on the colours

The palette here is chapter-local and deliberately not chapter 01’s. There, blue marks the authoritative copy of the data, green marks anything that takes load off the request path, orange marks a rung forced by something other than throughput, and red marks the step you cannot undo.

Here the same colours index this chapter’s deep dives instead of classifying components:

• Blue — the ordering fix (Deep dive 3 ordering and what a sequence number buys).
• Orange — the two routing decisions: the group threshold (Deep dive 4 11 versus groups and where the design changes), and the online/offline branch that The offline queue that is not a queue turns into a query rather than a mailbox.
• Green — the stateful-tier fix (Deep dive 2 transport websocket long polling sse).
• Red — the thing that quietly costs more than the chat itself (Deep dive 6 presence where the heartbeat interval comes from).

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

7. 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 different resources each impose their own floor on the number of machines. They disagree with each other by a factor of five, and the largest floor wins, because a fleet has to satisfy all four at once.

Start from the memory answer. Holding 20 M connections at roughly 10 KB of kernel state each is 200 GB, about three machines’ worth of memory (Six worked estimations derives exactly this). Three machines is the wrong answer, because memory is not the binding resource, the one that runs out first. The rest of this section is the arithmetic behind each resource that actually binds.

(a) Memory, if the socket buffers are not tuned

The kernel is the core of the operating system. For every socket it reserves two buffers: a receive buffer holding bytes that have arrived but not yet been read by the application, and a send buffer holding bytes written by the application but not yet put on the wire.

The 10 KB figure above is the steady state for an autotuned socket — one whose buffers the kernel shrinks to fit the traffic actually flowing — carrying 100 B messages. But the kernel’s ceilings for those buffers are much larger: a 128 KiB receive buffer and a 16 KiB send buffer. A traffic burst can drive every socket toward those ceilings at once.

Kernel limits are powers of two, so keep them in binary units (128 KiB = 131,072 B, 16 KiB = 16,384 B) and convert to decimal once, at the end:

per socket, untuned       131,072 + 16,384       =  147,456  B  (144 KiB)
20,000,000 x 147,456                             =  2,949,120,000,000  B  =  2.95 TB
2,949,120,000,000 / 64,000,000,000 per box       =  46.1  ->  47  boxes

The last line divides by 64 GB, one box’s RAM, and rounds up because a partial box does not exist.

Tuning tcp_rmem and tcp_wmem down — the two kernel settings that cap those receive and send buffers — is what makes the 10 KB figure true. Untuned, a burst needs 47 boxes for memory alone.

The number to remember is not 10 KB. It is that the per-connection footprint is a configuration decision spanning roughly 14x, from 10 KB to 144 KiB, and the end you land on is a choice.

(b) File descriptors

A file descriptor is the small integer handle the operating system gives a process for each thing it has open — every file, and every socket. The kernel caps how many one process may hold at once.

That cap, fs.nr_open, is practically 1,048,576. It is a power of two, so divide by it directly rather than rounding it to a million first:

20,000,000 / 1,048,576    =  19.1   ->  20  boxes

So 20 boxes is a hard floor, assuming one process per box. Running several processes per box raises it.

(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, the rewriting of addresses as packets pass through a middlebox — rewrites the client’s address to its own, so every connection it forwards has the same source address. That leaves only the 65,535 source ports to tell those connections apart — and that budget is per (proxy IP, backend IP, backend port) combination:

20,000,000 / 65,535       =  305.2   ->  306  distinct proxy/backend tuples

Read that result as: the fleet needs at least 306 distinct (proxy IP, backend IP, backend port) combinations, however you assemble them. Fewer, and some connections have no port left to be given.

This constraint 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.

Three fixes, any of which multiplies the tuple count: give the backend multiple listen ports, give the proxy multiple IP addresses, or use direct server return, where the backend replies straight to the client instead of routing the response back through the proxy.

(d) Blast radius, which is the one that decides

The blast radius of a failure is how many users it takes down with it. Pick C connections per box, and a box dying means C clients simultaneously discover their socket is gone and all reconnect at once.

Start with the cost you would expect to dominate: the encryption handshake. TLS is Transport Layer Security, which every connection performs before it can carry data.

at C = 200,000        20,000,000 / 200,000   =  100  boxes
one box dies          200,000 clients reconnect at once
TLS 1.3 handshake     ~1.5 ms of CPU; a 32-core box does 32 / 0.0015  =  21,333 /s
spread over 99 boxes  200,000 / 99           =  2,020  per box  ->  0.1 s

The third line reads: one handshake costs 1.5 ms of one core, so 32 cores get through 32 / 0.0015 = 21,333 handshakes a second. The fourth spreads the 200 k orphaned clients over the 99 surviving boxes, giving 2,020 handshakes each, which at 21,333/s takes about a tenth of a second.

A tenth of a second of processor time is nothing. Handshake CPU is not the problem — the session registry is.

Every reconnect does two things far more expensive than a handshake: it writes a row into the session registry, and it triggers a presence transition that has to be fanned out to watchers.

registry capacity                 100,000  ops/s        [CAPACITY, assumed]
budget for reconnects, 10%        10,000   ops/s        [assumed share]
jitter window needed              200,000 / 10,000   =  20  s
presence pushes in the burst      200,000 x 20 watchers  =  4,000,000

Reconnect jitter is not a guess; it is blast radius / op budget. 200,000 clients to re-register, at 10,000 registry operations a second, takes 20 seconds — so spread the reconnects over 20 seconds and the registry never notices.

Two halves of that sentence are earned differently by the arithmetic:

• The form is derived. A jitter window is a blast radius divided by the operations per second you are willing to spend on it.
• The magnitude, 20 seconds, is only as good as its two inputs, and neither is derived here. 100,000 ops/s is a stated capacity for the registry, and 10% is a stated share of it for reconnects; both sit in the assumptions table (Assumptions and which ones are load bearing). Halve the budget and the window doubles to 40 s. The expression does not change.

Jitter means each client waits a random delay, drawn from that 20-second window, before trying again. Without it the whole herd retries in lockstep on a fixed backoff (a fixed waiting period before a retry) and one box’s death becomes a registry outage (The retry storm derived).

Landing the number

100 boxes at 200 k connections each. That is inside the 40-200 range ch 02 arrives at, and it was reached from the failure domain rather than from RAM.

Everyday connection load, as opposed to storm load, is undramatic:

mean connection lifetime  1,800 s
connects/s                20,000,000 / 1,800    =  11,111
handshake CPU             11,111 x 0.0015       =  16.7  cores, fleet-wide

The second line uses the fact that if 20 M connections each last 1,800 s on average, then in steady state 20 M of them must be replaced every 1,800 s — so 20,000,000 / 1,800 = 11,111 new connections a second. Each costs 1.5 ms of a core, giving 16.7 cores of handshake work across the entire fleet.

Sixteen cores across a hundred boxes. The connection tier is idle in steady state and saturated in a storm, which is the signature of a system sized by its failure mode.

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

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

The three candidates

Glossed before they are compared:

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

The table compares them on the six things that matter for chat. The row to look at first is the last one: the verdict is decided by the second row (per-message overhead) and the first (direction).

Why long polling loses, in numbers

The table asserts it; here is the arithmetic.

Every long-polling request carries a fresh set of HTTP headers — cookies, user agent, auth token, the lot — costing about 800 B. Each client re-issues a request every 30 s, so with 20 M clients:

new requests/s        20,000,000 / 30        =  666,667
header bytes/s        666,667 x 800          =  533,333,600  B/s
message bytes/s       1,828,704 x 100        =  182,870,400  B/s
overhead ratio        533333600 / 182870400  =  2.92

Line 3 is the useful payload for comparison: 1.83 M deliveries a second (Back of the envelope) at 100 B each.

The HTTP headers cost 2.9x the messages they carry.

The cost is not only bytes. Between one poll completing and the next one being established there is a window during which the server has nowhere to write, and that window is roughly one mobile round trip:

reconnect gap         50 ms
clients in the gap    666,667 x 0.05         =  33,333
share of the fleet    33333 / 20000000       =  0.00167

Line 2 asks how many clients are inside that 50 ms gap at any instant: 666,667 clients per second start a new gap, and each gap lasts 0.05 s, so 33,333 of them are in one right now.

0.17% of all clients are unreachable at any instant, permanently, by construction. Messages to them wait up to a full round trip before there is even a socket to write to. WebSocket’s equivalent number is zero, because the socket is always there.

Server-Sent Events loses for a different reason: it is one-directional. A chat client sends as often as it receives, so SSE needs a second channel — ordinary POST requests — for the send path. That is two transports and two failure modes adopted in order to avoid maintaining one.

The consequence: the serving tier becomes stateful

Choosing WebSocket is what sets up the whole rest of the chapter.

A stateless web tier lets any box serve any request, because no box holds anything the next request needs (ch 01). Here, the socket for user B exists on exactly one box out of a hundred. Delivering to B means finding that box first.

That is an instance of service discovery — the general problem of looking up where something currently lives.

The session registry, and its size

The answer is a session registry: a table of user_id -> (gateway_id, device_id, expires_at).

Each gateway writes a row when a client connects. The row carries a time-to-live of twice the heartbeat interval, so a row belonging to a machine that died expires by itself rather than pointing at a corpse. Price it:

entries               20,000,000
bytes/entry           8 user + 4 gateway + 8 device + 4 expiry + 40 overhead  =  64
size                  20,000,000 x 64        =  1,280,000,000  B  =  1.28 GB
lookups/s             1,828,704              (one per delivery, §3)
sharded 16 ways       1828704 / 16           =  114,294  /s per shard

The 40 B of “overhead” on line 2 is the hash-table bookkeeping any key-value store adds per entry — pointers and slot metadata — and it dwarfs the 24 B of real data, which is normal at this row size.

1.28 GB and 114 k operations per second per shard: the registry is small and hot, which is exactly a Redis-shaped problem — an in-memory key-value store, fast and small, whose contents can be rebuilt from the gateways if lost.

The alternative: no lookup at all

The obvious way to delete the lookup is to make every gateway subscribe to a message bus — a shared broker that delivers each published message to everyone who registered interest in that topic — for every conversation any of its users belong to. Then nobody has to ask where anybody is.

It does not survive its own arithmetic:

users per gateway     200,000
conversations each    50
subscriptions/gateway 200,000 x 50   =  10,000,000
across 100 gateways   10000000 x 100 =  1,000,000,000

A billion active subscriptions in a broker, all torn down and re-established every time the fleet is redeployed. Rejected.

Why not 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 sitting next to it on the circle, and adding or removing a machine moves only a small slice of keys.

It is the right tool for deciding which machine owns a conversation. It is the wrong tool here, and the reason is a single word: a hash tells you where the user should be, not where they are. The load balancer, which knows nothing about your hash ring, already chose the box at connect time.

You can force the two to agree by redirecting each new connection to whichever machine the ring says owns that user (Deep dive). That does remove the registry entirely. It costs one extra round trip on every connect, and it creates a hot spot whenever a popular region happens to hash together.

Registry for locating sockets, consistent hashing for owning conversations. They are different questions, and giving the same answer to both is a mistake.

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

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

9.1 Why server timestamps are insufficient

Three failures, in increasing order of how much they hurt.

Failure 1: ties

Server clocks are read to the millisecond. Two messages in the same conversation can easily land inside the same millisecond and so carry the identical created_at.

Breaking the tie by msg_id gives you an order. It is deterministic — everyone who sorts the same rows gets the same answer — and stable across re-sorts. It is just not necessarily the order either participant actually observed.

Failure 2: clock skew across gateways

This is the real one.

Two messages in one conversation can arrive at two different gateway boxes, each stamping the message from its own clock. Those clocks are NTP-disciplined — the Network Time Protocol continuously nudges each machine’s clock toward a reference — but discipline is not equality. A few milliseconds of residual disagreement is normal.

Here is the question to answer: if message A really was sent 50 ms before message B, how often do their two timestamps come out the wrong way round?

Work it in four steps. Assume each host’s clock error is about 10 ms.

Step 1 — the error that matters is the difference of two clocks, not one. Two independent errors of 10 ms each do not add to 20 ms; their variances add, so the standard deviation of the difference is 10 x sqrt(2) = 14.14 ms. sigma is the standard deviation, meaning the typical size of that disagreement.

Step 2 — the inversion condition. The order flips when the clock difference is bigger than, and opposite in sign to, the true 50 ms gap between the messages.

Step 3 — express the gap in standard deviations. That count is z: 50 / 14.14 = 3.536. The true gap is 3.5 sigmas wide.

Step 4 — turn z into a probability. Phi is the normal distribution’s cumulative function, which answers “what fraction of the bell curve lies below this many sigmas?” Phi(-3.536) = 0.000203.

skew of the difference of two hosts   10 x 1.4142   =  14.14  ms
true gap between the two messages                   =  50     ms
z                                     50 / 14.14    =  3.536
P(order inverted)  =  Phi(-3.536)                   =  0.000203

That is about 1 in 4,900, which sounds ignorable. So scale it up to the platform.

Assume 5% of messages arrive within 100 ms of the previous one in the same conversation — the rapid back-and-forth that is most of what people actually notice going wrong:

burst messages/day    20,000,000,000 x 0.05    =  1,000,000,000
inverted pairs/day    1000000000 x 0.000203    =  203,000

Two hundred thousand inverted message pairs a day, and every one is a bug report that cannot be reproduced.

The unit is pairs, not conversations. The derivation multiplies burst messages by the per-pair inversion probability, so it counts adjacent messages that swap; how many distinct conversations those land in is a different and unasked question.

No amount of NTP tightening removes it. Tighter synchronisation shrinks sigma, which moves the tail inward — but the tail does not vanish, and the platform is large enough to find whatever is left of it.

Failure 3: sorting by id does not save you

The natural next idea is to sort by msg_id instead of by timestamp. It does not help.

A Snowflake-style id — the widely-copied scheme in which a 64-bit id packs a timestamp, a machine number and a counter — is k-sortable, meaning ids sort into creation order only to within some window. Here that window is a millisecond.

More to the point, its high bits are the local clock (Data model the 64 bit layout derived). Ordering by id reproduces exactly the skew you were trying to escape, in a form that is harder to see.

9.2 What seq buys

The fix is one counter per conversation, and ordering is only the first of four things it delivers.

Give each conversation a monotonic counter — one that only ever increases, never repeats and never goes backwards — assigned by a single owner, namely the shard that owns that conv_id.

Four things fall out, and only the first is ordering. Read the right-hand column as “what you would have had to do without seq”:

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

9.3 Pricing the serialization point

The obvious objection is that a per-conversation counter is a serialization point — a place where operations must be handled strictly one at a time, which is normally where throughput goes to die.

So price it. The question is: how many messages per second does a single conversation’s counter actually see?

To answer that you need the number of conversations, which needs the mean number of members per conversation, which is where the arithmetic starts:

memberships           500,000,000 x 50         =  25,000,000,000
mean members/conv     0.913 x 2 + 0.087 x 25   =  4.0
conversations         25,000,000,000 / 4       =  6,250,000,000
messages/s                                        231,481
per conversation      231481 / 6250000000      =  0.000037  /s

Line 1 counts memberships, not conversations: 500 M users each in 50 conversations gives 25 B (user, conversation) pairs. Line 3 converts memberships to conversations by dividing by the mean members each conversation has — because a conversation with 4 members consumes 4 memberships.

That denominator on line 2 needs defending, because the obvious reading of Assumptions and which ones are load bearing gives a different number.

Splitting conversations 70/30 would give 0.7 x 2 + 0.3 x 25 = 8.9 members per conversation and only 2.8 B conversations. But the 70/30 in §2 is a split of traffic, not of conversation count. Group threads are busier per thread than 1:1 threads — about 4.5x busier here — and that is what lets 70% of the messages fit into 91% of the conversations:

1:1     0.913 x 6,250,000,000  =  5,707,000,000 convs, 0.70 x 2e10 msgs  ->  2.5 msg/conv/day
group   0.087 x 6,250,000,000  =    543,000,000 convs, 0.30 x 2e10 msgs  ->   11 msg/conv/day

Read each line as: this share of the 6.25 B conversations, carrying this share of the 20 B daily messages, works out to this many messages per conversation per day. The two right-hand numbers are the 4.5x, divided before they were rounded for display: 11.04 / 2.45 = 4.5.

That 4.5x activity ratio is an assumption, and it sits in the assumptions table with the rest (Assumptions and which ones are load bearing). It is soft. It moves the conversation count and therefore the per-conversation rate, and the conclusion here survives anything within an order of magnitude of it — even the 8.9-member reading leaves the sequencer at 0.00008 messages per second per conversation.

The busiest realistic conversation is a few messages per second. The average conversation gets one message every eight hours — invert the rate to see it: 1 / 0.000037 = 27,000 seconds, which is 7.5 hours, rounded to eight everywhere else in this chapter.

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

9.4 Two alternatives, and why each loses

A global sequencer would handle the throughput perfectly well; ch 07 derives 4.2 billion ids per second. It loses for two reasons that have nothing to do with throughput. It imposes an order across conversations that no human being can perceive. And it destroys gap detection: every client would see enormous holes in its numbering, because the missing numbers went to other people’s conversations.

Vector clocks are the general answer to ordering events without a coordinator. Each participant keeps a counter, every message carries the full set of counters, and comparing two sets tells you whether one event definitely came before the other or whether they are concurrent (Vector clocks and the sibling nobody wants).

They are the wrong tool here for one reason: they exist for the case where no single writer exists, and a conversation has an obvious one.

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

There is an exact group size at which the routing strategy has to change, and the number comes from the size of the server fleet rather than from anything about groups.

Two questions get confused here, so separate them. Both are about fanout, but one is about bytes on disk and the other is about network sends.

Storage fanout: never. Back of the envelope prices it — one copy per recipient is 7.9x the bytes and 86.5 PB, and it buys a query that last_seq - last_read_seq already answers in constant time. Store the message once, in the conversation.

Socket fanout: always, but the routing strategy flips at a threshold you can derive.

For a group of M members, the sender’s gateway must get the message onto M-1 other sockets. There are two ways to do that:

• Direct routing. Look up each member in the session registry, then send to whichever gateway holds them. Cost per message: M registry lookups and up to M cross-gateway sends. Needs no per-conversation infrastructure at all.
• Broadcast. Publish once to a per-conversation topic; every gateway holding at least one member receives one copy and fans out to its own sockets locally. Cost per message: G sends, where G is the number of gateways holding at least one member. Needs a live topic per conversation, and a subscription per (gateway, conversation) pair.

So the comparison turns on G — how many distinct gateways M members happen to be spread across.

Deriving G

Members land on gateways independently of each other, because the load balancer knows nothing about conversations. So with N = 100 gateways:

• The chance that one member misses one particular gateway is 1 - 1/N = 0.99.
• The chance that all M members miss it is (1 - 1/N)^M.
• So the chance that a given gateway holds at least one member is 1 - (1 - 1/N)^M.
• Multiply by N gateways to get the expected count.

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

Each row compares G sends (broadcast) against M sends (direct), and the last column is M / G — how many times more sends direct routing costs.

Reading the table

G can never exceed N. With only 100 gateways in the fleet, a 5,000-member group is still only 100 gateways, so broadcast’s cost stops growing at 100 while direct routing’s keeps climbing with M. That is the whole mechanism.

Now look at the last column as M grows. Broadcast always sends fewer copies — but how much fewer is what changes, and it changes character at saturation:

• Below saturation, the advantage is a small constant: 1.1x at 25 members, 1.6x at 100. That is not enough to pay for a live topic and a subscription per (gateway, conversation) pair, on a platform with 6.25 B conversations — that is the billion-subscription bill Deep dive 2 transport websocket long polling sse already rejected. Use direct routing.
• Above saturation, G is pinned at N, so the advantage is M/N and grows without bound: 5x at 500 members, 50x at 5,000, 1,000x at 100,000. Now one topic per big channel is trivially worth it. Use broadcast.

So the threshold is the point where G stops growing. Solve for where G reaches 99% of N, which is where (1 - 1/N)^M has fallen to 0.01:

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

The threshold is 458 members, and the number that produced it is the gateway count, not anything about groups. Halve the fleet to 50 gateways and the threshold halves with it: ln(0.01)/ln(0.98) = 228.

What else changes above the threshold

Three things, and all three are about work that scales with M.

Receipts must be suppressed. In a 100 k-member channel where every member acknowledges both delivered and read, one message produces 2 x 100,000 = 200,000 return events. Receipts collapse into an aggregate count (“seen by 4.2 k”) or are turned off entirely.

Presence must be suppressed for the same reason, and the case is 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 you do not load the member list in order to route a message. The broadcast topic is the member list.

Those three together say something the routing arithmetic on its own does not. A “group” and a “channel” are different systems that share an API, and the boundary is at 458 members for this fleet. Product usually rounds it to 500 or 1,000 and caps groups there, which is the same decision with a rounder number.

11. Deep dive 5: delivery semantics

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

11.1 Exactly-once is not achievable, and here is the proof shape

Start with the negative result everything else here is built on — no protocol can deliver a message exactly once — then convert it into the number that makes the alternative unavoidable: how many duplicates a day this system actually produces.

The protocol is three steps. The sender transmits. The receiver stores. The receiver sends back an ack, a small confirmation that it got the message.

Now suppose the ack never arrives. The sender cannot distinguish between two situations:

• (a) The message was lost before it was stored.
• (b) The message was stored, and the ack was lost on the way home.

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.

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)

Adding another round trip does not help, because the same ambiguity applies to that round trip — you have just moved the uncertainty one step later.

This is the two-generals problem: two armies on opposite hills who can only communicate by messengers that may be captured, and who therefore can never both become certain they have agreed on a time to attack. It is a theorem, not an engineering gap. No protocol closes it.

So there are exactly two implementable choices, and one of them is not really available:

Exactly-once is at-least-once plus deduplication, and the deduplication happens at the receiver. Anyone who says “we do exactly-once delivery” is describing at-least-once transport plus idempotent processing.

How many duplicates that actually means

Quantify it, so dedup is obviously mandatory rather than merely advisable. A hop is one network handoff between two components.

per-hop failure probability   0.001
hops on the ack path          3        (device -> gateway -> store -> back)
P(ack lost | stored)          3 x 0.001            =  0.003
duplicates/day                158,000,000,000 x 0.003  =  474,000,000

Line 3 approximates “at least one of three hops fails” as three times the single-hop probability, which is close enough at 0.1%. Line 4 applies that 0.3% to every one of the 1.58e11 daily deliveries from Back of the envelope, because every delivery has an ack path.

Four hundred and seventy-four million duplicate deliveries a day at a 0.1% per-hop failure rate. Dedup is not a refinement.

11.2 The dedup mechanism, both ends

Deduplication has to happen twice — once where messages enter the system and once where they leave it — and both ends have a price.

Sender side, keyed on client_msg_id

The client generates a ULID (The three details a reviewer looks for) before sending, and reuses that same id on every retry of that message.

The server remembers the (sender_id, client_msg_id) pairs it has already 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 them for as long as retries can still arrive:

window                        300 s        (retries stop well inside a 60 s backoff ladder)
entries in the window         231,481 x 300         =  69,444,300
bytes/entry                   24
dedup set size                69444300 x 24         =  1,666,663,200  B  =  1.67 GB

Line 2 is the platform’s send rate times the window: everything sent in the last 300 s is still retryable, so all of it must be remembered. The 24 B on line 3 is an 8 B sender id plus a 16 B ULID.

1.67 GB of Redis buys server-side idempotency for the entire platform — it makes sending the same message twice have exactly the same effect as sending it once.

Receiver side, keyed on (conv_id, seq)

The client keeps the last 1,000 sequence numbers it has seen, per conversation.

Sixteen bytes is the cost of holding one of those numbers, not the size of the number itself. The seq is 8 B, the same width as msg_id in Back of the envelope; the hash slot and pointer the index needs in order to find it again cost roughly 8 B more.

per conversation      1,000 x 16 B          =  16,000  B
per device, 50 convs  50 x 16,000           =  800,000  B  =  800 KB

800 KB on a phone is nothing, and that one structure answers both of the client’s questions: have I already applied this? and am I missing anything?

The client-side inbox

The listing below is that structure. Two lines in it are guards rather than style, and they are the two worth reading closely.

highest starts at None, not at 0. Zero is a real sequence number, and a truthiness test on an integer cannot tell “nothing applied yet” from “applied seq 0”. A conversation numbered from zero would have gap detection silently switched off for its entire life.

applied is an OrderedDict, not a set. The 1,000 priced above is a bound, and a set has no way to evict its oldest member. A price the code does not enforce is prose.

from collections import OrderedDict


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

    KEEP = 1_000                          # the bound priced above, enforced here

    def __init__(self) -> None:
        # OrderedDict, not set: 1,000 remembered seqs is a bound, and a set
        # cannot evict. A priced bound that the code does not enforce is prose.
        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, nothing else
        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"
assert box.apply(43, "c") == "gap:[42]"
assert box.apply(42, "b") == "applied"

# The seq-0 case, which is the one a truthiness test loses. Under
# `if seq > self.highest + 1 and self.highest:` the second line returns
# "applied" and the hole [1, 2] is never reported to anyone.
zero = Inbox()
assert zero.apply(0, "x") == "applied"
assert zero.apply(3, "y") == "gap:[1, 2]"

# The bound is real. With an unbounded set this loop leaves 200,000 entries
# resident on a phone against a priced 1,000.
big = Inbox()
for s in range(200_000):
    assert big.apply(s, "m") == "applied"
assert len(big.applied) == Inbox.KEEP
assert big.apply(199_999, "m") == "duplicate"   # the recent tail still dedups
assert big.apply(0, "m") == "applied"           # evicted, so no longer detectable

Three groups of assertions, and each proves something different.

The first four calls are the normal path. Applying 41 twice returns "duplicate" the second time — that is the dedup. Applying 43 next returns "gap:[42]", because 43 is more than one past the highest applied, so the client knows exactly which message to go and fetch. It then applies 42 with no complaint, because gap detection is about noticing holes, not about refusing out-of-order arrivals.

The zero block is the None guard. Sequence 0 applies, then 3 correctly reports gap:[1, 2]. Had highest started at 0 with a truthiness test, self.highest would be falsy after applying seq 0 and the gap check would be skipped — the hole would never be reported to anyone.

The big block is the bound. After 200,000 applies the structure still holds exactly 1,000 entries. The recent tail still dedups, and the last line shows what that costs.

That last line is the price of the bound, stated rather than hidden: a redelivery older than 1,000 sequence numbers is applied twice.

So price the window rather than asserting it is fine. In the busiest realistic conversation, a few messages per second (What seq buys), 1,000 sequence numbers is 1,000 / 3 = 333 seconds of history — just past the 300 s sender-side retry window above, so retries expire before the memory does. In an ordinary conversation at 0.000037 messages/s it covers years.

KEEP is the dial. A conversation that sustained more than three messages a second would have to turn it up.

11.3 Receipts, and why read must be a cursor

Receipts are the sent/delivered/read markers. Implemented naively they cost more than the messages themselves; turned into cursors, the problem disappears.

The naive implementation has each delivery generate two return events, one delivered and one read. Since there are 1.58e11 deliveries a day (Back of the envelope), that doubles to 3.16e11 events:

2 x 158,000,000,000       =  316,000,000,000  /day
per second                316,000,000,000 / 86,400  =  3,657,407
vs message send rate      3657407 / 231481          =  15.8x

Receipts would be sixteen times the traffic of the messages they describe. Sixteen times, for two grey ticks.

The fix is to make a receipt cover a range instead of a message. One read event each time a conversation is opened, carrying only the highest sequence number the user has now seen — which implies every message below it is read too.

Users open the app 15 times a day, so:

opens/day                 500,000,000 x 15           =  7,500,000,000
opens/s                   7,500,000,000 / 86,400     =  86,806
`read` half only          158000000000 / 7500000000  =  21.1x

Read receipts are cursors, not events. delivered gets exactly the same treatment: one acknowledgement each time the socket is flushed, covering a whole range of sequence numbers, rather than one per message.

Two ratios that get confused

21.1x and 42x are both correct, and they measure different things. Keep them apart.

• 21.1x is the read half alone: deliveries (1.58e11/day) over opens (7.5e9/day).
• 42x is the pair of them, and it is the figure the bottleneck table in Bottlenecks and scaling carries. Both halves fall from 3.66 M/s to the 86,806/s of opens, and 3,657,407 / 86,806 = 42x.

Quoting 21x against the 3.66 M/s endpoint takes the ratio from one comparison and staples it to the other. It is the kind of mistake an interviewer notices precisely because both numbers are real.

11.4 The offline queue that is not a queue

Most designs include a component this one does not: a per-user mailbox holding messages that arrived while the user was disconnected. Price what that mailbox would cost, and then notice that the data you already have answers the same question.

First, size the mailbox. Each user receives 316 deliveries per day and opens the app 15 times, so at a typical open there are about 21 messages waiting:

158,000,000,000 / 500,000,000   =  316   deliveries/user/day
316 / 15                        =  21    messages waiting at a typical open
500,000,000 x 21 x 100 B        =  1,050,000,000,000  B  =  1.05 TB

The third line assumes every user is sitting on a typical backlog at once, which is the honest worst case for a store you have to keep hot.

That 1.05 TB is what a separate offline queue would cost, and 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 starting at last_delivered_seq — the offline queue is a query, not a store. It is the very same query that powers scrolling back through history, so it is code you have already written and already tested.

The one thing offline users genuinely need in addition is a wake-up, which goes out through the platform push services carrying no message content.

12. 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 turns out to be set by phone batteries and mobile-carrier equipment rather than by anything about how fresh the indicator needs to be.

Presence looks trivial and is the most expensive subsystem in the design if you set that one constant wrong. There are two costs to account for: the heartbeats coming in, and the notifications going out when someone’s state changes.

The heartbeat cost

Heartbeat cost is connections / interval, and connections is 20 M. Each connection sends one tiny frame every h seconds purely to prove it is still alive, so the server-side rate is fixed by arithmetic, not by user behaviour. Nobody has to do anything for this traffic to exist.

Four candidate intervals:

h = 10 s     20,000,000 / 10    =  2,000,000  /s
h = 30 s     20,000,000 / 30    =  666,667    /s
h = 60 s     20,000,000 / 60    =  333,333    /s
h = 180 s    20,000,000 / 180   =  111,111    /s

Against a message rate of 231,481/s:

at h = 30    666667 / 231481    =  2.88x the entire chat write load
at h = 180   111111 / 231481    =  0.48x

At a 30-second heartbeat, presence is three times the traffic of chat itself.

That is one side of the tradeoff. The other side is staleness: how long the indicator can keep claiming someone is online after they have actually gone.

Do not declare a user offline on the first missed beat — one miss is too trigger-happy on a mobile network. Wait for k = 2 consecutive misses. A user who vanishes does so at a random point inside the current interval, so detection lands somewhere uniformly between h and 2h, which averages 1.5h:

h = 30 s     mean staleness  1.5 x 30    =  45  s      worst 60 s
h = 180 s    mean staleness  1.5 x 180   =  270 s      worst 360 s

Choosing the interval

The table below puts the four candidate intervals side by side, so you can see all three costs move together. Look at how the second and fourth columns fall as the third rises: everything that makes the indicator fresher makes the system more expensive.

QPS in the second column means queries per second — the general term for how many requests a second a component handles, and the unit every rate in this chapter is quoted in.

The last column needs a gloss. Duty cycle is the fraction of time a 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 roughly 10 seconds afterwards. So the duty cycle is that tail divided by the heartbeat interval: 10 / 30 = 0.33 against 10 / 180 = 0.056. At h = 10 the 10 s tail exactly fills the 10 s interval, so the radio never gets to sleep at all.

h is not chosen by staleness. It is chosen by battery at one end and by NAT at the other.

The lower bound is battery. Each heartbeat drags the radio into that high-power state. h = 30 keeps it awake a third of the time, and that arrives as one-star reviews about battery life rather than as a metrics regression on any dashboard you own.

The upper bound is the carrier’s NAT timeout. NAT — the same address translation the proxy performs in C proxy port exhaustion — is what lets a mobile operator put many subscribers behind one public address: the operator’s equipment holds a table mapping each internal connection to a public port. It discards any entry that has been idle longer than some timeout, commonly 300 s.

Past that timeout the mapping is gone and the connection is silently half-open: the client believes it is connected, the server believes it is connected, and no bytes can pass in either direction. Any heartbeat interval close to 300 s risks this, so you need real margin under it.

Battery pushes up, NAT pushes down, and the window left is roughly 120-240 s. Staleness has no vote in it. 180 s sits in the middle of that window, which is why it is the answer.

So where does the green dot come from?

Not from heartbeats. At a 180-second beat, an indicator driven by heartbeats would be minutes behind.

It comes from activity. Any frame at all on the socket refreshes presence — a message, a receipt, a typing notification. The heartbeat is merely the floor for a client that is connected but doing nothing at all.

Then publish last_seen in coarse buckets — “active now”, “5 min ago” — so that an indicator updated on a slow timer never visibly contradicts itself.

Presence fanout, which is the larger half

Every online/offline transition has to reach everyone watching that user, and there are a lot of them:

transitions/user/day               10
naive watchers (all contacts)      20
updates/day    500,000,000 x 10 x 20      =  100,000,000,000
per second     100000000000 / 86,400      =  1,157,407
vs messages    1157407 / 231481           =  5.0x

Read that as: 500 M users, each flipping between online and offline 10 times a day, each flip told to 20 contacts.

Fanning presence to every contact costs five times the message traffic.

The fix is subscribe-on-view: send a transition only to the people who currently have that conversation open on screen. There are about 1.5 of those at any moment, against 20 contacts:

updates/day    500,000,000 x 10 x 1.5     =  7,500,000,000
per second     7500000000 / 86,400        =  86,806
reduction      1157407 / 86806            =  13.3x

Subscribe-on-view is a 13x reduction and it costs nothing, because a presence indicator nobody is looking at has no value. You are not degrading the product; you are declining to compute an answer no one will read.

On top of that, rate-limit transitions per user with a token bucket set to one per 60 s (Token bucket). That stops a flapping connection (one repeatedly dropping and reconnecting as a phone moves between cell towers) from emitting a hundred transitions a minute into the fanout.

13. Bottlenecks and scaling

Every limit derived above lands in one table, with what you do when each is reached — and after the table, the one decision that has to be made about geography.

Read the table as an escalation path: “Binds at” is the number where the component stops coping, “First fix” is what you reach for, and “Then” is what you do when the first fix runs out too.

Two entries in that table use shorthand. LSM stands for 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. Cold storage is cheaper, slower storage for data that is rarely read.

Geography

Finally, the one geographic decision. A conversation is owned by exactly one region — the region of the conversation, not the region of the user.

That follows directly from Deep dive 3 ordering and what a sequence number buys: the sequencer must have a single owner, and an owner has to live somewhere. A round trip between regions is 70-150 ms, so a user travelling abroad pays that round trip on every send.

The alternative is multi-master sequencing, in which several regions may assign numbers at once. That requires a consensus protocol (an algorithm by which a group of machines agrees on a single value despite failures) added to a problem that already has an obvious single writer. Pay the cross-region round trip instead.

14. Failure modes

Eight ways the system breaks in production — and, at the end, the one property that makes all of them survivable.

For each row: “Blast radius” is how much of the platform notices, “Detection” is the signal that tells you it happened, and “Mitigation” is what the design already does about it. Nothing here is a new component — every mitigation is a mechanism derived earlier in the chapter.

The row that matters is the last one, and it 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 in the table degrades to “delivered late” rather than “lost”.

Design the system so that the only permanent failure mode is a lost socket, because a lost socket is just a reconnect.

15. Alternatives rejected

Every design considered and discarded appears with the number that discarded it, so the reasoning is checkable rather than asserted.

16. Interviewer pushback

Eight questions this design invites, with each answer in italics. State the number and where it came from: “458” alone sounds memorised, “458, from ln(0.01)/ln(0.99) with 100 gateways” does not.

“Can you guarantee exactly-once delivery?”

No, and neither can anyone else. If the ack is lost the sender cannot tell whether the message was stored, so it must either retry — at-least-once, duplicates — or not — at-most-once, loss. I take at-least-once and make the receiver idempotent on (conv_id, seq), with a client-generated client_msg_id for server-side dedup. At a 0.1% per-hop failure rate over three hops that is about 474 M duplicates a day, so this is a mainline path, not an edge case.

“Why not just use timestamps for ordering?”

Because two messages in one conversation can be stamped by two gateways whose clocks differ. At 10 ms of per-host skew, the difference has a 14.1 ms sigma, so a 50 ms real gap inverts with probability 2e-4 — about 203,000 inverted message pairs a day. A per-conversation sequence number fixes it for the cost of a single-writer counter that averages one increment every eight hours, and it also gives me gap detection and O(1) read cursors, neither of which timestamps can.

“A per-conversation counter is a single point of contention. Doesn’t that limit you?”

It limits one conversation, which is the correct granularity. Global throughput is 231 k messages/s spread over 6.25 B conversations. The busiest realistic case is a large channel at a few messages per second, and that is nowhere near a shard’s limit. If a channel did exceed it, I would batch — assign a block of seqs and fill it — before I would weaken the ordering guarantee.

“You said 100 gateway boxes. The memory estimate in Six worked estimations says three.”

Both are right and the gap is the useful part. Memory says three, so memory is not what sizes this tier. File descriptors say 20, untuned socket buffers say 47, proxy port limits say 306 distinct proxy/backend tuples, and the failure domain says 100 at 200 k connections each. I take the failure domain, because one box dying means that many simultaneous reconnects, and the reconnect jitter window is blast radius / op budget — 20 seconds if the registry gives reconnects 10% of 100 k ops/s, and I would want to measure both of those before shipping the 20.

“How do you find which box holds a user’s socket?”

A session registry keyed by user id, 20 M rows at 64 B, so 1.28 GB, taking 1.83 M lookups/s sharded 16 ways. I rejected the alternatives explicitly: bus subscriptions are 10 M per gateway, and consistent hashing answers where the user should be rather than where the load balancer put them. Consistent hashing does have a job here — owning conversations for the sequencer — just not this one.

“At what group size does the design change?”

458 members, and the number comes from the fleet, not from the group. With 100 gateways and members distributed independently, the number of gateways holding at least one member is 100 x (1 - 0.99^M), which saturates at 100. Below saturation broadcast saves only 1.1x to 1.6x in sends, which does not pay for a topic and subscriptions on every one of 6.25 B conversations, so I route directly. Above saturation the saving is M/N and unbounded — 50x at 5,000 members — so I broadcast. Solving for 99% saturation gives ln(0.01)/ln(0.99) = 458. Halve the fleet and the threshold halves.

“Your presence system costs more than your chat system. Is that acceptable?”

It is what a naive presence design does, which is why it is worth deriving. Heartbeats at 30 s are 2e7 / 30 = 667 k/s against a 231 k/s message rate, and naive presence fanout to 20 contacts is 1.16 M/s. Two changes fix it: heartbeat at 180 s, which is set by radio battery and the 300 s carrier NAT timeout rather than by staleness, and fan out only to watchers with the conversation on screen, which is 13x cheaper. Presence then costs 87 k/s, well under the chat traffic, and the green dot comes from activity rather than from the heartbeat.

“What about end-to-end encryption?” — that is, encrypting each message on the sending device with a key the server never holds, so that only the recipients’ devices can read it.

It changes what the server can do, not the shape of the system. The server still assigns seq, still routes, still stores — it just cannot read body. What it costs is anything requiring plaintext: server-side search, media transcoding, and content moderation move to the client or disappear. Group key distribution and the per-device fanout of key material are the real work, and multi-device is what makes it hard, not the messaging.

Cheat sheet

The whole chapter compressed to nineteen lines.

Related: 11 — News Feed System is the same push/pull question without a real-time deadline; ch 02 is where the 20 M connection estimate and its trap come from; ch 04 supplies the retry-storm and token-bucket machinery; ch 05 owns conversations for the sequencer; ch 07 supplies client_msg_id.