Git’s database internals I: packed object store

https://github.blog/2022-08-29-gits-database-internals-i-packed-object-store/

by todsacerdoti • 4 years ago

216 64 4 years ago

josephg2• 4 years ago

One of the things that surprises me about Git is that it doesn’t store diffs. It just stores the full content of every file every time it’s modified and committed.

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.

mandeepj• 4 years ago

It just stores the full content of every file every time it’s modified and committed.

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

thro388• 4 years ago

Maybe OP stores binary files?

_ikke_• 4 years ago

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.

CorrectHorseBat• 4 years ago

Branches are just pointers to commits in Git. How those commits are stored doesn't affect their size.

tomstuart• 4 years ago

I know what you mean, but — as the article explains [0] — Git’s packfile format uses delta compression, which is essentially “storing diffs”.

[0] https://github.blog/2022-08-29-gits-database-internals-i-pac...

srvmshr• 4 years ago

In my mental model of git internals: I envision the initial commit stores a full copy in object store - and thereafter the states are captured as diffs. If a new file is added at a later commit stage, of course the "blob" will be stored, but subsequent commits will add the deltas to it - not a full copy.

masklinn10• 4 years ago

Git’s packfile format uses delta compression, which is essentially “storing diffs”.

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

pocketarc• 4 years ago

It's a reminder that sometimes it's OK to ignore hypothetical problems.

"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?

MonkeyMalarky• 4 years ago

I have used shallow clones to speed up and shrink what gets pulled into a docker image when building it. Of course it was a hack to make up for past mistakes but I was glad the option was available.

masklinn10• 4 years ago

Did you need to update the docker image in-place afterwards? Unless you did, why not just export?

Existenceblinks• 4 years ago

It kinda store diff in `rr-cache/` the preimage | postimage | thisimage combined is a kind of diff.

Nzen• 4 years ago

Ah, thanks. You've reminded me about the 2016 debacle [0] wherein github rate limited the cocoapods repository because their practice of using a shallow clone and later fetches impacted github's performance. I'm going to warc that now, so I don't forget again.

[0] https://github.com/CocoaPods/CocoaPods/issues/4989#issuecomm...

[+] https://github.com/orgs/Homebrew/discussions/225

giancarlostoro• 4 years ago

It's easy to forget that code is... so small, but I guess if your codebase on its own was hundreds of megabytes big, then that would become noticed more quickly. I never realized it stored a copy every time, I assumed it used diffs. So git uses the same solution some of us use when we're about to do something on git we're unfamiliar with... you copy the entire directory housing your code + git repo into a new location just in case it fails miserably.

NavinF• 4 years ago

I never realized it stored a copy every time, I assumed it used diffs

git does store diffs. People are confusing the logical representation with the on-disk layout.

masklinn10• 4 years ago

Modern CRDTs are massively more space efficient than git but nobody seems to notice or care about the size of our git repositories.

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.

HWR_14• 4 years ago

I still don't grok how CRDTs deal with conflicts. Or is it just "this happens so rarely I'll just use last update"?

davidjfelix• 4 years ago

That's a LWW (last write wins) resolution strategy. Here's a pretty good overview of a variety of CRDT methods: https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...

masklinn10• 4 years ago

This article gives me whiplash, it starts at a high level, dives, stops just before it touches upon the implementation details (and all the weird stuff which makes you realise the developers were human after all) then shoots back up again.

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).

kevincox• 4 years ago

Also presumably "shutting down concurrent reads from that file" is not much of a problem because the file can just be unlinked and it will be GCed when the last reader finishes naturally. Other than hung processes the only downside is extra disk space usage and some cache.

srathi• 4 years ago

Shameless plug: I gave a tech talk on this at my last company, and implemented some of these in Golang as a learning exercise [0]. While it is not mandatory to know the internals, but doing so helps a lot when you occasionally encounter a git-gotcha!

[0] https://github.com/ssrathi/gogit

spapas824• 4 years ago

I have written a small python library to read info directly from the .git folder (without using the git executable): https://github.com/spapas/python-git-info/

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 :|

masklinn10• 4 years ago

The packfile is a really complex/messy format and in the top of that it lacks any proper documentation!

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.

spapas824• 4 years ago

Can you please share the documentation you used to understand the pack file implemention? It will be very useful to me!

ori_b2• 4 years ago

Yes. The wire format docs, especially for HTTP, are atrocious. The pack format is well documented enough. (https://github.com/git/git/tree/maint/Documentation/technica...)

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.

tex0• 4 years ago

Packfiles give me PTSD. They are so notoriously hard to maintain on the large scale server side.

I really wish git wasn't using them.

gbrown_• 4 years ago

Could you elaborate on "maintain" please?

legulere• 4 years ago

What if Git had a long-running daemon that could satisfy queries on-demand, but also keep that in-memory representation of data instead of needing to parse objects from disk every time

I guess that would be performance-wise the same as switching from running the compiler in a one-off mode to a LSP analyzer.

vaibhavsagar• 4 years ago

I also have my own implementation of packfiles [1], which I implemented as part of a toy Git implementation in Haskell [2]. I personally found the packfile format underdocumented, e.g. the official reference for the packfile generation strategy is an IRC transcript [3].

1: https://github.com/vaibhavsagar/duffer/blob/bad9c6c6cf09f717...

2: https://vaibhavsagar.com/blog/2017/08/13/i-haskell-a-git/

3: https://git-scm.com/docs/pack-heuristics/

Git’s database internals I: packed object store

Related Stories