./ahmedhashim

Taking a packfile apart left two questions open. The pack stored the newer version of a file whole and the older one as an 18-byte delta against it, but:

1. How did Git decide on that pairing?
2. How does Git find one object in a pack without reading the whole file?

Both answers use the same six-object demo pack. Here’s its git verify-pack -v output again:

d79cd4c394340fdbf839ecbc71e24b7c1384cf3c commit 190 138 12
1480ca830fac79e4e47a514654a7cf0e0428cc9c commit 145 112 150
3f20c233eae9d1047b393d111f906c76bfd772c0 blob   9982 3491 262
203b24db4881c92152fbd87d0aeacd7c74be79c5 tree   42 53 3753
a7732906e8812408a49c16cb765b85300721fb16 tree   42 52 3806
83299d47324f1ed351db0f6f277b97811cb288a4 blob   7 18 3858 1 3f20c233eae9d1047b393d111f906c76bfd772c0

3f20c2 is the newer version of the file and 83299d the older, stored as a delta against it. The last column is each object’s byte offset in the pack.

Choosing bases

Git tracks snapshots, not the history of individual files. A blob is just content, and the only thing that gives it a filename is the directory tree that lists it. So Git knows that 3f20c2 and 83299d exist and which tree lists each, but nothing in the object store says one is a newer version of the other. Rather than work that out, git pack-objects relies on heuristics that Linus explained on IRC in 2006, in a log that now ships with Git’s documentation.

The objects are sorted by three keys, in this order:

1. Type: A blob is only ever stored as a delta against another blob, and a tree against another tree. Objects of different types share almost no bytes, so the delta would be bigger than the object.
2. Path: pack_name_hash hashes the last sixteen non-whitespace characters of the path each object was first seen at into 32 bits, with the last characters counting most. This means every Makefile lands together and every .c file lands near the others.
3. Size: largest first.

Git then walks that list one object at a time. For each one, the candidate bases are the ten objects just before it in the list (pack.window), so the window slides forward as the walk proceeds and each object is a candidate for the ten after it. Here’s a window of three, at one step and the next:

  flowchart TB
    subgraph S1["Processing e: candidates are b, c, d"]
        direction LR
        A1["<strong>a</strong>"] ~~~ B1["<strong>b</strong>"] ~~~ C1["<strong>c</strong>"] ~~~ D1["<strong>d</strong>"] ~~~ E1["<strong style='color:#16181a'>e</strong>"] ~~~ F1["<strong>f</strong>"] ~~~ G1["<strong>g</strong>"]
    end
    subgraph S2["Processing f: candidates are c, d, e"]
        direction LR
        A2["<strong>a</strong>"] ~~~ B2["<strong>b</strong>"] ~~~ C2["<strong>c</strong>"] ~~~ D2["<strong>d</strong>"] ~~~ E2["<strong>e</strong>"] ~~~ F2["<strong style='color:#16181a'>f</strong>"] ~~~ G2["<strong>g</strong>"]
    end
    S1 ~~~ S2
    classDef cand stroke:#5ea1ff,stroke-width:2px
    classDef cur fill:#5eff6c,stroke:#5eff6c,color:#16181a
    class B1,C1,D1,C2,D2,E2 cand
    class E1,F2 cur
    style S1 fill:transparent
    style S2 fill:transparent

Between the two steps, b fell out of the window and e joined it.

An object is stored one way, either whole or as a delta against a single base. So Git tries a delta against each candidate and keeps whichever came out smallest. If no candidate works, the object is stored whole and becomes the root of a new chain, which is how a file with hundreds of versions ends up as a series of chains rather than one.

Most pairs are rejected before any content is compared. A chain is capped at 50 deltas (pack.depth), so a candidate already at the bottom of one that deep is skipped, since a delta against it would sit at depth 51. So is a candidate more than 32 times bigger, or one whose size difference is already larger than the best delta so far. Those checks are the first thing in try_delta.

Sorting largest first is what makes the deltas point backward. Files tend to grow, so the newest version is usually the biggest. That puts it first in its group, where it gets stored whole, and every older version after it becomes a delta that mostly says “copy”. When a file shrinks instead, the sort flips: the older, larger version is the one stored whole and the newer one is a delta against it. The delta is still small, since the newer content is mostly a subset of the older, but reading the newest version now costs a delta step instead of none.

Once every object has its representation, the pack is written out newest first, starting with the objects reachable from the branch tips. That way the front of the pack is what a checkout needs, and every base lands ahead of the deltas that point at it.

All of this costs CPU time. The window stays at ten because, as Linus put it, “having too big of a sliding window makes it very expensive to generate the pack”, and git gc --aggressive widens it to 250 when the space is worth the wait. His view at the time was that packing was “somewhat CPU-wasteful” but “you’re really only supposed to do it maybe once a month (and you can do it during the night)”.

The index

