How should you approach to design an Uber Trip System?

Contributors: F M Nurul Huda Pathan, Soumya Ranjan Mishra

Uber is an American technology company that provides ride-hailing, food delivery (Uber Eats), package delivery, couriers, freight transportation, and, through a partnership with Lime, electric bicycle and motorized scooter rental. Most of its revenues come from ride-hailing.

Let’s now discuss how the ride-hailing operations are done in Uber.

• Uber provides different service options. It includes a private ride in a car with a driver for up to four passengers. Depending on the location, It also offers other levels of service at different prices including black luxury vehicles, newer or premium level vehicles, cars with leather seats, sport utility vehicles, minivans, vans, hatchbacks, electric cars, hybrid vehicles, motorcycles, auto-rickshaws, actual taxicabs, lower-cost shared transport with other passengers going in the same general direction.
• It determines the fees and terms on which drivers transport riders. It uses a dynamic pricing model. Fares fluctuate depending on the local supply and demand at the time of service. Customers are quoted the fare in advance. Service is generally accessed via a mobile app.
• Users need to set up a personal profile with a name, phone number, other information, and payment preference, which could be a credit card, e-commerce payment system, or, in some cases, cash. After the service is complete, the customer may be given the option to provide a gratuity to the driver, which is also billed to the customer’s payment method.
• Drivers usually provide a vehicle, which could be owned, rented, or leased. Drivers must meet requirements for age, health, car age, and type, have a driver’s license and a smartphone or tablet and may be required to pass a background check. In many cities, vehicles must pass annual safety inspections and/or must have an emblem posted in the passenger window. Some cities also require drivers to have a business license. There may be accommodations for hearing-impaired drivers. Drivers may be notified before accepting a trip if it will be longer than 45 minutes.
• After each trip completion, drivers and customers may rate each other, and users with low ratings may be deactivated.

Now, let’s discuss how an Uber Trip system can be designed. The system must have the following standard features.

• Riders will be able to view the available drivers in nearby locations.
• Riders will be able to request rides from source to destination.
• Nearby drivers will get notified of the ride, and one of the drivers will confirm the ride.
• Pickup ETA will be shown to customers when a ride is dispatched to pick up the rider.
• Once the trip is completed, the rider must be shown the trip details such as the trip map, price, etc. in the ride receipt.

The Uber Trip System architecture will have the following components.

Pre-Trip Component:

It has the following sub-components as

• Driver Location Manager: This component will be responsible for maintaining the changing driver locations. It will ingest the messages emitted by the drivers’ uber app containing their current locations and update the car location index.
• Trip Dispatcher: It will be responsible for handling the trip requests from users and dispatch a driver in response to those requests.
• Arrival ETA Calculator: This component will be responsible for calculating the ETA for the driver to reach the rider once the driver has accepted the ride.

On-Trip Component:

It has the following sub-components which include

• Trip Recorder: GPS signals transmitted from the ride when the trip is in progress are recorded. These GPS signals will be then recorded in a data store which will be used by subsequent sub-component systems such as Map Matcher and Pricing Calculator.
• Map Matcher: It will be responsible for matching the trip on the actual map using algorithms specialized for this purpose.
• Price Calculator: It will then use the recorded trip information for computing the price which users have to pay for the trip.

Data Storage:

Driver Locations: Here, the driver location information such as latitude and longitudes will be stored.

Trip Records: This database will record trip details. These details can be used to draw insights by the company to draw patterns and business insights.

How are the Pre-Trip Components designed?

Pre-trip components perform the following actions.

• Update Driver Location -It involves updating the driver locations as drivers keep changing their locations.
• List nearby drivers-It comprises the steps involved in fetching the list of nearby drivers.
• Requesting for a ride-It includes a series of steps involved in requesting and dispatching a ride.

These components are designed to show the cars in the nearby locations and dispatch the ride on users’ requests. The location of the cars can be stored in an in-memory car location index, which can support high read and write requests. The driver app will keep on sending the updated car locations, which will be updated in this index. The index will be queried when the rider app requests for nearby car locations or places a ride request.

Car Location Index will maintain the driver locations in a distributed index, which is spread across multiple nodes. Nodes contain driver information containing their locations, the number of people in the car, and if they are on a trip. These pieces of information are aggregated as objects and are distributed across the nodes using some mechanisms (e.g., city, product, and so forth) along with replication.

Some properties that a car index location must contain are-

• It must store the current locations of all drivers and must support fast queries by location and properties such as driver’s trip status.
• It must support a high volume of reads and writes.
• The data stored in these indexes must be ephemeral, and we don’t need long-term durable storage.

ETA for the car arrival is calculated by considering factors such as route, traffic, and weather account. There are two primary components of estimating an ETA given an origin and destination on a road network such as

