Designing Uber: Real-Time Location, Dispatch, and Ride Matching

Why Study Uber?

Uber coordinates millions of concurrent trips across thousands of cities, matching riders with nearby drivers in seconds while both parties are physically moving. Unlike most system design case studies where the hard problem is storage or fan-out, Uber's hard problem is geospatial: finding "who is near me, right now" at massive scale, continuously, under tight latency budgets.

Requirements Analysis

Functional Requirements

1. Location Tracking: Continuously track driver (and active rider) locations
2. Ride Request: Rider requests a trip from pickup to destination
3. Matching: Find and assign the best nearby available driver
4. Pricing: Compute fare, including dynamic surge pricing under high demand
5. Trip Management: Track a trip through its full lifecycle (requested → completed)
6. Real-Time Updates: Both rider and driver see live location and trip status

Non-Functional Requirements

High-Level Architecture

Geospatial Indexing: Geohash vs. S2 Cells

Why Proximity Search Needs an Index

Finding "drivers within 2km of this rider" sounds like a simple query, but a naive approach - scanning every driver row and computing a haversine distance - is O(n) per request. With millions of drivers and thousands of match requests per second, that's untenable. What's needed is a way to turn 2D proximity into something an index (or an in-memory hash map) can answer in near-constant time: a spatial encoding that maps nearby coordinates to nearby (often identical-prefix) keys.

Geohash

Geohash recursively subdivides the world into a grid of rectangular cells, encoding each cell as a base32 string. Every extra character narrows the cell further - 9q8yy is a bigger area than 9q8yyk. Points physically close to each other usually (not always, because of edge effects at cell boundaries) share a common string prefix, which is what makes range queries and prefix lookups useful for proximity search.

Google S2 Cells

S2 projects the Earth's surface onto a cube and recursively subdivides each cube face into a hierarchy of cells, indexed via a Hilbert space-filling curve. The practical advantage over geohash is that S2 cells are closer to uniform in physical area at every latitude and don't suffer from the specific boundary discontinuities geohash has near cell edges (where two physically adjacent points can have very different prefixes) - which matters when doing consistent, predictable "nearest neighbor" ring searches. Uber built its own similar system (originally influenced by S2) for exactly this reason.

Geohash vs. S2 Comparison

Real-Time Location Updates

Why WebSockets, Not Polling

Driver apps maintain a persistent WebSocket (or similar long-lived) connection to a location gateway rather than polling an HTTP endpoint. Polling at a frequency high enough to feel "real-time" (every few seconds) from millions of idle devices wastes enormous connection-setup overhead; a persistent connection lets the server push trip offers and status changes to drivers/riders instantly, and lets drivers stream location cheaply over an already-open channel.

Ping Frequency Tradeoffs

Dispatch / Matching Service

Nearest-Available-Driver Algorithm

The matching service doesn't just grab the closest driver by straight-line distance - it ranks candidates by estimated time to pickup (accounting for road network and traffic), and often batches nearby requests together to solve a small local assignment problem rather than greedily matching one-by-one, which reduces total fleet idle time across a busy area.

Matching Timeout and Re-Broadcast

If a driver doesn't accept an offer within a short timeout (typically several seconds), the offer expires and dispatch moves to the next-ranked candidate rather than waiting indefinitely - keeping the rider's wait time bounded. A driver who is offered a trip is provisionally "locked" (reserved) for that offer window so two riders can't simultaneously be matched to the same driver; if the offer times out or is declined, the lock releases and the driver becomes available to the next search.

Trip State Machine

Each transition is driven by an explicit event (driver app action, rider app action, or a system timeout) and is written to the trip record, giving both apps a single source of truth for what UI to render. Keeping this as an explicit state machine - rather than a loose set of boolean flags - is what prevents invalid transitions like "completing" a trip that was never marked in-progress, or double-cancelling.

Surge Pricing

Supply/Demand Ratio Per Geo-Cell

Surge pricing computes a multiplier per geographic cell (the same cell granularity used for matching) based on the ratio of open ride requests to available drivers in that cell over a short rolling window. A cell with many riders requesting and few available drivers gets a higher multiplier; a balanced or oversupplied cell stays at 1x.

