LevelDB 完全解析（十一）：Compaction

Compaction 的作用

因为 LevelDB 的增删改都是通过追加写来实现的，所以需要通过后台线程的 compaction 来：

1. 清理过期（旧版本或者已删除）的数据。
2. 维护数据的有序性。

Compaction 的触发

除了从外部调用 CompactRange，LevelDB 有几种情况会自动触发 compaction：

1. 当 MemTable 的大小达到阈值时，进行 MemTable 切换，然后需要将 Immutable MemTable 刷到外存上 —— 一般称之为 Minor Compaction。
2. 当 level-n 的 SSTable 超过限制，level-n 和 level-n+1 的 SSTable 会进行 compaction —— 一般称之为 Major Compaction。
1. level-0 是通过 SSTable 的数量来判断是否需要 compaction。
2. level-n(n > 0) 是通过 SSTable 的大小来判断是否需要 compaction。

Minor Compaction

Minor Compaction 比较简单，基本代码路径是： DBImpl::CompactMemTable
^[1]
=> DBImpl::WriteLevel0Table
^[2]
=> BuildTable
^[3]
。

Major Compaction

1. 每次 compaction 结束，更新 manifest 之后，都会调用 VersionSet::Finalize
   ^[4]
   计算下一次要进行 major compaction 的 level。

2. 每次 major compaction 开始时，调用 VersionSet::PickCompaction
   ^[5]
   计算需要进行 compaction 的 SSTable。

3. 如果选中的 level-n 的 SSTable 和 level-n+1 的 SSTable 的 key 范围没有重叠，可以直接将 level-n 的 SSTable “移动”到 level-n+1，只需要修改 Manifest。

4. 否则，调用 DBImpl::DoCompactionWork
   ^[6]
   对 level-n 和 level-n+1 的 SSTable 进行多路归并。

Compaction 的问题

Compaction 会对 LevelDB 的性能和稳定性带来一定影响：

1. 消耗 CPU：对 SSTable 进行解析、解压、压缩。
2. 消耗 I/O：大量的 SSTable 批量读写，十几倍甚至几十倍的写放大会消耗不少 I/O，同时缩短 SSD 的寿命（SSD 的写入次数是有限的）。
3. 缓存失效：删除旧 SSTable，生成新 SSTable。新 SSTable 的首次请求无法命中缓存，可能引发系统性能抖动。

常见的做法是，控制 compaction 的速度（比如 RocksDB 的 Rate Limiter
^[7]
），让 compaction 的过程尽可能平缓，不要引起 CPU、I/O、缓存失效的毛刺。这种做法带来一个问题：compaction 的速度应该控制在多少？Compaction 的速度如果太快，会影响系统性能；Compaction 的速度如果太慢，会阻塞写请求。这个速度和具体的硬件能力、工作负载高度相关，往往只能设置一个“经验值”，比较难通用。同时这种做法只能在一定程度上减少系统毛刺、抖动，Compaction 带来的写放大依然是那么大。

写放大简单分析

• +1 – WAL 的写入。
• +1 – Immutable Memtable 写入到 level-0 文件。
• +2 – level-0 和 level-1 的 compaction（level-0 的每个 SSTable 的 key 范围是重叠的。一般控制 level-0 和 level-1 的数据大小是一样的，每次拿全量 level-0 的数据和全量 level-1 的数据进行 compaction）。
• +11 – level-n 和 level-n+1 合并的写入（n >= 1，默认情况下，level-n+1 的数据大小是 level-n 的 10 倍）。

所以，总的写放大是 4 + 11(n-1)  = 11n – 7 倍。
假设有 5 个 level，写放大最大是 48 倍——也就是说，外部写入 1GB 的数据，内部观察到的 I/O 写流量会有 48GB。
关于 LSM-Tree 的写放大有不少论文进行了详细的介绍、讨论和提出优化方案，比如：

1. Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging – 这篇论文将各种 compaction 方式和影响介绍得非常清楚。
2. WiscKey: Separating Keys from Values in SSD-conscious Storage – 通过将键值分离，大大减少了写放大。
3. …

小结

1. 根据实际经验，在大部分场景下， compaction 带来的问题不是特别明显。
2. 一些会有突发流量的情况，很容易造成 compaction 的速度跟不上实际写入的速度，导致写失败。
3. Write intensive 的场景，写放大缩短了 SSD 的寿命也是个问题。

参考资料