Geospatial & LocationQuestion #11ADVANCED

Uber: Driver-Rider Geospatial Matching & Dynamic Surge Pricing

Real-time geospatial dispatch and routing engine using H3 spatial indexing, high-frequency location tracking streams, ETA computation graphs, and localized surge algorithms.

Category: Category 8: Geospatial & Location-Based•Updated: 2026-08-30
#Location#Driver-Rider Matching#Quadtrees#H3 Hexagons#ETA#Surge Pricing

Design a Cab-Aggregation Service like Uber

Author: System Design Expert | Date: 2026-08-28 Scope: End-to-end design of a ride-hailing aggregation platform connecting riders, drivers, and operations at scale.


Table of Contents

  1. Requirements Clarification
  2. Back-of-Envelope Calculations
  3. System Interface Design
  4. High-Level Architecture
  5. Core Component Design
  6. Data Model
  7. Key Design Decisions
  8. Scalability Strategy
  9. Curveball Scenarios
  10. Failure Modes and Mitigations

1. Requirements Clarification

1.1 Functional Requirements

ID Requirement Priority
FR-01 Rider App: Register/login, set pickup & destination, view nearby drivers, request ride, track driver in real-time, rate/review, payment P0
FR-02 Driver App: Register/login, go online/offline, accept/decline ride requests, navigate to rider & destination, update trip status, earnings dashboard P0
FR-03 Ride Matching: Match rider with nearest/eligible driver using geospatial proximity, ETA, driver rating, and rider preferences P0
FR-04 ETA Calculation: Estimate time of arrival for both driver-to-rider and rider-to-destination using real-time traffic data P0
FR-05 Dynamic Pricing (Surge): Adjust fare based on real-time supply-demand imbalance, time of day, weather, and events P0
FR-06 Trip Tracking: Real-time GPS tracking of the active trip with periodic position updates P0
FR-07 Payment Processing: Support multiple payment methods (card, wallet, cash), split fare, tolls, tips, refunds P0
FR-08 Rating & Reviews: Two-way rating system (rider rates driver, driver rates rider) post-trip P1
FR-09 Ride History: Both rider and driver can view past trips with receipts P1
FR-10 Admin Dashboard: Monitor fleet, detect anomalies, manage pricing, view analytics, handle disputes P1
FR-11 Notifications: Push/SMS/email for ride status changes, promotions, and alerts P1
FR-12 Multi-Vendor Aggregation: Support third-party cab providers (not just in-house drivers) with unified UX P2

1.2 Non-Functional Requirements

ID Requirement Target
NFR-01 Latency: Ride request to match < 2s (p95); ETA calculation < 500ms (p95) Critical
NFR-02 Availability: 99.99% uptime for core matching & tracking services Critical
NFR-03 Consistency: Payment must be exactly-once; trip state machine must be strongly consistent Critical
NFR-04 Scalability: Support 10M DAU, 500K concurrent ride requests, 2M active drivers Critical
NFR-05 Geospatial Accuracy: Driver location accuracy within 10m; ETA within 15% of actual High
NFR-06 Security: PII encryption at rest (AES-256), TLS 1.3 in transit, GDPR/CCPA compliance Critical
NFR-07 Durability: Zero data loss for payments and trip records (RPO = 0) Critical
NFR-08 Disaster Recovery: RTO < 5 min, multi-region active-active High

2. Back-of-Envelope Calculations

2.1 Assumption Sets

We reason from first principles with three scenarios:

Parameter Conservative (A) Base (B) Aggressive (C)
DAU (riders) 5M 10M 50M
Trips per rider/day 1.2 1.5 2.0
Total trips/day 6M 15M 100M
Peak hour ratio 20% of daily 20% of daily 20% of daily
Peak trips/hour 1.2M 3M 20M
Peak QPS (trip requests) ~333 ~833 ~5,555
Active drivers 1M 2M 10M
GPS updates/sec (drivers) 167 556 3,333

Note: Peak QPS = (peak trips/hour) / 3600. We use Base (B) for primary sizing and reference others for headroom.

2.2 Storage Estimates

Trip Records

  • Average trip record size: ~2 KB (metadata, route points, fare breakdown)
  • Daily: 15M × 2 KB = 30 GB/day
  • Annual: 30 GB × 365 = ~10.9 TB/year
  • 5-year retention (hot + warm): ~55 TB

Geospatial Index (Quadtrees)

  • Active drivers: 2M, each location entry ~200 bytes
  • In-memory quadtree: 2M × 200 B = ~400 MB (fits easily in Redis cluster)
  • Historical location traces (1-day retention): 2M drivers × 1 update/sec × 86400 sec × 100 B = ~17.3 GB/day

User Profiles

  • 100M riders + 20M drivers × 5 KB/profile = ~600 GB

