Location · Design 25

Design Nearby places

Design Yelp's "near me" search in a 45-minute interview: geohash, quadtree, S2/H3 and PostGIS compared, read-heavy caching, rating aggregation and ranking.

IntermediateInterview priority: High60 min
On this page
  1. How to use this page
  2. 1. Clarify the requirements
  3. 2. Back-of-the-envelope estimates
  4. 3. API
  5. 4. Data model
  6. 5. High-level design
  7. 6. Deep dives
  8. 7. Bottlenecks, failures and monitoring
  9. 8. Follow-up questions
  10. Quiz

How to use this page

This page follows the order of a real system design interview. At each step there is a Your turn box: write your own answer first (it stays in your browser), then open ours and compare. Reading a finished design feels easy; producing one under time pressure is the skill you are practising.

PhaseTime in a 45-min interviewWhat you produce
1. Clarify requirements5 minFunctional list, non-functional targets, what's out of scope
2. Estimate5 minSearches/s, index size, write rate
3. API5 minThe search call and the few write calls
4. Data model5 minPlaces, reviews, the geo index and the cache
5. High-level design10 minBoxes and arrows, the search path and the update path
6. Deep dives10–15 minGeo indexing, cell boundaries, density, ranking, freshness
7. Wrap up2–3 minBottlenecks, failures, what you would monitor

Users search for places near a location, optionally by category (restaurants, cafés) and radius, and see results ranked by distance, rating or relevance, with details for each place. Users can rate and review places. Business owners can add or update their place; changes may take a few minutes to appear. Skip photos, reservations and turn-by-turn directions.

1. Clarify the requirements

Your turn: scope it

The interviewer says: "Design Yelp." Write down what you would ask, then 4–6 functional requirements, 4–5 non-functional requirements with a target, and 2–3 things you would put out of scope.

Compare with our answer

The questions that matter most: How many places and users? What radius range? Do results sort by distance, rating or "best match"? Are reviews in scope? How quickly must an owner's edit appear? Do places move (food trucks)? Then write the agreed list on the board, as below.

Functional: what it must do

  • Search nearby: Location + radius (500 m – 20 km), optional category
  • Sort and filter: Distance, rating, open now
  • Place details: Name, address, hours, rating
  • Rate and review: 1–5 stars and text; the average rating updates within minutes
  • Add or edit a place: By owners; can appear after a delay

Out of scope

Photos and menusReservationsTurn-by-turn directions

Non-functional: how well it must work

QualityTargetWhy
Search latency< 200 ms (p99)Used on the move
Availability99.99%
Read-heavy~1,000 searches per place updateOptimise reads above all
FreshnessEdits visible within minutesOwners can wait a little
Scale200 M places, 100 M daily usersDense cities and empty deserts

2. Back-of-the-envelope estimates

Your turn: the numbers

Assume 100 M daily users, 5 searches each per day, 200 M places, a 100-byte index entry per place (id, latitude, longitude, category, rating), 2 KB of details per place, and 2 M reviews written per day. Work out searches per second (average and peak), the size of the geo index, the size of the full place data, and the review write rate.

Compare with our answer
  • Searches: 100 M × 5 = 500 M/day. ÷ ~86,400 ≈ 5,800/s average; lunch and evening peaks are about 3×, so plan for ~17–20 K/s.
  • Geo index: 200 M × 100 B = 20 GB. That fits in the RAM of one ordinary server.
  • Full place data: 200 M × 2 KB = 400 GB. A normal database with a cache in front.
  • Reviews: 2 M ÷ 86,400 ≈ 23 writes/s. At ~1 KB each, about 2 GB/day, ~730 GB/year.
  • Ratio: thousands of searches for every write. This is a read problem.

A strong answer mentions: searches/s with a peak factor · index size small enough for memory · details stored separately from the index · a write rate tiny next to the read rate · the conclusion "replicate, don't shard".

Assumptions: daily active users 100 M; searches per user per day 5; places 200 M; index entry per place 100 B; reviews written per day 2 M.

