Uber / Ride Sharing — System Design — System Design Portfolio

01

Problem Statement

At its core, Uber is a matchmaking service with a location constraint. A rider says "I need a car here," and the system finds the best available driver nearby. Everything else — surge pricing, ETAs, trip tracking — is layered on top of that core loop.

Think of it like a dating app, but instead of matching on interests, you're matching on proximity and availability, and the match has to happen in seconds, not hours.

Core question: How do you efficiently find the nearest available driver among millions of moving objects, match them to a rider with strong consistency guarantees, and stream real-time location updates — all in under 10 seconds?

Key insight: Uber is a local business. A rider in Dubai will never be matched with a driver in London. This means the hot path (matching) can be partitioned by geography, which fundamentally changes how you think about scale.

02

Requirements

Functional Requirements

Ride request: Riders specify pickup & dropoff, see ETA and fare estimate
Real-time matching: System matches rider with the best nearby available driver
Driver location broadcast: Drivers go online/offline and continuously report GPS position
Live trip tracking: Both rider and driver see each other's position on a map in real-time
Trip lifecycle: REQUESTED → MATCHED → DRIVER_EN_ROUTE → PICKUP → IN_PROGRESS → COMPLETED
Fare calculation: Based on distance, time, and demand (surge pricing)

Non-Functional Requirements

Low latency matching: Rider expects a driver match within 5–10 seconds
High availability: If Uber goes down at 2am on New Year's Eve, it's a safety issue
Real-time updates: Driver positions refresh every 3–4 seconds
Strong consistency on matching: A driver must never be matched to two riders simultaneously
Geographic scalability: Scale by adding cities, not by sharding within a city

Out of Scope

Payments processing, driver onboarding, ratings/reviews, scheduled rides. These are important but architecturally straightforward CRUD — not where the interesting design lives.

03

Scale Estimation

The critical insight: Uber scales geographically, not globally. A rider in Mumbai has zero interaction with a trip in São Paulo. The real unit of scale is per-city, not global.

Per City — NYC Scale (Worst Case)

30K

Concurrent Drivers

7,500/s

Location Writes

~25/s

Ride Requests (Peak)

1.2 MB

Geospatial Index

Global Aggregate

1M

Concurrent Drivers

250K/s

Location Writes

~2K/s

Ride Requests (Peak)

20M/day

Rides Completed

Derivation

Location writes: 30K drivers × (1 update / 4 sec) = 7,500 writes/sec — one Redis instance handles 100K+ ops/sec. One city fits on a single machine.

Ride requests: 500K rides/day ÷ 86,400 sec ≈ 6/sec average. Peak 4x → ~25 req/sec. A single Node.js server handles this.

Index size: 30K drivers × 40 bytes = 1.2 MB. Fits in L2 CPU cache.

Design implication: Matching is not a throughput problem within a city — it's a latency and correctness problem. Scale horizontally by adding cities, not by sharding within a city.

Interview move: "The interesting challenge isn't 250K writes/sec globally — it's that per-city throughput is modest (7,500 writes/sec, 25 ride requests/sec). The real scaling challenge is operational: deploying this per-city stack across 500+ cities."

04

API Design

Request a Ride

POST /v1/rides
{
  "rider_id": "u_abc123",
  "pickup":  { "lat": 40.7505, "lng": -73.9934 },
  "dropoff": { "lat": 40.7580, "lng": -73.9855 },
  "ride_type": "standard"
}
→ 201 { "ride_id": "r_xyz", "status": "REQUESTED", "fare_estimate": "$18-22", "eta_minutes": 4 }

Driver — Update Location

// Via WebSocket (persistent connection)
SEND { "type": "location_update", "lat": 40.7512, "lng": -73.9940, "heading": 45, "speed": 35 }
← ACK { "type": "ack", "ts": 1234567890 }

Driver — Accept / Decline Offer

POST /v1/rides/{ride_id}/respond
{ "driver_id": "d_456", "action": "accept" }
→ 200 { "status": "MATCHED", "rider": { "name": "Alice", "pickup": {...} } }

// If offer expired:
→ 409 { "error": "offer_expired", "message": "This trip is no longer available" }

Get Trip Status (Rider Polling Fallback)

GET /v1/rides/{ride_id}
→ 200 {
  "status": "DRIVER_EN_ROUTE",
  "driver": { "name": "Bob", "lat": 40.7510, "lng": -73.9938, "eta_minutes": 3 },
  "fare_estimate": "$18-22"
}

