How Uber handles millions of ride/food requests efficiently part 2

Published in

Nerd For Tech

5 min readOct 28, 2021

A detailed introduction to Uber’s fulfillment architecture on top of Googles’ cloud Spanner

In the previous post, we introduced the previous generation of Uber’s fulfillment service. The service was not able to scale to serve the rapid growing number of users, which led Uber’s fulfillment team to rewrite the service. In this blog, we will look at the problems of the previous generation of fulfillment service and how Uber resolved them.

If you haven’t read part 1 of the blog, I would recommend you take a look at it. Key concepts and high level architecture overview introduced in the blog is necessary to understand this post. Link to first blog: https://megtechcorner.medium.com/how-uber-handles-millions-of-ride-food-requests-efficiently-part-1-2aa8db436204

The problems

As a quick recap, one of the primary goal of the fulfillment service is to find nearby available drivers for users efficiently. The locations of the driver and user are converted to strings using H3 library[3]. A database index is used to index the encoded geolocation string for fast retrieval.

NoSQL database is used for data storage. Since NoSQL database doesn’t support index (as NoSQL doesn’t have distributed transaction), Uber’s fulfillment team uses a separate table to store the index. To keep the data in the data table and index table consistent, the team follows a design pattern called Saga[4] to implement distributed transaction.

The key idea of Saga is to break a large transaction into a list of small transactions. For example, if we want to update data table and index table inside a single transaction, we can use two smaller transactions, T1 and T2. Inside T1, we update data table and inside T2 we update index table. If T2 fails after T1 is committed, the database is in an inconsistent state. To bring the database back to a consistent state, we need to commit a compensating transaction C1, which reverts the change we made in T1. It is easy to see that this approach can bring many complexities to the system while consistency is not guaranteed.

Data consistency

With Saga, it is tricky to achieve data consistency. Imagine the case that application server that is coordinating the transactions crashes before committing the compensating transaction C1, it could be hard to figure out what we need to do to restore the consistency of the database. What Uber does is to constantly compare the expected state and current state of the database to fix any mismatch. However, “As we (Uber fulfillment team) built more complex write flows using the Saga pattern, debugging issues across multiple entities (tables/rows) and services became even harder.” [2]

Application complexity

Leaking database transaction logics into the application layer can significantly complicate the application logics. Consider the Saga design pattern, the application layer needs to generate a compensating transaction for each change and coordinate the transaction commit and abort process. Therefore “handling all the infrastructure concerns at the application layer made the application extremely inefficient”[1].

Solution: NewSQL

If we think about the problems facing Uber’s fulfillment service, what they really need is a system that can provide the scalability of a NoSQL system while offering index and distributed transaction support. That’s exactly what NewSQL is for. After comparing many NewSQL solutions, Uber’s fulfillment team decides to migrate the data storage to Google’s cloud Spanner. Google’s cloud Spanner is a NoSQL database, which stores the data in mapping: (key:string, timestamp:int64) → value:string. On top of the NoSQL stack, it build distributed transaction support using two-phase commit. Later, SQL support is added to the database as well[6].

Cheatsheet of cloud spanner

Supports distributed transactions
Native-support for secondary index
Highly scalable and low latency

Architecture of fulfillment service on top of cloud Spanner

With cloud Spanner, the architecture is greatly simplified. Cloud Spanner database is replicated in multiple regions for high availability and reliability. The fulfillment service can be largely stateless. To update the location of the driver, it only needs to update the location in the supply entity table (Refer to part 1 on the definition of the table and sample database schemas.) The index is automatically updated by the Spanner. To find nearby drivers for the user, the application layer can directly send the SQL query, as specified in part 1 of the blog, to Spanner.

Uber fulfillment service architecture. Source: [2]

End of Story?

With the cloud Spanner, the architecture of Uber’s fulfillment is greatly simplified while the consistency and scalability issues are resolved. However is this the end of the story? Well, no. Software engineering can be much more complicated and many corner cases need to be handled to deliver a great service.

Spanner client

The out-of-box Spanner client doesn’t provide the asynchronous support which is essential to the fulfillment service. Further, the support for DML (data manipulation language) is not matured. Therefore the team built a custom Spanner client. Additionally, the custom client intercepts gRPC to improve observability and coalesces transactions to increase throughput.

Post commit events

Fulfillment needs to run post commit actions. One example is offer expiration. However cloud Spanner doesn’t have change data capture solution. The team built their own solution using a table.

The asynchronous tasks are stored in a special database table, called task queue. The entity table update and task queue task insertion are executed inside a single Spanner transaction. Tailer periodically scans the Task Queue table to discover new tasks. It sends RPCs to workers to dispatch the tasks to them. Though not mentioned in the blog, we could imagine the complexities of this subsystem. How do trailers know which tasks to retry if workers fail? How to scan the task queue efficiently without overloading the database? How to split the scan work to different tailer replicas?

Closing

With cloud Spanner, the fulfillment team is able to simplify the system while resolving the consistency and scalability issues. However, every system has its own limitations. Migration to Spanner also brings new complexities, such as customized Spanner client and task queue subsystems.