Make your monorepo feel small with Git’s sparse index

https://github.blog/2021-11-10-make-your-monorepo-feel-small-with-gits-sparse-index/

by CRConrad • 5 years ago

221 151 5 years ago

github.blog

speedgoose5• 5 years ago

"One of the biggest traps for smart engineers is optimizing something that shouldn't exist."

Elon Musk.

solarmist4• 5 years ago

Let's make the snarky comment into a helpful comment. Why do you think it shouldn't exist?

speedgoose5• 5 years ago

Monorepos create more issues than what they solve.

joconde• 5 years ago

Was he talking about something specific?

plopz• 5 years ago

I remember him saying something like that during a walkthrough of the base building starship and if I recall it was in reference to overengineering something about the grid fins.

junon2• 5 years ago

He was talking about the battery vibrator plates or something in Tesla cars.

CRConrad4• 5 years ago

Wow, so he's actually said something smart for a change.

anaganisk2• 5 years ago

And then he comes up with Hyperloop.

arxanas5• 5 years ago

The index as a data structure is really starting to show its age, especially as developers adapt Git to monorepo scale. It's really fast for repositories up to a certain size, but big tech organizations grow exponentially, and start to suffer performance issues. At some point, you can't afford to use a data structure that scales with the size of the repo, and have to switch to one that scales with the size of the user's change.

I spent a good chunk of time working around the lack of sparse indexes in libgit2, which produced speedups on the order of 500x for certain operations, because reading and writing the entire index is unnecessary for most users of a monorepo: https://github.com/libgit2/libgit2/issues/6036. I'm excited to see sparse indexes make their way into Git proper.

Shameless plug: I'm working on improving monorepo-scale Git tooling at https://github.com/arxanas/git-branchless, such as with in-memory rebases: https://blog.waleedkhan.name/in-memory-rebases/. Try it out if you work in a Git monorepo.

stormbrew• 5 years ago

I'm working on improving monorepo-scale Git tooling at https://github.com/arxanas/git-branchless

I'm intrigued by this but the readme could maybe use some work to describe how you envision it being used day-to-day? All the examples seem to be about using it to fix things but I'm not at all clear how it helps enable a new workflow.

Even if it was just a link to a similar tool?

arxanas5• 5 years ago

Thanks for the feedback. I also received this request today to document a relevant workflow: https://github.com/arxanas/git-branchless/issues/210. If you want to be notified when I write the documentation (hopefully today?), then you can watch that issue.

There's a decent discussion here on "stacked changes": https://docs.graphite.dev/getting-started/why-use-stacked-ch..., with references to other articles. This workflow is sometimes called development via "patch stack" or "stacked diffs". But that's just a part of the workflow which git-branchless enables.

The most similar tool would be Mercurial as used at large companies (and in fact, `git-branchless` is, for now, just trying to get to feature parity with it). But I don't know if the feature set which engineers rely on is documented anywhere publicly.

I use git-branchless 1) simply to scale to a monorepo, because `git move` is a lot faster than `git rebase`, and 2) to do highly speculative work and jump between many different approaches to the same problem (a kind of breadth-first search). I always had this problem with Git where I wanted to make many speculative changes, but branch and stash management got in the way. (For example, it's hard to update a commit which is a common ancestor of two or more branches. `git move` solves this.) The branchless workflow lets me be more nimble and update the commit graph more deftly, so that I can do experimental work much more easily.

Buttersite• 5 years ago

Maybe this is a sign that monorepos are the problem?

arxanas5• 5 years ago

Why would this indicate that monorepos are the problem?

anon900112• 5 years ago

This is well written and deserves my upvote, because sparse-checkout is part of git and knowing how it works is useful.

That said, there's absolutely no reason to structure your code in a monorepo.

Here's what I think GitHub is doing:

1) Encourage monorepo adoption

2) Build tooling for monorepos

3) Selling tooling to developers stranded in monorepos

Microsoft, which owns GitHub, created the microsoft/git fork linked in the article, and they explain their justification here: https://github.com/microsoft/git#why-is-this-fork-needed

Well, because Git is a distributed version control system, each Git repository has a copy of all files in the entire history. As large repositories, aka monorepos grow, Git can struggle to manage all that data. As Git commands like status and fetch get slower, developers stop waiting and start switching context. And context switches harm developer productivity.

I believe that Google's brand is so big that it led to this mass cognitive dissonance, which is being exploited by GitHub.

To be clear, here are the two ideas in conflict:

* Git is decentralized and fast, and Google famously doesn't use it.

* Companies want to use "industry standard" tech, and Google is the standard for success.

Now apply those observations to a world where your engineers only use "git".

The result is market demand to misuse git for monorepos, which Microsoft is pouring huge amounts of resources into enabling via GitHub.

It makes great sense that GitHub wants to lean into this. More centralization and being more reliant on GitHub's custom tooling is obviously better for GitHub.

It just so happens that GitHub is building tools to enable monorepos, essentially normalizing their usage.

Then GitHub can sell tools to deal with your enormous monorepo, because your traditional tools will feel slow and worse than GitHub's tools.

In other words, GitHub is propping up the failed monorepo idea as a strategy to get people in the pipeline for things like CodeSpaces: https://github.com/features/codespaces

Because if you have 100 projects and they're all separate, you can do development locally for each and it's fast and sensible. But if all your projects are in one repo, the tools grind to a halt, and suddenly you need to buy a solution that just works to meet your business goals.

tsimionescu5• 5 years ago

Monorepos are much easier for everyone to use, and are the only natural way to manage code for any project. You keep talking about Google, but a much more famous monorepo is Linux itself. Perhaps Linus Torvalds has fallen into Google's hype?

The fact that git is very poor at scaling monorepos might mean that it's a bad idea to use git for larger organizations, not that it's a bad idea to use monorepos. If git can be improved to work with monorepos, all the better.

anon900112• 5 years ago

Monorepos are much easier for everyone to use, and are the only natural way to manage code for any project.

I strongly disagree with that, but I'll let this blog post explain it better than I can: https://medium.com/@mattklein123/monorepos-please-dont-e9a27...

You keep talking about Google, but a much more famous monorepo is Linux itself.

I thought it was fairly well known that monorepos came directly from Google as part of their SRE strategy. It didn't even come into common usage until around 2017 (according to wikipedia). If I'm remembering correctly, the SRE book recommends it, and that's why it gained popularity.

Also, I don't believe that Linux is a valid interpretation of "monorepo". Linux is a singular product. You can't build the kernel without all of the parts.

A better example would be if there was a "Linus" repo that contained both git and linux. There isn't, and for good reason.

The fact that git is very poor at scaling monorepos might mean that it's a bad idea to use git for larger organizations, not that it's a bad idea to use monorepos. If git can be improved to work with monorepos, all the better.

Any performance improvement in git is welcome, but anything that sacrifices a full clone of the entire repository is antithetical to decentralization.

The whole point of git is decentralized source code.

ratww7• 5 years ago

That said, there's absolutely no reason to structure your code in a monorepo.

Bullshit. There are very good reasons to use it in some situations. My company is using it and it's a tremendous productivity boon. And Git works perfectly fine for smaller scales.

Obviously, "because Google does it" is a terrible reason. But it's disingenuous to say that's the only reason people are doing it. Not everyone is a moron.

anon900112• 5 years ago

I'm glad you're having a good experience now, and git as a monorepo will work fine at smaller scales, but you will outgrow it at some point.

When you do, you have two choices. You can either commit to the monorepo direction and start using non-standard tooling that sacrifices decentralization, or you can break up your repo into smaller manageable repos.

I don't have any problem with small organizations throwing everything into one git repo because it's convenient.

My objection is that when you eventually do hit the limits of git, will you choose to break the fundamentals of git decentralization as a workaround? Or will you break up the repo into a couple of other repos with specific purposes?

I don't like that GitHub makes money by encouraging people to make the wrong choice at that juncture.

dboreham• 5 years ago

it's a tremendous productivity boon

Curious to hear more specifics on this. Did you migrate from separate repos to a monorepo and subsequently measure improved productivity as a result?

Orphis• 5 years ago

Git is decentralized and fast, and Google famously doesn't use it.

Most (all?) of Google OSS software is hosted on either Gerrit or Github. Git is not used by the "google3" monorepo, but it's used by quite a few major projects.

omegalulw• 5 years ago

Your take is extremely biased. You only just discuss why monorepos are bad.

Here's some of the many reasons why monorepos are excellent:

- Continuous integration. Every project is almost always using the lastest code from other projects and libraries it depends on.

- Builds from scratch are very easy and don't need extravagant tooling.

- Problems due to build versions in dependency management are reduced (everyone is expected to use HEAD).

