Architect a distributed Search Engine

Question

Design a distributed search system that handles millions of requests. Discuss trade-offs in consistency, availability, and performance.

Codemia · Accepted Answer

- **Functional Requirements**:
  - Provide search functionality for hotels, flights, and rental cars.
  - Support filtering by price, location, and amenities.
  - Allow sorting by user ratings, price, and distance.
  - Enable advanced search features like multi-city trips and flexible date ranges.
  - Return results in real-time with pagination support.

- **Non-Functional Requirements**:
  - The system must handle at least 10 million search requests per day.
  - Response time should be under 200ms for 95% of requests.
  - Ensure high availability (99.9%) with minimal downtime.
  - Consistency should be eventual to support high write loads without impacting read performance.
  - Must be scalable to handle peak loads, especially during travel seasons.

Assuming 10 million searches per day, we can break this down:
- Average requests per second (RPS): 
  
  $$ \text{RPS} = \frac{10,000,000 \text{ searches}}{86400 \text{ seconds}} \approx 115.74 \text{ RPS} $$

- Considering spikes, we can assume peak traffic might reach 3x the average, leading to around 350 RPS during peak times.
- Each search request might involve fetching data from multiple microservices (hotels, flights, etc.), so we should plan for a request handling capacity of at least 500 RPS to ensure smooth operation under load.

The architecture will consist of the following components:
- **API Gateway**: Using AWS API Gateway to handle incoming requests and route them to appropriate services.
- **Search Microservices**: Separate services for hotels, flights, and rental cars built using Node.js for lightweight processing.
- **Load Balancer**: AWS Elastic Load Balancer (ELB) to distribute traffic among microservices.
- **Caching Layer**: Redis for caching frequently accessed search results to reduce load on the backend and improve response times.
- **Database**: NoSQL database like DynamoDB for high availability and scalability, storing search indexes and metadata.
- **Message Queue**: AWS SQS for handling asynchronous tasks and ensuring decoupling of services.
- **Monitoring & Logging**: AWS CloudWatch for monitoring system health and logging, ensuring we can quickly identify and address issues.

A simple schema could include:
- **Search Index Table** (DynamoDB):
  - **PK**: search_id (unique ID for each search)
  - **SK**: category (hotel, flight, rental)
  - **user_id**: ID of the user performing the search
  - **location**: Search location
  - **date_range**: Start and end dates for the search
  - **results**: List of results returned, potentially in a serialized format.
  
- **User Preferences Table**:
  - **PK**: user_id
  - **preferences**: JSON object for user-specific search filters and settings.

This model supports quick lookups for user searches and allows for rapid retrieval of previous search results.

Several trade-offs need to be considered:
- **Consistency vs. Availability**: Opting for eventual consistency allows us to handle high write loads during peak times but means users might not see the most current data immediately. This is acceptable for search results, as users typically prioritize speed over the absolute latest info.
- **Caching**: Implementing a caching layer (Redis) improves read performance and reduces load on the database, but introduces complexity in cache invalidation strategies.
- **Service Granularity**: Microservices for hotels, flights, and rental cars improve scalability and maintainability but may complicate inter-service communication and increase latencies. We need to monitor and optimize API calls between services to mitigate this.
- **Monitoring and Alerting**: Setting up comprehensive monitoring adds overhead but is crucial for maintaining high availability and quickly diagnosing issues.

Architect a distributed Search Engine

Expedia

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Practice a Similar Problem on Codemia

Sample Answer

Requirements

Capacity Estimation

Submit Your Answer

Expedia Software Engineer Interview Guide

Related Questions

Design a high-throughput Inventory Management System

Design a low-latency Rate Limiting System

Design a fault-tolerant Payment System

Design a fault-tolerant Messaging System

Design Walmart Product Search