Design a chat messaging service

01Problem and scope

Scope the design to durable text, one-to-one conversations, then bounded groups, with multiple devices and advisory presence. An offline recipient does not make a send fail: acceptance depends on storage, and the recipient catches up later. Mobile push is a wake-up hint. Acknowledging a message before durable storage would violate this contract, so the sender receives success only after commit.

Support text, history, multiple devices, delivered/read receipts, online indicators, bounded groups and optional mobile push. Exclude attachments, end-to-end encryption protocol design, message editing and globally ordered history across unrelated conversations from the core exercise. If encryption becomes mandatory, discuss key distribution, multi-device recovery and server search limitations separately. The design separates connection capacity, durable acceptance and recipient delivery because each can reach capacity or fail independently. The conversation owner is the storage leader responsible for ordering that conversation’s messages and membership changes; its replicas preserve committed history if the leader fails.

02Functional requirements

A device cursor records the conversation position through which that device has safely applied history without gaps. Its progress is monotonic: later reports can advance it but cannot move it backward. Presence has a different purpose: a renewable, expiring lease estimates whether a device is still connected; it says nothing about which messages the device stored.

1. Send: Return accepted only after the chosen durable commit boundary.
2. Receive live: Low-latency hint/message delivery with client deduplication.
3. Fetch history: Ordered bounded pages with explicit membership/history boundary.
4. Reconnect: Recover every retained authorized message after the device cursor.
5. Report receipts: Monotonic device progress; read is distinct from delivered.
6. Show presence: Lease-based estimate, never a requirement for durable send success.
7. Change group membership: Membership change serialized with send authorization.

Client identity and ordered history

The sender's client creates stable clientMessageId=send-71 before sending. Repeating that identity with the same body returns the same accepted message; changing the body under it is a conflict. The recipient's devices independently resume their progress. An online event may arrive twice or out of order, but the displayed committed history uses the server's conversation sequence and one identity per message.

Membership, previews and pending sends

A removed group member cannot obtain newly unauthorized messages simply because a gateway still has an open socket. Decide history semantics explicitly: new members initially see messages from their join sequence onward; departed users cannot fetch new history after removal. Push previews avoid disclosing sensitive body text on a locked device by default. The sender may see a local pending bubble immediately, but only an accepted response gives it a committed sequence. A network timeout leaves the outcome unknown until retry resolves the same identity.

03Non-functional requirements

1. Acceptance latency: Accepted-message p95 below 200 ms within the home region.
2. Delivery latency: Online delivery p95 below 500 ms under normal load. Measure this separately: a fast commit can hide a slow delivery queue.
3. Availability: 99.9% eligible send availability. If a conversation owner loses its majority, reject new sends or leave them pending on the client; never acknowledge from a minority to preserve an online dot.
4. Durability: Accepted messages survive one storage-node or availability-zone loss through replicated authority.
5. Regional recovery: Declare a separate asynchronous recovery objective and measured loss window. Three replicas in one region do not imply zero regional data loss.
6. Retention: Keep history for an illustrative five years; changes affect storage and legal/product behavior. Scope each device cursor to a conversation and its permitted history range.

Message and receipt invariants

A read receipt is a client assertion, not proof of a human's attention. Acceptance, delivery and reading are separate observable outcomes.

04Capacity estimates

Workload assumptions and arithmetic

Use 500 million daily active users sending forty messages/day: 500M × 40 = 20B messages/day, or 20B / 86,400 = 231,481 writes/s. Fivefold peak is about 1.16 million writes/s. At 100 bytes of text, bodies total 2 TB/day and 3.65 PB over five years. A 300-byte stored envelope including IDs and metadata gives 6 TB/day and 10.95 PB over five years, before indexes, copies and retention cleanup.

