26 — A chat system

A chat system delivers messages between people in real time, keeps them in a consistent order, and catches up devices that were offline. Unlike the URL shortener and the news feed, it holds long-lived connections, so servers have state, and its hardest requirements are about correctness: no lost messages, no duplicates, and the same order for everyone. It follows the process from chapter 23.

Requirements

Functional.

1. One-to-one and group conversations. Groups of up to a few thousand members, with large broadcast channels treated separately.
2. Send and receive messages in real time while connected.
3. Deliver messages sent while a device was offline, when it reconnects, plus a push notification.
4. Several devices per user, each with the full history.
5. Delivery and read receipts.
6. Presence (“online”, “last seen”) and typing indicators.

Non-functional.

Presence and typing indicators are best-effort. They can be late or lost, and that’s stated as a requirement so that they don’t get the same machinery as messages.

Out of scope: end-to-end encryption (it changes what the server can see, but not the delivery design described here), voice and video, and message search.

Estimates

All inputs are assumptions (chapter 4).

DAY, peak = 86_400, 3
dau, msgs_per_user, concurrent, msg_bytes, conns_per_server = 50e6, 40, 20e6, 200, 100_000
msgs = dau * msgs_per_user
print(f"messages/day {msgs:,.0f}  avg {msgs/DAY:,.0f}/s  peak {msgs/DAY*peak:,.0f}/s")
print(f"storage/day {msgs*msg_bytes/1e9:,.0f} GB  per year {msgs*msg_bytes*365/1e12:,.0f} TB")
print(f"connection servers at {conns_per_server:,} each: {concurrent/conns_per_server:,.0f} (before headroom)")

messages/day 2,000,000,000  avg 23,148/s  peak 69,444/s
storage/day 400 GB  per year 146 TB
connection servers at 100,000 each: 200 (before headroom)

• Writes are heavy. Unlike the previous two designs, every message is a durable write, at about 70,000 a second at peak. Message storage must be partitioned from the start (chapter 11).
• Storage grows by about 150 TB a year, before replication. That points to a store built for large append-heavy data, partitioned by conversation.
• Connections are a resource of their own. 100,000 connections per server is an assumption. The real figure depends on memory per connection, TLS, heartbeat traffic and message rate, and has to come from a load test (chapter 3).

API

Clients hold one WebSocket per device. RFC 6455 defines it: an HTTP request with Upgrade: websocket, answered with 101 Switching Protocols, after which both sides can send frames at any time. The protocol includes ping and pong control frames, which both sides use to detect a dead connection.

The messages carried over it:

client -> server
  send   {conv_id, client_msg_id, sender_n, body}
  ack    {conv_id, seq}                     # delivered to this device up to seq
  read   {conv_id, seq}                     # user has read up to seq
  sync   {inbox_pos}                        # "what changed since inbox_pos?"
  typing {conv_id}

server -> client
  sent    {client_msg_id, conv_id, seq}     # stored durably, with its sequence number
  message {conv_id, seq, sender, client_msg_id, body}
  receipt {conv_id, user, delivered_seq, read_seq}
  typing  {conv_id, user}

History beyond what a device holds goes over plain HTTP: GET /conversations/{id}/messages?before_seq=…&limit=50, a cursor as in chapter 25. Media is uploaded to object storage first, and the message carries a reference.

Data model

Conversation metadata is relational and comparatively small, so it stays in PostgreSQL:

CREATE TABLE conversations (
    id          bigint      PRIMARY KEY,
    kind        text        NOT NULL,            -- 'direct', 'group', 'channel'
    last_seq    bigint      NOT NULL DEFAULT 0,
    created_at  timestamptz NOT NULL DEFAULT now()
);

CREATE TABLE members (
    conversation_id     bigint NOT NULL REFERENCES conversations(id),
    user_id             bigint NOT NULL,
    joined_seq          bigint NOT NULL,         -- history visible from here
    last_delivered_seq  bigint NOT NULL DEFAULT 0,
    last_read_seq       bigint NOT NULL DEFAULT 0,
    PRIMARY KEY (conversation_id, user_id)
);
CREATE INDEX members_by_user ON members (user_id, conversation_id);

Messages are where the volume is. Their access pattern is narrow: append to a conversation, read a range of a conversation by sequence number, and look up by client ID to detect a retry. A wide-column store such as Cassandra fits that pattern, with the conversation as the partition and the sequence number as the clustering key (chapter 14). A long-lived conversation would make an unbounded partition, so the partition key includes a bucket:

