Design a Real-Time Ride-Sharing Dispatch Service (Uber/Lyft)

1. Problem Statement & Scope Clarification

System Mission

Design a mission-critical, real-time ride-matching, dispatch, and dynamic surge pricing platform (equivalent to Uber, Lyft, or Grab) capable of ingesting high-frequency GPS telemetry from over 1 Million active drivers every 4 seconds, matching rider trip requests with the optimal available driver in under 1 second, orchestrating multi-driver offer cascades via distributed step leases, and computing localized supply-and-demand surge multipliers across discrete hexagonal spatial grids without double-booking or driver starvation.

At a glance:

Functional Requirements

1. Real-Time Driver Telemetry Ingestion (UpdateDriverLocation): Ingest live GPS coordinates (latitude, longitude, bearing, speed, driver_status) from 1 Million active drivers every 4 seconds with sub-50ms ingestion latency.
2. Nearby Driver Discovery & ETA Estimation: When a rider opens the app, retrieve the top $N$ nearby available drivers within a $5\text{ km}$ radius along with estimated pickup ETAs in $< 300\text{ ms}$.
3. Trip Request & Candidate Ring Dispatching: Ingest trip requests with pickup and dropoff coordinates, compute an expanding candidate driver ring (sorted by pickup ETA, driver rating, and acceptance probability), and dispatch sequential or batched 15-second exclusive offers.
4. Atomic Match Acceptance & Anti-Double-Booking: Guarantee that exactly one driver is assigned to a trip request. Prevent race conditions where two drivers accept overlapping offers simultaneously or two riders book the same driver.
5. Localized Dynamic Surge Pricing: Continuously evaluate live supply (available drivers) versus demand (ride requests and app opens) across Uber H3 hexagonal cells, dynamically adjusting trip fares with spatial smoothing to prevent gaming.
6. Trip Lifecycle State Machine: Enforce strict, monotonic state transitions across the trip lifecycle (REQUESTED $\to$ OFFERED $\to$ MATCHED $\to$ ARRIVING $\to$ IN_TRIP $\to$ COMPLETED / CANCELLED).

Non-Functional Requirements (SLAs & SLOs)

• Ultra-Low Latency:
  • Location Ingestion Path: $P99 < 50\text{ ms}$.
  • Driver Discovery (Pre-dispatch): $P99 < 300\text{ ms}$.
  • Match-Making Offer Dispatch: $P95 < 500\text{ ms}$, $P99 < 1.0\text{ second}$.
• Planetary Availability: $99.999\%$ uptime SLA for location ingestion and dispatch services ($< 5.26\text{ minutes}$ unscheduled downtime/year).
• Strict Consistency on Match Assignment: Zero double-booking invariant. A driver can be assigned to at most one active trip at any millisecond.
• Scalability: Sustain 1 Million active concurrent drivers, 10 Million completed trips/day, and up to 5,000 peak ride booking requests per second.

---

2. Capacity & Scale Estimation (Back-of-the-Envelope Math)

Driver Telemetry Volume & Ingestion Throughput (QPS)

• Active Concurrent Drivers: $1,000,000\text{ drivers}$ ($1\text{M}$).
• Driver GPS Broadcast Frequency: 1 ping every 4 seconds ($0.25\text{ Hz}$).
• Average Driver Ingestion QPS: $\text{QPS}_{\text{driver, avg}} = \frac{1,000,000\text{ drivers}}{4\text{ seconds}} = \mathbf{250,000\text{ writes/sec}}$
• Peak Driver Ingestion QPS ($2\times$ weekend evening / bad-weather rush): $\text{QPS}_{\text{driver, peak}} = 250,000 \times 2 = \mathbf{500,000\text{ writes/sec}}$

Rider Demand & Trip Booking Throughput

• Daily Completed Trips: $10,000,000\text{ trips/day}$ ($10\text{M}$).
• Average Completed Trip QPS: $\text{QPS}_{\text{trip, avg}} = \frac{10 \times 10^6}{86,400\text{ sec}} \approx \mathbf{115.7\text{ trips/sec}}$
• Peak Trip Booking QPS ($10\times$ diurnal peak + flash surges): $\text{QPS}_{\text{booking, peak}} \approx 115.7 \times 10 \approx \mathbf{1,157\text{ bookings/sec}} \quad (\text{dimensioned for } \mathbf{2,500\text{ QPS}})$
• Active Rider App Views (Nearby Driver Search):
  • $5\times$ more riders are viewing maps than booking rides: $\text{QPS}_{\text{rider search, peak}} = 2,500 \times 5 = \mathbf{12,500\text{ search QPS}}$

