rsdb

一个现代的无锁原子嵌入式数据库，旨在在读取性能上击败 LSM 树，在写入性能上击败传统的 B+ 树。

它采用模块化设计，也可以用于实现您自己的高性能持久化系统，使用包含的 LockFreeLog 和 PageCache。最终，将在 Tree 上构建一个版本化数据库，它提供多键事务和快照。

Tree 具有C语言API，因此您可以使用任何主流语言访问它。

extern crate rsdb;

let tree = rsdb::Config::default()
  .path(Some(path))
  .tree();

// set and get
tree.set(k, v1);
assert_eq!(tree.get(&k), Some(v1));

// compare and swap
tree.cas(k, Some(v1), Some(v2));

// scans
let mut iter = tree.scan(b"a non-present key < k!");
assert_eq!(iter.next(), Some((k, v2)));
assert_eq!(iter.next(), None);

// deletion
tree.del(&k);

警告

• 相当年轻，有很多模糊测试，但不要将其作为十亿美元的生意来赌！
• C语言API可能很快就会发生变化
• 日志清理目前仅通过 fallocate 在 Linux 上实现！
• 尚未得到许多性能调优的关注，它具有极高的理论性能，但要达到那里需要一些调整。目前，在特定负载下每秒大约只有200k个操作。这很快就会得到改善！

欢迎贡献！

• 想帮助推动开源嵌入式数据库的发展？查看 CONTRIBUTING.md！

功能

• 无锁的 b-link 树
• 带有预留槽位的无锁日志
• 带有缓存友好型部分更新的无锁页面缓存
• zstd 压缩
• 可配置的缓存大小
• C语言API
• 日志清理
• 合并运算符支持
• 支持多键事务和快照的高级接口
• 通过符号执行对无锁算法进行形式化验证

目标

1. 在读取性能上击败 LSM，在写入性能上击败传统的 B+ 树。
2. 不要使用过多的电力。我们的数据结构应该发挥现代硬件的优势。
3. 不要让用户惊讶于性能陷阱。
4. 将学术界的可靠性技术应用到实际实践中。

架构

无锁树在无锁日志上的无锁页缓存。页缓存将部分页面碎片分散到日志中，而不是像历史上用于旋转磁盘的B+树那样一次性重写整个页面。在页面读取时，我们并发地在日志中散列收集读取，以从其碎片中实现页面。

该系统主要受《申命记》架构的启发，并旨在实现RocksDB的最佳特性。

参考文献

• Bw-Tree：适用于新硬件平台的B树
• LLAMA：适用于现代硬件的缓存/存储子系统
• 申命记：云数据的事务支持