Design a Proximity Service: Geohash, Quadtree & S2 at Scale

Open Yelp, type "pizza," and within 50 milliseconds you get the twenty nearest places sorted by distance. That single feature — find the nearby things — powers Yelp, Google Maps, Uber, DoorDash, and Tinder. The prompt sounds trivial until you realize a naive SELECT that computes distance to all 200 million points on every query would take seconds and melt your database.

The whole design hinges on one decision: how you index two-dimensional space so a "within 2km" query touches a few hundred candidates instead of scanning the planet. Get the spatial index right and everything else — sharding, caching, the live-location firehose — falls into place around it.

This walks the standard interview rubric: requirements, capacity math with real numbers, the indexing choice, the API and data model, then the hard deep dives on radius search and the Uber-style write path.

What are we actually building?#

Two query shapes cover almost every proximity product:

• Radius search: "all pizza places within 2km of me." Bounded region, variable result count.
• k-nearest: "the 20 closest drivers." Fixed result count, variable radius that expands until you have enough hits.

Both attach to geo-tagged entities and usually combine with non-spatial filters (cuisine, rating, vehicle type, price). The functional surface is small; the traffic profile is what splits the design into two camps.

Yelp's points barely move, so its index can be rebuilt daily and served from a read replica. Uber's drivers ping their location every few seconds, so its index is a churning in-memory structure with TTLs. Deciding which camp you're in is the first thing to say out loud — it changes the datastore, the partition key, and the freshness guarantee.

Non-functional targets to commit to up front: p99 query latency under ~50ms, result freshness within a few seconds for live data, and availability over strict consistency (a driver appearing one second late is fine).

Capacity estimation: does this even need to be hard?#

Run the numbers before choosing tools — they tell you whether the problem is trivial or genuinely scary. Take a Yelp-style deployment: 200M points of interest, 10M daily active users, 5 radius queries per user per day, ~500 results per query.

The punchline: the query rate is laughably small — 6k QPS is nothing. And the geo index at 12 GB fits in RAM on a couple of nodes. The frightening number is the hydration fanout: turning 6,000 queries into 3 million record lookups per second to fill in names, ratings, and photos. That's what forces a Redis hot-set cache (~100 GB) or a column store with batched multi-get in front of the POI table. The index is cheap; serving the payload is where the cost lives.

Now contrast Uber: 3M drivers each posting every 4 seconds is 3M / 4 = 750,000 writes/sec just for location updates, before a single rider query. Same "proximity" label, completely different machine.

Which spatial index: geohash, quadtree, or S2?#

This is the core trade-off and the question interviewers push hardest on. All three map 2D coordinates onto a 1D orderable key so that nearby points sort near each other, letting a plain B-tree or KV store answer spatial queries.

The rule of thumb worth memorizing:

• Geohash when you want the simplest thing that shards in a KV store — great for static Yelp-style data.
• Quadtree when density varies wildly and data is dynamic — Uber's leaves subdivide hot downtowns automatically and merge empty rural cells.
• S2 when correctness on global data matters — antimeridian crossings, polar regions, and precise region queries where geohash's rectangular cells distort.

Geohash's weakness deserves emphasis. Because it's a Z-order curve, two physically adjacent points can land in cells whose hashes share almost nothing when they straddle a longitude or latitude boundary. That's why a geohash radius query can't just match one prefix — it has to probe the neighbors too.

Radius search with geohash, step by step#

Here's the concrete algorithm for "find everything within 2km of (37.7749, -122.4194)" — downtown San Francisco.

Why 9 cells instead of 1? Your 2km circle can spill across the edge of the center cell into any adjacent cell, and geohash's boundary discontinuity means those neighbors don't share the center's prefix. Probing all 9 guarantees full coverage. The Haversine refine then prunes the false positives — the candidate set is a rough square-ish region, and you only want the inscribed circle.

Two refinements interviewers reward:

• Multi-precision indexing: store each point at several geohash lengths so a small-radius query picks a tighter cell and overfetches less.
• Antimeridian and poles: near longitude 180° or the poles, the neighbor computation must wrap around. S2 handles this natively; with geohash you write explicit wrap-around logic. This is the single strongest argument for S2 on truly global data.

The live-driver pipeline: 750k writes/sec#

The Uber-style write path is the hardest deep dive, and one design choice makes or breaks it: partition by cell, not by driver.

Partitioning Kafka by geohash_prefix lands physically nearby drivers in the same partition, so a rider's "nearest drivers" query hits one partition's worth of locality instead of fanning across the cluster. Partitioning by driver_id would scatter neighbors randomly and destroy that locality.

At 750k writes/sec you shard the in-memory index by S2 cell — roughly level 12, about 2km cells — so a hot city scales on its own nodes independently of quiet regions. Use consistent hashing on cell_id so the cell-to-node mapping survives node failures without reshuffling everything. Stale locations get a ~30s TTL: a driver who stops pinging simply ages out of the index rather than lingering as a ghost.

Combining spatial and non-spatial filters#

Real queries are "pizza within 2km, rating > 4," not pure geometry. Two strategies:

Elasticsearch is the pragmatic answer for rich filtering — its BKD-tree indexes intersect multi-dimensional filters (price, rating) with a geo_point field natively, letting Lucene AND the posting lists together. The fallback for dense areas where a common category floods the bounding box: switch to k-nearest, expanding S2 cells outward until you have enough hits, then rerank by distance and rating.

And why not just use PostGIS?#

Because for a while, you should. PostGIS on Postgres with GiST (R-tree) indexes is excellent up to roughly 10k QPS and ~100M points on a single primary, supports full geometry (polygons, not just points), and gives you SQL joins with filters for free. Most proximity products never outgrow it.

It breaks down at three thresholds: write QPS beyond a single primary's ceiling (Uber's 750k/sec), latency demands under ~10ms p99 that require in-memory access, or the need for horizontal scale-out Postgres doesn't natively provide. At that point you move the hot path to Redis GEO, a custom S2/quadtree shard service, or Elasticsearch — while keeping PostGIS for lower-QPS and analytical workloads. Reaching for a distributed spatial cluster on day one is over-engineering; naming the exact threshold where PostGIS stops working is the senior signal.

How this shows up in interviews#

Interviewers use proximity service to test whether you can pick a data structure from first principles instead of reciting a stack. The failure mode is jumping straight to "I'll use Redis GEO" without establishing whether the workload is read- or write-heavy — those are different systems.

Score points by driving the conversation in this order: clarify Yelp vs Uber, do the capacity math out loud (and notice the index is tiny while hydration fanout dominates), then justify geohash vs quadtree vs S2 against that workload. Expect the follow-up "how does radius search handle a point right on a cell edge?" — the 9-cell probe plus Haversine refine is the answer that separates people who memorized "geohash" from people who understand it. If you claim S2, be ready to explain why: antimeridian and pole correctness.

The related designs share machinery. Design Uber is this problem's write-heavy sibling — the same cell index under a matching/dispatch layer. Design Instagram, Design Twitter, and Design YouTube reuse the fanout, caching, and hydration patterns that dominate the read path here.

Further learning#

• Design A Location Based Service (Yelp, Google Places) — ByteByteGo's walkthrough of the geohash and quadtree trade-offs, a clear complement to this article.
• Practice this topic on YeetCode — step through the requirements, indexing choice, and scaling deep dives interactively.

FAQ#

What is the best spatial index for a proximity service?#

There isn't one best — it depends on the workload. Geohash is the simplest and shards cleanly in a KV store, making it ideal for read-heavy, mostly-static data like Yelp businesses. Quadtree adapts to density by subdividing hot areas and merging empty ones, which suits dynamic write-heavy data like Uber's moving drivers. S2 gives spherical correctness (no pole or antimeridian distortion) and exact region covers, so pick it when your data is truly global or you need precise region queries. State the workload first, then the index follows.

Why does a geohash radius query need to check 9 cells?#

Geohash maps 2D space onto a 1D Z-order curve, and at cell boundaries two physically adjacent points can have hashes that share almost no prefix. A search circle centered in one cell will usually spill over its edges into neighboring cells, and those neighbors won't match the center's prefix. Probing the center cell plus its 8 neighbors guarantees you capture every point the circle could touch. You then compute exact Haversine distance to each candidate to discard the ones that fall inside the square region but outside the actual radius.

How do you handle 3 million drivers updating location every few seconds?#

That's about 750,000 writes per second (3M ÷ 4s). Drivers POST to an edge gateway that publishes to Kafka partitioned by geohash prefix — not driver ID — so nearby drivers land in the same partition and rider queries get locality. A location service consumes these and updates an in-memory geo index (Redis GEO or an S2-cell-to-driver map), sharded by S2 cell so hot cities scale independently, with a ~30s TTL that ages out drivers who stop reporting. Rider queries read from a separate path over the same in-memory index.

When should I use PostGIS instead of a specialized geo system?#

Use PostGIS for as long as you can — it handles up to roughly 10k QPS and 100M points on a single primary with GiST R-tree indexes, supports full geometry, and gives SQL joins and filters for free. Move off it only when you cross a concrete threshold: write throughput beyond a single primary, p99 latency requirements under ~10ms that demand in-memory access, or a need for horizontal scale-out. Even then, you typically keep PostGIS for lower-QPS and analytical workloads and only offload the hot path to Redis GEO, a custom S2 shard service, or Elasticsearch.

How do you combine "nearby" with filters like cuisine or rating?#

Two approaches. Spatial-first retrieves candidates in the radius, then filters by predicate in memory — best when the spatial cell is already small and selective. Composite indexing bakes the filter into the key (concatenating geohash with a category) or uses an engine like Elasticsearch that combines a geo_distance query with term and range filters in one pass, using BKD-tree indexes to intersect multi-dimensional predicates natively. For dense areas where a common category floods the bounding box, switch to k-nearest: expand S2 cells outward until you have enough hits, then rerank by distance and rating.