Design a messaging service (Facebook Messenger)

01Functional requirements

Mira sends one message to Ben. A lost response must not make her retry create a second message, and Ben’s offline phone must later recover the same saved conversation as his laptop. Keep a numbered history so every device can find missing messages.

1. FR1: Send direct and group messages. Support one-to-one and size-limited group text conversations on web and mobile. Give each send a stable client message ID so retries do not create extra messages.

2. FR2: Retain and synchronize history. Save accepted messages. Online and returning offline devices can fetch the same conversation history in order, continuing after the last message they saved on that device along with its conversation position.

3. FR3: Distinguish receipts. Tell the sender when the service has saved a message. Mark it delivered after the recipient device acknowledges saving it. In this example, mark it read when the recipient app reports that the conversation was open and the message displayed. This receipt cannot prove the person actually read or understood it.

4. FR4: Show temporary presence. Use recent signed-in device activity to estimate whether an account is online. Typing indicators expire; they are not part of saved conversation history.

5. FR5: Enforce membership and handle attachments. Check current membership before sending messages or reading history. By default, new members can read messages after their join position. Small attachments refer to separately verified private uploads.

Out of scope

• Voice/video calls, unlimited broadcast groups and one global order across all conversations.
• Mandatory end-to-end encryption. Adding it needs an explicit design for keys, recovery and server-side processing.
• Treating presence or a successful socket write as evidence that a person read a message.

Example: Mira sends client message m17 in conversation c8. Ben's laptop receives saved message s81 live; his offline phone later fetches that same message from history.

02Nonfunctional requirements

Assume 100 million daily active users, each sending 40 messages per day, and five million devices connected at once. Confirm these planning assumptions with the interviewer.

1. NFR1: Send latency. At least 95% of regional sends receive a saved-message acknowledgement within 150 ms at the planned load.

2. NFR2: Online delivery latency. At least 95% of messages to online recipient devices arrive within 300 ms under normal conditions. Offline delivery and human reading are outside this target.

3. NFR3: Durable acceptance. A saved-message acknowledgement means the message, its retry result and the work needed for later delivery have been committed. Accepted history survives one storage-node failure under the selected replication policy.

4. NFR4: One conversation history. Devices eventually display the same per-conversation order. Delivery may repeat, but one successful client message ID produces one visible message. Devices fetch missing messages from saved history.

5. NFR5: Availability trade-off. Saving and reading history target 99.9% availability per calendar month. If the current writer cannot reach the required database replicas or confirm it still owns the conversation’s next position, leave a send pending or return an error; do not acknowledge two conflicting histories.

6. NFR6: Current membership. Check current access for sends, history and attachments. Track membership changes with a version so an old connection cannot keep using revoked permission. Default history starts at the member's join position.

7. NFR7: Bounded connection resources. Limit queued outbound bytes per device. Expire old connection routes and disconnect slow devices with a way to resume from history. A 30-second presence timeout indicates recent activity, not human reading.

8. NFR8: Honest receipts. Delivered and read positions move forward only after their corresponding application actions. An AI summary does not send messages, change membership or advance receipts.

03Size messages and connections

1. **Sends:**100 million users × 40 messages/day = four billion messages/day, about 46,300 sends/second. A fivefold peak is about 230,000/second.
2. History storage: at 1 KB for message text and saved fields, four billion messages add 4 TB/day, or 12 TB with three copies before indexes, delivery state and attachments.
3. Delivery attempts: one message to 100 members with two connected devices each may require 200 live transmissions. One saved message and 200 device attempts are different workloads.
4. Connections: five million devices × 5 KB of assumed application state = 25 GB, excluding transport, operating-system memory and outgoing buffers. Measure full connection cost and simultaneous reconnects before choosing the gateway count.

Decision: size saved history for sends, delivery workers for recipients/devices and connection gateways for their complete measured memory/CPU costs.

04API Design: Requests, Responses and Retries

A send command over HTTP or the socket uses one stable operation identity:

{"type":"send","conversationId":"c8","clientMessageId":"m17","text":"Gate opens at 9","attachmentId":null}

{"type":"persisted","clientMessageId":"m17","messageId":"s81","sequence":81}

Save or retry a message

1. An HTTP client sends the same command to POST /conversations/c8/messages. In the transaction that saves the message and original result, the server checks current membership and assigns the next conversation position.
2. Return 201 Created after that transaction commits. A retry using m17 and the same text returns s81.
3. Return 409 Conflict if m17 is reused with a different conversation, text or attachment; 403 if membership denies sending; 404 for a removed conversation.
4. If the database cannot commit, return 503 without claiming success. After an uncertain timeout, retry m17 to discover or complete the original operation.

Catch up and report progress

1. GET /conversations/c8/messages?afterSequence=80&limit=50 returns saved messages after position 80 in order, plus a cursor for the next page.
2. After a device saves all messages through position 81 and records that position, it sends {"type":"delivered","conversationId":"c8","through":81}. It sends a separate read update after the app displays those messages while the conversation is open.
3. Save the greater of the previous and received position. A late update for 81 cannot move progress backward from 84, and repeating 81 has no further effect.
4. GET /conversations?cursor=... reads the account's inbox index to list its conversations. Changing group membership requires a separate authenticated command.

05Data Model and Storage Access Patterns

A conversation's sequence numbers describe its message order. A device cursor records how far that device has progressed; it can differ between the same person's phone and laptop.

The inbox helps find conversations; the directory helps find connected devices. Neither proves that a message was saved or that an account is still a member. Those decisions use the current conversation records.

06Persist before acknowledging

Start with one conversation application, a transactional history database and periodic client polling.

Send and save

