Design a proximity service

By the end of this lesson you’ll know which spatial index to reach for, why your first implementation will miss the nearest result, and how to cache answers so the database barely sees this workload at all.

Requirements

Pin down the shape before the storage. A find-nearby service like Yelp or a store locator has a tight set of functional needs and a very particular load profile.

• Functional: given a user’s latitude/longitude and a radius (or a “k nearest” count), return matching places, ranked. Filters apply on top (category, open-now, rating). Places change slowly; a coffee shop’s coordinates are essentially static.
• Non-functional: read-heavy by a wide margin — searches vastly outnumber edits. Low latency for typeahead (tens of milliseconds). Eventual freshness on the place data is fine; a newly added restaurant appearing a minute late is acceptable. High availability matters more than strong consistency here.

The decisive observation is the read/write asymmetry. Locations are written rarely and read constantly, which means we can afford to build a heavy index once and amortize it across millions of queries — the opposite of the next lesson’s write-heavy live-location problem.

Estimation

Suppose 100M places worldwide and 200M searches per day. Average search QPS is 2×10^8 / ~10^5 s ≈ 2,000, and we provision for a peak of ~10,000 (lunchtime and evening spikes). Each search must not touch 100M rows; it must touch the few hundred candidates inside the relevant cells. Place data is small — say 1 KB per record, so ~100 GB total, comfortably indexable and largely cacheable. The hot working set is “popular city centers”, a fraction of the whole, which is why caching by location pays off so well.

High-level design

The pipeline is the same regardless of which spatial index you pick: convert the user’s point and radius into a set of cell identifiers, fetch candidate places from those cells, compute exact distances and filters on that small set, then rank and return.

The geo-index service is the heart of it. Everything downstream operates on the small candidate set its cell lookup produces, which is why choosing the index well is the design’s central decision.

Deep dive

Choosing the spatial index

There are three families worth knowing, and the right answer depends on your access pattern.

Geohash interleaves the bits of latitude and longitude into a single string, where each added character refines the location into a smaller rectangle. Its great virtue is that nearby points usually share a prefix, so a LIKE 'u4pruyd%' prefix scan on an ordinary B-tree finds neighbors — no special index type required. Its great flaw is that the prefix property is only usually true: two points a meter apart can straddle a boundary and share no prefix at all (the classic example sits near the equator and prime meridian). Geohash cells are also non-uniform in real-world area because longitude degrees shrink toward the poles.

Quadtree recursively splits space into four quadrants, subdividing a cell only when it holds more than some threshold of points. This adapts to density: dense Manhattan gets deep, fine cells; the empty ocean gets one shallow cell. That adaptivity is the win for skewed data, but the tree is a stateful in-memory structure you must build, balance, and rebuild as data shifts — more operational weight than a string prefix.

S2 (Google) projects the sphere onto a cube and uses a Hilbert space-filling curve to give every cell a 64-bit ID; H3 (Uber) tiles the globe with hexagons. Both fix geohash’s worst problems: cells are far closer to equal-area, and IDs at different resolutions nest cleanly. H3’s hexagons have a uniquely useful property — every neighbor is equidistant (a hexagon has six edge-neighbors, all the same distance away), which makes “expand the search ring” operations clean. These are the production choice at scale; the cost is a library dependency and a steeper learning curve.

The cell-boundary problem

Here is the failure that bites every first implementation. You convert the user’s point to its cell, fetch the places in that cell, rank them, and return — and you miss the nearest coffee shop because it sits three meters away, just across the cell line, in the adjacent cell you never queried. A point’s cell tells you roughly where it is, but the true nearest neighbor can live in any of the surrounding cells.

The fix is to query the cell and its neighbors, not the cell alone. With a square grid you fetch the cell plus its eight surrounding cells (the 3×3 block); with H3 you fetch the center cell plus its kRing of neighbors for whatever k covers your radius. You then compute exact great-circle distances on the union of candidates and keep only those genuinely inside the radius. The cell index is a coarse filter that cheaply discards the 99.99% of places that are nowhere near; the precise distance math is the fine filter on what survives. Forgetting the coarse-then-fine split, and trusting a single cell, is the canonical proximity bug.

Bottlenecks & tradeoffs

The first bottleneck is the database, not the index math — and caching by cell is the lever. Because the workload is read-heavy and locations change slowly, the candidate list for a given cell is stable for minutes. Cache keyed by (cell_id, filters) and a popular downtown cell serves thousands of searches from memory between refreshes. This is why the read/write asymmetry from the requirements section is the whole game: you pay the index cost once and reap cache hits forever.

The second is density skew. A fixed-resolution grid wastes effort in the ocean and overflows in Times Square, where one cell might hold ten thousand places. Quadtrees and the variable resolution of S2/H3 exist precisely to keep the candidate count per query roughly bounded regardless of where the user stands.

The third is ranking versus distance. Returning the geometrically nearest places is rarely what a product wants; Yelp ranks by a blend of distance, rating, popularity, and sponsorship. So the cell lookup produces candidates, but the final order is a scoring step — and that scoring is what you cache and tune, separately from the geometry. Keep the two concerns apart: the spatial index answers “which places are plausibly nearby”, and a ranking service answers “in what order should I show them”.