Design Uber / Ride Sharing

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.

Requirements

Functional Requirements

Non-Functional Requirements

Out of Scope

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)

Global Aggregate

API Design

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 }

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

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 /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"
}

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

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.

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

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.

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.

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)
        

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?

Edge Case: The Phantom Accept

Concurrency Model

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?

The Four Components

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

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.

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

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

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?

The Four-Layer ETA Pipeline

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).

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
        

Edge Cases

Key Design Decisions & Tradeoffs

1. Location Updates: Push vs Pull

2. Geospatial Index: In-Memory vs Database

3. Matching: Single Offer vs Broadcast

4. Matching Consistency: Strong vs Eventually Consistent

What Can Go Wrong

Interview Tips

Evolution

How this design grows from MVP to planet-scale.