分类： NOSQL
2019-05-24 07:04:48
leveldb使用memtable/sstable的设计。其中sstable全称为sorted string table，顾名思义，是一组按字符串排序的表，sstable以分层的方式进行组织。每个level的数据量大约是上一层的10倍。由内存flush直接生成的sorted table放置于一个特殊的“young level”(也称为level-0)。当young level的文件数超过某个阈值（目前是4），就会将所有overlapping【注意overlapping的含义，是指键值范围(key range)上的重叠】的young files跟level-1 file进行merge，生成一组新的level-1文件，每个level-1文件包含2M数据（level-0是1M的文件，其他level都是2M的文件）。
young level中不同的文件可能包含相互重叠的键值。而其他各个level中的文件key range不会重叠【层内不重叠，跨层当然会重叠】。对于特定的层L(L >= 1)，如果level-L的文件总大小超过10^L MB（例如lelel-1 10M, level-2 100M），那么level-L中会有一个文件，跟level-(L+1)中键值范围重叠的所有文件进行合并，生成一组新的level-(L+1)文件。这些merge操作从效果上讲，会逐步将最新的update操作从young level迁移到最大level中，这个过程只用到了bulk reads/writes，从而将磁盘操作的代价最小化。
若level-L的总大小超过上限，levelDB会在后台线程中进行compact操作。该操作会选定某个level-L文件，以及level-(L+1)中所有范围与之重叠的文件。注意，即使level-L跟level-(L+1)文件的范围仅部分重合，level-(L+1)的整个文件也会用于compact操作的输入，并在操作完成后丢弃。从level-0向level-1进行compact时，会有些特殊处理，因为level-0本层的文件之间相互会有overlapping。如果遇到层内范围重合的情况，level-0的compact可能选定多于一个的level-0文件。
level-L的compact操作将所有选定的文件(通常一个L层，若干个L+1层)，重新生成为一组level-(L+1)文件。levelDB生成新的文件过程中，每当current output file数据达到2M时就写满，转而开始生成一个新的level-(L+1)文件。还有一个条件会触发levelDB生成新的level-(L+1)文件，即current output file的key range已经增长到可以覆盖10个level-(L+2)文件。这样做是为了避免后续对level-(L+1)进行compact时，不会选中过多的level-(L+2)文件。
还有一个问题，leveldb确定要对level-L进行compact操作之后，如何决定选择哪个文件呢？这里的策略是在整个key space循环轮流compact。具体而言，levelDB针对每一层都记录上次compact操作的ending key，下次compact操作会根据该key选定文件。
从上面的论述，我们可以推断level-0 compact操作最坏情况下会选定本层所有4个1M的文件，以及所有的level-1文件(10MB)，这种情况下levelDB将需要读14M并写14M。
跟level-0 compact的特殊情况不同，其他层L的compact只选定本层一个2M的文件，最坏情况下，该文件的key range跟level-(L+1)的大约12个文件重合（L+1是L层的10倍，加上两头的范围通常并不对齐，就是12个文件了）。因而该操作要读26m，写26m。假设磁盘io速率为100MB/s，则最坏情况下耗时大约0.5s。
如果我们对后台读写进行限速，例如只能使用100MB/s的10%，则compact操作大约要花费5s。这段时间新生成的level-0文件，不可以进行compact。如果用户写入的速率是10M/s，可能导致levelDB创建很多的level-0文件（5秒大约要积压大约50m，每个文件1m，就是约50个文件）。这会大幅增加read操作的代价，因为每次read要合并从大量文件读取的结果。
前面讲了选定level之后所进行的操作。那么leveldb 如何选定在哪层进行compact操作？leveldb会对每一层计算一个score，该值等于 current bytes / desired bytes。对于level-0，score = files / desired files。然后会选定score最大的层来compact。
选定L0进行compact的话，还有一个特殊之处，即选定了primary L0 file之后，还需要检查L0的其他文件，如果有重叠，则也要选定。通常来说，L0的compact会选定所有的L0文件，但并不总是如此。
参考资料：
https://github.com/basho/leveldb/blob/develop/db/version_set.cc 的 PickCompaction 函数
http://blog.sina.com.cn/s/blog_4575b5690102wny5.html
