LSM树（Log-Structured Merge Tree）原理与实现

题目描述
LSM树是一种高性能的写入优化数据结构，广泛应用于现代NoSQL数据库（如LevelDB、RocksDB、Cassandra）和存储系统中。与传统的B+树等原地更新数据结构不同，LSM树通过将随机写入转换为顺序写入来提升写入吞吐量，同时支持范围查询和点查询。面试中常考察其设计思想、层次结构、合并策略及读写流程。

一、LSM树的设计动机

1. 传统B+树的写入瓶颈：

   • B+树采用原地更新策略，每次写入可能需修改磁盘随机位置的数据页，导致大量随机I/O。
   • 机械硬盘随机I/O性能远低于顺序I/O（可能差100倍以上），成为系统瓶颈。

2. LSM树的核心思想：

   • 将随机写入缓冲在内存中，达到一定规模后批量顺序写入磁盘，最大化利用磁盘顺序I/O性能。
   • 通过后台合并操作（Compaction）管理多层级数据，保证查询效率。

二、LSM树的基本结构
LSM树分为内存部分和磁盘部分，典型层次如下：

1. MemTable（内存表）：

   • 使用跳表（SkipList）或平衡树等有序结构，支持快速插入和范围查询。
   • 所有写入首先追加到写前日志（Write-Ahead Log, WAL）用于崩溃恢复，再插入MemTable。

2. Immutable MemTable（不可变内存表）：

   • 当MemTable写满时，将其设为只读状态，并创建新的MemTable接收写入。
   • 只读的MemTable可被后台线程异步刷盘，避免阻塞写入。

3. 磁盘层级（SSTable系列）：

   • SSTable（Sorted String Table）：磁盘上的有序键值对文件，按键排序存储。
   • 数据被划分为多个层级（如L0, L1, L2...），每层容量随层级指数增长（如L1是L0的10倍）。
   • 低层级SSTable可能包含重复或已删除的键，高层级通过合并过程逐步消除冗余。

三、LSM树的写入流程

1. 写入请求首先追加到WAL（保证持久化），再插入MemTable。
2. 当MemTable大小达到阈值（如64MB）：
   • 当前MemTable转为Immutable MemTable，新建MemTable接收新写入。
   • 后台线程将Immutable MemTable刷盘为L0层的SSTable文件。
3. 磁盘层级通过合并操作（Compaction） 管理：
   • 当某一层SSTable数量或总大小超限时，触发合并。
   • 合并过程选择本层部分SSTable与下一层重叠键范围的SSTable进行归并排序，生成新的SSTable推入下一层。

四、LSM树的查询流程

1. 点查询（Point Query）：

   • 首先查询MemTable → 若未找到，查询Immutable MemTable → 若未找到，按磁盘层级从低到高查询。
   • 每层可能包含多个SSTable，需使用布隆过滤器（Bloom Filter） 快速跳过不可能包含目标键的文件。
   • 找到键后立即返回（高层级数据更新，因此优先低层级）。

2. 范围查询（Range Query）：

   • 合并遍历MemTable、Immutable MemTable及各层SSTable，利用其有序特性进行多路归并。

五、合并策略（Compaction）

1. Size-Tiered Compaction：

   • 每层允许存在多个大小相近的SSTable，当数量达到阈值时合并为一个更大的SSTable推入下一层。
   • 优点：写放大较低；缺点：空间放大明显（重复数据多）。

2. Leveled Compaction：

   • 每层SSTable的键范围不重叠（除L0外），合并时仅选择少量SSTable与下一层重叠部分合并。
   • 优点：读性能高、空间放大小；缺点：写放大较严重。

六、LSM树的优缺点

• 优点：
  • 高写入吞吐量（顺序I/O替代随机I/O）。
  • 天然支持削峰填谷，适应突发写入场景。
• 缺点：
  • 读操作可能需多次I/O（多层级查询）。
  • 合并操作可能引发写放大（Write Amplification）和I/O竞争。

七、优化技巧

1. 为每个SSTable配备布隆过滤器，减少无效磁盘访问。
2. 使用分段合并（Partial Compaction）降低I/O压力。
3. 在SSD环境下调整合并策略，平衡读写性能。

通过以上步骤，LSM树以追加写和后台合并为核心机制，在牺牲部分读性能的前提下，显著提升了写入效率，成为大数据存储系统的基石之一。