Driver — Go Online / Offline

PUT /v1/drivers/{driver_id}/status
{ "status": "AVAILABLE" }   // or "OFFLINE"
→ 200 { "status": "AVAILABLE" }

05

High-Level Architecture

The architecture splits into a local hot path (per-city: location, matching, surge) and a global cold path (auth, payments, analytics). The hot path is completely isolated per region.

Regional Isolation Model

The hot path (Location Svc, Matching Svc, Geo Index, Surge, ETA) is deployed per-city/region. If the London region goes down, NYC keeps running. The cold path (Auth, Payments, User Profiles, Analytics) is global but low-throughput and latency-tolerant.

Request Flow — Step Through

Rider App→API Gateway→Trip Service→Matching Svc→Geo Index→Driver Status (CAS)→Push to Driver→Driver Accepts→Notify Rider

Click Next Step to walk through the request flow.

06

Deep Dive — Geospatial Indexing

The core query: "Which drivers are within 2km of this rider?" with 1 million moving objects. A regular database with a B-tree spatial index can't handle 250K location updates/sec rebuilding indexes constantly.

Three Approaches Compared

Geohash

Idea: Fixed-size grid. Convert (lat, lng) → string prefix. Drivers in same cell share prefix.

Simple, O(1) lookup, works with any key-value store.

Fixed cell size — edge problems at cell boundaries. Query 9 cells to cover radius.

Quadtree

Idea: Recursive subdivision. Dense areas (Manhattan) subdivide more than sparse areas.

Adaptive density — high resolution where needed.

In-memory only, hard to distribute. Rebalancing on moves.

Google S2 ★

Idea: Hilbert curve on a cube projection → 64-bit integer cell IDs. Nearby points → nearby integers.

Correct sphere geometry, adaptive levels, native DB indexes.

More complex to understand. Overkill unless you can explain it.

How S2 Works — Step by Step

Step 1 — Sphere to Cube: Project Earth onto 6 cube faces. Unlike Mercator (which distorts poles), no cell is more than ~5.2× larger than any other. Think of wrapping a round ball in a box.

Step 2 — Hilbert Curve: A space-filling curve that visits every cell in the grid while preserving spatial locality. Points close in 2D stay close in 1D. Unlike a row-scan (which jumps from row end to next row start), the Hilbert curve snakes continuously — consecutive numbers are always neighbors on the grid.

Hilbert vs Row-Scan — The Lawn Mowing Analogy

Bad strategy (row scan): Mow entire row left→right, walk all the way back, mow next row. Constant long jumps.

Hilbert strategy: Mow in U-shape patterns that recursively nest at every scale. Never make a long jump. Always near where you just were.

Step 3 — Cell IDs: Every point on Earth becomes a 64-bit integer. Encodes: which cube face (3 bits), Hilbert curve position (up to 60 bits), precision level. Works natively with sorted sets, B-trees, any integer index.

S2 Level	Cell Size	Use Case
12	~3.3 km²	Coarse city-area queries
14	~0.2 km²	Neighborhood level
16	~0.01 km²	Street-block level
18	~150 m²	Individual building

Step 4 — The Payoff: "Find drivers within 2km" becomes: compute S2 cell ranges covering that circle → run ZRANGEBYSCORE drivers 576543209900 576543210100 in Redis → get 15 candidates → haversine for final filter. Narrowed 1M drivers → ~15 candidates with a simple integer range query.

sequenceDiagram participant R as Rider App participant M as Matching Svc participant S2 as S2 Library participant GI as Geo Index (Redis) R->>M: Request ride at (lat, lng) M->>S2: Cover 2km radius S2-->>M: Cell ranges [5765...99–5765...01] M->>GI: ZRANGEBYSCORE per range GI-->>M: [D1, D2, D3 ... D15] M->>M: Haversine filter + ETA rank M-->>R: Best candidate: D3 (ETA 4min)

Interview shortcut: "I'd use S2 cells — they map Earth to 64-bit integers via a Hilbert curve. Spatially close points get numerically close IDs, so 'find nearby drivers' becomes a range query on a sorted integer index. Works with any DB or Redis sorted set."

07

Deep Dive — Matching State Machine

