Ride Sharing Service (Uber, Lyft)

Overview

Introduction
Requirements
Data Model
API Design
Driver Location Update Flow
Ride Request Flow
Complete Architecture
Additional Discussion Points

Introduction

Designing Uber is one of the more challenging system design interview questions because it's easy to become overwhelmed by the multitude of components and over-engineer the solution. In this system design, we will focus on the core flows that most interviewers expect to see covered, as well as provide deep dives into the most critical aspects of the system.

Requirements

Functional Requirements
- Ride Request: Riders should be able to input their pickup and destination location, view nearby drivers, and receive real-time fare estimates.
- Ride Matching: The system should be able to efficiently and effectively match a rider with an available driver that meets their requirements.
- Driver Tracking: Once matched, the rider should be able to track the driver's location in real-time, along with the estimated time of arrival (ETA).
- Push Notifications: The system should send notifications for ride updates, driver arrival, trip completion, promotions, etc.
Non Functional Requirements
- Scalability: The platform must support more than 100 million daily active users (DAU), scaling efficiently with regional spikes in demand.
- High Availability: The system should be reliable and available 24/7, ensuring minimal downtime, as the switching cost for users is extremely low.
- Low Latency: The application must perform well even in areas with poor cellular networks, providing fast and responsive user interactions to ensure a smooth experience globally.
Non Covered
- Ride-Pooling: The implementation of ride-pooling services (where multiple passengers share a ride) will not be covered here.

Data Model

This is a basic outline of some of the core tables that could be included in a ride sharing service data model.

Riders: Stores information about individuals requesting rides.
- payment_method: The preferred method of payment (e.g., card, cash, wallet).
Drivers: Stores details about drivers in the system.
- status: Current status of the driver (e.g., active, inactive).
Vehicles: Tracks vehicles that are associated with drivers.
- driver_id: Foreign key linking the vehicle to a specific driver.
- make, model, year, license_plate: Vehicle identification details.
- status: Indicates if the vehicle is available, busy, or under maintenance.
Fares: Stores information about fare options presented to a rider.
- base_fare: The initial cost of the ride before any additional charges are applied.
- surge_multiplier: A dynamic multiplier applied during periods of high demand or low driver availability. It increases the fare to encourage more drivers to become available.
Rides: Stores information about rides initiated by riders.
- start_time, end_time: Timestamps marking the start and end of the ride.
- status: Current status of the ride (e.g., requested, accepted, completed, cancelled).
Payments: Handles payment details for completed rides.
- status: Indicates the current status of the payment (e.g., pending, completed, failed).

API Design

For a ride sharing services we will use a classic RESTful API to interact with the data. RESTful APIs are simple, widely used, stateless, and support caching which make it a good candidate for our system.

Our REST API will comprise of three main endpoints:

POST: /api/fares/estimate
- Description: Provides fare estimates based on the rider's pickup and destination locations.
- Params:
  - pickup_location: { latitude: float, longitude: float }
  - destination_location: { latitude: float, longitude: float }
POST: /api/rides/request
- Description: Allows a rider to request a ride by selecting a fare.
- Params:
  - fare_id: string
PUT: /api/rides/{ride_id}/accept
- Description: Allows a driver to accept a ride.

Driver Location Update Flow

Driver App
Long Polling:
How it works: The client repeatedly requests the server for updates, but the server holds the connection until new data is available.
Pros: Simple to implement and works well over traditional HTTP.
Cons: High server load due to repeated requests, especially when there are no updates. Higher latency than WebSockets.
Best for: Simple scenarios where real-time updates aren't crucial or if WebSocket support is limited.
Server-Sent Events (SSE):
How it works: The server sends updates to the client over a single, persistent HTTP connection.
Pros: Simple to implement for one-way communication (server → client). Uses fewer resources than WebSockets for simple data streams.
Cons: One-way communication only; the client cannot send data to the server over the same connection.
Best for: Streaming updates like ride status changes or notifications, but not suitable for two-way communication like WebSockets.
WebSockets:
How it works: A persistent, full-duplex connection between client and server. Both can send/receive messages in real time.
Pros: Real-time, bidirectional communication. Ideal for tracking drivers' locations, as it allows instantaneous updates. Low latency once the connection is established.
Cons: Requires more resources, and scaling can be more complex (e.g., handling thousands of concurrent connections).
Best for: Continuous location updates, real-time notifications, ride-tracking features.
QUIC (HTTP/3):
How it works: QUIC is a transport protocol that provides faster connection establishment and data transfer over HTTP/3. It’s reliable, secure, and built on UDP.
Pros: Lower latency than WebSockets due to faster connection setup. Multiplexing without head-of-line blocking, making it more efficient.
Cons: Newer technology, less supported than WebSockets. Complex to implement and debug.
Best for: Applications requiring faster connections and resilience against packet loss, like ride tracking.
While Uber uses QUIC (Quick UDP Internet Connections) in their production environment due to its superior performance under varying network conditions—a topic they delve into in their engineering blogs—for this system design, we will use WebSockets.
WebSockets are a good choice for an interview setting because they are widely understood, easier to implement, and effectively demonstrate the key concepts of real-time, bidirectional communication necessary for a ride-sharing application's driver location updates.
- WebSocket Connection: Establishes a secure, persistent connection to the Driver WebSocket Service via the API Gateway.
- Location Updates: Sends high-frequency (≈ 10s) location updates with relevant metadata.
API Gateway
- Connection Management: Manages WebSocket connections and routes them to the appropriate services.
- Additional Functionality: Performs authentication, authorization, and implements rate limiting. Also handles load balancing by distributing incoming connections and requests to maintain optimal performance.
Driver WebSocket Server
- Updates Handling: Receives location updates from the driver app sends onto the Location Queue.
- Scalability: Designed to scale horizontally to handle a large number of concurrent connections.
Location Service
Geohashing:
Description: Encodes latitude and longitude into a short alphanumeric string.
Grid System: Divides the world into a grid of cells, enabling proximity searches.
Pros: Simple implementation, good for rectangular area queries.
Cons: Varying cell sizes at different latitudes due to Earth's curvature.
Quadtrees:
Description: A hierarchical tree structure dividing space into four quadrants recursively.
Pros: Efficient for dynamic data, adaptable to varying data densities.
Cons: More complex implementation; can be less efficient for large datasets.
H3 Indexing (Uber's Hexagonal Hierarchical Spatial Index):
Description: Uses hexagonal tiling for better spatial uniformity.
Pros: Reduces distortion, efficient for k-nearest neighbor queries.
Cons: More complex; may require additional effort to integrate.
Chosen Approach: Geohashing for simplicity and sufficient performance for the application needs.
- Data Processing: Pulls messages off the Location Queue and converts GPS coordinates to geohashes and updates the Location Cache.
- In-Memory Datastore: Stores the data in Redis with geospatial indexing for fast data access. Expiration policies are also implemented to remove inactive drivers from the location cache.

Ride Request Flow

User Action
- The rider (user) opens the ride-sharing app on their mobile device. The app initiates connection to Rider WebSocket Service through the API Gateway.
API Gateway
- Persistent Connection: The rider's app establishes a persistent WebSocket connection to the Rider WebSocket Service via the API Gateway. Enables real-time communication for updates like ride status changes and driver location tracking. Performs authentication, authorization, and implements rate limiting. Also handles load balancing by distributing incoming connections and requests to maintain optimal performance.
- Subscription to Message Broker Topics: When the rider connects via WebSocket, the Rider WebSocket Service subscribes to a specific topic in a message broker (e.g., Apache Kafka) associated with that rider. Uses a hash of the Rider ID to create a unique and secure topic name. Facilitates the delivery of personalized real-time notifications to the rider, such as ride acceptance by a driver.
Ride Estimate
- Rider POST Request: The rider inputs their pickup and destination locations in the app and the app sends a POST request to the /api/fares/estimate endpoint to the Ride Service via the API Gateway.
- Third Party Mapping Service: Utilizes mapping services (e.g., Google Maps, Mapbox) to generate the best route between the origin and destination.
- Fare Calculation: Fares are calculated for different ride types (e.g., economy, XL) based on several factors including: distance, time, traffic conditions, demand factors (e.g. dynamic surge pricing) and stored in the database. An SQL database like PostgreSQL could be a good option as it supports Atomicity, Consistency, Isolation, Durability (ACID) properties ensure that transactions are processed reliably, which is critical for financial operations like fare calculations and ride status updates.
Ride Request
- POST Request: The app presents available ride options with corresponding fares. The rider selects a preferred ride option which will send a POST request to the /api/rides/request endpoint to the Ride Service via the API Gateway.
- Create Ride Entry: This will create a new ride entry in the database with status set to "Created". Also can implement optimistic or pessimistic locking in the database to prevent duplicate ride entries or conflicting updates during high traffic.
- Message Sent to Queue: The new ride is placed onto a Driver Assignment Queue for processing. This queue decouples ride creation from driver assignment to improve scalability and reliability.
Driver Assignment Service
- Processing Ride Requests: Listens to the Driver Assignment Queue and pulls new ride requests for processing.
- Locating Nearby Drivers: Geohashing converts the rider's origin coordinates into a geohash which is a hierarchical spatial data structure that encodes geographic locations into short alphanumeric strings.
- Querying the Location Cache: Uses the geohash prefix to find drivers in the immediate vicinity. Quickly narrows down potential drivers by searching within a specific geohash cell. If not enough drivers are found, expands the search to neighboring geohashes. Continues until a sufficient number of candidate drivers are identified. Drivers are prioritised using a scoring algorithm based factors such proximity to rider, vehicle type compatibility, driver status, etc.
- Sequential Driver Notification with Locking: Uses a distributed lock (e.g., Redis-based lock) to ensure the ride request is offered to one driver at a time to prevents multiple drivers from accepting the same ride. Sends a ride request to the highest-priority driver first.
- Sends Push Notification: Utilizes push notification services like Firebase Cloud Messaging (FCM) for Android or Apple Push Notification Service (APNS) for iOS. Sets a timeout period (e.g., 15 seconds) for the driver to respond. If accepted the driver confirms acceptance, and the ride status is updated accordingly. If no response or declined, releases the lock and proceeds to notify the next driver in the list. Repeats until a driver accepts the ride or the candidate list is exhausted. Ensures that at any given time, only one driver holds the lock for the ride request.
Driver Accepts the Ride
- PUT Request to Ride Service: The driver app sends a PUT request to the Ride Service to confirm acceptance of the ride. The request includes the driver's JWT (JSON Web Token) in the authorization header, which contains the driver's ID and other authentication claims. Ensures that only authenticated drivers can accept ride requests.
- Updating the Database: Updates the ride's status in the Ride Database from "Created" to "Accepted". Performs the update as an atomic transaction to prevent race conditions and ensure data integrity.
- Publishing Notification to Rider: Ride Service can create a message which indicates that the driver has accepted the ride and includes driver's name, profile picture, vehicle information (make, model, color, license plate), and estimated time of arrival (ETA). The Rider ID is included in the response from the update allowing the Ride Service to construct the rider's Kafka topic using a secure method, such as hashing the Rider ID.
- The Rider WebSocket Service is already subscribed to the rider's topic in Kafka, established when the rider app connected and authenticated. This persistent WebSocket connection is then used to send the notification to the rider's app in real time.

Complete Architecture

Additional Discussion Points

Scaling
- Scaling Driver Location Redis Cluster: Use Redis Cluster to partition data by region or driver ID. Set up master-replica configurations with Redis Sentinel for failover.
- Scaling PostgreSQL Database: For read scaling implement read replicas and load balancing for read operations. For write scaling using partitioning (sharding) is a viable option.
- Scaling WebSocket Servers: Use sticky sessions or TCP-level load balancing. Optimize resource usage and implement heartbeat mechanisms to ensure proper connection management.
Security
- Authentication & Authorization: Use token-based authentication (e.g., JWT) and enforce role-based access control (RBAC).
- Data Encryption: Encrypt data in transit (TLS/SSL) and at rest in databases.
Monitoring & Logging
- System Monitoring: Use tools like Prometheus and Grafana for real-time metrics (CPU, memory, latency). Implement health checks and application monitoring tools to monitor service performance.
- Centralized Logging: Aggregate logs with ELK Stack or Graylog. Employ structured logging (e.g., JSON) and set up alerts for critical events.

← PreviousCloud File Sharing Service (Dropbox, Google Drive)Next →Proximity Service (Yelp)

Ride Sharing Service (Uber, Lyft)