Uber

Interview scope and guarantees

Request a ride, find nearby eligible drivers, assign one driver, track trip state, and complete payment. Matching needs one current assignment per trip and a defined driver capacity. ETA is an estimate; a location point is not an availability guarantee.

Capacity worksheet

Assume 1 million online drivers update every 4 seconds: 250,000 updates/s. At 150 bytes/update that is 37.5 MB/s raw. With 1,000 ride requests/s, separate the high-volume location projection from the smaller but contention-sensitive assignment store.

Concrete API contract

POST /trips {pickup,destination,product} -> {tripId,state}
POST /drivers/{id}/locations {sequence,lat,lon}
POST /trip-offers/{id}/accept {generation}
POST /trips/{id}/transitions {expectedVersion,action}

Data model and access paths

driver_state(driver_id PK,status,current_trip,version)
trips(trip_id PK,rider_id,driver_id,state,version)
offers(offer_id PK,trip_id,driver_id,generation,expires_at)
locations(driver_id PK,cell,position,sequence,observed_at)

Evolve a solution and explain each change

Figure — Three architecture decisions for Uber, including the pressure each introduces.

Step 1: Find candidates

Index recent driver positions and filter eligibility. Nearby does not mean available or assigned.

Step 2: Offer a ride

Record a ride and issue expiring offers to a bounded candidate set. Two riders can concurrently target the same driver.

Step 3: Commit assignment

Conditionally claim driver and ride; use fencing for reassignment and stale location. A location projection must not grant exclusive ownership.

Responsibility overview

Figure — Connected responsibilities for Uber. Trace the authoritative and derived paths separately.

Worked end-to-end scenario

Riders R1 and R2 both see driver D within two kilometres. Each dispatcher sends an offer. D accepts R1; the assignment transaction verifies both that R1 is unassigned and D is available, then commits one assignment. R2’s attempt reloads and chooses another candidate. A late acceptance from an expired offer includes its old offer ID and cannot override a newer match. During the ride, location updates carry sequence or freshness metadata; a delayed packet must not move D back to yesterday’s street. ETA estimation can be approximate while assignment ownership remains strict.

Why these access paths matter

Use coarse spatial cells for candidate discovery, exact distance and freshness for refinement, and driver ID for authoritative availability. Store rides by rider and state; index dispatchable rides by zone. Cell boundaries require neighboring-cell queries. Assignment across records needs a clear transaction or coordination boundary, not two unrelated cache writes.

Build the baseline first

1. Rider → trip intent → nearby driver candidates.
2. Dispatcher → offer → atomic assignment.
3. Trip transitions → durable events → rider updates.

Evolve the design under load

1. Cell-indexed locations → bounded geo search.
2. City dispatch partitions → candidate ranking.
3. Regional gateways → live location updates.

Defend the hardest decision

Search neighboring spatial cells and calculate actual distance or ETA for candidates. Dense city cells need subdivision or bounded results. Atomically consume a valid offer and reserve driver capacity. A transaction spanning trip and driver state is straightforward when colocated; otherwise use an explicit reservation protocol with expiry and reconciliation rather than pretending two independent writes are atomic.

Failure and recovery analysis

Two dispatchers offer the same driver different trips. The driver’s authoritative compare-and-set chooses one winner; the losing trip returns to matching. A late acceptance with an old generation is rejected. A stale driver point must age out of eligibility even if it remains in the geospatial index. Losing GPS does not automatically cancel an in-progress trip.

Security and privacy boundary

Restrict precise trip location to participants and authorized operations; redact historical paths from ordinary service logs.

Interview follow-ups with reasoning

Question: How does surge pricing interact with acceptance?

Question: How do you rebalance city partitions?

Question: What if the payment provider times out?

Operate and verify the design

Match time, stale-location rate, rejected stale offers and assignment conflicts.

Deliver an expired offer acceptance after a different trip has reserved the same driver.

A second scenario to test transfer

Two riders receive the same driver as a nearby candidate. Two dispatchers send offers. The driver’s first valid accepted assignment commits at the owner; the competing transition fails and searches another candidate. A stale location index may continue listing the driver briefly, but the authoritative assignment check prevents double booking. This lets discovery be fast without making it the correctness boundary.

Can an available flag in the location cache authorize assigning a driver?

Compare alternatives

A design-changing exercise

The location cache says available but the driver row says assigned. Which wins?

Design workshop: reserve both driver and ride

Core scope is rider request, nearby matching, offer acceptance, trip progression and payment. Pooling and complex surge optimization are extensions. Choose five-second location freshness, offer expiry at ten seconds and no two active rides for a driver. Discovery latency may degrade; assignment safety must remain intact.

Choose a city-owned transactional assignment authority for the baseline. rides and drivers are co-located so acceptance locks driver and ride in stable order, verifies offer ID/deadline/version and atomically marks both assigned. This is a deliberate partitioning decision; the design does not claim arbitrary two-shard updates are atomic.

BEGIN;
SELECT * FROM drivers WHERE id=:driver FOR UPDATE;
SELECT * FROM rides WHERE id=:ride FOR UPDATE;
-- Validate owner epoch, offer identity, expiry, driver availability,
-- and ride awaiting_assignment. Then update both rows and outbox.
COMMIT;

A cross-city handoff first closes or transfers authority under a durable epoch; the driver cannot be available under both cities. A coordinator extension reserves driver with a fenced reservation, then attaches the ride and confirms. Recovery queries both reservation states and either finishes or releases the same identity. It must never issue an unrelated fresh reservation while the old one is unknown.

Figure — Two offers compete for one driver.

Location ingestion stores driver ID, sequence, observedAt, receivedAt and coarse cell. Reject older sequence updates, expire stale eligibility and move the driver between cells with versioned projection updates. At 100,000 drivers updating every five seconds, city ingestion is 20,000 updates/s; 100-byte raw records are 2 MB/s before indexing/replication. Keep only recent location in memory and a bounded diagnostic history under privacy policy.

Candidate search expands intersecting cells, filters vehicle/status/freshness and estimates road travel time for a bounded shortlist. Straight-line distance selects candidates cheaply but does not capture bridges or traffic. A simple score can combine pickup ETA with availability/wait fairness; show each term and do not claim globally optimal routing. Reject a candidate at acceptance if its authority state changed since discovery.

Figure — Ride state and fare contracts.

POST /quotes returns quoteId, estimateMinor, currency, expiresAt; POST /rides includes quoteId and stable requestKey. GET /rides/id returns trip version and driver location age. Store payment_attempts(trip_id,operation_key,state) and exact fare breakdown. Completion is a trip-authority transition; payment failure is separately recoverable. Driver location outage need not erase an active trip or authorize another one.

Exercise: A driver's location cache says available after assignment committed. Can a second dispatcher claim it?

Technical references

PostgreSQL transaction isolation and concurrent updates.