System Design

Design Uber / Ride Sharing

Matching drivers and riders, real-time location, surge pricing, trip state machine, and payment.

Interview tip Geospatial index (geohash/quadtree) for nearby drivers. Trip state machine: requested → accepted → arrived → ongoing → completed. Separate location service (high write) from trip service.

① Functional requirements

Rider requests ride: pickup, dropoff, ride type (economy/premium)
Match with nearest available driver (ETA < 5 min)
Real-time driver location on map during trip
Trip lifecycle: requested → accepted → arrived → in-progress → completed
Surge pricing during high demand
Payment charged after trip completion
Ratings for driver and rider after trip
Ride history for rider and driver

Out of scope (state in interview)

Driver onboarding and background checks
Food delivery (Uber Eats — mention as extension)
Route optimization / navigation engine
Pool/shared rides matching

② Non-functional requirements

Match driver within 30s of request p99
Location updates reflected on map within 4s
20M rides/day → ~230 rides/sec avg, ~2K/sec peak (rush hour)
250K location updates/sec (2M active drivers × 1 update/4s)
99.9% availability on matching service

③ Back-of-the-envelope scale

Assumptions

20M rides/day → ~230/sec avg, ~2K/sec peak
10M drivers; 20% active peak = 2M drivers online
Location updates: 2M × 0.25/sec = 500K updates/sec
Geospatial index: 2M active driver locations in memory
Matching queries: 2K/sec peak; each queries ~50 nearby drivers
Trip state storage: 20M trips/day × 30 days = 600M active trip records

Location service is write-heavy and separate from trip service. Geohash grid (precision 6 ≈ 1.2km × 0.6km cells) indexes drivers. Matching: query 9 surrounding cells → rank by distance + ETA + driver rating.

④ High-level architecture

Uber Ride-Sharing Platform

Rider App

Driver App

API Gateway + WebSocket

Trip Service (state machine)

Matching Service

Location Service

Pricing Service

Geospatial Index (Redis Geo)

Kafka (location stream)

Trip DB (Cassandra)

Payment Service

Notification Service

Request ride→Geo search drivers→Offer + accept→Trip in progress

Driver app sends GPS every 4s → Location Service → update Redis Geo index + publish to Kafka → rider app WebSocket subscribes to trip topic. Matching is stateless — queries geo index at request time. Trip state in Cassandra with optimistic locking.

⑤ Data flow & execution path

End-to-end execution flow

① Client→② API / LB→③ Core services→④ Cache + DB→⑤ Message queue→⑥ Async workers

Sync path: validate → authorize → read/write primary store
Async path: publish domain events → consumers (email, analytics, search index)
Read-heavy path: CDN / edge cache → regional cache → DB replica
Failure path: retry with backoff, DLQ, idempotent handlers

In interviews, trace one user action through this diagram. State what is synchronous (user waits) vs asynchronous (background), and where you enforce idempotency.

⑥ API & interfaces

Endpoint / flow	Purpose	Notes
POST /v1/trips/request	Request ride	{pickup, dropoff, rideType} → {tripId, estimatedFare, surgeMultiplier}
POST /v1/trips/{id}/accept	Driver accepts	Driver only; transitions requested→accepted; notifies rider
POST /v1/trips/{id}/status	Update trip status	arrived\|started\|completed — state machine validated
PUT /v1/drivers/{id}/location	Driver GPS update	{lat, lng, heading, ts} — high frequency, async
GET /v1/trips/{id}/location	Real-time driver location	WebSocket stream or poll; from Kafka trip topic
POST /v1/trips/{id}/rate	Rate trip	{rating, comment} — after completion only

⑦ Data model & storage

trips: trip_id, rider_id, driver_id, status, pickup, dropoff, fare, surge, created_at, version

driver_locations (Redis Geo): GEOADD drivers {lng} {lat} {driver_id}; GEORADIUS for search

drivers: driver_id, status (available|busy|offline), vehicle_type, rating

