Reachability, Grace Periods, and Cruft Packs

No command deletes a commit. Amending, resetting, rebasing, and deleting branches all move references and leave every object they displaced exactly where it was. The object store grows monotonically until a separate process computes which objects can still be reached from anything that matters and removes the rest. That computation is the whole of garbage collection in Git, and the interesting parts are what counts as a root, how long a reprieve an unreachable object gets, and what happens when the objects being removed are packed together with the ones being kept.

Liveness is reachability from roots

An object is live if some path of references leads to it from a root. Roots are not only branches: the set includes every reference under the reference namespace, HEAD, the index, the reflogs of all references and of HEAD, the state files of operations in progress such as a merge or a cherry-pick, and the administrative files of any additional worktree.

The index is a root because staging writes a blob before any commit names it. Without that root, git add followed by a collection would delete the staged content and leave an index entry pointing at nothing. The reflog is a root because it records positions the branch has left, which is exactly the data that makes a reset recoverable. The operation-state files are roots for the same reason: an interrupted merge holds blobs that only its in-progress tree references.

The traversal itself is straightforward: mark every root object, follow trees to their entries and commits to their trees and parents, and repeat until nothing new is marked. Tags add an indirection, since a reference may name a tag object that names a commit. The cost is proportional to the number of live objects, and the working set is the entire object graph, which is why the operation is expensive on large repositories and why it is batched rather than run after every command.

Anything not marked is unreachable. It may still be useful, which is why unreachability is not sufficient grounds for immediate deletion.

The two clocks

Deletion is deferred by two independent expiry policies. The reflog expires entries after a period, ninety days for entries reachable from the current tip and thirty days for entries that are not, by default. Object pruning then waits an additional period, two weeks by default, measured from the object’s own modification time.

The two clocks exist because they answer different questions. Reflog expiry bounds how far back the history of reference movements is remembered. Object expiry bounds how long a file that was written but never referenced survives. A blob created by an interrupted operation, a commit made and then immediately reset away, a tree written by a failed merge: none of these appear in a reflog, so the reflog policy does not protect them, and only the modification time keeps them alive.

Modification time is a filesystem property of a loose object file, which works because loose objects are never rewritten. Once objects are packed, that property is lost: a pack contains objects of many ages and has one mtime. This is the tension that cruft packs resolve.

Packing garbage without losing its age

Before cruft packs, an unreachable object had to remain loose for the duration of its grace period, because packing it would erase the timestamp that decided when it could be pruned. A repository that accumulated many unreachable objects therefore accumulated many loose files, each with inode and directory overhead, and the very state that collection was supposed to fix persisted for weeks.

A cruft pack stores unreachable objects in an ordinary pack alongside a separate file recording, for each object, the modification time it had when it was packed. The pack provides compression and a single file; the side file preserves the per-object age that pruning needs. When the grace period elapses, the pack is rewritten without the expired objects, and the survivors keep their recorded times.

The consequence is that a repository can be fully packed at all times, including its garbage, and that git gc no longer has to choose between reclaiming space and preserving recoverability. The cost is an extra file to keep consistent with its pack and a rewrite of the whole pack whenever anything inside it expires, which is why expiration is batched.

# Keep unreachable objects, but only those younger than the grace period.
git repack -a -d --cruft --cruft-expiration=2.weeks.ago

# What is unreachable right now, ignoring reflog entries as roots.
git fsck --unreachable --no-reflogs

# Full collection: pack refs, expire reflogs, repack, prune, write indexes.
git gc

What a full collection actually runs

A collection is a sequence, and the order matters. References are packed first, so that the reachability walk sees a compact set. Reflogs are expired next, which can remove roots and therefore make more objects unreachable in the same run. The repack then consolidates packs, optionally writing a cruft pack for the unreachable set, and drops redundant packs. Pruning removes loose objects past their expiry. Finally the derived indexes are rebuilt: the commit-graph, the multi-pack index, and the bloom filters that accelerate path-limited history.

Each step is separately invocable, and the composite command exists because the steps are only jointly meaningful. Running the repack without the reflog expiry leaves the same objects reachable; running the prune without the repack leaves loose objects that the repack would have consolidated. The automatic trigger is a count of loose objects crossing a threshold, which is a proxy for “enough has changed to be worth the walk”.

Partial clones break the closure assumption

A partial clone deliberately omits objects. A clone filtered to exclude blobs has commits and trees but no file contents; reading a file triggers a fetch from the promisor remote. Those absent objects are not garbage, and a reachability walk that treated absence as a reason to do anything would corrupt the repository.

Promisor packs are marked, and objects they are known to contain are treated as present for the purposes of connectivity checks even when the pack does not contain them. The marker is what distinguishes “this object was never here” from “this object was deleted”, and losing the marker turns a partial clone into a repository that fails every checkout. The failure mode on the other side is a server that prunes an object a client is relying on: the client’s next lazy fetch fails, and the only recovery is to fetch the object from another source or to discard the local history and clone again.

Shallow clones have a related but distinct problem. The boundary commits have parents that are known to exist upstream and are recorded as absent. Reachability stops at the boundary, so an object that is unreachable locally may be perfectly reachable in the full history. Collection inside a shallow clone is safe because it never claims more than the local graph, but any conclusion drawn from that graph about the upstream repository is wrong.

Sharing object stores and the delta island problem

Two mechanisms let repositories share objects. Alternates point one repository at another’s object directory, so a clone can borrow objects instead of copying them. Delta islands partition a server’s objects so that deltas are never built across a boundary.

Alternates make collection dangerous in a way that is easy to miss: the borrowing repository’s roots do not protect objects in the lender, and a collection in the lender can delete objects the borrower still needs. The borrower’s references are invisible to the lender’s walk. Repositories that share storage therefore have to coordinate collection, or accept that the borrower can be broken.

Delta islands address the opposite problem. On a server hosting many forks, an object shared by two forks may be delta-compressed against an object that only one fork’s clients have. A client of the other fork then downloads a delta whose base it must also download, defeating the compression. Islands mark groups of references and forbid deltas that cross between them, which costs compression ratio on the server and saves transfer on the wire.

The limits of the model

Reachability is a coarse definition of value. A commit that is reachable only through a tag nobody uses is kept forever; a commit that is unreachable but is the only record of an experiment is deleted after two weeks unless something names it. The system offers no notion of importance, only of naming.

The grace period is also a window during which a concurrent operation can be surprised. An object written by one process and not yet referenced can be pruned by another if its timestamp is old, which is why clocks and mount options that disturb modification times are hazardous, and why setting the expiry to zero is safe only when nothing else is running. The reflog is the main defence, and disabling it shortens the window to the object grace period alone.

None of this changes the object graph. Collection is the only operation that removes content, and it removes exactly the content that no name reaches.