感谢作者，原文链接：https://zhuanlan.zhihu.com/p/391249476
Compaction 是类 LSM Tree KV 存储实现中比较复杂的实现， CockroachDB 目前的 Pebble KV 存储引擎是在 golang/leveldb 的基础上修改并已在 CockroachDB 中代替原 RocksDB 的存储引擎，本文我们将来看下 Pebble 中的 Compaction 实现。
本文假设读者已了解 LSM Tree 的基本概念，不再重复介绍 LSM Tree 概念。
Pebble 的新写入将只需写入顺序的 WAL 并在内存 memtable 中应用修改既可以返回给用户，而 memtable 会在写满时 Flush 为 SST 文件，因此对于写入操作不论是 WAL 还是 Flush SST 都可以追加写，而代价是为了读取在读取 SST 更高效，需要通过 compaction 将 SST 进行整理为多 Level 每个 Level 中有序的结构，所以 compaction 可以理解将读取旧 SST (或 memtable)整理生成新 SST 的过程。
Level 结构中除 L0 中 SST 文件 Range 可能重叠不有序，其他 Level SST 有序不重叠
本文对于 Compaction 的实现我们将关注以下几个问题？
何时触发？
选哪个 Level 的哪些文件作为输入？
如何切分输出文件到目标 Level？
如何减少 Compaction 对读写延迟的影响?
Trigger Compaction
首先我们看下 "何时触发？"的问题，首先在 Pebble 所有 compaction 只有有写入的时才会触发，对于一个持续运行中只有读流量的 Pebble 是不会有 compaction 的。
Pebble 有引入类 LevelDB 的 Read-ReadTriggered Compaction 机制，但需要注意的是该机制只影响被触发后考虑读来选择参与 compaction 的文件，并不会因为读直接触发。
Compaction 可能会在以下情况被触发:
再次 Open DB 恢复数据后可能触发 Flush 和 Compaction
MemTable 切换后可能触发刷 L0 的 Flush
写入完成后(MemTable 引用归零或有 DeleteRange)可能立刻或延迟触发 Flush
Flush 后会尝试触再次 Flush 和 Compaction
Compaction/Flush/Ingest 后的 TableStats 统计收集发现有 DeleteRange 时可能触发
手动触发 Compaction
Close 整个 DB 时会尝试触发 Compaction
Compaction 自身完成后会尝试触发 Compaction
所以通常只有写入数据后的 Flush 会触发 Compaction，不过这里我们需要注意的是这里只是触发，触发不一定会执行，如果不能满足执行条件（e.g. 超过并发，超过 Pacer 限制， 未能找到合适的文件等）触发也不会执行， 常见的检查有：
DB 未在关闭过程中且非 Readonly 才需 Flush 或 Compaction
未有运行中的 Flush 才可 Flush
未被 Snapshot 持有的待刷 MemTable 大小超过 MemTableSize 配置的一半才可 Flush
运行的 Compaction 不大于 MaxConcurrentCompactions 才可 Compaction
找不到合适的 Compaction, 通常是因选择 Level 和文件时冲突等原因后文选择逻辑可看到
Pick Input Output Level and Files
在通过被触发并通满足一些运行条件后，我们先看下应该选择哪个 Level 并选择哪些文件作为输入，而之后选择输出到哪个 Level 的问题。
对于 Flush ，它的输入不是一个 Level 而是 MemTable(代码里是 -1 Level)，而其他正常 Compaction 则首先需要考虑选择从哪个 Level 找文件作为输入相较而言相对复杂
而输出 Level 对于非 L0 都通常都是当前 Level +1， 而 L0 则可能输出到 LBase 或 L0 自己。
LBase 会在每次 Versions 修改加载后后选择，会尽量选择底层 Level, 如果 Level 大小超过LBaseMaxBytes 则向上层选择，所以空 Pebble 的 L0 Compaction 会写到 L6 之后随着数据越来越多慢慢 L5..L4..L3......
Pick Delete-Only Compaction Input
首先尝试使用 DeleteHint(在对每个 SST 收集统计信息时和 flush/compaction 后维护)进行只有 input 没有 output 的 Delete-Only Compaction，会先检查 Hint 的最大 Tombstone SeqNum 和最小文件 SeqNum 之间的 Snapshot 已排空，并检查 Hint 所在 Level(即包含 DeleteRange 的 SST 的 Level)以下的被 Delete Hint 全囊括的 SST，确保没有其他已进行的 Compaction 且再次确认文件中的 Key 都比 Hint 中最早的 tombstone 早且 Snapshot 已排空都在 Hint 范围内则可作为 Delete-Only 的 Input，Delete-Only 的 Input 可能有来自多个 Level 的文件，但其没有 Output。
Delete Hint 会在 SST 被加载或新产生时收集产生，会对连续的 DeleteRange 合并但维护用到的 Tombstone 最小最大 SeqNum，文件最小 SeqNum 和 Range，在之后 Compaction/Flush 后重新检查和 Compaction 范围交叠的已有 Delete Hint 进行维护，如果刚完成的 Compaction 输入文件有最大 SeqNum 比 Hint 的最大 Tombstone SeqNum 大则清理 Hint。
如果有任何可 Delete-Only 的 SST 文件则异步触发 Delete-Only Compaction，不论是否有 Delete-Only Compaction，当前线程继续会继续检查其他 Compaction 触发条件。
Pick Manual Compaction Input
如果是手动触发的 compaction， 会检查指定的 Input Level ≥ Base Level，并确保没有冲突的已运行的 Compaction 如果有冲突将重试几次， 之后根据手动指定的 Level 和 Key Range 选择文件作为 Input 构建 Compaction 并异步触发 Compaction， 当前线程会继续尝试检查其他 Compaction 条件。
所以可以看到手动触发 Compaction 其实并不仅仅只是对指定的 Level 和 Range 进行 Compaction，也会触发其他满足条件的 Auto Compaction。
Pick Auto Compaction Input
选择 Auto Pick 前会再次检查 Compaction 并发度，只有当 L0 读放大超过当前 Compaction 数乘L0CompactionConcurrency 或 CompactionDebt(让 LSM Tree Stable 需 Compact 的数据大小) 超过当前 compaction 数乘 CompactionDebtConcurrency 才可新增并发，可以理解为读放大过大或待 Compaction 量过多两个条件
考虑后者是为了防止持续写入场景因一次 Compaction 完成读放大减少导致的并发度突降。
1） 计算 Level 分数
Auto Pick 首先将计算各个 Level 的 Score，基础 Score 计算方法是:
L0: (2 * 读放大) / L0CompactionThreshold
Other: (Level 中文件预估大小 + Tombstone 可缩减的 Size) / Level 最大大小
”Tombstone 可缩减的 Size“ 包括 Point Delete 和 Range Delete 同时会去除已在运行中 Compaction 文件 Tombstone 的影响
可以看到基础 Score，对于 L0 写放大越大越高，其他 Level 相对最大大小数据越多可删除的数据越多越高。
而在基础 Score 的基础上还会进行调整，调整的方式是 当前层分数 = 当前层分数 / 下一层分数 (如果 Next Level Score 小于 0.01 则除以 0.01), 即最终的 Score 将是当前和下个 Level 的相对值，对比基础 Score 相对越高最终 Score 越高, 调整的目的是避免一直选择 L0 等上层让 L5, L6 等下层饿死，调整后下层 Level 相对更有机会获得高优先级。
之后会按照分数从高到低尝试在 Level 中寻找合适的 Compaction 文件
2) 尝试选择高分 Level 中的文件作为基础输入
首先对于 Score 不足 1 或是最底层(会被 ElisionOnly 处理)可跳过该 Level，之后对于 L0 和非 L0 有不同处理。
对于非 L0 将选择 (和下一层交叠大小 * 1024) / (文件大小 + Tombstone 可缩减大小) 最小作为 Compaction 的基础输入， 可以理解为和下层交叠越少，文件大小越大， Point Delete/ Range Delete 越多的 SST 越容易被选择来 Compaction， 这样可以达到减少写放大且让 tombstone 能尽快向下退并被清理掉的目的，
对于 L0 的 Pick 根据 Output 的不同有两种: L0 → LBase 的 Base Compaction 和 L0→L0 的 Intra-L0 Compaction，Pick 会优先尝试 Base Compaction ， 找不到再尝试 Intra-L0，另外需要注意的是 Pebble L0 是通过 SubLevel 的方式组织，简单说即 L0 的 SST 被组织为多个子层， 上子层比下子层 SeqNum 更新，同子层内的 SST 文件 Range 有序不交叠，在横向上文件希望被切分为尽量对齐的多个 Interval。
对于 BaseCompaction 首先将对 Interval 进行打分，Score 为 Interval 中跨多个 SubLevel 的文件高度(depth)，如果当前 Interval 没有被其他 Interval 运行中的 BaseCompaction 扩展囊括则会再附加 subLevel 数来提高优先级，简单说 Base 的打分希望找到跨有最高重叠文件的 Interval，因为这样的 Interval 被 Compaction 能有效降低 L0 的 SubLevel 高度。之后从高分检查各个 Interval，选择其中第一个文件也即最底层文件为基准，从下层向上将 Interval 中的其他 SubLevel 文件加入候选并维护候选文件的最大最小 interval，并在加入每个文件之后对新加入文件以下 SubLevel 检查扩展加入其他最大最小 interval 内的文件，最终将得到一个正三角形的 input 基础文件集合(最终候选会在更后面扩展为矩阵形输入)，如果候选文件已经在 compaction 则停止新加入文件后的扩展和 Interval 内向上的扩展返回已加入的候选，最终如果候选能减少 SubLevel 高度大于 minCompactionDepth (目前 1)且参与的文件大于 100 MiB 小于 500 MiB 且和新加入层(包括扩展)新增大小不超过 150% 则可作为有效候选，对最终候选也将再次检查有没有其他正在进行的 Compaction， 如果有则继续尝试下个低分 interval。
如果 BaseCompaction 不能找到合适 Compaction， 则尝试 Intra-L0 Compaction 和 Base 很类似首先也将对 Interval 按照文件高度(depth)打分，然后从高分开始检查 Interval， 不同的是将从 Interval 中最后一个文件也即最上层的文件为基准向下层将 Interval 中的文件加入候选，并每次加入后进行扩展，因此会形成一个倒三角形的输入文件集合， 如果加 Interval 或扩展的文件有在 Compaction 则停止扩展和加 Interval 内文件只用已有文件作为候选， 最终如果候选能减少 SubLevel 高度大于 minCompactionDepth (目前 1)且参与的文件大于 100 MiB 小于 500 MiB 且和新加入层(包括扩展)新增大小不超过 150% 则可作为有效候选， 对于最终候选将再次尝试将倒三角输入扩展为矩形输入。
3) 尝试 Elision-Only Compaction
如果对所有 Level 都无法找到合适的 Compaction， 则会尝试在最低层 L6 寻找满足：
或删除的数目 > 10% 总记录数
或 Delete Range Size > 10% Size
的 SST 文件中最大 SeqNum 最小且对应 Seq 的 Snapshot 已排空的文件，进行 L6 → L6 的 Compaction，该操作不能优化读写但可让 Tombstone 占用的空间释放。
4) 尝试 Read-ReadTriggered Compaction
如果 Elision-Only 也没有合适的，则将尝试 Read-ReadTriggered， 首先在读取侧每个文件会维护 AllowedSeeks 计数，并根据文件大小初始一个不小于 100 值，读操作采样的在 seek 时 -1 当减到 0 时读操作将 pending 一个 readCompaction，而在 compaction 这如看到有 pending 的 readCompaction 则会对，对应 seek 多 level 中的 key range 尝试一次 compaction。
前面 4 步获取的 compaction 的输入通常还将再次修正， 首先需将 input 扩展到 Delete Range 所需的 atomic compaction unit，即如果 Delete Range 内的多个 SST 需同时被 Compaction，同样保证扩展后的 input 没有在 compaction，否则当前 Pick 不可用(会继续尝试其他 Level 或其他选择)
之后根据 Input 圈定 Output Level 中重叠的文件并对 Output 中重叠文件做相同扩展到 atomic compaction unit 的操作，加入 Output Level 中重叠文件可能会扩大 Compaction 的最大最小 Key。
注：最后 Compaction 会将 input 文件和 input 圈定的 output 层中重叠文件做归并。
因为 Compaction 的最大最小 Key 可能的变化，最后还会再尝试做一次扩展输入操作：
对于非 L0 Base Compaction，将用最新的最大最小 Key 找更多的重叠输入文件，并用新重叠文件到 output level 中找重叠，如果增加新输入文件不会导致输出文件数量变得更多则可以扩展，否则忽略这次扩展用原 Pick(注这里扩展同时需考虑不能已在 compaction)，新加入的同样需要保证不破坏 Delete Range
对于 L0 Base 则会先找到前一个文件的最大和后一个文件的最小 Key 来计算最大最小 Interval Index，并对该范围将前面选择正三角形输入扩大为矩形，新加入的同样需不破坏 Delete Range
到这里 compaction 的 input 和 output 中的文件即用于 compaction 的将被归并的文件。
Choose Split Output Files
在获取输入文件后，即可以通过 Iterator 合并 Input Level 和输出 Level 中重叠文件，迭代处理过程会有如消除被 Point 或 Delete Range 消除的 Key， merge 操作等细节，不过本节我们将关注“获得了实际要输出 Key Value 后，怎么写出文件，何时切分文件的问题”？
在获得实际要输出 Key Value 对后，在输出过程中将做以下检查：
超过目标 Level 对文件大小的限制则切换新文件，因为要保证切分点是 UserKey 可能会大一些
输出文件如果和下层文件重叠超过level TargetFileSize 的 10 倍则切分
如果是 Flush 会对输出按照 L0 SubLevel 已有切分点让写入切新文件
切分检查会保证切分 Key 是 UserKey， 且保证前一个 SST 的最大 Key SeqNum 不是特殊的 0 值。
规则 1 比较简单， 我们先看下规则 2： 因为输出的下层交叠过多需切分，主要实现是在新文件一开始用首 Key 到下层查找算出可能的 Limit，然后写出每个 Key 时检查超过 Limit 就切，只是需要处理当前文件如果被前面文件 Delete Range 囊括，则需用前一个文件的最大 UserKey 来去下层找 Limit，而如果找到 Limit 比 Delete Range 大则用 Delete Range 的开始 Key 再次修正 Limit。
另外规则 3：按照已有的 SubLevel 切分点切分，在创建 Flush Compaction 任务时会将当前 Version 的 SubLevel SplitKeys 给到 Compaction 任务，之后写出 Key 时比较简单只需根据 SplitKey 进行文件切分即可，但相对有些复杂的是 SubLevel SplitKeys 的计算，这个过程发生在 Version 每次变化之后重新计算(SubLevel 作为 RocksDB 没有而 Pebble 特有的东西并没有持久化到 Manifest 所以需每次 Version 变更后重新计算)， 而重新计算 SubLevel 信息并初始化 SplitKeys 的过程是：
用 L0 文件的 Start Key 排序去重将整个 Key 空间切分为连续的多个 Interval
遍历 L0 文件对每个文件维护正确的最大最下 interval index 信息，同时维护每个 interval 的文件数并维护 interval 的最大最小文件 interval， 同时在文件加入 interval 时发现已有文件则设置 sublevel + 1
遍历最终的 interval 列表，每当累计预估 interval 内 Byte 超过 flushSplitMaxBytes * subLevel 数时用 interval 的 Start Key 作为 SplitKey。
通过该方式可以感觉上在重建时恢复之前的 SubLevel 和 SplitKey， SubLevel 的 SplitKey 选取很大程度上决定最终 SubLevel 的效果。
可以看到在目标 Level 切分文件主要依据是： Level 本身文件大小限制，避免和下下层过多交叠影响后续 Compaction 的限制 和 Level 0 SubLeve 为了保持 SubLevel 形态的切分，另外具体切分会处理 Delete Range 等细节。
Compaction as fast as needed
Compaction 作为后台任务运行影响前台读写处理导致延迟尖刺问题是 LSM Tree 常见问题，在写入压力特别大资源不足时努力 Compaction 恢复 LSM Tree 稳定看上去是必须的(因为再不清理可能马上要 Stall， 当然也有一些希望在这种情况下做 Limit 的问题这里不讨论)，但在写入速度不是很快时我们希望不因 Compaction 运行影响正常读写，本节我们看下 Pebble 的 Compaction Pacer。
Pebble 分别提供了对 Flush / Compaction / Delete Obsolete 的 Pacer, 因为是独立三个 Pacer 支持各自设置限速。
Flush Pacer: 只有当"未 Flush 大小"小于 MemTableSize * 105% 时，才会限制 Flush 速度(默认 1MiB/s), 即通过动态计算的"未 Flush 大小”阈值动态判断当前 Flush 是否能跟上上游写入，如果跟得上则控制速度，否则全开
Compaction Pacer: 只有“让 LSM Tree 稳定所需 Compaction 的大小预估” 小于 MemTableSize * L0 写放大预估 时限制 Compaction 速度( 默认 4 MiB/S), 即通过动态计算的 CompactionDebt 阈值动态判断当前 Compaction 是否跟上上游写入，如果跟得上则控制速度，否则全开
Delete Pacer: 只在剩余空间不足 16GiB 或可删除文件大小比率大于 20% 时才按照 MinDeletionRate 配置进行速率限制(默认为 0 不限制)
可以看到目前 3 个 Pacer 都是通过内部指标和阈值相比的方式来动态推断清理是否可以跟上写入，如果能跟上则限制写入速度，如果写入超过清理速度则火力全开清理。
Summary
本文我们通过回答开始提出的 4 个问题的方式看了下 Pebble 的 Compaction 的一些实现，和上篇专栏文章相比并没有深入代码细节，但尝试改善了下说明方式同时也帮助自己整理理解，希望能帮助了解 Pebble Compaction~
网友评论