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:
- One-to-one and group chat (groups up to a few hundred members; very large channels are a different problem, see section 8).
- Text messages, plus attachments (images, files).
- Delivery to online users in real time, and to offline users when they return, plus push notifications.
- Message history that syncs across a user's devices.
- Sent, delivered and read indicators, and presence ("online", "last seen").
- Non-functional: low latency (a message should appear in well under a second), no lost messages, no duplicates, the same order for everybody in a conversation, high availability, and growth to hundreds of millions of users.
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:
| Quantity | Calculation | Result |
|---|---|---|
| messages per day | 50 M × 40 | 2 billion |
| messages per second, average | 2 × 10⁹ / 86,400 | about 23,000 |
| at the daily peak (assume 3 times average) | about 70,000 per second | |
| storage per day | 2 × 10⁹ × 100 bytes | 200 GB, or about 73 TB a year before replication |
| concurrent connections | assume 20% of users online | 10 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
- Gateways hold the persistent connections (WebSocket, or a similar protocol; plain HTTP polling is wasteful, see below). They do little: authenticate, keep the connection alive, pass messages in and out. Keeping them thin lets you scale them separately and restart them without losing data.
- The chat service is stateless: it validates a message, assigns its place in the conversation, stores it, and publishes it for delivery.
- The message store is the system of record. Delivery workers read from a queue, find where each recipient is connected via the session registry, and push the message there; offline recipients get a push notification and fetch the history when they return.
- Attachments do not travel through the chat path: the client uploads to object storage (with a short-lived signed URL), and the message carries only a link and metadata. A CDN serves them (DNS and CDNs).
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 rule | Adjacent messages shown in the wrong order |
|---|---|
| the sender's clock | 389 of 2,000 (19%) |
| the time the server received them | 131 (6.5%): messages sent within a few hundred milliseconds of each other can swap in transit |
| a sequence number assigned by the server on arrival | the 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:
- Gap detection: a client that has seq 41 and receives seq 43 knows it missed 42 and asks for it.
- Sync: a returning device says "I have up to 87", and the server sends everything after 87 (section 7).
- Read position and receipts: "read up to 87" is one small number per member.
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:
| Mechanism | Fixes | Does not fix |
|---|---|---|
| Sequence number (per conversation) | order; gaps below the highest number received | a lost last message; a lost message to a device that was offline |
| Acknowledgement and retry by the sender | a send or push that was lost | duplicates: a lost acknowledgement makes the sender send again |
| Deduplication (client message id, unique per conversation) | duplicates from retries, even across servers | losses |
| Sync on reconnect and a periodic "my latest is N" from the server | the lost tail; the offline period; a gap that was never noticed | nothing by itself, since it needs the store to be the truth |
The flow for one conversation, with the failures the network can produce:
- 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. - 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 2again. This is the deduplication step. - 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. - 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. - Bob goes offline;
seq 5andseq 6are stored and the push fails. When Bob reconnects he sendssync after 4(the highest number he has), and the server replays 5 and 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):
| Design | Loss rate | Never stored | Stored twice | Stored but missing at the recipient | Shown twice |
|---|---|---|---|---|---|
| 1. sequence numbers only | 5% | 258 | 0 | 234 | 0 |
| 2. + sender retries | 5% | 0 | 258 | 242 | 234 |
| 3. + deduplication | 5% | 0 | 0 | 242 | 0 |
| 4. + fetch the gaps it notices | 5% | 0 | 0 | 55 | 0 |
| 5. + sync on reconnect / "latest is N" | 5% | 0 | 0 | 0 | 0 |
| 1. sequence numbers only | 20% | 990 | 0 | 797 | 0 |
| 2. + sender retries | 20% | 0 | 1,311 | 845 | 873 |
| 3. + deduplication | 20% | 0 | 0 | 845 | 0 |
| 4. + fetch the gaps it notices | 20% | 0 | 0 | 208 | 0 |
| 5. + sync on reconnect / "latest is N" | 20% | 0 | 0 | 0 | 0 |
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:
- Fan-out on write: when a message is sent, write a copy into each member's own inbox. Reading is trivial (everything for me is in one place), writing is multiplied by the group size.
- Fan-out on read (store once): write the message once into the conversation's log, and give each member a cursor (their last-read sequence number). A member's client reads the conversations it belongs to from their logs. Writing costs the same regardless of the group size.
I measured the storage side in PostgreSQL by sending 2,000 messages to a group:
| Group size | Copy to each member: rows, time, size | Store once + cursors: rows, time, size |
|---|---|---|
| 2 | 4,000 rows, 0.01 s, 0.5 MB | 2,002 rows, 0.00 s, 0.3 MB |
| 10 | 20,000 rows, 0.04 s, 2.4 MB | 2,010 rows, 0.00 s, 0.3 MB |
| 100 | 200,000 rows, 0.42 s, 24 MB | 2,100 rows, 0.01 s, 0.3 MB |
| 1,000 | 2,000,000 rows, 4.7 s, 238 MB | 3,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 connections | Server memory | Per connection |
|---|---|---|
| 1,000 | 9 MB | 5.2 KB |
| 5,000 | 27 MB | 4.7 KB |
| 15,000 | 73 MB | 4.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
- Partition by conversation id everywhere in the write path (chat service, store, sequencer), so that one conversation's work is on one shard, and add shards as the numbers grow, with consistent hashing or a directory to avoid mass movement (partitioning).
- Replicate the store across zones, and write to a quorum so that an acknowledged message survives a machine failure. The acknowledgement to the sender should come after the message is durably stored; that is the promise "if you see sent, it will not be lost".
- A gateway or region fails: the clients reconnect (with jittered backoff) and sync from their last sequence number.
- Rate limits and abuse controls on senders, attachment size limits, scanning of uploaded files, and the ability to block users.
- Retention and deletion: deleting a message, "delete for everyone", account deletion and legal retention rules all need a place in the data model from the start (personal data must be removable on request).
- Search over history is a separate index (search), updated asynchronously from the message stream.
- Security: authenticate the connection and authorise every conversation action on the server; never trust the client's claim of who sent a message. Messages and attachments are encrypted in transit and at rest (security). With end-to-end encryption (the Signal protocol and its relatives) the servers store only ciphertext, which makes server-side search, spam checks and multi-device history sync much harder: each device has its own keys, and a group message is encrypted for each member's device. It is a product decision with real costs.
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:
| Consequence | In the model | What products do about it |
|---|---|---|
| One ciphertext per device | a 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 message | group messages cost storage and upload per member device; large groups use shared "sender keys", which weaken some guarantees |
| The server cannot search or filter | a search for a word in everything the server holds found 0 matches | search 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 messages | Bob's new laptop failed to decrypt a message sent before it existed (authentication failed) and read the next one | history 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 history | the lost phone held the only key for the old messages | backups 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 visible | the server still saw sender, recipient devices, conversation, sequence number, size and time | minimise 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.
- Observability: end-to-end delivery latency (send to delivered), the rate of duplicates and of gaps, connection counts and reconnect rates, queue depth (observability).
10. Common mistakes
- Ordering by the client's timestamp, or by arrival at whichever server received it.
- Retrying without an idempotency key, so a network glitch produces duplicate messages.
- Acknowledging to the sender before the message is durably stored.
- Copying every group message into every member's inbox.
- Using one global counter for sequence numbers.
- Making gateways stateful (keeping conversation state in their memory), so every restart loses data.
- Reconnect logic without backoff and jitter.
- Pushing presence to everyone on every change.
- Treating the live connection as the only delivery path, with no pull-based sync.
- Trusting identity claims from the client, and returning messages without checking that the caller belongs to the conversation.
11. Things to mention in an interview
- Clarify requirements, then estimate: messages per second, storage per year, concurrent connections.
- Persistent connections (WebSocket) against polling, thin gateways, session registry, push notifications for offline users.
- Ordering by a per-conversation sequence number from a single sequencer, not by clocks; gap detection; sync from the last sequence.
- At-least-once delivery with client message ids for idempotency, giving exactly-once storage; acknowledging after durable storage; receipts.
- Fan-out on write against on read, with the numbers (the cost grows with the group size), and the hybrid with small notifications.
- A log-structured, partitioned store keyed by (conversation, sequence); attachments in object storage.
- Presence by heartbeat with expiry and by-need fetching; ephemeral signals; large groups change the rules.
- Failure handling: reconnect with jitter, replicate the log, failover of the sequencer; security and end-to-end encryption trade-offs.
Quick recap
- A chat system is write-heavy and append-only with long-lived connections: the sample estimate was about 23,000 messages per second on average (70,000 at peak), 73 TB a year, and 10 million concurrent connections.
- Order by a server-assigned, per-conversation sequence number, not by clocks: sorting by sender clocks put 19% of adjacent messages in the wrong order in the simulation.
- Retry plus idempotency: a client-generated message id means a lost acknowledgement leads to a resend that is stored once.
- Store a group message once with per-member cursors: in a group of 1,000, copying to every member meant 2,000,000 rows and 238 MB against 3,000 rows and 0.4 MB.
- A held connection cost about 4.8 KB at the least, so gateways are many, thin and disposable, and the store with pull-based sync (from the last sequence number) is the real source of truth.
- Presence is a heartbeat with expiry, fetched by need; huge groups change the rules; and end-to-end encryption trades server-side features for privacy.
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
- Alex Xu, System Design Interview (self-published, 2020), chapter 12 "Design a Chat System", and Alex Xu and Sahil Ghosh, System Design Interview Volume 2 (2022).
- Facebook Engineering, Building Mobile-First Infrastructure for Messenger (2014); and Slack Engineering, Real-time Messaging (2023).
- Rick Reed, Scaling to Millions of Simultaneous Connections (Erlang Factory, 2012) on WhatsApp's connection servers.
- Discord Engineering, How Discord Stores Trillions of Messages (2023) and How Discord Stores Billions of Messages (2017), on partitioning messages by channel and time bucket.
- I. Fette and A. Melnikov, RFC 6455: The WebSocket Protocol (2011); Mozilla, WebSockets API and Server-sent events.
- Leslie Lamport, Time, Clocks, and the Ordering of Events in a Distributed System, Communications of the ACM, 1978.
- Signal, The Double Ratchet Algorithm and Signal Protocol documentation (end-to-end encryption).
- Martin Kleppmann, Designing Data-Intensive Applications (O'Reilly, 2017), chapters 5, 8 and 9 (replication, unreliable clocks, ordering guarantees).
- Signal, The X3DH Key Agreement Protocol and Sesame: multi-device messaging; IETF, The Messaging Layer Security (MLS) Protocol, RFC 9420.
Practise this topic: System Design System Design › Case studies