WAL Git
A few days ago I read Git at any scale. Although I managed to follow the architecture and the ideas behind it, I couldn’t stop thinking about how difficult it would be to come up with a solution like this one.
Whenever I come across an interesting article like this one, I need to understand it better. And the only way that works for me is implementing it and writing about the process. I have followed this method a few times already.
If you’ve already read the original article and understood the concepts behind it, feel free to skip this post. It adds no new ideas, only the real requests and objects behind them.
The Prompt
These days there is always a prompt.
I have never shared this approach before, but this is how I work now. Instead of building everything from scratch and spending a lot of time on stitching everything together, I ask the following to my trusted LLM:
Hey Claude, I have read this blog: https://cursor.com/blog/git-at-any-scale. I think I have followed it properly but I want to reproduce what they describe in there. I think the best way to learn everything is to you to prepare something like a coding interview where I have to implement some functions and fill the blanks. It’ll be ideal if at any point I can run some tests or even run a real git command to see how things start working together.
The most interesting parts to me are how the WAL and the CAS work with S3 but also the compaction algorithm implementation. What do you think? Can you prepare something?
The output was perfect. I just had to go through the code and fill in the blanks.1
The generated tests are the perfect example of our starting point and how the programming exercises are organized.
Permissions Size User Date Modified Name
.rw-r--r-- 5.7k jordi 29 Aug 10:17 conftest.py
.rw-r--r-- 3.2k jordi 29 Aug 10:18 test_00_preflight.py
.rw-r--r-- 4.6k jordi 30 Aug 12:20 test_01_objects.py
.rw-r--r-- 8.7k jordi 29 Aug 10:19 test_02_wal.py
.rw-r--r-- 9.4k jordi 29 Aug 10:20 test_03_compaction.py
.rw-r--r-- 6.5k jordi 29 Aug 10:22 test_04_serve.pyThe objects module is just an interface to interact with S3, nothing super interesting for our purposes but still nice to go through it. Especially these days, when we don’t write much code anymore.
Let’s first try to understand how things are put together by looking at how the push process works.
The Push
A walgit node is split in two: processes and a local cache on the node, and the repository itself in S3. This is how a push moves between them:
walgit.lock. Everything inside the dashed box is a cache, and can be deleted without losing a single commit. The bucket is the repository.I call the node’s local copy of the repository the “warm cache”. It’s no more than a local copy, but it acts as a cache: the ground truth lives on S3, and the copy can be regenerated from it whenever needed.
To understand what happens during a push, let’s use an example where one or more commits are pushed to a repository with git push http://.../<repo> main.
This is what the person pushing sees:
git push http://.../<repo> main
Enumerating objects: 3, done.
Counting objects: 100% (3/3), done.
Writing objects: 100% (3/3), 206 bytes | 206.00 KiB/s, done.
Total 3 (delta 0), reused 0 (delta 0), pack-reused 0 (from 0)
remote: walgit: seq=3 entry=543d651c6f7a pack=sha256:71972b034287 261B index-version=3
To http://.../<repo>
9965c5c..4e5911a main -> mainThe git client makes two calls to the server:
GET /<repo>/info/refs?service=git-receive-pack
No body. Git sends this on every push to get the repository’s refs before pushing any data.
| # | Who | What happens |
|---|---|---|
| 1 | server.py |
Calls |
| 2 |
|
Is called with the
|
| 3 | git http-backend |
Prints the response to stdout. |
| 4 | server.py |
Turns the output into an HTTP response: |
Then comes the real push.
POST /<repo>/git-receive-pack
| # | Who | What happens |
|---|---|---|
| 1 | git |
Sends the ref update, then a packfile. |
| 2 | server.py |
Takes the |
| 3 | server.py |
Calls |
| 4 | git http-backend |
Is called with the
|
| 5 | git http-backend |
Starts |
| 6 | pre-receive |
Reads one line on stdin containing the ref update. |
| 7 | pre-receive |
Also finds the packfile inside the quarantine directory. |
| 8 | pre-receive |
Proceeds to update the WAL (more details). |
| 9 | git |
Moves the quarantined objects into the repository and updates |
| 10 | post-receive |
Repoints HEAD and records the new ETag into |
| 11 | git http-backend |
Prints the response to stdout. |
| 12 | server.py |
Turns the output into an HTTP response: |
The part I had the most trouble understanding was how the server interacts with the client. But once you understand how git http-backend and the hooks work, everything starts to make sense. It’s a clever trick that allows the server to act as a proxy without needing to implement a custom server that speaks the Git protocol.
The most important part after seeing how everything is wired together is of course the WAL, the central idea behind Cursor’s post.
The WAL
The WAL (Write-Ahead Log) is formed by three different objects in S3: the packfile, the entry, and the index. Only the latter is mutable, and it’s the one that makes the other two visible.
Writing a pack or an entry changes nothing observable. They sit in the bucket, correct and unreferenced, and no reader has any way to find them. The visibility is managed in a single place, a pointer appearing inside index.json. That’s why the only operation that needs to be atomic is a single small PUT to that file. S3 makes it atomic with a conditional write, a compare-and-swap (CAS): the PUT only succeeds if the index still has the ETag you read.
index → entry → pack reachable. If something fails between 2 and 3, the first two writes are just garbage the garbage collector (GC) will clean later.Let’s follow the same approach we have taken while analyzing the push. Once the pre-receive hook is triggered and detects a packfile, it follows these steps:
| # | Who | What happens |
|---|---|---|
| 1 | pre-receive |
Puts the pack to S3
|
| 2 | pre-receive |
Puts the entry to S3
|
| 3 | pre-receive |
Gets the index object from S3. |
| 4 | pre-receive |
Calls |
| 5 | pre-receive |
Puts the index object to S3. |
| 6 | post-receive |
Records the new index ETag in |
The index will look like this after the push:
// repos/<repo>/index.json, ETag: "a0ef3e595968827261a3dbfb659e4183"
{
"repo_id": "<repo>",
"version": 3,
"next_seq": 4,
"base": null,
"entries": [
// seq 1 and 2, from earlier pushes
{
"seq": 3,
"entry_id": "543d651c6f7a4cb185ec39e39bf1dc42",
"key": "repos/<repo>/wal/543d651c6f7a4cb185ec39e39bf1dc42.json",
"pack": "sha256:71972b0342872cb8e0cf3d7587c37270339950a5fbca645acdac5cec5278b7f6",
"pack_size": 261
}
],
"refs": { "refs/heads/main": "4e5911a3f5c75f56ef21ab108a638e6f20337514" }
}As always, this is the happy path. When updating the WAL we can find two main errors:
CasConflict: The index.json has been modified by another process, and ETag doesn’t match anymore. We need to re-download the index, apply the changes, and upload it again.RefConflict: The ref has been moved to a value the client didn’t anticipate. We can’t recover from this, so we need to fail. The client can then fetch, rebase, and push again.
It’s easier to understand with an example. Imagine two walgit nodes serving two different clients. Both read the same ETag and both push to refs/heads/main. The loser hits both conflicts on the way down.
CasConflict after losing isn't the interesting part. The re-validation after it is. B's retry re-runs apply_push against the new index, discovers that main is no longer pointing to the expected commit, and stops. Without that second check B would append happily and A's commit would vanish.Note that files uploaded by node B are left behind. They are not a problem since they are not visible to anybody. They will be cleaned up by the garbage collector.
You might be wondering why retry after a CasConflict at all if it ends in a RefConflict. The case here is that both nodes were trying to apply changes on the same ref (main), but if one had been pushing to main and the other to a feature branch, the retry would have succeeded.
It’d look something like this:
CasConflict still happens, but when B's retry re-runs apply_push against the new index, the ref it updates hasn't moved, so its second compare-and-swap succeeds with seq=4.Now that we understand how the WAL works and how it’s updated while being durable and consistent, let’s dive into the other key part of the described solution, the sync process.
The Sync
The sync process is responsible for rebuilding the repository from the WAL and the files stored in S3. Without it, the repository would be either centralized in a single node or distributed without any consistency and synchronization.
index.json, and only once every pack is in (5). walgit never writes into objects/pack itself: git does, and git decides the file names.Back to the original push: its first request, the GET info/refs from the push, makes server.py call sync(). When the node has no warm cache, it must rebuild the repository entirely from the WAL.
| # | Who | What happens |
|---|---|---|
| 1 | server.py |
Runs |
| 2 | server.py |
Makes sure the hooks ( |
| 3 | server.py |
Loads |
| 4 | server.py |
Gets
|
| 5 | server.py |
The index lists two packs and ref main to
|
| 6 | server.py |
Creates a temporary directory to store the packfiles. |
| 7 | server.py |
Gets object
|
| 8 | git index-pack |
Indexes the pack into the warm cache. |
| 9 | server.py |
Same with the second pack. |
| 10 | server.py |
Temporary folder gets removed. |
| 11 | git update-ref |
Points |
| 12 | git symbolic-ref |
Points |
| 13 | server.py |
Writes to |
Once you have the warm cache, checking for updates is a single conditional GET: the node asks for index.json with If-None-Match set to the ETag it stored in walgit-state.json. A 304 means nothing changed, so it serves straight from disk. A 200 means someone pushed, so it downloads the missing packs, moves the refs, and saves the new ETag.
Closing Remarks
After reading Cursor’s post I thought I understood it. Implementing it showed me what I had missed: how git http-backend and the hooks let a plain HTTP server take pushes, and why a CasConflict is worth retrying while a RefConflict is not.
The whole design fits in two ideas. The bucket is the repository, and nodes are caches that can disappear at any moment. And every push is ordered by one conditional PUT on one small JSON object. Everything else is arranged so that losing that race is cheap.
There are a few things pending before I can call this project done. But they are secondary and won’t add much value to understanding how the general approach works. I leave the compaction and other mechanisms as something to be implemented later.
The code is on GitHub if you want to try the exercises yourself.
Footnotes
-
Models evolve fast. Last time I followed this approach the output was a project with blanks to be filled. This time the model generated a fully functional version, a green test suite, removed some parts that I will need to implement myself with a guided approach, and a tool to peek into the working solution if I’m stuck. See the initial version. ↩
-
A program that ships with
gitand speaks CGI. It felt like ancient technology to me, so here’s how it works: for each request,server.pystarts it, describes the request in environment variables, pipes the body to its stdin, and forwards whatever it prints. It readsPATH_INFOto get the repository and the service, and runs git’s server program on that directory. ↩