Scaling Git’s garbage collection

Why Git’s garbage collection is hard to scale

Git repositories accumulate junk over time: force-pushed commits, deleted branches, and other objects that no longer belong to any branch or tag. GitHub alone stores over 18.6 petabytes of Git data, and removing this unreachable data is occasionally necessary—especially when sensitive information like passwords or SSH keys needs to be purged from history.

The process of permanently removing unreachable objects has historically caused problems in busy or object-heavy repositories. Understanding why requires a closer look at how Git defines and handles unreachable data, and the tools we’ve built to make cleanup safer and more efficient—all of which have been contributed upstream to the open-source Git project.

Reachable versus unreachable objects

An object is reachable if you can get to it by starting from any branch or tag and crawling through history: commits to their parents, commits to their root trees, and trees to their sub-trees and blobs. Anything not contained within at least one branch or tag is unreachable—even if it has reachable objects as descendants, since it cannot be reached from any tip.

Unreachable objects can also exist in clusters entirely disconnected from the main object graph. Normally these objects remain in the repository until garbage collection runs—either automatically in the background or manually via:

$ git gc --prune=<date>

The --prune=<date> parameter is key: it restricts deletion to unreachable objects that haven’t been written since the given date. To understand why Git needs this age-based gating, we have to look at a race condition inherent to object deletion.

The raciness of deleting objects

Deleting an unreachable object should be straightforward: repack to remove the object and recompute dependent deltas, delete any loose copies, and update indexes like the multi-pack index or commit-graph. The problem emerges when pushes arrive during this process. The server advertises its objects at one point in time, but processes pushes that were based on that advertisement at another.

Suppose garbage collection decides to delete unreachable object C. If a background reference update makes C reachable before deletion completes—say, a push creates a new branch pointing at C—then the pusher may send objects that reference C without including C itself, since the advertisement listed it as present. If C is then deleted, the repository is left corrupt: reachable objects referencing C become missing, and any delta-based objects stored against C can no longer be inflated.

Git doesn’t fully prevent this race; instead, it mitigates it by gradually expiring unreachable objects based on their last write time. Objects written recently are more likely to become reachable again, so they’re retained. Objects that haven’t been touched recently are safer to prune. This strategy is simple and effective in practice, though not foolproof—we’ll revisit a scenario where it breaks down later.

The loose object problem

So how does Git track the age of unreachable objects that haven’t yet been pruned? Unreachable objects that are too recent to delete are stored as loose objects—individual files in .git/objects. Their filesystem mtime provides the age information Git needs.

The problem is that repositories with many recent unreachable objects must keep them all loose, which causes several issues:

• Objects with nearly identical contents can’t benefit from packfile deduplication, wasting significant disk space.
• A large number of files—particularly in a single directory—can exhaust inodes or degrade filesystem performance.
• Operations that scan all loose objects, like git repack -d, slow down as file counts grow.

Storing all unreachable objects in a single pack seems like an obvious fix, but it introduces a different problem: all objects in a pack share the pack file’s mtime. When Git needs to update any single unreachable object, it optimizes by touching the pack file’s mtime—which effectively resets the age of all unreachable objects in that pack. This makes it nearly impossible to expire any of them permanently, since they all appear perpetually recent.

Storing unreachable objects without the overhead

Git’s solution builds on an idea that has circulated on the Git mailing list for years: cruft packs. Instead of storing each unreachable object as its own loose file, Git packs them together and records per-object metadata alongside the pack.

A cruft pack consists of three files: the pack of Git objects itself, its pack index, and a new .mtimes file. The .mtimes file holds an array of 4-byte unsigned integers, one for each object in the pack. Each integer is an epoch timestamp representing that object’s mtime.

To look up an object’s mtime, Git performs a binary search on the pack index to find the object’s lexicographic position among the pack contents. That offset then indexes directly into the table in the .mtimes file. This design means all unreachable objects can live together in a single pack while each object still retains its own freshening timestamp, avoiding the drawbacks of both loose-object storage and rewriting whole packs for a single update.

Freshening on demand

