LSM Tree

LSM Tree（Log-Structured Merge Tree，日志结构合并树）是一种面向高并发写入优化，同时兼顾查询效率的键值存储模型。

一、核心主线

LSM Tree被广泛应用于 BigTable、HBase、Cassandra、TiDB 等 NoSQL 或分布式数据库中。

核心思路是：

将随机写转换为内存写和磁盘顺序写，以充分发挥内存与磁盘的性能优势。

整体数据流转过程：

1
2
3
4
5
6
7
8
9
10
11

写请求
  ↓
WAL：先记录日志，保证可靠性
  ↓
MemTable：在内存中有序写入
  ↓ 达到容量阈值
Immutable MemTable：冻结为只读结构
  ↓ 后台持久化
Level 0 SSTable
  ↓ Compaction
Level 1 → Level 2 → ... → Level N

二、LSM Tree 的设计基础

1. 顺序读写优于随机读写

LSM Tree 建立在一个重要结论之上：

磁盘或内存的顺序读写性能远高于随机读写性能。

这一规律不仅适用于机械硬盘，也适用于 SSD。

• 顺序读写：按照文件中数据的排列顺序进行操作，例如向文件尾部追加数据；
• 随机读写：不遵循文件中数据的排列顺序，需要在不同位置间跳转。

传统原地更新会造成大量随机写，而 LSM Tree 尽量不在磁盘中直接修改旧数据，而是：

1. 先在内存中处理写入；
2. 再将有序数据批量刷入磁盘；
3. 后台通过合并操作清理旧数据。

这样便把大量随机写转换成了顺序写。

三、LSM Tree 的核心组成

1. WAL

WAL 全称为 Write-Ahead Log，即预写日志。

MemTable 位于内存中，如果机器宕机或进程异常退出，尚未持久化的数据就会丢失。因此，修改 MemTable 前需要先把数据变更追加到磁盘上的 WAL 文件。

1
2
3
4
5
6
7

写请求
  ↓
追加到 WAL
  ↓
写入 MemTable
  ↓
返回成功

WAL 的核心作用是：

• 为内存数据提供持久化保障；
• 系统异常后可以根据日志恢复数据；
• 在保证可靠性的同时，保留内存写入的高性能。

2. MemTable

MemTable 是位于内存中的有序数据结构，用于保存最近更新的数据。

它按照 Key 的字典序组织数据。LSM Tree 并不限制其具体实现，只要满足以下要求即可：

• 数据保持有序；
• 写入效率高；
• 查询效率较高。

常见实现包括：

• 红黑树；
• 跳表。

2.1 新增数据

直接将新的 Key 和 Value 插入 MemTable。

2.2 修改数据

• 如果 Key 已存在于 MemTable，直接修改；
• 如果不存在，则在 MemTable 中插入该 Key 的新值。

LSM Tree 不需要立即找到并修改磁盘中的旧数据。

2.3 删除数据

LSM Tree 通常不会立即物理删除数据，而是写入一条带有 tombstone（墓碑）标记的记录。

1
2
3
4
5
6
7

删除 Key
  ↓
写入 Key + tombstone
  ↓
读取时视为数据已删除
  ↓
后续合并时清理旧值和删除标记

删除操作因此被转换为一次普通写入，避免了磁盘随机删除。

3. Immutable MemTable

当 MemTable 的数据量达到容量阈值，例如 32 MB 时，它会转变为只读的 Immutable MemTable。

随后系统会：

1. 将当前 MemTable 冻结为 Immutable MemTable；
2. 创建一个新的空 MemTable；
3. 新 MemTable 继续接收写请求；
4. 后台线程把 Immutable MemTable 持久化到磁盘。

1
2
3
4
5

旧 MemTable 达到阈值
        ↓
转为 Immutable MemTable ──→ 后台刷入磁盘
        ↓
新建 MemTable ─────────────→ 继续处理写请求

这样可以避免数据持久化过程阻塞新的写请求。

4. SSTable

