System requirements

Functional:

1. User Registration and Login: Users should be able to create accounts, log in, and manage their profiles.
2. Search and Browse: Users should be able to search for local establishments such as restaurants, theaters, and shopping centers based on location, category, or keyword.
3. Location Details: Users should be able to view detailed information about each establishment, including address, contact information, opening hours, and reviews.
4. Review and Rating: Users should be able to leave reviews and ratings for establishments they have visited.
5. Recommendations: The platform should provide personalized recommendations to users based on their preferences and past reviews.
6. Bookmarking: Users should be able to bookmark or save their favorite establishments for future reference.
7. Reporting: Users should be able to report any inappropriate content or reviews on the platform.
8. Admin Panel: An admin panel should be available to manage user accounts, reviews, and overall platform operations.

Non-Functional:

• Performance:
• Response time: Users expect fast search results and quick loading times for pages. This can be specified in seconds (e.g., search results displayed within 2 seconds).
• Scalability: The platform should handle an increasing number of users and establishments over time (as indicated by the capacity estimation).
• Availability: The platform should be accessible to users most of the time. This can be expressed as a percentage of uptime (e.g., 99.9% uptime).
• Reliability: The platform should function consistently and deliver accurate information. This includes aspects like data consistency and minimizing errors.
• Security: The platform needs to protect user data (e.g., login credentials, reviews) and ensure secure transactions.
• Usability: The platform should be user-friendly and intuitive for people with varying technical skills. This includes a well-designed interface and clear navigation.
• Maintainability: The codebase should be easy to understand and modify for future updates and bug fixes.

Capacity estimation

We can estimate the total number of places in the system to be 200 Million with 100K requests per second. Considering the future scale for 5 years with 20% growth per year we should build our system for at least a scale of 5 years.

• Our system should be ready to manage the mammoth scale of 400 Million.
• Our system should be able to handle the load of 200K requests per second.

API design

1. User Registration API:
2. Description: Allows users to create new accounts on the platform.
3. Input: User details such as username, email, password.
4. Output: Success message or error if registration fails.
5. User Login API:
6. Description: Allows registered users to log in to their accounts.
7. Input: Username/email and password.
8. Output: Access token/session token upon successful login, or error message if authentication fails.
9. Search Establishments API:
10. Description: Enables users to search for local establishments based on location, category, or keyword.
11. Input: Search query (location, category, keyword).
12. Output: List of establishments matching the search criteria, including basic details like name, address, and category.
13. Get Establishment Details API:
14. Description: Retrieves detailed information about a specific establishment.
15. Input: Establishment ID or unique identifier.
16. Output: Detailed information about the establishment, including address, contact information, opening hours, reviews, and ratings.
17. Leave Review API:
18. Description: Allows users to leave a review and rating for an establishment.
19. Input: Establishment ID, user ID, review text, rating.
20. Output: Success message or error if review submission fails.
21. Get User Profile API:
22. Description: Retrieves user profile information.
23. Input: User ID or username.
24. Output: User profile details including username, email, profile picture, bookmarked establishments, etc.
25. Bookmark Establishment API:
26. Description: Enables users to bookmark or save their favorite establishments.
27. Input: Establishment ID, user ID.
28. Output: Success message or error if bookmarking fails.
29. Report Content API:
30. Description: Allows users to report inappropriate content or reviews on the platform.
31. Input: Reported content ID, reason for reporting.
32. Output: Success message or error if reporting fails.
33. Admin Panel APIs:
34. Description: APIs used by administrators to manage user accounts, reviews, and overall platform operations.
35. Input: Admin credentials, action parameters.
36. Output: Results of the requested administrative action (e.g., user banned, review deleted).

Database design

Database Choices

• User Data:
• Database Type: SQL (Relational Database Management System - RDBMS)
• Reasoning: User data typically has a structured format (username, email, password, etc.), making it well-suited for relational databases where ACID (Atomicity, Consistency, Isolation, Durability) properties are essential for maintaining data integrity.
• CAP Theorem Focus: Consistency Focused - Ensuring that user data remains consistent across all operations is crucial, making relational databases a suitable choice.

• Establishment Information:
• Database Type: SQL or NoSQL (Depends on the scale and complexity of data)
• Reasoning: If the establishment data is relatively structured (name, category, address, etc.), SQL databases can efficiently handle it. However, if the platform deals with massive amounts of data or requires flexible schema, NoSQL databases like MongoDB may be more suitable.
• CAP Theorem Focus: Balanced - Depending on the choice between SQL and NoSQL, the focus may vary. SQL databases prioritize consistency, while NoSQL databases may prioritize availability and partition tolerance.

• Reviews, Bookmarks, and Reports:
• Database Type: SQL or NoSQL (Depends on the scale and access patterns)
• Reasoning: These data types are typically associated with user interactions and may grow rapidly. NoSQL databases like MongoDB or Cassandra can handle large volumes of data and provide horizontal scalability, making them suitable for storing user-generated content.
• CAP Theorem Focus: Availability Focused - In user-generated content scenarios, ensuring availability for read and write operations is crucial, especially during peak usage times.