Media (profile photos, vehicle docs)

  • 20M drivers × 500 KB avg = ~10 GB (object storage)

Database Sizing Summary

Data Type Daily Write Daily Read Storage (5yr)
Trip records 15M 50M 55 TB
User profiles 100K 10M 600 GB
Driver locations 173M 500M In-memory (Redis)
Payments 15M 30M 30 TB
Ratings 30M 10M 60 GB
Notifications 60M 0 Ephemeral

2.3 Bandwidth Estimates

Traffic Type Calculation Throughput
Ride requests 833 QPS × 2 KB ~16.7 MB/s
GPS streaming 556 QPS × 500 B ~278 KB/s
ETA queries 2,500 QPS × 1 KB ~2.5 MB/s
Trip tracking (active) 50K concurrent × 2 Hz × 200 B ~20 MB/s
API responses 5,000 QPS × 5 KB avg ~25 MB/s
Total estimated ~65 MB/s

2.4 Infrastructure Sizing (Base Case)

Component Instances CPU Memory Notes
API Gateway 20 4C 8 GB Load balanced
Ride Matching Service 30 8C 16 GB CPU-bound (geospatial)
ETA Service 20 8C 16 GB CPU-bound (routing)
Pricing Service 10 4C 8 GB Event-driven
Trip Service 20 4C 8 GB CRUD heavy
Payment Service 15 4C 8 GB Strong consistency
Notification Service 10 2C 4 GB Async
Redis Cluster (Geo) 50 nodes 4C 32 GB 10 shards, 5 replicas
Kafka Brokers 20 8C 32 GB 3 replicas
PostgreSQL (Payments) 3 16C 64 GB Primary + 2 replicas
Cassandra (Trips) 15 8C 32 GB 3 replicas

3. System Interface Design

3.1 API Definitions

Rider APIs

POST   /api/v1/rides/request          — Request a ride
GET    /api/v1/rides/{ride_id}/status — Get ride status
GET    /api/v1/rides/{ride_id}/eta    — Get ETA updates
GET    /api/v1/rides/nearby           — List nearby available drivers
POST   /api/v1/rides/{ride_id}/cancel — Cancel a ride
GET    /api/v1/rides/history          — Rider's ride history
POST   /api/v1/rides/{ride_id}/rate   — Rate a driver
GET    /api/v1/rides/{ride_id}/fare   — Get fare estimate
POST   /api/v1/payments/charge        — Charge payment method
GET    /api/v1/payments/receipt/{ride_id} — Get receipt

Driver APIs

POST   /api/v1/drivers/status         — Go online/offline
POST   /api/v1/drivers/location       — Update GPS location
GET    /api/v1/drivers/requests       — Get pending ride requests
POST   /api/v1/drivers/requests/{id}/accept  — Accept ride
POST   /api/v1/drivers/requests/{id}/decline — Decline ride
POST   /api/v1/drivers/trip/{id}/update     — Update trip phase
GET    /api/v1/drivers/earnings       — Earnings summary
GET    /api/v1/drivers/history        — Driver's trip history

Internal Service APIs

POST   /internal/matching/request     — Submit match request
GET    /internal/geo/nearby           — Geospatial query
POST   /internal/eta/calculate        — Calculate ETA
GET    /internal/pricing/surge/{zone} — Get surge multiplier
POST   /internal/trips/create         — Create trip record
POST   /internal/trips/{id}/update    — Update trip state
POST   /internal/payments/initiate    — Initiate payment
POST   /internal/payments/{id}/settle — Settle payment

3.2 Key Request/Response Contracts

Ride Request

POST /api/v1/rides/request
{
  "pickup": { "lat": 37.7749, "lng": -122.4194 },
  "dropoff": { "lat": 37.7849, "lng": -122.4094 },
  "ride_type": "uberX",
  "passenger_count": 2,
  "payment_method_id": "pm_abc123"
}

202 Accepted
{
  "ride_id": "ride_7f8a9b0c",
  "status": "searching",
  "estimated_fare": { "min": 12.50, "max": 15.00, "currency": "USD" },
  "eta_to_pickup_sec": 300,
  "surge_multiplier": 1.0
}

Driver Location Update

POST /api/v1/drivers/location
{
  "driver_id": "drv_001",
  "lat": 37.7751,
  "lng": -122.4190,
  "heading": 45.0,
  "speed_mph": 25.0,
  "timestamp": "2026-08-28T10:30:00Z"
}

200 OK
{ "ack": true }

4. High-Level Architecture

