leveldb实现分析

| 导语  leveldb是google开源的单机key-value存储引擎。基于Log-Structured-Merge Tree的实现。本文先介绍leveldb的总体架构，然后从各个基本操作出发，介绍leveldb的底层实现细节。

一、leveldb的特点

1.key和value可以是任意长度的字节数组 2.数据在磁盘上按key有序存储，调用者可以提供比较函数 3.提供了基本的操作：Put(key,value), Get(key), Delete(key)。支持多个基本操作组合一次批量的原子操作。 4.支持数据库的全景快照。并在此基础上做数据查询。 5.灵活iteration 支持前向遍历，后向遍历，区间范围遍历。 6.数据在磁盘自动使用Snappy压缩存储。

二、leveldb的总体架构

[ leveldb ]

1.Memtable：内存中的数据结构，主要是跳跃表（skipList）的实现。写key-value的操作的时候会把数据写到这里。

2.log文件：写操作的时候会通过顺序写的方式优先写到这个文件，然后再写入上面的memtable。避免机器宕机的时候，内存数据丢失。所以写操作，实际上是一次磁盘操作+一次内存操作。

3.Immutable Memtable：写入数据的时候，会先去检查Memtable的当前大小。当到达指定阈值的时候，会把Memtable置为Immutable Memtable。 Immutable Memtable不会允许数据写入。这时候会主动出发一次compaction，将Immutable Memtable转成level 0的sstable。

4.SSTable：磁盘的存储文件。文件分level存放。每个文件内的数据按key有序存储。level 0的文件是由内存中的Immutable Memtable做campaction导出来的。该层文件之间的key范围可能会存在重叠。其他层的sstable是由本省的文件和上一层的文件做归并排序（compaction）导出来的。文件可能在归并后被删除。除了level0，其他层level内不同文件之间key的范围不会存在重叠。

5.manifest文件：磁盘上的文件。记录sstable在各个level的分布，以及每个sstable最大key和最小key。

6.current文件：磁盘上的文件。记录当前的manifest文件。

三、leveldb的写操作

1、 预备知识

1.slice  slice是leveldb自定义的结构体，对string的封装。能够很方便地跟string进行转化。底层很多操作都是以slice为对象。

2.varint编码  varint是一种紧凑表示数字的方式。对于一个int32类型的数字，最少用一个字节表示数字，最多用5个字节表示数字。

[ varint编码 ] 具体编码方式： （1）原始整数二进制从最低位的bit开始每7个bit进行分组。 （2）每个分组的前面添加一个bit。除了最高位的那个分组添加0，其他的添加1。 （3）从最低位的分组到最高位的分组依次写入字符数组。 leveldb底层对一些key的大小使用了varint的编码方式。

2、实际写操作

（1）写入的key，和value按如下进行编码写入到string：

[ 写入key格式 ]

• sequence是每次写入分配的全局递增序列号。如果这次写入的是count个key-value，则下次sequence要增加count然后再分配出去。
• type是固定一个字节的枚举值。只有kTypeValue和kTypeDeletion，用于标识这是一个写入还是删除。可见删除，并不是真正的删掉key而是把key打个标记。后续的compaction会真正删掉key。
• 前面提到过的leveldb支持批量写入。一次批量写入多少个key-valuve，就有对于的count。以及组织成上图的string。

（2）writebatch入队

[ 任务队列 ]

• writer结构体除了包含WriterBatch指针外，还包含了sync（同步写盘），done（是否以及完成写入操作的标志）
• 之后去每次通过条件变量等待被唤醒，然后去检查是否队首的元素是之前自己push进去的元素。

（3）检查memtable是否由可用空间写入

• 如果level0的个数达到一定阈值，则sleep1000微妙，只发生一次
• 否则查看memtable当前大小是否小于指定阈值，如果小于，说明有空空间可以写入。
• 第二步检查发现memtable没有空间的话，就去检查level0文件个数。小于一定阈值，进行等待memtable compaction完成。
• 到了这里，说明level0是可以增加文件的。就把memtable置为Immutable memtable，然后出发memtable compaction。之后新建memtable和对应的log文件。

（4）队列取任务。

• 去第一个writer的时候，同时遍历后面的writer，然后合并到（1）的的格式。
• 去后面writer合并的时候会检查所有字节数的上限，同时如果当前writer的sync标志是true，但是第一个writer是false的时候，不会再继续合并后面的writer。

（5）写入log文件

[ log格式 ]

• 上面组装出来的slice，会以block（32KB）的大小进行切割，每次切割完得到一个type，用以标识这部分在原来slice的位置。
• type是个枚举值：kFullType，kFirstType，kLastType，kMiddleType。
• 切割完组织成一个record，然后再进行刷盘
• recode的格式是：4字节的crc校验码 | 2字节的长度 | 1字节的type | 被分割的数据