NumberEstimateWhy it matters
Searches per second5.79 K / s≈ 5,800/s average; plan ~3× for peaks.
Geo index size20 GB≈ 20 GB: it fits in memory on one machine, so replicate it rather than shard it.
Full place data400 GB~2 KB per place with details: in a normal database with a cache.
Review writes per second23.1 / s≈ 23/s: writes are tiny next to searches, so one sharded SQL cluster is plenty.
  • The whole geo index fits in RAM, so the scaling strategy is read replicas of the index, not sharding.
  • Searches cluster in cities: cache results per cell and category.

The surprise in the numbers is the index. Two hundred million places sounds like a big-data problem, but a compact entry per place is only 20 GB, which fits in memory. So the scaling plan is copy the whole index onto several machines and spread searches across them, not split it into shards. Sharding becomes worth it only if the index outgrows one machine (for example, if you add per-place embeddings for search) or if you need per-region data isolation.

3. API

Your turn: the API

Write the search call with every parameter it needs, then the calls for details, reviews and owner edits. What does pagination look like when results are ranked rather than sorted by an ID?

Compare with our answer

A strong answer mentions: latitude, longitude and radius on the search call · optional category, sort and open-now filters · a cursor rather than page numbers · details as a separate cacheable call · a review write that returns before the average updates · owner edits that are applied asynchronously.

The search endpoint is the hot path; everything else is ordinary CRUD (create, read, update, delete).

CallRequestResponseNotes
GET /v1/search/nearby?lat=&lng=&radius=&category=&sort=&cursor=–{ places[{ id, name, distance, rating }], nextCursor }The hot endpoint
GET /v1/places/{id}–{ name, address, hours, rating, … }Cached
POST /v1/places{ name, lat, lng, category, hours }201 { placeId }Owner adds a place
PATCH /v1/places/{id}{ fields }200Owner edits; index updated asynchronously

Two additions that interviewers like to hear:

  • POST /v1/places/{id}/reviews with { stars, text } returns 201 { reviewId }. The place's average rating is updated asynchronously, within minutes, so the review write stays cheap.
  • Pagination uses a cursor. Ranked results can shift between requests as ratings change. The cursor encodes the query plus the last (score, place_id) returned, so page 2 continues from where page 1 stopped instead of skipping or repeating places. Most users never go past the first page or two, so cap it (for example 10 pages).

4. Data model

Your turn: the tables

What is the source of truth, what is derived from it, and where does each piece live? Where does a place's average rating come from, and how is it kept up to date?

Compare with our answer

A strong answer mentions: a places table as the source of truth · reviews keyed by place with one review per user per place · a rating sum and count rolled up on the place · a separate in-memory geo index built from the places table · a results cache keyed by cell and category · the index and cache being derived data that can be rebuilt.

places Relational (PostgreSQL) + cache

  • place_id, name, address
  • lat, lng, category, hours
  • rating_sum, rating_count (rolled up from reviews)
  • updated_at

Source of truth for details; modest size, rarely written.

reviews Relational (PostgreSQL), sharded by place_id

  • review_id, place_id, user_id
  • stars (1–5), text, created_at
  • UNIQUE (place_id, user_id)

Small write rate; all reviews of a place sit together for paging and re-aggregation.

geo index In-memory (geohash prefix map or quadtree), replicated

  • geohash (e.g. “tdr1w”) → [place_id, …]
  • or quadtree: node → children / place ids

Built from the places table; answers “who is in these cells?” in microseconds.

search cache Redis

  • (geohash cell, category) → candidate ids + rating (TTL minutes)
  • exact distance and final order computed per request

Popular areas and categories repeat constantly.

The key idea is one source of truth, several derived copies. The places and reviews tables in PostgreSQL are the truth. The geo index and the results cache are both built from them, can be thrown away and rebuilt, and are allowed to be a few minutes behind.

