Uber and Lyft

1. Requirements

Functional

• Rider: fare estimate + ETA, request ride, live driver tracking, cancel, pay, rate.
• Driver: go online/offline, receive trip offers, accept/decline, navigate pickup/dropoff, earnings.
• Matching: assign nearby suitable driver (vehicle type, rating) within seconds.
• Surge pricing when demand ≫ supply; upfront price quote.
• Safety/fraud hooks: trip anomaly detection, SOS (out of scope for deep design).

Non-functional

• Match latency: p99 < 5 s from request to driver accept in normal conditions.
• Location freshness: rider sees driver move with < 10 s staleness.
• Availability: regional failure must not halt rides in other regions; city-level cells fail over.
• Correctness: exactly one driver per trip (no double-dispatch); idempotent rider retries.
• Scale: millions of drivers, tens of millions of trips/day.

Out of scope

• Maps rendering/tiles, turn-by-turn navigation engine internals, payments ledger internals, food-delivery stacking.

2. Capacity Estimation

Derivations:

• Location writes: 1 M / 4 s = 250 k writes/s; at ~100 B/ping ≈ 25 MB/s ingress — fits a sharded in-memory geo store + a Kafka location stream for consumers (ETA, fraud, analytics).
• Matching ops: 20 M/day ≈ 230/s avg; 10× city-peak ⇒ ~2.5 k matches/s global. Each match scans ~50–200 candidate drivers from a handful of cells — ~100 k–500 k candidate reads/s, all in-memory.
• Hot retention: only recent positions matter. 1 M drivers × 100 B × (6 h / 4 s = 5,400 pings) ≈ 540 GB if fully kept — instead keep latest position per driver (~100 MB) + a short rolling trail in the stream; history goes to cold storage via the event log.
• Trip store: 20 M × 5 KB ≈ 100 GB/day; indexed by trip_id, partitioned by city/day.

3. API Design

# Driver location stream (high frequency, lightweight, token-authed)
PUT /v1/drivers/{driver_id}/location
{ "lat": 12.9716, "lng": 77.5946, "ts": 1718…, "speed": 8.2, "heading": 140 }
-> 204   # write to geo index + location stream; no read-back

POST /v1/drivers/{driver_id}/status { "online": true, "vehicle": "sedan" }

# Rider
POST /v1/rides/estimate { pickup, dropoff, vehicle_class }
  -> { upfront_fare, surge_multiplier, eta_pickup_min, eta_trip_min }

POST /v1/rides { pickup, dropoff, vehicle_class, idempotency_key, price_token }
  # price_token binds the accepted upfront fare (prevents surge disputes)
  -> 202 { trip_id, status: REQUESTED }

GET /v1/rides/{trip_id} -> { status, driver{…}, eta, route_polyline }
POST /v1/rides/{trip_id}/cancel { reason } -> { fee }

# Driver app
GET /v1/drivers/{id}/offers  (long-poll / socket) -> { trip_id, pickup, fare, ttl_s: 15 }
POST /v1/rides/{trip_id}/accept { driver_id }     # CAS: only first accept wins
POST /v1/rides/{trip_id}/complete { dropoff, distance_m }

Idempotency: rider retries reuse idempotency_key (no duplicate trips); driver accept is a compare-and-swap on trip state (REQUESTED → MATCHED only if still REQUESTED).

4. Data Model & Storage

5. High-Level Design

Flow: driver pings → location ingestor → geo index + stream; rider request → matcher (cell search → rank → offer) → dispatch offers to drivers → accept CAS → trip service owns FSM → tracking/ETA/surge consume streams; pricing/fraud/payments async.

Regions are deployed per metro cluster with city-partitioned data (see Partitioning); cross-region failover is DNS-level, and in-flight trips are recoverable from the trip store.

6. Deep Dives

A. Geo-indexing: geohash vs quadtree vs S2

