Designing WhatsApp

1.1What it has to do

Before drawing any boxes, it pays to write down what the system must do, because every later decision gets tested against this list. For WhatsApp's core messaging, the list is short:

1. Send a text message from one person to another.
2. Deliver it even if the recipient is offline, as soon as they come back.
3. Show the sender what happened: sent, delivered, read (the ticks).
4. Group chats, up to 1,024 people today.
5. Photos, voice notes and videos.
6. Several devices per person: a phone plus a laptop or tablet.
7. End-to-end encryption: only the people in the chat can read the messages, not WhatsApp.

And a second list of qualities the system must have while doing it, usually called non-functional requirements:

• Fast: a message to someone online should arrive in well under a second.
• Never lose a message: once the sender sees one tick, the message must eventually arrive.
• No duplicates, right order: Ben should see each message once, and in the order Asha sent them.
• Light on the phone: the app mustn't drain the battery or the data plan.

Notice what's missing: WhatsApp doesn't promise to keep your chat history on its servers. We'll see in section 3 that this one omission shapes a large part of the design.

1.2How big is it?

The numbers matter because they decide which designs are even possible. In March 2014, WhatsApp's server lead Rick Reed gave these figures at a conference talk:

By 2020 WhatsApp had more than two billion users and delivered around 100 billion messages a day. We'll use the 2014 numbers through most of this case study, because they come with the most detail about how the servers were built.

Two of these numbers deserve a second look. Nineteen billion messages a day is about 220,000 a second on average, and the peak of 342,000 is only about one and a half times that, so the load is steady and heavy all day. And the servers send out more than twice as many messages as they receive. A message to a group arrives once and leaves once per member, and every delivered message also produces receipts going back to the sender, so the outgoing side is where much of the work is.

2.1The simplest thing that could work

Let's start as small as possible: one server, and two phones. Asha's phone sends "Running 10 min late, for Ben" to the server, and the server passes it to Ben's phone. The interesting question is the second half. How does the server get a message to Ben's phone?

The numbers from section 1 settle it. If the 147 million connected phones polled every ten seconds, the servers would handle 14.7 million requests a second, to deliver at most 342,000 messages a second. More than 97 out of every 100 requests would come back empty, and every one of them would wake the phone's radio, which is one of the most power-hungry parts of a phone.

On our single server, the bookkeeping is easy. The server keeps a table in memory from each user to their open connection, a hash map: ben → connection #48812. When Asha's message for Ben arrives, the server looks up ben and writes the message to that connection.

This works perfectly, as long as Ben is online. On the train, he isn't.

3.1A mailbox per person

When Asha's message arrives, the server looks up ben in its table of connections and finds nothing, because Ben's phone lost its connection in the tunnel. The server can't throw the message away, and it can't make Asha wait until Ben reappears, which might be tomorrow.

So the server keeps it. Each user gets a mailbox: a queue of messages waiting for them. A message for someone offline goes into their mailbox. When their phone connects, the server sends everything in the mailbox, in order. This pattern, hold a message until the next hop is ready and then pass it on, is called store and forward, and it's how email and the postal service work too.

Here is the whole journey of Asha's message, with Ben offline when she sends it:

The ticks fall straight out of this design. One tick means the message reached the server's mailbox and is safe from the sender's phone dying or losing signal. Two ticks mean Ben's device acknowledged it. Blue ticks are one more receipt, sent when Ben opens the chat. In a group, the second tick appears only when every member's device has the message, and the ticks turn blue only when everyone has read it.

3.2Delete after delivery

Look at the last step again: once Ben's phone has the message, the server deletes it. WhatsApp's privacy policy states this directly. Delivered messages are deleted from its servers, and an undelivered message is kept, encrypted, for up to 30 days while the server keeps trying.

That's a real design choice, and not every chat system makes it.

How big does the mailbox store get in practice? WhatsApp's 2014 talk gave a telling measurement: most messages are picked up very quickly, about half within a minute. So WhatsApp put a write-back cache in front of the mailbox files on disk. A new message goes into memory first and is written to disk only after a short delay. If Ben's phone collects it within that delay, it never touches the disk at all. The talk reported cache hit rates of 78% and 98% on two different measures.

This is the same trade a filesystem makes with dirty pages: hold writes in memory because many will be overwritten or become unnecessary soon. The risk is the same too. A message that is only in memory is lost if the server crashes, which is why the first tick must not be sent until the message is somewhere that survives a crash. In WhatsApp's design that meant every service ran as a primary and a secondary on different machines.

3.3Exactly once, from at-least-once

Our design has a gap. Asha's phone sends message a1, the server stores it and sends back an acknowledgement. Then Asha's train goes into a tunnel too, and the acknowledgement never arrives. From her phone's point of view, the message might not have arrived. What should it do?

