Design Facebook Messenger

Source: https://www.hack2hire.com/question-bank/questions/system-design/69d2bf7307421ca06eb8e38c
Company: Anthropic, Meta, Microsoft, Uber, Google
Difficulty: Medium

Problem statement

One-to-one and group messaging for a billion users: real-time delivery, offline sync, read receipts and message history on every device.

Requirements

We are building a Messenger-style chat service: one-to-one and group conversations for about a billion users, with real-time delivery to every logged-in device, offline catch-up, read receipts and full history on any device. Clarify scope first: text and images (no calls or end-to-end encryption here), groups capped at a few hundred members, history kept indefinitely.

Functional requirements

• Send a text or image message to a 1:1 or group conversation; online recipients see it in under a second.
• A user has several devices (phone, laptop, web); each receives every message and can reconnect after hours offline and catch up exactly.
• Messages within a conversation appear in the same order on every device; retries never create duplicates.
• Read receipts: show how far each member has read; unread counts in the inbox.
• Inbox: list conversations by latest activity, with last message preview.
• Push notification to offline users, without one per message in busy groups.
• Group membership changes (add, remove, leave) control what history each member can see.

Non-functional requirements

• Durable once acknowledged: a sent message the client saw ACKed is never lost.
• Send ACK p99 under 300 ms; end-to-end delivery to online devices p99 under 500 ms in-region.
• 99.99% availability for send and history; presence and typing indicators can degrade.
• Strict order per conversation; no global order needed.
• Spam and abuse limits on the send path.

Back-of-the-envelope estimation

• 1B DAU, 100M concurrent connections at peak (1.5 devices per online user).
• 100B messages/day ≈ 1.2M sends/s average, ~3M/s peak.
• Average fan-out ~3 devices per 1:1 send, ~40 for groups → ~10M device deliveries/s at peak.
• Message row ~300 B with indexes → 100B × 300 B = 30 TB/day, ~11 PB/year before replication. Cold history moves to cheaper tiers.
• Images: 5% of messages, ~200 KB each → 1 PB/day in object storage, served through a CDN.
• Gateways at ~500K connections each → ~200 gateway hosts at peak, plus headroom per region.

API design

Clients hold one WebSocket (or MQTT over TLS on mobile) to a gateway; REST is used for history and uploads. All calls carry an OAuth access token; every conversation call checks membership.

POST /v1/conversations                 {type: "group", member_ids: [...], title}
  → {conversation_id, created_at}
POST /v1/conversations/{cid}/members   {add: [...], remove: [...]}  → {membership_epoch}

# over the socket (or POST /v1/conversations/{cid}/messages as fallback)
send   {client_msg_id: uuid, conversation_id, body | {media_id}, sent_at}
  → ack {client_msg_id, message_id, seq, server_ts}   # after durable commit
  → nack {client_msg_id, code: "rate_limited" | "not_member" | "too_large"}

GET  /v1/conversations/{cid}/messages?after_seq=1820&limit=100
  → {messages: [{seq, message_id, sender_id, body, media, server_ts}], has_more}
GET  /v1/sync?cursor=<opaque>          → {conversations: [{cid, last_seq, read_seq}], next_cursor}
GET  /v1/inbox?before=<ts>&limit=50    → [{cid, last_seq, preview, unread_count}]

PUT  /v1/conversations/{cid}/read      {read_seq: 1830}   # monotonic; lower values ignored

POST /v1/media/uploads                 {content_type, size, sha256}
  → {media_id, upload_url (signed, 15 min)}
POST /v1/media/{media_id}/complete     → {status: "ready", variants}

# server → client stream frames
{type: "msg", cid, seq, ...}  {type: "receipt", cid, user_id, read_seq}  {type: "typing", cid, user_id}

client_msg_id makes send idempotent: a resend after a dropped ACK returns the original seq. The ACK means "committed", not "delivered".

Data model

Messages are append-only and read by range, which suits a wide-column store with cheap writes and tunable replication. Sequence assignment needs a linearizable increment, so it lives in a consistent store keyed by conversation. Membership is relational and small. Redis only answers "where is this device right now"; losing it costs latency, never messages.

High-level design

flowchart LR
  C[Clients] --> LB[Load balancer]
  LB --> GW[Chat gateways]
  GW --> MS[Message service]
  MS --> SEQ[(Seq and dedupe store)]
  MS --> MDB[(Message store)]
  MS --> K[Kafka]
  K --> FO[Fan-out workers]
  FO --> R[(Presence Redis)]
  FO --> GW
  K --> PN[Push notifier]
  K --> IX[Inbox updater]
  IX --> IDB[(Inbox store)]
  C --> API[History and sync API]
  API --> MDB
  C --> MU[Media service]
  MU --> S3[(Object store and CDN)]
  GW --> R

1. Session registration. A device connects to a gateway, authenticates, and writes sess:{user} device → gateway into Redis with a 90 s TTL, refreshed every 30 s by heartbeat.
2. Send. The gateway forwards to the message service, routed by cid to the conversation's home shard. It checks membership and rate limits, checks dedupe, increments next_seq, writes the message row (quorum), records the dedupe entry, and returns the ACK with seq. Only then does it publish to Kafka, partitioned by cid.
3. Fan-out. Workers consume the event, load the member list (cached), look up each member's devices in Redis, and push the frame to the right gateways over an internal RPC. Members with no live session go to the push notifier.
4. Delivery check. The client tracks the last contiguous seq per conversation. A gap (got 1832 after 1830) triggers a history fetch for the missing range rather than waiting.
5. Reconnect. The client calls /v1/sync with its cursor and gets each conversation's last_seq; for any conversation behind, it pages messages?after_seq=. The stream is a speed-up; the store is the truth.
6. Image. The client uploads straight to object storage with the signed URL, calls complete, then sends a normal message carrying media_id. Message bytes never pass through gateways.

