Design Facebook Messenger

Functional Requirements

1. Users should be able to send and receive messages in a 1:1 conversation, in near real time.
2. Users should be able to read their history and have it match on every device they own.
3. Users should be able to message a group.
4. Users should be able to see delivery and read state.

Below the line (out of scope):

• End-to-end encryption. Say it out loud as a deliberate cut, because it changes the server from a store that can read and index messages into one that cannot, and it makes multi-device sync a key-distribution problem rather than a storage problem.
• Voice and video calls. Different transport, different problem (signalling plus media relay).
• Search over message content, spam and safety classification, stories.

Non-Functional Requirements

• Do the concurrency number, because it sizes the part of the system that is unusual.
  • Take 2B monthly users, 500M of them online at once, and about 1.5 devices connected each: roughly 750M live connections.
  • A well-tuned connection node holds order of 100K sockets, so that is order of 7,500 nodes at perfect packing, and perfect packing is not a plan: with headroom and N+1 across availability zones call it 15,000 nodes that do nothing but hold sockets open.
  • That number is the design: the fleet that holds connections is separate from the fleet that does work, because they scale on completely different axes.
• Then the message number, which is smaller than people expect.
  • 100B messages a day is about 1.2M messages per second average, call it 3M at peak.
  • At roughly 200 bytes of text plus metadata that is order of 20 TB a day before replication, and it is append-only.
  • 1.2M writes/sec is a lot but it is evenly spread across billions of conversations, so there is no GLOBALLY hot key, which is the opposite of the ticketing problem.
    • Every conversation does have one serialization point, its seq counter, and that is fine precisely because a busy group is single-digit messages per second, three orders of magnitude below what one shard leader serializes.
• Latency is the product. Sender-to-recipient p99 under about 500ms while both are connected. Nobody forgives a chat app that feels slow.
• Durability is absolute, ordering is per-conversation.
  • Once the server has acked a send, that message must survive. Losing one is worse than being slow.
  • Ordering only has to be consistent within a conversation. There is no useful global order across conversations, and promising one would be a lie.
• Availability beats consistency for presence and typing indicators, which are disposable. It does not beat consistency for message delivery.
• Storage is trivial to reason about and expensive to hold: append-only, read overwhelmingly at the tail, and almost never deleted.

Defining the Core Entities

• User is the human: id, display name, and the devices they own.
• Device is a single installation, and it is a first-class entity rather than a detail. Each device has its own sync cursor, because a phone that has been off for a week is at a different point in the story than the laptop that is open right now.
• Conversation is the thread: id, type (direct or group), participant list, and last_seq. It is the unit of ordering and the unit of access control.
• Message is one entry in a conversation: (conversation_id, seq) as the primary key, plus sender, body, created_at, and the sender's client_message_id.
  • The seq is the whole design in one column. It is assigned by the server, it is monotonic per conversation, and it is what ordering, gap detection, and resumable sync are all built on.
• Participant joins a user to a conversation and carries that user's per-conversation state: their last_read_seq and their notification settings.
• Receipt is delivery and read state. Model it as a cursor per participant, not as a row per message per recipient, or a 250-message backlog turns into 250 receipt rows per person. Note what this does not fix: one message still advances one cursor per participant.

API or System Interface

WS     /v1/connect                            // long-lived, authenticated, one per device

POST   /v1/conversations/{id}/messages        // { clientMessageId, body }
                                              // → 202 { messageId, seq, serverTime }
GET    /v1/conversations?since={cursor}       // the conversation list, changed ones first
GET    /v1/conversations/{id}/messages        // ?after={seq} for sync, ?before={seq} for scrollback
POST   /v1/conversations/{id}/read            // { seq } advances this user's read cursor
POST   /v1/conversations                      // { type, participantIds } → 201

// pushed down the socket, never polled for
event  message.new                            // { conversationId, seq, senderId, body }
event  receipt.updated                        // { conversationId, userId, deliveredSeq, readSeq }
event  presence.changed                       // { userId, state, lastActiveAt } - best effort
event  typing                                 // fire and forget, never stored

