System design practice

Chat

medium websocket pub-sub durability presence

Store before the ack, then deliver over pub/sub or push.

Solve it in your browser Read the lesson first

Design one-to-one messaging for a chat app. Phones keep a WebSocket open to the service while the app is in the foreground; when it is not, the only way to reach the user is a push notification.

Functional requirements

Use these use case and scenario names exactly: the traffic, requirements and tests in problem.proschi refer to them.

Scale

Constraints

What is given

problem.proschi declares the sender and the recipient and the external push provider (APNs and FCM; about 200 ms per notification), and holds the traffic, requirements and tests. Add the components, the connections and the two use cases.

How your design is checked

You write the design as text in Proschi. Tests run in your browser: a simulation of the traffic above checks latency, availability, cost and what happens when a machine fails. How the simulation works.

Start designing

Lesson · 11 min read

Learn it: Chat #

Chat: store before the ack, deliver after it #

One-to-one chat mixes three ideas that each look simple alone: a durable write, a long-lived connection, and routing a message to whichever server holds the recipient. Get the order wrong and you either lose messages or make every sender wait for the slowest phone on the network.

What you'll learn #

The problem, explained #

Who uses it. 50 million daily active users on phones. In the foreground the app keeps a WebSocket open to the service; in the background the only way to reach the user is a push notification through APNs or FCM.

Functional requirements.

Non-functional requirements.

RequirementTarget
p99 (the latency 99% of requests beat)Send to ack under 100 ms, history under 200 ms
AvailabilitySending 99.95%
DurabilityA message is never lost once the sender saw the ack
OrderingThe ack never waits for delivery (push provider or recipient); after the ack, look up presence, then deliver
Fault toleranceAny single machine can fail
BudgetAt most $4,000 a month

What is given, and why. given.proschi declares the sender, the recipient and the external push provider, with a capacity of 10k notifications a second and roughly 200 ms per call. Everything between them is yours.

What the tests check.

Back-of-the-envelope #

sends, each one write and one presence lookup
10k rps
gateway work (sends + deliveries)
17k rps
push notifications (limit 10k)
3k rps
messages stored (1 KB each, average a third of peak)
≈ 290 GB/day
QuantityArithmeticResult
Sendsgiven10k rps
Online deliveries via pub/sub70% × 10k7k rps
Push notifications30% × 10k3k rps (provider limit 10k)
Presence lookupsone per send10k rps
Message writesone per send10k rps
Gateway work10k sends + 7k deliveries17k rps
History readsgiven2k rps
Messages per day (assume the average is a third of the peak)10k/s ÷ 3 × 86,400 sabout 290M
Storage per day (assume ~1 KB stored per message)290M × 1 KBabout 290 GB/day, about 100 TB/year

The storage line rests on two assumptions (the statement gives neither the average rate nor a message size), but it shows the shape: data grows forever, writes never stop, and reads want the recent messages of one conversation.

Gateways do two jobs. A message to an online recipient touches the gateway tier twice: once on the way in (the sender's gateway) and once on the way out (the recipient's gateway). That is 10k sends plus 7k deliveries. At 2k requests a second per service replica, 17k rps needs 8.5 replicas at 100%; divide by a 70% target, and check that the tier still copes with one replica lost.

The store must take 10k writes a second. A modelled relational database has one primary that takes every write: 5k writes a second per shard, however many read replicas you add, so 10k saturates it unless you shard. Cassandra is a wide-column store (rows grouped into partitions by a key, sorted inside each partition) in which every replica accepts writes, 20k a second each in the model, so two are lightly loaded. Real chat systems chose such stores for this append-heavy, partition-by-conversation pattern; Discord's write-up is the famous one.

Latency. The ack path is load balancer → gateway → message store → ack: a 2 ms hop, a 10 ms gateway, a 5 ms write, plus queueing and tails. That fits 100 ms easily. One 200 ms call to the push provider before the ack would not.

Connections, not just requests. A real gateway is also sized by open connections and memory per connection. With tens of millions online at peak you need enough gateways to hold them all: mention it, though the simulation counts only requests.

Cost. Service replicas $100, a load balancer $50, a Redis replica $150, a queue or broker replica $200, a Cassandra replica $500. With $4,000, every tier is sized, not padded.

Concepts #

The ack is a promise: store first #

An ack (acknowledgement) tells the sender "your message is safe", which is only honest once the message is in durable, replicated storage. Ack on receipt and store later, and a gateway crash between the two loses messages the sender believes were sent.

Once stored, everything else can be retried: delivery, the push notification, syncing the sender's other devices. The store is the source of truth; connections and notifications are just ways of telling people to look.

