bLSM: A General Purpose Log Structured Merge Tree 是一种 LSM（Log‑Structured Merge Tree）树的改进变体，旨在在保持写入高吞吐的同时，显著改善 读取和扫描性能，并优化合并调度，从而在实际存储系统中比传统 LSM 或 B‑Tree 更平衡地处理混合工作负载。(Medium)

📌 1. 背景：LSM‑Tree 简要回顾

LSM 树是一种面向 写密集型存储系统 的数据结构，它通过将写入操作缓存在内存，然后按批顺序写入磁盘，再通过 后台合并（compaction） 保持各层数据有序，从而极大减少随机磁盘写操作。(维基百科)

典型的 LSM 结构包括：

  • 内存层（C0）：快速接受写入
  • 磁盘层（C1、C2…）：通过合并保持有序、减少冗余
  • 可选 Bloom 过滤器 用于减少不必要的磁盘查找(维基百科)

LSM 树在大规模键值存储（如 Cassandra、RocksDB 等）非常常见，因为它能显著提高写性能。(Luke Olney)

📌 2. bLSM 的核心动机与贡献

bLSM 是由 Russell Sears 和 Raghu Ramakrishnan（Yahoo Research）提出的 针对 LSM 树的一种增强结构，主要目标是：

✅ 更好的 读取性能和扫描性能

传统 LSM 在写入友好但可能面临较高的读取延迟和扫描成本。bLSM 通过约束 on‑disk 组件数量以及引入更高效的合并调度，使得 查找和扫描不至于被过多层级膨胀拖慢。(CSDN)

✅ 引入更智能的 合并调度器

bLSM 提出了一种称为 “Spring and Gear Scheduler”（弹簧与齿轮调度器） 的机制，用于控制不同层之间的合并时机和进度，使写入延迟可控而不会影响总体吞吐。(CSDN)

📌 3. bLSM 的设计特点简介

🔹 三层 LSM 结构

bLSM 通常采用三层 LSM 树：

  • C0：内存层，快速写入
  • C1 / C2：磁盘层，受 Bloom 过滤器保护（Bloom filter 用于减少不必要读取）(Medium)

限制 on‑disk 层数量可以减少每次查找时需要访问多个层的成本，从而减少 读取放大（read amplification）。(CSDN)

🔹 “Spring and Gear” 合并调度器

合并调度器的核心思想是：

  • 通过将不同层的合并操作 同步调度，避免出现写停顿（write stall）
  • 采用类似时钟齿轮的机制让多次较小层合并配合少次数较大层合并，以平衡写入与合并的协同进度
  • 确保合并与填充过程之间保持节奏一致，从而提高整体系统响应稳定性(CSDN)

📌 4. bLSM 的性能与优点

设计目标传统 LSM 树bLSM
写入吞吐高保持高
写延迟抖动可能较大限制于可控范围
读取放大偏高降低
扫描性能受层数影响更优
合并调度简单或无调度高级调度支持

📌 5. 与传统 LSM 的对比

  • 读取放大：bLSM 在设计上更关注减少读取时需要扫描的层数和查找成本，改善查询响应。(CSDN)
  • 合并机制：传统 LSM 更依赖简单的合并策略，而 bLSM 的调度机制使写入与合并之间更柔和地协调。(CSDN)
  • Bloom 过滤器：二者都会使用 Bloom 过滤器来减少无效查找，但 bLSM 更强调将过滤器与合并机制结合优化查询。(Medium)

📌 6. 适用场景

bLSM 特别适合 写密集且需要低延迟读/扫描表现的系统，例如：

  • 高吞吐日志存储系统
  • 时序数据存储
  • 大规模键值存储服务

📌 总结

bLSM 是一种优化过的 LSM 树结构，在传统 LSM 的基础上：

📌 限制 on‑disk 组件数量
📌 引入高级合并调度器（Spring & Gear）
📌 更关注读取性能与延迟稳定性

从而在许多实际存储应用中表现出比标准 LSM 和某些 B‑Tree 实现更优的性能平衡。(Medium)