Two competing goals: speed (match in <10 sec) vs correctness (a driver must never be matched to two riders). Speed pushes toward parallel offers; correctness pushes toward serial. Uber chose serial — and the state machine reflects that.

Trip State Machine

stateDiagram-v2 [*] --> REQUESTED: Rider taps Request REQUESTED --> MATCHING: Enters dispatch MATCHING --> OFFERED: Best driver found OFFERED --> MATCHED: Driver accepts OFFERED --> MATCHING: Timeout / Decline MATCHING --> NO_DRIVERS: Retries exhausted MATCHED --> DRIVER_EN_ROUTE: Driver navigates DRIVER_EN_ROUTE --> ARRIVED: At pickup ARRIVED --> IN_PROGRESS: Rider picked up IN_PROGRESS --> COMPLETED: At dropoff REQUESTED --> CANCELLED: Rider cancels MATCHING --> CANCELLED: Rider cancels OFFERED --> CANCELLED: Rider cancels MATCHED --> CANCELLED: Either cancels

Driver State Machine

stateDiagram-v2 [*] --> OFFLINE OFFLINE --> AVAILABLE: Goes online AVAILABLE --> OFFERED: Trip offer received OFFERED --> ON_TRIP: Accepts OFFERED --> AVAILABLE: Declines / Timeout ON_TRIP --> AVAILABLE: Trip completed AVAILABLE --> OFFLINE: Goes offline

Preventing Double-Matching — The CAS Lock

The race condition: Trip A queries the geo index → finds Driver X. Trip B queries → also finds Driver X. Both send offers. Driver X has two offers on screen. Chaos.

The fix: Compare-and-Swap (CAS) on driver status. An optimistic lock — try the write, check if it succeeded.

-- Atomic claim attempt
UPDATE drivers
SET status = 'OFFERED', trip_id = 'trip_A'
WHERE driver_id = 'X' AND status = 'AVAILABLE'

-- Did it affect 1 row?
-- YES → We got the lock. Send push to Driver X.
-- NO  → Someone else claimed X. Move to next candidate.

# Redis equivalent (WATCH/MULTI/EXEC)
WATCH driver:X:status
status = GET driver:X:status
if status != "AVAILABLE":
    return FAILED

MULTI
  SET driver:X:status "OFFERED"
  SET driver:X:offered_trip "trip_A"
  SET driver:X:offer_expires (now + 15s)
EXEC
# If EXEC returns nil → another client modified the key → retry next driver

The Matching Flow — Full Trace

sequenceDiagram participant R as Rider participant TS as Trip Svc participant MS as Matching Svc participant GI as Geo Index participant DS as Driver Status (CAS) participant D1 as Driver 1 participant D2 as Driver 2 R->>TS: Request ride TS->>MS: Find driver for Trip T1 MS->>GI: Nearby drivers at (lat,lng) GI-->>MS: [D1 (0.5km), D2 (1.2km)] MS->>DS: CAS: D1 AVAILABLE → OFFERED DS-->>MS: SUCCESS ✓ MS->>D1: Push: "New trip, 0.5km away" Note over D1: 15-second timer starts alt Driver accepts D1->>MS: Accept MS->>DS: D1 → ON_TRIP MS->>TS: Trip T1 → MATCHED TS->>R: "Driver found! ETA 3 min" else Driver times out (15s) Note over MS: Timer fires MS->>DS: D1 → AVAILABLE (release) MS->>DS: CAS: D2 AVAILABLE → OFFERED DS-->>MS: SUCCESS ✓ MS->>D2: Push: "New trip, 1.2km away" end

Why 15 Seconds?

Too Short (5s)

High Timeout Rate

Driver might be driving, can't safely look at phone. More retries → slower overall match. Drivers get frustrated by missed opportunities.

Too Long (30s)

Terrible Rider UX

30s × 5 attempts = 2.5 min with no match. Closer drivers may become available but aren't considered. App feels broken.

15 Seconds — The Sweet Spot

Long enough for a driver to glance at the offer. Short enough that the retry loop completes within ~60 seconds worst case. After 3–5 failed offers, the system expands the search radius or returns NO_DRIVERS.

Edge Case: The Phantom Accept

Driver accepts after server-side timeout

