F M Nurul Huda Pathan
Business Analyst at LKQ Corporation at almaBetter
This article aims to make you understand the System Design of the Uber application. We hope you will enjoy the blog. Let’s Start!
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.
Now, let’s discuss how an Uber Trip system can be designed. The system must have the following standard features.
The Uber Trip System architecture will have the following components.
It has the following sub-components as
It has the following sub-components which include
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.
Pre-trip components perform the following actions.
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-
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
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.
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-
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.
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.
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.
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/
Related Articles
Top Tutorials