Design Yelp / nearby search

Scope the requirements

The product sounds like a database query — 'businesses within 5 km' — and the trap is believing your database can run it. The interviewer is scoring whether you spot that a radius query needs a spatial index, and whether you can compare the standard options rather than name-drop one.

Functional — what it must do

Return all businesses within a user-chosen radius (0.5–20 km) of a lat/long, ranked by distance.
Business owners can add, update and delete listings; changes may take until the next day to appear in search.
View business detail: info, hours, rating, reviews.
Users can leave one review with a star rating per business.
Explicitly cut: text search, ads, reservations, and the nearby-friends live-location variant — I flag that last one and keep it in my pocket for the real-time follow-up.

Non-functional — the numbers that shape the design

Search latency under 200 ms p99 — this is an interactive map pan, not a report.
Scale: 100M DAU, 200M businesses worldwide.
Heavily read-dominated: searches outnumber business edits by around 1,000 to 1.
Eventual consistency is fine for search results — a new restaurant appearing tomorrow is acceptable, per the requirements.
High availability on the search path; business writes can tolerate brief outages.

Say this out loud

The write path is a small CRUD service — I'll spend almost nothing on it. The question lives in the read path: how do I index 200M points so a radius query is one cheap lookup, and which spatial encoding do I choose.

Back-of-envelope estimates

The arithmetic here delivers a surprise most candidates miss: the geospatial index is tiny. Getting that number early stops you sharding something that fits in memory on one box.

Quantity	Estimate	How you got there
Search QPS	~5,000/s	100M DAU × 5 searches/day ÷ 86,400 s ≈ 5,800; call it 5k, peak ~10k.
Business writes	~20/s	even if 1% of 200M businesses change daily that's 2M ÷ 86,400 — a rounding error next to reads.
Geo-index size	~6 GB	200M rows × ~30 B (geohash string + business_id). Fits in RAM on one machine — replicate it, never shard it.
Business table	~200 GB	200M × ~1 KB of detail per business. Comfortable for one relational primary with read replicas.
Geohash cell at precision 6	~1.2 km × 0.6 km	matches the common search radii; shorter prefixes give bigger cells for wide searches.
Nearby-friends variant	~300k updates/s	10M concurrent sharers pinging every 30 s — a different system entirely; I name it and park it.

Say this out loud

5k QPS and a 6 GB index changes the shape of this design: the whole geo index fits in memory everywhere, so the problem is not scale — it's choosing an encoding that turns 'within 5 km' into an index-friendly lookup.

Sketch the API

A read endpoint that does all the work and a boring CRUD surface for owners. The interesting decision is keeping search parameters in the query string so results are cacheable.

GET/v1/search/nearby?lat=..&lng=..&radius=5000→ paginated list of { businessId, name, distance, rating }. The hot path — no auth needed, aggressively cacheable.

GET/v1/businesses/{id}→ full detail: info, hours, rating summary, top reviews.

POST/v1/businessesowner-authenticated create; PUT and DELETE on /{id} for updates. Feeds the index rebuild, not live search.

POST/v1/businesses/{id}/reviewsbody: { stars, text }. Unique per (user, business) — enforced by the database, not the client.

I quantise the lat/lng in the cache key to the geohash cell rather than raw coordinates — otherwise every user's slightly different GPS position is a distinct key and the cache hit rate collapses to zero.
Radius is a hint, not a contract: in sparse areas I widen the search (shorter geohash prefix) until I have enough results, and say so — returning three businesses in rural Montana because the radius was literal is a product failure.

Data model

Two tables carry the design: the business record and a deliberately skinny geo-index table that exists only to answer 'which businesses are in this cell'.

business

id PK · name · address · lat · lng · category · hours · num_reviews · avg_rating

Rating stored as running (count, average) updated on review write — never AVG() over all reviews per read.

geo_index

geohash · business_id (compound PK)

Geohash at precision 6 as a plain string — prefix queries ride an ordinary B-tree, no spatial extension required.

review

user_id · business_id · stars · text · created_at

Unique constraint on (user_id, business_id) enforces one review per user.

The database call

I'd start with Postgres for everything: the business table is classic relational read-mostly data, and the geohash trick means the geo index is an ordinary indexed string column. If the interviewer wants richer filtering — 'open now, serves brunch, within 2 km' — I'd switch the search path to Elasticsearch with a geo_point field, because post-filtering geo candidates in the app gets ugly fast. PostGIS is the other legitimate exit: real spatial types, same operational story as Postgres.