Storage Footprint & Bandwidth Sizing

• Driver Location Telemetry Packet Size: driver_id (16B UUID), lat (8B float64), lon (8B float64), bearing (2B), speed_mps (2B), status (1B: AVAILABLE, DISPATCHED, ON_TRIP), timestamp (8B) $\approx 45\text{ bytes}$ (with transport envelope $\approx 100\text{ bytes}$).
• Peak Telemetry Ingress Bandwidth: $\text{Bandwidth}_{\text{in}} = 500,000\text{ writes/sec} \times 100\text{ bytes} = 50\text{ MB/sec} = \mathbf{400\text{ Mbps}}$
• Active Driver Ephemeral Location Cache (Amazon MemoryDB / Redis): $1,000,000\text{ drivers} \times 200\text{ bytes (hash + index)} \approx \mathbf{200\text{ MB RAM}}$
• Persistent Trip Record (Aurora PostgreSQL): trip_id (16B), rider_id (16B), driver_id (16B), pickup_lat/lon (16B), dropoff_lat/lon (16B), fare_cents (8B), surge_multiplier (4B), status (16B), timestamps $\approx 1,000\text{ bytes } (1\text{ KB})$. $\text{Daily Master Trip Storage} = 10 \times 10^6 \times 1\text{ KB} = \mathbf{10\text{ GB/day}} \implies \mathbf{3.65\text{ TB/year}}$
• Raw Telemetry Historical Audit Lake (Amazon S3 - 30-Day Retention): $50\text{ MB/sec} \times 86,400\text{ sec/day} \times 30\text{ days} \approx \mathbf{129.6\text{ TB/month}}$

---

3. AWS-First High-Level Architecture

The architecture decouples the high-write driver telemetry ingestion plane from the ACID trip dispatch state machine and the real-time surge pricing streaming pipeline.

Synthesizing vector architecture diagram...

Follow a driver and a rider until they are matched. In the "Driver Ingestion & Connection Plane" panel, each driver's phone sends GPS every 4 s over a WebSocket, and the pings are batched into Kinesis. In the "Live Geospatial State Tier" panel, a stream worker writes each driver's latest position into MemoryDB, indexed by H3 cell. In the "Rider Ingress & Match Dispatch Tier" panel, a ride request asks the dispatch engine for the best nearby drivers (1), then starts a Step Functions offer saga (2), which takes an atomic compare-and-set lease on a driver in DynamoDB (3), so no other rider can be offered that driver, and pushes the offer (4); if the driver does not accept within 15 s, the lease is released and the next driver is tried. In the "Streaming Surge Pricing Engine" panel, Flink compares driver supply with rider searches per cell to set surge prices, and completed trips are recorded in Aurora. The CAS lease is what prevents double-booking, even with many dispatchers running in parallel.

Data Flow Walkthrough

