Design Facebook Messenger: real-time chat for a billion users

Design Facebook Messenger: one-to-one and group messaging for about a billion users, with real-time delivery, offline sync, delivery and read receipts, and full message history on every device a user owns.

Requirements

• Functional: send text and media in 1:1 and group chats; real-time delivery to online recipients; messages queued and synced when a device comes back online; sent, delivered and read receipts; online presence; history on every device, including a newly added one; push notifications for offline users.
• Non-functional: about a billion users and tens of billions of messages a day; delivery under a second for online recipients; an acknowledged message is never lost; per-conversation ordering; mobile clients on flaky networks with limited battery.

Clarifying questions

• Maximum group size?
• Is end-to-end encryption required (it changes where history and search can live)?
• How many devices per user, and must they all show the same state?
• How long is history kept?
• Are voice and video calls in scope? (Usually not.)

What a strong answer covers

• Back-of-the-envelope numbers for messages per second, storage per day and concurrent connections.
• Data model: users, conversations, participants, messages keyed by conversation with a per-conversation sequence number; per-user, per-device sync cursors.
• Persist before delivering: the message service stores the message, assigns its sequence and acknowledges the sender, then delivers.
• Real-time delivery through persistent connections (MQTT or WebSockets) to gateway servers, with a session registry mapping each user's devices to gateways; push notifications for offline devices.
• Offline sync: each device asks for everything after its last cursor, per conversation or through a per-user inbox; idempotent client message ids so retries don't duplicate.
• Receipts and presence as lightweight events, batched and rate-limited.
• Group fan-out: write once per conversation and fan out on read for large groups, fan out on write to inboxes for small ones.
• Storage in a wide-column store partitioned by conversation, media in object storage with a CDN, and multi-region replication with users homed in a region.

Follow-ups

• Add end-to-end encryption across a user's multiple devices.
• A user installs the app on a new phone with five years of history.
• Edits and "delete for everyone" without breaking sync.
• A region goes down. What do its users see?