4 ms·
Git’s database internals II: commit history queries
- ajross 4y agoFTA: > 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.
- cryptonector 4y agoFossil 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.
- rzzzt 4y agoAre octopus merges modeled as successive commits with two parents each?
- snvsn 4y agoOne 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
- cryptonector 4y agoOk, zero, one, two, or any number of parents. That's even easier.
- ruuda 4y agoThe 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.
- cryptonector 4y agoAnd 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.
- ByronBates 4y ago> 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 :).
- dralley 4y agoI 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 https://github.com/zlib-ng/zlib-ng/discussions/871
- ByronBates 4y agoThat 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`.
- svnpenn 4y agogitoxide is a cool project, but it cant even clone yet: https://github.com/Byron/gitoxide/discussions/300 https://github.com/Byron/gitoxide/discussions/300
- ByronBates 4y ago`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 https://github.com/Byron/gitoxide out`.