Three details worth saying out loud:

  • Store rating_sum and rating_count, not just an average. Adding a review is then rating_sum += stars, rating_count += 1, and editing a review from 2 to 5 stars is rating_sum += 3. With only an average stored, you cannot apply an edit without re-reading every review.
  • UNIQUE (place_id, user_id) stops one account from reviewing the same place twice, which is the first and cheapest defence against review spam.
  • Reviews are sharded by place_id, so all reviews of one place sit together: paging through them and recomputing a place's totals is a single-shard query.

5. High-level design

Your turn: draw it

Sketch the boxes: how does a search find candidates, where do details come from, and how does an owner's edit reach the index? Then step through ours.

Compare with our answer

The architecture, then the search path and the update path

  1. The architecture is read-optimised. A stateless search service queries replicas of an in-memory geo index and a results cache. The place service and database are the source of truth, and a change stream rebuilds the index replicas in the background.
  2. A search converts the user’s location into a geohash cell, adds the eight neighbouring cells so places just across a border aren’t missed, collects candidate places from the in-memory index, filters by exact distance and category, ranks, and fetches details for the top results.
  3. An owner edits their café’s hours. The change is saved in the places database and flows through a change stream to an index builder, which updates every index replica within a few minutes.
ComponentWhat it does
Search serviceStateless; geohash maths, filtering, ranking
Geo index replicasThe whole index in memory on each replica; add replicas for more QPS
Results cacheHot (cell, category) combinations
Places & reviews service + DBDetails, owner edits and reviews; rolls ratings up into rating_sum / rating_count
Change stream + index builderPropagates edits to the index within minutes

Trace the search out loud, one hop at a time:

  1. The phone sends lat=40.7580, lng=-73.9855, radius=1000, category=cafe. The load balancer picks any search instance; they are stateless.
  2. The search service computes the geohash cell of the location and its neighbours, then asks the results cache for (cell, cafe).
  3. On a miss, it asks a geo index replica for the places in those cells: perhaps 140 candidates in a dense area.
  4. It computes the true distance to each candidate, drops those outside 1 km and those that are closed if openNow is set, ranks the rest and takes the top 20.
  5. It fetches details for those 20 (from a details cache, falling back to the places database) and returns them.

The update path runs the other way, asynchronously: the owner's edit or a new review is written to PostgreSQL; change data capture (CDC, a process that reads the database's write-ahead log and turns each committed change into an event, for example Debezium) publishes it to a stream; the index builder applies it to every replica.

6. Deep dives

Your turn: the hard parts

Before reading on, write two or three sentences on each: how would you index 200 M points so "within 1 km of here" is fast? What goes wrong at a cell boundary? How do you cope with Manhattan and the Nevada desert in the same index? How would you rank a 5.0 with 2 reviews against a 4.6 with 3,000?

Compare with our answer

A strong answer mentions:

  • A spatial index (geohash, quadtree, S2/H3 or an R-tree) that turns a 2-D range into a few lookups, and why two B-tree range conditions don't.
  • Searching neighbouring cells and filtering by true distance; choosing a cell size from the radius.
  • Adaptive cells or expanding the search until enough candidates are found.
  • Two-stage retrieval then ranking, with a smoothed (Bayesian) rating.

Geo indexing: how do we find places within 1 km quickly?

The naive query is WHERE lat BETWEEN a AND b AND lng BETWEEN c AND d. A normal B-tree index (the sorted index most databases use by default) on (lat, lng) can use only the first range: it finds every place in a thin horizontal stripe of latitude that circles the whole planet, then checks longitude for each one. Two independent indexes don't help either; the database must intersect two huge lists. What we need is an index where nearby on the map means nearby in the index.

