黄东旭解析 TiDB 的核心优势
657
2024-03-31
TiKV 底层存储引擎使用 RocksDB ,RocksDB 是一个基于 LSM tree 的单机嵌入式数据库, 对于LSM Tree 来说compaction是个非常重要的操作,本文对TiKV中涉及的compaction相关内容进行了整理总结。
LSM Tree 通过将所有的数据修改操作转换为追加写方式:对于 insert 直接写入新的kv,对于 update 则写入修改后的kv,对于 delete 则写入一条 tombstone 标记删除的记录。通过这种方式将磁盘的随机写入转换为顺序写从而提高了写入性能,但不能进行 in-place 更新,由此带来了以下问题:
1、 大量的冗余和无效数据占用磁盘空间,造成空间放大。
2、 读取数据时如果内存中没有的话,需要从L0层开始进行查找sst file,造成读放大。
因此通过 compaction 操作将数据下层进行合并、清理已标记删除的数据降低空间放大、读放大的影响。但是compaction 又带来了写放大的问题,因此不同的数据库根据需要使用不同的compact 策略,以达到读、写、空间最优的平衡。Compaction属于资源密集型操作,需要读写大量的数据并进行排序,消耗较多的IO、CPU资源。
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文件,更新元数据信息。
以下几种算法是学术性的理论算法,不同的数据库在具体实现时会有优化调整
Classic Leveled
由ONeil 在 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层。
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。
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查看。
当选定需要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内支持该参数配置
当有大量数据写入时,如果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的发生。
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以加快速度。
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后才能将文件真正的删除。
如前面介绍,在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进行切分。
和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工具介绍。
tikv-ctl --host tikv_ip:port compact -d kv -c default tikv-ctl --host tikv_ip:port compact -d kv -c write --bottommost force当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等参数来进行控制。
为防止系统中存在大量历史版本数据影响系统性能,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 相关面板查看。
对于TiKV和RockDB都在不断完善compaction机制,以期降低LSM Tree带来的读放大、写放大以及空间放大问题,进一步提升系统性能。同时TiKV中提供了丰富的监控指标用于监控GC 、Compaction等,方便用户掌握相关运行情况、排查write stall等问题原因。
----------------------------------------------------------------
参考资料:
https://github.com/tikv/tikv
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
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。