日志结构合并树是一种巧妙的数据结构, 它是一种妥协的艺术: 它在关注写性能的同时也尽量照顾到了读性能, 适用于写多读少、写多读中等的场景, 甚至在一些数据库产品中直接将其作为核心存储引擎 (如 TiDB -> TiKV 基于 RocksDB);
因此很有必要学习一下 LSM-Tree 的原理;
B+ 树 (如数据库索引) 和 log append 型操作 (如数据库 WAL 日志) 是数据读写效率的两个极端; 磁盘读写分为随机读写和顺序读写，一般来说随机读写的效率要低于顺序读写。
- B+ 树解决的是磁盘随机读慢的问题, 但随机写无法保证效率, 因为写入数据时涉及到树的重构: 读效率高而写效率差;
- log append 型文件操作解决的是磁盘随机写慢的问题, 但读时需要遍历整个文件: 写效率高而读效率差;
为了在排序和 log append 型文件操作之间做个折中, 就引入了 Log-Structed Merge Tree 模型, LSM Tree 既有日志型的文件操作提升写效率, 又在每个 sstable 中排序保证了查询效率;
LSM-Tree 的数据结构
WAL
MemTable
SST (Sorted String Table)
LSM-Tree 的压缩
在 LSM-Tree 中，压缩算法主要有两种策略：Tiering 和 Leveling, 它们的区别主要体现在如何组织和管理不同层级的数据，以及如何执行合并操作;
Tiering
Tiering 策略允许每一层（Level）包含多个 SSTable，并且每一层的 SSTable 之间可以有重叠的键范围。压缩操作主要发生在同一层内，将多个小的 SSTable 合并成一个更大的 SSTable，然后将其推送到下一层。
特点:
- 写放大较低：由于每一层可以包含多个 SSTable，压缩操作不需要频繁地将数据向下层移动，因此写放大（Write Amplification）较低。
- 读放大较高：由于每一层的 SSTable 之间可能有重叠的键范围，查询时可能需要检查多个 SSTable，导致读放大（Read Amplification）较高。
- 空间放大较高：每一层可能包含多个 SSTable，且这些 SSTable 之间可能有重复的数据，因此空间放大（Space Amplification）较高。
适用场景:
- Tiering 适合写密集型工作负载，尤其是对写性能要求较高的场景。
Leveling
Leveling 策略要求每一层（Level）只能包含一个 SSTable，并且每一层的 SSTable 的键范围不重叠。压缩操作主要发生在相邻的两层之间，将上层的 SSTable 与下层的 SSTable 合并，生成一个新的 SSTable 并推送到下层。
特点:
- 写放大较高：由于每一层只能包含一个 SSTable，压缩操作需要频繁地将数据向下层移动，导致写放大较高。
- 读放大较低：由于每一层的 SSTable 之间没有重叠的键范围，查询时通常只需要检查一个 SSTable，因此读放大较低。
- 空间放大较低：每一层只有一个 SSTable，且键范围不重叠，因此空间放大较低。
适用场景:
- Leveling 适合读密集型工作负载，尤其是对读性能要求较高的场景。
策略对比
| 特性 | Tiering | Leveling |
|---|---|---|
| 写放大 | 较低 | 较高 |
| 读放大 | 较高 | 较低 |
| 空间放大 | 较高 | 较低 |
| 适用场景 | 写密集型工作负载 | 读密集型工作负载 |
| 压缩策略 | 同一层内合并多个 SSTable | 相邻层之间合并 SSTable |
| SSTable 重叠 | 允许同一层内 SSTable 键范围重叠 | 不允许同一层内 SSTable 键范围重叠 |
混合策略:
在实际应用中，有些系统会采用 混合策略，结合 Tiering 和 Leveling 的优点。例如，在较低的层级使用 Tiering 以减少写放大，而在较高的层级使用 Leveling 以降低读放大和空间放大。
通过选择合适的压缩策略，LSM-Tree 可以在不同的工作负载下实现性能的优化。