It has to send it again. Giving up would lose messages, which we promised never to do. But resending creates the opposite problem: the server may now have the message twice, and Ben would see "Running 10 min late" twice.

The fix is to make sending a message safe to repeat. Asha's phone gives each message an ID when it's created, before it's sent the first time, and every retry carries the same ID. Whoever receives it keeps a record of IDs already seen and ignores repeats. Sending "a message at least once" plus "ignore IDs you've seen" adds up to each message being stored exactly once.

This short Python program plays that out. server_store is the server's side, and the loop is Asha's phone, retrying whenever the acknowledgement is lost (a coin flip, with a fixed seed so the run repeats):

import random
random.seed(3)
 
seen, inbox = set(), []
 
def server_store(msg_id, text):
    if msg_id in seen:
        return "duplicate, ignored"
    seen.add(msg_id)
    inbox.append(text)
    return "stored"
 
for msg_id, text in [("a1", "Running 10 min late"), ("a2", "Start without me")]:
    attempt = 1
    while True:
        result = server_store(msg_id, text)
        ack_lost = random.random() < 0.5
        print(f"{msg_id} attempt {attempt}: {result}, ack {'lost' if ack_lost else 'received'}")
        if not ack_lost:
            break
        attempt += 1
 
print("Ben's mailbox:", inbox)

a1 attempt 1: stored, ack lost
a1 attempt 2: duplicate, ignored, ack received
a2 attempt 1: stored, ack lost
a2 attempt 2: duplicate, ignored, ack received
Ben's mailbox: ['Running 10 min late', 'Start without me']

