Design Nearby Friends

Real-Time Location System Design

Overview

Open the app and a small list appears: which of my friends are near me right now — within ~5 km — and it updates live as they (and I) move around. A friend two blocks away pops onto the list; another drives off and drops away a minute later. That live, mutual, moving list is the feature we're designing.

The shape is different from the two nearby-things problems it superficially resembles. Yelp is static proximity search: the businesses never move, so you build one geospatial index once and read it. Ride-sharing matches riders to drivers — two different populations, and the match is a one-time assignment. Nearby Friends is neither. Here every user is simultaneously a moving broadcaster and a moving subscriber: everyone continuously reports their location, and everyone continuously receives the locations of a specific set of other people — their friends — filtered to those who happen to be close. Nothing is static, and the "who should see this update" question is answered by the friend graph, not by a radius alone.

That makes the crux real-time fan-out over a social graph, not proximity search on its own. When you move, your new position must be pushed — within a second or two, over a persistent connection — to the handful of your friends who are both online and nearby. Multiply that by millions of people all moving at once and the hard part is the write/fan-out amplification: a firehose of tiny location updates, each of which must be routed to a small, constantly-changing set of recipients.

It's labeled Medium because the building blocks are individually familiar — a geospatial cell index (borrow the fundamentals from ride-sharing) and a pub/sub connection fleet (borrow the fan-out machinery from Facebook Live comments) — and the interview is about combining them correctly: intersecting the friend graph with nearby cells, and taming the update firehose. In this walkthrough you'll scope it, size it, model the data, design the API, draw the ingest/fan-out/subscription paths, and go deep on real-time fan-out, geospatial matching for moving entities, and scaling the firehose.

Functional requirements

• Share my location. While the feature is on, my app reports my location every few seconds so friends can see me move.
• See nearby friends, live. I see the subset of my friends currently within a radius R (~5 km), with their approximate location/distance, updating in near real time as anyone moves.
• Appear / disappear as people cross the radius. A friend who moves within R shows up within a second or two; one who moves out of R (or goes offline) drops off.
• Opt in / opt out. A user can turn location sharing off entirely (or per-friend); when off, they neither broadcast nor appear.

Out of scope (state it): the friendship system itself (we assume a friend graph exists — no friend requests, no privacy-group management beyond a simple on/off), precise turn-by-turn maps or navigation, location history / "where were you last Tuesday" (we keep only current location on the hot path), and place check-ins / geofenced notifications (touched in Extensions). Naming these keeps the interview on the moving-broadcaster core.

Non-functional requirements

• Real-time, low-latency updates. A friend's movement should reflect on my screen within ~1–2 seconds — target < 2 s p99. A location that's 30 seconds stale makes "nearby" wrong.
• High write throughput (the firehose). Millions of users each posting a tiny location update every few seconds is the dominant load — on the order of a million writes/sec. The ingest path must absorb it cheaply.
• Fan-out over the friend graph. Each update goes not to everyone nearby, but to the intersection of my friends and people near me who are online. The routing must exploit that the recipient set is small and specific.
• Availability and graceful staleness over strong consistency. A friend's dot lagging by a second, or a just-crossed-the-radius friend appearing a beat late, is fine. An error page or frozen list is not. Locations are approximate and disposable by nature.
• Battery and bandwidth friendliness. The client is a phone. Update frequency must adapt (a stationary user shouldn't ping every 2 seconds), because the naive "always ping fast" both drains batteries and inflates the firehose.

Estimations

State assumptions; the goal is to justify the in-memory location store, the graph-aware fan-out, and adaptive update rates — not to be exact.

Rounded assumptions

• Users with the feature enabled and online concurrently at peak: ~10M.
• Each online user posts a location update every ~10 seconds on average (adaptive — faster when moving, slower when still).
• Location updates/sec ≈ 10M ÷ 10 = ~1M updates/sec sustained — the dominant write load.
• Average friends per user: ~200, of whom only a fraction are online and nearby at any moment — say ~5–10 friends are within R and online for a typical user.
• Fan-out amplification is the number to watch. If we naively pushed every update to all of a user's friends (worst case, every friend online): 1M updates/sec × 200 friends = 2×10^8 = ~200M pushes/sec. Filtering to nearby + online friends (~5–10) collapses that to 1M × ~8 ≈ ~8M pushes/sec — ~25× smaller, and the whole reason the geo filter must happen before fan-out, not after.

How the numbers affect the design

Storage

• A user's current location is tiny: user id (8 bytes), lat+lng (16 bytes), timestamp (8 bytes), cell id + small metadata ≈ ~40 bytes. For 10M online users that's ~400 MB of hot location state — it fits in memory across a sharded fleet. The pressure is not size; it's the ~1M/sec update rate.
• The friend graph is durable and comparatively static: ~200 edges/user, a few billion edges globally, stored once and read to resolve "who are my friends." It changes rarely relative to location updates.
• We do not store location history on the hot path. If a product wants "last seen," sample it far more coarsely into a durable side store — never per ping.

Core entities / data model

Two very different stores, as in ride-sharing:

• The location store + cell index are the hot write path: an in-memory key-value map keyed by user_id (and a derived geo_cell → users index over it), updated ~1M times/sec, last-write-wins, disposable. On a restart it refills within seconds as clients re-ping — losing it costs nothing permanent.
• The durable Friendship graph is the authoritative, slow-changing store (Postgres/a graph store, sharded by user_id). It's read on the fan-out path to answer "who are this user's friends," and it must not lose writes — but it isn't in the per-ping hot path.

The connection registry (user_id → gateway_id) is what makes fan-out targeted: unlike Live comments, where the registry is video → gateways for a broadcast channel, here delivery is to specific people, so we need a per-user routing map — the same shape WhatsApp uses, and exactly the contrast Live comments calls out.

API design

Three groups: the client streaming its own location up (the firehose), the client receiving nearby-friend updates pushed down, and a pull fallback for the current snapshot. We label the payload Body: and the response Returns:.

Post my location (high frequency)

POST /api/location            (usually sent over the WebSocket below, not a fresh HTTP call)
Body: { "lat": ..., "lng": ..., "moving": true }
200 OK
Returns: { "ok": true }

Sent every ~2–30 seconds depending on movement (adaptive — deep dive 3). It's the firehose: tiny, frequent, best-effort. The server overwrites the user's current location (last-write-wins), re-buckets them in the cell index if their cell changed, and triggers fan-out to nearby online friends. A dropped update is harmless; the next arrives shortly. In practice this rides a persistent connection rather than a fresh HTTP request per ping, to avoid per-ping connection overhead.

Real-time channel (receive nearby-friend updates)

Channel: WebSocket  wss://nf.example.com/connect?token=...
  authenticates, then both posts this user's location AND receives friends' updates

Server → client messages (pushed):
  { "type": "friend_nearby",  "friend_id": "...", "lat": ..., "lng": ..., "distance_km": 1.8 }
  { "type": "friend_moved",   "friend_id": "...", "lat": ..., "lng": ..., "distance_km": 3.1 }
  { "type": "friend_left",    "friend_id": "..." }   // moved out of R or went offline

The client opens one WebSocket and keeps it open. It posts its own location and receives friends' movements on the same socket — one auth, one reconnect path (the same single-connection argument Live comments makes). The server pushes only relevant events: a friend entering R (friend_nearby), moving while inside R (friend_moved), or leaving (friend_left).

Get nearby friends (snapshot / fallback)

GET /api/nearby
200 OK
Returns: { "friends": [ { "friend_id": "...", "lat": ..., "lng": ..., "distance_km": 1.8, "updated_at": ... }, ... ] }

A pull endpoint returning the current nearby-friend list — used on app open and after a reconnect to seed the list before live updates resume. It reads the in-memory location store, never a durable scan.

High-level architecture

Three flows matter and have different shapes: a location ingest path (the write firehose), a fan-out / subscription path (route each update to nearby online friends), and a client experience path (opening the app, a friend coming online/into range). Shared cast:

• Gateway servers (connection layer). Hold the long-lived WebSocket connections (~100K–1M each), receive each client's location posts, and push friends' updates down. Geo-distributed so a phone connects to a nearby edge.
• Location ingest service + in-memory location store + cell index. Absorbs the firehose, overwrites current location (last-write-wins), and keeps the geo_cell → users index current.
• Fan-out service. For each update, resolves the poster's friends, filters to those online and nearby, and publishes the update to the gateways holding those friends.
• Friend graph store. Durable, authoritative user → friends, read on the fan-out path.
• Connection registry. user_id → gateway_id, so an update can be routed to the exact gateways holding the relevant friends.

1. Location ingest path

A user moves; their app posts a new position, and the system absorbs it cheaply in memory and keeps the cell index current.

flowchart LR
    Client[User app] -->|"location update (every ~2-30s)"| GW[Gateway]
    GW -->|"forward"| Ingest[Location Ingest Service]
    Ingest -->|"overwrite current loc (last-write-wins)"| Loc[(Location Store - in-memory, sharded by region)]
    Ingest -->|"re-bucket if cell changed"| Cell[(Cell Index - geo_cell to users)]
    Ingest -->|"notify: this user moved"| Fan[Fan-out Service]

1. The client posts its position over its WebSocket to a gateway.
2. The ingest service overwrites the user's current location in the in-memory store (old positions are worthless).
3. It recomputes the user's geo_cell; if it differs from the stored one, it removes the user from the old cell bucket and inserts them into the new one (deep dive 2). Most updates stay in the same cell, so the common case is a cheap coordinate overwrite.
4. It hands the update to the fan-out service to route to nearby online friends.

2. Fan-out / subscription path

The interesting flow: one location update must reach the poster's friends who are both online and nearby — a small, specific set — and nobody else.

flowchart LR
    Fan[Fan-out Service] -->|"who are my friends?"| Graph[(Friend Graph - durable)]
    Fan -->|"which of them are near me?"| Cell[(Cell Index)]
    Fan -->|"which are online + where?"| Reg[(Connection Registry)]
    Fan -->|"publish to gateways holding those friends"| GWs[Gateways]
    GWs -->|"push friend_moved / friend_nearby"| Friends[Nearby online friends]

1. The fan-out service resolves the poster's friends from the durable graph (cached hot — the graph changes rarely).
2. It intersects that set with the users currently in the poster's cell and its neighbors (from the cell index) — the nearby friends — and checks the connection registry for which are online.
3. For each surviving friend, it looks up the gateway holding that friend's connection and publishes the update there.
4. Each gateway pushes a friend_moved (or friend_nearby on first entry into R) down that friend's socket. The million-way amplification never happens in one place — it's a handful of targeted publishes per update.

3. Client experience path (app open / friend comes into range)

flowchart LR
    User[User opens app] -->|"connect + auth"| GW[Gateway]
    GW -->|"register user to gateway"| Reg[(Connection Registry)]
    GW -->|"GET nearby snapshot"| Snap[Nearby Query]
    Snap -->|"friends in my cells, within R"| GW
    GW -->|"seed list, then live updates"| User

1. The app connects to a nearby gateway; the gateway registers user → this gateway so friends' updates can be routed here, and so this user's own updates can be fanned out.
2. The gateway resolves an initial nearby snapshot — the user's friends currently within R — and seeds the list so the screen isn't blank.
3. From then on, the user receives live friend_nearby / friend_moved / friend_left events. A friend crossing into R triggers friend_nearby on the mover's next update; a friend going offline (connection dropped from the registry) triggers friend_left.

4. Combined architecture

flowchart LR
    App[User apps] -->|"location updates"| GW[Gateways]
    GW -->|"overwrite loc"| Ingest[Location Ingest]
    Ingest -->|"last-write-wins"| Loc[(Location Store - in-memory, sharded)]
    Ingest -->|"re-bucket"| Cell[(Cell Index)]
    Ingest -->|"moved"| Fan[Fan-out Service]
    Fan -->|"friends"| Graph[(Friend Graph - durable)]
    Fan -->|"nearby?"| Cell
    Fan -->|"online + gateway?"| Reg[(Connection Registry)]
    Fan -->|"publish to relevant gateways"| GW
    GW -->|"push friend updates"| App

The shape to notice: the in-memory core (location store + cell index) absorbs the firehose and answers "who's near X," the durable friend graph supplies the recipient set, and the connection registry turns "these friends" into "these gateways." The fan-out service is the bridge: it delivers to only O(nearby online friends) per update (~5–10 pushes, never O(everyone in the region)), though computing that set costs O(friends) — intersecting the cached friend list against the cell index. That's a handful of in-memory reads, cheap but not literally zero.

Deep dives

1. Real-time location ingest and fan-out over the friend graph

This is the defining problem: ~1M tiny updates/sec, each of which must be pushed within a second or two to a specific, small, constantly-changing set of recipients — the poster's online, nearby friends. Two sub-problems: absorbing the writes, and routing the fan-out.

Absorbing the writes follows one observation, exactly as in ride-sharing: you only ever need each user's current location. So keep it in an in-memory store keyed by user_id, last-write-wins — a new update overwrites the old, no append, no log. The data is disposable (a restart refills from the next round of pings), which is what lets a single shard sustain its slice of the 1M/sec without per-write disk durability.

Routing the fan-out is where Nearby Friends diverges from both its cousins. The recipient set is friends(me) ∩ nearby(me) ∩ online. How you assemble that set is the whole ballgame:

flowchart LR
    Upd[My location update] --> Friends["friends(me) - from cached graph"]
    Friends --> Near["intersect with users in my cells - nearby"]
    Near --> Online["keep those with a live connection - online"]
    Online --> Route["route to their gateways - targeted push"]
    Route --> Deliver["~5-10 pushes, not 200"]
    style Route fill:#dcfce7,stroke:#16a34a,color:#14532d

Symmetry: entering and leaving the radius. Because everyone moves, membership churns constantly. When my update puts me within R of friend F for the first time, F should get a friend_nearby (appear) event; when I move beyond R, F should get friend_left (disappear). The clean way: the fan-out service knows the previous cell/distance and the new one, and emits the transition.

Crucially the transition is reciprocal. The same update that tells F "I appeared" must also tell me that F is now nearby — otherwise, if I walk toward a stationary friend who only pings every ~30 s (adaptive frequency, below), they wouldn't surface on my screen until their next slow ping, blowing the < 2 s target. This is free: the fan-out already computed friends(me) ∩ nearby for my update, so it has my newly-nearby (and newly-left) friends in hand — deliver those deltas back to me in the same step, not just outward to them.

Going offline is the other exit — when a connection drops, the registry entry is removed. Setting a TTL on the in-memory location key gives this cheaply: a user whose app died stops pinging, their entry expires, and a reaper emits friend_left to their nearby friends — the same stale-entry trick ride-sharing uses to drop dead drivers.

2. Geospatial matching for moving entities

"Which of my friends are within R?" is a proximity query, but with a twist Yelp never faces: the points move constantly, so the index isn't built once — it's re-maintained ~1M times/sec. The core index is the same one ride-sharing develops in depth, so we borrow it rather than re-derive it: divide the world into cells, bucket each user into their cell, and answer "near point X" by reading X's cell and its neighbors.

Cells and neighbors. Tag each user with a geohash (or an S2/H3 cell id) whose cell size is ≥ R, so the query point's cell plus its 8 neighbors fully cover the radius. "Friends within R of me" then becomes:

1. Compute my cell (size >= R, e.g. a ~5 km geohash cell for R = 5 km).
2. Gather users in my cell + its 8 neighbors  -> everyone nearby (all users, not just friends).
3. Intersect that set with friends(me)         -> nearby friends.
4. Exact haversine distance < R                -> trim the corners of the 9-cell block to the true circle.

The friend-graph intersection (step 3) is the piece Yelp and ride-sharing don't have: nearby-anyone is not the answer; nearby-and-a-friend is. Two ways to order the intersection, and the better one depends on which set is smaller:

• If a user has few friends relative to the cell population (a crowded downtown cell with thousands of strangers), start from friends and check each friend's current cell/distance — O(friends).
• If the cell is sparse (few people around), start from the cell occupants and intersect with the friend set — O(nearby users).

In practice, resolving from the friend side is usually cheaper and is also how fan-out works (you already have friends(me) in hand), so the common implementation checks each friend's stored location rather than scanning a dense cell.

Re-bucketing as users cross cells. This is the moving-entity cost Yelp never pays. On each update, recompute the user's cell; if it changed, delete them from the old bucket and insert into the new one — one delete + one insert. Most updates keep the user in the same cell (people don't cross a 5 km boundary every 10 seconds), so re-bucketing is a rare event and the common path is just the coordinate overwrite.

flowchart LR
    Upd[User moves] --> Same{"new cell == old cell?"}
    Same -->|"yes (common)"| Cheap["just overwrite coords - no index change"]
    Same -->|"no (crossed a boundary)"| Move["remove from old cell + add to new cell"]
    Move --> Trans["may fire friend_nearby / friend_left transitions"]

3. Scaling the update firehose

The firehose is ~1M updates/sec of moving points across a global, battery-powered client fleet. Four levers keep it affordable.

Adaptive update frequency (the biggest lever). A stationary user's location doesn't change, so pinging every 2 seconds is pure waste — of battery and of firehose capacity. Have the client adapt its rate to movement:

Connection management across a gateway fleet. 10M concurrent WebSockets live on a geo-distributed fleet of gateways (~100K–1M each), exactly the connection layer Live comments details — reuse it. Load-balance new connections by connection count (they're long-lived), keep the user → gateway registry in a fast shared store (Redis), and on reconnect re-seed the client with a fresh nearby snapshot (the equivalent of Live comments' backfill). Because locations are ephemeral, a dropped connection is cheap: the user simply stops appearing to friends until they reconnect and re-ping — no durable per-message recovery needed.

Sharding by geography. No single node holds every user or takes every update. Partition the location store and cell index by region (city/metro), so London's load lives on London's shards and a busy city can't starve a quiet one. A query or fan-out near a region boundary hits the owning shard and the adjacent one(s), then merges — rare, since most users are interior to a region. Fan-out mostly stays within a shard, because nearby friends are, by definition, in nearby cells on the same shard.

