Design Yelp

Constraints

The Set Up

Defining the Core Entities

1. Business : Represents a business or service listed on Yelp. Includes details like name, location, category, and average rating.
2. User : Represents a Yelp user who can search for businesses and leave reviews.
3. Review : Represents a review left by a user for a business, including rating and optional text.

Yelp Entities

The API

// Search for businesses
GET /businesses?query&location&category&page -> Business[]

// View business details and reviews
GET /businesses/:businessId -> Business & Review[]

// View business details
GET /businesses/:businessId -> Business

// View reviews for a business
GET /businesses/:businessId/reviews?page= -> Review[]

// Leave a review
POST /businesses/:businessId/reviews
{
  rating: number,
  text?: string
}

High-Level Design

1) Users should be able to search for businesses

Yelp High-Level Design

1. Client : Users interact with the system through a web or mobile application.
2. API Gateway : Routes incoming requests to the appropriate services. In this case, the Business Service.
3. Business Service : Handles incoming search requests by processing query parameters and formulating database queries to retrieve relevant business information.
4. Database : Stores information about businesses such as name, description, location, category, etc.

1. The client sends a GET request to /businesses with the search parameters as optional query params.
2. The API Gateway routes this request to the Business Service.
3. The Business Service queries the Database based on the search criteria.
4. The results are returned to the client via the API Gateway.

2) Users should be able to view businesses

Yelp High-Level Design

1. The client sends a GET request to /businesses/:businessId .
2. The API Gateway routes this to the Business Service.
3. The Business Service retrieves business details and reviews from the Database.
4. The combined information is returned to the client.

3) Users should be able to leave reviews on businesses

Yelp High-Level Design

1. The client sends a POST request to /businesses/:businessId/reviews with the review data.
2. The API Gateway routes this to the Review Service.
3. The Review Service stores it in the Database.
4. A confirmation is sent back to the client.

Potential Deep Dives

1) How would you efficiently calculate and update the average rating for businesses to ensure it's readily available in search results?

Bad Solution: Naive Approach

Approach

As alluded to, the simplest approach is to calculate the average rating on the fly. This is simple and requires no additional data or infrastructure.

We'd simply craft a query that joins the businesses and reviews and then calculates the average rating for each business.

SELECT
  b.business_id,
  b.name,
  b.location,
  b.category,
  AVG(r.rating) AS average_rating
FROM businesses b
JOIN reviews r ON b.business_id = r.business_id
GROUP BY b.business_id;

Challenges

While this approach is simple, it has significant scalability issues:

1. Performance degradation: As the number of reviews grows, this query becomes increasingly expensive. The JOIN operation between businesses and reviews tables can be particularly costly, especially for popular businesses with thousands or millions of reviews.
2. Unnecessary recalculation: The average rating is recalculated for every search query, even if no new reviews have been added since the last calculation. This is computationally wasteful.
3. Impact on read operations: Constantly running this heavy query for every search can significantly slow down other read operations on the database, affecting overall system performance.

Given our scale of 100M daily users and 10M businesses, this naive approach would likely lead to unacceptable performance and user experience issues.

Good Solution: Periodic Update with Cron Job

Approach

Alternatively, we could pre-compute the average rating for each business and store it in the database. This pre-computation can be done using a cron job that runs periodically (e.g., once a day, once an hour, etc). The cron job would query the reviews table, calculate the average rating for each business, and update a new average_rating column in the businesses table.

Now, anytime we search or query a business, we can simply read the average_rating from the database.

Periodic Update with Cron Job

Challenges

The main downside with this approach is that it does not account for real-time changes in reviews. You can imagine a business with very few reviews and a currently low average rating. If you give the business a 5-star rating, your expectation would be that the average rating increases to reflect your vote. However, since we're recalculating the average rating periodically, this may not happen for hours or even days, leading to a stale average rating and confused users.

Great Solution: Synchronous Update with Optimistic Locking

Approach

Our goal with the great solution is to make sure we can update the average rating as we receive new reviews rather than periodically via a cron job. Doing this is relatively straight forward in that we simply need to both add the new review to the Review table while also updating the average rating for the business in the Business table.

To make that update efficient, we can introduce a new column, num_reviews , into the Business table. Now, to update an average rating, we simple calculate (old_rating * num_reviews + new_rating) / (num_reviews + 1) , which is cheap, just a few CPU cycles so it can be done synchronously for each new review.