flowchart TB
    subgraph Clients["Clients"]
        RA["Rider App"]
        DA["Driver App"]
        ADM["Admin Web"]
    end

    subgraph Edge["Edge Layer"]
        CDN["CDN / WAF"]
        LB["Load Balancer"]
        GW["API Gateway"]
    end

    subgraph Auth["Auth & Security"]
        AUTH["Auth Service<br/>(OAuth2 / JWT)"]
        RBAC["Rate Limiter"]
    end

    subgraph Core["Core Services"]
        RS["Ride Service"]
        MS["Matching Service"]
        ETA["ETA Service"]
        PS["Pricing Service"]
        TS["Trip Service"]
        PMS["Payment Service"]
        NS["Notification Service"]
        USS["User Service"]
    end

    subgraph Geo["Geospatial Layer"]
        QI["Quadtree Index<br/>(Redis Geo)"]
        GS["Geofence Service"]
        RT["Routing Engine<br/>(OSRM / GraphHopper)"]
    end

    subgraph Streaming["Streaming & Events"]
        KAFKA["Kafka Cluster"]
        GPS_S["GPS Stream"]
        RIDE_S["Ride Events"]
        PRICE_S["Price Events"]
    end

    subgraph Storage["Data Stores"]
        PG["PostgreSQL<br/>(Users, Payments)"]
        CAS["Cassandra<br/>(Trips, History)"]
        REDIS["Redis Cluster<br/>(Geo, Cache, Sessions)"]
        ES["Elasticsearch<br/>(Search, Logs)"]
        S3["S3 / Object Store<br/>(Docs, Receipts)"]
    end

    subgraph External["External Services"]
        PAYGW["Payment Gateway<br/>(Stripe / Adyen)"]
        MAPS["Maps API<br/>(Google / Mapbox)"]
        SMS["SMS / Push Gateway"]
    end

    RA --> CDN
    DA --> CDN
    ADM --> CDN
    CDN --> LB
    LB --> GW
    GW --> AUTH
    GW --> RBAC
    GW --> RS
    GW --> TS
    GW --> USS

    RS --> MS
    RS --> ETA
    RS --> PS
    RS --> PMS
    RS --> NS

    MS --> QI
    MS --> ETA

    ETA --> RT
    ETA --> MAPS

    PS --> KAFKA

    RS --> KAFKA
    MS --> KAFKA

    KAFKA --> GPS_S
    KAFKA --> RIDE_S
    KAFKA --> PRICE_S

    GPS_S --> QI
    RIDE_S --> TS
    RIDE_S --> NS
    PRICE_S --> PS

    TS --> CAS
    TS --> ES
    PMS --> PG
    PMS --> PAYGW
    USS --> PG
    NS --> SMS

    QI --> REDIS
    RT --> REDIS

5. Core Component Design

5.1 Matching Service (The Heart of the System)

The matching service is the most critical component. It must find the optimal driver for a rider request in under 2 seconds.

Matching Pipeline

flowchart LR
    A["Ride Request"] --> B["Geofence Validation"]
    B --> C["Candidate Retrieval<br/>(Quadtree Query)"]
    C --> D["ETA Filtering<br/>(< threshold)"]
    D --> E["Scoring & Ranking"]
    E --> F["Top-K Selection"]
    F --> G["Parallel Driver Poll"]
    G --> H["First Accept Wins"]
    H --> I["Lock Driver + Rider"]
    I --> J["Emit Match Event"]

    C --> K["No Candidates?"]
    K -->|"Yes"| L["Expand Radius /<br/>Broadcast"]
    L --> G

Quadtree-Based Candidate Retrieval

  • Data Structure: Hierarchical spatial partitioning using a Quadtree (or Redis GEO as production implementation)
  • Insertion: O(log N) per driver location update
  • Range Query: O(log N + K) where K = number of candidates in range
  • Fallback: If quadtree returns too few candidates, expand search radius iteratively (1km → 2km → 5km → city-wide broadcast)

Scoring Algorithm

Each candidate driver is scored using a weighted formula:

Score = w1 × (1 / ETA_to_pickup)
      + w2 × (1 / ETA_to_dropoff)
      + w3 × driver_rating_normalized
      + w4 × (1 - acceptance_rate_penalty)
      + w5 × vehicle_type_match_bonus
      + w6 × distance_to_pickup_normalized
Factor Weight Rationale
ETA to pickup 0.30 Primary user-facing metric
ETA to dropoff 0.15 Avoids assigning drivers that create long deadhead
Driver rating 0.15 Quality of service
Acceptance rate 0.10 Penalizes drivers who frequently decline
Vehicle match 0.10 Rider requested specific type
Distance 0.20 Closer is generally better

Driver Polling Strategy

  1. Top-K parallel poll: Send request to top K drivers simultaneously (K = 3-5)
  2. Acceptance timeout: 15 seconds per driver
  3. First accept wins: Atomic lock prevents double-assignment
  4. Fallback: If all decline, retry with next batch of candidates
  5. Broadcast: After 3 rounds, broadcast to all available drivers in zone

5.2 ETA Service

Architecture

