存储引擎内核原理：LSM-Tree 写放大的量化分析与 Compaction 策略优化

存储引擎内核原理：LSM-Tree 写放大的量化分析与 Compaction 策略优化

一、LSM-Tree 写放大的生产级痛点

LSM-Tree（Log-Structured Merge Tree）是 RocksDB、LevelDB、Cassandra、HBase 等存储引擎的核心数据结构。它的写入性能远优于 B-Tree——写入只追加到内存表（MemTable），顺序写 WAL 日志，不产生随机 IO。但 LSM-Tree 的写放大（Write Amplification）是生产环境中最棘手的问题。

写放大的定义：用户写入 1 字节的数据，底层磁盘实际写入的字节数。在 RocksDB 的默认 Level Compaction 策略下，写放大通常在 10-30 倍之间。这意味着用户写入 1GB 数据，磁盘实际写入 10-30GB。在 SSD 上，写放大直接加速闪存磨损，缩短设备寿命；在 HDD 上，写放大消耗大量 IO 带宽，影响读取延迟。

更隐蔽的问题是读放大。LSM-Tree 的数据分散在多层，查询时需要从 L0 到 Ln 逐层查找。L0 层的 SSTable 之间有范围重叠，查询 L0 时需要检查所有 SSTable。如果 L0 文件积压过多（Compaction 跟不上写入速度），查询延迟会从毫秒级飙升到秒级。

二、LSM-Tree 的分层架构与 Compaction 机制

2.1 数据写入与读取路径

flowchart TD A[写入请求] --> B[WAL 顺序写日志] A --> C[MemTable 内存表写入] C --> D{MemTable 已满?} D -->|是| E[Immutable MemTable] E --> F[Flush 到 L0 SSTable] D -->|否| C G[读取请求] --> H[MemTable 查找] H -->|未命中| I[Immutable MemTable 查找] I -->|未命中| J[Block Cache 查找] J -->|未命中| K[L0 SSTable 查找] K -->|未命中| L[L1 SSTable 查找] L -->|未命中| M[Ln SSTable 查找] M -->|未命中| N[返回不存在]

2.2 Level Compaction 的写放大分析

Level Compaction 的规则：Ln 层的总大小达到阈值后，选取 Ln 层的一个 SSTable，与 Ln+1 层中所有有范围重叠的 SSTable 合并，生成新的 Ln+1 SSTable。

写放大的来源：同一份数据在每一层 Compaction 时都被重写一次。假设层数为 L，写放大约为 L 倍（每层重写一次）。RocksDB 默认配置下，L0 到 L6 共 7 层，理论写放大约 10-14 倍（因为 L0 到 L1 的放大更大）。

量化推导：

• L0 到 L1：L0 的 SSTable 直接 Flush，大小约write_buffer_size（默认 64MB）。L1 的目标大小为max_bytes_for_level_base（默认 256MB）。L0 的 4 个文件合并到 L1，写放大约 4 倍。
• L1 到 L2：L1 的一个 SSTable（约 2MB）与 L2 中重叠的 10 个 SSTable 合并，写放大约 10 倍。
• L2 到 L3：类似，写放大约 10 倍。
• 总写放大：4 + 10 + 10 + 10 + 10 + 10 ≈ 54 倍（最坏情况）

实际生产中，由于数据分布和 Compaction 选择策略的差异，写放大通常在 10-30 倍之间。

2.3 Compaction 策略的代码级实现

package storage import ( "sort" ) // SSTableMeta 表示一个 SSTable 文件的元信息 type SSTableMeta struct { Level int // 所在层级 FileID string // 文件标识 SmallestKey []byte // 最小 key LargestKey []byte // 最大 key FileSize int64 // 文件大小（字节） } // LevelCompaction 执行 Level Compaction type LevelCompaction struct { levels [][]SSTableMeta // 各层 SSTable 元信息 levelSize []int64 // 各层总大小 } // PickCompaction 选择需要 Compaction 的层级和文件 func (lc *LevelCompaction) PickCompaction() (int, []SSTableMeta, []SSTableMeta) { // 优先选择超过大小阈值的最低层 for level := 0; level < len(lc.levels)-1; level++ { if lc.levelSize[level] > lc.targetSize(level) { // 选择该层中与下一层重叠最多的 SSTable sourceFiles := lc.pickSourceFile(level) targetFiles := lc.pickOverlapFiles(level+1, sourceFiles) return level, sourceFiles, targetFiles } } return -1, nil, nil } // targetSize 计算目标层的大小阈值 func (lc *LevelCompaction) targetSize(level int) int64 { if level == 0 { return 256 * 1024 * 1024 // L0: 256MB } base := int64(256 * 1024 * 1024) return base * int64(1<<level) // 每层 10 倍增长 } // pickSourceFile 选择源层中需要 Compaction 的 SSTable func (lc *LevelCompaction) pickSourceFile(level int) []SSTableMeta { files := lc.levels[level] // 选择文件大小最大的 SSTable（减少 Compaction 次数） sort.Slice(files, func(i, j int) bool { return files[i].FileSize > files[j].FileSize }) return files[:1] // 每次只选一个文件 } // pickOverlapFiles 选择目标层中与源文件有范围重叠的 SSTable func (lc *LevelCompaction) pickOverlapFiles(targetLevel int, sourceFiles []SSTableMeta) []SSTableMeta { var result []SSTableMeta for _, target := range lc.levels[targetLevel] { for _, src := range sourceFiles { if overlaps(src.SmallestKey, src.LargestKey, target.SmallestKey, target.LargestKey) { result = append(result, target) break } } } return result } // overlaps 判断两个 key 范围是否有重叠 func overlaps(s1, e1, s2, e2 []byte) bool { return compare(e1, s2) >= 0 && compare(s1, e2) <= 0 } func compare(a, b []byte) int { for i := 0; i < len(a) && i < len(b); i++ { if a[i] < b[i] { return -1 } if a[i] > b[i] { return 1 } } if len(a) < len(b) { return -1 } if len(a) > len(b) { return 1 } return 0 }

三、Compaction 策略优化：Tiered 与 FIFO

3.1 Tiered Compaction（Leveled Compaction 的替代方案）

Tiered Compaction（类似 Cassandra 的 STCS）的思路是：同一层的 SSTable 先不合并，积累到一定数量后，整层一起合并到下一层。这减少了 Compaction 的频率，但代价是同一层内有范围重叠的 SSTable，查询时需要检查更多文件。

写放大对比：

3.2 RocksDB 的 Hybrid Compaction

RocksDB 支持混合策略：L0 层使用 Tiered Compaction（减少 L0 到 L1 的写放大），L1+ 层使用 Level Compaction（保证查询性能）。这是通过compaction_style和level0_file_num_compaction_trigger参数控制的。

# RocksDB 混合 Compaction 配置（Python 绑定示例） import rocksdb opts = rocksdb.Options() opts.create_if_missing = True opts.compaction_style = rocksdb.Options.LEVEL # 全局 Level Compaction # L0 层优化：减少 L0 文件积压 opts.level0_file_num_compaction_trigger = 4 # L0 达到 4 个文件触发 Compaction opts.level0_slowdown_writes_trigger = 20 # L0 达到 20 个文件时写入限速 opts.level0_stop_writes_trigger = 36 # L0 达到 36 个文件时停止写入 # 写缓冲区优化 opts.write_buffer_size = 64 * 1024 * 1024 # 64MB MemTable opts.max_write_buffer_number = 4 # 最多 4 个 MemTable（含 Immutable） opts.min_write_buffer_number_to_merge = 2 # 至少 2 个 MemTable 才合并 Flush # Compaction 并发 opts.max_background_compactions = 4 # 最多 4 个后台 Compaction 线程 opts.max_background_flushes = 2 # 最多 2 个后台 Flush 线程 # 目标层大小 opts.max_bytes_for_level_base = 256 * 1024 * 1024 # L1 目标 256MB opts.max_bytes_for_level_multiplier = 10 # 每层 10 倍增长

3.3 Sub-Compaction：并行 Compaction 加速

当 Compaction 的输入文件很大时（如 L5 到 L6，输入可能数十 GB），单线程合并耗时过长。RocksDB 支持将一个 Compaction 任务拆分为多个 Sub-Compaction，按 key 范围并行执行。

# 启用 Sub-Compaction opts.max_subcompactions = 4 # 每个 Compaction 最多拆分为 4 个子任务

Sub-Compaction 的效果：在 8 核机器上，L5 到 L6 的 Compaction 时间从 120 秒降低到 35 秒。但 Sub-Compaction 需要额外的临时空间（输出文件在合并完成前不能覆盖输入文件），磁盘空间峰值可能达到输入数据的 2 倍。

四、LSM-Tree 优化的边界与权衡

4.1 写放大与读放大的零和博弈

Level Compaction 降低读放大（每层无重叠），但增加写放大（每层数据重写）。Tiered Compaction 降低写放大（层数少、合并频率低），但增加读放大（层内有重叠）。两者是零和博弈——不可能同时最小化写放大和读放大。

选择策略的关键是业务读写比。如果写占比超过 70%，优先使用 Tiered Compaction 降低写放大；如果读占比超过 70%，优先使用 Level Compaction 降低读放大。

4.2 Compaction 对前台写入的干扰

Compaction 是后台任务，但它消耗磁盘 IO 带宽。当 Compaction 的 IO 需求与前台写入的 IO 需求冲突时，前台写入的延迟会抖动。RocksDB 通过rate_limiter限制 Compaction 的 IO 速率，但限制过紧会导致 Compaction 跟不上写入速度，L0 文件积压，最终触发level0_stop_writes_trigger导致写入完全停止。

4.3 BlobDB：大值分离存储

当 value 边长较大（超过 1KB）时，每次 Compaction 都需要移动完整的 value，写放大急剧增加。RocksDB 的 BlobDB 方案将大 value 分离存储到 Blob 文件中，LSM-Tree 只存储 value 的引用指针。Compaction 时只移动指针，不移动 value，大幅降低写放大。

但 BlobDB 引入了新的问题：读取大 value 需要额外的 IO（先读 LSM-Tree 获取指针，再读 Blob 文件获取 value），读放大增加。Blob 文件的垃圾回收也需要额外的 Compaction 机制。

4.4 分区 Compaction 的风险

RocksDB 支持将 Column Family 分区为多个实例，每个实例独立 Compaction。这减少了单个实例的 Compaction 压力，但增加了全局的 Compaction 线程数和内存占用。当多个 Column Family 同时触发 Compaction 时，IO 带宽的竞争可能比单实例更严重。

五、总结

LSM-Tree 的写放大是结构性的——它是分层合并策略的必然代价。优化方向不是消除写放大，而是在写放大、读放大和空间放大之间找到业务场景的最优平衡。

落地路线建议：

1. 量化当前写放大：通过 RocksDB 的STATISTICS选项统计BYTES_WRITTEN和BYTES_READ，计算实际写放大倍数。
2. 根据读写比选择 Compaction 策略：写占比 > 70% 用 Tiered，读占比 > 70% 用 Level，中间场景用 Hybrid。
3. 调优 L0 参数：level0_file_num_compaction_trigger设为 4-8，避免 L0 积压导致读取性能退化。
4. 启用 Sub-Compaction：对大层（L4+）的 Compaction 拆分为 2-4 个子任务，缩短 Compaction 时间。
5. 大值场景启用 BlobDB：value 平均大小超过 1KB 时，将大 value 分离存储，降低写放大。
6. 监控 Compaction 积压：设置level0_slowdown_writes_trigger告警，在写入限速前发现 Compaction 跟不上的问题。