The cost is one database write before the ack: a few milliseconds on a store built for appends. Ephemeral signals such as "typing…" indicators are the exception: fine to lose, they never touch the database.

Deep dive The same order in Proschi

Store, answer, then publish asynchronously, here for comments on a thread:

title "Durable comments"

reader "Reader"        [Actor]
api    "Comments API"  [REST API]  x2
store  "Comment Store" [Cassandra] x2
fanout "Comment Bus"   [Kafka]     x2

reader -> api    : HTTPS
api    -> store  : write
api    -> fanout : publish

usecase "Post comment" {
  reader -> api    : POST /threads/5/comments
  api    -> store  : INSERT comment c_9
  store --> api    : ok
  api   --> reader : 201 {"id": "c_9"}
  api   ->> fanout : CommentPosted c_9
}

WebSockets and stateful gateways #

Chat needs the server to talk first, which plain request/response HTTP cannot. A WebSocket (RFC 6455) starts as an HTTP request and upgrades to a long-lived, two-way TCP connection where either side sends at any time.

That makes a gateway stateful: Bob is connected to gateway 7, not to "the service". Losing it drops his connection (his app reconnects elsewhere), and anyone reaching Bob must know where he is. Load balancers must support long-lived connections, and deploys must drain them gradually.

OptionHowCost
WebSocketOne long-lived, two-way connectionStateful servers; the default for chat
Long pollingThe client holds a request open until there is news, then re-opens itWorks everywhere, but a request per message
Server-sent eventsA long-lived HTTP streamServer to client only

Skip WebSockets for occasional updates, where a push notification or a periodic poll is enough.

Presence and pub/sub routing #

The sender is on gateway 3, the recipient on gateway 7. Two pieces get the message across:

If nobody is connected, send a push notification instead. Presence can be stale: a phone that just lost signal looks online until its key expires. That is fine, because the message is stored: the app fetches it when it next opens and deduplicates by message id. Real systems also send the push when the recipient's device does not confirm the delivery.

Trade-offs: presence is one more store to keep available, and very large groups need fan-out to many gateways. Slack's real-time messaging uses the same split: gateway servers hold connections, separate servers track presence.

Deep dive Presence and pub/sub in Proschi

Live sports scores use the same lookup-then-publish shape:

title "Live scores"

source   "Match Data"  [Third Party API]
feed     "Score Feed"  [Worker]          x2
registry "Who Watches" [Redis]           x2
bus      "Score Bus"   [NATS]            x2
edge     "Socket Edge" [WebSocket]       x3
fan      "Fan"         [Actor]

source -> feed     : webhook
feed   -> registry : lookup
feed   -> bus      : publish
bus    -> edge     : deliver
edge   -> fan      : WebSocket

usecase "Goal scored" {
  source    -> feed     : GoalScored match 12
  feed      -> registry : GET watchers:match12
  registry --> feed     : edge-2
  feed     ->> bus      : PUBLISH edge.2 goal
  bus      ->> edge     : goal (on edge-2)
  edge     ->> fan      : SCORE 1-0
}

Designing it step by step #

1. Scope. Ask: one-to-one or groups (one-to-one)? Guarantees (never lost after the ack; delivered at least once, so a message may arrive twice but never zero times, and the client deduplicates)? Ordering (per conversation, by time)? Multi-device (history anywhere)? Receipts, typing indicators, media (out of scope; name them)? Confirm 10k sends a second, 70% of recipients online, 2k history loads a second.

2. High-level design. Draw three paths.

History uses a separate stateless API: it is ordinary request/response and should not take gateway capacity meant for live traffic.

3. Deep dive.

4. Wrap-up. Walk the requirements: the ack follows the write; delivery follows the ack in both scenarios; nothing is single; the budget fits. Then extensions: time-ordered message ids, delivery and read receipts as reverse-direction messages, groups with per-group fan-out, end-to-end encryption, and syncing a user's other devices by listing every connected device in presence and delivering to each.

Common mistakes #

Delivering before the ack (wrong/deliver-before-ack). The gateway stores the message, publishes it, waits for the recipient's connection to confirm, then acks. It feels "more correct" (the ack means "delivered"), but the sender now waits on the recipient's phone, perhaps on a slow network, and a stuck connection stalls them. It fails Delivery happens after the ack.

Other classic mistakes.

In the interview #

Likely follow-ups, with short answers:

Further reading #

Now design it

Review cards for this problem

Short questions on the ideas it needs, from the review cards. Review them daily so they stick.

More system design problems