Detailed Design of Uber

Define the detailed architecture required for a scalable ride-hailing service like Uber. Analyze how real-time location tracking using quadtrees and caching (Redis) is implemented. Learn to select appropriate databases (MySQL and Cassandra) and to design for fault tolerance to achieve high availability.

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