Uber SubmitQueue: a high-performance speculative merge queue

Airbnb has a version of this internally that was pretty awesome called Evergreen, based on the Uber paper as well.

I wish more companies would open source their monorepo infra. A well done monorepo is a huge force multiplier on a large organization, but the OSS world is lacking a lot of the infra so everyone starts from a painful place and works up or has a bad impression of monorepos. Google's Piper is another example where open sourcing or selling it would have done wonders for the industry. In an age of agents landing code very quickly piper has scaled very well since it was already at unimaginable commit velocity, meanwhile everyone else is trying to rebuild source control to keep up.

I'm reading from the repo and I'm a little dumbfounded what's the innovation.

> SubmitQueue speculatively rebases and validates multiple changes in parallel against predicted future states of HEAD. When validations pass, changes land automatically. When they fail, SubmitQueue isolates the offending change and retries the rest — all without human intervention.

This seems to be a feature of GitHub (We have it in an old enterprise server installation) that does the same thing:

> When a pull request is added to the merge queue, the changes in the pull request are grouped into a merge_group with the latest version of the base_branch as well as changes from pull requests ahead of it in the queue. GitHub will merge all these changes into the base_branch once the checks required by the branch protections of base_branch pass.

https://docs.github.com/en/repositories/configuring-branches...

I understand not everybody uses GitHub but I'm pretty sure other providers also have similar features, e.g. https://docs.gitlab.com/ci/pipelines/merge_trains/#enforce-m...

So what's different/special about Uber's thing?

Keeping your trunk consistently green at scale is probably too costly. Not even Google can keep its google3 monorepo consistently buildable let alone green. It’s more worthwhile to keep trunk mostly green, stop chasing the final 0.1%, and instead develop tooling to quickly identify culprits to be rolled back automatically.

I believe that the solution to the coordination problem is good monorepo tooling (like the OP) plus AI to understand the whole codebase and help the engineers understand how their part fits in.

I was one of the biggest proponents of microservices, going so far as to traveling around the world spreading the gospel of microservices keynoting large tech conferences. I believed that microservices were the best solution to scaling large teams of developers, so that small teams could work on small problems, where the API was the only contract between them.

But even then I cautioned that the overhead made it not worthwhile for small teams -- that it was a solution to the coordination problem for large organizations. And that Google was not a counterexample because they had spent so many resources on their monorepo tooling.

But there is a new factor in town that changes the calculus:

AIs can grok monorepos much easier than a cluster of microservices. AIs change the calculus here. They allow the developer to work successfully in even the largest monorepos, and the AIs themselves will give better results when all of the code is in one place.

Alternatively: don't worry about keeping trunk "green" at all. Have a second branch called "stable" or something that auto-fast-forwards to latest trunk whenever trunk is green. Checkout stable, push new changes to trunk, avoid breaking CI, but if you break CI then don't worry about it, just push up a fix.

If you act like trunk is this "sacred" thing that must always be ready to deploy then what you end up with is a bunch of long-lived branches and PRs and all the merge conflicts and overhead that come with those.

I struggle with how these ideas meaningfully reduce the fundamental coordination problem.

The merge queue does provide serialization over change sets, but the ordering of these changes is very particular. Often, one change needs to go in before another change. The most common example I've experienced being database migrations.

It is a problem that ultimately must be solved externally. Speculatively deriving arbitrary order is likely to generate far more noise than signal in meaningfully complex merge scenarios. How many speculative orderings are we going to spend energy investigating before we find one we like / trust?

If you are in a situation where you have so much conflicting work that you think a specialized robot needs to be employed to sort it out, then you need to back the hell away from the technology and have a human conversation about the business and everyone's role in it.

The origin of this was from Uber ATC self driving division. We wrote the original submit queue inside of Phabricator and then it was eventually pulled out and made its own product.

It was fun to work on and find all the edge cases along the way.

So they reinvented OpenStack's Zuul?

I've always thought if you're pushing changes at the sort of velocity that requires it, you're doing something wrong, anyway.

Discussion of earlier work by Uber in this same vein, back when it was solely an internal product (to be clear, I don’t know how much the system has evolved internally since these posts, and I don’t know for sure that this system includes all the same components).

https://news.ycombinator.com/item?id=19692820.

Monorepo benefits maybe a small set of developers that manages it for the whole company, at the cost of most other engineers who develop in it. Unnecessary waste of time.

Case in point another new merge queue has to be created to somehow manage the messiness