Assume 10% of daily users are online simultaneously with 1.2 connected devices each: 500M × 0.10 × 1.2 = 60M connections. At a measured 20,000 active connections per gateway, the fleet needs 3,000 gateway-equivalents before failover reserve. That per-node figure must come from a representative TLS, heartbeat and messaging benchmark, not a universal limit. Thirty-second heartbeats produce 60M / 30 = 2M heartbeats/s even with no chat messages.

Worked estimates

Capacity implications and limits

A one-to-one read/write bandwidth ratio does not apply once groups, retries and multiple devices are included. Partition the append log for write throughput; scale gateways for sockets and delivery bandwidth; budget presence separately.

05APIs and contracts

Request and response example

The sender sends {"type":"send","conversationId":"c8","clientMessageId":"send-71","body":"Train arrives at six"} on an authenticated connection. The server replies {"type":"accepted","messageId":"m901","sequence":1042} only after commit. The same operation is available as an authenticated HTTP POST for retry/fallback. A body mismatch under send-71 returns 409 instead of silently replacing text.

Interface contracts

Validation and response semantics

Connection handshake authenticates user and device. Each send/history operation still checks conversation membership at the authority. Payload size, per-sender message rate and group size are bounded; use 429 or a structured retryable error for overload. A reconnect includes device identity and per-conversation cursors, not a claim that every earlier push was received. History may include tombstones/control events needed to preserve cursor continuity while hiding removed content. Pagination uses sequence positions rather than wall-clock timestamps, which can tie or move backward.

06Data model and access patterns

The model needs both a shared message order and separate device progress. Conversation sequences order accepted history; client message IDs identify send retries; device cursors track delivery to each phone or laptop. Membership records govern access, and an outbox row records delivery work in the same commit as the message so a dispatcher can recover it after a crash.

Join, removal and rejoin are ordered control events in the same conversation log. One join timestamp cannot represent a member who leaves and rejoins: replacing it either leaks the absent interval or hides permitted earlier history.

The query WHERE conversationId='c8' AND sequence>1040 ORDER BY sequence LIMIT 100 is a range read. Partition by conversation, optionally using bounded time/sequence buckets for older history while retaining a conversation routing index. Hashing each message ID independently would scatter the exact range query we need. User-to-conversation summaries form a derived inbox index; they are not a second authority for the message body.

A session directory maps (userId,deviceId) to gateway and connection generation with a lease expiry. A newer generation supersedes a disconnected socket; delivery failures refresh directory state. The directory and presence caches are derived from active sessions and may be stale. Log durability never depends on them. Store only bounded recent pages in memory, such as the latest messages of visible conversations; archival history has different retrieval and redundancy economics. Both partitioned SQL and suitable wide-column systems can support the append/range pattern when their real consistency and throughput meet the contract.

07Basic working design

Conversation commit and local sockets

Start with one chat process, one SQL database and connected clients. The process holds a local map of authenticated device connections. The sender's send begins a transaction: check membership, look up send-71, allocate c8 sequence 1042, insert m901 and an outbox row, then commit. Only after commit return accepted. The dispatcher reads the outbox and writes to the recipient's socket if connected; otherwise the history remains available for catch-up.

Recipient persistence and retry recovery

The recipient's phone stores m901, advances its contiguous local cursor and reports deliveredThrough 1042. If the report disappears, it can repeat it. The recipient’s laptop later reads after 1040 and obtains 1041 and 1042. The sender does not need to retype the message because the recipient happened to be offline. A database row plus recovery query is more important than a perfect live notification path.

Long-poll baseline and its limits

Long polling can implement delivery initially: hold a request until new data or timeout, then reopen it. WebSocket provides a persistent bidirectional transport and may reduce repeated HTTP setup. Neither transport makes a message durable in the database or prevents a retried send from inserting a duplicate. The baseline already differentiates pending, accepted, delivered and read states, so later gateway fleets preserve those semantics instead of redefining “sent” whenever a process crashes.

08Find the baseline flaws

09Improve the design, step by step

1. Split connection gateways from conversation storage. When one process cannot manage the connection load, move sockets to gateways with bounded event-driven buffers and an expiring session directory. Storage workers consume a bounded number of concurrent requests, independent of idle connection count. This improves isolation and allows gateway replacement. It costs routing hops, directory staleness and reconnect logic. A single process remains simpler for small communities; a separate thread per socket is not required by the product.

2. Partition and replicate conversation authority. Write throughput and accepted-message durability trigger many logical conversation partitions, each with a replicated leader. Membership checks, sequence allocation, deduplication and outbox insertion remain one partition-local atomic operation. This distributes independent conversations but leaves a very hot group on one owner. A globally ordered log is rejected because unrelated conversations need no shared order; splitting one huge group's order would change the product semantics.

3. Decouple delivery with durable outbox dispatch. A slow recipient gateway or push provider must not delay durable acceptance. Commit m901 first; delivery workers then route notifications and update conversation summaries. The improvement is recoverable delivery without blocking acceptance on the recipient's device. The cost is queue lag and at-least-once delivery, meaning events may repeat. Exactly-once transport is not assumed; clients and storage deduplicate identities. Direct post-commit delivery may remain a low-latency fast path, but the durable outbox repairs missed attempts.

4. Bound history/presence work and introduce archive tiers. Five-year storage and millions of heartbeats trigger recent-page caches, time/sequence history buckets, colder storage and selective presence subscriptions. This reduces hot storage and unnecessary broadcasts. It costs archive latency, cache misses and advisory status. Erasure coding can reduce cold-history redundancy overhead but changes repair/read behavior; it is not a substitute for protecting current writes. Broadcasting every heartbeat to every friend is rejected because the amplification has little user value.

Erasure coding stores data fragments together with additional encoded fragments so the data can be reconstructed after the supported number of fragment losses. It can use less space than several full copies, but reconstruction and repair require extra work. That tradeoff may suit old history while newly accepted messages retain the chosen fast replicated commit path.

All steps preserve the same accepted boundary. A faster socket acknowledgement that drops durability would be a contract regression, not a performance improvement.

10Detailed architecture

Connection routing and conversation ownership

The edge balances new connections among healthy gateways; existing traffic stays on its authenticated socket. Gateways forward c8 sends through a conversation router that resolves the current owner and its ownership version, called an epoch. The owner checks membership and commits the ordered log, request deduplication and outbox to a replica group. A majority failure stops acceptance for that partition; an obsolete owner is rejected by storage-epoch checks.

Live delivery and push hints

Outbox dispatchers resolve each recipient's current devices through the session directory, then send to the appropriate gateways. Group fanout expands one log entry into bounded recipient tasks. An offline-device worker may send a privacy-conscious wake-up to the external mobile push provider, but provider acceptance is not a delivered/read receipt. Conversation summary indexes and device cursor stores support user views and recovery.

Authorized recent and archived history

History APIs route to the authoritative or sufficiently current log and may use recent immutable page caches. They check membership and allowed history bounds before returning entries. Presence uses a separate directory whose entries expire unless devices renew them. It combines rapid online/offline changes before notifying subscribed contacts, reducing status flicker and unnecessary updates. Its failure can make an online dot inaccurate without losing messages.

Acceptance boundary and connection leases

Synchronous send work ends when m901 is durably committed; live delivery, push, receipts and inbox summaries occur afterward. Receipts themselves become durable monotonic updates so device reconnects do not move progress backward. The diagram separates these steps so a successful send is not confused with successful device delivery.

Concrete storage and transport choices

A practical baseline uses PostgreSQL for the message, membership, request identity and outbox transaction, with separate gateway processes and a disposable leased routing cache. At the large illustrative load, move whole conversation partitions onto storage that actually supports the required atomic operation and safe leader changes. PostgreSQL synchronous replication, Cassandra-style replica counts and a custom Raft-backed log have different guarantees; a “quorum” label does not make them interchangeable. Verify committed-history preservation and current authorization reads in the chosen implementation.

11Write path and acknowledgement

One conversation owner serializes membership, retry identity and sequence allocation in the acceptance transaction. Request send-71 becomes message m901 at sequence 1042; notification delivery starts only after that commit.

1. The sender's client journals send-71 with its body before transmission and shows a pending bubble. It authenticates the connection and supplies conversation c8.
2. The gateway enforces size/rate limits and forwards to c8's current owner. It does not invent a final sequence or accepted response.
3. The owner begins a transaction, checks current membership and the unique sender/client-message identity. If already committed with matching payload, return its existing m901/1042 result.
4. For a new request, allocate the next conversation sequence under the same owner lock, insert m901 and its deduplication identity, and append outbox event deliver-c8-1042 in the transaction.
5. Commit through the required replica quorum. Only now emit accepted 1042. A lost response is an unknown transport outcome; retrying send-71 returns the same message.
6. The dispatcher reads the outbox, expands eligible recipients and resolves the recipient's phone gateway. It sends the committed message or a hint to fetch it, recording bounded retry state.
7. If the recipient is offline, retain the log and schedule optional push. No client-visible send failure is inferred from advisory presence. When a delivery attempt fails, retry routing without re-inserting the message.

The conversation lock orders a membership removal against a send. If removal commits first, the send is rejected; if send commits first, its eligibility follows the defined membership boundary. This decision is local to c8, not a global transaction across every participant's inbox.

12Read and delivery path

Each recipient device maintains its own contiguous cursor. The following recovery path starts at sequence 1040 and handles message 1042 arriving before the intervening history has been applied.

1. The recipient's phone receives committed c8 sequence 1042. If its durable cursor is 1040, it detects the gap and fetches from 1040 instead of claiming that everything through 1042 arrived.
2. The history service authorizes the recipient and returns a bounded ordered page, including any necessary control/tombstone positions. It does not depend on whether the earlier gateway still exists.
3. The phone atomically stores newly applied message identities and its new contiguous cursor in one local transaction, then sends deliveredThrough 1042. Advancing the cursor before saving the message could permanently skip it after a client crash. A repeated m901 event produces no second bubble.
4. The server updates that device cursor with a maximum operation, so a delayed receipt for 1041 cannot move it backward. A read action generates a separate readThrough update constrained by the application's receipt policy.
5. The recipient's laptop reconnects later with its own cursor 1040 and repeats the authorized history path. Phone delivery does not incorrectly advance the laptop's state.
6. The sender's client receives updated receipt summaries asynchronously. It may display “delivered to a device” or another explicitly chosen aggregation, rather than implying every device or the human saw the text.

For group c9, the same log is stored once while delivery reaches multiple authorized members/devices. Large groups may receive lightweight wake-ups and fetch history in bounded pages. Presence subscriptions fetch an initial relevant snapshot and receive debounced changes; neither an online dot nor push-provider response is proof that a message was read.

An authorized page carries an opaque continuation through the log, including safe skip/control positions for intervals the device cannot read. Those positions reveal no hidden message body; current membership and stored history intervals still filter every returned message. If the cursor predates retained history, return an explicit history-expired/reset response with the earliest retained position instead of making the device fetch an unfillable gap forever. A reset acknowledges the retention limit; it does not claim the deleted history was delivered.

13Correctness deep dive

Identity and sequence authority

The storage transaction, not the transport, decides the message identity. Deduplication is scoped to (c8,sender17,send-71) and compares the payload hash. The sequence increment and insert share that transaction; a sequence reserved outside it would complicate contiguous recovery and failure handling.

Lost receipt after device persistence

Stale gateway and cursor recovery

A stale G1 entry in the directory may receive another attempt. Its connection-generation check prevents directing data onto an unrelated reused session, while current recipient/membership checks protect disclosure. Failed routing is retried or left for cursor recovery. During a storage leadership change, the old leader's epoch must be fenced from commits; two leaders assigning sequence 1042 independently would violate the invariant. The replica protocol establishes that authority, while the gateway directory merely locates sockets.

