Design Yelp

Difficulty: easy

Description: Design an online platform that supplies geo-based search and publishes crowd-sourced reviews about businesses similar to Yelp.

Introduction

Yelp is a popular online platform that helps users discover and evaluate local businesses. Users can search for nearby restaurants, salons, and other services using geo-based search functionality. The platform allows users to read and write reviews, rate businesses, and access comprehensive business information including contact details, hours of operation, and photos.

Functional Requirements

Core Requirements

1. Search and view businesses: User should be able to search for businesses by keyword and location, and view detailed information about a business.

2. Post a review: User should be able to post a review for a business.

3. Get paginated reviews: User should be able to get paginated reviews for a business.

Out of Scope

• Business management and maintenance
• Authentication and authorization
• Rate limit and anti-abuse

Scale Requirements

• 1M Daily Active Users
• Read:write ratio = 100:1
• Data retention for 5 years
• Assuming that each user performs 1 write operation per 10 days.
• Assuming that each review is 1KB in size.

Non-Functional Requirements

• High Availability: Implement redundancy and failover strategies to ensure that the system remains operational even in the event of component failures.
• Scalability: The system should be able to scale horizontally to accommodate increasing loads and spikes in user activity without degradation in performance.
• Low Latency: Optimize database queries, use efficient caching mechanisms, and minimize network latency to ensure a fast user experience.

API Endpoints

GET /search?lon={longitude}&lat={latitude}&radius={radius}&keyword={keyword}

Searches for businesses within a circular area defined by the given longitude and latitude as the center and the specified radius, containing the keyword.

Response Body:

{
  "status": 200, // number
  "business": [...] // business ids array
}

GET /businesses/{business_id}

Retrieves detailed information about a business, including user reviews, ratings, and photos.

Response Body:

{
  "business_id": "The id of the business",
  "latitude": 37.4219407, // double
  "longitude": -122.0019211, // double
  "name": "The business name",
  "description": "The description of the business",
  "street": "123 Main St",
  "city": "Metropolis",
  "state": "NY",
  "zip_code": "12345"
  "rating": 4.6 // number
}

POST /reviews

Enables users to submit a review for a business, which includes a rating and text content.

Request Body:

{
  "business_id": "The id of the business",
  "rating": 4.6, // number
  "content": "The content of"
}

Response Body:

{
  "status": 200,
  "review_id": "The unique id of the review"
}

GET /businesses/{business_id}/reviews?page={page_number}&limit={limit_per_page}&last_timestamp={last_page_timestamp}

Retrieves a paginated list of reviews for a specific business.

Response Body:

{
  "status": 200,
  "current_page": 1,
  "per_page": 10,
  "total_pages": 5,
  "total_reviews": 50,
  "reviews": [
    {
      "review_id": "The unique id of the review",
      "user_id": "The unique id of the user who wrote the review",
      "rating": 4.5,
      "content": "The written content of the review",
      "timestamp": "The date and time when the review was posted"
    },
    {
      "review_id": "Another unique id of a review",
      "user_id": "The unique id of another user",
      "rating": 3.8,
      "content": "The written content of another review",
      "timestamp": "The date and time when this review was posted"
    }
    // ... more reviews
  ]
}

High Level Design

1. Search and view businesses

User should be able to search for businesses by keyword and location, and view detailed information about a business.

The design focuses on optimizing read operations for business search and viewing:

Read Path (Customers):

1. The customer sends a request to fetch reviews.
2. The request goes through a Load Balancer, which forwards it to the Review Service.
3. The Review Service first checks the Cache for the requested review data.
   • If the data is found in the Cache (cache hit), it is returned directly to the customer.
   • If the data is not found in the Cache (cache miss), the Review Service queries the Review Database for the required reviews.
4. If the data was fetched from the database, the Review Service updates the Cache with this data for future requests.
5. The Review Service returns the review data to the customer.

Data Sources:

1. Business Database serves as the source of truth for all business data
2. Cache stores frequently accessed business information for fast retrieval
3. Elasticsearch indexes business data for advanced search capabilities
4. Change Data Capture (CDC) ensures data consistency between sources

Businesses Table

CREATE TABLE Businesses (
  business_id SERIAL PRIMARY KEY,
  owner_id INT REFERENCES Users(user_id),
  name VARCHAR(255) NOT NULL,
  description TEXT,
  city VARCHAR(255) NOT NULL,
  state VARCHAR(255) NOT NULL,
  zip_code VARCHAR(10) NOT NULL,
  latitude FLOAT NOT NULL,
  longitude FLOAT NOT NULL,
  category VARCHAR(255) NOT NULL,
  -- Additional fields for services, amenities, etc.
);

2. Post a review

User should be able to post a review for a business.

The design implements an asynchronous write architecture for review submission:

Write Path (Reviewers):

1. Reviewers submit reviews through a load balancer
2. Load balancer routes write requests to the Review Service
3. Review Service processes review logic and sends data to Message Queue
   • Handles POST /review
4. Message Queue acts as an asynchronous buffer, decoupling the service
5. Database Updater consumes messages and writes reviews to Review Database and Cache
6. Review Database stores all review data as the source of truth

Reviews Table

CREATE TABLE Reviews (
  review_id SERIAL PRIMARY KEY,
  business_id INT REFERENCES Businesses(business_id),
  user_id INT REFERENCES Users(user_id),
  rating DECIMAL(2, 1) CHECK (rating >= 0 AND rating <= 5),
  content TEXT,
  review_date TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
  -- Additional fields like photos, response from business, etc.
);

