System Design Interview: Design a Proximity Service for Nearby Places

Problem and Scope

Design a global nearby-place search service. The catalog contains 50 million restaurants, shops, and public facilities. A user supplies a current position, a radius from 500 meters to 50 kilometers, a category, and an opening-time filter, then receives the nearest 20 results. Search traffic peaks at 200,000 requests per second. Place creation, relocation, and closure peak at 100 updates per second. Read latency must stay below 150 milliseconds at p99.

This problem treats places as slowly changing static entities. Second-by-second driver, courier, or friend locations, matching, and exclusive assignment belong to a different dynamic-location system. Distance means geographic distance over the Earth's surface. Route time, personalization, and advertising auctions are outside the core scope. All counts and SLOs are interview assumptions.

The central problem is a two-dimensional radius query. A normal B-tree over latitude and longitude cannot directly jump to every row inside a query circle. The recommended pattern first uses a spatial index or discrete grid to create a candidate superset, then computes exact distance, filters, sorts, and truncates. A cell hit is only a coarse filter; sharing a cell or neighboring cell does not prove that a place is inside the radius.

What Interviewers Evaluate

The first signal is defining correctness before components. Every result must be inside the radius, pass the filters, and appear in a deterministic nearest-first order. The candidate set must cover places across cell boundaries, and exact distance must verify the coarse result. Querying only the user's geohash misses a business tens of meters away across an arbitrary cell edge.

The second signal is choosing an index from the update pattern. Static businesses can start with PostGIS GiST, an R-tree, or a database's native distance index. When read traffic and global routing justify it, places can be mapped into H3, S2, or geohash cells. Merely saying “use Redis GEO” does not explain circle coverage, resolution, hot spots, or exact distance.

The third signal is recognizing spatial skew. Oceans and rural cells are nearly empty, while one downtown cell may be extremely hot. Uniform latitude-longitude ranges do not produce uniform shards. A useful design routes by a coarse spatial prefix, splits dense cells, and adds replicas for read-hot cells. Large-radius queries cross shards, so one lookup cannot always be assumed to hit one node.

Finally, pagination, consistency, and failure must agree. For distance pagination, the user coordinates, filters, catalog version, last distance, and place ID are part of the cursor contract. Updates or a shard timeout can change the result set. A strong answer declares snapshot or best-effort semantics and makes partial results recognizable.

Questions to Clarify Before Answering

• Are locations static or continuously moving? The 100-update-per-second peak supports caching and asynchronous indexing. Moving entities need tighter freshness, a write-optimized index, and matching consistency.
• Does “nearest” mean geographic distance or travel time? This design uses geographic distance. Travel time needs a road graph and a separate ETA service, normally applied to a small coarse candidate set.
• Must results be complete, or are 20 approximate candidates acceptable? This problem requires correct radius filtering and a deterministic nearest 20 among indexed places. Cells may only generate candidates.
• How fresh must opening status be? Location and category can tolerate minute-scale propagation. If temporary closure needs seconds, keep it in a separate short-TTL overlay instead of giving the static catalog one mixed promise.
• Is deep pagination required? Nearby search usually needs only a few pages. This design caps a result session at 100 places. Exporting every result within 50 kilometers needs an asynchronous or regional-browse API.
• May a cross-shard failure return partial data? The exploration API may return partial=true with missing regions. A strict caller may fail and retry. Partial data must not be presented as the complete nearest set.

30-Second Answer

“I would separate the catalog write path from the search path. Versioned place records enter the source-of-truth catalog and asynchronously update a spatial index. Each place stores exact coordinates, a coarse routing cell, and a search-resolution cell. A query validates its radius and filters, then uses an H3, S2, geohash cover or a PostGIS distance index to obtain a candidate superset. It computes exact spherical distance, filters, and sorts by (distance, place_id) before taking 20.

The coarse prefix routes to shards. Dense cells can split, and a cross-cell query visits a bounded number of shards in parallel before a global top-k merge. Cache keys include the cells, radius bucket, filters, and catalog version; a versioned move invalidates both old and new cells. A cursor binds the original query and catalog snapshot. I would verify boundaries, the date line, poles, hot cities, relocation, shard timeouts, and stale caches while measuring correctness and p99.”

Step-by-Step Deep Dive

Step 1: Fix the API, model, and invariants

The API accepts bounded radii, valid coordinates, approved filters, and a small page size. The response includes computed distance, catalog version, completeness, and a continuation cursor.

GET /v1/places/nearby?lat=&lng=&radius_m=&category=&open_at=&limit=&cursor=

Place {
  place_id, lat, lng, search_cell, routing_cell,
  category, status, hours_version, location_version, updated_at
}

Cursor {
  query_hash, catalog_version, last_distance_m, last_place_id
}

Maintain four invariants: every result satisfies radius and filters; candidate generation cannot omit a point inside the circle; final order is (distancem, placeid); and an old location version cannot overwrite a new one. Coordinates use one declared reference system, reject invalid ranges, and use meters internally.

Step 2: Choose the simplest spatial index that meets the target

A first version can use a relational database with a spatial index. A radius query uses an indexable bounding shape to reduce the set, then an exact-distance function to filter it. The official earthdistance documentation explicitly says the indexable box contains some points outside the requested great-circle distance, so a second distance check is required. This candidate-superset rule is independent of one vendor.

When one database topology cannot handle global read traffic or explicit spatial routing is needed, encode each place into fixed-resolution H3, S2, or geohash cells. Convert the query circle into a covering set of cells, read each cell's inverted list, deduplicate, and refine. H3's hierarchy changes resolution efficiently, but geographic containment across parent and child cells has approximation concerns. Exact point-to-point verification still decides inclusion.

One fixed resolution creates opposite problems: large cells amplify candidates, while tiny cells make a 50-kilometer query enumerate too many cells. Select from a small set of predefined resolutions based on radius and precompute those levels for each place, or route large radii through a coarser index. Candidate amplification, fanout, and p99 load tests choose the levels.

Step 3: Execute candidate search and global top-k

The query service converts the circle to candidate cells, covering every intersecting cell rather than just the center. It reads coarse-filtered place IDs and coordinates from each cell in parallel under an overall deadline and per-shard budget. It deduplicates by place_id, computes exact geographic distance, removes points outside the circle, and applies authorization, status, and category filters.

Each shard may return its local top k, but the truncation needs a proof. If every shard orders by the same final distance and returns at least the global k, a shard's item k+1 cannot enter the global top k. The aggregator merges with a size-k max heap. Work is linear in returned candidates, with O(k) merge memory.

A large radius or dense downtown can produce too many candidates. The service sets a candidate budget but cannot silently truncate and claim exactness. It can choose a finer grid, push category filtering down, expand in rings until 20 results exist and the minimum possible distance from every unsearched region exceeds the current twentieth result, or return an explicit resource-limit error.

Step 4: Budget sharding, hot spots, and capacity

Map cell directories to shards with a coarse routingcell, instead of randomly sharding by placeid, which would broadcast every spatial query. A directory service maintains the routing table and epoch. A query uses one epoch and retries on a routing change so a cell split cannot create a gap.

If one search-index record including ID, coordinates, filter fields, and overhead is estimated at 128 to 256 bytes, 50 million records require roughly 6 to 12 GiB before replication, multiple resolutions, and database overhead. This magnitude can be partitioned and served by read-optimized nodes, but it does not prove that any particular database will meet the target.

At 200,000 QPS and an illustrative average fanout of six cell reads, the backend sees about 1.2 million cell reads per second. Caching and batch reads must reduce operations. Add replicas based on read heat and split dense cells into children. Merging sparse cells changes storage and routing only; geometric coverage still controls correctness.

Step 5: Make writes, caches, and consistency converge

After ownership validation, the place service updates the source record and increments location_version. A change event contains old cell, new cell, and version. The index consumer writes the new version into the new cell before removing the old cell. Reads deduplicate by version, making replay safe and preventing a delayed delete from letting stale data win. A cross-shard move exposes bounded index lag and converges by version instead of requiring an instantaneous distributed transaction.

Use two cache layers: cell-to-candidate IDs and complete place objects. A candidate key includes index version, cell, category, and status bucket. A final-response cache must also include a coordinate bucket, radius bucket, filters, and catalog version, so it usually has lower hit rate. Updates invalidate both old and new cells, while a short TTL bounds a lost invalidation event.

If open_at changes every minute, do not purge every spatial cache each minute. Cache static candidates and opening rules, then evaluate rules at query time. Temporary closures live in a small fresh overlay. Opening-state churn therefore does not rebuild the geographic index.

Step 6: Define pagination and failure semantics

The cursor hashes coordinates, radius, filters, and catalogversion, then stores the last (distancem, place_id). A next-page call rejects different query parameters. If short-lived snapshots are supported, it reads the same catalog version. A best-effort API instead documents that concurrent updates may create duplicates or omissions and lets the client deduplicate IDs.

Each shard receives a deadline shorter than the 150-millisecond end-to-end target. After one shard times out, the response cannot be called the global nearest 20 because the missing shard may contain closer places. An exploration API may return partial=true, the missing cells, and a retry cursor. A strict client receives a clear unavailable result. Circuit breaking isolates the failed shard, not the entire global index.

Regional deployment should prefer a complete local read replica or geographic partition. Cross-border policy governs place metadata and audit, while even public business coordinates require authorized sourcing. Failover may use only a region with a sufficiently fresh index and must return as_of; it cannot fall back to a catalog table scan during an incident.

Step 7: Verify with geometric counterexamples and faults

For small test data, use brute-force exact distance as an oracle. Generate random points and circles and compare result sets. Target cell edges and corners, positive and negative 180-degree longitude, polar regions, a point exactly on the radius, duplicate coordinates, zero results, tied positions 20 and 21, and a relocation across cells. Assert no false negatives, no outside points, and stable tie-breaking.

Load tests separately cover empty regions, normal cities, and an extremely dense hot spot. Measure cell fanout, candidate amplification, exact-distance computations, cache hit rate, shard p95/p99, merge time, and end-to-end p99. Faults include one slow cell replica, a routing-epoch change, a lost invalidation, consumer replay, an interrupted cross-shard move, and regional failover.

Roll out with shadow queries. Send a small traffic sample to both the new index and a trusted old implementation, then compare the top-20 set, order, distance, and missing rate. A latency improvement cannot excuse false negatives; omitting a correct nearby place is an index-correctness failure.

Strong Sample Answer

“I first scope this to static-place retrieval, not moving-driver matching. A place catalog stores exact coordinates and a monotonic location version, then emits events to a spatial index. Reads do not sort the whole table by a latitude-longitude expression. They convert the circle into cells that fully cover it. I can begin with a PostGIS spatial index and introduce H3, S2, or geohash when global traffic needs explicit spatial routing. Cells only coarse-filter; exact geographic distance decides inclusion, followed by stable sorting on distance and place ID.

A coarse cell routes to a shard. Dense cells split and read-hot cells gain replicas. A query reads bounded shards in parallel, each returns a local top-k, and the aggregator produces the global top-k. Excess candidates trigger more selective filtering or ring expansion, never silent truncation. Cell candidates and place objects are cached with index versions. A move invalidates both cells, and location versions make replay converge.

The cursor binds coordinates, radius, filters, catalog version, and the last distance/place ID. A shard timeout means global nearest results are unprovable, so an exploration API marks the response partial and names missing cells while a strict API fails. For verification, brute-force distance is the oracle. Random comparisons and targeted cell-edge, date-line, polar, tie, move, and routing-change cases prove correctness before hot-city load and fault tests prove 150-millisecond p99.”

Common Mistakes

• Querying only the center geohash → a circle crossing the cell edge loses close neighbors → read every intersecting cell and verify exact distance.
• Treating neighboring cells as inside the radius → a far cell corner may exceed the radius → use the grid for candidates and spherical distance for inclusion.
• Randomly sharding by place ID → every nearby query broadcasts globally → route by coarse spatial prefix, then split or replicate hot cells.
• Using one finest resolution → small-radius precision produces explosive large-radius fanout → use a few controlled levels chosen from measurements.
• Caching by coordinates alone → radius, category, or catalog versions contaminate one another → put the complete query contract and version in the key.
• Deleting before adding during a move → a consumer failure temporarily removes the place → write the new version first, delete the old cell later, and deduplicate by version.
• Calling a response “nearest 20” after a shard timeout → the missing shard may contain closer results → mark partial data or fail strict requests.
• Testing only dense downtown data → boundary, polar, and sparse-region bugs remain hidden → use a brute-force oracle, property tests, and targeted geometric counterexamples.

Follow-up Questions and Answers

Follow-up 1: Why not use PostGIS for the entire system?

It is a good first choice. A spatial database already supplies correct index candidates and distance functions, so the team can ship a reliable system with fewer components. Introduce a discrete grid and separate search tier only after traffic, global routing, hotspot isolation, or cost measurements show that the database topology misses the target. Shadow migration must compare complete result sets, not just latency.

Follow-up 2: How do you prove the cell cover cannot miss a place inside the circle?

Use the library's circle or polygon covering operation rather than guessing a neighbor count. The cover may include extra cells, but it must include every cell intersecting the circle. Exact distance removes false positives afterward. Compare against a full-scan oracle over random circles, cell corners, the date line, and polar areas. Any false negative blocks release.

Follow-up 3: What if a 50-kilometer query covers thousands of fine cells?

Switch to a precomputed coarser level so cell count stays bounded, then rely on pushed-down filters and exact refinement. Ring expansion can stop once 20 results exist and the minimum possible distance of every unvisited region exceeds the current twentieth result. If a large-radius request still exceeds its resource budget, reject it or make it asynchronous rather than silently searching less.

Follow-up 4: How would this become nearby-driver matching?

The problem changes materially. Driver locations need second-scale writes and expiry, an index partitioned by city or cell, and protection against out-of-order updates and ghost drivers. After candidate retrieval, ranking needs ETA, state, and fairness. Final assignment requires a versioned conditional update or single owner to prevent double dispatch; an eventually consistent spatial index cannot reserve the driver.

Follow-up 5: Will minute-by-minute opening status create an invalidation storm?

Separate static spatial candidates from dynamic status. Cell caches hold IDs, locations, and categories. Query nodes evaluate opening rules for open_at, while temporary closures come from a small fresh overlay. Only location or category changes invalidate the spatial candidate cache. Monitor overlay freshness and return unknown status or a business-approved degradation when it is unavailable.