- The whole organization settles on a common build patterns - so if you want to add a new dependency you wouldn't need to struggle with their build system. Conversely, you need to write lesser documentation on how to build your code - cause that's now standard.

anon900112• 5 years ago

Heh, the major problems that I've run into using monorepos in the real world at scale are:

- CI breaks all the time. Even one temperamental test from anywhere else in the organization can cause your CI run to fail.

- Building the monorepo locally becomes very complicated, even to just get your little section running. Now all developers need all the tools used in the monorepo.

- Dependencies get upgraded unexpectedly. Tests aren't perfect, so people upgrade dependencies and your code inevitably breaks.

It's cool that everyone is on the same coding style, but that's very much achievable with a shared linter configuration.

jeffbee3• 5 years ago

Git is ... fast, and Google ... doesn't use it.

Everything about git is orders of magnitude slower than the monorepo in use at Google. Git is not fast, and its slowness scales with the size of your repo.

ajkjk• 5 years ago

Very much doubt that's their corporate strategy. More likely it's as simple as: lots of people have monorepos; they have lots of issues with Git and Github; Github wants their business.

solarmist4• 5 years ago

From my understanding Microsoft is doing it because they want to use git for developing windows which is(was?) a large monorepo.

saghm• 5 years ago

Then GitHub can sell tools to deal with your enormous monorepo, because your traditional tools will feel slow and worse than GitHub's tools

The "tool" in this case is a feature being added to upstream git, which everyone gets for free. It seems reasonable to assume other git providers will also be adding support for it server-side where needed; I have to imagine Gitlab either already is or will be doing work to support monorepos as well, assuming there's enough demand for it. At worst, this seems like it could be trying to lock people into git generally rather than GitHub specifically, but more likely this is just work being done to support something that (potential) customers are already asking for.

nightpool3• 5 years ago

Is there a point in having a monorepo if you're all in on the microservices approach? I'm a big microservices skeptic, but as far as I understand it, the benefit of microservices is independence of change & deployment enforced by solid API contracts—don't you give that all up when you use a monorepo? What does "Monorepo with microservices" give you that a normal monolithic backend doesn't?

(Obviously e.g. an image resizer or something else completely decoupled from your business logic should be a separate service / repo anyway—my point is more along the lines of "If something shares code, shouldn't it share a deployment strategy?")

radlad2• 5 years ago

Monorepo with microservices gives you the ability to scale and perform SRE-type maintenance at a granular level. Teams maintain responsibility for their service, but are more easily able to refactor, share code, pull dependencies like GraphQL schemas into the frontend, etc. across many services.

nightpool3• 5 years ago

So basically each team has to reinvent devops from the ground up, and staff their own on call rotation, instead of having a centralized devops function that provides a stable platform? That sounds horrendous.

Although, that said, I can at least see the benefits of the "1 service per team" methodology, where you have a dedicated team that's independently responsible for updating their service. I'm more used to associating "microservices" with the model where a single team is managing 5 or 6 interacting services, and the benefits there seem much smaller.

echelon3• 5 years ago

Is there a point in having a monorepo if you're all in on the microservices approach?

Monorepos are excellent for microservices.

- You can update the protobuf service graph (all strongly typed) easily and make sure all the code changes are compatible. You still have to release in a sensible order to make sure the APIs are talking in an expected way, but this at least ensures that the code agrees.

- You can address library vulns and upgrades all at once for everything. Everything can get the new gRPC release at the same time. Instead of having app owners be on the hook for this, a central team can manage these important upgrades and provide assistance / pairing for only the most complex situations.

- If you're the one working on a very large library migration, you can rebase daily against the entire fleet of microservices and not manage N-many code changes in N-many repos. This makes huge efforts much easier. Bonus: you can land incrementally across everything.

- If you're the one scoping out one of these "big changes", you can statically find all of the code you'll impact or need to understand. This is such an amazing win. No more hunting for repos and grepping for code in hundreds of undiscovered places.

- Once a vuln is fixed, you can tell all apps to deploy after SHA X to fix VULN Y. This is such an easy thing for app owners to do.