flowchart TB
    REQ["ETA Request"] --> CACHE["Cache Check<br/>(Redis)"]
    CACHE -->|"Hit"| RETURN["Return Cached ETA"]
    CACHE -->|"Miss"| ROUTE["Routing Engine"]
    ROUTE --> TRAFFIC["Real-Time Traffic Data"]
    ROUTE --> HIST["Historical Patterns"]
    TRAFFIC --> ML["ML ETA Model"]
    HIST --> ML
    ML --> RESULT["ETA Result"]
    RESULT --> CACHE
    RESULT --> RETURN

ETA Calculation Layers

Layer Source Latency Accuracy
L1: Haversine Straight-line distance / avg speed < 1ms Low (baseline)
L2: Road Network OSRM/GraphHopper shortest path 50-200ms Medium
L3: Real-Time Traffic Live congestion data + L2 200-500ms High
L4: ML Prediction Historical patterns + weather + events 500-1000ms Highest
  • Caching: Route-based cache with 5-minute TTL; key = (pickup_hash, dropoff_hash, time_bucket)
  • Degradation: L4 → L3 → L2 → L1 on latency pressure

5.3 Dynamic Pricing (Surge) Service

Pricing Formula

Final Fare = Base Fare × Distance Factor × Time Factor × Surge Multiplier × Vehicle Multiplier

Surge Multiplier Calculation

flowchart LR
    A["Zone Demand"] --> D["Demand/Supply Ratio"]
    B["Zone Supply"] --> D
    C["External Factors<br/>(Weather, Events)"] --> D
    D -->|"Ratio > 1.5"| S["Surge Up<br/>×1.1 per 30s"]
    D -->|"Ratio < 0.8"| SD["Surge Down<br/>×0.95 per 30s"]
    D -->|"0.8-1.5"| ST["Stable<br/>×1.0"]
    S --> CAP["Cap at ×3.0"]
    SD --> FLOOR["Floor at ×1.0"]
    CAP --> OUT["Publish Surge"]
    FLOOR --> OUT
    ST --> OUT
  • Geofencing: City divided into hexagonal zones (H3 library, resolution 7)
  • Update frequency: Every 30 seconds per zone
  • Smoothing: Exponential moving average to prevent oscillation
  • Caps: Maximum 3× surge; minimum 1× (no discount below base)

5.4 Trip Service

Trip State Machine

stateDiagram-v2
    [*] --> REQUESTED
    REQUESTED --> SEARCHING
    SEARCHING --> MATCHED
    SEARCHING --> CANCELLED_RIDER
    SEARCHING --> CANCELLED_NO_DRIVER
    MATCHED --> DRIVER_ACCEPTED
    MATCHED --> DRIVER_DECLINED
    DRIVER_DECLINED --> SEARCHING
    DRIVER_ACCEPTED --> DRIVER_EN_ROUTE
    DRIVER_EN_ROUTE --> ARRIVED_AT_PICKUP
    ARRIVED_AT_PICKUP --> RIDER_BOARDING
    RIDER_BOARDING --> IN_PROGRESS
    IN_PROGRESS --> COMPLETED
    IN_PROGRESS --> CANCELLED_ENROUTE
    COMPLETED --> PAYMENT_PENDING
    PAYMENT_PENDING --> PAYMENT_SUCCESS
    PAYMENT_PENDING --> PAYMENT_FAILED
    PAYMENT_SUCCESS --> [*]
    PAYMENT_FAILED --> DISPUTE
    CANCELLED_RIDER --> [*]
    CANCELLED_NO_DRIVER --> [*]
    CANCELLED_ENROUTE --> [*]
    DISPUTE --> RESOLVED
    RESOLVED --> [*]

5.5 Payment Service

Payment Flow

sequenceDiagram
    participant R as Rider
    participant TS as Trip Service
    participant PS as Payment Service
    participant PG as Payment Gateway
    participant DB as Payment DB
    participant D as Driver

    TS->>PS: initiate_payment(ride_id, amount)
    PS->>PG: authorize(payment_method, amount)
    PG-->>PS: auth_token
    PS->>DB: record authorization
    PS-->>TS: payment_authorized

    Note over TS,D: Trip completes...

    TS->>PS: settle_payment(ride_id, final_amount)
    PS->>PG: capture(auth_token, final_amount)
    PG-->>PS: capture_success
    PS->>DB: record settlement
    PS->>PS: split fare (platform, driver)
    PS->>D: credit driver earnings
    PS-->>TS: payment_complete
    TS->>R: send receipt
  • Idempotency: Every payment operation carries an idempotency key
  • Split payments: Platform commission (20-25%) vs. driver earnings settled in separate ledgers
  • Reconciliation: Daily batch reconciliation with payment gateway

