◐ system-design/design-uber.md

35. Design Uber / Ride Hailing

Tests: real-time location, geo-indexing (S2 / H3), matching, dispatch, payments, surge pricing, websockets at scale.

~4 min read·updated 5/29/2026

35. Design Uber / Ride Hailing

Tests: real-time location, geo-indexing (S2 / H3), matching, dispatch, payments, surge pricing, websockets at scale.

35.1 Requirements

Functional

  • Driver app: broadcast location.
  • Rider app: request a ride; get matched with a driver.
  • Real-time tracking during the ride.
  • Pricing (surge in high-demand areas).
  • Payment after trip.
  • Trip history.

Non-functional

  • Real-time location updates (~5 sec).
  • Low-latency matching (P95 < 5 sec from request to driver assignment).
  • High availability (lost rides cost money).
  • Geographically distributed (many cities, many regions).
  • Scale: 100M+ users, 5M+ active drivers, millions of trips/day, tens of thousands of QPS for location updates.

35.2 Estimates

  • 5M active drivers × 1 location/4 sec = ~1.25M location updates/sec peak. Huge.
  • Trips: ~10M/day = ~120/sec average; peak 1K/sec.
  • Storage of location: ephemeral (no need for full history at scale; sample for analytics).

35.3 High-level architecture

[ Driver app ]──ws──→[ Location ingest ]──→[ Geo-index (per region) ]
[ Rider app ]──→[ Trip svc ]──→[ Match svc ]←─[ Geo-index ]
                       │
                  [ Trip DB ]
                       │
                  [ Pricing svc ]──→[ Surge model ]
                  [ Payments svc ]
                  [ Notification svc ]──→[ Driver app + Rider app ws ]

35.4 Location updates

Drivers stream location every ~4 sec. Aggregated:

  • WebSocket to nearest gateway region.
  • In-memory cache: driver_id → (lat, lon, ts, status).
  • Persisted (briefly) for matching; not kept long term.

Volume: 1M+ updates/sec → distribute across many ingest servers, partitioned by driver_id.

35.5 Geo indexing: the central problem

To find "nearest driver to a rider," you need a spatial index optimized for "find drivers within R meters."

Approaches

R-tree (in PostGIS): bounding-box hierarchies. Works great in a single DB; doesn't shard well.

Geohash: encode lat/lon into a string. Nearby points share prefix. Range scan covers nearby cells. Issues at cell boundaries.

Google S2: hierarchical decomposition of the sphere into cells. Each cell has a 64-bit ID. Used in Google Maps, Foursquare.

Uber H3: hexagonal hierarchical index. Hexagons have uniform distance to neighbors (no diagonal vs straight problem). Used in Uber's Marketplace.

Why hexagons (H3)

  • Each hex has 6 equidistant neighbors (squares have 8 with diagonal further).
  • Cell sizes uniform.
  • "k-ring" query: get all hexes within k steps — natural for "find drivers in 1km radius."

Architecture

  • Each city/region has its own geo-index instance.
  • Drivers in a city register their hex cells.
  • Match request: get rider's hex; query nearby hexes; return drivers.

In-memory KV store (Redis with geo commands, or custom built on H3).

35.6 Trip request → match flow

1. Rider app: POST /trips/request {pickup, destination}
2. Trip svc: create trip in PENDING state; emit MatchRequested event
3. Match svc: 
   - Convert pickup to H3 cell
   - Query nearby drivers (geo-index)
   - Filter: status=AVAILABLE, vehicle_type matches, in service area
   - Score: distance, ETA, driver rating, etc.
   - Top N candidates
4. For each (in order):
   - Send offer to driver (WebSocket push) with timeout (10-30 sec)
   - On accept: assign driver to trip; notify rider
   - On reject/timeout: try next candidate
5. If no driver matches in T seconds: expand radius, raise surge, try again
6. If still no match: notify rider "no driver available"

Match service is stateful per region; sharded by city.

35.7 Live tracking

Once matched:

  • Driver app sends location to Trip svc.
  • Trip svc broadcasts to Rider app via WebSocket.
  • ETA updated by routing service (computes based on traffic).

35.8 Routing & ETA

