Courses › System Design › Question Breakdowns

Design Yelp (Nearby Places)

Geospatial indexing with grids, geohashes and QuadTrees, and sharding the index.

Design a proximity service like Yelp: given a location, find nearby places (restaurants, shops, theaters) and show their reviews. It's the standard geospatial indexing question: why two B-tree indexes on latitude and longitude don't work, and how grids, geohashes and quadtrees do.

Requirements

Functional

  • Users can search for places near a location within a radius, optionally filtered by category
  • Users can view a place and its reviews (text, photos, rating)
  • Business owners can add, update and remove places

Out of scope: reservations, recommendations, real-time moving objects (that's the Uber breakdown).

Non-functional

  • Low-latency search (< 200ms)
  • Very read-heavy: searches vastly outnumber place edits, and places rarely move
  • Scale: ~200M places worldwide, ~20k searches/second at peak
  • Eventual consistency is fine: a new place may take a minute to appear in search

Core Entities

  • Place: id, name, lat, lng, category, rating, review count, hours, address (~1 KB per row)
  • Review: place, user, rating, text, photos

API

GET  /v1/search?lat=&lng=&radius=2000&category=coffee&sort=distance&pageToken=
→ { places[]: { id, name, category, rating, distance, thumbnail }, nextPageToken }
GET  /v1/places/{id}                       → place + recent reviews
POST /v1/places/{id}/reviews  { rating, text, photoIds[] }

High-Level Design

user = client "Client" @0,1
lb = service "Load Balancer" @1,1
search = service "Search Service" @2,0
place = service "Place / Review\nService" @2,2
geo = service "Geo Index\n(in memory)" @3,0
cache = cache "Cache" @2,1
db = store "Places & Reviews DB" @3,2
user -> lb
lb -> search, place
search -> geo : nearby IDs
search -> cache
place -> cache
place -> db
db --> geo : periodic rebuild

Search finds place IDs in an in-memory geo index, then loads their details from the cache or database. Place and review writes go to the database, and the index catches up periodically.

Deep Dives

1. Why not just SQL?

SELECT * FROM places
WHERE lat BETWEEN :lat - :d AND :lat + :d
  AND lng BETWEEN :lng - :d AND :lng + :d;

A B-tree index helps with only one of the two ranges. The latitude index returns a stripe around the whole planet (every place in that latitude band, from Lisbon to Beijing), and the longitude check filters it row by row. With 200M rows that stripe holds millions of places. The fix is a key that keeps places near each other in both dimensions close together in the index.

2. Fixed grids

Split the map into equal cells, store each place's cell ID, and index it. With cells about as big as the search radius, a search reads the user's cell plus its 8 neighbors, then filters by exact distance.

Geohash is the usual way to name cells: it interleaves the bits of latitude and longitude into a string, so a longer shared prefix means a closer location. 6 characters give cells of roughly 1.2 km × 0.6 km. The index is just (geohash6, place_id) in any ordered store, and a search is nine prefix lookups.

The problem: places aren't evenly spread. A cell in midtown Manhattan holds thousands of restaurants while a cell in rural Montana holds none, so any fixed cell size is wrong somewhere.

3. QuadTrees: grids that adapt

Start with one cell for the whole world, and split any cell holding more than a capacity (say 100 places) into four quadrants. Dense cities end up with many tiny cells, and empty areas stay as a few big ones.

world = service "World\n(over capacity)" @1.5,0
nw = service "NW" @0,1
ne = service "NE (dense)" @1,1
sw = service "SW" @2,1
se = service "SE" @3,1
a = store "leaf: 64 places" @0,2
b = store "leaf: 97 places" @1,2
c = store "leaf: 31 places" @2,2
d = store "leaf: 88 places" @3,2
world -> nw, ne, sw, se
ne -> a, b, c, d
  • Search is a range query: descend only into quadrants that intersect the search circle's bounding box, collect places from the leaves you reach, then filter by exact distance. Nothing special is needed to find neighbors.
  • Memory: a leaf entry is an ID plus two coordinates, ~20 bytes, so 200M places is ~4 GB, and ~2M leaves plus their parents add well under 1 GB.
  • Updates: insert into the leaf and split it if it overflows. Since places rarely change, many systems simply rebuild the tree from a snapshot and swap it in.

[!TIP] Geohash is the other common answer Geohash cells live happily in a database index or Redis (GEOSEARCH is built on geohashes), and they shard by prefix. QuadTrees adapt to density but live in application memory. Google's S2 and Uber's H3 are production-grade cell systems with better shapes near the poles. Knowing two of these, and why you'd pick one, is ideal.

4. Partitioning the index

At ~5 GB, the whole index fits in one server's memory, so the first answer is don't partition: replicate. Every search server holds the full index, and 20k searches/second is a few dozen servers behind a load balancer, with copies in each region.

If the index grows (more data per place, many more places), shard by geography, since a search only ever needs one area. Make shards from geohash prefixes sized by traffic, not area, so Manhattan gets its own shards while a whole rural state shares one. A search near a shard edge queries the two or three shards its radius overlaps.

5. Replication and recovery

The database is the source of truth, and the index is derived. Stream place changes to the search servers through change data capture (CDC): a new or moved place shows up in the index within seconds, with no batch job. A new or restarted server loads the latest index snapshot from object storage and replays the change stream from the snapshot's position, so it's serving within minutes.

6. Ranking by popularity

"Best coffee near me" is not "closest coffee". Score each candidate with a blend such as rating_weight × bayesian_rating − distance_weight × distance_km, where the Bayesian rating pulls a 5.0 from 3 reviews toward the average. Fetch more candidates than you return (say 200 for a page of 20) so ranking has room to work. Keep rating and review count in the index entry, refreshed through the same CDC stream.

What's expected at each level

  • Mid-level: recognizes plain lat/lng indexes don't work; proposes a grid or geohash.
  • Senior: QuadTree (or geohash) with sizes and the neighbor search, caching, sharding the index.
  • Staff: replicate vs. shard from the size estimate, traffic-based geo shards, CDC-driven index freshness, ranking that blends rating with distance, and how the design changes if objects move (Uber).