In git every file, every directory and every commit is an object, and its name is the SHA-1 hash of its own content: the same value serves as identifier and as checksum. It is an architectural choice, and it changes how a project’s history is stored, verified and exchanged between machines.

I am writing a few weeks after the tool’s first public commit (e83c516, 7 April 2005, message “the information manager from hell”). git is still a raw set of low-level commands, not a finished version control system. Its storage model is worth a look all the same, because it is the part that will stay put even as the interface changes.

Context

For years the Linux kernel was coordinated with BitKeeper, a proprietary distributed version control system given to the community for free use. In April 2005 that grant fell through: from 1 July, anyone wanting BitKeeper has to pay for the commercial edition. Linus Torvalds, who handles kernel integration, was left without the tool the workflow of hundreds of developers rested on.

The free alternatives already to hand — CVS, Subversion — are centralised: a single server holds the complete history, clients keep a working copy. Torvalds also tried monotone, a distributed system that already named revisions by cryptographic hash, but for the kernel’s size he found it too slow (tens of thousands of files, a history years long). Hence the choice to write his own tool from scratch, tuned to the kernel’s use case before any concern for generality.

Architecture

git does not store the differences between versions. It stores snapshots. The store holds four object types:

  • blob — the raw content of a file, with no name or metadata;
  • tree — the list of entries in a directory, each with mode, name and the hash of the child blob or tree;
  • commit — a pointer to a tree (the full state of the tree at that moment), plus author, date, message and a reference to one or more parent commits;
  • tag — a named reference to another object.

Each object is compressed, prefixed with a header carrying type and length, and the whole is run through SHA-1. The first two hex characters of the hash name a directory under .git/objects, the other thirty-eight the file. Retrieving an object therefore needs its hash: the store is content-addressed.

Two properties follow from this, direct consequences of the model rather than later additions.

The first is automatic deduplication. Two files with the same content, in two different commits, give the same hash, hence the same blob, stored once. A commit that touches three files out of ten thousand creates three new blobs, the trees along the changed path and one commit; the rest of the tree stays shared by reference with the previous commit.

The second is verifiable integrity. An object’s name is its checksum. The hash of a commit takes in the hash of its tree, which takes in the hashes of its blobs and sub-trees, which in turn depend on the content. The hash of a commit also takes in those of its parents. The history thus becomes a chain of hashes: a commit’s name depends, all the way down, on every byte of every file and every commit before it. It is the structure of a Merkle tree.

The critical point

That chain of hashes turns the history into a directed acyclic graph (DAG) of commits, and it is the DAG that keeps the distributed model coherent. There is no central authority handing out sequential revision numbers: two developers working out of each other’s sight produce independent commits, and when they merge them git finds the common ancestor by walking back the parent pointers, then does a three-way merge. A branch is a forty-byte file holding a commit’s hash, not a copy of the tree. Creating it, moving it, deleting it costs as much as writing that file.

All of this rests, though, on the collision resistance of SHA-1. If two different contents produced the same hash, git could not tell them apart: the store would keep the first and throw away the second believing it identical, and the integrity of the chain would give way at the very point it is founded on. In practice the function is taken as sound today, but not without reservations. In February 2005 Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu described a collision attack on full SHA-1 with an estimated cost below 2⁶⁹ operations, against the 2⁸⁰ of a brute-force search. It is a theoretical result, out of practical reach today: nobody has yet exhibited a real collision. But it says the function’s security margin is narrower than was thought, and for a system that ties its very notion of object identity to that function it is a dependency to watch.

Implications

With a content-addressed store, clone is defined in one line: copy every object reachable from a reference. The result is a complete repository, with the whole history, independent of its origin. Between “server” and “client” there is no architectural difference: there are repositories, and some exchange objects with others. A commit made locally is a commit in full, immutable from the instant it exists, whether or not it is ever published.

This changes where the cost of distributed work falls. To verify integrity you need trust neither the transport channel nor the source repository: recomputing the hashes is enough to know whether the objects received are the ones expected. Once written, history cannot be altered quietly, because altering it would change the downstream hashes.

Limits

git today is awkward. The interface is a set of low-level commands — what people are already starting to call the plumbing — made to be combined in scripts, not driven by hand. Friendlier layers are growing around the core: Petr Baudis is building Cogito on top of these commands. The storage model described here is solid; the ergonomics built over it are still to be written, and will change more than once.

There is also a cost the snapshot model carries with it: every repository holds the whole history. For projects with large binary files or very long histories, “every clone is complete” stops being only an advantage. It is the price of distributed verifiability, and it is paid in full.

https://lkml.org/lkml/2005/4/6/121 https://www.kernel.org/pub/software/scm/git/docs/ https://www.bitkeeper.com/ https://venge.net/monotone/ https://www.iacr.org/archive/crypto2005/36210017/36210017.pdf https://www.noze.it/en/insights/git-open-source/

Cover image: Linus Torvalds, a man wearing glasses and a light shirt, photographed at a Linux conference in 2003 — photo by Alex Dawson, CC BY-SA 2.0 — https://commons.wikimedia.org/wiki/File:Linus_Torvalds,_2002,_Australian_Linux_conference.jpg