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)