lsmtk

此库提供了一个日志结构的合并树实现；此合并树使用一种称为“三角压缩”的新压缩算法，在理论和实践中都实现了6.5倍的写放大因子。

三角压缩

三角压缩注意到一个观察结果：从一个级别移动到下一个级别是低效的；相反，压缩应该跨越多个级别来移动尽可能多的数据。

压缩算法的核心来自以下 Python 片段中的直觉

sums = 0
count = 0
ingest = 0
for i in range(2**ceil(LSM_NUM_LEVELS)):
    bits = 0
    while i and (1 << bits) & i:
        bits += 1
    sums += (1 << bits) * TARGET_FILE_SIZE * LSM_LEVEL_0_NUM_FILES
    ingest += TARGET_FILE_SIZE * LSM_LEVEL_0_NUM_FILES
    count += 1
COMPACTION_AVERAGE_SIZE = sums / count + LSM_LEVEL_0_NUM_FILES * TARGET_FILE_SIZE # bytes
WRITE_AMPLIFICATION = sums / ingest

在此压缩中，我们选择最低的N个满级，在遇到第一个空级时停止。这样我们就可以像 Rust 中的 Vec 或 C++ 中的 vector 一样分摊压缩的成本。

三角压缩算法将这种直觉推广到从 LSM 树中选择三角形，使得该级别下文件的传递闭包将包含在压缩中。

检查 src/tree/mod.rs 了解压缩算法。

权衡

写放大因子被限制在6.5倍以下。

• 读放大因子无限制，但根据经验保持在较低水平。
• 空间放大因子被限制在2倍以下。

在一个经验基准测试中，我们摄取了44GiB的数据，我们发现写放大因子保持在3倍以下（垃圾是已被压缩的 SST；在实际系统中，它将定期清空）

4.0K    db/compaction
71M     db/ingest
8.8M    db/mani
44G     db/sst
127G    db/trash

进程计数器确认了2.9倍的写放大因子。

lsmtk.bytes_ingested = 46552563486
lsmtk.compaction.bytes_written = 135401535775

状态

活跃开发。

范围

此库提供了 lsm 图的组件。它最终将扩展到支持创建类似于 LevelDB 和 RocksDB 的嵌入式 lsm 图所需的一切。

缺点

• 此库尚未经过充分测试，未来将进行积极开发。
• 未使用 LevelDB（祖父重叠）和 PebblesDB（保护页）中的技巧。这些都是100%兼容的，并且只会提高压缩算法的性能。
• 没有针对过度摄取的反压。
• 在约40GiB的点上出现并发错误，压缩将停滞。这只是一个原型阶段，我已耗尽资金继续开发。

文档

最新的文档始终可在docs.rs找到。