Uber SubmitQueue: a high-performance speculative merge queue | Hacker News Reader

Uber SubmitQueue: a high-performance speculative merge queue

github.com

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.

Keeping Master Green at Scale https://dl.acm.org/doi/10.1145/3302424.3303970

The problem with many of these tools is they are built on lots of other tech, like S3 dev called out: https://x.com/haipingfu/status/2084880266858995990

Piper is built on lots of other tech like spanner and chubby and many others. And some of those have specific hardware requirements that only exist in Google datacenters. Untangling that web of tech is neigh impossible (or not something worth the cost to leadership).

Why is that a problem? They sell Spanner on GCP. Sell Piper as well! It's obvious as shit but Google doesn't know what it's doing anymore. They should have bought GitHub, not Microsoft, and then we wouldn't have had the problems with scaling GitHub either.

Piper only works with CitC. Which is effectively a virtual file system when mounted locally. And when you have a monorepo that big, standard tools that want to scan an entire directory will stop working. Every part of the developer tool chain has to change to deal with code base that big.

I agree that Google should have bought github. The tech they built to scale Google Code I think would have helped a ton with GitHub.

They sell and support Google Drive on Mac and windows, and the web. Selling a VFS layer is entirely within their capabilities. Blaze/Bazel has already been exported. You're right that there's a whole stack, but if Facebook can make jj happen, Google could make hg happen.

> A well done monorepo is a huge force multiplier on a large organization

How so?

I work at a company which uses a monorepo, and I haven't seen any upside to it yet. We have a tools team that's invested a vast amount of work in it. Still seems strictly worse than a 'normal' polyrepo setup. I haven't understood why so many people are so enthusiastic about it.

Do you do any cross workspace/repo work, or are you mostly constrained to a single namespace?

Not op but I do cross repo work, but it's rightfully separate PRs as its separate services, separate contracts and separate deployments. Pretending a monorepo cross service PRs are contiguous is a recipe for deployment race conditions

Is it one or the other? You either need to keep everything in separate PRs or you need to pretend that services are contiguous where deployment order doesn't matter?

1. No submodules. They suck. They don't work with worktrees. They're a pain to work with.

2. Cross-project changes become trivial instead of nightmarish.

3. Testing becomes tractable. Make a change in a submodule? Good luck testing that it doesn't break any of the other repos that depend on it. You essentially turn its API into a fully public API, which introduces a ton of extra work (if you do it right, which nobody does).

I don't understand how come monorepos never just got "solved", and why git didn't expand in that direction.

I switched from a company with a monorepo to one without, and it just feels like going back to the stone age.

I work at a monorepo company and any time someone gets to work on a project that necessitates working outside of the monorepo, it's a night-and-day improvement.

Tools, especially open source ones (linters, static analysis, scanning, LSPs, IDEs, etc) are not built for monorepos, and with AI Agents working in the monorepo results in an enormous increase in input tokens as the agents are constantly trying to grep this giant source tree.

I'm sure it's possible that we're doing the monorepo thing wrong, but I'm genuinely curious what the upside is that you're experiencing? Or are these drawbacks unique to our implementation?

> Tools, especially open source ones (linters, static analysis, scanning, LSPs, IDEs, etc) are not built for monorepos, and with AI Agents working in the monorepo results in an enormous increase in input tokens as the agents are constantly trying to grep this giant source tree.

I've been thinking that one could dynamically patch .claude/settings.json (or its equivalent for other agents) to allow reads/writes only to the active app/package being edited and its dependencies (other packages/apps).

You can, if you have a trusted build graph. I know that “cone-shaped” checkout tools like this are common in monorepo environments, but unfortunately there aren’t any maintained open source implementations that I’m aware of.

This is a great idea.

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?

I think it's much cleverer about the order in which it tries to merge PRs, and how they are grouped.

GitHub merge queues just do it in the order you click.

Also I'm pretty sure it predates GitHub's implementation by a fair bit. Uber were one of the first people to do this. Maybe the first IIRC.

Yes this existed at least since 2018 or 2019 at Uber.

I was long before github made it. Otherwise thing is similar from usage perspective

I've been doing this for years (8+ at most recent place?) and we did it about 15years ago at place before. We keep having to relearn these features, which is on eof the reasons why some groups are far more effective than others

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.

Microservices is a deployment strategy. Monorepo is a code organization strategy. They are not mutually exclusive.

While you are technically correct (the best kind of correct), I would challenge you to find an organization that is doing the monorepo/microservice combo correctly. And what I mean by that is with microservices, the API is the only contract. Every service should be deployable independently.

If you have a monorepo, you're almost certainly violating that somewhere, using a shared library, or a shared database, or even just blocking deployment because some other service has turned the repo red.

