前言从半个月前开始写，到现在断断续续地写，但终于能寄出去了(被简单的书吞没了好几次)。 很辛苦。
最近，笔者正在补习有关RocksDB数据库基础的详细内容。 因为：
次要原因——目前，所有Flink实时任务的状态后端都是RocksDB； 主要原因——将在未来利用TiDB构建HTAP服务。 TiDB可以与现有的MySQL无缝协作，其基础是RocksDB。 RocksDB与笔者多次提到的HBase一样，是基于LSM树的存储引擎，但前者偏向于嵌入式应用，重量更轻。 官可以先吃这篇文章获得关于LSM树的前置知识。
首先大致看看RocksDB数据库的读写流程。 其实和HBase很相似。
RocksDB数据库读写的概要直接画画说明。 这张照片取自Flink PMC大人物Stefan Richter在Flink Forward 2018上演讲的PPT，笔者重新绘制。
RocksDB的写缓存(LSM树的最低级别)名为memtable，与HBase中的MemStore相对应； 读缓存名称为block cache，对应于HBase中同名的组件。
执行写入时，同时写入memtable和预写入日志WAL。 当memtable满时，它会自动转换为不变的[immutable]memtable，刷新到磁盘，并创建L0级sstable文件。 sstable是有序字符串表(sorted string table )，内部存储的数据按密钥排序，以下简称SST。
执行读取操作时，首先读取存储器中的数据。 根据局部性原理，写入后立即读取数据的可能性变高。 这意味着activememtable-immutablememtable-block cache。 如果内存未命中，则遍历L0层sstable进行搜索。 如果仍未命中，则用二分搜索法在L1层以上的sstable中找到对应的key。
随着sstable的写入，系统打开的文件越多，累积在同一密钥中的数据的更改(更新、删除)操作也越多。 由于sstable保持不变，因此执行compaction操作，合并多个密钥区间重叠的sstable，以减少文件数量并立即清理无效数据。 本文暂时不能翻译“compaction”一词，但我个人认为它是“压缩”(compression )？ 还是“合并”？ 都是单方面的。
从上述概要可以进一步认识到，LSM树是将读取性能交换为trade-off来获得写入性能的结构，RocksDB中的flush和compaction的操作是LSM思想的核心。 这里介绍了基于LSM的存储通用的两种压缩策略： size-tiered compaction和leveled compaction。
共同的精简战略-分层精简和空间扩大-分层精简的想法非常直接。 每一层允许的SST文件的最大数量具有相同的阈值，下面的阈值为4，说明随着memtable继续刷新到SST，某一层的SST数量达到阈值时的情况。
33559 www.Scylla db.com/2018/01/17/compaction-series-space-amplification/size-tiered compaction的优点是简单易行的单个SST的大小可能会很大，在较高级别通常显示数百GB到TB级别的SST文件。 其缺点是空间扩大严重。 以下详细叙述。
3http://www.Sina.com/(空间应用程序)是指存储引擎中数据实际占用的磁盘空间大于数据的实际大小。 例如，如果数据的真实大小为10MB，并且实际保存时占用了25MB的空间，则“空间放大因子”(space amplification factor )为2.5。
为什么会发生空间扩大呢？ 很明显，LSM-based存储引擎中的所有数据添加或删除都必须等待compaction运行到相应的密钥，而不是原位。 也就是说，一个key可以同时对应多个值，删除标记被认为是特殊的值，只有一个值真正有效，其馀的可以进行空间扩大。 另外，在compaction过程中，由于原始数据在执行完成之前无法删除(防止无法意外恢复)，因此同一compaction的数据最多可以膨胀两倍，这也属于空间扩大的范畴。
为了在Cassandra的size-tiered compaction战略中更容易理解，我举两个例子。 每层的SST数阈值仍为默认值4。
以约3MB/s的速度继续插入新数据(保证统一密钥)，时间和磁盘占有量图表如下。 在照片中可以看到很多毛刺，这就是compaction过程中的空间放大。 请注意，2000 s到2500 s之间还有一个高尖峰。 原始数据量为6GB，但瞬间增加到12GB。 Cassandra在lydhs之间
的compaction，lydhs的缺陷就显现出来了。尽管这只是暂时的，但是也要求我们必须预留出很多不必要的空闲空间，增加成本。 重复写入一个400万条数据的集合（约1.2GB大，保证unique key），共重复写入15次来模拟数据更新，时间与磁盘占用的曲线图如下。这种情况更厉害，最高会占用多达9.3GB磁盘空间，放大因子为7.75。虽然中途也会触发compaction，但是最低只能压缩到3.5GB左右，仍然有近3倍的放大。这是因为重复key过多，就算每层compaction过后消除了本层的空间放大，但key重复的数据仍然存在于较低层中，始终有冗余。只有手动触发了full compaction（即图中2500秒过后的最后一小段），才能完全消除空间放大，但我们也知道full compaction是极耗费性能的。
接下来介绍leveled compaction，看看它是否能解决size-tiered compaction的空间放大问题。
leveled compaction与写放大leveled compaction的思路是：对于L1层及以上的数据，将size-tiered compaction中原本的lydhs拆开，成为多个key互不相交的自信的猎豹的序列，这样的序列叫做“run”。L0层是从memtable flush过来的新SST，该层各个SST的key是可以相交的，并且其数量阈值单独控制（如4）。从L1层开始，每层都包含恰好一个run，并且run内包含的数据量阈值呈指数增长。
下图是假设从L1层开始，每个自信的猎豹的大小都相同（在实际操作中不会强制要求这点），且数据量阈值按10倍增长的示例。即L1最多可以有10个SST，L2最多可以有100个，以此类推。
https://www.scylladb.com/2018/01/31/compaction-series-leveled-compaction/随着SST不断写入，L1的数据量会超过阈值。这时就会选择L1中的至少一个SST，将其数据合并到L2层与其key有交集的那些文件中，并从L1删除这些数据。仍然以上图为例，一个L1层SST的key区间大致能够对应到10个L2层的SST，所以一次compaction会影响到11个文件。该次compaction完成后，L2的数据量又有可能超过阈值，进而触发L2到L3的compaction，如此往复，就可以完成Ln层到Ln+1层的compaction了。
可见，leveled compaction与size-tiered compaction相比，每次做compaction时不必再选取一层内所有的数据，并且每层中SST的key区间都是不相交的，重复key减少了，所以很大程度上缓解了空间放大的问题。重复一遍上一节做的两个实验，曲线图分别如下。
持续写入实验，尖峰消失了。
持续更新实验，磁盘占用量的峰值大幅降低，从原来的9.3GB缩减到了不到4GB。
但是鱼与熊掌不可兼得，空间放大并不是唯一掣肘的因素。仍然以size-tiered compaction的第一个实验为例，写入的总数据量约为9GB大，但是查看磁盘的实际写入量，会发现写入了50个G的数据。这就叫写放大（write amplification）问题。
写放大又是怎么产生的呢？下面的图能够说明。
可见，这是由compaction的本质决定的：同一份数据会不断地随着compaction过程向更高的层级重复写入，有多少层就会写多少次。但是，我们的leveled compaction的写放大要严重得多，同等条件下实际写入量会达到110GB，是size-tiered compaction的两倍有余。这是因为Ln层SST在合并到Ln+1层时是一对多的，故重复写入的次数会更多。在极端情况下，我们甚至可以观测到数十倍的写放大。
写放大会带来两个风险：一是更多的磁盘带宽耗费在了无意义的写操作上，会影响读操作的效率；二是对于闪存存储（SSD），会造成存储介质的寿命更快消耗，因为闪存颗粒的擦写次数是有限制的。在实际使用时，必须权衡好空间放大、写放大、读放大三者的优先级。
RocksDB的混合compaction策略由于上述两种compaction策略都有各自的优缺点，所以RocksDB在L1层及以上采用leveled compaction，而在L0层采用size-tiered compaction。下面分别来看看。
leveled compaction当L0层的文件数目达到level0_file_num_compaction_trigger阈值时，就会触发L0层SST合并到L1。
L1层及以后的compaction过程完全符合前文所述的leveled compaction逻辑，如下图所示，很容易理解。
多个compaction过程是可以并行进行的，如下图所示。最大并行数由max_background_compactions参数来指定。
前面说过，leveled compaction策略中每一层的数据量是有阈值的，那么在RocksDB中这个阈值该如何确定呢？需要分两种情况来讨论。
参数level_compaction_dynamic_level_bytes为false这种情况下，L1层的大小阈值直接由参数max_bytes_for_level_base决定，单位是字节。各层的大小阈值会满足如下的递推关系：
target_size(Lk+1) = target_size(Lk) * max_bytes_for_level_multiplier * max_bytes_for_level_multiplier_additional[k]
其中，max_bytes_for_level_multiplier是固定的倍数因子，max_bytes_for_level_multiplier_additional[k]是第k层对应的可变倍数因子。举个例子，假设max_bytes_for_level_base = 314572800，max_bytes_for_level_multiplier = 10，所有max_bytes_for_level_multiplier_additional[k]都为1，那么就会形成如下图所示的各层阈值。
可见，这与上文讲leveled compaction时的示例是一个意思。
参数level_compaction_dynamic_level_bytes为true这种情况比较特殊。最高一层的大小不设阈值限制，亦即target_size(Ln)就是Ln层的实际大小，而更低层的大小阈值会满足如下的倒推关系：
target_size(Lk-1) = target_size(Lk) / max_bytes_for_level_multiplier
可见，max_bytes_for_level_multiplier的作用从乘法因子变成了除法因子。特别地，如果出现了target_size(Lk) < max_bytes_for_level_base / max_bytes_for_level_multiplier的情况，那么这一层及比它低的层就都不会再存储任何数据。
举个例子，假设现在有7层（包括L0），L6层已经存储了276GB的数据，并且max_bytes_for_level_base = 1073741824，max_bytes_for_level_multiplier = 10，那么就会形成如下图所示的各层阈值，亦即L5~L1的阈值分别是27.6GB、2.76GB、0.276GB、0、0。
可见，有90%的数据都落在了最高一层，9%的数据落在了次高一层。由于每个run包含的key都是不重复的，所以这种情况比上一种更能减少空间放大。
universal compactionuniversal compaction是RocksDB中size-tiered compaction的别名，专门用于L0层的compaction，因为L0层的SST的key区间是几乎肯定有重合的。
前文已经说过，当L0层的文件数目达到level0_file_num_compaction_trigger阈值时，就会触发L0层SST合并到L1。universal compaction还会检查以下条件。
空间放大比例
假设L0层现有的SST文件为(R1, R1, R2, ..., Rn)，其中R1是最新写入的SST，Rn是较旧的SST。所谓空间放大比例，就是指R1~Rn-1文件的总大小除以Rn的大小，如果这个比值比max_size_amplification_percent / 100要大，那么就会将L0层所有SST做compaction。
相邻文件大小比例
有一个参数size_ratio用于控制相邻文件大小比例的阈值。如果size(R2) / size(R1)的比值小于1 + size_ratio / 100，就表示R1和R2两个SST可以做compaction。接下来继续检查size(R3) / size(R1 + R2)是否小于1 + size_ratio / 100，若仍满足，就将R3也加入待compaction的SST里来。如此往复，直到不再满足上述比例条件为止。
当然，如果上述两个条件都没能触发compaction，该策略就会线性地从R1开始合并，直到L0层的文件数目小于level0_file_num_compaction_trigger阈值。
The End还是写的很乱，但就这样吧。
困了。明天加班，民那晚安。