But still, I can’t reason about how so many changes to a repo can be recorded in a way that’s so efficient that it’s almost imperceptible in time cost. And I’ve yet to see a satisfactory answer to this question. I need concrete examples.
With this foundation, Git is already quite efficient in common scenarios since most commits create only a few new objects: the commit, the new versions of the files, and all directory nodes all the way to the top.
Git could store all of these in the filesystem. Often, they are stored in indexed and compressed pack files though. But the underlying principle remains the same.
When you ask git for a diff it compares the trees and when there is a difference it compares the files the trees reference and it shows you a diff.
Git does not store diffs, it stores file trees.
git add . && git commit -m wip
This is basically the speed of
find .
Then it takes all that metadata, comine it to one, add it to a commit message and it's done.
Doesn't take a lot of time to do these things, but it will for very large files.
Going the other direction is fast, reverse lookup all that metadata and copy the contents back into the working directory
Git logically stores file contents as blobs in essentially a key-value store. However, the physical storage writes many objects into a single "packfile", and for each object it uses heuristics to look for "likely similar" object candidates already in the packfile, computes deltas based on them, choosing the smallest possible delta or falling back to storing the object as-is if it can't find a good candidate.
Start with a filesystem like this. They all have a root object with an id that is pointing to a tree. The tree is (name, type, pointer to data):
root object 1:
dir1 directory 2
dir2 directory 3
file1 file 4
file2 file 5
What it stores is the following:
root object 6:
dir1 directory 2
dir2 directory 3
file1 file 7
file2 file 5
1. The new root object, which is a bunch of pointers
2. the new file data
That is very fast to store, and very efficient to store and retrieve. It is not slower to access old data vs new data.
The data is all immutable, all you are storing is pointers to which data is named what.
If you had a file in dir1 instead, you would update the root object and dir1. dir2 would be untouched, so you would still store ... just as much as above.
This is how git works at a high level.
In practice, most commits change a small number of files. So you will update the root object, and all the directory objects on the way to your new file, but that's it.
Most source code trees are lets say 10 directories deep max? So even if you have a thousand directories, you are updating only the directory objects that are parents of your file's path. So maybe 10 directory objects get updated. All others are untouched.
So O(10) changed directory objects to store, plus the root object, plus the new file data. Everything else is reused.
This is very fast.
The worst case for something like the above is where you change a file in every directory. It will then have to rewrite every directory object, even for small file changes.
Or you have flat directories with huge numbers of small files. You then pay the cost of rewriting the directory objects all the time.
But for most source code layouts, the above works very fast.
Even without compression, the total space usage of your repo is O(total amount of changed data) rather than O(total amount of data represented by all root objects)
1 million revisions of kernel, at 4gig of data each, would be 4PB if you were storing complete copies at every revision.
Instead it's like 9 gigabytes or something, total.
It's because git does heavy deduplication, in the same way that functional, persistent data structures do heavy deduplication.
For example, if you have a tree data structure and one tree (let's call it tree 1) like this
A
/ \
C B
A
/ \
B D
A_tree_1
/ \
C B
A_tree_2
/ \
B D
A_tree_1 A_tree_2
/ \ / \
/ \ / \
/ \ / \
C B D
(But note that the "spine" of the tree - the path from the possibly deduplicated subtrees until the root - will not itself be deduplicated. That is, even if A is identical between tree 1 and tree 2, you still need different A_tree_1 and A_tree_2, because one of them contains pointers to C and B, and the other contains pointers to B and D)
That's how persistent data structures work in functional programming (for example, in Haskell, if you are careful with sharing you can have two different trees share a subtree rather than making a deep copy them, lowering the memory usage)
And that's how objects in git work (which include commits, filesystem trees, and file contents, that are called blobs). Two different objects that share subtrees will also share storage. That's not a diff, that's just how things are stored in Git. But ultimately, whenever you need to diff, you only need to consider the diff between C and D; B is common between A_tree_1 and A_tree_2 and doesn't need to be diffed.
And the reason this works is that in Git, objects are immutable: you don't modify an existing commit when you do git commit --amend for example, you create an entirely new commit (and the old commit is still in the repository, until you run git gc to get rid of it - but it probably occupies almost no space, because its filesystem tree is probably quite similar to the other commit)
(That's how it works in functional programming too: persistent data structures are commonly used there because in functional programming, you don't modify existing trees, you create new ones whenever you want to do a "functional update"; but you deduplicate the trees so that this update can still be somewhat efficient)
And the mechanism this deduplication is implemented in Git is content addressing: every object is identified by a sha1 hash of its contents, and every time you try to store an object with a given sha1 hash, git will first verify if this object already exist and if so, it will reuse the existing object.
(This means that a "pointer" to a subtree, in git, is just its sha1 hash. So the reason that A_tree_1 and A_tree_2, in Git, need to be different objects, is that inside them there are different hashes: one has C and B, and the other, B and D)
(Deduplication in Haskell's data structures wouldn't use content addressing, but instead you manually tell that a given tree will be built with a subtree from another tree, and then it just works because no tree can be modified)
Note: content addressing is also how deduplication in filesystems like btrfs work. In those filesystems, the kernel will hash a piece of a file (an extent) and check in a hash table whether that particular extent is already stored somewhere. If yes, you don't need to store again. (you can disable online deduplication too, and do it offline, with a batch job)