深入现代存储引擎内核：LSM-Tree 的读写流模型、分层压缩算法与布隆过滤全景剖析

1. 存储架构的范式演进：B+ 树与 LSM-Tree

在数据库与底层存储引擎的设计中，I/O 模式的取舍始终是决定系统吞吐与延迟表现的核心物理约束：

• 传统 B+ 树体系：采用原地更新（In-place Update）机制。每次写入或修改记录时，都需要精确找到对应的数据页（Page）并覆写磁盘扇区。在大规模并发写或时序数据写入场景下，大量的数据页分散在磁盘各处，引发严重的随机 I/O（Random I/O），成为性能瓶颈。
• LSM-Tree（Log-Structured Merge-tree）体系：由 Patrick O’Neil 等人提出，其核心哲学是化随机写为顺序追加写（Append-Only Sequential Write）。通过内存缓冲（MemTable）累积批量写操作，配合后台异步的多路归并压缩（Compaction），实现了极致的写吞吐能力。

如今，LSM-Tree 已成为 RocksDB、LevelDB、Apache Cassandra、TiKV、ClickHouse 等云原生分布式数据库与高性能时序引擎的工业标准。本文将结合 LSMTreeLab 仿真系统，深入解剖 LSM-Tree 的四大核心阶段：WAL预写、MemTable内存表、SSTable分层组织与 Leveled Compaction 归并压缩。

2. LSM-Tree 存储体系核心架构

LSMTreeLab 完整实现了多级存储模型，其数据流架构如下：

[ 写请求 Put(k, v) / Delete(k) ]
           │
           ├───► 1. 顺序追加写 WAL (Write-Ahead Log, 磁盘持久化保障)
           │
           └───► 2. 写入 Active MemTable (内存跳表/红黑树, 保持 Key 有序)
                       │
                       ▼ (达到容量阈值)
                 Immutable MemTable (冻结只读队列)
                       │
                       ▼ (异步 Flush 刷盘)
           ┌──────────────────────────────────────────────┐
           │ Level 0 SSTables (直接刷盘, Key 范围允许重叠)  │
           └──────────────────────┬───────────────────────┘
                                  │ (触发 Leveled Compaction)
                                  ▼
           ┌──────────────────────────────────────────────┐
           │ Level 1 SSTables (多路归并, 分区有序无重叠)   │
           └──────────────────────┬───────────────────────┘
                                  │ (容量超限逐级下沉)
                                  ▼
           ┌──────────────────────────────────────────────┐
           │ Level 2..k SSTables (大容量归档, 彻底清除墓碑) │
           └──────────────────────────────────────────────┘

3. 核心算法与底层原理剖析

3.1 读写路径与多版本遮蔽（Multi-Version Shadowing）

• 写入路径（Write Path）：
  任何 Put 或 Delete 操作均无需在磁盘上检索旧数据。
  • Put(key, value)：直接生成包含时间戳的新版本记录；
  • Delete(key)：生成一个带有特殊标记的墓碑条目（Tombstone Record）；
  • 写入 WAL 确保宕机可重放，随后写入 Active MemTable 即刻返回给客户端，耗时通常 $< 1\text{ms}$。
• 点查路径（Read / Point Query Path）：
  由于同一 Key 的多次更新可能分布在内存与不同层级的 SSTable 中，读取遵循严格的时序倒序探测链条：

  $$\text{Search Order: } \text{Active MemTable} \longrightarrow \text{Immutable MemTable} \longrightarrow \text{Level 0 (从新到旧)} \longrightarrow \text{Level 1} \dots \text{Level } k$$

  一旦在某一阶段命中（无论是有效值还是墓碑标记），立即停止向下探测并返回结果。

3.2 布隆过滤器（Bloom Filter）加速与读放大消除

若无辅助索引，点查不存在的 Key 需要遍历所有 SSTable，造成极其严重的读放大（Read Amplification）。

每个 SSTable 头部内嵌了固定大小的布隆过滤器（位图 $m$ bits，哈希函数个数 $k$）：

$$k = \frac{m}{n} \ln 2 \approx 0.693 \times \frac{m}{n}$$

// BloomFilter 核心判定实现
mightContain(key) {
  for (let i = 0; i < this.numHashes; i++) {
    const idx = this.hash(key, i * 31);
    const byteIdx = Math.floor(idx / 8);
    const bitIdx = idx % 8;
    if ((this.bits[byteIdx] & (1 << bitIdx)) === 0) {
      return false; // 100% 绝对不存在，安全短路跳过磁盘读取！
    }
  }
  return true; // 可能存在，进入 SSTable 二分查找
}

3.3 分层压缩（Leveled Compaction）多路归并算法

随着 Level 0 SSTable 数量超过阈值（如 3~4 个），必须启动后台 Compaction 线程：

1. 输入选取：选取 Level 0 的全部 SSTable 以及 Level 1 中与 Level 0 Key 范围重叠的所有 SSTable。
2. 多路归并排序（Multi-way Merge Sort）：
   • 遍历所有输入条目，对于相同 Key 的多个历史版本，仅保留时间戳最新（Timestamp 最大）的版本，丢弃旧版本脏数据；
3. 墓碑物理清除（Tombstone Purge）：
   • 若当前 Compaction 目标是系统最底层（Max Level），说明更深层不可能存在该 Key 的更早历史版本，此时直接将 Tombstone 条目彻底丢弃，实现物理空间回收。
4. 切块输出：将归并后的有序流均匀切分为固定大小的 Level 1 SSTable，保证 Level 1 内部所有 SSTable 的 Key 区间互不重叠。

4. LSM-Tree 三大放大效应平衡（RUM 猜想）

在存储系统设计中，著名的 RUM 猜想（Read/Update/Memory Overhead Tradeoff） 指出任何存储引擎都无法同时最优化读、写、空间开销。LSM-Tree 围绕三大放大效应进行动态权衡：

5. 总结与展望

LSM-Tree 通过优雅的 Append-Only 与分层多路归并设计，成功击破了磁盘随机写入的物理瓶颈。LSMTreeLab 提供了开箱即用的可视化演练环境，使开发者能够实时观测 MemTable 刷盘、布隆过滤器命中以及分层压缩的完整动态过程。

随着现代 NVMe SSD、持久内存（PMEM）与 CXL 内存池技术的爆发，未来的 LSM-Tree 正在朝向近内存存储优化、异步 io_uring 批处理与 ZNS（Zoned Namespaces）原生分区的方向加速演进。