Design a Chat App

The question

"Design a chat application: one-to-one and small group chats, online status, and sent/delivered/read receipts."

Clarify the requirements

• Functional: 1:1 and group chats (up to 200 members), text messages (media is out of scope or via links), message history, online/last-seen status, delivery and read receipts, push notifications when offline.
• Scale: 50 million daily active users, 40 messages sent per user per day.
• Non-functional: messages appear in under a second; messages are never lost; order is preserved within a conversation; works on flaky mobile networks.

Estimate the scale

• Messages: 50M × 40 = 2 billion/day ≈ 23,000 messages/s (peak ~60,000/s).
• Concurrent connections: if 20% are online at peak, 10 million open connections. At ~100,000 connections per gateway server, that's ~100 servers.
• Storage: 2B × ~200 bytes ≈ 400 GB/day ≈ 150 TB/year before replication. A write-heavy, append-only workload.

API and data model

Clients keep a WebSocket open to a gateway; REST is used for history and setup.

WS  send     { client_msg_id, conversation_id, text }
WS  receive  { message_id, conversation_id, sender_id, text, seq, sent_at }
WS  ack      { conversation_id, seq, status: "delivered" | "read" }
GET /conversations/{id}/messages?before_seq=...&limit=50

messages:      (conversation_id, seq) PK | message_id | sender_id | text | sent_at
conversations: conversation_id | type | members
receipts:      conversation_id | user_id | delivered_seq | read_seq

Messages are partitioned by conversation_id and ordered by seq within it: a wide-column store or a sharded SQL table suits this append-and-read-recent pattern.

High-level design

 client A ══ WebSocket ══► gateway 1 ─┐                     ┌─► message store (by conversation)
                                      ├─► chat service ─────┤
 client B ══ WebSocket ══► gateway 7 ◄┘        │            └─► presence (Redis: user -> gateway)
                                               └─► push service (APNs / FCM) for offline users

1. A sends a message to its gateway; the chat service assigns the next seq for the conversation and stores it.
2. It acknowledges A ("sent"), then looks up which gateway each recipient is connected to (presence map) and forwards the message.
3. Online recipients get it over their socket and ack "delivered"; offline recipients get a push notification and fetch history when they reconnect.

Deep dives

1. Ordering and duplicates. Clients retry on bad networks, so the same message can arrive twice. The client sends a client_msg_id; the server ignores repeats of the same ID (idempotency). A per-conversation seq (from an atomic counter for that conversation) gives every member the same order, and gaps tell a client it missed something and should fetch history.

class ChatService:
    def __init__(self):
        self.next_seq = {}        # conversation -> next sequence number
        self.seen = {}            # (conversation, client_msg_id) -> seq already assigned
        self.log = {}             # conversation -> list of (seq, sender, text)

    def send(self, conversation, sender, client_msg_id, text):
        key = (conversation, client_msg_id)
        if key in self.seen:                       # a retry: return the original result
            return self.seen[key], "duplicate ignored"
        seq = self.next_seq.get(conversation, 1)
        self.next_seq[conversation] = seq + 1
        self.seen[key] = seq
        self.log.setdefault(conversation, []).append((seq, sender, text))
        return seq, "stored"


def missing(received_seqs):
    '''A client that sees a gap knows to fetch history.'''
    expected = range(1, max(received_seqs) + 1)
    return [s for s in expected if s not in received_seqs]


chat = ChatService()
print(chat.send("c1", "ana", "a-1", "hi!"))
print(chat.send("c1", "ben", "b-1", "hey Ana"))
print(chat.send("c1", "ana", "a-1", "hi!"))           # network retry of the first message
print(chat.send("c1", "ana", "a-2", "lunch?"))
print("history:", [f"{seq}:{who}:{text}" for seq, who, text in chat.log["c1"]])
print("client got 1, 2 and 4 -> missing:", missing({1, 2, 4}))

(1, 'stored')
(2, 'stored')
(1, 'duplicate ignored')
(3, 'stored')
history: ['1:ana:hi!', '2:ben:hey Ana', '3:ana:lunch?']
client got 1, 2 and 4 -> missing: [3]

2. Finding the recipient's connection. Each gateway registers user_id → gateway_id in Redis when a socket opens (with a heartbeat TTL). The chat service looks this up and routes the message to that gateway, often through a pub/sub channel per gateway.

3. Group fan-out. For a 200-member group, write the message once (by conversation) and fan out delivery to online members. Very large groups (thousands) move toward a pull model: notify "new messages" and let clients fetch.

4. Presence. "Online" = has a live socket; "last seen" = time of the last heartbeat. Broadcasting every status change to every contact is expensive, so send presence only to users who currently have that chat open, and batch updates.

Trade-offs

• WebSockets vs long polling: WebSockets give low latency and server push; long polling is simpler through old proxies but costs more requests.
• Storage model: per-conversation partitions make history reads fast; a user's inbox (list of recent conversations) is kept as a separate, small index.
• Delivery guarantees: at-least-once delivery + client-side dedup (by message_id) is simpler and safer than trying for exactly-once.
• End-to-end encryption (if required) moves message content out of the server's reach and changes search, backup and multi-device sync.

What interviewers look for

• Persistent connections and how the server finds a user's connection.
• Ordering within a conversation and idempotent retries.
• An offline path (push notification + history sync).
• Realistic numbers for connections and storage.

Key points

• WebSocket gateways + a presence map (user → gateway) in Redis.
• Per-conversation sequence numbers give order; gaps trigger history fetches.
• Client message IDs make retries safe.
• Offline users get a push, then sync from history.