Git cannot portably modify a file in place, so freshening an object—updating its mtime—requires writing a separate loose copy of that object. If every object in a cruft pack needed freshening at once, that would recreate the performance problem the design was meant to solve. In practice, such mass updates are uncommon, so writing loose copies for a small subset of unreachable objects is an acceptable trade-off in the typical case.

Building cruft packs: the reachable/unreachable split

Despite its name, git gc doesn’t always delete unreachable objects. The outcome depends on the --prune flag. With --prune=never, Git repacks all reachable objects and moves every unreachable object into a cruft pack. With --prune=1.day.ago, Git deletes unreachable objects older than one day before packing the remaining unreachable objects.

This behavior stems from Git’s handling of unreachable object closures. Git only needs a reachability closure over reachable objects, but its garbage collection tries to leave unreachable clusters intact: if Git encounters an unreachable cluster of objects, it will either expire the whole cluster or none of it—never a subset.

No expiration: three steps to a cruft pack

With --date=never, the goal is simply to consolidate all unreachable objects into a single cruft pack:

1. Starting from all branches and tags, generate a pack containing only reachable objects.
2. Enumerate objects in all existing packs that don’t appear in the reachable pack, and create a new pack containing just those unreachable objects.
3. Delete the existing packs.

Step one works like git repack -A. Git runs a reachability traversal beginning at each branch and tag, walking from commits to parents, trees to sub-trees, and so on, marking every object seen as reachable. This produces the set of objects destined for the new reachable pack.

The traversal above shows the same commit graph from earlier. The currently walked commit is dark blue; green marks visited commits. Git walks until it finds a commit with no parents or one already marked reachable. Repeating this across all references marks every reachable object.

Step two requires finding the complement—objects never marked. A naive approach would store all object IDs in a set and remove them during the walk. That’s impractical: each ID needs at least 20 bytes. The linux.git repository currently holds nearly nine million objects, requiring ~180 MB just to hold the IDs.

Instead, Git inspects every object in every existing pack, checking whether each appears in the new reachable pack. Any object in an existing pack that’s missing from the reachable pack becomes a cruft pack candidate.

In the illustration, Git iterates through pre-existing packs (pack-abc.pack, pack-def.pack, pack-123.pack) one object at a time. Object c8 is checked against the reachable pack (pack-xyz.pack) and marked unreachable (red) since it doesn’t match. Repeating this marks each original object either green (reachable) or red (unreachable).

Git then builds a new pack from the unreachable set:

This cruft pack (pack-cruft.pack) contains exactly the unreachable objects present at the start of garbage collection. While marking objects, Git records each object’s mtime, which later gets written to a corresponding *.mtimes file alongside the pack.

The mtime tracking routine is straightforward, though the implementation details are omitted here for brevity:

• An object in a packfile inherits its mtime from the packfile.
• A loose object’s mtime comes from the loose object file.
• An object in an existing cruft pack gets its mtime from the cruft pack’s *.mtimes file at the appropriate index.

If an object appears more than once (an unreachable object in a cruft pack freshened into a loose copy, for example), the most recent mtime among all occurrences is recorded in the new cruft pack.

Pruning: rescuing fresh unreachable clusters

Generating cruft packs with object expiration—"pruning"—is trickier. It aims to pack reachable and unreachable objects into two packfiles, deleting unreachable objects whose mtime predates the expiration date. But Git preserves connected clusters of unreachable objects if any member is too new to expire.

Consider a repository with several unreachable blobs connected to a tree object. If the tree’s mtime is recent enough to escape pruning, the connected blobs stay as well, even if the blobs are old enough to be pruned on their own. This preserves the repository’s reachability closure in case the tree becomes reachable again.

The procedure differs from the non-expiring case:

1. Generate a candidate list of cruft objects using the same process as the no-expiration flow.
2. From the candidates, perform a reachability traversal, adding every object seen to the cruft pack, but only traversing while objects remain too recent to prune.

Above, unreachable objects are red. Git traverses from entry points into the unreachable graph, asking of each object: “Is it old enough to prune?” If yes, Git leaves it alone. If not—the object’s mtime is too recent—Git marks it as rescued (green) and continues traversing everything reachable from it. Rescued objects are stored in the cruft pack.

