#31 Points of Interest (POI) / Yelp — Solution

✦ AI-Generated Solution · System Design · Comprehensive Find nearby POIs at scale: 500M POIs, 100K QPS, p99 < 100ms, global. Across the reported experiences the interviewer drills hardest on the geo index (geohash vs quadtree), index building, and sharding.

1. Requirements

Functional

• nearby(lat, lng, radius) and nearest_k(lat, lng, k) over POIs (restaurants, shops…).
• Return POI details (name, category, rating).
• Update business info / add-remove POIs.

Non-functional

• 100K QPS, read-heavy (≫ writes).
• p99 < 100ms; global distribution.
• Eventual consistency for POI details is fine; spatial results must be correct.

2. Capacity

• 500M POIs × ~1KB ≈ 500GB of metadata → fits a sharded DB; the index is the interesting part.
• 100K QPS read → heavy caching + replicas; writes are comparatively rare (business updates).

3. The Core Problem: Spatial Indexing

A B-tree on (lat, lng) can't answer "nearby" efficiently (2D range). You need a spatial index that maps 2D → 1D or partitions space:

Recommendation: Geohash as the primary, shardable, cacheable index for "nearby in a radius"; mention quadtree/S2 when the interviewer pushes on dense-area adaptivity or exact nearest-N. Most strong answers lead with geohash and discuss quadtree as the trade-off.

Handling the geohash edge problem

A POI just across a cell boundary can be closer than ones inside your cell. Always query the target cell plus its 8 neighbors, merge candidates, then sort by true haversine distance and take the radius/k.

def nearby(lat, lng, radius):
    precision = precision_for_radius(radius)         # coarser cell for larger radius
    cell = geohash.encode(lat, lng, precision)
    cells = [cell] + geohash.neighbors(cell)         # 3x3 block -> fixes edge cases
    candidates = []
    for c in cells:
        candidates += index.range_scan(prefix=c)     # shard-local prefix scan
    return sorted(candidates, key=lambda p: haversine(lat, lng, p))[:K]

4. Architecture

• Geo Query Service computes the geohash cells and fans out prefix scans.
• Geo Index is sharded by geohash prefix so a query touches few shards; POIs are co-located by region.
• POI DB is the source of truth; an Index Builder (batch + streaming) keeps the index current.
• Redis caches hot cells (popular city centers) — this is what carries the 100K QPS.

5. Sharding & Index Building

• Shard by geohash prefix (region) → spatial locality, queries stay shard-local. Beware hotspots (Manhattan): split hot prefixes into finer sub-shards, and load-balance with replicas.
• Index build: initial bulk build from the POI DB (MapReduce/Spark over all POIs → geohash → index). Keep it fresh via a CDC/stream from POI writes so adds/edits/moves update the index incrementally.
• Avoid sharding purely by poi_id for the index — it would force every query to fan out to all shards.

6. Read & Write Paths

• Read: geohash the request → check Redis for the cell block → on miss, scan index shards + enrich details from POI DB → cache → return distance-sorted results.
• Write (efficient updates, called out in Experience 4): update POI DB → emit CDC event → index builder updates the affected geohash cell(s) → invalidate that cell's cache entry. Moving a POI = remove from old cell, add to new cell.

7. Scaling & Global

• Read replicas + aggressive cell caching absorb the read-heavy 100K QPS.
• Geo-distribute: serve users from the nearest region; POIs are inherently region-partitioned.
• CDN/edge cache for static POI detail payloads.

8. Summary