Design a Ride-Sharing Service (Uber)

Clarifying questions I'd ask first

• Service types — just rides or also pool, deliveries, scheduled?
• Driver supply model — always-on or app-toggled?
• Pricing — surge, dynamic, fixed?
• Multi-stop trips in scope?
• Driver acceptance — auto-accept, manual, sequenced offers?

Assumptions for this design

200 cities globally, 20M active drivers, 5M concurrent online at peak, 5M concurrent riders looking. Drivers update location every 4s idle, 1s on trip. Sub-3-second match latency p99. Single-stop rides for v1. WebSocket for both apps. Pricing, routing, payments, fraud as independent services.

Quick capacity check

• Location updates: ~1.5M/sec (5M drivers, 80% idle at 1/4Hz, 20% on-trip at 1Hz)
• Ride requests: ~28K/sec at peak
• Match decisions: ~28K/sec, each evaluating 10-20 candidates
• WebSocket frames: ~50M/sec across 10M connections
• Solution: regional sharding — single city's matching domain is independent

Geospatial indexing — H3 over geohash

• Need "available drivers within 2 km of pickup" in milliseconds with 5M drivers updating every few seconds
• Geohash works but cells distort near poles, prefix boundaries cause discontinuity
• H3 (Uber's open source): hexagonal cells, consistent area at a given resolution, exactly 6 neighbors, built-in kRing for nearby cells
• Resolution 8 cells are ~0.74 km² — perfect for city-scale matching
• Stored in Redis as SET per cell; HASH per driver with location + status; 20s TTL evicts stale drivers
• Update on location: if cell changed, remove from old SET, add to new
• Query on match: kRing(cell, 2) returns ~19 cells; fetch drivers, filter by status and vehicle type

Matching — batch bipartite optimization

• Naive closest-driver-wins is wrong: closest may be heading wrong way, low acceptance, sub-optimal globally across concurrent requests
• Buffer requests for 2 seconds; run Hungarian algorithm or weighted matching across the batch
• Score (rider, driver) pairs by ETA + driver acceptance probability + completion rate + utilization + vehicle type + predicted profitability
• 2s batch window is the sweet spot — shorter is local-only, longer feels laggy
• Selected driver gets 15-second OFFER frame; if declined or expired, next candidate; after N declines, cancel with no_driver_found

High-level shape

• Driver app streams location → WebSocket LB (sticky by driver_id) → Location Service → Redis H3 index update
• Rider POST /trips → Trip API → (parallel) Pricing for fare, Routing for ETA, Fraud for risk → Matcher → Redis geo lookup → bipartite optimization → OFFER frames via WebSocket
• Trip Service writes state transitions to Cassandra and emits events to Kafka; Pricing finalizes fare on completion; Payments charges async; Notifications push receipt
• WebSocket fan-out: presence in Redis (user_id → instance_id, 90s TTL); deliveries routed via Kafka topic per instance

Trip state machine

• REQUESTED → MATCHED → ACCEPTED → DRIVER_ARRIVING → ARRIVED → IN_PROGRESS → COMPLETED → PAID; CANCELLED reachable from most
• Event-sourced in Cassandra — every transition appended to trip_events
• Optimistic concurrency on version column — rider cancel and driver "trip started" can race; only one wins
• Cancellation logic layered: free before MATCHED, free with grace after, fee after grace, no-show fee on timeout

Surge pricing — market-clearing

• Per-zone multiplier balances supply against demand
• Computed every ~30s from (requests/min) / (available drivers)
• High multiplier draws drivers in (visible heat map) and reduces demand — reaches equilibrium
• Stored in Redis surge:zone:{id}; Trip API reads current multiplier; rider's fare locked at request time
• Sanity cap (5x max) protects against runaway pricing

LLD — clean abstractions

• GeospatialIndex interface (RedisH3Index impl); could swap to PostGIS for smaller deployment
• MatchOptimizer extracted — the bipartite algorithm tunable independently
• OfferDispatcher returns futures; declined offers route to next candidate non-blocking
• TripStateMachine powers both service and API ("can this be cancelled?")
• WebSocketHub abstracts the regional hub topology
• Trip Service uses optimistic concurrency on version for race-free transitions

Driver battery and bandwidth

• Idle: 4-second updates
• Heading to pickup: 2-second updates
• On trip: 1-second updates (rider sees live)
• Speed=0 (parked): 10-second updates
• App backgrounded: 30 seconds
• Compact binary frames (CBOR/protobuf), per-message deflate WebSocket compression

Failure handling

• Location Service crash: clients reconnect; driver in "location stale" briefly; matcher excludes
• Redis cluster failure: matching halts in region; failover ~30s; drivers re-broadcast on reconnect; PostgreSQL cube fallback for extended outage
• Matcher down: requests queued in Kafka; degraded latency on burst recovery
• Driver declines: matcher offers next candidate; after N declines, cancel
• Payment failure: trip in PAYMENT_FAILED; retry job; driver paid from settlement, not held hostage by rider payment
• Offline driver: 90s heartbeat miss → evicted from index; active trip stays valid; reconnect resumes

Production extras

• Driver identity verification (background + biometric)
• Anti-fraud risk scoring on every request
• Emergency button in app, trip share with trusted contacts
• Phone number masking via carrier-level proxy
• Rate limits per device/account
• Audit log for dispute resolution and regulatory compliance
• Distributed tracing per trip request through full pipeline

At 10× scale

• Per-cell matching with dedicated matchers
• Edge-local matching with no cross-region coordination
• ML demand prediction for pre-positioned drivers
• Native pool/share-ride routing as a separate sub-system

Recommendation

H3 hexagonal geospatial index in Redis sharded per region, batch bipartite matching with 2-second window scoring ETA plus driver behavior factors, event-sourced trip state machine in Cassandra with optimistic concurrency, WebSocket bidirectional channel with sticky-LB and presence-in-Redis, adaptive location update frequency for battery, and surge pricing as a market-clearing mechanism per zone — the same shape Uber, Lyft, and Grab run for ride-sharing today.