Compaction过程

由上述所示，compaction分为两类：

• minor compaction
• major compaction

这两类compaction负责在不同的场景下进行不同的数据整理。

Minor Compaction

一次minorcompaction非常简单，其本质就是将一个内存数据库中的所有数据持久化到一个磁盘文件中。

每次minorcompaction结束后，都会生成一个新的sstable文件，也意味着Leveldb的版本状态发生了变化，会进行一个版本的更替。有关版本控制的内容，将在接下去一篇文章中详细展开。

值得注意的是，minorcompaction是一个时效性要求非常高的过程，要求其在尽可能短的时间内完成，否则就会堵塞正常的写入操作，因此minorcompaction的优先级高于major compaction。当进行minorcompaction的时候有major compaction正在进行，则会首先暂停majorcompaction。

Major Compaction

相比于minor compaction，majorcompaction就会复杂地多。首先看一下一次major compaction的示意图。

0层中浅蓝色的三个sstable文件，加上1层中的绿色的sstable文件，四个文件进行了合并，输出成两个按序组织的新的1层sstable文件进行替换。

条件

那么什么时候，会触发leveldb进行majorcompaction呢。总结地来说为以下三个条件：

• 当0层文件数超过预定的上限（默认为4个）；
• 当level i层文件的总大小超过(10 ^ i) MB；
• 当某个文件无效读取的次数过多；

0层文件个数规定

由于compaction的其中一个目的是为了提高读取的效率，因此leveldb不允许0层存在过多的文件数，一旦超过了上限值，即可进行majorcompaction。

非0层文件数据大小限制

对于level i（i >=1）的情况来说，一个读取最多只会访问一个sstable文件，因此，本身对于读取效率的影响不会太大。针对于这部分数据发生compaction的条件，从提升读取效率转变成了降低compaction的IO开销。

假设leveldb的合并策略只有第一条，那么会导致1层文件的个数越来越多或者总的数据量越来越大，而通常一次合并中，0层文件key的取值范围是很大的，导致每一次0层文件与1层文件进行合并时，1层文件输入文件的总数据量非常庞大。所以不仅需要控制0层文件的个数，同样，每一层文件的总大小同样需要进行控制，使得每次进行compaction时，IO开销尽量保持常量。

故leveldb规定，1层文件总大小上限为10MB，2层为100MB，依次类推，最高层（7层）没有限制。

文件读取次数过多

以上两个机制能够保证随着合并的进行，数据是严格下沉的，但是仍然存在一个问题。

假设0层文件完成合并之后，1层文件同时达到了数据上限，同时需要进行合并。

更加糟糕的是，在最差的情况下，0-n层的文件同时达到了合并的条件，每一层都需要进行合并。

其中一种优化机制是：

• source层的文件个数只有一个；
• source层文件与source+1层文件没有重叠；
• source层文件与source+2层的文件重叠部分不超过10个文件；

当满足这几个条件时，可以将souce层的该文件直接移至source+1层。

但是该条件非常苛刻，还是无法解决上述问题。为了避免可能存在这种“巨大”的合并开销，leveldb引入了第三个机制：”错峰合并“。

那么（1）如何找寻这种适合错峰合并的文件（2）以及如果判断哪个时机是适合进行错峰合并的呢？

对于问题（1）Leveldb的作者认为，一个文件一次查询的开销为10ms,若某个文件的查询次数过多，且查询在该文件中不命中,那么这种行为就可以视为无效的查询开销，这种文件就可以进行错峰合并。

对于问题（2），对于一个1MB的文件，对其合并的开销为25ms。因此当一个文件1MB的文件无效查询超过25次时，便可以对其进行合并。

对于一个1MB的文件，其合并开销为（1）source层1MB的文件读取，（2）source+1层10-12MB的文件读取（3）source+1层10-12MB的文件写入。

总结25MB的文件IO开销，除以100MB／s的文件IO速度，估计开销为25ms。

采样探测

在每个sstable文件的元数据中，还有一个额外的字段seekLeft，默认为文件的大小除以16KB。

leveldb在正常的数据访问时，会顺带进行采样探测。正常的数据访问包括（1）用户直接调用Get接口（2）用户使用迭代器进行访问。

采样的规则：

记录本次访问的第一个sstable文件。若在该文件中访问命中，则不做任何处理；若在该文件中访问不命中，则对该文件的seekLeft标志做减一操作。

知道某一个文件的seekLeft标志减少到0时，触发对该文件的错峰合并。

故以上三种机制可以保障每次进行compaction的时候，总体开销不会呈现上升趋势。

过程

整个compaction可以简单地分为以下几步：

• 寻找合适的输入文件；
• 根据key重叠情况扩大输入文件集合；
• 多路合并；
• 积分计算；寻找输入文件：

不同情况下发起的合并动作，其初始的输入文件不同。

对于level 0层文件数过多引发的合并场景或由于leveli层文件总量过大的合并场景，采用轮转的方法选择起始输入文件，记录了上一次该层合并的文件的最大key，下一次则选择在此key之后的首个文件。

对于错峰合并，起始输入文件则为该查询次数过多的文件。

扩大输入文件集合

该过程如下：

• 红星标注的为起始输入文件；
• 在leveli层中，查找与起始输入文件有key重叠的文件，如图中红线所标注，最终构成leveli层的输入文件；
• 利用level i层的输入文件，在leveli+1层找寻有key重叠的文件，结果为绿线标注的文件，构成leveli，i+1层的输入文件；
• 最后利用两层的输入文件，在不扩大level i+1输入文件的前提下，查找leveli层的有key重叠的文件，结果为蓝线标准的文件，构成最终的输入文件；

多路合并：

多路合并的过程比较简单，即将level i层的文件，与leveli+1层的文件中的数据项，按序整理之后，输出到leveli+1层的若干个新文件中，即合并完成。

注意在整理的过程中，需要将冗余的数据进行清理，即同一条数据的多个版本信息，只保留最新的那一份。

但是要注意，某些仍然在使用的旧版本的数据，在此时不能立刻删除，而得等到用户使用结束，释放句柄后，根据引用计数来进行清除。

积分计算

每一次compaction都会消除若干source层的旧文件，新增source+1层的新文件，因此触发进行合并的条件状态可能也发生了变化。故在leveldb中，使用了计分牌来维护每一层文件的文件个数及数据总量信息，来挑选出下一个需要进行合并的层数。

计分的规则很简单：

• 对于0层文件，该层的分数为文件总数／4；
• 对于非0层文件，该层的分数为文件数据总量／数据总量上限；

将得分最高的层数记录，若该得分超过1，则为下一次进行合并的层数；