Design Uber (Ride-Hailing)

A ride-hailing service connects riders who request a trip with nearby available drivers. The hard parts are ingesting a continuous stream of driver locations, finding the nearest available drivers in milliseconds, assigning each driver to at most one rider at a time, and keeping a trip consistent while both phones lose connectivity intermittently.

Requirements

Functional

• A rider requests a ride with pickup and drop-off locations and sees a fare estimate.
• The system matches the rider with a nearby available driver.
• The driver accepts or declines the offer.
• Rider and driver see each other's live location during the pickup and the trip.
• Trip lifecycle: requested, matched, driver arriving, in progress, completed or cancelled.
• Payment at the end of the trip (delegated to the payment system).

Non-functional

• Matching latency: a driver offer within a few seconds of the request.
• Location freshness: driver positions no older than a few seconds.
• High availability for the request and matching path. A brief loss of location updates is acceptable; a double-assigned driver is not.
• Strong consistency for driver assignment and trip state. Eventual consistency for the map view.
• Scale by city: load is geographically partitioned, with peaks in a few dense areas.

Estimation

Assumptions: 5 million drivers online at peak worldwide, one location update every 4 seconds, 20 million trips per day, 2 million riders with the app open at peak.

• Location writes: 5,000,000 / 4 s = 1,250,000 updates per second at peak.
• Update size: driver id, latitude, longitude, heading, speed, timestamp, about 50 bytes. Bandwidth: 1,250,000 x 50 B = 62.5 MB/s ingress.
• Trip requests: 20,000,000 / 86,400 s is about 230 per second on average. Assuming a peak factor of 5, about 1,200 per second.
• Trip storage: 20,000,000 trips x 1 KB = 20 GB per day, about 7 TB per year before compression.
• Location history for trips: a 20-minute trip at 1 update per 4 s is 300 points x 50 B = 15 KB per trip, so about 300 GB per day if retained for every trip.

The dominant load is location writes, not trip requests. Driver locations are only useful while fresh, so they belong in memory, not in a durable database.

What the numbers imply

• 5 million drivers x about 100 B per entry is only about 500 MB, so the index fits on one machine in capacity. It is sharded for write throughput: a Redis-class node handles about 100,000 simple ops/s, so 1.25 million writes/s needs at least 13 shards. Plan 30 to 50 for headroom and replicas. Partitioning by region gives this naturally.
• 62.5 MB/s of ingress is small. The constraint is 5 million persistent connections, or about 50 to 100 gateways at 50,000 to 100,000 connections each.
• 1,200 requests/s at peak, each reading about 7 to 9 cells, is under 10,000 index reads/s, far below the write rate. Matching is a small consumer of the index; ingestion dominates.
• Each trip makes about 6 state transitions, so about 7,000 trip writes/s at peak, which needs a few database shards (by ride id) with headroom.
• 300 GB/day of location history is too much to keep for every trip. Downsample to about 1 point per 10 seconds after the trip and expire raw points after 30 to 90 days.

API design

POST /v1/rides/estimate      { pickup, dropoff, product }  -> { fare_range, eta_pickup }
POST /v1/rides               { pickup, dropoff, product, idempotency_key } -> { ride_id, status }
GET  /v1/rides/{ride_id}     -> { status, driver, location, eta }
POST /v1/rides/{ride_id}/cancel

# driver app
PUT  /v1/drivers/{id}/location  { lat, lng, heading, ts }   (or a persistent connection)
PUT  /v1/drivers/{id}/status    { available | offline }
POST /v1/offers/{offer_id}/accept
POST /v1/offers/{offer_id}/decline

Driver location updates and live trip tracking use a persistent connection (WebSockets) or a lightweight protocol, because opening an HTTP request every 4 seconds per driver is wasteful. The ride request carries an idempotency key so a retry on a flaky network does not create two rides.

Data model

Trip row: ride_id, rider_id, driver_id, status, pickup, dropoff, requested_at, matched_at, started_at, ended_at, fare, version. The version column supports optimistic concurrency on state transitions.

High-level design

flowchart LR
    RA["Rider app"] --> GW["API gateway"]
    DA["Driver app"] --> LB["Location gateway (persistent connections)"]
    GW --> RS["Ride service"]
    RS --> MS["Matching service"]
    MS --> LI[("Location index (in memory, sharded by cell)")]
    LB --> LS["Location service"]
    LS --> LI
    LS --> K[["Kafka: location stream"]]
    RS --> DB[("Trip database")]
    MS --> DS["Dispatch service"]
    DS --> NS["Push / connection gateway"]
    NS --> DA
    RS --> ETA["ETA and routing service"]
    RS --> PR["Pricing service"]
    K --> AN["Analytics, history, surge computation"]
    RS --> PAY["Payment service"]

Component responsibilities:

