Git’s database internals II: commit history queries | Hacker News Reader

Git’s database internals II: commit history queries

github.blog

133 pointstodsacerdoti12 comments

> This is fast enough for small repositories, but as the repository increases in size the overhead of parsing these plain-text files to get the graph relationships becomes too expensive. Even the fact that we need a binary search to locate the object within the packfile begins to add up.

From my experience and measurements as the author of `gitoxide` both the parsing of commits as well as the binary search to find the object are negligible costs here. The majority of the time is spent in `zlib` which has to inflate objects and deltas prior to use. This makes me wonder what `zstd` would do to these kinds of workloads.

In any case, the object database decoding performance is the bottleneck when traversing commits, and one can expect to get about 120000 commits per second on the linux kernel pack on a modern CPU core like M1 with `gitoxide`s implementation.

Besides that, I find the explanation of the commit-graph file interesting and how it relates to commit-graph queries. There is so much to learn, and so much still to implement :).

I wonder if zlib-ng would make a difference, since it has a lot of optimizations for modern hardware.

https://github.com/zlib-ng/zlib-ng/discussions/871

That number is already based on using `zlib-ng`. Sometimes I wonder if it's cheating since `git` might not actually use it. In any case, improving the efficiency of `zlib` along with the Rust integration for it has immediate impact on the git object database performance of `gitoxide`.

gitoxide is a cool project, but it cant even clone yet:

https://github.com/Byron/gitoxide/discussions/300

`gitoxide` can currently perform many of the tasks required, and closing the loop for a full clone with worktree is going to happen at the end of this year.

That said, here is how to receive a pack from the remote and resolve it: `mkdir out && gix -v no-repo pack receive https://github.com/Byron/gitoxide out`.

FTA:

> Graph databases need not apply

The previous blog entry had some of the same apologia about database theory and why git seems to be breaking rules. This seems misplaced to me. Git is a foundational technology of the modern internet, used and relied on by... basically everyone to do exactly the job for which it was engineered. It's exactly the place where you'd expect to see a special-purpose data store in use, tuned to exactly the application space where it resides.

That's not to say it's not interesting to talk about graph databases or B trees (from the last post) and how they might be applied to source control. But please don't stop in the middle of your discussion about git to do it. We know git stands alone, tell us how git works.

Fossil uses SQL and is very Git-like in many ways (but with an opinionated, merge-hap-hap-happy UI), and definitely is graph-like in its schema. That tends to prove that, indeed, there's nothing that special about Git that makes it not like other databases.

Commit metadata is decidedly relational (or, rather, can be modeled as such). Commits have zero, one, or two parent commits (thinking of root commits as parentless), they have an author, a date, a commit synopsis and a commit message, a root object, and maybe some other metadata (e.g., who pushed, who signed off, etc.). That's all perfectly appropriate for a relational DB.

The main issue that has come up over time with Fossil-style DVCSes is the size of the metadata you must keep and examine to do things like `git log -- some-file`. The metadata size issue is always going to be an issue, but maybe an ad-hoc DB can wring more compression out than a general purpose DB. Git itself had the second problem, and it had to get solved by using a Bloom filter to reduce the set of commits that need to be examined.

Are octopus merges modeled as successive commits with two parents each?

Ok, zero, one, two, or any number of parents. That's even easier.

One commit with as many parents as merged branches. (A git commit can have an arbitrary number of parent commits.)

Try git cat-file -p $SHA

The comment in part I that b-trees are not appropriate because Git does not do “live updating” of the packfiles also felt a bit misplaced to me. Writing small objects and then aggregating them into larger ones when we get too many of them, especially with geometric repacks, that sounds a lot like LSM trees, which underpin LevelDB and descendants, which in turn are used as the storage engine in many newer relational databases. It's not b-trees, sure, but there is something that updates with every commit, and you want to balance fast lookups, disk usage, and write amplification. In that sense Git's use case does not sound so special to me at all.

And the things to do to amortize b-tree write magnification, are well known, so b-tree magnification alone is not an excuse not to use b-trees.

Reply on news.ycombinator.com