Skip to content

00. Design a Proximity / Nearby Service

~20 min read · Level: intermediate · Part 1 of 4 (Overview → HLD → LLD → Q&A)

Problem

A proximity service answers one deceptively small question: "what is near me?" It is the engine behind Yelp's nearby restaurants, Google Maps' places around this pin, and the "shops within 500 m" strip inside a dozen delivery and travel apps. A user stands somewhere with a phone, the app sends a latitude and longitude, and the service returns the places within some radius, filtered by whatever the user cares about and ranked so the good ones are on top.

The naive mental model — "compute the distance from the user to every place, sort, take the top twenty" — is exactly the wrong one, and seeing why is most of the interview. With tens of millions of places, a per-query full scan is hopeless: you cannot touch 50 million rows in under 100 ms, sixty thousand times a second. The whole design exists to avoid that scan. You want to reduce "everything on Earth" to "the few hundred places that could plausibly be within a kilometer" using a spatial index, and only then measure exact distance and rank. Getting that reduction right — how the space is chopped into cells, how big the cells are, how you keep the index fresh — is the substance of the problem.

To keep the reasoning concrete, thread one query through the whole design: "restaurants within 1 km of me, open now, ranked" — issued at 50,000 QPS against a catalog of 50 million places. A lunchtime crowd in a dense downtown fires this same shape of query over and over; the coordinates differ by a few meters, the radius and intent are identical, and the answer must land in well under 100 ms. That single query, at that rate, against that catalog, tests every decision below.

Functional requirements

  • Radius search: given a point and a radius (or a viewport), return places inside it.
  • Attribute filters: narrow by category (restaurant, cafe), by "open now", by price tier, by minimum rating.
  • Ranking: order the results by a blend of distance, rating, review count, and popularity — not by distance alone.
  • Place management: add, edit, and remove places; update hours, category, and rating.
  • Pagination: return the top N with a stable way to fetch the next page.

De-scoped for this round, and worth naming so the interviewer hears a decision rather than an omission: turn-by-turn routing and travel-time estimation (that is a graph problem, not a proximity problem), full-text search over place names (that is the autocomplete/search study), the review-writing and photo-hosting subsystems, and per-user personalized ranking models. Each is real; none changes the spatial core.

Non-functional requirements

The dominant constraint is read latency under a read-heavy, spatially-skewed load. Every structural decision follows from it.

  • Latency: a nearby query should return in well under 100 ms at the service layer, ideally 20–50 ms, because it sits on an interactive map that redraws as the user pans.
  • Read-heavy: searches vastly outnumber writes. A restaurant's location essentially never changes; its hours and rating change occasionally; users search constantly. The system is tuned for reads and tolerates a slow, batch-friendly write path.
  • Spatial skew: queries are not spread evenly over the map. Downtown at lunch draws orders of magnitude more traffic than farmland at any hour, and places themselves cluster the same way. The design must survive hot regions and dense cells.
  • Freshness tolerance: results can be slightly stale. A rating that updates a few minutes late, or a newly-added cafe that becomes searchable a minute after it is created, is acceptable. "Open now", by contrast, must be correct to the minute — which forces a decision about what belongs in the index and what is computed per query.
  • Availability: the read path should target four nines. A maps app that cannot answer "what's near me" is broken; a slightly stale answer is not.

Scale estimation

Assume 50 million places worldwide and a steady 50,000 nearby-queries/second at peak, concentrated in daytime urban hours.

Storage. The full place record — name, address, category, hours, phone, rating, photos-pointer — averages ~2 KB, so the source-of-truth catalog is 50M × 2 KB = 100 GB. That is a modest database, not a big-data problem. The spatial index needs far less per place: a place id, its lat/lng, its cell id, and a couple of ranking attributes (category, rating) — call it ~100 bytes. So 50M × 100 B = 5 GB, which fits comfortably in memory on a single large node and trivially across a small sharded cluster. This is the number that matters: the searchable index is small enough to hold in RAM, which is what makes sub-50 ms possible.

Write load. New places and edits are rare against this backdrop. Even at 10 million place changes a year — generous — that is 10M / (365 × 86,400) ≈ 0.3 writes/second on average, peaking maybe in the tens per second. Rating and review-count updates are more frequent but are aggregated asynchronously, not written on the query path. Against 50,000 read QPS, writes are a rounding error; this is a read-optimization problem with a batch write path bolted on.

Query fan-in. Here is where the index granularity earns its keep. Index the world with geohash precision 6 — cells roughly 1.2 km × 0.6 km, about 0.7 km². A 1 km-radius query is covered by the cell containing the point plus its 8 neighbors: 9 cells per query. In a dense downtown cell there might be ~200 candidate places, so a query gathers 9 × 200 ≈ 1,800 candidates, runs an exact-distance filter down to the ~1,200 truly within 1 km, applies "open now" to reach a few hundred, and ranks those to return the top 20. Contrast the coarse alternative: geohash precision 5 (~5 km cells) means each cell holds ~25× the places, so a dense cell carries ~5,000 places and the candidate set balloons past 20,000 — 100 ms of pointless scanning. Fine cells cut the scan but multiply lookups: precision 7 (~150 m) needs ~49 cells to cover 1 km. Precision 6 is chosen because it matches the 1 km radius — enough cells to cover the circle, few enough places per cell to scan fast.

Backend QPS after cache. Fifty thousand raw queries do not all reach the index. By snapping each query's coordinates to its cell before caching, users standing within the same ~1 km cell share one cached result set; in a packed downtown that collapses thousands of distinct requests into one. A ~70% cache hit ratio leaves 50,000 × 0.30 ≈ 15,000 QPS reaching the index tier, and each of those touches 9 cells, so 15,000 × 9 ≈ 135,000 cell lookups/second spread across the shards. On a 20-shard in-memory index that is ~6,750 lookups/second per shard — unremarkable for RAM.

Bandwidth. A result page of 20 places at ~500 bytes each is ~10 KB, so 50,000 × 10 KB = 500 MB/s outbound at peak. Compact payloads and the result cache absorb most of it; the tail is standard CDN and gzip territory.

API sketch

GET /api/v1/nearby
  query: lat=37.7749&lng=-122.4194&radius_m=1000
         &category=restaurant&open_now=true&min_rating=4.0
         &limit=20&cursor=<opaque>
  200:  { "results": [ { "place_id": "...", "name": "...", "distance_m": 240,
                         "rating": 4.5, "open_now": true, "score": 0.87 }, ... ],
          "next_cursor": "<opaque>" }

GET /api/v1/places/{place_id}
  200:  { full place record incl. hours, address, category }

POST /api/v1/places            # add a place (admin/business owner)
  body: { "name": "...", "lat": ..., "lng": ..., "category": "...", "hours": {...} }
  201:  { "place_id": "..." }

PATCH /api/v1/places/{place_id}   # edit hours / category / location
  200:  { updated record }

Solutioning

Start from the fan-in math and the architecture writes itself. The one thing you must never do is scan 50 million places, so the first move is a spatial index that turns a point-and-radius into a bounded cell lookup. The reframing to carry into the room: a nearby query is not a distance-sort over all places; it is a bounded-cell fetch over a handful of cells. You never look at the whole map — you compute the ~9 cells the circle touches, pull their candidate lists from memory, and only then pay for exact distance. Whether those cells come from a fixed geohash grid or an adaptive quadtree is the first real tradeoff, and it is a tradeoff about granularity. A fixed grid is simple and shards cleanly, but a one-size cell is too coarse for downtown and too fine for the countryside — a geohash-6 cell holds ~200 places downtown and 2 in a rural county. A quadtree fixes that by subdividing only where places are dense: cap each leaf at ~100 places, and downtown grows a deep subtree of tiny cells while the ocean stays one shallow cell. Granularity then follows density, and the candidate count per query is bounded by construction rather than by a cell size you guessed. The pragmatic answer, developed in the LLD, is geohash for its clean sharding and predictable neighbor math, precision tuned to the common radius, with per-cell candidate caps to contain the pathological downtown cell.

The second tension is read amplification against spatial skew, and the answer is caching — but caching a proximity query is not obvious, because every user's coordinates differ by a few meters, so a cache keyed on raw lat/lng would never hit. The trick is that the cache key is not the user's exact coordinates; it is the cell they fall in. Snap the query point to its geohash cell (and bucket the radius and a coarse time window), and every user in that ~1 km cell issuing the same query shares one cached result. Put numbers on it: at 50,000 QPS a 70% hit ratio drops index-tier load to 15,000 QPS; pushing snapping to a coarser cell would lift the hit ratio toward 85% and cut index load to ~7,500 QPS, but a coarser snap means a user near the cell edge sees results centered on the cell, not on them — the accuracy cost of a cheaper cache. Skew also concentrates load on a few downtown shards; the same cache absorbs most of it, and hot shards get extra read replicas rather than a re-partition.

The third tension is index-update lag versus result accuracy, and it is resolved by splitting attributes into two classes. Location is effectively immutable — a restaurant does not move — so the spatial index is rebuilt rarely and can be treated as static and cache-friendly. Rating and review count drift slowly and feed ranking; a few minutes of staleness there costs nothing, so they are updated asynchronously and the index tolerates lag. "Open now", though, is neither static nor lag-tolerant — so it never lives in the index at all. It is derived at query time from the place's stored hours and the current clock, because baking a per-minute-changing boolean into a spatial index would mean rewriting the index continuously. The memory hook: "open now" is not an index dimension; it is a query-time filter. Static location goes in the index, slow attributes lag gracefully, and the one fast-changing attribute is computed on the fly.

The result is a system whose read path is a cache lookup that, on miss, fans out to ~9 in-memory cells, distance-filters, applies open-now, ranks, and caches the page; whose write path is a rare, batch-friendly update to a durable place store that asynchronously refreshes the index; and whose ranking rides on attributes that are allowed to lag by minutes. The next files take these decisions down to components (HLD) and then to the index structures, the radius algorithm, and the concurrency corners (LLD).