LSM 树 设计思想总结

LSM 树的设计思想很有意思。

LSM 树将对磁盘的随机写入转化为了磁盘友好型的顺序写（无论机械磁盘还是 SSD，随机读写都要远远慢于顺序读写），从而大大提高了写性能。

1、怎么转化顺序写？

核心就是在内存中维护一个有序的内存表（memtable），当内存表大于阈值的时候批量刷入磁盘，生成最新的 SSTable 文件。因为本身 memtable 已经维护了按键排序的键值对，所以这个步骤可以高效地完成。

写入内存表时先将数据写入 WAL 日志，用以在发生故障时，通过重放 WAL 恢复内存中的数据，保证数据库的数据一致性。

2、空间放大和读放大

在这种追加（append-only）写入模式下，删除数据变成了对数据添加删除标记，更新数据变成了写入新的 value，在同一个时间数据库中会存在同个 key 的新值和旧值。这种影响被称之为 空间放大（Space Amplification）。

随着数据的写入，底层的 SSTable 文件也会越来越多。

读请求在这个模式下，变成了先在内存中寻找关键字，如果找不到则在磁盘中按照新-> 旧查找 SSTable 文件。为了优化这种访问模式的读性能，存储引擎通常使用常见的针对读的优化策略，比如使用额外的 Bloom Filter、读 Cache。

这种需要多次读取的过程（或者说影响）被称之为读放大（Read Amplification）。

3、读放大怎么优化？使用compaction

很显然，读放大会影响 LSM 树的读性能。

为了优化读性能（读放大），同时优化存储空间（空间放大），LSM 树通过在运行合并和压缩过程减少 SSTable 文件数量，删除无效（被删除或者被覆盖） 的旧值。这一过程被称之为 compaction。

4、compaction压缩对写入的放大

但是 compaction 也会一些影响，在数据库的生命周期中每次的数据写入实际上会造成多次的磁盘写入。这种影响被称之为写放大（Write Amplification）。

在写入繁重的应用程序中，性能瓶颈可能是数据库可以写入磁盘的速度。在这种情况下，写放大会导致直接的性能代价：存储引擎写入磁盘的次数越多，可用磁盘带宽内的每秒写入次数越少。

这也是我认为 LSM 引擎存储的一个缺点，就是压缩过程有可能会干扰到正在进行的读写请求。尽管存储引擎尝试逐步执行压缩而不影响并发访问，但是磁盘资源有限，所以很容易发生请求需要等待磁盘完成昂贵的压缩操作。对吞吐量和平均响应时间的影响通常很小，但是如果是高百分位情况下（如 P99 RT），有时就会出现查询响应较长的情况。

上述是对 LSM 树的个人总结，一些没有提到实现细节的抽象描述（比如 memtable、compaction），在实际的存储中都有对应的实现，细节可能不同，但是设计思想都是类似。

5、写放大、读放大、空间放大的TradeOff

在RocksDB 实现中，写放大、读放大、空间放大，这三者就像 CAP 定理一样，无法同时达到最优。

为此 RocksDB 暴露了很多参数来让使用者进行调优，以适应更多的应用场景。这其中很大一部分工作是在写放大、读放大和空间放大这三个放大因子之间做好 trade off。