5.6 Real-Time Tracking Service

  • Protocol: WebSocket for bidirectional real-time updates
  • Update frequency: Driver app sends GPS every 2-5 seconds; throttled to 2 Hz server-side
  • **Interpolated positions broadcast to rider’s WebSocket connection
  • Interpolation: Linear interpolation between GPS points for smooth animation
  • Persistence: GPS traces written to Kafka → compacted to Cassandra (1-day hot, 30-day warm)

6. Data Model

6.1 Relational Schema (PostgreSQL — Users, Payments)

-- Users
CREATE TABLE users (
    user_id         UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    email           VARCHAR(255) UNIQUE NOT NULL,
    phone           VARCHAR(20) UNIQUE NOT NULL,
    name            VARCHAR(255) NOT NULL,
    role          VARCHAR(20) NOT NULL CHECK (role IN ('rider', 'driver', 'admin')),
    status          VARCHAR(20) DEFAULT 'active',
    created_at      TIMESTAMPTZ DEFAULT NOW(),
    updated_at      TIMESTAMPTZ DEFAULT NOW()
);

-- Driver profiles
CREATE TABLE drivers (
    driver_id       UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    user_id         UUID REFERENCES users(user_id) UNIQUE,
    vehicle_make    VARCHAR(100),
    vehicle_model   VARCHAR(100),
    vehicle_year    INT,
    license_plate   VARCHAR(20) UNIQUE,
    rating          DECIMAL(3,2) DEFAULT 5.00,
    total_trips     INT DEFAULT 0,
    acceptance_rate DECIMAL(5,4) DEFAULT 0.0000,
    is_online       BOOLEAN DEFAULT FALSE,
    current_lat     DECIMAL(10,7),
    current_lng     DECIMAL(10,7),
    created_at      TIMESTAMPTZ DEFAULT NOW()
);

-- Payment methods
CREATE TABLE payment_methods (
    pm_id           UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    user_id         UUID REFERENCES users(user_id),
    type            VARCHAR(20) NOT NULL, -- 'card', 'wallet', 'cash'
    provider_ref    VARCHAR(255),         -- Stripe token etc.
    is_default      BOOLEAN DEFAULT FALSE,
    created_at      TIMESTAMPTZ DEFAULT NOW()
);

-- Payment transactions
CREATE TABLE payment_transactions (
    txn_id          UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    ride_id         UUID NOT NULL,
    user_id         UUID REFERENCES users(user_id),
    driver_id       UUID REFERENCES drivers(driver_id),
    amount          DECIMAL(10,2) NOT NULL,
    currency        VARCHAR(3) DEFAULT 'USD',
    status          VARCHAR(20) NOT NULL, -- 'authorized', 'captured', 'refunded', 'failed'
    provider_txn_id VARCHAR(255),
    idempotency_key VARCHAR(64) UNIQUE NOT NULL,
    created_at      TIMESTAMPTZ DEFAULT NOW(),
    settled_at      TIMESTAMPTZ
);

-- Ratings
CREATE TABLE ratings (
    rating_id       UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    ride_id         UUID NOT NULL,
    rater_id        UUID NOT NULL,
    ratee_id        UUID NOT NULL,
    score           INT CHECK (score BETWEEN 1 AND 5),
    comment         TEXT,
    created_at      TIMESTAMPTZ DEFAULT NOW(),
    UNIQUE(ride_id, rater_id, ratee_id)
);

6.2 NoSQL Schema (Cassandra — Trips)

-- Trip records (partitioned by user for fast history lookup)
CREATE TABLE trips_by_rider (
    rider_id        UUID,
    ride_id         UUID,
    driver_id       UUID,
    pickup_lat      DECIMAL,
    pickup_lng      DECIMAL,
    dropoff_lat     DECIMAL,
    dropoff_lng     DECIMAL,
    status          TEXT,
    fare            DECIMAL,
    surge_mult      DECIMAL,
    started_at      TIMESTAMP,
    completed_at    TIMESTAMP,
    created_at      TIMESTAMP,
    PRIMARY KEY ((rider_id), created_at, ride_id)
) WITH CLUSTERING ORDER BY (created_at DESC);

-- Trip GPS traces (partitioned by ride_id)
CREATE TABLE trip_gps_traces (
    ride_id         UUID,
    timestamp       TIMESTAMP,
    lat             DECIMAL,
    lng             DECIMAL,
    speed           DECIMAL,
    heading         DECIMAL,
    PRIMARY KEY ((ride_id), timestamp)
) WITH COMPACT STORAGE;

6.3 Redis Geo Schema

# Driver locations (geo-indexed)
GEOADD drivers:active 37.7749 -122.4194 drv_001
GEOADD drivers:active 37.7849 -122.4094 drv_002

# Query nearby drivers (within 5km)
GEORADIUS drivers:active 37.7749 -122.4194 5 km WITHCOORD WITHDIST