• Geohash (e.g. precision 6 ≈ 1.2 × 0.6 km cells): dead simple — position update = compute hash, move driver id between sets; rider search = fetch own + 8 neighbor cells and expand rings until enough candidates. Weakness: boundary problem (two adjacent drivers in different cells) — solved by always searching neighbor cells; and uneven density (downtown cell with 5 k drivers) — solved by cell splitting or precision-7 sub-cells in hotspots.
• Quadtrees: adaptive subdivision fits density naturally (split cells past N drivers), but rebalancing on churn (drivers move constantly) costs more, and distributed quadtrees need careful ownership handoff.
• S2 (used by Google-scale systems): hierarchical cell IDs on the sphere with good locality; great if you need multi-resolution queries (surge at level 12, matching at level 15). Cost: library complexity, harder to eyeball-debug than geohash strings.
• Interview stance: geohash-6/7 + neighbor-ring search is the default answer (simple, shardable: cell → owner node via hash), S2 when asked "how would Google do it", quadtree when asked about adaptive density. Benchmark numbers to quote: ring search over ~9–25 cells touches ~50–200 drivers in < 5 ms in-memory.

B. Matching and dispatch

• Batched matching: accumulate requests for a 2–4 s window per metro, then match the batch. Batching trades ~2 s of latency for dramatically better pairing (fewer criss-crossing pickups) and absorbs micro-bursts.
• Offer protocol: rank candidates (distance, rating, acceptance history, vehicle match), send parallel offers to top 3–5 with a 10–15 s TTL; first accept CAS wins; losers get instant release. Parallel offers cut tail match latency vs sequential dialing; cap parallelism to avoid spamming drivers.
• Why not Hungarian/global optimum: optimal assignment over 10 k open requests × 50 k drivers is computationally infeasible per 2 s window and stale before it finishes. Greedy-by-batch with good ranking is within a few % on pickup time and runs in milliseconds.
• Failure modes: no driver accepts → widen radius + bump surge → re-offer; rider cancels mid-dispatch → revocation events to offered drivers; double-accept prevented by the state CAS (the losing accept gets 409 TRIP_TAKEN).

C. ETA, driver location stream, and surge

• Location stream: pings → Kafka (location-stream) with 4 s cadence; consumers: geo index updater, ETA feature builder, fraud (teleporting driver = spoofed GPS), heatmaps. Driver app downsamples (no ping when stationary) to halve write load.
• ETA: two-tier — (1) cached estimate keyed by (pickup-cell, drop-cell, 5-min bucket) served in < 10 ms for the fare quote; (2) live routing (contraction hierarchies over the road graph) for matched-trip tracking and finalists. Cache hit ratio > 90% on popular corridors.
• Surge: per geohash-5 cell (~5 × 5 km), every 30–60 s: multiplier = f(open_requests / available_drivers, ETA trend), clamped (e.g. ≤ 3×) and smoothed (EWMA) to avoid oscillation. The price_token from estimate binds the quote so post-surge disputes are impossible; drivers see a heatmap, creating the supply feedback loop.

7. Bottlenecks, Trade-offs & Monitoring

Bottlenecks: hotspot cells (airports — pre-split + dedicated matcher shard); location-write fan-in (shard ingestor by cell, batch Redis writes); match latency during demand spikes (auto-widen radius is cheaper than waiting); thundering requotes (cache estimates 30–60 s per rider).

Monitoring: match success rate, time-to-accept p50/p99, pickup ETA accuracy (|predicted − actual|), surge multiplier distribution, driver ping lag, unmatched-request rate by cell, double-dispatch count (must be 0).

Interview one-liners

• Q: How do you find nearby drivers without scanning all? A: Geohash cell index; search own + neighbor rings, expand until K candidates.
• Q: Optimal matching? A: Too slow at city scale — batched greedy every 2–4 s is within a few % and finishes in ms.
• Q: Two drivers accept at once? A: State CAS REQUESTED → MATCHED; loser gets 409.
• Q: Surge math in one line? A: Per-cell demand/supply ratio, EWMA-smoothed, recomputed every ~30–60 s, clamped.

Related

• Geospatial indexing — geohash, quadtrees, S2
• Message queues — dispatch offers and trip events
• Stream Processing — location stream consumers
• cache-aside — ETA/estimate caching
• Partitioning — city-partitioned trips, cell-sharded ingestors
• Linearizability — why the accept CAS is the one linearizable op