{"id":67031,"date":"2022-09-13T09:00:49","date_gmt":"2022-09-13T16:00:49","guid":{"rendered":"https:\/\/github.blog\/?p=67031"},"modified":"2022-09-13T09:54:52","modified_gmt":"2022-09-13T16:54:52","slug":"scaling-gits-garbage-collection","status":"publish","type":"post","link":"https:\/\/github.blog\/engineering\/architecture-optimization\/scaling-gits-garbage-collection\/","title":{"rendered":"Scaling Git\u2019s garbage collection"},"content":{"rendered":"

At GitHub, we store a lot of Git data: more than 18.6 petabytes of it, to be precise. That’s more than six times the size of the Library of Congress’s digital collections1<\/a><\/sup>. Most of that data comes from the contents of your repositories: your READMEs, source files, tests, licenses, and so on.<\/p>\n

But some of that data is just junk: some bit of your repository that is no longer important. It could be a file that you force-pushed<\/a> over, or the contents of a branch you deleted without merging. In general, this slice of repository data is anything that isn’t contained in at least one of your repository’s branches or tags. Normally, we don’t remove any unreachable data from repositories. But occasionally we do, usually to remove sensitive data, like passwords or SSH keys<\/a> from your repository’s history.<\/p>\n

The process for permanently removing unreachable objects from a repository’s history has a history of causing problems within GitHub, especially in busy repositories or ones with lots of objects. In this post, we’ll talk about what those problems were, why we had them, the tools we built<\/a> to address them, and some interesting ways we’ve built on top of them. All of this work was contributed upstream<\/a> to the open-source Git project. Let’s dive in.<\/p>\n

Object reachability<\/span><\/a><\/h2>\n

In this post, we’re going to talk a lot about “reachable” and “unreachable” objects. You may have heard these terms before, but perhaps only casually. Since we’re going to use them a lot, it will help to have more concrete definitions of the two. An object is reachable<\/em> when there is at least one branch or tag along which you can reach the object in question. An object is “reached” by crawling through history\u2014from commits to their parents, commits to their root trees, and trees to their sub-trees and blobs. An object is unreachable<\/em> when no such branch or tag exists.<\/p>\n

\"Sample<\/p>\n

Here, we’re looking at a sample object graph. For simplicity, I’m only showing commits (identified here as circles). Arrows point from commits to their parent(s). A few commits have boxes that are connected to them, which represent the tips of branches and tags.<\/p>\n

The parts of the graph that are colored blue are reachable, and the red parts are considered unreachable. You’ll find that if you start at any branch or tag, and follow its arrows, that all commits along that path are considered reachable. Note that unreachable commits which have reachable ones as parents (in our diagram above, anytime an arrow points from a red commit to a blue one) are still considered unreachable, since they are not contained within any branch or tag.<\/p>\n

Unreachable objects can also appear in clusters that are totally disconnected from the main object graph, as indicated by the two lone red commits towards the right-hand side of the image.<\/p>\n

Pruning unreachable objects<\/span><\/a><\/h2>\n

Normally, unreachable objects stick around in your repository until they are either automatically or manually cleaned up. If you’ve ever seen the message, “Auto packing the repository for optimum performance,” in your terminal, Git is doing this for you in the background. You can also trigger garbage collection<\/a> manually by running:<\/p>\n

$ git gc --prune=<date>\n<\/code><\/pre>\n
That tells Git to trigger a garbage collection and remove unreachable objects. But observant readers might notice the optional <date><\/code> parameter to the --prune<\/code> flag. What is that? The short answer is that Git allows you to restrict which objects get permanently deleted based on the last time they were written. But to fully explain, we first need to talk a little bit about a race condition that can occur when removing objects from a Git repository.<\/p>\n
Object deletion raciness<\/span><\/a><\/h3>\n
Normally, deleting an unreachable object from a Git repository should not be a notable event. Since the object is unreachable, it’s not part of any branch or tag, and so deleting it doesn’t change the repository’s reachable state. In other words, removing an unreachable object from a repository should be as simple as:<\/p>\n
    \n
  1. Repacking the repository to remove any copies of the object in question (and recomputing any deltas that are based on that object).<\/li>\n
  2. Removing any loose copies of the object that happen to exist.<\/li>\n
  3. Updating any additional indexes (like the multi-pack index<\/a><\/code>, or commit-graph<\/a><\/code>) that depend on the (now stale) packs that were removed.<\/li>\n<\/ol>\n
    The racy behavior occurs when a repository receives one or more pushes during this process. The main culprit is that the server advertises its objects<\/a> at a different point in time from processing the objects that the client sent based on that advertisement.<\/p>\n
    Consider what happens if Git decides (as part of running a git gc<\/code> operation) that it wants to delete some unreachable object C<\/code>. If C<\/code> becomes reachable by some background reference update (e.g., an incoming push that creates a new branch pointing at C<\/code>), it will then be advertised to any incoming pushes. If one of these pushes happens before C<\/code> is actually removed, then the repository can end up in a corrupt state. Since the pusher will assume C<\/code> is reachable (since it was part of the object advertisement), it is allowed to include objects that either reference or depend on C<\/code>, without sending C<\/code> itself. If C<\/code> is then deleted while other reachable parts of the repository depend on it, then the repository will be left in a corrupt state.<\/p>\n
    Suppose the server receives that push before proceeding to delete C<\/code>. Then, any objects from the incoming push that are related to it would be immediately corrupt. Reachable parts of the repository that reference C<\/code> are no longer closed<\/a>2<\/a><\/sup> over reachability since C<\/code> is missing. And any objects that are stored as a delta against C<\/code> can no longer be inflated for the same reason.<\/p>\n
    \"Figure<\/p>\n
    In case that was confusing, the above figure should help clear things up. The general idea is that one side (responsible for garbage collecting the repository) decides that a certain object is unreachable, while another side makes that object reachable and accepts an incoming push based on that object\u2014before the original side ultimately deletes that (now-reachable) object\u2014leaving the repository in a corrupt state.<\/p>\n
    Mitigating object deletion raciness<\/span><\/a><\/h3>\n
    Git does not completely prevent this race from happening. Instead, it works around the race by gradually expiring unreachable objects based on the last time they were written. This explains the mysterious --prune=<date><\/code> option from a few sections ago: when garbage collecting a repository, only unreachable objects which haven’t been written since <date><\/code> are removed. Anything else (that is, the set of objects that have been written at least once since <date><\/code>) are left around.<\/p>\n
    The idea is that objects which have been written recently are more likely to become reachable again in the future, and would thus be more likely to be susceptible to the kind of race we talked about above if they were to be pruned. Objects which haven’t been written recently, on the other hand, are proportionally less likely to become reachable again, and so they are safe (or, at least, safer) to remove.<\/p>\n
    This idea isn’t foolproof, and it is certainly possible to run into the race we talked about earlier. We’ll discuss one such scenario towards the end of this post (along with the way we worked around it). But in practice, this strategy is simple and effective, preventing most instances of potential repository corruption.<\/p>\n
    Storing loose unreachable objects<\/span><\/a><\/h2>\n
    But one question remains: how does Git keep track of the age of unreachable objects which haven’t yet aged out of the repository?<\/p>\n
    The answer, though simple, is at the heart of the problem we’re trying to solve here. Unreachable objects which have been written too recently to be removed from the repository are stored as loose objects, the individual object files stored in .git\/objects<\/code>. Storing these unreachable objects individually means that we can rely on their stat()<\/a><\/code> modification time (hereafter, mtime<\/code>) to tell us how recently they were written.<\/p>\n
    But this leads to an unfortunate problem: if a repository has many unreachable objects, and a large number of them were written recently, they must all be stored individually as loose objects. This is undesirable for a number of reasons:<\/p>\n