（6）插入memtable

• 插入memtable的格式：

[ key格式 ]

• 插入的过程是用internal key做比较，默认按user key升序，相同user key下按sequcence降序，找到插入的位置
• memtable的底层实现是skiplist：

[ skiplist ]

• 跳跃表是在链表基础上扩展的数据结构。每个node节点，除了存key以外，还会存一个指针数组。数组的大小是这个节点的高度，数组的值指向下一个node节点。随机生成一个小于最大值的数作为当前要插入节点的高度。
• 每次插入从最高层去比较找到要插入点的前驱node指针。

四、leveldb的版本管理

[ 版本管理 ]

1. leveldb版本管理的数据结构是由一个循环的双向链表组成。每个元素是一个version。
2. version具体指什么？

• 之前提到的memtable是在内存里面的，之后会经过compaction落到磁盘文件，直接到level0的sst文件。level0的文件里面的key-value做归并排序得到后面level的文件。
• 每个level里面的每个文件存储按key有序排列。
• 所谓verison，就是这些所有level的sst文件组成的集合。

3.每次做完compaction后，就是去组成新的version数据结构，然后插到head元素的后面。

[ version ]

1.version是一堆sst的集合，每个sst在version里面如何表示？

• 上述的数据结构用来描述一个sst文件，由于key-value在文件内有序，所以只需记录最大key和最小key。
• number是文件的编号，全局递增，通过number就可以找到一个sst文件（dbname/[0-9]+.(sst|ldb)）
• refs是这个结果体的引用技术，为0是这个结构体变量会被delete掉。

[ 生成新的version ]

1.version是如何生成的？

• 每次做完compaction生成新的文件，会生成一个versionEdit的数据结构，
• 这个数据结构，描述本次compaction做完后要新增的FileMetaData，以及要被删掉的文件编号。
• 通过这个builder的类，可以实现Version1+VersionEdit=Version2。由此来产生新的version。

2.有了version就可以来确定一个快照来。

• 快照的核心点，是确定一个sequence，同时对当前version的引用计数+1，防止这个version被删掉。
• 有了这个sequence，比如同一个key由多个版本，大于这个sequence的用户看不到，小于sequence的，取最大的，作为用户查询结果。

3.目前我们对leveldb的版本管理做了一个大概的描述，为后续的compaction做铺垫。

五、leveldb的compaction

leveldb 中的compaction分两种：内存中的memtable数据compact到sst文件以及磁盘中的sst文件做归并排序整到到下一层的sst文件。

1、内存到磁盘的compaction

[ sst文件的物理格式 ]

（1）sst的布局如图

• DataBlock: 主要用来存放key和value
• MetaBlcok: 存放关于key-value的元信息，leveldb里面主要用来构建bloom filter，可以挡住一部分无效查询。

[filter 0] [filter 1] [filter 2] … [filter N-1] [offset of filter 0] : 4 bytes [offset of filter 1] : 4 bytes [offset of filter 2] : 4 bytes … [offset of filter N-1] : 4 bytes [offset of beginning of offset array] : 4 bytes lg(base) : 1 byte

bloom filter的原理是对集合里面的每个元素，用k个哈希函数，算出k个位置，然后组成一个字节数组。

leveldb中每对20k的数据进行一次bloom filter的计算，[filter i]对应算出来的结果，[offset of filter 0] 是对应filter的偏移量。

• MetaIndex Block：key是filter的名称，主要用来存放meta block的索引，这个索引是由block的偏移量和大小组成。
• Index Block：key是对应块的最大key，value用来存放data block的索引，这个索引是由block的偏移量和大小组成。
• footer：主要存放上面两个block的索引。

[ 每个block格式 ]

（2）每个block的逻辑分布一样：

• 每个entry对应到key，value。key采用压缩编码的方式： 跟上一个key的共享部分大小+非共享部分大小+value大小+key的差异部分+value的值。
• 第一个entry保存的是全量的key，这个叫重启点
• 放在restart数组里面，后面的key没个一定数量建立一个重启点，放到restart数组里面。
• 最后的num是restart的个数。
• 组成上面的bock内容后，会对内容做snap压缩，对metablock的内容不做压缩。最后的type表明压缩方式。
• 需要注意的是，生成sst文件后，leveldb会把该文件里面的index信息放在缓存中。主要包含indexblock以及meta block的内容。

（3）怎样为从memtable生成的sst文件选择level

• 如果跟level0的文件有key范围重叠的直接选择level0，
• 如果没有，则循环去找出level+1跟新生成的文件有key范围重叠，或是level+2的重叠文件总大小大雨一定值的level

