System Design Lab›System Design Questions›Design Yelp (Proximity Service)
Design Yelp (Proximity Service)
MediumSearchgeolocationsearchcachingranking
Question Overview
Design a location-based search service that finds businesses near a user and ranks them by distance and rating. Expect to compare geohash, quadtree, and S2/H3 indexing, handle both dense cities and empty countryside, and serve a read-heavy workload with low latency.…
Sign up to see the full question and AI interviewer
Requirements
- Find businesses within a 0.5-25 km radius of a point, filtered by category, price, rating, and open now
- Rank results by a blend of distance, rating, and relevance, with stable pagination
- Business detail pages with hours, photos, and reviews; owners create and edit listings
- Users post 1-5 star reviews and see their own review immediately
- Nearby search p99 under 200 ms and highly available; listing changes visible within minutes
Back-of-the-envelope numbers
- Searches: 100M DAU × 5 = 500M/day ÷ 86,400 s ≈ 5.8K QPS average, ~17K QPS at 3× peak
- Listing updates: 1M/day ÷ 86,400 s ≈ 12 writes/s, so searches outnumber listing writes roughly 500:1
- Geo index: 200M businesses × (8 B ID + 8 B lat + 8 B lng) ≈ 4.8 GB, which fits in RAM on every search replica
- Quadtree: capping leaves at 100 businesses gives ~2M leaves and ~0.67M internal nodes, only ~200 MB of structure on top of the points
- Dense areas: a 5 km radius covers π × 5² ≈ 78.5 km²; at 2,000 businesses/km² that is ~157K candidates, so cap and pre-rank per cell
- Business metadata: 200M × ~2 KB ≈ 400 GB, sharded by business_id and fronted by a cache for detail pages
- Reviews: 500K/day × ~1 KB ≈ 0.5 GB/day ≈ 183 GB/year, only ~6 writes/s
Key components
- Geo index service: an in-memory geohash, quadtree, or S2/H3 index replicated on stateless search nodes, since the whole index fits in RAM
- Geohash: encode each location as a base32 string; query the covering cell plus its 8 neighbors, then filter by exact haversine distance
- Quadtree or S2 cells: subdivide adaptively until a leaf holds at most 100 businesses, so downtowns get small cells and rural areas large ones
- Index refresh: listing changes flow through a change stream to update replicas incrementally, with a periodic full rebuild as a safety net
- Business and review stores: sharded by business_id with read replicas and a detail-page cache; rating aggregates updated asynchronously
- Ranking: score candidates on distance decay, Bayesian-averaged rating, and popularity; a search engine with geo filters handles text queries
- Caching: cache results by (cell, filters) with short TTLs, and serve photos from a CDN
Common mistakes
- Filtering with lat BETWEEN and lng BETWEEN on separate B-tree indexes, which narrows only one dimension and scans a whole stripe
- Searching only the geohash cell containing the user, missing nearby businesses just across a cell boundary
- Using a fixed grid regardless of density, so city cells hold thousands of businesses and rural cells return nothing
- Measuring distance with Euclidean math on raw degrees, ignoring that a degree of longitude shrinks toward the poles
- Sharding the small geo index by region, creating hot shards and cross-shard border queries, instead of simply replicating it
- Ranking by raw average rating, so a business with one 5-star review outranks a 4.7 with 2,000 reviews
Likely follow-ups
- How would you support searching along a driving route rather than around a single point?
- How would the design change for moving objects, such as drivers updating their location every few seconds?
- How would you implement open now across time zones and holiday hours?
- How would you keep search fresh when a business moves or permanently closes?
- How would you detect and filter fake or incentivized reviews?
- How would you keep pagination stable when the user's location shifts slightly between pages?
No community solutions yet
Be the first to publish your solution
Practice ‘Design Yelp (Proximity Service)’ with an AI Interviewer
Get scored feedback on your diagram, scalability approach, and trade-offs. Free while we grow — up to 3 full interviews a day.