Chapter 30 of 33

Design a Chat Application

WhatsApp, Telegram, Slack and Discord all solve the same core problem: when Asha presses "send", Ravi's phone should show the message within a fraction of a second, even if Ravi is in a different city, on a weak 4G network, or offline until tomorrow. This makes a chat application very different from the URL shortener in the previous chapter, Design a URL Shortener. There, the client always asked and the server answered. In chat, the server must push data to clients the moment it arrives, keep hundreds of millions of connections open, and never lose or reorder a message.

A chat system delivers messages between users in near real time over long-lived connections, stores them durably, delivers them later to offline users, keeps a consistent order within each conversation, and reports status such as sent, delivered, read and online.


Step 1: Requirements

Functional

  1. One-to-one chat and group chat (groups up to a fixed size; WhatsApp's current limit is 1,024 members).

  2. Offline delivery: messages to an offline user are delivered when they come back, plus a push notification.

  3. Message status: sent (reached the server), delivered (reached the recipient's device), read.

  4. Presence: online / last seen; optionally "typing...".

  5. Multiple devices per user (phone + laptop) see the same conversation.

  6. Media (photos, documents) and chat history on a new device.

Non-Functional

  • Low latency: delivery in well under a second for online users.

  • Durability: once the sender sees "sent", the message must never be lost.

  • Ordering: everyone in a conversation sees messages in the same order.

  • High availability and scale to hundreds of millions of daily users.

  • Privacy: ideally end-to-end encryption, so the server cannot read message content.


Step 2: Estimation

Assumptions: 500 million daily active users, each sending 40 messages a day, about 200 bytes stored per message (text plus IDs, timestamps and status), peak twice the average, 20% of daily users online at the busiest moment, and one tuned gateway server holding about 200,000 open connections.

# Back-of-the-envelope numbers for a WhatsApp-style chat service
dau = 500_000_000                 # daily active users
msgs_per_user_per_day = 40        # messages sent per user per day
bytes_per_msg = 200               # text (~100 B) + ids, timestamps, status
peak_factor = 2
peak_online_fraction = 0.2        # share of DAU connected at the busiest moment
conns_per_gateway = 200_000       # open WebSocket connections one tuned server holds

msgs_per_day = dau * msgs_per_user_per_day
avg_qps = msgs_per_day / 86_400
storage_per_day_tb = msgs_per_day * bytes_per_msg / 1e12
concurrent = dau * peak_online_fraction
gateways = concurrent / conns_per_gateway

print(f"Messages per day: {msgs_per_day:,}")
print(f"Message QPS (avg / peak): {avg_qps:,.0f} / {avg_qps*peak_factor:,.0f}")
print(f"Storage per day: {storage_per_day_tb:.1f} TB, per year: {storage_per_day_tb*365/1000:.2f} PB")
print(f"Concurrent connections at peak: {concurrent:,.0f}")
print(f"Gateway servers needed (no headroom): {gateways:,.0f}")

Output:

Messages per day: 20,000,000,000
Message QPS (avg / peak): 231,481 / 462,963
Storage per day: 4.0 TB, per year: 1.46 PB
Concurrent connections at peak: 100,000,000
Gateway servers needed (no headroom): 500
  • ~230,000 messages/s on average, ~460,000 at peak. Every message is written once and read by only one or a few devices, so writes are of the same order as reads. Unlike the read-heavy URL shortener, this is a write-heavy system.

  • ~4 TB of new data per day if messages are kept on the server, about 1.5 PB a year. That calls for a horizontally scalable store optimised for writes.

  • ~100 million concurrent connections needing about 500 connection servers before headroom; in practice you plan for more, so a server failure or deployment does not overload the rest. Holding connections, not CPU, is the defining constraint.


Step 3: How Does the Server Push to the Client?

Plain HTTP is request-response: the client asks, the server answers. For chat, the server needs to send data whenever a message arrives. Options:

Technique

How it works

Pros

Cons

Short polling

Client asks "anything new?" every few seconds

Trivial to build

Most requests return nothing; wasted battery and server load; delay up to the polling interval

Long polling

Client asks; server holds the request open until a message arrives or a timeout, then client asks again

Near real time over plain HTTP

New request after every message; awkward for sending; timeouts and reconnects

Server-Sent Events (SSE)

One long HTTP response streaming events from server to client

Simple, auto-reconnect built into browsers

Server-to-client only; sending still needs separate requests

WebSocket (RFC 6455)

Starts as an HTTP request with an Upgrade header, then becomes a persistent, full-duplex connection over the same TCP connection

Both directions, tiny per-message overhead, lowest latency

Stateful servers; load balancing and reconnect logic are harder

Chat apps use WebSockets (or a similar persistent protocol over TCP; WhatsApp historically used a customised XMPP-style protocol). Non-real-time actions such as login, profile updates and fetching old history can still use normal REST APIs.

Client                                   Server
  | GET /chat HTTP/1.1                     |
  | Upgrade: websocket                     |
  | Connection: Upgrade                    |
  | Sec-WebSocket-Key: ...                 |
  |--------------------------------------->|
  |<---------------------------------------|
  | HTTP/1.1 101 Switching Protocols       |
  |                                        |
  |<======= frames in both directions =====>|   one TCP connection, kept open

Step 4: High-Level Design

   Asha's phone                                                Ravi's phone
        |  WebSocket                                       WebSocket |
        v                                                           v
  +-------------+      +------------------+               +-------------+
  | Gateway 7   |----->|  Chat (message)  |-------------> | Gateway 42  |
  | (holds the  |      |  service         |  route to the | (holds Ravi's
  | connection) |      |  - assign seq/ID |  gateway that |  connection)|
  +-------------+      |  - persist       |  owns Ravi    +-------------+
                       |  - fan out       |
                       +---+-----+-----+--+
                           |     |     |
          +----------------+     |     +-------------------+
          v                      v                         v
  +----------------+   +--------------------+    +-------------------+
  | Session registry|   | Message store      |    | Push notification |
  | (Redis):        |   | (Cassandra-style,  |    | service -> APNs / |
  | user -> gateway |   |  partitioned by    |    | FCM when offline  |
  +----------------+   |  conversation)     |    +-------------------+
                       +--------------------+
  Other services: Presence, Group membership, Media upload (object storage + CDN),
  REST API for login / history; Kafka between components for async work.

Components

  • Gateway (connection) servers: hold the WebSocket connections. They are stateful (each knows which users are connected to it) but contain no business logic, so they stay simple and can hold many connections. The load balancer only picks a gateway at connect time (chapter Load Balancing); after that the connection stays put.

  • Session registry: a fast key-value store (Redis) mapping user/device → gateway, updated on connect and disconnect, with a TTL refreshed by heartbeats so crashed gateways do not leave stale entries.

  • Chat service: stateless; validates, assigns ordering, persists, and routes messages.

  • Message store: durable storage of messages (or of undelivered messages only, see below).

  • Push notification service: sends via Apple Push Notification service (APNs) or Firebase Cloud Messaging (FCM) when the recipient has no live connection, because mobile operating systems kill background sockets.


Step 5: Life of a Message

1. Asha's app creates client_msg_id = "a-001", shows the message with a clock icon,
   and sends it over her WebSocket to Gateway 7.
2. Gateway 7 forwards it to the Chat service.
3. Chat service: drop it if (conversation, client_msg_id) was already seen;
   otherwise assign the next sequence number for the conversation (#57).
4. Persist the message (replicated write).           <-- only now is it safe
5. ACK to Asha: "stored as #57"  -> one tick (sent).
6. Look up Ravi in the session registry -> Gateway 42.
   a. Online:  forward to Gateway 42, which pushes it down Ravi's WebSocket.
   b. Offline: keep it for later delivery and ask the push service to notify him.
7. Ravi's app stores it and sends a DELIVERED receipt -> Asha sees two ticks.
8. When Ravi opens the chat, a READ receipt flows back -> ticks turn blue.

Why persist before acknowledging? If the server ACKs first and then crashes, Asha believes the message was sent but it is gone. The order "store, then ACK" is what makes the "sent" tick trustworthy. Receipts are just small messages travelling the same pipeline in the reverse direction.

Delivery Guarantees: At-Least-Once + Deduplication

Networks fail at the worst moments. If Asha's ACK is lost, her app cannot know whether the server stored the message, so it retries. Retries make delivery at-least-once, which can create duplicates. The fix is idempotency: the client attaches a unique client_msg_id, and the server ignores a message it has already stored. Recipients likewise ignore a sequence number they already have. The combination behaves like "exactly once" from the user's point of view (the same idea as in Message Queues & Pub/Sub).

Simulation: Ordering, Retries and Offline Delivery

This Python model contains no networking, only the core rules: persist, then fan out; queue for offline users; drop retried duplicates; assign a per-conversation sequence number.

from collections import defaultdict
from dataclasses import dataclass


@dataclass
class Message:
    conv_id: str
    seq: int              # per-conversation order, assigned by the server
    client_msg_id: str    # chosen by the sender's phone, used to drop duplicates
    sender: str
    text: str


class ChatServer:
    """In-memory model of the message service: no sockets, just the logic."""

    def __init__(self):
        self.online = {}                        # user -> callback (stands in for a WebSocket)
        self.next_seq = defaultdict(int)        # conv_id -> last sequence number
        self.seen = {}                          # (conv_id, client_msg_id) -> Message
        self.history = defaultdict(list)        # conv_id -> stored messages
        self.pending = defaultdict(list)        # user -> messages waiting for delivery
        self.members = {}                       # conv_id -> list of users

    def connect(self, user, deliver):
        self.online[user] = deliver
        waiting, self.pending[user] = self.pending[user], []
        for msg in waiting:                     # flush the offline inbox, in order
            deliver(msg)

    def disconnect(self, user):
        self.online.pop(user, None)

    def send(self, conv_id, sender, client_msg_id, text):
        key = (conv_id, client_msg_id)
        if key in self.seen:                    # retry of a message we already stored
            return ("ACK (duplicate ignored)", self.seen[key].seq)
        self.next_seq[conv_id] += 1
        msg = Message(conv_id, self.next_seq[conv_id], client_msg_id, sender, text)
        self.seen[key] = msg
        self.history[conv_id].append(msg)       # 1. persist first
        for user in self.members[conv_id]:      # 2. then fan out to every other member
            if user == sender:
                continue
            if user in self.online:
                self.online[user](msg)
            else:
                self.pending[user].append(msg)  # 3. offline: queue + push notification
        return ("ACK", msg.seq)


def device(name):
    def deliver(msg):
        print(f"  [{name}'s phone] #{msg.seq} {msg.sender}: {msg.text}  -> sends DELIVERED receipt")
    return deliver


server = ChatServer()
server.members["group:gate-prep"] = ["asha", "ravi", "meera"]
server.connect("asha", device("asha"))
server.connect("ravi", device("ravi"))          # meera is offline

print("asha sends:", server.send("group:gate-prep", "asha", "a-001", "Mock test at 7 pm?"))
print("ravi sends:", server.send("group:gate-prep", "ravi", "r-001", "Yes, joining"))

# asha's network drops before the ACK arrives, so her phone retries the same message
print("asha retries:", server.send("group:gate-prep", "asha", "a-001", "Mock test at 7 pm?"))

print("meera comes online:")
server.connect("meera", device("meera"))
print("Stored history:", [(m.seq, m.sender) for m in server.history["group:gate-prep"]])

Output:

  [ravi's phone] #1 asha: Mock test at 7 pm?  -> sends DELIVERED receipt
asha sends: ('ACK', 1)
  [asha's phone] #2 ravi: Yes, joining  -> sends DELIVERED receipt
ravi sends: ('ACK', 2)
asha retries: ('ACK (duplicate ignored)', 1)
meera comes online:
  [meera's phone] #1 asha: Mock test at 7 pm?  -> sends DELIVERED receipt
  [meera's phone] #2 ravi: Yes, joining  -> sends DELIVERED receipt
Stored history: [(1, 'asha'), (2, 'ravi')]

Asha's retry did not create a second copy (it returned the original sequence number 1), and Meera, who was offline, received both messages in the correct order the moment she connected.


Step 6: Ordering and Message IDs

Using each phone's clock to order messages fails: phone clocks drift and can be set wrongly by hand. Messages need an order decided by the server.

  • Per-conversation sequence number: the chat service assigns 1, 2, 3 ... within each conversation. This gives a clear total order inside a chat, which is all users can see. Assigning it requires that one place owns each conversation's counter at a time (for example, by routing all messages of a conversation to the same partition, or using an atomic counter in the store).

  • Globally unique, time-sortable IDs: a Snowflake-style 64-bit ID (timestamp bits + machine ID bits + per-millisecond sequence bits) can be generated on any server without coordination and sorts roughly by time. Useful as the message's primary ID and as the clustering key in storage.

There is no need for a single global order across all conversations; that would be a huge bottleneck for no benefit.


Step 7: Storing Messages

The workload is huge write volume, and reads that are almost always "the latest N messages of conversation X", paging backwards. Wide-column stores such as Cassandra, ScyllaDB or HBase fit this well: they spread partitions over many nodes with consistent hashing (chapter Consistent Hashing) and write sequentially via log-structured storage. Discord, for example, has publicly described storing its messages first in Cassandra and later in ScyllaDB; Facebook Messenger used HBase.

CREATE TABLE messages (
    conversation_id  text,
    bucket           int,         -- e.g. week number, so one busy group
                                  -- does not grow an unbounded partition
    message_id       bigint,      -- Snowflake ID or per-conversation seq
    sender_id        text,
    body             blob,        -- ciphertext if end-to-end encrypted
    PRIMARY KEY ((conversation_id, bucket), message_id)
) WITH CLUSTERING ORDER BY (message_id DESC);

-- "latest 50 messages":   SELECT ... WHERE conversation_id = ? AND bucket = ? LIMIT 50;

The partition key keeps a conversation's messages together on the same replicas, and the clustering order keeps them sorted, so loading a chat is one sequential read. Smaller, relational data (users, groups, memberships) can live in a SQL database.

Store Forever or Until Delivered?

A product choice with big system consequences. WhatsApp's model keeps messages on its servers only until they are delivered (undelivered messages are deleted after 30 days; history lives on the devices, with optional encrypted backups). Slack, Telegram cloud chats and Discord keep full history on the server so any device can scroll back. "Store until delivered" massively reduces storage; "store forever" enables search and multi-device history.

Multi-Device Sync

Each device keeps a cursor: the last sequence number it has for each conversation. On reconnect, the device asks "give me everything after #57", which handles offline periods and multiple devices in one uniform way. A message from Asha is also delivered to Asha's other devices so her laptop shows what she sent from her phone.


Step 8: Group Chats

For a group, the chat service looks up the member list and delivers the message to every member's devices: fan-out on write. With a cap of about a thousand members, this is fine: one message becomes at most about a thousand deliveries, and the message itself is stored once per conversation, not once per member. The number of members multiplies network work, so groups are capped, and very large broadcast-style channels are designed differently (recipients pull new posts instead of having each one pushed), a push-versus-pull trade-off that comes up again whenever one sender reaches a very large audience.


Step 9: Presence, Media and Encryption

Presence (Online / Last Seen)

  • The client sends a small heartbeat every few tens of seconds. If heartbeats stop for longer than a timeout, the user is marked offline and "last seen" is stored. Using heartbeats instead of the disconnect event avoids flicker when a phone switches between Wi-Fi and mobile data.

  • Broadcasting every status change to every contact would be enormous. Systems send presence only to users who currently have the chat open (subscribe on open, unsubscribe on close), and treat presence as best effort: a few seconds of staleness is fine.

  • "Typing..." indicators are sent but never stored.

Media

Large files never travel through the chat pipeline. The sender uploads the (encrypted) file to object storage, usually through a pre-signed URL, and sends a normal small message containing the file's reference, size and decryption key; recipients download it from storage or a CDN (chapters Object Storage & File Storage and Content Delivery Networks (CDN)). Thumbnails are sent inline so the chat renders instantly.

End-to-End Encryption

With end-to-end encryption, only the sender's and recipients' devices hold the keys; the server stores and forwards ciphertext. WhatsApp and Signal use the Signal Protocol, which combines an initial key agreement (with keys pre-published to the server) and a "double ratchet" that changes keys with every message, so stealing one key does not reveal past or future messages. (Signal has since strengthened the initial key agreement against future quantum computers with PQXDH; the overall design is unchanged.) Design consequences: the server cannot search message content or build server-side previews, groups need key distribution among members, and each extra device needs its own keys. Encryption in transit (TLS) to the gateway is used in all cases.


Step 10: Failures and Scaling

  • Gateway crash: its clients reconnect (with randomised backoff, so millions do not reconnect in the same second), land on other gateways, update the registry, and resync from their cursors. Nothing is lost because messages are persisted before being acknowledged.

  • Deployments: drain gateways gradually, asking clients to reconnect elsewhere, rather than killing millions of sockets at once.

  • Between services: a queue such as Kafka (partitioned by conversation ID, which also preserves per-conversation order) decouples the chat service from push notifications, analytics and search indexing.

  • Multi-region: users connect to the nearest region; messages between regions travel over the backbone. Keeping each conversation's sequence numbers in one home region avoids conflicting orders.


Common Mistakes

  • Using HTTP polling for message delivery at this scale.

  • Ordering messages by client timestamps.

  • Acknowledging before persisting, which makes "sent" a lie after a crash.

  • No deduplication, so retries show the same message twice.

  • Putting business logic in gateway servers, making these stateful machines heavy and risky to deploy.

  • Sending media through the WebSocket pipeline instead of object storage.

  • Storing a copy of each group message per member.

  • Forgetting offline users and push notifications.


Interview Questions

1. Why WebSockets instead of long polling for chat?

A WebSocket is one persistent, full-duplex connection with very small per-frame overhead, so the server can push messages instantly and the client can send on the same connection. Long polling needs a new HTTP request after every response and separate requests for sending, wasting bandwidth, battery and server resources at scale.

2. How does the chat service know which server to send Ravi's message to?

A session registry (for example Redis) maps each user's devices to the gateway holding their connection. Gateways write the entry on connect, refresh it with heartbeats (TTL) and remove it on disconnect. The chat service looks up the recipient and forwards to that gateway; if no entry exists, the user is offline.

3. How do you guarantee messages are not lost or duplicated?

Persist the message (replicated) before acknowledging the sender; retry unacknowledged sends from the client (at-least-once); deduplicate using a client-generated message ID; recipients ACK delivery and resync by sequence-number cursor after reconnecting, ignoring sequence numbers they already hold.

4. How do you keep messages in order?

The server assigns a monotonically increasing sequence number per conversation (or a time-sortable ID from a single owner of that conversation), and clients display by that number, not by device clocks. Partitioning queues by conversation ID keeps per-conversation order through the pipeline. No global order across conversations is needed.

5. With 100 million concurrent users, how many gateway servers do you need?

At about 200,000 connections per server, 100M ÷ 200,000 = 500 servers, plus headroom for failures and deployments (for example 30 to 50% more). The limit is memory and file descriptors per connection, not CPU.

6. Why choose a wide-column store like Cassandra for messages?

Very high write throughput with horizontal scaling, and a data model where a partition key (conversation) plus a clustering key (message ID) makes "latest N messages of a chat" a single sorted, sequential read. Joins and complex transactions, the strengths of SQL, are not needed for messages.


Summary

  • Chat needs server push: use persistent WebSocket connections held by stateful gateway servers; keep logic in stateless chat services.

  • A session registry maps users to gateways; offline users get stored messages plus push notifications.

  • Message flow: dedupe → assign sequence → persist → ACK (sent) → deliver (delivered) → read receipt (read).

  • At-least-once delivery + client message IDs = no loss and no visible duplicates.

  • Order with per-conversation sequence numbers, never device clocks.

  • Store messages in a wide-column store partitioned by conversation (and time bucket), clustered by message ID.

  • Groups: fan-out on write with a member cap; media through object storage; presence via heartbeats, best effort; end-to-end encryption with the Signal Protocol.

In chat design, the connection is the product: keep it open, store before you acknowledge, and order by the server, not the clock.