Design a event-driven Search System

Question

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

Codemia · Accepted Answer

### Functional Requirements
1. **Search Functionality**: Users should be able to search for rides based on various criteria (location, type of service, fare estimates).
2. **Real-time Updates**: The system must provide real-time updates on ride availability, estimated arrival times, and pricing.
3. **Event Handling**: The system should process events such as ride requests, cancellations, and driver status updates in real-time.
4. **User Personalization**: The search results should consider user preferences and past behavior to enhance the search experience.

### Non-Functional Requirements
1. **Scalability**: The system should handle millions of requests per second, especially during peak hours.
2. **Availability**: 99.99% uptime with no single point of failure; must be resilient to regional outages.
3. **Latency**: Search results should be returned within 200 milliseconds for a seamless user experience.
4. **Consistency**: While eventual consistency is acceptable for some data, critical data (like ride availability) must be strongly consistent.

### Estimation of Scale
1. **User Estimates**: Assume Uber has 100 million active users.
2. **Search Requests**: If 10% of users search for rides at peak time, that results in 10 million searches.
3. **Event Throughput**: Each search may trigger several events (e.g., location updates, price changes). If we estimate 3 events per search, that results in 30 million events per second.
4. **Data Storage**: Each ride request might generate 100 KB of data (user info, ride info, event data). For 30 million events, that would require approximately 3 TB of data per second at peak times, necessitating a robust storage solution.

### Component Diagram
- **Load Balancer**: Distributes incoming search requests to multiple search service instances.
- **Search Service**: Stateless microservices deployed in multiple regions to handle search logic and event processing. Technologies: Node.js for server-side logic, Redis for caching recent search results.
- **Event Stream Processor**: Kafka for handling event streams, processing events in real-time, and updating search indexes.
- **Data Store**: A combination of Cassandra for ride availability (high write throughput, eventual consistency) and PostgreSQL for user preferences (strong consistency).
- **Cache Layer**: Memcached for caching frequent search queries and results, reducing load on the database.

### Schema Design
1. **Users Table**: Stores user profiles.
   - `user_id (PK)`, `name`, `email`, `preferences`
2. **Rides Table**: Stores ride details.
   - `ride_id (PK)`, `user_id (FK)`, `pickup_location`, `dropoff_location`, `status`, `fare`
3. **Events Table**: Logs events for ride requests.
   - `event_id (PK)`, `ride_id (FK)`, `event_type`, `timestamp`, `details`
4. **Search Index**: An inverted index for quick lookup of rides based on location and availability.
   - `location (PK)`, `ride_ids (array)`

### Access Patterns
- Frequent reads for search queries (caching).
- High write loads for ride requests and event logs.

### Architectural Decisions
1. **Consistency vs. Availability**: Chose eventual consistency for ride availability to handle the high throughput of events, but implemented a strong consistency model for critical operations (e.g., confirming a ride).
2. **Eventual Consistency**: Utilized event sourcing and CQRS (Command Query Responsibility Segregation) patterns to maintain a clean separation between read and write operations, allowing for better performance.
3. **Horizontal Scaling**: Designed the system to scale horizontally, enabling the addition of more instances as traffic increases, but at the cost of increased complexity in managing state.
4. **Deployment Strategy**: Adopted a canary deployment strategy to minimize risk during updates, allowing for gradual rollout and monitoring of new features.

Design a event-driven Search System

Uber

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

Estimation of Scale

Submit Your Answer

Uber 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