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的SSTable的大小是固定的。当一个Level的SSTable达到一定的阈值时，将多个SSTable合并成一个更大的SSTable。这样可以减少Write Amplification。

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