OptionHowGood atCatch
PostGIS (GiST / R-tree)The database indexes bounding boxes in a tree; ST_DWithin and the <-> nearest-neighbour operator use itExact, simple, transactional; one system to runEach query does real work on the database; at ~20 K searches/s you need many replicas
GeohashInterleave the bits of longitude and latitude, encode in base 32; places sharing a prefix are in the same cellPlain strings: works in any key-value store, sorted set or cache key; trivially cacheableFixed grid ignores density; cells are rectangles that shrink in width away from the equator; boundary problem
QuadtreeSplit the world into 4 squares, and split again any square holding more than K places (say 100)Adapts to density: tiny cells in Manhattan, huge ones in the desertLives in memory and must be built and kept in step; finding neighbours is trickier
S2 (Google) / H3 (Uber)Hierarchical cells over the sphere: S2 projects onto a cube and orders cells along a Hilbert curve (64-bit ids, 31 levels); H3 uses hexagons at 16 resolutionsBetter geometry than geohash, no pole or date-line oddities; H3 hexagons have 6 equidistant neighboursNeeds a library; H3 children don't exactly tile their parent, so roll-ups are approximate

Geohash precision is what you tune. Cell sizes at the equator (width shrinks with latitude: at New York's 41° N a cell is about 76% as wide):

LengthCell sizeTypical use
439 km × 19.5 kmRegion
54.9 km × 4.9 kmTown, 5–20 km searches
61.2 km × 0.61 kmNeighbourhood, ~1 km searches
7153 m × 153 mStreet

Choice: an in-memory geohash (or S2) index on replicated search nodes, built from the places table. It answers in microseconds, needs no special database, and the same cell ids become cache keys. PostGIS is the right first version and the right answer for a smaller product; say so, then explain that at 20 K mostly repeated searches a second a purpose-built in-memory index is far cheaper per query. Elasticsearch and OpenSearch (geo_point, stored in BKD trees) and Redis GEOSEARCH (a 52-bit geohash in a sorted set) are other off-the-shelf options worth naming.

-- PostGIS: the simple first version
CREATE INDEX places_geog_idx ON places USING GIST (geog);   -- geog geography(Point, 4326)

SELECT place_id, name,
       ST_Distance(geog, ST_MakePoint(-73.9855, 40.7580)::geography) AS metres
FROM places
WHERE category = 'cafe'
  AND ST_DWithin(geog, ST_MakePoint(-73.9855, 40.7580)::geography, 1000)  -- uses the index
ORDER BY metres
LIMIT 20;

Cell boundaries: why check the neighbours?

The boundary problem, and the 3×3 fix

Two places a few metres apart can sit in different cells, and across some boundaries (the equator, the prime meridian) they share no prefix at all. So the search always reads the user's cell plus its 8 neighbours, then filters by true distance.

Dense cities and empty countryside

One length-6 cell in Midtown Manhattan can hold thousands of places; one in Nevada holds none. A fixed grid gives too many candidates in one and too few in the other.

OptionHowCatch
Fixed cell sizeSame precision everywhereThousands of candidates to score in cities; empty results in the countryside
Expand until enoughStart small; if fewer than ~50 candidates, move to the parent cell (drop one geohash character) and retryExtra round trips in sparse areas, but each is microseconds in memory
Quadtree / S2 adaptive cellsSplit a cell only when it holds more than K placesNeighbour finding is more complex; the tree must be rebuilt or updated as places change
Cap per cellKeep each cell's list pre-sorted by quality; read only the top N per cellThe best place just outside the top N of a dense cell is never considered

Choice: expand-until-enough on a geohash/S2 index, plus a per-cell cap in the densest cells. If the interviewer prefers a quadtree, the arithmetic is reassuring: 200 M places at up to 100 per leaf is about 2 M leaves, a few hundred megabytes of tree on top of the 20 GB of entries, built in minutes at start-up.

Ranking: which café comes first?

Retrieval and ranking are two separate stages. Retrieval finds a few hundred candidates by location and hard filters (category, open now). Ranking orders them with a score and returns the top 20.

OptionCatch
Sort by distanceFine as a user-chosen sort, but the nearest place is often not the one people want
Sort by average starsA 5.0 from 2 reviews (perhaps the owner's friends) beats a proven 4.6 from 3,000
Weighted score with a smoothed rating, distance, popularity and open-nowWeights need tuning; later, a model trained on clicks and visits can replace hand-written weights

The smoothed rating is a Bayesian average: pretend each place starts with C imaginary reviews at the global mean m. With m = 3.8 and C = 20:

  • 5.0 from 2 reviews: (20 × 3.8 + 10) ÷ 22 = 3.91
  • 4.6 from 3,000 reviews: (20 × 3.8 + 13,800) ÷ 3,020 = 4.59

The proven café wins, and a new place with a handful of great reviews still climbs as reviews accumulate. A simple score is then something like 0.5 × rating_score + 0.3 × distance_score + 0.2 × popularity_score, each normalised to 0–1, with distance decaying (a place twice as far away is not half as good).

Personalisation and "open now"

Personalisation (cuisines you like, price levels you pick) is a re-ranking step on the top few hundred candidates, so it never touches the geo index. Keep the features in a per-user profile cache.

Open now is surprisingly fiddly: hours are stored in the place's local time zone, a place can close after midnight (18:00–02:00 belongs to the previous day), and holidays override the normal schedule. Store hours as (day, open, close) in local time plus the place's time-zone name, and evaluate them at query time in that zone; never precompute an "open" flag that goes stale every hour.

Reviews and rating aggregation

A review write inserts a row and must change the place's rating_sum and rating_count. Options:

OptionHowCatch
Recompute on readAVG(stars) over all reviews on every searchAbsurd at 20 K searches/s
Same transactionInsert the review and update the place's totals togetherSimple and exact at 23 writes/s; a very popular place makes its row a lock hot spot
Asynchronous roll-upInsert the review; a consumer of the change stream adds it to the totals, which flow to the index like any editThe rating lags by seconds to minutes, which the requirements allow

Choice: insert the review, roll up asynchronously, and run a nightly job that recomputes totals from the reviews table to repair any drift. The index carries the rating so ranking never touches the database.

Freshness: how do edits reach the index?

An owner changes opening hours; a new review moves the rating. Updating every replica synchronously on each write would make writes slow and couple them to every search node. Instead, writes go to PostgreSQL; CDC publishes each change to a stream such as Kafka; each index replica (or a builder feeding them) applies changes in order.

New replicas start from a snapshot (a full dump of the index taken at a known stream offset) and then replay the stream from that offset. A nightly full rebuild from the database catches anything the stream path got wrong, and is swapped in atomically.

Caching a read-heavy service

Searches cluster heavily: lunchtime café searches in central London repeat thousands of times with nearly identical inputs. But the exact location differs per user, so caching final results by raw coordinates gives almost no hits.

  • Cache candidates per (cell, category), not final results. Distance and the final order are computed per request from the cached candidates, which is cheap.
  • Details cache per place_id with a TTL of minutes, deleted when the place changes.
  • CDN for photos and static assets; search responses are personalised and short-lived, so they mostly bypass it.
  • A busy cell like Times Square is a hot key; keep the top cells in each search instance's local memory for a few seconds as well (see caching).

7. Bottlenecks, failures and monitoring

Scaling bottlenecks

BottleneckFix
Read QPSAdd index replicas behind the load balancer; cache hot cells
Hot areas (Times Square)Results cache by (cell, category, sort)
Index rebuildsBuild a new index in the background and swap atomically
Global latencyDeploy replicas in several regions; route to the nearest

When things fail

FailureWhat happens
An index replica diesLB stops sending it traffic; others serve; a new replica loads a snapshot
Index builder lagsSearches use slightly stale data; alert on lag
Places DB downSearches still work from the index + cache; edits wait

What to monitor

Search latency (p99)Results per query (too many / too few)Index freshness lagCache hit ratioReplica memory and QPS

8. Follow-up questions

Your turn: the interviewer pushes

Answer these three in order before opening ours. 1) Food trucks change location every few hours, and delivery couriers every few seconds. Does the design still work? 2) The product team wants "search along my route" for a road trip. What changes? 3) A competitor floods your newest restaurants with one-star reviews from fresh accounts. What do you do?

