Git’s database internals I: packed object store
github.blog
github.blog
> Git does not currently have the capability to update a packfile in real time without shutting down concurrent reads from that file. Such a change could be possible, but it would require updating Git’s storage significantly. I think this is one area where a database expert could contribute to the Git project in really interesting ways.
I'm not sure it would be super useful, because of the delta-ification process. Adding "literal" (non-delta) files to a pack isn't much of a gain (file contents are zlib-compressed either way).
Decoding the pack files was notoriously difficult, probably there are still cases that I don't handle properly. The packfile is a really complex/messy format and in the top of that it lacks any proper documentation!
This article explains a lot of the concepts very good but doesn't go into implementation details (where the big snakes are). Another great resource for unpacking packfiles is this post: https://codewords.recurse.com/issues/three/unpacking-git-pac... and of course reading the source code of other git clients.
Unfortunately it seems that the official packfile format documentation is the git source code :|
Maybe it’s changed since you'd checked it, but I found the pack files to be documented, through nowhere near as well as index files (now that was a pleasure, the index file format is straightforward, pretty logical, and very well documented).
The problem I had with the pack files documentation is that it’s non-linear, so if you read it linearly as you implement it you hit areas which turn out to be documented a few screens later. Furthermore it doesn’t necessarily define or spell out what it’s talking about, so it can take a while to realise that it has 3 (.5?) different formats of varints, or that the size it provides is for decompressed content, and that it relies on zlib to discover the end of the compressed stream (and good luck to you if your implementation doesn’t expose that).
But in my experience, it’s really nothing compared to the documentation of the wire format. That leaves even more details out, some of the explanations are outright misleading (I spent hours convinced the v2 protocol was using an HTTP connection as a half-duplex socket and wondering how I would manage), and with TODOs covering half the protocol.
I also used gitoxide’s source when I got unsure / lost about the nomenclature / varints.
I’d suggest giving it a pass unless you have to or are really interested though.
I wrote the 9front implementation (https://git.9front.org/plan9front/plan9front/HEAD/sys/src/cm...) more or less entirely from the official documentation in the git repo. For debugging, GIT_TRACE_PACKET=1 is very useful for getting valid packet traces.
Repacking efficiently for serving is the most annoying part, and I still haven't implemented delta reuse.
The pack format docs were one of the documents affected, it now lives at https://github.com/git/git/blob/master/Documentation/gitform....
I work on concurrent editing systems (using CRDTs). People always ask about how we deal with the problem that if we store changes forever, the filesize grows indefinitely. Modern CRDTs are massively more space efficient than git but nobody seems to notice or care about the size of our git repositories. I think git supports shallow clones but I don’t know anyone who bothers with them.
That's not true; otherwise each git branch folder would be huge, but it's not. It stores the snapshot of changes in branch folders
No, gp is right. There is no snapshot of changes. Each unique version of a file is an object in the object store. That does mean each commit would only introduce new objects for files that have changed (these are already added to the object store when you use `git add`) .
But the pack files like the article explains (which are created regularly during gc/maintenance runs) is why the repo size can often be smaller then the working tree.
> Not only is each object compressed individually, they can also be compressed against each other to take advantage of common data.
[0] https://github.blog/2022-08-29-gits-database-internals-i-pac...
The actual model of git internals is that every commit always stores full copies (of modified entries, unmodified entries are dedup'd through the magic of content addressing).
Then as an optimisation of the packing process git will perform delta compression between objects based on a bunch of heuristics. Until you pack you get full copies, and depending how "hard" you pack you may or may not gets huge savings.
Furthermore, Git's pack files are ordered, so depending on the selection it makes it can diff later files from earlier ones (your model) or the reverse, or even both at the same time.
You can see some of the early packing heuristics at https://github.com/git/git/blob/master/Documentation/technic...
As far as the actual internals are concerned, yes. But as a model it's not wrong. It's like epicycles aren't wrong as a model either. GP's mental model of Git is mine as well, and it works very well for me.
As a model it's wrong, and useless, and possibly harmful.
Because the "states are captured as diffs" model does not tell you anything true that's useful. And at worst it gives you incorrect ideas of the performance characteristics of the system e.g. that small changes are bad, because lots of changes means lots of diffs to apply which is slow.
By forgetting that model, you're strictly less wrong, and helped no less about reasoning about git.
> It's like epicycles aren't wrong as a model either.
But they were. "Adding epicycles" has literally become a saying about trying to pile on more crap to try and (fail to) make an incorrect model work.
And epicycles were at least trying to keep a simple model working, the "snapshot model" is more complicated than git's actual behaviour to start with.
them: harmful
me: how?
them: really harmful
me: sure, but, can you explain it?
them: like a bajillion harmfulIt's no more wrong than epicycles. It's not useless either: it works very well for me. For users (as opposed to Git developers), it's hard to see how it could be harmful.
Systems like CVS or Subversion indeed store diffs of file conceptually and storage wise. This has notable co sequences: when doing operations on a large span of revisions all takes long as a bunch of diffs have to be applied in sequence. This then leads to reluctance of small commits for the wrong reasons.
Wrong assumptions about the workings leading to wrong decisions is harmful.
This happens in Git as well though. If you have to rebase your commits across a few thousand upstream commits, you'll be in for some pain. (For example, I've a commit to PostgreSQL to add ALWAYS DEFERRED constraints, and I've had to rebase it across thousands of upstream commits because I've lacked the time to see that contribution across the finish line.)
You seem to be indirectly arguing for merge-based workflows. (At least that's what I'm reading between the lines. Perhaps my reading is wrong, but I'll run with it until you tell me otherwise.) However, a) merging is not always accepted by upstream, and b) merge-based workflows suck.
I grant that merging is very simple with Git's internals: Git does the three-way merge thing, you manually merge conflicts, you create a commit for the conflict-resolved checked out state, recording the two parents in that commit, and you're done. This works because Git simply stores the objects as they are, internally using deltas -not quite diffs- to compress the object store. This is very simple, yes, but it yields a workflow that doesn't work for many projects. Rebasing is much better, and it always works, especially with [0].
So now you might wonder how to deal with the rebase-across-thousands-of-commits problem. Well, I've a script[0] (not originally mine, but I've hacked on it) that does something like bisection to find upstream commits causing conflicts so as to greatly speed up the process.
[0] https://gist.github.com/nicowilliams/ea2fa2b445c2db50d2ee650...
However rebase is a single special operation. The diff-based storage affects all. From updating a local repository from upstream, diffing between some distance, ...
No one is saying Git does or should do that.
> If you got to rebase over many decisions you are likely in trouble anyways.
That script I linked made it easy.
> There small commits can be helpful to ease dealing with merge conflicts.
They were indeed mostly small commits. Mine wasn't that small -- it's fairly invasive and not possible to split up into more than two commits.
Delta compression is just an implementation detail for storage optimization. Conceptually each commit is an immutable snapshot in its own right.
That tends to lead to a merge-centric workflow.
The alternative makes it easy to understand rebase. Ergo it's good.
If commits were diffs, then that process doesn't make any sense. It only makes sense when you think of commits as snapshots, and cherry-pick ing as taking a commit, calculating the diff with the current commit, and then applying that diff to make a brand new commit.
> If commits were diffs, then that process doesn't make any sense. It only makes sense when you think of commits as snapshots, and cherry-pick ing as taking a commit, calculating the diff with the current commit, and then applying that diff to make a brand new commit.
Sure it does. It works for me. You can use whatever mental model of Git that you works for you.
Commits in your .git directory aren’t stored using deltas from a previous commit. Each different version of every file is stored in full.
> You have two nearly identical 22K objects on your disk (each compressed to approximately 7K). Wouldn’t it be nice if Git could store one of them in full but then the second object only as the delta between it and the first?
> It turns out that it can. The initial format in which Git saves objects on disk is called a “loose” object format. However, occasionally Git packs up several of these objects into a single binary file called a “packfile” in order to save space and be more efficient.
...
> What is also interesting is that the second version of the file is the one that is stored intact, whereas the original version is stored as a delta — this is because you’re most likely to need faster access to the most recent version of the file.
So thinking in those terms for modelling / visualising git's behaviour is nonsensical.
josephg said:
> Each different version of every file is stored in full.
which is an untrue statement about how git internally manages its data. It would be fine had they instead said:
> From the user's point of view, it's as if each different version of every file is stored in full. Internally, git may perform compression, including differential compression.
This isn't the first time I've seen this confusion. This 2014 StackOverflow thread [0] does the same, as does an old HN thread. [1] The solution is clear communication.
The simplified model that leaves out tricky implementation details is just "every file that's different is a different blob object, stored in full on its own, under the hash of its contents". If you work with this model, you're basically correct in all your reasoning, except that in reality a bit less storage is used because some objects get packed. If you work with the wrong (wrong! not simplified, wrong!) model "every blob object is stored as base-and-deltas", you won't reason correctly about either how the object store presents itself in plumbing commands or how it's stored.
I never said that Git commits are diffs. Keep it civil.
> The simplified model that leaves out tricky implementation details [...]
Models do that.
> If you work with this model, you're basically correct in all your reasoning, except that in reality a bit less storage is used because some objects get packed.
That's it? That's the one detail that should stop me thinking correctly based on this model?
FWIW it's closer to lossless compression e.g. LZ77's behaviour: git's delta compression has two commands which are LITERAL and COPY, and technically it doesn't need to copy linearly from the base object, it would be unlikely[0] but a delta could start by COPY-ing the end of the base object, then add literal data, then COPY the start of the base object (or COPY the end again, or whatever, you get the point).
[0] outside of handcrafting, as the packing process would need to find such a situation which it would estimate useful
I was too lazy to implement the diffing algorithm, so I used the suffixarray from the go standard library and greedily grabbed the longest match at each point in the input. It's been a while, but I think I got a 12% improvement on my test case. (Probably wouldn't do that well in general.)
I'm assumed the git code just runs off of a diff (longest common substring), but I never checked.
"How does git deal with the problem that if we store changes forever, the file size grows indefinitely?"
Even though Git uses deltas for diffs to reduce space usage, it still technically grows indefinitely, same as CRDTs. So the answer is it doesn't, and it doesn't matter.
If the size of something actually becomes a problem, -then- it can be handled (e.g. Git LFS).
With CRDTs, depending on what you're doing, it might never become a problem. Keeping all versions of a document is entirely inconsequential, as an example. The size might grow indefinitely but how many edits is a document going to have, realistically?
[0] https://github.com/CocoaPods/CocoaPods/issues/4989#issuecomm...
git does store diffs. People are confusing the logical representation with the on-disk layout.
The packing process explained in the article is why: rather than make compression an intrinsic part of the system's model (which most VCS do / have done), git moves it to a later "optimisation" phase. This is an additional and somewhat odd costs, but on the other hand it can be extremely efficient (at $DAYJOB we've got files whose compression ratio is 99%).
An other interesting bit (which makes it very annoying to inspect the raw contents of a git repo) is that git DEFLATEs object contents when it stores them on-disk. But while that's clearly documented for packfiles (although the lack of end-of-data marker is implicit and extremely annoying), it's not really spelled out for loose object, you get to find out when you can't make heads or tails of loose objects, and git barfs at your hand-crafted loose objects.
1: https://github.com/vaibhavsagar/duffer/blob/bad9c6c6cf09f717...
2: https://vaibhavsagar.com/blog/2017/08/13/i-haskell-a-git/
I guess that would be performance-wise the same as switching from running the compiler in a one-off mode to a LSP analyzer.
I really wish git wasn't using them.