• The send returns 202, not 201, and it returns the seq.
  • 202 is honest: the server has durably accepted the message and taken responsibility for delivering it, which is not the same as having delivered it.
  • Returning the seq is what lets the sender's own other devices reconcile the optimistic bubble they already drew.
• clientMessageId is supplied by the client and is the idempotency key. A phone that retries on a flaky network must not create two messages, and this is the only thing that prevents it.
• Sync is one shape used everywhere: ?after={seq}. Scrollback is the same call in the other direction. A client that has been offline and a client that is scrolling up are running the same query.

1) Users should be able to send and receive a message in real time

• Split the fleet that holds connections from the fleet that does work.
  • Connection nodes terminate the WebSocket, authenticate the device, and do nothing else. They are memory-bound and almost stateless in what they compute.
  • The MessageService is a normal stateless service that is CPU and database bound.
  • Keeping them separate means you can deploy the logic without dropping 750M sockets, which alone justifies the split.
• A SessionRegistry answers the only hard routing question: which node is holding this device's socket?
  • Key is userId, value is the set of (deviceId, nodeId) currently connected, with a TTL and a heartbeat.
  • Do the heartbeat arithmetic before calling this the cheap part, because it is not.
    • 750M devices on a 30-second TTL is order of 25M writes/sec, which is roughly 20x the entire message write rate.
    • So the node batches: one heartbeat per node covering all ~100K of its sockets, which turns 25M/sec into 7,500 writes per interval and stores liveness per node with a membership set under it.
    • The heartbeat rewrites the entry rather than just extending a TTL, so losing the registry heals in one interval instead of waiting for every client to reconnect.
  • Redis is a reasonable home: it is small, it is hot, and losing it costs a reconnect rather than a message.
• The send path, in order:
  • the sender's connection node hands the message to MessageService
  • MessageService assigns the next seq for that conversation and writes the message durably
  • only then does it ack the sender, because an ack before the write is a lie
  • it looks up every participant's devices in the SessionRegistry and pushes to the nodes holding them
  • devices that are not connected get a push notification instead, and will sync when they come back
• Write once, fan out to many. The body is stored one time in the conversation log, so a 50-person group stores one body and not fifty. The push itself does carry the body, because a client that had to fetch every message it was just told about would double the round trips.

2) History that matches on every device

• Every device tracks its own cursor, and sync is one question: what is there after my seq?
  • A device that has been offline for a week asks the same question as a device that was offline for two seconds.
  • There is no separate "catch up" path to get wrong, which is the point.
• Be precise about "its cursor", because the seq is per conversation and a device has thousands of them.
  • So sync is two phases, not one query: the conversation list returns which conversations changed and what each one's last_seq now is, and only then does the client pull tails for the ones it is behind on.
  • A device with 2,000 conversations that ran one query per conversation would turn every reconnect into 2,000 reads, which is exactly the storm this design is trying to survive.
  • The alternative worth naming, because it is what Messenger actually does: a per-USER inbox sequence layered over the per-conversation one, so a device really does hold a single integer and sync really is one call. It costs an inbox write per participant per message, which is the fan-out the group cap is paying for.
• Real-time delivery is an optimization, not the source of truth.
  • The socket push is a hint that something arrived. The seq range is the truth.
  • If a push is dropped mid-stream, the client notices a gap in seq and pulls the range it missed.
  • But gap detection only fires when a LATER message arrives, so it cannot see tail loss, and tail loss is the common case: someone sends a last message and stops typing. Nothing later ever comes, so no gap is ever observed.
  • The conversation list is what actually covers that: it returns each conversation's current last_seq, so a client compares against its own position and needs no later message to notice. Run it on reconnect and on foreground.
  • This is why the design does not need reliable delivery over the socket, and that is a large simplification.
