Design a Chat System

Requirements

Functional

• One-to-one chat between users.
• Group chat (up to ~500 members; larger "channels" are a stretch goal).
• Messages are delivered in real time when the recipient is online and stored for later when offline.
• Delivery receipts: sent, delivered, read.
• Online/offline presence and "last seen".
• Chat history synced across a user's devices (phone, desktop, web).
• Push notifications for offline users. Media attachments via upload links.

Non-functional

• Low latency: end-to-end delivery under ~200 ms for online users in the same region.
• No message loss: once the server acknowledges a message, it must be durable.
• Ordering: messages within a conversation appear in the same order for every participant.
• High availability, with graceful handling of flaky mobile networks and reconnect storms.
• Optional: end-to-end encryption (changes what the server can see, not the delivery design).

Capacity Estimates

Assume 500 M daily active users, each sending 40 messages per day, average message 200 bytes including metadata, and an average of 3 recipients per message (mostly 1:1 with some groups).

The numbers point to two separate problems: a huge number of mostly idle long-lived connections, and a write-heavy, append-only message store that is read mostly by recency.

API Design

Connection setup and history use HTTPS; live traffic uses a WebSocket with small JSON (or protobuf) frames.

GET  /api/v1/connect              -> upgrade to WebSocket (auth token in header)

Client -> server frames
  { "type": "send", "clientMsgId": "c-7f3a", "convId": "g_42", "body": "hi", "attachments": [] }
  { "type": "ack",  "convId": "g_42", "upToSeq": 1088 }          // delivered
  { "type": "read", "convId": "g_42", "upToSeq": 1088 }          // read receipt
  { "type": "ping" }

Server -> client frames
  { "type": "sent",    "clientMsgId": "c-7f3a", "convId": "g_42", "seq": 1089, "ts": 1793350000 }
  { "type": "message", "convId": "g_42", "seq": 1089, "from": "u_9", "body": "hi" }
  { "type": "presence","userId": "u_9", "status": "online" }

REST
  GET  /api/v1/conversations/{convId}/messages?beforeSeq=1089&limit=50
  GET  /api/v1/sync?since=<cursor>        // catch up after reconnect
  POST /api/v1/conversations              // create group { "members": [...] }
  POST /api/v1/media/upload-url           // pre-signed object-store URL

clientMsgId makes retries idempotent; seq is the server-assigned position in the conversation.

Data Model

-- CQL-style: one partition per conversation per time bucket keeps partitions bounded
CREATE TABLE messages (
  conv_id    bigint,
  bucket     int,          -- e.g. days since epoch, or a fixed count of messages
  seq        bigint,
  sender_id  bigint,
  body       text,
  created_at timestamp,
  PRIMARY KEY ((conv_id, bucket), seq)
) WITH CLUSTERING ORDER BY (seq DESC);

A wide-column store suits this workload: very high write rates, append-only rows, and reads that are almost always "latest N messages of one conversation".

High-Level Design

flowchart LR
  A[Client A] <--> GW1[Chat Gateway 1]
  B[Client B] <--> GW2[Chat Gateway 2]
  GW1 --> CS[Chat Service]
  CS --> SEQ[Sequence Allocator]
  CS --> DB[(Message Store)]
  CS --> SR[(Session Registry)]
  CS --> BUS[[Message Bus]]
  BUS --> GW2
  BUS --> PN[Push Notification Service]
  GW1 --> PR[Presence Service]
  PR --> PC[(Presence Cache)]
  A --> API[REST API for history and media]
  API --> DB
  API --> OS[(Object Store and CDN)]

Send flow:

1. Client A sends a frame over its WebSocket to Gateway 1.
2. The Chat Service assigns the next seq for the conversation, writes the message durably, and replies sent to A (one grey tick).
3. It looks up each recipient's devices in the session registry. Online devices get the message via the bus to their gateway; offline users get a push notification.
4. When B's device receives it, B sends an ack; the server records the delivered position and notifies A (two ticks). A read frame does the same for read receipts.

Deep Dives

Connection layer: WebSockets at scale

