Designing a Ride Sharing Service (Uber/Lyft)

Designing Uber is one of the most complex system design questions because it combines real-time constraints, heavy write throughput (location updates), and complex consistency requirements (payment/matching).

1. Requirements

Functional Requirements

• Rider: Can see nearby cabs. Can request a ride. Can track the driver in real-time.
• Driver: Can accept a ride. Can mark trip as started/ended.
• System: Must match riders with the nearest available driver optimally.

Non-Functional Requirements

• Low Latency: Matching must happen in < 2 seconds.
• Consistency: A driver cannot be assigned to two riders simultaneously.
• High Availability: The system must accept ride requests even if payments are slow.

2. High-Level Architecture

The system is split into two distinct subsystems: the Supply Service (Drivers) and the Demand Service (Riders).

Components

1. WebSocket Gateway: Maintains persistent connections with Driver and Rider apps (avoiding HTTP polling overhead).
2. Location Service: Ingests streams of latitude/longitude updates from drivers.
3. Map Service: Calculates ETA and routes (using Google Maps or OpenStreetMap data).
4. Matching Service: The "brain" that pairs Supply with Demand.
5. Trip Service: Manages the state machine of a trip.

3. The Core Challenge: Geospatial Indexing

How do we efficiently find "all drivers within 1km of User X"?

Naive Approach: SQL

SELECT * FROM drivers WHERE lat BETWEEN x1 AND x2 AND long BETWEEN y1 AND y2

• Problem: This requires a full table scan or massive B-Tree index lookups for every request. It doesn't scale to millions of drivers.

Solution 1: QuadTrees

Solution 2: Geohashing (String-based)

We divide the world into a grid and assign a unique string base-32 string to each cell.

• u4pruydqqvj represents a precise 1 meter box.
• u4pruy represents a larger neighborhood.
• Pro: Neighbors share common prefixes. querying neighbors is just string matching.

Interactive: Spatial Indexing (H3/S2)

Solution 3: Google S2 / Uber H3 (The Industry Standard)

Uber actually uses H3 (Hexagonal Hierarchical Spatial Index).

• Why Hexagons? In a square grid, diagonal neighbors are further away than horizontal neighbors. In a hexagon grid, all 6 neighbors are equidistant. This simplifies "Expand Ring" search algorithms significantly.
• Implementation: Each driver's location is mapped to an H3 Cell ID (a 64-bit integer). This ID is the Sharding Key.

4. Driver Location Updates (Heavy Write Load)

Drivers send updates every 3 seconds. With 1 million active drivers, that's ~330k writes per second.

The Problem with Databases

Writing 330k updates/sec to Postgres or MySQL will kill the disk I/O.

The Solution: Ephemeral Storage (Redis)

We don't need to persist every historical location forever immediately. We only need the current location for matching.

1. Ingestion: Driver app sends coordinates via WebSocket.
2. Buffer: Updates go into a Redis Cluster (Geospatial Set).
   • Command: GEOADD drivers <long> <lat> <driver_id>
3. Expiry: Set a TTL of 10 seconds. If a driver loses connection, they "disappear" from the index automatically.
4. Archival: A separate Kafka stream pumps data to Cassandra/S3 for "Trip History" and analytics/auditing.

5. The Matching Service

When a rider requests a ride:

1. Find Candidates: Query Redis GEORADIUS for drivers within 2km.
2. Filter: Remove drivers who are "Busy" or have "Low Rating".
3. Rank: Call Map Service to get actual driving ETA (not just straight-line distance).
4. Lock: Attempt to "Reserve" the best driver using a Distributed Lock (Redis Redlock).
   • Why? Multiple riders might be requesting in the same area. We must ensure only one rider grabs that driver.
5. Offer: Send "New Ride Request" notification to Driver.
6. Accept: If Driver accepts, create Trip. If Driver ignores/declines, try the next driver in the ranked list.

6. Fault Tolerance

• Ringpop: Uber uses a library called Ringpop for application-layer sharding. It allows services to gossip and discover which node handles which Hexagon ID.
• Availability vs Consistency: For the "Location Service", we favor Availability (AP). It's okay if a driver position is 3 seconds stale. For "Payment/Trip", we favor Consistency (CP).

Summary

• Index: H3 (Hexagonal) for uniform neighborhood traversal.
• Storage: Redis for high-write throughput of ephemeral locations.
• Communication: WebSocket for bi-directional low-latency updates.
• Scale: Shard by H3 Cell ID.