Transcript
Dhruva Juloori: I'm Dhruva. I work at Uber's developer platform. My work primarily focuses on handling continuous integration of changes at scale, especially in developer environments with high commit velocity. Today I'm here to share some insights and learnings from my experience at Uber on how we handle merging and continuous integration at Uber, all while keeping mainlines green for most of the repositories that are onboarded to SubmitQueue.
Why is Green Mainline Hard?
I would like to get started with the first principles. Why is maintaining a green mainline a hard problem today? What you see is a representation of a certain repository with commit points in the main branch, all being green, meaning that all the checks that developer cares are passing. Now there are two developers, Alice and Bob, basically create a new branch from the same reference point to introduce their changes respectively. Alice introduces the change C1 and Bob introduces change C2. Both of them test their changes in the CI. All the build checks and the test checks pass. Pretty good. Alice goes ahead and merges the change to the mainline. The mainline is still not broken. It's still green. When Bob goes ahead and tries to merge the change, the build steps fail on the mainline and the mainline is red, meaning it is broken, because both of the developers have tested their changes individually but not collectively together.
Now just imagine at scale when hundreds of developers are concurrently committing to a single codebase. Now for that matter, when we have an army of agents concurrently committing to a single codebase, it gets very hard to maintain the stability of the mainline. At Uber, we have about 4,500-plus engineers working from 10-plus global development centers, concurrently committing to six of our monorepos primarily. Go being the busiest and the largest, followed by mobile repos, iOS, Android, and then the backend repos, Java, Python, and finally the web. Our monorepos handle a scale about 65,000-plus changes per month and are home to 1,000-plus business critical microservices. They facilitate 100,000-plus deployments per month, and host about 135 million lines of code, or even more than that as we are speaking.
The Drawbacks of a Red Mainline
What are the drawbacks of a red mainline? Delayed rollouts. If your most stable branch is broken or red, you will not be able to release any features, patches, or enhancements to production that could directly impact any organization or a business in terms of cost. Hampered productivity. Since all the developers are trying to create a branch from the mainline, they might not be sure why their changes are failing in CI. Is it because of their changes or is it because of something else, which leads to a loss of time? Then, rollbacks become very complex because when hundreds of developers are concurrently committing, it gets very hard to restore back to the last known stable state because developers might have already created their branches and started developing. No business or an organization wants to be in this state because the mainline being broken or red impacts directly in terms of cost, time, and resources.
SubmitQueue: Uber's CI Scheduling System
How do we solve it? Welcome to SubmitQueue. This is what I work on at Uber. It's essentially Uber's merge queue. It provides an illusion of single queue to the developers to submit their changes. It guarantees reasonable SLOs for developers to land the changes very quickly. It utilizes CI resources very efficiently. Of course, it always guarantees green mainlines at scale even with thousands of changes per day or hundreds of changes per hour. Before diving deep, I would like to give a small high-level overview of the system, and we can take a working example to see how all of this fits into pieces. SubmitQueue broadly consists of four core components. The first one being the enumerator. It takes the queue of pending changes and builds the binary decision tree of all the possible builds for those changes, which we internally call as a speculation tree. Then the profiler.
It accepts the speculation trees built by the enumerator, and ranks the changes according to the landing order based on predicted build times. The prioritizer. It computes the probability of build needed for each node by predicting the change success. Also, by using the land ranking order information supplied by the profiler. The selector, this is the most easy one. It selects the top probability nodes, and schedules them as builds in CI based on the resource availability. Based on the build outcomes, it either rejects or lands the change to the repository.
Now let's see how all of this works by taking a working example. Let's say we have three changes, C1, C2, and C3 arrived in the order mentioned. For C1, there's only one possible build. You need to test the change C1 against the head of the mainline to make a decision either to reject or land the change. For C2, there are two possible builds. Since it has arrived after C1, C2 needs to be tested in the cases when C1 has passed and also in the cases when C1 is a failure. We denote these builds as B12 and B2. B12 represents the build steps for the change C2 against the head of the mainline and the change C1. B2 represents the build steps for the change C2 just against the head of the mainline. Now in a similar fashion for C3, we have about four possible builds.
We are testing the change C3 in all the cases of when C1 and C2 are successful and also when both of the changes are a failure. In this fashion, for n changes, we approximately need about 2 power n builds. Basically, these are all perfect binary trees, decision trees. For n changes, the total possible nodes are 2 power n minus 1. This possibly doesn't scale because we have very limited resources in reality, so we need better approaches on how we select or prioritize our builds in CI.
Conflict Analysis
First, we introduce the concept of conflict analysis. Until at this point, we assume all the changes conflict with each other. We cannot commit any change in parallel. If we can prove that changes are independent, it helps us to reduce the number of possible builds so that your tree height is very minimal. Also, it helps us to commit changes in parallel. How can we prove? We try to do conflict analysis among those changes by leveraging the build system. It could be Buck, Bazel, or any other build system for that matter. The intuition behind conflict analysis is two changes are said to be independent if they affect a disjoint set of build targets. Meaning that if two changes affect the same set of build targets, they are conflicting, otherwise they are not. Let's take an example. In this case, the change C2 and C3 are not conflicting with each other, but they both are conflicting with C1.
In this case, the total possible builds are 5. Basically we reduce it by a factor of 2. C2 and C3 can be committed in parallel, but they just have to wait for C1. This is a second example where the change C1 and C2 are not conflicting, but they both are conflicting with C3. The total possible builds are 6. If you just take a brute force approach, the total possible builds would be 7, basically 2 power 3 minus 1. We reduced by 1 build. Now just imagine at scale, like when there are n changes, like this conflict analysis could definitely help us to trim down the number of possible builds, and also helps us to commit the changes in parallel. So far, so good. What if actually real conflicts exist? There are high chances during peak traffic hours, like when our developers are trying to concurrently commit to a short repository, or maybe like very high density commit volume repositories. Conflicts can exist. In the cases when conflict exists, we need to be more smarter on how do we prioritize our builds.
Probabilistic Speculation
Then we introduce the concept of probabilistic speculation. What we do here is we try to compute the probability of build needed for each node in the tree. If you just take this tree as an example for the three changes, for B1, the probability of the build B1 needed to make a decision for C1 either to land or reject would be 100%, because there's only one possible build. For C2, you would need the build B12 only in the case when the build B1 is successful, and you would need the build B2 only when the build B1 is failure. The success and failure of build B1 depends on the change C1, essentially depends on what change are we building. In a similar fashion, you could try to compute the probability of build needed for all the nodes. This is just a concept of conditional probability of mutual exclusive events.
Once you compute the probabilities, you could select the top probability nodes as builds and schedule them in CI. So far so good. We thought so at least when we were implementing it at Uber, but that had actually introduced one more new challenge. If you just take this as an example, now basically we have two changes, the change C1 and change C2, and C2 has two possible builds, as I mentioned earlier, and C1 has only one build. Now if the C1 is basically changing a large subset of build targets in a monorepo, and change C2 is possibly a trivial change, though all the build outcomes of the change C2 have been evaluated in the CI, it still has to wait, because we don't know what build to consider to make a decision. In a similar fashion, this is an example for three changes. If C3 is a small change, and compared to the change C1 and C2, though all the builds of C3 have been finished, we don't know what build to consider to make a decision to land C3, because the builds of C1 and C2 are still in progress.
This actually causes a very detrimental effect on the queue, because the longer the change waits in the queue, the higher the chances of it conflicting with future incoming changes into the queue. What this means is, as the conflict rate goes up, the height and width of the tree increases, which means that the number of possible builds are increasing. Then we have to wait more and we have to build more to make a decision. In order to tackle that, we want to be in a position to land the change as soon as we determine it is safe to land. In both the cases, in the first case, C2 can be landed, because all of the builds have been evaluated in the CI, and yield the same outcome. In the second case, all of the builds of C3 have been evaluated in the CI and they have the same outcome.
To determine the safety of these changes and land them as soon as possible once we know they are safe to land, we introduce the concept of bypassing large diff, which basically means the changes can be landed faster if all of the speculative builds with conflicting changes ahead are evaluated and yield the same outcome. In this case, the change C3 can be landed because the order of landing doesn't really matter. Because the state of the mainline when the change C1 and C2 landed first and then C3 next would be equivalent to the state of the mainline when C3 landed first and then C1, C2 next. The order of operations doesn't really matter. It is just a commutative or associative. Like A plus B equal to B plus A, or A into B equal to B into A. The order of addition or multiplication here doesn't really matter. The result is always the same.
Now taking all of these factors into consideration, we want to prioritize our builds in such a way that we want to schedule all of the speculative builds of the possible bypassing changes, so that we can land changes faster. In the cases when changes cannot bypass its conflicting changes ahead, we only want to prioritize the most likely builds so that resources are used effectively. Now taking these two goals and putting them into a mathematical notation, we derive the following formula. The probability of build needed depends on the build outcomes of the conflicting changes ahead and the ability of the respective change to bypass its conflicting changes ahead. The next question is, how do we evaluate build outcomes and the finish times? We use machine learning to predict the change success and predict the build times. For each repository, we train classification and regression models. Our prediction accuracy for a classification model is about 97%, and mean absolute percentage error for our regression model is about 5% to 7% on average.
Our prominent feature set include some of the change characteristics like number of affected build targets, number of git commits in a particular diff, and number of files changed, status of pre-submit checks. Some of the dynamic speculation characteristics such as the height of the tree, the width of the tree, and the position of the node in the tree, things like that.
Architecture of SubmitQueue
Now summarizing our discussion. This is the overall architecture of SubmitQueue. Basically, there is an API through which developer submits the changes to merge into a repository. SubmitQueue accepts these changes, and enumerator does the conflict analysis between the changes and builds the speculation trees. Then profiler accepts these speculation trees and uses the build time analyzer to predict the build times of each node, and ranks the changes according to the landing order. Once the landing order is determined, the prioritizer tries to compute the probability of build needed by predicting the change success using the success predictor. Then the selector selects the top probability nodes and schedules them as builds in the CI. Based on the outcomes, it either rejects or lands the change. SubmitQueue has been at Uber since the tail end of 2018, this has been our journey. Our recent or the latest enhancements include the bypassing large diff compounded by the build time prediction.
After our recent rollout, we observed a significant impact in terms of resource usage in CI. Basically, for our major monorepos, we saw like a 53% drop in CI resource usage. Since we are building less, our CPU consumption got down by 45%. Since we have improved our prioritization, our wait times or our land times have been improved by 37%. We are able to land changes faster than what we used to before 2024.
Resources
These are some of the resources that we have published. "Keeping Master Green at Scale", is a EuroSys paper that we published in 2019. "Bypassing Large Diffs in SubmitQueue" is an Uber engineering blog. "CI at Scale: Lean, Green and Fast", we published this paper recently at ICSE 2025. "Slashing CI Costs at Uber" is an Uber engineering blog. Please feel free to check them out.
See more presentations with transcripts
