Design a Ride Matching Service

Question

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

Codemia · Accepted Answer

### Functional Requirements
1. **User Registration and Authentication**: Users must be able to register and log in securely.
2. **Ride Request Creation**: Users should be able to create a ride request specifying pickup and drop-off locations, time, and capacity.
3. **Ride Matching**: The system must match riders with drivers based on proximity, availability, and preferences.
4. **Real-time Updates**: Users should receive real-time updates on ride status (matched, in-progress, completed).
5. **Rating and Feedback**: Users can rate their ride experience and leave feedback for drivers.

### Non-Functional Requirements
1. **Scalability**: The system should handle millions of requests per day, scaling horizontally as needed.
2. **Availability**: Aim for 99.9% uptime to ensure users can access services anytime.
3. **Latency**: Ride matching should occur in under 2 seconds to provide a responsive user experience.
4. **Data Consistency**: Ride requests must be processed reliably, ensuring no double bookings occur.

Assuming Dropbox has around 500 million users, with an active user base of 10% (50 million users). Assuming 10% of active users use the ride matching service daily, that's 5 million requests. If each user makes an average of 2 requests per session, we can estimate:

- **Daily Requests**: 5 million users x 2 requests = 10 million requests.
- **Peak Load**: Assuming peak usage is 2x average, we need to support 20 million requests per day.
- **Requests per second (RPS)**: Dividing by 86,400 seconds in a day gives approximately 231 RPS.

To ensure system resilience, we might target 500 RPS handling capabilities to manage spikes.

The architecture consists of several key components:
1. **API Gateway**: Routes incoming requests and handles user authentication (using OAuth2).
2. **Microservices**:
   - **User Service**: Manages user profiles and authentication.
   - **Ride Service**: Handles ride request creation and matching logic.
   - **Notification Service**: Sends real-time updates to users (using WebSocket or Server-Sent Events).
3. **Database**: A distributed NoSQL database (like MongoDB) for storing user profiles and ride requests.
4. **Message Queue**: Use Apache Kafka for handling asynchronous processing of ride requests and updates.
5. **Cache Layer**: Redis for caching ride requests and user session data to speed up retrieval.

### Component Diagram
- Users -> API Gateway -> Microservices (User, Ride, Notification) -> Database (MongoDB)
- Ride Service -> Message Queue (Kafka) -> Notification Service

### User Schema
```json
{
  "user_id": "string",
  "name": "string",
  "email": "string",
  "password_hash": "string",
  "phone_number": "string"
}
```

### Ride Request Schema
```json
{
  "ride_id": "string",
  "user_id": "string",
  "pickup_location": {"type": "Point", "coordinates": [longitude, latitude]},
  "dropoff_location": {"type": "Point", "coordinates": [longitude, latitude]},
  "capacity": "integer",
  "status": "string",
  "created_at": "timestamp"
}
```

### Access Patterns
- Frequent read operations for user authentication and ride lookup.
- Moderate writes for ride requests and updates.

1. **Consistency vs Availability**: Choosing a distributed NoSQL database offers high availability but might lead to eventual consistency. This is acceptable in ride matching as slight delays in data consistency (e.g., ride availability) can be managed with user notifications.
2. **Real-Time vs Batch Processing**: Real-time updates for ride status enhance user experience but increase system complexity. A balance can be struck by using a mix of real-time for immediate notifications and batch processing for analytics.
3. **Caching Strategy**: While caching improves performance, it introduces complexity in cache invalidation. For frequently accessed ride requests, caching is critical, but we must ensure that stale data is managed effectively.
4. **Horizontal Scaling**: While it allows handling higher loads, it adds operational complexity in managing multiple service instances and data consistency across them.

Design a Ride Matching Service

Dropbox

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

Submit Your Answer

Dropbox Machine Learning 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