Design Uber

Match riders with nearby drivers in seconds, track trips live, and price them, for millions of concurrent users worldwide.

Difficulty: hard. Patterns: geospatial, matching, streaming, marketplace. Reported at Uber, Lyft, DoorDash, Grab, Amazon.

Study shows every answer; Practice hides them until you have produced your own.

Functional requirements

• Rider requests a trip from pickup to destination. Gets an upfront price and an ETA for the pickup before confirming.
• Match the request with a nearby available driver. Driver can accept or decline; on decline or timeout, offer to the next candidate.
• Live location of drivers. Riders see nearby cars on the map before requesting and their assigned car approaching after.
• Trip lifecycle. Requested → matched → driver en route → in progress → completed → paid. Both sides see status changes in real time.
• Pricing and surge. Upfront fare from distance, time, and a demand multiplier per area. The quoted fare is honoured if the route is followed.
• Payments and receipts. Charge the rider at trip end; pay out drivers on a schedule. Assume the payment system from the payments question.
• Out of scope. Ratings, support, fraud detection, pooled rides, and the driver onboarding and document verification process.

Non-functional requirements

• Scale (20 M trips/day · 5 M concurrent drivers). Drivers are the write-heavy population: every online driver reports location every few seconds.
• Match time (p95 < 10 s to a confirmed driver). Includes the driver's acceptance window. Slow matching is the most visible failure.
• Location freshness (< 5 s stale on the rider's map). Drives the ping interval and the push path to riders.
• Consistency (one driver, one trip). A driver is never assigned two trips at once and a request is never matched twice. Hard invariant.
• Availability (99.99 % for request and match). Degrade pricing and ETA before degrading matching; a trip with an approximate ETA beats no trip.
• Latency for ETA and price (p95 < 1 s). Shown before the rider confirms; uses the routing engine from the maps question.
• Regional isolation. A city's matching must not be affected by load or failure in another region. Data locality for privacy.

Back-of-envelope estimates

• Driver location pings per second: ~1.25 M. 5 M concurrent drivers × one ping every 4 s = 1.25 M pings/s. The dominant write stream; each ping ~100 B → ~125 MB/s ingest.
• Trip requests per second: ~230 avg · ~1 k peak. 20 M trips/day ÷ 86 400 ≈ 230/s average; evening and event peaks 4–5×. Matching is CPU cheap per request; the hard part is the geospatial lookup under the ping write load.
• Concurrent active trips: ~350 k. 230 trips/s × ~25 min average trip = 230 × 1 500 s ≈ ~350 k trips in progress at once (Little's law). Each has two live participants receiving updates.
• Rider map updates per second: ~2–5 M pushes. Riders browsing see ~10 nearby cars refreshed every 4 s; riders in a trip see one car. With ~2 M riders viewing the map: 2 M × 10 ÷ 4 = 5 M car-position pushes/s. Batch per rider into one message: ~500 k messages/s.
• Geo index size: ~500 MB. 5 M drivers × ~100 B (id, cell, lat, lng, heading, status, ts) = ~500 MB. Fits in memory in one region's index; partition by city or coarse cell for isolation and parallelism.
• Nearby-driver query cost: ~9 cells · ~50 candidates. A pickup query covers the pickup's cell and its 8 neighbours at a cell size of ~1 km (S2 level 13 or H3 res 8). In a dense city that is ~50–200 drivers, then filter by status and ETA. Tens of microseconds in memory.
• Trip event storage: ~40 GB/day. Each trip stores ~20 state events plus a location trace of ~400 points × 20 B ≈ 10 KB. 20 M × (10 KB + 1 KB events) ≈ ~220 GB/day raw; compress traces 5× → ~40–50 GB/day. Hot for a week, then cold storage.

Components

• Rider app: Requests trips, shows nearby cars and the assigned driver approaching, and receives trip status over a persistent connection. Sends its own location during the trip for the trace and for arrival detection.
• Driver app: Reports location every few seconds while online, receives trip offers with a countdown, accepts or declines, and drives the trip states (arrived, started, completed).
• API + WebSocket gateway: REST for requests and state changes; WebSocket per active rider and driver for pushes. Routes to the regional deployment for the user's city. Holds a connection registry (user → server) so services can push.
• Location service (ingest · geo index): Ingests driver pings, validates and smooths them, updates the in-memory geo index (driver → cell) and the last-known position store, and publishes pings to the stream. Answers "available drivers near (lat, lng)".
• Geo index (in-memory · S2/H3 cells): Sharded by city. Maps each cell id to the set of driver ids currently in it, plus a driver → (cell, position, status, ts) map. Updated on every ping; a nearby query reads the pickup cell and its neighbours.
• Trip service (state machine): Owns the trip lifecycle and its invariants. Creates the request, runs the matching flow with the Dispatch service, applies driver responses, records state changes transactionally, and emits trip events.
• Dispatch service (matching): Given a request, gets candidates from the geo index, ranks by ETA (routing service) and other factors, and offers the trip to drivers one at a time or in a small batch with an acceptance timeout. Enforces one-driver-one-trip with a lock per driver.
• Pricing & surge: Computes upfront fares from distance and time estimates, applies the surge multiplier for the pickup cell, and stores a fare quote id honoured at trip end. Surge is recomputed per cell every minute from request and supply counts.
• Routing / ETA (maps question): The routing engine: driver-to-pickup ETAs for ranking candidates, and pickup-to-destination distance and time for pricing. Treated as an external dependency with a strict latency budget and a fallback (haversine × factor).
• Event stream (Kafka · pings + trip events): Two families of topics: driver location pings (keyed by geo cell, huge volume, short retention) and trip events (keyed by trip id, durable). Consumers: surge computation, analytics, the trace archiver, and the rider push fan-out.
• Trip DB (Postgres (sharded by city) / Spanner): Trips, their state history, fare quotes, and assignments. Sharded by city since trips never cross cities. Strong consistency for the assignment row is what backs the one-driver-one-trip guarantee.
• Live state store (Redis · locks · last positions): Driver status and lock (available / offered / on-trip) with TTLs, last-known positions for fast reads, connection registry for pushes, and surge multipliers per cell.
• Trace & analytics store (object storage · warehouse): Compressed trip traces and all events for receipts, disputes, and analytics. Written by stream consumers, never on the request path.
• Payment system: Charges the rider at trip completion against the stored payment method, using an idempotency key derived from the trip id. Driver payouts run on a schedule from completed trips.

User flows

1. Driver location ingest and the geo index. The biggest stream in the system. Every online driver reports every few seconds; the index must reflect it within a second and serve nearby queries at the same time.
2. Rider requests a trip: price, then match. Two phases: an upfront quote the rider can decline, then a request that must find a driver within seconds. The quote id ties them together.
3. Driver accepts (or declines) and the trip proceeds. The assignment is the one place where two writers race: the driver's acceptance and the offer timeout. The trip row's state guard settles it.
4. Surge pricing from live supply and demand. A per-cell multiplier recomputed every minute from request counts and available drivers, smoothed so it does not whipsaw, and locked into quotes.
5. Failures: driver goes offline mid-offer, dispatcher crashes, region degrades. The invariants must survive crashes at every point. Locks with TTLs, guarded state transitions, and a sweeper make the system self-healing.

Deep dives

1. The geo index: finding nearby drivers under 1 M writes per second. How do you index millions of moving points so that "available drivers within 2 km" is a microsecond query while positions change every few seconds?
2. Matching: nearest driver vs optimal assignment. Offer each request to the closest driver immediately, or wait a moment and solve the assignment across many requests and drivers?
3. Real-time updates to riders and drivers. Hundreds of thousands of trips in progress, millions watching the map. How do positions and status changes reach the right phones?
4. ETA and upfront pricing. Pickup ETA and fare are shown before the rider commits. How are they computed fast and honoured fairly?
5. Trip state, invariants, and the database. Which parts of this system need strong consistency, and how do you keep them small?