"Show me coffee shops within 2 km." Yelp, Google Maps and every food-delivery app answer that question thousands of times a second. A normal database index can't: latitude and longitude are two numbers, and "near" is a circle, not a range. This walkthrough shows how geo indexes turn a 2-D question into a 1-D lookup, and why the index is small enough to copy everywhere.
The Yelp-style nearby-search interview end to end: radius search with filters at about 15,000 searches a second, with edits visible within minutes; 200 million businesses need only a ~10 GB geo index, so every host keeps a full in-memory copy. Deep dives show why two B-tree indexes fail, how geohash cells turn near into prefix lookups, why the search reads the user's cell plus its 8 neighbours (the cell north of tdr1y is tdr4n), and how caching by cell and a separate change-event write path keep search up.
Phase 1: Requirements (5 minutes)#
"When an owner adds a business or changes its hours, how fast must searches see it?"
"Within a few minutes is fine. Even the next day would be acceptable for a new listing."
"Then searching and editing are two different systems with very different needs: a huge read path that can be a little stale, and a tiny write path that must be correct."
- Search businesses near a point:
(lat, lng, radius)with radius from 0.5 to 20 km - Filter by category ("cafe") and "open now"; sort by distance or a mix of distance and rating
- Page through results, 20 at a time
- View a business's details page
- Owners add, edit and remove their businesses
- Out of scope: writing reviews, map tiles, turn-by-turn routes
- Latency: p99 under 200 ms for a search
- Read-heavy: searches outnumber business edits by orders of magnitude
- Availability: search stays up even if the business database is down
- Freshness: edits visible within minutes
- Privacy: don't store users' precise locations longer than the request needs
Phase 2: Estimation (5 minutes)#
- Daily active users: 100M, each running 5 searches a day
- Searches: 500M/day ÷ 86,400 s ≈ 5,800/s on average, peak ~2.5x ≈ 15,000/s
- Businesses: 200M, each with a ~1 KB record (name, address, hours, category, rating): ~200 GB in the business database
- Geo index entry: business ID (8 B) + lat/lng (16 B) + cell ID (8 B) ≈ 32 B
- Whole geo index: 200M × 32 B ≈ 6.4 GB, plus overhead, call it ~10 GB
- Business edits: a few thousand an hour, ~1/s: negligible
"That 10 GB is the most important number. The whole index fits in the memory of one ordinary server. So I won't shard it. I'll replicate it: every search server can hold a full copy, and I add copies for throughput and regions."
Phase 3: API (3 minutes)#
GET /v1/search/nearby?lat=12.9716&lng=77.5946&radius_m=2000&category=cafe&open_now=true&limit=20&cursor=...
→ 200 {
"results": [ { "id": "b_8812", "name": "...", "distance_m": 340, "rating": 4.6 }, ... ],
"next_cursor": "..."
}
GET /v1/businesses/b_8812 → 200 { full details }
POST /v1/businesses → 201 (owner)
PUT /v1/businesses/b_8812 → 200 (owner)The cursor encodes the last result's position so paging is stable. The search never needs the user's identity, and the location isn't written to any log at full precision.
Phase 4: High-level design (10 minutes)#
%% title: Proximity service: a read-only geo index, separate from business writes
flowchart TD
U@{ icon: "sd:phone", label: "Mobile app" }
LB@{ icon: "sd:load-balancer", label: "Load balancer" }
LBS["Location service<br/>stateless, read-only"]:::core
GI@{ icon: "sd:index", label: "Geo index · in memory<br/>cell ID → business IDs" }
BC@{ icon: "tech:redis", label: "Redis<br/>business details, hot cells" }
BS["Business service<br/>owner edits"]:::service
DB@{ icon: "tech:postgresql", label: "PostgreSQL<br/>primary + read replicas" }
CDC@{ icon: "tech:kafka", label: "Kafka · business changes" }
O@{ icon: "sd:store", label: "Business owners" }
U --> LB
LB -->|"search"| LBS
LBS --> GI
LBS --> BC
BC -->|"miss"| DB
O --> BS
BS --> DB
DB -->|"change events"| CDC
CDC -->|"update index within minutes"| GI
class U,O client
class LB edge
class GI,BC cache
class DB store
class CDC queue- Pick a precision. The location service picks the finest cell that is still at least as wide as the radius: for 500 m, geohash length 6 (about 1.2 × 0.6 km); for 2 km, length 5 (about 4.9 km).
- Find the cells. It computes the user's cell and its 8 neighbours: 9 cell IDs.
- Collect candidates. It reads the business IDs in those 9 cells from the in-memory index.
- Filter and rank. It computes the exact distance to each candidate, drops those outside the radius or the wrong category, and ranks the rest.
- Hydrate. It fetches names, ratings and hours for the top 20 from Redis (falling back to a read replica) and returns them.
The write side is deliberately boring: owners edit through the business service, which writes PostgreSQL. A change-data-capture stream carries each change to the index servers, which update their copy within minutes. A nightly full rebuild catches anything the stream missed.
Phase 5: Deep dives (15 minutes)#
Deep dive 1: Turning "near" into an index lookup#
Why not two B-tree indexes?
Put an index on lat and another on lng, and query WHERE lat BETWEEN a AND b AND lng BETWEEN c AND d. What does the database actually do with 200 million rows?
One strong answer
- Each index alone is a huge band. The latitude range of a 2 km box is a strip that circles the whole planet; the longitude range is a strip from pole to pole. Each strip holds millions of businesses.
- The database intersects two big sets. It uses one index (or both, with a bitmap merge) and filters the rest, reading far more rows than the few hundred that are actually near.
- The fix: map 2-D space to cells with IDs that sort well, so "near this point" becomes "these few cell IDs", a small number of exact or prefix lookups.
Three ways to build the cells:
Geohash
- Interleaves lat/lng bits into a base32 string; a shared prefix means a shared cell
- Fixed grid: length 5 ≈ 4.9 km, length 6 ≈ 1.2 × 0.6 km, length 7 ≈ 150 m
- Works in any key-value store or B-tree, and Redis has geo commands built on it
- Dense cities get very full cells
Quadtree
- Splits a square into 4 whenever it holds more than N businesses (say 100)
- Adapts: tiny cells downtown, huge ones over the ocean
- Built in memory at startup (minutes for 200M points)
- Updates and rebalancing are custom code
S2 / H3 cells
- Library-defined hierarchies of cells covering the sphere
- Better shapes near the poles; H3 hexagons have uniform neighbours
- What large ride-hailing and maps systems tend to use
- Another library to learn and debug
"I'll use geohash: it's a string, so it works in Redis, PostgreSQL or a plain in-memory map, and the precision table is easy to reason about in an interview. If dense cells hurt, I'd move to a quadtree or S2."
The trap every interviewer waits for is the boundary problem. Two cafés 50 metres apart can sit on opposite sides of a cell edge and share no prefix at all. In Bengaluru, the cell directly north of tdr1y is tdr4n: neighbours, yet they diverge at the fourth character. That's why the search always reads the user's cell plus its 8 neighbours, then filters by exact distance. Nine lookups cover the circle whatever cell the user is in, provided the cell is at least as wide as the radius.
If the nine cells return too few results (a rural area), drop one character of precision (cells roughly 4 to 8 times larger on each side) and search again.
Deep dive 2: Serving 15,000 searches a second#
The geo index is about 10 GB, and it changes about once a second. That shape points to one strategy: copy it, don't shard it.
1. Full copies, many replicas
Each location-service host holds the whole index in memory. Add hosts for throughput and put a set in every region near users. No cross-shard queries, no scatter-gather.
2. Cache by cell, not by user
Thousands of people search near the same station. Cache results keyed by category plus the cell at the search's precision (for example cafe:tdr1y) for a minute. Rounding the location to a cell turns millions of unique coordinates into a cacheable key, and stops the cache storing anyone's exact position.
3. Keep the ranking cheap
Exact distance (haversine) on a few hundred candidates is microseconds. Ranking mixes distance and rating; anything heavier (personalised ranking) runs on the top 100 only.
4. Freshness by stream, safety by rebuild
Change events update the index within minutes. A nightly rebuild from the database replaces each copy in turn, so a missed event can never live longer than a day.
Hot spots still matter. A geohash-5 cell over a dense downtown can hold tens of thousands of businesses, so the candidate set gets large. Either index those areas one level finer, or use a quadtree that splits busy cells automatically.
Phase 6: Trade-offs and failure modes (5 minutes)#
An index host dies
It holds only a copy. The load balancer sends traffic to the others; a replacement loads a snapshot and replays recent changes.
The business database is down
Searches keep working: the index and the details cache are in memory. Owner edits fail until it's back. The two paths are isolated on purpose.
A change event is lost
The listing is stale until the nightly rebuild. Acceptable under "minutes, ideally; a day at worst".
Results near the poles or the 180° line
Geohash cells get skinny near the poles and neighbours wrap across the antimeridian. Use a library's neighbour function rather than string arithmetic, or S2 cells.
Location privacy
Round coordinates before logging, cache by cell, and never persist the raw request location with a user ID.
| Decision | We chose | We gave up |
|---|---|---|
| Index | Geohash cells, 9-cell search | Perfect cell shapes (S2/H3) |
| Scale | Full in-memory copy per host | Index sizes beyond RAM (fine at ~10 GB) |
| Freshness | Change stream + nightly rebuild | Instant visibility of edits |
| Caching | By category + cell | Per-user personalised caching |
Go deeper in the course#
- Week 0, Part 6: Terminology and theory: index types, including geospatial R-trees, quadtrees and geohash-style cells
- Week 1, Day 2: Replication trade-offs: why a small read-mostly dataset is replicated, not partitioned
- Week 1, Day 1: Partitioning deep-dive: what you'd do if the index outgrew one machine
- Week 1, Day 4: Hot keys and skew: dense downtown cells are hot keys in disguise
- Week 4, Day 1: Caching patterns: caching business details and cell results
- Week 7, Day 2: Indexing pipeline: change data capture from the database into a search index
- Week 7, Day 3: Query processing and relevance: ranking candidates by more than distance
- Side quest: Uber: H3 cells for moving drivers, where locations change every few seconds
- Side quest: Blinkit quick commerce: proximity to dark stores and delivery radius
Check yourself#
Proximity service
Q1/3 The whole geo index is about 10 GB and changes about once a second. How should it scale for 15,000 searches/s?
Answer & explanation
Answer: B
10 GB fits in RAM, and it rarely changes, so replicating full copies avoids scatter-gather and scales linearly by adding hosts.
Q2/3 Why does a geohash search read the user's cell and its 8 neighbours?
Answer & explanation
Answer: C
Two places 50 m apart can fall either side of a cell boundary. Reading the 3×3 block, then filtering by exact distance, covers the radius.
Q3/3 A rural search returns only 2 results from the 9 cells. What's the usual next step?
Answer & explanation
Answer: B
One fewer character means larger cells (and a wider area). Expand until there are enough candidates or the maximum radius is reached.
New lessons by email
New lessons, side quests and case files as they ship, at most once a week. No spam, unsubscribe anytime.
Discussion · …
Public: everyone reading this lesson sees comments. Be kind and keep it on the material.