Design Uber / Ride-Hailing

hard

Scale: 10M active drivers; ~100K dispatches/min peak globally Storage: Geo index hot in RAM (cell-sharded); trips in DW for compliance Uber, Lyft, DoorDash

Case StudyGeoRealtime

Ride-hailing matches riders with nearby drivers in real time, tracks the trip state machine through to payment, and handles pricing surge. Uber, Lyft, DiDi, Grab share the design.

Scale10M active drivers; ~100K dispatches/min peak globally

StorageGeo index hot in RAM (cell-sharded); trips in DW for compliance

Key Concepts

1. Geo-indexing makes or breaks the system. Naive WHERE distance(driver, rider) < 5km is hopeless at 10M drivers. Production uses S2 cells (Google, quadtree), H3 (Uber, hexagonal), or geohashes. Earth divided into hierarchical cells; drivers indexed by cell ID. Lookup: fetch drivers in target cell + 6 neighbors. Cell size tuned for 10-100 drivers/cell. Stored in sharded Redis with TTL — drivers re-ping every ~4s.

1. Geo-indexing makes or breaks the system.WHERE distance(driver, rider) < 5km

2. Dispatch: tight latency budget. Rider taps Request → dispatcher has ~5 seconds. Fetch K nearest drivers from geo index → score by ETA (requires routing service, not Euclidean distance) → filter by driver state → send offers. Sequential: offer to #1, wait 5s, then #2 — fair but slow. Parallel: offer to top 5 simultaneously, first accept wins — fast but ghost dispatches. Hybrid: parallel within batches.

2. Dispatch: tight latency budget.

3. Trip state must be durable. States: requested → matched → enroute → started → completed. Trip service uses a strongly consistent store (Spanner, CockroachDB, sharded MySQL with sync replication). Persist state transitions before acking clients. Idempotency keys on every state-changing API (mobile networks drop packets). Driver app crashes mid-trip — reconnect, resume from persisted state.

3. Trip state must be durable.requested → matched → enroute → started → completed

4. Pricing and surge. Stream processor (Flink) on demand events (requests) and supply events (driver heartbeats) per cell, per minute. Compute demand:supply → multiplier (1.0, 1.2, 1.5, 2.0, 3.0). Smooth with moving average or hysteresis to avoid oscillation. Quote locked at request time, persisted with the trip — never recompute from current surge.

4. Pricing and surge.

5. Component map. Mobile gateway (long-poll for drivers, stateless API for riders). Location service + geo-sharded Redis. Dispatcher (in-memory state, DB snapshots). Pricing stream processor. Trip service (strongly consistent). Payments (separate, idempotent). Maps/ETA (Google/Mapbox or in-house OSRM). Notification service. Cross-region: usually region-pinned with handoff at trip start.

5. Component map.

High-level design

Driver: app → gRPC → location service → geo-sharded Redis (cell → driver list) + presence service.
Rider request: app → API gateway → dispatcher → geo index lookup → ETA scoring → offer service → driver app push.
Trip lifecycle: state machine in trip service (strongly consistent store), persisted on every transition.
Pricing: stream processor on demand/supply events → per-cell multipliers → quote service.
Payments: separate service; trip end triggers idempotent charge.
Analytics + Fraud: async pipelines from event stream.

Geo indexing

S2 cells (Google): quadtree-based, hierarchical. Cell IDs are 64-bit; sub-meter precision available.

H3 (Uber, open-source): hexagonal grid, 16 resolution levels. Hex tiles tile uniformly — equal-area neighbors.

Geohash: simple z-order curve over lat/lon; cells aren't equal-area; convenient for prefix queries.

Use case: cell size tuned so 10-100 drivers per cell. Sharded by cell ID; hot cells (downtown) get extra capacity.

Query: fetch drivers in target cell + 6 neighbors (H3 hex tiling) or 8 (S2/geohash square).

Storage: Redis with TTL = ~30s; drivers re-ping every 4s to keep entries fresh.

Dispatch

Candidate set: fetch K nearest drivers (e.g., top 20) from geo index.

Scoring: ETA via routing service (Google Maps, Mapbox, in-house OSRM), driver rating, vehicle type, last-trip-ago.

Offers: top scoring drivers sent push notifications with X-second accept window.

Sequential: offer to #1, wait 5s, then #2, etc. Fair but slow.

Parallel: offer to top 5 simultaneously, first accept wins. Fast but ghost dispatches.

Hybrid: parallel within accept-window batches.

Locking on accept: optimistic — first accept commits, others see 'already accepted'.

Components

Mobile gateway (long-polling or WebSocket for driver, stateless API for rider).
Location service + geo-sharded Redis (per-cell driver lists).
Dispatcher service (in-memory state per active request, persists snapshots).
Pricing/surge stream processor (Flink/Spark Streaming).
Trip service (Spanner / Vitess / sharded MySQL with sync replication).
Payments service (separate, idempotent).
Maps / ETA service (third-party or in-house OSRM/Valhalla).
Notification service (push to driver app).

Trade-offs

Location update rate: dense pings → high write cost; sparse → stale matching. 4s typical.

Dispatch latency target: a few seconds. Sequential is fairer but slower than parallel.

Geo cell size: small = precise, more cells, more memory. Large = fewer cells, blurry matching.

Strong consistency for trip state non-negotiable. Eventual consistency for location fine.

Idempotency keys on mobile-originated requests — networks are flaky.

Cross-region failover: hard for active trips; usually region-pinned with cross-region trip handoff at start.

Surge pricing

Stream of demand events (ride requests) and supply events (driver heartbeats) per cell, per minute.

Compute demand:supply ratio per cell; map to multiplier (1.0, 1.2, 1.5, 2.0, 3.0).

Smoothing: don't oscillate every minute — moving average or hysteresis.

Quote: rider sees multiplier at request time, locked for the trip duration.

Display: 'fares are 1.5x normal' in app; transparency reduces complaints.