Crush the FAANG Interview
See Plans β†’
ARCHITECTURE CASE STUDIES9 min read Β· Updated 2026-11-20 Β· View Raw Markdown (.md)

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.

KEY ENGINEERING TAKEAWAYS
  • 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.

INTERVIEW FOLLOW-UP FAQ

Frequently Asked Questions

How do you prevent two riders from matching with the same driver simultaneously?

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.

CONTINUE PRACTICING IN THE PLATFORM

Related Video Courses & Python 3.14 Workspaces

Drill every problem and architecture diagram from this guide inside Crush the FAANG Interview: