Real-time Chat

Clarify the requirements and turn them into a contract

Start by separating what the system does from how well it must do it. The functional surface for this problem is small and standard: one-to-one and group messaging, delivery and read receipts plus presence (online, away, last-seen), and a persisted, ordered message history that a client can scroll. Notice what is deliberately out of scope so you do not waste interview time: media transcoding, end-to-end encryption key exchange, search, and spam are real but orthogonal. Call them out, park them, and move on.

The non-functional requirements are where this problem actually lives, and the simulator encodes them as hard SLOs. Real-time, low-latency delivery means an end-to-end p99 budget — the gym sets 150 ms for delivery through the cell. Per-conversation ordering means two messages in the same conversation must be shown in the same order to everyone, forever; note that this is per-conversation, not a global total order, which matters enormously for scale. Reliable delivery means a message that the sender saw as sent must eventually reach every member, including members who are offline at send time — this is the store-and-forward requirement. Finally, availability under failure: the gym demands at least 95 percent of messages delivered while a gateway crashes and a network link is cut.

Quantify the contract before drawing any boxes, because the numbers drive every later decision. The graded targets are: availability at least 0.95 (the heaviest-weighted objective), delivery p99 at most 150 ms, throughput at least 9,000 messages/sec sustained, and peak gateway saturation at most 0.90. Those four numbers are the rubric you are optimizing against; if a design choice does not move one of them, it is decoration. Note there is deliberately no cost SLO in this scenario, so redundancy is essentially free to add.

• Functional: 1:1 and group messaging; delivery and read receipts plus presence; persisted, ordered, scrollable history.
• Non-functional / SLOs: availability >= 95% (weight 3), delivery p99 <= 150 ms (weight 2), throughput >= 9,000 rps (weight 2), peak saturation <= 90% (weight 1).
• Explicitly out of scope here: media pipeline, E2E encryption, full-text search, anti-abuse.
• Ordering is scoped per conversation, not globally — say this out loud, it unlocks the scalable design.

Back-of-the-envelope: connections, message rate, storage, bandwidth

Chat has two independent scaling dimensions, and conflating them is the most common interview mistake. The first is concurrent connections — how many sockets you hold open. The second is message rate — how many sends and deliveries flow per second. They scale separately: a billion idle phones are cheap to hold and expensive to message; a small busy group is the reverse.

Work the global numbers first, then map to the cell the simulator grades. Assume 500 million daily active users, each sending about 40 messages/day. That is 500M x 40 = 20 billion messages/day, or 20e9 / 86,400 ~= 231,000 messages/sec on average. Apply a peak-to-average factor of about 2.5x for the busy evening hour and you are near 600,000 messages/sec at peak. Delivery amplifies this: a 1:1 message is one delivery, but a group message fans out to every online member, so a realistic average fan-out of about 3 pushes peak delivery events past 1.5 million/sec. You shard this across cells; at roughly 9,000 delivery events/sec per cell — exactly the simulator's baseRps — that is on the order of 150 to 200 cells (1.5M divided by 9,000). The gym is asking you to design one cell correctly.

Connections: assume 20 percent of DAU are connected at once, so 100 million live WebSocket sockets. A well-tuned gateway holds on the order of 100,000 connections (memory is the limit: 100k sockets x ~30 KB of socket buffers and app state ~= 3 GB; WhatsApp famously demonstrated 2M+ per host, so 100k is conservative). That is ~1,000 gateway processes fleet-wide for connections alone — and that count is driven by socket count, not message rate, which is why you size the gateway fleet on the larger of the two dimensions.

Storage and bandwidth: a text message with metadata is roughly 1 KB (media lives in a separate blob store; the message row carries only a pointer). 20 billion/day x 1 KB ~= 20 TB/day of message data, about 7 PB/year before replication, ~21 PB/year at replication factor 3. This is append-heavy, range-read-by-conversation data — a wide-column store, not a single relational table. Egress at peak is roughly 1.5M deliveries/sec x 1 KB ~= 1.5 GB/sec, which is why delivery, not durable write, dominates the hot path.

• 20B messages/day -> ~231k/sec average, ~600k/sec peak; with ~3x group fan-out, ~1.5M delivery events/sec at peak.
• Simulator cell = ~9,000 delivery events/sec; the global fleet is on the order of 150-200 such cells.
• ~100M concurrent sockets / ~100k per gateway -> ~1,000 gateways for connections alone (separate from message-rate sizing).
• ~20 TB/day, ~7 PB/year message data (RF3 ~21 PB); ~1.5 GB/sec peak egress — delivery dominates the hot path.

High-level architecture: the five components and why each exists

The reference topology is a single ingress that fans into redundant connection-holders, decoupled from durable storage by a buffer. Concretely: clients open persistent WebSocket connections to an edge load balancer, which spreads them across stateless WebSocket gateway servers; gateways hand accepted messages to a delivery queue; a consumer drains the queue into an append-only, conversation-partitioned message store. Those are exactly the five required component kinds the gym checks for: client, lb, service (gateways), queue, db.

Why a WebSocket gateway tier and not plain HTTP request handlers? Because delivery is server-initiated. The server must push B's incoming message down B's already-open socket the instant it arrives; you cannot do that with a connection the client only opens to ask a question. WebSockets give you a bidirectional, low-overhead, long-lived channel — the rubric awards this full marks (10), with HTTP long-polling as a partial-credit fallback (5) for hostile proxies and 5-second REST polling as a wasteful last resort (2). The gateways are deliberately stateless about message content: they own sockets and routing, nothing durable, so any gateway can be killed and its clients reconnect elsewhere.

Why a queue between the gateways and the store? It decouples delivery latency from durability latency. The gateway can accept a message, enqueue it, and return a fast sent acknowledgement to the sender without waiting on a disk write, which protects the 150 ms p99. The queue also absorbs bursts — when a group goes off and the send rate spikes, the buffer can fill and drain instead of overloading the store. And because the queue is partitioned by conversation id, it preserves per-conversation order on the way to the store. In the simulator this is one queue node with a drain capacity of 22,000 rps and an 80,000-request buffer; in production it is a partitioned log such as Kafka where each conversation maps deterministically to a partition.

Why an append-only store partitioned by conversation? Because the write pattern is pure append and the dominant read is the most recent N messages in one conversation. Partition by conversation id, cluster by sequence number, and both operations are single-partition and fast. The rubric scores this design 10, a single un-partitioned relational table 4 (fine early, a write hotspot at volume), and memory-only 0 (it cannot satisfy store-and-forward). Two more components belong in your verbal answer even though the gym abstracts them into the gateway and queue: a session registry (user id -> gateway id, in a fast KV/cache) so a gateway can find which gateway holds a recipient's socket, and a push-notification path (APNs/FCM) to wake offline recipients.

Deep dive 1 — Ordering, idempotency, and reliable delivery

This is the correctness heart of the problem, and the gym's delivery rubric wants three mechanisms together, each worth 5 points: per-conversation sequence numbers, acknowledgements plus retries keyed by an idempotency token, and a queue between the gateways and the store. Each solves a distinct failure.

Per-conversation sequence numbers give you ordering without global coordination. When a message lands in its conversation's partition, the store assigns the next monotonic sequence number for that conversation id. Because the conversation id is the partition key, the counter lives on exactly one partition — no cross-shard consensus, no distributed clock. Clients render strictly by sequence number, so even if two messages traverse different gateways and arrive out of order on the wire, the client sorts them deterministically. Crucially, this is per-conversation order, which is all users perceive; a global total order across all conversations would require consensus and would not scale, and nobody can observe it anyway.

Idempotency makes retries safe. The sender generates a unique message id (a UUID or a client-sequence tuple) and attaches it to the send. The network is unreliable, so the client retries until it receives an ack; every retry carries the same message id. The store dedupes on (conversation id, message id), so a message delivered twice on the wire is persisted and shown once. Without this, an ack lost on the return path causes the client to resend and the recipient to see duplicates — the classic at-least-once-becomes-exactly-once trick. The rubric explicitly rewards acks plus retries with idempotency keys and explicitly penalises fire-and-forget with no acknowledgements, because without acks you can guarantee neither delivery nor order.

The queue ties it together. The gateway enqueues onto the conversation's partition and returns the sent ack; a consumer assigns the sequence number and persists. FIFO within a partition means messages for one conversation are sequenced in the order they were enqueued, even under retry, and the durable write happens off the latency-critical path. There are two acknowledgement hops to keep straight: the sender's sent ack (the server durably accepted the message) and the recipient's delivered and read receipts (the message reached B's device and B opened it). Receipts are themselves just small messages flowing back through the same gateways, sequenced per conversation.

• Sequence numbers are assigned on the conversation's single partition — ordering with zero cross-shard coordination.
• Client-supplied message id + store-side dedupe on (conversation id, message id) turns at-least-once retries into exactly-once display.
• Sent ack (server persisted) is distinct from delivered/read receipts (reached/opened on the recipient device).
• A per-conversation partitioned queue preserves order and moves the durable write off the 150 ms latency path.

Deep dive 2 — Routing to the recipient, surviving the partition, and offline delivery

Delivery is a routing problem: recipient B's socket lives on some gateway, and when A sends, the system must find that gateway and push there — fast. The mechanism is a session registry mapping user id to gateway id, kept in a fast KV/cache and updated on every connect and disconnect. A sending gateway looks up each online recipient, then either forwards directly to the owning gateway or publishes onto a pub/sub channel the owning gateway subscribes to. Presence rides the same plumbing: clients heartbeat over the socket, a presence service derives online/away/last-seen, and the state propagates with a short TTL. Presence is intentionally approximate — never pay for strong consistency on whether someone is online two seconds ago.

Offline recipients are handled by store-and-forward, and this is why durability sits on the critical path of correctness even though it is off the critical path of latency. If the registry shows no live socket for a recipient, the message is already durably stored, so you simply do nothing synchronous for that recipient and fire a push notification (APNs/FCM) to wake their app. On reconnect, the client pulls everything it missed with a single range read: messages in each conversation with sequence number greater than the client's last acknowledged sequence. That is one cheap single-partition scan, and sequence numbers make catch-up exact with no duplicates and no gaps. The rubric's top answer (10 points) is precisely this: push to online members via gateways, store-and-forward for offline, deliver on reconnect plus a push.

Now the centerpiece the simulator is built around: surviving a network partition. The chaos script cuts the edge between the load balancer and the gateway tier at t=18s for six seconds. If you have a single gateway path, the load balancer suddenly has nowhere to forward — in the engine, the cut removes its only outbound edge, so 100 percent of traffic is dropped for the entire window. That single event drops availability well below the 0.95 target and collapses throughput. The fix, and the reason the reference graph draws gateway A and gateway B as two separate paths under one load balancer, is path redundancy: the partition resolver cuts exactly one lb-to-gateway edge, so when the link to path A is cut, the load balancer reroutes every connection onto the still-alive path B. Redundant replicas inside one pool do not help here, because the cut is on the path, not the box — you need a second independent path, not a bigger first one.

For that reroute to actually hold the SLOs, each path must be sized to carry the full peak alone. The reference runs each path as 3 replicas x 5,500 rps = 16,500 rps. Peak offered load is baseRps 9,000 x the 1.5x group surge ~= 13,500, and with the engine's ~5 percent load wiggle about 14,200 rps. A single surviving path at 16,500 rps carries 14,200 at ~0.86 utilization — just under the 0.90 saturation SLO. Size each path at only 15,000 and the surviving path runs at ~0.95 and fails saturation; run one shared pool and the partition fails availability outright. The two numbers — two paths, each at ~1.16x peak — are the whole ballgame.

• Session registry (user id -> gateway id) plus pub/sub lets any gateway route to the gateway holding a recipient's socket.
• Offline: message is already durable; send a push; client pulls seq > last_acked on reconnect (one single-partition range read).
• Partition cuts one LB->gateway edge: a single path drops 100% for the window; two independent paths reroute and keep delivering.
• Each path is sized at 3 x 5,500 = 16,500 rps so the survivor carries the ~14,200 peak at ~0.86 saturation (under the 0.90 SLO).

Bottlenecks under load: walking the chaos timeline

The simulator's 40-second run is a scripted gauntlet, and each event maps to a specific SLO and a specific scaling lever. Reading the timeline is how you reverse-engineer the reference capacities.

From t=0 to 12s the cell runs steady at 9,000 rps and everything is green. At t=10s a gateway crashes (kill_node removes one replica). With the starter's 2 replicas x 3,500 = 7,000 rps per pool, losing one leaves 3,500 — already below the base 9,000, so messages drop. With the reference's 3 replicas per path, a lost replica drops a path from 16,500 to 11,000, still above base load; and because the engine distributes load across the two paths weighted by capacity, both paths settle at equal utilization rather than pinning the survivor. The lever is replicas per path; the SLO at risk is saturation.

At t=12s the group goes off and load jumps to 1.5x, ~13,500 (~14,200 with the engine's wiggle). Anything sized below peak now drops continuously. This is why every node on the path is provisioned above peak: gateways at 16,500 per path, the queue draining at 22,000, the store at 20,000. The store deserves emphasis — at 20,000 rps against a 14,200 peak it never becomes the bottleneck, which is the point of putting the queue in front of it. At t=18s the partition hits (covered above): availability, the heaviest-weighted SLO, is on the line, and only the second path saves it. At t=26s the surge eases to a sustained 1.3x (~11,700), and at t=30s a latency spike multiplies the queue's processing time by 8x (the engine's latency_spike factor). The queue's 5 ms base becomes 40 ms, then everything is multiplied by a congestion factor of 1/(1 - utilization). The defence is to keep utilization low: the queue drains at 22,000 against a fill that peaks near 14,200 during the 1.5x surge (utilization ~0.65) and sits around 11,700 during the spike window (utilization ~0.53), so the congestion factor stays in a 2-3x band and the 8x spike lands the queue's own latency around 85 to 115 ms.

Two facts keep that from blowing the 150 ms budget. First, most of the steady-state p99 is the gateway and store hops, not the queue: the simulator gives each service hop a base processing latency that, with light queueing, sums to a steady-state p99 of roughly 70 to 100 ms across the load stages — already under budget. Second, and decisively, the latency SLO is scored as the median of per-tick p99 over the whole run, not the worst tick. The two genuinely ugly excursions are each only a six-second blip: the queue spike pushes a tick's p99 toward ~175 ms, and the partition is worse still — the surviving gateway runs at ~0.86 utilization, its congestion factor jumps to ~7x, and per-tick p99 briefly approaches ~240 ms. The median sails past both, staying comfortably under 150 ms. The lesson doubles up: keeping the gateway off its saturation ceiling protects latency as much as availability.

The general scaling rules fall out of this. Gateways scale horizontally on the larger of connection count and message rate; add replicas, and add whole independent paths for partition tolerance. The store scales by adding conversation-id shards, since the partition key already spreads load and hot conversations. The queue scales by adding partitions, which also raises drain throughput. The load balancer (50,000 rps in the reference) is almost never the bottleneck and is cheap to over-provision as a single logical tier. Keep the queue's drain rate strictly above its fill rate — that is the binding constraint — and its buffer (80,000) is then just insurance for transients.

• Gateway crash (t=10s) -> need >=3 replicas/path so the survivors don't pin; threatens saturation.
• Group surge 1.5x (t=12s) -> every path node sized above ~14,200 peak: gw 16,500, queue 22,000, store 20,000.
• LB<->gateway partition (t=18s) -> only a second independent gateway path keeps availability >= 0.95; the survivor at ~0.86 sat is the binding saturation sample.
• Queue latency spike 8x (t=30s) -> keep drain (22,000) well above fill (~11,700 at t=30) so utilization (~0.5-0.65) holds the congestion factor near 2-3x; the median-of-p99 scoring absorbs the 6-second blip.

Key trade-offs to defend in the interview

Transport. WebSockets win for chat because delivery is server-initiated and connections are long-lived: bidirectional, low per-message overhead, lowest latency. HTTP long-polling is the graceful fallback when a corporate proxy blocks WebSocket upgrades — it works, at higher overhead and latency. Periodic REST polling is the last resort: a client polling every 5 seconds wastes requests and adds up to 5 seconds of latency. The rubric mirrors this exactly with 10, 5, and 2 points.

Where ordering lives. Per-conversation sequence numbers on the conversation's single partition are cheap and exactly match what users perceive. A global total order would need consensus across shards, would throttle throughput, and is unobservable to any user. Choose per-conversation order deliberately and say why.

Fan-out on write versus on read. Chat stores each message once per conversation (one ordered log) and fans out to online sockets on delivery, with offline members pulling on reconnect. This avoids writing N copies into the store and keeps history a single clean append log. Contrast this with a news feed, where fan-out-on-write into per-user timelines is often correct because reads vastly outnumber writes; chat's write/read ratio and its strict ordering requirement push the other way.

Stateless gateways plus an external registry versus sticky sessions. Stateless gateways let the load balancer place any connection anywhere and let you reroute on crash or partition — the property that wins this scenario — at the cost of a registry lookup to find a recipient's gateway. Sticky routing avoids the lookup but pins users to a host and degrades badly when that host dies. Finally, redundancy versus cost: two full gateway paths roughly double gateway spend compared with one pool. There is no cost SLO in this scenario, and availability is the heaviest-weighted objective, so the trade is clearly worth it here — but state it explicitly, because in a cost-sensitive variant you would push the redundancy down to multi-AZ replicas within one logical path instead of two full paths.