• calculating the route from origin to destination with the least cost
• estimating the time taken to traverse the route.

Every intersection of a road on a map is represented by a node and each road segment by a directed edge.

We can use Dijkstra’s algorithm to find the shortest path between source and destination. This algorithm has a time complexity of O(N_logN) to find the shortest path for N nodes. But ride-hailing apps like Uber require a highly scaled approach to determine the routes. To solve this we can use partitioning the entire graph, pre-computing the best path within partitions, and interacting with just the boundaries of the partitions. It will give a time complexity of O(√N_log√N). Thus the complexity to find the shortest path can be reduced.

After the optimal route is found, we can find the estimated time to traverse the road segment by taking traffic into account, which is a function of time, weather, and real-life events. This traffic information can be used to populate the edge weights on the graph.

How are On-Trip and Post-Trip Components designed?

These components are responsible for handling the processes which involve from start to completion of the trip. It keeps track of the locations of the ride when the trip is in progress. It is also responsible for generating the route map and computing the trip cost when it gets completed.

GPS locations sent by the rider/driver app while the trip is in progress are stored in a database. Some of the characteristics of this database are-

• It must support a high volume of writes.
• The storage must be durable.
• It must support time-series-based queries such as the location of the driver in a given time range.

Map Matcher module takes in raw GPS signals as input and outputs the position on the road network. The input GPS signals consist of latitude, longitude, speed, and course. The positions on a road network consist of latitude (on an actual road), longitude (on a real road), road segment id, road name, and direction/heading. The route map generated by Map Matcher is used for-

i) finding the actual position of the driver on the road network

ii) calculating the fare prices.

Optimizations

• One of the problems with the proposed design is that both the heavy reads and writes are directed to the data store. We can optimize the system by separating the read traffic from the writes by caching the raw driver locations in a distributed cache (Redis). Redis is an open-source, in-memory data structure store, used as a database, cache, and message broker. The raw driver locations from the Redis cache are leveraged by MapMatcher to create the matched map and persist it in the data store.

We can also improve the predicted ETAs by applying machine learning on top of the ETA calculation mechanism mentioned above. The first challenge of using machine learning involves feature engineering to come up with features such as region, time, trip type, and driver behavior to predict realistic ETAs.

Another exciting challenge would be to select the machine learning model, which can be used for predicting the ETAs. For this use-case, we would rely on using a non-linear(e.g., ETA doesn’t linearly relate with an hour of the day) and non-parametric(there is no prior information on the interaction between different features and ETA) model such as Random Forest, Neural networks and KNN learning. We can further improve the ETA prediction by monitoring customer issues when the ETA prediction is off.

Extended requirement

In the design above, the drivers were being notified of the nearby riders, and they were accepting the rides they wanted. As an extension of the existing implementation, we may extend the system to enable automated matching of drivers to riders.

The drivers are matched to riders based on factors such as the distance between drivers and riders, the direction in which the driver is moving, traffic, and so forth. We can apply the naïve approach of matching riders to the nearest driver.

However, this approach doesn’t tackle the problem of something called a trip upgrade, which occurs when a rider is matched to a driver and, at the same time, an additional driver, and an additional rider enters the system. The trip upgrade scenario is illustrated in the images below.

How to handle datacenter failures?

• It doesn’t happen very often, but there could be an unexpected cascading failure or an upstream network provider could fail.
• Uber maintains a backup data center and the switches are in place to route everything over to the backup data center.
• The problem is the data for in-process trips may not be in the backup data center. Rather than replicate data they use driver phones as a source of trip data.
• What happens is the Dispatch system periodically sends an encrypted State Digest down to driver phones. Now let’s say there’s a data center failover. The next time the driver phone sends a location update to the Dispatch system will detect that it doesn’t know about this trip and ask them for the State Digest. The Dispatch system then updates itself from the State Digest and the trip keeps on going like nothing happened.

Conclusion

Uber is a company with a complicated history. Still, its founders had made something that was impossible. They survived sabotages, strikes, and discontent with the governments of different countries around the whole world. The necessity to provide people with good services at affordable prices is urgent nowadays. Not all people can use the quality they want. Uber opens new perspectives and possibilities.

As a final word, we would like to suggest some points that might be improved in system design are as follows:

1.Reduce Driver Downtime 

2.Own Local Event Recommendations 

3.Customize the experience 

4.Create Loyalty Programs

Finally, we had a word on Uber system design. I think our work will help you in certain ways. Clap for us. If you suggest adding something more, feel free to reach me. See you next time with another blog!!!

Reference

https://www.techtakshila.com/system-design-interview/chapter-3/

https://www.geeksforgeeks.org/system-design-of-uber-app-uber-system-architecture/

https://www.educative.io/blog/uber-backend-system-design