SYSTEM DESIGN #23 · INTERVIEW GUIDE
Design Uber
Every time you open Uber and see a car moving toward you in real time, a system is processing 500,000 GPS location updates per second, running a matching algorithm that pairs riders and drivers in under 2 minutes, computing a dynamic surge price using a PID controller, and estimating your arrival time against live traffic data — all simultaneously. This is one of the most complex real-time systems ever built at scale: it combines geospatial indexing with Redis Geo (GEORADIUS queries), live WebSocket tracking for 10 million concurrent trips, supply-demand surge pricing that responds to local imbalances in seconds, and an OSRM-based ETA engine trained on billions of historical trips. You will learn the exact architecture that powers Uber, Lyft, and Grab — every component, every trade-off, and every scaling decision explained.
Redis GeoOSRMH3 HexagonsWebSocketPID Controller
💡
The Gist — What Problem Are We Solving?
A real-time marketplace matching riders with nearby drivers — in under a minute
Uber is a two-sided marketplace where every second matters: riders want a car in under a minute, drivers want to maximise earnings without dead miles. The system must maintain a live map of every driver on Earth updating every 4 seconds, find the best match in milliseconds, calculate accurate ETAs using real-time traffic, and adjust prices dynamically when demand spikes — all simultaneously for millions of concurrent users.
💬Think of it as a stock exchange for car journeys — except bids arrive every 4 seconds from hundreds of thousands of moving vehicles, and the ‘clearing price’ is computed by a PID controller watching supply and demand in real time.
These are the capabilities the system must deliver — what users and operators can actually do with it.
📍
Ride Request
📍Rider sets pickup and destination; system estimates ETA and price before confirming
🔍
Driver Matching
🔍Find best available driver by ETA and rating; offer and accept flow
🗺️
Live Tracking
🗺️Rider and driver see each other’s real-time location during trip
💰
Dynamic Pricing
💰Surge multiplier based on supply/demand per geographic zone
⭐
Ratings
⭐Mutual post-trip ratings; driver and rider scores affect matching priority
⚡
Non-Functional Requirements
These define how well the system must perform — the quality attributes that separate a toy from a production system.
⏱️ Matching Latency
⏱️Driver offer sent within 500ms of rider request
🗺️ Location Freshness
🗺️Driver location updated every 4 seconds; staleness <5s
📈 Scale
📈Millions of concurrent trips; 500K location writes/sec globally
🎯 ETA Accuracy
🎯p50 ETA within 1 minute of actual pickup time
💰 Surge Accuracy
💰Surge multiplier updated every 30 seconds per geohash cell
📊
Key Metrics — The Numbers That Define This System
The headline numbers to know cold — and be ready to explain how each one is achieved.
🏗️
System Architecture Diagram
Full data flow from source to serving. Each layer scales independently.
Ingestion
Uber Architecture
Driver App
GPS every 4s
→
→
Redis Geo + Kafka; Rider Request
→
↓
Processing
→
→
WebSocket offer to driver
→
↓
Storage
WebSocket Gateway
live tracking); Surge Engine
→
→
→
🗺️
End-to-End User Journey
Trace a single request end-to-end — the story interviewers want you to tell fluently.
1
Driver goes online
— App sends GPS location every 4 seconds. Location Service: Redis GEOADD lat lng driver_id; Kafka event for demand forecasting.
2
Rider opens app
— Map shows available drivers (GEORADIUS query). Surge overlay shown if applicable. Rider enters destination.
3
Rider requests ride
— Request published to Matching Service. GEORADIUS: all available drivers within 2km. ETA Service ranks by predicted pickup time.
4
Driver offered trip
— Best candidate receives WebSocket push offer. 15-second accept window. Countdown timer shown.
5
Driver accepts
— Trip state created in Redis: {rider_id, driver_id, status, route}. Both apps begin receiving each other’s location every 4 seconds.
6
Trip in progress
— Driver location published every 4s → Kafka → WebSocket gateway → rider app. ETA to destination updated every 30s.
🔭
High-Level Design — Component Breakdown
Core components — each with a single, well-defined responsibility. The key architectural insight: each layer scales independently, and failure in one component is isolated from the rest.
1 — Location Svc
Handles responsibilities for the Location Svc layer. Designed for independent horizontal scaling — additional instances added without architectural changes. Communicates asynchronously with adjacent components to maximise throughput and fault isolation.
2 — Matching Svc
Scores and ranks candidates by ETA, rating, and acceptance rate. Dispatches offers via WebSocket with 15-second acceptance window. Falls back to next candidate on decline. P95 match time <30 seconds.
3 — WS Gateway
Terminates WebSocket connections. Maintains connection registry in Redis. Routes incoming messages to target connection via gRPC. Scales horizontally with sticky routing via consistent hash on user_id.
4 — Surge Engine
Handles responsibilities for the Surge Engine layer. Designed for independent horizontal scaling — additional instances added without architectural changes. Communicates asynchronously with adjacent components to maximise throughput and fault isolation.
5 — ETA Service
Handles responsibilities for the ETA Service layer. Designed for independent horizontal scaling — additional instances added without architectural changes. Communicates asynchronously with adjacent components to maximise throughput and fault isolation.
6 — Trip Store
Handles responsibilities for the Trip Store layer. Designed for independent horizontal scaling — additional instances added without architectural changes. Communicates asynchronously with adjacent components to maximise throughput and fault isolation.
🔬
Low-Level Design — Deep Dives
Deep dives worth explaining in detail in any senior engineering interview. For each: know the data structure, the algorithm, the why, and the trade-off you made.
1 — Location Update Pipeline
500K updates/sec · Redis Geo
Driver app sends GPS update every 4 seconds (15s when idle). Payload: {driver_id, lat, lng, heading, speed, ts} — ~60 bytes. Fleet of location service nodes (50K updates/sec each) parse and validate updates. GEOADD snap_map:{city} lng lat driver_id — O(log N). Stale driver pruning: separate sorted set driver_ts:{city} with ZADD driver_id ts; background job ZRANGEBYSCORE to find inactive drivers (last_ts < now-60s) and GEODREM them. City-partitioned geo index keeps each GEORADIUS query fast.
def update_driver_location(driver_id, lat, lng, city):
pipe = redis.pipeline()
pipe.geoadd(f’drivers:{city}’, lng, lat, driver_id)
pipe.zadd(f’driver_ts:{city}’, {driver_id: time.time()})
pipe.execute()
2 — Matching Service
GEORADIUS · ETA Scoring
Rider requests trip: (1) GEORADIUS drivers:{city} rider_lng rider_lat 5 km ASC COUNT 50 → candidate drivers. (2) Parallel OSRM ETA requests for each candidate (timeout 200ms). (3) Score = 0.7×(1/eta) + 0.2×driver_rating + 0.1×acceptance_rate. (4) Dispatch to top-ranked driver via WebSocket. (5) 15-second acceptance window; on decline, next candidate. (6) On accept: assign trip in Redis, notify rider. Matching SLA: <30 seconds to first offer for p95 of trips.
def match_trip(rider_id, city):
rider_loc = get_rider_location(rider_id)
candidates = redis.georadius(f’drivers:{city}’,
rider_loc.lng, rider_loc.lat, 5, ‘km’, count=50)
etas = parallel_osrm_eta(candidates, rider_loc)
scored = sorted(candidates, key=lambda d: score(d, etas[d.id]))
return dispatch_offer(scored[0], rider_id)
3 — Surge Pricing Engine
PID Controller · H3 Hexagons
Surge computed per H3 resolution-8 hexagon (~460m). Every 60 seconds: supply = GEORADIUS count in hex (available drivers). Demand = ZCOUNT ride_requests:{hex} now-300 now (requests in last 5 min). Ratio = demand/supply. Surge = 1.0 + 0.4×max(ratio-1.0, 0), capped at 5.0×. PID controller smooths: surge_t = Kp×error + Ki×integral(error) + Kd×d(error)/dt. Geographic smoothing: adjacent hexagons with >30% difference averaged with weight 0.3.
def compute_surge(hex_id):
supply = get_available_drivers(hex_id)
demand = get_recent_requests(hex_id, window_s=300)
ratio = (demand + 1) / (supply + 1) # avoid div/0
raw_surge = 1.0 + 0.4 * max(ratio – 1.0, 0)
return min(pid_controller.update(raw_surge), MAX_SURGE)
4 — ETA Engine
OSRM + Traffic Model
ETA computation: (1) OSRM pre-computes road graph (contraction hierarchies) for routing in <10ms. (2) Traffic model: gradient boosting trained on 1B+ historical trips predicts travel time multiplier per road segment by hour-of-day, day-of-week, and special events. (3) Final ETA = OSRM_route_time × traffic_multiplier. Traffic model updated every 5 minutes from live trip telemetry. Model served from Redis (pre-computed multipliers per segment) — no ML inference on critical path.
def get_eta(origin, destination):
route = osrm.route(origin, destination)
traffic_mult = redis.get(f’traffic:{route.segment_id}:{hour}’)
return route.duration_s * float(traffic_mult or 1.0)
⚖️
Trade-offs & Decision Log
Every senior interview comes down to these decisions. Know the exact trade-off, the reasoning, and the specific numbers that justify each choice.
⚖️ Geohash vs H3 for Driver-Rider Matching
✓
Geohash + Redis GEORADIUS ✅ Chosen
- Redis GEORADIUS returns drivers within Xkm in O(N+log M) where N=results
- Geohash prefix search enables instant region filtering
- Redis cluster handles 500K location updates/sec natively
- Geohash cells are rectangular — slight distortion near poles
→
H3 (Uber’s hex grid)
- Hexagonal cells have uniform area — no shape distortion
- Consistent cell size at each resolution level
- Better for surge pricing zone calculation
- Requires H3 library and custom spatial index
💡Decision: Redis GEORADIUS for real-time driver lookup (simple, fast); H3 hexagons for surge pricing zone computation (uniform area required)
⚖️ Static vs Dynamic ETA Computation
✓
OSRM + Live Traffic Overlay ✅ Chosen
- OSRM pre-computes road graph — routing in <10ms
- Live traffic layer applied as multiplicative speed factor
- Billions of historical trips train traffic prediction model
- Traffic model must be updated every 5min or ETAs drift
→
Google Maps API (third-party)
- Best-in-class accuracy — Google has most traffic data
- $5/1000 requests × 10M trips/day = $50K/day API cost
- Dependent on Google pricing changes and availability
- Cannot customise for ride-share-specific patterns (surge zones)
💡Decision: OSRM for routing graph; internal ML model (gradient boosting on historical trips) for travel time prediction; Google Maps as fallback for new cities
🎯Interview Questions — Answered
The exact questions interviewers ask — with production-grade answers
Q1
How does Uber match riders and drivers in under 2 minutes globally?
Matching algorithm: (1) GEORADIUS query: find all available drivers within 5km of rider — Redis Geo returns results in O(N+log M) where N=results. Typical result: 10-50 drivers. (2) ETA computation: OSRM routing called for each candidate driver — parallelised across drivers with timeout of 200ms. (3) Scoring: drivers ranked by ETA + driver rating + acceptance rate. (4) Offer dispatch: top-ranked driver receives trip offer via WebSocket; 15-second acceptance window. (5) If declined: next driver in ranked list. (6) Fallback: if no driver accepts after 3 attempts, search radius expanded to 8km and re-ranked. Matching SLA: <30 seconds to first driver offer for 95% of trips.
Q2
How does surge pricing work and how quickly does it respond?
Surge pricing uses a PID (Proportional-Integral-Derivative) controller: (1) Input: supply/demand ratio per H3 hexagon (resolution 8, ~460m diameter) updated every 60 seconds. (2) Supply = available drivers in hex. Demand = ride requests in hex in last 5 minutes. (3) Surge multiplier = f(demand/supply): 1.0 if ratio ≤1.0, 1.0+0.4×(ratio-1.0) for linear zone, capped at 5.0×. (4) PID controller smooths multiplier changes — prevents oscillation where surge attracts drivers, overshoots, creates low supply, oscillates. (5) Geo smoothing: adjacent hexagons with >30% surge difference are smoothed using a weighted average. (6) Response time: surge updates every 60 seconds — drivers on the boundary of a surge zone see updated rates within 60 seconds of demand shift.
Q3
How is driver location updated at scale without overwhelming the backend?
Location update pipeline: (1) Driver app sends GPS update every 4 seconds while driving (every 15 seconds while idle — battery optimisation). (2) Update payload: {driver_id, lat, lng, heading, speed, timestamp} — ~50 bytes. (3) At 5M active drivers × 1 update/4s = 1.25M updates/sec. (4) Load balanced across fleet of location service nodes; each node handles 50K updates/sec. (5) Location stored in Redis Geo (GEOADD O(log N)) keyed by city — partitioned by city to keep geo index manageable. (6) Stale driver pruning: drivers not updated in >60 seconds removed from geo index via a background job. (7) Historical breadcrumbs: raw GPS trace stored in Kafka → S3 for ETA model training, but not served in real time.
System Design Series · Every Tuesday & Thursday
Level up your system design interviews
Each post covers Gist, Functional & Non-Functional Requirements, Key Metrics, System Diagram, User Journey, HLD, LLD, and Trade-offs & FAQs.
Subscribe to never miss a post →
Previous Articles
Categories: System Design
Tags: geohash, interview prep, matching, ride sharing, surge pricing, system design, uber
Leave a Reply