Design Uber: Driver Locations, Matching Without Double Booking, Surge and Trips

Listen

Requirements. The rider opens the app and sees nearby cars. They enter a destination and get a price and pickup ETA, request a ride, get matched, track the driver, and pay automatically at the end. Drivers go online, stream their location, receive offers to accept or decline, and start and end trips. Shared rides, scheduled rides and food delivery are out of scope, though mention that pooling turns matching into a routing problem.

Qualities. Matching should take a few seconds. Assignment must be strongly consistent: a driver can never be on two trips, even under retries and races. Locations need freshness, not durability; dropping a ping is fine. A price quote should be honoured for a few minutes so the rider isn't surprised. Availability matters a lot, because an outage leaves people stranded at night. And like food delivery, isolate cities from each other.

Ask scale

Assume thirty million trips a day: about three hundred ride requests a second, a thousand at peak, plus several price quotes per trip. The big numbers come from movement. Two million drivers online at peak, pinging every four seconds, is half a million location writes a second. And ten million riders with the app open, refreshing nearby cars every five seconds, is two million reads a second. So the supply index, where the drivers are right now, is the hot path.

Memory and storage. Each live driver record is about sixty-four bytes, so two million drivers is only around a hundred twenty-eight megabytes. The problem isn't size, it's half a million updates a second plus millions of queries. Trips are about five kilobytes with their route, roughly a hundred fifty gigabytes a day. Raw pings are a couple of terabytes a day, which go to a stream and cold storage for analytics, fraud checks and fare disputes.

trips/day             30M
  30M / 100,000 s    = 300/s
  peak x3            = ~1K/s
quotes ~5 per trip    = 5K/s peak

drivers online, peak  2M
  ping every 4 s     = 500K/s
riders with app open  10M
  nearby-cars poll 5 s
                     = 2M/s reads
-> supply index is the hot path

live driver: id, lat, lng,
  heading, status, cell ~ 64 B
  2M x 64 B          = 128 MB

trip record ~ 5 KB with route
  30M x 5 KB         = 150 GB/day
  x 365              = ~55 TB/yr

raw pings 500K/s x 50 B
  = 25 MB/s = ~2 TB/day
  -> stream, cold storage

Define API

The API. A quote takes pickup, drop-off and product, and returns a price, an ETA, and an expiry. Requesting a ride references the quote, so the price is locked, and carries an idempotency key. Drivers post locations, often over a persistent connection to cut overhead. Drivers accept offers. Riders receive driver position and trip status over a socket, and drivers receive offers and trip updates over theirs.

POST /v1/quotes
  { pickup, dropoff, product }
  -> { quoteId, price, eta,
       expiresAt }
POST /v1/rides  { quoteId }
  Idempotency-Key: ..
POST /v1/drivers/me/location
  { lat, lng, heading, ts }
POST /v1/offers/{id}/accept
WS   rider: driver pos, status
WS   driver: offers, trip

Data model

Data model. Trips are the money records: a consistent, replicated store keyed by trip ID, sharded by city. A separate driver state row holds status, open, offered or on trip, the current trip ID and a version number; this row is how we prevent double booking. Quotes are short-lived with a time-to-live. And the live supply index lives in sharded memory, mapping each cell to the drivers currently in it.

trip   (tripId, cityId, riderId,
        driverId, state, version,
        quoteId, fare, route)
driver_state (driverId PK,
        status, tripId, version)
        status: offline | open |
        offered | on_trip
quote  (quoteId, price, mult,
        expiresAt)  short TTL
supply (in RAM) cell -> drivers

High-level design

Start with the location path. Drivers stream pings to the location service through the edge gateway. Each ping updates the driver's cell and position in the in-memory supply index, and is also written to the event stream for anything that needs history. The rider's map of nearby cars is a read from the same index, slightly blurred and throttled, because riders only need an impression of supply, not exact positions.

The request path. The rider gets a quote from pricing. On request, the trip service creates a trip in the requested state and asks matching for a driver. Matching pulls open drivers from cells around the pickup, asks routing for real road ETAs, picks the best and sends an offer. When the driver accepts, the trip and driver state update atomically. After the trip ends, payments charges the card.

Deep dive: supply index