At T+14.5s driver's slow phone receives the offer. At T+15s server times out, moves to next candidate. At T+15.2s driver taps Accept. The accept endpoint validates: trip.status == OFFERED AND trip.offered_driver == D1. Since the trip already moved back to MATCHING, the validation fails. Driver sees "This trip is no longer available." Slightly frustrating, but correct.

Concurrency Model

Multiple Matching Service instances can run in parallel. The geospatial index is "loose" (eventually consistent, multiple readers). The driver status store is "tight" (strongly consistent, atomic CAS). Think of it like an auction — everyone browses the catalog freely, but bids go through a single auctioneer. Two bidders on the same item don't break the system.

08

Deep Dive — Real-Time Trip Tracking

The rider stares at a little car icon crawling toward them on the map. That icon updates every few seconds, smoothly. This is a real-time pub/sub problem — the driver publishes location, the rider subscribes, the trip is the channel.

Why Not Just Poll?

✗ HTTP Polling (3s)

3.3M req/sec globally

Each request: full TCP handshake, TLS, headers, teardown. 90% of responses are "location moved 10m." ~10 GB/sec bandwidth wasted on headers.

✓ WebSocket

250K msg/sec globally

Persistent full-duplex TCP. No headers, no handshakes. ~100 MB/sec bandwidth. 30× less bandwidth, 13× fewer messages.

The Four Components

1. Connection Gateway (Stateful)

Holds all WebSocket connections. Each instance maintains ~50K–100K connections. Separate from API servers because it's stateful — a rider's connection lives on a specific instance. Scaling: add instances, Redis handles cross-instance routing.

2. Redis Pub/Sub (Message Bus)

Decouples driver's gateway from rider's gateway. Each trip has a channel trip:{trip_id}. Driver's gateway publishes, rider's gateway subscribes. Messages are ephemeral — if one update is missed, the next arrives in 3 seconds. Not Kafka — no need for durability/replay here.

3. Location Processing Pipeline

Road snapping (GPS might be 30m off-road) → noise filtering (discard impossible-speed outliers) → rate normalization (one processed update per 3–4 sec). Adds ~10–50ms latency. Also computes heading + speed for client interpolation.

4. Client-Side Interpolation

The app doesn't teleport the car icon between updates. It animates smoothly from position P1 to P2 over 4 seconds using heading and speed. The smoothness is a client-side illusion, not a server achievement. Server sends coarse updates; client fills the gaps.

End-to-End Data Flow

sequenceDiagram participant DP as Driver Phone participant G7 as Gateway #7 participant LP as Location Pipeline participant RPS as Redis Pub/Sub participant G3 as Gateway #3 participant RP as Rider Phone DP->>G7: GPS: (40.7506, -73.9931) G7->>LP: Raw location LP->>LP: Road snap + noise filter LP->>RPS: PUBLISH trip:T1 {lat, lng, heading, speed} RPS->>G3: Message delivered (subscriber) G3->>RP: WebSocket push RP->>RP: Animate car icon (interpolation) Note over DP,RP: Total server latency ~25ms + network ~150ms = ~200ms

Connection Failure Handling

Rider WS Drops

App detects disconnection, reconnects (possibly to different gateway). During gap, app continues interpolating from last known position. New gateway subscribes to same Redis channel. Usually seamless.

Driver WS Drops

No location updates flow. After 5–10s of silence, rider sees "Updating driver location..." Car icon freezes. When driver reconnects, updates resume. Location TTL (30s) auto-marks driver offline if phone died.

Gateway Crash

50K connections drop simultaneously. Clients reconnect with exponential backoff + jitter: delay = random(0, min(30s, 2^attempt)). Spreads reconnection storm over several seconds.

Multiple Observers

"Share trip status" adds 2–3 family watchers. Redis Pub/Sub fans out natively — one publish, multiple subscribers. Operations dashboard uses a separate Kafka pipeline for aggregation.

09

Deep Dive — Spike Scenarios & Surge Pricing

Beyoncé concert at MSG ends. 20,000 people pour out. ~4,800 ride requests in 10 minutes from one city block. Available drivers nearby: 50. That's a 96:1 ratio. Three problems hit simultaneously.

Problem 1: Supply/Demand

4,800 riders, 50 drivers. Even with a 5km radius, maybe 300 drivers. Physical constraint — no amount of engineering makes 300 serve 4,800.

Problem 2: Geo Hot Spot

Thousands of queries hit the same S2 cell. If sharded by region, one shard gets 100× normal load while neighbors sit idle.

