LevelDB储存过程解析

本文是研究LevelDB结构之后为了加深印象写的，然后主要是写存储过程的细节（其实本来像画个gif来实现的，但是太麻烦了……）。细节部分都是靠各种资料总结的，然后推荐先看一下文章底部的资料，因为有些重复部分没写

如有理解错误，还请指出

首先收到一个添加key的请求，先直接写入log文件（追加写入）

然后插入到内存的储存区（内存储存区内按照key的顺序排列），等到内存储存的数据达到一定大小后（1M），将内存内的数据写入level为0的sst文件内，然后删除log（这里说一下需要注意的是level0内的数据都是直接从内存写入的，所以不同sst文件的key可能会有重复，和其他level不同，其他level在合并的时候都会去掉重复key，不过level0不经过合并这个步骤（当然要是每次从内存写入的时候都更新一下也行，但是io消耗太大，不如在合并到level1的时候进行操作）。所以说level0和其他level相比，更像一个缓存数据用的）

等到level0级别的sst文件达到一定数量后，挑选其中一个sst文件合并到level1（如果没有level1那么就生成level1，其他level也是这么来的。然后因为level0会有重复key（上面也说过原因），所以合并到level1的时候会先去掉和被选中的sst文件内重复的key再合并（所以可能会涉及到level0级别的多个sst文件更新））

合并的时候会检查level0中的key是否和level1中的key有重合，如果有重合那就读取重合的文件和level0中被挑选的sst文件进行更新key，然后排序key之后再按照2M一个sst文件写入level1（这里就可以看出key按照顺序排列的好处了，因为挨着的key基本都在一个文件里，从level0里选择sst文件的key是挨着的，level1的也是，更新的话只需要更新1~2个文件，能减少需要读取的sst文件个数。比如level0抽取的sst文件key是A1~C3的，和level1里面A1~C5的sst刚好能重合，就只需要读取一个文件进行合并了。如果是按照插入顺序之类的乱序，可能会从N个文件里找到重复的key，合并需要读取的文件也就会更多了）

等到level1的文件数据达到10M时（每个级别最大数据量为10^level，level1为10M，level2就是100M），就选择其中一个sst文件合并到leve2。合并方法也是找到重复的key更新，排序，然后生成sst。不过这一层的sst单个文件不再是2M，而是更大一些，每增加一层sst文件最大限制都会扩大。这样设计是为了一层满了之后不至于逐层更新。

剩下的level层也是像上面那样进行更新，所以level最大的一层，数据也是最旧的

删除操作和更新操作基本也都是直接插入数据，只不过删除操作插入的是删除标记，更新操作是直接重新插入一遍数据（在level合并的时候会进行处理更新）

在进行读取key的时候，会先从内存查找是否有这个key，然后再到level0查找，如果还是没有就会到更高层level挨个查找，因为越高层数据越旧，没有被更新到的可能也就越大（比如一个储存在level3的key被在level2标记了删除，但是还没更新到。那么当查找这个key的时候就会优先找到在level2的删除标记（当然level3的key也会在多次合并操作之后被删除掉））

本文章配合以下资料阅读更佳：

http://blog.nosqlfan.com/html/2882.html

http://www.cnblogs.com/haippy/archive/2011/12/04/2276064.html