The 100 problems, solved / Maps and location / 039 · Design Uber

Design Uber

Match riders to the nearest drivers in seconds while every driver moves.

Problem 039 of 100Maps and locationL51 Nov 2026
Concepts this design leans on

01The design, in the six-step framework

1. Requirements

Functional

  • Riders request a trip from A to B and get matched with a nearby driver within seconds.
  • Drivers share location continuously; riders see the driver approach.
  • Fare estimate before the trip, final fare and payment after.
  • Trip lifecycle: requested, matched, en route, in progress, completed, cancelled.
  • Out of scope: surge pricing models, driver onboarding, ratings.

Non-functional

  • 5 million active drivers; 30 million trips a day; a city at peak has 100,000 online drivers.
  • Match within 5 s; driver location visible to the rider with under 3 s delay.
  • A driver is never assigned two trips; a trip is never charged twice.
  • Matching availability 99.99 percent in each city independently.
  • Location history retained 30 days for support and safety.
Back of the envelope

5 M drivers × 1 update every 4 s = 1.25 million location updates per second.

30 M trips a day is 350 trips a second average, a few thousand at a global peak; matching is rare compared with location writes, which is the key observation.

Location history: 1.25 M/s × 30 B × 86,400 s = 3.2 TB a day, 100 TB for 30 days; in cold storage, not the live index.

The live index per city: 100,000 drivers × 100 B = 10 MB, trivially in memory; the planet's live index is 500 MB.

2. Core entities

  • Driver: driver_id, vehicle, status (offline, available, on trip), current cell, last location, last update.
  • Rider: rider_id, payment method, default location.
  • Trip: trip_id, rider_id, driver_id, pickup, dropoff, state, fare estimate, final fare, timestamps, version.
  • Location sample: driver_id, lat, lon, heading, timestamp (streamed and archived).
  • Offer: trip_id, driver_id, expires_at, response.

3. API

  • POST /drivers/{id}/location every 4 s with lat, lon, heading. Called by the driver app over a persistent connection.
  • POST /trips with pickup, dropoff; returns trip_id and a fare estimate. Called by the rider app.
  • WS /trips/{id}/events: the rider's stream of matched, driver location, arrived, started, completed.
  • POST /offers/{id}/accept or decline: the driver's answer within a 15 s window.
  • POST /trips/{id}/state: driver app advances arrived, started, completed; each with the trip version.

4. High-level design

ClientsEdgeServicesDatalocationupdatepublisharchiverequestfind drivernearbyofferRider appDriver appConnection gateway(WebSocket)Location service(per-city in-memory index)Matching serviceTrip serviceLocation streamTrips DB(transactional, by city)Location archive

One trip:

  1. Driver apps keep a persistent connection to the gateway and send a location every 4 s; the location service updates the driver's entry in the city's in-memory geospatial index and publishes the sample to the stream.
  2. A rider requests a trip; the trip service creates the trip in state requested in the city-partitioned trips database and asks the matching service for a driver.
  3. Matching queries the location index for available drivers within a growing radius, ranks them by estimated arrival time, and sends an offer to the best one with a 15 s expiry; on decline or timeout it moves to the next.
  4. On accept, the trip service moves the trip to matched in a transaction that also marks the driver on trip; the rider's stream receives the match and then the driver's location updates every few seconds.
  5. The driver app advances the state through arrived, started and completed; completion computes the fare from the recorded path and charges the rider through the payment service with the trip_id as the idempotency key.

5. Deep dives

How does the location index absorb 1.25 million writes a second and still answer nearby queries?

Writing each sample to a database is 1.25 M writes a second for data that is obsolete 4 s later. The index is in memory, partitioned by city (a driver moves between cities rarely): each city server keeps a map from cell id to the set of driver ids in it and a map from driver id to its latest sample. An update is two hash operations; a nearby query reads a few cells. The stream carries the samples to the archive for history, and the index is rebuilt from the stream if a city server restarts, taking seconds because only the last sample per driver matters. Sharding by city also isolates failures: Mumbai's index being down does not affect Berlin.

How do we make sure a driver is never on two trips?

OptionBehaviourTrade-off
Check status in the index, then assignTwo matchers can both see available and both assignRace; double booking
Lock the driver in the index when offeredAn offer marks the driver pending for 15 sWorks for one city server; must be released on timeout
Transactional assignment in the trips databaseAccept runs a transaction: driver row status must be available, set to on trip, trip to matchedOne database round trip; the truth lives in one place

Use both the pending mark (to stop sending the same driver two offers) and the transactional accept as the final guard; the database row is the source of truth and the index is a hint.

How is the rider's view of the approaching driver kept under 3 s?

The rider's gateway connection subscribes to the matched driver's samples: the location service, on each update for a driver who is on a trip, publishes the sample to a per-trip topic in the pub/sub layer, and the rider's gateway pushes it down the socket. The path is update, publish, push: well under a second. Only drivers on trips generate per-trip publishes, so this adds at most a few hundred thousand messages a second, not millions.

What does the city-level failure story look like?

The requirement that cities are independent drives the partitioning: a city has its own location index servers (replicated as a pair), its own trips database shard and its own matchers. A region outage takes down the cities homed there, so large cities run their index pair across two zones and the trips database replicates synchronously within the region. The driver app tolerates a lost connection by buffering samples and reconnecting; a trip in progress continues because its state is in the database and both apps hold the last known state.

How is the rider charged exactly once when the payment call times out?

Completion sends a charge request to the payment service with trip_id as the idempotency key; if the request times out and is retried, the payment service recognises the key and returns the original result instead of charging again. The trip's state machine records charged only after the payment service confirms, and a reconciliation job compares trips in completed-but-uncharged state against the payment ledger every few minutes to catch the case where the confirmation itself was lost.

6. What a strong answer sounds like

  • Lead with the asymmetry: millions of location writes a second, hundreds of matches a second; design the index for writes and the trip store for correctness.
  • Quote 1.25 M updates a second, 10 MB per city index, 3.2 TB a day of history going to cold storage.
  • Explain the two-layer guard against double booking and why the database, not the index, is the truth.
  • Expect follow-ups on ETA computation (routing service), on surge zones computed from supply and demand per cell, and on what happens when a driver's phone dies mid-trip.
  • A common mistake is to store live locations in the trips database; separate the ephemeral index from the transactional store.

02Where this question was reported