The matching problem
Uber must find a nearby available driver for each rider within seconds, across a constantly moving fleet. The two hard parts are fast spatial search and avoiding double booking.
Geospatial indexing
Drivers continuously stream their location. The system indexes positions using a grid of cells so it can answer the query find drivers near this point without scanning everyone. Each cell holds the drivers currently inside it.
- Drivers publish location updates frequently
- A cell index maps regions to nearby drivers
- A nearby query reads the rider cell plus its neighbors
Avoiding double dispatch
Two riders must not be offered the same driver. The dispatcher marks a candidate driver as reserved while an offer is outstanding, so concurrent matches do not collide.
Speed comes from the spatial index; correctness comes from reserving a driver before the offer resolves.
Key idea
Index moving drivers by spatial cells for fast nearby lookups, and reserve a candidate before offering it so two riders never grab the same car.