./ahmedhashim

Choosing bases and building the index ended with a pack sitting on disk, immutable. Let’s take a look at what happens when packs move over the network, and when a repository gets big enough that the design starts to show.

Everything below comes back to the same clone output:

$ git clone https://github.com/atom/atom
Cloning into 'atom'...
remote: Enumerating objects: 204170, done.
remote: Counting objects: 100% (86/86), done.
remote: Compressing objects: 100% (24/24), done.
remote: Total 204170 (delta 64), reused 62 (delta 62), pack-reused 204084 (from 1)
Receiving objects: 100% (204170/204170), 322.85 MiB | 48.84 MiB/s, done.
Resolving deltas: 100% (144707/144707), done.

On the wire

A git fetch sends a packfile, the same format Git stores on disk, which is why the clone output above is full of pack terms like delta and pack-reused. The client tells the server which commits it already has. The server then works out which objects are missing from that and sends them as a single pack.

Most of those objects are already deltas on the server’s disk. As long as the base is going in the same pack, the server sends the delta as it is, without decompressing or recomputing anything, so serving a fetch is mostly copying bytes from one file to another. The reused and pack-reused counts in the clone output are how many objects were sent that way.

Sometimes the client already has the base of a delta from an earlier fetch. In this case the server doesn’t send the base at all. It instead sends the delta as a “ref delta”, which names its base by object id rather than by position in the pack, and trusts the client to find it locally. A pack with those holes in it is called a “thin pack”.

This works for a transfer, but a pack on disk has a rule: every delta’s base must be somewhere in the same file, because Git only opens one pack to rebuild an object. So before the client stores a thin pack, it copies each missing base out of its other packs and appends it to the end of the new one.

The Resolving deltas line in the clone output is the other half of storing a pack. The .idx needs every object’s id, and a delta’s id can only be computed from the rebuilt object. So the client walks every delta, rebuilds the object it describes, hashes it and records the id. In the clone above, 144,707 of the 204,170 objects arrived as deltas and went through that step.

Small transfers don’t stay packed. If a fetch brings in fewer than 100 objects (transfer.unpackLimit), the client unpacks them into loose objects. Above that, it keeps the pack and writes an index for it. So a fresh clone has exactly one pack, the one it downloaded. After a month of pulling, the repository has that pack plus one more for every pull that was big enough to keep, and a scattering of loose objects from the small ones.

Counting objects

Everything above works fine until the repository gets big. The first problem is the Counting objects step in the clone output. To serve a clone, the server has to work out which objects to send, and since no list of them exists it walks every commit and every tree. GitHub wrote in 2015 that counting the Linux kernel could take up to eight minutes of CPU before a single byte of pack was sent.

The fix was reachability bitmaps, ported from JGit in Git 2.0. A bitmap belongs to one commit and has one bit per object in the pack: bit i is set if object i in pack order is reachable from that commit. Storing one for every commit would take too much space, so Git only writes them for the branch tips and a thinning sample of older commits. A commit without its own bitmap starts from the nearest ancestor that has one and walks the difference.

With bitmaps in place, working out what to send is bit arithmetic. Here’s a pack of eight objects with two branches, where the client is fetching main and already has v1:

pack position          0 1 2 3 4 5 6 7

reachable from main    1 1 1 1 1 0 1 1
reachable from v1      1 1 0 1 0 0 1 0

main AND NOT v1        0 0 1 0 1 0 0 1   -> send objects 2, 4 and 7

A clone is the same with nothing to subtract: OR together the bitmaps of every branch tip and send whatever is set. That’s why the clone at the top only counted 86 objects. The other 204,084 were answered by bitmaps, and the server copied them straight out of its pack. The bitmaps themselves stay small because pack order puts related objects side by side, so each one is long runs of identical bits and compresses well.

There’s a catch, however. Bit 3 means “the object at position 3 in this pack”, so a bitmap only describes the pack it was written for. Objects that arrive later, whether in new packs or loose, aren’t in it. For those, the server is back to walking commits and trees, and the longer it’s been since the last bitmap was written, the more of them there are.

Repacking everything

The obvious fix is to put everything back in one pack, which is what a full repack does. But that means rewriting every object, and bigger repositories both take longer to repack and grow faster. By 2020, GitHub’s maintenance jobs on its largest repositories were hitting their timeouts. Three things changed:

1. Multi-pack index: a single sorted name table that covers many packs, so a lookup is still one binary search instead of one per pack. Without it, find_pack_entry tries each pack in turn, most recently used first. See git multi-pack-index.
2. Multi-pack bitmaps: bitmaps were extended to cover a multi-pack index instead of a single pack, so new packs no longer fall outside them.
3. Geometric repacking: git repack --geometric=2 keeps every pack at least twice the size of the next smaller one, counted in objects, so each run only combines the small packs that break that rule:

  flowchart LR
    subgraph B["Before"]
        direction LR
        B1["<strong>pack</strong><br/><span class='mermaid-detail'>64 objects</span>"] ~~~ B2["<strong>pack</strong><br/><span class='mermaid-detail'>32 objects</span>"] ~~~ B3["<strong>pack</strong><br/><span class='mermaid-detail'>5 objects</span>"] ~~~ B4["<strong>pack</strong><br/><span class='mermaid-detail'>3 objects</span>"] ~~~ B5["<strong>pack</strong><br/><span class='mermaid-detail'>1 object</span>"]
    end
    subgraph A["After --geometric=2"]
        direction LR
        A1["<strong>pack</strong><br/><span class='mermaid-detail'>64 objects</span>"] ~~~ A2["<strong>pack</strong><br/><span class='mermaid-detail'>32 objects</span>"] ~~~ A3["<strong style='color:#16181a'>pack</strong><br/><span class='mermaid-detail' style='color:#16181a'>9 objects</span>"]
    end
    B ~~~ A
    classDef roll stroke:#5ea1ff,stroke-width:2px
    classDef new fill:#5eff6c,stroke:#5eff6c,color:#16181a
    class B3,B4,B5 roll
    class A3 new
    style A fill:transparent
    style B fill:transparent

Walking the packs from largest to smallest, each one should be at least double the next. 64 to 32 passes, 32 to 5 passes, but 5 to 3 fails, so everything from the 5-object pack down is combined into one new pack of 9. Since 32 is more than twice 9, the rule holds again and the two big packs are left untouched. Each repack now costs in proportion to what was pushed since the last one, with an occasional full rewrite to bring related objects back together. GitHub’s average repack dropped from about a minute to fifteen seconds.

Unreachable objects got their own treatment in Git 2.37. Instead of writing them out as loose files to expire later, which on a busy repository could exhaust inodes, a cruft pack holds them with a separate .mtimes file recording when each one expires.

Delta failures

The last set of problems is with the deltas themselves. The heuristics for choosing a base work well for most repositories, and at scale there are a few places where they don’t.

The first is the name hash, which only sees the last sixteen characters of a path. In a monorepo with thousands of package.json or BUILD files, they all get the same hash and crowd the window with unrelated candidates, so the actual previous version of a file can sit just outside it. The result is whole objects where deltas belong, and packs much larger than they need to be.

Git 2.49 added --name-hash-version=2, which mixes the parent directories into the hash, and Git 2.51 added --path-walk, which groups objects by full path for a first pass before the usual window runs.

Hosts like GitHub keep a repository and all of its forks in one shared pack, since most of their objects are the same. That creates a different problem. When the server repacks, the smallest delta for an object in one fork might be against a base that only exists in another fork. That saves disk space, but a client fetching the first fork will never have that base, so the delta can’t be sent as it is. The server has to decompress the object and compute a new delta, on every fetch.

Delta islands (pack.island) fix this by grouping refs into islands, usually one per fork, and only allowing a delta when its base is reachable from the same island as the object.

Then there are the objects no heuristic can help. Deltas match bytes, and compressed or binary content shares few of them between versions. Above 512 MiB (core.bigFileThreshold) Git doesn’t even try, so every version of a large binary is another full copy in the pack, and in every clone, forever.

Git LFS solves this by storing a pointer file in the repository and the content elsewhere. Partial clone (--filter=blob:none) takes the other approach and leaves blobs on the server until a checkout needs them.

Linus said in 2006 that the point of packs was that they let Git “still conceptually never deal with deltas at all, and be a ‘whole object’ store”. Twenty years on, Git writes the same version 2 pack, and the rest of Git sees nothing but whole objects. Every fix above added a file next to the pack, changed how often it gets rewritten, or changed how the bases inside it are chosen. None of them changed the pack format itself. When a clone stalls on counting objects or a repack runs past its timeout, that’s where the size of the repository shows first.

The next time you clone something and that output scrolls past, you’ll know what each line is doing. A great deal of work went into making those lines go by quickly, and almost all of it lives in one file you’ll never have to open.