codient/blog

How git clone works · part 2

This post is the written version of the video above, with diagrams you can click and a quiz.

remote: Enumerating objects: 33760, done.
remote: Counting objects: 100% (72/72), done.
remote: Compressing objects: 100% (42/42), done.
remote: Total 33760 (delta 44), reused 30 (delta 30), pack-reused 33688 (from 2)
Receiving objects: 100% (33760/33760), 9.89 MiB | 36.44 MiB/s, done.
Resolving deltas: 100% (19195/19195), done.

This is the output you get when you run git clone. In part 1, we discussed how the server finds the git objects it needs to send to the clients. This post covers the rest of lines you see in the git clone output. Once the server knows which objects your commit needs, it creates a packfile that includes all of the objects and the client takes this packfile and recreates all of the files on disk.

Loose objects

When git saves an object, it compresses it and writes it to its own file in .git/objects, named by its hash. These are loose objects.

Our tiny repository from part 1 has 13 objects, so 13 files.

$ find .git/objects -type f # the tiny repo, before packing
.git/objects/c2/008c90… c1
.git/objects/10/3f64e4… c2
.git/objects/96/0a520e… c3
.git/objects/3d/027221… c4
.git/objects/15/17b594… tree c1
… 8 more, one file per object

One at a time

The simplest version of git clone asks for each file in turn. One request, one answer, then the next.

For our tiny repo, that's 13 requests.

Git did clone like this once, from plain web servers. It still can.

The pack file

However, as repos get larger - one file at a time doesn't scale.

Git's answer: put every object in one file and send that. One request, one answer. That file is a pack file.

The file starts with the word PACK and the number of objects. Then the objects, one after another: each one's type and size, then its contents, compressed. It ends with a checksum, a fingerprint of every byte before it.

The tiny repo's real pack file: 1,084 bytes
Each block is drawn to scale. Click one.
Click a block.
Check yourself
What's at the very end of a pack file?

Deltas

Our repo has 3 versions of app.py. Version 1 and version 3 differ only in the last line: print('version 1') against print('version 3').

So git stores version 3 whole, and version 1 as changes from version 3. This is exactly how git stores version 1:

copy the first 747 bytes of version 3, then add 4 new bytes, a `1`, a quote, a bracket and a newline.

Rebuild app.py v1 from its delta
The delta is two instructions. Run them on version 3.
app.py v3, stored whole
rebuilding app.py v1

12 bytes instead of 751. That's a delta.

Compression + Deltas takes a repo like ExpressJS from 157 MB to 10 MB.

Express, three ways
Check yourself
app.py v1 is stored as a delta against v3. What's in those 12 bytes?
Express: 157 MB of objects. What does compressing each object get it to, before deltas?

Finding deltas

Git doesn't keep a list of which objects are versions of each other. The only way to find a good delta is to compute one and see how small it comes out.

Try every pair? Our 13 objects make 78 pairs (13choose2). Git's own repository makes about 90 billion.

So git sorts the objects by kind, file name, then size (descending) so likely matches land next to each other. Then it tries each object against only the 10 just before it. That's the window. It keeps the smallest delta it finds.

Slide the window
The 13 objects in git's order. Step through them and see what each one is tried against. Shrink the window to see what it costs.

The window is an optimization. Two versions that are more than 10 objects apart never get compared, so git can miss a smaller delta.

On git's own repository, it's still about 16 seconds of searching and compressing.

That is still too slow to run on every clone.

Check yourself
Why does git sort the objects before searching?
What does the window give up?

Search once, copy on every clone

So the server searches once. Every so often it packs its loose objects into a stored pack file, and that's when the delta search runs. Git does this by itself once a repository has about ~6,700 loose objects. GitHub does it in the background.

At the same time, it saves the bitmaps from part 1. Each bit lines up with one object in that stored pack.

Now, lets say a clone of c4 comes in. Step 3: read c4's bitmap. Every bit is a 1, so all 13 objects go.

Step 4: build a new pack file for this clone. Every object is already in the stored pack, so the server copies its bytes, deltas and all. Since the whole stretch is going, it copies the stretch in one go.

Note that the pack file contains the deltas for app.py v1 and app.py v2. This is because the whole file for app.py v3 is also part of the pack file. And the client machine can rebuild the app.py v1 and v2 objects from the deltas.

Building one clone's pack file, git's own repository
Check yourself
On a busy server, when does the delta search run?
The server copies app.py v1's stored delta into your pack. Why does that work?

Reading the output

GitHub doesn't pack after every push. So I pushed one commit to the tiny server, app.py version 4. That's 3 new objects: a commit, a tree and the new app.py. A small push like that stays loose. And c5 has no bitmap yet.

Then I cloned it:

remote: Enumerating objects: 16, done.
remote: Counting objects: 100% (3/3), done.
remote: Compressing objects: 100% (3/3), done.
remote: Total 16 (delta 0), reused 0 (delta 0), pack-reused 13

Enumerating objects, 16. c5 has no bitmap, so the server walks back from it to c4, which has one. 3 walked, plus c4's 13.

pack-reused 13. The existing pack file, copied in one go.

Counting objects, 3. The loose objects aren't in the stored pack, so the server looks each one up: what kind, how big, where it lives.

Compressing objects, 3. The delta search, on just those 3.

Push, repack, clone
Change the server, then read its clone output. Every output here is a real run against the tiny repo.
stored pack file
loose objects
Check yourself
A server has a stored pack of 13 objects and 6 loose ones from two pushes. What does Counting objects say?
After a repack, which lines disappear?

Step 5: check and unpack

The pack file arrives. That's Receiving objects.

The pack file carries no names, so the client machine hashes each object as it arrives. The hash is the name.

A delta can't be hashed yet. So your machine turns every delta back into a whole object and hashes that. That's Resolving deltas.

Then it checks the checksum at the end, and that every commit's tree and parents arrived.

Your machine doesn't trust the server. I flipped one bit inside app.py v3 in the tiny pack and cloned again:

error: inflate: data stream error (incorrect data check)
fatal: pack has bad object at offset 496: inflate returned -3

Git threw the whole thing out.

The hash is the name
This is app.py v3. Your browser hashes it the way git does. c4's tree expects 02d845b1…. Change any character.
…

It doesn't matter who sends the file. If the hashes match the commit you asked for, the data is right.

Check yourself
How does your machine learn each object's name?
Why can't your machine hash a delta as it arrives?
A server sends a pack with one changed byte inside app.py v3. What happens?

The whole clone

  • 1 Ask: what branches are there?
  • 2 Choose: which commits the client wants.
  • 3 Find: bitmaps say which objects to send. Enumerating objects
  • 4 Build and send: one pack file, mostly copied from the server's stored packs. Counting objects Compressing objects pack-reused
  • 5 Check and unpack: your machine names and checks every object. Receiving objects Resolving deltas