• Store messages keyed by (conversation_id, seq) in a wide-column store.
  • The access pattern is a range scan over a partition key, which is exactly what Cassandra or HBase is for.
  • Reads are overwhelmingly at the tail, so the hot rows stay in cache and old history falls to cheap storage.
  • Facebook's own answer was HBase first and then MyRocks, and be careful quoting that: MyRocks is RocksDB underneath MySQL, so their history actually runs from a wide-column store TOWARDS sharded MySQL, not away from it.
    • What survives either choice is the access pattern and the engine shape: an ordered range scan over one partition key, served by a log-structured engine that likes append-heavy writes.
    • Saying that is stronger than name-dropping a store, and it does not fall over if the interviewer knows the actual history.
• The conversation list is a separate, much smaller read. It is per-user, sorted by recency, and it is what the app opens to, so it should not require touching the message log.

3) Group conversations

• A group is the same conversation object with more participants, which is what makes the seq model pay off. One log, one seq counter, one write, N deliveries.
• Fan-out on write is right here, and it is worth saying why, since the usual answer is the opposite.
  • A social feed fans out on read for celebrities because one author has 100M followers.
  • Group chats have a hard product cap, 250 in Messenger's case, so the fan-out is bounded by design rather than by hope.
  • Bounded fan-out means you can afford to do the work at write time and keep reads trivial.
• Fan-out is to devices, not to users, so a 250-person group with 1.5 devices each is order of 375 pushes, and most of those are offline and become push notifications instead.
• Membership changes are entries in the log too, so "Ana added Bo" gets a seq and arrives in the right place in the story rather than as a side channel.
• Say the limit out loud: if the product ever wanted thousands, it would stop being a chat and become a broadcast channel, and the right answer is to change the product (fan out on read, no per-member receipts) rather than to scale the fan-out past the cap.

4) Delivery state, read state, and presence

• Three states, and they are three different facts:
  • sent is the server's 202 and it is a fact about the server
  • delivered is the recipient's device acking receipt and it is a fact about a device
  • read is the recipient's app being open at that message and it is a fact about a human
• Carry them as cursors per participant, never as a row per message per recipient.
  • delivered_seq and read_seq on the Participant row say everything a per-message table would say, in two integers.
  • Participant is per user, but delivered is a fact about a device, so state the convention: delivered_seq is the MAXIMUM across that user's devices, which means the tick promises "it reached at least one of their devices", not all of them. Say that out loud, because it is a product promise and not just a storage detail.
  • Marking a 400-message backlog read is one write, and the sender's UI can colour every bubble at or below that seq.
• Presence is best-effort and must never be on the message path.
  • It is a TTL'd key written by the connection node's heartbeat: alive means "there was a heartbeat in the last 30 seconds".
  • Do not fan presence out to everyone: publish only to people currently looking at a conversation with that person, or the write amplification dwarfs the actual messages.
  • If presence is wrong for a minute, nobody is harmed. Design it as disposable and say so.
• Offline devices get a push notification through APNs or FCM, carrying the conversation and seq but not necessarily the body, so the app can wake and sync properly rather than trusting a payload that may arrive out of order.

• If they just nod: "the riskiest part is a message being lost or duplicated across retries and reconnects, shall I open that?"
• Running behind: protect dives 1 and 2. They contain the actual engineering.

1) How is a message never lost and never duplicated?

2) Ordering: what is it, and who assigns it?

• Client timestamps cannot order a conversation, and saying why is most of the answer.
  • Phone clocks are wrong, sometimes by minutes, and users can set them by hand.
  • Two devices in different timezones with skewed clocks produce a conversation that reads as a shuffled deck.
• So the server assigns a monotonically increasing seq per conversation, and that is the order. Full stop.
  • Ordering is only promised inside a conversation, which is the only place it means anything.
  • Two messages sent at the same instant get two different seqs, and which one is lower is arbitrary but consistent for everyone.