Synchronous Update with Optimistic Locking

Challenges

In doing this, we've actually introduced a new problem. What happens if multiple reviews come in at the same time for the same business? One could overwrite the other, leading to an inconsistent state!

Let's imagine a timeline of events:

1. Business A has 100 reviews with an average rating of 4.0
2. User 1 reads the current state: num_reviews = 100, avg_rating = 4.0
3. User 2 also reads the current state: num_reviews = 100, avg_rating = 4.0
4. User 1 submits a 5-star review and calculates: new_avg = (4.0 * 100 + 5) / 101 ≈ 4.01
5. User 2 submits a 3-star review and calculates: new_avg = (4.0 * 100 + 3) / 101 ≈ 3.99
6. User 1's update completes: num_reviews = 101, avg_rating = 4.01
7. User 2's update overwrites: num_reviews = 101, avg_rating = 3.99

The final state (num_reviews = 101, avg_rating = 3.99) is incorrect because it doesn't account for User 1's 5-star review. The correct average should be: (4.0 * 100 + 5 + 3) / 102 ≈ 4.00

To solve this issue, we can use optimistic locking. Optimistic locking is a technique where we first read the current state of the business and then attempt to update it. If the state has changed since we read it, our update fails. We'll often add a version number to the table you want to lock on, but in our case, we can just check if the number of reviews has changed.

Now, when user 2 would have overwritten user 1's review, our update will fail because the number of reviews has changed. User 2 will have to read the state again and recalculate the average rating. This solves the problem of concurrent updates and ensures the average rating is always up to date and consistent.

2) How would you modify your system to ensure that a user can only leave one review per business?

def leave_review(user_id, business_id):
    reviews_for_business = db.get_reviews_for_business(business_id)
    if user_id in reviews_for_business:
        return "User has already reviewed this business"
    else:
        db.leave_review(user_id, business_id)

ALTER TABLE reviews
ADD CONSTRAINT unique_user_business UNIQUE (user_id, business_id);

3) How can you improve search to handle complex queries more efficiently?

// This query sucks. Very very slow.
SELECT * 
FROM businesses 
WHERE latitude > 10 AND latitude < 20 
AND longitude > 10 AND longitude < 20
AND name LIKE '%coffee%';

Bad Solution: Basic Database Indexing

Approach

The first thing we could do to improve the performance of this query is to add a simple B-tree index on the latitude and longitude columns. Ideally, this would make it faster to find businesses within a bounding box.

CREATE INDEX idx_latitude_longitude ON businesses (latitude, longitude);

Challenges

The reality is this approach doesn't work as effectively as we might hope. The simple B-tree index we'd typically use for single-column or composite indexes is not well-optimized for querying 2-dimensional data like latitude and longitude. Here's why:

1. Range queries: When searching for businesses within a geographic area, we're essentially performing a range query on both latitude and longitude. B-tree indexes are efficient for single-dimension range queries but struggle with multi-dimensional ranges.
2. Lack of spatial awareness: B-tree indexes don't understand the spatial relationship between points. They treat latitude and longitude as independent values, which doesn't capture the 2D nature of geographic coordinates.

To truly optimize geographic searches, we need more specialized indexing structures designed for spatial data, such as R-trees, quadtrees, or geohash-based indexes. These structures are specifically built to handle the complexities of 2D (or even 3D) spatial data and can significantly improve the performance of geographic queries.

Great Solution: Elasticsearch

Approach

Instead, there are 3 different types of indexing strategies we'll need in order to search of 3, very different types of filters:

1. Location : To efficiently search by location we need to use a geospatial index like geohashes , quadtrees , or R-trees .
2. Name : To efficiently search by name we need to use a full text search index which uses a technique called inverted indexes to quickly search for terms in a document.
3. Category : To efficiently search by category we can use a simple B-tree index .

There are several technologies which support all three of these indexing strategies (and more). One common example is Elasticsearch .

Elasticsearch is a search optimized database that is purpose built for fast search queries. It's optimized for handling large datasets and can handle complex queries that traditional databases struggle with making it a perfect fit for our use case.

Elasticsearch supports various geospatial indexing strategies including geohashing, quadtrees, and R-trees, allowing for efficient location-based searches. It also excels at full-text search and category filtering, making it ideal for our multi-faceted search requirements.

