CS Fundamentals Trainer · Guides

Design a chat system

A worked design with numbers: persistent connections, per-conversation sequence numbers for ordering, idempotent delivery, fan-out on write against on read, presence, offline sync and very large groups.

36 min read

"Design a chat system" is one of the most common system-design questions, because it touches almost everything at once: long-lived connections, ordering in a distributed system, delivery guarantees over networks that lose messages, storage at a very high write rate, fan-out to groups, presence and offline users. It is useful to practise as a worked example, with numbers. This guide designs a chat service step by step and measures the parts that are easy to get wrong: how bad it is to order by the sender's clock, what the two fan-out designs cost to store, and how much memory it takes to hold a connection open. The scripts are in the appendix.

It is a case study in the style of design a news feed, and it uses ideas from other guides, including message queues and consistent hashing: load balancing and DNS and HTTP for the front, replication and sharding and storage engines for the store, consensus and time for ordering, resilience for retries and time-series workloads for the write path.

Read this first: end-to-end encryption changes the design, and it has limits. This guide designs a chat service in which the server can read messages (they are encrypted in transit and at rest, but the service holds the keys). That is what makes server-side search, spam and abuse checks, history on a new device, and message recovery simple. With end-to-end encryption (E2EE) the servers store only ciphertext that they cannot read, and each of those features gets harder or impossible; section 9.1 shows the consequences with a small model. E2EE also does not hide metadata (who talks to whom, when, how much), does not protect a compromised phone, and depends on the users verifying each other's keys. If your product promises privacy, decide this before the rest, because it changes storage, search, sync, backup and moderation.

1. Requirements first

Before drawing boxes, agree on what the system must do. For this design:

Out of scope here: voice and video calls, search and bots. End-to-end encryption is not built into this design, but its consequences are important enough to have a box at the top and section 9.1.

2. A rough size

Estimates guide the design; they need not be exact. Assume 50 million daily users sending 40 messages each:

QuantityCalculationResult
messages per day50 M × 402 billion
messages per second, average2 × 10⁹ / 86,400about 23,000
at the daily peak (assume 3 times average)about 70,000 per second
storage per day2 × 10⁹ × 100 bytes200 GB, or about 73 TB a year before replication
concurrent connectionsassume 20% of users online10 million

Two things stand out. The workload is write-heavy and append-only: a message is written once, rarely changed, and read a few times. And 10 million simultaneous open connections is the unusual part for a web system, since an ordinary request/response service holds a connection for milliseconds, while a chat gateway holds each for hours.

3. The architecture

Diagram: The main components of a chat system

Why a persistent connection? The server must be able to push a message at the moment it arrives. With HTTP polling every few seconds, latency is half the interval on average and most requests find nothing. Long polling, server-sent events and WebSockets all keep a channel open; WebSockets are the usual choice for two-way traffic. Clients must reconnect automatically with randomised, growing delays, otherwise a gateway restart makes 100,000 clients reconnect at the same second (retry storms).

Diagram: Sending a message from Alice to Bob

4. Ordering: who decides what came first?

Everyone in a conversation must see the messages in the same order, and replies should follow the messages they answer. The tempting answer is to use the time the sender's phone put on the message. I simulated 2,000 messages from five people whose phone clocks are wrong by up to about two seconds (the offsets here ranged from −0.2 to +1.7 s), where each message is a reply to the one before it:

Ordering ruleAdjacent messages shown in the wrong order
the sender's clock389 of 2,000 (19%)
the time the server received them131 (6.5%): messages sent within a few hundred milliseconds of each other can swap in transit
a sequence number assigned by the server on arrivalthe same order on every client, always (by construction)

