带你全面了解 compaction 的 13 个问题
作者： h5n1 原文来源：https://tidb.net/blog/eedf77ff
1 概述
TiKV 底层存储引擎使用 RocksDB ，RocksDB 是一个基于 LSM tree 的单机嵌入式数据库， 对于 LSM Tree 来说 compaction 是个非常重要的操作，本文对 TiKV 中涉及的 compaction 相关内容进行了整理总结。
2 为什么需要 compaction ?
LSM Tree 通过将所有的数据修改操作转换为追加写方式：对于 insert 直接写入新的 kv，对于 update 则写入修改后的 kv，对于 delete 则写入一条 tombstone 标记删除的记录。通过这种方式将磁盘的随机写入转换为顺序写从而提高了写入性能，但不能进行 in-place 更新，由此带来了以下问题：
1、 大量的冗余和无效数据占用磁盘空间，造成空间放大。
2、 读取数据时如果内存中没有的话，需要从 L0 层开始进行查找 sst file，造成读放大。
因此通过 compaction 操作将数据下层进行合并、清理已标记删除的数据降低空间放大、读放大的影响。但是 compaction 又带来了写放大的问题，因此不同的数据库根据需要使用不同的 compact 策略，以达到读、写、空间最优的平衡。Compaction 属于资源密集型操作，需要读写大量的数据并进行排序，消耗较多的 IO、CPU 资源。
3 Compaction 做什么？
RocksDB 的 compaction 包含 2 方面：一是 memtable 写满后 flush 到磁盘，这是一种特殊的 compacttion，也称为 minor compaction。二是从 L0 层开始往下层合并数据，也被称为 major compaction，也是常说的 compaction。
Compaction 实际上就是一个归并排序的过程，将 Ln 层写入 Ln+1 层，过滤掉已经 delete 的数据，实现数据物理删除。其主要过程:
1、 准备：根据一定条件和优先级等从 Ln/Ln+1 层选择需要合并的 sst 文件，确定需要处理的 key 范围。
2、处理：将读到 key value 数据，进行合并、排序，处理不同类型的 key 的操作。
3、写入：将排序好的数据写入到 Ln+1 层 sst 文件，更新元数据信息。
4 Compaction 有哪些常见算法？
以下几种算法是学术性的理论算法，不同的数据库在具体实现时会有优化调整
Classic Leveled
由 O’Neil 在 LSM tree 论文中第一次提出，该算法中每层只有一个 Sorted-Run(每个 sorted-run 是一组有序的数据集合) ， 以分区方式包含在多个文件内，每一层大小是上一层的固定倍数 (叫 fanout)。合并时使用 all-to-all 方式, 每次都将 Ln 的所有数据合并到 Ln+1 层，并将 Ln+1 层重写，会读取 Ln+1 层所有数据。 RocskDB 使用 some-to-some 方式每次合并时只读写部分数据。
Leveled-N
和上面 Classic Leveled 类似，不过每层可以有 N 个 Rorted-Run，每层的数据不是完全有序的。
Tiered
Tiered 方式同样每层可以包含多个 Sorted-Run ，Ln 层所有的数据向下合并到 Ln+1 层新的 Sorted-Run，不需要读取 Ln+1 层原有的数据。Tiered 方式能够最大的减少写放大，提升写入性能。
FIFO
只有 1 层，写放大最小，每次 compaction 删除最老的文件，适合于带时间序列的数据。
RocksDB 中 compaction 算法支持 Leveled compaction、Universal compaction、FIFO compaction。 对于 Leveled compaction 实际上是 tiered+leveled 组合方式 (后续描述均为此方式)，Universal compaction 即 tiered compaction。
RocksDB 的 leveled compaction 中 level 0 包含有多个 sorted-run，有多个 sst 文件，之间存在数据重叠，在 compaction 时将所有 L0 文件合并到 L1 层。对于 L1-Lmax 层，每一层都是一个有序的 Rorted-Run，包含有多个 sst file。在进行读取时首先使用二分查找可能包含数据的文件，然后在文件内使用二分查找需要的数据。
在 TiKV 内可使用 compaction-style 参数修改每个 CF 的 compaction 算法，支持的选项值包括 0- level compaction(默认)、1-universal compaction 、2- FIFO，而 Level 总层数可通过参数 num-levels 控制，默认为 7 层。
5 ColumnFamily 和 SST file 的关系？
RocksDB 内使用 Column Family(CF) 来进行数据的逻辑隔离，CF 内可以使用不同的 key，每个 CF 使用不同的 memtable 和 sst 文件，所有的 CF 共享 WAL、Manifest。每个 CF 的 memtable flush 时都会切换 WAL，其他的 CF 也开始使用新的 WAL，旧的 WAL 要保证里面所有 CF 的数据都被 flush 后才能删除。
在 RocskDB 内每个 Column Family 都分配了一个 ID，在 SST 文件有 Column Family ID，默认 L1 层 sst file 的大小由参数 target-file-size-base 决定，L2-Lmax 的 sst 文件大小为 target-file-size-base*target_file_size_multiplier (默认为 1), TiDB 内支持参数 target-file-size-base，默认为 8M。
经过 CF 的逻辑划分后类似结构如下:
在 TiDB 中存在 2 个 rocksdb 实例, 一个用于存储实际的用户数据，称为 kv db，另一个用于存储 raft log，叫做 raft db(6.1.0 版本开始 raft db 默认被 raft egine 取代)。kv db 有 4 个 CF：default、write、lock、raft ，raft db 只有一个 default CF。
6 什么时候触发 compaction ?
RocksDB 的 compaction 由后台线程 BGWorkCompaction 进行调度。该线程的触发一般有手动触发和自动触发两种情况：
手动触发
RocksDB 提供 CompactRange、CompactFiles 等接口允许用户手动 compaction，从而使用户能根据自己的场景触发 compaction。
自动触发
当 WAL 切换或 memtable 被写满后会调用检查是否需要进行 compaction，具体如下：
1、 Memtable 达到 write-buffer-size(TiKV 内默认 128M) 参数大小时会转换为 immtuable memtable 等待 flush 到磁盘，并开启一个新的 memtable 用于写入。
2、 Memtable flush 时会导致 WAL 切换，同时当 WAL 大小达到 max-total-wal-size(TiKV 默认 4G) 时也会进行切换。
3、 当达到如下条件时则调度 compaction 线程执行 compact 操作。
(1) sst 文件设置以下标记时：达到 ttl 时间、达到定期 compaction 时间、已被标记为 compaction 等。
(2) 遍历所有 level，计算每层的 score，如果 score>1，则需要 compaction，当有多个 level 都达到触发条件时，会选择 score 最大的 level 先进行 compact。score 计算方法如下：
L0 层：当前 L0 sst 文件数和 level0-file-num-compaction-trigger 参数比例。
L1 层：Ln 层总大小 (不包含正在 compact 的文件) 和 max-bytes-for-level-base*max-bytes-for-level-multiplier^(N-1) 的比例。
除了上面的条件触发方式外，RocksDB 使用 BottomMost Recompaction 对最底层的 delete 记录进行再次检查和清理：当某个操作执行时其快照引用的文件位于最底层时，如果包含很多 delete 则这些 delete 的数据不能通过正常的 compact 方式清理掉，因此在操作执行完后 release snapshot 时重新检查 bottommost level ，确定哪些文件可以被 compact，comapct 后生成的文件仍位于最底层。
自动 compaction 可通过 disable-auto-compactions 参数关闭，从而可以让用户只使用自定义的 compaction 策略，TiKV 内同样支持该参数设置。Compaction 的触发原因可通过监控 TiKV Detail –> RocksDB KV/ RocksDB raft -> Compaction reason 查看。
7 Compaction 时选择那些文件?
当选定需要 compaction 的 Ln 层后便需要决定需要向下层合并哪些文件，在选择需要合并的文件时主要考虑 2 方面：文件优先级和范围边界。
文件优先级
选择优先级最高的文件进行合并，如果该文件正被其他线程进行合并，则按照优先级依次往下选择。目前有 4 种优先级策略，在 tikv 内可通过参数 compaction-pri 设置，可选值
0 (ByCompensatedSize)，1 (OldestLargestSeqFirst)，2 (OldestSmallestSeqFirst)，3 (MinOverlappingRatio)。
1、 ByCompensatedSize
优先选择包含 delete 做多的文件，越早删除的数据就越早 compact，减少空间放大和读放大
2、 OldestLargestSeqFirst
优先选择最后更新时间最早的文件，将文件上的冷数据合并到下一层，相对热数据留在上一层，减少读放大。 TiKV 的 lockcf 默认使用该策略。
3、 OldestSmallestSeqFirst
优先选择包含最老数据的文件，通常有较大 key 范围数据长时间未向下合并，与下层的 key 重叠较少，减少写放大。
4、 MinOverlappingRatio
优先选择和下层 key 重叠率最小的文件，TiKV 的 defaultcf 、writecf 的默认使用策略。
范围边界
通过文件优先级选定文件后还要考虑文件的 key 范围，扩大需要 compact 的文件范围，如下 5 个文件，如果在 f3 优先级最高，则在 compact 时同时将{f2,f3,f4} 3 个文件向下合并，因为 f2、f4 中 key 范围与 f3 有重叠，因此 compact 的 key 范围由[k4,k6]扩展到了[k3,k8]。如果选择的文件中有任何文件在被 compact 则会终止 compact 文件选择过程。
对于 Ln+1 层需要按照上述方式对与 Ln 层有重叠 key 范围的文件进行扩展，然后将 Ln、Ln+1 选择的文件内的 key 作为 input 数据进行归并排序、清理冗余数据后写入 Ln+1 层。如果 Ln 层要 compact 的文件与下层无重叠，则直接将该文件移动到 Ln+1 层。
为了限制每次 compaction 的量大小，RocksDB 支持通过 max_compaction_bytes 参数限制每轮 compact 的大小，该参数仅限制 input level 的大小，TiKV 内支持该参数配置
8 L0 层文件堆积后如何处理？
当有大量数据写入时，如果 L0 到 L1 的 compaction 速度来不及处理会导致 L0 层文件逐渐累积增多，通过 subcompact 并行方式可提升 L0 层 compact 速度。当 L0 层文件数量达到一定数量后则会引起 write stall，文件数量达到 level0-slowdown-writes-trigger 后 会降低写入速度，当达到 level0-stop-writes-trigger 后则完全停止写入。
当 L0 向 L1 层合并时，如果 L1 层的 sst file 正在往 L2 层合并被锁住，将导致本次 L0 -> L1 层的 compact 不能执行，因此造成 L0 层文件不能及时清理。基于此 RocksDB 引入了 intra-L0 compaction，即在发生上述情况时在 L0 层内部进行 compact, 将多个 sst file 合并为 1 个大的 sst file，以此减少 L0 层文件数量，在一定程度上能够提升 L0 层的读性能和减少 write stall 的发生。
9 如何设置 compaction 并发线程数？
Flush & Compaction
Flush 线程和 Compaction 线程是 RocksDB 的 2 类后台线程 ，使用线程池方式管理，在 memtable 写满或 WAL 切换时检查是否需要 flush 或 compaction，如果需要则从线程池里调度线程完成 flush 或 compaction。
默认情况下 RocksDB(5.6.1 版本) 对 flush 和 compaction 线程池统一进行管理，通过 Options::max_background_jobs 选项可设置后台线程最大数量，RocksDB 会自动调整 flush 和 compaction 线程数量。仍可以通过 Options::max_background_flushes 和 Options::max_background_compactions 选项设置 flush 和 compact 线程的数量。flush 线程由于其关键性会放入 HighPriority 线程池，而 compact 线程放入 LowPriority 线程池。
TiKV 内提供了参数 max-background-jobs、max-background-flushes 可用于调整 Options::max_background_jobs 和 Options::max_background_flushes，TiKV 会根据上述参数值计算 compact 线程数量。TiKV 内线程数默认计算如下：
max_background_jobs = MAX(2, max-background-jobs 参数)
max_flushs = MIN(max_background_jobs+ 3) / 4, max_background_flushes)
max_compactions = max_background_jobs - max_flushs
SubCompaction
由于 L0 层文件由 memtable flush 生成文件之间存在重叠，不能以 sst file 为最小分组单位进行并发 compaction，因此通过单线程将 L0 所有文件都合并到 L1 层。L0 to L1 的并发合并使用 subcompaction 方式：
(1) 首先获取 L0 层和 L1 层涉及的每个 sst 文件的 smallest key/largest key
(2) 将这些 Key 去重排序，每 2 个 key 分为一组作为一个 range，预估 key 范围覆盖的 sst 文件的总大小 sum。
(3) 根据参数 max_subcompaction、range 的数量、sum/4.0/5/max_file_size 中的最小值决定 subcompaction 线程数量。
(4) 将 range 分配给每个线程，每个线程只处理文件的一部分 key 的 compact，最后 compact 主线程将 subcompact 线程的结果进行合并整理。
在 TiKV 内可通过参数 max-sub-compactions 设置 subcompaction 的最大并发线程数，kv db 默认为 3，raft db 默认为 2。SubCompact 线程数量不受 max-background-jobs 限制，但 TiKV 内设置的默认数量受 max_compaction 线程数影响，计算方式为：max_sub_compactions =MAX(1,MIN(max_sub_compactions 参数, (max_compactions - 1)))。
除了 L0 -> L1 compact 时可使用 subcompaction 外，在 manual compaction(leveled compction) 时 L1+ 层也使用 subcompaction 以加快速度。
10 SST 文件什么时候删除？
RocksDB 使用 version 来表示数据库的当前状态（即某一时刻 sst 文件的集合），每当增加或删除一个 sst file 时都会对 Manifest 增加一条 version edit 记录。当执行查询或修改时会引用当前 version，同时会对该 version 下的 sst file 设置 reference count。
Compact 完成后会在 output level 生成新的文件，同时需要删除旧的 Input 文件，如果仍有其他操作在 compact 后仍未执行完成，则在 compact 后不能立即将需要的文件删除，等到 sst file 的 reference count 降为 0 后才能将文件真正的删除。
11 Compaction Guard
如前面介绍，在 compact 选择文件时由于 key 范围重叠，因此会扩展选定的 sst 文件，以包含进所有需要的 Key，由此会造成的问题是需要额外读写一些多余的 key，同时由于一个 sst file 里可能包含有多个不同的 key，在对某段范围 key 删除后不方便直接删除 sst file。
Comapction Guard 是根据 key 将 sst 文件分隔成一个个具有指定边界的小文件，从而降低 compaction 时读写 key 数量和方便物理删除 sst file。
TiKV 利用 RocksDB 的 SST Partitioner 接口实现 compaction guard，在 compact 时将 sst file 按照 region 的 end key 进行切分，实现了大部分的 region 和 sst file 对应，只对 kv db 的 default CF、write CF 有效，通过按 region 切分 sst file 后可以实现 sst file 的快速删除，也能提升 region 迁移速度。
该功能默认启用通过参数 enable_compaction_guard 设置，当启用后 使用 compaction-guard-max-output-file-size 覆盖 target-file-size-base 的参数值。如果 sst file 大小小于 compaction-guard-min-output-file-size(默认 8M) 或大于 compaction-guard-maxt-output-file-size 时都不会触发 compaction guard 进行切分。
12 TiDB 内有哪些场景触发 Compaction?
和 RocksDB 类似 TiDB 内也有自动和手动 compaction，不过无论是自动还手动都是通过调用 RockDB 的 manual compaction 函数在 RocksDB 内产生一次手动 compact。
自动 compaction
对于 wirte/default cf，每隔 region-compact-check-interval(默认 5 分钟) 时间，就会检查是否需要触发手动 RocskDB 的 compact，如果一个 region 中 tombstone key 数量超过 region-compact-min-tombstones (默认 10000) 并且 tombstone key 数量超过 Key 数量的 region-compact-tombstones-percent（默认 30%）, 则会触发 tikv 的自动 compaction，每次会检查 region-compact-check-step(默认 100) 个 region，tikv 会调用 RockDB 的 manual compaction 函数 CompactRange 在 RocksDB 内产生一次手动 compact。
对于 lockcf 每隔 lock-cf-compact-threshold(默认 10 分钟)，如果 lockcf 的数据量达到 lock-cf-compact-threshold 则会调用 RockDB 的 manual compaction 函数。
手动 compaction
手动 compaction 是指使用 tikv-ctl 命令执行的 compact。具体可参考 TiDB 官方文档 tikv-ctl 工具介绍。
13 WriteStall 有哪些触发场景
当 RocksDB 的 flush 或 compact 速度落后于数据写入速度就会增加空间放大和读放大，可能导致磁盘空间被撑满或严重的读性能下降，为此则需要限制数据写入速度或者完全停止写入，这个限制就是 write stall， write stall 触发原因有：1、 memtable 数量过多 2、L0 文件数量过多 3、 待 compact 的数据量过多。
memtable 数量过多
当 memtable 数量达到 min-write-buffer-number-to-merge(默认值为 1)
参数个时会触发 flsush，Flush 慢主要由于磁盘性能问题引起，当等待 flush 的 memetable 数量 >= 参数 max-write-buffer-number 时会完全停止写入。当 max-write-buffer-number>3 且等待 flush 的 memetable 数量 >= 参数 max-write-buffer-number-1 时会降低写入速度。
当由于 memtable 数量引起 write stall 时，内存充足的情况下可尝试调大 max-write-buffer-number、max_background_jobs 、write_buffer_size 进行缓解。
L0 数量过多
当 L0 sst 文件数达到 level0_slowdown_writes_trigger 后会触发 write stall 降低写入速度，当达到 level0_stop_writes_trigger 则完全停止写入。
当由于 memtable 数量引起 write stall 时，内存充足的情况下可尝试调大 max_background_jobs 、write_buffer_size、min-write-buffer-number-to-merge 进行缓解。
待 compact 的数据量过多
当需要 compact 的文件数量达到 soft_pending_compaction_byte 参数值时会触发 write stall，降低写入速度，当达到 hard_pending_compaction_byte 时会完全停止写入.
TiKV 内提供了相关监控用于观察 compact 的相关活动，可通过 TiKV Detail -> RockDB KV/rfat 中相关面板查看。
触发 write stall 的原因可通过 Write Stall Reason 面板查看。
等待 compact 的文件大小：
Compact 的读写速度：
5.2 版本开始，tidb 优化流控机制，在 scheduler 层进行流控代替 rocksdb 的 wrtie stall 机制，可以避免 write stall 机制卡住 Raftstore 或 Apply 线程导致的次生问题，该功能通过 storage.flow-control 控制是否开启流量控制机制。开启后，TiKV 会自动关闭 KV DB 的 write stall 机制，还会关闭 RaftDB 中除 memtable 以外的 write stall 机制，除此之外还可以使用 memtables-threshold、l0-files-threshold、soft-pending-compaction-bytes-limit、hard-pending-compaction-bytes-limit 等参数来进行控制。
14 GC 和 Compaction 有哪些关联？
为防止系统中存在大量历史版本数据影响系统性能，TiKV 会定期进行 GC 清理已经过期的历史版本，每隔 tidb_gc_run_interval 时间就发起一次 GC，GC 过程主要清理 3 个步骤，1、resolve lock 清理锁，实际调用使用 RockDB 的 delete 将记录设置为 tombstone 。2、truncate/drop table 或 Index 后的 sst 文件清理，直接使用物理删除 sst 文件方式。 3、MVCC 版本清理，使用 RockDB 的 delete 将记录设置为 tombstone ，（GC 相关原理可参考 ：TiDB GC 之原理浅析https://tidb.net/blog/ed740c2c）。
从 GC 原理可以看出虽然在 TiKV 层执行的数据清理但在底层 RocksDB 存储引擎数据是仍然存在的，只是增加了一个被设置了删除标记 tombstone 记录，对于 tombstone 记录要等到 compact 到最底层 bottom level 时才能真正的删除。
GC 属于资源密集型操作，需要较多的 IO 和 CPU 消耗，TiDB 在 5.0 版本引入了 GC in Compaction Filter 功能，在 RocksDB compact 时进行 GC，以降低每次定期 GC 时处理的数据量，加快 GC 处理速度，从而减少读操作和降低 CPU。CompactionFilter 是 RocksDB 的提供的一个接口，允许用户根据自定义的逻辑去修改或删除 KV，从而实现自定义的垃圾回收。
当 RocksDB 执行 compact 时会调用 TiKV 的 CompactionFilter 逻辑，获取当前 safepoint 时间，然后对比 WriteCF 中的 commit_ts，对于 safepoint 前的记录则不会保留，之后采用异步的方式清理 DefaultCF 中的对应数据。由于异步清理 defaultCF 会导致在 WriteCF 中版本记录已经清理但 DefaultCF 中的记录却没有清理，产生 orphan version，为此 TiKV 增加了 DefaultCF 中 orphan version 记录的清理功能，官方对应 GC in Compaction Filter 功能也在不断的增强和完善。
GC 时 CPU 监控可通过 TiKV Detail -> Thread CPU -> GC Worker CPU 面板查看，GC 运行的相关监控可通过 TiKV Detail -> GC 相关面板查看。
15 总结
对于 TiKV 和 RockDB 都在不断完善 compaction 机制，以期降低 LSM Tree 带来的读放大、写放大以及空间放大问题，进一步提升系统性能。同时 TiKV 中提供了丰富的监控指标用于监控 GC 、Compaction 等，方便用户掌握相关运行情况、排查 write stall 等问题原因。
—————————————————————-
参考资料：
https://github.com/facebook/rocksdb/wiki
https://www.jianshu.com/p/88f286142fb7
http://mysql.taobao.org/monthly/2018/10/08/
https://blog.csdn.net/Z_Stand/article/details/107592966
https://kernelmaker.github.io/Rocksdb_Study_5
https://github.com/xieyu/blog/blob/master/src/rocksdb/flush-and-compact.md
https://rocksdb.org/blog/2017/06/26/17-level-based-changes.html
https://github.com/tikv/tikv/pull/8115
https://github.com/facebook/rocksdb/issues/9106
版权声明: 本文为 InfoQ 作者【TiDB 社区干货传送门】的原创文章。
原文链接:【http://xie.infoq.cn/article/eeea9c9d067cfd46d4e2f7a74】。文章转载请联系作者。
TiDB 社区官网:https://tidb.net/ 2021.12.15 加入
TiDB 社区干货传送门是由 TiDB 社区中布道师组委会自发组织的 TiDB 社区优质内容对外宣布的栏目，旨在加深 TiDBer 之间的交流和学习。一起构建有爱、互助、共创共建的 TiDB 社区 https://tidb.net/
评论