• Why WebSockets: full-duplex, low overhead per message, server can push instantly. Long polling works as a fallback but costs a request per message batch; Server-Sent Events are one-way only.
• Stateful gateways: each gateway holds ~100 K mostly idle sockets using an event-driven runtime (epoll, Netty, Erlang/Elixir, Go). Gateways do no business logic; they authenticate, frame, and forward.
• Routing: on connect, the gateway writes user_id/device → gateway_id into the session registry. Senders look this up to route messages; entries expire if heartbeats stop.
• Load balancing: an L4 balancer spreads new connections; it cannot rebalance existing ones, so gateways should drain gradually on deploys (tell clients to reconnect with jittered backoff).
• Heartbeats every ~30 s detect dead connections behind mobile NATs that silently drop idle flows.

Message ordering and delivery guarantees

• Per-conversation sequence numbers: the Chat Service assigns a strictly increasing seq per conversation (a Redis INCR on conv:{id}, or a single owner shard per conversation). Clients sort by seq, never by device clock.
• Ordering is only guaranteed within a conversation. Global ordering is unnecessary and would be a bottleneck.
• At-least-once + idempotency: clients retry send until they get sent; the server deduplicates by (sender, clientMsgId). Receivers deduplicate by (convId, seq). Together this gives effectively-exactly-once display.
• Gap detection: if a client holds seq 1085 and receives 1088, it fetches 1086-1087 through the history API.
• Sync after reconnect: the client sends its last known seq per conversation (or a single sync cursor) and the server returns everything newer, so missed pushes are never lost.

Group chat fan-out

• Small groups (≤ a few hundred): write the message once to the conversation partition, then fan out a delivery event to each online member's gateway. Storage stays O(1) per message; only the notification is O(members).
• Per-user inbox counters (unread count, last seq) are updated asynchronously per member.
• Large channels (thousands+): do not push every message to every member. Push to members currently viewing the channel; others get a lightweight "channel has unread messages" flag and pull history when they open it. This mirrors the push/pull hybrid used in news feeds.
• Membership changes are themselves messages in the sequence, so every member sees joins and leaves in the same order as the chat content.

Presence

• A gateway marks a user online on connect and refreshes a key with a TTL on each heartbeat; when heartbeats stop, the key expires and the user becomes offline with last_seen set.
• Fan-out cost is the problem: notifying every contact on each change is expensive for users with many contacts. Mitigations: only publish presence to contacts who currently have the chat open (subscribe on view), debounce flapping connections for a few seconds, and fetch presence lazily for large groups.
• Presence is best-effort and eventually consistent; it should never block messaging.

Storage and multi-device history

• Partition messages by conversation and a time or size bucket so no partition grows without bound in a long-lived chat.
• Recent messages are read most; keep the latest pages per active conversation in cache and serve older history directly from the store.
• Each device keeps its own cursor, so a laptop that was offline for a week can sync independently of the phone.
• Media goes to object storage via pre-signed URLs; the message only carries the media key, size, and a thumbnail.
• Retention and deletion ("delete for everyone") are tombstone messages with their own seq, so all devices apply them consistently.

Scaling & Reliability

• Horizontal gateways: add servers to add connection capacity; keep them stateless apart from open sockets.
• Message bus (Kafka, or a pub/sub layer keyed by gateway id) decouples chat services from gateways and buffers bursts.
• Replicated store with quorum writes (e.g. RF=3, QUORUM) so an acknowledged message survives a node loss.
• Hot conversations: a viral group concentrates sequence allocation and writes on one partition; time buckets and a dedicated sequencer per hot conversation keep it manageable.
• Multi-region: home each conversation in one region for ordering; route sends there and replicate to other regions asynchronously for reads.
• Offline users are handled by APNs/FCM push notifications, rate-limited and collapsed per conversation.
• Monitoring: track delivery latency percentiles, undelivered backlog, reconnect rate and sequence gaps.

Trade-offs

Interview Tips

• Separate the connection tier (stateful gateways) from the chat logic (stateless services); interviewers look for this split.
• Explain how a server finds the gateway holding the recipient's socket (session registry).
• Walk through the ack flow and show how client message IDs plus sequence numbers prevent loss and duplicates.
• State that ordering is per conversation and why global ordering is unnecessary.
• Treat presence as best-effort and discuss its fan-out cost.
• Cover reconnect storms, offline sync, and multi-device cursors; these separate strong answers from average ones.

References

• System Design Primer: Asynchronism and message queues
• MDN: The WebSocket API
• Discord Engineering: How Discord stores trillions of messages
• Slack Engineering: Real-time messaging
• Karan Pratap Singh: System Design (WhatsApp case study)