SSTable 全称为 Sorted String Table，是 LSM Tree 在磁盘上的主要持久化结构。

它具有三个重要特征：

• 持久化：数据保存在磁盘中；
• 有序：记录按照 Key 的字典序排列；
• 不可变：文件生成后不再原地修改。

SSTable 中的 Key 和 Value 连续存储，文件还会保存 Key 对应数据位置的偏移量，形成稀疏索引，以提高查询速度。

1
2
3

SSTable
├── Key / Value 数据区
└── 稀疏索引：Key → Offset

四、数据冗余与 Compaction

1. 为什么需要合并

MemTable 会不断被持久化为新的 SSTable，因此同一个 Key 可能同时存在于多个 SSTable 中。

例如：

1
2

旧 SSTable：user:1 = A
新 SSTable：user:1 = B

其中新 SSTable 中的 B 才是最新值，旧值 A 已经失效，但仍然占用磁盘空间。

删除操作也类似：旧 SSTable 中可能保存数据，新 SSTable 中保存其 tombstone 标记。

为了清理冗余版本和已删除数据，LSM Tree 会周期性执行 Compaction（合并）。

2. Level 分层

LSM Tree 使用 Level 对 SSTable 进行分层：

1
2
3
4
5
6
7
8
9
10
11

Immutable MemTable
        ↓
Level 0
        ↓
Level 1
        ↓
Level 2
        ↓
...
        ↓
Level N

• Immutable MemTable 刷盘后形成 Level 0 SSTable；
• Level N 中的数据通过合并下沉到 Level N+1；
• 层级越低，数据通常越新；
• 层级越高，数据通常越旧。

如果同一个 Key 同时存在于多个层级，应优先使用较低层级中的值。

3. Leveled Compaction Strategy

主要合并策略是 LCS（Leveled Compaction Strategy，分层合并策略）。

其基本规则包括：

• SSTable 文件大小通常保持一致，例如默认约为 160 MB；
• 每个 Level 都有总容量限制；
• 层级越高，允许保存的数据总量越大；
• 单个 SSTable 内部的 Key 有序；
• Level 1～N 中，同一层的不同 SSTable 之间也按照 Key 范围有序且互不重叠。

容量示例：

1
2
3

Level 1：总容量约 10 GB
Level 2：总容量约 100 GB
更高层级：容量继续递增

4. 分层合并过程

当 Level N 的文件总量超过阈值时：

1. 从 Level N 选择一个 SSTable；
2. 找出 Level N+1 中与其 Key 范围有交集的 SSTable；
3. 将这些 SSTable 合并；
4. 清除重复记录和已失效的旧版本；
5. 生成若干新的 SSTable；
6. 将新文件归入 Level N+1；
7. 如果 Level N+1 也超出容量限制，则继续向下合并。

1
2
3
4
5
6
7
8
9

Level N 的 SSTable
        +
Level N+1 中 Key 范围重叠的 SSTable
        ↓
合并、排序、清除旧版本
        ↓
生成新的 SSTable
        ↓
归入 Level N+1

5. Level 0 的特殊性

Level 0 SSTable 直接来自不同的 Immutable MemTable，因此多个 Level 0 文件的 Key 范围可能相互重叠。

经过合并后：

• Level 1～N 同一层的 SSTable 之间通常不存在 Key 范围重叠；
• 一个 Key 在同一个非 Level 0 层级中至多出现一次；
• 查询高层级数据时更容易定位目标 SSTable。

五、写数据流程

1. 完整写入链路

LSM Tree 处理写请求的过程如下：

1. 将数据变更追加到 WAL；
2. 把数据写入 MemTable；
3. 此时即可向客户端返回成功；
4. MemTable 达到容量阈值后转为 Immutable MemTable；
5. 新建一个 MemTable 继续处理请求；
6. 后台将 Immutable MemTable 持久化为 Level 0 SSTable；
7. Level 0 超过容量阈值后触发 Compaction；
8. SSTable 逐层下沉至 Level 1、Level 2，直到容量满足限制。