Compare with our answer

A strong answer mentions:

  1. Food trucks are fine as normal edits if minutes of lag are acceptable; couriers are not: fast-moving objects need a separate in-memory index updated every few seconds (as in Uber), kept apart from the static places index.
  2. Cover the route's polyline with cells (S2 can cover a buffered line), search those cells, and rank by detour time rather than straight-line distance.
  3. Rate-limit and score reviews by account age, history and network; hold suspicious reviews out of the average until they pass checks; subtract removed reviews from the totals; and alert on sudden rating drops.
How do you stop fake reviews?

Limit one review per user per place, weight reviews by account age and history, detect bursts from new accounts or one network, and hide (not delete) suspect reviews from the average.

How would you handle moving things, like food trucks?

Frequent location updates → keep those in a separate fast-changing index (like Uber’s) rather than the static places index.

Geohash vs quadtree vs H3?

Geohash: simple strings, easy to cache. Quadtree: adapts to density. H3/S2: hierarchical cells with nicer geometry; used by Uber and Google.

More senior follow-ups
  • Multi-region. The index is only 20 GB, so every region keeps a full copy and serves its own users; the places database has one primary region, and CDC fans changes out to every region's index. An edit takes slightly longer to reach far regions.
  • Exact nearest-k instead of a radius. "The 10 closest petrol stations" has no radius; search the user's cell, expand outwards ring by ring until you have k results and the next ring is farther than the k-th result.
  • Polygon areas. A national park or an airport is an area, not a point; store its polygon and index it under every cell it overlaps (S2 coverings do this well).
  • Search by name or text. "Joe's pizza near me" combines a text match with a location filter; that is a search engine job (Elasticsearch/OpenSearch with geo_distance filters), see search.
