Introduction

最近对 LSM-Tree 比较好奇，为了更好的理解，所以就用 Ruby 写了一个 toy project https://github.com/yfractal/lsm-tree。

Why?

Log Structured Merge Tress (LSM-trees) 被很多的数据库所使用，比如 BigTable, LevelDB, RocksDB, Apach Cassandra, HBase 等，是一个非常重要的数据结构。

数据库会有各种各样的适用场景，比如经常会听到 Cassandra 适合高写入。再比如 RocksDB 可能出现卡死的情况 [2]。

这些都是由实现所决定的。当了解了实现，就可以更好的使用和理解问题背后的原因。

所以我用 Ruby 写了一个非常简单的实现 [1]。

Current State & Future Plan

目前实现了 Tired compacting Log-Structured Merge Tree。可以用来了解 LSM-Tree 的数据结构，以及如何做 compaction。

如果时间允许的话，后续会实现 crash recovery 以及 range query。

优化方面，也有很多东西做尝试，比如使用 mmap 做文件到磁盘的映射，尝试如何用 Ruby 做并发/并行，参数调优，优化 Bloom Filter 的使用 [4]。

Other Learning Resource

LSM trees (Log Structured Merge Trees) - Detailed video[5] 可以用来快速了解 LSM-Tree 如何工作。

cs265-lsm-tree[3] 使用 C++ 实现，里面的文档对实现有详细的描述。

如果想对 LSM-Tree 有更深入的理解，也可以参考这两篇 [6][7] 论文。

References

1. https://github.com/yfractal/lsm-tree
2. RocksDB compaction caused lievelock https://twitter.com/otbzi/status/1315616340082790400
3. https://github.com/jackdent/cs265-lsm-tree
4. NIV DAYAN. Optimal Bloom Filters and Adaptive Merging For LSM-Trees. 2018
5. LSM trees (Log Structured Merge Trees) - Detailed video https://www.youtube.com/watch?v=oUNjDHYFES8
6. Siying Dong. Optimizing Space Amplification in RocksDB. 2017
7. Patrick O'Neil. The Log-Structured Merge-Tree (LSM-Tree). 1996