1. Mira's client labels one intended send m17. If a response is lost, it resends m17 rather than inventing a new send ID.
2. The application checks that Mira currently belongs to conversation c8, then looks for a saved result for her m17. Matching content returns that result; changed content is rejected.
3. For a new send, the database locks c8’s conversation record for the transaction, rechecks current membership and reserves the unique sender/request pair. It reads the next position, 81, advances that counter and saves message s81, m17’s result and pending delivery work together. Another send must wait before reading the updated counter; simultaneous sends cannot both choose 81. Concurrent retries cannot both reserve m17.
4. Return “persisted” only after the configured durable save completes. Here persisted means the service saved the message, not that Ben received or read it.
5. A background program finds pending delivery records and retries after crashes. Saving that work with the message closes the gap between “saved” and “scheduled for delivery”; this table is often called an outbox.

Receive and read

1. Ben's device asks for conversation messages after its last applied position 80 and receives s81 at 81.
2. The device saves/applies the message, recognizes repeated s81 IDs and sends a delivered-through 81 acknowledgement.
3. Read-through 81 means Ben’s app reports that the conversation was open and messages through 81 were displayed. Saving on the server, saving on his device and displaying the messages are separate steps; none proves human understanding.

Each conversation has one accepted sequence; unrelated conversations need no global sequence. If the database cannot save the message with its required replica copies and conversation position, keep it pending on the sender’s device or return an error. Initially delivery work can run alongside the application; separate it when recipient work delays new sends.

07Separate connection routing, delivery and presence

Choose how devices communicate

• Periodic polling repeatedly asks for new messages: simple, with extra requests or delay.
• Long polling holds a request until an update or timeout, then repeats.
• A WebSocket keeps a two-way connection open. It reduces repeated setup but does not save messages or recover offline history by itself.

Find Ben's devices

1. His phone connects to gateway G1; his laptop connects to G2. A gateway is the server holding that device's live connection.
2. A session directory saves each device's gateway and an expiry time. A new session version on reconnect prevents a delayed old connection update from replacing its newer route.
3. A delivery worker reads these routes and sends the saved message to both devices. If the directory points to a gateway that no longer holds the device’s connection, that delivery attempt fails. On reconnect, the device fetches missing messages from saved history.
4. Limit queued outgoing bytes. Disconnect a device that cannot keep up and let it resume from its last applied position, instead of retaining unlimited memory.

Estimate online status

1. Devices send periodic “still connected” heartbeats. In this example, expire presence after 30 seconds without one.
2. Ben can remain online while either approved device has recent activity. Typing indicators expire even sooner.
3. Presence estimates recent connection activity. It proves neither delivery nor reading.

Choose storage placement

• Measure gateway CPU/memory, then add gateways and a shared route directory when needed.
• Partition history by conversation to keep its ordered messages together; use a separate user-inbox index to list conversations.
• Storing group history separately for each user duplicates content and complicates one order.
• A queue can route many conversations by key through a limited number of partitions; it need not create a physical topic for every chat.

08Separate live gateways from durable ordering

1. Separate connections from saving. Gateways hold live device connections; conversation services save messages. The directory tells delivery programs which gateway to contact.
2. Partition by conversation. Give each conversation one ordering mechanism and replicate its accepted history under the durability promise before acknowledging saves.
3. Replace a failed writer safely. Losing contact does not prove the old writer stopped. For example, storage records that writer permission 12 has been replaced by 13. Each write compares its permission number with that saved number as part of accepting the write; a late write carrying 12 is rejected. A separate earlier comparison could race replacement. This rejection is called fencing.
4. Recover delivery work. Workers read the saved outbox, retry unfinished sends and mark completed work. Clients check message IDs so repeated delivery does not add another visible message.
5. Limit live buffering. Expire old routes and disconnect slow devices with a history-resume position. Accepted messages remain in saved history even when their connection disappears.

09Follow an online send and an offline return

1. The response is lost: Mira sends m17. The transaction saves s81 at position 81 plus the original result and pending delivery work, but Mira receives no acknowledgement.
2. The send is retried: Mira resends m17. The application finds its saved result and returns s81/81. It does not append another message.
3. A live device receives it: a delivery program finds Ben's laptop route. The laptop checks whether s81 is already stored; it saves one visible copy, then acknowledges delivered-through 81.
4. An offline device catches up: Ben's phone last applied 75. It fetches 76–81 from saved conversation history. If live 82 arrives first, keep it waiting while fetching the gap, then apply the ordered messages.
5. Ben reads: read-through advances when his app reports the conversation open and messages displayed through that position. Receiving bytes alone does not advance it.
6. Access changes: attachment downloads and history reads recheck current membership. Removing Ben updates the membership version; an old signed-in socket cannot preserve the old permission.

For groups, many delivery attempts still refer to one saved message. Stable send IDs prevent duplicate creation; stable message IDs prevent duplicate display. They solve different retry points.

10State privacy, overload and ordering limits

1. A region cannot reach the replicas needed to save a send: leave it pending or return an error. Letting disconnected writers each confirm a different message at position 81 would break the single conversation order promised here.
2. A group is very busy: batch database writes and separate recipient delivery first. Splitting one conversation's ordered writes is a larger correctness change, not just adding a server.
3. A writer is replaced: reject the old writer at the accepted write path as described above. A timeout alone is insufficient.
4. A device falls behind: bound its outgoing queue and recover from saved history after reconnecting. Measure oldest pending delivery age as well as queue length.
5. Security: encrypt transport/storage, revoke devices, check membership and rate-limit abuse. End-to-end encryption is a separate design where only endpoints hold message keys; it changes recovery, search and review.
6. Observe cost and failures: track save latency, delivery delay, reconnect bursts and reuse of one send ID with changed content. Retained history drives storage; recipients and devices multiply delivery work.