#disk #copy-on-write #datastructures #n #or #efficient #entries

sanakirja

Copy-on-write datastructures, storable on disk (or elsewhere) with a stable format

84 releases (19 stable)

new 1.2.8 Jul 25, 2021
1.2.5 Jun 15, 2021
1.2.0 Mar 9, 2021
0.15.11 Jan 17, 2021
0.2.0 Mar 30, 2016

#52 in Database interfaces

Download history 174/week @ 2021-04-05 195/week @ 2021-04-12 271/week @ 2021-04-19 87/week @ 2021-04-26 156/week @ 2021-05-03 80/week @ 2021-05-10 164/week @ 2021-05-17 74/week @ 2021-05-24 143/week @ 2021-05-31 142/week @ 2021-06-07 111/week @ 2021-06-14 47/week @ 2021-06-21 220/week @ 2021-06-28 162/week @ 2021-07-05 154/week @ 2021-07-12 189/week @ 2021-07-19

573 downloads per month
Used in 6 crates (5 directly)

MIT/Apache

310KB
6.5K SLoC

Sanakirja

Sanakirja is an on-disk transactional key-value store, based on B trees and copy-on-write. An optional transactional reference counting makes it efficient to clone tables. Formally, the fork_db operation is in O(log n) in the worst case, where n is bounded above by the total number of entries in the entire file.

Rather low-level

This crate is relatively low-level, in the sense that it is possible to keep pointers to a freed database, and to leak memory. The only constraint is this: all calls that modify a Db may change that Db, and it is invalid to keep an old value. Moreover, if you forget to record the new value of a Db, or a newly-created Db, this may leak memory.

One strong point of this design is to be able to use arbitrary type hierarchies, by using tables (i.e. the Db type) as values in another table. In such cases, it is easy to write wrappers around these types to update values automatically just before committing a transaction.

no_std available

A more basic crate called Sanakirja-core is also available, and compiles with no_std. The main difference with this crate (Sanakirja) is that Sanakirja implements allocator traits required by Sanakirja-core, using operating system primitives such as mmap.

This makes it possible to use Sanakirja-core in contexts such as WASM, or even to use Sanakirja-core as part of a filesystem.

Example

In the following example, the calls to method set_root register the B trees created by create_db and fork_db as "root tables" (there can be at most 510 root tables), so we don't lose track of these tables.

use sanakirja::*;
let env = Env::new("db", 1 << 20, 2).unwrap();
let mut txn = Env::mut_txn_begin(&env).unwrap();
let mut db = btree::create_db::<_, u64, u64>(&mut txn).unwrap();
let db2 = btree::fork_db(&mut txn, &db).unwrap();

btree::put(&mut txn, &mut db, &12u64, &5432u64).unwrap();

let ndb = 0;
let ndb2 = 1;
txn.set_root(ndb, db.db);
txn.set_root(ndb2, db2.db);
txn.commit().unwrap();

let txn = Env::txn_begin(&env).unwrap();

let db: btree::Db<u64, u64> = txn.root_db(ndb).unwrap();
assert_eq!(btree::get(&txn, &db, &12, None).unwrap(), Some((&12, &5432)));

let db2: btree::Db<u64, u64> = txn.root_db(ndb2).unwrap();
assert_eq!(btree::get(&txn, &db, &12, None).unwrap(), None);

Dependencies

~0.8–1.8MB
~40K SLoC