Design Yelp (Nearby Places)
Places barely move and reads dominate. Index them with a geohash column or an in-memory quadtree, cover the search circle with a few cells, and replicate the index.
- ~17K/speak searches from 100M daily users
- ≤ 9 cellscover any circle at the right precision
- ~1.9 GBquadtree for 200M businesses
Show what to say
“Places barely move and reads dominate, so I'd build a geo index and replicate it. A geohash column makes near-me an indexed prefix query: pick the longest hash whose cells are at least the radius, scan the at most 9 cells covering the circle, then filter by exact distance. For uneven density I'd use an in-memory quadtree, about 2 GB, a full copy per search server.”
Trade-offs
- Geohash vs quadtree: geohash is one simple SQL column but cells are uneven; a quadtree adapts to density but needs a service.
- Replicate vs shard the index: full copies keep servers independent and easy to recover, but cost memory each; sharding adds routing.
- Change feed vs nightly rebuild: a feed shows new listings in minutes, but nightly rebuilds alone are simpler and a day stale.
Bring it up before they ask
Cell edges: a place just across a boundary can be nearer than most in your own cell, so always read the covering cells, not just yours.
Businesses barely move, so build a geo index once and read it a lot: a column, or an in-memory that splits only where places are dense. Search one cell, or the few cells covering your radius, then sort by exact distance. Reads dwarf writes.
Functional
- Find businesses within a radius of a point (0.5 to 20 km)
- Filter by category and sort by distance
- Business details page
- Owners add, edit and delete listings
- Show results on a map
Non-functional
- Search responds in under 100 ms
- About 17K searches a second at peak
- Highly available: reads work if a server dies
- Edits show up within minutes to a day
- Scales to 200 million businesses
Out of scope
- Reviews and photos storage
- Ranking by personal taste
- Live location tracking of moving things (see the ride-sharing design)
Scope, scale and API
Read more · 254 words
- Static or moving? Restaurants do not move. Cars do, and that is a different design.
- Radius and size? Fixed radii or any, and how many businesses?
- Freshness? Is a listing visible the next day, or within a minute?
- Result order? Distance, rating, or a mix?
Size it:
| Quantity | Calculation | Result |
|---|---|---|
| Searches | 100M daily users × 5 ÷ 86,400 s | ≈ 5.8K/s, ~17K/s at 3x peak |
| Businesses | 200M × 1 KB | 200 GB |
| Geohash index | 200M × (9 chars + 8 B id = 17 B) | ≈ 3.4 GB |
| Quadtree leaves | 200M ÷ 100 per leaf | 2M leaves |
| Quadtree memory | 200M × 8 B ids + 2.67M nodes × 100 B | ≈ 1.9 GB |
| Search servers | 17K ÷ 6 servers | ≈ 2.8K/s each |
The index is tiny and fits in the memory of one machine. So replicate it; do not it. Search is a read-only, service, and writes are rare.
The API:
| Method | Path | Notes |
|---|---|---|
| GET | /v1/search/nearby | lat, lon, radius, category, cursor → businesses with distanceM, plus nextCursor |
| GET | /v1/businesses/:id | Details, from the cache |
| POST | /v1/businesses | Owner adds a listing; address is geocoded |
| PUT | /v1/businesses/:id | Edit |
| DELETE | /v1/businesses/:id | Remove |
Results are paged with a cursor (distance and id of the last result), not an offset, so the next page is stable.
Data model and architecture
The is not stored in the database.
Read more · 81 words
It is built from this table every night, saved as a snapshot file, and kept current from the change feed.
Two paths. Search reads an in-memory index and a . Writes go to the database and a change feed that updates the index. Play Search nearby, A cold business, Owner adds a business and An index server restarts.
CREATE TABLE business (
id bigint PRIMARY KEY,
name text NOT NULL,
category text NOT NULL,
lat double precision NOT NULL,
lon double precision NOT NULL,
geohash text NOT NULL, -- 9 characters, about 5 m cells
hours jsonb, rating real
);
CREATE INDEX business_geohash ON business (geohash text_pattern_ops); -- makes LIKE 'prefix%' a range scan
-- search: WHERE geohash LIKE '9q8yy%' OR geohash LIKE '9q8yz%' ... then filter by exact distanceTap any box to see what it is and what it talks to.
- Client
- API gateway
- Service
- Cache
- Database
- Queue
- Worker
Text description
- The user opens the app in San Francisco and asks for restaurants within 1 km.
- The gateway sends GET /search?lat=37.77&lon=-122.42&radius=1000 to any location server.
- The location server asks its in-memory quadtree: find the leaves that touch a 1 km circle, check exact distances, keep the closest 20.
- A few hundred businesses were examined out of 200 million. 20 ids come back, nearest first, with distances.
- One multi-get fetches the name, photo, rating and hours of those 20 businesses.
- All 20 are cached: the whole search took a few milliseconds, with no database call.
- The app draws 20 results on the map.
Geohash
A turns a point into a short string: longer is a smaller cell, and a shared prefix means the same cell.
Read more · 87 words
So "near me" becomes an indexed LIKE 'prefix%' query.
Pick the longest hash whose cells are at least as big as the radius, and the circle touches at most 3 x 3 = 9 cells. In San Francisco, 0.5 km uses 6 characters, 1 or 2 km use 5, 5 km uses 4, and 20 km uses 3. Scan those cells, drop anything past the radius, sort, take 20.
The weakness is density: one cell in midtown can hold thousands of places while the next holds none.
Quadtree
A starts with the whole map as one box.
Read more · 63 words
When a box holds more than 100 businesses, it splits into four. Downtown ends up as many tiny leaves, the desert as one big leaf, so every leaf stays near 100.
Search walks down to the boxes that touch the circle and checks their points. 200M businesses make about 2M leaves and 1.9 GB, so each search server holds a full copy.
Step-by-step answer
In one line each:
Read more · 352 words
Clarify
Static places, radius range, freshness, order.
Estimate
17K searches a second; an index of about 2 to 3 GB.
Pick the index
first, for uneven density.
Design the services
Read-only search, cached details, a change feed.
Scale and failure
, rebuilds, hot cells, .
In full:
Notice it is read heavy and static
Searches outnumber edits by orders of magnitude, and places do not move. Precompute, replicate and cache.
Store the source of truth in a database
A business table with latitude, longitude and a 9-character geohash. A pool serves details.
Index space with cells
Explain geohash: strings, shared prefixes, cell sizes. Cover the circle with at most 9 cells and filter by exact distance.
Handle the edges and density
Cells have edges, so read neighbours. Cells have uneven populations, so mention quadtrees or S2 and H3.
Build the quadtree
Capacity 100 per leaf. Sizes: 2M leaves, about 2 GB, so a full copy per search server. Rebuild nightly; apply the change feed in between.
Cache the details
Search returns ids and distances. A multi-get fetches names and photos from a cache with a one hour expiry.
Deal with freshness
Adds and deletes arrive through a feed within minutes. A deleted business is also filtered at read time against the cache.
Add filters and ranking
Filter by category after the geo lookup, or keep a quadtree per category. Rank by distance blended with rating.
Implementation
Tabs: distance helpers, the index (covering cells and a range scan), and the .
Read more · 65 words
Both indexes are checked against a brute-force scan.
- The geohash test shows radius to precision (0.5 km: 6, 1 and 2 km: 5, 5 km: 4, 20 km: 3) and at most 9 cells per circle.
- Both indexes return exactly what a brute-force scan returns over 100 queries at five radii.
- The quadtree test shows depth adapting to density and the 200M-business memory sum.
// Great-circle distance in kilometres, and the box that contains a circle. Both indexes use these:
// the index finds candidates cheaply; the exact distance check throws away the ones in the corners.
const EARTH_RADIUS_KM = 6371;
const KM_PER_DEGREE_LAT = (Math.PI * EARTH_RADIUS_KM) / 180; // about 111.19
const rad = (d) => (d * Math.PI) / 180;
export function haversineKm(a, b) {
const dLat = rad(b.lat - a.lat);
const dLon = rad(b.lon - a.lon);
const h = Math.sin(dLat / 2) ** 2 + Math.cos(rad(a.lat)) * Math.cos(rad(b.lat)) * Math.sin(dLon / 2) ** 2;
return 2 * EARTH_RADIUS_KM * Math.asin(Math.sqrt(h));
}
// Smallest lat/lon rectangle that holds every point within `radiusKm` of the centre.
// (Ignores the poles and the date line; a real service handles those as special cases.)
export function boundingBox(lat, lon, radiusKm) {
const dLat = radiusKm / KM_PER_DEGREE_LAT;
const dLon = radiusKm / (KM_PER_DEGREE_LAT * Math.cos(rad(lat)));
return { latLo: lat - dLat, latHi: lat + dLat, lonLo: lon - dLon, lonHi: lon + dLon };
}
export { KM_PER_DEGREE_LAT };Failure modes
Read more · 92 words
| What breaks | Effect | Mitigation |
|---|---|---|
| A search server restarts | Fewer copies | Other copies serve; reload snapshot, replay feed |
| A zone is lost | Half the capacity | Copies in two zones; sized for 3x peak |
| Index and database disagree | A closed business appears | Check status in the detail cache; fix by the feed and nightly rebuild |
| A hot cell (a stadium event) | One cell dominates | Smaller leaves; cache popular queries |
| Geocoding is wrong | A pin in the sea | Validate; manual review for outliers |
| Cache goes cold | Database load spikes | Replicas; stagger expiries; warm after deploy |
Trade-offs
Pick by constraints. Click through the tree, then compare.
Read more · 91 words
| Choice | Gain | Cost |
|---|---|---|
| Geohash in SQL | Simplest; any database | Uneven cells; neighbours to read |
| In-memory quadtree | Adapts to density | A service to build and refresh |
| S2 or H3 | Hierarchical ids, shardable | More machinery |
| Replicate vs shard | Simple, resilient | Memory per server |
Is density very uneven (a big city next to empty countryside)?
Follow-up questions
How would this change for moving objects?
A moving thing needs constant writes and a short-lived index, as in the ride-sharing design: overwrite the latest position in memory.
How do you search near the date line or the poles?
Cells wrap in longitude and degenerate near the poles, so the covering code handles those as special cases. Most apps clamp the search area.
How do you rank beyond distance?
Fetch the nearest few hundred, then blend distance, rating, popularity and opening hours in a second stage.
Check yourself
Question 1 of 3Score 2 out of 3 or better to mark this page complete.
Patterns behind this
The coding patterns this design is built on. Practise them and the design questions get easier.