• Location gateway and service. Terminates driver connections, validates updates, and writes the latest position into the location index. It also appends every update to a log for history and analytics.
• Location index. Holds the current position of each online driver, partitioned by geographic cell. Answers "available drivers within radius r of point p".
• Ride service. Owns the trip state machine and the trip database.
• Matching and dispatch service. Chooses candidate drivers, sends offers, and handles accept, decline, and timeout.
• ETA and routing service. Computes road-network travel time (see Google Maps).
• Pricing service. Computes fare estimates and demand-based multipliers.

Deep dive

1. Geospatial index for driver lookup

A query over all 5 million drivers by distance is too slow. The index partitions the plane into cells so that a query reads a small set of cells. Options (see geospatial indexing):

A common design keeps a map from cell id to the set of driver ids in that cell. When a driver moves, the location service removes the driver from the old cell and adds it to the new one. A query computes the rider's cell, then reads that cell and its neighbors, then filters by exact distance and availability. If too few drivers are found, it expands to the next ring of cells.

The sketch below shows the cell lookup using a simple integer grid, with a record as the cell key (real systems use geohash, S2, or H3 cell ids).

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    static final double CELL = 0.01; // grid size in degrees, roughly 1 km

    record Cell(int x, int y) {
        static Cell of(double lat, double lng) {
            return new Cell((int) Math.floor(lat / CELL), (int) Math.floor(lng / CELL));
        }
    }

    static final class Index {
        private final Map<Cell, List<Integer>> cells = new HashMap<>();

        void add(int id, double lat, double lng) {
            cells.computeIfAbsent(Cell.of(lat, lng), c -> new ArrayList<>()).add(id);
        }

        List<Integer> nearby(double lat, double lng) {
            var center = Cell.of(lat, lng);
            var found = new ArrayList<Integer>();
            for (int dx = -1; dx <= 1; dx++) {
                for (int dy = -1; dy <= 1; dy++) {
                    var ids = cells.get(new Cell(center.x() + dx, center.y() + dy));
                    if (ids != null) {
                        found.addAll(ids);
                    }
                }
            }
            Collections.sort(found);
            return found;
        }
    }

    public static void main(String[] args) {
        var idx = new Index();
        idx.add(1, 37.7749, -122.4194);
        idx.add(2, 37.7800, -122.4180); // adjacent cell
        idx.add(3, 37.9000, -122.3000); // far away
        System.out.println(idx.nearby(37.7760, -122.4190));
    }
}

[1, 2]

Sharding: the location index is partitioned by cell id (or by a coarse parent cell), so a query touches one or a few shards. Dense cells are hot; they are split into smaller cells or assigned dedicated shards. Because each entry is overwritten every few seconds, the index needs no durability. A failed shard rebuilds within seconds as drivers send their next update. A TTL on each entry removes drivers that stopped reporting.

2. Matching and dispatch without double assignment

Steps for one request:

1. Ride service creates the trip in REQUESTED state.
2. Matching service queries the index for available drivers near the pickup, ranks them by ETA to the pickup (road ETA, not straight-line distance), and takes the top candidates.
3. Dispatch atomically reserves the best candidate (AVAILABLE to OFFERED, see below), sends the offer, and starts a timer (for example 10 to 15 seconds).
4. The driver accepts, declines, or the timer fires. On decline or timeout, the reservation is released and the next candidate is reserved and receives an offer.
5. On accept, the driver moves from OFFERED to ON_TRIP and the trip moves from REQUESTED to MATCHED.

sequenceDiagram
    participant R as Rider app
    participant RS as Ride service
    participant M as Matching
    participant L as Location index
    participant D as Driver app
    R->>RS: request ride (idempotency key)
    RS->>RS: create trip REQUESTED
    RS->>M: find driver
    M->>L: nearby available drivers
    L-->>M: candidates
    M->>M: rank by ETA
    M->>L: reserve driver (compare-and-set AVAILABLE to OFFERED, expiry 15 s)
    M->>D: offer (timeout 15 s)
    D-->>M: accept
    M->>L: set driver ON_TRIP
    M->>RS: trip MATCHED
    RS-->>R: driver assigned

The double-assignment risk: two concurrent requests both select driver X. The fix is an atomic claim on the driver record: a compare-and-set from AVAILABLE to OFFERED(trip_id) with an expiry equal to the offer timeout. Only one request succeeds; the other moves to its next candidate. On accept, the driver moves from OFFERED to ON_TRIP; on decline or expiry, the record returns to AVAILABLE. The offer state expires automatically, so a crashed matching service never leaves a driver locked. The trip transition uses the version column (UPDATE ... WHERE ride_id = ? AND version = ?) so that a late accept after a cancel is rejected.

Alternatives: a batch approach collects requests and drivers for a few seconds per region and solves an assignment problem (minimizing total pickup time). This improves global efficiency but adds latency and complexity. Greedy per-request matching is simpler and lower latency.

3. Location ingestion at 1.25 M writes per second