messages
  partition key:  (conversation_id, seq / 10000)     -- one bucket per 10,000 messages
  clustering key: seq
  columns:        sender_id, client_msg_id, body, media_ref, sent_at

A smaller deployment could keep messages in PostgreSQL with PRIMARY KEY (conversation_id, seq) and a unique index on (conversation_id, sender_id, client_msg_id), partitioned by conversation. The shape of the data is the same either way.

The session registry is in Redis: conn:{user_id} is a hash from device ID to the connection server holding that device, with a time-to-live refreshed by heartbeats.

Topology

 devices ==WebSocket==> [L4 load balancer] ==> [connection servers] (hold sockets)
                                                  |         ^
                                    send / ack    |         | deliver
                                                  v         |
                         [chat service, partitioned by conversation_id]
                            |  assign seq, dedupe     |  look up devices
                            v                         v
                     [message store]         [session registry (Redis)]
                     [PostgreSQL: conversations, members]
                            |
                            v
                      [log stream] --> [push notifications] --> APNs / FCM

Connection servers are thin. They terminate TLS and WebSockets, authenticate the device, and pass frames on. They hold no message state, so losing one loses connections, not messages.

The chat service owns conversations. Each conversation is handled by exactly one chat service instance at a time, chosen by hashing the conversation ID onto partitions whose ownership is managed by a coordination service with leases (chapter 13). That single owner is what makes ordering cheap: it assigns sequence numbers without coordinating with anyone.

Routing. To deliver a message, the owner looks up each member’s devices in the session registry and sends the message to the connection servers holding them. Devices not in the registry are offline. They get a push notification and catch up on reconnect.

Sending a message

1. The device creates a client_msg_id (a UUID) and a per-sender counter sender_n, and sends the message.
2. The connection server forwards it to the owner of the conversation.
3. The owner checks whether this client_msg_id has already been stored. If so, it returns the stored sequence number. That is the retry case.
4. Otherwise it assigns seq = last_seq + 1 and writes the message to the message store. Only after the write is durable does it answer the sender with sent {seq}.
5. It delivers the message to every member’s online devices.
6. Each device acknowledges, which advances its delivery watermark.

Step 4’s order matters: acknowledging before the write is durable would break the first requirement. Step 5 happens after the acknowledgement, and can fail without losing anything, because any device that misses a delivery recovers it by sync.

Why a sequence number, and why one place assigns it

Timestamps can’t order messages. Device clocks are wrong, server clocks drift, and two messages sent a millisecond apart from different places can arrive in either order (chapter 13). Lamport and vector clocks capture causality, but they don’t give all members one total order without more machinery.

A single counter per conversation, incremented by the conversation’s owner, gives one total order that every member sees. It also gives two things for free:

• Gap detection. A device that has seq 41 and receives 43 knows 42 exists, and can wait or ask for it.
• Cheap sync. “Everything after 41” is a range read on the clustering key.

The owner doesn’t need a lock in the database to increment the counter, because it’s the only writer for that conversation. As a guard against two owners during a lease handover, the message store’s write is conditional on (conversation_id, seq) not existing, so a stale owner’s write fails instead of creating a second message 42. This plays the role of a fencing token.

A sender’s own order

A per-conversation sequence orders messages by when the owner received them. If a device sends messages 1, 2 and 3 quickly, and 2 is lost and retried, the owner receives 1, 3, 2, and the conversation shows them in that order. That violates the second half of the ordering requirement.

The sender_n counter fixes this. The owner tracks the next expected sender_n per sender and conversation. A message that arrives early is held, without an acknowledgement, until the gap fills. This is the same idea as TCP’s sequence numbers, applied per sender.

Simulating ordering and deduplication

The program below runs one conversation with two senders, each typing 500 messages at 50 ms intervals. Every network hop loses 20% of packets and delays the rest by 10 to 300 ms, so packets also reorder. Senders retry after 500 ms without an acknowledgement. The server retries delivery to the receiver up to three times. The receiver is disconnected for five seconds in the middle.

The naive version stores every attempt as a new message and shows messages as they arrive. The safe version uses client_msg_id and sender_n at the server, and sequence numbers, buffering and sync at the receiver.

import heapq, random