1
2
3
4
5
6
7
8
9
10
11

客户端写请求
      ↓
WAL
      ↓
MemTable
      ↓ 返回成功
Immutable MemTable
      ↓
Level 0 SSTable
      ↓ Compaction
Level 1 → Level 2 → ... → Level N

2. 写性能高的原因

LSM Tree 写性能较高，主要因为：

• 首先写入内存中的 MemTable；
• WAL 使用追加写，属于顺序写；
• 不直接在磁盘中随机查找并修改旧记录；
• 数据以批量、有序的方式刷入磁盘；
• 数据整理和旧版本清理由后台 Compaction 完成。

六、读数据流程

1. 查询顺序

为了读到某个 Key 的最新值，LSM Tree 会按照数据从新到旧的顺序查找：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

MemTable
  ↓ 未找到
Immutable MemTable
  ↓ 未找到
Level 0 最新 SSTable
  ↓ 未找到
Level 0 其他 SSTable
  ↓ 未找到
Level 1
  ↓
Level 2
  ↓
...
  ↓
Level N

具体流程：

1. 先查询 MemTable；
2. 未找到时查询 Immutable MemTable；
3. 继续查询 Level 0 中最新的 SSTable；
4. 遍历 Level 0 的相关 SSTable；
5. 再依次查询 Level 1～N；
6. 找到后立即返回，全部未找到则表示数据不存在。

2. 为什么必须从新到旧查询

同一个 Key 可能存在多个版本：

1
2
3
4

MemTable：最新版本
Level 0：较新版本
Level 3：更旧版本
Level 5：最旧版本

如果不按新旧顺序查询，就可能返回已经失效的旧值。

同样，如果先找到 tombstone，就应认为该数据已被删除，不能继续返回更旧层级中的历史值。

七、LSM Tree 的核心权衡

1. 优势

• 将随机写转换为内存写和磁盘顺序写；
• 非常适合高并发写入；
• WAL 保证内存数据的可靠性；
• SSTable 有序并带有索引，可以兼顾查询效率；
• 数据可以通过分层和合并持续整理；
• 很适合作为分布式 NoSQL 数据库的底层存储模型。

2. 代价

• 同一个 Key 可能存在多个版本，占用额外空间；
• 读取数据可能需要查询多个内存结构和 SSTable；
• 后台 Compaction 会消耗 CPU、磁盘 I/O 和存储带宽；
• 数据不会在修改或删除时立即原地更新，而是延迟到合并阶段清理。

LSM Tree 的本质权衡是：

通过增加读路径和后台合并的复杂度，换取更高的写入性能。

八、核心架构思想

1. 顺序读写性能高于随机读写，是 LSM Tree 成立的基础。
2. 写请求先进入 WAL，再写入 MemTable，在性能和可靠性之间取得平衡。
3. MemTable 保存最新数据，并通过有序结构提高读写效率。
4. 删除不立即清除旧数据，而是写入 tombstone，将随机删除转换为普通写入。
5. Immutable MemTable 让后台刷盘不阻塞新的写请求。
6. SSTable 是持久化、有序且不可变的磁盘文件。
7. 同一 Key 可以存在多个版本，较新的结构或较低层级中的值优先。
8. Compaction 负责清除冗余版本、整理数据并回收空间。
9. Level 0 的文件可能重叠，Level 1～N 同层文件通常不重叠。
10. 写入路径短而快速，读取路径需要从新到旧逐层查找。
11. LSM Tree 用读放大、写放大和后台合并成本，换取高并发写入能力。

九、一句话总结

LSM Tree 通过 WAL 保证可靠性，在 MemTable 中承接高速内存写入，再将数据有序地刷入不可变的 SSTable，并通过分层 Compaction 清理旧版本和 tombstone；它用更复杂的读取路径与后台合并成本，将大量随机写转换为顺序写，因此非常适合高并发写入的 NoSQL 和分布式数据库。