关于leveldb框架的介绍,已经有无数个大佬进行过详细论述了。以下三篇博客就很不错,本文的图片也基本摘自第一篇博客:
LevelDB原理探究与代码分析
Leveldb二三事
leveldb实现原理
本文为看完以上博客后总结的一些问题,在雄神的鼎力相助下一起阅读源码找到的答案,欢迎交流指正。

一、log日志文件相关

1、Log日志文件结构?

图片5.png
图片6.png

2、如何实现的log日志顺序读写?

从文件的角度,数据库操作被顺序写入的log文件;从操作系统的角度,linux 的文件系统ext4会将文件分散在整个磁盘,在文件之间留有大量的自由空间,而不是像Windows那样将文件一个接一个的放置。当一个文件被编辑了并且变大了,一般都会有足够的自由空间来保存文件。如果碎片真的产生了,文件系统就会尝试在日常使用中将文件移动来减少碎片,所以不需要专门的碎片整理程序。同时log文件的大小是有大小限制的,最大为1M,这样就可以尽量保证一个log文件在一块连续的区间,而读写操作使用了内存映射的系统调用。

3、Down机恢复如何实现?

       每次打开一个DB的时候,首先根据当前manifest文件恢复信息到当前version(version提供对各文件的操作方法),从而获取包含down机后没有dump进disk的操作的log文件,再根据这些log文件重构memtable,并将其dump到磁盘中进行compaction操作,这时就保证了down机时丢失数据的恢复。恢复过程中新建了一个version,遍历db目录下所有文件,将文件元信息写入manifest,再将current指向manifest文件。

4、什么扩容机制?

       如果前一次映射的空间已写满,则先将文件扩展一定的长度(每次扩展的长度按64KB,128KB,...的顺序逐次翻倍,最大到1MB),然后映射到内存,对映射的内存再以32KB的Page进行切分,每次写入的日志填充到Page中,攒积一定量后Sync到磁盘上。

5、新老日志文件如何更换?

       Leveldb有自己的垃圾回收机制,当触发时会删除过期文件(包括log文件)。触发时机有三:
a、将immemtable转化为sstable后触发leveldb的垃圾回收机制。
b、后台compaction时触发垃圾回收机制。
c、open一个db,将db恢复后触发垃圾回收机制。

二、跳表相关(memtable)

1、leveldb中跳表最大几层?

12。

2、插入元素到跳表第n层的概率?

每上一层的概率为25%。

3、跳表中成员(即memtable的record)的结构?

图片7.png

4、跳表中的record和log中的content和sstable中的record有何区别?

与log中的content的结构都不同,而与sstable中的record内容顺序基本相同,这里的sequence Num实际就在sstable中record中的nonshared Key里面。

三、sstable相关

1、.sst文件结构?

图片8.png

实际上这里的Record中Key存储了Internal Key中的所有元素,通过sstable的迭代器(双重迭代器,遍历index block,然后遍历date block返回一个record)获取到的实际上是已经合并好的Key(shared + nonshared)。此外,一个sst文件内部的Index Block的结构实际与Data Block一样,只不过每个group只包含一条记录,即Data Block的最大Key与偏移。其实这里说最大Key并不是很准确,理论上,只要保存最大Key就可以实现二分查找,但是Level DB在这里做了个优化,它并没有保存最大key,而是保存一个能分隔两个Data Block的最短Key,如:假定Data Block1的最后一个Key为“abcdefg”,Data Block2的第一个Key为“abzxcv”,则index可以记录Data Block1的索引key为“abd”;

2、sstable中的每个.sst文件如何实现的存在磁盘连续空间?

sst文件是将一个个block顺序append的,从而实现磁盘顺序写,而不像其他B+树型数据库,需要将几个K/V插入到不同文件位置中去。

3、compaction操作何时触发?

(1)memtable会compact到sst中的触发条件基本可以认为是memtable大于4M(还有条件比如要求没有达到IO文件的硬上限,这类条件一般都是满足的)。
(2)对于level n(n>0)的文件来说,则超过指定字节数就进行压缩。
(3)对于level 0的文件来说,超过4(可以在config中修改该数值)个文件即进行压缩(level 0的文件之间,key可能是交叉重叠的,因此不希望level 0的文件数特别多。考虑write buffer 比较小的时候,如果使用size来限制,那么level 0的文件数可能太多,另一个方面,如果write buffer过大,使用固定大小的size 来限制level 0的话,可能算出来的level 0的文件数又太少,触发 level 0 compaction的情况发生的又太频繁。因此level 0 走了一个特殊);
(4)当某个文件查找次数过多,也会触发compaction操作。那么查找次数多少算多呢,该文件size/16k(因为查找操作需要I/O1M文件,compaction操作一般需要执行25M I/O操作,所以查找25次等于1次compaction操作,即查找一次与compaction40K文件成本相当,作者比较保守,就选择了size/16k)。

4、如何compact?

compact分为两种:
(1)memtable到sst的compact:此时首先将memtable顺序写入一个sst文件,然后挑出一个合适的level放入(不一定是level0,若level0,level1都没有与该sst重复,而level2与该sst重复了,则放入level1中)。
(2)sst之间的合并: 首先需要挑出本层要与下一层进行合并的文件,这个文件如何挑选呢?选择compact_pointer(也就是manifest文件中的Type = kCompactPointer点)之后的最近文件(若没有或compact_pointer为空,就挑第一个文件),若Level0则再挑所有与选出的文件重叠的所有文件。那么compact_pointer怎么选的呢?记录上次上一层与该层文件compaction的范围的最大key,即为compact_pointer。然后将挑选出来要compact的文件们(这个过程是动态的,可能挑选了两次才进行了compact ,也可能是level0挑出来的多个文件)逐个与下一层的文件们多路归并,最后记录到version中。至于归并的过程,实际使用的是一个复合迭代器(要合并的各文件各自有table::iterator迭代器,每次走向next时,首先将最小的那个迭代器next,然后再选出当前最小的一个为当前复合迭代器的key,实际也就是归并的方式。至于各sst文件各自的table::iterator,则是用两个Block::iter(index block和date block的)实现的,先走index block的,再根据offset走date block的。关于迭代器的内容具体可看levelDB之iterator总结),通过该复合迭代器遍历,并判断丢弃掉老数据,即完成了归并。

5、查找一对key/value时如何快速定位到相关文件,具体实现?

这是Version中的函数,Version中含有sstable的元信息,故其可以对内存中的sstable元信息(FileMetaData,记录了一个sstable的number,最小最大key)进行操作,通过二分找到相应文件,然后先在cache中查找有没有该K/V,若没有,则open之前二分找到的文件,然后二分查找index block中的key,然后通过该index block中的offset来找到record。

6、Leveldb中的bloom filter如何实现?

 首先,对于Bloom filter参数的研究有以下结论:错误率不大于є的情况下,m最好要等于n log2(1/є)才能表示任意n个元素的集合;在哈希函数的个数取到最优时,要让错误率不超过є,m至少需要取到最小值的1.44倍;k = ln2· (m/n)时取得最优的哈希函数的个数。其中m是位数,n是K/V数,k是哈希函数数。具体证明见Bloom Filter概念和原理。Leveldb中,m/n是用户的一个输入,一般取10,由上面计算可知此时错误率略小于1%。此时关于bloom filter还有一个问题,就是如何实现k个哈希函数呢?Leveldb中使用了double-hashing方法,先将key哈希成一个uint数,然后再将其加一个delta,加k次,就有k个哈希结果了,具体代码如下:

    //从这里就是bloom过滤器的实现了

    uint32_t h = BloomHash(keys[i]);//就是一个hash将字符串转换成一个unit32(这个值基本不会相同)

    const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits

    for (size_t j = 0; j < k_; j++) {

        const uint32_t bitpos = h % bits;//hash 函数   

        array[bitpos/8] |= (1 << (bitpos % 8));

        h += delta;(每次将h+delta,这样就有k个初始值了)

    }

最后的结果以filter block的形式存在sst文件中的Meta Block中。

7、Leveldb中的cache如何实现?

Leveldb中的cache基本可以说就是一个最基础的LRU算法实现,主要用到了双向链表、哈希表和LRU(least recently used)思想。LRUCache维护了一个双向循环链表lru_和一个hash表table,当要插入一个元素时,首先将其插入到链表lru的尾部,然后根据hash值将其插入到hash表中。当hash表中已存在hash值与要插入元素的hash值相同的元素时,将原有元素从链表中移除,这样就可以保证最近使用的元素在链表的最尾部,这也意味着最近最少使用的元素在链表的头部,这样即可实现LRU的思想。除了LRUCache,leveldb中还有ShardedLRUCache类(用于线程安全的cache),由于要保证线程安全,经常会出现有的线程需要等待锁而阻塞的情况,这样会导致效率降低,所以该类中包含了16个LRUCache对象,每次取出插入的LRUHandle中的hash值的高4位获取数字i,并将该LRUHandle插入第i个LRUCache中,这样就减少了线程间等待锁的开销。

四、manifest文件相关

1、manifest文件结构?

图片9.png

最前面的Type是后面字段的类型。

2、manifest文件作用?

      manifest文件是一个清单文件,记录了当前数据库的信息。SSTable中的某个文件属于特定层级,而且其存储的记录是key有序的,那么必然有文件中的最小key和最大key,这是非常重要的信息,LevelDb应该记下这些信息。Manifest就是干这个的,它记载了SSTable各个文件的管理信息,比如属于哪个Level,文件名称叫啥,最小key和最大key各自是多少。在数据库重启时,会遍历所有文件,将各文件的元信息记录在manifest文件中,然后在LevleDb的运行过程中,随着Compaction的进行,SSTable文件会发生变化,会有新的文件产生,老的文件被废弃,Manifest也会跟着反映这种变化,此时内存中往往会新生成versionEdit来记载这种变化,manifest文件也会记录这种变化(即重启数据库后,manifest文件不会再遍历文件,而只是记录之后文件的变化,如NewFile,DeleteFile)。因此,manifest文件只有在重启leveldb或用户修复leveldb的时候才会替换。

3、Manifest文件内容如何更新?

       以log的机制更新的。

4、manifest文件何时如何更换?

       manifest文件只有在重启leveldb或用户修复leveldb的时候才会替换。