Design Yelp

Design a local discovery service. People open the app and ask for things like "ramen near me, open now, rated 4 stars or more", see results on a map and in a list, open a business page with photos and reviews, and write reviews of their own. Business owners update their hours, photos and menus.

The catalogue holds a couple of hundred million places worldwide, but each search only cares about a small patch of the map. Density varies wildly: one block of a big city can hold more restaurants than a whole rural county. Searches are far more frequent than new places or reviews, and results must come back fast enough to redraw as the user drags the map.

In 45 minutes, cover how you index locations for nearby search, how filters and ranking work, how reviews and ratings are stored, and how the system stays fast at peak.

Sketch on the HLD board, write your answer in the Design doc, and size it with the Estimator. Start the mock interview from the timer for a 45-minute run.

Design Path · Location & Marketplaces · problem 23 of 70

Ask before you design. Try answering each yourself, then compare.

1. What scale should we assume?
   Typical answer

   About 200 M places, 50 M daily users, roughly 5 searches per user per day, and 1 M new reviews per day.

2. What search inputs do we support?
   Typical answer

   A location (the user's position or the visible map area), a radius from 0.5 to 25 km, an optional text query or category, and filters such as open now, price and minimum rating.

3. How fresh must results be?
   Typical answer

   A new review or a changed rating can take a few minutes to affect search. Edits to opening hours should appear within a minute.

4. How fast must search be?
   Typical answer

   p99 under 200 ms server-side, including ranking.

5. Can a user review the same place twice?
   Typical answer

   One review per user per place, editable. Reviews go through automated spam filtering before they count.

6. Are photos in scope?
   Typical answer

   Storing and serving them, yes. Image moderation is a black box.

Requirements

Functional

• Search places near a point or inside a map viewport, with optional text, category and filters.
• Rank results by a mix of relevance, distance, rating and popularity, with pagination.
• Show a place page with details, photos, rating summary and reviews.
• Write, edit and delete one review per user per place; owners edit their listing.

Non-functional

• Search p99 under 200 ms; place page p99 under 150 ms.
• 99.95% availability for search and place pages; review writes may degrade briefly.
• Peak ~9,000 searches/s and ~30,000 place page reads/s.
• Rating and review changes reflected in search within 5 minutes.

Out of scope

• Reservations, delivery and ads.
• Personalised recommendations beyond simple ranking signals.
• Turn-by-turn directions.

Back-of-the-envelope estimates

• Search: 50 M × 5 = 250 M searches/day ≈ 2,900/s average and ~9,000/s at peak, plus extra requests while users pan the map.
• Place pages: about 3 per search, ~9,000/s average and ~30,000/s at peak.
• Reviews: 1 M per day ≈ 12/s. At ~2 KB each that is 2 GB/day, ~3.6 TB over 5 years, ~11 TB with three replicas.
• Places: 200 M × ~1 KB of searchable fields ≈ 200 GB. The geo index itself (id, geohash, a few ranking fields) is ~10 GB, which fits in memory on every search node.
• Photos: a few hundred million images, hundreds of TB in object storage behind a CDN.

This is a read-heavy problem with a small, slowly changing index: the design is driven by search latency and by fitting the geo index in memory, not by write volume.

API

GET  /v1/search?lat=..&lng=..&radius=1500&q=ramen&open_now=1&min_rating=4&cursor=..
                                     -> {results: [{placeId, name, distanceM, rating, reviewCount}], nextCursor}
GET  /v1/search?bbox=s,w,n,e&category=coffee   -> same shape (map viewport)
GET  /v1/places/{id}                           -> {details, hours, photos[], ratingAvg, ratingHistogram}
GET  /v1/places/{id}/reviews?sort=recent&cursor=..
PUT  /v1/places/{id}/reviews/me {stars, text}  -> 200 {reviewId, status: PENDING}

Writing a review is a PUT on the user's own review of that place, so it is naturally idempotent and enforces one review per user per place.

Data model

places(place_id PK, name, lat, lng, geohash, category_ids, hours, price, rating_sum, rating_count, updated_at) in a relational store, sharded by place_id; it is the source of truth and changes slowly.

reviews(place_id, review_id, user_id, stars, text, status, created_at) in a wide-column store partitioned by place_id and clustered by time, so a place's newest reviews are one sequential read; a secondary table keyed by user_id serves a user's profile and enforces one review per place.

The search index is derived: each document holds the place's geohash prefixes, categories, text fields and ranking features. It is rebuilt from change events, never written directly by the API. Photos live in object storage keyed by place.

High-level design

Search path: the app calls the gateway, which routes to the search service. The service normalises the request, snapping the location to a geohash cell and rounding the radius, and checks the search cache, where popular areas and queries are kept for a minute or two. On a miss it chooses a geohash precision whose cells are at least as big as the radius, and asks the geo search index for places in the user's cell and its eight neighbours that match the text, category and filters. It then computes exact distances, drops anything outside the radius, ranks the remaining candidates and returns a page with a cursor.

Place page: the place service reads details and the stored rating sum and count from the places DB through a cache, and fetches the first page of reviews from the review store. Photos load from the CDN.

Write path: a review goes to the review service, which writes it as PENDING and publishes an event. After spam checks pass, the rating aggregator adds the stars to the place's sum and count and emits an index update, so search sees the new rating within minutes. Listing edits follow the same event path into the index.

Open the HLD board and press Reference to see the architecture diagram.

Deep dives

Indexing locations: geohash, quadtree or S2

A geohash interleaves latitude and longitude bits into one string, so places in the same cell share a prefix and a nearby query becomes a few prefix lookups. Two traps: points just across a cell border have different prefixes, so always search the 3x3 block of cells around the user; and a fixed precision suits a city but not a desert, so pick the precision per query from the radius. A quadtree instead splits a square into four children only when it holds more than, say, 100 places, so dense downtowns get tiny cells and empty land gets huge ones; it adapts better but lives in memory and needs rebuilding. Spherical cell systems such as S2 or H3 behave better near the poles and give more uniform cell areas. Any of these is fine if you handle borders and density.

Filtering and ranking

The geo step only produces candidates. Combine it with an inverted index so text, category and filters such as price are intersected with the cell lists in one query. 'Open now' depends on local time, so store opening intervals per weekday in minutes and evaluate them against the place's time zone at query time. Rank with a simple scoring function, for example text relevance × a rating score that shrinks low review counts toward the average × a distance decay, then refine the top few hundred with a learned model if time allows. Shrinking toward the average stops a place with a single 5-star review from outranking one with 4.6 stars from 2,000 reviews.

Keeping search fast at peak

The geo index is only ~10 GB, so give every search node a full in-memory replica and scale reads by adding replicas rather than sharding by region. That avoids hot shards when a festival fills one city. Cache whole result pages keyed by (cell at the chosen precision, normalised query, filters) with a TTL of a minute or two: many users in the same neighbourhood search for the same things. Because places almost never move, index updates are mostly attribute changes (rating, hours), streamed in near real time and applied as small in-place updates, with a full nightly rebuild as a safety net.

Reviews and rating aggregates

Store the sum and count of stars on the place row instead of recomputing an average from every review. A new review adds to both; an edit adds the difference; a deletion or a review later flagged as spam subtracts. The aggregator consumes review events keyed by place, so updates for one place apply in order, and it records the last review event applied for each place so a replayed event is not counted twice. A periodic job recomputes the true totals from the review store and repairs drift.

Failure modes

• If a search node dies, the load balancer sends traffic to other replicas, each of which holds the full index.
• If the index update stream lags, search serves slightly stale ratings and hours; place pages still read fresh data from the places DB.
• If the search cache is cold or down, every request hits the index; replicas are sized to handle peak without the cache, just with higher latency.
• If the review store is unavailable, place pages show details and the cached rating summary without the review list, and new reviews are queued on the client.
• If a bad bulk import corrupts listings, the index can be rebuilt from the places DB snapshot taken before the import.

Core algorithm in code

import math
from collections import defaultdict

BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"


def encode(lat: float, lng: float, precision: int) -> str:
    """Interleave longitude and latitude bisection bits, 5 bits per character."""
    lat_lo, lat_hi, lng_lo, lng_hi = -90.0, 90.0, -180.0, 180.0
    out, bits, ch, even = [], 0, 0, True
    while len(out) < precision:
        if even:
            mid = (lng_lo + lng_hi) / 2
            ch = (ch << 1) | (lng >= mid)
            lng_lo, lng_hi = (mid, lng_hi) if lng >= mid else (lng_lo, mid)
        else:
            mid = (lat_lo + lat_hi) / 2
            ch = (ch << 1) | (lat >= mid)
            lat_lo, lat_hi = (mid, lat_hi) if lat >= mid else (lat_lo, mid)
        even, bits = not even, bits + 1
        if bits == 5:
            out.append(BASE32[ch])
            bits, ch = 0, 0
    return "".join(out)


def cell_size(precision: int):
    """(lat_deg, lng_deg) height and width of a cell at this precision."""
    lng_bits = math.ceil(precision * 5 / 2)
    lat_bits = precision * 5 // 2
    return 180 / 2 ** lat_bits, 360 / 2 ** lng_bits


def neighbours(lat: float, lng: float, precision: int) -> set:
    """The point's cell plus the 8 around it, so results near a cell edge are not missed."""
    dlat, dlng = cell_size(precision)
    return {encode(lat + i * dlat, lng + j * dlng, precision) for i in (-1, 0, 1) for j in (-1, 0, 1)}


def km(a_lat, a_lng, b_lat, b_lng):
    p1, p2 = math.radians(a_lat), math.radians(b_lat)
    h = math.sin((p2 - p1) / 2) ** 2 + math.cos(p1) * math.cos(p2) * math.sin(math.radians(b_lng - a_lng) / 2) ** 2
    return 2 * 6371 * math.asin(math.sqrt(h))


class PlaceIndex:
    """Each place is indexed under its geohash prefixes at several precisions."""
    PRECISIONS = range(4, 8)

    def __init__(self):
        self.cells = {p: defaultdict(list) for p in self.PRECISIONS}

    def add(self, name, lat, lng, rating):
        h = encode(lat, lng, max(self.PRECISIONS))
        for p in self.PRECISIONS:
            self.cells[p][h[:p]].append((name, lat, lng, rating))

    def precision_for(self, radius_km, lat):
        """Finest precision whose cell is at least as big as the radius in both directions,
        so the 3x3 block around the user is guaranteed to cover the whole circle."""
        for p in sorted(self.PRECISIONS, reverse=True):
            dlat, dlng = cell_size(p)
            if dlat * 111 >= radius_km and dlng * 111 * math.cos(math.radians(lat)) >= radius_km:
                return p
        return min(self.PRECISIONS)

    def nearby(self, lat, lng, radius_km, min_rating=0.0):
        p = self.precision_for(radius_km, lat)
        hits = []
        for cell in neighbours(lat, lng, p):       # 9 key lookups, no table scan
            for name, plat, plng, rating in self.cells[p].get(cell, ()):
                d = km(lat, lng, plat, plng)
                if d <= radius_km and rating >= min_rating:
                    hits.append((round(d, 2), rating, name))
        return p, sorted(hits)


idx = PlaceIndex()
places = [("Corner Espresso", 40.7484, -73.9857, 4.6), ("Night Noodles", 40.7505, -73.9934, 4.2),
          ("Bagel Stop", 40.7527, -73.9772, 3.4), ("Harbor Diner", 40.7033, -74.0170, 4.8),
          ("Park Tacos", 40.7410, -73.9897, 4.4), ("Brooklyn Pie", 40.6782, -73.9442, 4.9)]
for p in places:
    idx.add(*p)

me = (40.7480, -73.9860)
print("my cell (precision 6):", encode(*me, 6))
for radius in (0.5, 1.5, 8.0):
    p, hits = idx.nearby(*me, radius_km=radius, min_rating=4.0)
    print("radius %.1f km -> precision %d, 9 cells around %s" % (radius, p, encode(*me, p)))
    for d, rating, name in hits:
        print("   %-16s %.2f km  rating %.1f" % (name, d, rating))

Trade-offs

• A geohash fits ordinary key-value and search indexes and is easy to cache, but fixed cells handle uneven density poorly; a quadtree adapts to density but must be kept in memory and rebuilt.
• Replicating the whole geo index on every search node avoids hot regional shards but means every node must apply every update and have the memory for the full index.
• Caching results by cell and query cuts load at peak but shows ratings and hours that can be a minute or two old.
• Storing rating sum and count makes reads O(1) but needs careful handling of edits, deletions and replays, plus a repair job.

What a strong answer shows

• Explains a concrete spatial index and handles cell borders by searching neighbouring cells.
• Adapts cell size to the radius or to local density.
• Combines geo filtering with text, category and attribute filters, then ranks with sensible signals.
• Uses estimates to show the index is small and read-heavy, and scales with replicas and caching.
• Keeps the search index derived and updated asynchronously from the source of truth.
• Maintains rating aggregates incrementally and idempotently.

Mistakes to avoid

• Running radius queries with separate B-tree indexes on latitude and longitude over 200 M rows.
• Searching only the user's own geohash cell and missing places just across the border.
• Using one fixed cell size for both dense cities and empty areas.
• Recomputing the average rating from all reviews on every page view.
• Writing to the search index synchronously in the review request path.

Follow-ups to expect

• How would you search along a route, such as coffee on my drive? (Sample points along the route and union the cell queries, rank by detour.)
• How would you detect fake reviews? (Account age, burst detection per place, device and network signals, hold suspect reviews for moderation.)
• How do you support a map viewport rather than a radius? (Cover the bounding box with cells at a suitable precision, then filter by box.)
• How would you personalise ranking? (Add user features, such as preferred categories and price, to a learned re-ranker over the top candidates.)

Practice next