sanakirja 0.10.0

A key-value dictionary, using copy-on-write and B trees.
Documentation

Fast and reliable key-value store.

Features

  • ACID semantics.

  • B trees with copy-on-write.

  • Support for referential transparency: databases can be cloned in time O(log n) (where n is the size of the database). This was the original motivation for writing this library.

Concurrency model

In Sanakirja, mutable transactions (MutTxn) exclude each other, but do not exclude "readers" (i.e. immutable transactions, or Txn). The only exclusion is that a single immutable transaction cannot be alive at the same time as two successive mutable transactions. In other words, a Txn started before the commit of a mutable transaction must finish before the next mutable transaction is started.

These rules are enforced by the current version of the crate: before starting, mutable transactions will wait until all immutable transactions that had been started before the last commit are finished.

In the following example, two consecutive mutable transactions are started in a thread parallel to the main thread, which starts one immutable transaction.

The line assert!(now.elapsed().as_secs() >= 3) below checks that the second mutable transactions waits the end of the immutable transaction on the main thread to complete.

std::fs::create_dir_all("test").unwrap();
let env = Arc::new(Env::new("test", 409600).unwrap());
let env_ = env.clone();
let t = std::thread::spawn(move || {
println!("starting first mutable txn");
let txn = env_.mut_txn_begin().unwrap();
std::thread::sleep(std::time::Duration::from_secs(2));
txn.commit().unwrap();
println!("first mutable txn committed");
std::thread::sleep(std::time::Duration::from_secs(1));
println!("starting second mutable txn");
let now = std::time::Instant::now();
let txn = env_.mut_txn_begin().unwrap();
std::thread::sleep(std::time::Duration::from_secs(2));
assert!(now.elapsed().as_secs() >= 3);
txn.commit().unwrap();
println!("second mutable txn committed");
});

std::thread::sleep(std::time::Duration::from_secs(1));
let txn = env.txn_begin().unwrap();
std::thread::sleep(std::time::Duration::from_secs(5));
std::mem::drop(txn);

t.join().unwrap();

The following example shows that mutable transactions are mutually exclusive:

let env = Arc::new(Env::new("test", 409600).unwrap());
let env_ = env.clone();
let t = std::thread::spawn(move || {
println!("starting first mutable txn");
let txn = env_.mut_txn_begin().unwrap();
std::thread::sleep(std::time::Duration::from_secs(2));
txn.commit().unwrap();
});
let txn = env.mut_txn_begin().unwrap();
std::thread::sleep(std::time::Duration::from_secs(2));
txn.commit().unwrap();
t.join().unwrap();

Corruption-safety

Sanakirja guarantees a corruption-safe database only insofar as the following properties are respected:

  • All references to a Db modified by a call to put or del must be updated (for example with txn.set_root() if the Db was obtained with txn.root()), so that the previous version doesn't get used anymore after put or del return.

  • Every Db must be referenced exactly once in the file, which is something the Rust typesystem cannot guarantee by itself (because the objects are stored in a file instead of the main memory). The only way to get a second reference to a Db is to explicitly call the fork method of a mutable transaction.