Both messages were sent twice, because both first acknowledgements were lost. Each retry carried the same ID, so the second copy was recognised and dropped, and Ben's mailbox holds each message once, in order. The same check runs again on Ben's phone, so a message delivered twice from the mailbox (because Ben's acknowledgement was lost) is also shown once.

WhatsApp hasn't published its exact acknowledgement protocol, but its whitepaper builds on Signal's protocol design, which describes exactly this: the network may lose, delay, reorder or duplicate messages, so every guarantee is built at the ends, from IDs, receipts and retries.

One server with mailboxes, receipts and IDs now meets most of our requirements. It just can't hold 147 million connections.

4.1A million connections on one machine

In section 1 we estimated about 150 servers at a million connections each. Getting even one server to hold a million connections was a real piece of engineering. In 2012 WhatsApp's servers started out holding about 200,000 connections each. After a month of work they reached two million on one machine, and in one unplanned test a server peaked at 2.8 million before the engineers stepped in. Each server had 24 CPU threads and 100 GB of memory. In 2014's production setup each chat server held about a million phones, leaving plenty of headroom.

What made this possible was mostly the language the server was written in: Erlang. In Erlang each connection gets its own process, which, unlike an operating system process, costs only a couple of kilobytes of memory to start. A million connections become a million tiny processes, each running a simple sequential loop: read from my connection, handle the message, repeat. The Erlang runtime spreads those processes over all the CPU cores and switches between them itself.

4.2Which server is Ben on?

Now the problem that section 1 warned about. Asha's phone is connected to chat server 17. Ben's phone, when it comes out of the tunnel, connects to chat server 92. Asha's message arrives at server 17, which has no connection for Ben.

A shared directory of who is connected where is usually called a session registry. In its simplest form it's a big hash map from user ID to server, split across several machines so that no one machine holds all of it. When Ben's phone connects to server 92, server 92 writes ben → 92. When the connection closes, server 92 removes it. And when server 17 has a message for Ben, it looks him up and forwards the message to server 92 in a single hop.

Here is the design at this point, with the request paths you can step through. The next diagram then zooms into the routing itself.

Notice the order in the second step. The message goes into the mailbox before the server tries to find Ben. That makes the mailbox the source of truth and the fast path an optimisation: if the lookup is stale, the forward fails, or Ben's phone dies mid-delivery, nothing is lost, because the message is still in the mailbox and will be delivered when Ben's phone next connects.

Stale entries are the registry's real difficulty. If server 92 crashes, it can't remove its million → 92 entries on the way down, so the registry briefly sends messages to a dead server. Two common defences are to give each entry a lifetime that the server must keep renewing (a lease, like the ones in chapter 30), and to clear every entry for a server the moment the cluster notices it's gone.

How did WhatsApp itself do this? Its 2014 talk describes services split into partitions, usually 2 to 32, each running as a primary and secondary pair, with Erlang's built-in process groups (pg2) used to address them and a routing layer on top so that "all messages are single-hop". The exact layout of its session table was never published, so treat the registry above as the standard design and not a description of WhatsApp's code.

4.3When everyone reconnects at once

On 22 February 2014, WhatsApp went down for about three and a half hours. According to Rick Reed's talk a few weeks later, it began with a glitch in a back-end router, which disconnected a large number of servers from each other at once. They all tried to reconnect at the same moment, and the process groups used for routing generated so much traffic between nodes that queues grew from zero to four million messages within seconds. The team had to stop and restart the whole system, for the first time in years.

This failure, everyone reconnecting at once and overwhelming the thing they reconnect to, is called a thundering herd, and every system built around long-lived connections has to plan for it. Phones that lose their connection should wait a random, growing amount of time before reconnecting, so that a million phones dropped together don't return together. And the registry has to survive a burst of millions of writes in a minute.

5.1Who copies the message?

Asha also posts "Running late, start without me" to the group "Trip", which has five members. Five people, each possibly online or offline, each on whichever chat server their phone happened to reach. Someone has to turn one message into five deliveries.

That fan-out is why the servers sent out more than twice as many messages as they received in section 1. It also caused trouble in a less obvious place: the 2014 talk mentions people in many busy groups receiving thousands of messages an hour, whose mailboxes were large enough to push other users' messages out of the write-back cache.

6.1Send a pointer, not the file

Ben replies with a 12 MB video of the train. If that video travelled the same way as text, through a chat server, into a mailbox and out again, each chat server would spend most of its time moving large files, and a video stuck in the queue would delay every small text message behind it.

So media takes a separate path. Ben's phone uploads the video to a blob store, a service built only to store and serve large files, and gets back a pointer to it. The chat message itself contains only that pointer, plus a few small fields we'll meet in section 7. Text and media travel on different roads: the chat servers move millions of small messages a second, and the media servers move fewer, much larger files.

The two kinds of traffic differ a lot. In 2013 WhatsApp's media servers handled 214 million images on their busiest day, at up to 29 gigabits a second outbound. On New Year's Eve 2013, users downloaded two billion photos, and a single photo was downloaded 32 million times as it was forwarded around.

That last number points at one more saving. When someone forwards a photo, their phone doesn't upload it again. The forwarded message reuses the same pointer, so the file is stored once however many times it's passed on. WhatsApp's privacy policy describes keeping forwarded media on its servers, encrypted, to make further forwards efficient.

7.1The problem

Everything so far would work with the server able to read every message. WhatsApp's last requirement removes that: since 2016, every message is end-to-end encrypted, meaning it's encrypted on Asha's phone and only Ben's phone can decrypt it. The server stores, routes and fans out messages it can't read.

The difficulty is that Asha and Ben have to agree on a secret key to encrypt with, and every way they can communicate passes through the server they don't want to trust. Worse, Ben may be offline when Asha sends her very first message, so the two phones can't have a conversation to set the key up.

7.2Agreeing on a key with someone who's asleep

The building block is a Diffie–Hellman exchange. Each side has a private key, a random number kept secret, and a public key derived from it. Combining your private key with my public key gives the same result as combining my private key with your public key. Someone who sees both public keys can't compute that result. So two people who swap public keys end up sharing a secret that nobody watching the swap can work out.

WhatsApp (using the Signal protocol) has each device generate and keep three kinds of key pair:

• an identity key, long-lived, which identifies the device;
• a signed prekey, replaced periodically, and signed with the identity key so nobody can substitute a fake one;
• a batch of one-time prekeys, each used for one new conversation and then discarded.

When Ben's phone registers, it uploads the public halves of all of these to the server, which stores them under Ben's account. The server holds nothing secret.

When Asha writes to Ben for the first time, her phone fetches Ben's prekey bundle: his public identity key, his signed prekey, and one one-time prekey, which the server then deletes so that nobody else gets it. Asha's phone checks the signature on the signed prekey and creates a fresh key pair of its own for this conversation, an ephemeral key. Then it performs four Diffie–Hellman combinations:

All four results are fed through a key-derivation function into one shared secret. This protocol is called X3DH ("extended triple Diffie–Hellman"). Asha's first message carries her public identity key and ephemeral key in its header. When Ben's phone comes online and receives it, it performs the same four combinations from its side, arrives at the same secret, and deletes the one-time prekey that was used. Ben was offline the whole time, and the server, which saw every public key, can't compute the secret because it has none of the private keys.

7.3A new key for every message

Asha and Ben now share a secret. The obvious next step is to encrypt every message with it. The weakness is that if anyone ever steals that key, say from Ben's phone a year from now, they can decrypt every message ever sent with it, including recordings of old traffic.

The Signal protocol avoids this with a ratchet: a key that only turns forwards. From the shared secret, each side derives a chain key. To encrypt a message, the phone computes two things from the current chain key with HMAC, a keyed hash function: a message key, used once to encrypt this message and then deleted, and the next chain key, which replaces the current one. Because a hash can't be reversed, the new chain key reveals nothing about the old one.

This program computes the first three steps of such a chain:

import hashlib, hmac
 
def step(chain_key):
    message_key = hmac.new(chain_key, b"\x01", hashlib.sha256).digest()
    next_chain = hmac.new(chain_key, b"\x02", hashlib.sha256).digest()
    return next_chain, message_key
 
chain = hashlib.sha256(b"secret Asha and Ben agreed on").digest()
for n in range(1, 4):
    chain, key = step(chain)
    print(f"message {n}: key {key.hex()[:12]}  next chain {chain.hex()[:12]}")

message 1: key b26699ed126a  next chain 8db54b84a2e5
message 2: key 374887423c52  next chain 4ebef309b71e
message 3: key 5ec1e0d33d36  next chain d9d02da84848

Each message gets an unrelated-looking key, and each step's chain key comes from the one before. Going forward is one HMAC call. Going backward, from d9d0… to 4ebe…, would mean reversing SHA-256, which nobody can do. So once Asha's phone has deleted message 1's key and the old chain key, a thief who later steals her phone can't decrypt message 1. This property is called forward secrecy. (WhatsApp's real constants are the 0x01 and 0x02 used here, and its message keys are expanded to 80 bytes: an encryption key, an authentication key and an initialisation vector.)

That handles stealing old keys. What about a thief who steals today's chain key? They could step it forward and read every future message. So the protocol adds a second ratchet. Every message also carries a fresh Diffie–Hellman public key from its sender. Whenever a reply arrives with a new key, both phones mix a new Diffie–Hellman result into a root key and derive fresh chain keys from it. Fresh randomness enters with every back-and-forth, so a thief who copied the keys once is locked out again as soon as the conversation continues. This is called post-compromise security, and the combination of the two ratchets is the Double Ratchet.

Messages can arrive out of order, which a ratchet that only moves forward has to handle. Each message carries its position in the chain, and if message 5 arrives before message 4, the receiver steps the chain twice, uses key 5, and stores key 4 in a small table of skipped message keys, with a cap on its size, until message 4 turns up.

7.4Encrypting for a group

Back to the group "Trip". Section 5 had the server fanning out one message to every member, but with pairwise sessions, Asha would have to encrypt the message separately for every member device, which means uploading one ciphertext per device again.

The Signal protocol's answer is Sender Keys. The first time Asha sends to the group, her phone creates a chain key and a signing key just for her messages in that group, and sends them to each member over their existing pairwise encrypted sessions. That happens once. After that, every message Asha sends to the group is encrypted once with the next key from her group chain, signed with her signing key, and uploaded once. The server fans out that one ciphertext, which works with section 5's design unchanged.

7.5What the server still knows

End-to-end encryption hides what people say, not the fact that they're talking. The server still routes every message, so it sees who sends to whom, when, how often, roughly how large each message is, which devices each account has, and from which network addresses. The connection between each phone and the chat server is encrypted too, with a protocol called Noise, so that eavesdroppers on the network can't see even that. But the server itself necessarily knows it.

8.1Who encrypts for the laptop?

Ben also uses WhatsApp on his laptop. Asha's message has to reach both devices. With everything we've built so far, that's harder than it sounds: the message is encrypted for a session with Ben's phone, and the laptop doesn't have that session's keys.

8.2Trusting the device list

Client fan-out raises a new risk. Asha's phone asks the server for Ben's list of devices, then encrypts for each one. A malicious or hacked server could slip in an extra device that it controls, and Asha's phone would dutifully encrypt for it.

WhatsApp closes this with signatures from Ben's phone, his primary device. When Ben links his laptop, the phone scans a QR code shown on the laptop, which contains the laptop's public identity key. The phone then signs a statement, "this laptop belongs to my account", with the phone's identity key, and signs the new list of Ben's devices. Senders verify those signatures before encrypting for a device, and the server can't produce them because it doesn't have the phone's private key. Signed device lists also expire after at most 35 days, so a list can't be replayed forever.

Two more pieces finish the picture. The laptop starts with no history, because the server deleted everything after delivery (section 3), so Ben's phone encrypts a bundle of recent chats, uploads it as an encrypted blob, and sends the key to the laptop end-to-end. And if Asha's phone was working from an out-of-date list of Ben's devices, the server notices that the list Asha used doesn't match its own record, tells her phone, and her phone fetches the new device, verifies it, and sends that device the message too.

9.1Every box, and why it's there

We've added one piece at a time, each because the previous version broke. Here is the result, and the reason each part exists:

And here is Asha's original message passing through all of them, now that we know what each one does:

9.2From top to bottom

The design reaches from the whole system down to bytes. It's worth seeing the levels together, because each level's choice is driven by the level above:

10.1Failures this design has to survive

10.2The tradeoffs, in one table