另一种键值型数据库

计划

• 使yakvdb线程安全
  • 在池中的页面上有独立的读写锁吗？
  • 现在不能在异步上下文中使用
    • 未为 RefCell<...> 实现特质的 Sync
• 将 Tree 特质分割为 pub KV-only 和内部页面感知
  • 以避免实现细节泄漏到公共API中
• 迭代器实现（特性 iter）
  • 范围查找（返回迭代器）
• 命令行界面（CLI）
  • 连接到文件并探索它
  • 查找X64'00cafebabe'
  • 插入X64'00cafebabe' X64'00deadbeef'
  • 删除X64'00cafebabe'
  • 上面X64'00cafebabe'
  • 下面X64'00cafebabe'
  • 最小值
  • 最大值
  • len（从 min 到 max 迭代）
  • 基本的碎片整理/恢复工具
• 添加基于 tokio::fs 的异步实现
  • 但是不能回到同步
  • somehow make feature switch to async?

极其简单（可能最简单？）的单文件BTree键值数据库。

为娱乐和学习而构建：目标是“去神秘化”数据库。

操作的摊销运行时复杂度

• 插入/删除：O(log(N) * log(K) + K)
• 查找/最小值/最大值/上面/下面：O(log(N) * log(K))

其中

• N - 树中的条目数
• K - 页中的条目数

对每个页面运行二分搜索（log(K)）并最多触及 log(N) 个页面。

在插入/删除时，每个页面执行 O(K) 清理以保持键有序，以及如果需要执行额外的维护（页面拆分或合并）。

每个插入/删除都会刷新到磁盘以确保持久性。

API

• Page 定义 BTree 节点（实现： Block）
• 树 定义了完整的B树（实现：文件）

示例

只需执行 cargo run --release 从 main.rs 运行示例

• 创建/打开数据库（文件）
• 生成随机的键值对
• 插入所有键值对
• 查找所有键并检查值是否匹配
• 按升序迭代所有键
• 按降序迭代所有键
• 移除所有键并检查数据库是否为空

典型的结果如下。

$ 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)

代码

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])

其他

• Bitcask