[−][src]Crate sanakirja

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 for the end of the immutable transaction on the main thread to complete.

use sanakirja::{Env, Commit};
let dir = tempfile::TempDir::new().unwrap();
let env = std::sync::Arc::new(Env::new_anon(409600).unwrap());
let env_ = env.clone();
let t = std::thread::spawn(move || {
    println!("starting first mutable txn");
    let txn = Env::mut_txn_begin(env_.clone()).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(env_).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(env).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:

use sanakirja::{Env, Commit};
let dir = tempfile::TempDir::new().unwrap();
let env = std::sync::Arc::new(Env::new_anon(409600).unwrap());
let env_ = env.clone();
let t = std::thread::spawn(move || {
    println!("starting first mutable txn");
    let txn = Env::mut_txn_begin(env_).unwrap();
    std::thread::sleep(std::time::Duration::from_secs(2));
    txn.commit().unwrap();
});
let txn = Env::mut_txn_begin(env).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.

Modules

value

Values, which might be either inlined on the page, or stored as a reference if too large.

Structs

CRCError
Cursor	A position in a database (mostly for internal use).
Db	A database is a skip list of (page offset, key, value).
DbIterator	An iterator over a database.
Env	Environment, required to start any transactions. Thread-safe, but opening the same database several times in the same process is not cross-platform.
Exclusive	Represents an exclusive lock taken on the environment.
MutTxn	A mutable transaction.
Page	This is a semi-owned page: just as we can mutate several indices of an array in the same scope, we must be able to get several pages from a single environment in the same scope. However, pages don't outlive their environment. Pages longer than one PAGE_SIZE might trigger calls to munmap when they go out of scope.
RevDbIterator	An iterator over a database.
Shared	Represents a shared lock taken on the environment.
Statistics	Statistics about the database, useful for debugging and benchmarking purposes.
Txn	An immutable transaction.
UnsafeDb	An untyped database, with the same memory representation as `Db<K, V>`. The only way to convert between `Db<K, V>` and `UnsafeDb` is `std::mem::transmute`. Provisions must be taken outside of this crate to ensure that the database doesn't change type (for example by wrapping this type in a static type with phantom type markers).

Enums

Alignment	Alignment of representables on page. The only implication is on how the `write_value` and `read_value` methods are going to be implemented.
Error	Errors that can occur while transacting.

Constants

ZERO_HEADER

The size of the initial reserved section on the first page.

Traits

Commit	Transactions that can be committed.
LoadPage	Trait for loading a page and a root. Base trait to implement "storage engines" under Sanakirja.
Representable	Types that can be stored in a Sanakirja database, as keys or values. Some care must be taken when storing things.
Transaction	Trait for operations common to mutable and immutable transactions.

Functions

cur ^⚠	Current value of the cursor.
debug	Dumps a number of databases into a dot file.
debug_	Dumps a number of databases into a dot file.
next ^⚠	Return the current element, and then move the cursor forward by one step. This function is safe to use if (1) its `cursor` argument has been initialised and (2) its `txn` argument has not been mutated since that initialisation.
prev ^⚠	Return the current element, and then move the cursor backwards by one step. See the documentation for `next` for more detail.