LSM Tree 再入门
原
GrissomFI约 16 分钟
GrissomFI约 16 分钟LSM Tree 入门
在RocksDB 工作原理入门一文中，我们已对 LSM Tree 的基本概念进行了简要介绍。本文将进一步基于原始论文《The Log-Structured Merge-Tree (LSM-Tree)》出发，从原理与流程两个角度深入解析 LSM Tree 的工作机制。这是本系列的第一篇文章，旨在帮助读者系统理解 LSM Tree 的核心思想与关键步骤。
代码：https://github.com/brianxiadong/java-lsm-tree
目录
1. LSM Tree 经典论文简介 2. LSM Tree 核心原理与组件实现 3. LSM Tree 操作流程详解 4. 总结
1. LSM Tree 经典论文简介
1.1 论文背景
LSM Tree（Log-Structured Merge Tree）的概念最早由 Patrick O'Neil 等人在 1996 年的经典论文《The Log-Structured Merge-Tree (LSM-Tree)》[1] 中提出。这篇论文在数据库存储领域具有里程碑意义，为现代 NoSQL 数据库和分布式存储系统奠定了重要的理论基础。
1.2 核心思想
LSM Tree 的核心思想是将随机写入转换为顺序写入，从而充分利用磁盘的顺序访问性能优势。传统的 B+Tree 结构在处理大量写入操作时，由于需要维护树结构的平衡性，往往产生大量的随机 I/O 操作，导致性能瓶颈。
LSM Tree 通过以下设计解决了这个问题：
1. 分层存储架构：将数据分为内存层（C₀）和磁盘层（C₁），新数据首先写入内存，然后批量刷写到磁盘 2. 顺序写入优化：所有磁盘写入都是顺序的，避免了随机 I/O 的性能损失 3. Rolling Merge 算法：通过后台的合并过程，将小文件逐步合并为大文件，保持数据的有序性
1.3 理论创新
论文的主要理论贡献包括：
1. 性能分析模型：提供了 LSM Tree 与 B+Tree 的数学性能对比模型 2. 写入成本分析：
• B+Tree 写入成本：O(log_B N) 次随机 I/O • LSM Tree 写入成本：O(1) 次顺序 I/O + 后台合并成本
1.4 历史影响
这篇论文的影响深远，为后来的许多知名系统提供了理论基础：
• BigTable [2]：Google 的分布式存储系统，采用了 LSM Tree 的核心思想 • LevelDB/RocksDB：广泛使用的嵌入式存储引擎 • Cassandra、HBase：流行的 NoSQL 数据库系统 • 现代时序数据库：如 InfluxDB、TimescaleDB 等
2. LSM Tree 核心原理与组件实现
2.1 整体架构设计
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 各组件之间的协作关系，下面展示完整的系统架构图：
┌─────────────────────────────────────────────────────────────────────────────────┐
│ LSM Tree 整体系统架构 │
│ │
│ ┌─────────────────┐ ┌─────────────────┐ ┌─────────────────┐ │
│ │ 客户端接口 │ │ 读写协调器 │ │ 版本管理器 │ │
│ │ ┌─────────────┐ │ │ ┌─────────────┐ │ │ ┌─────────────┐ │ │
│ │ │ PUT/GET/DEL │ │ │ │ 读写路由 │ │ │ │ MVCC 控制 │ │ │
│ │ │ 批量操作 │ │ │ │ 并发控制 │ │ │ │ 快照管理 │ │ │
│ │ │ 范围查询 │ │ │ │ 一致性保证 │ │ │ │ 事务支持 │ │ │
│ │ └─────────────┘ │ │ └─────────────┘ │ │ └─────────────┘ │ │
│ └─────────────────┘ └─────────────────┘ └─────────────────┘ │
│ │ │ │ │
│ └───────────────────────┼───────────────────────┘ │
│ │ │
│ ┌────────────────────────────────┼────────────────────────────────────────┐ │
│ │ 核心存储引擎 │ │ │
│ │ ▼ │ │
│ │ ┌─────────────────────────────────────────────────────────────────┐ │ │
│ │ │ 内存层 (Memory 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 限流 │ │ │ │
│ │ │ │ 并发控制 │ │ │ │ 告警机制 │ │ │ │ 线程池管理 │ │ │ │
│ │ │ └─────────────┘ │ │ └─────────────┘ │ │ └─────────────┘ │ │ │
│ │ └─────────────────┘ └─────────────────┘ └─────────────────┘ │ │
│ └─────────────────────────────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────────────────────────────┘2.2 MemTable 设计与实现
2.2.1 SkipList 数据结构
MemTable 采用 SkipList（跳表）作为核心数据结构，提供高效的插入、查找和范围查询能力。SkipList 是由 William Pugh 在 1990 年提出的概率性数据结构 [3]：
SkipList 多层索引结构 (最大层数: 32)
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] ──→ [50] │
│ │ │ Value: ... │ │ forward[1] ──→ [35] │
│ │ │ Version: v1 │ │ forward[0] ──→ [35] │
│ │ │ Height: 4 │ │ │
│ │ └─────────────┘ │ 注：forward[i] 指向第i层的下一个节点 │
│ └─────────────────┘ │
└─────────────────────────────────────────────────────────────────────────┘查找过程示例 (查找 key = 35):
1. 从 Level 3 开始: HEAD → NULL (35 > 30, 下降到 Level 2) 2. Level 2: HEAD → [30] → NULL (35 > 30, 从[30]下降到 Level 1) 3. Level 1: [30] → [50] (35 < 50, 从[30]下降到 Level 0) 4. Level 0: [30] → [35] (找到目标节点)
时间复杂度: O(log n)，空间复杂度: O(n)
2.2.2 版本化存储机制
版本化存储设计：
┌──────────────────────────────────────────────────────────────┐
│ 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 标记删除 • 时间戳索引：支持时间范围查询
2.2.3 内存管理与阈值控制
内存管理策略：
┌─────────────────────────────────────────────────────────────┐
│ MemTable 内存分配： │
│ │
│ ┌─────────────────┐ 阈值检查 ┌───────────────────┐ │
│ │ Active MemTable │ ────────────→ │Immutable MemTable │ │
│ │ 当前大小: 45MB │ 64MB 触发 │ 大小: 64MB │ │
│ │ 状态: 可写 │ │ 状态: 只读 │ │
│ └─────────────────┘ └──────────────────┘ │
│ │ │ │
│ ▼ 继续写入 ▼ 后台刷盘 │
│ ┌─────────────────┐ ┌─────────────────┐ │
│ │ 新 MemTable │ │ SSTable 文件 │ │
│ │ 大小: 0MB │ │ Level 0 │ │
│ └─────────────────┘ └─────────────────┘ │
└─────────────────────────────────────────────────────────────┘内存管理参数：
| 参数 | 默认值 | 作用 | 调优建议 |
|---|---|---|---|
| MemTable 大小阈值 | |||
| Immutable 队列长度 | |||
| 写入缓冲区大小 | |||
| 内存分配器 |
2.3 SSTable 文件格式设计
2.3.1 文件结构布局
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"):
1. 读取文件尾 → 获取索引块和过滤器位置 2. 检查布隆过滤器 → 判断 Key 可能存在 3. 二分查找索引块 → 定位目标数据块 4. 读取数据块 → 在块内二分查找 Key 5. 返回 Value 或 NotFound
性能特性:
• 顺序写入: O(1) 追加写入 • 随机读取: O(log n) 二分查找 • 空间效率: 压缩率 60-80% • 缓存友好: 块级别预读
2.3.2 多级索引机制
SSTable 采用三级索引结构，实现高效的数据定位：
1. 文件级索引：快速定位目标文件 2. 块级索引：在文件内快速定位数据块 3. 块内搜索：在数据块内进行二分查找
2.3.3 压缩算法选择
| 压缩算法 | 压缩比 | 压缩速度 | 解压速度 | 适用场景 |
|---|---|---|---|---|
| LZ4 | ||||
| Snappy | ||||
| ZSTD | ||||
| GZIP | ||||
| 无压缩 |
2.4 WAL (Write-Ahead Log) 机制
2.4.1 WAL 设计原理
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水位线 │
└─────────────────────────────────────────────────────────────────────────────┘2.4.2 恢复机制
系统启动时，WAL 恢复过程包括：
1. 扫描 WAL 文件：读取所有未刷盘的日志记录 2. 重建 MemTable：将日志记录重新插入到 MemTable 3. 校验完整性：验证数据的一致性和完整性 4. 清理日志：删除已经刷盘的日志文件
2.5 Compaction 合并策略
2.5.1 Leveled Compaction 策略
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 │ │
│ └─────────────┘ └─────────────┘ └─────────────┘ └─────────────┘ │
│ │
│ 特征: 键范围不重叠，查找效率高 │
│ 触发条件: 总大小 ≥ 640MB (10 × 64MB) │
│ │ │
│ ▼ Compaction (10:1 合并) │
└─────────────────────────────────────────────────────────────────────────────┘
│
┌───────────────────────────────────────▼─────────────────────────────────────┐
│ Level 2 (压缩层) │
│ │
│ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │
│ │ SST-201 │ │ SST-202 │ │ SST-203 │ │
│ │ [a-h] │ │ [i-q] │ │ [r-z] │ │
│ │ 256MB │ │ 256MB │ │ 256MB │ │
│ └─────────────┘ └─────────────┘ └─────────────┘ │
│ │
│ 特征: 文件更大，层级更深，存储密度高 │
│ 触发条件: 总大小 ≥ 2.56GB (10 × 256MB) │
└─────────────────────────────────────────────────────────────────────────────┘2.5.2 合并过程详细步骤
1. 选择合并文件
• Level N: 选择最老的文件 (FIFO 策略) • Level N+1: 选择键范围重叠的所有文件
• 同时读取多个 SSTable 文件 • 按键值进行归并排序 • 处理重复键值 (保留最新版本) • 清理删除标记和过期数据
• 按目标层级的文件大小分割 • 构建索引和 Bloom Filter • 应用压缩算法 • 原子性替换旧文件
3. LSM Tree 操作流程详解
3.1 写入操作 (PUT) 流程
写入操作流程 (PUT key="user:123", value="Alice")：
1. 请求预处理阶段
• 客户端发送 PUT 请求到 LSM Tree • 请求参数： key="user:123", value="Alice"• 生成序列号 (LSN): 1001 • 数据校验：检查 key/value 格式 • 权限验证：检查写入权限 • 限流检查：检查写入速率
• 构造日志记录： [LSN:1001][PUT][user:123][Alice]• 写入日志缓冲区：内存操作 • 刷盘操作： fsync()确保持久化• 校验写入：验证日志完整性 • WAL 确保数据持久性，防止系统崩溃时数据丢失
• WAL 写入成功后，将数据插入到 MemTable • SkipList 插入： O(log n)时间复杂度• 版本管理：设置版本号和时间戳 • 内存统计：更新大小和计数器 • 阈值检查：判断是否需要刷盘
• 构造响应：成功状态码 • 性能统计：记录延迟指标 • 日志记录：记录操作日志 • 返回客户端：完成写入操作 • 客户端收到 "OK" 响应，确认写入完成
关键特点：
• 顺序执行：请求预处理 → WAL → MemTable → 响应返回 • 原子性：整个操作要么全部成功，要么全部失败 • 高性能：内存操作，写入延迟低（通常 < 1ms） • 持久性：WAL 确保数据不会因系统故障而丢失
3.2 读取操作 (GET) 流程
读取操作查找策略 (GET key="user:123")：
1. MemTable 查找（内存层）
• 查找顺序：Active MemTable → Immutable MemTable • 时间复杂度：O(log n) • 命中率：80%（热数据） • 数据特征：最新写入的数据，访问速度最快
• 查找方式：并行查找多个 SSTable 文件 • 优化技术：使用 Bloom Filter 快速过滤 • 命中率：15%（近期数据） • 特点：文件间可能有重叠，需要检查多个文件
• 查找方式：二分查找定位文件 • 优化技术：块级索引快速定位 • 命中率：5%（历史数据） • 特点：文件间无重叠，查找效率高
读取性能优化策略：
1. 缓存层优化： 缓存类型 功能 命中率 适用场景 Block Cache 缓存热点数据块 90% 频繁访问的数据块 Row Cache 缓存热点行数据 70% 完整行数据的重复访问 OS Page Cache 系统级缓存 95% 操作系统层面的文件缓存 2. 索引优化技术：
• Bloom Filter [7]：减少 90% 无效磁盘访问 • 分层索引：快速定位目标文件 • 预取策略：批量读取相邻数据
3.3 删除操作 (DELETE) 流程
删除操作实现 (DELETE key="user:123")：
逻辑删除策略（Tombstone Marker）：
1. 原始数据状态
• Key: user:123 • Value: "Alice" • Type: PUT • Version: 1001
• Key: user:123 • Value: null • Type: DELETE（Tombstone 标记） • Version: 1005 • 说明：不直接删除数据，而是添加删除标记
• 逻辑删除：数据仍存在于存储中，但标记为已删除 • 版本控制：删除标记具有更高的版本号 • 读取屏蔽：读取时遇到删除标记会返回"不存在" • 延迟清理：实际数据清理在 Compaction 时进行
删除标记清理机制：
1. 清理条件判断：
• 版本覆盖：所有旧版本已被覆盖 • 时间过期：超过配置的保留时间（TTL） • Compaction 触发：在 Compaction 过程中遇到删除标记
• 清理前状态：[PUT v1] [PUT v2] [DELETE v3] [PUT v4] • 清理后状态：[PUT v4] • 清理结果：只保留最新有效版本，删除所有历史版本和删除标记
• 空间回收：释放被删除数据占用的存储空间 • 性能优化：减少无效数据的扫描开销 • 一致性保证：确保删除操作的最终一致性
3.4 Compaction 过程可视化
3.4.1 Level 0 到 Level 1 合并过程
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]3.4.2 删除标记清理过程
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) │
└─────────────────────────────────────────────────────────────┘清理规则应用:
1. user:100 处理:
• 版本比较: v1001 > v900 • 操作: 保留 "Alice"，丢弃 "Old" • 原因: 新版本覆盖旧版本
• 版本情况: 只有一个版本 • 操作: 保留 "Bob" • 原因: 无冲突，直接保留
• 版本比较: DELETE v1003 > PUT v800 • 操作: 删除所有版本 • 原因: 删除标记优先级最高
• 版本情况: 只有一个版本 • 操作: 保留 "David" • 原因: 无冲突，直接保留
合并后状态:
新 SST (Level 1) 最终结果:
• user:100 → "Alice" (PUT, v1001)• user:101 → "Bob" (PUT, v1002)• user:103 → "David" (PUT, v950)
空间优化效果:
• 清理记录数: 2 个记录被清理 • 空间节省: 约 30% 存储空间 • 优化类型: 版本去重 + 删除标记清理
4. 总结
4.1 LSM Tree 核心优势
通过本文的学习，我们可以总结出 LSM Tree 的核心优势：
| 核心优势 | 技术特点 | 具体实现 | 性能效果 |
|---|---|---|---|
| 写入性能优异 | |||
| 存储效率高 | |||
| 扩展性强 | |||
4.2 适用场景
LSM Tree 特别适合以下应用场景：
| 适用程度 | 负载特征 | 典型应用 | 推荐理由 |
|---|---|---|---|
| 高度适合 | |||
| 适合 | |||
| 不适合 | |||
4.3 技术发展趋势
LSM Tree 作为现代存储系统的重要技术，正在以下方向持续发展：
1. 硬件优化适配：针对 NVMe SSD、持久化内存等新硬件的优化 2. 智能调优：基于机器学习的自适应参数调优 3. 云原生支持：更好地支持容器化和微服务架构 4. 多模数据支持：支持图数据、时序数据等多种数据模型
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.