./ahmedhashim

Dissecting a packfile raised two questions. The pack stored the newer version of a file intact, and the older version as an 18-byte delta against that file. But:

1. How did Git choose that pairing?
2. How does Git locate one object in a pack without reading the entire file?

Note that both answers reuse the same six-object demo pack. Here’s the output of git verify-pack -v on it 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. 83299d is the older version stored as a delta against it. The last column shows each object’s byte offset within the pack.

Choosing bases

Git stores snapshots, it doesn’t store history about individual files. Blobs only contain content; the only thing that associates them with a filename is a directory tree that lists them. Git knows 3f20c2 and 83299d exist, and which trees list each of them, but nothing in Git’s object store explicitly says that one is derived from the other. Rather than figure that out, git pack-objects uses heuristics Linus described on IRC in 2006 that are now included in Git’s documentation.

Objects are sorted by three keys, in this order:

1. Type: A blob will only ever be stored as a delta against another blob, or tree against another tree. Objects of different types share almost no bytes, making the delta larger than the object itself would be.
2. Path: pack_name_hash hashes the last sixteen non-whitespace characters of the path each object was first seen at into 32 bits, giving the last characters more weight. The effect is that every Makefile lands in the same bucket and every .c file lands near every other .c file.
3. Size: biggest objects first.

Git then walks that list one object at a time. For each object, the candidate bases are the ten objects that appear just before it in the list (pack.window). That window slides forward as the walk continues, so each object is a candidate for the ten after it. Here’s a window of size three, at one step and then 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 these two steps b fell out the window and e joined it.

Objects are stored in one fashion, entirely or as a delta against one base. So Git tries one against each candidate and keeps whichever resulted in the smallest output. Failing all candidates, it stores the object complete and starts a new chain with it. That’s how a file with hundreds of versions winds up a series of chains rather than one.

The majority of pairs are discarded before any bytes are compared. A packfile chain can contain at most 50 deltas (pack.depth), so any candidate at the bottom of one that deep will be skipped, as a delta against it would be at depth 51. Same thing if it is more than 32 times larger, or if its size difference is already greater than that of the best delta found so far. All those checks happen before anything else in try_delta.

Sorting largest first causes the deltas to point backwards. Files usually get larger as they change, so the newest version is typically the largest. It goes first in its group and so gets stored whole. Every older version after it becomes a delta that mostly says “copy”. If a file gets smaller instead then the sort order reverses: the older bigger version gets stored whole and the newer version becomes a delta against it. The delta will still typically be small since the newer content was mostly just a subset of the older. But now reading the newest version requires a delta step instead of zero.

When every object has its representation, the pack is written out newest first, beginning with objects reachable from the branch tips. That ensures the front of the pack contains what a checkout needs, and every base lands ahead of the deltas pointing at it.

All of this takes CPU time. The default window remains ten because, as Linus explained, “having too big of a sliding window makes it very expensive to generate the pack”, but git gc --aggressive expands it out to 250 if waiting is worth the space. At the time his rationale 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 sequentially read an entire pack from front to back without an index, but you can’t seek to an arbitrary object. Because a zlib stream doesn’t contain its length, the only way to know where entry n ends is to decompress it first. So to get to entry 5,000, you’d need to decompress the preceding 4,999 entries. This is where the .idx file comes in handy.

Version 2 of the index has six tables:

• Header: four bytes saying this is a pack index file, followed by the version number.
• Fanout: an index to jump quickly to an id. Since ids are sorted, every id starting with a given byte is contiguous in the names table. The fanout table has one entry for each of the 256 possible first bytes, and entry i contains the number of ids starting with byte i or smaller. Two adjacent entries in fanout thus give the start and end of one group of ids in the name table.
• Names: all object ids contained in the pack, sorted. This is the table Git binary searches.
• CRC32: a checksum of the compressed bytes of each object as they’re laid out in the .pack. This lets Git copy an object from one pack file to another without decompressing it first, yet still detect corruption.
• Offsets: the position in the .pack where each object begins. One 4-byte number per object, in the same order as the names.
• Large offsets: 8-byte offsets for any object past the 2 GiB mark, since 4 bytes can’t hold offsets that big. Empty in most packs.

Here’s the demo pack’s index, with the fanout table collapsed to the points where the value 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                   |
           +----------------------------------+

Take a look at the fanout column. Read it top-down and notice it’s a running total. Reading two adjacent entries off this table is the trick that allows fast lookup:

  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 locate 3f20c2, Git takes its first byte, 3f, and reads fanout entry 3f and the one before it. Entry 3e is 2, so there are two ids preceding the 3f block. Those ids occupy positions 0 and 1 of the names table, so block 3f starts at position 2. Entry 3f is 3, so the block ends before position 3 and contains just one id. That id is 3f20c2, and position 2 of the offsets table tells us it starts at byte 262. Git seeks to that byte in the .pack file and decompresses that one object. If our pack had a million objects, this block would be much longer and Git would binary search within it, but it’s still only one search per pack.

Each pack also comes with a third file besides the .pack and .idx: the .rev file, which is simply the index in reverse. While the .idx is ordered by id, the objects inside the .pack are physically arranged in another order, and occasionally Git needs to go from a position 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. Below is the demo pack’s .rev file next to the offsets it was derived 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 file, at offset 12, is d79cd4. That object id is found at position 5 in the sorted names table, so the first .rev entry is 5. Git uses this to determine the size of an object from its position in the pack, since the .pack file never stores an object’s size anywhere: the object at pack position 2 must finish right where the object at pack position 3 starts. So using the .rev file, we know that 3f20c2 is 3,753 minus 262 bytes long, header included.

A pack, once written, never changes. A repack writes a new pack and index next to the old ones, then deletes the old ones. That immutability is what allows the rest of Git to be simple: a pack is a file that you read, never one you edit.

Up until this point we’ve only talked about a pack sitting quietly at rest on disk. The design starts to show once a pack needs to move across the network, underneath a repository that has grown too big for a single pack.