- You can collect common service library code in a central place (eg. internal Guava, auth tools, i18n, etc). Such packages are easy to share and reuse. All of your internal code is "vendored" essentially, but you can choose to depend on only the things you need. A monorepo only feels heavy if you depend on all the things (or your tooling doesn't support git or build operations - you seriously have to staff a monorepo team).

- Other teams can easily discover and read your code.

Monorepos are the best possible way to go as long as you have the tooling to support it. They fall over and become a burden if they're not seriously staffed. When they work, they really work.

echelon3• 5 years ago

Should have also mentioned: all those changes to cross cutting library code will trigger builds and tests of the dependent services. You can find out at once what breaks. It's a superpower.

nightpool3• 5 years ago

None of this addresses my question—what benefits do you get from having monorepo-with-microservices over a monolithic backend? All of the things you mentioned would be even easier with a monolithic backend.

rsj_hn2• 5 years ago

Yeah, I've seen it used to allow teams to use consistent frameworks and libraries across many different microservices. Think of authentication, DB clients, logging, webservers, grpc/http service front ends, uptime oracle -- there's lots of cross cutting concerns that are shared code among many microservices.

So the next thing you decide to do is create some microservice framework that bundles all that stuff in and allow your microservice team to write some business logic on top. But now 99% of your executables are in this microservice framework that everyone is using, and that's the point where a lot of companies go the monorepo route.

Actually most companies do some mix -- have a lot of stuff in a big repo and then other smaller repos alongside that.

aranchelk3• 5 years ago

The more I've come to rely on techniques like canary testing and opt-in version upgrades the more firmly I believe one of the main motivations for monorepos is flawed: at any given time there may not be a fact of the matter as to which single version of an app or service is running in an environment.

At places I’ve worked when we thought about canary testing we ignored the fact that there were multiple versions of the software running in parallel, we classified it as part of an orchestration process and not a reality about the code or env, but we really did have multiple versions of a service running at once, sometimes for days.

Similarly if you’ve got a setup where you can upgrade users/regions/etc piecemeal (opt-in or by other selection criteria) I don’t know how you reflect this in a monorepo. I’m curious how Google actually does this as I recall they have offered user opt-in upgrades for Gmail. My suspicion is this gets solved with something like directories ./v2/ and ./v3/ — but that’s far from ideal.

coryrc• 5 years ago

Only binaries are released. Binaries are timestamped and linked to a changelist.

The "opt-in upgrades" are all live code. I know more than a few "foo" "foo2" directories, but I wouldn't want an actively-delivered, long-running service to be living in a feature branch so I would still expect anyone to be using a similar naming scheme.

eximius4• 5 years ago

that doesnt seem like a problem with monorepos (or otherwise).

youd just need to tag your releases, right?

aranchelk3• 5 years ago

I don't think it's a problem, rather I'm challenging a touted benefit.

In large monorepos the supposition is you've got a class of compatible apps and services bundled together. Version dependencies are somewhat implicit: the correct version for each project to interoperate is whatever was checked-in together in your commit.

I don't know how it works in practice at different orgs, but there's certainly an idea I've heard repeated that you can essentially test, build, and deploy your monorepo atomically, but the reality in my experience is you can't escape the need to think about compatibility across multiple versions of services once you use techniques like canary testing or targeted upgrades.

ASinclair• 5 years ago

I’m curious how Google actually does this

Branches are cut for releases. Binaries are versioned.

jeffbee3• 5 years ago

the main motivations for monorepos is flawed: at any given time there may not be a fact of the matter as to which single version of an app or service is running in an environment.

Your understanding of the motivations for monorepo is flawed. I've never heard anyone even advocate for this as a reason for monorepos. For some actual reasons people use monorepos, see https://danluu.com/monorepo/

Regarding your question, which I re-emphasize has got nothing to do with the arrangement of the source code, the solution is to simply treat your protocol as API and follow these rules: 1) Follow "Postel's Law", accepting to the best of your abilities unknown messages and fields; 2) never change the meaning of anything in an existing protocol. Do not change between incompatible types, or change an optional item to required; 3) Never re-use a retired aspect of the protocol with a different meaning; 4) Generally do not make any incompatible change to an existing protocol. If you must change the semantics, then you are making a new protocol, not changing the old one,

I don’t know how you reflect this in a monorepo

You don't. Why would the deployed version of some application be coded in your repo? It's simply a fact on the ground and there's no reason for that to appear in source control.

aranchelk3• 5 years ago

We may just be talking past each other, but in the link you provided, sections "Simplified dependencies" and (to a lesser extent) "Cross-project changes" are pretty much exactly what I'm talking about.

junon2• 5 years ago

What I'd really like to see is Git have the ability to consolidate repeat submodules down into a single set of objects in the super repository. Currently cloning the same submodule results in a copy of the repository for each path, which is absurd.

It's been something on my list to address on the mailing lists for a while, just haven't had time.

