arthrop0d

Brief articles on varied topics.

Git Packfiles and Pack Indexes

git

A Git packfile is a binary file that stores many Git objects together, often using delta compression so similar objects share most of their data. A companion pack index maps each object’s ID to its location in the pack, allowing Git to find an object without reading the pack from the beginning.

The problem packfiles solve

Git treats commits, trees, blobs, and annotated tags as objects. A blob contains file data; a tree describes directory contents; a commit points to a tree and its parents. Each object has a content-derived ID, traditionally a SHA-1 hash and, in repositories using the newer format, possibly a SHA-256 hash.

In a simple repository, Git can store each object as a separate compressed file under .git/objects. That is easy to understand, but inefficient at scale:

A repository with a long history can therefore accumulate many small files and repeated data. Packing combines those objects into larger files and gives Git a better opportunity to compress them together.

Packing is not a different object model. Commits, trees, blobs, and tags still have the same contents and IDs; only their on-disk representation changes.

Git commonly creates or refreshes packs during garbage collection, maintenance, cloning, fetching, and operations that consolidate loose objects. You may have encountered the result in .git/objects/pack/, where files appear in matching .pack and .idx pairs.

What a packfile contains

A pack begins with a header identifying the pack format and the number of contained objects. It then stores one entry per object. An entry can contain the object’s complete content, or a delta: instructions for reconstructing the content from another object.

For a complete entry, the pack records the object type and the uncompressed size, followed by compressed data. The object’s ID is not necessarily stored beside the entry as a convenient label. Git can derive the ID by reconstructing the object and hashing its canonical representation, which includes the object type, its length, and its content.

A delta entry instead describes a difference from a base object, meaning the object from which it can be rebuilt. Its instructions generally say either:

For example, if two versions of a source file differ by a few lines, a delta can copy most of the old version and insert the changed lines. This is similar in spirit to a binary patch, but it is part of Git’s storage format rather than a patch intended for people to read or apply manually.

There are two ways a delta identifies its base:

Delta chains let Git save more space, but they add work when reading: Git may need to reconstruct a base, apply another delta, and continue until it reaches a complete object. Pack creation tries to balance compression against lookup and reconstruction cost, and it limits or rearranges chains when appropriate.

The pack ends with a checksum covering its contents. This helps Git detect a truncated or corrupted pack, but it is not what Git uses to locate an individual object.

How the index finds an object

The .idx file is the lookup structure for its corresponding .pack file. It contains object IDs in sorted order and enough information to translate a matching ID into a byte offset in the pack.

The usual version 2 index has three important pieces:

  1. A fan-out table has 256 four-byte counts. Each count says how many object IDs begin with a byte value less than or equal to a particular value.
  2. A sorted table contains every object ID in the pack, ordered by its raw bytes.
  3. A table maps each ID’s position to its pack offset. The offset is the byte position where that object’s entry begins.

The fan-out table narrows the search immediately. If the first byte of the requested object ID is 0x7a, Git reads the counts for the preceding and current byte values to determine the range of sorted IDs that could match. It then performs a binary search in that range rather than examining every object.

Most offsets fit in four bytes. For a pack larger than that range, an index entry uses a marker bit and refers to a separate table containing an eight-byte offset. This preserves compact indexes for normal packs while supporting very large ones.

An index also carries checksums for integrity checking and identifies the pack it belongs to. It is a separate file because Git can build and use the lookup information without modifying the pack’s object data.

A lookup from name to content

Suppose Git needs the object named by a commit’s parent ID. The path is roughly:

  1. Search loose-object storage if applicable, and search the relevant pack indexes.
  2. Use the index’s fan-out table and sorted IDs to find the requested ID.
  3. Read the corresponding pack offset from the index.
  4. Seek directly to that byte offset in the pack.
  5. Decode the entry. If it is a delta, locate and reconstruct its base, then apply the delta instructions.
  6. Verify or use the resulting object according to the operation being performed.

The index therefore does not contain the object itself, and it does not eliminate the cost of decompressing a delta chain. Its specific job is to avoid a linear scan through all pack entries to discover where the requested object starts.

That division of labor explains several familiar Git messages. “Counting objects” and “Compressing objects” describe pack construction or transfer; “index-pack” describes creating or checking the index for a received pack. Errors mentioning a missing base, a bad pack header, or a corrupt .idx file refer to different failures in this storage-and-lookup pipeline.

← All articles