Kafka sits after commit so that a published event always describes a stored message. If fan-out lags or Kafka is down, sends still succeed and clients recover through sync. Each conversation has a home region where its sequence is assigned; users mostly talk within a region, so a cross-region send costs one extra hop (~70–150 ms), not a global consensus round.

Deep dives

Per-conversation ordering, idempotency, and catch-up. Ordering comes from one counter per conversation, not from clocks. The sequence store shard that owns cid runs seq = next_seq++ and the dedupe insert in one transaction; a hot group of 300 members sending 50 msg/s is trivial for one row. Seqs are dense, so gaps are detectable: if the message write fails after the seq is taken, the service writes a tombstone at that seq so clients don't wait forever. The client keeps (cid → last_contiguous_seq) locally; catch-up is a range scan on the clustering key, ~1 ms per 100 rows. Retries with the same client_msg_id hit the dedupe row and return the original seq, so "at least once" from client plus dedupe gives "exactly once" in the log.

Presence and device routing in Redis. 100M sessions × ~100 B = ~10 GB, sharded by user across a Redis cluster, with ~10M lookups/s from fan-out (batched with pipelining, one round trip per worker batch). It fits because the data is small, short-lived and rebuildable: if a shard dies, entries reappear within one heartbeat, and in the meantime messages to those users go to push and sync. Stale entries (gateway crashed) are handled by the gateway rejecting frames for unknown sessions and by TTL expiry. Never treat a Redis miss as "message delivered"; it only means "use push".

Read receipts as progress markers. A receipt is read_seq per (member, conversation), monotonic: UPDATE members SET read_seq = max(read_seq, :v). It implicitly marks everything below as read, so one write replaces hundreds of per-message receipts. Clients debounce to one update per 2 s per conversation. Fan-out of receipts goes only to online members, and in groups over ~50 members the UI shows "seen by N" fetched on demand instead of pushing every update. Per-device truth isn't tracked: reading on the laptop clears the phone's badge via the same receipt event. Unread count = last_seq − read_seq, computed, not stored.

Media upload and orphan cleanup. Upload creates a pending media row and a 15-minute signed PUT URL. complete verifies size and sha256, runs a malware and content scan, generates thumbnails, and marks ready. Sending a message flips it to attached. A daily sweep deletes pending or ready rows older than 24 h with no message, plus their objects. Downloads use short-lived signed CDN URLs (1 h) re-issued by the history API after a membership check, so a removed member's old links stop working. Identical sha256 per owner is deduplicated.

Group membership and history visibility. Each member row records joined_seq and left_seq. History reads clamp to [joined_seq, left_seq), so a new member sees only messages after they joined (or the whole history if the group setting allows). A membership change is itself a system message with a seq, so every device sees it in order with the chat. Fan-out uses the member list as of the message's seq, cached with membership_epoch so a removal takes effect on the next message.

Trade-offs

• Per-conversation home shards give simple strict order but tie each conversation to one region; a regional failover promotes a replica and may lose the last ~1 s of un-replicated sends unless replication is synchronous across zones (we do sync within region, async across).
• ACK on commit, fan-out after, means senders wait ~20–50 ms more than ACK-on-receive, but nothing acknowledged is lost and Kafka outages only add delivery lag.
• Redis for presence is fast and cheap but can be briefly wrong; correctness rests on sync, so a wrong answer costs a push notification or a few seconds, not a message.
• Range-based read receipts lose "who read exactly which message" in large groups; that's accepted for 100× fewer writes.
• Collapsing push notifications (one per conversation per 30 s while unread, muted groups never) loses some immediacy for a far better user experience and lower APNs/FCM cost.
• Gateway draining on deploy (stop new connections, send "reconnect elsewhere" with jitter over 5 minutes) slows rollouts but avoids reconnect storms of 500K clients at once.
• Spam control on send (per-user token buckets, new-account limits, first-contact message requests, URL reputation) adds a few ms to the hot path and occasionally slows legitimate bursts.

Interviewer expectations

Mid-level (L4)

• Persistent connections through gateways, a message store, and a clear send → store → deliver flow.
• Offline users get push and fetch history on reconnect.
• Basic estimates for connections and message volume.

Senior (L5)

• Per-conversation sequence numbers for order, client_msg_id for idempotency, ACK after durable write.
• Cursor-based catch-up as the source of truth, with the real-time stream as an optimization.
• Presence/session routing in a cache that is explicitly non-authoritative; read receipts as monotonic markers.
• Media uploaded out of band with signed URLs.

Staff (L6+)

• Region ownership of conversations, failover and its data-loss window, gateway draining.
• Fan-out cost for large groups, notification collapsing, receipt aggregation.
• Membership-aware history visibility, URL expiry, orphan cleanup, and abuse containment designed into the send path.
• Explains what fails when each component (Redis, Kafka, a gateway, a region) goes down and why no acknowledged message is lost.