从SSTable到LSM-Tree之二

 Here is the article. 

背景

LSM-Tree (Log Structured Merge Tree)，日志结构合并树。它在 1996 年由论文《The Log-Structured Merge-Tree (LSM-Tree) 》^[1]首次提出，但真正得到广泛应用是在 2006 年Google Bigtable 论文之后，论文中提到 Bigtable 使用的数据结构就是 LSM-Tree。

目前，LSM-Tree 已经被广泛应用于一些流行的的 Key-Value 型存储引擎中，如 Bigtable、Cassandra、HBase、RocksDB^[2]、LevelDB、ScyllaDB^[3]等。LSM 已经成为基于磁盘的 Key-Value 型存储引擎的标配。

为什么需要 LSM-Tree ？

我们知道，磁盘的顺序读写性能要比随机读写性能高2个数量级以上。日志结构指的就是日志形式的追加写（Append Only），它是顺序写。

LSM-Tree 相比于传统的 B+ 树存储引擎，具有更高的写入性能。通过把磁盘随机写转换为顺序写，来大幅提升写入性能。代价是，牺牲了部分读性能及写放大问题。这么说，并不是说 B+ 树不存在写放大，它实际也存在写放大问题。我们稍后再研究这个问题。

LSM-Tree 结构

我们先看看原始论文中描述的 LSM-Tree 结构，再看看实际存储引擎中的实现。