模块化、异步实现的日志结构合并树

注意：虽然此实现已被我们使用且未引起重大问题，但我们不建议在生产环境中使用。请使用 leveldb 或 rocksdb crate 来实现此目的。

此实现的目标不是重新实现LevelDB。主要区别包括

• 键值分离：值可以单独存储以提高压缩速度，如WiscKey论文中所述
• 并发压缩：多个线程可以同时压缩以提高写入吞吐量
• 异步支持：所有API调用都作为异步函数公开
• io_uring支持：用于Linux上的异步文件系统访问。可选，目前仍被视为实验性。
• 布隆过滤器以加快查找速度

支持的平台和架构

目前，代码仅在Linux的x86机器上进行了测试，但它应该可以在Rust编译器支持的多数系统上运行。

磁盘格式

LSM使用zerocopy和（当可能时）mmap来存储数据，以实现高性能。实现不考虑字节序，因此磁盘格式不可移植。跨机器复制应在系统不同层处理。然而，如果需要，我们可能会在未来添加转换工具或一个endianess功能标志。

计划的功能

• FLSM：与PebblesDB类似，LSM-rs将分片键空间以减少写放大并提高压缩速度
• 自定义排序函数
• 更多模块化和配置选项

特性标志

• snappy-compression：使用snappy格式在磁盘上压缩数据（默认启用）
• bloom-filters：向数据块添加布隆过滤器以更有效地搜索。（默认启用）
• async-io：使用 tokio_uring 进行 I/O 操作，而不是标准库中的 I/O。注意，这仅在最近的 Linux 内核版本中有效。（默认禁用）
• wisckey：分别存储键和值。这通常会导致更高的吞吐量，但 CPU 使用率略高。（默认禁用）

同步 API

这个 crate 提供了一个异步 API，旨在与 Tokio 或类似运行时一起使用。或者，您可以使用本仓库中包含的 lsm-sync crate，该 crate 内部使用 Tokio，但提供同步 API。

排序顺序

您需要以某种方式序列化数据，使其字节表示形式保持与反序列化数据的相同顺序。例如，您可能希望使用 大端 编码，以确保数值顺序正确。

用法

您可以使用以下方式创建或打开一个新的数据库实例。

use lsm::{Database, Params};

// Set options here, such as the location of the database files
let params = Params {
    db_path,
    ..Default::default()
};

// Instantiate database
let database = Database::new_with_params(SM, params)
    .await
    .expect("Failed to create database instance");

要写入数据库，请使用 get 调用。请注意，该 crate 仅支持写入字节数组。（反）序列化应在另一层中发生。

let key = String::from("mykey").into_bytes();
let value = String::from("hello world").into_bytes();

database.put(key, value).await.expect("Writing to database failed");

在读取时，LSM 将返回数据的引用以避免复制。

let value_ref = database.get(&key).await.expect("Reading failed");

// Returns a slice to the data
let data: &[u8] = value_ref.get_value();

// Assuming the put from above workd, this will print "hello world"
println!("{}", std::str::from_utf(data).unwrap());

请参阅测试，以获取更多如何使用该 crate 的示例。

测试

此库包含几个测试。我们提供了一个 justfile 以方便使用。

just test #runs all tests for all configurations
just lint #runs cargo clippy

关于 io-uring 的说明

目前，io-uring 功能依赖于 tokio-uring-executor，它是围绕 tokio-uring 的简单多线程包装器。最终 tokio-uring 将 原生支持多线程，并且此解决方案将被删除。

我还想添加对更成熟的 io_uring 运行时（如 gloomio）的支持，但在此 crate 上工作的时间有限。欢迎提供帮助。

类似 Crates

这是一个提供类似功能的 crate 的不完全列表。如果您知道其他可以添加的 crate，请告知。

LSM 树

• rust-rocksdb：RocksDB 的 Rust 绑定
• leveldb：LevelDB 的 Rust 绑定
• wickdb：LevelDB 的 Rust 重新实现
• agatedb：TiKV 的 WiscKey 实现的 Rust 版本

其他键值存储

它们在方法上存在显著差异，但也提供了键值存储抽象

• redb