Design nearby friends

"Nearby places" is a search problem: the index is huge but it sits still. "Nearby friends" is a stream problem wearing a geo-search costume — the indexed objects move every few seconds, so the work is in the writes, not the reads.

Source: Vol. 2 Ch. 2 Streaming / moving objects Satellite of C22 (geo-index)

First principle — the index moves

In C19 (nearby places) you index a few hundred million businesses that never move; a write happens when a shop opens, a read happens millions of times a second. You build the index once and serve it forever. Nearby-friends inverts the ratio: a few hundred million users each emit a fresh location every few seconds, and a "read" is just whoever happens to have a live subscription open. The dominant cost is therefore the continuous re-indexing of moving points and the fan-out of each move to the people who care — this is a stream-processing problem (DDIA Ch. 11: in-memory operator state fed by a change stream), not a static spatial-search problem. Everything else follows from that one observation.

The geo-index is borrowed, not re-derived

The mechanics of "given a point, find the cell and its eight neighbours" — geohash vs. quadtree vs. S2, neighbour-cell expansion, handling the cell-boundary problem — are taught once in C22 (the geo-index anchor), and the static serving path is worked in C19. This case does not re-derive them. We take a fixed-resolution grid (say geohash level 6, ~1.2 km cells) as given and ask the question those cases never have to: what happens when every indexed point jumps to a new cell every ten seconds? That is the entire delta, and it is where the senior signal lives.

1. Clarify the contract

Treat the prompt as a product contract before it is a box diagram. The system must:

Show me which of my friends are nearby (within some radius, e.g. 5 km), updated within a few seconds of them moving.
Honour visibility: a user who is invisible, or who has hidden themselves from me specifically, must not appear — and toggling invisible must take effect promptly.
Not melt the phone battery: location capture and uplink frequency are part of the design, not an afterthought.
Scale to ~10M concurrently-active users emitting updates.

Just as important, what it need not do: it is not a location history / playback service (no durable trajectory store unless a separate product asks), it is not navigation (no sub-metre accuracy, no routing), and it does not need strong consistency — a friend's dot being 8 seconds stale is fine; a friend's dot appearing after they went invisible is not. Those two sentences shape every storage choice below: ephemeral, in-memory, last-write-wins on location; authoritative and strongly-checked on visibility.

2. Put numbers on it

One estimate dominates everything. Take 10M concurrently-active users, each sending one location update every 10 s:

10,000,000 / 10 = 1,000,000 location updates / s

A million writes per second into a moving index. Now the design question is what each write fans out to. Two strategies:

Naive cell-broadcast. When a user moves, push their new position to everyone subscribed to that geo-cell. In a dense urban cell there might be hundreds of people present, and you broadcast to all of them whether or not they are friends. If the average occupied cell has ~200 subscribers, fan-out is 1,000,000 × 200 = 2 × 10⁸ pushes/s — and most are discarded client-side because the mover is a stranger. Worse, you've just shipped a stranger's coordinates to 200 phones, which is a privacy leak even if the UI hides it.

Friend-first filtering. Instead, push a move only to the mover's friends who are also nearby. An average user has ~200 friends, but at any moment only a handful are inside the 5 km radius — call it ~5. So fan-out per move is ~5, not ~200:

1,000,000 × 5 = 5 × 10⁶ pushes / s

That is the load-bearing comparison: 2×10⁸ / 5×10⁶ = 40× less delivery work, plus it never leaks a non-friend's position. Friend-first filtering is not an optimisation here; it is the design.

Location updates ingested

1,000,000 / s

Naive cell-broadcast fan-out

~2×10⁸ push/s

Friend-first fan-out

~5×10⁶ push/s

Delivery work saved

~40×

Two more numbers keep the design honest. Memory: a live location entry is tiny — user id + lat/lng + timestamp + cell ≈ 40 bytes; 10M of them is ~400 MB, trivially in RAM across a sharded store (DDIA Ch. 6: partition by user or by cell). There is no reason to touch a disk on the hot path. Connections: 10M concurrent users holding a push channel is ~10M sockets; at ~100k WebSocket connections per edge node that is ~100 gateway nodes — sized like any presence/chat fleet, and the reason push must be cheap per idle connection.

3. Data model & API

The API expresses the product operation and hides the grid, the broker, and the shard map:

API / operation	Why it exists
`update_location(lat, lng, accuracy, ts)`	The write that drives everything; client-throttled and accuracy-aware (see battery dive).
`subscribe_nearby()` → stream	Opens a push channel; server emits `friend_moved` / `friend_left` events filtered to this user.
`set_visibility(policy)`	Authoritative privacy switch (global invisible, per-friend hide, "ghost mode"). Strongly consistent.

