Design Uber's Real-Time Dispatch & Schemaless MySQL Architecture

1. Problem Statement & Scope Clarification

System Mission

Design Uber’s real-time geospatial dispatch platform and distributed append-only storage engine (Schemaless). The system must match millions of riders with nearby drivers in real time ($< 1\text{ s}$ matching latency), ingest continuous GPS streams from over $6\text{M}+$ active drivers ($375\text{k}+$ location updates/sec), partition stateful dispatch services via a decentralized gossip-based consistent hashing ring (Ringpop), and persist billions of immutable trip lifecycle transitions across a horizontally sharded MySQL InnoDB datastore with zero in-place updates.

Synthesizing vector architecture diagram...

Functional Requirements

1. Real-Time Driver Location Ingestion: Ingest high-frequency GPS telemetry ($(\text{lat}, \text{lng}, \text{bearing}, \text{speed})$) from $6\text{M}+$ drivers every 4 seconds, indexing locations into geospatial hierarchical cells (Google S2 / Uber H3).
2. Geospatial Dispatch Matching (DISCO): When a rider requests a trip, identify the top $K$ optimal available drivers within a dynamic geospatial radius based on Estimated Time of Arrival (ETA), vehicle category, and supply-demand balance in $< 1,000\text{ ms}$.
3. Decentralized Request Routing (Ringpop): Distribute active trips and supply state across stateful dispatch worker nodes using consistent hashing with a SWIM gossip protocol, automatically re-balancing ring membership upon node failure.
4. Append-Only Immutable State Persistence (Schemaless): Record every state transition of a trip (REQUESTED, OFFERED, ACCEPTED, ARRIVING, IN_TRANSIT, COMPLETED, BILLED) as an immutable cell in Schemaless.
5. Asynchronous Secondary Indexing: Decouple query indexing from write paths. Tail the MySQL binlogs via Kafka to maintain secondary indexes (e.g., query trips by rider_uuid, driver_uuid, or created_at_time) in Amazon OpenSearch and relational index tables.

Non-Functional Requirements (SLAs & SLOs)

• High Availability: $99.99\%$ availability for driver-rider matching and ride state updates ($< 52.6$ minutes downtime per year).
• Matching Latency: $P50 < 300\text{ ms}$, $P95 < 800\text{ ms}$, $P99 < 1,500\text{ ms}$ for dispatch match completion.
• GPS Ingestion Throughput: Ingest $> 375,000\text{ GPS pings/sec}$ with $P99 < 50\text{ ms}$ write latency to in-memory spatial caches.
• Storage Durability: Zero data loss ($RPO = 0$) for confirmed trip state cells across multi-AZ MySQL InnoDB replicas with semi-synchronous replication.
• CAP / PACELC Classification:
  • Real-Time Dispatch (Ringpop / DISCO): AP system under CAP; PA/EL under PACELC. Availability and low latency over strict consistency; localized temporary supply mismatches are resolved via optimistic locking rather than blocking distributed locks.
  • Schemaless Storage & Billing: CP system enforcing strict ACID guarantees per shard partition key (row_key = trip_uuid).

Out-of-Scope

• Turn-by-turn routing navigation algorithms and street-level map graph rendering (handled by Routing Engine).
• Fare calculation machine learning pricing models (Surge pricing rates ingested as precomputed inputs).
• Regulatory tax reporting and local municipal compliance filings.

---

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

Traffic Scale Calculations