• Assigning the seq is the one place a conversation is a hot key, so say how you allocate it.
  • All writes for one conversation go to one shard, keyed by conversation_id, and the counter is incremented there.
  • Allocate it with a single writer per conversation or a conditional write that returns the value it set, not with a distributed lock.
    • Do not reach for a Cassandra counter column here: counter increments are not idempotent, so the retry this design guarantees would double-count, and you cannot read-and-increment atomically to learn the value you were given.
  • This is fine precisely because conversations are small: a busy group is a few messages a second, not thousands.
• The client shows an optimistic bubble before it has a seq, and must reconcile.
  • Render immediately with a local placeholder so the app feels instant, keyed by clientMessageId.
  • When the 202 comes back with a seq, slot the message into its true position, which may move it.
  • Getting this wrong is the classic bug where your own message jumps around after sending.
• Gaps are detectable and therefore recoverable: a client that holds seq 40 and receives 42 knows exactly what to ask for. A design without seq numbers cannot even tell that it missed something.
• Which is exactly why the seq space has to be gapless, and this is the failure to pre-empt.
  • If the seq is allocated in one step and the message written in another, a process dying in between burns a number that nothing will ever fill.
  • A client holding 40 that sees 42 then asks for 41 forever, and the recovery path for the WHOLE design stalls on a message that does not exist.
  • So allocate inside the same write that stores the message, and if a hole can still happen, publish a per-conversation head watermark so a client can be told "nothing below 512 is coming" and move on.

3) Multi-device sync, and the read cursor

• These are two different cursors and conflating them is the bug behind the question.
  • Sync cursor is per device: how far this installation has caught up. The laptop and the phone are genuinely at different points.
  • Read cursor is per user: whether the human has seen it. Reading on desktop must clear the badge on the phone.
• Adding a new device is a bounded backfill, not a full history download.
  • Sync the conversation list first, then the last screenful of each, then older pages lazily as the user scrolls.
  • A new laptop pulling four years of history eagerly is how you take down your own storage tier.
• Read state moving backwards has to be impossible.
  • The advance is a conditional write, and it must be scoped or it moves every row in the table:
    • UPDATE participant SET read_seq = :n WHERE conversation_id = :c AND user_id = :u AND read_seq < :n
    • delivered_seq needs the identical guard, since delivery acks arrive from several devices out of order and regress the same way.
  • Without the guard, a phone that was offline delivers a stale "I read up to 30" after the desktop said 45, and the badge comes back from the dead.
  • This is a compare-and-set: the same guarded-write shape as the seq allocation earlier, and it is worth naming as such.
• Devices that have been gone a long time are a special case worth pre-empting: past some threshold, do not replay the gap message by message, just resync the conversation list and let the client pull tails.

4) What melts first, and what happens when a node dies

• The database is not the interesting failure here, and saying so early buys credibility.
  • 1.2M writes/sec spread over billions of conversations is a sharding exercise with no hot key, which is the easy kind of scale.
  • Contrast with a ticketing system, where the whole problem is one row. Here, the whole problem is one socket.
• What actually melts is the reconnect storm.
  • A connection node holding 100K sockets dies, and 100K devices reconnect at once, then each one runs a sync query.
  • Lose a whole availability zone and that is millions of simultaneous reconnects plus millions of catch-up reads.
  • The fix is unglamorous and expected: jittered exponential backoff on the client, connection nodes that shed load rather than accept everything, and sync that returns a bounded page instead of everything since forever.
• Session registry churn is the second thing.
  • Every connect and disconnect is a write, so a flapping mobile network turns into registry write load that has nothing to do with messages being sent.
  • Short TTLs with heartbeats mean a dead node's entries expire on their own rather than needing cleanup, which is the same expiry-and-reclaim pattern as a lease.
• The silent failure is worse than the storm, and it is the one to name first.
  • Recovery is "notice a gap in seq and pull", but a client only notices a gap when a LATER push arrives.
  • So if pushes stop while the socket stays healthy (a stale registry entry, a wedged outbound path, an evicted key), the client sees no gap, has no reason to reconnect, and sits quietly stale forever.
  • Push being only a hint is what makes dropped pushes survivable, but it also means the pull path needs a trigger that does not depend on a push: an idle resync, or a periodic server-sent head watermark per open conversation.
