Uber (Ride Hailing)

Metadata

Building Blocks Used

This case study builds upon the following foundational concepts:

• WebSockets & Long Polling (Real-time tracking)
• Consistent Hashing (Distributing geohashes)
• Message Queues (Decoupling services)

1. System Requirements

Functional Requirements

• Drivers can regularly broadcast their current GPS location.
• Riders can see nearby available drivers on a map in real-time.
• Riders can request a ride, and the system matches them with the closest available driver.
• Once matched, the driver and rider can see each other's location continuously updated until the trip ends.

Non-Functional Requirements

• High Concurrency & Write Heavy: Millions of drivers pinging their location every 5 seconds.
• Low Latency Matchmaking: Riders expect to find a driver in seconds.
• Accuracy: Geospatial queries must accurately return drivers within a specific radius.

2. Back-of-the-Envelope Estimation

• Active Drivers: 1 Million.
• Active Riders: 5 Million.
• Location Pings: Drivers ping their location every 5 seconds.

QPS (Queries Per Second)

• Driver Location Writes: 1,000,000 / 5 = 200,000 Writes / second.
• Rider Map Reads: Assuming riders open the app 2 times a day and stare at the map for 1 minute (refreshing every 5 seconds).
  • 5,000,000 × 2 × (60 / 5) / 86400 ≈ 1,500 Reads / second.
• Takeaway: This system is heavily skewed towards writes. 200k writes/sec is massive. We cannot write driver locations to a traditional SQL database or we will instantly lock up the disk.

3. High-Level Architecture

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#ffcc00', 'edgeLabelBackground':'#ffffff'}}}%%
graph TD
    classDef client fill:#f9f9f9,stroke:#333,stroke-width:2px;
    classDef svc fill:#cce5ff,stroke:#007bff,stroke-width:2px;
    classDef db fill:#f8d7da,stroke:#dc3545,stroke-width:2px;
    classDef mq fill:#ffeeba,stroke:#ffc107,stroke-width:2px;

    D((Driver)):::client -->|Location Ping (5s)| API[API Gateway]:::svc
    R((Rider)):::client -->|Find Drivers| API
    
    API --> LocSvc[Location Service]:::svc
    API --> MatchSvc[Matchmaking Service]:::svc
    
    LocSvc -->|Publish| Kafka[(Kafka<br/>Message Queue)]:::mq
    
    Kafka -->|Update Tree| Indexer[QuadTree Updater Worker]:::svc
    Kafka -->|Persist History| Cassandra[(Cassandra<br/>Trip History)]:::db
    
    Indexer --> Redis[(Redis<br/>Driver State)]:::db
    Indexer --> QuadTree[(QuadTree Index<br/>Memory)]:::db
    
    MatchSvc --> QuadTree

4. Deep Dive: Tracking Driver Locations

If 1 million drivers send a GPS coordinate (lat, long) every 5 seconds, how do we process 200,000 writes/sec?

We use a Message Queue like Kafka as a buffer.

1. The phone hits the Location Service.
2. The Location Service drops the GPS ping into Kafka and instantly returns a 200 OK.
3. Background workers (Consumers) process the Kafka stream at their own pace, updating the driver's current state in an in-memory Redis Cache.
4. Separately, a database like Cassandra logs the historical path for billing and analytics (an append-only workload that Cassandra excels at).

5. Deep Dive: Geospatial Indexing (The Core Problem)

When a rider opens the app, we need to answer: "Find all active drivers within a 3-mile radius of (Lat: 37.77, Long: -122.41)."

Approach 1: SQL Database

SELECT * FROM drivers 
WHERE lat BETWEEN 37.70 AND 37.84 
  AND long BETWEEN -122.48 AND -122.34;

This is a 2D range query. Traditional B-Tree indexes (used in Postgres/MySQL) are 1D. They cannot efficiently index two dimensions simultaneously. This query would require scanning millions of rows.

Approach 2: Geohash

Geohash divides the Earth into a grid of grids. It converts a 2D coordinate into a 1D string (e.g., 9q8yy).

• 9q8 represents the Bay Area.
• 9q8yy represents a specific neighborhood in San Francisco. Drivers matching 9q8yy* are nearby. This is great, but grids are fixed in size. A grid over Manhattan might contain 10,000 drivers, while a grid over rural Montana contains 0.

Approach 3: QuadTree (The Standard Solution)

A QuadTree is a tree data structure where each node has exactly four children. We start with the whole world as the root node. We divide it into 4 quadrants. If a quadrant has more than N drivers (e.g., 500), we subdivide it into 4 smaller quadrants. We repeat this recursively.

Why is this brilliant?

• In dense cities (New York), the grid squares become tiny, allowing highly precise local searches.
• In rural areas (Montana), the grid square remains massive.
• The tree perfectly adapts to the density of the drivers!

When a rider searches for a driver, we traverse the QuadTree from the root down to the rider's specific quadrant, and return the list of drivers in that leaf node.

6. Bottlenecks & Trade-offs

The Write Bottleneck on the QuadTree

QuadTrees are typically stored entirely in RAM because they require complex pointer traversal. If we have 200,000 driver movements per second, we have to update the QuadTree 200,000 times a second. If a driver crosses a quadrant boundary, we have to remove them from Node A and add them to Node B. Locking the tree for thread safety during these writes will throttle the system.

The Solution: We don't update the QuadTree every 5 seconds. A rider doesn't care if a car on the map is 10 feet further down the road. We only update the QuadTree if the driver moves significantly (e.g., more than 50 meters) or crosses a major grid boundary. We also shard the QuadTree. Node 1 handles the North America tree, Node 2 handles the Europe tree, etc.

Real-Time Updates After Matching

Once a rider requests a ride and a driver accepts, they enter a trip. They no longer need the QuadTree. The driver and rider establish a persistent WebSocket connection. The driver's phone sends GPS coordinates to a Pub/Sub topic specifically for that trip_id, and the rider's phone subscribes to it, providing a smooth, 1-second refresh rate on the map.

7. Summary of Building Blocks Used

Website Metadata