6 ms·

Uber SubmitQueue: a high-performance speculative merge queue

69 points by handfuloflight 3mo ago

inigyou 2mo ago
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.
- conradludgate 2mo ago
  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
  - inigyou 2mo ago
    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.
    - AlotOfReading 2mo ago
      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.
  - orf 2mo ago
    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?
  - fweimer 2mo ago
    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).
mi_lk 2mo ago
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
- kyrra 2mo ago
  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.
  - dastbe 2mo ago
    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.
  - inigyou 2mo ago
    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.
esprehn 2mo ago
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.
- esafak 2mo ago
  Keeping Master Green at Scale https://dl.acm.org/doi/10.1145/3302424.3303970 https://dl.acm.org/doi/10.1145/3302424.3303970
- kyrra 2mo ago
  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 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).
  - fragmede 2mo ago
    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.
    - kyrra 2mo ago
      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.
hyperpape 2mo ago
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 https://news.ycombinator.com/item?id=19692820.
deleted 2mo ago
[deleted]
kccqzy 2mo ago
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.
jedberg 2mo ago
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.
- consensus1 2mo ago
  Microservices is a deployment strategy. Monorepo is a code organization strategy. They are not mutually exclusive.
  - jedberg 2mo ago
    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.
    - claytonjy 2mo ago
      [dead]
- yissachar 2mo ago
medellin 2mo ago
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.
- akshayshah 2mo ago
  Huh - are you sure? I was pretty sure that the original implementation came from the Android & iOS repos.
- wbxp99 2mo ago
  For those wondering “why is this needed”, IIRC the build took ~6 hours, so batching builds and testing were necessary to keep up
sdfhbdf 2mo ago
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-and-merges-in-your-repository/configuring-pull-request-merges/managing-a-merge-queue#how-merge-queues-work 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-merge-trains https://docs.gitlab.com/ci/pipelines/merge_trains/#enforce-m... So what's different/special about Uber's thing?
- IshKebab 2mo ago
  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.
  - mac-mc 2mo ago
    Yes this existed at least since 2018 or 2019 at Uber.
- para_parolu 2mo ago
  I was long before github made it. Otherwise thing is similar from usage perspective
- egwor 2mo ago
  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
wasmperson 2mo ago
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.
- ReaLNero 2mo ago
  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.
  - wasmperson 2mo ago
    > 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.
- conradludgate 2mo ago
  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
bob1029 2mo ago
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.

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.

conradludgate 2mo ago
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
- inigyou 2mo ago
  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.
  - AlotOfReading 2mo ago
    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.
- orf 2mo ago
  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?
- fweimer 2mo ago
  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).

mi_lk 2mo ago

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

kyrra 2mo ago
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.
- dastbe 2mo ago
  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.
- inigyou 2mo ago
  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.

esprehn 2mo ago

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.

esafak 2mo ago
Keeping Master Green at Scale https://dl.acm.org/doi/10.1145/3302424.3303970 https://dl.acm.org/doi/10.1145/3302424.3303970
kyrra 2mo ago
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 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).
- fragmede 2mo ago
  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.
  - kyrra 2mo ago
    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.

hyperpape 2mo ago

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 https://news.ycombinator.com/item?id=19692820.

deleted 2mo ago

[deleted]

kccqzy 2mo ago

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.

jedberg 2mo ago

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.

consensus1 2mo ago
Microservices is a deployment strategy. Monorepo is a code organization strategy. They are not mutually exclusive.
- jedberg 2mo ago
  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.
  - claytonjy 2mo ago
    [dead]
yissachar 2mo ago

medellin 2mo ago

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.

akshayshah 2mo ago
Huh - are you sure? I was pretty sure that the original implementation came from the Android & iOS repos.
wbxp99 2mo ago
For those wondering “why is this needed”, IIRC the build took ~6 hours, so batching builds and testing were necessary to keep up

sdfhbdf 2mo ago

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-and-merges-in-your-repository/configuring-pull-request-merges/managing-a-merge-queue#how-merge-queues-work 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-merge-trains https://docs.gitlab.com/ci/pipelines/merge_trains/#enforce-m... So what's different/special about Uber's thing?

IshKebab 2mo ago
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.
- mac-mc 2mo ago
  Yes this existed at least since 2018 or 2019 at Uber.
para_parolu 2mo ago
I was long before github made it. Otherwise thing is similar from usage perspective
egwor 2mo ago
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

wasmperson 2mo ago

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.

ReaLNero 2mo ago
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.
- wasmperson 2mo ago
  > 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.
conradludgate 2mo ago
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

bob1029 2mo ago

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.