System Design HLD-19.14
Design a proximity service (Yelp, nearby places)
Design a nearby-places service: read-heavy geo queries, geohash versus quadtree indexes held in memory, caching by cell, and slow business updates.
The problem
"Coffee near me." The app sends your position and gets back the twenty best places within walking distance, ranked by distance, rating and whether they are open. Millions of people ask this every hour, from every corner of every city.
Compare it with ride hailing ( Design a ride-hailing service (Uber) ). There, the things being searched for (cars) move every few seconds. Here, they almost never move: a cafe changes its opening hours occasionally and its location essentially never. That one difference flips the design. The index can be built in advance, held in memory, copied to as many servers as needed, and cached aggressively. The interesting decisions are which spatial index to use and how to keep it fresh enough.
Requirements
Functional
- Given a location and a radius (or "the best nearby"), return matching businesses with distance, ranked and paginated.
- Filter by category, open now, price.
- Show a business's details page.
- Business owners add and edit businesses; changes may take a while to appear in search.
Non-functional
- Scale: 200 million businesses; 100 million daily users doing 5 searches each.
- Latency: under 200 ms for a search.
- Availability: very high for reads; writes can tolerate brief delays.
- Freshness: new or edited businesses visible within hours, not seconds.
Out of scope
- Reviews and photos (separate services), map tiles, and turn-by-turn directions.
Estimates
- Search QPS: 100M x 5 = 500 million searches a day, about 5,800 per second on average and roughly 17,000 at a 3x peak.
- Business data: 200M businesses x about 1 KB of details = 200 GB. It lives in a database with read replicas.
- Spatial index: only id, latitude and longitude are needed to find candidates: 8 + 8 + 8 = 24 bytes per business, so 200M x 24 bytes = 4.8 GB. That fits in memory, so every search server can hold the whole index and we scale by replicating, not sharding.
- Writes: if 1 million businesses change something each day, that is about 12 writes per second. Reads outnumber writes by more than a thousand to one.
API
GET /v1/search/nearby?lat=51.5007&lng=-0.1246&radius=1000&category=cafe&open_now=true&cursor=...
-> { results: [ { id, name, distance_m, rating, open_now } ], next_cursor }
GET /v1/businesses/{id}
POST /v1/businesses (owner)
PUT /v1/businesses/{id} (owner)
The search returns ids and summary fields; the client fetches full details only for the business the user taps.
Data model
- Businesses (relational database, primary plus read replicas, Replication: leader-follower ):
id, name, category, lat, lng, address, hours, price, rating, updated_at. Writes go to the primary; detail reads go to replicas behind a cache. - Spatial index (in memory on each search server): a map from cell to business ids, built from the database.
- Search cache:
(cell, category, filters) -> ranked ids, with a lifetime of minutes.
High-level design
- Search path A search server turns the location and radius into cells, checks the cache for this cell and filter combination, and otherwise reads candidates from its in-memory index, filters by real distance and attributes, ranks them and returns a page of ids.
- Details path Tapping a result reads the business details through a cache in front of the database read replicas. Details change rarely, so the hit ratio is high.
- Update path Owner edits go to the primary database and replicate. Every few hours an index builder reads recent changes and publishes a new index snapshot, which search servers load and swap in.
Deep dives
Deep dive 1: Geohash or quadtree
Both turn "near this point" into "in these cells" ( Geospatial indexing ).
- Geohash divides the world into a fixed grid and names each cell with a string; longer strings are smaller cells, and nearby cells usually share a prefix. The index is a hash map from geohash to business ids, easy to build, shard and cache. Its weakness is that cell size is the same everywhere: a cell that holds 5 businesses in the countryside holds 5,000 in a city centre.
- Quadtree starts with one square and splits any square holding too many businesses into four. Dense areas get small cells and sparse areas big ones, so each leaf holds a similar number of businesses.
Here is a quadtree over 20,000 businesses in a 40 km square, with two dense centres:
# A quadtree adapts cell size to density: split any square holding more
# than 100 businesses. Then answer "within 1 km" by visiting only the
# leaves that touch the search circle. Two dense centres, sparse elsewhere.
import math, random
rnd = random.Random(3)
pts = [(rnd.gauss(12, 1.5), rnd.gauss(14, 1.5)) for _ in range(12000)]
pts += [(rnd.gauss(28, 2.5), rnd.gauss(26, 2.5)) for _ in range(4000)]
pts += [(rnd.uniform(0, 40), rnd.uniform(0, 40)) for _ in range(4000)]
pts = [(x, y) for x, y in pts if 0 <= x < 40 and 0 <= y < 40] # km
MAX = 100
def build(x, y, size, items, leaves):
if len(items) <= MAX or size < 0.1:
leaves.append((x, y, size, items))
return
h = size / 2
for dx in (0, h):
for dy in (0, h):
sub = [p for p in items if x + dx <= p[0] < x + dx + h
and y + dy <= p[1] < y + dy + h]
build(x + dx, y + dy, h, sub, leaves)
leaves = []
build(0, 0, 40, pts, leaves)
sizes = sorted(size for _, _, size, _ in leaves)
print(f"{len(pts)} businesses -> {len(leaves)} leaves, "
f"from {sizes[0] * 1000:.0f} m to {sizes[-1]:.0f} km wide")
def nearby(qx, qy, r=1.0):
scanned, hits, visited = 0, 0, 0
for x, y, s, items in leaves:
# distance from the query point to the nearest point of the square
dx = max(x - qx, 0, qx - (x + s))
dy = max(y - qy, 0, qy - (y + s))
if math.hypot(dx, dy) > r:
continue
visited += 1
scanned += len(items)
hits += sum(math.dist((qx, qy), p) <= r for p in items)
return visited, scanned, hits
for name, q in (("downtown", (12, 14)), ("suburb", (35, 5))):
v, sc, h = nearby(*q)
print(f"{name:9} visited {v:2} leaves, scanned {sc:4}, "
f"found {h:4} within 1 km")Output
20000 businesses -> 415 leaves, from 156 m to 5 km wide
downtown visited 48 leaves, scanned 3162, found 2364 within 1 km
suburb visited 4 leaves, scanned 247, found 9 within 1 km Leaves range from 156 m wide downtown to 5 km wide in the countryside. A 1 km search in the suburb visited 4 leaves and found 9 places, while the same search downtown found 2,364, far more than anyone will scroll. That points at the real query: not "everything within 1 km" but "the best 20 nearby", which means expanding the radius until there are enough candidates in sparse areas and ranking a capped candidate set in dense ones. A quadtree lets you find "the nearest leaves with enough businesses" directly; with geohash you get the same effect by stepping to a shorter prefix (bigger cells) when results are thin.
At 4.8 GB, either index fits in memory. Geohash is simpler to update incrementally (move an id between two map entries); a quadtree is usually rebuilt from scratch, which takes minutes and suits this workload, where hours of staleness are acceptable.
Deep dive 2: Neighbours and edges
A user standing near the edge of a cell may be 50 m from a cafe in the next cell and 400 m from everything in their own. So a search always covers the user's cell and its neighbours, then filters candidates by the real distance. With geohash that is the cell plus its 8 neighbours; with a quadtree it is every leaf that touches the search circle, as the sample does. Near the poles and the 180th meridian, cells behave oddly, which is one reason production systems lean on well-tested geo libraries rather than hand-rolled code.
Deep dive 3: Caching by cell
Users near each other ask nearly the same question. Snapping a query to its cell turns millions of slightly different coordinates into a manageable number of cache keys: (geohash6, category, open_now) -> ranked candidate ids. Cache them for a few minutes ( Caching patterns ), then compute each user's exact distances from the cached candidates, which is cheap. Popular cells (city centres at lunchtime) stay hot; rural cells are rarely cached and rarely needed.
"Open now" changes with the clock, so either keep it out of the cache key and filter after the cache, or keep cache lifetimes short enough that hours boundaries do not matter.
Deep dive 4: Business updates
Updates are rare and may be slow to appear, which lets us keep the read path simple:
- Writes go to the primary database only. Search servers are never written to directly.
- An index builder runs every few hours (or consumes a change stream) and publishes a versioned index snapshot. Servers load it alongside the old one and swap atomically, so no search ever sees a half-built index.
- A brand-new business shows up in search after the next build, but its details page works at once, because details come from the database.
Try it
Try this:
- Choose the precision whose cell is closest to a 1 km search radius. How many of the nine cells would a search need?
- Find a pair of points that share a long prefix and a pair that are close but share a short one. What does that tell you about using prefixes alone?
- Our cache key uses 6 characters. What would happen to the hit ratio and the result quality with 5 or 7?
Bottlenecks and failure modes
| Failure | Impact | Mitigation |
|---|---|---|
| Dense city centre | Thousands of candidates per query | Quadtree leaves or capped candidate sets; rank top N only |
| Sparse area | Too few results | Expand radius or move to bigger cells until enough |
| Hot cells at peak times | One cache key very busy | Replicated cache; short lifetimes; local server caches |
| Bad index snapshot | Wrong or missing results everywhere | Validate counts before publishing; roll back to previous version |
| Primary database down | Owners cannot edit | Reads unaffected; writes retry or queue |
| Cell edges | Missed nearby places | Always search neighbouring cells and filter by real distance |
Trade-offs we made
| Option | Wins when | Loses when |
|---|---|---|
| Whole index in memory on every server (chosen) | Any server answers any query; scale by adding replicas | Each server needs memory for the full index |
| Shard the index by region | Smaller servers; handles a much larger dataset | Routing; searches near region edges hit two shards |
| Periodic rebuild (chosen) | Simple, consistent snapshots | New businesses appear in search after hours |
| Geohash map | Easy to build, update and use as a cache key | Uneven density per cell |
| Quadtree | Even density per leaf | Harder to update incrementally |
Extensions
- Ranking: blend distance, rating, popularity and personal history.
- Search by text ("vegan pizza near me") with an inverted index restricted to nearby candidates ( Inverted indexes and full-text search ).
- Polygons: delivery areas and neighbourhoods rather than circles.
- Multi-region deployment with indexes per continent.
In the wild
Where you will see this: review sites, map apps, food delivery and real estate search, store locators, and dating apps. The pattern is consistent when the searched-for things move rarely: build a spatial index offline, hold it in memory on many replicas, cache by cell, and accept slightly stale results in exchange for very fast, cheap reads.
Check yourself
-
Why can every search server hold the whole spatial index?
Show answer
B. The index needs only id, latitude and longitude, about 5 GB for 200 million businesses 24 bytes per business times 200 million is 4.8 GB, which fits in memory.
-
What does a quadtree give you that a fixed geohash grid does not?
Show answer
B. Cells that adapt to density, so each leaf holds a similar number of businesses Dense areas split into small leaves and sparse areas keep big ones.
-
Why does a nearby search include neighbouring cells?
Show answer
B. The nearest place can be just across the cell boundary Cells are a coarse filter; real distance decides.
-
An owner adds a new cafe. When does it appear in nearby search?
Show answer
B. After the next index build, typically within hours Search reads periodic snapshots; the requirement allows hours of delay, which keeps reads simple.
Recap
- Businesses rarely move, so build the spatial index offline and keep it in memory on every search server.
- Geohash is a simple fixed grid; a quadtree adapts cell size to density.
- Always search neighbouring cells, then filter by real distance and rank a capped candidate set.
- Cache results by cell and filters for minutes; compute exact distances per user.
- Owner edits go to the database and reach search through versioned index snapshots.
Next up
- Crack the system design round learning path