LOSS = 0.2                       # chance any single network hop drops a packet
DELAY = (0.01, 0.30)             # one-way delay in seconds, uniform: causes reordering
RETRY_AFTER = 0.5                # resend if no ack within this time
PUSH_TRIES = 3                   # server gives up pushing after this many tries
OFFLINE = (10.0, 15.0)           # the receiver's connection is down in this window
MESSAGES_PER_SENDER = 500

def at(t, fn, *args):
    heapq.heappush(events, (t, rng.random(), fn, args))

def hop(fn, *args, to_receiver=False):
    lost = rng.random() < LOSS
    if to_receiver and OFFLINE[0] <= clock < OFFLINE[1]:
        lost = True
    if not lost:
        at(clock + rng.uniform(*DELAY), fn, *args)

class Server:
    def __init__(self, safe):
        self.safe, self.log, self.seq_of = safe, [], {}
        self.expected, self.held = {}, {}
        self.attempts = self.duplicates = self.held_count = 0

    def receive(self, sender, n):
        self.attempts += 1
        msg_id = (sender.name, n)                       # client-generated ID
        if not self.safe:
            self.store(sender, msg_id)
            return
        expected = self.expected.get(sender.name, 0)
        if n < expected:                                # a retry of something stored
            self.duplicates += 1
            hop(sender.ack, n, self.seq_of[msg_id])
        elif n > expected:                              # an earlier message is missing
            self.held_count += 1
            self.held[msg_id] = sender                  # no ack yet; sender will retry
        else:
            self.store(sender, msg_id)
            self.expected[sender.name] = n + 1
            nxt = (sender.name, n + 1)
            if nxt in self.held:
                self.receive(self.held.pop(nxt), n + 1)

    def store(self, sender, msg_id):
        self.log.append(msg_id)
        seq = len(self.log)                             # per-conversation sequence number
        self.seq_of.setdefault(msg_id, seq)
        hop(sender.ack, msg_id[1], seq)
        self.push(seq, msg_id, 1)

    def push(self, seq, msg_id, attempt):
        if seq in receiver.acked or attempt > PUSH_TRIES:
            return
        hop(receiver.push, seq, msg_id, to_receiver=True)
        at(clock + RETRY_AFTER, self.push, seq, msg_id, attempt + 1)

class Sender:
    def __init__(self, name):
        self.name, self.acked = name, set()
    def send(self, n):
        if n not in self.acked:
            hop(server.receive, self, n)
            at(clock + RETRY_AFTER, self.send, n)
    def ack(self, n, seq):
        self.acked.add(n)

class Receiver:
    def __init__(self, safe):
        self.safe, self.shown, self.pending, self.acked = safe, [], {}, set()
        self.next_seq = 1
        self.dropped_dups = self.buffered = self.synced = 0
    def push(self, seq, msg_id):
        self.acked.add(seq)                             # ack (simplified: instant)
        if not self.safe:
            self.shown.append((seq, msg_id))
            return
        if seq < self.next_seq or seq in self.pending:
            self.dropped_dups += 1
            return
        if seq > self.next_seq:
            self.buffered += 1
        self.pending[seq] = msg_id
        self.drain()
    def drain(self):
        while self.next_seq in self.pending:
            self.shown.append((self.next_seq, self.pending.pop(self.next_seq)))
            self.next_seq += 1
    def sync(self):                                     # "give me everything after next_seq - 1"
        for seq in range(self.next_seq, len(server.log) + 1):
            if seq not in self.pending:
                self.synced += 1
                self.pending[seq] = server.log[seq - 1]
        self.drain()