• Active Riders: $150,000,000$ Monthly Active Users (MAU); $30,000,000$ Daily Active Users (DAU).
• Active Drivers: $6,000,000$ drivers globally; $1,500,000$ concurrently online during peak hours.
• Completed Trips per Day: $30,000,000$ trips/day.
• Driver GPS Ingestion QPS: Each online driver pings location every 4 seconds ($0.25\text{ pings/sec}$): $\text{GPS Ingestion QPS} = \frac{1,500,000\text{ concurrently online drivers}}{4\text{ s}} = \mathbf{375,000\text{ location pings/sec}}$ (All 6 M registered drivers are never online at once; the 1.5 M concurrent figure above is what the fleet, Redis TTLs and DISCO sizing are built on.)
• Dispatch Ride Request QPS: $\text{Average Ride Request QPS} = \frac{30,000,000\text{ trips}}{86,400\text{ s}} \approx 347\text{ QPS}$ $\text{Peak Dispatch QPS (Surge / New Year's Eve / Rain Storms)} = 347 \times 15 \approx \mathbf{5,200\text{ requests/sec}}$
• State Transition Writes to Schemaless: Each trip generates an average of $20$ immutable state transitions (events, location pings, payment auths, status updates): $\text{Total Daily Cells Written} = 30,000,000\text{ trips} \times 20\text{ cells} = \mathbf{600,000,000\text{ cells/day}}$ $\text{Peak Cell Write QPS} = \frac{600 \times 10^6}{86,400\text{ s}} \times 4.0\text{ (peak multiplier)} \approx \mathbf{27,777\text{ writes/sec (Provision for 30,000 QPS)}}$

Storage Calculations (3-Year Horizon)

• Schemaless Cell Size Breakdown:
  • added_id: 8 bytes (BIGINT auto-increment)
  • row_key: 16 bytes (UUID binary)
  • column_name: 32 bytes (VARCHAR)
  • ref_key: 8 bytes (BIGINT version)
  • body (JSON/MsgPack compressed payload): 1,200 bytes
  • Indexes and InnoDB row overhead: 150 bytes
  • Total per cell: $\approx \mathbf{1.4\text{ KB}}$.
• Daily Raw Storage Growth: $\text{Daily Raw Storage} = 600,000,000 \times 1.4\text{ KB} \approx 840\text{ GB/day}$
• 3-Year Raw Storage Volume: $\text{3-Year Raw Volume} = 840\text{ GB/day} \times 1,095\text{ days} \approx \mathbf{920\text{ TB (0.92 Petabytes)}}$
• Replication Multiplier ($RF = 3$ Across Multi-AZ MySQL Shards): $\text{Total Storage Footprint} = 920\text{ TB} \times 3 = \mathbf{2.76\text{ Petabytes Storage (AWS EBS gp3 / io2)}}$

Memory & Cache Sizing (Driver Locations & DISCO Ring)

• Active Driver Spatial Index (H3 Resolution 8 Hexagons): $6,000,000\text{ drivers} \times 128\text{ bytes per driver state} \approx \mathbf{768\text{ MB RAM}}$ (fits entirely in memory).
• Active Trip Contexts: $1,000,000$ concurrent in-progress trips $\times 4\text{ KB state} = \mathbf{4\text{ GB RAM}}$.
• ElastiCache Redis Spatial Tier (Driver Geofence Index): Provisioned across 6 nodes in cluster mode: $\mathbf{120\text{ GB RAM}}$ for working sets and sub-millisecond proximity queries.

Fleet Sizing & Compute Resources

• DISCO Dispatch Workers (Ringpop Nodes on AWS ECS Fargate - 4 vCPU, 16 GB RAM): Each node coordinates $5,000$ active drivers and processes $1,500$ dispatch match evaluations/sec. $\text{DISCO Fleet Size} = \frac{1,500,000\text{ peak drivers}}{5,000\text{ drivers/node}} = \mathbf{300\text{ tasks (100 per AZ across 3 AZs)}}$
• Schemaless MySQL Database Shards: Dividing $30,000\text{ peak write QPS}$ across database shards (each AWS Aurora / MySQL node comfortably handles $1,500\text{ write QPS}$): $\text{Database Shards} = \frac{30,000\text{ QPS}}{1,500\text{ QPS/shard}} = \mathbf{20\text{ Shards (Each shard: 1 Primary + 2 Multi-AZ Replicas)}}$

---

3. AWS-First High-Level Architecture

Synthesizing vector architecture diagram...

Follow a ride request from the top. Rider and driver apps enter through Route 53 and the NLB to any DISCO dispatch node. In the "Real-Time Dispatch Tier" panel, the nodes form a Ringpop ring kept in sync by gossip: each H3 area is owned by exactly one node, so any node that receives a request forwards it to the owner, which looks up drivers in the Redis supply grid and makes the match. In the "Schemaless Storage Tier" panel, trips are written through the Schemaless router to about 20 MySQL shards, each with a read replica. In the "Change Data Capture & Async Processing Tier" panel, each shard's binlog streams into Kafka, where consumers build secondary indexes in OpenSearch and archive to S3. Owning each area on exactly one node means matching needs no distributed locks between nodes.

Data Flow Walkthrough

1. Driver GPS Ingestion Flow:
   • Drivers emit GPS pings every 4 seconds. The request hits AWS NLB and routes to a DISCO worker node.
   • The DISCO worker maps the driver's coordinates to an Uber H3 hexagonal cell index (resolution 8, edge length $\approx 461\text{ m}$, about $0.8\text{ km}$ across).
   • The driver's location, heading, and status (AVAILABLE) update in ElastiCache Redis with a 10-second TTL.
2. Rider Dispatch Request Flow:
   • A rider requests a pickup at coordinate $(\text{lat}, \text{lng})$. The request reaches a DISCO node.
   • The receiving node consults the Ringpop consistent hash ring. Ringpop hashes the trip's geographic H3 cell or rider UUID to determine the authoritative coordinator node responsible for this geographic partition. If the current node is not the owner, it proxies the request to the target DISCO node in $< 5\text{ ms}$.
   • The coordinator DISCO node queries Redis for all AVAILABLE drivers located within the pickup H3 hexagon and neighboring concentric k-rings.
   • Drivers are scored via a batch ETA matrix, and the top candidate is selected.
3. Schemaless Append-Only Write Flow:
   • The match generates a trip record: row_key = trip_uuid.
   • The DISCO service writes an immutable cell to the Schemaless Proxy: column_name = "status", ref_key = 1, body = {"state": "REQUESTED", "rider_id": "...", "origin": {...}}.
   • The Schemaless Proxy hashes row_key across 20 MySQL shards: shard_id = MurmurHash3(row_key) % 20.
   • The target MySQL primary executes a single fast append into InnoDB: INSERT INTO schemaless_cells (row_key, column_name, ref_key, body) VALUES (...). Zero lock contention occurs because the write is an append, not an in-place update.
4. CDC Secondary Index Pipeline:
   • A binlog tailing agent (Debezium/Maxwell) captures the newly appended cell from MySQL's binary log and publishes the change event to Amazon MSK (Kafka).
   • Async index workers consume the Kafka topic, extract secondary attributes (rider_id, driver_id, created_at), and update the secondary query index in Amazon OpenSearch, allowing support agents and users to query historical trips.

---

End-to-End Request Tracing Walkthrough

---

4. API Interface Design & Wire Protocol

1. Trip Dispatch Request (POST /v1/dispatch/trips)

httpCopy
POST /v1/dispatch/trips HTTP/1.1
Host: dispatch.uber.internal
Content-Type: application/json
X-Client-UUID: rider_01HZX894KMNPQ
Idempotency-Key: 9a8b7c6d-5e4f-3a2b-1c0d-9e8f7a6b5c4d

{
  "rider_uuid": "rider_01HZX894KMNPQ",
  "pickup_location": {
    "latitude": 37.774929,
    "longitude": -122.419418,
    "h3_index": "8828308281fffff",
    "street_address": "1455 Market St, San Francisco, CA"
  },
  "dropoff_location": {
    "latitude": 37.789172,
    "longitude": -122.401449,
    "h3_index": "8828308295fffff",
    "street_address": "Montgomery St Station, San Francisco, CA"
  },
  "vehicle_category": "UBER_X",
  "surge_multiplier": 1.2,
  "max_acceptable_eta_seconds": 600
}

Response: 201 Created

jsonCopy
{
  "trip_uuid": "trip_84920194-7f12-4000-8000-abcdef123456",
  "status": "DISPATCHING",
  "estimated_pickup_epoch_ms": 1773648192000,
  "surge_multiplier": 1.2,
  "assigned_driver": null,
  "created_at_epoch_ms": 1773648000000,
  "poll_interval_ms": 2000
}

---

2. Driver Location Ingestion Stream Protocol (gRPC / Protobuf)

protobufCopy
syntax = "proto3";

package uber.dispatch.v1;

service LocationIngestionService {
  rpc PushDriverLocation (DriverLocationRequest) returns (DriverLocationResponse);
  rpc BatchDriverLocations (BatchDriverLocationRequest) returns (DriverLocationResponse);
}

message DriverLocationRequest {
  string driver_uuid = 1;
  double latitude = 2;
  double longitude = 3;
  float bearing_degrees = 4;
  float speed_meters_per_sec = 5;
  uint64 h3_index = 6;
  string vehicle_category = 7;
  enum DriverStatus {
    AVAILABLE = 0;
    ASSIGNED = 1;
    IN_TRANSIT = 2;
    OFFLINE = 3;
  }
  DriverStatus status = 8;
  int64 timestamp_epoch_ms = 9;
}

message DriverLocationResponse {
  bool acknowledged = 1;
  int32 next_reporting_interval_seconds = 2;
}

---

3. Status Codes & Error Contracts

---

5. Data Models & Storage Architecture

The Schemaless MySQL Relational Schema

Schemaless structures data into shards, rows, and cells. A single row represents a business entity (e.g., a trip). Within a row, data is organized into columns (e.g., status, driver, payment, rating). Each column contains multiple cells representing the historical timeline of updates, keyed by ref_key.

Synthesizing vector architecture diagram...

Read the three tables as layers. A SCHEMALESS_ROW is one entity (such as a trip), identified by row_key, which also decides its shard. Its data lives in SCHEMALESS_CELLs: each cell holds one column (such as "status" or "payment") at one version (ref_key) as a JSON blob, and cells are only ever appended, never updated in place, so the full history of every column is kept and concurrent writers never overwrite each other. added_id gives every cell a global order, which is what change streams read. SECONDARY_INDEX maps another key (such as driver ID) back to a row_key, and is built asynchronously from those streams. This append-only cell design is what let Uber use sharded MySQL as a scalable, schemaless store.

Production MySQL DDL for Schemaless Cells Table

sqlCopy
-- Executed on each of the 20 MySQL Shards
CREATE TABLE schemaless_cells (
    added_id BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
    row_key VARBINARY(64) NOT NULL,
    column_name VARCHAR(64) NOT NULL,
    ref_key BIGINT UNSIGNED NOT NULL,
    body MEDIUMBLOB NOT NULL,          -- Compressed JSON / MsgPack payload
    is_deleted TINYINT UNSIGNED NOT NULL DEFAULT 0,
    created_at TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
    
    PRIMARY KEY (added_id),            -- Clustered Index: Enables sequential binlog tailing
    UNIQUE KEY uq_cell (row_key, column_name, ref_key)  -- Deduplication & Idempotency; its (row_key, column_name) prefix also serves
                                                        -- "latest state" lookups (ORDER BY ref_key DESC LIMIT 1), so no separate index is needed
) ENGINE=InnoDB DEFAULT CHARSET=binary
ROW_FORMAT=COMPRESSED
KEY_BLOCK_SIZE=8;

Why added_idis the Clustered Primary Key

In traditional relational databases, the primary key would be (row_key, column_name, ref_key). However, in a distributed append-only system, using added_id AUTO_INCREMENT as the clustered primary key provides two critical production advantages:

1. Zero B-Tree Page Splits on Writes: Every new write appends strictly to the end of the InnoDB clustered index leaf pages. Disk writes are sequential, eliminating costly page splits and minimizing disk I/O.
2. Deterministic, Monotonic Binlog Tailing: CDC tailing engines (Debezium/Maxwell) checkpoint their position simply by storing the highest added_id observed. Catching up after worker restarts requires a simple query: SELECT * FROM schemaless_cells WHERE added_id > :last_checkpoint ORDER BY added_id ASC LIMIT 1000.

---