State, by ownership and durability:

active location — in-memory, TTL'd, last-write-wins cell membership — in-memory index, derived friend edge — durable graph (rarely changes) visibility policy — durable, authoritative presence/subscription — which node holds the socket

The split is deliberate: location is ephemeral (lose it on crash, it self-heals on the next ping in ≤10 s), but the friend graph and visibility policy are durable facts you must never lose or read stale on the privacy-critical path.

4. Linearized design

Walk a single location update through the system in the order events actually move; the bottleneck exposes itself.

1. Throttle at the client. The phone decides when to send (battery dive below): adaptive cadence, and suppress pings that don't change the answer (still inside the same cell, hasn't moved).
2. Ingest into the location stream. The update lands on a gateway and is written to the in-memory active-location store, partitioned by user id, with a short TTL (e.g. 30 s). This is the 1M writes/s firehose.
3. Detect a meaningful change. Compare new cell to old cell / distance moved. If the user is still in the same cell and barely moved, drop it — no fan-out. This collapse is what keeps step 5 affordable.
4. Compute the recipient set — friend-first. Look up the mover's friend edges, intersect with "friends currently within radius" (from the cell index), and for each candidate apply the visibility check. The intersection is small (~5), not the whole cell (~200).
5. Push via pub/sub. Emit a friend_moved event to each recipient's subscription, routed to whichever gateway node holds that recipient's socket. ~5 pushes per move on average.

phone (adaptive cadence, suppress no-op pings) │ update_location(lat,lng,ts) ~1,000,000 /s ▼ ┌──────────────────────────────────────────────────────────────┐ │ INGEST → in-memory active-location store (TTL 30s, by user) │ │ ┌───────────────┐ │ │ │ geo-cell index│ user → cell, cell → {users here} │ │ └───────────────┘ │ └───────────────────────────┬──────────────────────────────────┘ │ cell changed / moved enough? ── no ─▶ drop (no fan-out) │ yes ▼ ┌──────────────────────────────────────────────┐ │ FRIEND-GRAPH ∩ IN-RADIUS ∩ VISIBILITY │ │ ~200 friends → ~5 nearby → minus hidden │ AUTHORITATIVE │ visibility checked HERE, at delivery, per-edge│ privacy check └───────────────────────┬──────────────────────┘ │ recipient set (~5) ▼ ┌──────────────────────────────────────────────┐ │ PUB/SUB → route to node holding each socket │ ~5,000,000 push/s └──────────────────────────────────────────────┘ │ │ │ ▼ ▼ ▼ friend A's friend B's friend C's open stream open stream open stream

The bottleneck is now visible and correctly placed: it is the fan-out at step 4–5, and we already shrank it 40× by filtering friend-first instead of broadcasting the cell. Step 3's no-op suppression shrinks the input to step 4. Nothing here is a database query on the hot path.

5. Deep dives

(1) This is a write/stream problem, not a search problem

The instinct from C19/C22 is "build a spatial index, answer range queries." That instinct is a trap here. In a static index, indexing is a one-time cost amortised over millions of reads; you happily pay for a balanced quadtree or a sorted geohash because you build it rarely. But our points move at 1M relocations/s. Re-balancing a tree or re-sorting an SSTable a million times a second is absurd — you would spend all your cycles maintaining the index and never serve anyone.

So we deliberately use a cheap, mutable index: a flat hash from cell→set-of-users held in memory, where a move is two O(1) set operations (remove from old cell, add to new cell). We give up the elegant logarithmic range query because we don't need it — the radius query is tiny (a 3×3 block of cells around the mover), and it runs against live in-memory sets, not a durable structure. This is exactly DDIA Ch. 11's model: an in-memory stream operator whose state is continuously mutated by an input change-stream, with no durable index in the loop. Recognising "the objects move, so the index must be a mutable in-memory thing fed by a stream, not a durable searchable structure" is the single sentence that separates this answer from a rehash of C19.

(2) The battery/freshness tension can sink an otherwise-correct backend

You can architect the server perfectly and still ship a product people uninstall, because continuous GPS + radio uplink is the fastest way to drain a phone. Freshness and battery pull in opposite directions, and the resolution lives on the client:

Adaptive cadence. Send often when the user is moving fast (driving), rarely when stationary (sitting in a café). A phone that hasn't moved 50 m in two minutes should drop to a very slow heartbeat.
No-op suppression. If the new position is in the same cell and within accuracy noise of the last sent point, don't send at all — it would change nobody's view. This is also what protects step 3 of the pipeline.
Coarse is fine. "Nearby friends" needs cell-level, not sub-metre, precision. Coarser fixes let the OS use cheap network/Wi-Fi positioning instead of the power-hungry GPS chip — saving battery and improving privacy (you never collect more precision than the product needs).
Server-suggested cadence. The server can tell a client "no friends near you, slow down" — a user alone in a region needs far fewer updates than one in a friend-dense city.

The senior framing: location frequency is a joint decision between battery, freshness SLA, and server load — the same throttle knob (lower cadence) helps all three of the phone's battery, the ingest firehose, and the fan-out. It is the cheapest lever in the system and it lives on the device.

(3) The privacy check is authoritative and runs at delivery, not at ingest

This is the question that separates a passing answer from a strong one. The naive design checks visibility when a location is written ("if you're invisible, don't store your location"). That is wrong, because a user's location is necessarily cached in many places by the time they toggle invisible — in the active-location store, in the cell index, possibly in flight inside the pub/sub layer, in a recipient's last-received event, and in transit on the wire. There is no single point where you can "delete" them everywhere atomically. Trying to make ingest the enforcement point means the toggle races against five caches and loses.

The fix is to make visibility an authoritative, strongly-consistent fact and to check it at the last possible moment — delivery (step 4 above, per recipient edge). The location data can be as stale and as widely cached as it likes; what matters is that the instant before we emit a friend_moved event to recipient R about mover M, we re-read M's authoritative visibility-toward-R and suppress if it forbids. Because that check reads the source of truth on every delivery, flipping invisible takes effect on the very next tick regardless of how many stale copies of the coordinate exist. This is the classic move: data eventually-consistent and cheap, authorisation strongly-consistent and checked at the egress gate. (See lesson 09 for why you can pick different consistency models for different facts in the same system.)

Why "check at ingest" is the trap

If you gate at write time, invisibility is only as fresh as the slowest cache holding your last visible location. If you gate at delivery, invisibility is as fresh as one read of the source of truth — and the coordinate caches become harmless, because no one is ever allowed to send them without re-clearing the gate. The cost is one authoritative read per delivery (~5M/s), which is exactly why visibility is a tiny, hot, replicated, in-memory-cached key, not a join against a relational table.

6. Trade-offs

Choice	Buys	Costs	Choose when
Push (pub/sub) vs poll	freshness, lower latency	10M persistent sockets, fan-out machinery	active friend sets are small; freshness SLA is seconds
Friend-first vs geo-first (cell broadcast)	~40× less fan-out, no stranger-location leak	a friend-graph lookup per move	always for this product (dense cells make it mandatory)
In-memory active store vs durable writes	1M writes/s with no disk; self-healing on crash	location lost on crash (re-sent in ≤10 s)	state is ephemeral; staleness of seconds is acceptable
Coarse cell vs precise GPS	battery + privacy + cheaper index	can't do metre-level features	"nearby" semantics; never for navigation
Visibility at delivery vs at ingest	invisibility takes effect next tick, immune to caches	one authoritative read per push	always — it is the correctness requirement

The sharpest trade is friend-first filtering. Geo-first (broadcast the cell, let clients discard non-friends) is simpler to write and avoids a graph lookup, but it loses on both axes that matter: it does 40× the delivery work in dense cells and it ships a non-friend's live coordinates to every phone in the cell, which is a privacy incident waiting to be reverse-engineered from the network traffic. The graph lookup you pay for is cheap (a friend-edge fetch from an in-memory adjacency set) and it is the same lookup that lets you run the visibility gate. You pay once, you win twice.

7. Failure modes

