Case study: Proximity service (Yelp nearby)
Design a read-heavy nearby search service: geohash and quadtree spatial indexes that fit in memory on every replica, 9-cell neighbour lookups, and async CDC updates.
35 min9 steps
By the end you can
- Estimate search QPS, business dataset size and why the entire geo index fits in memory without sharding
- Explain geohash boundary issues, 9-cell neighbour queries and when to use a quadtree for uneven density
- Design a multi-tier read path with cell caching and replicated in-memory geo indexes fed asynchronously from the database
- Predict system behaviour during a hot-cell event, a bad index rollout or background index rebuild slowdowns
Requirements
Nearby businesses
- Radius/category search; detail views; owner edits
Search p99 <100 ms
- High read availability; eventual search freshness; immediate detail invalidation
Estimates
Searches/s
5,800
100M users / 5 / 86,400; 15k peak
Edits/s
~1
100k/day
Business details
200 GB
200M / 1 KB
Geo index
6 GB
200M / 30 B
Regional replicas
3-4
~5k queries/s each; leave headroom
API
GET /v1/search?lat&lng&radius&category&cursor
- Radius <=20 km; businesses + next cursor
GET /v1/businesses/{id}; PUT /v1/businesses/{id}
- Write DB; invalidate biz:{id}; index catches up
Data model
Database
- businessId, geohash, lat/lng, category, rating; shard by businessId
Read replicas
- CDC geoindex; cell:{geohash} cache 60s; biz:{id} cache
High-level design
Put the steps of an uncached nearby search in order.
- 1The Search API stores the cell result in the cache with a 60-second TTL and returns 200
- 2The Search API filters out candidates whose exact distance exceeds the radius and sorts the rest
- 3The Search API converts (lat, lng, radius) into the centre geohash cell and its 8 neighbouring cells
- 4The Search API fetches candidate businesses for those cells from an in-memory geo-index replica
- 5The Search API checks the cell cache and misses
Deep dive: boundary effects and adaptive cells
Geohash boundaries
- Query every cell intersecting radius; filter exact Haversine distance
Adaptive cells
- Quadtree/S2 splits dense areas; fixed cells vary in occupancy
Alternatives
proximity-scan
- 20k rows/miss; saturated DB; <90% goodput
Quadtree
- Adaptive density; extra implementation
PostGIS GiST
- Simple V1; spatial SQL; replica throughput ceiling
Failure scenarios you can run
Inject
Times Square: 30%
Observe
Hot cell hits cache
Result
Long tail reaches geo replicas
Inject
geoindex down: 0.5s
Observe
Uncached searches time out
Result
Cached searches/details survive; blue/green index swap
Inject
Index rebuild: 5x slower
Observe
Miss work rises ~2ms to ~10ms
Result
Hot-cell cache keeps index below saturation
Wrap up
Watch
- Search p99, cache hit rate, CDC lag
Size
- Read-heavy workload; full in-memory geo replicas
Score each stage from 1 to 4.
Answer this step to continue.