# 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.

- **Author:** Former Amazon Software Engineer (Crush the FAANG Interview)
- **Category:** Architecture Case Studies
- **Updated:** 2026-11-20
- **Canonical URL:** https://crushthefaanginterview.com/blog/design-uber-real-time-geo-dispatch-architecture

## Key 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.

## 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.

## Related Video & Interactive Courses
- [Design Uber](https://crushthefaanginterview.com/course/sd-31-design-uber)
- [Design a Proximity Service / Yelp](https://crushthefaanginterview.com/course/sd-30-design-a-proximity-service)
- [Pub-Sub Messaging](https://crushthefaanginterview.com/course/sd-18-pub-sub)
- [Distributed Cache](https://crushthefaanginterview.com/course/sd-16-distributed-cache)
