介绍

leveldb用compaction对已有的sstable进行合并，并且删除不再有效的kv数据，减少数据规模和减少文件数量。

主要方式

bigtable中讲到三种类型的compaction， minor，major和full。

minor compaction就是把memtable中的数据导出到SSTable中；

major compaction就是合并不同级别的SSTable

full则是合并所有的SSTable

其中LevelDB包含前两种，即minor和major。

minor compaction

当满足一些其他条件之后（这里的其他条件不涉及到这个阈值大小）(mem_->ApproximateMemoryUsage() > options_.write_buffer_size) 就会有

    log_ = new log::Writer(lfile);
    imm_ = mem_;
    has_imm_.Release_Store(imm_);
    mem_ = new MemTable(internal_comparator_);

这些操作，及上面描述的操作。而再查找write_buffer_size在Options::Options() 中进行了如下初始化write_buffer_size(4<<20),所以这里不知道是不是文档过久未更新的原因，所以从代码来看应该是阈值达到4MB时。而且这里的计算也不是已日志文件为依据的，而是以memtable的内存使用量为依据，当然这里两个数据应该是相差不大的，只是直观上来说应该是memtable的内存使用量。

1、先将memtable转换为immutable memtable，此时不能往其中写入记录，只能从中读取KV内容。memtable其实是一个多层级队列skiplist，其中的记录是根据key有序排列的。所以只需要直接顺序写入SSTABLE就可以。已经被标记删除的key不会在此时删除，会在更高层级的compaction中去做。

Major compaction

当某个level下的SSTable文件数目超过一定设置值后，levelDb会从这个level的SSTable中选择一个文件（level>0），将其和高一层级的level+1的SSTable文件合并，这就是major compaction。

对于level0

Level 0的SSTable文件有些特殊，尽管每个文件也是根据Key由小到大排列，但是因为level 0的文件是通过minor compaction直接生成的，所以任意两个level 0下的两个sstable文件可能再key范围上有重叠。所以在做major compaction的时候，对于大于level 0的层级，选择其中一个文件就行，但是对于level 0来说，指定某个文件后，本level中很可能有其他SSTable文件的key范围和这个文件有重叠，这种情况下，要找出所有有重叠的文件和level 1的文件进行合并，即level 0在进行文件选择的时候，可能会有多个文件参与major compaction。

选择哪些文件compaction和合并？

levelDb在选定某个level进行compaction后，还要选择是具体哪个文件要进行compaction，levelDb在这里有个小技巧， 就是说轮流来，比如这次是文件A进行compaction，那么下次就是在key range上紧挨着文件A的文件B进行compaction，这样每个文件都会有机会轮流和高层的level 文件进行合并。

如果选好了level L的文件A和level L+1层的文件进行合并，那么问题又来了，应该选择level L+1哪些文件进行合并？levelDb选择L+1层中和文件A在key range上有重叠的所有文件来和文件A进行合并。

也就是说，选定了level L的文件A,之后在level L+1中找到了所有需要合并的文件B,C,D…..等等。剩下的问题就是具体是如何进行major 合并的？就是说给定了一系列文件，每个文件内部是key有序的，如何对这些文件进行合并，使得新生成的文件仍然Key有序，同时抛掉哪些不再有价值的KV 数据。

major合并过程

Major compaction的过程如下：对多个文件采用多路归并排序的方式，依次找出其中最小的Key记录，也就是对多个文件中的所有记录重新进行排序。之后采取一定的标准判断这个Key是否还需要保存，如果判断没有保存价值，那么直接抛掉，如果觉得还需要继续保存，那么就将其写入level L+1层中新生成的一个SSTable文件中。就这样对KV数据一一处理，形成了一系列新的L+1层数据文件，之前的L层文件和L+1层参与compaction 的文件数据此时已经没有意义了，所以全部删除。这样就完成了L层和L+1层文件记录的合并过程。

哪些数据被抛弃

那么在major compaction过程中，判断一个KV记录是否抛弃的标准是什么呢？其中一个标准是:对于某个key来说，如果在小于L层中存在这个Key，那么这个KV在major compaction过程中可以抛掉。因为我们前面分析过，对于层级低于L的文件中如果存在同一Key的记录，那么说明对于Key来说，有更新鲜的Value存在，那么过去的Value就等于没有意义了，所以可以删除。