压缩合并

压缩合并

压缩算法约束LSM树的形状。它们决定哪些排序的运行可以被它合并，哪些排序的运行需要被读取操作访问。您可以在这里阅读更多关于RocksDB压缩的内容:多线程压缩（ https://github.com/facebook/rocksdb/wiki/RocksDB-Basics#multi-threaded-compactions ）

压缩算法概述

来源: https://smalldatum.blogspot.com/2018/08/name-that-compaction-algorithm.html

这里我们提供了压缩算法的分类:经典的分层、分层、分层+分层、分级- n、FIFO。其中，RocksDB实现了分层+分层(代码中称为级别压缩)、分层(代码中称为通用)和FIFO。

Classic Leveled 经典分层

由O’Neil等人的LSM-tree paper引入的经典水平压缩，以读写放大为代价，将空间放大最小化。

LSM树是一个层次序列。每个级别都是一个排序的运行，可以将范围划分为多个文件。每一层都比上一层大很多倍。相邻层的大小比有时称为扇出，当在所有层之间使用相同的扇出时，写入放大被最小化。压缩为级别N (Ln)将Ln-1的数据合并为Ln。压缩到Ln重写以前合并到Ln中的数据。在最坏的情况下，每级写放大等于扇出，但在实践中它往往比扇出小，Hyeontaek Lim等人在本文中解释了这一点。原始LSM论文中的压缩是all-to-all—Ln-1中的所有数据与Ln中的所有数据合并。对于LevelDB和RocksDB，它是一些到一些的——Ln-1中的一些数据与Ln中的一些(重叠的)数据合并。

虽然写放大通常在水平比分层情况下更糟，但在一些情况下，水平是有竞争力的。第一个是键顺序插入，在这种情况下，RocksDB优化大大减少了写放大器。第二个是倾斜写入，其中只有一小部分键可能被更新。在RocksDB中，使用正确的压缩优先级值，压缩应该在最小的级别停止，该级别足够大，可以捕获写工作集——它不会一直到最大级别。当级别压缩是some-to-some时，那么只对与写键重叠的LSM树切片进行压缩，这比all-to-all压缩产生的写放大更小。

Leveled-N

level - N 压缩类似于level压缩，但具有更少的写和更多的读放大。它允许每个级别有多个排序的运行。压缩将Ln-1中的所有排序运行合并为Ln中的一个排序运行，这是水平的。然后将“-N”添加到名称中，表示每个级别可以运行n次排序。陀思妥耶夫斯基的论文定义了一种名为Fluid LSM的压缩算法，其中最大层有1个排序运行，而非最大层可以有超过1个排序运行。将压实级别提升到最大级别。

Tiered 分层

分层压缩以读取和空间放大为代价，将写放大最小化。

LSM树仍然可以被看作是由Niv Dayan和Stratos Idreos在陀思妥耶夫斯基的论文中解释的层次序列。每个级别都有N个排序的运行。 Ln中的每次排序运行都比Ln-1中的一次排序运行大~N倍。压缩合并一个级别中的所有排序运行，以在下一个级别中创建一个新的排序运行。在本例中，N类似于水平压实的扇出。合并到Ln时，压缩不会读取/重写Ln中的排序运行。每级的写放大是1，这是远远低于水平，它是扇出。

分层的一种常见方法是合并大小相似的已排序的运行，而不需要层次的概念(层次的概念意味着特定大小的已排序运行的数量的目标)。其中大多数包含一些主压缩的概念，包括最大的排序运行和触发主压缩和非主压缩的条件。太多的文件和太多的字节是典型的条件。

分层压缩有几个挑战:

当压缩包含从最大级别开始的排序运行时，瞬态空间放大很大。
块索引和布鲁姆过滤器对于大的排序运行将是大的。把它们分成更小的部分是个好主意。
大型排序运行的压缩需要很长时间。多线程会有所帮助。
压缩是所有。当存在倾斜且大多数键没有得到更新时，大型排序运行可能会被重写，因为压缩是所有到所有的。在传统的分层算法中，无法重写大型排序运行的子集。

对于分层压缩，级别的概念通常是用来推断LSM树的形状和估计写入放大的概念。对于RocksDB，它们也是一个实现细节。LSM树超过L0的级别可用于存储较大的排序运行。这样做的好处是将大型排序运行划分为较小的SSTs。这减少了最大的bloom过滤器和块索引块的大小(这对块缓存更友好)，而且在支持分区索引/过滤器之前，这是一个大问题。通过使用子压缩，可以实现最大排序运行的多线程压缩。注意，RocksDB使用的名称是通用的，而不是分层的。

在RocksDB代码基中分层压缩称为通用压缩。

Tiered+Leveled

与分层相比，分层+分层具有更少的写放大和更少的空间放大。

分层+分层方法是一种混合方法，它对较小的级别使用分层，对较大的级别使用分层。对于LSM树从分层切换到分层的级别，它是灵活的。现在我假设如果Ln是水平的，那么接下来的所有级别(Ln+1, Ln+2，…)都必须是水平的。

来自VLDB 2018的SlimDB是分层+拉平的一个例子，虽然它可能允许Lk在Ln为k > n拉平时进行分层。流体LSM被描述为分层+拉平，但我认为它是level - n。

