./ahmedhashim

Choosing bases and building the index left us with an immutable pack sitting on disk. Let’s see what happens when packs travel over the network, and what happens when a repository grows large enough that the design starts to show.

Everything below ties 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 transmits a packfile (same format Git uses for objects on disk). This is why the clone output above is littered with pack nomenclature like delta and pack-reused. The client sends a list of commits it already has to the server. The server determines what objects it is missing based on that list and sends back a single pack containing those objects.

Most of those objects are already deltas on disk on the server. As long as the base also goes in that pack, the server will send that delta as-is without having to decompress or recompute anything, so serving up a fetch mostly just involves copying bytes from one file to another file. 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 from a previous fetch. When this happens the server will omit sending the base completely. Instead it sends the delta as a “ref delta”, which refers to its base by object id instead of by offset in the pack. It expects the client to resolve it locally. A pack with those holes in it is called a “thin pack”.

This would work fine for a transfer, but there is one rule for packs on disk: every delta’s base must be somewhere in the same file, because Git only opens one pack to reconstruct an object. So prior to storing a thin pack, the client copies each missing base out of its existing packs and appends them to the end of the new pack.

The other half of storing a pack shows up on the Resolving deltas line of the clone output. The .idx requires the id of every object, and you can only compute a delta’s id after you’ve rebuilt the object it describes. So the client walks each delta, rebuilds it, hashes the result and notes the id. Of the objects cloned above, 144,707 out of 204,170 were received as deltas and required this step.

Small fetches don’t stay packed. If a fetch retrieves fewer than 100 objects (transfer.unpackLimit), the client unpacks them into loose objects instead. Otherwise, it leaves the pack intact, writing out an index for it. This means a newly cloned repo will have exactly one pack: the one it downloaded. One month of pulling leaves you with that pack, plus one pack for each pull large enough to retain, plus some loose objects left behind by the small pulls.

Counting objects

All of the above is well and good until your repository grows in size. The first issue you’ll notice is the Counting objects line of the clone output. When serving a clone request, the server has to determine which objects need to be sent to you. Without any existing list of those objects, it must walk every commit and every tree. As GitHub stated in 2015, counting the Linux kernel repository took up to eight minutes of CPU time before sending the first byte of pack data.

The solution was reachability bitmaps, ported from JGit in Git 2.0. A bitmap is associated with one commit, and has one bit for every object in the pack: bit i indicates whether object i (in pack order) is reachable from that commit. Saving one of these for every commit would take too much space, so Git only saves them for the branch tips and a thinned-out sample of older commits. If a commit doesn’t have its own bitmap, Git starts from the nearest ancestor that does and walks the difference.

Now that we have bitmaps, figuring out what to send becomes bitwise math. Here’s a pack of eight objects with two branches. The client wants 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

Notice that a clone is the same except there’s nothing to subtract: OR together the bitmaps of every branch tip and send whatever is turned on. That’s why the clone above only counted 86 objects. The other 204,084 were answered by bitmaps and the server simply sent them directly out of its pack file. Bitmaps themselves remain small because pack order places related objects near each other, meaning each bitmap is long runs of the same bit value and compresses very well.

However, there’s a caveat. Bit 3 is interpreted as “the object at position 3 in this pack”, which means a bitmap only describes the pack it was created for. Objects that arrive later, either in later packs or as loose objects, aren’t covered. The server is forced to fall back to walking commits and trees for those, and the longer it’s been since the last bitmap was written, the more of them there will be.

Repacking everything

The simple solution would be to store everything in one pack again, which a full repack achieves. However, that means rewriting all objects, and larger repositories take longer to repack, and also grow more quickly. By 2020, GitHub’s maintenance tasks were timing out against its largest repos. Three things changed:

1. Multi-pack index: instead of having a sorted name table for each pack, a single sorted table spans multiple packs. This allows a lookup to still be done with one binary search, instead of one per pack. Without it, find_pack_entry searches each pack in turn, starting with the most recently used. See git multi-pack-index.
2. Multi-pack bitmaps: bitmaps were generalized to cover a multi-pack index rather than just one pack, so new packs no longer fall outside them.
3. Geometric repacking: with git repack --geometric=2, every pack is kept at least twice the size of the next smaller pack, measured in objects. This ensures each run only combines the small packs that violate this 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 from the biggest pack to the smallest, each pack should be at least twice as large as the one after it. 64 to 32 passes, 32 to 5 passes, but 5 to 3 fails, so all packs from the 5-object pack down are combined into a single new pack of 9 objects. Since 32 is more than twice 9, the rule holds again and the two large packs are left alone. Each repack now costs roughly in proportion to what you’ve pushed since the last one, with an occasional complete rewrite to move related objects closer together again. GitHub’s average repack time dropped from about a minute to 15 seconds.

Git 2.37 started treating unreachable objects differently. Rather than writing them out to loose files that expire later (which could use up all the inodes on a busy repo), unreachable objects are stored in a cruft pack, along with a separate .mtimes file that stores when each object expires.

Delta failures

The final category of problems relates to the deltas themselves. The heuristics for choosing a base work well for most repos, but when you get to a big enough scale there are a couple places where they fall short.

The first is the name hash, which only looks at the last sixteen characters of a path. If you have thousands of package.json or BUILD files in a monorepo, they will all have the same hash. They crowd the window with irrelevant candidates, potentially leaving the actual previous version of your file just outside it. The result is whole objects where deltas should be, and bloated packs.

Git 2.49 introduced --name-hash-version=2, which folds the parent directories into the hash. Git 2.51 introduced --path-walk, which buckets objects by their full path and walks those buckets first, before the normal sliding window runs.

Hosts like GitHub store a repository and all its forks in the same shared pack because most of their objects are identical. However, that presents another problem. When the server repacks, the smallest delta for an object in one fork could have a base that only exists in another fork. That saves disk space, but a client fetching that first fork will never have that base, so the delta can’t be sent as-is. The server has to decompress that object and create a new delta from scratch, for every single fetch.

Delta islands (pack.island) help by assigning refs to islands (usually one island per fork) and permitting a delta only if its base is reachable from the same island as the object.

Then there are objects no heuristic can salvage. Deltas work on matching bytes, and compressed or binary content doesn’t have many between versions. Over a threshold of 512 MiB (core.bigFileThreshold) Git gives up on deltas entirely, so every version of a huge binary is another full copy in the pack, and in every clone, forever.

Git LFS avoids this by having a pointer file in the repo, and storing the content somewhere else. Partial clone (--filter=blob:none) takes the opposite approach, and leaves blobs on the server until a checkout actually 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”. Two decades later, Git still writes the same version 2 pack, and as far as the rest of Git is concerned, everything is a whole object. Every fix listed above added a file alongside the pack, changed how frequently it gets rewritten, or changed which bases inside it get picked. None of them changed the pack format. When cloning spends too long counting objects, or a repack hits its timeout, that’s where repository size becomes visible first.

When you next clone something and watch that output scroll by, you’ll know what each line is doing. An awful lot of work went into making those lines scroll by so fast, and nearly all of it is contained in a single file you’ll never need to open.