Uber's dispatch system matches millions of riders to drivers in real time, across the globe. The interesting parts: efficient geo-indexing (find drivers near a rider in <100ms), the matching algorithm (not just nearest), and the surge pricing feedback loop.
Geo-indexing with H3
Divide Earth into hexagonal cells (Uber's H3 library). Each hex has a fixed-size ID. To find drivers near a rider: query the rider's hex + 6 neighbors. ~100 candidates instead of N. Fast in any KV store: GET drivers:hex:8928308280fffff.
Matching algorithm
Naïve: nearest driver. But that's locally optimal, globally bad — it starves drivers in distant hexes. Uber uses batch matching: collect requests over 1-5 seconds, run a bipartite matching that minimizes total wait time across all riders. Slightly slower for individual requests, much better overall.
Surge pricing
Demand > supply in a hex → multiply fare. The price feedback brings in more drivers (from neighboring hexes) and reduces requests (price-sensitive users wait). Algorithm: simple ratio (open requests / available drivers), capped at 5x, smoothed over 5-minute windows to avoid flapping.
Driver state machine
OFFLINE → ONLINE → AVAILABLE → MATCHED → EN_ROUTE_TO_RIDER
→ ARRIVED → IN_TRIP → COMPLETED → AVAILABLEGeographic sharding
One service can't handle global state. Shard by city or region — each shard owns its hexes, drivers, riders. Cross-shard rides (rare, e.g., between adjacent cities) handled by explicit handoff. Replicate per region for low latency.