Uber Design (Ride-Hailing)

---

0) Problem Restatement

Design a ride-hailing service like Uber where riders can request rides, and drivers are matched with them in real-time. Key challenges include highly accurate location tracking, low-latency matching, handling demand spikes (surge pricing), and maintaining strong consistency for payments and trip records across millions of concurrent sessions.

---

1) Requirements

1.1 Functional

• Request Ride: Rider provides pickup/dropoff and requests a vehicle.
• Driver Matching: System finds the nearest available driver.
• Real-time Tracking: Rider and driver can see each other's live location.
• Payments: Automatic fare calculation and processing.
• Ratings: Both parties rate each other post-trip.

1.2 Non-Functional

• Low Latency: Matching and updates must happen in < 1-2 seconds.
• High Availability: Service must be operational globally 24/7.
• Scalability: Support millions of drivers and riders simultaneously.
• Consistency: Critical for trip states and wallet/payment transactions.

1.3 Scale Estimates

• DAU: 20 Million riders, 2 Million drivers.
• Trips per Day: 5 Million.
• Peak Request Rate: 10,000 matches per second during rush hours.
• Location Updates: Drivers push GPS updates every 5 seconds (~400k writes/sec).

1.4 API Design

The core APIs required for the service:

• Request Ride: POST /v1/rides/request - Initiate a trip request.
• Update Location: POST /v1/driver/location - Driver heartbeat and GPS.
• Accept Ride: POST /v1/driver/accept - Driver claims a match.
• Complete Trip: POST /v1/rides/:id/complete - Trigger payment and rating.

---

2) High-Level Architecture

2.1 Overview

• Matching Service: Uses geospatial indexing (like S2/H3) to find nearest drivers.
• Location Service: High-throughput ingestion for driver GPS heartbeats.
• Trip Service: Manages the lifecycle and state machine of a ride.
• Payment Service: Integrates with external gateways for secure transactions.

2.2 Architecture Diagram

Architectural Diagram Locked
Sign In to Unlock Diagram

---

3) Data Model

Trips Table (Strong Consistency)

json { "trip_id": "UUID", "rider_id": "UUID", "driver_id": "UUID", "pickup_location": "Geography", "dropoff_location": "Geography", "status": "enum (requesting, matched, in_progress, completed)", "fare": "decimal", "created_at": "timestamp" }

---

4) Flows

4.1 Matching Flow

1. Rider requests a ride; Pricing Service calculates surge.
2. Matching Service queries Geospatial Index for nearby "active" drivers.
3. System sends push notifications to drivers in waves (nearest first).
4. First driver to accept is tied to the trip ID in a transaction.

---

5) Scale Considerations

• Geospatial Sharding: Use H3 cells to shard the matching engine so London and NYC matchings don't compete for the same server.
• Surge Pricing: Implement a separate low-latency service that monitors supply/demand ratios per cell.
• WebSocket Gateway: Maintain persistent connections for live location updates.

---

6) Deep Dive Topics

6.1 Geospatial Indexing (Quadtrees vs. H3)

• Quadtrees: Good for static data but hard to re-balance for moving objects (drivers).
• H3 (Uber's Choice): Uses hexagonal tiling. Hexagons have the same distance to all neighbors, simplifying ETA calculations and preventing the "corner" bias seen in square grids.
• Sharding: By using H3 cell IDs as shard keys, we ensure that matching requests for "Downtown SF" are processed by a dedicated cluster of matching engines.

6.2 Consistency & Distributed Transactions

• The Double-Accept Problem: Two drivers accept the same ride at the same millisecond.
• Solution: Use atomic UPDATE with a WHERE status = 'requesting' clause or a distributed lock (Redis/Zookeeper) to ensure only one driver is tied to a Trip ID.

---

7) Tradeoffs & Extensions

7.1 Tradeoffs

• WebSocket vs. HTTP Heartbeats: WebSockets provide lower latency for "car moving on map" but require significantly more server memory. Uber uses a mix of highly optimized UDP/HTTP heartbeats for basic location and WebSockets for active "on-trip" views.
• ACID vs. BASE: High availability (AP) is needed for location updates, but strict consistency (CP) is non-negotiable for payments and trip history.

7.2 Extensions

• Uber Pool (Matching Optimization): Solving the "Static Traveling Salesman" problem in real-time to group passengers with minimal detour.
• Dynamic Routing: Integrating real-time traffic data to provide hyper-accurate ETAs.

---

8) Wrap-Up

Designing Uber requires balancing extreme write throughput (driver heartbeats) with complex real-time matching. By leveraging hexagonal geospatial indexing and a robust trip state machine, the system provides a seamless experience for millions of concurrent users.