2、ss文件直接的compacion

这里指的是当前version 几个sstable之间做归并排序，生成新的sstable，并建立新version的过程。

（1）触发时机：满足一下任意一个条件

• level0的文件个数太多，超过指定值。（level0 的sst文件是由memmtable做compaction生成的，文件之间的key范围有可能重叠。）
• 其他level，有一个level总文件的大小超过指定值。（默认level1上限10M，后面每一层是前一层的10倍）
• 某个文件被查找太多次数，但又没命中。leveldb中每个filemeta中维护一个allowed_seeks。

（2）如何选择做compaction的文件

• 先找到开始的文件： 1.优先考虑文件个数太多，或是超过指定上限大小的情况。选择该level的第一个lagestkey>compact_pointer（这个是保存上次做compaction所有文件的最大key）的文件。如果没有，直接选择该level的第一个文件。 2.上述1不满足的时候，直接选择allowed_seedk被减到0 的文件，作为开始的文件。
• 当找到开始文件的时候，要判断一次当前是不是level0。level0比较特殊，文件之间可能会有key范围重叠。所有这时候会把level0中，跟选中文件key范围重叠的文件也加进来。
• 最终做归并排序的文件要放到下面数据结构的inputs数组里面：

1. inputs[0] 就是前面找的文件集合。 inputs[1]选取算法：当前level被选中文件的smallkey，lagest_key拿到level+1查找有跟这个范围重叠的文件。
2. 上述一轮过后，会做一次调整： 重新算出 inputs[0]， inputs[1]合一起所有文件的small_key，lagest_key。到level中选出跟这个key范围重叠的文件集合expanded0。 算出expanded0的small_key，lagest_key，并拿到level+1算出新的key重叠文件集合expanded1。 如果expanded1的文件个数跟inputs[1]一样，则用expanded0代替inputs[0]，expanded1代替inputs[1]
3. 上述都做完后算出level+2中，跟上面算出key范围重叠的文件集合放到grandparents_中。

（3）构建迭代器 （4）循环每个key，对于要保留的key，生成sst文件 什么样的key需要做保留？

• 做compaction之前会取当前最老snapshot的sequence。
• 遍历key的时候，相同key是按sequence递减的。所以最要保留相同key的seq大于等于snapshotsequence的部分即可。
• 对于被打了删除标志的key，必须满足key的seq小于snapshot_sequence且后面的level范围包含这个key，才能被保留。
• 循环期间会有一个判断，如果当前所有遍历过的key在grandparents中重叠范围大于指定的值后，会提前停止compaction。

（5）删除之前做compaction的文件集合，把新的文件集合应用于当前的version（放到level+1），生成新的version。

六、读流程

一个key的读流程：memtable->Immutable Memtable->level0->level1…

• 到level0这里的时候，会判断包含这个key范围的所有文件。在所有文件内查找。
• sst table中的查找，会先从缓存中拿出indexhandle 二分查找出所在的block，然后在block里面二分查找restart，最后再找到对应的key
• bloom filter 会过滤一些无效的key查询

七、恢复流程

每次重启leveldb的时候，会做一次recover

• 从current文件找到当前的manifest
• 从manifest读出记录恢复到当前version
• 找到最小min_log（小于这个num的log都已经明确把memtable导出为sst文件）
• 大于这个min_log的log文件，读出记录生成memtable。

八、LRUCache设计

[ LRUCache ]

leveldb 把一些数据的索引放到了缓存中。缓存的设计是个多路的lru cache。每个lru cace由HashTable+双向链表来实现。

• 每个具体的元素由下面的数据结构来描述：

• 每个LRUCache维护两个双向循环链表：inuse，lru。
• 每个元素维护一个引用计数，刚开始插入的时候为2，放到in_use。
• 每次被擦除时候，引用计数减一，当减到为1的时候放到lru_。

九、内存分配器Arena

leveldb实现一个简单的内存分配器，用于memtable生成一个新节点的时候分配内存。

• 核心数据结构是std::vector blocks;每个指向1KB数据大小的内存块。
• 如果要的数据大小大于1KB，则直接分配。如果小于等于1KB，则分出一个1KB大小的内存块放入blocks，然后再在里面分配出去。

参考链接： https://github.com/google/leveldb/blob/master/doc/index.md http://bean-li.github.io/leveldb-sstable/ https://segmentfault.com/a/1190000009707717 http://www.cnblogs.com/haippy/archive/2011/12/04/2276064.html https://yq.aliyun.com/articles/64357?spm=5176.10695662.1996646101.searchclickresult.78696fe4uMnDpN

如果您觉得我们的内容还不错，就请转发到朋友圈，和小伙伴一起分享吧~