• Backpressure, which this design gets almost for free and should say out loud.
  • A node holding 100K sockets with unbounded per-connection queues dies the moment a slice of clients stop draining, which on mobile is normal rather than exceptional.
  • So the outbound queue per connection is bounded, and here is the payoff: because a push is only a hint, a node under pressure can DROP the queued frames and send one resync marker instead.
  • Correctness is untouched, because the seq range is the truth. A design where the socket was the source of truth could not do that.
• What a device does when its node dies: the socket closes, the client reconnects to a different node through the load balancer, re-registers in the SessionRegistry, and syncs from its cursor. Nothing is lost because nothing durable lived on that node.
• The messages in flight during that window are the in-flight loss window, and you should name it: a push aimed at a dead node is simply dropped, and the client's post-reconnect sync is what recovers it. That is why the design tolerates unreliable pushes by construction.

5) Offline delivery and notifications

• The SessionRegistry lookup returns nothing for that device, which is the whole trigger. Not connected means notify through the platform instead.
• Send the pointer, not the story.
  • The payload carries conversation id and seq, and enough text for the notification to be useful.
  • The app treats the notification as a nudge and syncs from its cursor, because push delivery is neither ordered nor guaranteed.
  • Building the timeline from notification payloads is how you end up with messages in the wrong order.
• Collapse aggressively. Twenty messages in a busy group must not become twenty banners: collapse per conversation and let the count carry the volume.
• Respect the read cursor: if the user reads on another device, the notification on this one should be withdrawn, which is a real API on both platforms and a detail most candidates miss.
• APNs and FCM are third parties with their own failure modes, so treat them as best-effort and never as the durable path. The durable path is always the message log plus the sync cursor.

Final Design

• Devices hold a long-lived WebSocket to a ConnectionNode, and the connection fleet is sized and deployed independently of everything else because it scales on sockets rather than on work.
• The SessionRegistry maps userId to the set of connected (deviceId, nodeId), with TTLs refreshed by heartbeat, so failure cleans itself up.
• MessageService assigns the per-conversation seq, writes to the message log, and only then acks the sender with a 202.
• The message log is a wide-column store keyed by (conversation_id, seq), which turns both sync and scrollback into a range scan on one partition.
• Fan-out is on write and bounded by the product's group cap, going to devices rather than users, with disconnected devices falling through to APNs or FCM.
• Delivery and read state are cursors on the Participant row, so a 400-message backlog is one write. Be precise about what that buys: cursors collapse the per-MESSAGE dimension, not the per-PARTICIPANT one, so a 250-person group is still 250 cursor advances per message, which is why large groups batch receipts or drop per-member delivery state entirely.
• Presence is a TTL'd key written by heartbeats and published narrowly, deliberately kept off the message path and treated as disposable.
• Every client recovers the same way: notice a gap in seq, ask for the range after its cursor, and apply idempotently.

What is Expected at Each Level

• Mid-level candidates are expected to produce the connection layer, the message store, and the fan-out, and to know that the recipient's socket lives on another machine so something has to route to it.
• Senior candidates are expected to:
  • make the send idempotent with a client-supplied id and say what a duplicate would look like without it
  • put a server-assigned per-conversation seq at the centre and use it for ordering, gap detection, and sync
  • separate the per-device sync cursor from the per-user read cursor
  • ack only after the durable write, and explain why the ack ordering matters
  • model receipts as cursors instead of a row per message per recipient
• Staff candidates are expected to:
  • open with the concurrency math, 750M sockets and the node count that implies, and let it drive the split of the connection fleet from the service fleet
  • argue fan-out on write here against the usual social-feed answer, using the product's bounded group size as the reason
  • treat real-time push as an optimization over a pull-based sync protocol, which is what makes dropped pushes survivable
  • identify the reconnect storm rather than the database as the thing that melts, and give the boring fixes
  • name what the design does not solve: end-to-end encryption would invalidate server-side fan-out and history, and say what it would cost