Uber SubmitQueue: a high-performance speculative merge queue

hhandfuloflight 8 days ago 30 commentsRead Article on github.com

⚡ Community Insights

Discussion Sentiment

43% Positive

Analyzed from 1503 words in the discussion.

Discussion (30 Comments)Read Original on HackerNews

sdfhbdf•8 minutes 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...

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?

esprehn•about 1 hour 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.

twic•9 minutes ago

> 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.

fastball•7 minutes ago

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

kyrra•24 minutes 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

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•16 minutes 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.

mupuff1234•8 minutes ago

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.

fcarraldo•3 minutes ago

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?

esafak•26 minutes ago

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

jedberg•22 minutes 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.

yissachar•7 minutes ago

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".

consensus1•11 minutes ago

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

jedberg•2 minutes 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.

kccqzy•about 1 hour 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.

medellin•22 minutes 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•10 minutes ago

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

inigyou•about 2 hours 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•about 2 hours 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

fweimer•20 minutes 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).

orf•about 1 hour 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?

inigyou•about 1 hour 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•38 minutes 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.

hyperpape•about 1 hour 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.

mi_lk•about 2 hours 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•about 1 hour 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.

inigyou•44 minutes 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.

sroussey•20 minutes ago

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.

dastbe•about 1 hour 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.

medellin•25 minutes ago

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