You can read a pack front to back without the index, but you can’t jump to a particular object. A zlib stream doesn’t say how long it is, so the only way to find where entry n ends is to decompress it, which means reaching entry 5,000 requires decompressing the 4,999 before it. This is where the .idx file comes in.

Version 2 of the index consists of six tables:

• Header: a four-byte signature that marks the file as a pack index, followed by the version number.
• Fanout: a shortcut for finding an id quickly. Ids are sorted, so every id that starts with the same byte sits together in the names table. The fanout table has one entry for each of the 256 possible first bytes, and entry i holds how many ids start with i or a smaller byte. Two neighbouring entries therefore give the start and end of one block of ids.
• Names: every object id in the pack, sorted. This is the table Git binary searches.
• CRC32: a checksum of each object’s bytes as they sit in the .pack, so Git can copy an object between packs without decompressing it and still catch corruption.
• Offsets: where each object starts in the .pack, one 4-byte number per object, in the same order as the names.
• Large offsets: 8-byte entries for any object past the 2 GiB mark, since 4 bytes can’t hold offsets that big (empty for most packs).

Here’s the demo pack’s index, with the fanout table collapsed to the entries where the count changes:

           +----------------------------------+
header     | \377tOc                          |  signature
           | version = 2                      |
           +----------------------------------+
fanout     | [00..13] = 0                     |
           | [14..1f] = 1                     |  one object starts with 14
           | [20..3e] = 2                     |  one more starts with 20
           | [3f..82] = 3                     |  one more starts with 3f
           | [83..a6] = 4                     |
           | [a7..d6] = 5                     |
           | [d7..ff] = 6                     |  total objects
           +----------------------------------+
names      | 0  1480ca...                     |
           | 1  203b24...                     |
           | 2  3f20c2...                     |
           | 3  83299d...                     |
           | 4  a77329...                     |
           | 5  d79cd4...                     |
           +----------------------------------+
crc32      | 6 x 4 bytes                      |
           +----------------------------------+
offsets    | 0  150                           |
           | 1  3753                          |
           | 2  262                           |
           | 3  3858                          |
           | 4  3806                          |
           | 5  12                            |
           +----------------------------------+
trailer    | pack checksum                    |
           | index checksum                   |
           +----------------------------------+

Read the fanout column top to bottom and you can see it’s a running total. Reading two neighbours off that table is what makes the lookup fast:

  flowchart LR
    K["<strong>3f20c2…</strong>"]
    F["<strong>fanout</strong><br/><span class='mermaid-detail'>[0x3e] = 2, [0x3f] = 3</span>"]
    N["<strong>names</strong><br/><span class='mermaid-detail'>one candidate at position 2</span>"]
    O["<strong>offsets</strong><br/><span class='mermaid-detail'>[2] = 262</span>"]
    P["<strong style='color:#16181a'>.pack</strong><br/><span class='mermaid-detail' style='color:#16181a'>decompress at 262</span>"]
    K --> F --> N --> O --> P
    classDef step stroke:#5ea1ff,stroke-width:2px
    classDef found fill:#5eff6c,stroke:#5eff6c,color:#16181a
    class F,N,O step
    class P found

To find 3f20c2, Git takes its first byte, 3f, and reads fanout entry 3f and the one before it. Entry 3e is 2, so two ids come before the 3f block. They fill positions 0 and 1 of the names table, which means the block starts at position 2. Entry 3f is 3, so the block ends before position 3 and holds a single id. That id is 3f20c2, and position 2 of the offsets table says it starts at byte 262. Git seeks there in the .pack and decompresses one object. In a pack with a million objects the block would be longer and Git would binary search inside it, but it’s still one search per pack.

Every pack comes with a third file beside the .pack and .idx, the .rev, which is the index read the other way. The .idx is sorted by id, but the objects in the .pack are laid out in a different order, and sometimes Git needs to go from a spot in the pack back to the id stored there. The .rev has one entry per object, in pack order, holding that object’s position in the names table. Here’s the demo pack’s, next to the offsets it was built from:

pack order   offset   .rev entry   id

   0            12  ->   5          d79cd4
   1           150  ->   0          1480ca
   2           262  ->   2          3f20c2
   3          3753  ->   1          203b24
   4          3806  ->   4          a77329
   5          3858  ->   3          83299d

The first object in the pack, at offset 12, is d79cd4. That id sits at position 5 of the sorted names table, so the first .rev entry is 5. Git uses this mapping to work out an object’s size, which the .pack never records: the object at pack position 2 must end where the object at pack position 3 begins, so 3f20c2 is 3,753 minus 262 bytes long, including its header.

A pack never changes once it’s written. A repack writes a new pack and index beside the old ones, then deletes the old ones. That immutability is what keeps the rest of Git simple: a pack is a file you read, never one you edit.

Everything so far has been about a pack at rest on disk. The design starts to show once a pack has to move, over the network and under a repository that’s grown too big for a single pack.