# Driver detail cache
HSET driver:drv_001 rating 4.8 vehicle uberX online 1

# Surge multipliers per H3 zone
HSET surge:multipliers h3_8928308280 1.5 h3_8928308281 1.2

# Ride state cache
HSET ride:ride_abc status MATCHED driver drv_001 eta 300
EXPIRE ride:ride_abc 3600

7. Key Design Decisions

7.1 Decision Matrix

Decision Option A Option B Chosen Rationale
Geospatial Index PostGIS (R-Tree) Redis GEO / Quadtree Redis GEO Sub-ms latency for hot data; PostGIS too slow for 500K QPS location queries
Trip Storage PostgreSQL Cassandra Cassandra Write-heavy (15M trips/day); Cassandra handles 100K+ writes/sec per node with tunable consistency
Payment Storage Cassandra PostgreSQL PostgreSQL ACID required for financial data; exactly-once semantics
Real-time Comms REST polling WebSocket WebSocket 2 Hz GPS updates; polling would generate 100× more requests
Matching Strategy Centralized queue Geospatial broadcast Geospatial broadcast Scales with city size; no single bottleneck
Surge Computation Centralized Zone-local Zone-local Decouples cities; each zone computes independently
Event Transport RabbitMQ Kafka Kafka Higher throughput, replayability, partition-based scaling
Routing Engine Google Maps API Self-hosted OSRM Hybrid OSRM for internal routing; Google for address geocoding and fallback

7.2 Trade-off Deep Dives

Redis GEO vs. Custom Quadtree

Aspect Redis GEO Custom Quadtree
Latency < 1ms < 1ms (in-process)
Operational overhead Low (managed) High (self-hosted)
Consistency Approximate (GeoHash) Exact
Scaling Sharded Redis cluster Manual partitioning
Rich queries Radius only Arbitrary polygons

Decision: Redis GEO for primary indexing (speed + ops simplicity); custom quadtree in Matching Service for complex polygon queries (geofences, no-ride zones).

Cassandra vs. NewSQL for Trips

Aspect Cassandra CockroachDB / Spanner
Write throughput 100K+/sec/node 50K+/sec/node
Read latency P99 ~10ms P99 ~5ms
Operational complexity Medium High
Global consistency Tunable (QUORUM) Strong (default)
Cost Lower Higher

Decision: Cassandra for trip records (write-heavy, eventual consistency acceptable); PostgreSQL for payments (strong consistency mandatory).


8. Scalability Strategy

8.1 Horizontal Scaling Plan

flowchart TB
    subgraph City1["City: San Francisco"]
        GW1["API Gateway Pool"]
        MS1["Matching Pool"]
        GEO1["Redis Geo Shard A-D"]
    end

    subgraph City2["City: New York"]
        GW2["API Gateway Pool"]
        MS2["Matching Pool"]
        GEO2["Redis Geo Shard E-H"]
    end

    subgraph City3["City: London"]
        GW3["API Gateway Pool"]
        MS3["Matching Pool"]
        GEO3["Redis Geo Shard I-L"]
    end

    subgraph Global["Global Services"]
        PAY["Payment Service"]
        USR["User Service"]
        KAFKA["Kafka (cross-region)"]
    end

    GW1 --> MS1 --> GEO1
    GW2 --> MS2 --> GEO2
    GW3 --> MS3 --> GEO3
    MS1 --> PAY
    MS2 --> PAY
    MS3 --> PAY
    MS1 --> KAFKA
    MS2 --> KAFKA
    MS3 --> KAFKA

8.2 Scaling Dimensions

Dimension Strategy Trigger
Geographic City-level sharding Each city gets isolated service pools
Compute Auto-scaling groups (K8s HPA) CPU > 70% for 3 min
Database Cassandra ring expansion Write latency > 50ms p99
Cache Redis shard addition Memory > 75% or hit ratio < 90%
Streaming Kafka partition increase Consumer lag > 10K messages
WebSocket Connection sharding by user_id Connections per proxy > 50K

8.3 Caching Strategy

Cache Layer TTL Eviction Hit Ratio Target
L1: In-process (Caffeine) 30s LRU 40%
L2: Redis (per-city) 5 min LRU + TTL 85%
L3: CDN (static assets) 24h Age 95%

8.4 Database Partitioning

  • PostgreSQL: Table partitioning by created_at (monthly) for payments; by user_id hash for users
  • Cassandra: Composite primary keys with rider_id as partition key; hot partition mitigation via salted keys
  • Redis: Key hash tagging — driver:{city_hash}:{driver_id} for shard affinity

9. Curveball Scenarios

Curveball 1: “A major concert ends — 50,000 riders request rides from the same venue in 10 minutes. Design the system to handle this.”

