数据库 闲来无事,用 Ruby 撸了个 LSM-Tree

yfractal · 2022年05月01日 · 最后由 daqing 回复于 2022年05月02日 · 923 次阅读

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
需要 登录 后方可回复, 如果你还没有账号请 注册新账号