Design Yelp

Yelp is a proximity-based business discovery platform where users can search for nearby businesses, read reviews, view photos, and leave ratings. The core challenge is efficiently querying billions of locations to find relevant places within a given radius with minimal latency.

This walkthrough follows the Interview Framework and focuses on what you'd actually present in a 45-60 minute interview.

Phase 1: Requirements

Functional Requirements

1. Search nearby places — Users should be able to search for businesses by location (latitude/longitude) and radius, optionally filtered by category (restaurants, cafes, etc.)
2. Add a place — Business owners can add new places with name, description, category, location, and photos
3. Add reviews — Users can submit reviews with text, ratings (1-5 stars), and photos
4. View place details — Users can view business information, photos, and reviews

Non-Functional Requirements

Capacity Estimation

Scale assumptions:

• 500 million places globally
• 60 million daily active users
• 1 million new reviews per day
• Read-heavy: ~100:1 read-to-write ratio

Storage:

Places:  500M × 1.3 KB = ~650 GB
Photos:  500M × 280 B (metadata) = ~140 GB
         + actual images in blob storage (~3 MB each = 1.5 PB)
Reviews: 1M/day × 537 B × 365 days × 10 years = ~2 TB
Users:   178M × 264 B = ~47 GB

Total metadata: ~3 TB (fits on a single large database, but we'll shard for performance)

Throughput:

Search QPS: 60M DAU × 5 searches/day / 86,400 sec = ~3,500 QPS
           Peak (3x): ~10,000 QPS

Write QPS: 1M reviews/day / 86,400 = ~12 writes/sec (negligible)

Phase 2: Data Model

Core Entities

-- Places table
Place {
  place_id:    BIGINT PRIMARY KEY  -- 8 bytes, from ID generator
  name:        VARCHAR(256)
  description: TEXT(1000)
  category:    VARCHAR(64)         -- "restaurant", "cafe", etc.
  latitude:    DOUBLE              -- 8 bytes
  longitude:   DOUBLE              -- 8 bytes
  review_count: INT                -- number of reviews
  rating_sum:  BIGINT              -- sum of all ratings
  avg_rating:  DECIMAL(2,1)        -- computed, updated periodically
  last_review_at: TIMESTAMP        -- denormalized for recency ranking
  created_at:  TIMESTAMP
}

-- Reviews table
Review {
  review_id:   BIGINT PRIMARY KEY
  place_id:    BIGINT              -- FK to Place
  user_id:     BIGINT              -- FK to User
  rating:      TINYINT             -- 1-5
  text:        TEXT(512)
  created_at:  TIMESTAMP
}

-- Review daily aggregates for batch rating updates
ReviewDailyAgg {
  place_id:     BIGINT
  bucket_start: DATE               -- e.g., 2024-07-10
  rating_sum:   INT
  review_count: INT
  PRIMARY KEY (place_id, bucket_start)
}

-- Photos table (metadata only, actual images in blob storage)
Photo {
  photo_id:    BIGINT PRIMARY KEY
  place_id:    BIGINT              -- nullable if photo is tied to a review
  review_id:   BIGINT              
  user_id:     
  photo_url:   ()        
  created_at:  
}




 {
  user_id:      
  name:        ()
  email:       ()
  created_at:  
}

Geospatial Index Structure

For efficient proximity search, we need a spatial index. The key data structure is a QuadTree stored in memory:

QuadTreeNode {
  // Bounding box
  top_left:     (latitude, longitude)
  bottom_right: (latitude, longitude)

  // Either children (internal node) or places (leaf node)
  children:     QuadTreeNode[4]  // NW, NE, SW, SE
  places:       List<{place_id, latitude, longitude}>  // Leaf nodes, max 500
}

Phase 3: API Design

REST API

# Search nearby places
GET /v1/places/search
  Query params:
    latitude:   float (required)
    longitude:  float (required)
    radius:     int   (meters, default 5000, max 50000)
    category:   string (optional, e.g., "restaurant")
    limit:      int   (default 20, max 100)
  Response:
    {
      "places": [
        {
          "place_id": "123",
          "name": "Joe's Pizza",
          "category": "restaurant",
          "latitude": 40.7128,
          "longitude": -74.0060,
          "avg_rating": 4.5,
          "distance_meters": 250,
          "thumbnail_url": "https://..."
        }
      ],
      "next_cursor": "..."
    }

  Cursor pagination:
    next_cursor encodes the last item's (score, distance_meters, place_id)   


 
  
    {
       ,
       ,
       ,
       ,
       ,
       ,
       ,
       ,
       [, ],
       {}
    }


 
  
    {
       ,
       ,
       ,
       ,
       ,
       []
    }


 
  
    {
       ,
       ,
       []
    }


 
  
          
      
     

Phase 4: High-Level Design

Architecture Diagram

Component Responsibilities

Search Flow Walkthrough

1. User searches "coffee shops within 2km"
   → Request: GET /v1/places/search?latitude=40.7&longitude=-74.0&radius=2000&category=cafe

2. API Gateway routes to Search Service

3. Search Service:
   a. Checks cache for this query (geohash + category + radius)
   b. Cache miss → queries a QuadTree replica (load balanced)
   c. QuadTree returns candidate place_ids from intersecting nodes (superset)

  4. Search Service aggregates:
   a. Filters to exact radius using Haversine distance
   b. Filters by category (if specified)
   c. Ranks by relevance (normalized scores: distance × 0.4 + rating × 0.4 + recency × 0.2)
      with a stable tie-breaker (place_id) for cursor pagination
   d. Takes top N results

5. Search Service enriches:
   a. Batch-fetches place details via Place Service or shard router,
      grouping place_ids by shard and using cache to avoid fan-out
   b. Returns enriched results to client

Latency breakdown:
- Cache check: ~1ms
- QuadTree lookup: ~5-10ms (in-memory)
- Distance filtering + ranking: ~2ms
- DB fetch (20 places, cached): ~10-30ms
- Total: 20-50ms typical, <100ms P99

Write Flow: Adding a New Place

1. Business owner submits new place
   → POST /v1/places with place details + photos

2. Place Service:
   a. Validates input
   b. Uploads photos to Blob Storage, gets URLs
   c. Inserts place record into Place DB
   d. Publishes "place_created" event to message queue

3. QuadTree Update Worker (async):
   a. Consumes "place_created" event
   b. Determines which segment the place belongs to
   c. Updates the QuadTree (may trigger split if segment > 500 places)

Phase 5: Deep Dives

Deep Dive 1: Geospatial Indexing with QuadTree

The core challenge is: How do we efficiently find all places within a radius?

Why Not Just Use SQL?

A naive approach:

SELECT * FROM places
WHERE latitude BETWEEN ? AND ?
  AND longitude BETWEEN ? AND ?

Problems:

• Even with B-tree indexes on lat/lng, this scans many rows
• Can't efficiently combine two range queries
• Gets slower as data grows

QuadTree Solution

A QuadTree recursively divides 2D space into four quadrants:

World (root)
├── NW quadrant
│   ├── NW-NW (leaf: [place1, place2, ...])
│   ├── NW-NE (leaf: [place3, ...])
│   └── ...
├── NE quadrant
├── SW quadrant
└── SE quadrant

Rules:

• Each leaf node contains at most 500 places
• When a leaf exceeds 500, split into 4 children
• Range queries use recursive tree traversal to find all intersecting nodes

Search Algorithm:

def search(node, center, radius):
    if not intersects(node.bounds, center, radius):
        return []

    if node.is_leaf():
        # Filter places within exact radius
        return [p for p in node.places
                if distance(p, center) <= radius]

    # Recursively search children
    results = []
    for child in node.children:
        results.extend(search(child, center, radius))
    return results

QuadTree Memory Requirements

Per place (raw data): place_id (8B) + lat (8B) + lng (8B) = 24 bytes
500M places × 24 bytes = 12 GB raw data

Leaf nodes: 500M places / 500 per leaf = 1M leaf nodes
Internal nodes: ~333K (roughly 1/3 of leaf count in a QuadTree)
Per internal node: bounding box (32B) + 4 child pointers (32B) = 64 bytes
Internal node overhead: 333K × 64B = ~21 MB

Object/runtime overhead: 2-3x for data structures, pointers, alignment
Realistic total: 30-50 GB

→ Fits on a large server (64-128 GB RAM)
→ Must replicate for fault tolerance (see below)

Time Complexity:

• Finding relevant segments: O(log N) where N = number of places
• For large radius spanning many segments: O(S × M) where S = segments, M = places per segment
• Typical search (5km radius): touches 10-50 segments → still very fast

QuadTree Replication and Fault Tolerance

Since the QuadTree is critical for all searches, we must replicate it:

QuadTree Cluster:
├── Primary (handles writes)
├── Replica 1 (read traffic)
└── Replica 2 (read traffic)

Replication strategy:
- Writes go to primary, async replicated to followers
- Reads load-balanced across all replicas
- If primary fails, promote a replica (leader election)

Rebuilding the QuadTree:

• Snapshot to disk periodically (serialize tree structure)
• On restart: load snapshot + replay recent changes from write-ahead log
• Full rebuild from database: ~30-60 minutes for 500M places
• Keep at least one replica alive during rebuilds

Deep Dive 2: Handling Hot Spots

Problem: Some areas (Manhattan, downtown SF) have far more places and queries than others.

Dynamic Segment Sizing

Instead of fixed-size grid cells, QuadTree naturally adapts:

• Dense urban areas → smaller segments (more splits)
• Rural areas → larger segments (fewer splits)

Replicating Hot Segments

For extremely popular areas:

1. Identify hot segments by query rate
2. Replicate those segments across multiple QuadTree servers
3. Load balancer distributes queries to replicas

Segment "Manhattan-Downtown":
  - Replica 1 (Server A)
  - Replica 2 (Server B)
  - Replica 3 (Server C)

Deep Dive 3: Caching Strategy

What to Cache

Cache-Aside Pattern for Search

def search_places(lat, lng, radius, category):
    # Use precision 5 (~5km × 5km cells) to group nearby queries
    # Cache a superset per cell so any point inside can be re-filtered accurately
    geo_cell = geohash(lat, lng, precision=5)
    cache_key = f"search:{geo_cell}:{category}:{radius}"

    cached = redis.get(cache_key)
    if cached:
        # Re-filter cached results for exact location (handles edge cases)
        return filter_by_distance(cached, lat, lng, radius)

    # Build a superset by searching from the cell center with an expanded radius
    center = geohash_center(geo_cell)
    expanded_radius = radius + cell_diagonal_meters(geo_cell) / 2

    # QuadTree returns place_ids only (no category stored in spatial index)
    place_ids = quadtree_search(center.lat, center.lng, expanded_radius)

    # Batch fetch place details from cache/DB, then filter by category
    places = batch_get_places(place_ids)
    results = [p for p in places if category is None or p.category == category]

    redis.setex(cache_key, 300, results)  # 5 min TTL
    return filter_by_distance(results, lat, lng, radius)

Deep Dive 4: Rating Calculation

Problem: Recomputing average rating on every review is expensive.

Recency signal: Store last_review_at on Place for ranking. Update it on each review write (synchronously with the review insert) or via a short-lag async job.

Approach 1: Incremental Update with Atomic Operations

# On new review - use atomic SQL update to avoid race conditions
def add_review(place_id, rating):
    db.execute("""
        UPDATE places SET
            review_count = review_count + 1,
            rating_sum = rating_sum + ?,
            avg_rating = (rating_sum + ?) / (review_count + 1)
        WHERE place_id = ?
    """, rating, rating, place_id)

Pros: Immediate updates, no race conditions with atomic SQL Cons: Can't easily apply complex weighting (e.g., recent reviews matter more)

Approach 2: Incremental Batch (Recommended)

Maintain a review_daily_agg table with (place_id, bucket_start, rating_sum, review_count) updated on each review write.

# Runs every hour - only processes places with new reviews
def recalculate_ratings():
    # Get places with review aggregates since last run (typically ~50K places/hour)
    places_to_update = db.query("""
        SELECT DISTINCT place_id FROM review_daily_agg
        WHERE bucket_start > NOW() - INTERVAL 1 HOUR
    """)

    for place_id in places_to_update:
        # Weighted average: recent buckets count more
        avg = db.query("""
            SELECT SUM(rating_sum * weight) / SUM(review_count * weight) FROM (
                SELECT rating_sum,
                       review_count,
                       CASE WHEN bucket_start > NOW() - INTERVAL 6 MONTHS THEN 1.5
                            WHEN bucket_start > NOW() - INTERVAL 2 YEARS THEN 1.0
                            ELSE 0.5 END as weight
                FROM review_daily_agg WHERE place_id = ?
            )
        """, place_id)
        update_place(place_id, avg_rating=avg)

Why incremental batch?

• Only processes ~50K places/hour (places with new reviews), not all 500M
• Runs in minutes, not days
• Can apply complex weighting logic
• No race conditions since it's a single writer
• Avoids scanning raw reviews by using time-bucketed aggregates

Deep Dive 5: Data Partitioning

Option 1: Partition by Region (Not Recommended)

Shard 1: North America
Shard 2: Europe
Shard 3: Asia
...

Problems:

• Hot spots (NYC has more queries than entire states)
• Cross-region queries are complex

Option 2: Partition by Place ID (Recommended)

place_id → hash(place_id) % num_shards → shard

Benefits:

• Even distribution regardless of geography
• Easy to add shards (consistent hashing)

QuadTree is replicated (not sharded) because:

• It only stores place_id + coordinates (~30-50 GB with overhead)
• Fits on a single large server, replicated across 3 nodes for fault tolerance
• Actual place details fetched from sharded DB after search

Search enrichment uses a shard router or Place Service to group place_ids by shard and batch requests to avoid scatter-gather per result.

Common Pitfalls

Interview Checklist

Before finishing your design, verify you've covered:

• Proximity search algorithm — Explained QuadTree (or alternative) for geospatial queries
• Search latency — Showed how caching + in-memory index achieves < 100ms typical
• Fault tolerance — QuadTree replicated, leader election for failover
• Hot spot handling — Discussed dynamic segments and replication for popular areas
• Write path — Explained async QuadTree updates for new places
• Rating system — Covered incremental batch vs atomic updates
• Data partitioning — Explained sharding strategy for the database
• Photo storage — Mentioned blob storage for images, only metadata in DB

Summary