Proximity service (Yelp nearby)
Find businesses near a location. The data barely changes and the queries are heavily concentrated on dense areas, so the design is a read-optimised geo index — geohash, quadtree or S2/H3 cells — replicated and cached, fed asynchronously from the source of truth.
Component labels and connections
- Clients (client) · calls: Load balancer
- Load balancer (loadBalancer) · calls: Search API 1, Search API 2
- Search API 1 (service) · calls: Cell + detail cache, Geo index (read replicas), Business DB
- Search API 2 (service) · calls: Cell + detail cache, Geo index (read replicas), Business DB
- Cell + detail cache (cache) · calls: none
- Geo index (read replicas) (searchIndex) · calls: none
- Business DB (database) · calls: none
Requirements
Functional
- Search businesses within a radius of a point, optionally filtered by category.
- View business details.
- Owners add or update businesses; changes may take minutes to appear in search.
Non-functional
- Search p99 under ~100 ms.
- Read-heavy: ~5,000 searches/s against a few updates per second.
- Highly available reads; eventual consistency for updates is acceptable.
Worked estimates
Search rate
≈ 5,800 searches/s average, ≈ 15k/s peak
100M DAU × 5 searches/day ÷ 86,400
Data
≈ 200 GB of details; the geo index itself (ID + cell + lat/lng ≈ 30 B) is ≈ 6 GB — fits in memory on every replica
200M businesses × ~1 KB
Cell size
a 1 km radius search reads the cell and its 8 neighbours
geohash length 6 ≈ 1.2 km × 0.6 km
Index replicas
3 replicas per region plus headroom; no sharding needed for the index
15k/s ÷ ~5k queries/s per replica (in-memory, 9 cell lookups + filtering)
Write rate
≈ 1/s — rebuilding or patching the index asynchronously is cheap
~100k business updates/day
API
GET /v1/search?lat&lng&radius&category&cursor
Request: radius ≤ 20 km
Response: 200 { businesses[], next }
GET /v1/businesses/{id}
Request: —
Response: 200 { details }
PUT /v1/businesses/{id}
Request: { fields }
Response: 200
Visible in details immediately (cache invalidated); in search after the index catches up.
Data model
- businesses — store: db
businesses is the source of truth, sharded by businessId; the geohash column is derived from lat/lng on write.
The geo index maps cell → business IDs (plus lat/lng for exact distance filtering). It is a read replica of the DB in a different shape, rebuilt or patched from a change stream.
Search results for popular cells are cached for a minute; details are cached until updated.
High-level design
Trace permitted calls in the architecture above, then open the reference canvas to inspect routing.
Deep dives
Geohash, and why you also query neighbours
Geohash interleaves the bits of latitude and longitude and encodes them in base 32, so a prefix is a rectangle and longer prefixes are smaller rectangles (length 6 ≈ 1.2 × 0.6 km). Nearby points usually share a prefix, but not always: two points either side of a cell boundary can have completely different hashes. So a search computes the cell for the point and its 8 neighbours, fetches all candidates, and filters by exact distance.
Choosing a cell size and handling density
Pick the geohash length whose cell is about the search radius. In sparse areas a small radius returns nothing, so expand to a shorter prefix (bigger cells) until enough results come back. In dense areas fixed cells hold thousands of businesses; a quadtree, or Google's S2 cells (a hierarchy on a cube projection), adapt to density. Uber's H3 uses hexagons for uniform neighbour distances.
Keeping the index fresh
Business data changes rarely, so the index is a derived view: a change-data-capture stream from the business DB patches the in-memory index on each replica, with a nightly full rebuild as a safety net. The index lags the database by seconds to minutes, which the requirements allow; details are read from the database (through a cache invalidated on update), so an owner sees their own edit immediately.
Failure scenarios
Everyone searches Times Square
Scenario and expected result
New Year's Eve: one cell receives 30% of all searches.
Expected: The hot cell's results are cached, so it costs one index query per minute. The rest of this scenario is spread uniformly, so the cache hit rate drops overall and the index replicas work harder — they have the headroom.
The geo index is unavailable
Scenario and expected result
The geo index replicas are down from t = 1.5 s to 2.0 s (a bad index build was rolled out).
Expected: Cached cells keep answering; uncached searches time out. Details, which come from the database, are unaffected. A safer rollout would build the new index beside the old one and switch atomically, keeping the old one until the new one is verified.
Index replicas slow down 5×
Scenario and expected result
From t = 1.5 s to 2.3 s index queries take 5× longer — the replicas are rebuilding in the background and competing for CPU.
Expected: Cache hits are unaffected; misses take ~10 ms longer and the index's worker pool gets busier. Because the cache absorbs most of the popular cells, the index never saturates.
Alternative designs
Reference
- Inspect the architecture above and run the same scenario.
No geo index: scan the business table
- A query without an index is a full scan of every business for every search. In the simulated cell the database scans 20,000 rows per search and saturates almost immediately — the reason geo indexes exist.
Reference
- Inspect the architecture above and run the same scenario.
Quadtree instead of fixed geohash cells
- A quadtree splits a square until each leaf holds at most k businesses, so dense Manhattan gets tiny cells and the Sahara one big one: every query reads a similar number of results. It is built in memory at startup (seconds for 200M points) and updated incrementally. Geohash cells are simpler, work as a plain database index, but have very uneven occupancy.
Reference
- Inspect the architecture above and run the same scenario.
Database-native spatial index (PostGIS, R-tree)
- Radius queries in SQL with an R-tree or GiST index, no separate system. Excellent up to a few thousand queries per second per replica; beyond that, read replicas or a dedicated in-memory index take over. Often the right first version.
Clarifying questions
- Maximum search radius?
- Number of businesses and growth?
- How fast must updates appear in search?
- Filters and ranking needed?
Common mistakes
- Computing distance to every business per query.
- Querying only the point's own cell and missing results across the boundary.
- Sharding a small index that fits in memory.
- Synchronously updating the index in the owner's write path.
- Ignoring density differences between cities and rural areas.
Self-assessment rubric
requirements / levels 1-4
- 1/4 'Find nearby places'.
- 2/4 Radius search and details.
- 3/4 Read-heavy ratio, latency, freshness tolerance.
- 4/4 Separates search freshness from detail freshness.
estimates / levels 1-4
- 1/4 None.
- 2/4 QPS.
- 3/4 Index size shows it fits in memory; replica count.
- 4/4 Cell size chosen from search radius.
api / levels 1-4
- 1/4 Search endpoint.
- 2/4 With radius and filters.
- 3/4 Pagination and limits on radius.
- 4/4 Owner update path and visibility semantics.
data model / levels 1-4
- 1/4 Lat/lng columns.
- 2/4 Geohash column with an index.
- 3/4 Source table + derived geo index.
- 4/4 Density handling (quadtree/S2/H3) justified.
high level / levels 1-4
- 1/4 Query the database.
- 2/4 Index + database.
- 3/4 Replicated in-memory index, caches, async updates.
- 4/4 Regional deployment and safe index rollout.
deep dive / levels 1-4
- 1/4 None.
- 2/4 Explains geohash.
- 3/4 Neighbour cells and boundary effects.
- 4/4 Adaptive cells and CDC-based index updates.
wrap-up / levels 1-4
- 1/4 Stops.
- 2/4 Metrics.
- 3/4 Hot cells and index lag as risks.
- 4/4 Index build verification and rollback plan.