Design a Chat App: Messaging System Design Interview Guide

"Design a chat app" looks like a question about sending messages, and sending is the easy part. The hard parts are finding the recipient's open connection among a million, never losing a message the sender saw ticked, and giving a phone that was offline for a day exactly what it missed, in order, without duplicates. A good answer is built around those three problems.

The problem it solves

One-to-one and group messaging with delivery in well under a second when both people are online, and reliable catch-up when they are not. The lesson's scale: one million connected users and 50,000 messages a second at peak.

Those numbers shape the design immediately. Polling is out: a million phones asking "anything new?" every few seconds is far more traffic than the messages themselves. Each phone holds a persistent connection, usually a WebSocket, to one of many gateway servers. That makes gateways stateful, since a socket lives on one machine, and it creates the central question: when a message for Ben arrives, which gateway holds Ben's socket?

The intuition

The delivery path has four steps, and their order is the design:

1. The sender's socket carries the message to its gateway. No new connection per message.
2. Persist, then acknowledge. The message is written to a durable store and given a sequence number within its conversation. Only then does the sender see the tick. If a gateway dies before the write, the sender has no tick and retries; if it dies after, nothing is lost.
3. Look up the recipient in the session registry, a fast key-value map from user to the gateway holding their socket, updated on every connect and disconnect.
4. Push it down that socket, forwarded to the right gateway rather than broadcast to all of them. If the recipient has no socket, queue a push notification instead; the message is already stored.

Recovery then needs no special machinery. Each phone remembers the last sequence number it has per conversation. On reconnect it registers with a gateway and asks for everything after that number. A gap in live delivery triggers the same pull. Retries from a sender carry a client message id, so the store can recognise a resend and not store it twice.

Group chats reuse the same pieces: one stored copy with one sequence, fanned out to each member's gateway.

Rough sizing helps the conversation: 50,000 messages a second is an upper bound of about 4.3 billion a day if the peak lasted all day, and at an assumed 200 bytes each, under a terabyte a day before replication. Those are illustrative assumptions for the discussion, not measurements.

Watch it run

The animation starts with a million phones, each holding one open socket to one of many gateways. A sends a message up the socket it already has; no new connection. The gateway stores it first and gives it a sequence number, before acknowledging anything. Only then does the sender get its tick, and a crash from here on loses nothing. Where is B? The registry maps each user to the gateway holding their socket: gateway 2, so the message is forwarded there rather than broadcast. It is pushed down B's socket, and B has it in about 40 ms without ever asking. Now B is offline instead, so the registry has no gateway to hand back. The stored copy simply waits, and a push notification is queued. B reconnects, re-registers, and pulls everything after sequence 4470. The last two frames name the risks: sockets are state, so gateways are stateful and the registry sits on every delivery, where stale entries hurt. And acknowledging before storing is faster, until a gateway dies mid-message.

The code

