Yet Another Kev-Value DataBase

PLAN:

• make yakvdb thread-safe
  • distinct RW locks on pages in the pool?
  • cannot use it in async context now:
    • the trait Sync is not implemented for RefCell<...>
• split Tree trait into pub KV-only and internal page-aware
  • to avoid leaking impl details leak into public API
• iterator impl (feature iter)
  • range lookup (returning an iterator)
• CLI
  • connect to a file and explore it
  • lookup X64'00cafebabe'
  • insert X64'00cafebabe' X64'00deadbeef'
  • remove X64'00cafebabe'
  • above X64'00cafebabe'
  • below X64'00cafebabe'
  • min
  • max
  • len (iterate from min to max)
  • basic defragment/restore utilities
• add async impl based on tokio::fs
  • you can't go back to sync though
  • somehow make feature switch to async?

Extremely simple (simplest possible?) single-file BTree-based key-value database.

Built for fun and learning: goal is to "demystify" the "database".

Operations amortized runtime complexity:

• insert/remove: O(log(N) * log(K) + K)
• lookup/min/max/above/below: O(log(N) * log(K))

Where:

• N - number of entries in a tree
• K - number of entries in a page

Binary search is run for each page (log(K)) and touches at most log(N) pages.

On insert/remove each page performs O(K) cleanup to keep keys ordered, as well as extra housekeeping is performed if necessary (split or merge of pages).

Each insert/remove gets flushed to disk for durability.

API

• Page defines BTree node (impl: Block)
• Tree defines full BTree (impl: File)

Demo

Just cargo run --release to run example from main.rs:

• create/open database (file)
• generate random key-value pairs
• insert all key-value pairs
• lookup all keys and check values match
• iterate all keys in ascending order
• iterate all keys in descending order
• remove all keys and check database is empty

The typical result looks like one below.

$ RUST_LOG=info cargo run --release
[snip]

# 1M
[...] file="target/main_1M.tmp" count=1000000 page=4096
[...] insert: 28742 ms (rate=34792 op/s)
[...] lookup: 5316 ms (rate=188111 op/s)
[...] iter: min=000003cf1bb4e04d max=ffffe6e240320123
[...] iter:  asc 553 ms (rate=1808318 op/s) n=1000000
[...] iter: desc 538 ms (rate=1858736 op/s) n=1000000
[...] remove: 27101 ms (rate=36899 op/s)

# 10M
[...] file="target/10M.db" count=10000000 page=4096
[...] insert: 371971 ms (rate=26883 op/s)
[...] lookup: 95038 ms (rate=105221 op/s)
[...] iter: min=00000244ad95c9eb max=ffffffbd837a505b
[...] iter:  asc 6793 ms (rate=1472103 op/s) n=10000000
[...] iter: desc 7008 ms (rate=1426940 op/s) n=10000000
[...] remove: 368056 ms (rate=27169 op/s)

# 100M
[...] file="target/100M.db" count=100000000 page=4096
[...] insert: 4387618 ms (rate=22791 op/s)
[...] lookup: 1003484 ms (rate=99652 op/s)
[...] iter: min=000000542c79d673 max=ffffffbd837a505b
[...] iter:  asc 74953 ms (rate=1334169 op/s) n=100000000
[...] iter: desc 73857 ms (rate=1353967 op/s) n=100000000
[...] remove: 4145790 ms (rate=24120 op/s)

Code

use std::cell::Ref;
use crate::api::error::Result;
use crate::disk::block::Block;
use crate::disk::file::File;

// Create new database with given page_size
let mut db: File<Block> = File::make(path, /*page_size=*/4096).unwrap();
// Or open a database from an existing file
let mut db: File<Block> = File::open(path).unwrap();

let r: Result<Optional<Ref<u8>>> = db.lookup(&b"key");
let _: Result<()> = db.insert(&b"key", &b"val");
let _: Result<()> = db.remove(&b"key");

// To iterate: db.min(), db.max(), db.above(&[u8]), db.below(&[u8])

Other

• Bitcask