BOOK DEEP READ · System Design Interview Vol 2 · Ch 2
System Design Interview Vol 2 · Ch 2 · Alex Xu & Sahn Lam · 2022
Apple has Find My. Facebook once had a feature called Nearby Friends: open a map and see which of your friends happens to be close by, with a little note saying "updated 3 minutes ago". This chapter builds that from nothing. It looks like the same kind of problem as the previous chapter — finding nearby restaurants — but the answer turns out to be almost the opposite.
To find restaurants, the last chapter numbered every shop in the world and filed them into one enormous ledger sorted by location; you show up, you look it up. This chapter is looking for people, and people move every half minute. That ledger would need three million edits a second — you could never keep up. Stranger still: the right answer here is not a faster ledger. It is no ledger at all.
Do it the old way and your phone has to ask the server, every half minute, "where are my few hundred friends right now?" — and the server has to go leaf through the ledger for each one. With a hundred million people asking at once, the servers struggle, and your phone battery does not survive until lunch. Uber worked this way early on, and has said publicly that the first thing to collapse was not the servers but the battery.
Think of each person as a little broadcast channel. You and your few hundred friends each open one; you subscribe to theirs, they subscribe to yours. Whoever moves shouts into their own channel — "I'm over here now" — and only the people who subscribed can hear it. Nobody looks anything up. The locations come to you.
So who measures the distance? Whoever hears the shout. Your friend calls out, the server holding your connection hears it, holds up a ruler and checks: is he within five miles of me? If yes, show him; if not, pretend you never heard. The system never has to answer the big question "who in this city is near whom" — only a long series of tiny ones: "is he near me?"
Locations are written on notes that fade. Each person's current position is one sticky note that disappears by itself after forty seconds. The elegance is in what that buys: someone closes the app, steps into a lift, runs out of battery — their note simply evaporates, and they fade off their friends' maps on their own. Nobody has to sweep up.
The whole thing works because of one precondition: you already know which few hundred people you care about. So it only handles friends. If you want to find strangers around you — a set nobody knows in advance — you have to go back to the previous chapter's big ledger. Real products run both.
And the cost is real: every phone must hold a wire open to the server at all times. The connection itself consumes resources, and even shipping a new server version means waiting for the old wires to empty out.
To find where your friends are, don't search — give everyone a broadcast channel, let movers shout, and let listeners measure the distance themselves. Write each position on a note that vanishes in forty seconds, so anyone who drops offline fades off the map on their own. Finding strangers is what the previous chapter's ledger is for.
Want the mechanisms, the numbers and the diagrams? → Switch to the deep read
You would expect Nearby Friends to be the previous chapter's proximity service with a different data source. The two chapters in fact run in opposite directions: Ch 1 indexes motionless places into a geohash grid and waits for you to query it, whereas here the objects move every 30 seconds and the index is stale the moment it is built — so the whole chapter's answer is don't search at all. It seizes on one precondition — your friends are a known set of a few hundred people — and demotes a geospatial search into publish/subscribe along the friend graph: locations are pushed out, and distance is computed at the receiving end. The second counterintuitive claim: this location data is supposed to rot on arrival. It goes into a cache with an expiry, dropped messages are never resent, and putting a durable queue like Kafka on the hot path is a liability rather than an asset.
This is Ch 2 of System Design Interview Vol 2, immediately after Ch 1's proximity service: the previous chapter handles things that don't move (restaurants, petrol stations), this one handles people who do, and Ch 3 on Google Maps carries the geography line into road graphs and navigation. Its real-world counterparts are Apple's Find My, the car crawling across your Uber map, the green dot on a Discord avatar. It is also the first time the book puts a stateful connection tier on the table.
The requirement is small: open the app, see friends within 5 miles with their distance and an "updated N minutes ago" stamp, refreshed every 30 seconds. The scale is not: one billion registered users, of whom perhaps 10% use the feature — 100 million active users.
Do the arithmetic first. One report per person per 30 seconds gives 100M ÷ 30 ≈ 3.3 million location updates per second. For comparison, the previous chapter's proximity service ran at roughly 5,000 read QPS with almost no writes — this chapter's write volume is three orders of magnitude higher, and every write has to spread to a group of people immediately. The old approach hits three walls:
First, the index cannot take it. A geohash grid index only works when the indexed objects rarely move; 3.3 million coordinate changes a second means 3.3 million index deletes-plus-inserts a second, and write amplification will flatten any B-tree.
Second, polling cannot take it. Have each client ask "where are my friends" every 30 seconds and you get 3.3 million queries a second, each pulling a few hundred friends' coordinates. Uber did exactly this early on, and later said publicly that the first thing to fail on that path was not the servers but phone batteries.
Third, and most easily missed: the server needs the right to speak first. When a friend moves, the server learns of it first, yet HTTP's shape is "client asks, server answers" — the server has no standing to open its mouth. To make "my friend moves and my screen updates" possible, you first need a channel the server can write into unprompted.
The previous chapter asked "what restaurants are around me" — the candidate set is unknown, it could be any shop on earth, so the world must be indexed first. This chapter looks like it asks "which friends are around me", but it is really asking something of a different nature: among my few hundred friends, who is close to me right now. The candidate set is known in advance, and it holds hundreds, not billions.
Once you see that, the problem changes species: no geospatial index is needed, only a friend list (which you already have) and a route to push the location down. A search problem has been demoted to a delivery problem — that is the chapter's one core trick, and every component below merely paves that route. State the cost up front: it fails completely for strangers, since you cannot pre-subscribe to someone you have not met.
The first component is a WebSocket server: every online user holds an open two-way channel to it, so the server can push down whenever it likes. The price is that this tier is stateful — "user B's connection is held by box 7" exists only in box 7's memory. Three bills follow:
The second component is the route the location travels: give every user a channel, channel:{user_id}, meaning "this person's location broadcast", and let each of A's online friends subscribe to it via whichever WS server holds them. One update then runs as in Fig 2: phone A reports its coordinates → the server writes the cache and publishes to channel:A → every WS server subscribed to that channel receives a copy → each one computes the distance per relevant connection it holds and pushes down only those within 5 miles.
Why distance is computed at the receiving end. The radius is each recipient's own business: B cares how far A is from B, C cares how far A is from C, and the same broadcast has a different answer for each. Computed at the receiver, the publisher never needs to know where anyone is, and the pub/sub layer in the middle degenerates into a pure pipe — it does not understand geography and does not need to.
The scale of the fan-out. Each update is copied to every online friend of the publisher. Taking a few hundred friends each with roughly a tenth online at any moment, the fan-out multiplier sits in the tens; multiply by 3.3 million updates a second and total system deliveries land on the order of hundreds of millions per second. That number explains both why pub/sub has to become a cluster and why no step on this path may be heavy — one extra disk write, one extra network hop, multiplied by that, is a catastrophe.
The third component is storage, and it splits into two halves of entirely different character.
The hot half is just a key-value cache: user_id → (lat, lng, timestamp) in Redis, with a TTL set slightly longer than the refresh interval (40 seconds against a 30-second cadence). Here sits the prettiest detail in the chapter: one mechanism solves two problems. It makes stale positions expire by themselves — you never see a two-hour-old coordinate presented as "now" — and it makes offline detection free. A user closes the app, steps into a lift, runs out of battery; no component has to notice, no "went offline" message is needed, the entry evaporates after 40 seconds and friends' maps quietly drop the dot. Offline logic you never wrote is offline logic that cannot be wrong.
The cold half is location history, appended to something like Cassandra (partition key user_id, clustering key the timestamp). What matters is that it stays off the hot path: history is useless for live display and serves only replay and analytics, so it goes asynchronously and tolerates lag, and its hiccups must never propagate back into the push path — in practice it lands in Kafka first and is consumed into storage. A sense of cost, too: 3.3 million records a second at tens of bytes each is a dozen-odd terabytes of raw writes per day, which makes "do we keep history, and for how long" a product question that has to be answered here, not a technical footnote.
A single Redis cannot absorb 3.3 million PUBLISH calls a second and the hundreds of millions of deliveries behind them, so pub/sub has to be a cluster. The unit of sharding is the channel: consistent-hash channel:{user_id} across N servers and record ownership in service discovery (etcd or ZooKeeper), which a WS server consults before subscribing.
The cost model is not what intuition suggests: a channel is merely an entry in a "channel → subscriber list" map, and one with no subscribers does not exist at all — so even with a billion user IDs, the number of real channels equals only those online and subscribed to. The expense is entirely CPU: every message walks the subscriber list and is delivered copy by copy, so bigger fan-out is what costs, while the channel count barely matters.
Channels migrate during scale-out and failure, and a few location messages can be lost in that window. Losing them is perfectly acceptable here, for a hard reason: a location is an idempotent full snapshot, not a delta, so the next 30-second report repairs the state on its own, and the consequence of a drop is that one dot moves half a minute late. That judgement drives the whole of the next section.
If the requirement grows into "show any nearby user, not just friends", this design runs out — you cannot pre-subscribe to someone you don't know. The right answer is to run both: friends keep the pub/sub push, strangers go back to the previous chapter's grid index — the cache maintains "geohash cell → the online users currently in it", and a query takes the union of your own cell and its neighbours. Because only online users are held and the set entries carry a TTL as well, this index is far smaller than "all users".
Table 1 · Server push vs client polling
| Push over a long connection (this chapter) | Client polling on a timer | |
|---|---|---|
| Latency | Arrives as the friend moves, sub-second | Bounded by the interval, 30 seconds at best |
| Server cost | Hundreds of millions of sockets held open; boxes sized by connection count | No connection state, but 3.3M queries/s hit the data tier |
| Client cost | One socket plus heartbeats; power-frugal | Wakes the radio every cycle — the battery fails first |
| Operational cost | High: stateful, deploys must drain, reconnect storms | Low: stateless, scale at will |
| When to pick it | Real time is the selling point; many concurrent users | Slow updates are fine, small user base, or a rarely opened screen |
Table 2 · What carries the location messages
| Redis Pub/Sub (this chapter) | Message queue (Kafka etc.) | Direct RPC fan-out | |
|---|---|---|---|
| Semantics | Fire and forget, nothing on disk, dropped if nobody listens | Durable, replayable, with consumer offsets | Point to point, no broker |
| Latency | Sub-millisecond | Milliseconds to tens, one extra disk write | Low, but you maintain the routing |
| Cost | Losses are unrecoverable | Pays throughput and latency for reliability you don't need; a topic per user is infeasible | Sender must know which box holds each receiver — heavy coupling |
| Verdict here | A location is an idempotent snapshot that self-heals in 30s — reliability is a liability | Belongs on the history bypass only | Degenerates into N×N connections at scale |
| Good for | State broadcast: presence, live location, cursors | Billing, orders, chat — streams where one loss is a bug | A handful of fixed services |
Table 3 · Which end computes the distance
| At the sender (filter before publishing) | In a central service | At the receiver (this chapter) | |
|---|---|---|---|
| Feasible? | Publisher must know every friend's position — an inverted dependency, pulling hundreds of coordinates per publish | Needs a global live view of who is where; concentrates load into a natural single point | Needs only the position of the user on this very connection — parallel by construction |
| Side effect | Forces the pub/sub layer to understand geography | Changing the radius means changing central logic | Every subscriber can have their own radius |
Table 4 · Two kinds of "nearby": this chapter vs the last
| Nearby friends (this chapter) | Nearby places / strangers (Ch 1) | |
|---|---|---|
| Candidate set | Known, a few hundred; changes every 30s at 3.3M write QPS | Unknown, any object; almost static at ~5,000 read QPS |
| Approach | Fan out along the graph, filter at the receiver, no read amplification | Geohash grid index, read the cell plus its 8 neighbours |
| Main cost | Operating a stateful connection tier | Index maintenance, rising with how fast objects move |
What actually transfers out of this chapter is not the Nearby Friends product but the general shape of state broadcast: a crowd of clients holds long connections, a change to some entity fans out along a known relationship graph, and each receiver decides whether to display it. Swap "location" for "presence" and you get the green dot on an avatar; swap it for "order status" and you get the courier crawling across a delivery app; swap it for "document cursor" and you get the coloured flags in collaborative editing.
The high-scoring moves in an interview are equally fixed: do the 3.3M QPS arithmetic first to show why the previous chapter's approach is out; name the known candidate set and convert a search problem into a delivery one; point out that the TTL also buys offline detection; and be willing to argue that reliable delivery is not wanted here — that last one separates someone who memorised an architecture diagram from someone who thought about it.
① In one line: when the candidate set is known, don't search — flip "nearby friends" from a geospatial query into publish/subscribe along the friend graph.
② Scale dictates shape: 100M active users × one report per 30s = 3.3 million location updates per second, which rules out both indexing and polling at once.
③ Long connections are mandatory: HTTP gives the server no right to speak first, hence the WebSocket tier — stateful, and sized by connection count rather than QPS.
④ One channel per person: channel:{user_id}, subscribed on a friend's behalf by whichever server holds them; the pub/sub layer is a pure pipe with no notion of geography.
⑤ Distance is computed at the receiver: the same broadcast has a different answer per recipient, so receiver-side computation is what lets everyone hold their own radius and lets the middle stay ignorant.
⑥ The TTL is semantics, not cleanup: a 40-second expiry retires stale positions and delivers offline detection at the same time — offline logic you never wrote cannot be wrong. Storage splits accordingly, with the history stream written asynchronously off the hot path.
⑦ Reliable delivery is not wanted here: a location is an idempotent snapshot that self-heals in 30 seconds, so Kafka on the hot path is a liability — swap in chat messages and the judgement instantly reverses.
⑧ Pub/sub is consistent-hashed by channel into a cluster with service discovery tracking ownership; the expense is CPU fan-out, not channel count. Finding strangers means returning to Ch 1's geohash grid — real products run both.