Map data + real-time traffic.

  • OSRM / Valhalla (open source).
  • Google Maps / Mapbox APIs.
  • ML-based ETA with historical patterns.

For scale: precomputed graph (highway hierarchy) + contraction hierarchies for fast routing queries.

35.9 Pricing & surge

Base price + per-mile + per-min + service fee.

Surge multiplier:

  • Per region (small geofences, e.g., H3 cells).
  • Continuously updated based on supply/demand.
  • Stream processor (Flink): consumes ride requests + completed matches; updates per-cell surge factor.

When rider requests during surge: app shows multiplier upfront for confirmation.

35.10 Payments

After trip ends:

  • Compute fare (actual time + distance + surge applied at request time).
  • Charge rider's saved payment method (tokenized; via Stripe / Adyen / Braintree).
  • Record transaction.
  • Pay driver (delayed payout, batched).

Payment service: own DB; idempotency keys per trip; webhooks from PSP for status.

35.11 Notifications

  • Push (APNS / FCM) for "driver is here."
  • WebSocket for live updates within app.
  • SMS fallback if app not active.

35.12 Trip storage

Trips persist long-term:

  • trips: trip_id, rider_id, driver_id, pickup, dropoff, fare, status, timestamps.
  • Sharded by trip_id or by city.
  • Postgres or distributed SQL (Spanner-class for cross-shard analytics).

35.13 Multi-region / multi-city

Each city is largely independent. Architecture per city:

  • Local Match svc.
  • Local geo-index.
  • Local payment processing (regional).
  • Shared user / driver identity.

Failover within a region (multi-AZ); cross-region failover only for catastrophic events.

35.14 Cell-based architecture

Uber uses cell-based architecture (similar to AWS): each city is a cell with its own stack. Failures contained. Promotes a new city = spin up a cell.

35.15 Failure modes

  • Match svc down for a city: rides fail; manual fallback (call dispatcher).
  • Geo-index lag: drivers shown as available who aren't, or vice versa.
  • Payment failure: charge later (debt collection workflow), retry, fall back to cash if allowed.
  • WebSocket gateway crash: reconnect to another; map of (driver_id → gateway) regenerates.

35.16 Scaling chokepoints

  • WebSocket gateway: tens of millions of long-lived connections. Needs horizontal scale.
  • Location ingest: partitioning by driver_id; each partition handles a fraction.
  • Match svc: per-city sharding; biggest cities get dedicated clusters.
  • Counter / surge updates: stream processor must keep up.

35.17 ML in the loop

  • ETA prediction.
  • Ranking driver candidates (probability of accept, completion).
  • Surge forecasting.
  • Fraud detection (collusion between driver and rider).

Feature store (online + offline) provides features at request time.

35.18 Sketch for interview

[Driver app]──ws──→[Loc ingest]──→[Geo-index (H3)]
[Rider app]──→[Trip svc]──→[Match svc]──→[Geo-index]
                              ↓
                        candidate offers via ws to drivers
                              ↓
                       chosen driver → trip ACTIVE
[Trip svc]──→[Routing/ETA svc]
[Trip svc]──→[Pricing svc]──→[Surge model from Flink]
[Trip svc]──→[Payments svc]──→[PSP]
[Notif svc]──→[APNS/FCM, ws]
[Trip DB] sharded by trip_id; per-city analytics

35.19 What an interviewer wants

  • Geo-index with H3 / S2 / geohash and rationale (hex preferred).
  • WebSocket for real-time bidirectional driver/rider updates.
  • City-based partitioning.
  • Match algorithm: nearby + filter + score + offer-with-timeout.
  • Idempotent payments with tokenization.
  • Stream-driven surge.

Key takeaways

  • Geo-index is the central data structure (H3 / S2). Per-city sharding.
  • Real-time pipeline: drivers stream location → ingest → in-memory index → match.
  • Match: nearby candidates + offer-with-timeout + retry / radius expansion.
  • Surge: stream processing in real-time per cell.
  • Cell-based architecture per city limits blast radius.
  • WebSocket scale: millions of concurrent connections; partitioned gateways.

// 2 views

●main
UTF-8·typescript