We’ll release a usable version of Pijul later today. Pijul itself is in an alpha stage, but is based on a number of other things we’ve needed to write, among which a key-value store known as Sanakirja.

Before anything else, the source code is on the Nest!, and you can clone it if you already have Pijul:

$ pijul clone https://nest.pijul.com/pijul/sanakirja

Or, if you already have an account with an SSH public key:

$ pijul clone login@nest.pijul.com/pijul/sanakirja

We’ve blogged about Sanakirja before, but we feel like it has now reached a stage where it can be used fearlessly by Pijul, and hopefully by other projects.

So, what makes Sanakirja different, and why did we embark on such a big mission? Well, there are at least two reasons: transactionality and a fork operation.

Full transactionality

Sanakirja is /fully transactional/: all operations take place within a transaction, and transactions can be cancelled. One advantage of these data structures is that we can keep several copies of the structure in the file, that share their common parts.

Sanakirja includes an allocator for that file, which reserves blocks of fixed size (4 kbytes), which needs to maintain a list of free blocks in the file. Now, instead of writing directly to that list, we just clone the 4k block containing its head, and change that only (then, if we write to the same block again in the same transaction, we don’t need to clone it anymore).

The first page in the file has pointers to various B trees and that list, which means Sanakirja can revert transactions by simply not updating these references on the first page.

Fork

Another benefit of using B trees, and the main reason to write Sanakirja, is to allow fast database forks. This is achieved by storing reference counts on blocks of the B tree. To make these transactional too, they are actually stored in a different B tree. Cycles are avoided by not storing reference counts less than or equal to 1.

This is how we fork repositories in Pijul. Our “branches” database has the following type:

sanakirja::Db<self::small_string::UnsafeSmallStr, (NodesDb, PatchSet, RevPatchSet)>

Basically, a database whose keys are “small strings” (an internal type defined in libpijul, basically a string of length at most 256), and whose value is three databases, one containing the file graph, and the two other containing patches (PatchSet is sorted by patch identifier, and RevPatchSet by time at which the patch was applied).

The forking code is the following:

Branch {
   db: self.txn.fork(&mut self.rng, &branch.db)?,
   patches: self.txn.fork(&mut self.rng, &branch.patches)?,
   revpatches: self.txn.fork(&mut self.rng, &branch.revpatches)?,
   name: SmallString::from_str(new_name)
}

The three calls to fork just increase a reference count, without copying any data.

How to use Sanakirja

We believe Sanakirja to be stable enough to be used in other projects. The API is unlikely to change, except maybe that we might start depending on serde for serialization in the future, without any consequence on the calls.

The main thing to keep in mind when using it is, databases cannot be left dangling, they have to be explicitly stored back into the database after modification. LMDB, which uses a similar scheme, solves this by using an array of databases, and the user only ever sees indices in that array, and not direct pointers to databases.