How does Git's garbage collection system work, including packfile generation, delta compression, reachability analysis, and the commit-graph optimization?

Think of Git garbage collection like a warehouse reorganization with an inventory audit. Initially, every item (object) sits loose on the warehouse floor in its own labeled box. Over time, the floor fills up with thousands of boxes. The gc process consolidates similar items into sealed shipping containers (packfiles) using efficient stacking (delta compression), runs an inventory check to identify items nobody has claimed in months (unreachable objects past reflog expiry), discards those unclaimed items (pruning), and updates the warehouse map (commit-graph) so workers can navigate faster.

Git gc performs several interconnected operations. First, it packs loose objects from .git/objects/<xx>/<38-chars> into packfiles in .git/objects/pack/. The packing algorithm sorts objects by type and filename, then uses a sliding window (default size 10) to find similar objects and compute binary deltas between them. A new version of a file is stored as a delta against the previous version, dramatically reducing storage. The resulting .pack file has a companion .idx file enabling O(1) SHA lookups. Second, gc prunes unreachable objects: those not reachable from any ref (branch, tag, stash) or reflog entry. Unreachable reflog entries expire after gc.reflogExpireUnreachable (default 30 days), and reachable entries after gc.reflogExpire (default 90 days). Only after reflog expiry does pruning remove the objects.

Internally, the packing heuristic is sophisticated. Objects are sorted by type, then by filename (to group versions of the same file), then by size descending (so the largest version is the base and deltas are applied forward). The delta compression algorithm finds the minimal set of copy and insert instructions to transform one object into another. Git allows delta chains (delta of a delta) up to gc.depth (default 50) levels deep, trading read speed for compression ratio. The multi-pack-index (MIDX) file, introduced for repositories with multiple packfiles, provides a unified lookup table across all packs without repacking them. The geometric repacking strategy (available since Git 2.34 with --geometric=<factor>) ensures packfile sizes follow a geometric progression, reducing the frequency of expensive full repacks while keeping the total number of packs bounded.

The commit-graph file (.git/objects/info/commit-graph) is a separate optimization that pre-computes topological information for the commit DAG. It stores commit OID, tree OID, parent list, generation number (topological depth), and commit timestamp in a binary format with O(1) lookup by position. Generation numbers enable Git to quickly determine reachability without walking the full graph: if commit A has generation number 100 and commit B has generation number 50, A cannot be an ancestor of B. This accelerates git log, git merge-base, git branch --contains, and git push (which needs to determine which commits the remote lacks). The changed-path Bloom filter extension adds per-commit Bloom filters recording which paths changed, making git log -- <path> dramatically faster by skipping commits that definitely did not touch the path.

A critical gotcha: never run git gc while another Git operation is active in the same repository, as concurrent access to packfiles during repacking can cause corruption. Git uses lock files (.lock suffix) for safety, but parallel gc invocations should be avoided. Another trap: git gc --aggressive sounds beneficial but is rarely worth the cost. It tries all possible delta bases (rather than the sliding window heuristic), consuming enormous CPU time (potentially hours for large repos) for marginal compression improvement. Standard gc is sufficient for routine maintenance. Also, gc.auto (default 6700 loose objects) controls when automatic gc triggers during regular operations like commit. In CI environments where repositories are cloned fresh each run, disable auto-gc with git config gc.auto 0 to avoid wasting build time. For long-lived server-side repositories, use git maintenance start to schedule periodic maintenance including prefetch, commit-graph updates, and incremental repacking.