Design Uber

• 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.

• 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.

• 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.

• 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.

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.
   1. Driver app sends a location ping over its WebSocket every 4 s while online.
   2. Gateway forwards to the Location service for the driver's city.
   3. Location service validates and smooths the fix, then updates the geo index.
   4. Last-known position and status are written to the live state store; the ping is published to the stream.
   5. Riders viewing the area receive a batched update of nearby car positions.
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.
   1. Rider enters a destination; the app asks for an upfront fare and pickup ETA.
   2. Pricing gets distance and duration from routing, applies the cell's surge multiplier, and stores the quote.
   3. Rider confirms; Trip service creates the trip in state "requested" and asks Dispatch to match.
   4. Dispatch queries the geo index for available drivers near the pickup.
   5. Dispatch ranks candidates by ETA to the pickup and other factors.
   6. Dispatch locks the best driver and pushes the offer with a countdown.
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.
   1. Driver taps accept within the window.
   2. Trip service assigns atomically: trip requested → matched with this driver, driver lock → on_trip.
   3. If the driver declines or the timer expires, Dispatch releases the lock and offers to the next candidate.
   4. Both apps receive the match; the rider sees the real driver and car approaching.
   5. Driver marks arrived, started, and completed; each is a guarded state transition and an event, and the trace is archived.
   6. Trip service charges the rider through the payment system with a trip-derived idempotency key and releases the driver.
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.
   1. Trip requests and driver pings flow through the event stream keyed by cell.
   2. Pricing service aggregates demand and supply per cell over a sliding window.
   3. Multiplier is computed from the demand-to-supply ratio and smoothed.
   4. Multipliers are written to the live store and pushed to driver apps as a heat map.
   5. A quote freezes the multiplier at quote time; confirmation honours it within the expiry.
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.
   1. A driver with an outstanding offer loses connectivity.
   2. A dispatcher instance crashes while holding a driver lock and a requested trip.
   3. The routing service is slow or down.
   4. The geo index shard for a city restarts.
   5. A whole region is degraded.

Ask: 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?

Good answers name: In-memory cell grid (S2 / H3) per city, sets of drivers per cell, Redis GEO (geohash sorted set), PostGIS / database spatial index, Quadtree with rebalancing.

Our pick: A Location service per city holding an in-memory index: cell → set of driver ids, and driver → (cell, position, status, ts). Cells at roughly 1 km (H3 resolution 8 or S2 level 13). Pings update both maps; a nearby query reads the pickup cell plus one ring, expanding to two rings if fewer than 10 available candidates. Last-known positions are mirrored to Redis with a TTL, which is both the rebuild source after a restart and the fallback query path (GEOSEARCH) during it. Very dense cells can be subdivided by using a finer level for the query in those areas.

1. A driver sits exactly on a cell boundary and jitters between two cells every ping. Cost?
   Two set operations per ping either way, so no extra cost to the index. The rider-facing map might flicker if positions are grouped by cell; smooth positions client side and debounce cell changes for display only, never for the index.
2. How do you handle a stadium letting out: 5 000 requests in one cell in two minutes?
   The index is fine: reads scale with candidates, not requests. Dispatch is the pressure point: thousands of concurrent matchings competing for the same few hundred drivers. Batch matching helps here: collect requests in the hot cell for a second and solve an assignment problem (requests × drivers by ETA) rather than first come first served. Surge does the rest by pulling in supply.
3. Why per city and not one global index?
   Isolation and locality. A city's drivers never match riders in another city, so there is no cross-city query. Per-city shards mean a bug or overload in one city cannot affect another, deployments can be regional for latency and data residency, and each shard fits comfortably in memory. Cities that border each other (a metro area) are treated as one shard.
4. What does the index return for a driver whose last ping was 40 seconds ago?
   Nothing: the query filters by freshness (say 15 s) because a stale position means an unreliable ETA and possibly an offline driver. The Redis TTL on driver status backs this up: without pings, the driver falls out of "available" automatically.

Ask: Offer each request to the closest driver immediately, or wait a moment and solve the assignment across many requests and drivers?

Good answers name: Short-window batch assignment with ETA as cost, greedy fallback, Greedy nearest available driver, Broadcast offers to many drivers, first to accept wins.

Our pick: Dispatch groups incoming requests by area and runs a matching tick every 1–2 seconds in busy areas (immediately when there is no contention). Each tick builds a cost matrix of ETA from candidate drivers to requests, adjusted for fairness and acceptance history, and solves the assignment (Hungarian for small matrices, a greedy approximation for large ones). The result is a proposed driver per request; offers go out sequentially with a lock and a 15 s acceptance window; declines feed back into the next tick. The trip row's guarded update is the final arbiter. Explain that "wait a second to match better" is the same principle as the matchmaking queue for games.

1. A driver declines three offers in a row. What happens to them and to the riders?
   Each rider is re-offered to the next candidate within seconds; they never see the decline. The driver's acceptance rate drops, which lowers their ranking for a while and, on some platforms, temporarily pauses offers. Persistent decliners are a supply quality problem handled outside dispatch.
2. How do you decide the batch window length?
   Measure pickup time and match time as a function of window length per area type. Dense areas gain from 1–3 s; sparse areas gain nothing and should match instantly. Make it adaptive: window = f(requests per second in the area), capped at a few seconds so the rider's spinner never feels long.
3. Two dispatchers in the same city: how do they avoid offering the same driver?
   The per-driver lock in Redis (SET NX with TTL). Whoever sets it owns the driver for the offer window. Partition dispatch by area so this rarely happens in the first place; the lock handles the boundary cases.
