Design Yelp

Proximity Search System Design

Overview

Open Yelp, type "coffee," and the app answers a deceptively simple question: which businesses are near me right now, and which are good? Behind that one tap is a proximity search over millions of business locations, a set of category and open-now filters, a ranking pass that blends distance with rating, and a business-detail lookup that pulls in the profile, photos, and review summary. The heart of the problem is spatial: you cannot answer "within 2 km of this lat/lng" efficiently with an ordinary B-tree, because two independent coordinates don't collapse into one sortable key without help.

It is labeled "Medium" because the system is conceptually clean — search + read a profile — but the one part that is genuinely hard, the geospatial index, has several viable answers (geohash, quadtree, S2/H3) and the interviewer wants to see you pick one and reason about its edge cases: cell boundaries, uneven density, and how a radius query maps onto cells. Get the index right and the rest — caching, read replicas, denormalized ratings — falls out naturally because the workload is overwhelmingly read-heavy.

The single most important framing to state early: this is a read-heavy system. Searches and profile views vastly outnumber writes (a new review, a new business). That means the design should lean on precomputed indexes, aggressive caching, read replicas, and a CDN for static business data — and treat writes (reviews, ratings) as the comparatively rare path.

In this walkthrough you'll scope the system, size it, model the data, design the API, draw the read path, and then go deep on the three parts that matter: the geospatial index, ranking and filtering, and reviews/ratings at scale.