A toy model, not a messaging server: dictionaries stand in for the store, the registry and the gateways. The order of operations in send is the design. Ben gets the first message live, misses the second while offline (the phone's retry of it is stored once), and pulls it on reconnect:

class Chat:
    """Toy model: gateways hold sockets, a registry finds them, a store orders messages."""
    def __init__(self):
        self.store = {}            # conversation -> [(seq, sender, text)]
        self.ids = {}              # (sender, client_id) -> seq: retries are idempotent
        self.registry = {}         # user -> gateway currently holding the socket
        self.alive = set()         # gateways that are up
        self.inbox = {}            # user -> conversation -> messages on the phone
        self.pushes = []           # notifications queued for offline users

    def connect(self, user, gateway):
        self.alive.add(gateway)
        self.registry[user] = gateway
        self.sync(user)            # pull everything after the last sequence seen

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

    def crash(self, gateway):
        self.alive.discard(gateway)   # registry entries now point at a dead gateway

    def send(self, sender, to, text, client_id):
        conv = tuple(sorted((sender, to)))
        if (sender, client_id) in self.ids:            # a retry: already stored
            return self.ids[sender, client_id]
        log = self.store.setdefault(conv, [])
        msg = (len(log) + 1, sender, text)
        log.append(msg)                                # 1. persist and sequence
        self.ids[sender, client_id] = msg[0]           # 2. only now ack the sender
        gateway = self.registry.get(to)                # 3. where is the recipient?
        if gateway in self.alive:
            self.receive(to, conv, msg)                # 4. push down the open socket
        else:
            self.pushes.append((to, msg[0]))           #    or queue a notification
        return msg[0]

    def receive(self, user, conv, msg):
        mine = self.inbox.setdefault(user, {}).setdefault(conv, [])
        if msg[0] == len(mine) + 1:
            mine.append(msg)                           # next in order
        elif msg[0] > len(mine) + 1:
            self.sync(user)                            # a gap: pull what is missing

    def sync(self, user):
        for conv, log in self.store.items():
            if user in conv:
                mine = self.inbox.setdefault(user, {}).setdefault(conv, [])
                mine.extend(log[len(mine):])           # everything after my last seq

chat = Chat()
chat.connect("ana", "gw1")
chat.connect("ben", "gw2")
chat.send("ana", "ben", "on my way", client_id=1)
print(chat.inbox["ben"])            # {('ana', 'ben'): [(1, 'ana', 'on my way')]}
chat.disconnect("ben")
chat.send("ana", "ben", "at the door", client_id=2)
chat.send("ana", "ben", "at the door", client_id=2)   # the phone retried: same id
print(chat.pushes, len(chat.store[("ana", "ben")]))    # [('ben', 2)] 2
chat.connect("ben", "gw3")
print([seq for seq, *_ in chat.inbox["ben"][("ana", "ben")]])   # [1, 2]

Why persist before acknowledging: 10,000 seeded sends through gateways that die mid-message 1% of the time. Acknowledging first loses every message whose gateway died between the tick and the write; storing first loses none, because a sender with no tick retries:

import random

def lost_messages(ack_first, sends=10_000, crash_rate=0.01):
    """Count messages the sender saw acknowledged but that were never stored."""
    stored, acked = set(), set()
    for m in range(sends):
        while m not in stored:
            crash = random.random() < crash_rate
            if ack_first:
                acked.add(m)                           # tick shown to the sender
                if crash:
                    break                              # died before the write: gone
                stored.add(m)
            else:
                if crash:
                    continue                           # died before the write: no tick, retry
                stored.add(m)
                acked.add(m)
    return len(acked - stored)

random.seed(26)
print(lost_messages(ack_first=True), lost_messages(ack_first=False))   # 105 0

Checked on 300 seeded random histories of sends, resends, disconnects, reconnects and gateway crashes among four users: once everyone reconnects, every phone must hold exactly the messages of each conversation, in the order they were sent, compared against an independent list the test keeps itself, with sequence numbers gap-free and every resend stored once:

random.seed(26)
ok = True
for _ in range(300):
    c, users, truth, sent = Chat(), ["u0", "u1", "u2", "u3"], {}, 0
    for u in users:
        c.connect(u, random.choice(["g1", "g2", "g3"]))
    for _ in range(80):
        r, (a, b) = random.random(), random.sample(users, 2)
        if r < 0.55:
            sent += 1
            c.send(a, b, "m%d" % sent, sent)
            truth.setdefault(tuple(sorted((a, b))), []).append("m%d" % sent)
            if random.random() < 0.2:
                c.send(a, b, "m%d" % sent, sent)       # a resend of the same message
        elif r < 0.7:
            c.disconnect(a)
        elif r < 0.85:
            c.connect(a, random.choice(["g1", "g2", "g3"]))
        else:
            c.crash(random.choice(["g1", "g2", "g3"]))
    for u in users:
        c.connect(u, "g9")                             # everyone comes back
    for conv, texts in truth.items():
        log = c.store[conv]
        ok &= [s for s, *_ in log] == list(range(1, len(log) + 1))
        for u in conv:
            ok &= [text for *_, text in c.inbox[u][conv]] == texts
    ok &= sum(len(log) for log in c.store.values()) == sent
print(ok)                                              # True

The complexity

• Per message: one durable write, one registry lookup, one forward between gateways. Constant work, independent of the user count.
• Reconnect: proportional to the messages missed, read by sequence range.
• Group message: one write, then one delivery per online member; fan-out grows with group size.
• State: one registry entry per connected user, one socket per user on some gateway.

Where it goes wrong

• Acknowledging before persisting. Faster, and it loses messages whenever a gateway dies at the wrong moment.
• Stale registry entries. A phone that drops off a train leaves its entry pointing at a socket that no longer exists. Heartbeats and expiry keep the registry honest; sequence-based sync covers the gap.
• Ordering by timestamp. Clocks on different servers disagree. Order within a conversation by the sequence the store assigns.
• No idempotency. Mobile clients retry constantly; without a client message id, retries become duplicates.
• Broadcasting to every gateway. It works for ten gateways and collapses at a hundred. Look up, then forward.

When it shows up in interviews

It is one of the classic system design prompts, and its follow-ups are well worn: read receipts and typing indicators (ephemeral, never stored), group chats, presence, multiple devices per user, and end-to-end encryption. The offline path is the same idea as a notification system, and the store behind it is usually partitioned by conversation, the approach described in database sharding.

How to say it in an interview

"Each phone keeps a WebSocket to one of many stateful gateways, and a registry maps each user to their gateway. When a message arrives I persist it first and give it a per-conversation sequence number, then acknowledge, so a gateway crash cannot lose an acknowledged message. I look up the recipient, forward to their gateway and push down the socket, or queue a push notification if they are offline. On reconnect the phone asks for everything after its last sequence number, and client message ids make retries idempotent."