Rocksdb金沙官网线上: Compaction原理

概述

     compaction主要包括两类:将内存中imutable 转储到磁盘上sst的过程称之为flush或者minor compaction;磁盘上的sst文件从低层向高层转储的过程称之为compaction或者是major compaction。对于myrocks来说,compaction过程都由后台线程触发,对于minor compaction和major compaction分别对应一组线程,通过参数rocksdb_max_background_flushes和rocksdb_max_background_compactions可以来控制。通过minor compaction,内存中的数据不断地写入的磁盘,保证有足够的内存来应对新的写入;而通过major compaction,多层之间的SST文件的重复数据和无用的数据可以迅速减少,进而减少sst文件占用的磁盘空间。对于读而言,由于需要访问的sst文件变少了,也会有性能的提升。由于compaction过程在后台不断地做,单位时间内compaction的内容不多,不会影响整体的性能,当然这个可以根据实际的场景对参数进行调整,compaction的整体架构可以参见图1。了解了compaction的基本概念,下面会详细介绍compaction的流程,主要包括两部分flush(minor compaction),compaction(major compaction),对应的入口函数分别是BackgroundFlush和BackgroundCompaction。

金沙官网线上 1

                                          图1

flush(minor-compaction)

      Rockdb中在内存的数据都是通过memtable存储,主要包括两种形式,active-memtable和immutable-memtable。active-memtable是当前正在提供写操作的memtable,当active-memtable写入超过阀值(通过参数wirte_buffer_size控制),会将这个memtable标记为read-only,然后再创建一个新的memtable供新的写入,这个read-only的memtable就是immutable-memtable。我们所说的flush操作就是将imumutable-memtable 写入到level0的过程。flush过程以column family为单位进行,一个column family是一组sst文件的集合,在myrocks中一个表可以是一个单独的column family,也可以多个表共用一个column family。每个column family中可能包含一个或多个immutable-memtable,一个flush线程会抓取column family中所有的immutable-memtable进行merge,然后flush到level0。由于一个线程在flush过程中,新的写入也源源不断进来,进而产生新的immutable-memtable,其它flush线程可以新起一个任务进行flush,因此在rocksdb体系下,active-memtable->immutable-memtable->sst文件转换过程是流水作业,并且flush可以并发执行,相对于levelDB,并发compaction的速度要快很多。通过参数max_write_buffer_number可以控制memtable的总数量,如果写入非常快,而compaction很慢,会导致memtable数量超过阀值,导致write stall的严重后果。另外一个参数是min_write_buffer_number_to_merge,整个参数是控制至少几个immutable才会触发flush,默认是1。flush的基本流程如下:

1.遍历immutable-list,如果没有其它线程flush,则加入队列

2.通过迭代器逐一扫描key-value,将key-value写入到data-block 

3.如果data block大小已经超过block_size(比如16k),或者已经key-value对是最后的一对,则触发一次block-flush

4.根据压缩算法对block进行压缩,并生成对应的index block记录(begin_key, last_key, offset)

5.至此若干个block已经写入文件,并为每个block生成了indexblock记录

6.写入index block,meta block,metaindex block以及footer信息到文件尾

7.将变化sst文件的元信息写入manifest文件

      flush实质是对memtable中的记录进行一次有序遍历,在这个过程中会去掉一些冗余的记录,然后以block为单位写入sst文件,写入文件时根据压缩策略确定是否对block进行压缩。为什么会有冗余记录?这个主要是因为rocksdb中无论是insert,update还是delete,所有的写入操作都是以append的方式写入memtable,比如先后对key=1的记录执行三个操作insert(1),update(1),delete(1),在rocksdb中会产生3条不同记录。(在innodb中,对于同一个key的操作都是原地更新,只有一条记录)。实际上delete后这个记录不应该存在了,所以在合并时,可以干掉这些冗余的记录,比如这里的insert(1),update(1),这种合并使得flush到level0的sst已经比较紧凑。冗余记录主要有以下三种情况:(user_key, op)表示对user_key的操作,比如put,delete等。

