Uber (ride matching)
Track a million moving drivers and match each ride request to a nearby free driver in about a second. The write path is a firehose of location pings; the correctness problem is never assigning one driver to two riders.
Component labels and connections
- Clients (client) · calls: Load balancer
- Load balancer (loadBalancer) · calls: Dispatch API 1, Dispatch API 2
- Dispatch API 1 (service) · calls: Location index (by cell), Dispatch state
- Dispatch API 2 (service) · calls: Location index (by cell), Dispatch state
- Location index (by cell) (kvStore) · calls: none
- Dispatch state (database) · calls: none
Requirements
Functional
- Drivers send their location every few seconds.
- A rider requests a ride; the system finds nearby available drivers, offers the trip, and assigns exactly one driver.
- Track trip state (requested, assigned, in progress, completed).
Non-functional
- Matching decision within ~1 s of the request.
- Location updates are loss-tolerant: a newer one arrives seconds later.
- A driver is never assigned two concurrent trips.
- Survive the loss of a data centre: dispatch for a city must fail over.
Worked estimates
Location writes
≈ 250k writes/s, each ~100 B
1M online drivers ÷ 4 s ping interval
Location memory
≈ 400 MB — the supply index fits in memory
1M drivers × ~200 B (position, cell, state, timestamp) × 2 replicas
Ride requests
≈ 700 requests/s at peak, each a geo query plus a claim
20M trips/day ÷ 86,400 × ~3 peak factor
Geo query size
tens to a few hundred candidates — query the rider's cell and its neighbours, not a radius over everything
drivers within ~2 km in a dense city
Ingress bandwidth
≈ 75 MB/s — fine; the per-request overhead is what you optimise (batching, persistent connections)
250k/s × ~300 B with headers
API
POST /v1/drivers/{id}/location
Request: { lat, lng, heading, ts }
Response: 200
Last-write-wins by timestamp; stale pings are dropped.
POST /v1/rides
Request: { pickup, dropoff, product } + Idempotency-Key
Response: 200 { tripId, driver } · 409 candidate taken (retry with next)
POST /v1/trips/{id}/complete
Request: —
Response: 200
Frees the driver.
Data model
- locations — store: geo
- drivers — store: dispatchdb
locations: latest position per driver plus its geo cell (H3 hexagon at resolution ~8–9), held in memory and indexed by cell. Not a durable history — that goes to a log for analytics.
drivers: authoritative dispatch state (available / on trip), changed only by atomic conditional updates.
Trips are a separate durable entity with a state machine; payment and receipts hang off it.
High-level design
Trace permitted calls in the architecture above, then open the reference canvas to inspect routing.
Deep dives
Indexing moving points
Map each location to a cell (H3 resolution 8 cells are about 0.7 km² each) and keep, per cell, the set of drivers in it. A ping that changes cell moves the driver between two sets. A query takes the rider's cell plus one or two rings of neighbours, filters by state and ranks by estimated time of arrival from a routing engine, not straight-line distance. Shard the index by cell (or city) so one city's load stays on its shards.
Assigning exactly one driver
Matching proposes; the dispatch state decides. Claim a driver with an atomic conditional write (available 1 → 0, or compare-and-set on a version) in the store that owns the driver. A rejected claim moves on to the next candidate. The offer to the driver has a timeout, after which the claim is released — a lease. Batch matching (collect requests for a second, solve an assignment problem per area) gives better global ETAs than greedy nearest-driver.
Ping ingestion
Pings arrive over persistent connections, are validated (clock, speed sanity checks), written to the in-memory index and appended to a log (Kafka) for ETA models, fraud detection and trip reconstruction. Last-write-wins by device timestamp drops out-of-order pings. Losing a few pings is harmless; losing the index means rebuilding it from the next 4 s of pings.
Regional failover
Dispatch state is per city, so cities are the unit of failover. Uber has described keeping enough trip state on the driver's phone to rebuild a trip in another data centre after failover; the general lesson is that the partition key (city) should also be the failure domain.
Failure scenarios
Everyone wants the same driver downtown
Scenario and expected result
After a concert, 20% of all traffic targets one driver ID — many riders' nearest candidate is the same car. Pings and claims for that driver race.
Expected: Exactly one rider gets the driver; every other claim gets 409 and would retry with the next candidate. Goodput drops because a 409 counts as a failed request, but the invariant holds: no double assignment. Compare the read-then-write alternative.
Location pings triple
Scenario and expected result
From t = 1.2 s to 2.2 s traffic triples — a mobile client release that pings every second instead of every 4.
Expected: The in-memory index absorbs it: writes are sub-millisecond and the ring has spare workers. Matching latency barely moves. If pings went to the dispatch database instead, it would be the first thing to fall over.
The dispatch database leader dies
Scenario and expected result
The dispatch database leader is killed at t = 1.5 s; a replica is promoted after about 0.5 s.
Expected: Location updates continue (they never touch the dispatch database). Ride claims and completions fail for the half second of detection and election, then resume on the new leader. With semi-synchronous replication and fencing, no acknowledged assignment is lost and the old leader cannot assign anyone after it returns.
Alternative designs
Reference
- Inspect the architecture above and run the same scenario.
Read the driver's state, then write it
- The obvious code: read available, if 1 then set 0. Two dispatchers matching two riders to the same nearby driver both read 1 and both assign. Run the downtown surge against it and the engine reports the driver 'oversold'. Use an atomic conditional update (compare-and-set, or decrement-if-positive) instead.
Reference
- Inspect the architecture above and run the same scenario.
Store locations in the relational database
- Durable and queryable with a spatial index, but 250k updates/s of data that is obsolete in 4 seconds is the worst workload for a WAL-based, disk-backed store. Keep the hot supply index in memory and send pings to a log for history.
Reference
- Inspect the architecture above and run the same scenario.
Geohash or quadtree instead of H3
- Geohash cells are rectangles whose neighbours have different shapes and whose size varies with latitude; a quadtree adapts to density but must be rebalanced as drivers move. Uber built H3 because hexagons have uniform neighbour distances, which makes 'cells within k rings' a good approximation of a radius.
Clarifying questions
- How many drivers online, and how often do they ping?
- Matching radius and time target?
- Can a driver have pooled trips?
- Is the system global or per city?
Common mistakes
- Writing every ping to a relational database.
- Radius queries over all drivers instead of cell lookups.
- Read-then-write driver assignment.
- Treating location data as precious and replicating it synchronously.
- Ignoring which unit fails over.
Self-assessment rubric
requirements / levels 1-4
- 1/4 Request a ride.
- 2/4 Locations and matching.
- 3/4 Latency, loss tolerance, no double assignment.
- 4/4 Failover unit and trip state machine.
estimates / levels 1-4
- 1/4 None.
- 2/4 Ping rate.
- 3/4 Ping rate, index memory, ride rate.
- 4/4 Shows the index fits in memory and the database must not take pings.
api / levels 1-4
- 1/4 Endpoints.
- 2/4 Ping and request.
- 3/4 Claim conflicts and idempotent ride requests.
- 4/4 Offer/accept with timeouts (leases).
data model / levels 1-4
- 1/4 Drivers table with lat/lng.
- 2/4 Geo index named.
- 3/4 Cell-based in-memory index + authoritative dispatch state.
- 4/4 Separates hot location state, durable trips and the ping log.
high level / levels 1-4
- 1/4 One service and DB.
- 2/4 Location service + dispatch.
- 3/4 Sharded index, atomic claims, log for history.
- 4/4 City-scoped sharding and failover.
deep dive / levels 1-4
- 1/4 None.
- 2/4 Mentions geohash.
- 3/4 Cell queries with neighbour rings and ETA ranking.
- 4/4 Race-free assignment, batch matching and index rebuild.
wrap-up / levels 1-4
- 1/4 Stops.
- 2/4 Metrics.
- 3/4 Hot cells and dispatch store as risks.
- 4/4 Matching latency SLO, conflict rate and failover drills.