Store	What	Why
Redis Geo	Active driver locations	GEOADD/GEORADIUS; TTL 30s — stale drivers auto-removed
Kafka	Location stream + trip events	500K msgs/sec location; trip events for analytics
Cassandra	Trip records	Partition by trip_id; status history; high write throughput
PostgreSQL	Driver/rider profiles, payments	ACID for payment; trip references payment_id

⑧ Deep dive — core components

Geospatial matching

On ride request: GEORADIUS pickup_lat_lng 5km WITHDIST COUNT 50 ASC → 50 nearest drivers. Filter: status=available, vehicle_type matches, rating > 4.0. Rank by: ETA (distance/avg_speed) + driver acceptance rate. Send offer to top 3 simultaneously; first accept wins; cancel others.

Geohash precision: 6 chars = ~1.2km cell. Query cell + 8 neighbors. Index update: driver moves → GEOADD overwrites previous position atomically.

Location update pipeline at 500K/sec

Driver app → Location API (async, fire-and-forget) → Kafka topic partitioned by driver_id → consumers: (1) update Redis Geo, (2) if driver in active trip, publish to trip WebSocket topic for rider. API responds 202 immediately — no blocking.

Stale location: Redis TTL 30s on driver key. If no update in 30s, driver marked offline in matching. Driver heartbeat every 4s keeps TTL alive.

Trip state machine

States: REQUESTED → ACCEPTED → ARRIVED → IN_PROGRESS → COMPLETED | CANCELLED. Transitions validated server-side (can't COMPLETE from REQUESTED). Each transition: UPDATE trip SET status=new, version=version+1 WHERE version=expected. Failed transition → 409 Conflict (concurrent update).

Cancellation: rider can cancel before ACCEPTED (free); after ACCEPTED (fee). Driver cancel → re-match rider automatically.

Surge pricing

Surge = f(demand/supply ratio in geohash cell). Demand: ride requests in last 5 min. Supply: available drivers in cell. Ratio > 2.0 → 1.5× surge; > 4.0 → 2.5×. Computed every 1 min by pricing service; cached in Redis per cell. Shown to rider before confirm.

⑨ Trade-offs & alternatives

Decision	Option A	Option B	Pick when
Geo index	Redis Geo (geohash)	Quadtree in memory	Redis Geo ops-managed; quadtree custom but flexible
Matching	Broadcast to top 3	Sequential offer	Broadcast faster; sequential less driver annoyance
Location	WebSocket push	Client poll 4s	WebSocket for smooth map; poll simpler
Trip storage	Cassandra	PostgreSQL	Cassandra for write scale; PG for simpler ACID
Surge	Geohash cell	City-wide	Cell granular; city-wide simpler but unfair

⑩ 45-minute interview script

0–5 min: Clarify request, match, trip lifecycle, payment, location
5–12 min: Scale — 20M rides/day, 500K location updates/sec
12–22 min: Architecture — location, matching, trip, payment services
22–30 min: Geospatial index and matching algorithm deep dive
30–36 min: Location update pipeline (Kafka + Redis Geo)
36–42 min: Trip state machine with version locking
42–45 min: Surge pricing model

⑪ Likely follow-up questions

Question	Short answer
No drivers available?	Expand search radius incrementally; after 5km show "no drivers"; suggest schedule later
Driver accepts then cancels?	Trip back to REQUESTED; re-match; penalize driver acceptance rate
Rider and driver see different locations?	Location eventually consistent; 4s staleness acceptable; rider sees last known
Payment fails after trip?	Retry 3×; mark trip PAYMENT_PENDING; block rider next request until resolved
Driver in tunnel (no GPS)?	Last known location used; interpolate; mark low-confidence on map
Match during New Year surge?	Surge pricing reduces demand; waiting room for riders; incentive bonus for drivers

⑫ Revision checklist

Geospatial index (Redis Geo / geohash)
GEORADIUS for nearby driver search
Location update async via Kafka
Trip state machine with valid transitions
Optimistic locking on trip status
Broadcast offer to top N drivers
500K location updates/sec handling
Stale driver TTL (30s heartbeat)
Surge pricing by geohash cell
WebSocket for real-time rider map

geospatialreal-timematchingstate machinelocation