Problem 3: Driver Starvation

Aggressively pulling drivers toward MSG drains Midtown Manhattan. Someone 15 blocks away now sees "no drivers available." You've solved one hot spot by creating a dead zone around it.

Solution 1: Surge Pricing (Load Shedding in Economics Clothing)

Demand/Supply Ratio	Surge Multiplier	Effect
1.0–1.5	1.0×	Normal pricing
1.5–2.0	1.3×	Mild surge
2.0–3.0	1.8×	Some riders choose alternatives
3.0–5.0	2.5×	Many riders drop off
5.0+	3.0×+	Only urgent riders remain

Demand side: 2.5× pricing reduces 4,800 requests to ~1,500 — a serviceable number. Supply side: Drivers 3–5km away see the surge zone on their app and converge. Surge pricing is a load shedding mechanism wearing an economics hat.

Timing matters: Uses a 5-minute sliding window with smoothing. Can't recalculate every second (surge bounces wildly: $45 → $28 → $52) — erodes trust.

Solution 2: Request Coalescing & Read Replicas

Read replicas: Matching queries are read-heavy during spikes. Multiple Redis replicas, load-balanced. 1.2MB of data replicates with negligible lag.

Request coalescing: 200 requests from the same block in 2 seconds? Run one geospatial query, get candidates, do optimal batch assignment instead of greedy first-come-first-served. Better outcomes than individual matching.

Solution 3: Supply Reservation

Each zone keeps a minimum supply threshold (e.g., 5 drivers per hexagon). When matching for the spike area, filter out drivers who are the "last few" in their home zone. Like a hospital — don't send every doctor to the disaster site; keep some for unrelated emergencies.

Spike Timeline — Minute by Minute

T+0 min — Concert Ends

20,000 people start exiting. Available drivers near MSG: ~50.

T+1 min — First Wave

~500 requests hit matching. First 40–50 riders matched quickly. Surge calculation detects spike.

T+2 min — Surge Activates

Demand/supply ratio hits 10:1. Surge rises to 1.5×, then 2.0×. Drivers 3–5km away see surge zone appear.

T+3–5 min — Demand Shaping

Surge reaches 2.5×. ~30% of riders abandon and choose alternatives. Remaining riders enter virtual queue with increasing ETAs.

T+5–10 min — Supply Response

Drivers attracted by surge converge. Supply increases from 50 to ~150. Search radius expands to 5km. Rides matched with 8–12 min ETAs.

T+10–20 min — Stabilization

Demand tapers. Supply catches up. Surge begins dropping. By T+20, system back to equilibrium.

The insight: Not every problem is a software problem. The system's job during a spike is to manage scarcity gracefully — not pretend scarcity doesn't exist.

10

Deep Dive — ETA Calculation

When the rider sees "3 min away," that's not a guess — it's a prediction pipeline with four layers, each trading accuracy for speed.

Why Not Just Use Google Maps?

Cost + Latency Kill It

5 ETA calculations per app open × 1M opens/day = 5M API calls/day per city. At $5/1K calls = $25,000/day per city. Across 500 cities → $12.5M/day. Plus 100–300ms latency per call. Uber built their own routing engine.

The Four-Layer ETA Pipeline

Layer	When Used	Latency	Accuracy
Haversine + Detour Factor	Rider browsing, quick filter	<1ms	±40%
Pre-Computed Zone Matrix	"X min away" on nearby drivers	<1ms	±20%
Contraction Hierarchies	After match — "arriving in X"	5–50ms	±10%
ML Correction	Final correction layer	+5ms	±5–7%

Layer 1 — Haversine + Detour Factor

straight_line = haversine(driver_lat, driver_lng, rider_lat, rider_lng)
estimated_dist = straight_line × detour_factor   // Manhattan: 1.4, London: 1.7
eta = estimated_dist / avg_speed_at_time_of_day  // 8am rush: 15km/h, 3am: 40km/h

Sub-millisecond. Just arithmetic. Good enough for "is the nearest driver ~3 minutes or ~15 minutes away?" — the coarse filter.

Layer 2 — Pre-Computed Zone Matrix

Divide the city into ~500m hexagonal zones. Pre-compute travel time between zone pairs within 10–15km (sparse matrix: ~1.5M entries, 6 MB in memory). Updated every 5–15 min from crowdsourced trip data. Lookup: O(1) hash map.