def run(safe, seed=11):
    global rng, events, clock, server, receiver
    rng, events, clock = random.Random(seed), [], 0.0
    server, receiver = Server(safe), Receiver(safe)
    senders = [Sender("alice"), Sender("bob")]
    for s in senders:
        for n in range(MESSAGES_PER_SENDER):
            at(n * 0.05 + rng.random() * 0.01, s.send, n)
    if safe:
        at(OFFLINE[1], receiver.sync)                   # sync on reconnect
    while events:
        clock, _, fn, args = heapq.heappop(events)
        fn(*args)
    if safe:
        receiver.sync()                                 # periodic sync catches stragglers
    shown_ids = [m for _, m in receiver.shown]
    typing_inversions = sum(
        1 for s in senders for n in range(1, MESSAGES_PER_SENDER)
        if server.seq_of[(s.name, n)] < server.seq_of[(s.name, n - 1)])
    out_of_order = sum(1 for a, b in zip(receiver.shown, receiver.shown[1:]) if b[0] < a[0])
    print("safe" if safe else "naive")
    print(f"  attempts reaching the server        {server.attempts:,}")
    print(f"  messages stored                     {len(server.log):,} (typed {2*MESSAGES_PER_SENDER:,})")
    print(f"  stored out of the sender's order    {typing_inversions:,}")
    print(f"  shown to the receiver               {len(shown_ids):,} "
          f"({len(shown_ids) - len(set(shown_ids)):,} duplicates, "
          f"{2*MESSAGES_PER_SENDER - len(set(shown_ids)):,} missing)")
    print(f"  shown out of sequence order         {out_of_order:,}")
    if safe:
        print(f"  retries recognized at the server    {server.duplicates:,}")
        print(f"  early arrivals held at the server   {server.held_count:,}")
        print(f"  duplicate pushes dropped            {receiver.dropped_dups:,}")
        print(f"  pushes buffered behind a gap        {receiver.buffered:,}")
        print(f"  messages fetched by sync            {receiver.synced:,}")

run(safe=False)
run(safe=True)

naive
  attempts reaching the server        1,260
  messages stored                     1,260 (typed 1,000)
  stored out of the sender's order    406
  shown to the receiver               1,040 (206 duplicates, 166 missing)
  shown out of sequence order         465
safe
  attempts reaching the server        2,960
  messages stored                     1,000 (typed 1,000)
  stored out of the sender's order    0
  shown to the receiver               1,000 (0 duplicates, 0 missing)
  shown out of sequence order         0
  retries recognized at the server    598
  early arrivals held at the server   1,362
  duplicate pushes dropped            18
  pushes buffered behind a gap        766
  messages fetched by sync            200

The naive version stored 1,260 messages for 1,000 typed: every retry whose original had arrived became a second copy. The receiver saw 206 duplicates, missed 166 messages entirely (lost during the disconnection, or when push retries ran out, with nothing to catch them up), and saw 465 messages out of order. 406 messages were stored out of their sender’s typing order.

The safe version stored exactly 1,000, in typing order per sender, and the receiver showed all 1,000 once, in sequence. Each mechanism did part of the work:

Sync fetched 200 messages, a fifth of the conversation. The push path is a fast path that’s allowed to fail, and sync is the path that guarantees completeness. A design without sync loses messages whenever a device disconnects, whatever the push path does.

The run also shows a cost. Holding early arrivals without acknowledging them made the safe version take 2,960 attempts against 1,260, because each held message was resent until the gap ahead of it filled. A loss stalls everything the sender sends after it, which is head-of-line blocking. A client can bound it by limiting how many unacknowledged messages a device has in flight per conversation, and the server can acknowledge a held message as “received, waiting” so that the sender stops resending it.

Receipts as watermarks

Delivery and read receipts could be stored per message per member. In a group, that grows quickly. With 50 members, 1,000 messages a day, and each member opening the conversation 20 times a day (assumptions):

members, msgs_day, opens_per_member = 50, 1_000, 20     # assumptions
per_message = members * msgs_day
watermark = members * opens_per_member
print(f"per-message receipts: {per_message:,} writes, {per_message*(members-1):,} deliveries")
print(f"read watermark:       {watermark:,} writes, {watermark*(members-1):,} deliveries")

per-message receipts: 50,000 writes, 2,450,000 deliveries
read watermark:       1,000 writes, 49,000 deliveries

A watermark stores one number per member per conversation: last_delivered_seq and last_read_seq in the members table. Reading up to 812 implies reading everything before it, so there’s no information lost for the usual display (“read by 31 of 49”). The device sends a read only when the user actually views new messages, and the server coalesces receipt updates before fanning them out, so a burst of scrolling becomes one update. The same idea appears as consumer offsets in Kafka (chapter 8).

Offline sync and multiple devices

Every device keeps, per conversation, the highest sequence number it holds. On reconnect it has to find out which of possibly thousands of conversations changed. Sending a map of every conversation’s last sequence number would be large, and checking each one on the server would be slow.