Intentional duplicates versus retries

A timed-out client may have sent the same text twice intentionally under two different IDs; the service keeps both. Content equality is not a valid deduplication rule for chat.

Membership intervals at delivery

14Failure and recovery

15Operations, security, and cost

Separate acceptance, delivery and read metrics

Measure pending-to-accepted latency, accepted-to-device-delivered lag and delivered-to-read reports separately. Alert on outbox age, duplicate-send retries, owner failovers, replica lag, reconnect rate, gap-fetch frequency and hot-group queue length. Presence churn has its own budget. A high send-success rate can coexist with a broken delivery system, so acceptance alone cannot be the service dashboard.

Retention, sockets and group-fanout costs

The main costs are retained message copies, gateway resources for sockets, and delivery to each recipient device. Three copies of the 10.95 PB five-year envelope estimate need 32.85 PB before indexes and backups. If recent-page caching saves a history query but duplicates every user's entire five-year history in memory, it loses economically. Cache bounded visible conversations and measure reuse. Large-group delivery can be batched by gateway so one payload serves several local recipients, trading gateway CPU against inter-server bandwidth.

Message authorization and abuse controls

Authorize every send/read, bound group membership and message size, and rate-limit spam per account and conversation. Avoid putting sensitive text in logs and default push previews. Transport encryption does not equal end-to-end encryption; if the latter is required, the server stores ciphertext and the key-management design changes the product's recovery/search behavior.

Crash, reconnect and migration drills

Test crashes before/after the message commit and before/after client receipt persistence. Simulate stale gateway directory entries, leader fencing, group-member removal during send, and a large reconnect wave. Roll out storage migrations by copying a conversation partition, replaying its log, fencing old ownership and comparing range reads. Changing partition layout must not renumber committed messages or reset deduplication identities.

16Decision ledger and limitations

User-ID partitioning gives local user-history reads but can duplicate a conversation across participants and complicate one shared ordering authority. We choose conversation ownership plus a derived per-user conversation index. Time/sequence buckets bound old-history partitions. A wide-column log-oriented engine can fit append/range access, but rejecting SQL categorically is unjustified; benchmark the actual transaction, partition and storage requirements.

WebSocket and long polling are transport alternatives. WebSocket reduces repeated request setup and supports two-way events; long polling works through ordinary request infrastructure but reconnects frequently. Frequent short polling is simpler at tiny scale and wastes more empty work at high connection counts. None eliminates the durable offline log. Cold erasure-coded storage can save redundancy bytes but brings repair and read-latency tradeoffs; preserve fast replicated protection for new acknowledged messages.

17Interview closing

“I designed durable text chat with one-to-one conversations, groups, history, presence and multi-device recovery. A send is accepted only after the conversation owner commits its stable request identity, immutable message, ordered sequence and delivery outbox. Duplicate attempts recover that result. Every recipient device has an independent cursor, so live delivery can repeat or fail without changing committed history.

“The workload is about 231,000 average writes per second and sixty million assumed live connections, so socket gateways and storage partitions scale separately. Conversations own order and membership; gateways locate devices. I use bounded asynchronous delivery and push only as a wake-up mechanism. Presence is a lease-based hint rather than evidence that a message was read.

“I accept temporary send unavailability when a conversation lacks safe write authority. The remaining bottlenecks are very hot groups, recipient amplification and reconnect storms. I would next measure acceptance and delivery lag separately under a gateway-failure load test.”

If the interviewer requests a million-member broadcast group, avoid extending the small-group fanout loop blindly. Store one ordered channel log, send coalesced update hints, and have active subscribers fetch pages through caches. Re-estimate moderation, bandwidth and ordering requirements while preserving the accepted-message boundary.

Recall the key ideas

Answer from memory before opening each card. Explain why the choice works and what it costs. Revisit missed cards tomorrow.