Layer 3 — Contraction Hierarchies (The Big One)

Full graph-based shortest path on the road network. Nodes = intersections. Edges = road segments. Weights = travel time (not distance — a 1km highway takes 30s, a 1km local road takes 3 min).

How Contraction Hierarchies Work — The Highway Analogy

You drive cross-city the same way: "get on Highway 1, take it across, exit at 5th Ave." You skip unimportant streets mentally. CH formalizes this: offline, rank nodes by importance (highways > residential). Add "shortcut edges" that skip unimportant nodes. Online, search upward from source and downward from target — they meet at an important node (highway). Explores ~1,000 nodes instead of 1,000,000. Query drops from ~100ms to ~0.1ms — a thousand× faster.

Real-time traffic: Edge weights updated every 1–5 min using GPS data from active drivers (millions of real-time speed observations). Uses Customizable Contraction Hierarchies — hierarchy structure pre-computed once, weights swappable in ~1 second.

Layer 4 — ML Correction

Fixes systematic biases the graph misses: traffic lights, left turns, school zones, pickup complexity. Input: graph ETA + time/day/weather/zone. Trained on billions of historical trips. Improves accuracy from ~85% to ~90–93% within ±2 minutes.

The Data Flywheel

flowchart LR A["Trip Completed"] --> B["Actual vs Predicted"] B --> C["Zone Matrix Update"] B --> D["Road Segment Weights"] B --> E["ML Model Retrain"] C --> F["Better ETAs"] D --> F E --> F F --> G["More Trips"] G --> A

Competitive moat: Every completed trip makes future predictions better. Uber has billions of historical trips. A new ride-hailing startup has zero trip data to train on.

Edge Cases

GPS Tunnel Problem

Driver enters tunnel, GPS lost for 2 min. System predicts progress based on route + average tunnel traversal time. Synthetic ETA updates without GPS.

Driver Goes Off-Route

Wrong turn or shortcut. Recalculate from current position every 30–60s. If deviation is significant, ETA adjusts automatically.

11

Key Design Decisions & Tradeoffs

1. Location Updates: Push vs Pull

✓ Push (Driver → Server)

Driver Pushes Every 4s

Via persistent WebSocket/HTTP2. Server just receives and writes. Natural direction of data flow. Only active drivers send.

✗ Server Polls Drivers

Poll 1M Drivers Every 4s

250K polls/sec initiated by server. Backwards — server does all the work. Drivers that went offline still get polled. Massive waste.

2. Geospatial Index: In-Memory vs Database

✓ In-Memory (Redis)

Sub-ms Queries, 250K Writes/s

Only stores current locations (~40MB globally). Data is ephemeral — if Redis dies, drivers re-report within 4 seconds. Perfect fit for volatile, high-throughput workload.

✗ PostgreSQL + PostGIS

Durable But Slow

Constantly rebuilding B-tree spatial indexes at 250K writes/sec. Overkill durability for data that expires in seconds. Trip history goes here — not live locations.

3. Matching: Single Offer vs Broadcast

✓ Serial (One at a Time)

Sequential Offers with 15s Timeout

Clean UX — one driver considers at a time. No race conditions. Tradeoff: slower if drivers decline (up to 60s worst case).

✗ Broadcast to All Nearby

Fan-Out to 10 Drivers

Faster first match, but 9 angry drivers who tapped Accept and lost. Race conditions everywhere. Terrible driver experience.

4. Matching Consistency: Strong vs Eventually Consistent

✓ Strong (CAS Lock)

Atomic Compare-and-Swap

A driver can only be in one OFFERED state at a time. Single serialization point. Correctness is non-negotiable — you can't tell two riders "driver found" for the same driver.

✗ Eventually Consistent

Optimistic, Resolve Conflicts Later

Higher throughput, but double-matching becomes possible. Resolving after-the-fact ("sorry, your driver was reassigned") is terrible UX.

12

What Can Go Wrong

GPS Drift in Urban Canyons

Tall buildings cause GPS accuracy to drop to 50–100m. Driver appears inside a building. Fix: Road-snapping algorithm pins coordinates to nearest road segment. Handles approximate locations gracefully.

Stale Driver Location

Driver's app crashes. Last known location stays in index — matching service offers trips to a "ghost." Fix: TTL on location entries (30s). No update received → auto-mark offline, remove from geo index.

