Chat System (WhatsApp/Messenger) — System Design Interview

Phase 1: Clarify, Scope & Constraints

Interviewer: "Design a chat system like WhatsApp or Facebook Messenger. Where do you start?"

Candidate: "Let me clarify the core scope. Chat systems range from 1-1 messaging to large group chats to broadcast channels. What's the primary use case — 1-1 messaging, group chats, or both?"

Interviewer: "Both. 1-1 messaging and group chats up to 500 members."

Candidate: "Good. The core user journeys I want to cover:

1. Send message: User A sends a message to User B (or a group). The message is delivered in real time if the recipient is online; if offline, delivered when they reconnect.
2. Receive message: User B sees the message appear instantly in the conversation view.
3. Read receipts & status: Sender sees 'sent to server' (single check), 'delivered to device' (double check), and 'read' (blue check) indicators.
4. Online presence: Users can see if contacts are online or when they were last active.
5. Message history: Users can scroll back through conversation history.

Non-goals for V1:

• Voice/video calls (separate real-time media system)
• Message reactions, polls, or rich media upload (focus on text messages with media URLs)
• End-to-end encryption protocol design (assume E2E exists but don't detail Signal Protocol)
• Message forwarding, pinning, or replies threading (V2 features)

Core complexity:

The hardest problems here are:

1. Real-time bidirectional communication: HTTP is request-response; chat is push-based. We need persistent connections or server-push mechanisms.
2. Message ordering and delivery guarantees: If User A sends messages rapidly, they must appear in order on User B's device even if messages take different network paths.
3. Presence at scale: Tracking online status for 2B users in real time is a massive write workload.

WHY: Real-time delivery is what distinguishes a chat system from async messaging (email). The transport protocol choice (WebSocket vs long-polling vs SSE) fundamentally shapes the architecture. Presence is a distinct subsystem with its own scaling challenges.

Non-functional requirements:

• Message delivery latency: P99 < 500ms for online recipients (same region)
• Consistency: Messages must arrive in send order per conversation (at-least-once delivery, deduplicated on client)
• Durability: Messages must not be lost once acknowledged to the sender
• Availability: 99.99% — chat unavailability is immediately noticeable
• Scale: 2B registered users, 500M DAU

Back-of-envelope math:

Assumptions:

• 500M DAU
• Average 40 messages sent per user per day
• Average message size: 100 bytes (text)
• Average group chat: 10 members
• 80% of messages are 1-1; 20% are group

Message write QPS: $500M \times 40 = 20B \text{ messages/day}$ $20B \div 86{,}400 \approx 231{,}500 \text{ messages/s average}$ $\text{Peak} \approx 231{,}500 \times 3 = 695{,}000 \text{ messages/s}$

Delivery events (fan-out for group messages):

• 1-1: $0.8 \times 695K = 556K$ deliveries/s
• Group (avg 10 members): $0.2 \times 695K \times 10 = 1.39M$ delivery events/s
• Total delivery events: ~2M/s

Storage: $20B \text{ msg/day} \times 100\text{ bytes} = 2\text{ TB/day}$ $2\text{ TB} \times 365 = 730\text{ TB/year}$

WHY: 2M delivery events/s is a very high write throughput — this rules out a traditional RDBMS for message storage. We need a write-optimized store like Cassandra or HBase. 700 TB/year also mandates planning for tiered storage.

WebSocket connections:

• 100M concurrent users (peak, ~20% of DAU online simultaneously)
• Each WebSocket connection requires a file descriptor on the Chat Server
• Typical limit: 10K–100K concurrent WebSocket connections per server
• Servers needed: $100M \div 65{,}000 \approx 1{,}540$ chat servers

WHY: This is why chat servers can't be your regular stateless web servers — they hold long-lived connections, requiring careful connection management and a separate connection tier.

Interviewer: "Why WebSockets over HTTP long polling or Server-Sent Events?"

Candidate: "Three options:

• HTTP Long polling: Client holds a request open until the server has data. Wastes a thread/connection per client on the server; high latency (poll interval). Works everywhere but inefficient.
• Server-Sent Events (SSE): Server-to-client streaming only — can't send messages to the server over SSE without a separate HTTP connection. Breaks the bidirectional nature of chat.
• WebSocket: Full-duplex, persistent connection. Single TCP connection for both send and receive. Supported by all modern browsers and mobile clients.

WHY: Chat is inherently bidirectional — both parties send and receive at any time. WebSocket is the only option that provides full-duplex over a single connection. The downside is statefulness on servers (connections must be maintained), but that's solvable with a connection registry."

Phase 2: High-Level Architecture

Interviewer: "What does your API look like?"

Candidate: "Two API surfaces:

REST API (for non-real-time operations):

POST /api/v1/conversations
  Request:  { "participant_ids": ["uid2", "uid3"] }
  Response: { "conversation_id": "conv123", "type": "group", ... }

GET /api/v1/conversations/{conv_id}/messages?before={msg_id}&limit=50
  Response: { "messages": [...], "has_more": true, "next_cursor": "..." }

POST /api/v1/conversations/{conv_id}/messages
  (Fallback for offline send; normally via WebSocket)

WebSocket protocol (binary, lightweight):

// Client → Server: Send message
{
  "type": "message",
  "client_msg_id": "client-uuid",   // Idempotency key
  "conversation_id": "conv123",
  "content": "Hello!",
  "timestamp": 1705320000000
}

// Server → Client: New message delivery
{
  "type": "message",
  "message_id": "server-msg-id",    // Server-assigned Snowflake ID
  "conversation_id": "conv123",
  "sender_id": "uid1",
  "content": "Hello!",
  "server_timestamp": 1705320001000
}

// Server → Client: Delivery acknowledgment
{
  "type": "ack",
  "client_msg_id": "client-uuid",
  "server_msg_id": "server-msg-id",
  "status": "delivered"  // "sent" | "delivered" | "read"
}

// Client → Server: Read receipt
{
  "type": "read_receipt",
  "conversation_id": "conv123",
  "last_read_msg_id": "server-msg-id"
}

Data model:

Copy
-- Messages (Cassandra — write-heavy, time-ordered)
CREATE TABLE messages (
    conversation_id UUID,
    message_id      BIGINT,        -- Snowflake ID (monotonic, sortable)
    sender_id       UUID,
    content         TEXT,
    content_type    TEXT,          -- 'text', 'image_url', 'video_url'
    created_at      TIMESTAMP,
    PRIMARY KEY ((conversation_id), message_id)
) WITH CLUSTERING ORDER BY (message_id DESC);

-- Conversations (PostgreSQL)
CREATE TABLE conversations (
    conversation_id UUID PRIMARY KEY,
    type            VARCHAR(10),   -- 'direct', 'group'
    created_at      TIMESTAMPTZ,
    last_message_id BIGINT
);

-- Conversation members (PostgreSQL)
CREATE TABLE conversation_members (
    conversation_id UUID NOT NULL,
    user_id         UUID NOT NULL,
    joined_at       TIMESTAMPTZ,
    last_read_msg_id BIGINT DEFAULT 0,
    PRIMARY KEY (conversation_id, user_id)
);
CREATE INDEX idx_user_conversations ON conversation_members(user_id);

-- User presence (Redis — volatile, frequently updated)
-- Key: presence:{user_id}
-- Value: { "status": "online", "last_seen": <timestamp> }
-- TTL: 60 seconds (refreshed every 30s by heartbeat; expired = offline)

WHY: Cassandra for messages — partition key conversation_id keeps all messages of a conversation on the same (set of) nodes, enabling efficient range reads. Snowflake IDs as clustering key provide monotonic ordering within a conversation. PostgreSQL for conversation metadata — low write rate, ACID needed for membership changes.

Core architecture diagram:"

-+ResetFullscreen

Write path (User A sends message to User B):

1. Client A sends {type: message, ...} over WebSocket to Chat Server 1
2. Chat Server 1 persists message to Cassandra (durable write)
3. Sends ACK back to Client A over WebSocket ({type: ack, status: "sent"})
4. Publishes message event to Kafka messages topic
5. Message Router consumes from Kafka, looks up User B's server in connection registry
6. If B is on Chat Server 2: pushes message to Chat Server 2, which delivers to Client B over WebSocket
7. Chat Server 2 sends delivery ACK back to Chat Server 1 (via Kafka acks topic)
8. Chat Server 1 pushes delivery status update to Client A ({status: "delivered"})

Read path (User B opens app after being offline):

1. Client B connects WebSocket, sends {type: sync, last_msg_id: "xyz"}
2. Chat Server queries Cassandra: SELECT * FROM messages WHERE conversation_id = ? AND message_id > ?
3. Returns missed messages in bulk; Client B processes them in order"

Interviewer: "Why sticky load balancing by user_id? Can't you use round-robin?"

Candidate: "Round-robin works but makes the connection registry a critical hot path — every message delivery requires a registry lookup. With sticky load balancing (consistent hashing by user_id), the same user always connects to the same server (absent server failure), so message routing can sometimes skip the registry lookup for co-located users. More importantly, sticky ensures that if User A sends 5 messages rapidly, they all go through the same Chat Server and can be ordered correctly before publishing to Kafka.

The downside is uneven load if some users are more active. We mitigate with consistent hashing (smooth rebalancing when servers are added/removed)."

Phase 3: Deep Dive & Evolution

Interviewer: "What breaks first when traffic spikes to 10x? You're at 2M delivery events/s — what's your bottleneck?"

Candidate: "Let me triage:

1. Chat Servers: At 100M concurrent connections across 1,540 servers = 65K connections/server. At 10x: 1M concurrent = 1M ÷ 65K = 15,400 servers. That's a lot, but linearly scalable.

2. Connection Registry (Redis): Every message delivery does a GET conn_server:{user_id}. At 2M delivery events/s = 2M Redis reads/s. A single Redis node handles ~500K ops/s. Need Redis Cluster with at least 4 shards.

3. Cassandra writes: 231K messages/s average. Cassandra handles ~50K–100K writes/s per node; need 3–5 nodes minimum, but Cassandra scales horizontally.

4. Kafka fan-out for group messages: Group messages are partitioned by conversation_id. A popular group with 500 members generates 500 delivery events per message. If that group is in one Kafka partition, it bottlenecks. Solution: partition group fan-out by recipient user_id hash, not conversation_id.

Message ordering guarantees:

Within a conversation, messages must arrive in send order. Challenge: Client A sends M1 and M2 rapidly; they may arrive at different Kafka partitions and be processed by different Message Routers.

Solution: Sequence numbers per conversation. The Chat Server assigns a monotonically increasing sequence number per conversation when persisting to Cassandra (using Cassandra's lightweight transactions or a Redis counter per conversation). The client re-sorts messages by sequence number, not arrival time.

# Redis counter per conversation
INCR conv_seq:{conversation_id}  → returns seq_num

This adds one Redis round trip per message but guarantees sequence numbers are globally ordered within a conversation.

WHY: Without sequence numbers, messages can appear out of order on the recipient's screen — a critical UX bug for chat. Snowflake IDs don't guarantee ordering across multiple Chat Server instances because of clock skew.

Offline message delivery:

When User B is offline, messages are stored in Cassandra with status pending. When User B reconnects:

1. Chat Server registers the new WebSocket connection in ConnRegistry
2. Queries for pending messages: SELECT * FROM messages WHERE conversation_id IN (...) AND message_id > last_seen_msg_id
3. Delivers in bulk, ordered by message_id

We also send a mobile push notification (via the Notification System) to prompt User B to open the app.

Presence subsystem at scale:

Tracking 500M DAU presence with 30-second heartbeats:

• Heartbeat rate: $500M \div 30 = 16.7M \text{ heartbeats/s}$

That's 16.7M Redis writes/s — far too high for a single cluster. We need a tiered presence approach:

1. Local presence: Chat Servers maintain a local hash map of connected users ({user_id: last_heartbeat_time}). No Redis write needed.
2. Presence Service: Chat Servers periodically report their connected user counts to the Presence Service in batches (not per-heartbeat).
3. User query: "Is User X online?" → Check which Chat Server X is connected to (from ConnRegistry) → Ask that server directly.

This reduces Redis presence writes from 16.7M/s to a manageable batch update rate.

Here's the evolved architecture:"

-+ResetFullscreen

Changes from core design:

1. Sequence numbers: INCR conv_seq:{conv_id} in ConnRegistry for ordering guarantees
2. Group Fan-out Worker: Separate worker expands group membership → per-user delivery events
3. Tiered presence: Chat Servers maintain local presence maps; batch updates to Presence Service
4. Push notification gateway integration for offline users
5. Acks Kafka topic: Delivery confirmations flow back to sender's Chat Server asynchronously

Phase 4: Robustness & Operations

Interviewer: "What happens if a Chat Server crashes while holding 65K active WebSocket connections?"

Candidate: "All 65K users lose their connections and immediately reconnect (client auto-reconnect with exponential backoff). The events:

1. LB detects server failure via health checks (usually within 5–30 seconds)
2. Consistent hashing redistributes the failed server's user_id range to neighboring servers
3. ConnRegistry entries for the failed server's users are stale — we clean them with a TTL or the Presence Service detects the server went down and bulk-deletes its entries
4. Users reconnect; their WebSocket handshake registers them on a new server; they sync missed messages from Cassandra

Impact: up to 30 seconds where messages to those users are undeliverable (stored in Cassandra). Messages are not lost — they're queued and delivered on reconnect.

WHY: Stateful connection servers are inherently harder to fail over than stateless servers. The design accepts brief unavailability during failover rather than trying to migrate live WebSocket connections (which is extremely complex).

Interviewer: "What about message ordering when Client A sends 3 messages rapidly while the Chat Server is slow?"

Candidate: "Client A assigns client_msg_id (client-side UUID) and a client_sequence (incrementing counter). Even if messages arrive at the server out of order (unlikely on a single connection, but possible with retries), the server uses client_sequence to detect gaps.

If a gap is detected: the server asks the client to resend the missing message. This is the same protocol WebSocket chat apps use — ordered delivery is enforced per sender, per connection.

Interviewer: "How do you handle split-brain in the connection registry? Two Chat Servers might think they own the same user's connection."

Candidate: "This happens during failover: old server hasn't fully died (zombie state), and the user has reconnected to a new server. The registry might briefly show two entries.

Solution: ConnRegistry stores {server_id, session_id, timestamp} — not just server_id. When the new server registers the user, it writes a newer timestamp. The Message Router uses the entry with the highest timestamp. The old server's session is invalidated when it tries to send and gets a 'session expired' error.

Key SLIs:

• Message delivery P99 < 500ms (online recipient)
• Message delivery P99 < 30s (offline → online transition)
• Connection establishment P99 < 200ms
• WebSocket connection drop rate < 0.1%/hour
• Message loss rate = 0% (durably stored before ACK sent)

Executive Summary:

Three key trade-offs:

1. Stateful Chat Servers: Holding WebSocket connections makes servers stateful and harder to scale. The alternative (HTTP long-polling) is simpler to operate but worse for users. The operational complexity is worth the latency improvement.
2. Cassandra for messages: Excellent write throughput and time-ordered reads within a conversation, but no ad-hoc querying. Searching message content requires a separate Elasticsearch index.
3. Eventual consistency on delivery status: 'Delivered' receipts are eventually consistent — if the ack message is dropped, the sender won't see 'delivered' until the next message. This is acceptable; the WhatsApp model explicitly documents that receipts are best-effort.

V2 improvements:

• End-to-end encryption (Signal Protocol — message content opaque to servers)
• Message search (Elasticsearch with E2E encryption challenges)
• Disappearing messages (TTL on Cassandra rows)
• Large group support (>500 members) using the fan-out-on-read pattern"