• Photos:
• Database Type: Object Storage or File System (e.g., Amazon S3, Google Cloud Storage)
• Reasoning: Storing photos as binary data directly in databases can lead to performance issues and database bloat. Object storage solutions offer scalable and cost-effective storage options specifically designed for storing large files like images.
• CAP Theorem Focus: Availability Focused - Object storage solutions prioritize availability and partition tolerance to ensure that files are accessible and retrievable at all times.

In summary, the choice of databases for Yelp would depend on the nature of the data, scalability requirements, access patterns, and the trade-offs between consistency, availability, and partition tolerance dictated by the CAP theorem. While SQL databases offer strong consistency and relational data modeling capabilities, NoSQL databases provide flexibility, scalability, and performance advantages for certain types of data. Additionally, using specialized storage solutions like object storage for files such as photos can optimize performance and scalability.

Data Partitioning

The most suitable partitioning strategy for this system is likely geographic partitioning. Here's why:

1. Considering the user search functionality based on location, storing establishment data partitioned by geographic region allows for faster retrieval of relevant establishments during searches.
2. Geographic partitioning helps distribute the load across servers efficiently, especially as the user base and establishment data grow.

Sharding

The best sharding strategy would be Category-Based Sharding. This strategy involves partitioning data based on the category of establishments (e.g., restaurants, theaters, shopping centers), ensuring that establishments of similar types are stored together within each shard. 

This approach optimizes query performance by grouping related data together, allowing for more efficient retrieval and analysis based on user preferences and search patterns. Additionally, it minimizes cross-shard operations and enhances scalability by evenly distributing the workload across shards based on the popularity and diversity of establishment categories.

Scaling Strategy: Horizontal Scaling

Horizontal scaling is the preferred approach. Here's why:

1. The system anticipates a significant increase in establishments and potentially reviews over time. Horizontal scaling allows adding more database servers to distribute the load and handle growing data volumes efficiently.
2. Read operations are likely more frequent than writes (searches vs. submitting reviews). Horizontal scaling allows for independent scaling of read replicas to handle high read traffic without impacting write performance on the primary database.

Read/Write Separation

Implementing read/write separation is highly beneficial for this system. Here's why:

1. Read operations (searches, browsing establishments) are anticipated to be much more frequent than write operations (adding reviews, bookmarks).
2. Read/write separation allows for independent scaling of read replicas to handle high read traffic without affecting the performance of write operations on the primary database. This improves overall system responsiveness and availability.

High-level design

1. Frontend Client/Application:
2. The user-facing interface where users interact with the platform to search for establishments, leave reviews, and perform other actions.
3. Web Server:
4. Serves web pages to users and handles user requests from the frontend client.
5. Implements the API endpoints required for various functionalities.
6. API Gateway:
7. Acts as an entry point for client requests, routing them to the appropriate microservices.
8. Handles authentication, rate limiting, and other cross-cutting concerns.
9. Authentication Service:
10. Manages user authentication and authorization.
11. Issues access tokens for authenticated users.
12. User Service:
13. Handles user-related functionalities such as user registration, login, profile management, and preferences.
14. Establishment Service:
15. Manages establishment data, including CRUD operations for establishments, fetching establishment details, and handling search queries.
16. Review Service:
17. Handles functionalities related to reviews and ratings, such as submitting reviews, fetching reviews for establishments, and calculating average ratings.
18. Bookmark Service:
19. Manages bookmarking functionality, allowing users to save their favorite establishments for future reference.
20. Reporting Service:
21. Handles reporting functionalities, allowing users to flag inappropriate content or reviews on the platform.
22. Photo Service:
23. Manages photos associated with establishments, including uploading, retrieving, and serving images.
24. Search Service:
25. Implements search functionality, allowing users to search for establishments based on various criteria such as location, category, or keyword.
26. Recommendation Service:
27. Provides personalized recommendations to users based on their preferences, past reviews, and browsing history.
28. Admin Panel:
29. A separate interface for administrators to manage user accounts, reviews, reported content, and overall platform operations.
30. Database(s):
31. Relational or NoSQL databases to store user data, establishment information, reviews, bookmarks, reports, and photos.
32. Content Delivery Network (CDN):
33. Distributes static assets such as images, CSS, and JavaScript files to improve performance and reduce server load.
34. Caching Layer:
35. Implements caching mechanisms to store frequently accessed data, improving response times and reducing database load.
36. Load Balancer:
37. Distributes incoming traffic across multiple instances of web servers and microservices to ensure scalability and fault tolerance.
38. Monitoring & Logging:
39. Tools and services to monitor system health, track user interactions, and log errors and performance metrics for troubleshooting and analysis.

Request flows

Here is a sequence diagram for when user makes a search for an enstablishment, adds photos, leaves a review.

Detailed component design

Leveraging Geohashing and Quadtrees for Efficient Search