Nearby places on one page
  • Numbers: ~5,800 searches/s average, ~20 K/s peak; 200 M places × 100 B = 20 GB index (fits in RAM); 400 GB details; ~23 review writes/s.
  • Scale by replication, not sharding: every search node holds the whole index.
  • Index: geohash or S2 cells in memory; PostGIS (GiST) is the right smaller-scale answer; quadtree adapts to density.
  • Boundaries: search the cell + 8 neighbours, or cover the radius's bounding box; then filter by true distance. Cells must be at least the radius in both dimensions.
  • Density: expand to the parent cell until enough candidates; cap per cell in dense areas.
  • Ranking: retrieve a few hundred, re-rank by score; use a Bayesian average, not raw stars.
  • Ratings: store rating_sum and rating_count; roll up asynchronously and idempotently; nightly recompute.
  • Freshness: PostgreSQL → CDC → stream → index replicas; snapshot + replay for new replicas; drop lagging replicas.
  • Cache candidates per (cell, category), details per place; local cache for hot cells.
Mock interviewPractise it as a mock interview: scope, size and the big decisionsOpens in the ByteAtlas lab. Your progress is saved in this browser.
Check what stuck

1. Your places table has a B-tree index on (lat, lng). Why is WHERE lat BETWEEN … AND lng BETWEEN … still slow for a 1 km search?

2. A user stands 30 m from the edge of geohash cell dr5ru7 and searches for cafés within 300 m. The search reads only dr5ru7. What happens?

3. The geo index is 20 GB and peak load is 20,000 searches per second. What is the best way to scale it?

4. Café A has 5.0 stars from 2 reviews; café B has 4.6 from 3,000. Both are 300 m away. Which ranking rule handles this best?

5. The rating roll-up consumer reads review events from a stream and adds each to the place's rating_sum. It crashes after an update but before committing its offset. What is the risk and the fix?

6. A design uses length-6 geohash cells (1.2 km × 0.61 km) and the 3×3 neighbour block for 1 km searches. What is wrong?

7. An owner edits opening hours. Which update path fits the requirements?

Score 60% or more and the lesson is marked complete.

Passing the quiz also marks it complete. Progress is saved in this browser only.