Staleness, battery, and privacy tradeoffs. Every knob trades freshness against cost:

• Update interval vs freshness: slower pings save battery and firehose but make friends' dots staler. Adaptive frequency gets the best of both by spending updates only on movers.
• Location precision vs privacy: you can deliberately coarsen a friend's reported position (snap to ~100 m, or show "1.8 km away" rather than an exact pin) — cheaper to transmit and more privacy-preserving, which for a friends product is often desirable, not a compromise.
• TTL vs flapping: a short location TTL drops crashed clients quickly but risks flapping a friend off/on across a brief signal loss; a slightly longer TTL (a few ping intervals) smooths that at the cost of showing a just-disconnected friend for a few extra seconds.

Tradeoffs & bottlenecks

• In-memory location vs durability. Current location in memory with last-write-wins is what makes ~1M updates/sec affordable, but the store isn't a rebuildable source of truth — a restart loses in-flight positions and relies on the next pings. That's the right trade because the durable friend graph, which does matter, is off the hot path.
• Filter-before-fan-out vs push-then-filter. Filtering to nearby + online friends server-side (~5–10 recipients) beats broadcasting to all ~200 and filtering on the client (~25× the firehose and battery). The cost is a graph read + cell lookup per update, which is why both must be in-memory-fast.
• Fixed grid vs adaptive index. For constantly-moving points a fixed geohash/S2/H3 grid avoids the split/merge rebalancing a quadtree pays under high write churn. The trade is fixed-resolution cells (too coarse in dense cities), mitigated by finer resolution per region — see ride-sharing.
• Adaptive vs fixed update frequency. Movement-adaptive pings slash battery and firehose cost but add a slow-interval of lag when a stationary user starts moving (mitigated by an immediate ping on movement onset).
• Targeted vs broadcast fan-out. A per-user user → gateway registry enables precise delivery to specific friends but is larger and churnier than Live comments' video → gateways broadcast map. The friend-graph product genuinely needs targeted routing; a broadcast map can't express "only these people."
• Freshness vs privacy vs cost. Coarsening reported location (snap to ~100 m, distance-only) is simultaneously cheaper to transmit and more private — a rare case where the cost-saving and the user-protecting choice coincide.
• Hot dense regions. A stadium or festival makes one region's shard hot (many users, many mutual friends, heavy fan-out). Handle it by sub-sharding the region and capping/ranking fan-out for users with huge nearby-friend counts.