1. Driver Telemetry Stream: Active drivers maintain open WSS connections to the ECS Driver WebSocket fleet behind an AWS NLB. Every 4 seconds, devices emit a binary GPS packet. The WebSocket workers validate tokens and batch pings into an Amazon Kinesis Data Stream (128 shards with KPL record aggregation: the $1\text{ MB/s}$ per-shard byte limit binds at $50\text{ MB/s} \to 50$ shards minimum, provisioned as 128 for burst headroom; without aggregation the $1{,}000$ records/s limit would demand 500 shards for $500\text{k pings/sec}$).
2. Spatial Index Update: ECS Location Processors consume the Kinesis stream, converting each driver's coordinate into an Uber H3 Resolution 8 index ($\approx 461\text{m}$ edge length). The processor atomically updates the driver's location hash, moves the driver ID from the previous cell's set to the new cell's set (SREM old, SADD new, in one pipeline), and refreshes the $15\text{ s}$ hash TTL in Amazon MemoryDB for Redis. Because sets have no per-member TTL, readers always confirm EXISTS loc:driver:<id> before offering a driver, which filters out drivers whose hash expired after a disconnect.
3. Rider Search & Pre-Dispatch ETA: When a rider opens the app, the client dispatches a search query. The Dispatch Service queries MemoryDB for available drivers with a progressively expanding H3 ring around the pickup cell: $k=2$ first (19 hexagons, guaranteed reach $\approx 2.0\text{ km}$ at Resolution 8, enough in a dense city), then $k=4$ (61 cells, $\approx 3.6\text{ km}$) and $k=6$ (127 cells, $\approx 5.2\text{ km}$, the full $5\text{ km}$ search radius) only while fewer than 8 available drivers have been found. The nearest 8 drivers and estimated arrival ETAs are returned in $< 200\text{ ms}$.
4. Trip Booking & Match Saga Launch: When the rider taps "Request Ride", the Dispatch Service calculates the fare with live surge multipliers from Redis and creates an initial trip record marked REQUESTED in Amazon Aurora PostgreSQL. It then launches an AWS Step Functions Express Workflow to orchestrate the dispatch offer cascade.
5. Exclusive 15-Second Driver Offer: The Step Functions workflow selects the candidate driver with the lowest pickup ETA and attempts an atomic lease acquisition in Amazon DynamoDB as a single TransactWriteItems with two conditional puts: the trip's offer row (TRIP#<trip_id>/OFFER, condition attribute_not_exists(PK) OR ExpiresAt < :now) and the driver's global lock row (DRIVER#<driver_id>/LOCK, condition attribute_not_exists(PK)). Either both succeed or neither does, so a driver can never hold offers for two trips and a trip can never have two live offers. A push notification is dispatched to the driver's mobile device with a 15-second countdown timer.
6. Acceptance or Cascade Transition:
   • Acceptance Path: The driver taps "Accept" within 15 seconds. The mobile client calls POST /v1/trips/{id}/accept. The backend updates DynamoDB to COMMITTED, transitions the Aurora trip record to MATCHED, assigns the driver's state in MemoryDB to ON_TRIP, and pushes a WebSocket confirmation to the rider.
   • Rejection / Timeout Cascade: If the driver declines or the 15-second timer fires, the Step Functions state machine marks the offer EXPIRED in DynamoDB and cascades immediately to the next nearest candidate driver in the dispatch ring.

Core Request Tracing Execution Walkthrough

---

4. API Interface Design & Wire Protocols

1. Request a Ride (POST /v1/trips)

Initiates a ride dispatch request with pickup, dropoff, and vehicle tier specifications.

Request Headers & Payload

httpCopy
POST /v1/trips HTTP/1.1
Host: dispatch.rides.platform.aws.internal
Authorization: Bearer jwt_rdr_live_88192a0e
Idempotency-Key: idemp_trip_req_99a8b7c6d5e4
Content-Type: application/json

jsonCopy
{
  "rider_id": "usr_rdr_77182930",
  "pickup_location": {
    "latitude": 37.774929,
    "longitude": -122.419416,
    "street_address": "1355 Market St, San Francisco, CA"
  },
  "dropoff_location": {
    "latitude": 37.789172,
    "longitude": -122.401449,
    "street_address": "Union Square, San Francisco, CA"
  },
  "vehicle_tier": "UBER_X",
  "fare_quote_id": "quote_fx_8819203a"
}

Response: 201 Created

jsonCopy
{
  "trip_id": "trip_live_99a8b7c6d5e4",
  "status": "SEARCHING_FOR_DRIVER",
  "fare_cents": 1850,
  "currency": "USD",
  "surge_multiplier": 1.35,
  "pickup_eta_seconds": 240,
  "created_at": "2026-09-16T14:32:00.120Z"
}

2. Driver Accepts Ride Offer (POST /v1/trips/{trip_id}/accept)

Called by the driver app within the 15-second offer window.

httpCopy
POST /v1/trips/trip_live_99a8b7c6d5e4/accept HTTP/1.1
Host: dispatch.rides.platform.aws.internal
Authorization: Bearer jwt_drv_live_44019283
Content-Type: application/json

{
  "driver_id": "drv_10293847",
  "offer_token": "off_tok_88192a0e7182",
  "current_coordinates": {
    "latitude": 37.776102,
    "longitude": -122.417291
  }
}

Response: 200 OK(Accepted)

jsonCopy
{
  "trip_id": "trip_live_99a8b7c6d5e4",
  "status": "MATCHED",
  "rider_name": "Sarah T.",
  "rider_rating": 4.9,
  "pickup_location": {
    "latitude": 37.774929,
    "longitude": -122.419416,
    "street_address": "1355 Market St"
  },
  "route_polyline": "u{~nFjk`uVv]fYtXo\\rUqV..."
}

Response: 409 Conflict(Expired or Already Taken)

jsonCopy
{
  "error": {
    "code": "OFFER_EXPIRED_OR_ACCEPTED_BY_ANOTHER",
    "message": "This ride offer has expired or was accepted by another driver.",
    "trip_id": "trip_live_99a8b7c6d5e4"
  }
}

---

5. Data Models & Storage Architecture

Database Selection Justification

1. Amazon MemoryDB for Redis (Cluster Mode): Chosen for the ultra-fast active driver geospatial index. MemoryDB provides in-memory read latencies ($< 1\text{ ms}$) backed by a multi-AZ distributed transactional write-ahead log for persistence, ensuring zero driver location loss during shard failovers.
2. Amazon DynamoDB: Chosen for atomic driver offer leases. DynamoDB's strongly consistent reads and conditional writes (attribute_not_exists) guarantee that two drivers can never accept the same offer simultaneously.
3. Amazon Aurora PostgreSQL Multi-AZ: Master ACID datastore for persistent trip lifecycles, user financial transactions, and billing receipts.

1. In-Memory Geospatial Layout (Uber H3 Spatial Index in MemoryDB)

textCopy
1. Active Drivers in Hexagonal Cell:
   Key:    h3:8:<h3_resolution_8_index>:drivers
   Example: h3:8:8828308281fffff:drivers
   Type:   SET
   Members: [ "drv_101", "drv_102", "drv_105", ... ]

2. Live Driver Telemetry Hash:
   Key:    loc:driver:<driver_id>
   Type:   HASH
   Fields: {
             "lat": "37.774929",
             "lon": "-122.419416",
             "bearing": "182.5",
             "status": "AVAILABLE", // AVAILABLE, OFFERED, ON_TRIP
             "h3": "8828308281fffff",
             "last_ping_epoch_ms": "1767225600120"
           }
   TTL:    15 seconds (Auto-purged if driver disconnects)

2. DynamoDB Dispatch Offer Lock Table (DispatchOfferLocks)

3. Aurora PostgreSQL Master Trip Schema DDL

sqlCopy
CREATE TABLE trips (
    trip_id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    rider_id UUID NOT NULL,
    driver_id UUID,
    status VARCHAR(32) NOT NULL CHECK (
        status IN ('REQUESTED', 'OFFERED', 'MATCHED', 'ARRIVING', 'IN_TRIP', 'COMPLETED', 'CANCELLED')
    ),
    pickup_geom GEOMETRY(Point, 4326) NOT NULL,
    dropoff_geom GEOMETRY(Point, 4326) NOT NULL,
    pickup_h3_index CHAR(15) NOT NULL, -- Uber H3 Resolution 8 index
    fare_cents INTEGER NOT NULL CHECK (fare_cents > 0),
    driver_payout_cents INTEGER CHECK (driver_payout_cents >= 0),
    platform_fee_cents INTEGER CHECK (platform_fee_cents >= 0),
    surge_multiplier NUMERIC(3, 2) DEFAULT 1.0 CHECK (surge_multiplier >= 1.0),
    fencing_token BIGINT,                    -- DynamoDB offer_version that won the match CAS (Section 8.2)
    vehicle_tier VARCHAR(32) NOT NULL DEFAULT 'UBER_X',
    requested_at TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    matched_at TIMESTAMPTZ,
    started_at TIMESTAMPTZ,
    completed_at TIMESTAMPTZ,
    created_at TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    updated_at TIMESTAMPTZ NOT NULL DEFAULT NOW()
);

CREATE INDEX idx_trips_rider_status ON trips (rider_id, status);
CREATE INDEX idx_trips_driver_status ON trips (driver_id, status);
CREATE INDEX idx_trips_created_date ON trips (created_at DESC);

---