Nearby Places (Yelp)

What the interviewer is asking

"Design Yelp", also asked as "design a nearby places service", is about one question asked over and over: what's near this point? Storing restaurants and reviews is easy. The hard part is answering that question about 100,000 times a second, when places crowd into city centers and almost vanish in the countryside.

Two facts shape the design: searches outnumber edits by tens of thousands to one, and the data a search needs fits in one server's memory. Below are the 8 steps of the interview framework: scope, data, API, the busy path, numbers, services, scale and deep dives.

1. Scope: what version 1 must do

• Search near a point: places within 1 km, or the 20 closest.
• Filter by category: cafés, pharmacies, gyms.
• Place pages: a place's details and its reviews.
• Owners' edits: business owners add a place or change its hours. These writes are rare.

Park the rest out loud: ranking by personal taste, drawing the results on a map (the Google Maps lesson), and photos (the Files and Object Storage lesson).

2. Data: places and reviews

record   fields
place    id, name, category, lat, lng, rating, review_count, address, hours
review   id, place_id, user_id, stars, text, time

The average rating and the review count are copied onto the place and updated as reviews arrive, so a results list shows stars without reading a single review. The busy path needs only a place's position, category, name and rating.

3. The API: three calls

GET /places/nearby?lat=40.71&lng=-74.01&radius=1km&category=cafe
→ 200 OK  [{"id": 42, "name": "Blue Cup", "rating": 4.6, "distance": "350 m"}, …]

GET /places/42
→ 200 OK  {"name": "Blue Cup", "hours": …, "reviews": […]}

POST /places  {"name": "Café Luz", "category": "cafe", "lat": 40.71, "lng": -74.01}
→ 201 Created  {"id": 43}

The point comes from the phone, which knows its position from GPS. A home address is wrong whenever the user is out, and an IP address locates a device only roughly, often to a city. A search changes nothing, so it's a GET; a limit=20 parameter can ask for the 20 closest instead.

4. The busy path: the nearby search

1. The app reads the phone's position: 40.71, -74.01.
2. It sends GET /places/nearby with that point, 1 km and "cafe".
3. The server finds the cafés within 1 km of the point.
4. It sorts them by distance and keeps the 20 closest.
5. It answers with each one's name, rating and distance.

Everything else in the design exists to keep step 3 fast.

5. The numbers

From the interviewer: about 100,000 searches a second at the busiest time, about 300 place edits a minute, and 200 million places at about 1 KB each. Say an index entry (id, position, category, name, rating) takes about 100 bytes, and one search server handles about 1,000 searches a second.

what              working
edits             300 a minute ÷ 60 = 5 a second
reads per write   100,000 ÷ 5 = 20,000 searches for each edit
place records     200 million × 1 KB = 200 GB, 600 GB in 3 copies
search index      200 million × 100 bytes = 20 GB
search servers    100,000 ÷ 1,000 = 100 at the peak

Watch two slips: 100,000 ÷ 300 mixes a second with a minute, and the 3 copies of stored data aren't memory per server. The index number changes the design: 20 GB fits in one ordinary server's memory, so every search server can hold all of it.

6. Services: search apart from place pages

• Search service: finds the places near a point, keeps the asked category, sorts by distance.
• Place service: place pages with their reviews, and owners' new places and edits.

Each grows with its own load, and a rush of searches can't slow an owner's save.

7. Scale: the whole index on every search server

Say one database server answers about 5,000 simple lookups a second. A nearby search is far from simple, so the database is at least 20× short.

• Sharding the places by id over 20 databases fails: the places near one user sit on every shard, so each search asks all 20 (scatter-gather).
• Caching results by the exact point fails: no two phones stand at the same spot.
• Copying the index works: the whole 20 GB in memory on each of about 100 search servers behind a load balancer. Any server answers any search alone.

These are copies, as with read replicas in the Replication lesson, and with 5 edits a second, keeping them alike is cheap. A new server loads the 20 GB at about 1 GB a second, in about 20 seconds. Place pages read the database and its read replicas.

8. Deep dive: why an index on latitude fails

A database's first idea is an index on lat and a box about 1 km each way around the user (0.01° of latitude is about 1.1 km; of longitude in New York, about 0.84 km):

SELECT … WHERE lat BETWEEN 40.70 AND 40.72
          AND lng BETWEEN -74.02 AND -74.00

The index jumps to 40.70 and reads every entry up to 40.72. On a small sample:

lat      lng       place      read?             in the box?
40.696   -73.99    Brooklyn   no, below 40.70   no
40.704   -111.89   Utah       yes               no
40.705   -74.01    New York   yes               yes
40.707   31.60     Turkey     yes               no
40.709   -74.01    New York   yes               yes
40.712   -3.61     Spain      yes               no
40.715   116.02    China      yes               no
40.718   140.47    Japan      yes               no

7 entries read to keep 2. The latitude range is a band around the whole globe: 360° long against a box 0.02° wide, 18,000 times as long.

A two-column index on (lat, lng) doesn't help: it sorts by latitude first, so the whole band still sits between 40.70 and 40.72. Two-column indexes shine when the first column is an exact match, like user_id = 7. A second index on lng only adds a band from pole to pole.

The fix indexes both dimensions at once: split the map into square cells, give each a code, and index the code. Places near each other share a cell, so a search reads its own cell and the 8 around it. A geohash is a common code: each extra character splits a square into 32, and nearby points usually share a prefix (the Uber lesson runs this search). Many databases offer a geospatial index that does this; in the interview, explain the idea.

9. Deep dive: the quadtree

Cells of one size don't fit a real map. Say the busiest 1 km cell downtown holds about 3,000 places and the fields around the city hold none. With 100 m cells, a countryside search that must reach 10 km walks through tens of thousands of empty cells. With 5 km cells, one cell over the lesson's city holds about 7,000 places, all read on every search.

A quadtree adapts. It starts with one square for the whole map; any square holding more than K places splits into 4 quarters, each checked the same way. The lesson's toy map has 12 places on a map 4 km across, with K = 4 (a real system might use a few hundred):

square   places   result
map      12       more than 4: split into NW, NE, SW, SE
NW       7        more than 4: split into NW1 to NW4
NE       2        leaf
SW       1        leaf
SE       2        leaf
NW1      3        leaf
NW2      2        leaf
NW3      1        leaf
NW4      1        leaf

That's 7 leaves: four 1 km squares downtown and three 2 km squares around them. Finding a leaf is a walk down from the root, one step per level; for the whole world, about 20 levels reach squares of about 100 m.

A search finds the user's leaf, reads it and the leaves that touch it (more if those hold too few), then sorts the candidates by real distance. In the toy, Ana's leaf SE holds only 2 places, so the search reads NE, SW and NW4 (across a corner) too. Her 3 closest are i at 0.6 km, g at 0.7 km and j at 0.8 km, none in her own leaf. The other downtown leaves are never read: the nearest is about 1.2 km away, farther than her third result, so it can't hold anything closer.

On the real map, distance between two latitude and longitude points comes from the haversine formula, the distance along the Earth's surface. Raw degrees mislead: a degree of longitude is about 111 km at the equator but about 84 km in New York.

Geohash or quadtree? Both are accepted. A geohash grid is easy to compute and to split by prefix, but its cells don't adapt. A quadtree adapts to density and lives in memory, which suits places: they rarely move, they cluster, and reads dominate.

10. Deep dive: serving the index

• An index builder reads the database's changes, updates the quadtree every few minutes, say 5, and saves a snapshot. At 5 edits a second, one update holds about 1,500 changes.
• Each search server loads the newest snapshot when it starts, then applies each small update in memory. A full rebuild can run once a night.
• A new café shows up within minutes: fine for a listing, and searches never wait for an edit.

Updating all 100 servers before the owner's save returns makes every save wait on 100 machines. Asking the database for recent edits on every search brings back 100,000 queries a second.

Popular searches repeat: at lunchtime, thousands of people downtown look for restaurants. Each search server caches popular answers keyed by the leaf plus the category: the matching places of that leaf and its neighbors. A hit only sorts that short list by the user's own distance, and entries expire after a few minutes, like the index. Keying by the exact point or by user id would share nothing.

What breaks first

• The index outgrows one server's memory: shard it by region, as in the Sharding lesson, with copies of each shard; searches near a border ask two shards.
• A bad snapshot: keep the previous one, load a new one on a few servers first, and roll back if searches go wrong.
• Rare categories: a leaf may hold no pharmacy, so the search keeps widening; a separate tree for busy categories keeps it short.

Summary: the order to follow

1. Scope: search near a point by category, place pages with reviews, owners' edits.
2. Data: places (with their rating and review count) and reviews.
3. API: GET /places/nearby?lat=&lng=&radius=&category=, GET /places/{id}, POST /places.
4. Busy path: the nearby search.
5. Numbers: 20,000 searches for each edit; a 20 GB index that fits in memory.
6. Services: search apart from place pages and edits.
7. Scale: the whole index in memory on about 100 search servers behind a load balancer.
8. Deep dives: a latitude index reads a band around the globe; a quadtree splits crowded squares and searches the leaf, then its neighbors; snapshots every few minutes and a cache by leaf and category.

The same pieces carry over to any "what's near me" question: a small index of positions in memory, copied rather than split, cells that adapt to density, and a few minutes of staleness traded for fast reads.