Proximity service
“Find things near me” is a two-dimensional range query, and ordinary indexes are one-dimensional. The trick is to map 2-D space to 1-D cell ids (geohash, S2, H3) so a nearby search becomes a few index lookups: the point’s cell plus its 8 neighbours, then filter by true distance. Or use an adaptive quadtree that splits dense areas. The design splits on the data: places are read-heavy and change slowly (200M places ≈ 6 GB: precompute, replicate everywhere, rebuild offline), while driver locations are write-heavy and short-lived (1M drivers every 4 s = 250k writes/s: latest position only, in memory, sharded by region, stale entries expired).
The problem
Section titled “The problem”Yelp and Google Maps answer “coffee within 1 km”. Uber, Lyft and DoorDash answer “the 10 nearest available drivers to this pickup”. Both are proximity queries, but the data behaves very differently:
| Places (Yelp-like) | Drivers (Uber-like) | |
|---|---|---|
| Count | 100M-500M | 1M-5M online |
| Change rate | A few edits per second worldwide | Every driver, every 4 s |
| Read pattern | Very high QPS, cacheable by area | Per ride request, must be fresh |
| Staleness allowed | Minutes to a day | Seconds |
| Right store | Precomputed index, replicated | In-memory, sharded, overwritten |
The competing goals:
| Goal | Pulls toward |
|---|---|
| Correct results (nothing within the radius is missed) | Search neighbouring cells, filter by true distance |
| Low latency under heavy read load | Small in-memory index, replicas, caching |
| Fresh moving data | Cheap overwrites, expiry of silent entries |
| Even load despite dense cities | Adaptive cells, sharding by region and finer cells |
Requirements and scope
Section titled “Requirements and scope”| In scope (typical) | Ask about | |
|---|---|---|
| Functional | Search places within radius r (0.5-20 km) of a point, with filters; add/edit places; track driver locations; find K nearest available drivers. | Radius or K-nearest? Ranked by distance only, or by rating too? |
| Scale | 200M places, 5k searches/s (peak ≈3×); 1M online drivers, update every 4 s. | DAU, searches per user, drivers per city at peak? |
| Latency | Search p99 under 100 ms; driver match under 1 s. | Is ETA (road distance) needed, or straight-line? |
| Freshness | New place visible within hours; driver position within ~5 s. | Can a new listing take a day? |
| Availability | Search stays up if writes are down. | Region failover for matching? |
| Out of scope | Routing and ETA engine, maps rendering, payments. |
Back of the envelope
Section titled “Back of the envelope”Drag the assumptions. Two surprises: the places index fits on one machine (so you replicate rather than shard it), and drivers, a much smaller dataset, generate 50× more writes than places get reads.
What to say out loud: “The places index is a few GB, so I’ll replicate it to every search node and scale reads horizontally. Driver locations are about 250k writes a second but tiny in total, so they go into an in-memory store keyed by city, overwritten in place, with stale drivers expired.”
API and data model
Section titled “API and data model”GET /places/nearby?lat=..&lon=..&radius_m=1000&category=coffee&limit=20 -> [ { place_id, name, lat, lon, distance_m, rating } ]POST /places { name, lat, lon, category, ... } -- owners, rarePUT /drivers/{id}/location { lat, lon, heading, at } -- every ~4 sPOST /rides { pickup_lat, pickup_lon } -> { ride_id, driver_id, eta_s }
Place { place_id, name, lat, lon, geohash6, category, rating, ... } -- DB rowGeo index cell_id -> [ (place_id, lat, lon) ] -- in memoryDriver loc region key -> sorted set of (driver_id, cell score); last_seen per driverTwo decisions hide in that sketch:
- The index stores cell → ids, the database stores everything else. Keep the index small (id + coordinates) so it fits in memory; fetch names, photos and hours from a cache keyed by id for the 20 results you return.
- Precision is chosen per query, from the radius. The cell must be at least as big as the radius for the 9-cell search to be complete. Store each place at several precisions (e.g. geohash lengths 4, 5, 6), or use a structure where coarser cells are prefixes of finer ones, so one index serves every radius.
High-level design
Section titled “High-level design”Step through each flow. The top half is the read-heavy places path, the middle is the write-heavy drivers path, and the bottom is how place edits reach the index.
| Component | Role | Why it’s there |
|---|---|---|
| Search (×N) | Encodes the point, computes neighbour cells, reads the index, filters by distance, ranks. | Stateless, so it scales with read QPS. |
| Geo index | Cell id → place ids + coordinates, in memory on each search node (or a small replicated cache). | 6 GB fits; replication beats sharding for reads. |
| Places DB | Source of truth, primary + read replicas, with a geohash column and a B-tree index on it. |
Durable, and can serve cell queries itself at low scale. |
| Index builder | Rebuilds or patches the index from the change stream; publishes a versioned snapshot. | Keeps writes off the read path. |
| Ingest (×N) | Receives driver pings, writes latest position, appends history to a log. | Absorbs 250k writes/s. |
| Driver locations | Per-region in-memory geo sets (e.g. Redis GEOADD / GEOSEARCH), plus last-seen times. |
Overwrite in place; region = shard. |
| Matcher | Radius search, rank by ETA, atomically claim a driver. | Two riders must not get the same driver. |
Deep dive: cells, geohash and the neighbour problem
Section titled “Deep dive: cells, geohash and the neighbour problem”A geohash splits the world in half by longitude (bit 1 = east half), then the result by latitude, alternating, and writes every 5 bits as one base-32 character. San Francisco’s Market Street is 9q8yyk. Two properties make it useful:
- A prefix is a cell. Every point in cell
9q8yyhas a hash starting with9q8yy, so “all places in this cell” is one range scan on a sorted index, in any database. - Each character shrinks the cell ~32×. Length 4 ≈ 39 × 20 km, 5 ≈ 4.9 × 4.9 km, 6 ≈ 1.2 × 0.6 km, 7 ≈ 153 × 153 m (at the equator; cells get narrower in longitude toward the poles).
The catch: nearby points can be in different cells, sometimes with a short common prefix (across the equator or the prime meridian, they share none). So a search never reads just one cell. It reads the point’s cell plus its 8 neighbours, and filters by true distance. Click the map, change the radius and the precision:
nearby(lat, lon, radius): p <- finest precision whose cell height and width are both >= radius center <- geohash(lat, lon, p) cells <- center + its 8 neighbours -- neighbours: geohash of (lat ± cell_h, lon ± cell_w) candidates <- union of index[c] for c in cells results <- [x in candidates where haversine(x, (lat, lon)) <= radius] if count(results) < wanted and p > MIN: retry with p - 1 -- widen in sparse areas return top results by distance (or score)What the simulator shows: if cells are smaller than the radius, some places in the circle sit outside the 9 cells (missed). If cells are much larger, downtown you scan hundreds of candidates to return a handful. Picking precision from the radius is the fix, and the “widen if too few” loop handles sparse suburbs. The same 9-cell idea works on any grid; the matrix page covers neighbour arithmetic on 2-D grids.
S2 and H3 are the industrial versions:
| Scheme | Cell shape | Levels | Notes |
|---|---|---|---|
| Geohash | Rectangles on lat/lon | 1-12 chars | Simple, prefix = cell; distorted near poles; boundary jumps |
| S2 (Google) | Quadrilaterals on a cube projected to the sphere | 31 levels (0-30), 64-bit ids | Hilbert curve keeps nearby cells close in id order; “region covering” turns any circle into a few cell ranges |
| H3 (Uber) | Hexagons (plus 12 pentagons) | 16 resolutions (0-15) | Every neighbour is the same distance away, good for surge pricing and smoothing; gridDisk(k) = rings of neighbours |
Deep dive: quadtrees and dense cities
Section titled “Deep dive: quadtrees and dense cities”Fixed grids treat Manhattan and the Sahara the same. A quadtree adapts: start with one square; when a leaf holds more than C places, split it into four. Dense areas get deep, small leaves; empty areas stay as one big leaf. Add points and a cluster below:
query(node, center, r, out): if distance from center to node's square > r: return -- prune the whole subtree if node is a leaf: out += [p in node.points where dist(p, center) <= r] else: for child in node.children: query(child, center, r, out)For K-nearest instead of a radius, walk nodes in order of distance with a heap and stop once the K-th best result is closer than the next node. Practical notes:
- Size. 200M places with leaves of 100 ≈ 4M leaves and ≈1.3M internal nodes: a few hundred MB on top of the place ids. It fits in memory on each server.
- Build offline, swap in. Splitting and merging nodes under concurrent writes is painful. Build the tree from a snapshot (minutes for 200M points), load it on each search node, and swap versions atomically. Patch small updates in place, or just wait for the next build.
- Startup. A new server builds or downloads the tree before taking traffic; roll out gradually so the fleet isn’t all rebuilding at once.
- Geohash vs quadtree. Geohash works in any database with a string index and is easy to shard by prefix. A quadtree balances density automatically but is an in-memory structure you own. S2 gives you both: hierarchical cells with ids you can store in any index.
Deep dive: moving drivers, sharding and hot spots
Section titled “Deep dive: moving drivers, sharding and hot spots”Driver locations are the opposite workload: 250k writes/s, each overwriting the last position, and a driver who stops sending must vanish within seconds.
- Latest position only, in memory.
GEOADD drivers:{city} lon lat driver_idstores a member in a sorted set with a 52-bit geohash score; adding again overwrites.GEOSEARCH … FROMLONLAT lon lat BYRADIUS 2 km ASC COUNT 10returns the nearest, costing O(N + log M) where N is the members in the bounding box around the circle. - Shard by region. One key (or cluster of keys) per city or per coarse cell. Every ride request touches one shard; writes spread across cities. A rider near a city border also queries the neighbouring region.
- Expire silent drivers. Sorted-set members can’t have their own TTL. Keep
last_seenin a second sorted set (score = timestamp) and sweep members older than ~30 s every few seconds, or write into one key per time bucket (drivers:sf:t1234) with a key-level expiry and read the newest two buckets. - History goes elsewhere. The full GPS trail is appended to a log (Kafka) for trip records and ETA models, never kept in the hot store.
- Claim atomically. The matcher sends an offer only after a conditional set (
SET lock NX EX 15) succeeds, so two riders can’t book one driver. This is a short lease.
Hot spots. A stadium lets out and 5,000 riders and 2,000 drivers pile into a few cells of one city shard. Options: split hot regions into finer cells (each its own key), which is what H3 resolutions make easy; route big cities to bigger shards; and cache place-search results per cell, since everyone at the stadium gets the same answer. For places, dense cities are why a quadtree or multi-precision geohash beats a single fixed grid.
Multi-region. Places are global but read-only on the hot path, so replicate the index to every region. Drivers are naturally regional: a driver in São Paulo never matches a rider in Tokyo, so each region runs its own driver store and matcher with no cross-region coordination.
Failure modes
Section titled “Failure modes”| What breaks | What you see | Design response |
|---|---|---|
| Search radius bigger than cell | Places in the circle missing | Choose precision from radius; widen when too few results |
| Point near a cell edge | Nearest place in a neighbour cell is missed | Always read the 8 neighbours, filter by true distance |
| Dense city cell | Thousands of candidates per search, slow p99 | Finer precision or quadtree; cap candidates; cache per cell |
| Driver goes offline silently | Riders matched to ghosts | Last-seen sweep (~30 s), time-bucketed keys |
| Two matchers pick the same driver | Double booking | Conditional set with expiry as a claim; loser tries the next |
| Driver store shard down | No matching in one city | Replica failover; drivers re-send within 4 s, so state rebuilds itself quickly |
| Index rebuild fails | Stale places | Keep serving the last good version; alert on index age |
| Pole/antimeridian edge cases | Wrong neighbours or distances | Use S2/H3 libraries for neighbour math; haversine, not flat distance |
What it costs
Section titled “What it costs”| Operation | Time | Space |
|---|---|---|
| Encode a point to a cell | O(precision bits) | — |
| Nearby search, geohash | 9 index lookups + O(candidates) filter | O(places) ≈ 32 B each in the index |
| Nearby search, quadtree | O(depth + leaves touched × C) | ≈ 2 × places / C leaves + internal nodes |
| K-nearest, quadtree | about O(depth + K) node visits, each an O(log) heap op | O(K + frontier) |
Driver update (GEOADD) |
O(log M) per update | ≈100 B per driver |
Driver radius search (GEOSEARCH) |
O(N + log M), N = drivers in the bounding box | — |
| Throughput | 5k searches/s on 1-2 replicas; 250k driver writes/s across region shards | 6.4 GB places index; 100 MB drivers |
In the interview
Section titled “In the interview”A good 45-minute arc:
- Clarify (5 min). Static places, moving drivers, or both. Radius or K-nearest, ranking, freshness, scale.
- Estimate (5 min). Index size (fits in RAM), search QPS, driver writes/s.
- Why a normal index fails (3 min).
WHERE lat BETWEEN … AND lon BETWEEN …uses one index and scans a whole stripe of the map. - Spatial index (12 min). Geohash: prefix = cell, precision from radius, 9 cells, filter by haversine. Mention quadtree for density, S2/H3 as production choices.
- Architecture (10 min). Replicated in-memory index for places, rebuilt offline from the DB; region-sharded in-memory store for drivers with expiry; atomic driver claim.
- Scale and edges (10 min). Hot cells, border queries, multi-region, failure handling.
Follow-ups to expect: “Two-dimensional index in plain Postgres?” A geohash column with a B-tree and prefix ranges, or PostGIS with a GiST (R-tree) index. “Return the 10 nearest, however far.” Start fine and widen precision until 10 results, or K-nearest on a quadtree. “Drivers on the edge of a city.” Query the adjacent regions’ shards too. “Why hexagons?” Equal-distance neighbours, so rings and smoothing behave the same in every direction.
Check yourself
Section titled “Check yourself”Go deeper
Section titled “Go deeper”- Redis docs: GEOSEARCH and geospatial indexing: geo sets as sorted sets with 52-bit geohash scores, and the exact search cost.
- S2 Geometry: S2 cell hierarchy: cube-face projection, Hilbert curve ordering, 31 levels of cells.
- Uber Engineering: H3, Uber’s hexagonal hierarchical spatial index and the H3 resolution table: why hexagons, and cell sizes per resolution.
- Wikipedia: Geohash: the bit interleaving, base-32 alphabet, cell dimensions per length, and edge cases.
Concept pages to drill: Indexing · Bit manipulation · Matrix · Heap · Divide and conquer · Caching · TTL and expiry