Design a Ride Matching Service

Question

Design a geo-distributed 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**: Allow users to sign up, log in, and manage profiles securely.
2. **Ride Request Creation**: Users can create ride requests specifying origin, destination, and time.
3. **Ride Matching**: Match riders with drivers based on proximity, availability, and preferences.
4. **Real-time Updates**: Provide real-time updates to users on ride status and driver location.
5. **Payment Processing**: Integrate a payment gateway for seamless ride payments.

### Non-Functional Requirements
1. **Scalability**: Support millions of ride requests and user interactions concurrently.
2. **Availability**: 99.99% uptime to ensure reliability for users needing rides.
3. **Latency**: Ensure ride matching occurs within 2 seconds.
4. **Data Security**: Protect user data and transaction information using encryption and secure protocols.

### Back-of-Envelope Calculations
1. **User Base**: Assume Brex targets 10 million active users.
2. **Requests per User**: On average, each user makes 2 ride requests per day, resulting in 20 million requests daily.
3. **Requests per Second (QPS)**: 
   - Total daily requests: 20 million
   - Total seconds in a day: 86400
   - QPS = 20,000,000 / 86,400 ≈ 231.5 ~ 232 QPS.
4. **Data Storage Needs**: If each user record is 1 KB and each ride record is 2 KB, 
   - Total user data: 10 million * 1 KB = 10 GB
   - Total ride data per day: 20 million * 2 KB = 40 GB
   - Monthly growth: 1.2 TB for ride data, 300 GB for user data.

### Component Diagram
- **User Service**: Manages user authentication and profiles (using Node.js + Express).
- **Ride Service**: Handles ride requests and matching logic (using Python + Flask).
- **Matching Engine**: A microservice for real-time ride matching using Apache Kafka for message queuing.
- **Database**: Use PostgreSQL for relational data storage, with Redis for caching frequently accessed data (like user sessions).
- **Load Balancer**: NGINX or AWS ELB for distributing incoming requests.
- **Monitoring**: Prometheus and Grafana for real-time system monitoring and alerting.
- **API Gateway**: Use Kong or AWS API Gateway for rate limiting and routing.

### Schema Design
1. **User Table**:
   - `user_id` (PK, UUID)
   - `name` (VARCHAR)
   - `email` (VARCHAR, unique)
   - `hashed_password` (VARCHAR)
   - `created_at` (TIMESTAMP)

2. **Ride Table**:
   - `ride_id` (PK, UUID)
   - `user_id` (FK, UUID)
   - `origin` (POINT)
   - `destination` (POINT)
   - `status` (ENUM: PENDING, MATCHED, COMPLETED)
   - `created_at` (TIMESTAMP)

3. **Driver Table**:
   - `driver_id` (PK, UUID)
   - `location` (POINT)
   - `availability` (BOOLEAN)
   - `rating` (FLOAT)
   - `vehicle_info` (JSON)

### Access Patterns
- Frequent reads for user profiles and ride statuses.
- Write-heavy operations for ride requests and updates.

### Architectural Decisions
1. **Consistency vs Availability**: Opt for eventual consistency for ride matching to prioritize availability and responsiveness. This allows users to receive matches quickly, although it may lead to temporary discrepancies in driver availability.
2. **Database Choice**: Choosing PostgreSQL ensures strong consistency and complex queries, but may have performance trade-offs under heavy write loads. Caching with Redis mitigates this by reducing read load on the primary database.
3. **Message Queue vs Direct Calls**: Using Kafka for ride matching introduces some latency due to asynchronous processing but enhances scalability and decouples services, allowing for smoother traffic handling.
4. **Load Balancing**: While an active-active load balancing strategy increases availability, it adds complexity in ensuring session persistence; sticky sessions may be needed for user requests, impacting the load distribution slightly.

Design a Ride Matching Service

Brex

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

Brex 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