3. Get paginated reviews

User should be able to get paginated reviews for a business.

The design implements a paginated read architecture for review retrieval:

1. Customers send paginated review requests through a load balancer
2. Load balancer routes read requests to the Review Service
3. Review Service queries Cache and Review Database for reviews
   • Handles GET /business/{business_id}/reviews?page={page_number}&limit={limit_per_page}&last_timestamp={last_page_timestamp}

For frequently accessed reviews, the Cache is used to store data, and the Review Service reads from the Cache.

• Such as the first few pages of reviews, popular reviews, etc.

For infrequently accessed reviews, the Review Service reads from the Review Database.

• Such as very old reviews.

Deep Dive Questions

How to implement Geo-spatial search using QuadTrees?

In the High Level Design, we use Elasticsearch to implement Geo-spatial search, but in the interview, there might be higher requirements. Let's see how to implement Geo-spatial search using QuadTrees.

QuadTrees are a type of data structure that is particularly well-suited for spatial indexing, which is the process of organizing data according to their geographic locations. This makes them an excellent choice for implementing location-based search in a system like Yelp, where users need to find businesses near a certain location. Unlike a naive approach that might involve dividing the space into uniform squares for search purposes, QuadTrees offer a dynamic and efficient solution. They adapt to the distribution of data points by subdividing the space into smaller regions only where the density of points is high. This adaptability reduces space wastage and speeds up the search process by quickly eliminating irrelevant areas.

However, it's important to note that in real-world applications, Geo-hashing is often preferred for its simplicity and efficiency. Geo-hashing converts geographic locations into a short string of characters and numbers, facilitating fast and accurate proximity searches. It simplifies handling spatial data in distributed systems due to its straightforward string-based representation. While QuadTrees provide a powerful method for spatial indexing with their dynamic subdivision of space, Geo-hashing is frequently used for its scalability and ease of integration into existing systems.

By comparing QuadTrees and Geo-hashing, we see that each has its advantages. QuadTrees excel in scenarios where the spatial distribution of data points is highly uneven, allowing for more efficient data organization and search. On the other hand, Geo-hashing offers a more uniform approach to spatial indexing, making it particularly useful for distributed systems where simplicity and speed are paramount. Depending on the specific requirements and constraints of the system being designed, either approach—or even a combination of both—could be employed to achieve efficient location-based search functionality.

In this document, we focus on implementing QuadTrees to demonstrate a dynamic and efficient method for spatial indexing.

Basic Concept

A QuadTree is a tree data structure in which each internal node has exactly four children. It is used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The regions may represent different levels of detail at different levels of the tree.

How QuadTrees Work

1. Initialization: The entire map is considered a square and represented as the root of the QuadTree. This square is then divided into four equal-sized quadrants.

2. Insertion: Each business location is inserted into the QuadTree. The insertion starts from the root node. If a node represents a region that should be subdivided (because it contains more than one point or exceeds a certain density), that node is split into four child quadrants, and the points it contains are distributed among these children. This process continues recursively.

3. Searching: To find all businesses within a certain radius of a point, the search begins at the root node and recursively visits nodes that intersect with the search area. If a node's region lies entirely within the search area, all businesses in that node are part of the result set. If a node's region does not intersect at all with the search area, it and its children are ignored.

Implementing QuadTrees for Yelp

1. Data Structure: Define the QuadTree node structure with properties for bounds (representing the spatial region), points (businesses within the region), and children (four child nodes).

class QuadTreeNode:
    def __init__(self, bounds):
        self.bounds = bounds  # The spatial region this node covers
        self.points = []      # Businesses within this region
        self.children = []    # Four children, one for each quadrant

2. Insert Businesses: When a new business is added, insert it into the QuadTree based on its geographic coordinates. If a node exceeds its capacity, subdivide it and redistribute the businesses among the new child nodes.

def insert(self, business):
    if self.should_subdivide():
        self.subdivide()
    # Determine which child quadrant the business belongs to and insert it there.
    # If the node is a leaf and has not reached capacity, add the business to the points list.

3. Search Query: When a user searches for businesses within a certain radius of their location, perform a range search on the QuadTree. This will efficiently return all businesses within the search area.

def search(self, center, radius):
    results = []
    # Check if the search area intersects with the node's bounds.
    if self.bounds.intersect(center, radius):
        # Add businesses within the search area to the results.
        results.extend([business for business in self.points if business.is_within(center, radius)])
        # Recursively search child nodes.
        for child in self.children:
            results.extend(child.search(center, radius))
    return results

4. Optimization: To optimize the search, consider adding additional spatial indexes or heuristics that can skip unnecessary branches of the tree, further reducing the search space.

Challenges and Considerations

• Dynamic Updates: QuadTrees need to handle updates efficiently, such as when businesses close or change locations. This may require removing and re-inserting points, which can be computationally expensive.

• Load Balancing: In a real-world scenario, business locations are not evenly distributed. Some areas may have a high density of businesses, leading to deep QuadTree nodes. Balancing the tree to prevent very deep or unbalanced trees is important for performance.

• Memory Usage: Each node in the QuadTree stores a list of points and child nodes, which can lead to high memory usage. Pruning and garbage collection strategies may be necessary to manage memory.

• Concurrency: In a high-traffic system like Yelp, multiple read and write operations may occur simultaneously. Implementing concurrency control, such as read-write locks, can ensure data consistency.

By using QuadTrees for spatial indexing in the Yelp-like system, the platform can provide efficient and fast location-based searches.

How can we ensure the authenticity and fairness of the reviews and ratings submitted by users?