1. Executive Summary & Scale Metrics
Uber is not a typical CRUD web application—it is a massive, real-time physical marketplace connecting physical vehicles to riders across thousands of cities globally.
Real-Time Geospatial Matching Scale
UberTelemetry write throughput and dispatch matchmaking SLAs
The fundamental computer science problem of ride-sharing is geospatial querying on a moving sphere under heavy write throughput. Calculating distances between spherical coordinates (latitude and longitude) requires the Haversine formula (trigonometric sines, cosines, and square roots). Running millions of Haversine math operations against a relational database every second is computationally impossible.
2. First-Principles Capacity Estimation & Physical Constraints
┌─────────────────────────────────────────────────────────────────────────────┐
│ CAPACITY & INGESTION DERIVATION │
├─────────────────────────┬─────────────────────────┬─────────────────────────┤
│ Dimension │ Production Formula │ Derived Value │
├─────────────────────────┼─────────────────────────┼─────────────────────────┤
│ Driver Write Ingress │ 5,000,000 drivers / 4s │ ~ 1,250,000 writes / sec│
│ Network Ingress (gRPC) │ 1.25M × 64 bytes (Proto)│ ~ 80 MB / sec │
│ Dispatch Match QPS │ 28M trips / day peak │ ~ 15,000 matches / sec │
│ H3 Index Computation │ Pure mathematical shift │ < 1.0 microsecond / CPU │
│ Match Latency SLA │ Discovery + ETA + Lock │ < 800 milliseconds │
└─────────────────────────┴─────────────────────────┴─────────────────────────┘Mathematical Derivations
-
Write Amplification & SSD Destruction in SQL: If 1,250,000 driver pings per second are written to a traditional PostgreSQL table with spatial B-Tree/R-Tree indexes:
Write IOPS = 1,250,000 × 3 index updates (Spatial + PK + Time) = 3,750,000 Disk IOPSStandard enterprise NVMe SSD arrays cap out at ~100k–500k random write IOPS. Writing transient location pings to disk destroys hardware endurance within months and causes catastrophic transaction queue locks.
-
H3 Hexagonal Geometric Efficiency:
- In square grids (Geohash / Quadtree), diagonal neighbors are
√(2) ≈ 1.414×farther than orthogonal neighbors (d_{diag} = √(2) · d_{orth}). - In hexagonal grids (H3), all 6 adjacent neighbors have identical centroid distance (
d = 2r cos(30^circ)).
- In square grids (Geohash / Quadtree), diagonal neighbors are
3. The Naive Design & Why It Collapses
NAIVE ARCHITECTURE: RELATIONAL SPATIAL DATABASE
[Driver Phone] ── HTTP POST /driver/location (every 4s) ──┐
▼
[Node.js API Server]
│
▼ (1.25M writes/sec)
[PostgreSQL + PostGIS DB]
Table: drivers (id, lat, lng)
▲
│
[Rider Phone] ── GET /nearby?lat=37.77&lng=-122.41 ───────┘
SQL: SELECT * FROM drivers
WHERE ST_DWithin(geom, ST_MakePoint(-122.41, 37.77), 2000);Why Naive Relational Spatial Databases Collapse Under Geospatial Load
UberThree fatal flaws of traditional SQL Haversine and PostGIS architectures
SSD Disk IOPS & Index Lock Explosion
criticalWriting 1,250,000 location updates per second into a PostgreSQL table causes massive write amplification, destroys SSD write endurance, and locks spatial B-Tree/R-Tree indexes.
Trigonometric Haversine CPU Bottlenecks
criticalEvaluating spatial bounding boxes across millions of rows requires calculating expensive trigonometric sines and cosines on server CPUs for every single search query.
Mobile Battery Drain via Continuous HTTP Handshakes
highOpening a new HTTPS connection (DNS + TCP 3-way handshake + TLS 1.3 negotiation) every 4 seconds keeps the phone's cellular radio at maximum power, draining batteries rapidly.
4. Deep Architecture: Layer-by-Layer Walkthrough
Uber solved this by building H3 (Hexagonal Hierarchical Spatial Indexing) and the DISCO (Dispatch) In-Memory Ringpop Engine.
┌─────────────────────────────────────────────────────────────────────────────────┐
│ UBER DISPATCH ARCHITECTURE │
│ │
│ ┌─────────────────────────────────────────────────────────────────────────┐ │
│ │ DRIVER TELEMETRY & INGESTION (gRPC) │ │
│ │ • Persistent TLS socket; Protobuf payload (lat, lng, bearing, speed) │ │
│ │ • Ingested into Netty/Go Gateway with zero HTTP handshake overhead │ │
│ └─────────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────────┐ │
│ │ H3 HEXAGONAL MAPPING & IN-MEMORY REGISTRY │ │
│ │ • Lat/Lng mapped mathematically to H3 Cell ID (64-bit integer) │ │
│ │ • Sharded in-memory via Ringpop (Consistent Hashing Ring) │ │
│ │ • Zero disk I/O for transient 4-second location pings │ │
│ └─────────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────────┐ │
│ │ DISCO DISPATCH & ROUTING ENGINE │ │
│ │ • Rider request maps to pickup H3 Hexagon │ │
Microsecond Step-by-Step Dispatch Flow
[Driver gRPC Ping] ──> [Ingestion Gateway] ──> [H3 Map: uint64] ──> [Ringpop In-Memory Bucket]
│
[Rider Tap "Request"] ──> [DISCO Engine] ──> [k-Ring (19 Hexagons)] ────────┤
│
▼
[Gurafu Street Graph ETA] ──> [Atomic 15s Lease Lock] ──> [Offer Sent to Driver]- Driver Location Transmission (0ms – 20ms): Drivers transmit binary Protobuf packets over a persistent gRPC HTTP/2 stream every 4 seconds. Zero TLS re-negotiation overhead.
- H3 Coordinate Projection (< 1 microsecond):
The gateway runs the H3 coordinate projection algorithm, converting
(37.7749, -122.4194)into the 64-bit index0x8828308281fffffpurely in CPU registers. - In-Memory Sharding via Ringpop (5ms): Using consistent hashing, the H3 index routes the driver update to the designated in-memory node in the Ringpop cluster. Zero disk writes occur.
- k-Ring Traversal & Dispatch Lock (20ms – 80ms):
When a rider requests a pickup, DISCO queries the rider's H3 cell and its 18 surrounding neighbors (
k=2). It ranks candidates using street-network routing (Gurafu) and acquires an atomic 15-second distributed lease on the top driver.
5. Interactive System Visualizer
Step through the end-to-end Uber dispatch pipeline, from driver gRPC pings to H3 k-ring indexing and atomic match locking:
Tracking millions of moving vehicles and matching riders in sub-second latency
GPS ping every 4s via gRPC
TLS termination & batching
Bearing, velocity, lat/lng
Consistent hashing shard key
Phase 1:Step 1: Driver Location Telemetry. Millions of drivers transmit GPS coordinates, speed, and heading every 4 seconds over persistent gRPC connections into a distributed Netty edge gateway.
6. Core Algorithms & Production Code Implementation
In-Memory H3 Spatial Indexing & Dispatch State Machine
export interface DriverLocation {
driverId: string;
lat: number;
lng: number;
h3Index: string; // 64-bit hex string e.g. "8828308281fffff"
bearing: number; // 0 - 360 degrees
status: "AVAILABLE" | "EN_ROUTE" | "ON_TRIP";
lastPingTimeMs: number;
}
export interface MatchCandidate {
driverId: string;
straightLineDistanceMeters: number;
estimatedArrivalSec: number;
}
7. Production Storage Engine & Ingestion Schemas
Apache Cassandra DDL: Completed Trips Ledger
CREATE KEYSPACE uber_dispatch
WITH replication = {'class': 'NetworkTopologyStrategy', 'us-west-2': 3, 'us-east-1': 3};
CREATE TABLE uber_dispatch.completed_trips (
city_id text,
trip_date date,
trip_id uuid,
rider_id uuid,
driver_id uuid,
pickup_h3_res8 text,
dropoff_h3_res8 text,
fare_amount decimal,
surge_multiplier float,
status text,
created_at timestamp,
PRIMARY KEY ((city_id, trip_date), trip_id)
)
gRPC Protobuf Contract: Driver Location Ingestion
syntax = "proto3";
package uber.telemetry.v1;
message LocationTelemetryPing {
string driver_id = 1;
double latitude = 2;
double longitude = 3;
float bearing_degrees = 4;
float speed_mps = 5;
uint64 h3_index = 6;
int64 timestamp_ms = 7;
enum DriverStatus {
AVAILABLE = 0;
EN_ROUTE = 1;
ON_TRIP =
8. Failure Modes & Self-Healing Matrix
Real-Time Geospatial Resilience Matrix
UberAutomated recovery for node crashes, network dead-zones, and dispatch concurrency races
9. Staff-Plus Interview Playbook & Trade-Offs
Spatial Indexing Architecture Comparison
| Indexing Model | Geometry Shape | Centroid Distance Symmetry | Cell Area Distortion | Optimal System Design Application |
|---|---|---|---|---|
| Uber H3 | Hexagon | Uniform (All 6 neighbors equal) | Minimal across latitudes | ✅ Ride-hailing dispatch, dynamic surge pricing |
| Google S2 | Quadtree Square | Non-uniform (√(2) diagonal error) | Moderate |
Staff Interview Rubric
If an interviewer asks: "How would you design the backend dispatch and matching system for Uber?"
- Calculate the Ingestion Scale First: Highlight that 1.25M writes/sec makes relational disk I/O mathematically impossible.
- Justify H3 Hexagons mathematically: Explain the uniform neighbor distance property of hexagons over squares/Geohash.
- Present In-Memory Sharding with Ringpop: Detail consistent hashing with SWIM gossip protocol for ephemeral driver locations.
- Explain Two-Stage Dispatch & Atomic Leases: Walk through k-ring candidate discovery (
<2.5ms), street graph ETA scoring, and atomic 15-second distributed lease locking.