Failure	Mitigation
User appears after going invisible	Visibility is authoritative and checked at delivery, per recipient edge — never gated at ingest. Stale coordinate caches are harmless because no push escapes without re-reading the gate.
Location-update storm (1M/s spikes higher)	Client throttling + no-op suppression cut the input; ingest is partitioned by user (DDIA Ch. 6) so the firehose spreads; shed by lengthening server-suggested cadence under load.
Stale "nearby" friend lingering on screen	Every location carries a timestamp and a 30 s TTL; an expired entry emits `friend_left`. Aggressive expiry beats showing a friend who left an hour ago.
Pub/sub layer overload (fan-out hot cell)	Shard the broker by recipient (so one node's failure is local); coalesce multiple moves of the same friend within a tick; degrade non-critical subscriptions to polling.
Gateway node crash	Active locations are ephemeral and self-heal on the next ping (≤10 s); clients reconnect their subscription to a new node; only durable facts (graph, visibility) must survive, and they live elsewhere.

8. Interview Q&A

How is this different from "find nearby restaurants" (C19)? (senior answer) The indexed objects move. In C19 the index is built once and read millions of times, so you invest in a durable searchable structure. Here every point relocates ~1M times/s, so a durable index would spend all its cycles re-balancing. It's a stream problem (DDIA Ch. 11): a cheap mutable in-memory cell index fed by a change stream, with the work in writes and fan-out, not in range queries.
What's the load and what dominates it? (senior answer) 10M active users × 1 update/10 s = 1M updates/s ingest. The cost driver is fan-out: naive cell-broadcast is ~200 recipients/move (~2×10⁸ push/s), friend-first is ~5/move (~5×10⁶ push/s) — about 40× less. Friend-first filtering is the design, not an optimisation, and it also stops leaking strangers' coordinates.
A user toggles invisible, but their location is cached in five places. Guarantee they vanish on the next tick. (senior answer) Don't try to purge the caches — you can't do it atomically. Make visibility an authoritative, strongly-consistent fact and check it at delivery: immediately before pushing a friend_moved event to recipient R, re-read the mover's visibility-toward-R from the source of truth and suppress if forbidden. The coordinate caches become harmless because no push escapes the gate. Invisibility is then as fresh as one read, not as fresh as the slowest cache.
Why not just check privacy at ingest and skip storing invisible users? (senior answer) Because by the time the toggle arrives, the last visible location is already in the active store, the cell index, the broker, and recipients' clients. Ingest-time gating races those caches and loses. Egress-time gating is the only place with a single authoritative read on the path to the eyeball.
The backend is perfect but users complain about battery. What did you miss? (senior answer) Location cadence is a client-side product decision, not just a server input. Adaptive frequency (fast when moving, slow when still), no-op suppression (same cell + within noise = don't send), coarse positioning (Wi-Fi/cell instead of GPS), and a server-suggested cadence ("no friends near, slow down"). The same throttle helps battery, ingest load, and fan-out at once.
How do you keep 1M writes/s off the disk? (senior answer) Active location is ephemeral and last-write-wins with a short TTL — ~40 bytes × 10M ≈ 400 MB, sharded in memory by user id (DDIA Ch. 6). On a crash the data self-heals on the next ping within 10 s, so durability buys nothing. Only the friend graph and visibility policy are durable.
A celebrity is in a packed stadium — hot cell. What breaks and how do you fix it? (senior answer) The cell-membership set and any geo-first broadcast blow up. Friend-first filtering already caps each move's fan-out at the mover's nearby-friend count regardless of how crowded the cell is, so most of the hotspot evaporates. For the residual, shard the broker by recipient (not by cell) so no single node owns the crowd, coalesce repeat moves within a tick, and degrade to polling under pressure.
How fresh does "nearby" need to be, and what does that buy you? (senior answer) Seconds, not milliseconds, and eventual consistency is fine for the dot's position. That permission is what lets the whole location path be in-memory, lossy, and lazily expired (30 s TTL). The only thing that must be strongly consistent is visibility — and that's exactly the one fact we read authoritatively at delivery.

Related lessons

This case is the streaming / moving-object satellite of C22, which is the anchor for all geohash / quadtree / neighbour-cell mechanics — go there for the index itself; come here for what happens when the points move. C19 (nearby places) is the static-serving counterpart and the cleanest contrast: same geometry, opposite read/write ratio. The push pipeline is lesson 11's pub/sub at graph scale, and the in-memory-state-fed-by-a-change-stream model is its stream-processing core. Partitioning the ingest firehose and the cell index by user/cell is lesson 07; choosing eventual consistency for location while keeping visibility strongly consistent is lesson 09; degrading to polling and shedding under a hot cell is lesson 13.

C22 · geo-index anchor C19 · static nearby search Async messaging / pub-sub Partitioning Consistency & CAP Fault tolerance

Takeaway

Nearby-friends looks like geo-search but is a stream-processing problem: the index moves at 1M updates/s, so it must be a cheap mutable in-memory cell map fed by a change stream, not a durable searchable structure (DDIA Ch. 11). The cost is fan-out, and the one decision that wins is friend-first filtering — ~5 recipients/move instead of ~200, a 40× cut that also stops leaking strangers' coordinates. Location may be ephemeral, lossy, and seconds-stale; visibility may not — make it authoritative and check it at delivery, so toggling invisible takes effect on the next tick no matter how many caches still hold your last position. Battery is solved on the client with adaptive, suppressed, coarse updates — and that same throttle is the cheapest lever for server load too.