Detailed Design of Uber

Let’s look at the detailed design of our Uber system and learn how the various components work together to offer a functioning service:

Components

Let’s discuss the components of our Uber system design in detail.

Location manager

Riders and drivers connect to the location manager service. It shows nearby drivers when a rider opens the app and receives driver location updates every ~4 seconds. The service forwards driver locations to the quadtree map service to determine the driver’s current map segment. It also stores each driver’s latest location and, during trips, records the route taken.

Quadtree map service

The quadtree map service updates the driver locations. The main problem is how we efficiently find nearby drivers.

We’ll modify the solution discussed in the Yelp chapter according to our requirements. We used quadtreesA quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The data associated with a leaf cell varies by application, but the leaf cell represents a “unit of interesting spatial information”. Source: Wikipedia on Yelp to find the location. Quadtrees partition the map into hierarchical spatial regions. When the number of drivers in a region exceeds a predefined threshold, the node is subdivided into four child regions, and the drivers are redistributed accordingly.

Each leaf node in quadtrees contains segments that can’t be divided further. We can use the same quadtrees for finding the drivers. The ...