关于压缩(Compaction)与压缩(Compression)的区别¶
这段内容在原文是没有的,翻译君实在没有什么好办法,不得不加上这段话
RocksDB 涉及两个压缩概念,英文原文是 Compaction 和 Compression。两个术语用中文翻译,都是“压缩”,实际上大家交流的时候也都是使用“压缩”。这个 wiki 很良心地写了两个压缩的内容,用英语能区分,但是用中文。。。嗯。。。。这里简单介绍下两个压缩的区别。
compaction,在 RocksDB,或者说 LSM 存储中,指的是把数据从 Ln 层,存储到 Ln+1 层这个过程,例如把重复的旧的数据删除之类的。
compression,在这里指的是数据压缩,把 1MB 的数据压缩成 500KB 这样。数据还是那些数据,只是从明文,变成了压缩之后的数据。
他们的关系大概是:
通过 Compaction 把数据压缩到不同的层,每层使用不同的 Compression 算法压缩数据,减少存储空间。
下面开始是正文。
--
压缩算法限制 LSM 树的形状。他们决定了那些排序结果可以被合并以及那些排序结果需要被一个读取操作访问。你可以参考 多线程压缩 了解关于 RocksDB 压缩的更多细节。
压缩算法概述¶
源:https://smalldatum.blogspot.com/2018/08/name-that-compaction-algorithm.html
这里我们展示一系列压缩算法:经典 Leveled,Tiered,Tiered+Leveled,Leveled-N,FIFO。除了这些,RocksDB 实现了 Tiered+Leveled 和 termed Level,Tiered termed Universal,FIFO。
经典 Leveled¶
经典 Leveled 压缩算法,第一次在 O'Neil et al 的 LSM-tree 论文中出现,将读操作的空间放大以及写放大最小化。
LSM 树是一系列的层。每一层都是一个排序结果,可以被按照范围切分成许多分片放到独立的文件中。每一层都比上一层大非常多倍。相邻层的大小倍数叫做扇出,当所有层之间的扇出都相同的时候,写放大会被最小化。把数据压缩进第 N 层(Ln)会把地 N-1 层(Ln-1)的数据合并到 Ln。压缩到 Ln 会把之前和并进 Ln 的数据重写。最坏情况下,每层的写放大等于扇出数,但实际操作中,通常他会比扇出数小,Hyeontaek Lim et al 的论文有相关解释。
原始 LSM 论文中的压缩算法使用 all-to-all 的——所有 Ln-1 的数据会跟所有 Ln 层的数据合并。LevelDB 和 RocksDB 的则是 some-to-some 的——Ln-1 的部分数据和并进 Ln 层的部分数据(有覆盖的部分)
尽管 leveled 的写放大通常比 tiered 要大,但是在某些场景,leveled 是有优势的。首先是按 key 顺序插入,一个 RocksDB 的优化大大减少这种场景的写放大。另一个是有倾向性的写操作,导致只有一小块的 key 会被更新。把 RocksDB 的压缩优先级设置为正确的数值,压缩过程应该在层数最小的,拥有足够空间存储写操作的层停止——他不会一致写到最大层。当 leveled 压缩是 some-to-some 模式,那么压缩只会对 LSM 树的一个写操作覆盖了的分片进行处理,这样可以让写放大比 all-to-all 模式小很多。
Leveled-N¶
Leveled-N 跟 Leveled 压缩算法很像,但是会有更小的写放大,更多的读放大。它允许每层拥有大于一个排序结果。压缩合并所有 Ln-1 的排序结果到 Ln 的一个排序结果中,也就是 Leveled。然后 "-N“会被驾到名称中用于暗示每层可能会有 n 个排序结果。Dostoevsky 的论文定义了一个压缩算法,名称是 Fluid LSM,他最大的层有一个排序结果,但是非最大层有多于一个排序结果。leveled 压缩会在最大层完成
Tiered¶
Tiered 压缩通过增加读放大和空间放大,来最小化写放大。
LSM 树仍旧可以看成是 Niv Dayan 和 Stratos Idreos 论文中讲到的一系列的层。每一层有 N 个排序结果。每个 Ln 层的排序结果都比上一层的排序结果大 n 倍。压缩合并同一层的所有排序结果来构造一个下一层的新的排序结果。这里的 N 与 leveled 压缩的扇出类似。合并到下一层的时候,压缩不会读/重写已经排序好的 Ln 层的结果。每层的写放大是 1,远小于 Leveled 的扇出。
一个比较接近 Tiered 的实现是合并相似大小的排序结果,不必关心层的概念(这个概念会引入一个特定大小的排序结果的目标数字)。大多数(实现)包含一些主压缩的概念,也就是包含最大的排序结果,然后还有一些条件用来触发主,和非主压缩。通常的情况是会导致大量的文件以及自己。
tiered 压缩也有一些挑战:
- 当压缩包含一个最大层的排序结果的时候,会有一个短暂的空间放大。
- 对于那些比较大的排序结果,排序结果的块索引和 bloom 过滤器会比较大。把他们切小块点通常是个好主意。
- 大的排序结果进一步压缩会花费非常多的时间。多线程可能有帮助
- 压缩过程是 all-to-all 的。如果写入有倾向性,并且大多数 key 都不更新,那么大量的排序结果都可能因为 all-to-all 的压缩过程倍重写。在传统的 tiered 算法中,没办法只重写一个大排序结果的一个子集。
对于 tiered 压缩,层的概念通常是一个用于构成 LSM 树形状的概念,以及用于估算写放大。对于 RocksDB 而言,他们还是一个开发细节。L0 之上的层在 LSM 树中可以用来存储更大的排序结果。这样做的好处是可以吧排序结果切分成更小的 SST 文件。这减少了最大的 bloom 过滤器以及块索引块的大小——这对于块索引更友好——并且在分片索引/过滤倍支持之前是一个非常重要的主意。如果引入子压缩,就可以使对大块排序结果进行多线程压缩变为可能。注意 RocksDB 使用“universal”而不是 tiered 这个名字。
Tiered 压缩算法在 RocksDB 的代码里倍命名为“Universal 压缩”。
Tiered+Leveled¶
Tiered+Leveled 会有比 leveled 更小的写放大,以及比 teired 更小的空间放大。
Tiered+Leveled 实现方式是一种混合实现,在小的层使用 tiered,在大的层使用 leveld。具体哪一层切换 tiered 和 leveled 可以非常灵活。现在我假定如果 Ln 是 leveled 那么所有之后的层(Ln+1,Ln+2)都是 leveled。
VLDB2018 的 SlimDB 是一个 tiered+leveled 的例子,机关它允许 Lk 层使用 tiered,Ln 使用 leveled,而 k>n。Fluid LSM 倍描述为 tiered+leveled 的实现,但是我认为它是 Leveled-N。
RocksDB 中的 Leveled 压缩也是 Tiered+Leveled。遵照 max_write_buffer_number 的设置,可能会有 N 个排序结果在 memtable 这一层——只有一个是活跃可写的,剩下的都是只读,等待落盘的。一个 memtable 落盘过程类似于 tiered 压缩——memtable 的输出在 L0 构建一个新的排序结果并且不需要读/重写 L0 上已经存在的排序结果。根据 level0_file_num_compaction_trigger 的配置,L0 可以有多个排序结果。所以 L0 是 Teired 的。memtable 层没有压缩,所以也就没有该层是 tiered 还是 leveled 的说法。RocksDB 中 L0 的子压缩过程会更加有趣,但这是另一篇文章的内容了。
FIFO¶
FIFO 风格的压缩在淘汰的时候把最老的文件丢弃,可以被用于缓存数据。
选项¶
这里我们给出选项的概述以及他们如何影响压缩:
- Options::compaction_style —— RocksDB 目前支持两种压缩算法——Universal 风格和 Level 风格。这个选项在这两个之间切换。可以是 kCompactionStyleUniversal 或者 kCompactionStyleLevel。如果是 kCompactionStyleUniversal,你可以用 Options::compaction_options_universal 配置 universal 风格参数。
- Options::disable_auto_compactions——关闭自动压缩。你仍然可以选择手动压缩。
- Options::compaction_filter——允许应用在后台压缩的时候修改/删除一个键值对。如果希望针对不同的压缩过程,使用不同的过滤器,客户需要提供一个 compaction_filter_factory。用户只能声明一种压缩过滤器或者工厂。
- Options::compaction_filter_factory——一个用于提供允许应用在后台压缩的时候修改/删除一个键值对的过滤器的工厂。
其他会影响压缩性能以及触发条件的选项是:
- Options::access_hint_on_compaction_start——压缩启动的时候,声明文件访问模式。对于该压缩的所有文件都会应用这个选项。默认:NORMAL
- Options::level0_file_num_compaction_trigger——触发 level0 压缩发生的文件数量。一个负数表示 level-0 压缩不会因为文件数量而被触发。
- Options::target_file_size_base 与 Options::target_file_size_multiplier——压缩的目标文件大小。target_file_size_base 是 level-1 的每个文件的大小。Level-L 目标文件的大小可以通过 target_file_size_base * (target_file_size_multiplier ^ (L-1))
来计算。比如,如果 target_file_size_base 为 2MB,target_file_size_multiplier 为 10,那么 level-1 的每个文件大小就为 2MB,level2 每个文件的大小就是 20MB,level3 的文件就是 200MB。默认的 target_file_size_base 为 64MB,target_file_size_multiplier 为 1。
- Options::max_compaction_bytes——所有压缩后的文件的最大大小。如果需要压缩的文件总大小大于这个值,我们在压缩的时候会避免展开更低级别的文件。
- Options::max_background_compactions——后台并发执行的最大线程数,会提交给默认优先级为 LOW 的线程池。
- Options::compaction_readahead_size——如果非零,我们在压缩的时候会做更大的读。如果你在机械硬盘上运行 RocksDB,你应该把这个值设置为至少 2MB。如果你不使用直接 IO,我们会强制设置这个为 2MB。
压缩还可以人工触发,参考 人工触发压缩
参考 rocksdb/options.h 了解更多的选项信息。
Leveled 风格压缩¶
Universal 风格压缩¶
关于 Universal 风格的压缩的描述,参考 Universal-Compaction-Style
如果你正在使用 Universal 风格的压缩,有一个 CompactionOptionsUniversal 对象,会持有该风格的所有特殊压缩配置。额外的定义在 rocksdb/universal_compaction.h,你可以在 Options::compaction_options_universal 中设置他。我们在这里简单介绍 Options::compaction_options_universal:
- CompactionOptionsUniversal::size_ratio —— 比较文件大小的时候的灵活性比例。如果候选文件的大小比下一个文件小 1%,那么把下一个文件也包括进压缩候选集。默认:1
- CompactionOptionsUniversal::min_merge_width —— 一次压缩中最小的文件数量。默认:2
- CompactionOptionsUniversal::max_merge_width —— 一次压缩中最大的文件数量。默认:UINT_MAX
- CompactionOptionsUniversal::max_size_amplification_percent —— 空间放大被定义为一个 byte 的数据存储在硬盘上需要多少额外的存储空间。例如,一个空间放大为 2% 意味着一个持有 100byte 用户数据的数据库,需要占用 102byte 的物理存储。通过这个定义,一个完全压缩的数据库的空间放大为 0%。RocksDB 用下面公式计算空间放大率:假设所有文件,除了最早的文件以外,都计算进空间放大中。默认 200,这意味着一个 100byte 的数据库可能需要占用 300byte 存储。
- CompactionOptionsUniversal::compression_size_percent —— 如果这个选项被设置为 -1(默认值),所有的输出文件都会根据指定的压缩(compress)类型进行压缩(compress)。如果这个选项不是负数,我们会尝试确保压缩(compress)大小刚好比这个值大。正常情况下,至少这个比例的数据会被压缩。当我们把压缩(compact)到一个新的文件,他是不是需要被压缩(compress)的标准是这样的:假设根据生成时间排序的文件列表如下:[A1....An B1....Bm C1....Ct],A1 是最新的,而 Ct 时最老的,我们将把 B1...Bm 压缩 [compact],我们计算所有的文件大小为总的大小 total_size,我们把 C1...Ct 的总大小计算为 total_C,如果 total_C / total_size < compression_size_percent,压缩(compact)输出的文件会被压缩(compress)。(这个行为看起来很诡异,但是代码确实是这么写的。。。)
- CompactionOptionsUniversal::stop_style —— 停止选取下一个文件的算法条件。可以是 kCompactionStopStyleSimilarSize(选择相似大小的文件)或者 kCompactionStopStyleTotalSize(选取的文件的总大小>下一个文件)。默认为 kCompactionStopStyleTotalSize
FIFO 压缩风格¶
参考 FIFO压缩风格
线程池¶
压缩过程在线程池中进行,参考 线程池