← CatZep/Engineering Guides/System Design/Search, Geo & Logistics

Designing a Proximity Service

A system design interview guide to building a Yelp-style "nearby places" service that, given a location, returns the businesses around you fast — by indexing the world spatially instead of scanning every row.

A proximity service answers a deceptively simple question: "what is near me?" Type that into a maps or reviews app and you expect a list of restaurants, gas stations, or pharmacies within a few kilometers, sorted by distance, in well under a second. The naive way to compute this — store every place with its latitude and longitude and, on each request, look at all of them — falls over the moment you have millions of places and thousands of queries per second. The interesting part of the design is not the distance formula; it is the spatial index that lets you look at a few hundred candidate places instead of all of them. This guide builds up from why the obvious query does not scale, through the indexing options an interviewer expects you to compare, to the read-heavy serving architecture that ties it together.

Concepts to understand first

Each definition includes a concrete example and the condition under which the mechanism is useful. You can read this guide without opening another guide.

1. Requirements and Clarifying Questions

Before drawing boxes, spend the first few minutes agreeing on what the system must do. The questions below are the ones that change the design; the answers in brackets are a sensible default if the interviewer lets you choose.

• What is being searched? Fixed places such as restaurants and shops [yes], or moving objects such as drivers [no, that is ride matching]?
• How is the radius chosen? A fixed set such as 0.5, 1, 2, 5 and 20 km [yes], or any value?
• How are results ranked? By distance only [yes for the core], or also by rating, open-now and ads?
• How fresh must edits be? Does a new or edited business need to show up instantly [no, the next day is fine]?
• How big? How many places and how many users [200 million places, 100 million daily users]?

2. Back-of-the-Envelope Estimation

200 million place entries at a nominal 16 bytes of ID+cell payload total 3.2 GB, but this excludes coordinates, index/tree/hash overhead, allocation, replicas, and snapshots. One-server fit is a hypothesis to benchmark, not a conclusion from payload alone. Place details at 1 KB each are 200 GB payload.

100M users×5 searches/day averages 5787 QPS; a stated 3× peak gives 17,361 QPS. Read replication may suffice if measured index memory and CPU fit; shard by geography or another scheme only when actual capacity/skew/availability requires it. Track update lag and stale closed/moved places.

3. API and Data Model

Keep the public API small. One search endpoint and a standard CRUD set for business owners is enough.

GET  /v1/search/nearby?lat=37.776&lng=-122.416&radius=500&limit=20&cursor=...
  -> 200 { "places": [ {"id": 42, "name": "Blue Cafe", "distance_m": 180, ...} ],
           "next_cursor": "..." }

GET    /v1/places/{id}          # full details
POST   /v1/places               # owner creates (authenticated)
PUT    /v1/places/{id}          # owner updates
DELETE /v1/places/{id}

Store two things separately: the place details, which are large and rarely change, and the small geo index, which is what every search touches.

-- source of truth for details
CREATE TABLE places (
  id          BIGINT PRIMARY KEY,
  name        TEXT, category TEXT, address TEXT,
  lat         DOUBLE, lng DOUBLE,
  rating      REAL,  updated_at TIMESTAMP
);

-- what the search reads: one row per place, keyed by cell
CREATE TABLE geo_index (
  geohash     CHAR(8),      -- store the long form; query any prefix
  place_id    BIGINT,
  PRIMARY KEY (geohash, place_id)
);

4. The Range Query Problem

Start with the design everyone reaches for first: a table of places, each with a latitude and a longitude, and a query that asks for everything inside a bounding box around the user. In SQL it looks like a simple range filter on two columns.

SELECT id, name, lat, lng FROM places
WHERE lat  BETWEEN :user_lat - d AND :user_lat + d
  AND lng  BETWEEN :user_lng - d AND :user_lng + d;

This works on a small dataset and is completely correct. The trouble is performance at scale. Latitude and longitude are two independent dimensions, and a standard B-tree index can only order rows along one of them at a time. An index on lat narrows the search to a horizontal band of the planet; an index on lng narrows it to a vertical band. Neither narrows it to the small square you actually want. The database ends up scanning one long band and checking the other coordinate row by row, so the work grows with the total number of places, not with how many are genuinely nearby.

The root cause is that nearness in two dimensions has no natural single ordering. Two places can be close on the map yet far apart in any one-column sort. To make "near me" cheap, you need a way to map 2D location into something a single index can order, so that points which are close on the ground end up close in the index. That is exactly what spatial indexes do, and the three approaches below are the ones an interviewer will want you to weigh against each other.

5. Geohash

A geohash interleaves longitude/latitude subdivision bits into base32 cells. Shared prefixes identify the same rectangle, but nearby points can lie across a high-level cut with unrelated prefixes. Dimensions vary by precision and latitude; odd bit counts give unequal axis subdivisions, not a universal 'odd character length means rectangles' rule.

Query a conservative covering of every cell intersecting the radius's bounding region, then refine distances. A query cell plus eight neighbors suffices only if radius fits the cell geometry at that latitude and wrap/pole handling is correct. For larger radii, finer cells, or polar cases, enumerate a larger covering or use S2/H3/PostGIS with documented geometry semantics.

Haversine gives spherical great-circle distance, not exact ellipsoidal geodesic or road travel distance. Ranking by walking/driving ETA requires routing after candidate filtering. Validate finite lat/lon, permitted bounds, positive radius, and geohash precision.

6. Quadtree

A quadtree subdivides a rectangle into four children where density is high. Range search visits all children whose bounds intersect the query; radius search uses a conservative bound and distance refinement. The result can touch many leaves, so per-leaf capacity does not bound the entire query cost.

Coincident points may never separate: enforce max depth/minimum cell size and allow overflow leaves. Define half-open boundary ownership to avoid lost/duplicated points. Updates and replicated publication need consistent snapshot/version handling; adaptive resolution trades indexing complexity for reduced density skew.

7. Grid and Cell Systems

The third family treats the planet as a set of named cells produced by a well-defined cell system, the best known being Google's S2. S2 projects the sphere onto the six faces of a cube and recursively subdivides each face into a hierarchy of cells, giving every cell a 64-bit id. Like a geohash, an S2 cell id is a single sortable number whose ordering preserves locality, so nearby cells have nearby ids; like a quadtree, the cells form a hierarchy you can query at coarse or fine levels.

Uber's open-source H3 is the other well-known cell system. It tiles the globe with hexagons (plus 12 pentagons per resolution, which are needed to close the sphere). A hexagon's six neighbors are all the same distance from its center, while a square has 4 edge neighbors and 4 farther corner neighbors, so "k rings of hexagons around me" approximates a circle well. That makes H3 popular for ride-hailing and delivery analytics, such as surge pricing per hexagon.

What a mature cell system buys you over a hand-rolled grid is correctness on a sphere and a clean, ready-made notion of "the cells covering this region." Given a query area, the library returns the small set of cell ids that cover it, and you look up places tagged with those ids. The two-column lat/long range query becomes a set-membership test on a handful of cell ids — exactly the kind of thing a single index handles well.

8. The Search Algorithm

Choose a distance/geometry model first: planar metres for a local toy example, spherical great-circle distance for an approximation, or ellipsoidal geodesic distance for tighter geographic accuracy. Driving/walking time is a separate routing model.

1. Build a conservative covering of the radius's bounding region, including every intersecting cell and proper pole/antimeridian handling.
2. Read candidates from the index, deduplicating IDs if multiple covers/levels overlap. Bounds and density determine cost; leaf capacity alone does not bound an entire query.
3. Compute distance under the chosen model and remove candidates outside the requested radius.
4. Apply current eligibility/visibility, rank with deterministic ties, and paginate with an explicit snapshot/freshness policy.

A fixed cell plus eight neighbors is sufficient only under documented cell-size/radius/location assumptions. Haversine is a spherical calculation, not exact ellipsoidal distance. Benchmark candidate volume and stale-update handling rather than assuming a cell lookup always returns a small bounded set.

9. Handling Uneven Density

Real-world places are not spread evenly. A dense city center may hold orders of magnitude more businesses per square kilometer than a rural area, and this lopsidedness is what punishes a one-size-fits-all index. With fixed cells, a downtown cell can return tens of thousands of candidates while a rural cell returns three — the same query costs wildly different amounts depending on where you stand.

This is precisely where the quadtree earns its keep: because it splits busy regions finely and leaves empty regions coarse, every leaf holds roughly the same bounded number of places. A query in a dense downtown descends a few extra levels and still lands on a small candidate set, so cost stays predictable everywhere. The fixed-grid alternative forces an awkward compromise on cell size, and the usual mitigations — capping results per cell, or maintaining different precisions for different regions — are really just approximations of what the quadtree does for free.

10. Precomputation and Caching

A proximity service is overwhelmingly read-heavy, and most of the work is the same from request to request: the set of places near a given area changes slowly, while queries for that area arrive constantly. That mismatch is an invitation to precompute and cache. Rather than recomputing candidate sets on every request, you can keep per-cell results warm and serve repeated queries straight from memory.

• Index at write time. Compute each place's cell id (geohash, quadtree leaf, or S2 id) when the place is created or moved, not at query time. The expensive encoding happens once per place, not once per request.
• Cache by cell. Use the cell id as a natural cache key. The list of places in a popular cell is a perfect candidate for an in-memory cache, since many users querying the same neighborhood hit the same cells.
• Tolerate slight staleness. Businesses do not open and close by the second, so a cache that lags by minutes is fine. This loose freshness requirement is what makes aggressive caching safe.

11. Serving Architecture

