./ahmedhashim

Most developers use Git every day, but much of it happens under the hood. When you clone a repository you get output that looks like this:

$ 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.

The server found 204,170 objects, but only counted 86 and compressed 24. The other 204,084 were read directly out of a pack. After that, your computer spent the last line resolving 144,707 deltas. What is happening here?

Everything above happens in a single file format known as the packfile.

The packfile

A packfile is simply one file containing multiple Git objects. Git will typically store each object in its own compressed file. There are three types of objects you should know about here:

1. Blob: the contents of a single file.
2. Tree: the listing of one directory, naming the blobs and subtrees inside it.
3. Commit: a pointer to the root tree, plus the parent commits, author and message.

Commits, trees, blobs. A repository with any significant history will end up with hundreds of thousands of these things. A pack contains them all inside a single file. Similar objects are stored as small differences between each other which are called deltas. An index is kept alongside the pack so Git can still access any object instantly by its id.

That fixes two problems Git imposes upon itself:

1. Size: Each revision of each file is stored whole, and SHA-1 gives a one-line edit an entirely different id, so without packing, the object store bloats by an entire copy every time you edit something. Deltas store just the difference.
2. Transfer: Remember how a clone would have to receive those objects one file at a time? Well, instead the pack is the thing that Git actually sends. The clone above downloaded a single pack containing all 204,170 objects, and that one file now lives in its .git/objects/pack.

So let’s open one up.

Loose objects

Git takes your object and sticks on a short header: blob 9982\0, then hashes that combined content. The hash of that is now the object id for your data. Git compresses it with zlib, then sticks it in .git/objects/, in a directory named for the first two hex characters of the object id. We call that a loose object. Loose objects are Git’s simplest form of object storage because writing one never requires Git to modify anything already on disk.

Here’s a repository into which I committed a header file ten kilobytes in size, added a comment and committed again:

$ du -b .git/objects/*/*
58    .git/objects/a7/732906e8812408a49c16cb765b85300721fb16
59    .git/objects/20/3b24db4881c92152fbd87d0aeacd7c74be79c5
129   .git/objects/14/80ca830fac79e4e47a514654a7cf0e0428cc9c
174   .git/objects/d7/9cd4c394340fdbf839ecbc71e24b7c1384cf3c
4809  .git/objects/83/299d47324f1ed351db0f6f277b97811cb288a4
4825  .git/objects/3f/20c233eae9d1047b393d111f906c76bfd772c0

As you can see, the four small files are the commits and trees. The two large ones are blobs: 83299d is the original file, 9,959 bytes; 3f20c2 is the file with my line added, 9,982 bytes. Individually, they compress down to around 4.8 KB each, so adding my single line cost me 4.8 KB of disk space. That’s because the loose format can’t express “same as 83299d, plus a line”.

The other cost is the filesystem. Each object is a file, each read is an open. Two hex digits only allow for 256 directory names (00 through ff), so a repository with several hundred thousand objects is several hundred thousand small files spread across those directories. That’s a terrible layout for anything that needs to touch them all, like cloning a repository, or git log -p, which needs to read many of them sequentially.

Inside a pack

Git addresses both of these problems by packing. git gc can be run manually to do this. Git will also perform the task automatically after running certain commands once you have around 6,700 loose objects (Git estimates you have this many by checking in only one directory). Once gc is complete, the six loose files will be replaced by a single pack:

$ git gc
$ ls .git/objects/pack
pack-3bf68430aae7e0388ad9fc7a7a353d45e1a9e726.idx
pack-3bf68430aae7e0388ad9fc7a7a353d45e1a9e726.pack
pack-3bf68430aae7e0388ad9fc7a7a353d45e1a9e726.rev

git verify-pack -v shows what ends up in the packfile. The columns are object id, type, uncompressed size, size in pack, and offset. Delta entries have extra columns for chain depth and the base they point to:

$ git verify-pack -v .git/objects/pack/pack-3bf68430aae7e0388ad9fc7a7a353d45e1a9e726.idx
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
non delta: 5 objects
chain length = 1: 1 object

Notice how the newer blob 3f20c2 gets stored whole in 3,491 bytes. The older blob 83299d is stored as a delta of only 18 bytes against it. Each version of the file now takes up less space than it did loose. Even the whole blob is smaller, since loose objects are zlib level 1 compressed to keep writes quick, while packs are compressed with the default level 6.

The delta points backwards intentionally. The latest version is the one readers care about most of the time, so that’s the version we keep whole. Reading it requires only one decompression pass.

The pack on disk is simply a header, a run of object entries, and a checksum. Here is the demo pack, with offsets from the listing above:

  flowchart LR
    H["<strong>PACK</strong><br/><span class='mermaid-detail'>v2, 6 objects</span>"]
    C["<strong>2 commits</strong><br/><span class='mermaid-detail'>at 12, 150</span>"]
    B1["<strong style='color:#16181a'>blob</strong><br/><span class='mermaid-detail' style='color:#16181a'>3f20c2 at 262</span>"]
    T["<strong>2 trees</strong><br/><span class='mermaid-detail'>at 3753, 3806</span>"]
    B2["<strong style='color:#16181a'>delta</strong><br/><span class='mermaid-detail' style='color:#16181a'>83299d at 3858</span>"]
    X["<strong>SHA-1</strong><br/><span class='mermaid-detail'>trailer</span>"]
    H --> C --> B1 --> T --> B2 --> X
    B2 -.->|"3,596 bytes back"| B1
    classDef whole fill:#5eff6c,stroke:#5eff6c,color:#16181a
    classDef delta fill:#5ea1ff,stroke:#5ea1ff,color:#16181a
    class B1 whole
    class B2 delta

The header is the four bytes PACK, followed by a version (Git only writes version 2) and a 32-bit object count. So a single pack can contain up to 2^32 objects. The trailer is a SHA-1 of everything up until that point. Git names the pack file based on this hash. Each object entry between header and trailer starts with a variable-length header which packs the type into three bits along with the size. After the header comes the zlib stream containing just that object’s data. Here are the two blob entries from our demo pack file, broken down:

3f20c2, whole, at offset 262

         +---+-----+------+
  be     | 1 | 011 | 1110 |  more bytes follow, type 3 = blob, size bits 0-3
         +---+-----+------+
  ef     | 1 | 1101111    |  more bytes follow, size bits 4-10
         +---+------------+
  04     | 0 | 0000100    |  last header byte, size bits 11-17
         +---+------------+
  78 9c  | zlib stream    |  3,488 bytes
  ...    +----------------+
                              size = 9,982

83299d, delta, at offset 3858

         +---+-----+------+
  67     | 0 | 110 | 0111 |  last header byte, type 6 = offset delta, size 7
         +---+-----+------+
  9b     | 1 | 0011011    |  more bytes follow, offset bits
         +---+------------+
  0c     | 0 | 0001100    |  last offset byte, offset bits
         +---+------------+
  78 9c  | zlib stream    |  15 bytes
  ...    +----------------+
                              base is 3,596 bytes back, at offset 262

The top bit of each byte indicates whether there is a subsequent byte. Thus a small object requires a single header byte, while a large object header has as many bytes as are needed. The remaining bits are used to store the uncompressed object size, with the low-order bits in the first byte and progressively higher bits in each subsequent byte. Note this is little-endian order. For deltas this means the size of the delta-chunk, not the size of the object the delta recreates. The location of the base is stored directly after the header and immediately before the zlib compressed stream starts. You can find layouts for the rest of the objects in the format document.

Pay attention to the fact that every entry has its own zlib stream. Git doesn’t compress the entire pack into a single stream. If Git did that, the compressed pack would be smaller. zlib takes advantage of repeated bytes to compress, and two objects will usually have some bytes in common. However, if Git compressed the entire pack into a single stream, to read the last object you would need to decompress the entire pack. By giving each object its own stream, Git can just seek to the entry it wants and decompress that one.

Deltas

That delta above was only 18 bytes long, but 15 of those bytes were part of the zlib stream. Let’s see what’s in it. A delta contains instructions to recreate one object from another object. There are two types of instructions:

1. Copy: copy a range of bytes from the base.
2. Insert: insert bytes not present in the base.

The delta begins with the size of the base, then the size of our target blob, both encoded as varints. Here’s the full seven-byte delta for the older blob:

fe 4d      base size    9,982
e7 4d      target size  9,959
b0 e7 26   copy 0x26e7 bytes from offset 0

b0 is 1011 0000 in binary. The high bit indicates copy, and the low seven bits indicate which of the following offset and size bytes are provided. Only the two size bytes are provided, so the offset is zero and the size is 0x26e7 (9,959). The delta says “copy the first 9,959 bytes of the base, then stop”. The base is the newer file, so stopping 23 bytes short of its end skips the line I appended. What remains is the original file.

An insert instruction is costly. A copy only needs to specify the starting point and number of bytes to copy, but an insert needs to include the new bytes themselves, and it can specify at most 127 bytes. Thus deltas that delete content can be small while deltas that add content cannot be. That’s why Git will choose to store the larger object whole and delta compress the smaller one against it: the delta only needs to leave bytes out.

Note that deltas operate on bytes, unlike git diff, which Git knows how to compute lazily from entire objects. Aditya Mukerjee has a nice write-up of parsing packs by hand that walks through all of these bytes.

Each delta must specify which object it bases its changes off of, and the pack entry may record that object in one of two ways:

1. Offset delta: store how far back in the same pack the base starts. That’s what the two offset bytes (9b 0c) in the entry header above were. They encode 3,596, and 3,858 minus 3,596 is 262, the entire blob.
2. Ref delta: store the 20-byte id of the base instead. Git only uses this when the base is not in the same pack.

A delta can itself be built on top of another delta, so deltas are chained together. Here’s a file with four revisions chained within a single pack. The newest is stored whole, and each older version is a delta against the one after it:

  flowchart LR
    V1["<strong style='color:#16181a'>oldest</strong><br/><span class='mermaid-detail' style='color:#16181a'>delta, depth 3</span>"]
    V2["<strong>v2</strong><br/><span class='mermaid-detail'>delta, depth 2</span>"]
    V3["<strong>v3</strong><br/><span class='mermaid-detail'>delta, depth 1</span>"]
    V4["<strong style='color:#16181a'>newest</strong><br/><span class='mermaid-detail' style='color:#16181a'>whole</span>"]
    V1 -.->|"base"| V2 -.->|"base"| V3 -.->|"base"| V4
    classDef whole fill:#5eff6c,stroke:#5eff6c,color:#16181a
    classDef delta fill:#5ea1ff,stroke:#5ea1ff,color:#16181a
    class V4 whole
    class V1 delta

Reading the latest version is one decompression. Reading the oldest version means Git walks back through the arrows until it finds the full object, decompresses that, then goes back out applying each delta in turn, three of them in this example. Two settings determine how much effort that requires:

1. pack.depth: limits a chain to 50 deltas.
2. core.deltaBaseCacheLimit: allocates 96 MiB per thread for caching previously-decompressed bases. This allows decompressing a base once and then reusing it for reading many objects that share that base.

Older versions are at the ends of long chains, so reading old history requires more work than reading recent history. Increasing pack.depth allows longer chains which decreases pack size but makes those old reads even slower.

Two mysteries were left unexplained up there. Git decided on its own to use 3f20c2 as the base of 83299d, and verify-pack magically knew where each object began without parsing the file. Those come next, in how Git picks a base, and how the index finds it.