Machine-generated source transcript; recognition errors remain. Timestamps and subtitles use the selected source recording’s clock, not clip-relative time. Section links use cited source moments; sections without a verified moment return to the talk start.
0:00:04 Hello everyone. We are here to present our talk, merging at AI scale. This is essentially
0:00:12 Uber's journey from going to a fully green trunk to somewhat broken trunk. I'm Preetam
0:00:21 Dwivedi. I'm a staff engineer at Uber working in developer platform.
0:00:25 Hi, I'm Manjiri. I'm a senior engineer working alongside Preetam in the developer plan at Uber.
0:00:32 Great. So here's the outline for the talk.
0:00:36 We're going to go over how the merging works at Uber at the moment,
0:00:41 and then how AI changed the landscape,
0:00:44 and then how to respond to that, how we adapt it,
0:00:48 and then discuss the results and talk about what are we planning next.
0:00:52 So at Uber, we have six language-based monorepos, where more than 5,000 developers are contributing
0:01:05 over 36,000 commits, 27,000 PRs every week.
0:01:12 And pretty much every changes to the services libraries are being done in one of these monorepos.
0:01:19 For the purpose of this talk, we're going to focus mostly on Go code when we talk about
0:01:24 anything because that is the biggest one and that's where the most of the scaling challenges
0:01:28 we face. So let's understand the problem a little bit and understand why we need a merge queue here.
0:01:38 So given here, basically we have two users, user A and B, grading PR A and B on a base edge from
0:01:48 the trunk and when the PRs are created and CI is run, the CI is green, builds are passing,
0:01:54 everything is good. Now when A is merged into the trunk, we can see the builds for the merge
0:02:02 commit are still green, builds are still passing, but when the PR B is merged into the trunk,
0:02:10 builds are no longer green. And the reason is that B was never tested with the changes that
0:02:16 were merged by A. So we never tested the combination of those two things before merging,
0:02:24 and hence when B is merged, it's broken. Now imagine when we have thousands of
0:02:32 engineers working in a monorepo and everyone is making changes, like hundreds and thousands of
0:02:40 those every day. This is a constant problem where trunk is broken very frequently and there is a
0:02:48 burden on fixing and there is a toll across the company to sort of figure it out and fix it.
0:02:57 So here we're going to present a solution to that problem and that solution is Summit Queue.
0:03:03 That is our Uber's merge queue that we deploy to solve this problem.
0:03:09 And in this case, we can see our two examples here, PRA and PRAB.
0:03:14 And here, essentially, what we are doing is we are predicting the futures that could be true on main.
0:03:21 So there are three things here.
0:03:23 A could land on its own to the main.
0:03:26 B could land on its own to the main.
0:03:29 And then the combination of A and B.
0:03:31 In general, I think what we're going to do is that we want to land the change that is going to keep the trunk green as a whole.
0:03:38 So in this case, when we land A and B together, the trunk is green.
0:03:43 And that's how basically SummitQ works and keeps the trunk green for our monorepos.
0:03:50 Now, how does it scale in this version of it?
0:03:54 There are three things that SummitQ employs.
0:03:57 The very first thing is target analysis.
0:03:58 What it means is when two users are working across two different services, they don't really have any overlapping changes.
0:04:07 So those two things can be built and tested independently of each other and then can be merged.
0:04:13 So this allows us to basically get higher throughput and not serialize every change that is entering into the queue.
0:04:20 Second is probabilistic speculation. What it means is we are using historical
0:04:27 the build information and also the the change characteristics to predict what is the success
0:04:34 score for a given change. And then we are using that to basically decide what our builds are
0:04:41 likely needed in order to land that change. And so in that case we prioritize the builds that are
0:04:46 most likely needed and are important for that change
0:04:50 to be much to the trunk rather than like every other build
0:04:53 that comes from the speculation.
0:04:55 The third part is bypassing the large changes.
0:04:58 What it means is that if we have a large change
0:05:00 sitting in the queue, which is taking longer to build,
0:05:03 and at the same time if we have a smaller changes entering
0:05:06 into the queue, those can be built faster.
0:05:09 And so those changes don't need to wait for large changes
0:05:12 to land before they can land.
0:05:14 So in this case, we can land the smaller changes
0:05:16 without landing the larger changes first.
0:05:18 And this optimization allows us to basically move fast
0:05:22 and get a higher throughput of the queue.
0:05:24 So this is what has worked
0:05:27 when it was just humans landing changes, creating PRs.
0:05:33 But then we had AI,
0:05:36 and the changes at which the PRs were created and landed,
0:05:41 it all changed.
0:05:43 So to understand it better,
0:05:45 let's look at some of the numbers.
0:05:46 So in January 2026, we were doing roughly 90 requests every hour.
0:05:55 And by March, we were doing 130 requests every hour.
0:05:59 So that's roughly a 44% increase in two months.
0:06:03 And the reason for this increase is primarily because of the AI-generated changes.
0:06:08 Now, given the way the system was built, the rate of these changes had effect on it.
0:06:18 So looking into those, we had 30 minutes of P95 line times when we were doing 90 requests every hour.
0:06:27 And that went to roughly three to four hours when we were doing 130 requests every hour.
0:06:34 So in this case, we were still keeping the trunk green at all times, but at the cost of developers essentially waiting for three to four hours to land their changes to the trunk.
0:06:46 Now I'm going to hand over to Manjri, and she's going to talk about our response to it and how we adapted to the situation.
0:06:55 Great. Thanks, Pritam.
0:06:56 So, Pritam just walked us through a few optimizations that SubmitQ had that worked so far in keeping up with the demand that humans generated.
0:07:07 But once AI came into the picture, the optimizations we had were no longer sufficient.
0:07:12 So, our response essentially was another set of optimizations to our existing SubmitQ.
0:07:20 And we approached the response in three different ways.
0:07:23 The first was we introduced this concept of admission gating, which helped us to shape the traffic that we accept into the queue.
0:07:31 Next, we introduced the concept of deferrals, which is a secondary queue that we introduced that helps with developer experience from the pain that comes with admission gating.
0:07:43 And lastly, we implemented what we call conflict relaxation, which helps us buy back more parallelism within the queue itself.
0:07:54 Next, we will look at each of these interventions in a little bit of depth and understand exactly what each of them are doing.
0:08:03 So the first one, admission gating, is basically what it sounds like.
0:08:08 There is a gate at the admission of every request into the main submit queue.
0:08:12 we look at the request that comes in and we categorize it as one of two things.
0:08:19 Either it's a small change or it's an expensive change.
0:08:22 And the definition of this could be anything.
0:08:25 One of the definitions that we use is the target analysis that Pritam talked about earlier in the slides.
0:08:32 A small change touches fewer targets.
0:08:35 an expensive change might be something that spans across multiple targets,
0:08:41 the entire build graph, something like that.
0:08:44 So a smaller change is more likely to give you higher parallelism.
0:08:49 And we basically say admit it during peak hours and add it to the active
0:08:54 submit queue, build and test as usual and move along.
0:08:59 But an expensive change has the capability to basically be a bottleneck
0:09:04 by holding resources needing to validate against everything else that's in the queue.
0:09:11 So to protect the rest of the queue, what we do in this phase is just to reject any expensive change during peak hours.
0:09:21 What this means is that the developer has to come back and retry their expensive change outside peak hours.
0:09:28 So this gives us control into what enters the queue by moving the burden onto a very small subset of changes and developers.
0:09:40 Let's look at the trade-off of admission gating.
0:09:44 After we implemented this, we definitely observed an increase in our throughput.
0:09:49 We were able to achieve over 20% increase.
0:09:51 Our land rate went from 130 to about 160 during business hours.
0:09:57 but it came at a cost. And the cost is that developers become the schedulers.
0:10:04 Not all developers, since we do protect the smaller changes, but you can imagine if you are
0:10:10 a developer who owns any types of libraries that span the entire code, you will be particularly
0:10:18 targeted in this because the work that you do naturally falls into the expensive change bucket.
0:10:25 So we managed to protect the capacity during peak hours, but had to make developers wait.
0:10:32 Next slide.
0:10:34 So the next thing that we do is targeted more towards bettering the developer experience of the cons that come from admission gating.
0:10:45 What if instead of outright rejecting expensive changes,
0:10:49 we are able to record them and replay them back into the main queue
0:10:54 based on the status of the queue
0:10:57 when we have, let's say, a better handle on the capacity.
0:11:01 And that's exactly what deferrals implement.
0:11:04 During peak hours, if an expensive request comes in,
0:11:07 we no longer reject it, but put it into a deferred queue
0:11:11 where it is perfected.
0:11:13 and once the gates permit, usually upon, for example, we can say after peak hours,
0:11:20 we put this persisted request back onto the active submit queue.
0:11:26 So essentially, we shape the traffic in a way where we release more expensive changes
0:11:32 when the queue is able to handle it.
0:11:35 So what this solves is a developer submits once and then we automatically release it for them
0:11:42 when the capacity allows.
0:11:44 Next slide.
0:11:45 So the trade-off here is
0:11:47 it solves the problem for the developer.
0:11:49 They don't have to wake up early,
0:11:51 stay up late,
0:11:52 try to find a particular window
0:11:54 where the queue looks good
0:11:56 and hit the button on their end.
0:11:58 We will handle that for them.
0:12:00 But the other side of this,
0:12:02 the path that comes with this
0:12:04 is that it doesn't really solve
0:12:06 the waiting for the developer.
0:12:09 You still have to wait
0:12:10 the same amount of time
0:12:11 for your expensive change to go into the queue.
0:12:16 Next slide.
0:12:18 So before we look at the next and final optimization that we did,
0:12:23 I want to touch a little bit on the concept of what a target overlap is
0:12:29 and how that serializes work in some way.
0:12:33 So recall that Fritam mentioned the target analysis that we perform
0:12:37 to determine whether two requests should be serialized
0:12:42 or can they go in parallel.
0:12:45 So an example that we are looking at here
0:12:47 is a strict one connected component.
0:12:50 What this means is that each of these requests,
0:12:53 A through F, touch some subset of targets
0:12:56 and there's at least one overlap of targets
0:13:00 between each pair of views.
0:13:02 So like A and B overlap on at least one target,
0:13:05 B and C overlap at least one target, similarly for C, D, E, and F. And what this makes SubmitQ do is
0:13:13 group all of these requests into a single component. And that means that all of these
0:13:19 have to go together. And this is basically what prevents us from doing work faster.
0:13:29 and the next optimization we do is how do we break this?
0:13:34 Is there a way where we can break this up in a smart way?
0:13:37 Next slide.
0:13:39 So conflict relaxation is what helps us break these links
0:13:43 in an informed fashion.
0:13:46 Before is basically the status quo.
0:13:49 Any relevant overlap between two requests
0:13:52 makes them conflict with each other
0:13:55 and makes them serialize one behind the other.
0:13:59 But with relaxation, we essentially do three steps.
0:14:03 First, we rank the overlap.
0:14:05 So it's no longer a binary decision of,
0:14:09 is there at least one overlap between these two requests?
0:14:12 Think of it more as a, how strong is this overlap?
0:14:17 Once we have that, we keep the stronger links
0:14:20 and relax the weaker ones to buy back parallelism
0:14:25 based on a config value that we set.
0:14:29 Next slide.
0:14:30 So the first step is essentially scoring these edges
0:14:33 or these overlaps.
0:14:35 We use a Jaccard scoring
0:14:36 for computing this dependency overlap.
0:14:39 We basically have overlapping targets.
0:14:42 We check for that
0:14:44 and any new dependency edges that are introduced.
0:14:46 We compute a combination of these two
0:14:49 into a continuous valued score between 0 and 1
0:14:53 where a higher value of score indicates a stronger overlap
0:14:57 and a lower value of the score indicates a weaker edge
0:15:02 with fewer targets that overlap between the requests.
0:15:06 Next slide.
0:15:06 Once we are armed with this knowledge,
0:15:08 we basically make this conflict graph again, right?
0:15:13 So taking the same example and adding some numbers
0:15:16 to the conflicts that we have from the earlier slide.
0:15:20 Let's say we have these six changes
0:15:22 and the config value we set says we want at least 50% parallelism in the queue at all times.
0:15:29 What this means is that we need at least three separate queues
0:15:34 that are working independent of each other.
0:15:39 And based on the overlap scores that we have computed,
0:15:46 we are able to make this choice of dropping certain edges
0:15:50 in order to be able to achieve that target queue size that we have.
0:15:55 So in this case, the weakest edges are between B and C and D and E.
0:16:01 And we drop those two, which gives us three separate connected components.
0:16:06 And this is how we essentially go from a serial chain of six requests
0:16:12 to a parallelized chain where two each exist in three separate queues.
0:16:19 Next slide.
0:16:20 So next comes a question of where exactly do we make this determination of dropping the edges, right?
0:16:29 So there are two places where we can do this.
0:16:32 One is at a global level.
0:16:35 Every time we are trying to assign conflict drafts and building them, we can basically recompute this every time.
0:16:44 And what that does is it introduces some level of instability into the graph, which is determined by any new request that enter the queue, any work that finishes and exits the queue.
0:16:58 So essentially, we can do that.
0:17:02 But what we chose to do instead was a more local assignment of overlaps.
0:17:09 And the place that we choose to do this at is only at the new arrival checkpoint.
0:17:16 So once a new request comes in, we essentially take that and compute the edges of this with everything that exists in the queue,
0:17:25 make the decisions and that's how it stays. The next decision making will only happen when another
0:17:33 new arrival comes in. So the concept is simple. We assign once at entry time and basically reuse this.
0:17:40 What this helps us do is any work that we schedule based on previous conflict graphs that we have
0:17:49 created is preserved and it helps us hang on to speculative builds that can help us move faster
0:17:57 towards a finalization of its best. So the trade-off of this final intervention was the
0:18:06 biggest that we saw. We saw over 50% increase in the throughput. So we went from about 160
0:18:13 lands per hour to almost 250, sometimes even greater during peak hours. So it worked in that
0:18:21 it not only helped us significantly improve our throughputs while giving us extremely good
0:18:30 P95 land times, but it came at a cost as everything does. And the trade-off that we have given away
0:18:37 here is basically what Pritham alluded to in the very first slide talking about the integration
0:18:44 testing. Some combinations of changes will land untested because we are dropping edges from our
0:18:53 conflict graph. What this means is main can now be broken and this creates essentially a new
0:19:01 obligation where we have to validate what lands after it has landed. And to talk a little bit more
0:19:10 about how we do this, I will hand it back to Pritam. Great. Thanks Manjri for walking us through
0:19:20 those three solutions that we employed. So taking back this example that we had initially,
0:19:27 We had basically two changes here, A and B, and say we do a pre-merge validation independently after relaxing those conflict between those two things.
0:19:39 And then say we landed.
0:19:40 So now the landed state is essentially A lands first, then B, and now the combination of A plus B fails on the truck.
0:19:51 So this is where we started at the start of this talk.
0:19:55 And so now we have a broken trunk again.
0:19:59 So now how are we dealing with this?
0:20:03 So we have a system here called StowPipe.
0:20:07 And StowPipe is our post-land validation system.
0:20:12 It's responsible for validating any commit that lands on
0:20:15 to the main and then making sure that
0:20:19 it detects basically if builds are broken. And if so, then
0:20:23 and it creates a recovery strategy for that.
0:20:28 Now, here we have basically two things.
0:20:32 One is every change that is being landed by SummitQ
0:20:36 lands onto the main trunk.
0:20:38 And then we have the second reference here,
0:20:41 or the pointer, if you call, is the verified main.
0:20:45 And the verified main is essentially the one
0:20:47 that is being managed by StowPipe.
0:20:51 So let's take an example to understand it better.
0:20:54 So imagine we have this commit A where main and verified main both are pointing to it.
0:21:01 This is a good known commit.
0:21:03 This is building.
0:21:05 This is green on the trunk.
0:21:07 Now let's say we have another set of commits that land onto the main, say B, C, and D.
0:21:14 Now main moves to point to the D commit.
0:21:18 So at this point, a store pipe is going to take this range of commits, essentially B, C, and D,
0:21:25 on top of A and validate these newly landed changes to see if this new state is still buildable and is still passing or not.
0:21:36 In this case, we can see it fails.
0:21:38 And so now a store pipe is not going to move the verified main pointer in this case.
0:21:44 it will just keep it at A because that's what the good known last commit is on the trunk.
0:21:51 Now over time more commits land under the trunk and main moves to commit G. So now between the
0:22:00 new state that we have G and the previously good known state which is A, we have more commits in
0:22:07 between. So we have B, C, D, E, F, and G commits in between. So now store pipe is going to take
0:22:15 those commit range and basically validate and see if those are buildable and if builds are passing.
0:22:22 So now say in this case builds are passing and so the store pipe will basically take the verified
0:22:29 main pointer and point it to the newly validated good known commit G in this case.
0:22:37 So that's what a store pipe does.
0:22:39 It is essentially observing the newly landed commits onto the main,
0:22:44 verifying if they can build or not.
0:22:46 And if they pass, move the pointer.
0:22:48 If not, then continuously look for more changes and keep validating.
0:22:55 So now let's look at when a commit landed on main breaks the trunk.
0:23:02 So what happens in that case?
0:23:04 As I said earlier, StowPipe is essentially validating and then detecting that it failed.
0:23:09 And on failure, it basically alerts.
0:23:11 So OnCall gets paged.
0:23:13 And as a response to this broken trunk, OnCall is responsible to prepare a fix or revert that change, get it reviewed, and then land through SummitQ.
0:23:25 and then eventually it merges back into the trunk
0:23:29 and then a stovepipe continuously validates the new state
0:23:33 to see if it has been fixed or not
0:23:36 and then accordingly move the pointer to the newly landed comment.
0:23:42 So with all of this, I want to just recap on basically what we have achieved.
0:23:49 So at peak times, we are able to do roughly 300 Lens per hour
0:23:55 we are still able to maintain our P95 land time to 30 minutes.
0:24:00 And this is essentially a 233% increase since the January numbers that we have,
0:24:08 which were like 90 lands per hour.
0:24:12 So with this, we are doing all this work in the open.
0:24:17 We have SummitQ and StovePipe being developed and everything is in the open source.
0:24:26 So if you want to explore and contribute, do scan the QR code, explore the project, and feel free to contribute to the project.
0:24:38 What are we doing next?
0:24:39 And as we have already done this work, we are still looking ways to make it better, optimize for throughput, handle the recovery process in a better way, and also improve on how we tag what is green or not.
0:25:00 So as a first thing we are thinking about is on SummitQ side basically batching related changes together.
0:25:07 So that way we run less number of builds and we can do more work with the same amount of resources.
0:25:15 Second is today we have a single pointer, verified main, which points whether a repository head is green or not, or a given commit is green or not.
0:25:25 We want to do better where basically we can say a given service is green, a given project is green.
0:25:31 So even if a commit on the trunk is broken, we can essentially tell which part of the trunk is broken and not all of it.
0:25:40 So that would allow us to basically do a better sort of rollouts of those services and changes, and we don't have to block it.
0:25:49 And the third one is basically, as I said, the recovery process from a broken trunk is manual.
0:25:56 So most of the investment is on automating the fixes or reverting the fixes and then landing those to Summit Q in an automated way so that our time to recovery can be reduced and we can fix the broken fronts faster.
0:26:13 And so as a closing point, I want to call out that we chose a hybrid approach to validating
0:26:21 the changes. One, we are still doing the pre-merge validations. We are still making sure that we
0:26:32 test the changes where it matters and relax the changes where we can take that hit and validate
0:26:40 validate them later after they land to the trunk. And then we are running the whole exhaustive
0:26:46 validation with the help of a store pipe post landing to the trunk. And that allows us to
0:26:53 basically have this balance where we are validating whatever matters before and then validating
0:26:59 everything at the end to make sure it is still right. And our consumers can consume the good
0:27:06 state. And with that, that would be our end of the talk. If you want to learn more about Summit
0:27:14 Queue and inner working software, feel free to scan these QR codes. These are the previously
0:27:20 talks that we have done on Summit Queue in depth, and they go over in detail on how it
0:27:27 functions internally. And again, thank you. Thank you.
