Matt Ranney, Chief Systems Architect at Uber, gave an overview of their dispatch system, responsible for matching Uber's drivers and riders. Ranney explained the driving forces that led to a rewrite of this system. He described the architectural principles that underpin it, several of the algorithms implemented and why Uber decided to design and implement their own RPC protocol.
The old dispatch system was designed for private transportation (1 driver, 1 vehicle, 1 rider) and built around the concept of moving people, but Uber wants to enter new markets, such as goods transportation. Uber also sharded its data by city. As Uber grew and expanded to ever more cities, some of them quite big, it became difficult to manage its data. Finally, the dispatch system had multiple points of failure, a consequence of Uber's hectic growth and the system's scramble to keep up with that growth.
[...]
To achieve that kind of scale, Uber chose to use Google's S2 Geometry Library. S2 is able to split a sphere into cells, each with an id. The Earth is roughly spherical, so S2 can represent each square centimeter of it with a 64-bit integer. S2 has two important properties for Uber: it is possible to define each cell's resolution and it is possible to find the cells that cover a given area. Uber uses 3,31 km2 cells to shard its data. All this new data enables Uber to reduce wait times, extra driving by partners and the overall estimated times to arrival (ETA). So, what happens when a rider wants to use Uber? Uber uses the rider location and S2's area coverage function to look for drivers that can be matched with a rider. Uber then chooses the shortest ETA, taking into account not only the drivers who are available, but also those that will become available in time to pick up the rider.
Using the S2 Geometry Library to shard the earth, that's smart !