9 releases (breaking)

0.6.2 Jun 12, 2023
0.6.1 May 23, 2023
0.5.0 May 21, 2023
0.4.0 May 20, 2023
0.0.0 Jul 10, 2021

#742 in Database interfaces

26 downloads per month

MIT license

665KB
2K SLoC

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

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

Dependencies

~4–13MB
~129K SLoC