LevelDB Compaction
简介
LevelDB 中的 Compaction 分为两种，Minor Compaction 和 Major Compaction 。
Minor Compaction
Minor Compaction 将内存中的 MemTable dump 到外存，产生一个 SSTable 文件。
此外，Minor Compaction 优先级高于 Major Compaction 。
Major Compaction
Major Combination 用于 level 间的 merge ，一次合并将层 i 的一个 SSTable 合并到层 i+1 。
- 对于 level > 0 的 SSTable，选择其中一个 SSTable 与 下一层 SSTable 做合并
- 对于 level-0 的 SSTable，会将 SSTable 合并成多个不重叠的 1 层 SSTable 。
触发时机
- 当 0 层 SSTable 数超过阈值（默认为 4）
- 由于 Compaction 的其中一个目的是为了提高读取的效率，因此 LevelDB 不允许 0 层存在过多的文件数，一旦超过了上限值，即可进行 Major Compaction。
- 当 level-i 层 SSTable 的总大小超过阈值（10^i MB）
- 对于level i（i >= 1）的情况来说，一个读取最多只会访问一个 SSTable 文件，因此，SSTable 数对于读取效率的影响不会太大。针对于这部分数据发生 Compaction 的条件，从提升读取效率转变成了降低 Compaction 的 IO 开销。此外，这也有助于减低 Compaction 的开销。
- 当某个 SSTable 无效读取的次数过多 :
Compaction 与版本
需要注意到，每次 Compaction 后，LevelDB 的持久化数据的 Snapshot （亦即 SSTable + WAL） 的版本就发生变化了。
Compaction 速度问题
注意到 Compaction 存在两个问题：
- Compaction 对外存 I/O 带宽的挤占
- Compaction 可能跟不上 MemTable 的写入速度
所以 LevelDB 规定了两个变量：
- 当 0 层文件数量超过
SlowdownTrigger时，写入的速度主要减慢 - 当 0 层文件数量超过
PauseTrigger时，写入暂停，直至 Major Compaction 完成
评价
- 消耗 CPU 和 I/O 资源
- 缓存失效
这两者可能引起毛刺，一种方式是限速，但也不能限速太过。
写放大分析
- +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 倍。