Now that Sanakirja is in a usable state, the main operation before we can start to use Pijul for other purposes than tests is to plug Sanakirja in. This post describes our strategy for doing this, and the difficulties we’ve had.
This is the part I want to blog about, since I’ve had a really hard time figuring out how to do it. The main problem comes from the following patterns we use all the time in Pijul:
This means doing something for every key and value in increasing order, starting from a particular key and value. When we designed the format of Pijul repositories, we chose the order of edge flags carefully, so that edge flags that are often iterated together are ordered consecutively.
Initially, I wanted to use closures to iterate, as Sanakirja can do this without allocating a single byte on the heap. I had a Backend trait, with the following function (among others):
trait Backend {
fn iter<'a, F:FnMut(&'a[u8],&'a[u8]) -> bool> (
&'a self, key0:&[u8], value0:&[u8], mut f:F
) {
unimplemented!()
}
}
In other words, my iterator was borrowing the backend for lifetime 'a, and applying function f on slices with the same lifetime. Unfortunately, this is not usable in real cases (at least not in Rust 1.6), since the only thing such a method would be useful for would be to change stuff in its borrowed environment. But then Rust thinks that closure f might outlive the function that called iter.
I’m not sure why this happens, since f must have returned by the end of the call to iter, and it does not implement the Send trait, which would be necessary to move it to another thread.
Then, another design, compatible with the for notation of Rust, is to use iterators. Iterators have another main advantage: they can be used with tons of methods such as take_while or map, which will allow us to simplify the harder parts of our code.
The first drawback is, iterators are stateful, which means that Sanakirja will need to allocate a vector on the heap. Since Sanakirja is also written in Rust, the borrow checker could allow us to perform this allocation only once, and still be safe and usable. In contrast, there’s no way in Rust to use two nested LMDB cursors, as they’re both mutable, and borrow the transaction.
So, I rewrote my trait:
trait Backend {
type Iter:Iterator;
fn iter(&self, key0:&[u8], value0:&[u8]) -> Self::Iter {
unimplemented!()
}
}
But then, Iter is not just any iterator, it yields only pairs of byte slices, valid for “at least” the time self is borrowed by iter. Since Rust’s associated types (or type families) do not accept parameters (it’s actually an RFC), the only way this is possible is the following:
trait Backend<'a> {
type Iter:Iterator <Item = (&'a[u8], &'a[u8])>;
fn iter(&'a self, key0:&[u8], value0:&[u8]) -> Self::Iter {
unimplemented!()
}
}
This had hit me in other projects before (in particular Coturnix), but now I understand the problem. The issue now, is that this is not usable either. For instance, if I want to iterate and the change the database, I cannot simply do this:
fn test<'a, B:Backend<'a>>(backend:&mut B)
{
{
for (x,y) in backend.iter(b"key", b"value") {
println!("{:?}", (x,y))
}
}
backend.put(b"bla", b"bli");
}
Because when I call backend.iter, it has the effect of borrowing backend for lifetime 'a, which is defined beforehand, and can therefore not be the small scope I defined aroudn the for loop. When the borrow checker runs into backend.put, it sees an immutable borrow in lifetime 'a, which is larger than the current scope, and refuses to borrow backend mutably.
Edit: this blog has no comments, but someone posted this post on reddit, and people rightfully commented that “higher ranked lifetimes”, documented here, solve the problem. I didn’t know about these, thanks to dbaupp and bjzaba for the explanation!
However, we can’t use them in Pijul, since child transactions in Sanakirja are implemented with a different type from their parent. This disallows arbitrarily nested transactions, but I couldn’t see any use case, and the implementation of commit is chosen at compile time rather than with an if (for a really tiny performance gain, of course).
Alright then, what if I still want to have both LMDB and Sanakirja as possible backends? Since Sanakirja is not widely used and tested, bugs observed in Pijul might sometimes come from Sanakirja. Changing backends would make the codebase more robust, and force us to define a precise semantics for backend operations.
Then, I decided to do a very Ocamlish thing: using modules as the poor man’s typeclasses. The difference is that the module support in Rust is not as good as in Ocaml (obviously, typeclasses are usually easier to use and less verbose), and hence I believe there’s no way to say “import this module and check it has that signature”.
Anyway, I now have a file called lmdb_backend.rs, with the following definitions:
mod backend {
struct Repository<'environment> { .. }
impl Repository<'environment> {
...
}
}
Which I can then use by writing the following in lib.rs:
mod lmdb_backend;
pub use lmdb_backend::backend;
And then, from child modules of lib:
use super::backend::*;
For the iterators, it’s probably not a huge problem in Pijul: I can restrict allocations to a constant number per transaction, and there are already heap allocations even in non-mutable transactions, like caches to avoid running into loops (as Pijul generalizes files to something that can contain loops).
For the traits, two things would improve the situation:
Implement the RFC for adding parameters to associated types. As commented above, this is already done for lifetimes alone.
Add module signatures. As observed in this research paper, modules and typeclasses are not exactly comparable when nested modules are involved. For my particular use case, having both modules and typeclasses could be useful and expressive, and since nested typeclasses with lifetimes can quickly become really messy, functors are probably a great way to implement this “backend” structure. Pijul’s development followed the following track:
Before that, Pijul had stayed for some time in a prototype state without a backend (serializing the whole repository to the disk on every operation). Relying on LMDB was very comfortable in the beginning, since it allowed us to benchmark our approach without having to develop a whole database engine.
But then, what we need is not exactly a trait, since Pijul will have exactly one standard repository format. We just need something to specify a replacable interface at exactly one point in the development, and allow Rust to inline whatever it wants once that module is stabilized. Plugging Sanakirja in will certainly not be bug-free, and when a bug is identified, being able to move back easily to the LMDB backend would be helpful.
For large values, the Sanakirja API is not as nice as the LMDB one, the main reason being a focus on simplicity and on-disk-compactness rather than ease of use.
In Sanakirja, large values are returned as an iterator over &[u8], whereas LMDB returns a &[u8]. The implications on the file layout are clear: LMDB manages a free pages in a fancy way, which allows it to detect consecutive free pages. Then, when allocating a value spanning on several pages, it finds consecutive free pages, and if there’s none, it expands the file. The consequence of this is that the file might become relatively scarce when many large values are allocated.
Sanakirja has a different tradeoff, where all values are always returned as an iterator. In the future, we might introduce new methods that return a single slice and panic on large values.
This repeats all the problems we’ve had with iterators. The solution is the same: embed an Iter type in the backend module, and verify manually that all backends have the same module signature.
Then, we’re also undertaking the important task of splitting the 3000 lines of the main file in libpijul into smaller modules. So far, the structure and interdependencies were not easy to understand from the source.
For my defense, I will argue that code based on theory is highly likely to be of this form in the early versions, since the things you can explain in five minutes and two drawings on a whiteboard can sometimes take five lines, sometimes five hundred lines, to write efficiently.
Anyway, now our module structure looks like:
lib
├── mod fs_representation
├── mod lmdb_backend
│ └── mod backend
├── mod file_operations
├── mod patch
├── mod graph
├── mod diff
├── mod record
├── mod output_repository
└── mod apply