Clocks on different machines disagree, and nothing makes them agree exactly (consensus and time, Lamport's classic paper on ordering events). What users need is not the "true" order, which does not exist when two people type at the same moment, but an agreed one. So the design gives each conversation a single sequencer: all messages of a conversation go to the same chat-service shard (partitioned by conversation id), which stamps each one with the next number (1, 2, 3, …) when it stores it. Clients display messages sorted by that number, and show their own just-typed message provisionally, in grey, until the number comes back. The sequence number gives an order, not a delivery guarantee (section 5.1 shows why and what completes it). It then helps with the rest:

The sequence is per conversation, not global: a global counter would be a bottleneck and would not be needed, since messages in different conversations are not compared. Because one shard owns one conversation, its failover must be handled carefully (a new owner must continue from the highest stored number; see leader election).

5. Delivery: at least once, made exactly once

Networks lose packets and connections drop mid-message. A sender who does not receive an acknowledgement cannot know whether the message arrived: it may have been lost on the way there, or the acknowledgement may have been lost on the way back. The only safe policy is to retry until acknowledged, which means the server may receive the same message twice. This is at-least-once delivery; the way to get the effect of exactly-once is idempotency: the client gives each message a unique client message id (a UUID generated on the device), and the server remembers the ids it has seen for the conversation, so that a repeat is recognised, not stored again, and answered with the original sequence number. Step through it, then turn on the lost acknowledgement:

Interactive animation: chat delivery

With the acknowledgement lost, the message was sent twice but stored once and shown to the recipient once, because the second arrival was recognised by its id. The duplicate check can be a unique constraint on (conversation, client message id) in the store (idempotency in distributed transactions), so it is correct even if two attempts reach different servers at the same time.

The same applies on the way out: the server pushes a message to Bob and waits for his client's acknowledgement; if it does not come, it will push again, and Bob's client ignores sequence numbers it already has.

Receipts are small messages of their own. "Sent" is the server's acknowledgement; "delivered" is the recipient device's acknowledgement; "read" is sent when the user opens the conversation, and can be reduced to one number ("read up to seq N"). In large groups per-person receipts are expensive and often dropped or aggregated.

5.1 One message, end to end: acknowledgement, reconnect, replay and deduplication

A sequence number is an ordering device, not a delivery guarantee. It tells everyone how to sort the messages that exist, and it lets a client notice a hole below the highest number it has seen. It does not make a message arrive: if the last message of a burst is lost on the way to a recipient, that recipient has no later number to compare with, and cannot know that anything is missing. Delivery comes from the combination of four mechanisms, and each fixes something the others cannot:

MechanismFixesDoes not fix
Sequence number (per conversation)order; gaps below the highest number receiveda lost last message; a lost message to a device that was offline
Acknowledgement and retry by the sendera send or push that was lostduplicates: a lost acknowledgement makes the sender send again
Deduplication (client message id, unique per conversation)duplicates from retries, even across serverslosses
Sync on reconnect and a periodic "my latest is N" from the serverthe lost tail; the offline period; a gap that was never noticednothing by itself, since it needs the store to be the truth

The flow for one conversation, with the failures the network can produce:

  1. Alice's client creates message A2 with a fresh client id and sends it; the server stores it as seq 2, pushes it to Bob and returns the acknowledgement, which is lost.
  2. Alice's client times out and retries with the same client id. The server finds the id in its table, stores nothing new and answers seq 2 again. This is the deduplication step.
  3. The push of the next message, seq 3, is lost on the way to Bob. Bob has 1 and 2 and cannot tell that 3 exists.
  4. Alice sends seq 4. Bob receives it, sees that his highest number is 4 and that 3 is missing, and asks for the gap (fetch after 2). The server replays 3 and 4; Bob already has 4 and ignores it.
  5. Bob goes offline; seq 5 and seq 6 are stored and the push fails. When Bob reconnects he sends sync after 4 (the highest number he has), and the server replays 5 and 6.
  6. If the last message in the conversation had been the lost one, only step 5's mechanism would find it: the client must ask on reconnect, and a long-lived connection should carry a periodic message from the server with the latest number, so that a silent tail loss is noticed in seconds.

To check that each layer is needed, I simulated 1,000 conversations of five messages (5,000 messages) in which every send, push and acknowledgement can be lost independently, adding one mechanism at a time (flow.py; at most 8 attempts per message):

DesignLoss rateNever storedStored twiceStored but missing at the recipientShown twice
1. sequence numbers only5%25802340
2. + sender retries5%0258242234
3. + deduplication5%002420
4. + fetch the gaps it notices5%00550
5. + sync on reconnect / "latest is N"5%0000
1. sequence numbers only20%99007970
2. + sender retries20%01,311845873
3. + deduplication20%008450
4. + fetch the gaps it notices20%002080
5. + sync on reconnect / "latest is N"20%0000

Retries cured the lost sends and created duplicates; deduplication removed the duplicates; gap detection fixed most missing messages but still left some (55 and 208), all of them tails that no later number could reveal; only the pull-based sync closed the rest. The simulation models the logic and not a real network: loss is independent, there is no reordering, and the sequencer never fails. Failure of the sequencer is a separate problem: a new owner must continue above the highest stored number, or two messages get the same seq (see section 4). Note also what "exactly once" means here: the sender may transmit many times, the store holds the message once, and the recipient's screen shows it once, because the effect is made idempotent. The network does not deliver it once.

6. Storage and fan-out

How should a group message be stored? There are two designs:

I measured the storage side in PostgreSQL by sending 2,000 messages to a group:

Group sizeCopy to each member: rows, time, sizeStore once + cursors: rows, time, size
24,000 rows, 0.01 s, 0.5 MB2,002 rows, 0.00 s, 0.3 MB
1020,000 rows, 0.04 s, 2.4 MB2,010 rows, 0.00 s, 0.3 MB
100200,000 rows, 0.42 s, 24 MB2,100 rows, 0.01 s, 0.3 MB
1,0002,000,000 rows, 4.7 s, 238 MB3,000 rows, 0.01 s, 0.4 MB

(The 1,000 cursors of the second design are written once, when the members join, not for each message; a cursor is updated only when its owner reads.) Copying cost grows in proportion to the group size, with about 600 times more storage and several hundred times more write time for a group of 1,000, and a message in a busy group would become thousands of writes that all have to be replicated. Storing once is flat. This is why real systems store a conversation log and per-user pointers.

The copy-per-member design still has its place: for one-to-one chats (fan-out of 2) it simplifies the model, and for notification feeds you want the per-user list precomputed. Many systems use a hybrid: write once to the log, and fan-out only a small notification (conversation id, sequence number, unread count) to each member's online gateway or push token. That small notification is what scales with the group size, and it is cheap and ephemeral.

Choosing the store

The message log is written constantly, almost never updated, and read by (conversation, sequence range): recent messages mostly, older ones when scrolling. That fits a wide-column or log-structured store (LSM trees) such as Cassandra, ScyllaDB or HBase, partitioned by conversation and bucketed by time so that no single partition grows without limit; Discord's engineering posts describe exactly this. A relational database with partitioning (sharding) works well at a smaller scale. Whatever is chosen, the key is (conversation id, sequence number): the data for one conversation sits together on disk, and a page of history is one contiguous read. Hot recent messages can be cached (caching).

7. Connections, routing and offline sync

What holding a connection costs

I wrote a server in Go that accepts connections, one goroutine each with a 4 KB buffer, and leaves them idle, and measured its resident memory with 1,000, 5,000 and 15,000 clients connected:

Idle connectionsServer memoryPer connection
1,0009 MB5.2 KB
5,00027 MB4.7 KB
15,00073 MB4.8 KB

About 5 KB each, in process memory, with idle connections costing nearly no CPU. So 10 million connections need at least 48 GB of memory across the gateways for the bare connections, and with TLS state, WebSocket buffers and per-user data in memory it is several times that. If one server comfortably holds 100,000 connections, 10 million concurrent users need about 100 gateway servers plus headroom. This is a lower bound; the real limits are the operating system (file descriptors, kernel buffers), the load of heartbeats and the burst when thousands reconnect together. It also shows why gateways should be thin and stateless about conversations: when one dies, only its connections are lost, and the clients reconnect to another.

Finding the recipient

Delivery workers need to know which gateway holds Bob's connection. The session registry maps user → gateway (and device), written when a client connects and removed on disconnect or expiry. A user can have several devices, so a message is delivered to all of them. If Bob has no connection, the worker sends a push notification (APNs, FCM) through the platform provider, and the message waits in the store. Alternatively, publish/subscribe channels per user or per conversation let gateways subscribe to what their connected users need, which avoids a lookup at the cost of many subscriptions.

Offline and multi-device sync

The store is the truth, and connections are an optimisation. When a device connects, it sends, per conversation, the highest sequence number it has; the server answers with everything newer (or with a "too many, fetch in pages" signal). The same mechanism covers a new phone, a reconnect after a tunnel, and a gap detected in the live stream. This is why a design that depends on connections never losing anything is fragile, and one that treats the connection as a fast path over a pull-based sync is robust.

8. Presence, typing and very large groups

Presence ("online", "last seen") sounds simple and is expensive if done naively. The usual method is a heartbeat: while connected, the client pings every 20 to 30 seconds, and the presence store keeps a key per user with a short expiry (about 1.5 to 2 heartbeats), renewed by each ping. If the pings stop, the key expires and the user is "offline", without needing the disconnect to be noticed. Notifying contacts is the costly part: if every status change were pushed to everyone who has you as a contact, a user with 500 contacts who flaps between wifi and mobile data generates thousands of messages. So presence is fetched when needed (when a contact list or conversation is opened) and pushed only to users who are looking at you right now, with a delay or "debounce" for brief disconnections.

Typing indicators and similar signals are ephemeral: they are sent over the live connection, not stored, and can be lost without harm. Mark them as such in the protocol so the system does not give them the machinery (storage, retries) that messages need.

Very large groups (a channel with 100,000 members) break the model. Per-member receipts and per-member notifications are too many. Systems change the rules: no read receipts, notify only when mentioned, deliver only to members who are online and looking at the channel, and fetch the rest on demand. A broadcast channel with a million readers is a publish/subscribe system with caching at the edge more than a chat.

9. Scaling, failure and the rest

9.1 End-to-end encryption and multi-device limits

In an E2EE design, the sender's device encrypts for every recipient device, not for every user, and the server only routes and stores the ciphertext. I built a small model of the structure with X25519 key agreement and AES-GCM (e2ee_model.py, using the Python cryptography package). It is a simplified model of the structure, not the Signal protocol: it has no ratchet, no forward secrecy and no verification of keys, and must not be used for real messages. It shows five consequences that hold for real systems too:

ConsequenceIn the modelWhat products do about it
One ciphertext per devicea message to a group of 3 users with 1 device each stored 3 ciphertexts; after Bob added a laptop, the next message stored 4. Each copy is 83 bytes for a 23-byte messagegroup messages cost storage and upload per member device; large groups use shared "sender keys", which weaken some guarantees
The server cannot search or filtera search for a word in everything the server holds found 0 matchessearch runs on the device, over its local history; spam and abuse reports rely on users forwarding the plaintext, or on checks on the device
A new device cannot read old messagesBob's new laptop failed to decrypt a message sent before it existed (authentication failed) and read the next onehistory needs a device-to-device transfer, or an encrypted backup; "sync across devices" is no longer a plain database read
Losing the only device loses the historythe lost phone held the only key for the old messagesbackups under a user-held key or passphrase; if the provider can recover the key, the system is not end-to-end for that data
Metadata is still visiblethe server still saw sender, recipient devices, conversation, sequence number, size and timeminimise and expire it; sealed-sender and similar techniques reduce, but do not remove, what the server learns

Two limits are easy to overlook. First, multi-device means multi-key: every linked device is another place where messages can be read, so linking a device is a security-critical action, and a "web client" that downloads its code from the server can be changed by the server to leak plaintext. Second, E2EE protects messages in transit and on the server, not on the endpoint: notifications, backups to a cloud account, screenshots, and malware on the phone are all outside it. State these limits to the users, in the product, as clearly as the guarantee. For the cryptography itself use a vetted protocol and library (the Signal protocol or MLS), not a design of your own.

10. Common mistakes

11. Things to mention in an interview

Quick recap

Appendix: the experiment code

Four files. order.py (Python standard library) simulates 2,000 messages from five people whose phone clocks are wrong by up to about two seconds; the true order is known, so wrong pairs can be counted. fanout.sql needs a scratch PostgreSQL 16 server and compares two ways to store a group message for 2, 10, 100 and 1,000 members. server.go and client.go (Go 1.24) hold up to 15,000 idle TCP connections between two processes on one machine and report the server's resident memory per connection. The connections are plain TCP, one goroutine and a 4 KB read buffer each: a real gateway adds WebSocket framing, TLS state and application data, so treat the figure as a lower bound, not a capacity plan. The ordering simulation uses random numbers with a fixed seed. Database times are single runs on a small virtual machine. The capacity estimates in section 2 are arithmetic on assumed inputs, not measurements of a real service.

order.py: ordering messages by client clocks, arrival, or a sequence number

"""Ordering messages in a conversation: client clocks against a server-assigned sequence number."""
import random
r = random.Random(11)

# Five people in a chat, each with a phone clock that is wrong by up to +/- 2 seconds.
skew = {u: r.uniform(-2.0, 2.0) for u in "ABCDE"}
# A real conversation in which each message is a reply to the previous one: the true order is 0, 1, 2, ...
true_time, msgs = 0.0, []
for i in range(2000):
    true_time += r.expovariate(1 / 0.8)                    # a reply every 0.8 s on average
    sender = r.choice("ABCDE")
    msgs.append({"id": i, "sender": sender, "true": true_time, "client_ts": true_time + skew[sender]})

def wrong_pairs(order):
    """Adjacent messages whose displayed order differs from the true order (replies shown before the message they answer)."""
    return sum(1 for a, b in zip(order, order[1:]) if a["id"] > b["id"])

by_client = sorted(msgs, key=lambda m: m["client_ts"])
print(f"messages: {len(msgs)}, phone clocks off by {min(skew.values()):+.1f} to {max(skew.values()):+.1f} s")
print(f"sorted by the sender's clock: {wrong_pairs(by_client)} adjacent pairs shown in the wrong order ({wrong_pairs(by_client)/len(msgs)*100:.0f}% of messages)")

# The server receives messages over networks with random delay (20 to 400 ms), so arrival order is not true order either.
arrival = sorted(msgs, key=lambda m: m["true"] + r.uniform(0.02, 0.4))
print(f"sorted by server arrival time: {wrong_pairs(arrival)} pairs wrong (messages sent within a few hundred ms of each other can swap)")
# ...but what matters is that everybody sees the same order. The server assigns a sequence number as messages arrive:
seq = {m["id"]: n for n, m in enumerate(arrival)}
view = {u: sorted(msgs, key=lambda m: seq[m["id"]]) for u in "ABCDE"}
print("every client sorting by the server's sequence number sees the same order:", all([m["id"] for m in view[u]] == [m["id"] for m in view["A"]] for u in "ABCDE"))

fanout.sql: copy to every member against store once with read cursors

-- Group chat storage: copy each message into every member's inbox (fan-out on write),
-- or store it once in the conversation and give each member a read cursor (fan-out on read).
-- Sends 2,000 messages to a group of N members, for several N.
\timing off
CREATE TEMP TABLE results (design text, members int, seconds numeric, rows_written bigint, size_mb numeric);
DO $$
DECLARE n int; t0 timestamptz; sz bigint; rows bigint;
BEGIN
  FOREACH n IN ARRAY ARRAY[2, 10, 100, 1000] LOOP
    -- design A: one row per message per recipient
    DROP TABLE IF EXISTS inbox; CREATE TABLE inbox (user_id int, conv_id int, seq int, body text, PRIMARY KEY (user_id, conv_id, seq));
    t0 := clock_timestamp();
    INSERT INTO inbox SELECT u, 1, s, 'hello, this is a chat message of average length' FROM generate_series(1, n) u, generate_series(1, 2000) s;
    GET DIAGNOSTICS rows = ROW_COUNT; sz := pg_total_relation_size('inbox');
    INSERT INTO results VALUES ('copy to each member', n, extract(epoch FROM clock_timestamp() - t0), rows, sz / 1048576.0);
    -- design B: one row per message, plus one cursor per member (updated when the member reads, not when a message is sent)
    DROP TABLE IF EXISTS messages, cursors; CREATE TABLE messages (conv_id int, seq int, body text, PRIMARY KEY (conv_id, seq)); CREATE TABLE cursors (user_id int, conv_id int, last_read int, PRIMARY KEY (user_id, conv_id));
    t0 := clock_timestamp();
    INSERT INTO messages SELECT 1, s, 'hello, this is a chat message of average length' FROM generate_series(1, 2000) s;
    GET DIAGNOSTICS rows = ROW_COUNT;
    INSERT INTO cursors SELECT u, 1, 0 FROM generate_series(1, n) u;
    INSERT INTO results VALUES ('store once + read cursors', n, extract(epoch FROM clock_timestamp() - t0), rows + n, (pg_total_relation_size('messages') + pg_total_relation_size('cursors')) / 1048576.0);
  END LOOP;
END $$;
SELECT design, members, round(seconds, 2) AS seconds, rows_written, round(size_mb, 1) AS size_mb FROM results ORDER BY members, design;

server.go: memory used by idle connections

// server.go: holds N idle connections, one goroutine each (like a chat gateway holding WebSockets), and prints its memory use.
package main

import (
	"bufio"
	"fmt"
	"net"
	"os"
	"runtime"
	"strconv"
	"time"
)

func rss() int { // resident memory in KB, from /proc
	b, _ := os.ReadFile("/proc/self/status")
	var kb int
	for _, l := range splitLines(string(b)) {
		if len(l) > 6 && l[:6] == "VmRSS:" {
			fmt.Sscanf(l[6:], "%d", &kb)
		}
	}
	return kb
}
func splitLines(s string) (out []string) {
	start := 0
	for i := range s {
		if s[i] == '\n' {
			out = append(out, s[start:i])
			start = i + 1
		}
	}
	return
}

func main() {
	want, _ := strconv.Atoi(os.Args[1])
	ln, _ := net.Listen("tcp", "127.0.0.1:9100")
	base := rss()
	count := 0
	done := make(chan struct{})
	for {
		c, err := ln.Accept()
		if err != nil {
			panic(err)
		}
		count++
		go func(c net.Conn) { // one goroutine per connection, blocked waiting for the next message
			r := bufio.NewReader(c)
			r.ReadByte()
		}(c)
		if count == want {
			time.Sleep(500 * time.Millisecond)
			runtime.GC()
			after := rss()
			fmt.Printf("server: %d idle connections, %d goroutines, resident memory %d MB (%.1f KB per connection, before any: %d MB)\n",
				count, runtime.NumGoroutine(), after/1024, float64(after-base)/float64(count), base/1024)
			close(done)
			break
		}
	}
	<-done
}

client.go: opens the connections for the server test

// client.go: opens N connections to the server and keeps them open.
package main

import (
	"net"
	"os"
	"strconv"
	"time"
)

func main() {
	n, _ := strconv.Atoi(os.Args[1])
	conns := make([]net.Conn, 0, n)
	for i := 0; i < n; i++ {
		c, err := net.Dial("tcp", "127.0.0.1:9100")
		if err != nil {
			panic(err)
		}
		conns = append(conns, c)
	}
	time.Sleep(3 * time.Second)
	_ = conns
}

flow.py: sequence numbers, retries, deduplication and sync, one layer at a time

Python standard library only; deterministic.

"""End-to-end delivery flow of a chat message: sequence numbers, acks, reconnect, replay, deduplication.
Deterministic, stdlib only. Each layer is switched on in turn so you can see what it adds."""
import random

def simulate(loss, retry, dedup, gap_fetch, heartbeat, seed=1, n=5):
    """One short conversation of n messages (a tail loss only shows up at the end of a conversation)."""
    rnd = random.Random(seed)
    store = {}            # server: seq -> client message id
    seen = {}             # dedup table: client message id -> seq
    next_seq = 1
    have = {}             # recipient: seq -> client message id
    never_stored = 0
    for cid in range(n):
        stored = False
        for attempt in range(8):
            if rnd.random() < loss: 
                if not retry: break
                continue                                      # the send was lost
            if dedup and cid in seen:
                seq = seen[cid]
            else:
                seq = next_seq; next_seq += 1
                store[seq] = cid; seen[cid] = seq
            stored = True
            if rnd.random() >= loss: have[seq] = cid          # push reaches the recipient
            if rnd.random() >= loss: break                    # ack reaches the sender: stop retrying
            if not retry: break
        if not stored: never_stored += 1
    if gap_fetch:                                             # only holes BELOW the highest number received are visible
        top = max(have) if have else 0
        for s in range(1, top + 1):
            if s in store: have[s] = store[s]
    if heartbeat:                                             # the server also says "my latest is N"
        for s in store: have[s] = store[s]
    shown_ids = list(have.values())
    return dict(never_stored=never_stored,
                stored_twice=len(store) - len(set(store.values())),
                missing=len(set(store.values()) - set(shown_ids)),
                shown_twice=len(shown_ids) - len(set(shown_ids)))

def many(loss, **kw):
    tot = dict(never_stored=0, stored_twice=0, missing=0, shown_twice=0)
    for seed in range(1000):
        for k, v in simulate(loss, seed=seed, **kw).items(): tot[k] += v
    return tot

rows = [
 ("1  sequence numbers only (no retry)",                 dict(retry=False, dedup=False, gap_fetch=False, heartbeat=False)),
 ("2  + sender retries until acked",                      dict(retry=True,  dedup=False, gap_fetch=False, heartbeat=False)),
 ("3  + server dedups on client message id",              dict(retry=True,  dedup=True,  gap_fetch=False, heartbeat=False)),
 ("4  + recipient fetches the gaps it notices",           dict(retry=True,  dedup=True,  gap_fetch=True,  heartbeat=False)),
 ("5  + sync on reconnect/heartbeat (latest seq known)",  dict(retry=True,  dedup=True,  gap_fetch=True,  heartbeat=True)),
]
for loss in (0.05, 0.20):
    print(f"\npacket loss {int(loss*100)}% on each of send, push and ack; 1,000 conversations of 5 messages = 5,000 messages")
    print(f"{'design':56s} never_stored stored_twice missing_on_recipient shown_twice")
    for name, kw in rows:
        r = many(loss, **kw)
        print(f"{name:56s} {r['never_stored']:>12} {r['stored_twice']:>12} {r['missing']:>20} {r['shown_twice']:>11}")

# One message, traced: send lost ack, retry, reconnect.
print("\nTrace of one conversation (ack of #2 lost, push of #3 lost, device offline for #4, #5):")
trace = [
 "alice -> server  m=A1 id=a1        server stores seq 1, pushes 1 to bob, acks alice",
 "alice -> server  m=A2 id=a2        server stores seq 2; the ACK is lost on the way back",
 "alice -> server  m=A2 id=a2 (retry) server finds id=a2 already stored -> answers seq 2, stores nothing new",
 "alice -> server  m=A3 id=a3        server stores seq 3; the PUSH to bob is lost",
 "bob receives seq 1, 2. Nothing arrives for 3. Bob cannot know that: he has no later number to compare",
 "alice -> server  m=A4 id=a4        server stores seq 4, pushes; bob now has 1,2,4 and sees the hole at 3",
 "bob -> server    fetch after=2     server replays seq 3, 4 (bob ignores 4: already has it)",
 "bob goes offline; alice sends A5, A6 (seq 5, 6) -> push fails, they stay in the store",
 "bob reconnects: sync after=4       server replays 5, 6; bob's screen now holds 1..6 exactly once",
]
print("\n".join(trace))

e2ee_model.py: a simplified model of per-device end-to-end encryption

Needs the Python cryptography package. A model of the structure only; not the Signal protocol and not for real use.

"""A simplified end-to-end encryption model: ONE ciphertext per recipient DEVICE (X25519 key agreement + HKDF + AES-GCM).
This shows the structural consequences (what the server stores, what a new device can read, what grows).
It is NOT the Signal protocol: no ratchet, no forward secrecy, no authentication of keys. Do not use it for real messages."""
import os
from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey
from cryptography.hazmat.primitives.ciphers.aead import AESGCM
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes, serialization
from cryptography.exceptions import InvalidTag

def pub(k): return k.public_key().public_bytes(serialization.Encoding.Raw, serialization.PublicFormat.Raw)
def kdf(shared): return HKDF(algorithm=hashes.SHA256(), length=32, salt=None, info=b"chat-demo").derive(shared)

class Device:
    def __init__(self, user, name): self.user, self.name, self.key = user, name, X25519PrivateKey.generate(); self.inbox = {}
    def public(self): return pub(self.key)

def encrypt_for(sender_eph, device, plaintext):
    shared = sender_eph.exchange(__import__("cryptography.hazmat.primitives.asymmetric.x25519", fromlist=["X25519PublicKey"]).X25519PublicKey.from_public_bytes(device.public()))
    nonce = os.urandom(12)
    return pub(sender_eph) + nonce + AESGCM(kdf(shared)).encrypt(nonce, plaintext, None)

def decrypt(device, blob):
    from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PublicKey
    eph, nonce, ct = blob[:32], blob[32:44], blob[44:]
    shared = device.key.exchange(X25519PublicKey.from_public_bytes(eph))
    return AESGCM(kdf(shared)).decrypt(nonce, ct, None)

server_store = []     # what the server keeps: (conversation, seq, device, ciphertext) plus metadata it can see
alice_phone = Device("alice", "phone")
bob_phone, bob_laptop = Device("bob", "phone"), Device("bob", "laptop")
carol_phone = Device("carol", "phone")
members = {"alice": [alice_phone], "bob": [bob_phone], "carol": [carol_phone]}

def send(sender, text, seq):
    eph = X25519PrivateKey.generate()
    n = 0
    for user, devs in members.items():
        for d in devs:                       # one ciphertext per device (including the sender's other devices)
            blob = encrypt_for(eph, d, text.encode())
            server_store.append(dict(conv="g1", seq=seq, sender=sender, to=f"{d.user}/{d.name}", size=len(blob), ct=blob)); n += 1
    return n

print("1. a group of 3 users, 1 device each:  ciphertexts stored for one 23-byte message =", send("alice", "meet at 9, bring slides", 1))
members["bob"].append(bob_laptop)
print("2. bob adds a laptop; a second message: ciphertexts stored =", send("alice", "ok, 9:15 instead", 2))

# what can the server do?
hit = [r for r in server_store if b"slides" in r["ct"]]
print("3. server searches its store for the word 'slides':", len(hit), "matches (it holds only ciphertext)")
print("   but it still sees: sender, recipient devices, conversation, sequence number, size, time -> metadata")

# can the NEW device read the OLD message?
old = [r for r in server_store if r["seq"] == 1 and r["to"] == "bob/phone"][0]["ct"]
try: decrypt(bob_laptop, old); print("4. laptop reads message 1: yes")
except InvalidTag: print("4. bob's new laptop tries to read message 1 (sent before it existed): cannot decrypt -> history needs a device-to-device transfer or a key backup")
new = [r for r in server_store if r["seq"] == 2 and r["to"] == "bob/laptop"][0]["ct"]
print("   laptop reads message 2:", decrypt(bob_laptop, new).decode())

# lost device
members["bob"].remove(bob_phone)
print("5. bob loses his phone: its key was the only copy of message 1 on bob's side ->",
      "history on the server is unreadable without a backup key; if the backup is protected only by the server, E2EE is not end-to-end")
print("6. size: 23-byte message -> ", [r["size"] for r in server_store][:1], "bytes per device copy (32-byte key + 12-byte nonce + 16-byte tag + text)")
print("   total stored for", len({r['seq'] for r in server_store}), "messages:", len(server_store), "copies")

Sources

Practise this topic: System Design System Design › Case studies

More guides