Design Facebook Search with Typeahead

Question

Design a search system with typeahead autocomplete for Facebook. Cover indexing strategies, ranking algorithms, query processing, and how to suggest top 10 results based on character input, frequency, and social signals.

Codemia · Accepted Answer

### Functional Requirements:
1. **Typeahead Autocomplete**: As users type in the search bar, suggestions should appear in real-time, displaying up to 10 results.
2. **Searchable Entities**: Support searching for users, pages, groups, and posts.
3. **Ranking Mechanism**: Results should be ranked based on relevance, user frequency of interaction, and social signals (e.g., likes, shares).
4. **Filters**: Allow users to filter results by type (e.g., users, posts).

### Non-Functional Requirements:
1. **Performance**: The system must return results in under 100ms under normal load.
2. **Scalability**: Must handle up to 1 billion users generating a high volume of daily searches.
3. **Availability**: The system should have 99.9% uptime.
4. **Consistency**: Ensure users see the most up-to-date results based on their interactions.

1. **User Base**: Facebook has approximately 2.89 billion monthly active users.
2. **Search Queries**: Assuming each user performs an average of 5 searches per day, that leads to:
   - Total searches per day: 2.89 billion * 5 = 14.45 billion searches/day.
3. **Queries per Second (QPS)**: 
   - 14.45 billion searches/day / 86400 seconds/day = ~167,000 QPS.
4. **Typeahead Requests**: If 10% of these searches utilize typeahead, we expect:
   - Typeahead requests: 167,000 QPS * 0.1 = 16,700 QPS.
5. **Data Index Size**: Assuming an average of 100 bytes per entity and 1 billion searchable entities:
   - Total index size = 1 billion * 100 bytes = ~100 GB.

### Component Diagram:
- **User Interface**: Web and mobile clients that send search queries.
- **Load Balancer**: Distributes incoming requests across multiple servers to manage load.
- **Search Service**: Handles incoming search queries and typeahead requests using:
  - **Elasticsearch**: For indexing and searching data quickly.
  - **Redis**: For caching popular search queries and results to improve performance.
- **Ranking Service**: Implements ranking algorithms based on frequency and social signals, using machine learning models.
- **Data Store**: 
  - **Cassandra**: For storing user data and search logs, providing high availability and partition tolerance.
  - **Hadoop**: For batch processing and analytics of search data to improve ranking algorithms.

### Schema Design:
1. **User Table**:
   - `user_id` (UUID, Primary Key)
   - `name` (String)
   - `profile_pic` (String)
   - `social_signals` (JSON, contains likes, shares, etc.)

2. **Post Table**:
   - `post_id` (UUID, Primary Key)
   - `user_id` (UUID, Foreign Key)
   - `content` (Text)
   - `timestamp` (DateTime)
   - `likes` (Integer)

3. **Search Log Table**:
   - `search_id` (UUID, Primary Key)
   - `user_id` (UUID, Foreign Key)
   - `query` (String)
   - `timestamp` (DateTime)
   - `result_count` (Integer)

### Access Patterns:
- Frequent read access for searching users and posts.
- Write-heavy access for logging search queries and user interactions.

1. **Consistency vs. Availability**: By using Elasticsearch for real-time search, we sacrifice some consistency in favor of availability and performance. We need to ensure that updates to user data are eventually consistent, which is acceptable given the nature of search.
2. **Complexity of Ranking Algorithms**: Implementing machine learning models for ranking increases complexity but can significantly improve the relevance of search results. This might require additional resources for model training and updates.
3. **Caching Strategies**: Using Redis for caching can enhance performance but introduces complexity in cache invalidation. We need to ensure that the cache remains consistent with the underlying data to avoid serving stale results.
4. **Scalability**: Leveraging Cassandra provides high scalability but requires careful data modeling to avoid hotspots and ensure efficient querying.

Design Facebook Search with Typeahead

Meta

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Requirements

Functional Requirements:

Capacity Estimation

Submit Your Answer

Meta 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