Design a Real-Time Chat Application (WhatsApp / Slack)

WebSocket vs Long Polling vs SSE: Why WebSocket?

Why WebSocket is ideal for chat:

1. Bi-directional: Client sends messages AND receives messages on the same connection
2. Low latency: No HTTP overhead per message (WebSocket frames are tiny: 2-14 bytes header vs 200+ bytes for HTTP headers)
3. Efficient: 500M users × 1 WebSocket each = 500M connections. With HTTP polling every 1s, that's 500M HTTP requests/sec (30× the load)

When Long Polling is acceptable: As a WebSocket fallback behind corporate proxies that block WebSocket upgrades. Implement auto-detection: try WebSocket → if fails, fall back to Long Polling.

Why Cassandra for Messages (Not MySQL/PostgreSQL/MongoDB)?

Message access patterns:
  1. Write a message (append-only, VERY frequent)
  2. Read recent messages for a conversation (time-range query, VERY frequent)
  3. Search messages (not on Cassandra — use Elasticsearch)
  4. Never: JOINs, transactions, or complex queries on messages

Cassandra ✓:
  - Partition key = conversation_id → all messages for a conversation on same node
  - Clustering key = message_id (time-sorted) → efficient range reads
  - LSM-tree storage → optimized for high write throughput (50K msgs/sec easily)
  - TTL support → auto-expire messages after retention period
  - Linear horizontal scaling → add nodes as message volume grows
  - Multi-DC replication built-in → low latency reads globally

MySQL/PostgreSQL ✗:
  - Single-writer primary → write bottleneck at scale
  - Sharding required (by conversation_id) — Cassandra gives this natively
  - No built-in TTL → need cron jobs for data cleanup

MongoDB:
  - Could work (document model, sharding, TTL indexes)
  - But: Cassandra's time-series data model (partition + clustering key) is a
    more natural fit for "messages ordered by time within a conversation"
  - MongoDB's WiredTiger engine handles writes well but Cassandra's LSM-tree
    is better for append-heavy workloads

E2EE: Why Signal Protocol (Not PGP/TLS)?

Option 1: TLS only (transport encryption)
  ✓ Simple — HTTPS encrypts in transit
  ✗ Server sees plaintext → compromised server exposes all messages
  ✗ Government subpoena → server can hand over messages

Option 2: PGP (Pretty Good Privacy)
  ✓ End-to-end encrypted
  ✗ No forward secrecy (one key compromise exposes ALL past messages)
  ✗ Manual key management (user must manage public/private keys)
  ✗ No key ratcheting → same key for all messages in a session

Option 3: Signal Protocol ⭐ (Double Ratchet)
  ✓ End-to-end encrypted
  ✓ Forward secrecy (new ephemeral key per message → past messages safe even if key leaked)
  ✓ Post-compromise security (future messages safe after device recovers from compromise)
  ✓ Transparent key exchange (Diffie-Hellman, no manual key sharing)
  ✗ Complex implementation
  ✗ Server cannot index/search message content (search must be client-side)

Why Signal Protocol wins:
  - Forward secrecy is critical: leaked key only compromises ONE message, not all history
  - Double Ratchet derives a new key per message → each message has a unique encryption key
  - Used by: WhatsApp, Signal, Facebook Messenger (secret conversations), Skype

Message Ordering: The Distributed Systems Challenge

Problem: User A sends "Hello" then "How are you?" from two different devices.
  Due to network delays, "How are you?" might arrive at the server BEFORE "Hello"

Solutions:
  1. Client-generated timestamp → but clocks are not synchronized across devices

  2. Snowflake ID ⭐ (recommended):
     - Server assigns a monotonically increasing ID on receipt
     - Within a single server: guaranteed ordered
     - Across servers: approximately ordered (Snowflake embeds timestamp)
     - Per-conversation ordering: route all messages for a conversation to
       the same Kafka partition (partition key = conversation_id) → strict FIFO

  3. Lamport Clock / Vector Clock:
     - Tracks causal ordering (A happened before B)
     - Overkill for chat — Snowflake + Kafka partition ordering is sufficient

  4. Client sequence number:
     - Each client maintains a per-conversation sequence counter
     - Server detects gaps: "Got seq 5, missing seq 4" → requests retransmission
     - Useful for offline-first sync

Connection Management: The WebSocket Server Scaling Problem

Problem: 500M WebSocket connections. Each connection is stateful (tied to one server).
  If a server dies, all its connections are lost.

Solution 1: Sticky Load Balancing
  - L4 LB hashes client IP → always routes to same WS server
  - ✓ Simple
  - ✗ Uneven distribution; server failure drops all its clients

Solution 2: Connection Registry (Redis) ⭐
  - Redis stores: user_id → {ws_server_id, device_id}
  - When message needs to be delivered:
    1. Lookup recipient's WS server from Redis
    2. Send message to that server via internal RPC
    3. Server pushes to client over existing WebSocket
  - ✓ Decoupled: any server can route to any other
  - ✓ Server failure: client reconnects to any server, Redis updated
  - ✗ Extra hop (Redis lookup + internal RPC)

Solution 3: Pub/Sub Fan-Out
  - Each WS server subscribes to user-specific Redis Pub/Sub channels
  - Message for user X → PUBLISH to channel "user:X" → reaches the right server
  - ✓ Simpler than direct RPC routing
  - ✗ Redis Pub/Sub doesn't persist → if server is down, message lost from this channel
  - → Combine with message store (Cassandra) for durability

Production approach:
  Redis for connection registry + internal gRPC for message delivery +
  Cassandra for persistence + Kafka for async processing

Group Chat: Small Groups vs Large Channels

Small Groups (< 256 members, WhatsApp-style):
  - Store members list in a Redis SET
  - Message delivery: iterate members, send to each connected user
  - Fan-out is small (< 256) → done synchronously
  - Every member gets every message (no threading)

Large Channels (1000+ members, Slack/Discord-style):
  - Message delivery is fan-out-on-read (too expensive to push to 100K members)
  - Channel messages stored in Cassandra
  - Client polls for new messages or subscribes to channel WebSocket room
  - Unread count tracked per user per channel (Redis counter)
  - Threading: messages have parent_id → tree structure (like Reddit comments)

  Why fan-out-on-read for large channels:
    10K members × 100 messages/hour = 1M deliveries/hour per channel
    With 1000 active channels = 1B deliveries/hour → infeasible with fan-out-on-write
    Instead: each member fetches new messages when they open the channel