Hot Spot Overloads a Shard

Concert/sports event: 50K requests from one small area. If geo index sharded by region, one shard is crushed. Fix: Read replicas for query load + request coalescing for batch matching + dynamic re-sharding of hot cells.

Double Matching (Race Condition)

Two concurrent ride requests match the same driver in the gap between querying index and sending offer. Fix: Atomic CAS on driver status. If CAS fails, retry with next candidate. Design guarantees at-most-one active offer per driver.

Network Partition During Active Trip

Driver loses connectivity mid-trip. Rider sees frozen map. Fix: Rider app shows "connection lost" after N seconds. Trip continues — fare calculated from GPS data when connectivity resumes. Client interpolation masks brief gaps.

Gateway Server Crash

50K WebSocket connections drop simultaneously. Fix: Exponential backoff + jitter on reconnection. Graceful shutdown protocol: send "please reconnect" before retiring instances.

⚠

Anti-patterns

🚫

Nearest-driver wins every trip

Greedy local assignment leaves Dashers idle on one side, riders waiting on other.

✓ Better: 2-second batched window + Hungarian-algorithm assignment optimizing global score (distance, ETA, fairness).

🚫

Single Postgres table for all locations

Millions of driver location pings/sec melts OLTP. Geo query on B-tree is O(N).

✓ Better: Redis GEO or H3 hex-cell index; ring queries on cell + 18 neighbors; history to Cassandra.

🚫

Strong consistency on all trip state

2PC across driver + rider + payments is slow AND brittle.

✓ Better: Saga with idempotent steps; compensating actions on failure; strong only on fund movements.

13

Interview Tips

💡

Start with single-rider, single-driver
"One rider, one driver, same server." Build the simplest working version first, then scale. This grounds the conversation in reality and shows you don't pattern-match to distributed systems.

⚡

Derive the numbers — they drive the design
"250K location writes/sec" is the number that forces you toward an in-memory index. "25 ride requests/sec per city" shows matching isn't a throughput problem. Derive these from assumptions, don't assert them.

🎯

Name the geospatial approach explicitly
Interviewers want to hear "geohash," "quadtree," or "S2 cells." Don't just say "spatial index." Start with geohash (simple, correct), then mention S2 for production scale.

🔒

The matching lock is where you show depth
Discuss CAS on driver status, the 15-second timeout, phantom accepts, and how multiple matcher instances can coexist without double-matching. This is distributed systems in action.

📊

Highlight the read/write asymmetry
Location writes are 100× more frequent than ride requests. The location ingestion path and the matching path have completely different characteristics and should be separate subsystems.

🌍

Uber scales geographically, not globally
"A rider in Dubai never matches with a driver in London. The hot path is per-city — 7,500 location writes/sec fits on one Redis instance. Scale by adding cities, not by sharding within a city."

🔥

Discuss demand spikes — most candidates don't
"Not every problem is a software problem. A concert ending creates a 100:1 ratio. The system manages scarcity with surge pricing (demand shaping), request coalescing (batch assignment), and supply reservation (prevent dead zones)."

14

Evolution

How this design grows from MVP to planet-scale.

1

Single City MVP

One server, PostgreSQL with PostGIS, simple "closest driver" matching via Haversine. HTTP polling for location updates. Works for 1K drivers. Prove the market before scaling.

2

Multi-City Scale

Geospatial index moves to Redis with geohashing. Location ingestion becomes a separate service. WebSocket connections for real-time tracking. Shard by city. Add surge pricing watching supply/demand ratios.

3

Regional Isolation

Each region gets its own deployment of the hot path (location, matching, surge, ETA). Global services (auth, payments, analytics) remain shared. If London goes down, NYC keeps running. Deploy per-region independently.

4

Planet Scale

S2-based geospatial indexing with adaptive cell sizes. ML-powered matching with ETA prediction, driver acceptance probability, and optimal batch assignment. Contraction Hierarchies for routing. Kafka for event streaming. Billions of trip data feeding the ML flywheel.

📺

References & Videos

System Design: Uber Lyft ride sharing

Gaurav Sen · 28 min

Uber System Design

Tech Dummies Narendra L · 24 min

Design Uber — System Design Interview

Exponent · 15 min

Design Uber/Lyft

Hello Interview

Uber's Fulfillment Platform Rearchitecture

Uber Engineering