The multiplier is recomputed continuously (every few seconds to a minute) and cached per cell with a short TTL, since demand can shift quickly. It's smoothed and capped to avoid wild spikes from noisy short-term fluctuations (e.g., a temporary lull of two drivers finishing back-to-back trips shouldn't itself trigger extreme surge), and applied to the fare at the moment a rider requests a trip, then locked in for that specific request so the price can't shift after the rider has already committed.

Database Schema

Drivers Table

CREATE TABLE drivers (
    id BIGINT PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    vehicle_type VARCHAR(20) NOT NULL,
    status VARCHAR(20) NOT NULL DEFAULT 'offline',
    -- offline | available | offered | on_trip
    rating DECIMAL(3,2) DEFAULT 5.00,
    current_cell_id VARCHAR(20),
    last_ping_at TIMESTAMP,
    created_at TIMESTAMP DEFAULT NOW()
);
 
CREATE INDEX idx_status_cell ON drivers(status, current_cell_id);

Trips Table

CREATE TABLE trips (
    id BIGINT PRIMARY KEY,
    rider_id BIGINT NOT NULL,
    driver_id BIGINT,
    state VARCHAR(20) NOT NULL DEFAULT 'requested',
    -- requested | matching | matched | driver_arriving | in_progress | completed | cancelled
    pickup_lat DOUBLE PRECISION NOT NULL,
    pickup_lng DOUBLE PRECISION NOT NULL,
    dropoff_lat DOUBLE PRECISION NOT NULL,
    dropoff_lng DOUBLE PRECISION NOT NULL,
    surge_multiplier DECIMAL(4,2) DEFAULT 1.00,
    fare_estimate_cents INT,
    fare_final_cents INT,
    requested_at TIMESTAMP DEFAULT NOW(),
    matched_at TIMESTAMP,
    started_at TIMESTAMP,
    completed_at TIMESTAMP
);
 
CREATE INDEX idx_rider_id ON trips(rider_id, requested_at DESC);
CREATE INDEX idx_driver_id ON trips(driver_id, requested_at DESC);
CREATE INDEX idx_state ON trips(state);

Driver Locations (Time-Series-ish Table)

CREATE TABLE driver_locations (
    driver_id BIGINT NOT NULL,
    lat DOUBLE PRECISION NOT NULL,
    lng DOUBLE PRECISION NOT NULL,
    cell_id VARCHAR(20) NOT NULL,
    heading SMALLINT,
    speed_mps DECIMAL(5,2),
    recorded_at TIMESTAMP NOT NULL,
    PRIMARY KEY (driver_id, recorded_at)
);
 
CREATE INDEX idx_cell_recent ON driver_locations(cell_id, recorded_at DESC);

End-to-End Ride Request Flow

Scaling Challenges & Solutions

Key Takeaways

1. Spatial indexing is the foundation: Geohash or S2 cells turn "who's nearby" from an O(n) scan into an O(1) lookup - this is the single most important design decision in the whole system.
2. Persistent connections beat polling for real-time state: WebSockets let the server push offers and status instantly and let clients stream location cheaply.
3. Matching is a ranked, time-bounded search, not a single lookup: ETA-based ranking, offer timeouts, and re-broadcast keep the system both accurate and live.
4. Model the trip lifecycle explicitly: A state machine enforced server-side prevents an entire class of "impossible state" bugs.
5. Surge pricing is a supply/demand signal, not just a price: It rations scarce drivers and pulls in idle supply from nearby cells.
6. Separate the hot path from the historical record: Live matching reads an in-memory index; the durable location table serves history, auditing, and analytics.

Follow-Up Questions to Consider

1. How would you handle a driver going offline mid-trip (app crash, connectivity loss, or the phone dying)?
2. How would you design multi-stop or shared/pooled rides, where a driver serves more than one rider concurrently?
3. How would you extend the matching algorithm to account for driver preferences (e.g., avoiding certain areas, ending a shift soon)?
4. How would you detect and prevent GPS spoofing or fraudulent location pings from drivers trying to manipulate surge zones?
5. How would you design the ETA prediction system itself - the piece that ranks candidates by predicted arrival time?