RocksDB中的分层压缩也是分层+分层的。max_write_buffer_number选项可以在memtable级别执行N次排序的运行——只有一次是活动的，其余的都是只读的，等待刷新。 memtable刷新类似于分层压缩——memtable输出在L0中创建一个新的排序运行，并且不读取/重写L0中现有的排序运行。由于level0_file_num_compaction_trigger，在级别0 (L0)中可以有N个排序的运行。所以L0是分层的。压缩不会在memtable级别进行，因此不必将其标记为分层或水平。 RocksDB L0中的子压缩使这一点更加有趣，但这是另一篇文章的主题。

FIFO

FIFOStyle 压缩在过时时删除最旧的文件，并可用于类似缓存的数据。

Options 选项

下面我们将概述影响压缩行为的选项:

Options::compaction_style - RocksDB目前支持两种压缩算法-通用样式和级别样式。此选项在两者之间切换。可以是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 - 触发0级压缩的文件数量。负值意味着0级压缩根本不会由文件数量触发。
Options::target_file_size_base 和 Options::target_file_size_multiplier - 压缩的目标文件大小。target_file_size_base是级别1的每个文件大小。目标文件大小级别可以计算L target_file_size_base * (target_file_size_multiplier ^ (L - 1))例如,如果target_file_size_base是2 mb, target_file_size_multiplier是10,然后在一级将2 mb,每个文件和每个文件2级将20 mb,并且每个文件三级将200 mb。默认target_file_size_base为64MB，默认target_file_size_multiplier为1。
Options::max_compaction_bytes - 所有压缩文件中的最大字节数。如果压缩的总压缩覆盖的范围超过这个数量，我们将避免展开压缩的低层文件集。
Options::max_background_compactions - 并发后台作业的最大数量，提交给默认的低优先级线程池
Options::compaction_readahead_size - 如果非零，则在压缩时执行更大的读取。如果您在旋转磁盘上运行RocksDB，您应该将其设置为至少2MB。如果不使用直接I/O设置，我们强制它为2MB。

压缩也可以手动触发。查阅 Manual Compaction 人工压缩( https://github.com/facebook/rocksdb/wiki/Manual-Compaction )

您可以在 rocksdb/options.h 中了解更多有关这些选项的信息

Leveled 风格压缩

参见 Leveled 压缩（ https://github.com/facebook/rocksdb/wiki/Leveled-Compaction ）

普遍风格压缩

有关通用样式压缩的描述，请参见 (Universal compaction style) 通用样式压缩 ( https://github.com/facebook/rocksdb/wiki/Universal-Compaction )

如果您使用的是通用样式压缩，则有一个对象CompactionOptionsUniversal，它包含该压缩的所有不同选项。确切的定义在rocksdb/universal_compact.h中，您可以在Options::compaction_options_universal中设置它。下面我们简要介绍一下CompactionOptionsUniversal中的选项:

CompactionOptionsUniversal::size_ratio - 比较文件大小时的灵活性百分比。如果候选文件的大小比下一个文件的大小小1%，那么将下一个文件包含到这个候选集中。默认值:1
CompactionOptionsUniversal::min_merge_width - 一次压缩运行中文件的最小数量。默认值:2
CompactionOptionsUniversal::max_merge_width - 一次压缩运行中文件的最大数量。默认值:UINT_MAX
CompactionOptionsUniversal::max_size_amplification_percent - 大小放大定义为在数据库中存储单个字节数据所需的额外存储量(以百分比为单位)。例如，2%的大小放大意味着包含100字节用户数据的数据库可能会占用102字节的物理存储空间。根据这个定义，完全压缩的数据库的大小放大为0%。Rocksdb使用以下启发式来计算大小放大:它假设所有文件(不包括最早的文件)都对大小放大有贡献。默认值:200，这意味着一个100字节的数据库可能需要多达300字节的存储空间。
CompactionOptionsUniversal::compression_size_percent - 如果将该选项设置为-1(默认值)，所有输出文件将遵循指定的压缩类型。如果这个选项不为负，我们将尝试确保压缩大小刚好高于这个值。在正常情况下，至少要压缩这个百分比的数据。当我们压缩到一个新文件时，以下是是否需要压缩它的标准: 假设这里是按生成时间排序的文件列表:[A1…一个B1…Bm C1……，其中A1是最新的，Ct是最古老的，我们要压缩B1…Bm，我们计算所有文件的总大小为total_size，以及C1的总大小…Ct作为total_C，如果total_C / total_size < 此百分比，则压缩输出文件将被压缩
CompactionOptionsUniversal::stop_style - 用于停止在单个压缩运行中选择文件的算法。可以是kCompactionStopStyleSimilarSize(选择大小相似的文件)或kCompactionStopStyleTotalSize(选择文件的下一个文件的总大小)。

默认值:kCompactionStopStyleTotalSize

FIFO压缩

参见FIFO压缩样式（ https://github.com/facebook/rocksdb/wiki/FIFO-compaction-style ）

线程池

压缩在线程池中执行。参见线程池。( https://github.com/facebook/rocksdb/wiki/Thread-Pool )

压缩合并

压缩合并

压缩算法概述

Classic Leveled 经典分层

Leveled-N

Tiered 分层

Tiered+Leveled

FIFO

Options 选项

Leveled 风格压缩

普遍 风格压缩

FIFO压缩

线程池

普遍风格压缩