“I now understand that git not only comes with an append-only (“immutable”) content-addressable database, but is also a boring mutable key-value store.”
I learned Git from Scott Chacon’s Git Internals book from 2007. It was great if you’re a systems programmer and you prefer to learn how things work bottom up. Very early in the book on page 21:
“In addition to the Git objects, which are immutable – that is, they
cannot ever be changed, there are references also stored in Git.
Unlike the objects, references can constantly change. They are
simple pointers to a particular commit, something like a tag, but easily
moveable. Examples of references are branches and remotes.”
As an aside, the minimal design for a mutable key-value store on top of an immutable object store needs only 1 ref (the root). Or 2 refs (the old root and new root) for crash recovery if your durable storage doesn’t provide atomic ref updates. Then the recovery protocol reads both root descriptors and selects the newest (by logical timestamp) whose checksum passes. The embedded database system lmdb uses this kind of design, with 2 alternating root pages, although its object model is not content addressed.
As an aside to your aside, a neat project that demonstrates a key-value store on content addressable storage (git-compatible) is Irmin (https://irmin.org/). It’s a shame that the ideas used in git aren’t used in more software.
To clarify, git itself doesn’t implement KV on top of its content-addressable store. It just uses file system, and, as far as I understand, doesn’t provide particularly strong atomicity guarantees at that.
It is a beautiful idea that append-only KV + a single mutable root pointer allow you to build anything fancy on top, including, eg, full relational model, but this is not an idea that git uses in its implementation, I think its mostly just a bunch of ad-hoc files on the file system.
I happen to have a homegrown system I use as a foundation for builds writ large (atomic tree snapshots with recursively derived build artifacts), which has some similarities to Irmin. The major feature I don’t have (and don’t need) in that system is Irmin’s mergeable replicated data types, which in my mind is Irmin’s most notable feature: https://www.youtube.com/watch?v=_1zFtB4HSwU.
Unlike Irmin, my system’s support for “custom data types” is the bare minimum needed to walk the object graph in a generic way: an object has an array of links to other objects in a uniform format, in addition to its blob body. IMO, one of Git’s flaws as a generic object store is that facilities like garbage collection require knowledge of a closed set of object kinds and kind-specific format parsing to traverse their links.
“I now understand that git not only comes with an append-only (“immutable”) content-addressable database, but is also a boring mutable key-value store.”
I learned Git from Scott Chacon’s Git Internals book from 2007. It was great if you’re a systems programmer and you prefer to learn how things work bottom up. Very early in the book on page 21:
“In addition to the Git objects, which are immutable – that is, they cannot ever be changed, there are references also stored in Git. Unlike the objects, references can constantly change. They are simple pointers to a particular commit, something like a tag, but easily moveable. Examples of references are branches and remotes.”
As an aside, the minimal design for a mutable key-value store on top of an immutable object store needs only 1 ref (the root). Or 2 refs (the old root and new root) for crash recovery if your durable storage doesn’t provide atomic ref updates. Then the recovery protocol reads both root descriptors and selects the newest (by logical timestamp) whose checksum passes. The embedded database system lmdb uses this kind of design, with 2 alternating root pages, although its object model is not content addressed.
score 5 · canonical
As an aside to your aside, a neat project that demonstrates a key-value store on content addressable storage (git-compatible) is Irmin (https://irmin.org/). It’s a shame that the ideas used in git aren’t used in more software.
score 1 · canonical
To clarify, git itself doesn’t implement KV on top of its content-addressable store. It just uses file system, and, as far as I understand, doesn’t provide particularly strong atomicity guarantees at that.
It is a beautiful idea that append-only KV + a single mutable root pointer allow you to build anything fancy on top, including, eg, full relational model, but this is not an idea that git uses in its implementation, I think its mostly just a bunch of ad-hoc files on the file system.
score 1 · canonical
I happen to have a homegrown system I use as a foundation for builds writ large (atomic tree snapshots with recursively derived build artifacts), which has some similarities to Irmin. The major feature I don’t have (and don’t need) in that system is Irmin’s mergeable replicated data types, which in my mind is Irmin’s most notable feature: https://www.youtube.com/watch?v=_1zFtB4HSwU.
Unlike Irmin, my system’s support for “custom data types” is the bare minimum needed to walk the object graph in a generic way: an object has an array of links to other objects in a uniform format, in addition to its blob body. IMO, one of Git’s flaws as a generic object store is that facilities like garbage collection require knowledge of a closed set of object kinds and kind-specific format parsing to traverse their links.
score 2 · canonical