High-level design

Split reads from writes explicitly: a stateless location-based search service that only ever reads from cache and replicas, and a separate business service that owns writes. The index refresh rides replication, off the hot path.

notice the search service never touches the primary — reads come from redis and replicas only, and listing changes flow to the cache asynchronously because next-day freshness was agreed up front.

Client sends lat/lng/radius → the search service computes the geohash of the position at the precision matching the radius, plus its 8 neighbouring cells (the boundary fix).
It fetches those 9 cell buckets from Redis (geohash → [business_ids]) — on a miss, a prefix query against geo_index on a read replica back-fills the cache.
Candidate businesses are hydrated from the Redis detail cache, exact distance is computed in the service, results filtered to the radius and ranked.
Owner edits go through the business service to the Postgres primary; replication carries them to replicas, and a change-feed consumer refreshes the affected cell buckets — search never sees a write.
Reviews write the review row and atomically bump the (count, average) pair on the business row in one transaction.

Deep dives — where the interview is won

Phase 01

Two B-trees on lat and long cannot answer a radius query

The naive query is WHERE lat BETWEEN x1 AND x2 AND lng BETWEEN y1 AND y2. With separate indexes on lat and lng, each index alone matches an enormous band around the planet — every business in a 10 km latitude strip is millions of rows — and the database intersects the two huge sets to find a few hundred survivors. It works at 10k businesses and dies at 200M. This is the first thing to say out loud, because it motivates everything that follows.

The fix is dimensionality reduction: encode 2-D position into a 1-D value that preserves proximity, so nearby points get nearby index entries. That's exactly what geohash does — interleave the bits of lat and lng and base32-encode them, so shared prefixes mean shared cells. Now 'everything near me' becomes WHERE geohash LIKE '9q8yy%' — a range scan on one ordinary B-tree, no spatial extension, no exotic database.

two-column b-tree can't answer a radius query — you scan lat range, then filter lng.

Trade-offAny space-filling-curve encoding has discontinuities: two points a metre apart on either side of a cell boundary can share no prefix at all. The 8-neighbour query is the tax you pay, and forgetting it silently drops results at every cell edge.

Phase 02

Geohash vs quadtree vs S2: pick geohash, know why the others exist

Geohash is a fixed global grid: dead simple, index-friendly strings, precision tuned by prefix length (precision 6 ≈ 1.2 km × 0.6 km). Its weaknesses: cells are rectangles of uneven real-world size by latitude, and the boundary problem forces the 9-cell query. Quadtree recursively subdivides space until each leaf holds ≤ ~100 businesses, so it adapts to density — Manhattan gets tiny leaves, Nevada gets huge ones — and for 200M businesses it's only ~1–2 GB in memory. But it's an in-memory structure per server: rebuilds take minutes, updates need locking, and every server must hold and refresh its own copy. S2 (Google) and H3 (Uber) map the sphere onto hierarchical cells via a space-filling curve and can cover an arbitrary radius with a set of mixed-size cells — the most precise and flexible, and the most machinery to explain.

My interview answer: geohash strings in a plain table, because at 6 GB the index is trivially replicable and a B-tree range scan at 5k QPS is nothing. I name Redis GEO as the packaged version of the same idea (geohash encoded into a sorted-set score) and PostGIS as the 'real spatial types' alternative. What earns the senior signal is stating when I'd switch: quadtree if density adaptivity dominates, S2/H3 if I need precise radius covering or hexagonal neighbour math — H3 shows up again in ride-sharing surge pricing for exactly that reason.

geohash prefix → cell. query the caller's cell plus 8 neighbours. simple sql prefix index.

Trade-offGeohash buys operational simplicity with imprecision — you over-fetch a 9-cell rectangle and post-filter to the true circle; the adaptive structures buy precision with state you must build, rebuild and keep consistent on every node.

Phase 03

A 6 GB index gets replicated, not sharded

The reflex at '200M businesses, 100M users' is to shard. Run the numbers instead: 30 bytes per (geohash, id) row is ~6 GB — the entire world's geo index fits in the page cache of every replica, and in Redis several times over. Sharding it would create the problem it pretends to solve: a radius query near a shard boundary becomes a cross-shard scatter-gather, adding latency and failure modes to save memory nobody was short of.