A per-user inbox log solves this. Whenever a message is stored in a conversation, an entry (user_inbox_pos, conv_id, seq) is appended to each member’s inbox, with user_inbox_pos increasing per user. A device stores one number, its inbox position. On reconnect it sends sync {inbox_pos}, receives the list of conversations that changed and their new last sequence numbers, and then fetches each conversation’s missing range. A device offline for a week and a device offline for a second use the same code path.

Multiple devices fit the same model: each device is a separate reader with its own inbox position and its own delivery watermark. A message sent from a user’s phone is delivered to the same user’s laptop like any other member’s device, and the laptop recognizes its own user as the sender.

For a device that isn’t connected at all, a push notification goes through the platform services (APNs for Apple devices, FCM for Android). Their delivery is outside the system’s control, so a notification is a nudge to open the app, after which the device syncs. They aren’t a delivery channel. Chapter 27 covers them.

Group fan-out

For a direct conversation or a small group, the owner sends each message to each member’s connected devices: a handful of sends per message.

Large groups and channels behave more like the news feed. Sending one copy per online member means many copies to the same connection servers, since a large group’s members are spread across all of them. An alternative is for the owner to send one copy per connection server that holds at least one member, and let that server deliver locally. A simulation with 500 connection servers and 30% of members online (both assumptions), with members placed on servers at random:

import random
rng = random.Random(5)
SERVERS = 500          # assumption: connection servers in the fleet
ONLINE = 0.3           # assumption: share of members connected at any moment

print("members  online  per-member sends  servers reached  saving")
for members in (10, 100, 1_000, 10_000, 100_000):
    online = [m for m in range(members) if rng.random() < ONLINE]
    home = {m: rng.randrange(SERVERS) for m in online}   # which server holds each connection
    servers = len(set(home.values()))
    print(f"{members:>7,}  {len(online):>6,}  {len(online):>16,}  {servers:>15,}  {len(online)/max(servers,1):>5.1f}x")

members  online  per-member sends  servers reached  saving
     10       1                 1                1    1.0x
    100      30                30               29    1.0x
  1,000     303               303              221    1.4x
 10,000   2,963             2,963              500    5.9x
100,000  30,098            30,098              500   60.2x

Below about a thousand members, almost every online member is on a different server, so per-server delivery saves nothing and adds a lookup. Above ten thousand, every server is reached, and per-server delivery cuts sends by the ratio of online members to servers. So small groups use per-member delivery, and large channels use a publish-subscribe topic per channel that connection servers subscribe to while any of their devices are in the channel.

Redis pub/sub is a common choice for that topic, with one caveat: its documentation states that it has at-most-once delivery semantics. A message published while a subscriber is disconnected is lost to that subscriber. That’s acceptable only because sync is the correctness path, as the simulation showed. Large channels also usually drop per-member receipts and limit who can post, which removes most of the fan-out in the other direction.

Presence and typing

Presence looks simple and is often the most expensive part of chat. Each connected device sends a heartbeat (the WebSocket ping, or an application message) every few tens of seconds. The registry entry’s time-to-live is a small multiple of that interval, so a device that vanishes without closing its connection shows as offline once the entry expires. “Last seen” is the time of the last heartbeat.

The cost is fan-out. Every change of one user’s status could be sent to everyone who has that user as a contact, and status changes happen every time a phone locks or unlocks. Three limits keep it manageable:

• Subscribe lazily. A device receives presence only for the conversations on screen, and subscribes when one is opened.
• Coarsen. “Online” and “last seen within the hour” change far less often than a precise timestamp.
• Drop under load. Presence and typing indicators are best-effort by requirement. They’re never stored, never retried, and are the first traffic shed when a server is overloaded (chapter 16).

Failure modes

Almost every row ends in the same place: the device reconnects and syncs. That’s by design. The real-time path can fail in many ways, and sync makes all of them recoverable without special cases.

The takeaway

A chat system’s hard parts are correctness under unreliable delivery and the state held in long-lived connections. One owner per conversation assigning sequence numbers gives every member the same order, gap detection and cheap sync. Client message IDs make retries safe, and per-sender counters keep a sender’s own messages in typing order. In the simulation, sequence numbers and IDs removed duplicates and misordering, and sync recovered a fifth of the messages the push path never delivered. Real-time delivery is the fast path, and sync is the correctness path. Receipts are watermarks rather than per-message flags, large groups fan out per server rather than per member, and presence is best-effort by design.