Packfiles, Delta Chains, and What Garbage Collection Actually Deletes

The object model is a set of immutable blobs, trees, and commits addressed by hash. On disk, almost none of them are stored that way. A freshly created object is written as a single zlib-compressed file under a two-character directory named from its hash, but any repository that has been used for a while stores the bulk of its objects inside a small number of packfiles, where each object may be encoded as a delta against another. The two representations describe the same graph; the difference is a trade between write cost and read cost that the repository makes automatically and can be tuned.

The loose object path

A loose object’s path is derived mechanically: .git/objects/ plus the first two hex characters of the hash as a directory, plus the remaining characters as a filename. The split exists because a flat directory with hundreds of thousands of entries is slow to look up on filesystems that do not index directory entries well. With a 256-way fanout, each directory holds a manageable number.

The file content is the object header and payload compressed with zlib. Reading requires inflating, parsing the header, and verifying the hash. Writing requires computing the hash first, since the path depends on it, then compressing and writing atomically — a temporary file followed by a rename, so that a crash cannot leave a truncated object at a path that claims to hold valid content.

A single loose object is therefore an independent unit: self-describing, self-verifying, and independent of every other file. That independence is why a repository can be repaired by copying objects between directories, and it is also why loose storage scales badly. A commit that changes one line in a large file creates a complete new compressed copy of that file.

Pack format and delta encoding

A packfile stores many objects in one file, with an index beside it. The pack begins with the four bytes PACK, a version number, and a count of objects; each object follows as a header and data; the file ends with a checksum of everything before it.

The object header encodes a type in three bits and a size as a variable-length integer, where each byte’s high bit indicates another byte follows. Four types are the base types — commit, tree, blob, tag — and two are deltas: OFS_DELTA, whose base is at a negative offset from the current object’s position in the same pack, and REF_DELTA, whose base is named by a 20-byte object id and may live in a different pack.

A delta is a program, not a diff. It begins with the base size and the result size as variable-length integers, then a sequence of instructions. An instruction with its high bit set copies a run of bytes from the base, with the offset and length each encoded in optional bytes whose presence is signalled by individual bits in the opcode. An instruction with its high bit clear inserts that many literal bytes which follow in the delta stream. Copy instructions dominate when the two versions are similar, which is the entire point: a version of a file that differs in a few lines encodes as a handful of copy instructions around the changed regions plus the new text.

OFS_DELTA is preferred inside a pack because the offset is smaller than a full object id and, more importantly, it constrains the base to be earlier in the same file, which allows a reader to resolve a chain with a single forward pass and a bounded window of memory. REF_DELTA appears in packs sent over the wire, where the sender cannot know the receiver’s offsets.

Chains are the reason delta compression is not applied without limit. A delta against a delta requires resolving the base first, so reading the object at the end of a chain of depth d requires d decompressions. The packer bounds depth — the default is 50 — and also bounds the total delta size, because a long chain of small deltas can still cost more to resolve than the object is worth. The --depth and --window options to git repack control these directly; a larger window finds better bases at the cost of a slower pack.

The index and the multi-pack case

The pack index maps object ids to offsets. Version 2 of the format begins with a four-byte magic number and a version word, then a 256-entry fanout table: entry i holds the number of objects whose first byte is at most i. That makes the search range for a given id computable in one lookup rather than a scan, and the sorted id table that follows is searched within that range. Then come a table of CRC32 values for each object, a table of 32-bit offsets, and — for packs larger than 4 GiB — a table of 64-bit offsets for the entries whose 32-bit value has its high bit set.

git verify-pack -v reads an index and prints each object with its type, size, and — for deltas — the base it is stored against and the depth of the chain. The output is the only convenient way to see the chain structure, since it is otherwise implicit in the pack bytes:

$ git verify-pack -v .git/objects/pack/pack-*.idx | sort -k5 -n | tail -3
# columns: object id, type, size, size-in-pack, offset, [base id, depth]

