How Uber efficiently processes its millions of taxi and food orders. Part 1

Detailed analysis of Uber’s fulfillment architecture.

As described in [1], the fulfillment service must “get the client’s intention and implement it by selecting the right set of providers (performers) ”. For example, one of the possible intentions of the client is a trip from one point to another, and the provider in this case will be a free taxi driver who is as close as possible to the client. The ultimate goal of an order fulfillment service is an efficient search for available drivers near the client.

In this two-part series, we’ll take a closer look at Uber’s fulfillment service architecture and how it scales as the number of users grows. In this article, we will look at the previous generation of data modeling and architecture of fulfillment service, and in the next article, we will talk about why, as the number of users increased, Uber moved the fulfillment service to Google Cloud Spanner and how it made this transition.

The second part of the article can be found at link

High-level architecture overview

High-level architecture, source: [1]
High-level architecture, source: [1]

The diagram above depicts Uber’s previous generation high-level order fulfillment architecture. It is based on two data models: a delivery entity (Supply) and a trip entity (Trip). The essence of travel represents the unit of work, namely the journey from one point to another, while the essence of delivery represents the person who can do the job.

The essence of the trip

The entity of the trip is modeled as a list of waypoints, where the Waypoint contains information about the location (Location) and a number of tasks (Task) that we can perform in this location. Below is an example of defining the entity of a trip.

Disclaimer: The code in this article is how I would implement Uber fulfillment services based on information from [1] and [2]… I don’t work for Uber and I don’t know how they are actually implemented.

enum Task {
  PICK_UP
  DROP_OFF 
}
class Location {
  long longitude;
  long latitude;
}
class WayPoint {
  Location location;
  Task task;
}
class Trip {
  List<WayPoint> points;
}
// Простая поездка может содержать две путевые точки, одну с задачей PICK_UP 
// и одну с задачей DROP_OFF.

Essence of delivery

The delivery essence is a set of tasks that must be performed by the driver. For example, if a driver is taking a customer to a destination and accepts a request from a new customer, the delivery entity for the driver will have two waypoints: one for the current customer, DROP_OFF, and one for the new customer, PICK_UP.

Taxi and delivery services

The trip and delivery entities are managed by the taxi and delivery services respectively. These two services are independent microservices, the data of which is synchronized at the storage level. More information on this can be found in the infrastructure section below.

Geospatial index

A geospatial index stores location information for drivers and customers. It is used to match the location of a customer with the location of drivers, that is, to find the closest available drivers for a specific customer. The geospatial index is at the heart of the matching process, so its performance is extremely important.
Uber uses a geolocation code called H3 [2]… As shown in the picture below, the entire map is divided into hexagons, the so-called cells. Each hexagonal cell is assigned a unique string identifier.
H3 divides the map into hexagonal cells, source: [2]
H3 divides the map into hexagonal cells, source: [2]

The H3 library provides functions to efficiently convert location data (longitude and latitude) to an H3 cell ID and convert an H3 cell ID back to a location. [3]… Below is an example of using the H3 library.

function example() {
  const lat = 37.7955;
  const lng = -122.3937;
  const res = 10;
  return h3.geoToH3(lat, lng, res);
}
// output: "8a283082a677fff"

With a geospatial index, we don’t need any special maintenance for storing or retrieving data from the database. Hence, any database can satisfy our functional requirements (but not necessarily performance requirements!). If we were using a relational database, we could define the following schema for storing driver information. The “location” field stores the cell ID h3.

create table driver (
  driver_id INT NOT NULL,
  given_name VARCHAR(100),
  surname VARCHAR(100),
  location VARCHAR(30),
  available BOOLEAN,
  ...
);
create index driver_by_location_and_availability on table driver (location, available);

If the driver’s location is updated, then implementing this in the delivery entity service can be no more complicated than a database update statement changing the location.

Comparison

Matching is the process of finding available drivers for a client. With geospatial encodings, the mapping process involves two steps.

Step 1: find the cells of interest

The figure on the right shows the user and the area of ​​interest (district).
The figure on the right shows the user and the area of ​​interest (district).

Suppose a customer is on Market Street and we want to find all available drivers in this area (highlighted in a red circle). Our first step is to call the h3.geoToH3 () function to get the cell id of the client’s location. We then call the h3.kRing () function to find the IDs of the 6 hexagons adjacent to the customer cell. (The definition of the kRing () function is shown below.) In total, we will have 7 lines covering the area inside the red circle, and we will store them in an array called cells_of_interest.

The definition of the kRing function:

List kRing (String origin, int k);

Step 2: search the database

We could just use a database query to find suitable drivers.

SELECT driver_id
FROM driver USING INDEX (driver_by_location_and_availability)
WHERE available AND location IN cells_of_interest;

Infrastructure

Uber infrastructure, source: [1]
Uber infrastructure, source: [1]

The image above shows the fulfillment service infrastructure. It has three main components: a service to run application logic, a database to store data, and a transaction manager to ensure consistency.

Uber uses Pod to launch its independent microservices [6]… Consistent hashing is used to separate work across different service instances. Consistent hashing also improves in-memory cache hit rates. Besides in-memory cache, there is another layer of caching provided by Redis.

Data is stored in Cassandra [7] – NoSQL database. Given the volume of Uber data and the frequency with which it is updated, NoSQL is better suited to their performance requirements. The service also maintains replay logs in Kafka. Replay logs record what changes have been made to the database. For example, in one entry, you can note that the driver’s location changes from “axxx” to “ayyy”. If writing to the database fails, we can simply rerun the commands stored in Kafka to bring the database into a consistent state.

There are two mechanisms to implement transactions on top of a NoSQL database. A sequential queue in each service instance is used to sequence incoming requests, and Saga [5] used to implement distributed transactions. Distributed transactions are needed when we need to update multiple records atomically. For example, when a driver accepts an order, we need to update the driver entity and the customer’s trip entity in one transaction. Otherwise, the database may remain in an inconsistent state, on the client side, the request is accepted by the driver, but on the driver side, the request is not accepted.

Recommended reading

Part 2 of the series, which explores how Uber scales fulfillment services with the Google Cloud Spanner database, can be found at link

Links

The translation of the article was prepared on the eve of the start of the course “Microservice Architecture”

Similar Posts

Leave a Reply