Packfiles and Delta Chains: How Git Stores Similar Objects Once

Loose objects are one file per object, each deflated independently. That is a fine format for writing and a poor one for keeping: a repository with a hundred thousand commits holds several hundred thousand objects, most of them small, each occupying at least one filesystem block plus the header overhead of the compression stream. Worse, successive versions of a file share almost all their bytes, and independent deflation cannot exploit that at all. A packfile solves both problems at once by concatenating many objects into one file and encoding some of them as instructions against others.

One file, many objects

A pack begins with the four bytes PACK, a four-byte version number, and a four-byte count of the objects it contains. Objects follow back to back, then a twenty-byte checksum over every preceding byte. There is no per-object offset table in the pack itself; a reader either scans sequentially or consults the accompanying index.

Each object starts with a variable-length header. The first byte holds a continuation bit, three bits of type, and four bits of size. While the continuation bit is set, the following bytes contribute seven more bits of size each, least significant group first. Type 1 is a commit, 2 a tree, 3 a blob, 4 a tag. Types 6 and 7 are the interesting ones: an object stored as a delta against another object in the same pack, referenced either by offset or by identifier.

After the header comes a zlib stream. For an undeltified object the stream is the object’s payload, and its length must match the size in the header. For a delta, the stream is the instruction sequence, and the size in the header is the size of the reconstructed object, not of the instructions. A reader must therefore decode the delta fully before it can verify the length, which is one reason delta chains are expanded with care.

Decoding the header is short enough to do by hand:

def read_object_header(buf: bytes, pos: int):
    b = buf[pos]
    pos += 1
    kind = (b >> 4) & 0x07
    size = b & 0x0F
    shift = 4
    while b & 0x80:
        b = buf[pos]
        pos += 1
        size |= (b & 0x7F) << shift
        shift += 7
    return kind, size, pos

Deltas are instructions, not diffs

A delta payload begins with two variable-length integers: the size of the base object and the size of the result. Then come instructions, each introduced by one byte. If the high bit is clear, the low seven bits give a literal length between 1 and 127, and that many bytes follow verbatim. If the high bit is set, the instruction is a copy from the base: the low bits act as a mask selecting which of four offset bytes and three size bytes are present, each present byte contributing eight bits to the corresponding value, least significant first. A copy size of zero means 65536 bytes, which is why a single copy instruction cannot exceed that.

There is no delete instruction. The result is assembled from copies and literals only, so any byte of the base that is not copied is simply skipped by not being referenced. This makes the encoding cheap to apply, and it makes the result deterministic: given a base and a delta, exactly one byte string comes out, and its hash must equal the identifier the pack claims.

The format is also why deltas are not reusable across unrelated content. A delta is meaningful only with its exact base, and the base is identified by position in the same pack or by identifier anywhere. Recompressing a pack with different object ordering invalidates offset deltas and forces them to be recomputed or converted.

Offset deltas and ref deltas

An offset delta stores the distance backwards to its base as a variable-length integer with an unusual encoding: each continuation adds seven bits and applies a bias of one, which keeps the representation minimal. The base is always earlier in the pack, which guarantees that a single forward scan can resolve every chain without seeking, provided the chain is walked from the base end.

A ref delta stores the twenty raw bytes of the base object’s identifier instead. It is used when the base is not in the same pack, which happens in thin packs: a server sending a pack to a client may delta against an object the client already has, omitting the base entirely. The client repairs the pack by supplying the missing base and rewriting the checksum, a step called fixing a thin pack. Ref deltas also appear when a pack is created incrementally against an existing one.

The index makes random access possible

A pack without an index can only be read sequentially, which is useless for looking up one commit among a million. The .idx file supplies the mapping. Version 2 begins with the magic bytes \377tOc and a version number, followed by a fanout table of 256 four-byte entries. Entry i holds the number of objects whose first identifier byte is less than or equal to i, so the table is cumulative and the last entry equals the object count.

Then come the identifiers themselves, sorted, twenty bytes each; a CRC32 per object, used to verify individual objects without hashing the whole pack; four-byte offsets into the pack, with the high bit set to indicate that the real offset lives in a following table of eight-byte values for packs larger than four gigabytes; the pack checksum; and the index checksum.

Lookup is a fanout-bounded binary search. The first byte of the wanted identifier selects a range in the sorted table, the range is bisected, and the offset is read from the parallel array. The fanout also gives the number of objects sharing a prefix, which is what makes git cat-file --batch-all-objects and object counting cheap.

A multi-pack index extends the idea across several packs. It carries its own fanout, identifier, and offset tables, with a pack number per object, so a lookup does not have to try each pack in turn. It also allows a repository to keep many packs without a proportional slowdown, which is what makes incremental repacking strategies practical.

Choosing bases is a cost decision

Delta compression turns into a search problem: for each object, which earlier object makes the best base? Testing every pair is quadratic. Git bounds the search with a window of candidate objects considered at once, and bounds the resulting chains with a maximum depth. Both are configurable, and both trade compression ratio against the time and memory needed to produce the pack.

The trade is asymmetric. Compression is paid once, at pack time, while decompression is paid on every read. A deeper chain means more instructions to apply and more bases to inflate, so a read of the deepest object costs the sum of the whole chain. That is why depth is capped rather than maximised, and why a repack with a larger window produces a smaller pack that is not necessarily faster to read.

Ordering matters as much as the search. Objects are sorted by type, then by path or name where known, then by size, so that versions of the same file land near each other and become candidates for one another. Binary files defeat this: a compressed image or an archive has no internal redundancy that a line-oriented delta can exploit, so a new version typically becomes a full copy regardless of the base chosen. Repositories that store such files pay for it in pack size, and no configuration fixes that.

Reading, repairing, and the failure modes

A pack is verified by hashing its contents and comparing the trailing checksum, and each object can be verified against its CRC32 in the index without a full rehash. Corruption therefore surfaces as a specific object failing, not as a silently wrong tree. A missing base is a different failure: a ref delta whose base is absent cannot be applied, and a thin pack that was never fixed is unusable until the base is supplied.

Delta chains also interact with memory. Applying a chain requires the intermediate results, and a long chain over large blobs can require holding several expanded objects at once. Servers bound this with the same depth limit that bounds storage, and clients inherit whatever the server produced.

The pack format is where the object model stops being a pure content-addressed store and becomes a storage engine with heuristics. Nothing about it is visible in the object graph: the same commit has the same identifier whether it was stored loose, in a pack, or as a delta against a base chosen by a window. What changes is the cost of reading it, which is why reachability and collection operate on packs as units and why fetch can send deltas against objects the receiver already holds.