Putting it together, the production shape reflects the read-heavy nature of the workload: a tier of stateless servers, a cache in front of the spatial index, and a separate, lower-traffic path for updating places. Reads scale horizontally; writes are comparatively rare and can be handled more deliberately.

• Stateless query servers. They receive "nearby" requests, compute the query cells, consult the cache, fall back to the spatial index in the database on a miss, run the exact-distance filter, and return ranked results. Being stateless, they scale out simply behind a load balancer.
• Spatial index + cache. The geohash/quadtree/S2 index lives in the database (or in memory for a quadtree), fronted by a cache keyed on cell id so hot neighborhoods are served without touching the database.
• Place data store. The source of truth for place details — name, category, rating, hours — alongside the cell id used for lookups.
• Write/ingestion path. A separate path adds and updates places, recomputing the cell id and invalidating any cached cells. Kept distinct from reads so a burst of edits never slows queries.

The recurring theme is the split between a cheap, cacheable coarse lookup and an exact fine filter, served by a fleet that is mostly read replicas and caches. That separation — plus indexing at write time so reads stay light — is what lets a proximity service answer "what is near me?" in milliseconds across millions of places.

12. Failure Modes

13. Tradeoffs and Alternatives

Worked example: neighbors across a grid boundary

Use a planar metre grid for the learning model; production geography requires globe-aware covering.

Run a small, testable model

Download concepts.py. It uses only the Python 3.10+ standard library. From the directory where you saved it, run:

python3 concepts.py geo
python3 concepts.py test

The grid model tests boundary neighbors and an expanded radius against a brute-force reference.

The program contains deterministic assertions and failure traces. It is a learning model, not a production service: it does not implement network consensus, distributed durability, authentication, or third-party delivery. Read its contracts and try changing an input before extending it.

14. A 45-Minute Interview Walkthrough

15. Common Mistakes

16. Summary

A proximity service is fundamentally a spatial-indexing problem dressed up as a search feature. The design is a chain of choices that each reduce work:

17. Check Yourself

1. Why can't a composite B-tree index on (lat, lng) answer a bounding-box query efficiently?
   Answer

   The index is sorted by lat first. It can narrow to the latitude band quickly, but inside that band rows are not sorted by lng in one contiguous run, so the database scans the whole band and filters longitude row by row.

2. A user searches with a 2 km radius. Which geohash length do you pick, and why?
   Answer

   Length 5. Its cell is about 4.9 km × 4.9 km, which is at least the radius, so the 3×3 block covers the whole circle. Length 6 cells (0.61 km short side) are smaller than the radius, so 3×3 would not be enough.

3. Two coffee shops are 20 m apart but their geohashes share no prefix. How is that possible, and how does the search still find both?
   Answer

   They sit on opposite sides of a major cut such as the equator or the prime meridian, where the first bit already differs. The search includes the 8 neighbor cells of the query cell, so the shop across the cut is still in the candidate set.

4. When would you choose a quadtree over geohash?
   Answer

   When density is very uneven and you need every lookup to return a bounded number of candidates, for example a mix of dense cities and empty countryside. The cost is an in-memory tree you must build and rebuild.

5. Your index is 3.2 GB. Do you shard it? What do you do instead?
   Answer

   No. It fits in RAM on one server. Replicate it across many servers for read throughput and availability. Shard by region only when it no longer fits.

6. Why is caching by cell id so effective here?
   Answer

   Many users in the same area query the same few cells, and place data changes slowly, so a cached cell list is reused many times before it goes stale.

18. Key Terms

Geohash

A string encoding a rectangular latitude/longitude cell by interleaving longitude and latitude subdivision bits and representing them in base32. Longer shared prefixes identify a smaller shared cell. Example and limits above.

Quadtree

A region tree splits a rectangle into four children when it is crowded, allowing smaller leaves in dense areas. Range search visits only children whose bounds intersect the query. Example and limits above.

S2

Google's library that projects the sphere onto a cube and numbers cells along a Hilbert curve with 64-bit ids.

H3

Uber's hexagonal hierarchical grid system.

Haversine

The formula for great-circle distance between two lat/lng points on a sphere.

Covering

The set of cells that together contain a query region.

Boundary problem

Nearby points that fall in different cells; solved by also searching neighbor cells.

Thundering herd

Many requests missing the cache at once and all hitting the database.

19. Further Reading

• Gustavo Niemeyer's original geohash description (2008), and the Wikipedia "Geohash" article for the bit layout and cell-size table.
• R. A. Finkel and J. L. Bentley, "Quad Trees: A Data Structure for Retrieval on Composite Keys," Acta Informatica, 1974.
• The S2 Geometry library documentation (s2geometry.io) and the H3 documentation (h3geo.org).
• PostGIS documentation for ST_DWithin and GiST indexes, a real database approach to the same problem.
• Alex Xu and Sahn Lam, System Design Interview, Volume 2, chapter "Proximity Service."