arthrop0d

Brief articles on varied topics.

Git Packfiles and Delta Compression

gitalgorithms

A Git packfile is a binary file that stores many repository objects together, often saving space by storing later objects as changes—or deltas—against similar earlier objects. Git uses packfiles to keep repositories small and make transfers practical.

The problem packfiles solve

Git objects are the data behind commits: blobs hold file contents, trees describe directories, and commits record snapshots and history. Each object is named by a hash of its type and contents; this makes the object store content-addressed, meaning the name identifies the exact data.

Originally, Git can store each object as a separate compressed file under .git/objects. This is simple and useful for writes, but a repository with thousands of commits accumulates thousands of files. That creates filesystem overhead, wastes repeated content, and makes network transfers less efficient.

A packfile combines many objects into one file. It can also notice that two versions of a file are mostly alike. Instead of storing both complete files, it stores one complete object and a compact recipe for reconstructing the other.

A delta is not a textual diff. It is a binary instruction stream that says which byte ranges to copy from a base and which new bytes to insert.

What a packfile contains

A pack normally has a companion pack index file. The index maps an object’s hash to its location in the pack, allowing Git to find an object without scanning the entire file. The pack itself contains a header, object entries, and a checksum.

An entry can contain an entire object, or it can contain a delta. A complete entry records the object’s type and size, followed by compressed data. Git commonly compresses that data with zlib, but compression and delta compression are separate ideas: zlib removes local byte-pattern repetition, while a delta reuses bytes from another object.

A delta entry identifies its base, the complete or delta object from which it can be reconstructed. Git has two ways to identify that base:

The delta data begins with the base object’s size and the result object’s size. It then contains instructions. A copy instruction selects an offset and length from the base; an insert instruction supplies literal bytes. Applying those instructions in order produces the target object, whose type is inherited from the base.

For example, successive versions of a source file might be represented like this conceptually:

base:   function parse(input) { ... }
change: copy bytes 0-24
        insert "async "
        copy the remaining bytes

The actual pack format uses compact binary fields rather than this readable notation, but the principle is the same.

Resolving a delta chain

A delta may use another delta as its base. This creates a delta chain:

full object A <- delta B <- delta C <- delta D

To read D, Git first finds A, reconstructs B, applies C to B, and finally applies D to C. The reader therefore works from the oldest complete base toward the requested object.

The pack index gets Git to the requested entry quickly, but it does not eliminate this reconstruction work. A long chain can save disk space while costing CPU time and memory during checkout, diffing, cloning, or serving an object. Git therefore limits chain depth when creating packs. Readers can also cache recently reconstructed objects, which helps when nearby operations request related versions.

This explains errors and diagnostics that mention a bad object, delta base, or pack. A missing base makes the dependent delta impossible to reconstruct. Corruption can be detected by checksums and by verifying that reconstructed content has the expected object hash.

What garbage collection changes

A repository grows through normal work: new commits create new trees and blobs, and commands may first write those objects as loose files. Deleted or rewritten branches can also leave objects that are no longer reachable from current references. A reference is a named pointer such as a branch or tag; an object is reachable when Git can follow references and history to get to it.

git gc performs housekeeping. Depending on repository state and configuration, it can pack loose objects, combine existing packs, remove obsolete temporary data, and prune unreachable objects after a safety period. Reflogs—local records of where references used to point—can keep otherwise unreachable objects protected for a while, which is why recently deleted commits are often recoverable.

Garbage collection is therefore more than deletion. Repacking changes the physical arrangement of surviving objects and the delta relationships between them. It may consolidate many small packs into fewer large ones, reducing filesystem lookups and improving sequential reads. It can also make the repository smaller by finding better matches among a larger set of objects.

The performance trade-off

Packing is not automatically faster in every dimension. Creating a good pack requires comparing objects and selecting useful bases, so repacking can consume substantial CPU and temporary disk space. A pack with deep delta chains may be smaller but slower to read. A pack with shallow chains or more complete objects uses more disk but reduces reconstruction work.

Commands such as git repack expose controls for this trade-off, including the search window used to find similar objects and the maximum delta-chain depth. An aggressive repack searches more broadly; it can improve compression, but it is expensive and is not a routine fix for every performance problem.

In practice, Git’s maintenance behavior balances three costs:

Thus a repository that suddenly becomes slow, large, or busy with pack-related messages may need housekeeping rather than source-code changes. Garbage collection removes objects that no longer matter; repacking decides how the remaining objects share storage. Together, they determine whether Git pays more during maintenance or during ordinary reads and transfers.

← All articles