4. What is the invariant and where exactly is it enforced?
   One driver has at most one active trip; one trip has at most one driver. Enforced at the durable layer by the guarded UPDATE on the trip row and a unique partial index on (driver_id) WHERE status IN (matched, in_progress). The Redis lock only reduces wasted offers; correctness does not depend on it.

Ask: Hundreds of thousands of trips in progress, millions watching the map. How do positions and status changes reach the right phones?

Good answers name: WebSocket per user; trip events pushed reliably; map positions fanned out per cell, batched and lossy, Polling every few seconds, Push everything through one topic per user.

Our pick: Persistent WebSocket per active rider and driver with a registry of user → gateway server. Trip status changes: Trip service emits an event; a consumer looks up both participants and pushes; missed pushes are recovered by the client fetching trip state on reconnect. Assigned-driver position: the Location service forwards that driver's pings directly to the rider's socket at the fast interval. Map cars: clients subscribe to the cells in their viewport; a fan-out consumer aggregates pings per cell every 3–4 s and pushes one message per subscribed rider with lightly obfuscated positions and rotating tokens. Everything on the map path is at-most-once by design.

1. A rider's phone goes through a tunnel for 30 s during a trip. What do they see after?
   On reconnect the client fetches GET /trips/{id} for the authoritative state and the driver's current position, then resumes the stream. Anything pushed during the gap is irrelevant because the current state supersedes it. The app shows "reconnecting" rather than stale movement.
2. Why obfuscate car positions on the browse map?
   Precise, continuous positions of identifiable drivers let anyone track a specific person. Rounding positions, rotating anonymous tokens per session, and showing only a few cars limits that. After matching, the rider legitimately needs the exact position of one driver, and gets it.
3. How many gateway servers and how do you size them?
   Roughly 7 M concurrent connections at peak (drivers plus active and browsing riders) at 30–50 k per server: a few hundred servers per large region. Drivers are the constant load; riders spike with demand. Autoscale on connection count, and drain connections gracefully on deploys as in the chat design.

Ask: Pickup ETA and fare are shown before the rider commits. How are they computed fast and honoured fairly?

Good answers name: Routing-based quote stored with inputs, per-cell surge frozen at quote time, adjustments only for defined deviations, Metered fare (distance and time at completion), Precomputed zone-to-zone price table.

Our pick: Quote path: one routing call for distance and duration, a Redis read for the surge multiplier of the pickup cell, and a precomputed pickup ETA per cell (refreshed every few seconds from the nearest available drivers) so the quote does not wait on candidate ranking. Store quote id, inputs, multiplier, fare, and a 5-minute expiry. Trip creation references the quote and inherits its fare. At completion, compare the driven route to the quoted one; adjust only under defined rules (rider-requested stops, material detours, waiting time, tolls) and itemise them on the receipt. Fallback when routing is unavailable: haversine distance × a per-city road factor and historical speed profile, with the quote marked approximate.

1. The quoted fare is honoured but the driver is paid on distance and time. Who eats the difference?
   The platform, by design. The quote is an estimate that is right on average; per-trip errors net out across millions of trips. The risk is systematic bias, so the ETA-versus-actual and fare-versus-metered error distributions are tracked per city and fed back into the estimation models.
2. How is the pickup ETA per cell precomputed?
   A small job per city runs every few seconds: for each cell with recent demand, take the nearest few available drivers from the geo index and their routing ETA to the cell centre, keep the best. Cache in Redis with a short TTL. Cells with no drivers show "no cars nearby" rather than a guess.
3. Surge changes between quote and confirm. Which applies?
   The quote's, within its expiry. That is the entire point of freezing the multiplier in the quote: the rider decides on a known price. After expiry, a fresh quote with the current multiplier, shown clearly as changed.

Ask: Which parts of this system need strong consistency, and how do you keep them small?

Good answers name: Relational trip DB sharded by city, guarded transitions, outbox events, Redis for advisory locks and live state, Everything in Redis for speed, Event-sourced trips (the event log is the truth).

Our pick: A trips table per city shard with a state column, a driver_id, and a partial unique index on driver_id for active states; every transition is an UPDATE with a WHERE on the expected current state; the outbox pattern publishes trip events after commit. Redis holds the driver lock (advisory, TTL), live statuses, and last positions. A sweeper resolves trips stuck in transitional states by consulting the source that knows (dispatcher heartbeats, driver pings). The payment charge uses the trip id as its idempotency key so a retried completion cannot double charge. Name the boundary explicitly in the interview: strong consistency for trips and assignment, eventual for everything else.

1. A rider cancels at the same instant the driver accepts. Outcome?
   Both issue guarded UPDATEs: cancel requires status=requested or matched; accept requires status=requested. The database serialises them; one succeeds and the other sees zero rows and gets a 409. Whichever won is the truth, and the events tell both apps. Cancellation fees are decided by which happened first per the recorded timestamps.
2. Why shard by city rather than by trip id?
   Locality and isolation: dispatch, surge, and analytics all operate per city, so co-locating a city's trips makes those queries local and lets you deploy a city's stack in its region. Trip id sharding spreads one city across all shards and makes "active trips in this city" a scatter-gather. The cost is uneven shard sizes, handled by splitting the largest metros.
3. How would you run a migration of the trips table with 350 k trips in flight?
   Additive schema changes only, applied online; dual-write for a new column during transition; never lock the table. For a resharding, move whole cities during their quiet hours with a brief write pause per city, since the shard key is the city.