目录
什么是LSM树
磁盘结构与顺序IO
LSM树结构
LSM树的写入
SSTable合并
LSM树的读取
LSM树的删除
总结
什么是LSM树
LSM 树全名日志结构合并树（Log-Structured Merge Tree），是一种用于存储和管理数据的树状数据结构，常用于写频繁数据库中。
MYSQL 中常用 B+ 树组织数据结构，但实际上 B+ 树并不适合写频繁的场景 ，在 B + 树中，当插入或删除数据导致节点数据量超出上限或低于下限，就需要进行节点的分裂或合并操作。
- 当向一个已满的叶子节点插入新数据时，需要将节点分裂为两个，并调整相关指针和索引。
- 当删除操作使节点数据量过少时，可能需要与相邻节点合并，同样也会带来较大的开销。
在写频繁场景下，LSM树更适合组织数据，LSM树的核心思想是利用顺序IO提高效率。
磁盘结构与顺序IO
一个机械磁盘的结构如下：
其中存储与读取相关的结构抽象出来如下图：
- 盘片：是磁盘存储数据的基础，一般由铝合金或玻璃等材料制成，表面涂有一层磁性材料。数据就以磁化的形式存储在这些盘片上，通常一个机械磁盘会包含多个盘片，它们叠放在一起，共同旋转。
- 磁头：负责在盘片上读写数据，每个盘片的上下两面都有对应的磁头。磁头通过移动到不同的位置来访问盘片上的不同区域。在工作时，磁头与盘片表面保持非常小的间隙，通过感应盘片上磁性材料的变化来读取数据，或者通过改变磁性材料的状态来写入数据。
- 磁道：盘片表面被划分成许多同心圆，这些同心圆就称为磁道。每个磁道都可以存储一定量的数据，从盘片的中心向外，磁道的长度逐渐增加，但存储的数据量是相同的。
- 扇区：每个磁道又被进一步划分为若干个相等的部分，每个部分称为一个扇区。扇区是磁盘存储数据的基本单位，通常每个扇区的大小为 512 字节。
- 柱面：由各个盘片上相同位置的磁道组成的一个假想的圆柱体，在进行数据读写时，磁头可以在同一柱面的不同盘片的磁道之间快速切换，而无需移动到其他位置，从而提高数据访问效率。
当磁盘进行IO时，需要先进行寻道，磁盘由多个盘片组成，每个盘片又被划分为多个同心圆磁道，数据就存储在这些磁道上。当需要读取数据时，首先要将磁头移动到目标数据所在的磁道上。这一过程由磁盘的寻道机构负责，寻道机构根据目标数据的逻辑地址计算出磁头需要移动的距离和方向，然后通过电机驱动磁头臂移动，使磁头定位到目标磁道。
磁头定位到目标磁道后，需要等待目标数据块旋转到磁头下方。因为磁盘在不断地旋转，数据是按一定顺序存储在磁道上的。磁盘的旋转速度通常以每分钟转数（RPM）来衡量，常见的硬盘转速有 5400RPM、7200RPM 等。在等待过程中，磁盘控制器会不断监测磁盘的旋转位置，当目标数据块即将到达磁头下方时，就准备进行数据读取。
当磁头定位到目标位置后，磁盘控制器会向磁头发送电信号，磁头根据这些信号改变磁场，从而在盘片的磁性涂层上记录数据。数据以二进制的形式被编码为磁道上的磁化方向变化。数据写入完成后，磁盘会进行写入验证。磁头会立即读取刚刚写入的数据，并与原始要写入的数据进行比较，检查是否存在错误。
如果验证发现错误，磁盘控制器会尝试重新写入数据，或者向操作系统报告写入错误。如果验证成功，磁盘控制器会向操作系统发送写入完成的确认信号。
上面的过程实际上最耗时的操作就是寻道与定位的过程，因为磁盘的旋转结构与磁头的寻道结构是机械结构。那么如何缩短IO的时间？只需要减少定位的时间就能大大提升IO的效率。
在顺序 I/O 中，数据是按顺序存储的，当磁头定位到第一个数据块后，后续的数据块会很快旋转到磁头下方，减少了等待数据块旋转的时间。
假设要读取一个由多个相邻扇区组成的大文件，磁头在找到文件的起始扇区后，随着磁盘的旋转，后续的扇区会迅速经过磁头，使得数据能够快速地被读取出来，降低了旋转延迟带来的时间损耗。
同时操作系统和存储设备也会采用预读策略来优化顺序 I/O 性能。由于顺序 I/O 具有很强的规律性，系统可以预测到接下来要访问的数据块，提前将这些数据从存储设备读取到内存缓冲区中。
比如，当应用程序顺序读取一个文本文件时，系统会自动预读文件中尚未被请求但后续可能会用到的数据块。当应用程序需要访问这些数据时，数据已经在内存缓冲区中，直接从内存中读取数据比从存储设备读取要快得多，从而缩短了 I/O 时间。
通常情况下，顺序IO的效率是随机IO的40-400倍。那么LSM是如何利用顺序IO的呢？
LSM树结构
LSM树并不是严格的树结构，而是一种存储结构。通过牺牲部分读性能，来提升写性能。整体结构如下图：
内存部分：
- Active MemTable：活跃的内存表，用于接收写入的数据。新写入的数据首先进入这里，因为在内存中操作，所以写入速度很快。当 Active MemTable 达到一定大小（Full）后，会转换为 Immutable MemTable。
- Immutable MemTable：不可变内存表，由 Active MemTable 转换而来。此时不能再向其写入新数据，等待被刷写到磁盘。读取操作会同时查找 Active MemTable 和 Immutable MemTable。
- Block Cache：块缓存，用于缓存从磁盘读取的数据块，加快后续的读取操作。如果读取的数据在缓存中命中，就无需访问磁盘，提高了读取效率。
磁盘部分：
- WAL（Write - Ahead Log）：预写日志，用于保证数据的持久性。在数据写入 Active MemTable 之前，会先写入 WAL，这样在系统崩溃时可以通过 WAL 恢复数据。
- SS Table（Sorted String Table）：有序字符串表，是 LSM 树在磁盘上的存储结构。Immutable MemTable 被刷写到磁盘后会形成 SS Table。不同层级（Level 1、Level 2、Level 3 等）的 SS Table 大小和数量不同，层级越高，包含的数据量越大，且数据是有序的。
- Compaction：合并操作，随着写入的进行，磁盘上会产生多个 SS Table，为了减少数据冗余和提高读取效率，会定期进行合并操作，将多个 SS Table 合并成一个，并移除过期和重复的数据。
LSM树的写入
当有新数据写入时，首先会将数据写入到内存中的 MemTable（内存表）。写入之前会记录操作在此磁盘WAL日志文件中， MemTable 通常是基于某种数据结构实现，如跳表或哈希表，以便快速地进行插入和查找操作。在 MemTable 中，数据按照键值对的形式存储，新写入的数据会被添加到 MemTable 的合适位置。
当 MemTable 达到内存阈值后，它会被转换为 Immutable MemTable（不可变内存表），这意味着该 MemTable 不再接受新的写入操作，而是准备被刷写到磁盘。
在将 Immutable MemTable 写入磁盘时，实际上等同于将大量的随机IO转化为批量的顺序 IO 也就提高了写入的效率。
Immutable MemTable 中的数据会被刷写到磁盘上，形成一个 SSTable。SSTable 是 LSM 树在磁盘上存储数据的基本单元写入后就不可修改，其中的数据是按照键排序。同时 SSTable 采用分层设计
L0 层：L0 层的 SSTable 是由内存中的 Immutable MemTable 直接转换而来，它的特点是数据可能存在重叠，即不同的 SSTable 之间可能包含相同键的不同版本数据。每层 SSTable 数量通常有一定的限制，当达到限制时，会触发 L0 层与下一层（L1 层）的合并操作。
L1 及更高层（L2、L3 等）：L1 层及更高层的 SSTable 在数据范围上是不重叠的，每个 SSTable 都覆盖一个连续的键值范围。随着层数的增加，SSTable 的大小通常会逐渐增大，这是因为在合并过程中，会将多个较小的 SSTable 合并成一个较大的 SSTable，以减少磁盘 I/O 和提高查询性能。
SSTable合并
当某一层的 SSTable 数量达到阈值时，会触发合并操作。例如，L0 层的 SSTable 数量超过限制，就需要将 L0 层的 SSTable 与 L1 层的 SSTable 进行合并。在合并过程中，会将多个 SSTable 中的数据读取出来，按照键进行排序和合并，去除重复的数据，生成新的 SSTable，并将其放置到合适的层次。
这样的设计使得越下层的SSTable合并的频率就越少，因为合并操作需要读取和写入大量的数据，可能会占用较多的系统资源和 I/O 带宽，影响系统的性能。而下层的SSTable较大，合并的消耗更大。同时合并操作也可以清理过期数据和重复数据，有效地利用了磁盘空间。
LSM树的读取
当读取时，会先从内存中的 MemTable 开始查找，因为这里的数据是最新的，读取速度也最快。如果在 MemTable 中没有找到，则会按照层级顺序依次在磁盘上的各个 Level 中查找。如果在 MemTable 中没有找到，则会按照层级顺序依次在磁盘上的各个 Level 中查找。这样读取能保证每次读取的都是最新数据。
在每个层级 LSM 树会为每个 SSTable 维护一个布隆过滤器，在查找数据时，首先通过布隆过滤器快速判断目标键值是否可能存在于该 SSTable 中，如果布隆过滤器判断不存在，则可以直接跳过该 SSTable 的查找，减少了不必要的磁盘 I/O 操作。
如果布隆过滤器判断存在，会在 SSTable 中查找，SSTable 中的数据是有序的，所以这个查找可以通过二分查找进行，但每次二分都是一次磁盘IO，为了提高效率我们还可以为每个 SSTable 维护一个稀疏索引，这里就不展开了。
同时为了提高读取性能，LSM 树通常也会结合缓存机制。在内存中设置缓存，用于存储最近读取的数据块或键值对。当有读取请求时，首先检查缓存中是否存在目标数据，如果存在，则直接从缓存中返回，避免了磁盘 I/O 操作，大大提高了读取速度。
LSM树的删除
LSM树的删除操作并不是直接删除数据，而是通过一种叫墓碑标志的特殊数据来标识数据的删除。
删除操作分为：待删除数据在内存中、待删除数据在磁盘中 和 该数据根本不存在 三种情况。
待删除数据在内存中：当执行删除操作时，并不会直接将数据从MemTable中移除，而是为该数据添加一个“墓碑标记”。这个标记就像是一个特殊的标签，用于告诉系统该数据已经被标记为删除。 例如，若要删除键为“key1”的数据，会在MemTable中找到对应的键值对，并为其设置一个删除标记，而不是立即释放存储该键值对的内存空间。这样做的好处是可以避免频繁的内存分配和释放操作，提高删除操作的效率。 当MemTable达到一定的大小或满足其他条件时，会将其刷写到磁盘上的SSTable中，带有“墓碑标记”的数据也会被写入SSTable。
待删除数据在磁盘中：对于已经存储在磁盘SSTable中的数据，同样是通过“墓碑标记”来进行删除操作。当需要删除某个数据时，不会在相应的SSTable中为该数据添加“墓碑标记”。而是在内存中的 MemTable 插入一个墓碑标志。后续在进行SSTable的合并或压缩操作时，带有“墓碑标记”的数据不会被复制到新的SSTable中，从而实现了数据的逻辑删除。但在合并或压缩操作之前，带有“墓碑标记”的数据仍然会占用磁盘空间。
该数据根本不存在：当执行删除操作时，如果发现要删除的数据在LSM树中根本不存在，那么这个删除操作实际上是一个“空操作”，不会执行。
总结
LSM 树的设计思想是将对数据的修改增量保存在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘，而不是像传统的 B + 树那样每次修改都直接写入磁盘。这样可以减少磁盘随机写操作，将其转化为顺序写操作，从而提高写性能。
LSM 树通常由内存中的数据结构和磁盘上的多层有序文件组成。内存中的数据结构 MemTable用于暂存最近的写入操作。当 MemTable 达到一定大小后，会被转换为一个 Immutable MemTable，然后写入磁盘成为一个 SSTable（Sorted String Table）。磁盘上的 SSTable 按照一定的层次结构组织，层次越高，SSTable 越大，数据越旧。
新的数据写入时，首先写入到内存中的 MemTable。因为是在内存中操作，所以写入速度非常快。当 MemTable 的大小达到预先设定的阈值时，会被冻结成 Immutable MemTable，此时可以继续接收新的写入请求并写入新的 MemTable。Immutable MemTable 随后会被异步地写入磁盘，形成一个新的 SSTable。
读取数据时，需要依次从内存中的 MemTable、Immutable MemTable 以及磁盘上的各级 SSTable 中查找。由于新的数据优先保存在内存中，所以大部分情况下可以快速找到数据。如果在内存中未找到，则按照层次从低到高在磁盘上的 SSTable 中查找，直到找到数据或者确定数据不存在。
LSM 树通过牺牲一定的读取性能来换取高效的写入性能，并且通过合理的合并策略来平衡读写性能，是一种在现代存储系统中广泛应用的数据结构。适合写多读少的应用场景，如日志系统、时间序列数据库、分布式键值存储系统（如 LevelDB、RocksDB 等）。这些系统通常需要频繁地写入数据，而对读取的实时性要求相对较低，LSM 树的特性可以很好地满足它们的需求。
