a versioned datastore that takes inspiration from git

Getting started

To get started I made a small prototype in GNU Guile to see what are the difficulties that I will encounter. The performance bottleneck relates to fetching the latest triple given a SUBJECT and PREDICATE ie.:

(ref tx subject predicate)

The problem can be expressed as follow:

The API offered by wiredtiger allows to efficently retrieve all the versions of a triple identified by SUBJECT and PREDICATE. Given history is a DAG there is no total order defined. That is, if the history was linear it would be trivial to ref the correct triple. history write access of a given branch is linear/serial, it's enforced by a lock (because otherwise it much more difficult to do anything). Since ref operation happens at a given tx, it also means that it happens in a single branch. In that branch, that is still a DAG, we can implement a total order by doing the same thing that git rebase does, that is linearize the DAG and number each transaction starting form the first transaction as if they happened in that order. This is not true, but for transactions for which that matters there is later merge transaction that fix it, and since ref always look for the most recent transaction, it won't see a broken state of database and see the merge transaction first.