Design a Search for Airbnb

Question

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

Codemia · Accepted Answer

### Functional Requirements
1. **Search Listings**: Users should be able to search for listings based on location, check-in/check-out dates, price range, and number of guests.
2. **Filters and Sorting**: Users should be able to apply filters (e.g., type of property, amenities) and sort results (e.g., by price, rating).
3. **Geo-Search Capabilities**: The search should support geo-location features, allowing users to see listings on a map.
4. **Real-time Availability**: The system must provide real-time availability of listings based on the search criteria.
5. **User Personalization**: The system should offer personalized search results based on user preferences and past searches.

### Non-Functional Requirements
1. **Scalability**: The system should handle millions of requests per second (QPS) during peak times.
2. **Low Latency**: Search results should be returned in under 200 milliseconds.
3. **High Availability**: The system should be available 99.99% of the time.
4. **Consistency**: The availability of up-to-date listing information is crucial, even if it means relaxing immediate consistency in some areas.

### Back-of-Envelope Calculations
- **User Base**: Assume 100 million users with 10% active users daily, leading to 10 million daily active users.
- **Search Requests**: If each user performs an average of 5 searches daily, total search requests = 10 million users * 5 searches = 50 million searches per day, which translates to about 580 requests per second (QPS).
- **Peak Request Handling**: During peak hours, assume a 5x increase in search requests, resulting in a need to handle approximately 2900 requests per second.
- **Data Storage**: If each listing takes about 2KB and there are 7 million listings, total storage needed will be around 14GB.

### Component Diagram
- **Frontend**: Mobile and web applications for users to initiate search requests.
- **API Gateway**: Acts as a single entry point for all requests, handling rate limiting and routing.
- **Search Service**: A microservice responsible for processing search queries and returning results. Technologies: Node.js or Go for performance, with gRPC for internal communication.
- **Database**: Use a distributed NoSQL database like Cassandra for fast reads and high write throughput, with geo-partitioning based on location. 
- **Caching Layer**: Redis for in-memory caching of frequent queries and results to reduce load on the database.
- **Load Balancer**: Distributes incoming requests across multiple instances of the search service.
- **Monitoring**: Use Prometheus and Grafana for monitoring performance and alerting on anomalies.

### Schema Design
- **Listings Table**:
  - `listing_id` (UUID, Primary Key)
  - `title` (String)
  - `description` (Text)
  - `location` (Geospatial data)
  - `price` (Decimal)
  - `availability` (Boolean)
  - `amenities` (Array of Strings)
  - `rating` (Float)
  - `created_at` (Timestamp)

- **Search Index**: Utilize Elasticsearch for indexing listings to allow for fast full-text search and geo-based queries.
- **User Preferences Table**: Store user-specific search preferences and history to support personalization.

### Architectural Decisions
1. **Consistency vs Availability**: Choosing a NoSQL database like Cassandra allows for high availability and partition tolerance, but may require eventual consistency, which is acceptable for search scenarios where stale data can be tolerated for a short period.
2. **Caching Strategy**: Utilizing Redis for caching can significantly speed up search response times but introduces complexity in cache invalidation strategies. Deciding on a TTL (Time to Live) for cached results helps balance freshness and performance.
3. **Data Partitioning**: Geo-partitioning the database ensures that searches for a specific location can be handled by the nearest data node, improving response times but complicating cross-region queries. This trade-off is acceptable given the focus on local searches.
4. **Rate Limiting**: Implementing rate limiting at the API Gateway can prevent abuse and manage traffic, but might affect user experience during high traffic events. Adaptive rate limiting can be considered to balance load while maintaining user satisfaction.

Design a Search for Airbnb

Airbnb

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

Functional Requirements

Capacity Estimation

Back-of-Envelope Calculations

Submit Your Answer

Airbnb 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