[][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.