You can have microservices while still using a monorepo. They are still useful for creating service topology that can segment scaling and permissions, though I think people get carried away in the number of services created.

I think the eventual sweet spot will be monorepos that have good modular boundaries, and dynamically adjusting service topology that doesn't rely on pre-committed decisions on what code lives in a "service".

IME, AI does find established patterns more quickly a in monorepo (sometimes the ones you want, sometimes the ones you don't) - but at the cost of an enormous overhead tax you pay on input token cost.

Giving agents pointers to the right patterns, libraries and services helps avoid expensive grep goose chases, but if you're already curating the input you can do the same thing with small repositories.

I'm going to play devil's advocate here.

As a developer, I quite like monorepos to a certain size (eg: until they get big enough that the tooling we typically use outside of big tech starts to fall down).

As an AI, I'm not sure that I care? I'd guess that context management can actually be easier if each microservice has a well documented API (openapi/graphql/grpc/asyncapi/whatever) and you provide the agent harness the ability to drop into each polyrepo as required (and give it the ability to access said documentation).

The tedium of making branches / commits / pull requests across 6 repos to land a feature is less problematic to an agent.

Admittedly the way I'm using agents at the moment is more repo orientated where it's sandboxed to a single repo, but conceptually I think polyrepo microservices could end up being a sweet spot.

> The tedium of making branches / commits / pull requests across 6 repos to land a feature is less problematic to an agent.

You're probably not using your microservices correctly if you need to change more than one service at the same time. The whole point of microservices is independently developing and deploying the services. Sweeping changes like that should be done in pieces, one service at a time.

Which is why microservices are best for larger organizations, because it reduces coordination between dev groups.

if service A calls service B, and service B adds a new endpoint, or a new optional argument, service A needs an update to take advantage of it

if a library is used by multiple services, and gets an important bug fix, each service using the library needs to update to get the fix

these are sequences of changes, not literally at the same time or requiring deployment coordination, but when this happens a lot people start asking about monorepos

But a monorepo wouldn't make any of that easier.

You have to make the change to service A and B, and then test both and deploy both. You haven't saved any time or effort in a monorepo.

A library needs updating, you still have to update it and then test and deploy every service that relies on it independently. Again you haven't saved any time or effort. In fact you've made it worse, because if those services are maintained by different people, you just forced them to test and deploy on your timeline and priority, not theirs. You actually made the coordination problem worse.

The big thing about monorepos in this case is making a change atomic across a set of projects. Multirepos can't do this 99% of the time and often add a lot more procedure to something close. It's inherently async.

> The big thing about monorepos in this case is making a change atomic across a set of projects.

The thing microservices is supposed to solve is eliminating the need to make atomic changes across services. There is an inherent overhead in doing that, like making your service support both new and old APIs as long as any service exists using the old API. This is the cost of microservices.

The world isn't just backend. There are mobile projects, games, native desktop apps which act together as a suite and web frontends. Also microservices bring up their own host of issues and extra labor. Both are essentially the semantic versioning library update problem, and when you need to propagate a breaking change it create a whole bunch more labor that is significantly reduced in a monorepo vs. a multirepo/microservice world.

The tradeoff is you need to invest into repo scaling, much like a backend service that needs to invest in scaling itself too.

I haven’t worked at a Big Tech monorepo place, but I hope/assume that in the service dependency case, you would touch both in one changeset and the deploy tooling understands the dependency tree and orders the deployments correctly. Without that i agree its the polyrepo approach just with all PRs in the same repo instead of multiple.

In the library scenario, I know tooling like bazel ensures that’s one changeset, not 3+. Tests run for both the changed library and all consumers of it in the same pass. You’re right that it might loop in others for review who weren’t expecting it, but i think that’s the same in a polyrepo approach.

IMO AI agents harnesses (claude code, codex, etc) haven't added monorepo features yet as of a couple of months ago and thats what makes them painful. Basic things like, only apply these skills to the subdir that the .agents/skills directory exists in would go a long way. Or even reading the skills in a subdir .agents/skills directory. Or the ability to specify the basic monorepo custom VCS and other actions in a way that isn't limited to fragile skills and AGENTS.md specs that can get forgotten or unused as the context windows grows in a session and so on.

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.

In my experience, it's a monorepo problem.

We have a monorepo at work and the CI only runs a minority of tests prior to merging, and then reverts bad commits later. It can take a few hours until every test has run including your commit. I don't know enough about the setup to know how it decides to run what tests though

Yeah that's true. It becomes O(N^2) with one factor of N being the number of commits to the repo, and another factor being the amount of CI stuff you do every time the repo changes.

You can do better than O(N^2) if your changes are monotonic /independent (or you're able to cache for basically the same reason). This usually requires either luck, a huge amount of programmer discipline, or very different programming languages than we're used to like unison.

How does it handle conflicts during reverting? If another merge depends on a change, and that change causes a failing/broken test, does it revert both?

It's not really about a monorepo, but how many changes you can have in flight in parallel. Desirability of merge-and-rebase-and-check depends on more factors: the rate of change, the number of developers, the time the pre-merge checks take and the reliability of those checks, and how often pre-merge checks fail (legitimately or otherwise). How conflict-prone queue changes are matters, too.

I would like to have something like this for one of the repositories I work on, which is pretty far away from being a monorepo (it's mainly producing two tightly interlinked binary objects). Fortunately, I believe Gitlab offers something like it, at least as a preview feature (under the namemerge-and-rebase or something like that).

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.

Huh - are you sure? I was pretty sure that the original implementation came from the Android & iOS repos.

For those wondering “why is this needed”, IIRC the build took ~6 hours, so batching builds and testing were necessary to keep up

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 don’t understand how this would work.

If you’re using Git and you branch off ‘stable’, you won’t be able to merge to ‘trunk’ unless you rebase to pick up all of its changes. If a commit were to be reverted in the trunk now you need to revert it from all PRs as well. In the end, it’s equivalent to having one branch.

> I don’t understand how this would work.

It's not all that strange: it's basically how version control worked before everybody switched to git. Anybody still on SVN is basically using this exact development model.

> If you’re using Git and you branch off ‘stable’, you won’t be able to merge to ‘trunk’ unless you rebase to pick up all of its changes.

Yeah, so you just do that. To be clear: most people would be doing their work on trunk. When I say "checkout stable" I mean "checkout stable if you need to start from something that passes CI". In the case where trunk passes CI or was recently passing CI this is basically the same as checking out trunk.

> If a commit were to be reverted in the trunk now you need to revert it from all PRs as well.

Most people push straight into trunk, no PRs needed. For the cases where you need PRs, reverting something in trunk won't affect them: `git revert` adds a new commit just like any other change.

If by "revert" what you actually meant was rolling back trunk to an earlier commit: don't do that.

How does this work with a monorepo with hundreds of teams around the globe? If you break the trunk, that means no other teams can release

> How does this work with a monorepo with hundreds of teams around the globe? If you break the trunk, that means no other teams can release

If you break trunk you just fix it. If a release needs to happen urgently and trunk is broken then you can use stable, which is the last working version of trunk.

EDIT: RE: hundreds of teams: If it's a bunch of independently-built things (libraries, programs, or servers) that happen to share a repo then it will work fine. If you're talking a single mega-project like Linux then maybe not, but Linux is pretty exceptional.

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.

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.

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

It's really the case that Git is terrible at scale. Honestly most source control is.

When you have teams of 10,000+ people working on code, if you wanted to shard it, it will be lots of little projects, then you're going to have dependency hell. The core in for teams will either have to spend most of their time upgrading everyone's packages, our other teams are going to have to deal with those upgrades.

The core infra teams are either supporting lots of versions all at once, or spending extra time on source control.

I don't know about Uber, but at Google the monorepo is absolutely amazing.

I will the one big issues that is really hard in a monorepo, if you want to upgrade some external library not built by Google, when that library has a large breaking API change, it will never get upgraded.

this was always the nice thing at amazon, because you never needed an atomic migration with version sets.

it was definitely a case of making many things worse to do than in a monorepo, but more things viable to do.

It should be sharded per team.

I think many shops made the mistake of sharding per deployment unit or compilation unit of a larger whole. My first exposure was sharding per executable file of a firmware image. That's just terrible. You can't coordinate changes that you want to be atomic in the firmware image.

In response I think some people went to monorepo to get atomic change sets but now they're too big. If you have an android app team and a backend team, and they don't deploy together or build together or do anything together besides agree on an API, which has to be backwards compatible anyway because apps don't instantly self-update, there's no need to put those things together if it causes headaches. It's probably better to have too many things together than too few, but neither is ideal.

No, team is way too small. Team group is a better resolution. You want a certain amount of ownership for a repo that will survive a team being laid off, for example. And a bit of cross responsibility may seem annoying to a single IC, but is beneficial to the company.

I use the word team loosely as people who work together, not people under a single direct manager. Thanks for the clarification.

That doesn't counter my point - yes there'll be dependency hell but at the same time fundamental developer tools like code intelligence or basic git operations take eons to complete or need strange workarounds

So code infra/library team benefit from monorepos but at the same time most other developers have to suffer

I don't know about Google but monorepos I've worked in are painful and far from ideal dev experience

I know what kind of engineer you are from this comment.

A good one probably. Because he's obviously correct.

Reply on news.ycombinator.com