So the read path scales the boring way: cache cell buckets and business details in Redis, back them with as many Postgres read replicas as traffic needs, and keep the search tier stateless so it autoscales. The business detail table at ~200 GB is the thing that eventually shards — by business_id, which is clean because detail lookups are always point reads by id.

6 gb fits on one node; add replicas for read scale. sharding this small a dataset is over-engineering.

Trade-offFull replication means every replica absorbs every write — fine at 20 writes/s, and I'd say explicitly that this decision gets revisited only if write volume grows a thousandfold.

Phase 04

The nearby-friends variant flips the problem into a fan-out system

Interviewers love this pivot: 'now make it live friend locations'. The shape inverts — businesses move never, friends move constantly. 10M concurrent sharers updating every 30 s is ~300k location writes/s, and every update must reach that user's nearby friends within seconds. Polling a search index is hopeless; this becomes a push system: each client holds a WebSocket, locations land in a Redis cache with a TTL (stale sharers vanish automatically), and each update publishes to a per-user pub/sub channel that the user's friends subscribe to. Receivers compute distance client- or edge-side and surface friends within 5 miles.

The load isn't the writes, it's the fan-out: 300k updates/s × ~400 friends each is ~100M deliveries/s at the pub/sub layer, so the channel cluster shards by user_id. This is the same live-location machinery the ride-sharing question is built on — there it feeds matching instead of friends.

nearby-friends: fanout on each user's location update to their friends' watch lists.

Trade-offPub/sub delivery is fire-and-forget — a dropped update is corrected by the next ping 30 s later, which is exactly the consistency this feature needs; adding delivery guarantees here would buy nothing and cost throughput.

Follow-ups you should expect

How do you pick the geohash precision for a given radius?

Match the cell size to the radius: precision 6 cells are ~1.2 km across, so they suit 1–3 km searches; a 20 km search drops to precision 4. If a search returns too few results — sparse areas — I shorten the prefix and search again, expanding outward until I have enough candidates. The radius is a ranking input, not a hard wall.

How would you add filters like 'open now' or 'serves coffee'?

For a couple of attributes, fetch geo candidates first and post-filter in the service — the 9-cell fetch returns hundreds of rows, which is cheap to filter. The moment filtering becomes rich and combinatorial, I move the search path to Elasticsearch with a geo_point field and structured filters, and keep Postgres as the source of truth feeding it.

A business updates its location — when does search see it?

The requirement said next-day is acceptable, so I take the cheap path: the write lands in Postgres, and a change-feed consumer refreshes the affected geohash cell buckets in cache — minutes in practice, a day in the worst case. If the interviewer tightens the requirement, I dual-write to the cache on update and accept the complexity of keeping two writes consistent.

Why not Redis GEO for everything instead of your own geohash table?

Redis GEO is a fine answer and I'd accept it — GEOADD and GEOSEARCH implement exactly this design, geohash-encoded into a sorted set. I keep the table version as the source of truth because Redis is a cache tier in this design, not durable storage, and rebuilding 6 GB from Postgres is a one-minute job. Mechanically they're the same idea, and saying that is the point.

How do ratings stay correct under concurrent reviews?

The review insert and the (num_reviews, avg_rating) update happen in one transaction, with the running average recomputed as (avg × n + stars) / (n + 1). The unique constraint on (user_id, business_id) makes retries idempotent. At Yelp's write volume this never contends; if it did, I'd batch-recompute periodically and accept eventually consistent ratings.

Where candidates lose the room

Writing WHERE lat BETWEEN … AND lng BETWEEN … with two B-tree indexes and not noticing the intersection problem — this is the core insight of the question, and missing it caps the interview.
Ignoring the cell-boundary problem — a user standing near a geohash edge silently loses half their results, and the interviewer knows to ask about the restaurant across the street.
Sharding the geo index at 6 GB — it broadcasts that you didn't do the storage estimate, and it turns single-cell lookups into scatter-gathers.
Saying 'just use Elasticsearch' with no mechanics — it's a valid tool, but with no mention of geo_point, prefix encodings or the boundary issue, it reads as name-dropping.
Recomputing AVG() over all reviews on every write or read instead of keeping a running (count, average) pair on the business row.