harvie• 5 years ago

I hope one day all of this will be as easy as in SVN. eg.:

I have repository https://example.com/myrepo

And i can simply do:

svn co https://example.com/myrepo/some/directory/

And i can work with that subdirectory as if it was actual repo. Completely transparently.

This i really miss in git.

Gigachad2• 5 years ago

I'm working in hell right now. The current company has the site frontend, backend, and tests in separate repos and it's basically impossible to do anything without force merging because the build is broken without a chicken and egg situation between the 3 pull requests.

laurent123456• 5 years ago

I worked at a company that not only did that, but also decided to split the main web app into multiple repos, one per country. It was so much fun to do anything in this project.

hinkley• 5 years ago

You might want the front end and backend to be compatible across revision numbers, so that’s less of a problem and more of an impedance mismatch with your process.

The tests are a trickier problem, in theory you could lock version numbers (the new behavior increments to the new tests) but tests have bugs, and this doesn’t solve two people making behavioral changes at the same time.

Short of merging the tests into the respective projects, going full feature toggle for all breaking changes is the only other lever that comes to mind.

williamvds3• 5 years ago

With shallow checkouts cloning is much quicker. You could try combining it with sparse checkouts too. You can even have Git fetch the full history in the background, and from a quick test you can do stuff like commit while it's fetching. Obviously the limited history means commands like log and blame will be inaccurate until it's done.

  $ git clone --depth=1 <url>
  $ cd repo
  $ git fetch --unshallow &
  $ <do work>

vtbassmatt5• 5 years ago

This is really expensive for the server (the unshallow step specifically). Consider a partial clone here instead.

zwieback• 5 years ago

Yeah, that's really the one thing I miss from my SVN days. I'm also still using Perforce, which can do even crazier things with workspace mappings.

xxpor2• 5 years ago

As someone raised on git, and is seriously confused/scared every time he has to use svn, I'm not sure what you mean. I use the folder git creates as a repo too?

williamvds3• 5 years ago

Per my understanding of SVN, a checkout only downloads the lastest version of all the files ("pristines"). Git on the other hand clones just about everything from the remote repository, giving you a fully-fledged repository locally. SVN operations that need more history like log and blame will communicate with the repository for that info.

afranchuk• 5 years ago

The subtlety is that the checkout command as written is checking out only a subdirectory, not the entire repository. Look closely at the given checkout url.

rq1• 5 years ago

What I was looking for recently is a way to make “sparse push”. And trigger a chain reaction with hooks.

Didn’t find anything interesting.

rurban• 5 years ago

Even better looks the new OTR merge strategy, which benefits everyone. Not only the tiny monorepo userbase.

haberman• 5 years ago

The index file stores a list of every file at HEAD, along with the object ID for its blob and some metadata. This list of files is stored as a flat list and Git parses the index into an array.

I'm surprised that the index is not hierarchical, like tree objects in Git's object storage.

With tree objects (https://git-scm.com/book/en/v2/Git-Internals-Git-Objects#_tr...), each level of the hierarchy is a separate object. So you would only need to load directories that are interesting to you. You could use a single hash compare to determine that two directories are identical without actually recursing into them.

In particular, I can't understand why you would need a full list of all files to create a commit. If your commit is known not to touch certain directories, it should be able to simply refer to the existing tree object without loading or expanding it.

I guess that's what this sparse-index work is doing. I'm just surprised it didn't already work that way.

arxanas5• 5 years ago

It makes more sense if you think of the index as a structure meant specifically to speed up `git status` operations. (It was originally called the "dircache"! See https://github.com/git/git/commit/5adf317b31729707fad4967c1a...) We desperately want to reduce the number of file accesses we have to make, so directly using the object database and a tree object (or similar structures) would more than double file accesses.

There's performance-related metadata in the index which isn't in tree objects. For example, the modified-time of a given file exists in its index entry, which can be used to avoid reading the file from disk if it seems to be unmodified. If you have to do a disk lookup to decide whether to read a file from disk, then the overhead is potentially as much as the operation itself.

There's also semantic metadata, such as which stage the file is in (for merge conflict resolution).

It's worth noting that you can turn on the cache tree extension (https://git-scm.com/docs/index-format#_cache_tree) in order to speed up commit operations. It doesn't replace objects in the index with trees, but it does keep ranges of the index cached, if they're known to correspond to a tree.

Make your monorepo feel small with Git’s sparse index

Related Stories