Out of scope (say so): business-owner tools and ad bidding, reservations/ordering, the recommendation feed, photo upload pipeline internals (mention CDN, don't design transcoding), and abuse/fraud detection beyond basic double-review prevention.

Functional requirements

• Search nearby businesses. Given a lat/lng and radius R, return businesses inside that circle, optionally filtered by category, minimum rating, and open-now, ranked by a blend of distance and rating.
• View a business profile. Return the business's details — name, address, categories, hours, average rating, review count, photos (CDN URLs), and a page of reviews.
• Write a review. A user posts a star rating (1–5) plus optional text for a business they haven't already reviewed. The business's average rating updates.
• Read reviews. Paginated reviews for a business, newest or most-helpful first.

Out of scope (state it): owner dashboards, ads, reservations/ordering, personalized recommendations, and the media upload pipeline (we store CDN URLs and move on).

Non-functional requirements

• Read-heavy, low-latency search. Search and profile reads dominate by orders of magnitude. A search must return in well under ~200 ms p99. This drives the whole design toward a precomputed spatial index plus caching.
• Freshness tolerance. A business's average rating being a few seconds stale is fine. A newly added business appearing in search a minute late is fine. Strong consistency is not required on the read path — eventual consistency is acceptable.
• Availability over strong consistency. A slightly stale or slightly incomplete result set is better than an error page. Search should degrade gracefully.
• No double-reviews. A user may hold at most one review per business (they can edit it). This is a correctness requirement, enforced on the write path.
• Uneven geographic density. Manhattan has thousands of businesses per km²; rural areas have a handful per 100 km². The spatial index must handle both without either blowing up dense cells or scanning empty space.
• Durability of writes. Reviews and businesses must be durably stored; the search index is a derived structure that can be rebuilt from the source-of-truth business store.

Estimations

State assumptions first; the point is to justify design choices, not to nail exact numbers.

Rounded assumptions

• Businesses: ~50M globally (order of magnitude). Each business row is small (~1–2 KB of metadata); 50M × ~2 KB ≈ ~100 GB — comfortably fits a sharded relational store, and the searchable subset fits in memory-backed indexes.
• Searches/sec (read-heavy): assume ~100M searches/day → ~1,200 searches/sec average, call it ~5–10K/sec at peak. Profile views are similar or higher. Reads dominate.
• Reviews/day: assume ~1–5M new reviews/day → ~50 reviews/sec average. Writes are ~100× rarer than reads — this ratio is the headline.
• Photos: many per business, but they are static blobs served from a CDN; they never touch the search path. Only CDN URLs live in the DB.
• Hot businesses: rating/review activity is power-law — a handful of viral businesses (a newly opened famous restaurant) take a disproportionate share of review writes and profile reads, creating a hot key.

How the numbers affect the design

Core entities / data model

Four things are stored: the business (profile + location), the review (rating + text), the rating aggregate (denormalized average + count on the business), and the geo index (cell → business ids, a derived structure).

The Business row stores both the raw lat/lng and a precomputed cell_id (geohash string or quadtree/S2 cell). The raw coordinates are needed for the exact-distance filter and ranking; the cell_id is what the geo index buckets on. Photos are CDN URLs only — never bytes in the DB.

The avg_rating and review_count are denormalized onto the business row so a profile render and a rating filter never require a COUNT/AVG scan over the reviews table. They are kept fresh from the RatingAggregate (deep dive 3). The RatingAggregate stores sum_of_ratings and review_count rather than a precomputed average, because updating an average incrementally from a raw average is lossy — you need the sum and count to fold in a new rating correctly.

The Review table has a unique constraint on (business_id, user_id) — this is what enforces the no-double-review rule at the storage layer.

Where each lives. Business and Review rows live in a sharded relational DB (Postgres, sharded by business_id). The GeoIndex lives in a memory-backed store keyed by cell_id (Redis, or a dedicated spatial index / Elasticsearch geo index) so a cell lookup is O(1). The RatingAggregate counters for hot businesses are buffered in Redis and flushed to the DB asynchronously (deep dive 3). Photos live in a blob store served through a CDN.

API design

Four operations carry the system: nearby search, profile read, review write, and review list.

Search nearby businesses

GET /api/search?lat=37.77&lng=-122.41&radius_km=2&category=coffee&min_rating=4&open_now=true&limit=20&cursor=<opaque>
200 OK
Returns: { "results": [ { business_id, name, distance_km, avg_rating, review_count, ... } ], "next_cursor": "..." }

The core read. Server computes the covering cells for the (lat/lng, radius) query, gathers candidate business ids from the geo index, applies the exact-distance filter and the category/rating/open-now filters, ranks, and returns a page. Cursor-based pagination (never offset — the candidate set shifts as businesses are added).

Get a business profile

GET /api/businesses/{business_id}
200 OK
Returns: { business, avg_rating, review_count, photo_urls, reviews: { items: [...], next_cursor } }

Served cache-first (Redis or CDN for the static parts). avg_rating is the denormalized value (eventually consistent). Photos are CDN URLs the client fetches directly.

Write a review

POST /api/businesses/{business_id}/reviews
Body: { "rating": 5, "text": "great espresso" }
201 Created  (or 409 Conflict if the user already reviewed this business)
Returns: { review_id, created_at }

Inserts a Review with the (business_id, user_id) unique constraint (returns 409 on a duplicate — the double-review guard). Then updates the RatingAggregate (sum += rating, count += 1) and asynchronously refreshes the denormalized avg_rating on the business row (deep dive 3).

List reviews

GET /api/businesses/{business_id}/reviews?sort=helpful&limit=20&cursor=<opaque>
200 OK
Returns: { items: [...], next_cursor: "..." }

Paginated reviews from the DB (or a read replica), sorted by recency or helpful_count.

High-level architecture

There are two paths: a high-volume read path (search + profile) served from precomputed indexes and caches, and a low-volume write path (review → rating aggregate → index refresh). We'll draw the read path first because it dominates.

1. Read path — nearby search

flowchart LR
    Client["Client"] -->|"GET /search\n(lat,lng,radius,filters)"| SearchSvc["Search Service"]
    SearchSvc -->|"compute covering cells\nfor (point, radius)"| GeoIdx[("Geo Index\ncell_id -> business_ids")]
    GeoIdx -->|"candidate business_ids"| SearchSvc
    SearchSvc -->|"multi-get metadata\n+ exact distance + filters"| BizDB[("Business Store\n(read replica)")]
    SearchSvc -->|"rank by distance + rating"| Rank["Ranking"]
    Rank -->|"page of results"| Client
    SearchSvc -.->|"cache hot queries"| Cache[("Query/Result Cache\n(Redis)")]

1. The Search Service converts the (lat/lng, radius) into a small set of covering cells (deep dive 1).
2. It reads the candidate business_ids from the geo index for those cells — an O(cells) set of lookups.
3. It multi-gets business metadata (from a read replica), applies the exact haversine-distance filter (cells are a coarse over-approximation of the circle) plus category/rating/open-now filters.
4. It ranks the survivors by a distance+rating blend (deep dive 2) and returns a page.
5. Popular queries (dense downtown areas, "coffee near me") are cached; identical repeat queries hit the cache, not the index.

2. Read path — business profile

Profile reads are cache-first. The Business Service checks Redis; on a hit it returns the cached profile, on a miss it reads a business replica and paginates reviews from a review replica. Static business data (name, address, photos) is highly cacheable — served from Redis and, for media, a CDN the client fetches directly. The denormalized avg_rating avoids any aggregation at read time; for hot businesses the freshest average is read from the Redis rating buffer (deep dive 3), otherwise the async flush keeps the DB value fresh within seconds. This path is drawn end-to-end in the combined architecture diagram below.

3. Write path — review and rating update

sequenceDiagram
    participant C as Client
    participant API as Review Service
    participant DB as Review Store
    participant AGG as Rating Aggregate (Redis)
    participant IDX as Index/Denorm Refresh

    C->>API: POST review (rating, text)
    API->>DB: INSERT review (unique (business_id,user_id))
    alt already reviewed
        DB-->>API: unique violation
        API-->>C: 409 Conflict
    else new review
        DB-->>API: ok
        API->>AGG: update sum and count
        API-->>C: 201 Created
        AGG-->>IDX: async: recompute avg_rating on business row
    end

The write is validated (unique constraint), the rating aggregate is incremented, and the denormalized average is refreshed asynchronously. Adding a new business follows a similar async pattern: insert the row, compute its cell_id, and add its id to the geo index cell bucket.

4. Combined architecture

flowchart LR
    Client["Client"] --> GW["API Gateway\n+ CDN"]
    GW -->|"GET /search"| SearchSvc["Search Service"]
    GW -->|"GET /businesses/{id}"| BizSvc["Business Service"]
    GW -->|"POST review"| RevSvc["Review Service"]
    SearchSvc --> GeoIdx[("Geo Index\n(cells)")]
    SearchSvc --> Cache[("Redis cache")]
    SearchSvc --> BizRR[("Business replica")]
    BizSvc --> Cache
    BizSvc --> BizRR
    BizSvc --> RevRR[("Review replica")]
    RevSvc --> BizDB[("Business primary")]
    RevSvc --> RevDB[("Review primary")]
    RevSvc --> Agg[("Rating counters\n(Redis)")]
    Agg -.->|"async flush"| BizDB
    BizDB -.->|"replicate"| BizRR
    RevDB -.->|"replicate"| RevRR
    RevSvc -.->|"add id to cell"| GeoIdx

The read path (search + profile) and the write path (review + aggregate) are decoupled. A burst of reviews on a hot business never slows a search; the geo index and caches serve reads independently of the write throughput.

Deep dives

1. The geospatial index — mapping "within R km" to cells

This is the heart of the problem and where the interview is won or lost. The naive answer — SELECT * FROM businesses WHERE lat BETWEEN ? AND ? AND lng BETWEEN ? AND ? — is the trap. It cannot use a single index efficiently (a B-tree on lat and a B-tree on lng each prune one dimension, then the DB intersects two large candidate sets), and it degrades badly at scale. You need a spatial index that turns two coordinates into one indexable key — or, at the DB layer, a native spatial index (an R-tree / GiST, as in PostGIS) that answers bounding-box queries directly. The geohash/quadtree approach below is the app-level, shardable alternative you can build on any plain KV store.

The three serious options:

flowchart TD
    Q["query point\n+ radius 2km"] -->|"geohash at precision p, cell size >= R"| C["center cell\n'9q8yy'"]
    C -->|"add 8 neighbors\n(handle boundary)"| Nine["3x3 cell block\n(covers circle when cell >= R)"]
    Nine -->|"union business_ids"| Cand["candidate set"]
    Cand -->|"exact haversine\n< 2km ?"| Res["final results"]

flowchart TD
    Root["root cell (world)"] --> A["dense region\n(splits deeply)"]
    Root --> B["sparse region\n(stays one leaf)"]
    A --> A1["leaf <=100"]
    A --> A2["leaf <=100"]
    A --> A3["leaf <=100"]
    A --> A4["leaf <=100"]
    Query["(point, radius)"] -.->|"keep children whose\nbbox intersects circle"| A
    Query -.-> B

S2 / H3 — the production libraries. In practice you'd reach for S2 (Google, quadtree cells on a cube projection ordered by a Hilbert curve, giving hierarchical 64-bit cell ids that range-scan cleanly) or H3 (Uber, hexagonal cells with uniform 6-neighbor adjacency, nice for radius "rings"). Both give you multi-resolution cell ids so you can range-query a region and pick a resolution per query. Mentioning these signals real-world awareness; you don't need to implement them.

Recommendation. For the interview: lead with geohash (simple, correct, easy to explain boundary handling and precision), and escalate to a quadtree (or S2/H3) the moment uneven density comes up. Store the chosen cell_id denormalized on the business row so the index is a simple cell_id → {business_ids} map that any KV store can hold.

2. Ranking and filtering — distance, rating, and cheap filters

Once the geo index hands you a candidate set (a few hundred businesses at most, thanks to the covering cells), you filter and rank. The order of operations matters for performance: cheap, high-selectivity filters first; expensive ranking last.

Filtering, in order:

1. Exact distance — compute the haversine distance for each candidate and drop those outside radius R. The cells were a coarse over-approximation; this trims the corners of the 3×3 block down to the true circle.
2. Category — filter to businesses whose categories[] contains the requested category. Cheap set membership; can be pushed into the index by keying on (cell_id, category) if category filtering is common.
3. Min rating — drop businesses below min_rating using the denormalized avg_rating (no aggregation needed — that's why it's denormalized).
4. Open-now — evaluate the business's hours against the current local time in the business's timezone. This is a subtle correctness point: "open now" is relative to where the business is, not where the searcher is.

Ranking the survivors: combine distance and rating into a single score. A simple, defensible formula:

score = w_distance * proximity(distance) + w_rating * normalized_rating + w_relevance * text_match

proximity(d)      = 1 / (1 + d)      # closer is better, decays with distance
normalized_rating = (avg_rating - 1) / 4   # map 1..5 stars to 0..1
text_match        = 0 unless text search is used (see the search-extension section below)

• Precompute vs query-time ranking. You cannot fully precompute the score because distance depends on the searcher's location, which is different every query. But you can precompute the per-business parts (normalized rating, popularity, a quality prior) and combine them with the query-time distance cheaply. This is the standard split: static signals precomputed and stored, dynamic signals (distance, freshness) computed per request over the small candidate set.
• Because the candidate set is small (covering cells bound it), even a somewhat expensive ranking pass is fine — you're ranking hundreds of rows, not millions.

flowchart LR
    Cand["candidate set\n(from covering cells)"] -->|"exact haversine < R"| F1["distance filter"]
    F1 -->|"category contains ?"| F2["category filter"]
    F2 -->|"avg_rating >= min ?"| F3["rating filter"]
    F3 -->|"open in business TZ ?"| F4["open-now filter"]
    F4 -->|"score = distance + rating\n(+ relevance)"| Rank["rank + page"]

For richer text relevance ("best ramen"), you'd layer an inverted-index search (Elasticsearch) that also holds the geo field, letting one query do both text match and geo filtering. Mention it as the production path; the from-scratch answer is the geo index + denormalized filters above.

3. Reviews and ratings at scale — aggregation, hot businesses, freshness

Reviews are the write path, and although writes are rare in aggregate (~50/sec), they are power-law skewed: a newly viral business can take thousands of reviews and profile reads in a burst, creating a hot key on that one business's rating counter.

Keeping the average fresh. The business row stores a denormalized avg_rating and review_count. On each new review you must fold the new rating into the average. The correct way is to keep a sum and count, not just the average:

new_sum   = old_sum + rating
new_count = old_count + 1
avg_rating = new_sum / new_count

Storing only the average would make incremental updates lossy (you'd have to reconstruct the sum). The RatingAggregate holds (sum_of_ratings, review_count); avg_rating on the business row is derived and refreshed from it.

The hot-business counter problem. A naive UPDATE businesses SET review_count = review_count + 1, ... on every review serializes writes against one row. For a viral business that's a hot key. The fix is the standard sharded counter plus buffered flush:

Preventing double-reviews is enforced by the unique (business_id, user_id) constraint — an atomic conditional insert. A second review attempt returns 409 Conflict; an edit is an UPDATE of the existing row, which must adjust the aggregate by the delta (sum += new_rating - old_rating, count unchanged) rather than adding a fresh review.

Tradeoffs & bottlenecks

• Geohash vs quadtree. Geohash is simple (prefix strings, any B-tree/KV index, easy boundary reasoning) but uses a uniform grid that struggles with density skew. A quadtree is density-adaptive (bounded occupancy per cell) but more complex to build, rebalance, and update concurrently. Lead with geohash; escalate to quadtree/S2/H3 when density is the concern.
• Cell size vs query radius. Coarse cells → fewer cells to fetch but larger candidate sets (more exact-distance filtering). Fine cells → smaller candidate sets but more cells (and more neighbor cells) per query. Tune precision to the typical radius.
• Precompute vs query-time ranking. Static signals (normalized rating, popularity prior) precomputed; dynamic signals (distance) computed per query over the small candidate set. You cannot precompute the full score because distance depends on the searcher's location.
• Exact vs approximate average rating. Buffering rating updates in Redis and flushing asynchronously gives eventual consistency (seconds of lag) but eliminates the hot-key write bottleneck. Exact real-time averages would serialize writes on one row.
• Read replicas vs consistency. Serving searches and profiles from read replicas scales reads but adds replication lag — a just-written review may not appear on a replica for a moment. Acceptable given the freshness tolerance.
• Cache invalidation. Cached profiles/search results can go stale when a review lands or a business updates hours. Use short TTLs on volatile fields (rating) and long TTLs / CDN for static fields (name, photos, address).
• Index rebuild. The geo index is derived; rebuilding it (after a schema change or corruption) means rescanning 50M businesses and recomputing cells — a batch job, not a live-path concern, but plan for it.

Extensions if asked

• Text relevance search. "Best ramen near me" needs an inverted index (Elasticsearch) with a geo field, so one query does text match + geo filter + rating. This subsumes the hand-rolled geo index for richer queries.
• Personalized ranking. Blend in the user's past behavior, price preferences, and dietary filters — a full recommendation layer on top of the geo candidate set. Mention it; don't design it.
• Real-time "open now" and wait times. Live occupancy / wait-time estimates would add a streaming layer feeding per-business state. The static hours check is the baseline.
• Photo pipeline. Upload → blob store → transcode thumbnails → CDN, exactly like other media systems. We store only URLs; the pipeline is a separate design.
• Sharding the geo index geographically. Partition cells by region so a search hits only the shard(s) covering the query area, and dense regions get their own capacity.
• Autocomplete for business/category names. A trie or prefix index over names — a separate read-path structure from the geo index.

What interviewers look for & common mistakes

What interviewers usually reward:

• Naming the spatial-index problem up front — recognizing that a two-column lat/lng range scan can't be served by one index, and reaching for a geohash or quadtree deliberately.
• Explaining how a radius query maps to cells — computing covering cells, fetching the neighbor cells (not just the center), and applying an exact haversine filter to trim the over-approximation.
• Handling cell boundaries — the single most common miss; a point near a cell edge needs the neighboring cells queried too.
• Addressing uneven density — knowing that a fixed geohash precision breaks in dense cities, and that a quadtree (or variable precision) bounds per-cell occupancy.
• Framing the system as read-heavy — precomputed index, read replicas, cache-first reads, denormalized ratings; treating writes as the rare path.
• The denormalized, incrementally-maintained average — sum+count on an aggregate, buffered in Redis for hot businesses, never a full AVG scan on read.
• The double-review guard — a unique (business_id, user_id) constraint, and adjusting the aggregate by the delta on an edit.

Before you finish, do a quick mistake check:

• Did you reject the naive lat/lng range scan and pick a real spatial index (geohash or quadtree)?
• Did you show how a "within R km" query becomes a set of covering cells, and include boundary/neighbor cells?
• Did you apply an exact-distance filter after the coarse cell lookup?
• Did you address uneven density (dense city vs rural) rather than assuming one uniform grid?
• Did you denormalize avg_rating and maintain it incrementally from a sum+count, instead of scanning reviews on every read?
• Did you buffer hot-business rating updates in Redis and flush asynchronously?
• Did you enforce no-double-review with a unique constraint, and handle edits as a delta?
• Did you frame the whole system as read-heavy and lean on caching + read replicas + a CDN for static business data?