Design a proximity service
"Show me restaurants near me" is a range query in two dimensions — and the entire trick is turning a circle on a map into a bounded set of storage keys you can look up in O(1), then ranking what comes back.
price lets you scan a contiguous range, but it has no notion of "close in both lat and lng at once." A naïve WHERE dist(lat,lng, ?,?) < r has to compute a haversine distance against every row — a full table scan that gets slower as the world fills up. The whole design exists to avoid that scan: map 2-D coordinates to a 1-D key whose prefix encodes locality, so "nearby in space" becomes "nearby in keyspace," and a range query becomes a handful of exact key lookups. This is DDIA Ch. 3's multi-dimensional index problem, solved by space-filling curves.1. Clarify the contract
Treat the prompt as a product contract before a box diagram. A proximity service must:
- Find places near a point —
(lat, lng, radius)→ a ranked list of nearby businesses. - Filter by category, radius, open-now, rating.
- Rank the bounded candidate set by distance, relevance, and quality.
- Be fast on mobile — p99 well under ~200 ms; this is an interactive read.
- Accept place updates — but the data is mostly static (a restaurant moves rarely), so writes are cheap and we can precompute aggressively.
And, just as important, what it need not do: it is not a tracking system for fast-moving objects (that asymmetry — read-heavy, write-rare — is what lets us pre-bin places into cells; the moment objects move every second, the write path dominates and you are in C20's world). It need not be strongly consistent — a place that opened five minutes ago can be missing from one query; this is eventual-consistency territory, not a ledger.
2. Put numbers on the shape
The load-bearing number is geohash precision vs. cell size, because it sets both candidate count and cache granularity. Each geohash character adds ~5 bits, shrinking the cell ~32× in area:
| Geohash length | ≈ cell width | Use |
|---|---|---|
| 5 | ≈ 5 km | region / city-scale |
| 6 | ≈ 1.2 km | neighborhood — good default for "nearby" |
| 7 | ≈ 150 m | street block — dense urban precision |
| 8 | ≈ 38 m | single building |
Now the design driver. Candidate count is density × cell_area, and you size precision so a single cell returns a workable candidate set. In dense Manhattan, place density might be ~2000 restaurants/km². At length 6 (1.2 km ≈ 1.44 km² area) one cell holds 2000 · 1.44 ≈ 2900 candidates — too many to hydrate and rank per query. Drop to length 7 (150 m, ≈ 0.0225 km²): 2000 · 0.0225 ≈ 45 per cell — comfortable. In a rural area at ~5 restaurants/km², a length-7 cell holds 5 · 0.0225 ≈ 0.1 — essentially empty, so you must expand outward (coarser precision or more rings) until you gather enough. One precision does not fit both; precision is a function of local density.
3. Define the surface area
Keep the API small and expressed in product terms — it must not leak the cell, shard, or cache layout.
| API / operation | Why it exists |
|---|---|
GET /nearby?lat&lng&radius&category | The core read. Returns a ranked, filtered list. Note: caller passes a radius, not a cell — the service chooses precision and neighbor expansion internally. |
upsert_place(place) | Write path. Computes the place's cell key(s) at write time and indexes it — precompute, because reads vastly outnumber writes. |
get_place(id) | Hydration: turn a candidate ID into full metadata (name, hours, rating, photos). |
4. Model the data
The data model is the first architecture. The key separation is index vs. metadata — the geo-index maps a cell key to a list of place IDs, and the place store maps an ID to its full record. This is DDIA Ch. 6's distinction between a local secondary index (the cell→IDs mapping, partitioned by cell) and the primary record store (partitioned by place ID).
Why split them? Because the index is tiny and hot (just IDs, fully cacheable per cell) while metadata is large and changes independently. You can rebuild or re-bin the index without touching place records, and you can update a restaurant's hours without re-indexing its location.
5. Linearized design
Walk a /nearby request through the system; the bottleneck — candidate explosion in dense cells — surfaces naturally.
- 1. Pick precision. From the requested radius (and optionally local density), choose a geohash length whose cell is comparable to the radius.
- 2. Compute the 3×3 block. Geohash the query point, then add its 8 neighbors (see C22 for the neighbor algorithm). These 9 keys cover the radius even at a boundary.
- 3. Fetch candidate IDs. One lookup per cell against the geo-index (cache first — see deep dive). Union the ~9 ID lists.
- 4. Hydrate & filter. Batch-fetch metadata for the candidate IDs; drop those outside the exact radius (the cells over-approximate the circle), wrong category, or closed.
- 5. Rank. Score the bounded set by distance, relevance, quality, business rules. Cheap because the set is already small.
- 6. Cache. Cache the cell→IDs lists (and popular cell+category results) — coordinates never enter the cache key (privacy + hit rate; deep dive below).
6. Deep dives
Cache by cell: why the hit rate is so high
The single biggest serving win is that requests cluster. Thousands of users in Times Square at lunch issue near-identical "restaurants nearby" queries. If we keyed the cache on raw (lat, lng) every one would be a miss — coordinates are effectively unique. But if we key on the cell, all of them collapse onto the same handful of cell keys. The cell is a deliberate quantization of the query: it trades a little precision (the over-approximation we clean up in the filter step) for a massive collision rate. Lesson 06's hit-rate→origin-load math applies directly: if 95% of /nearby traffic concentrates in a few thousand popular cells, a cell cache serving 95% of reads cuts geo-index load 20×. The cached object is the small cell→IDs list, not the hydrated result, so it stays cheap and survives metadata churn (hydration can hit a separate, ID-keyed cache). The corollary in sparse areas: cell caching does little, because each rural query touches different, rarely-repeated cells — but those areas have low QPS anyway, so it does not matter. See lesson 06.
Ranking on a bounded candidate set
The architecture buys ranking a gift: by the time we rank, the candidate set is already small and bounded (~tens to low hundreds after the geo-fetch and filter). That means we can afford an expensive per-candidate scoring function — distance decay, rating, sponsored boosts, personalization — without scanning the world. This is the classic retrieve-then-rank split: a cheap, recall-oriented geo-retrieval narrows millions of places to a few dozen; an expensive, precision-oriented ranker orders those few. The geo-index does not need to be ranked at all — it only needs to return the right set. Keeping these phases separate is what lets you change the ranking model weekly without touching the index.
Privacy & freshness of user location
The query carries the user's exact position — the most sensitive datum in the system. Two disciplines: (1) Don't retain it. The exact (lat, lng) is needed only transiently to compute the cell and do the final exact-radius filter; it should not flow into logs, analytics, or cache keys. Caching on the cell rather than the coordinate is privacy-preserving by construction — the cache never sees a precise location, only a ~1.2 km bin. For analytics, coarsen to a low-precision geohash (length 5–6) so you keep aggregate demand signals without re-identifiable trails. (2) Freshness asymmetry. Place data is mostly static, so a stale-by-minutes index is fine and serving aggressively from cache is safe. We version place records and, on an upsert that moves a place across a cell boundary, invalidate the affected cells — but we do not chase per-second freshness, because nothing here moves per second. (That assumption is exactly what C20 drops.)
7. Trade-offs
| Choice | Buys | Costs | Choose when |
|---|---|---|---|
| Geohash vs quadtree (mechanics in C22) | simple prefix keying, trivial sharding | fixed grid wastes cells in skewed density | MVP / uniform-ish density |
| Cache by cell vs exact coordinate | huge hit rate; privacy by construction | cell over-approximates the circle | popular city queries (the default) |
| Precompute place cells vs compute at query | fast O(1) reads | extra write work, re-index on move | mostly-static places (this case) |
| Fixed precision vs density-adaptive | simplicity | too many candidates downtown, empty rural cells | tolerable density skew |
The sharpest trade-off is fixed precision vs. density-adaptive, and it is the one that separates a toy from a product. Pick a single global geohash length and you either bury the ranker under thousands of downtown candidates or return nothing in the countryside. Geohash's answer is to vary precision per query (fine downtown, expand rings rurally); a quadtree's answer is to vary it structurally — the tree subdivides only where density is high, so a dense cell becomes four children automatically. That structural adaptivity is exactly why C22 treats the quadtree as the more general index; here we just need to know that uniform precision is the thing that breaks, and density is the variable that breaks it.
8. Failure modes
| Failure | Mitigation |
|---|---|
| Missing results at cell boundary | Always fetch the 3×3 neighbor block, never the center cell alone (mechanism: C22). |
| Dense-cell candidate explosion | Increase precision (smaller cells) downtown, or cap + pre-rank candidates before hydration. |
| Empty rural cells | Expand outward — coarsen precision or add neighbor rings until enough candidates gather. |
| Hot cell / hot partition | Popular cells become hot keys (07): serve them from the cell cache; replicate hot cells; never shard so a megacity lands on one node. |
| Stale place data | Version records; on a boundary-crossing upsert, invalidate affected cells. |
| Location privacy leak | Never log/cache exact coords; key cache on cell; coarsen for analytics. |
9. Interview Q&A
- A user is 10 m from a cell edge and the nearest restaurant is just across it. Why does a naïve single-cell geohash miss it, and how do you fix it? (senior answer) Because a geohash cell is a square and the query is a circle: two points a few meters apart but on opposite sides of a boundary get different cell keys, so they look "far" in keyspace even though they're adjacent in space. Querying only the center cell silently drops everything across the line. The fix is neighbor-cell expansion — compute the center cell plus its 8 surrounding cells and union the results, so the radius is fully covered regardless of where in the cell the point sits. The actual algorithm for deriving the 8 neighbor keys (decode, step lat/lng, re-encode, handle wraparound) is the C22 mechanism; the serving-side rule is simply "never one cell — always the 3×3 block."
- How do you choose geohash precision? (senior answer) From candidate count = density × cell area. Pick the length whose cell yields a workable set: ~length-6 (1.2 km) as a neighborhood default, length-7 (150 m) downtown where density would otherwise give thousands per cell, and expand to coarser precision or extra rings in sparse areas. It's per-query, not global — uniform precision is the thing that breaks under density skew.
- Why does caching work so well here, and what do you key on? (senior answer) Because queries cluster geographically — thousands of users in one plaza issue the same lookup. Keying on raw coordinates makes every request unique (all misses); keying on the cell collapses them onto a few hot keys, so a popular-cell cache serves the bulk of reads and cuts index load ~20× (lesson 06). Bonus: a cell key never contains a precise location, so cell-caching is privacy-preserving by construction.
- Geohash or quadtree? (senior answer) Geohash for simplicity and prefix-based sharding when density is roughly uniform; quadtree when density is heavily skewed, because it subdivides structurally — dense regions get finer cells automatically. They solve the same retrieval problem; C22 derives both. The decision variable is density skew vs. implementation simplicity.
- Where does ranking happen, and why not rank in the index? (senior answer) Retrieve-then-rank: the geo-index does cheap, recall-oriented retrieval to a small bounded set; an expensive precision ranker then orders just those few dozen. Keeping them separate means the index only has to return the right set, and you can swap ranking models without touching the index.
- How is this different from a "nearby friends" / live-driver service? (senior answer) Write rate. Places are static, so we precompute cells and read-optimize aggressively. Moving objects update location every few seconds, so the write path dominates and the precompute-everything assumption collapses — that's the C20 streaming variant, with a different store (in-memory / pub-sub) and freshness contract.
- How do you handle a hot cell (a megacity downtown)? (senior answer) It's a hot-partition problem (lesson 07). Serve it from the cell cache so most reads never hit the index; replicate the hot cell across nodes; and ensure the sharding scheme doesn't put an entire metro on one partition. Increasing precision also helps by splitting one giant cell's traffic across many smaller keys.
Related foundation & cases
The geo-index mechanics — geohash bit-interleaving, quadtree subdivision, the neighbor-cell algorithm — are derived once in C22 (the anchor); this case links there rather than repeating them. The moving-object variant (live friends / drivers, write-heavy) is C20. Lesson 06 supplies the cache-by-cell hit-rate math, and lesson 07 the hot-cell / sharding reasoning. The multi-dimensional-index framing is DDIA Ch. 3; the index-vs-metadata (local secondary index) split is DDIA Ch. 6.