The CRC32s exist so that a delta can be resolved and checked without rehashing the whole object, which matters when the object is the base of a chain that must be verified.

A repository accumulates packs over time: one per fetch, one per repack. Without a multi-pack index, looking up an object requires probing each pack’s index in turn, and the number of packs grows with the number of fetches. The multi-pack index (git multi-pack-index write) consolidates the id-to-location mapping into a single file with its own fanout and offset tables, so a lookup is one binary search over the combined set. Repacking also merges packs, but a multi-pack index allows the consolidation of the lookup path without rewriting the packs themselves.

Reachability and pruning

Garbage collection has two jobs that are easy to conflate: compacting live objects into packs, and deleting objects that nothing refers to. Only the second is destructive, and it is governed by reachability.

Roots are refs, HEAD, the index, and the reflogs. The reflog is a root, which is why an object referenced only by a reflog entry survives — this is the mechanism that makes a rebase recoverable. Objects reachable from roots are kept; the rest are candidates for pruning, subject to an age threshold. The default is two weeks, configurable through gc.pruneExpire, and the grace period exists so that a concurrent process that has created an object but not yet written the ref pointing at it cannot have that object deleted underneath it.

git gc also expires reflog entries according to a separate policy, with a shorter default for unreachable entries than for reachable ones. Once the reflog entry is gone, the object loses its last root and becomes prunable on the next run after the grace period. The two-stage decay is why a lost commit can be recovered for a while and then abruptly not.

git fsck --lost-found and --unreachable enumerate what is dangling without deleting it, which is the safe way to look before a prune. git prune deletes without packing; git repack -a -d builds a single pack containing all reachable objects and removes the redundant packs afterwards.

Packing has its own heuristics. A repack with a large window produces smaller packs but takes longer; a geometric repacking strategy keeps the number of packs logarithmic by merging only packs of similar size, which avoids rewriting the entire repository on every maintenance run. The git maintenance command exposes these as scheduled tasks — a prefetch that updates remote-tracking refs, an incremental repack, a loose-object consolidation, a commit-graph write, and a pack-refs pass — so that the expensive full repack is rare.

Partial clone and the missing-object case

The usual assumption is that a clone contains every object reachable from the fetched refs. Partial clone breaks it deliberately: --filter=blob:none omits blobs, --filter=tree:0 omits trees as well, and --filter=blob:limit=<size> omits blobs above a size. The repository records the remote as a promisor, meaning that missing objects may be fetched on demand.

The consequences are structural rather than cosmetic. A command that needs a blob triggers a fetch for it, so an operation that touches many files performs many round trips; batching is what makes the difference between usable and unusable. git log -- path requires trees, so a tree-less clone must fetch trees before it can filter by path. Reachability calculations are unaffected, because commit and tree hashes are still present where they were not filtered, but any command that wants content must be prepared for a network call.

The promisor mechanism also changes garbage collection. An object that is absent is not an error to be repaired; it is expected. git fsck reports missing objects in a partial clone as a matter of course unless the promisor configuration is consulted, and a naive prune on such a repository would be dangerous in a different way — it can delete the local record of what the promisor is expected to supply.

Where the storage layer leaks into practice

Three observable consequences. A clone’s size is dominated by packed blobs, not by commit count, which is why a repository with a large binary file added and removed in history stays large until that object is unreachable and pruned — and stays in every existing clone until those clones are re-cloned or repacked with the object removed. A shallow clone truncates history at a depth rather than filtering by type, and a commit made on a shallow clone has a grafted parent, so pushing from it requires care. And a repository’s read performance for history traversal depends on whether a commit-graph file exists, since the graph stores commit metadata and generation numbers in a compact form that avoids inflating commit objects during a walk.

The graph itself is unchanged by any of this. Packing, deltas, pruning, and filtering all describe how the same immutable objects are stored and transmitted; identity is still the hash of the content, as set out in what a commit contains. What changes is which objects are present locally, which is the assumption that bisecting a rewritten history has to check before it starts.