Using an expiration date of d, object C(1,1) has mtime d+5, so it’s kept. Git starts a traversal there and rescues every object it encounters, including shared objects from older parts of the graph. Next is C(0,2), whose mtime d-10 precedes the cutoff, so it and everything reachable from it can be skipped.

Finally, Git inspects C(3,1); its mtime d+10 is too recent, so another traversal rescues it and its reachable objects. Notice the result: the main commit cluster is only partially rescued—precisely the objects needed to retain the closure over rescued commits. Commit C(2,1) loses some tree entries, but since C(2,1) itself will be pruned, those missing entries are irrelevant.

Integration and release

With cruft pack generation implemented for both pruning modes, the remaining work was wiring it into existing plumbing. Sub-commands like repack and gc needed new flags and configuration knobs to opt into the behavior.

$ git gc --prune=1.day.ago --cruft

or

$ git repack -d --cruft --cruft-expiration=1.day.ago

The first command runs garbage collection with a one-day expiration, repacking reachable objects and pruning unreachable ones older than a day into a cruft pack. The second repacks similarly. Documentation for the new options is available in the git-gc, git-repack, and git-config man pages.

GitHub submitted the full patch series to the open-source Git project, and cruft packs shipped in v2.37.0. The same tools that GitHub runs on its own repositories are now available in any Git release from 2.37 onward. The complete discussion is archived on the Git mailing list.

How GitHub rolled out cruft packs

After extensive testing to confirm that cruft packs were safe to enable across every repository on GitHub, the feature was deployed globally. Repositories with large numbers of unreachable objects received special attention during the rollout, since breaking deltas between reachable and unreachable objects — the two are now stored in separate packs, and deltas cannot cross pack boundaries — can make the initial cruft pack generation slow. A small number of repositories with many unreachable objects required extra time to produce their first cruft pack, so GitHub generated those packs outside of normal repository maintenance jobs to avoid timeouts.

Today, all repositories on GitHub and in GitHub Enterprise (version 3.3 and newer) use cruft packs to store unreachable objects. This has made garbage collection tractable for busy repositories that previously needed significant manual intervention. Before cruft packs, many repositories requiring cleanup were effectively out of reach because of the risk of creating an explosion of loose objects, which could hurt performance for every repository on a fileserver. Garbage collection is now a straightforward operation regardless of repository size.

Testing on a handful of repositories produced striking results. For repositories that regularly force-push a single commit to their main branch — leaving the majority of their objects unreachable — on-disk size dropped dramatically. The most extreme example tested shrank from 186 gigabytes to just 2 gigabytes. On github/github, the company's main codebase, the repository went from roughly 57 gigabytes to 27 gigabytes. More important than the disk savings is the reduction in object count: each replica previously held nearly 60 million objects, including years of test-merges, force-pushes, and other sources of unreachable objects, all of which added to the I/O cost of repacking. After garbage collection, only 11.8 million objects remained. Since each object consumes about 150 bytes of memory during repacking, GitHub saves around 7 gigabytes of RAM per maintenance run.

Handling races with limbo repositories

Even with cruft packs, garbage collection still must contend with the inherent raciness mentioned earlier in this article. Rather than redesigning Git to prevent the race entirely — a significant undertaking — GitHub chose to make the situation easy to recover from automatically.

The approach introduces a "limbo" repository that stores expired objects whenever a pruning garbage collection runs. Any object that expires from the main repository is placed in a separate pack inside the limbo repository. The garbage collection process then works as follows:

1. Generate a cruft pack of recent unreachable objects in the main repository.
2. Generate a second cruft pack of expired unreachable objects, stored outside the main repository in the limbo repository.
3. After garbage collection completes, run a git fsck in the main repository to detect any object corruption.
4. If any objects are missing, recover them by copying them from the limbo repository.

Generating the second cruft pack uses the same process as the first, with two differences: the expiration cutoff is set to "never" so that any object expired in the prior step is retained, and the original cruft pack is treated as a pack of reachable objects so that unreachable objects too recent to expire are ignored.

GitHub reports great success with the limbo approach and now treats garbage collection as a hands-off process from start to finish. The patches are available as a preliminary RFC on the Git mailing list.