codient/blog

How git clone works · part 1

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.

I've run the git clone command hundreds, if not thousands of times. But I never knew what any of these lines meant.

So I asked Claude to help me understand how git clone works under the hood. Turns out, cloning a repo is quite complex under the hood.

This post covers the first line of the git clone output (how the server enumerates objects). When I started diving deeper into it, I had no idea what it meant. If you are in the same boat as me, this post should be helpful to you. By the end of it, you will know how the client (your computer) interacts with the remote git server. And how the git server can serves clones for really large repositories fast.

I also recorded a video explaining these concepts if that is more of your jam.

Two computers

Every clone involves two computers. The client is your machine, the one asking for a repo. The server holds the repository.

In the output above, the lines that start with remote: come from the server.

Check yourself
Which computer printed “Counting objects”?

How your repository is stored on the server

The server doesn't keep a folder of files like the one on your laptop. It keeps git's objects.

I'll use a tiny repository to explain: four commits, c1 to c4, and two files, readme.md and app.py.

Git has three kinds of objects:

Git names every object by its hash, a fingerprint of what's inside. Change one byte and the name changes.

c2 changed app.py. c3 changed the readme. c4 changed app.py again. That's 13 objects: 4 commits, 4 trees, 5 blobs (2 versions of the readme and 3 versions of app.py).

The tiny repository
Click any object to see its real hash and what it points to.
Click c4 to start.

So then what does cloning do? It copies all 13 objects from the server to your machine.

Check yourself
c3 only changed the readme. Which new objects did c3 add?
What gives an object its name?

Five steps

Each git clone is broken down into 5 steps:

  1. Ask: the client asks the server what branches do you have? the server responds with the branch refs.
  2. Choose: the client says which commits it wants based on the earlier response.
  3. Find: the server works out every object those commits need.
  4. Build and send: the server puts them all in one file.
  5. Check and unpack: the client checks every object and writes out your files.

We will cover steps 1, 2 and 3 in this post.

Steps 1 and 2: the conversation

The client connects and asks what the server has. The server answers with its branches: main is at 3d027221, which is c4. A branch is just a name pointing at a commit.

Then the client says want 3d027221, and done. That's the whole order.

This is the real conversation, trimmed, with our tiny repo's hash. Run GIT_TRACE_PACKET=1 git clone … and you'll see it too.

The clone conversation
Step through it one message at a time.

One thing to note: the client always tells the server what commits it wants. The server takes that figures out which objects it needs to send back.

Check yourself
In step 2, what does the client send?

Step 3: find, by walking

All of the commits in Git are a DAG. The simplest way to find objects that belong to a particular commit is to walk the graph.

For example, in our simple repo to find all objects for c4, the steps would be:

Open c4. Inside are two hashes: its tree and its parent, c3. Open the tree, and add the readme and app.py to the list.

Follow the parent to c3 and open its tree. Its readme is the same one c4 has, already on the list, so skip it. Its app.py is older, so add it.

Keep going until c1, which has no parent. The walk ends at 13.

Walk the graph
Each click opens one object. Watch the list grow, and watch what gets skipped.
The walk starts at c4, the commit the client asked for.

For 13 objects, that's instant. The walk grows with the history.

Check yourself
Why does the walk skip the readme in c3's tree?
What makes the walk slow on a big repository?

At real size

Git's own repository has 424,727 objects and 83,045 commits. Walking the whole graph took 3.4 seconds on my laptop.

When the next person clones, the server walks it all again.

Bitmaps

As repositories get bigger, walking the whole graph doesn't scale.

The fix: do the walk once, and save the answer.

Give every object a number: the order it sits in the server's storage file. Then, for c4, write a row with one box per object: 1 if c4 needs it, 0 if it doesn't. That row is a bitmap. The server builds it ahead of time.

Now a clone of c4 is: read the row, send every 1. No walk.

One bitmap per commit
The objects in the order the server stores them. Pick a commit to see its row.

Reading the bitmap for git's own repo took 0.1s (compared to 3.4s to walk the whole graph).

One catch. Building bitmaps is computationally intensive. So the server only builds bitmaps every so often, not on every push, so a brand new commit has none.

For that commit, the server walks back until it hits a commit that has one, and reads that bitmap for the rest.

Check yourself
What does one box in c4's bitmap say?
You push c5 and someone clones it right away. What does the server do?

Pulling

Most of us run git pull way more often. Under the hood, it works almost the same way as a clone.

But there is one big difference. You already have most of the repo's history.

So the client adds one line: want c4, have c2. The server confirms it has c2 too, and sends only the difference.

Without bitmaps, it would walk both and compare. With them, it compares two rows: send what c4 needs and c2 doesn't.

A pull, as two rows
First guess: a pull from c2 to c4, how many of the 13 objects does it send?

From c2 to c4 it's six: c3, c4, their two trees, the new readme, the new app.py.

Check yourself
A pull says want c3, have c1. How many objects does it send?

Back to the first line

Your machine asked for one commit. The server then turned it into a list of objects.

That's the first line of the output. Enumerating objects.

The rest, counting, compressing, pack-reused, receiving and resolving deltas, is about building that one file and checking it. That's part 2.

Check yourself
Which output line is step 3?