We can issue a single search query to Elasticsearch that combines all of our filters and returns a ranked list of businesses.

{
  "query": {
    "bool": {
      "must": [
        {
          "match": {
            "name": "coffee"
          }
        },
        {
          "geo_distance": {
            "distance": "10km",
            "location": {
              "lat": 40.7128,
              "lon": -74.0060
            }
          }
        },
        {
          "term": {
            "category": "coffee shop"
          }
        }
      ]
    }
  }
}

Elasticsearch

Challenges

The main challenge you want to be aware of when introducing Elasticsearch is that you won’t want to use it as a primary database, this is a no-no. It is not optimized to maintain transactional data integrity with full ACID compliance, nor to handle complex transactions. Additionally, Elasticsearch’s fault tolerance mechanisms, while effective, require careful configuration to avoid potential data loss during node or network failures. It’s best utilized for what it’s designed for: search and analytical operations across large datasets, rather than primary data storage.

As a result, we need a way to ensure the data in Elasticsearch remains in sync (consistent) with our primary database. The best way to do this is to use a Change Data Capture (CDC) system to capture changes to the primary database and then apply them to Elasticsearch.

This works by having all DB changes captured as events and written to a queue or stream. We then have a consumer process that reads from the queue or stream and applies the same changes to Elasticsearch.

Great Solution: Postgres with Extensions

Approach

One way we can get around the consistency issue all together is to just use Postgres with the appropriate extensions enabled.

Postgres has a geospatial extension called PostGIS that can be used to index and query geographic data.

CREATE EXTENSION IF NOT EXISTS postgis;

Postgres also has a full text search extension called pg_trgm that can be used to index and query text data.

CREATE EXTENSION IF NOT EXISTS pg_trgm;

Postgres with Extensions

By using these extensions, we can create a geospatial index on the latitude and longitude columns and a full text search index on the business name and description columns without needing to introduce a new service.

Given that this is a small amount of data, 10M businesses x 1kb each = 10GB + 10M businesses x 100 reviews each x 1kb = 1TB , we don't need to worry too much about scaling, something that Elasticsearch excels at, so this is a perfectly reasonable solution.

However, it's worth noting that while PostGIS is excellent for geospatial queries, it may not perform as well as Elasticsearch for full-text search at very large scales.

1. They want you to determine and be able to talk about the correct geospatial indexing strategy. Essentially, this usually involves weighing the tradeoffs between geohashing and quadtrees, though more complex indexes like R-trees could be mentioned as well if you have familiarity. In my opinion, between geohashing and quadtrees, I'd opt for quadtrees since our updates are incredibly infrequent and businesses are clustered into densely populated regions (like NYC).
2. Next, you'll want to talk about second pass filtering. This is the process by which you'll take the results of your geospatial query and further filter them by exact distance. This is done by calculating the distance between the user's lat/long and the business lat/long and filtering out any that are outside of the desired radius. Technically speaking, this is done with something called the Haversine formula, which is like the Pythagorean theorem but optimized for calculating distances on a sphere.
3. Lastly, interviewer will often be looking for you to articulate the sequencing of the phases. The goal here is to reduce the size of the search space as quickly as possible. Distance will typically be the most restrictive filter, so we want to apply that first. Once we have our smaller set of businesses, we can apply the other filters (name, category, etc) to that smaller set to finalize the results.

4) How would you modify your system to allow searching by predefined location names such as cities or neighborhoods?

1. Go from a location name to a polygon.
2. Use that polygon to filter a set of businesses that exist within it.

1. Create a locations table with columns for name (e.g., "San Francisco"), type (e.g., "city", "neighborhood"), and polygon (to store the geographic data).
2. Populate this table with data from the chosen sources.
3. Index the name column for efficient lookups.

{
  "query": {
    "geo_bounding_box": { 
      "location": {
        "top_left": {
          "lat": 42,
          "lon": -72
        },
        "bottom_right": {
          "lat": 40,
          "lon": -74
        }
      }
    }
  }
}

{
  "id": "123",
  "name": "Pizza Place",
  "location_names": ["bay_area","san_francisco", "mission_district"],
  "category": "restaurant"
}

Final Design

Yelp Final Design

What is Expected at Each Level?

Mid-level

Senior

Staff+