Design Uber System Design Walkthrough: Geohash vs. Quadtree Spatial Indexing & Dispatch Matching
How to architect a 500,000-write/sec real-time location ingestion pipeline, spatial driver lookup index, and atomic ride-matching state machine.
- Read-heavy business directories (Yelp) suit static Quadtrees or read-replicated Geohash indexes; Uber's 4-second GPS pings from millions of active drivers create a massive write-heavy spatial workload.
- Separate ephemeral driver location state (in-memory sharded Redis Geohash / H3 hexagonal cells) from durable trip & billing state (ACID sharded SQL).
- Use distributed short-TTL driver locks so two concurrent rider requests in downtown rush hour never double-assign the same driver.
1. Sizing the GPS Write Firehose
With 2 million concurrent active drivers pinging GPS coordinates every 4 seconds, location ingestion sustains 500,000 writes/second (~1.5M/s at peak). Writing every 4-second ping directly into a disk-backed B-tree SQL index thrashes IOPS. Instead, stream pings into sharded in-memory location servers keyed by city/cell ID, updating both a DriverLocation table (latest cell) and the target H3/Geohash cell set in RAM, while batch-archiving breadcrumbs asynchronously to Kafka -> Object Storage for trip replay and ETA ML models.
2. Geohash vs. Dynamic Quadtree vs. Uber H3 Hexagons
Mentioning boundary neighbor queries (querying the center cell plus its k-ring neighbors so a driver 10 meters across a cell border isn't missed) and uniform hexagonal neighbor distances in H3 immediately signals Staff-caliber geospatial depth.
Frequently Asked Questions
Rank candidate drivers by road-network ETA (not raw Euclidean distance), then acquire an atomic Redis SET driver_lock:{id} NX EX 15 lock before sending the push offer to that driver. If declined or expired after 15s, advance to the next candidate.
Related Video Courses & Python 3.14 Workspaces
Drill every problem and architecture diagram from this guide inside Crush the FAANG Interview: