这篇文章结合 Leveldb 的读写过程来进一步讲解 LSM-Tree 。

LSM 组成部分

一个LSM（Log-structured merge）存储引擎通常包含三个部分：

  1. 预写日志（Write-ahead log）：预写日志是一种用于恢复临时数据的机制。在进行任何修改操作之前，系统会先将这些操作写入预写日志。如果系统在修改操作完成之前崩溃，那么在系统重启后，可以通过预写日志来恢复这些未完成的修改操作。

  2. 磁盘上的SST（Sorted String Table）：SST是一种用于维护LSM-tree结构的文件格式。在LSM-Tree中，数据首先被写入内存中的MemTable，当MemTable达到一定大小后，会将其内容排序，并写入到磁盘上形成一个SST文件。

  3. 内存中的Mem-table：Mem-table是一种内存数据结构，用于批量小写入。当有新的写入操作时，LSM-Tree首先将这些操作存储在内存中的MemTable中。当MemTable达到一定大小后，LSM-Tree会将其内容排序，并写入到磁盘上，形成一个SST文件。

写入过程

LSM（Log-structured merge）的写路径包含四个步骤：

  1. 将键值对写入预写日志：预写日志（Write-ahead log，简称WAL）是一种用于恢复临时数据的机制。在进行任何修改操作之前，系统会先将这些操作写入预写日志。如果系统在修改操作完成之前崩溃，那么在系统重启后，可以通过预写日志来恢复这些未完成的修改操作。这种机制可以保证系统在面临突然崩溃时，不会丢失未完成的写入操作。

  2. 将键值对写入memtable：Memtable是一种内存中的数据结构，用于暂时存储写入操作。当有新的写入操作时，LSM-Tree首先将这些操作存储在内存中的MemTable中。完成预写日志和MemTable的写入后，我们可以通知用户写操作已完成。这是因为即使此时系统崩溃，由于预写日志的存在，我们仍然可以恢复这些写入操作。

  3. 当一个mem-table满了，我们将它们冻结为不可变的mem-table，并在后台将它们刷新到磁盘作为SST文件：当MemTable达到一定大小后，LSM-Tree会将其内容排序，并写入到磁盘上，形成一个SST（Sorted String Table）文件。这个过程通常在后台进行，不会阻塞新的写入操作。这种设计可以减少磁盘I/O操作，从而提高写入性能。

  4. 引擎将在某些级别的一些文件压缩到较低的级别，以保持LSM树的良好形状，使得读放大率低：这个过程通常被称为压缩（Compaction）。压缩是LSM-Tree中的一个后台任务，它的主要作用是合并多个SST文件，并在这个过程中应用之前延迟的更新和删除操作。通过压缩，我们可以保持LSM-Tree的良好形状，使得读放大率低。读放大率是指执行一次读操作需要读取的数据块数量。如果LSM-Tree的形状良好，那么我们可以在读取一次数据时，尽可能地减少需要读取的数据块数量，从而提高读取性能。

读取过程

在LSM（Log-structured merge）中，读取一个键的过程包含两个步骤：

  1. 我们首先会探测所有的mem-table，从最新的到最旧的：在LSM中，新的写入操作首先被存储在内存中的MemTable中。因此，当我们想要读取一个键时，我们首先会在MemTable中查找这个键。由于新的写入操作被存储在最新的MemTable中，所以我们会从最新的MemTable开始查找，然后依次向旧的MemTable查找。

  2. 如果键未找到，我们将搜索包含SST的整个LSM树以找到数据：如果在所有的MemTable中都没有找到这个键，那么我们会在磁盘上的SST文件中查找这个键。SST文件是LSM中的一种文件格式，用于存储已经从MemTable写入到磁盘上的数据。在SST文件中，数据被存储在一个树形结构中，这个树形结构被称为LSM树。我们会在LSM树中查找这个键，直到找到这个键，或者确定这个键不存在。

在LSM中，有两种类型的读取操作：查找和扫描。

  • 查找：查找操作是指在LSM树中查找一个特定的键。在查找操作中，我们会按照上述的步骤，从MemTable和SST文件中查找这个键。

  • 扫描：扫描操作是指在存储引擎中迭代一个范围内的所有键。在扫描操作中，我们会首先在MemTable中迭代这个范围内的所有键，然后在SST文件中迭代这个范围内的所有键。由于LSM树的特性，我们可以在扫描操作中高效地迭代一个范围内的所有键。