Note: This post was originally published in 2020 and has been updated as of Nov. 15, 2021.
Designing a ride-sharing service like Uber or Lyft is a common system design interview question. These ride-sharing services match users with drivers. Users input a destination and send their current location, and nearby drivers are notified within seconds.
Our comprehensive system designing Uber and beyond.
Uber aims to make transportation easy and reliable. The popular smartphone app handles high traffic and complex data and systems. Uber enables customers to book affordable rides with drivers in their personal cars. The customers and drivers communicate using the Uber app.
There are two kinds of users that our system should account for: Drivers and Customers.
What we know about our system requirements is:
Similar services: Lyft, Didi, Via, Sidecar, etc.
Difficulty level: Hard
Helpful prerequisite: Designing Yelp
Constraints (i.e. capacity estimations and system limitations) are some of the most important considerations to make before designing Uber’s backend system. Constraints will generally differ depending on time of day and location.
We’ll design our build with the following constraints and estimations:
For our Uber solution, we will be referencing our answer to another popular system design interview question: Designing Yelp. Please take a minute to check our Yelp solution if you’re not familiar with it.
We would need to make modifications to align with our Uber system and its requirements. For instance, our QuadTree must be adapted for frequent updates.
A few issues arise if we use the Dynamic Grid solution from our Yelp problem:
In these cases, a QuadTree is not ideal because we can’t guarantee the tree will be updated as quickly as our system requires. The QuadTree must be updated with every driver’s update so that the system only uses fresh data reflecting everyone’s current location.
We could keep the most recent driver position in a hash table and update our QuadTree less frequently. We want to guarantee that a driver’s current location is reflected in the QuadTree within 15 seconds. We maintain a hash table that will store the current driver location. We can call it
We need to store
DriveIDin the hash table, which reflects a driver’s current and previous location. This means that we’ll need 35 bytes to store each record:
This totals to 35 bytes.
Since we assume one million drivers, we’ll require the following memory:
Now let’s discuss bandwidth. If we get the DriverID and location, it will require . This information is received every three seconds from 500 thousand daily active drivers, so we receive 9.5MB every three seconds.
To randomize distribution, we could distribute
DriverLocationHT on multiple servers based on the DriverID. This will help with scalability, performance, and fault tolerance. We will refer to the machines holding this information as the Driver Location servers.
These servers will do two more things. Once the server receives an update on a driver’s location, it will broadcast that information to relevant customers. The server will also notify the respective QuadTree server to refresh the driver’s location.
We’ll need to broadcast driver locations to our customers. We can use a Push Model so that the server pushes positions to relevant users. We can use a Notification Service and build it on the publisher/subscriber model.
When a customer opens the Uber app, they’ll query the server to find nearby drivers.
On the server side, we subscribe the customer to all updates from nearby drivers. Each update in a driver’s location in
DriverLocationHT will be broadcast to all subscribed customers. This ensures that each driver’s current location is displayed.
We’ve assumed one million active customers and 500 thousand active drivers per day. Let’s assume that five customers subscribe to one driver. We’ll store this information in a hash table for quick updates.
We need to store both driver and customer IDs. We need three bytes for DriverID and eight bytes for CustomerID, so we will need 21MB of memory.
Now for bandwidth. For every active driver, we have five subscribers. In total, this reaches:
We need to send DriverID (3 bytes) and their location (16 bytes) every second, which requires:
To efficiently implement the Notification service, we can either use HTTP long polling or push notifications. Customers are subscribed to nearby drivers when they open the Uber app for the first time.
When new drivers enter their areas, we need to add a new customer/driver subscription dynamically. To do so, we track the area that a customer is watching. However, this would get extra complicated.
Instead of pushing this information, we can design the system so customers pull the information from the server. Customers will send their current location so that the server can find nearby drivers from our QuadTree. The customer can then update their screen to reflect drivers’ current positions.
Customers should be able to query every five seconds. This will limit the number of round trips to the server.
To repartition, we can create a cushion so that each grid grows beyond the limit before we decide to partition it. Assume our grids can grow or shrink by an extra 10% before we partition them. This will decrease the load for a grid partition.
We’ll summarize how this use case works below.
We will need server replicas in case the Driver Location or Notification servers die. A secondary server can take control when a primary server dies. We can also store data in persistent storage like solid state drives (SSDs) to provide fast input and output. We can quickly use this persistent storage to recover data in the event that both primary and secondary servers die.
Uber also provides a ranking system for drivers. A customer can rate a driver according to wait times, courtesy, and safety. Let’s say we want to rank search results by popularity or relevance as well as proximity.
To do this, we need to return top-rated drivers within a given radius. Assume we track drivers’ ratings in a database and QuadTree. An aggregated number will represent popularity in the system based on these ratings. The system will search for the top 10 drivers in a given radius, while we ask each partition of the QuadTree to return the top drivers with a specified rating. The aggregator server will determine the top 10 drivers among all drivers returned by different partitions.
Now you know how to design Uber’s backend. This is a common question asked in system design interviews at top tech companies. There are many more common system design problems that your interviewers may ask you, such as designing TinyUrl.
To help you become a systems design pro, Educative has curated the Grokking Modern System Design for Software Engineers & Managers learning path. This path includes lessons on implementing microservices, using AWS architecture, and designing common systems for interviews. You’ll cover everything you need to know to design scalable systems for enterprise-level software.
Join a community of more than 1.6 million readers. A free, bi-monthly email with a roundup of Educative's top articles and coding tips.