In the Yelp Location Service, efficient search based on location is crucial. Here's how geohashing and quadtrees can be utilized to solve search problems:

1. Geohashing:

• Concept: Geohashing converts geographic coordinates (latitude, longitude) into a short string of characters. This string represents a specific geographic region at a certain level of precision.
• Benefits for Search:
• Fast Encoding/Decoding: Geohashing allows for quick conversion between location data and a compact string representation.
• Efficient Spatial Search: By storing geohashes alongside establishment data in the database, searches based on a user's location or a specific area can be performed efficiently.
• Implementation:
• Establishments can be pre-processed to generate geohashes based on their address or coordinates.
• During a location-based search, the user's location is converted into a geohash.
• The database can be queried to find establishments with geohashes that fall within a specific range (depending on the desired search radius).

2. Quadtrees:

• Concept: Quadtrees are hierarchical tree structures used to partition a two-dimensional space (like a map) into progressively smaller square quadrants.
• Benefits for Search:
• Spatial Indexing: Quadtrees offer a spatial indexing technique for efficient retrieval of nearby locations.
• Dynamic Search Radius: Unlike geohashing with a fixed range, quadtrees allow for dynamic search areas. By traversing the quadtree structure, establishments within a user-specified radius can be identified.
• Implementation:
• The geographic area covered by the service can be represented as the root quadtree node.
• Establishments can be inserted into the quadtree based on their location, traversing the tree to find the appropriate leaf node (quadrant).
• During a search, the user's location determines the starting point in the quadtree.
• The quadtree is recursively traversed, identifying establishments within the relevant quadrants based on the search radius.

Choosing Between Geohashing and Quadtrees:

• If precise location filtering is less critical and a fast search based on a general area is desired, geohashing might be a good choice due to its simplicity and efficiency.
• If the search functionality requires flexibility in defining search areas (e.g., rectangular areas instead of just circular radius), quadtrees offer a more suitable approach for spatial indexing.

In conclusion, both geohashing and quadtrees are valuable tools for optimizing location-based search in the Yelp Location Service. The choice between them depends on the specific search requirements and desired level of spatial precision.

Caching Strategy for Yelp Location Service

Caching plays a vital role in improving performance and scalability for the Yelp Location Service. Here's how we can implement a caching strategy to optimize the system:

Cache Layers:

• Client-side Caching: The user's browser can cache static assets like images, CSS, and JavaScript files. This reduces server load and improves perceived performance for returning users.
• API Gateway Cache: The API Gateway can implement a cache to store frequently accessed responses to search queries, establishment details, or other frequently requested data. This reduces database load and improves response times for repeated requests.
• Database Cache: The database itself might offer caching functionalities to store frequently accessed data in memory, reducing disk I/O operations and speeding up retrievals.

Trade offs/Tech choices

Throughout the design process, several trade-offs were made and specific technical choices were considered to optimize the Yelp Location Service. Here's a breakdown of some key decisions:

1. Database Sharding:

• Choice: Sharding by establishment type.
• Reasoning: This approach distributes reviews and potentially photos across multiple servers based on the establishment they belong to. It offers good performance for read operations on specific establishments and scales well with a growing number of establishments and reviews.

2. Scaling Strategy:

• Choice: Horizontal scaling.
• Reasoning: The system anticipates significant growth in establishments and potentially reviews. Horizontal scaling allows adding more database servers to distribute the load and handle growing data volumes efficiently. Additionally, read operations are anticipated to be more frequent, making horizontal scaling with read replicas ideal for handling high read traffic without impacting write performance.

3. Search Optimization:

• Choices: Both geohashing and quadtrees were discussed.
• Trade-off: Geohashing offers simplicity and efficiency for fast search based on a general area. Quadtrees provide more flexibility for defining search areas but might be more complex to implement.

Decision: The specific choice depends on the desired level of precision and flexibility in search areas. If precise location filtering is less critical, geohashing might be sufficient. If users need to define rectangular search areas, quadtrees would be a better fit.

Future improvements

Here are some potential future improvements for the Yelp Location Service:

1. Advanced Search and Filtering:

• Implement filters based on additional criteria like cuisine type (for restaurants), price range, amenities (e.g., Wi-Fi, outdoor seating), and accessibility features.
• Allow users to search by specific keywords within reviews to find establishments mentioned for a particular aspect (e.g., "great burgers").

2. Personalized Recommendations:

• Utilize machine learning to analyze user reviews, browsing history, and past behavior to recommend establishments that better match their preferences.
• Integrate with social networks to consider recommendations from friends or trusted reviewers.

3. AI-powered Chatbot Support:

• Introduce a chatbot to answer frequently asked questions, guide users through search functionalities, and potentially collect user feedback.
• Leverage natural language processing to understand user queries and provide relevant information or complete basic tasks.

4. Gamification and Incentives:

• Implement a gamification system with points or badges awarded for leaving reviews, adding photos, or being a helpful user.
• Offer occasional rewards or discounts at establishments based on user activity or contribution to the platform.