DDIA 中提到了 LSM-Tree，是一种高效的存储引擎，被广泛应用于分布式存储系统中。简单画图解释下相关的设计。

Append-Only Log#

如果我们要存储数据，最简单的可能会选择 key-value 的存储方式。那么内存中就会有一个Map，key 是数据的 key，value 是数据的 value。但是这种方式有一个问题，如果内存中的数据丢失了，那么数据就丢失了。所以我们需要将数据持久化到磁盘上。此时，内存中的 value 就需要改为指向磁盘上的数据的位置。

此时我们可以选择使用Append-Only Log，也就是只追加的日志。每次写入数据，都会追加到日志的末尾。这样即使系统崩溃了，我们也可以通过日志来恢复数据。

append-only-log

写入流程

  • 将数据写入内存中的 Map
  • 将数据通过 append 的方式写入日志

读取流程

  • 从内存中的 Map 中读取要查找的数据在文件中的位置
  • 从日志中读取数据

Pros

  • 简单
  • 可以通过日志来恢复数据
  • 顺序写入，性能高

Cons

  • 需要一个内存中的 Map 来存储数据，如果数据量大，内存不够，这种方案就不适用了
  • 无法进行范围查询，因为 key 是无序的

LSM-Tree#

为了解决Append-Only Log的问题，我们可以引入LSM-Tree。

内存中的数据使用 Tree 的数据结构进行存储，这样可以进行范围查询。当内存中的数据达到一定的阈值时，该 tree 变为不可写状态，使用一个新的 tree 接收最新的写数据，将不可变的 tree 数据写入到磁盘上。此时磁盘上的数据也是有序的。该 tree 称为MemTable，磁盘上的数据文件称为SSTable。

为了保证 memtable 在 crash 的时候不会丢失数据，我们可以使用WAL，也就是Write-Ahead Logging。在写入 memtable 之前，先将数据写入到 WAL 中。这样即使系统崩溃了，我们也可以通过 WAL 来恢复数据。

写入流程

  • 将数据写入 WAL，再写入 MemTable
  • 当内存中的 Tree 达到一定的阈值时，将 Tree 写入磁盘上的 SSTable

读取流程

  • 从内存中的 Tree 中读取数据
  • 如果内存中的 Tree 中没有数据，从磁盘上的 SSTable 中读取数据
  • SSTable 从最新的文件开始读取，因为 SSTable 的数据是有序的，所以我们可以使用二分查找来查找数据。但是不同文件之间未必是有序的。
  • 还可以通过 Bloom Filter 来判断数据是否存在于 SSTable 中，减少无效查询

如果 SSTable 中的数据量太大，我们可以将多个 SSTable 合并成一个更大的 SSTable。清理掉重复的数据，保留最新的数据。

lsm-tree

Compaction & Write Amplification#

LSM-Tree 中的数据可能会有很多重复的数据，为了减少重复的数据，我们可以将多个 SSTable 合并成一个更大的 SSTable。这个过程称为Compaction。

Write Amplification： 多个 SSTable 合并成一个 SSTable，写入的数据量会增加。这个过程称为Write Amplification。对于用户来说，我们只是写入了一次数据，但是因为文件合并，实际写入的数据量会增加。

为了管理这个过程，LevelDB引入了Level分层的组织方式：将 SSTable 分为不同的 Level，每个 Level 有容量阈值，达到阈值时向下一层合并。需要说明的是，分层并不能免费减少 Write Amplification：leveled 这类策略通常是用更多的重写去换更低的读放大和空间占用，它的价值在于把合并变成一层层可控的小步操作，并让每层内部保持有序。写放大、读放大、空间放大三者怎么取舍，取决于具体的 compaction 策略（如 size-tiered 与 leveled 的差异）。

  • 如果memtable写满了，将memtable写入到 Level 0的 SSTable 中。
  • 当 Level 0的 SSTable 达到一定的阈值时，将多个 SSTable 合并成一个更大的 SSTable，写入到 Level 1的 SSTable 中。
  • 以此类推，直到最后一个 Level，这个 Level 的 SSTable 的大小是固定的。
  • 从 level1到 leveln， 每个层级内的 SSTable 文件之间通常是有序的，但是不同层级之间的 SSTable 文件之间未必是有序的。

小结#

回头看，这套设计的每个部件都是在补前一个方案的短板：Append-Only Log 用顺序写换来写入性能和可恢复性，代价是内存索引和无序；MemTable + SSTable 补上有序性，WAL 补上崩溃恢复；Compaction 清理重复数据，又带来 Write Amplification；分层组织是在写放大、读放大、空间放大之间做权衡，并不消除这些代价。