Chapter 50: Design Uber/Lyft
Real-time ride-sharing platform with location tracking, matching, and dynamic pricing
1. Requirements
Functional Requirements
| Component | Requirement | Priority |
|---|---|---|
| Rider Flow | Request ride → see nearby drivers → get matched → track location → complete trip → pay | P0 |
| Driver Flow | Go online → receive ride requests → accept/reject → navigate → complete trip | P0 |
| Real-time Matching | Match rider to optimal driver within 2-5 seconds | P0 |
| Live Tracking | Show driver location on map in real-time (GPS every 4 seconds) | P0 |
| ETA Calculation | Accurate pickup/drop-off time estimates | P0 |
| Surge Pricing | Dynamic pricing based on supply/demand per zone | P1 |
| Payment | Process payments, split fares, apply promos | P0 |
| Ratings | Bi-directional ratings (rider ↔ driver) | P1 |
Non-Functional Requirements
20M rides/day
100M users
5M active drivers
99.99% uptime
Multi-region failover
<200ms API responses
<5s matching
Real-time location updates
No double-booking
Eventual consistency for location
Strong consistency for payments
2. Capacity Estimation
| Metric | Calculation | Result |
|---|---|---|
| Rides per day | Given | 20M rides/day |
| Peak QPS | 20M / 86400 × 3 (peak multiplier) | ~700 rides/sec peak → 14K API calls/sec (20 APIs per ride) |
| Active drivers online | 5M drivers × 20% online | 1M concurrent drivers |
| Location updates/sec | 1M drivers × (1 update / 4 sec) | 250K location updates/sec |
| Active trip tracking | Avg trip duration 20 min → 700 rides/sec × 1200 sec | 840K concurrent active trips |
| WebSocket connections | 1M drivers + 500K active riders | 1.5M concurrent connections |
| Storage (trips) | 20M rides/day × 2KB/trip × 365 days × 3 years | 44 TB trip history |
| Storage (location logs) | 250K updates/sec × 100 bytes × 86400 × 30 days | 65 TB/month (archive after 30 days) |
| Bandwidth | 250K location updates/sec × 500 bytes (in+out) | 125 MB/sec = 1 Gbps |
3. High-Level Design
Users, Trips)] RC[(Redis
Geospatial
Online Drivers)] TS_DB[(Time Series DB
Location History)] MQ[Message Queue
Kafka] end subgraph External MAPS[Maps API
Routing] PAY[Payment Gateway
Stripe] end R --> AG D --> AG R --> WS D --> WS AG --> US AG --> TS AG --> PP AG --> PS WS --> LS LS --> RC LS --> TS_DB LS --> MQ MQ --> ME ME --> RC ME --> ES ME --> PP ME --> NS TS --> PG TS --> MQ ES --> MAPS ES --> RC PP --> RC PS --> PAY PS --> PG US --> PG NS --> R NS --> D style ME fill:#ff9800 style LS fill:#4caf50 style RC fill:#f44336 style MQ fill:#2196f3
Service Responsibilities
| Service | Responsibility |
|---|---|
| Location Service | Ingest GPS updates from drivers, store in Redis geospatial index + time-series DB |
| Matching Engine | Find nearby drivers, score candidates, dispatch ride requests |
| Trip Service | Manage trip lifecycle (create, update status, complete), store trip details |
| Pricing Service | Calculate fares, apply surge pricing, store pricing zones and multipliers |
| ETA Service | Calculate pickup/drop-off ETAs using routing + traffic data |
| Payment Service | Process payments, handle refunds, manage payment methods |
| Notification Service | Push notifications, SMS, in-app messages via WebSocket |
4. Location Service
GPS Update Flow
Drivers send location every 4 seconds when online. Active trips may update every 2-3 seconds for smoother tracking.
Redis Geospatial Commands
GEOADD drivers:online {longitude} {latitude} {driver_id}
# Find drivers within 5km of rider
GEORADIUS drivers:online {rider_lon} {rider_lat} 5 km WITHDIST ASC COUNT 20
# Get driver's current location
GEOPOS drivers:online {driver_id}
# Remove offline driver
ZREM drivers:online {driver_id}
Data Partitioning
| Strategy | Approach | Pros/Cons |
|---|---|---|
| City-based sharding | Separate Redis cluster per city/region | ✅ Localized queries, easy scaling ❌ Cross-city rides need coordination |
| GeoHash sharding | Hash lat/lon to partition key (e.g., first 3 chars of GeoHash) | ✅ Automatic geo-distribution ❌ Boundary queries hit multiple shards |
5. Geospatial Indexing
Indexing Approaches
| Technique | How It Works | Query Time | Use Case |
|---|---|---|---|
| GeoHash | Encode lat/lon into base-32 string (e.g., "9q8yyk"). Nearby points share prefix. | O(1) for prefix lookup + O(n) filter | Redis GEORADIUS, simple proximity |
| S2 Geometry | Divide sphere into hierarchical cells (Hilbert curve). Variable resolution. | O(1) for cell lookup + O(k) covering cells | Google Maps, complex shapes, global coverage |
| QuadTree | Recursively divide 2D space into 4 quadrants. In-memory tree. | O(log n) traversal + O(m) results | Dynamic driver locations, in-memory cache |
| R-Tree | Bounding box hierarchy (like B-tree for spatial data). Disk-based. | O(log n) | PostGIS, complex polygon queries |
GeoHash vs S2 Comparison
| Aspect | GeoHash | S2 |
|---|---|---|
| Precision | 5 chars ≈ 5km, 6 chars ≈ 1km, 7 chars ≈ 150m | Level 10 ≈ 5km², Level 13 ≈ 1km², Level 16 ≈ 150m² |
| Boundary Issues | Points near cell edges have different prefixes | Better handling via cell covering (union of cells) |
| Polar Distortion | Cells become elongated near poles | Spherical geometry—uniform cell size |
| Implementation | Simple, built into Redis | Complex, requires S2 library (C++, Go, Java) |
| Recommendation | ✅ Use for Uber (good enough for urban areas) | ✅ Use if global coverage or complex shapes needed |
Finding Nearby Drivers (Pseudocode)
# Query Redis geospatial index
candidates = GEORADIUS drivers:online riderLon riderLat radiusKm km WITHDIST
# Filter available drivers
available = []
for (driverId, distance) in candidates:
driverStatus = GET driver:status:{driverId}
if driverStatus == "AVAILABLE":
available.append({id: driverId, distance: distance})
return available.sortBy(distance).limit(20)
# Complexity: O(log n) for Redis sorted set scan + O(k) for filtering k candidates
6. Matching Engine
Matching Algorithm
Goal: Match rider to best available driver within 2-5 seconds.
Scoring Function
Typical weights: w1=0.4, w2=0.3, w3=0.2, w4=0.1
Higher score = better match
| Factor | Weight | Reasoning |
|---|---|---|
| Distance | 40% | Closer driver = faster pickup |
| ETA | 30% | Accounts for traffic, heading direction |
| Rating | 20% | Rider experience matters |
| Acceptance Rate | 10% | Prefer drivers who don't reject frequently |
Dispatch Flow
Matching Strategies
| Strategy | Description | Pros/Cons |
|---|---|---|
| Serial Dispatch | Offer to best driver first, wait 10s, then next | ✅ Simple, fair to riders ❌ Slower matching |
| Parallel Broadcast | Send to top 5 drivers simultaneously, first to accept wins | ✅ Faster matching ❌ Drivers may feel they're competing |
| Auction-based | Drivers bid with price/ETA, rider picks | ✅ Market-driven ❌ Complex UX |
Uber uses serial dispatch with exponentially increasing radius (e.g., 1km → 3km → 5km) if no driver accepts.
7. ETA Calculation
ETA Components
| Component | Data Source | Method |
|---|---|---|
| Road Network | OpenStreetMap, Google Maps | Graph with nodes (intersections) and edges (roads) |
| Base Travel Time | Speed limits, distance | Dijkstra's algorithm or A* for shortest path |
| Historical Data | Past trip durations by time-of-day, day-of-week | Lookup table: segment → avg speed by hour |
| Real-time Traffic | GPS traces from active drivers, traffic APIs | Adjust edge weights based on current congestion |
| ML Model | Features: distance, time, weather, events | XGBoost/LightGBM to predict delta from base ETA |
ETA Formula
base_time = shortest_path_distance / avg_speed
traffic_multiplier = 1.0 (free flow) to 2.5 (heavy congestion)
pickup_delay = time for driver to pull over, rider to board (~30-60 sec)
ML_adjustment = predicted error correction
Routing Algorithm
Caching and Pre-computation
- Pre-compute: Common routes between high-demand areas (airports, downtown) at different times
- Cache: ETAs for driver → rider pairs (TTL 30 seconds)
- Fallback: Use straight-line distance × 1.3 (Manhattan distance approximation) if routing fails
8. Surge Pricing
Surge Multiplier Calculation
demand = ride requests in zone in last 5 minutes
supply = available drivers in zone
base_factor = tuned per city (typically 0.8-1.2)
Example:
Zone A: 100 requests, 20 drivers → 100/20 × 1.0 = 5.0x surge
Zone B: 50 requests, 60 drivers → 50/60 × 1.0 = 0.83 → 1.0x (no surge)
Geofenced Zones
Divide city into hexagonal zones (H3 library from Uber). Each zone tracks demand/supply independently.
Downtown
2.5x] Z2[Zone 2
Airport
3.0x] Z3[Zone 3
Suburbs
1.0x] Z4[Zone 4
Business District
1.8x] end PP[Pricing Service] --> Z1 PP --> Z2 PP --> Z3 PP --> Z4 PP -->|Update every 2 min| RC[Redis: zone_pricing]
Surge Pricing Flow
- Every 2 minutes: Pricing Service calculates surge multiplier per zone
- Store in Redis:
SET zone:{zone_id}:surge {multiplier} EX 300 - On ride request: Look up rider's pickup zone, apply multiplier to base fare
- Display to rider: Show multiplier (e.g., "1.5x surge in your area") before confirmation
- Lock price: Once rider confirms, fare is locked even if surge changes
Surge Heatmap
| Zone | Requests (5 min) | Available Drivers | Multiplier |
|---|---|---|---|
| Downtown | 150 | 30 | 2.5x |
| Airport | 200 | 50 | 2.0x |
| Midtown | 80 | 40 | 1.3x |
| Suburbs | 30 | 50 | 1.0x |
9. Trip State Machine
State Diagram
State Transitions
| From | To | Trigger | Side Effects |
|---|---|---|---|
| REQUESTED | MATCHING | Trip created | Start matching timer, find nearby drivers |
| MATCHING | MATCHED | Driver accepts | Lock driver status, send rider/driver details, calculate ETA |
| MATCHED | EN_ROUTE_TO_PICKUP | Driver starts navigation | Stream driver location to rider via WebSocket |
| EN_ROUTE_TO_PICKUP | ARRIVED_AT_PICKUP | Driver within 50m of pickup + manual confirm | Notify rider "Driver has arrived" |
| ARRIVED_AT_PICKUP | IN_TRIP | Driver swipes "Start trip" | Start trip timer, begin tracking route for fare calculation |
| IN_TRIP | COMPLETED | Driver swipes "End trip" at destination | Calculate fare, charge payment, release driver, prompt ratings |
| Any state | CANCELLED | Rider/driver cancels, or timeout | Apply cancellation fee if applicable, release driver, log event |
Idempotency and Consistency
- Idempotent transitions: Use
UPDATE trips SET status=NEW_STATUS WHERE id={trip_id} AND status=OLD_STATUSto prevent race conditions - Event sourcing: Store state transitions as events in Kafka (e.g.,
trip.matched,trip.started) for audit trail - Saga pattern: If payment fails on trip completion, compensate by reverting trip status and retrying
10. Scalability & Fault Tolerance
Scaling Strategies
| Component | Scaling Approach | Details |
|---|---|---|
| API Gateway | Horizontal + Load Balancer | Round-robin or least-connections across 100+ instances |
| WebSocket Gateway | Sticky sessions + Redis Pub/Sub | 1.5M connections → 1500 servers × 1000 conns each. Use Redis for cross-server messaging. |
| Location Service | Shard by city/region | NYC, SF, London each get dedicated Redis cluster. Route via city_id in request. |
| Matching Engine | Shard by city + Kafka partitions | Partition Kafka by city_id. Each city's matching runs independently. |
| Trip Service | Shard PostgreSQL by trip_id | Hash(trip_id) % N shards. Read replicas for read-heavy queries. |
| Redis (Geospatial) | Cluster mode + Replication | Master-replica for HA. Cache invalidation via TTL (300s for driver location). |
| Kafka | Partitions by city + Consumer groups | 1000 partitions for high throughput. Retain 7 days for replay. |
Multi-Region Architecture
Sharded DB] GS_PS[Payment Service] GS_Kafka[Kafka
Multi-Region] end DNS[GeoDNS] --> USW_API DNS --> USE_API DNS --> EU_API USW_API --> USW_LS USW_LS --> USW_RC USW_LS --> GS_Kafka USE_API --> USE_LS USE_LS --> USE_RC USE_LS --> GS_Kafka EU_API --> EU_LS EU_LS --> EU_RC EU_LS --> GS_Kafka GS_Kafka --> GS_TS GS_Kafka --> GS_PS
Fault Tolerance
| Failure Scenario | Mitigation |
|---|---|
| Redis node failure | Master-replica failover (Redis Sentinel or Cluster). Rebuild geospatial index from driver heartbeats. |
| WebSocket server crash | Client reconnects with exponential backoff. Resume from last known state via trip_id. |
| Matching Engine downtime | Queue requests in Kafka. Process backlog when service recovers. SLA: 99.9% uptime. |
| Payment gateway timeout | Retry with idempotency key. Store transaction log in DB for reconciliation. |
| Database partition failure | Promote read replica to master. Use Vitess or Citus for automated failover. |
| Network partition (split brain) | Use Raft consensus (etcd) for leader election. Prefer availability over consistency for location data. |
Monitoring & Alerts
- Metrics: Ride request rate, matching success rate, ETA accuracy, p99 latency, WebSocket connection count
- Dashboards: Grafana for real-time monitoring per city, surge pricing heatmaps
- Alerts: Page on-call if matching success rate < 90%, p99 latency > 500ms, or Redis memory > 80%
- Tracing: Use OpenTelemetry to trace ride request → matching → trip completion flow
Bottlenecks and Solutions
| Bottleneck | Solution |
|---|---|
| 250K location updates/sec | Use Kafka as buffer, batch writes to time-series DB, drop old data after 30 days |
| 1.5M WebSocket connections | Use socket.io with Redis adapter for pub/sub, or gRPC bidirectional streaming |
| Hot shard (NYC at 8 PM) | Sub-shard by borough, or use consistent hashing with virtual nodes |
| Thundering herd on surge price update | Use Redis SETEX with jitter, or broadcast via WebSocket instead of polling |
Cost Optimization
- Use spot instances for non-critical background jobs (analytics, ML training)
- Compress location logs (lat/lon as int32) to reduce storage by 50%
- Tier storage: Hot (Redis), warm (TimescaleDB), cold (S3 after 30 days)
- CDN for maps: Cache map tiles and static assets in CloudFront/CloudFlare
Geospatial Deep Dive: Boundary Problem & Solutions
The Boundary Problem
Problem: Driver is 100m from rider but in a different GeoHash cell. Standard single-cell query misses them.
GeoHash divides the world into grid cells. Two points near a cell boundary may have completely different GeoHash prefixes, even though they're physically close. This causes nearby drivers to be invisible to nearby riders.
Solution 1: Query 9 Cells (Center + 8 Neighbors)
Instead of querying only the rider's cell, query a 3×3 grid of cells:
Query cells: [NW, N, NE, W, E, E, SW, S, SE]
# Diagram (3x3 grid)
+---------+---------+---------+
| NW | N | NE |
| (D1) | | |
+---------+---------+---------+
| W | E(Rider)| E |
| | [here] | (D2) |
+---------+---------+---------+
| SW | S | SE |
| | (D3) | |
+---------+---------+---------+
Without neighbor query: Only finds drivers in cell E
With neighbor query: Finds D1, D2, D3 even though they're in adjacent cells
Implementation: For each search, compute the 8 neighboring GeoHash prefixes and query all 9 cells. Merge results and filter by actual distance (Haversine formula).
Trade-off: 9x more Redis queries, but ensures no drivers are missed near boundaries.
Solution 2: S2 Covering
Use S2RegionCoverer to find the minimum set of S2 cells that cover a circle around the rider.
S2RegionCoverer coverer;
coverer.set_max_cells(8); // Limit to 8 cells for efficiency
S2Cap cap = S2Cap::FromAxisAngle(rider_point, radius_angle);
vector<S2CellId> covering;
coverer.GetCovering(cap, &covering);
# Query drivers in union of these cells
for (cell_id : covering) {
drivers.append(query_drivers_in_cell(cell_id));
}
Pros: Spherical geometry (no polar distortion), variable-resolution cells adapt to circle shape.
Cons: Complex implementation, requires S2 library (C++/Go/Java), overkill for most use cases.
Solution 3: Multi-Resolution Indexing
Index drivers at multiple GeoHash precision levels:
| Level | Cell Size | Use Case |
|---|---|---|
| L12 (fine) | ~100m | Precise matching within 1km |
| L10 (coarse) | ~5km | Fallback when expanding search radius |
Strategy: Query fine level (L12) first for nearby drivers. If insufficient matches, query coarse level (L10) to cast a wider net.
GEOADD drivers:L12 {lon lat driver_id}
GEOADD drivers:L10 {lon lat driver_id}
# Query fine first, fallback to coarse
results = GEORADIUS drivers:L12 {lon lat} 1km
if len(results) < 5:
results += GEORADIUS drivers:L10 {lon lat} 5km
Matching Edge Cases
| Edge Case | Handling |
|---|---|
| Driver accepts then cancels | Apply penalty to driver rating/acceptance rate. Re-match from expanded pool (include drivers who were 2nd/3rd choice). |
| Two riders request same driver | First-come-first-served with optimistic lock. UPDATE driver_status SET status='MATCHED', trip_id={trip1} WHERE driver_id={id} AND status='AVAILABLE'. Second request gets 0 rows affected → retry with next driver. |
| No drivers available | Expand radius progressively (2km → 5km → 10km). Suggest estimated wait time. Trigger surge pricing to incentivize drivers to go online. |
| Driver going offline mid-trip | Trip continues (driver can still complete). Payment still captured at end. If driver doesn't complete, assign recovery driver to finish trip or cancel with partial refund. |
Summary
Uber/Lyft is a real-time, geo-distributed, write-heavy system with these key design choices:
- Location Service: Redis Geospatial (GEORADIUS) for O(1) nearby driver queries, city-based sharding
- Matching Engine: Score drivers by distance/ETA/rating, serial dispatch with timeout, expand radius if no match
- ETA: Dijkstra on road graph + historical data + real-time traffic + ML adjustment
- Surge Pricing: demand/supply ratio per hexagonal zone, updated every 2 minutes, locked on rider confirmation
- Trip State Machine: REQUESTED → MATCHING → MATCHED → IN_TRIP → COMPLETED, idempotent transitions
- Scalability: Shard by city, 1.5M WebSocket connections, multi-region, Kafka for async communication
- Fault Tolerance: Redis failover, WebSocket reconnect, payment retries, eventual consistency for location
Operational Readiness (Production-Grade)
Service Level Indicators (SLIs)
- Match time P99 < 30s: Time from rider request to driver acceptance (measured per city)
- ETA accuracy within 20%: Actual pickup time vs. predicted pickup time (|actual - predicted| / predicted < 0.2)
- Location update latency < 3s: Time from driver GPS update to rider app map refresh
Monitoring & Alerting
- Available drivers per zone: Track driver density per H3 hex (alert if < 5 drivers in high-demand zone, trigger surge)
- Match success rate: Ratio of successful matches to total ride requests (alert if < 90%, indicates supply shortage)
- Surge multiplier distribution: Monitor zones with > 3x surge (alert if > 10% of city, may indicate system issue)
- Payment failure rate: Track payment authorization failures (alert if > 5%, may be PSP issue or fraud spike)
Deployment Strategy
- City-by-city rollout: Deploy new pricing algorithm to 1 city first (e.g., Austin), monitor for 48 hours (watch for surge pricing bugs, match time impact) before expanding
- Feature flags per market: Use LaunchDarkly or similar to toggle features per city (e.g., enable UberPool only in high-density cities)
Circuit Breakers
- Matching → payment: If payment service down, degrade by allowing ride to start, charge later when service recovers (store payment intent)
- ETA → ML model: If ML service times out (> 1s), fallback to historical average ETA by time-of-day for that route
Disaster Recovery
- City-scoped: Losing one region only affects that city's rides (no cross-region dependencies), regional failover within 10 minutes
- Location data ephemeral: Driver location in Redis has no persistence (no cross-region replication needed), rebuilt from driver heartbeats