Hack University - Design a chat app

Interview 2: Design a chat app

Step 1, requirements. Functional: one-to-one messages, delivered instantly when the recipient is online, stored and shown when they come back. Non-functional: low latency (chat feels dead beyond ~1 second), no lost messages, 50 million users online at peak. Out of scope after asking: group chat, video.

Step 2, estimation. 50M online users sending 40 messages a day each: about 23,000 messages per second average. Each message ~200 bytes, so 2B messages/day ≈ 400 GB/day of message storage. That storage number, unlike the URL shortener's, says sharding from day one (unit 5), keyed by conversation so a chat's history lives together.

The new problem. HTTP is request-response: servers answer, they never call first. But chat needs the server to push Bob's message to Ada the instant it arrives. The tool is a websocket: a connection the client opens and both sides keep open, letting the server send messages down at any time.

Sizing the gateway fleet

Each connection server holds about 500,000 open websockets.

online_users = 50_000_000
connections_per_server = 500_000
messages_per_user_per_day = 40
SECONDS_PER_DAY = 86_400

servers = online_users // connections_per_server
messages_per_sec = online_users * messages_per_user_per_day / SECONDS_PER_DAY

print("Gateway servers needed:", servers)
print("Average messages/sec:", round(messages_per_sec))

Output

Gateway servers needed: 100
Average messages/sec: 23148

A hundred machines just to hold connections, before any message processing, is why chat systems separate the gateway tier from the logic tier. Those two jobs scale on completely different inputs.

Gateways scale with concurrent users, and the chat service scales with message rate. A quiet user holding a connection all day costs a gateway slot and almost no processing, so sizing one tier from the other's number would be wrong in both directions.

The 500,000 figure is optimistic and worth flagging as an assumption. Each connection costs memory and a file descriptor, so real numbers depend heavily on tuning, and a conservative 100,000 per server would mean 500 gateways rather than 100.

Note the N+1 consequence, which lesson 10-2's last block returns to. A hundred gateways at capacity means one failure has nowhere to put half a million reconnecting clients, so the real fleet is larger than the division suggests.

The 23,148 messages per second is the same arithmetic as lesson 9-1, and the peak figure would be several times it. That number sizes the chat service and the write path into the sharded store rather than the gateways.

Checking the sharding claim

Two billion messages a day at 200 bytes each, extended to a year.

import math
messages_per_day = 2_000_000_000
bytes_per_message = 200
node_capacity_tb = 4

storage_per_day_gb = messages_per_day * bytes_per_message / 1_000_000_000
storage_per_year_tb = storage_per_day_gb * 365 / 1000
print("Storage per day (GB):", storage_per_day_gb)
print("Storage per year (TB):", storage_per_year_tb)
print("Storage nodes needed:", math.ceil(storage_per_year_tb / node_capacity_tb))

Output

Storage per day (GB): 400.0
Storage per year (TB): 146.0
Storage nodes needed: 37

Thirty-seven nodes in year one is why this design shards immediately, unlike the URL shortener. That contrast is the whole point of running the estimate, since the same arithmetic said one database for the shortener and a sharded cluster here.

math.ceil rounds the node count up, because a fractional node is not a thing you can run. Rounding down would leave the last 2 TB of the year with nowhere to go.

Compare this with lesson 9-1's social app, which produced 2 TB a year from a similar user count. Messages are small and there are a hundred times more of them, so volume rather than record size is what makes chat a storage problem.

The 37 nodes also grow every year, which the single-year figure hides. Year two needs 74 unless old messages are archived to cheaper storage, so the design needs a retention or tiering answer as well as a sharding one.

Note that this ignores replication, and the real number is two or three times larger. Each shard is a leader-follower set from unit 4, so 37 shards of data means roughly a hundred machines holding it.

Steps 4 and 5, the message path

Websockets break lesson 2-3's rule: a connection is state, pinned to one gateway. We handle it honestly:

Ada's phone holds a websocket to gateway 17, Bob's to gateway 62. A Redis registry (lesson 2-3's shared store) maps user → gateway
Ada sends a message. Gateway 17 hands it to a stateless chat service, which writes it to the sharded message store, the source of truth, before anything else
The chat service looks up Bob, finds gateway 62, and forwards the message there for push delivery
If Bob is offline, the message simply waits in storage. When he reconnects, his client asks for everything after the last message ID it has

Deep dives interviewers reach for: delivery receipts are just tiny messages flowing backward. Ordering within a chat comes from sequence numbers assigned by the shard that owns the conversation (one writer per conversation, the lesson 4-2 trick). Duplicate sends on retry are killed by idempotency keys (lesson 6-2).

Why the message is stored before it is delivered

So a crash after that point cannot lose the message, since the requirement was no lost messages.

Once the message is durably stored, every failure has a recovery story. Delivery can be retried, and an offline Bob fetches it on reconnect, so the loss of a gateway or a process costs latency rather than data.

Deliver-then-store would open a window where a crash loses the message forever. Bob's phone shows it, the store never received it, and Ada's own history is missing a message she watched being sent, which is the worst kind of inconsistency because two users disagree about the past.

The order also gives the sender an honest acknowledgment. The write completing is what justifies showing a sent checkmark, and acknowledging before the store means the checkmark can be a lie.

Note the cost, which is that the store's write latency is now on the delivery path. A slow shard delays the message rather than just the history, and that is a real tradeoff the design accepts to satisfy the requirement.

Durability first and delivery second is the standard order whenever the requirement says no data loss. It is the same reasoning as a queue producer saving the raw file before enqueueing the job in lesson 6-1.

Which provisioning rule covers a gateway crash

The answer is lesson 2-3.

It is N+1 provisioning, meaning run enough capacity that losing one node still leaves room for its load. Here it means the gateway fleet needs headroom for half a million refugee connections.

Without that headroom the failure spreads, which is the specific danger. Reconnecting clients would fill the surviving gateways to capacity, some would be refused, and the retry traffic from those refusals adds load to a fleet that is already saturated.

The reconnect storm is also concentrated rather than spread out. Half a million clients discover the failure within seconds and reconnect at once, so the fleet must absorb a burst rather than a gradual migration, which argues for more than the bare minimum spare.

The reconnect-then-catch-up flow works precisely because messages were stored first and clients track the last id they received. The client asks for everything after that id, so nothing is lost and nothing is duplicated.

Note that this is the same rule applied to app servers in unit 2 and to database nodes in lesson 5-3. Recognizing that one arithmetic habit covers three different tiers is what makes it worth naming rather than rederiving.