LSM Tree（Log-Structured Merge Tree）的概念最早由 Patrick O'Neil 等人在 1996 年的经典论文《The Log-Structured Merge-Tree (LSM-Tree)》[1] 中提出。这篇论文在数据库存储领域具有里程碑意义，为现代 NoSQL 数据库和分布式存储系统奠定了重要的理论基础。
LSM Tree 的核心思想是将随机写入转换为顺序写入，从而充分利用磁盘的顺序访问性能优势。传统的 B+Tree 结构在处理大量写入操作时，由于需要维护树结构的平衡性，往往产生大量的随机 I/O 操作，导致性能瓶颈。
LSM Tree 通过以下设计解决了这个问题：
- 分层存储架构：
- 论文原始描述：将数据分为内存层（C₀）和磁盘层（C₁）
- 现代实现：内存层（MemTable）和多个磁盘层（SSTable Levels） 新数据首先写入内存，然后批量刷写到磁盘
- 顺序写入优化：所有磁盘写入都是顺序的，避免了随机 I/O 的性能损失
- Rolling Merge 算法：通过后台的合并过程，将小文件逐步合并为大文件，保持数据的有序性
论文的主要理论贡献包括：
- 性能分析模型：提供了 LSM Tree 与 B+Tree 的数学性能对比模型
- 写入成本分析：
- B+Tree 写入成本：O(log_B N) 次随机 I/O
- LSM Tree 写入成本：O(1) 次顺序 I/O（前台写入） + 分摊的后台合并成本
- Rolling Merge 算法：设计了高效的多路归并算法，确保数据的有序性和查询效率
这篇论文的影响深远，为后来的许多知名系统提供了理论基础：
- BigTable [2]：Google 的分布式存储系统，采用了 LSM Tree 的核心思想
- LevelDB/RocksDB：广泛使用的单机存储引擎，被众多分布式系统作为底层存储
- Cassandra、HBase：流行的 NoSQL 数据库系统
- 现代时序数据库：如 InfluxDB、TimescaleDB 等
本章详细解析 LSM Tree 的核心设计原理、关键组件实现技术，以及各组件之间的协同工作机制。从整体架构设计到具体的内存管理、磁盘存储、合并算法等实现细节，全面阐述 LSM Tree 的技术实现方案。
LSM Tree 采用分层存储架构，将数据按照访问频率和时间特征进行分层管理：
写入优化策略：
┌─────────────────┐ ┌─────────────────┐ ┌─────────────────┐
│ 随机写入请求 │───→│ 内存缓冲区 │───→│ 顺序刷盘 │
│ │ │ (MemTable) │ │ (SSTable) │
│ 用户写入操作 │ │ 内存中排序存储 │ │ 磁盘顺序写入 │
└─────────────────┘ └─────────────────┘ └─────────────────┘
LSM Tree 采用分层存储架构，每一层都有明确的设计目标：
┌─────────────────────────────────────────────────────────────┐
│ 内存层 (Memory Layer) │
│ ┌─────────────────┐ ┌──────────────────┐ │
│ │ Active MemTable │ │Immutable MemTable│ │
│ │ (可写) │ │ (只读) │ │
│ │ 64MB 阈值 │ │ 等待刷盘 │ │
│ └─────────────────┘ └──────────────────┘ │
└─────────────────────────────────────────────────────────────┘
│
▼ 刷盘操作
┌─────────────────────────────────────────────────────────────┐
│ 磁盘层 (Disk Layer) │
│ │
│ Level 0: ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ │
│ │SST-1 │ │SST-2 │ │SST-3 │ │SST-4 │ (可重叠) │
│ └──────┘ └──────┘ └──────┘ └──────┘ │
│ │ │
│ ▼ Compaction │
│ Level 1: ┌──────┐ ┌──────┐ ┌──────┐ │
│ │SST-5 │ │SST-6 │ │SST-7 │ (无重叠) │
│ └──────┘ └──────┘ └──────┘ │
│ │ │
│ ▼ Compaction │
│ Level 2: ┌──────┐ ┌──────┐ │
│ │SST-8 │ │SST-9 │ (无重叠，更大) │
│ └──────┘ └──────┘ │
└─────────────────────────────────────────────────────────────┘
为了更好地理解 LSM Tree 各组件之间的协作关系，下面展示完整的系统架构图：
┌─────────────────────────────────────────────────────────────────────────────────┐
│ LSM Tree 整体系统架构 │
│ │
│ ┌─────────────────┐ ┌─────────────────┐ ┌─────────────────┐ │
│ │ 客户端接口 │ │ 读写协调器 │ │ 版本管理器 │ │
│ │ ┌─────────────┐ │ │ ┌─────────────┐ │ │ ┌─────────────┐ │ │
│ │ │ PUT/GET/DEL │ │ │ │ 读写路由 │ │ │ │ MVCC 控制 │ │ │
│ │ │ 批量操作 │ │ │ │ 并发控制 │ │ │ │ 快照管理 │ │ │
│ │ │ 范围查询 │ │ │ │ 一致性保证 │ │ │ │ 事务支持 │ │ │
│ │ └─────────────┘ │ │ └─────────────┘ │ │ └─────────────┘ │ │
│ └─────────────────┘ └─────────────────┘ └─────────────────┘ │
│ │ │ │ │
│ └───────────────────────┼───────────────────────┘ │
│ │ │
│ ┌────────────────────────────────┼────────────────────────────────────────┐ │
│ │ 核心存储引擎 │ │ │
│ │ ▼ │ │
│ │ ┌─────────────────────────────────────────────────────────────────┐ │ │
│ │ │ 内存表层 (MemTable Layer) │ │ │
│ │ │ │ │ │
│ │ │ ┌─────────────────┐ ┌─────────────────┐ ┌─────────────────┐ │ │ │
│ │ │ │ Active MemTable │ │Immutable MemTable│ │ WAL 日志 │ │ │ │
│ │ │ │ ┌─────────────┐ │ │ ┌─────────────┐ │ │ ┌─────────────┐ │ │ │ │
│ │ │ │ │ SkipList │ │ │ │ SkipList │ │ │ │ 顺序日志 │ │ │ │ │
│ │ │ │ │ 64MB 阈值 │ │ │ │ 等待刷盘 │ │ │ │ 持久化保证 │ │ │ │ │
│ │ │ │ │ 可读写 │ │ │ │ 只读状态 │ │ │ │ 崩溃恢复 │ │ │ │ │
│ │ │ │ └─────────────┘ │ │ └─────────────┘ │ │ └─────────────┘ │ │ │ │
│ │ │ └─────────────────┘ └─────────────────┘ └─────────────────┘ │ │ │
│ │ └─────────────────────────────────────────────────────────────────┘ │ │
│ │ │ │ │
│ │ ▼ 刷盘操作 (Flush) │ │
│ │ ┌─────────────────────────────────────────────────────────────────┐ │ │
│ │ │ 磁盘层 (Disk Layer) │ │ │
│ │ │ │ │ │
│ │ │ Level 0: ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ │ │ │
│ │ │ │SST-1 │ │SST-2 │ │SST-3 │ │SST-4 │ (可重叠) │ │ │
│ │ │ │+BF │ │+BF │ │+BF │ │+BF │ │ │ │
│ │ │ └──────┘ └──────┘ └──────┘ └──────┘ │ │ │
│ │ │ │ │ │ │
│ │ │ ▼ Compaction │ │ │
│ │ │ Level 1: ┌──────┐ ┌──────┐ ┌──────┐ │ │ │
│ │ │ │SST-5 │ │SST-6 │ │SST-7 │ (无重叠) │ │ │
│ │ │ │+BF │ │+BF │ │+BF │ │ │ │
│ │ │ └──────┘ └──────┘ └──────┘ │ │ │
│ │ │ │ │ │ │
│ │ │ ▼ Compaction │ │ │
│ │ │ Level 2: ┌──────┐ ┌──────┐ │ │ │
│ │ │ │SST-8 │ │SST-9 │ (无重叠，更大) │ │ │
│ │ │ │+BF │ │+BF │ │ │ │
│ │ │ └──────┘ └──────┘ │ │ │
│ │ │ │ │ │
│ │ │ 注：BF = Bloom Filter，每个 SSTable 都包含布隆过滤器 │ │ │
│ │ └─────────────────────────────────────────────────────────────────┘ │ │
│ └────────────────────────────────────────────────────────────────────────┘ │
│ │
│ ┌─────────────────────────────────────────────────────────────────────────┐ │
│ │ 后台服务层 (Background Services) │ │
│ │ │ │
│ │ ┌─────────────────┐ ┌─────────────────┐ ┌─────────────────┐ │ │
│ │ │ Compaction 引擎 │ │ 监控诊断 │ │ 资源管理 │ │ │
│ │ │ ┌─────────────┐ │ │ ┌─────────────┐ │ │ ┌─────────────┐ │ │ │
│ │ │ │ 触发策略 │ │ │ │ 性能指标 │ │ │ │ 内存控制 │ │ │ │
│ │ │ │ 调度算法 │ │ │ │ 健康检查 │ │ │ │ I/O 限流 │ │ │ │
│ │ │ │ 并发控制 │ │ │ │ 告警机制 │ │ │ │ 线程池管理 │ │ │ │
│ │ │ └─────────────┘ │ │ └─────────────┘ │ │ └─────────────┘ │ │ │
│ │ └─────────────────┘ └─────────────────┘ └─────────────────┘ │ │
│ └─────────────────────────────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────────────────────────────┘
MemTable 作为 LSM Tree 的内存缓冲区，负责接收写入请求并提供高效的内存数据管理，采用 SkipList 作为核心数据结构。
MemTable 采用 SkipList（跳表）作为核心数据结构，提供高效的插入、查找和范围查询能力。SkipList 是由 William Pugh 在 1990 年提出的概率性数据结构 [3]：
SkipList 多层索引结构
概率性层级分布 | Java ConcurrentSkipListMap 实现限制: 32层 | 生产常用: 12-16层
Level 3: HEAD ─────────────────────────────────────────────────────────────→ NULL
│
▼
Level 2: HEAD ───────────────────────────→ [30] ───────────────────────────→ NULL
│ │
▼ ▼
Level 1: HEAD ──────→ [10] ──────────────→ [30] ──────────────→ [50] ──────→ NULL
│ │ │ │
▼ ▼ ▼ ▼
Level 0: HEAD → [5] → [10] → [15] → [20] → [30] → [35] → [40] → [50] → [60] → NULL
节点结构详解:
┌─────────────────────────────────────────────────────────────────────────┐
│ SkipList 节点结构 │
│ │
│ ┌─────────────────┐ │
│ │ 节点 [30] │ │
│ │ ┌─────────────┐ │ forward[3] ──→ NULL │
│ │ │ Key: 30 │ │ forward[2] ──→ NULL │
│ │ │ Value: ... │ │ forward[1] ──→ [50] │
│ │ │ Version: v1 │ │ forward[0] ──→ [35] │
│ │ │ Height: 4 │ │ │
│ │ └─────────────┘ │ 注：forward[i] 指向第i层的下一个节点 │
│ └─────────────────┘ │
└─────────────────────────────────────────────────────────────────────────┘
查找过程示例 (查找 key = 35):
- 从 Level 3 开始: HEAD → NULL (当前层无节点，下降到 Level 2)
- Level 2: HEAD → [30] → NULL (35 > 30，且节点[30] 的下一个节点是 NULL，因此从节点[30]下降到 Level 1)
- Level 1: [30] → [50] (35 < 50，因此从节点[30]下降到 Level 0)
- Level 0: 从[30]开始向右遍历 → [35] (找到目标节点)
时间复杂度: O(log n)，空间复杂度: O(n)
版本化存储设计：
┌──────────────────────────────────────────────────────────────┐
│ Key: "user:123" │
│ ┌─────────────────┐ ┌─────────────────┐ ┌─────────────────┐│
│ │ Version: 1001 │ │ Version: 1005 │ │ Version: 1010 ││
│ │ Value: "Alice" │ │ Value: "Bob" │ │ Type: DELETE ││
│ │ Type: PUT │ │ Type: PUT │ │ Value: null ││
│ │ Timestamp: T1 │ │ Timestamp: T2 │ │ Timestamp: T3 ││
│ └─────────────────┘ └─────────────────┘ └─────────────────┘│
└──────────────────────────────────────────────────────────────┘
版本管理策略：
- 单调递增序列号：保证版本顺序
- MVCC 支持：支持快照读取
- 删除标记：使用 Tombstone 标记删除
- 时间戳索引：支持时间范围查询
内存管理策略：
┌─────────────────────────────────────────────────────────────┐
│ MemTable 内存分配： │
│ │
│ ┌─────────────────┐ 阈值检查 ┌───────────────────┐ │
│ │ Active MemTable │ ────────────→ │Immutable MemTable │ │
│ │ 当前大小: 45MB │ 64MB 触发 │ 大小: 64MB │ │
│ │ 状态: 可写 │ │ 状态: 只读 │ │
│ └─────────────────┘ └──────────────────┘ │
│ │ │ │
│ ▼ 继续写入 ▼ 后台刷盘 │
│ ┌─────────────────┐ ┌─────────────────┐ │
│ │ 新 MemTable │ │ SSTable 文件 │ │
│ │ 大小: 0MB │ │ Level 0 │ │
│ └─────────────────┘ └─────────────────┘ │
└─────────────────────────────────────────────────────────────┘
内存管理参数：
| 参数 | 默认值 | 作用 | 调优建议 |
|---|---|---|---|
| MemTable 大小阈值 | 64MB | 触发刷盘操作 | 根据内存容量调整 |
| Immutable 队列长度 | 2-3 个 | 控制内存使用 | 避免内存溢出 |
| 写入缓冲区大小 | 4KB | 批量写入优化 | 根据写入模式调整 |
| 内存分配器 | jemalloc | 减少内存碎片 | 生产环境推荐 |
SSTable（Sorted String Table）作为 LSM Tree 的持久化存储格式，采用有序、不可变的设计，提供高效的磁盘数据组织和快速查找能力。
SSTable（Sorted String Table）采用分块存储和多级索引的文件格式：
SSTable 文件结构详解
┌────────────────────────────────────────────────────────────────────────────┐
│ SSTable 文件布局 │
│ │
│ 偏移量 0 ┌─────────────────────────────────────────────────────────┐ │
│ │ 文件头 (File Header) │ │
│ │ ┌─────────────────────────────────────────────────────┐ │ │
│ │ │ Magic Number │ 0x12345678 (4 bytes) │ │ │
│ │ │ Version │ 1.0 (4 bytes) │ │ │
│ │ │ Compression │ LZ4/Snappy/None (4 bytes) │ │ │
│ │ │ Block Size │ 4KB/8KB/16KB (4 bytes) │ │ │
│ │ │ Key Count │ 总键值对数量 (8 bytes) │ │ │
│ │ │ Min Key │ 最小键值 (变长) │ │ │
│ │ │ Max Key │ 最大键值 (变长) │ │ │
│ │ └─────────────────────────────────────────────────────┘ │ │
│ └─────────────────────────────────────────────────────────┘ │
│ │ │
│ 偏移量 N ┌─────────────────────────▼───────────────────────────────┐ │
│ │ 数据块区域 (Data Blocks) │ │
│ │ │ │
│ │ ┌─────────────────┐ ┌─────────────────┐ ┌─────────────┐ │ │
│ │ │ Block 1 │ │ Block 2 │ │ Block N │ │ │
│ │ │ ┌─────────────┐ │ │ ┌─────────────┐ │ │ ┌─────────┐ │ │ │
│ │ │ │Block Header │ │ │ │Block Header │ │ │ │Block Hdr│ │ │ │
│ │ │ │- Entry Count│ │ │ │- Entry Count│ │ │ │- Entries│ │ │ │
│ │ │ │- Restart Pts│ │ │ │- Restart Pts│ │ │ │- Restart│ │ │ │
│ │ │ ├─────────────┤ │ │ ├─────────────┤ │ │ ├─────────┤ │ │ │
│ │ │ │Key1│Value1 │ │ │ │Key5│Value5 │ │ │ │KeyN│ValN│ │ │ │
│ │ │ │Key2│Value2 │ │ │ │Key6│Value6 │ │ │ │...│... │ │ │ │
│ │ │ │Key3│Value3 │ │ │ │Key7│Value7 │ │ │ │ │ │ │ │ │
│ │ │ │Key4│Value4 │ │ │ │Key8│Value8 │ │ │ │ │ │ │ │ │
│ │ │ ├─────────────┤ │ │ ├─────────────┤ │ │ ├─────────┤ │ │ │
│ │ │ │Block Trailer│ │ │ │Block Trailer│ │ │ │Block Trl│ │ │ │
│ │ │ │- Checksum │ │ │ │- Checksum │ │ │ │- Chksum │ │ │ │
│ │ │ └─────────────┘ │ │ └─────────────┘ │ │ └─────────┘ │ │ │
│ │ └─────────────────┘ └─────────────────┘ └─────────────┘ │ │
│ └─────────────────────────────────────────────────────────┘ │
│ │ │
│ 偏移量 M ┌─────────────────────────▼───────────────────────────────┐ │
│ │ 索引块 (Index Block) │ │
│ │ ┌─────────────────────────────────────────────────────┐ │ │
│ │ │ Block 1 Index │ Offset: 1024, Size: 4096, LastKey │ │ │
│ │ │ Block 2 Index │ Offset: 5120, Size: 4096, LastKey │ │ │
│ │ │ Block N Index │ Offset: XXXX, Size: YYYY, LastKey │ │ │
│ │ └─────────────────────────────────────────────────────┘ │ │
│ └─────────────────────────────────────────────────────────┘ │
│ │ │
│ 偏移量 P ┌─────────────────────────▼───────────────────────────────┐ │
│ │ 布隆过滤器 (Bloom Filter) │ │
│ │ ┌─────────────────────────────────────────────────────┐ │ │
│ │ │ Filter Header │ Hash函数数量, 位数组大小 │ │ │
│ │ │ Bit Array │ [0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0] │ │ │
│ │ │ Hash Config │ MurmurHash3, CityHash配置 │ │ │
│ │ └─────────────────────────────────────────────────────┘ │ │
│ └─────────────────────────────────────────────────────────┘ │
│ │ │
│ 偏移量 Q ┌─────────────────────────▼───────────────────────────────┐ │
│ │ 文件尾 (File Footer) │ │
│ │ ┌─────────────────────────────────────────────────────┐ │ │
│ │ │ Index Offset │ 索引块起始位置 (8 bytes) │ │ │
│ │ │ Index Size │ 索引块大小 (8 bytes) │ │ │
│ │ │ Filter Offset │ 过滤器起始位置 (8 bytes) │ │ │
│ │ │ Filter Size │ 过滤器大小 (8 bytes) │ │ │
│ │ │ Data Checksum │ 数据校验和 (8 bytes) │ │ │
│ │ │ Footer Checksum │ 文件尾校验和 (8 bytes) │ │ │
│ │ └─────────────────────────────────────────────────────┘ │ │
│ └─────────────────────────────────────────────────────────┘ │
└────────────────────────────────────────────────────────────────────────────┘
读取流程示例 (查找 Key = "user123"):
- 读取文件尾 → 获取索引块和过滤器位置
- 检查布隆过滤器 → 判断 Key 可能存在
- 二分查找索引块 → 定位目标数据块
- 读取数据块 → 在块内二分查找 Key
- 返回 Value 或 NotFound
性能特性:
- 顺序写入: O(1) 追加写入
- 随机读取: O(log n) 二分查找
- 空间效率: 压缩率 60-80%
- 缓存友好: 块级别预读
SSTable 采用三级索引结构，实现高效的数据定位：
- 文件级索引：快速定位目标文件
- 块级索引：在文件内快速定位数据块
- 块内搜索：在数据块内进行二分查找
| 压缩算法 | 压缩比 | 压缩速度 | 解压速度 | 适用场景 |
|---|---|---|---|---|
| LZ4 [4] | 2.1x | 很快 | 很快 | 低延迟要求 |
| Snappy [5] | 2.5x | 快 | 快 | 均衡性能 |
| ZSTD [6] | 3.2x | 中等 | 快 | 高压缩比要求 |
| GZIP | 3.8x | 慢 | 中等 | 存储空间敏感 |
| 无压缩 | 1.0x | 最快 | 最快 | 高性能要求 |
WAL（Write-Ahead Log）机制通过预写日志保证数据持久性和崩溃恢复能力，确保系统在异常情况下数据不丢失。
WAL 通过预写日志保证数据持久性，确保系统崩溃时数据不丢失：
WAL 日志记录格式详解
┌────────────────────────────────────────────────────────────────────────────┐
│ WAL 记录完整结构 │
│ │
│ 偏移量 0 ┌─────────────────────────────────────────────────────────┐ │
│ │ 记录头 (Record Header) │ │
│ │ ┌─────────────────────────────────────────────────────┐ │ │
│ │ │ Magic Number │ 0xWAL1 (4 bytes) - 格式标识 │ │ │
│ │ │ LSN │ 1001 (8 bytes) - 日志序列号 │ │ │
│ │ │ Record Type │ 0x01 (1 byte) - PUT/DELETE/COMMIT │ │ │
│ │ │ Transaction ID │ 12345 (8 bytes) - 事务标识 │ │ │
│ │ │ Key Length │ 16 (4 bytes) - 键长度 │ │ │
│ │ │ Value Length │ 1024 (4 bytes) - 值长度 │ │ │
│ │ │ Timestamp │ 1640995200 (8 bytes) - Unix时间戳 │ │ │
│ │ │ Header Checksum │ 0xABCD (4 bytes) - 头部校验和 │ │ │
│ │ └─────────────────────────────────────────────────────┘ │ │
│ └─────────────────────────────────────────────────────────┘ │
│ │ │
│ 偏移量 41 ┌─────────────────────────▼───────────────────────────────┐ │
│ │ 记录体 (Record Body) │ │
│ │ ┌─────────────────────────────────────────────────────┐ │ │
│ │ │ Key Data │ "user:12345:profile" (16 bytes) │ │ │
│ │ │ Value Data │ {"name":"John","age":30} (1024 B) │ │ │
│ │ └─────────────────────────────────────────────────────┘ │ │
│ └─────────────────────────────────────────────────────────┘ │
│ │ │
│ 偏移量 1081 ┌─────────────────────────▼───────────────────────────────┐ │
│ │ 记录尾 (Record Trailer) │ │
│ │ ┌─────────────────────────────────────────────────────┐ │ │
│ │ │ Data Checksum │ 0x12345678 (8 bytes) - 数据校验和 │ │ │
│ │ │ Record Length │ 1089 (4 bytes) - 总记录长度 │ │ │
│ │ │ End Marker │ 0xEND1 (4 bytes) - 结束标记 │ │ │
│ │ └─────────────────────────────────────────────────────┘ │ │
│ └─────────────────────────────────────────────────────────┘ │
└────────────────────────────────────────────────────────────────────────────┘
记录类型定义:
┌─────────────┬─────────────┬─────────────────────────────────────────────┐
│ 类型码 │ 操作类型 │ 描述 │
├─────────────┼─────────────┼─────────────────────────────────────────────┤
│ 0x01 │ PUT │ 插入或更新键值对 │
│ 0x02 │ DELETE │ 删除指定键 │
│ 0x03 │ COMMIT │ 事务提交标记 │
│ 0x04 │ ROLLBACK │ 事务回滚标记 │
│ 0x05 │ CHECKPOINT │ 检查点标记 │
│ 0x06 │ FLUSH │ MemTable刷盘标记 │
│ 0xFF │ INVALID │ 无效记录(用于填充) │
└─────────────┴─────────────┴─────────────────────────────────────────────┘
WAL 文件组织结构:
┌─────────────────────────────────────────────────────────────────────────────┐
│ WAL 文件布局 │
│ │
│ ┌─────────────────┐ ┌─────────────────┐ ┌─────────────────┐ ┌─────────────┐ │
│ │ WAL Header │ │ Record 1 │ │ Record 2 │ │ Record N │ │
│ │ │ │ │ │ │ │ │ │
│ │ - File Version │ │ - Header │ │ - Header │ │ - Header │ │
│ │ - Start LSN │ │ - Body │ │ - Body │ │ - Body │ │
│ │ - File ID │ │ - Trailer │ │ - Trailer │ │ - Trailer │ │
│ │ - Create Time │ │ │ │ │ │ │ │
│ └─────────────────┘ └─────────────────┘ └─────────────────┘ └─────────────┘ │
│ │
│ 文件轮转策略: │
│ - 单文件大小: 64MB-256MB │
│ - 保留文件数: 3-10个 │
│ - 清理策略: 基于LSN水位线 │
└─────────────────────────────────────────────────────────────────────────────┘
系统启动时，WAL 恢复过程包括：
- 扫描 WAL 文件：读取所有未刷盘的日志记录
- 重建 MemTable：将日志记录重新插入到 MemTable
- 校验完整性：验证数据的一致性和完整性
- 清理日志：删除已经刷盘的日志文件
Compaction（合并）是 LSM Tree 的核心维护操作，负责将多个小文件合并为更大文件，优化读取性能并清理过期数据。
LSM Tree 采用分层合并策略，将数据从 Level 0 逐步合并到更深的层级：
LSM Tree 分层合并完整流程
┌─────────────────────────────────────────────────────────────────────────────┐
│ MemTable 层 │
│ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │
│ │ Active │ │ Immutable │ │ Immutable │ │
│ │ MemTable │ │ MemTable 1 │ │ MemTable 2 │ │
│ │ (写入中) │ │ (等待刷盘) │ │ (刷盘中) │ │
│ └─────────────┘ └─────────────┘ └─────────────┘ │
│ │ │
│ ▼ Flush (64MB) │
└─────────────────────────────────────────────────────────────────────────────┘
│
┌───────────────────────────────────────▼─────────────────────────────────────┐
│ Level 0 (重叠层) │
│ │
│ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │
│ │ SST-001 │ │ SST-002 │ │ SST-003 │ │ SST-004 │ │
│ │ [a-m] │ │ [c-p] │ │ [f-s] │ │ [h-z] │ │
│ │ 64MB │ │ 64MB │ │ 64MB │ │ 64MB │ │
│ └─────────────┘ └─────────────┘ └─────────────┘ └─────────────┘ │
│ │
│ 特征: 键范围重叠，需要查找多个文件 │
│ 触发条件: 文件数量 ≥ 4 个 (典型配置) │
│ │ │
│ ▼ Compaction (4:1 合并) │
└─────────────────────────────────────────────────────────────────────────────┘
│
┌───────────────────────────────────────▼─────────────────────────────────────┐
│ Level 1 (有序层) │
│ │
│ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │
│ │ SST-101 │ │ SST-102 │ │ SST-103 │ │ SST-104 │ │
│ │ [a-f] │ │ [g-m] │ │ [n-s] │ │ [t-z] │ │
│ │ 64MB │ │ 64MB │ │ 64MB │ │ 64MB │ │
│ └─────────────┘ └─────────────┘ └─────────────┘ └─────────────┘ │
│ │
│ 特征: 键范围不重叠，查找效率高 │
│ 触发条件: 总大小 ≥ 256MB (4 × 64MB) 或文件数量达到阈值 │
│ │ │
│ ▼ Compaction (4:1 合并) │
└─────────────────────────────────────────────────────────────────────────────┘
│
┌───────────────────────────────────────▼─────────────────────────────────────┐
│ Level 2 (压缩层) │
│ │
│ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │
│ │ SST-201 │ │ SST-202 │ │ SST-203 │ │
│ │ [a-h] │ │ [i-q] │ │ [r-z] │ │
│ │ 256MB │ │ 256MB │ │ 256MB │ │
│ └─────────────┘ └─────────────┘ └─────────────┘ │
│ │
│ 特征: 文件更大，层级更深，存储密度高 │
│ 触发条件: 总大小 ≥ 1GB (4 × 256MB) │
└─────────────────────────────────────────────────────────────────────────────┘
-
选择合并文件
- Level N: 选择最老的文件 (FIFO 策略)
- Level N+1: 选择键范围重叠的所有文件
-
多路归并排序
- 同时读取多个 SSTable 文件
- 按键值进行归并排序
- 处理重复键值 (保留最新版本)
- 清理删除标记和过期数据
-
生成新文件
- 按目标层级的文件大小分割
- 构建索引和 Bloom Filter
- 应用压缩算法
- 原子性替换旧文件
LSM Tree 的 Compaction 过程会引入三种关键性能放大效应，需要在设计时进行权衡：
-
写放大 (Write Amplification)：实际写入磁盘的数据量与用户请求写入数据量的比值。Compaction 过程中数据被多次重写，会增加写放大系数。Leveled Compaction 策略通常写放大较高（2-10 倍），而 Tiered Compaction 策略写放大较低（1.5-3 倍）。
-
读放大 (Read Amplification)：读取数据时需要访问的 SSTable 文件数量。分层结构可能导致需要检查多个层级的文件，增加读放大系数。通常 Level 0 的读放大最高（需要检查多个重叠文件），而深层级的读放大较低（文件有序不重叠）。
-
空间放大 (Space Amplification)：磁盘上无效数据（已删除或过期数据）占用的空间比例。删除标记未及时清理会增加空间放大系数。合理的 Compaction 策略可以控制空间放大在 10-50% 范围内。
性能权衡建议：
- 写密集型场景：优先选择 Tiered Compaction 策略，降低写放大
- 读密集型场景：优先选择 Leveled Compaction 策略，降低读放大
- 存储空间敏感场景：采用更激进的 Compaction 策略，及时清理无效数据
在理解了 LSM Tree 的核心架构和设计原理后，本节将详细解析其关键操作的具体执行流程。LSM Tree 通过精心设计的写入、读取、删除和 Compaction 流程，实现了高性能的数据管理。这些操作流程体现了 LSM Tree "写优化"的设计哲学，同时通过异步 Compaction 机制平衡读写性能。
写入操作是 LSM Tree 的核心优势所在，通过顺序写入和内存优先的设计实现高性能。PUT 操作遵循严格的原子性保证，确保数据在系统崩溃时不会丢失。
写入操作流程 (PUT key="user:123", value="Alice")：
-
请求预处理阶段
- 客户端发送 PUT 请求到 LSM Tree
- 请求参数：
key="user:123", value="Alice" - 生成序列号 (LSN): 1001
- 数据校验：检查 key/value 格式
- 权限验证：检查写入权限
- 限流检查：检查写入速率
-
WAL 日志写入阶段
- 构造日志记录：
[LSN:1001][PUT][user:123][Alice] - 写入日志缓冲区：内存操作
- 刷盘操作：
fsync()确保持久化 - 校验写入：验证日志完整性
- WAL 确保数据持久性，防止系统崩溃时数据丢失
- 构造日志记录：
-
MemTable 更新阶段
- WAL 写入成功后，将数据插入到 MemTable
- SkipList 插入：
O(log n)时间复杂度 - 版本管理：设置版本号和时间戳
- 内存统计：更新大小和计数器
- 阈值检查：判断是否需要刷盘
-
响应返回阶段
- 构造响应：成功状态码
- 性能统计：记录延迟指标
- 日志记录：记录操作日志
- 返回客户端：完成写入操作
- 客户端收到 "OK" 响应，确认写入完成
关键特点：
- 顺序执行：请求预处理 → WAL → MemTable → 响应返回
- 原子性：整个操作要么全部成功，要么全部失败
- 高性能：内存操作，写入延迟低（通常 < 1ms）
- 持久性：WAL 确保数据不会因系统故障而丢失
读取操作体现了 LSM Tree 在读写性能之间的平衡设计。GET 操作采用多层查找策略，从内存到磁盘逐层搜索，通过缓存和索引优化来弥补写入优化带来的读取性能挑战。
读取操作查找策略 (GET key="user:123")：
-
MemTable 查找（内存层）
- 查找顺序：Active MemTable → Immutable MemTable
- 时间复杂度：O(log n)
- 命中率：80%（热数据）
- 数据特征：最新写入的数据，访问速度最快
-
Level 0 查找（磁盘层）
- 查找方式：并行查找多个 SSTable 文件
- 优化技术：使用 Bloom Filter 快速过滤
- 命中率：15%（近期数据）
- 特点：文件间可能有重叠，需要检查多个文件
-
Level 1+ 查找（深层存储）
- 查找方式：二分查找定位文件
- 优化技术：块级索引快速定位
- 命中率：5%（历史数据）
- 特点：文件间无重叠，查找效率高
读取性能优化策略：
-
缓存层优化：
缓存类型 功能 命中率 适用场景 Block Cache 缓存热点数据块 90% 频繁访问的数据块 Row Cache 缓存热点行数据 70% 完整行数据的重复访问 OS Page Cache 系统级缓存 95% 操作系统层面的文件缓存 -
索引优化技术：
- Bloom Filter [7]：减少 90% 无效磁盘访问
- 分层索引：快速定位目标文件
- 预取策略：批量读取相邻数据
删除操作在 LSM Tree 中采用逻辑删除策略，通过 Tombstone 标记实现延迟清理。这种设计避免了立即删除带来的性能开销，同时保证了删除操作的最终一致性。
删除操作实现 (DELETE key="user:123")：
逻辑删除策略（Tombstone Marker）：
-
原始数据状态
- Key: user:123
- Value: "Alice"
- Type: PUT
- Version: 1001
-
删除标记创建
- Key: user:123
- Value: null
- Type: DELETE（Tombstone 标记）
- Version: 1005
- 说明：不直接删除数据，而是添加删除标记
-
删除操作特点
- 逻辑删除：数据仍存在于存储中，但标记为已删除
- 版本控制：删除标记具有更高的版本号
- 读取屏蔽：读取时遇到删除标记会返回"不存在"
- 延迟清理：实际数据清理在 Compaction 时进行
删除标记清理机制：
-
清理条件判断：
- 版本覆盖：所有旧版本已被覆盖
- 时间过期：超过配置的保留时间（TTL）
- Compaction 触发：在 Compaction 过程中遇到删除标记
-
清理执行过程：
- 清理前状态：[PUT v1] [PUT v2] [DELETE v3] [PUT v4]
- 清理后状态：[PUT v4]
- 清理结果：只保留最新有效版本，删除所有历史版本和删除标记
-
清理策略优势：
- 空间回收：释放被删除数据占用的存储空间
- 性能优化：减少无效数据的扫描开销
- 一致性保证：确保删除操作的最终一致性
Level 0 → Level 1 合并过程演示：：
初始状态:
Level 0: [SST1: A-F] [SST2: C-H] [SST3: E-J] [SST4: G-L]
Level 1: [SST5: A-D] [SST6: E-H] [SST7: I-L]
步骤 1: 选择合并文件：
┌─────────────────────────────────────────────────────────────┐
│ 触发条件: Level 0 文件数 = 4 (达到阈值) │
│ 选择策略: 全部 Level 0 文件 + 重叠的 Level 1 文件 │
│ 输入文件: SST1, SST2, SST3, SST4, SST5, SST6, SST7 │
└─────────────────────────────────────────────────────────────┘
步骤 2: 多路归并排序：
┌─────────────────────────────────────────────────────────────┐
│ 归并过程 (按时间戳，Level 0 > Level 1): │
│ SST1: A(t4) B(t4) C(t4) D(t4) E(t4) F(t4) │
│ SST2: C(t3) D(t3) E(t3) F(t3) G(t3) H(t3) │
│ SST3: E(t2) F(t2) G(t2) H(t2) I(t2) J(t2) │
│ SST4: G(t1) H(t1) I(t1) J(t1) K(t1) L(t1) │
│ SST5: A(t0) B(t0) C(t0) D(t0) │
│ SST6: E(t0) F(t0) G(t0) H(t0) │
│ SST7: I(t0) J(t0) K(t0) L(t0) │
│ │
│ 合并结果 (保留最新时间戳): │
│ A(t4←SST1) B(t4←SST1) C(t4←SST1) D(t4←SST1) │
│ E(t4←SST1) F(t4←SST1) G(t3←SST2) H(t3←SST2) │
│ I(t2←SST3) J(t2←SST3) K(t1←SST4) L(t1←SST4) │
└─────────────────────────────────────────────────────────────┘
步骤 3: 生成新文件：
┌─────────────────────────────────────────────────────────────┐
│ 输出文件分割 (每个文件 64MB): │
│ SST8: A(t4) B(t4) C(t4) D(t4) │
│ SST9: E(t4) F(t4) G(t3) H(t3) │
│ SST10: I(t2) J(t2) K(t1) L(t1) │
└─────────────────────────────────────────────────────────────┘
最终状态:
Level 0: [空]
Level 1: [SST8: A-D] [SST9: E-H] [SST10: I-L]
Tombstone 清理可视化：
合并前状态:
┌─────────────────────────────────────────────────────────────┐
│ SST1 (Level 0): │
│ user:100 → "Alice" (PUT, v1001) │
│ user:101 → "Bob" (PUT, v1002) │
│ user:102 → null (DELETE, v1003) ← Tombstone │
│ │
│ SST2 (Level 1): │
│ user:100 → "Old" (PUT, v900) │
│ user:102 → "Charlie" (PUT, v800) │
│ user:103 → "David" (PUT, v950) │
└─────────────────────────────────────────────────────────────┘
清理规则应用:
-
user:100 处理:
- 版本比较: v1001 > v900
- 操作: 保留 "Alice"，丢弃 "Old"
- 原因: 新版本覆盖旧版本
-
user:101 处理:
- 版本情况: 只有一个版本
- 操作: 保留 "Bob"
- 原因: 无冲突，直接保留
-
user:102 处理:
- 版本比较: DELETE v1003 > PUT v800
- 操作: 删除所有版本
- 原因: 删除标记优先级最高
-
user:103 处理:
- 版本情况: 只有一个版本
- 操作: 保留 "David"
- 原因: 无冲突，直接保留
合并后状态:
新 SST (Level 1) 最终结果:
- user:100 →
"Alice" (PUT, v1001) - user:101 →
"Bob" (PUT, v1002) - user:103 →
"David" (PUT, v950)
空间优化效果:
- 清理记录数: 2 个记录被清理
- 空间节省: 约 30% 存储空间
- 优化类型: 版本去重 + 删除标记清理
通过本文的学习，我们可以总结出 LSM Tree 的核心优势：
| 核心优势 | 技术特点 | 具体实现 | 性能效果 |
|---|---|---|---|
| 写入性能优异 | 顺序写入优化 | 将随机写入转换为顺序写入 | 大幅提升写入吞吐量 |
| 内存缓冲机制 | 内存缓冲机制减少磁盘 I/O | 降低写入延迟 | |
| 批量处理 | 批量刷盘提升整体吞吐量 | 提高 I/O 效率 | |
| 存储效率高 | 分层存储架构 | 分层存储架构优化空间利用 | 提升空间利用率 |
| 数据压缩 | 压缩算法减少存储开销 | 节省存储空间 | |
| 空间回收 | Compaction 机制回收无效空间 | 避免空间碎片 | |
| 扩展性强 | 大规模存储 | 支持大规模数据存储 | 满足海量数据需求 |
| 水平扩展 | 分层架构便于水平扩展 | 支持集群部署 | |
| 分布式友好 | 适合分布式环境部署 | 提升系统可用性 |
LSM Tree 特别适合以下应用场景：
| 适用程度 | 负载特征 | 典型应用 | 推荐理由 |
|---|---|---|---|
| 高度适合 | 写密集型 | 日志收集系统 | 充分发挥写入性能优势 |
| 时序数据 | 时序数据库 | 适合时间有序数据存储 | |
| 大数据处理 | 大数据分析平台 | 支持大规模数据存储 | |
| 适合 | 混合负载 | 内容管理系统 | 平衡读写性能 |
| 会话存储 | 用户会话管理 | 适合临时性数据存储 | |
| 不适合 | 读密集型 | 实时查询系统 | 多层查找影响读取性能 |
| 小数据量 | 轻量级应用 | Compaction 开销相对较大 |
LSM Tree 作为现代存储系统的重要技术，正在以下方向持续发展：
- 硬件优化适配：针对 NVMe SSD、持久化内存等新硬件的优化
- 智能调优：基于机器学习的自适应参数调优
- 云原生支持：更好地支持容器化和微服务架构
- 多模数据支持：支持图数据、时序数据等多种数据模型
LSM Tree 的设计思想和实现技术为我们提供了宝贵的工程经验，无论是在系统设计还是性能优化方面，都具有重要的参考价值。通过深入理解其核心原理，我们能够更好地设计和优化现代数据系统。
[1] O'Neil, P., Cheng, E., Gawlick, D., & O'Neil, E. (1996). The log-structured merge-tree (LSM-tree). Acta Informatica, 33(4), 351-385. [2] Chang, F., Dean, J., Ghemawat, S., Hsieh, W. C., Wallach, D. A., Burrows, M., ... & Gruber, R. E. (2008). Bigtable: A distributed storage system for structured data. ACM Transactions on Computer Systems, 26(2), 1-26. [3] Pugh, W. (1990). Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM, 33(6), 668-676. [4] LZ4 Development Team. "LZ4 - Extremely fast compression." GitHub, 2024. Available: https://github.com/lz4/lz4 [5] Google. "Snappy - A fast compressor/decompressor." GitHub, 2024. Available: https://github.com/google/snappy [6] Facebook. "Zstandard - Real-time data compression algorithm." GitHub, 2024. Available: https://github.com/facebook/zstd [7] Bloom, B. H. (1970). Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), 422-426.