1.对于(user_key,put),(user_key,delete),则可以将put删掉

2.对于(user_key,single-delete),(user_key,put),single-delete保证put,delete成对出现,可以同时将两条记录都删掉。

3.对于(user_key,put1),(user_key,put2),(user_key,put3)可以干掉比较老的put

对于以上3种情况,都要考虑snapshot,如果要删除的key在某个snapshot可见,则不能删除。注意第1种情况,(user_key,delete)这条记录是不能被删除的,因为对用户而言,这条记录已经不存在了,但由于rocksdb的LSM-tree存储结构,这个user_key的记录可能在level0,level1或者levelN,所以(user_key, delete)这条记录要保留,直到进行最后一层的compaction操作时才能将它干掉。第2种情况,single-delete是一个特殊的delete操作,这个操作保证了put,delete一定是成对出现的,所以flush时,可以将这两条记录同时干掉。 

compaction(major-compaction)

       我们通常所说的compaction就是major-compaction,sst文件从低level合并到高level的过程,这个过程与flush过程类似,也是通过迭代器将多个sst文件的key进行merge,遍历key然后创建sst文件。flush的触发条件是immutable memtable的数量是否超过了min_write_buffer_number_to_merge,而compaction的触发条件是两类:文件个数和文件大小。对于level0,触发条件是sst文件个数,通过参数level0_file_num_compaction_trigger控制,score通过sst文件数目与level0_file_num_compaction_trigger的比值得到。level1-levelN触发条件是sst文件的大小,通过参数max_bytes_for_level_base和max_bytes_for_level_multiplier来控制每一层最大的容量,score是本层当前的总容量与能存放的最大容量的比值。rocksdb中通过一个任务队列维护compaction任务流,通过判断某个level是否满足compaction条件来加入队列,然后从队列中获取任务来进行compact。compaction的主要流程如下:

1.首先找score最高的level,如果level的score>1,则选择从这个level进行compaction

2.根据一定的策略,从level中选择一个sst文件进行compact,对于level0,由于sst文件之间(minkey,maxkey)有重叠,所以可能有多个。

3.从level中选出的文件,我们能计算出(minkey,maxkey)

4.从level+1中选出与(minkey,maxkey)有重叠的sst文件

5.多个sst文件进行归并排序,合并写出到sst文件

6.根据压缩策略,对写出的sst文件进行压缩

7.合并结束后,利用VersionEdit更新VersionSet,更新统计信息

     上面的步骤基本介绍了compaction的流程,简单来说就是选择某个level的sst文件与level+1中存在重叠的sst文件进行合并,然后将合并后的文件写入到level+1层的过程。通过判断每个level的score是否大于1,确定level是否需要compact;对于level中sst文件的选择,会有几种策略,默认是选择文件size较大,包含delete记录较多的sst文件,这种文件尽快合并有利于缩小空间。关于选择sst文件的策略可以参考options.h中的CompactionPri的定义。每次会从level中选取一个sst文件与下层compact,但由于level0中可能会有多个sst文件存在重叠的范围,因此一次compaction可能有多个level0的sst文件参与。rocksdb后台一般有多个线程执行compact任务,compaction线程不断地从任务队列中获取任务,也会不断地检查每个level是否需要compact,然后加入到队列,因此整体来看,compact过程是并发的,但并发的基本原则是,多个并发任务不会有重叠的key。对于level0来说,由于多个sst文件会存在重叠的key范围,根据level0,level+1中参与compact的sst文件key范围进行分区,划分为多个子任务进行compact,所有子任务并发执行,都执行完成后,整个compact过程结束。另外还有一个问题要说明的是,compact时并不是都需要合并,如果level中的输入sst文件与level+1中无重叠,则可以直接将文件移到level+1中。 

Universal Compaction

      前面介绍的compaction类型是level compaction,在rocksdb中还有一类compaction,称之为Univeral Compaction。Univeral模式中,所有的sst文件都可能存在重叠的key范围。对于R1,R2,R3,...,Rn,每个R是一个sst文件,R1中包含了最新的数据,而Rn包含了最老的数据。合并的前提条件是sst文件数目大于level0_file_num_compaction_trigger,如果没有达到这个阀值,则不会触发合并。在满足前置条件的情况下,按优先级顺序触发以下合并。

1.如果空间放大超过一定的比例,则所有sst进行一次compaction,所谓的full compaction,通过参数max_size_amplification_percent控制。

2.如果前size(R1)小于size(R2)在一定比例,默认1%,则与R1与R2一起进行compaction,如果(R1+R2)*(100+ratio)%100<R3,则将R3也加入到compaction任务中,依次顺序加入sst文件

3.如果第1和第2种情况都没有compaction,则强制选择前N个文件进行合并。

      相对于level compaction,Univeral compaction由于每一次合并的文件较多,相对于level compaction的多层合并,写放大较小,付出的代价是空间放大较大。除了前面介绍的level compaction和univeral compaction,rocksdb还支持一种FIFO的compaction。FIFO顾名思义就是先进先出,这种模式周期性地删除旧数据。在FIFO模式下,所有文件都在level0,当sst文件总大小超过阀值max_table_files_size,则删除最老的sst文件。整个compaction是LSM-tree数据结构的核心,也是rocksDB的核心,本文梳理了几种compaction方式的基本流程,里面还有很多的细节没有涉及到,有兴趣的同学可以在本文的基础上仔细阅读源码,加深对compaction的理解。

附录

金沙官网线上,相关文件:

rocksdb/db/flush_job.cc 

include/rocksdb/universal_compaction.h

rocksdb/db/compaction_job.cc

db/compaction_picker.cc

rocksdb/table/block_based_table_builder.cc

相关接口:

FlushMemTableToOutputFile //flush memtable到level0

FlushJob::Run  //flush memtable 任务

PickMemtablesToFlush //选择可以flush的immutable-memtable

WriteLevel0Table //刷sst文件到level0

BuildTable //实现创建sst文件

UniversalCompactionPicker::NeedsCompaction //是否需要compact

PickCompaction //需要进行compact的sst文件

PickCompactionUniversalReadAmp //选择相邻的sst文件进行合并

NeedsCompaction //判断文件是否level是否需要compact

LevelCompactionPicker::PickCompaction // 获取level中sst文件进行compact

LevelCompactionPicker::PickCompactionBySize

IsTrivialMove // 是否可以移动更深的Level,没有overlap的情况下。

ShouldFormSubcompactions  // 判断是否可以将compaction任务分片

CompactionJob::Prepare    // 划分子任务

CompactionJob::Run()      // compaction的具体实现 

BlockBasedTableBuilder::Finish  //生成sst文件

参考文档

http://rocksdb.org/blog/2016/01/29/compaction_pri.html

http://smalldatum.blogspot.com/2016/02/compaction-priority-in-rocksdb.html

http://rocksdb.org/blog/2016/01/29/compaction_pri.html

https://github.com/facebook/rocksdb/blob/v3.11/include/rocksdb/options.h#L366-L423

http://rocksdb.org/blog/2015/07/23/dynamic-level.html

https://github.com/facebook/rocksdb/wiki/RocksDB-Tuning-Guide

http://alinuxer.sinaapp.com/?p=400

http://dirtysalt.github.io/leveldb.html

http://openinx.github.io/2014/08/17/leveldb-compaction/

http://www.cnblogs.com/KevinT/p/3819134.html

http://luodw.cc/2015/11/04/leveldb-20/

本文由金沙官网线上发布于数据库,转载请注明出处:Rocksdb金沙官网线上: Compaction原理

您可能还会对下面的文章感兴趣: