Git の大規模運用の課題と Linus Torvalds の設計思想について

Hosting Git repositories at scale is a nightmare. When Linus Torvalds designed the first version of *the information manager from hell* (that's actually the tagline for Git, look it up), he had a very specific use case in mind: his own. He wanted to replace BitKeeper, the distributed version control system that was being used to develop the Linux Kernel. Of course, the replacement had to be distributed too. The Kernel is an unusual software project; it is extremely decentralized, with many different maintainers for its many different subsystems. A distributed version control system is a natural fit for this workflow.

Twenty years later, Git has become an industry standard, but the truth is that its distributed nature is more of a hindrance than an advantage. The average open-source software project doesn't operate with a decentralized workflow. The average company definitely doesn't. They use the many advantages of the distributed model (such as being able to work offline, delay pushes, etc) but they very much rely on a centralized host. And hosting a Git repository, it turns out, is an incredibly hard thing to do.

What's hard about Git?

The challenge in hosting Git repositories at scale is inherent in the design of Git itself: a *distributed* version control system means that all instances of a repository are identical. There's nothing special about the repository on a Git server that doesn't apply to a repository on a developer's laptop. Although at first it may appear that this makes hosting Git repositories straightforward (simply put an HTTP daemon in front of an on-disk copy of a repository and you've got a Git server going!), there are many hard scalability and reliability challenges that make this quite the opposite.

In a normal Git repository, your code and metadata (files, commits, trees) are compressed and stored in *packfiles* — a simple binary serialization format which is convenient to deal with on a local machine, but not ideal to manage at scale on a server. Packfiles are the fundamental building block of Git storage *and* Git networking. When you push or fetch data from a repository, it's transferred as a packfile.

This is how Git works by design, but it would be fair to think that it needn't be that way. After all, you do not control the Git client (at least not without annoying your users and adding a lot of friction), but within the walls of your own server, you can do *anything* you want. Nothing ties you to using packfiles — Linus is not going to come over and check. The only restriction is that you do need to receive and send *packfiles* over the network for all Git operations.

Over the years, companies that tried hosting Git repositories at scale noticed that this *packfile*-based design was a major limitation on both availability and scalability. Packfiles are large binary files that must exist on a filesystem for Git to access them. The simple approach of having an HTTP server in front of a repository on disk has a very low ceiling. Ideally you'd want the repository to exist on many disks and many machines (this lets you run many Git operations in parallel, and keeps your repository available when a server crashes). But how do you do that?

There are broadly three possible approaches to accomplish this, in increasing order of complexity: distribute the filesystem, distribute the packfiles, or distribute Git itself.

Git without packfiles

Git is a content-addressable data store. All objects in a Git repository (blobs, trees, commits, etc) are keyed by the SHA-1 of their contents. This is something that intuitively maps very well to a distributed key-value store (the key is the SHA-1; the value is the actual object), and could provide a clean way to scale out the storage of a repository. But this actually doesn't work.

Here's the issue: the actual layout of a Git repository is a directed acyclic graph (DAG for short). You can look up any object via its SHA, but to perform even the most trivial operation in the repo, you must actually walk the DAG step by step.

COMMIT DAGTREE /main → c8f3?commit · c8f3NETWORK↓ OLDER COMMITSobjects 0/54 · round-trips 0key/value storeaa42a112c8f3e816f0214b70e8c487ab19b4d5c277b22dc83f7dc43040c22d6e21aa729a0db50f627cf191fe3e81b19092d080a5f31134e06c811f6e7a196e42e147b9086a70ce192ee45d83f7a9b02ec2a70c49b8e25ac074b1a93d47dd9b519d2a8c14d431dc31ef09e205

If you want to do an operation like listing the recent changes in a repository, you must process its commits. When you process a commit, you get a pointer to the root of its tree. From that tree, you get pointers to each file and each subtree. From the original commit, you get a pointer to its parent (the one that comes before it in the history). Crucially, at every step of this walk, you don't know the value of the next pointer until you fetch the previous one. If every fetch requires a round trip to a distributed store, things become very expensive very fast.

This approach to distributing Git at the object level has been tried before, many times, and it often fails at scale. The most promising implementation was attempted by my former mentor Shawn Pearce when he was working on the version control systems team at Google. His approach was storing the objects in a distributed hash table. This was only possible thanks to JGit, a custom Git implementation in Java. Like any good ol' Java library, JGit provides enough interfaces and factories and interface factories to abstract all the details of a normal Git repository, including replacing its on-disk packfiles with a DHT. Although the system worked and results were good enough for normal Git operations, the limitations of the Git protocol (which again, require *packfiles* to be sent over the network regardless of how you store data on the server) made the git clone performance bad enough to discard the design altogether.

GitHub and filesystems

A couple years after Git started to escape its Linux Kernel bubble, a scrappy startup was born in San Francisco. GitHub was founded in 2008 as a social coding platform with a very prescient tagline, "Git repository hosting: no longer a pain in the ass." I'm not joking here either, look it up. There was, all the way back in 2008, a broad consensus that despite (or perhaps because of) Git's distributed design, you actually needed a centralized way to host Git repositories to make them user-friendly, and doing this was very painful. GitHub was set on changing that.

Its platform started as (and mostly still is) a Rails monolith. The very first versions were running off a single, albeit beefy, machine, with a Ruby server and copies of the repositories on disk next to it. Scaling a Rails app is easy: deploy more instances of it. But in this particular case, since Git is involved, they quickly ran into the recurring question we're trying to solve here: If the Rails app needs to access the Git repositories on disk, how do you deploy more copies of them?

Being a thrifty bunch of misfits, the early systems engineers at GitHub tried the simplest approach that could possibly fix their scaling problems. The thinking was that, if they focused on distributing the *filesystem* (instead of packfiles, or Git itself), they could keep the Rails app unchanged and spend their time shipping more features for the ever-growing user base, instead of doing weird stuff with Git. Very pragmatic. It didn't work.

The team attempted many approaches to a distributed filesystem for Git data: the most obvious one, using NFS to store all repositories on a centralized server, was quickly discarded. The default implementation of Git makes a lot of assumptions about filesystem semantics (locking, tearing, reading, syncing...) that ensure decent performance on the local filesystem of a slow developer laptop, but pay no attention to how they behave over a networked filesystem. It was slow, and it was buggy.

Further attempts were made with (frankly, in retrospect, horrific) technologies that replicated the filesystem at the block level. A short-lived deployment with GFS. A longer-lived deployment based on DRBD. They all hit a wall. They were *terrible* to operate day to day, and they didn't make up for it with good performance. It all boils down to the design of *packfiles* on disk.

We've already seen how Git's graph-like data structures make round-trips prohibitively expensive. Unfortunately, a very similar principle also applies to the underlying data on-disk. There is no correlation between the layout of objects in the DAG and the way they're placed in a *packfile*. The key heuristic used when generating *packfiles* is minimizing their size; objects are placed randomly throughout the pack, they are compressed, and crucially they're rarely stored whole. Most objects are stored as a delta on top of another object in the same packfile. Reading an individual object, after following the many logical hops in the graph data structure, also involves following physical hops in the on-disk format.

COMMIT DAGTREE /HEAD·mergecommit · c8f3root /tree · f021server.tsblob · f7a9pack.tsblob · a112README.mdblob · c430Cargo.tomlblob · ef09main~1commit · 9d2aroot /tree · e8c4server.tsblob · d431pack.tsblob · b8e2README.mdblob · 21aaCargo.tomlblob · 92d0featurecommit · 74b1root /tree · 7a19