• Use persistent connections and a compact binary encoding to reduce overhead.
• The location service is stateless; it shards writes by driver id to the right index shard.
• Adaptive update rate: send less often when stationary, more often near a pickup. Batching on the client reduces radio use.
• Write to the in-memory index first, then asynchronously to Kafka for history. The matching path does not wait for the log.
• Only the latest position matters for matching, so overloaded shards can drop stale updates safely.

4. Trip state and live tracking

The trip is a state machine; only the ride service transitions it, and each transition is persisted before the notification is sent. Rider tracking subscribes to the driver's position through the connection gateway: the location service publishes updates for drivers on active trips to a pub/sub channel keyed by trip id. If a phone disconnects, the app reconnects and fetches the current state with GET /rides/{id}; state is never inferred from missed events. Cancellations after a threshold apply a fee, decided from the persisted timestamps.

5. ETA and pricing

ETA uses a road graph with live and historical speeds; the pickup ranking depends on it. Surge pricing divides the map into cells, compares open requests with available drivers per cell over a sliding window (computed in a stream processor consuming the request and location streams), and applies a multiplier. Prices are computed once, shown to the rider, and stored on the trip so the quoted fare is honored.

6. Thresholds and consistency choices

• Cell size. H3 resolution 8 has hexagons of about 0.74 km² (edge about 0.46 km) and resolution 9 about 0.1 km². Use resolution 8 by default, query the rider's cell plus its ring-1 neighbors (7 cells, covering roughly 1.2 km), and expand to ring 2 when fewer than about 10 candidates are found. Use resolution 9 in dense areas to keep candidate sets near 100 drivers.
• Consistency. Driver reservation is linearizable per driver, done as one atomic operation on the shard that owns the driver (for example a Lua script or SET ... NX PX). Trip transitions are linearizable per ride through the versioned update. The map view is eventually consistent, and a 1 to 2 second lag is acceptable.
• Offer policy. Offer timeout 10 to 15 seconds, at most 3 to 5 sequential offers per request before widening the search or notifying the rider of a delay. Track a driver's decline and timeout rate to deprioritize unresponsive drivers.
• Alternative for reservation. A distributed lock service adds a network round trip and a failure mode (lock leaked on crash). A CAS with expiry on the record that already holds the driver state is simpler and self-cleaning, so use it.

Bottlenecks and scaling

• Location index hot cells. Airports, stadiums, and city centers concentrate drivers. Use adaptive cell sizes (quadtree) or finer H3 resolution and more shards for hot regions.
• Region partitioning. Partition the whole system by city or region. Matching never crosses regions, which bounds shard count and keeps data local; trips near a boundary query both neighboring regions.
• Dispatch timers. Offer timeouts must survive a matching-service crash. Store the offer expiry in the driver record and let a worker sweep expired offers, or use a durable delay queue.
• Trip database. Shard by ride id. Queries by rider or driver id use secondary lookup tables or per-user indexes (see sharding).
• Failure of the location service. Matching degrades to last known positions for a short interval; drivers reconnect and repopulate the index.
• Multi-region failover. Trip state is replicated across regions (see multi-region); the location index is not, because it self-heals.

Failure modes

• Location shard lost. Drivers repopulate it within one or two update intervals (4 to 8 seconds). Matching sees fewer candidates and offers go to farther drivers, so pickup ETAs grow briefly. Replicas of the index can shorten this.
• Matching service crash mid-offer. The reservation expires by TTL, so the driver is not stuck. The trip stays REQUESTED, and a sweeper or the rider's retry (same idempotency key) restarts matching.
• Late accept. A driver accepts after expiry or after the rider cancelled. The reservation compare-and-set or the versioned trip update fails, and the driver sees "trip no longer available".
• At 10x scale. 12.5 million writes/s needs hundreds of index shards, and a few cells become hot enough to need finer cells and dedicated shards. Per-request greedy matching leaves more mismatch, so batching becomes more attractive. Kafka partitions and trip shards scale linearly, while the routing service call per candidate becomes the limit, so prefilter to about 5 to 10 candidates.

Trade-offs and follow-up questions

• Geohash versus quadtree versus H3: simplicity and key-value compatibility against uniform cells and density adaptation.
• Greedy matching versus batched global assignment: latency against overall pickup time.
• Straight-line distance versus road ETA for ranking: road ETA is more accurate but needs a routing call per candidate. A common compromise is to prefilter by distance, then compute ETA for the top few.
• How would shared rides (pooling) change matching? The problem becomes route insertion: adding a rider to a trip that already has stops, subject to detour limits.
• How to detect and handle GPS spoofing or a driver whose location stops updating? Validate speed between updates and expire stale entries by TTL.
• How to handle the rider and driver both cancelling simultaneously? The versioned state transition allows exactly one to win.
• The driver goes offline during an offer? The TTL frees the reservation. Mark the driver offline and offer to the next candidate right away, without waiting for the timer, when the connection closes.
• The rider cancels while an offer is pending? The trip update to CANCELLED wins by version, and the pending offer is invalidated.