Analysis

  • Spike magnitude: 50K requests in 10 min = ~83 QPS concentrated in a 1km² area
  • Supply constraint: Only ~200-500 drivers available nearby
  • Key challenges: Matching bottleneck, surge pricing fairness, rider experience during wait

Response

1. Demand Management

  • Virtual queuing: Riders beyond immediate match capacity enter a virtual queue with estimated wait time
  • Queue transparency: Show position in queue and expected wait; allow cancellation with penalty-free exit window
  • Staggered matching: Release queued riders in batches as drivers complete trips and become available

2. Supply Incentives

  • Heatmap push: Notify all offline drivers within 10km of high demand with elevated incentives
  • Destination signs: Show drivers the dropoff hotspot so they know where demand is concentrated
  • Completion bonus: Extra $5-10 for trips originating from the event zone

3. Surge Pricing

  • Rapid surge: Multiplier jumps to 2.5× within 2 minutes, caps at 3.0×
  • Gradual decay: After event dispersal, surge decays exponentially (half-life = 15 min)
  • Price ceiling enforcement: Regulatory compliance — cap at local maximum

4. Matching Optimization

  • Batch matching: Instead of 1:1 matching, use auction-based batch matching every 30 seconds
  • Multi-passenger option: Offer shared rides (pool) at lower price to maximize throughput
  • Extended radius: Temporarily expand search radius from 3km to 10km

5. System Resilience

  • Rate limiting per zone: Prevent API overload from retry storms
  • Circuit breaker: If matching latency > 5s, fall back to simplified nearest-neighbor matching
  • Async queue: Ride requests buffered in Kafka; processed at sustainable rate

Curveball 2: “Design a feature where riders can schedule rides up to 30 days in advance. How does this change the system?”

Analysis

  • New dimension: Temporal matching (not just spatial)
  • Uncertainty: Driver availability 30 days out is unknown
  • Commitment: Both parties need guarantees

Response

1. Two-Phase Matching

  • Phase 1 (Pre-schedule): Rider schedules → system creates a “pending request” with time window
  • Phase 2 (Pre-ride matching): 30-60 minutes before scheduled time, run normal matching with priority
  • Guarantee tier: Offer “Guaranteed Ride” at premium (system reserves capacity via driver incentives)

2. Driver Pre-Commitment

  • Shift bidding: Drivers can bid on scheduled rides in their area/time slot
  • Guaranteed earnings: Driver who accepts gets guaranteed minimum earnings for that slot
  • Penalty for no-show: Driver forfeits bonus if they don’t show up

3. Data Model Changes

CREATE TABLE scheduled_rides (
    schedule_id     UUID PRIMARY KEY,
    rider_id        UUID,
    pickup_time     TIMESTAMPTZ NOT NULL,
    pickup          GEOGRAPHY(POINT),
    dropoff         GEOGRAPHY(POINT),
    status          VARCHAR(20), -- 'scheduled', 'matching', 'confirmed', 'completed', 'cancelled'
    guarantee_tier  VARCHAR(20), -- 'standard', 'guaranteed'
    driver_id       UUID NULL,   -- NULL until matched
    reminder_sent   BOOLEAN DEFAULT FALSE,
    created_at      TIMESTAMPTZ DEFAULT NOW()
);

CREATE INDEX idx_scheduled_rides_time ON scheduled_rides(pickup_time);
CREATE INDEX idx_scheduled_rides_status ON scheduled_rides(status, pickup_time);

4. Scheduler Service

  • Cron-like processor: Scans scheduled_rides where pickup_time - NOW() < 60min and status = 'scheduled'
  • Priority injection: Scheduled rides injected into matching queue with elevated priority score
  • Reminder pipeline: Push notification 30 min and 5 min before pickup

5. Capacity Planning

  • Demand forecasting: Use scheduled ride data to predict future demand hotspots
  • Driver dispatch: Proactively position drivers near expected pickup zones

Curveball 3: “A competitor launches in your city with 50% lower prices. Design a response strategy at the system level.”

Analysis

  • Business threat: Price-sensitive riders may churn
  • System implications: Need dynamic competitive pricing, retention features, and data-driven decisions

Response

1. Competitive Intelligence Pipeline

  • Price scraping service: Monitor competitor pricing in real-time (web scraping + API)
  • Zone-level comparison: Compare prices per H3 zone, not just city-wide
  • Alert system: Trigger alerts when competitor price < our price × 0.8

2. Dynamic Counter-Pricing

If competitor_price < our_price × 0.8:
    If rider is new (first 3 rides):
        Match competitor price (loss leader)
    Elif rider is high-value (LTV > threshold):
        Offer targeted coupon (10-20% off)
    Else:
        Hold price, improve non-price value (faster ETA, better cars)

3. Retention Feature Rollout

  • Loyalty program: Points-based system integrated into the platform
  • Subscription tier: Monthly flat fee for discounted rides (reduces price sensitivity)
  • Referral amplification: Double referral bonuses during competitive periods

4. System-Level Changes

  • Promotion engine: New service to manage targeted, zone-specific, time-bound promotions
  • A/B testing framework: Test price elasticity in controlled zones
  • Churn prediction ML: Flag at-risk riders for proactive retention offers

5. Supply-Side Defense

  • Driver retention: Increase driver incentives to prevent supply drain
  • Exclusivity deals: Offer guaranteed minimum earnings to top-rated drivers

Curveball 4: “Regulators require you to share real-time trip data with city authorities. Design the compliance system.”

Response

1. Data Pipeline

  • Real-time feed: Kafka topic regulatory:trip_feed with trip events streamed to government API
  • Data minimization: Share only required fields (pickup, dropoff, timestamps, anonymized IDs)
  • PII redaction: Automatic PII stripping before regulatory export

2. Architecture

flowchart LR
    TS["Trip Service"] --> K["Kafka: regulatory_feed"]
    K --> REDACT["PII Redaction Service"]
    REDACT --> VALIDATE["Schema Validator"]
    VALIDATE --> GOV["Government API Gateway"]
    GOV --> AUDIT["Audit Log (immutable)"]

3. Compliance Features

  • Audit trail: Immutable log of all data shared (who, what, when)
  • Consent management: Rider opt-in/opt-out tracking
  • Data retention: Automatic deletion after regulatory retention period expires

10. Failure Modes and Mitigations

10.1 Failure Mode Analysis

Failure Mode Impact Probability Mitigation
Redis Geo cluster failure Matching stops; no driver discovery Low Multi-AZ Redis; fallback to PostGIS; cached driver list
Kafka broker failure Event loss; GPS stream interruption Low 3x replication; ISR-based acknowledgment; local buffering
Payment gateway timeout Riders charged but trip not recorded Medium Idempotent retries; compensating transactions; manual reconciliation queue
Matching service overload Ride requests timeout Medium Circuit breaker → broadcast fallback; request queuing; auto-scale
GPS signal loss (driver) Rider sees stale driver position Medium Last-known-location interpolation; estimated position based on route
Database split-brain Inconsistent trip/payment state Very Low Quorum-based writes; fencing tokens; automatic failover
WebSocket connection drop Real-time tracking stops Medium Auto-reconnect with last-seen position; SSE fallback
Surge pricing oscillation Prices fluctuate wildly Low EMA smoothing; minimum dwell time at each level; human override
DDoS attack Service unavailable Medium WAF + rate limiting + CDN absorption + auto-scaling
Region outage Entire city offline Very Low Multi-region active-active; DNS-based failover; graceful degradation

10.2 Disaster Recovery Plan

flowchart TB
    subgraph Primary["Primary Region (US-East)"]
        APP1["All Services"]
        DB1["DB Primary"]
    end

    subgraph Secondary["Secondary Region (US-West)"]
        APP2["All Services (standby)"]
        DB2["DB Replica"]
    end

    APP1 -->|"Async replication"| DB2
    DB1 -->|"Async replication"| DB2
    DNS["Global DNS"] -->|"Health check"| APP1
    DNS -->|"Failover"| APP2

    HEALTH["Health Monitor"] -->|"Detect failure"| DNS
    DNS -->|"Switch traffic"| APP2
  • RPO: < 1 minute (async replication lag)
  • RTO: < 5 minutes (automated DNS failover + warm standby)
  • Failover drill: Quarterly automated failover testing

10.3 Observability Stack

Component Tool Purpose
Metrics Prometheus + Grafana Latency, throughput, error rates, business KPIs
Tracing Jaeger / OpenTelemetry End-to-end request tracing across services
Logging ELK Stack Centralized structured logging
Alerting PagerDuty On-call alerts with auto-escalation
APM Datadog Application performance monitoring
Business Dashboard Custom Grafana Trips/hour, match rate, avg ETA, surge map

10.4 Key SLOs

Service SLO Measurement
Ride Matching 99.9% success within 2s Match latency histogram
ETA Service 99.5% within 500ms ETA calculation latency
Payment Processing 99.99% success rate Payment success ratio
GPS Tracking 99.9% uptime WebSocket connection uptime
Overall Platform 99.99% availability Error budget: 52 min/year downtime

Appendix A: Glossary

Term Definition
Quadtree Tree data structure where each internal node has exactly four children; used for 2D spatial partitioning
H3 Uber’s open-source hexagonal hierarchical spatial index system
OSRM Open Source Routing Machine — fast routing engine
Surge Pricing Dynamic pricing that increases fares during high-demand, low-supply periods
Deadhead Distance a driver travels empty (without a passenger)
ETA Estimated Time of Arrival

Appendix B: References