Deep dive one: the supply index. Divide the map into hexagon cells; Uber open-sourced a system for this called H3. Hexagons are nice because every neighbour is the same distance away, so rings of cells approximate a circle well. At a mid resolution a cell is under a square kilometre. Shard the index by cell, grouped by city, and when a driver crosses a boundary, remove them from the old cell and add them to the new one. Give entries a fifteen-second expiry, so a driver whose phone dies quietly disappears.

How do you handle half a million writes a second? Keep disk off the hot path. Ingest nodes are stateless and route each ping to the shard owning that cell. The shard updates memory in place and drops any ping older than the one it already has. Each shard has a standby replica, but even if both fail, the index refills from fresh pings within one ping cycle, about four seconds. That's the beauty of state that is constantly re-sent: recovery is free.

Deep dive: nearest car

Deep dive two: finding the nearest car. Start at the pickup cell and expand ring by ring until you have around twenty open drivers. Filter by product type, and prefer drivers heading toward the rider. Then the key point: rank by road ETA, not straight-line distance. A driver two hundred metres away across a river, or on the wrong side of a highway, can be ten minutes away. The routing service computes ETAs on a road graph with live traffic, and caches results between cell pairs for a short time.

Deep dive: assignment

Deep dive three: never double book. Two matchers working on two riders might both pick the same driver. So before sending an offer, matching does a conditional update on the driver's row: set status to offered, but only if it's still open and the version hasn't changed. Zero rows changed means someone else got there first, so try the next candidate. Acceptance is one transaction: driver to on trip, trip to accepted, only if the offer is still valid. An ignored offer expires after about fifteen seconds.

A senior-level point: greedy versus batched matching. Greedy gives each request its best driver immediately. But imagine two riders and two drivers: greedy can give the first rider a driver who was the only good option for the second, leaving the second rider a long wait. Batching collects requests in an area for a couple of seconds and solves an assignment problem that minimises total pickup time. In busy areas that small delay pays for itself.

offer: UPDATE driver_state
  SET status=offered, offer=77,
      version=version+1
  WHERE id=D AND status=open
  AND version=v   -- 0 rows: skip

accept (one transaction):
  driver_state -> on_trip(T)
  trip T -> ACCEPTED, driver D
  only if offer 77 still valid
offer timeout 15 s -> open

Deep dive: surge

Deep dive four: surge pricing. A stream job computes, for each cell about every minute, demand from quotes and requests and supply from open drivers. The ratio maps to a price multiplier. Smooth it over time and across neighbouring cells so prices don't flicker or jump at a street boundary, and apply caps and rules such as during emergencies. The quote records the multiplier, and a request within its expiry honours that price, even if surge changes a second later.

Deep dive: trip states

The trip lifecycle. Requested, accepted, arrived, in progress, completed, paid, with cancellation rules that depend on the state and how long it's been. Each change is written with an outbox entry in one transaction, and the event stream carries it to everyone who cares. Payments consumes the completed event and charges the card using the trip ID as an idempotency key, so a replayed event never charges twice. The final fare uses the route reconstructed from the driver's pings.

REQUESTED -> ACCEPTED
  -> ARRIVED -> IN_PROGRESS
  -> COMPLETED -> PAID
cancel: by rider or driver,
  fee rules by state + time

each change: state + outbox in
  one transaction
payments consumes COMPLETED,
  charges with tripId as key
fare = route from pings

Trade-offs

Failures. A lost supply shard refills from pings in seconds. If matching is down, requests wait and riders see a still-looking message, and the conditional updates mean recovery can't double book anyone. If the trip database fails over to a replica, trips already in progress continue, because both phones know the state and the driver app buffers pings to upload later. Monitor time to match, ETA error against actual pickup time, and offer acceptance rate.

Trade-offs. The supply index is fast but only approximately accurate at any instant, which is fine because ETAs absorb a few seconds of error. Batched matching adds a two-second delay for better outcomes overall. Smoothing surge slows its reaction but avoids price shocks. At ten times the scale, use finer cells in dense cities, more shards, fully regional stacks, and move completed trips to an archive so the hot trip store stays small.

Say it like this

The summary. Half a million pings a second go into a sharded in-memory index of hexagon cells, refilled from pings on failure. Candidates come from a ring search around the pickup, ranked by road ETA rather than distance. Assignment uses a conditional update on the driver's state, so no driver is ever double booked, and acceptance is a single transaction. Batch matching in busy areas. Surge is demand over supply per cell, locked into the quote. Trips are a state machine with outbox events driving payment.