Extensions if asked

Add only the extension that changes the design discussion. (These are standalone topics with no dedicated guide yet.)

• Geofenced friend notifications. "Tell me when a friend arrives near a place I care about" — evaluate the poster's new cell against saved geofences on the fan-out path, a small extra check off the same update stream.
• Location history / "last seen." Sample each user's position coarsely (every few minutes, or on significant movement) into a durable time-series store — deliberately not per ping, and off the hot path, exactly like ride-sharing's sampled trip route.
• Per-friend and group sharing controls. Extend sharing_enabled from a global toggle to per-friend or per-group visibility, filtering the fan-out recipient set — a graph/ACL enrichment, not a change to the core loop.
• Place check-ins and "who's here." Reuse the cell index for "which of my friends are at this venue," turning proximity-to-me into proximity-to-a-place — the same query with a fixed query point.
• ETA / directions to a nearby friend. Layer a routing service for "how far / how long to reach this friend," using real road-network distance instead of straight-line — a separate maps subsystem, out of the core scope.

What interviewers look for & common mistakes

What interviewers usually reward:

• Recognizing the shape — every user is a moving broadcaster and subscriber, and the recipient of each update is the friend graph intersected with proximity and online status, not a region broadcast (contrast static Yelp and rider↔driver ride-sharing).
• A write-optimized in-memory location path — last-write-wins, no durable per-ping persistence, sharded by region.
• Filter-before-fan-out — computing nearby + online friends server-side so each update produces ~5–10 targeted pushes, not ~200 broadcast-and-discarded ones.
• A fixed-grid geospatial index for moving points — geohash/S2/H3 with neighbor-cell coverage and cheap re-bucketing, and not a quadtree (rebalancing cost under write churn) — borrowing the fundamentals from ride-sharing.
• Targeted push over a connection fleet — a user → gateway registry and per-friend routing, reusing the connection machinery from Live comments but with the opposite (targeted, not broadcast) fan-out.
• Adaptive update frequency — slowing pings when stationary to protect battery and shrink the firehose.

Before you finish, do a quick mistake check:

• Did you keep current location in memory (last-write-wins) and avoid durably storing every update?
• Did you filter to nearby + online friends before fan-out, instead of broadcasting to all friends?
• Did you use a fixed-grid geospatial index and handle neighbor cells + re-bucketing as users move?
• Did you intersect the friend graph with nearby cells, rather than returning nearby strangers?
• Did you route updates to specific friends via a user → gateway registry, not a region broadcast?
• Did you make update frequency adaptive to movement for battery and firehose reasons?
• Did you handle a friend entering R (appear), leaving R, and going offline (disappear via TTL)?