Design Yelp / Proximity Service

Design Yelp / Proximity Service

The naive answer feels bulletproof: "I've got the user's location, I've got a places table with a lat and lng column — to find everything within 5 km I just compute the distance from the user to every place and keep the ones under 5 km." That sentence is the trap, and it fails on the very first metric that matters. With 500 million places, one radius query does 500 million haversine computations; at a generous ~10 ns each that's ~5 seconds per query — before you've served a second user. At Yelp's ~100K queries/sec that's 5×10¹³ distance calculations per second, a workload no fleet answers in real time. Your instinct is "add an index," but the 2D range query WHERE lat BETWEEN x-d AND x+d AND lng BETWEEN y-d AND y+d can't be served by a single B-tree: the latitude index returns a thin band that wraps the whole planet, the longitude index returns another planet-spanning band, and the engine has to intersect two enormous ID lists to keep the tiny box where they cross. You paid to read two continents to answer a question about one neighborhood. This lab derives the geospatial index that turns "measure distance to everything" into "measure distance to the ~1,000 things that could possibly be close."

Scope it like a senior (ask before you design)

Proximity search hides a dozen forks, and each one changes the index you'd pick. Pin these down before drawing a box:

• Radius search or top-K nearest? "All restaurants within 2 km" is a fixed-radius scan; "the 20 closest coffee shops" is a k-nearest query that grows its radius until it has K. The index must support the one you're actually asked for (k-NN needs the cells chained so you can walk outward).
• Static places or moving objects? Restaurants essentially never move — the index can be treated as near-static and rebuilt lazily. Nearby friends or drivers move every few seconds, and re-indexing millions of moving points per second is a completely different design (see the moving-objects drill in Defend). State which one.
• Read:write ratio? Yelp is overwhelmingly read-heavy (reads ≫ writes) — a place is written once and searched millions of times. That justifies an in-RAM read-optimized index that's expensive to rebuild but cheap to query.
• Density skew — cities vs rural? This is the whole ballgame. Places are wildly non-uniform: a 5 km cell over downtown San Francisco holds tens of thousands of restaurants; the same cell over the Pacific holds zero. Any design with a fixed cell size gets its worst-case latency from its densest cell — exactly where traffic is heaviest.
• Filters & ranking? Do results filter by category (restaurant/bar) and rating, and sort by distance or by popularity? Filtering shrinks the candidate set after the spatial cut; ranking by popularity means a precomputed score, refreshed off-peak, not on every review.
• Scale & growth? How many places, what QPS, what growth rate? (Drives whether the index fits one box or must be sharded, and how.)

Assume for this lab: 500M places (restaurants, shops, theaters), 100K queries/sec, growing ~20%/yr; fixed-radius and top-K nearest both wanted; places are near-static; reads ≫ writes; results filter by category and sort by distance or precomputed popularity; global coverage with extreme urban/rural density skew. This is Yelp; the moving-objects variant (nearby drivers/friends) is scoped as an explicit extension.

Reason to the design (derive it, don't recite it)

The one move behind every good answer: shrink the candidate set before you measure distance. Every design below is that same move done with progressively smarter cells.

Attempt 1 — SQL bounding box on two B-tree indexes. Store lat/lng, index each, select the box. As shown in The Trap, the two indexes are independent: each returns a planet-spanning strip, and you intersect two huge ID lists to find the small box where they overlap. Latency scales with the band size, not the answer size. It's also subtly incorrect: a fixed degree-delta isn't a fixed distance — one degree of longitude is ~111 km at the equator but shrinks to 0 at the poles, so a square-degree box over-selects near the equator and under-selects near the poles. Lesson carried forward: use lat/lng boxes only to nominate candidates, then always finish with a true spherical (haversine) distance.

Attempt 2 — a uniform grid. Chop the map into fixed cells, stamp each place with its GridID, and keep an in-RAM hash map GridID → list<LocationID>. Now finding a point's cell is pure arithmetic (no search), and a radius query touches only the containing cell plus its 8 neighbors. Size the cell to the query radius and you've turned a 500M-row scan into a 9-cell lookup. This is a real improvement — but it dies on the density question from Scope It. A cell sized for a 5 km search holds a handful of places over the ocean and tens of thousands downtown. Every query that lands in a dense cell scans a monster list, so your p99 latency is set by your single densest cell — precisely where the users are. Fixed cells can't win when the data is skewed, and real geography is always skewed.

Attempt 3 — make the cell size follow the data (the key insight). The fix is an adaptive spatial index: spend many tiny cells where places are dense and one giant cell where they're sparse, so every cell holds roughly the same bounded number of places. Three production-proven ways to get adaptive (or near-uniform) cells:

• Quadtree — cap a cell at, say, 500 places; when it overflows, split it into 4 equal quadrants and redistribute. Dense downtown becomes a deep pile of tiny leaves; open ocean stays one big leaf. Every leaf holds ≤500 places by construction, so worst-case scan cost is bounded everywhere. This is the natural fit for Yelp's static, skewed, RAM-resident data.
• Geohash — interleave the bits of lat and lng into one number, base-32 encode it into a string; a shared string prefix means spatial proximity, and the prefix length is the cell precision. It's not adaptive (precision is fixed per query), but it needs no tree to build/maintain and drops straight into an off-the-shelf store (Redis GEOSEARCH, or an Elasticsearch geo field). The prefix doubles as a natural shard key.
• S2 (Google) / H3 (Uber) — hierarchical cells on the sphere (S2 = a Hilbert curve over cube faces; H3 = hexagons). No lat/lng distortion, near-uniform cell areas, and clean equidistant neighbors — which is exactly what you want once objects move on a globe (ride-sharing). More concepts and a library dependency, but the cleanest neighbor math.

The query, in every variant, is the same two-phase shape: (1) compute the covering cells for the query circle and pull their candidate LocationIDs; (2) fetch those rows and apply the true haversine distance + category filter + ranking. The spatial index shrinks 500M to ~1,000; haversine turns ~1,000 candidates into the exact answer. We build the quadtree as the primary design and keep geohash/S2 as the named alternatives in the trade-off table.

Build it — the design worksheet

This is the artifact you'd produce on a whiteboard in a 45-minute round. Work it in order; every number below is traced, not asserted — recompute them before an interview.

1. Requirements

• Functional: addPlace / updatePlace / deletePlace; search(lat, lng, radius, category?) → places within the radius, filtered by category, sorted by distance or popularity; nearestK(lat, lng, k); add reviews (text, rating, photos).
• Non-functional: real-time search latency (tens of ms); overwhelmingly read-heavy; places near-static (index can lag writes by seconds); high availability for reads (a stale index is fine, a down index is not); horizontally scalable as places and QPS grow ~20%/yr.
• Out of scope for this lab: continuously moving objects (nearby drivers/friends) — called out as the escalation in Defend.

2. Back-of-envelope estimation (BOTE)

• The cost we're killing: full scan = 500M haversines/query. At ~10 ns each → ~5 s/query; at 100K QPS → 5×10¹³ distance calcs/s. Non-starter — this is why we index.
• Row store: a Place row ≈ LocationID (8B) + Name (256B) + Lat (8B) + Lng (8B) + Description (512B) + Category (1B) ≈ ~793 bytes. 500M × 793B ≈ ~400 GB on disk (reviews/photos live in separate tables keyed by LocationID). This is the source of truth; the interesting object is the tiny spatial index on top.
• Uniform-grid index (the baseline we reject): size cells to a 10-mile (~16 km) search → 100 sq mi cells. Land is ~200M sq mi → 200M ÷ 100 ≈ 2M grid cells (note: a 10-mile cell is 10×10 = 100 sq mi, not 10 — the widely-copied "20M grids" figure forgets to square the side). Grid keys: 4B × 2M = 8 MB. LocationIDs: 8B × 500M = 4 GB. Total ≈4 GB — dominated by the location IDs, not the keys.
• Quadtree index (the design): cap 500 places/leaf → 500M ÷ 500 = 1M leaves; internal nodes ≈ ⅓ of leaves ≈ 333K; internal pointers = 333K × 4 × 8B ≈ ~10 MB (a rounding error). Cache per place = ID + lat + lng = 24B → 24B × 500M = 12 GB. Total ≈12 GB — fits in RAM on one modern server. That's the counter-intuitive punchline: a planet-scale spatial index is small; the hard problems are fan-out, rebuild, and skew, not capacity.
• Geohash sizing (the alternative), traced: each geohash char = 5 bits, so precision p gives 32^p global cells. Precision 5 ≈ 4.9 km × 4.9 km cells (32⁵ ≈ 33.5M cells globally). For a radius ≤ 4.9 km query, scan the 3×3 = 9-cell block (center + 8 neighbors) — that's what guarantees no boundary miss (see Break It). Index = geohash-cell → list<LocationID>: 8B × 500M = 4 GB of IDs + ~0.27 GB for ≤33.5M 8-byte cell keys ≈ ~4.3 GB — same ballpark as the grid, and the same reason (IDs dominate).
• Places per cell & per query: if ~10M cells are actually populated (land with places), average = 500M ÷ 10M = 50 places/cell, so a 9-cell radius query nominates ~450 candidates — vs 500,000,000 for a full scan. In a dense downtown cell that average is thousands; that skew is exactly what the quadtree fixes by capping the leaf.

3. API sketch

POST /places
     body: { name, lat, lng, category, description }
     -> 201 { location_id }

GET  /search?lat=..&lng=..&radius_m=..&category=..&sort=distance|popularity&limit=20
     -> 200 [ { location_id, name, category, distance_m, rating }, ... ]   // sorted, filtered

GET  /nearest?lat=..&lng=..&k=20&category=..
     -> 200 [ ... ]   // grows radius until k results or max radius

PATCH  /places/{id}      -> 200   (async re-index)
DELETE /places/{id}      -> 204   (async de-index)

4. Data model & partitioning

• places (source of truth): location_id (PK), name, lat, lng, category, description, popularity_score, created_at. Sharded by hash(location_id) — every place fetch is a single-key lookup. ~400 GB, on disk, replicated.
• Spatial index (in-RAM, rebuildable cache, NOT the source of truth): cell → list<LocationID> (quadtree leaves or geohash cells). ~12 GB. If a node dies you rebuild it from the row store.
• Partitioning the index — two real choices, a genuine trade-off:
  • Shard by region (e.g. geohash prefix / ZIP): all places in a region on one server; a query hits exactly one server (no fan-out). But load mirrors geography → a popular region (downtown, a festival) becomes a hot shard, and regions grow unevenly so balance drifts. Good when traffic is geographically even and locality is valuable.
  • Shard by hash(LocationID): dense areas spread evenly, no hotspots. But a place's neighbors now scatter across all shards, so every radius query is a scatter-gather → fan out to all shards, each returns its local matches, an aggregator merges + haversine-ranks. You trade hot-shard risk for fan-out latency on every read. This is the usual choice at 100K QPS.
• Fast rebuild: keep a reverse index (shard# → set<(LocationID, lat, lng)>) so a fresh index server asks for exactly its places and rebuilds in seconds — instead of scanning 500M rows while serving nothing. Replicate that index too.

5. High-level architecture

The write path (blue) records a place in the source-of-truth store, which asynchronously updates the in-RAM spatial index. The read path (green) computes the covering cells, gathers candidate LocationIDs (scatter-gather across index shards), fetches the rows, and finishes with the true haversine filter + rank. A hot-query cache absorbs repeated popular searches; a reverse index makes a dead shard rebuild in seconds (amber = async/recovery).

6. Rubric — what a strong answer hits

• States the scale + the killer BOTE (500M haversines/query, 5×10¹³/s at full scan) before drawing boxes, and names the one move: shrink the candidate set before measuring distance.
• Rejects the SQL 2D-range box for the right reason (two independent B-trees → intersect two planet-spanning bands), and rejects the uniform grid for density skew — not vibes.
• Lands on an adaptive/near-uniform index (quadtree / geohash / S2) and can say why each and when to pick it.
• Handles the cell-boundary problem explicitly (scan all covering cells, never a single cell) and finishes with true haversine, not the lat/lng box.
• Picks a partitioning scheme (region vs hash) as a stated trade-off (hot shard vs scatter-gather), and names the reverse index for fast rebuild.
• Can defend every trade-off-table row with "buys X, costs Y, use when Z."
• Model-answer reading: check your worksheet against the guide's full treatment, Designing Yelp or Nearby Friends, and the building blocks it leans on: Geohashing and Quadtrees, Building Blocks II — Geospatial Indexing (Geohash/S2/H3), Data Sharding Techniques, and Consistent Hashing.

Break it — three traced failures

1. The density hotspot — a fixed cell over downtown holds 100K places. Take the uniform grid (or a fixed geohash precision) sized to a 5 km search. Averaged over ~10M populated cells, a cell holds ~50 places and a 9-cell query nominates ~450 candidates — instant. But a single geohash-precision-5 cell (~4.9 km × 4.9 km ≈ 24 km²) laid over downtown San Francisco can hold tens of thousands of restaurants; over Manhattan, more. Now a query landing there does a haversine against 100K candidates, and because that's the densest cell it's also where the most users are searching — your p99 is set by your worst cell under peak load. This is the reason fixed cells lose: the average looks great and the tail is catastrophic. The quadtree fixes it structurally — the 500-place cap means that downtown cell has already split into a deep pile of tiny leaves, so every leaf scan is ≤500 regardless of density. Adaptive resolution isn't a nicety; it's what bounds the tail.

2. The cell-boundary problem — the nearest place is just across the edge. The tempting optimization: compute the query point's single cell and return that cell's places. It's wrong, and silently so. A place sitting a few meters on the other side of the cell boundary is well inside your 5 km radius but lives in the neighbor cell — a single-cell answer drops it, and every query near an edge quietly under-returns. The fix is non-negotiable: scan every cell the query circle overlaps — for a radius ≤ cell-size that's the 3×3 = 9-cell block (center + 8 neighbors); for a quadtree, recurse from the root and prune only subtrees whose bounding box cannot intersect the circle. Then haversine-filter the union. The boundary bug never shows up in a happy-path demo (the nearest place happened to be in-cell); it shows up as "why does Yelp miss the taqueria across the street?" in production.

3. Moving objects — re-indexing cost thrashes the tree. The whole design leans on near-static places, so the index is a rebuildable read cache updated lazily. Point it at nearby friends or drivers and the assumption collapses: with, say, 10M users each emitting a location every 4 s, that's ~2.5M index mutations/sec. In a quadtree each move is a delete-from-old-leaf + insert-into-new-leaf, and a burst into a dense area triggers cascading splits — the tree spends all its time re-balancing and search throughput craters. Two escapes: (a) don't index individual moves at all — hold live positions in an in-memory geohash/S2 bucket keyed by cell and let clients push updates (Uber's approach: a driver's cell membership changes only when they cross a cell edge, not every ping); (b) accept staleness and batch. The lesson: an index tuned for static, read-heavy data is the wrong tool for a write-heavy moving-object workload — that's a different system (see the Uber escalation in Defend).

Optimise — with trade-offs

Bottlenecks worth naming out loud: (1) fan-out latency — with hash sharding every query scatters to all index shards; the aggregator waits for the slowest, so a single straggler shard sets tail latency (mitigate with hedged requests / a shard timeout that returns partial results). (2) rebuild coverage gap — a dead index shard serves nothing until rebuilt; the reverse index turns a minutes-long full-table rescan into a seconds-long targeted refill. (3) hot-query concentration — "restaurants near Times Square" repeats constantly; a short-TTL result cache keyed on (rounded cell, category) absorbs it cheaply since places are near-static.

Decision	Option A	Option B	Pick when
Cell scheme	Uniform grid (fixed cells)	Adaptive index (quadtree) / near-uniform (S2/H3)	Uniform grid only for near-uniform data or a quick prototype — it's dead simple and trivially shardable. Adaptive/near-uniform for real geography: density skew makes fixed cells blow up the tail (Break It #1). Yelp → quadtree.
Fixed vs adaptive cell size	Fixed precision (geohash length chosen per query)	Adaptive (quadtree 500-cap)	Fixed precision when you want zero tree maintenance and can tolerate uneven per-cell cost (and lean on an existing store). Adaptive when bounded worst-case scan matters more than operational simplicity — it guarantees ≤cap places/leaf everywhere.
Index build timing	Precompute in-RAM index (build once, rebuild on change)	On-query spatial computation (PostGIS ST_DWithin per request)	Precompute for read-heavy, near-static data at high QPS — you amortize build cost over millions of reads. On-query when data mutates constantly or QPS is low enough that a per-query DB spatial op is fine.
Store / engine	Custom in-RAM quadtree	Redis GEO / Elasticsearch geo / PostGIS (GiST R-tree)	Custom quadtree for max control, adaptive resolution, and lowest latency at 100K QPS — you own the code. Redis GEO (geohash under the hood) when you'd rather not run a tree and can accept fixed precision; Elasticsearch when you also need full-text + geo filters in one query; PostGIS when you need exact polygon geometry + transactions and the dataset fits one DB.
Index partitioning	Shard by region (geohash prefix)	Shard by hash(LocationID) + scatter-gather	Region sharding when traffic is geographically even and one-server-per-query locality is worth the hot-shard risk. Hash sharding (usual at scale) for even load, paying fan-out latency on every read.

Defend under drilling

Q1 — "Why not just put a B-tree on lat and another on lng and range-query the box?"
Because the two indexes are independent and neither maps to the 2D region. The lat index returns a thin band that wraps the entire planet; the lng index returns another; the engine intersects two multi-million-row ID lists to keep the little box where they cross — latency scales with the band, not the answer. And it's geometrically wrong: a fixed degree-delta is a different real distance at the equator vs the poles, so the box over/under-selects by latitude. A single spatial index (quadtree/geohash/S2) maps the 2D region to one lookup; lat/lng boxes only ever nominate candidates for a haversine finish.

Q2 — "Uniform grid or quadtree, and why?"
Quadtree, because real place density is extreme (downtown vs ocean). A uniform grid sized for the search radius holds ~50 places/cell on average but tens of thousands in a dense cell, and your p99 is set by that densest cell — exactly where traffic concentrates. The quadtree caps every leaf at ~500 places by splitting dense regions into deeper, smaller cells, so worst-case scan cost is bounded everywhere regardless of density. I pay for that with a tree to build/rebuild and more complex neighbor logic — worth it because the whole point is taming the tail, not the average.

Q3 — "How do you handle the cell-boundary edge case?"
Never answer from a single cell. The nearest place can sit a few meters across a cell edge, inside the radius but in the neighbor cell. For a grid/geohash with radius ≤ cell-size I scan the 3×3 covering block (center + 8 neighbors); for a quadtree I recurse from the root and prune only subtrees whose bounding box provably can't intersect the query circle, then haversine-filter the union. For k-nearest I chain the leaves and walk outward, growing the radius until I have k or hit a max. The single-cell shortcut passes every happy-path demo and silently under-returns near every boundary in production.

Q4 — "A place fails to appear right after it's added. Bug?"
Expected, and acceptable per the requirements. Writes go to the source-of-truth store synchronously; the in-RAM spatial index is updated asynchronously (it's a rebuildable read cache, not the SoT). So there's a seconds-scale window where a brand-new place is durable but not yet searchable. For Yelp that's fine — places are near-static and nobody needs a just-added restaurant to be searchable within 100 ms. If the product needed read-your-writes on the index, I'd dual-write or make the write path wait for index ack, trading write latency for freshness — a deliberate choice, not the default.

Q5 — "How do you rank by rating/popularity without killing search throughput?"
Precompute a popularity_score on the row and refresh it once or twice a day off-peak; the spatial phase returns candidates, and I sort the ~1,000 candidates by (distance or precomputed score) at query time. I do not mutate the tree on every review — that would thrash a read-optimized index for a signal that doesn't need to be real-time. Distance ranking is computed per query from the haversine I already need; popularity ranking rides on a batch-updated score.

Q6 (the 100× escalation) — "Now it's 50 billion places and 10M QPS — what breaks first?"
Not storage — the index scales near-linearly (50B places → ~1.2 TB of 24B entries, spread over ~100 index shards, still tiny per shard). What breaks is fan-out: hash sharding means every one of 10M QPS scatters to all ~100 shards = 10² billion sub-requests/sec, and tail latency is set by the slowest of 100 shards per query. Fixes: (a) move to region-aware sharding by geohash prefix so a query hits only the O(1) shards its covering cells map to, not all of them — trading even load for bounded fan-out; (b) a per-region read-replica tier so hot metros scale reads independently; (c) hedged requests + partial-result timeouts so one slow shard doesn't stall the query. The index-size axis is a non-event; the fan-out and hot-region axes are the real fight.

Q7 — "How would this change for moving objects (nearby drivers/friends)?"
Fundamentally — it becomes a write-heavy problem and the static-index assumption breaks (Break It #3). I stop indexing individual moves into a quadtree; instead I hold live positions in an in-memory geohash/S2 bucket keyed by cell, and a driver only changes bucket membership when they cross a cell edge, not on every GPS ping — so 2.5M pings/sec become far fewer bucket moves. S2/H3 earn their keep here because their near-uniform cells and clean equidistant neighbors make "who's in the cells around me right now" cheap and distortion-free on a globe. That's the Uber design, a different system from static Yelp — see Designing Uber — Geospatial Matching, Traced.

You can now defend

• You can compute, not assert, why "distance to every place" fails (500M haversines/query, 5×10¹³/s at 100K QPS) and state the one unifying move: shrink the candidate set before measuring distance.
• You can derive the geospatial index from first principles — SQL box → uniform grid → adaptive quadtree / geohash / S2 — and justify each transition by the failure it fixes (band-intersection, then density skew).
• You can handle the two edge cases interviewers probe — the cell-boundary miss (scan all covering cells + haversine) and the density hotspot (adaptive cap bounds the tail) — without hand-waving.
• You can defend the partitioning trade-off (region hot-shard vs hash scatter-gather), size the index (12 GB fits one box; fan-out is the real problem, not storage), and explain how the design changes for moving objects vs static places.

---

Re-authored/Deepened for this guide. Model-answer reading: Designing Yelp or Nearby Friends (System Design Problems). Building blocks: Geohashing and Quadtrees; Building Blocks II — Geospatial Indexing (Geohash/S2/H3); Data Sharding Techniques; Consistent Hashing. Escalation cross-referenced with Designing Uber — Geospatial Matching, Traced. BOTE figures recomputed and cross-checked against the model-answer page (500M places, 100K QPS, ~4 GB grid index, ~12 GB quadtree).

I just read a lesson on **Design Yelp / Proximity Service** (Hands-On Builds) and want to truly understand it. Explain Design Yelp / Proximity Service from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Design Yelp / Proximity Service** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Design Yelp / Proximity Service** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Design Yelp / Proximity Service** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.