[非技术向]LevelDb源码阅读总结

February 17, 2017 at 1:19 pm

又是一段时间没有更新博客了。这段时间主要有两件事,一件还是在过春节假期,另一件则是在抄写(真正意义上的抄写)LevelDb。抄写的过程根据git的提交记录来看从1月14日到2月16日大约一个月的时间,按照实际的提交次数来看,大约是不到两周,每天约6个小时,抄写的是LevelDb的1.7.0版本,原版本刨去测试性的代码大约1.3万左右,最后总计抄的大约1.2万,因为按照计划昨天应该要干完这件事,今天写个总结,所以稍微有些烂尾(挖坑不填的本性暴露无疑)。整体上基本保证了可运行,昨天或多或少修了重抄过程中的的一些错误,基本的std::map型的功能可以得到保证,但是真正要拿来用是不太现实的,可能还存在很多bug,代码仅仅自己可以用了吧。本来打算在抄完之后写一点具体一点、技术性强一点的总结,最后发现,毕竟BigTable已经10多年,LevelDb也有六七年的历史了,相关的技术性文章很多,网上中文的源码解析也非常多非常全,所以最后打消了这种想法,打算写一篇对源码阅读抄写的认识、和阅读LevelDb的源码过程中的一些收获。

本文主要有以下几个小节:
1. 对LevelDb源码进行阅读的初衷
2. 源码抄写的一些感想
3. 从抄写中学到的一些东西

这里列出两篇个人觉得LevelDb源码解析的比较技术向、全面、透彻的中文文章以避免吃瓜观众不小心踩了坑不好跳出去:
malolk.com/2016/10/11/leveldb-1.19源码阅读/
www.qkldx.net/topic/64/leveldb原理探究与代码分析

对LevelDb源码进行阅读的初衷

LevelDb是由Google的两位大牛Jeffrey Dean和Sanjay Ghemawat编写的开源的持久化KV存储的库(这两位也是BigTable论文的主要作者之二),在写这篇文章时(2017-2-17)已经发布1.18版本,源码现在已经托管在github上,并遵循New BSD协议。LevelDb的最初版本就考虑可移植性,所以现在应该支持大多的主流平台,具体的我就懒得查了。LevelDb自身是以库的形式提供的,而不是一个完整的数据库产品,没有服务器端、通信协议之类的约定,仅仅是做存储,所以阅读LevelDb的源码是无法看到一个完整的数据库的全貌的;LevelDb是inpired by BigTable的,简单地可以理解为BigTable的一个开源实现,它的整体设计,包括MemTable, SSTable,都和BigTable论文中描述的基本一致;我看的是相对早期的版本1.7.0,没有和现在的版本做过完整的对比,但从部分文件的对比来看没发现有什么较大变化;LevelDb 1.7.0由C++写成,有一个简单的C接口,整体大约1.8万行的代码,除去C接口、移植性相关代码、测试相关代码后大约1.3万行,属于可以全部阅读的代码量。

之所以看LevelDb,也算是突发奇想,想到什么干什么吧。应该是很早以前就决定要看看了,毕竟代码量不多,也是大牛写的,说不定可能学到不少东西。然后前段时间在学习LSM-tree相关的知识,wiki上说LevelDb也算是某种意义上实现了LSM-tree存储引擎,所以就顺势开始看了。非要将目的罗列1,2,3的话:
1. 之前看redis陷入到它异步框架里去了,完全没看存储的部分,这次打算实打实的阅读一份KV存储的源码;
2. LSM-tree相关论文看不懂,希望可以通过实际代码加深理解
3. 好久不写代码,再不写就真的不想写要转行了

阅读LevelDb的源码,学到的东西大致总结成这3点吧:
1. 可以看到一个LSM-tree型的KV存储的实现全貌,更好地理解BigTable和LSM-tree
2. 可以学到存储相关的基础数据结构的一些(非玩具型的)实现,比如:bloom filter,skip list,LRU Cache,hash,crc32c校验,Atomic Pointer
3. 看到一份文件组织合理、注释完整、代码风格统一、规范、精致的C++软件的源码

源码抄写的一些感想

// 源码抄写是我瞎搞的,感觉不是一个适用于所有人的好方法,切记勿轻易尝试 >_<

虽然这次最终的结果是一次源码抄写作业,但是初衷却是打算重新造轮子(reinvent)的。之前在知乎上看Chaos大神讲最好的方式就是自己先想一个设计方案,然后写出代码,最后和别人的好代码比较,这样子对代码能力的提高是最有效的。这句话当然没有错,我想这也是TopCoder/CodeForces这类型的网站的出发点吧。每每看到有大神这么说时,就觉得跃跃欲试,可以实践起来确实相当的困难,我从来不是那种非要搞出方案来的那种人,一般都是设个阈值,如果到了那个点,就不想了,直接查攻略。而LevelDb对于我这种完全没有相关基础的人来说别说通关了,第一关都过不去,所以最后的结果便变成了照着攻略打了一遍,有些地方甚至还跳过了。

这里我还有个疑惑,就是这种自己想出方案和熟知别人的方案后自己实现是不是还是存在一定的区别。以后缀数组和splay tree为例,这两个数据结构对我来说都是比较深奥难懂的,所以有段时间秉着这个原则,好好学习好好练习,最终将它们化为了自己的代码,可以手写毫无压力;之后有段时间可能一直在水,再遇到时就写不出来了。我觉得是我练得太少,所以又重复了一遍这个过程,这次刷的题比之前更多一些。然而,嗯,水到现在,我又完全不会写了,不要说写,理论依据我也已经忘的差不多了。以稍简单一点的网络流为例,之前更相关博客的时候应该是可以信手拈来,现在,只能是一脸蒙蔽。这些知识学了忘,忘了学,效率非常低,一直也没找到什么好办法,可能还是需要更长期的练习吧。

不管怎么说,造轮子还是需要更深的功力吧,还是回到源码抄写上来。

和直接进行源码阅读不同的是,抄写是一个字一个字敲出来的,所以不太可能会落掉、错过一些代码中的细节;抄写的另一个好处是如果代码的模块划分的相当好,你就可以直接对当前已经抄完的模块进行编译运行,也可以进行适当的修改,来加深对当前模块的印象,本次抄写的过程中git上每次commit应该都是可以编译通过的。如果只是进行源码阅读而不运行运行,脑子里就会有种“大概是这样,但是真的是这样吗?”的一种もやもや(阿阿我觉得这个词形容这个情况实在是太贴切了,额,顺带一提,もや汉字写作「靄」)的感觉。之前在OB一开始的时候老大也说过不把程序跑起来,一切理论都不要讲。这也是有一定道理的,毕竟产品最终落实到代码,而代码最终是要能跑起来的,看到它的实际运作才是学习最有效果的方式。不过一般来讲,程序中模块的解耦工作不可能做得那么好,所以能达到部分代码运行也是比较困难的(其中也需要一些功底要补充部分空实现代码来让它跑起来,这其实和单元测试有点像),而代码一旦达到一个数量级(比如10万行),那这个工作就相当难了。所以感觉LevelDb一共一万多行的代码量,进行“源码抄写”还是可行的。总之可以做到全代码阅读的代码并不一定能全代码抄写,这里还是有个数量级上的差。
源码抄写也有很多缺陷,就像和尚念经一样,有的时候一个字一个字读过去了,却完全不知道文章写的是啥。这估计是因为将注意力分散到了这个字怎么读、怎么写,而不像一般阅读时那样,出发点就是大意。在这次抄写过程中这一现象发生了多次,还是需要避免,或许先通读再抄会更好一点吧。
另外前面已经提到了,为了让代码可以运行,抄的过程中如果遇到没遇到的类、结构,很有可能就要扎根其中,这样最终可能递归太深,直接栈溢出了。一开始我就是这么干的,毕竟反正是要敲完的,那就递归呗,总会有出口的。但这样导致越來越深,最后爬都爬不出来,一天工作结束了,还在某个坑里,最终也不知道一整天学到了啥。后面我尝试对这些用到的类、函数做空实现,真正要用时再去抄内部实现,一些类成员,用不到的时候就先不添加。这样理解上效果好了一些,不过仍有缺点,那就是同一个类、函数可能要重复写好几遍,而不是一个线性的工作,增加了抄写的时间成本。

总之对于本次抄写,算是一个不太成功的尝试吧。有直接阅读体会不到的直接运行部分代码的快感,也有直接阅读时不会踩到的各种坑,时间上也比直接阅读要多一些。

从抄写中学到的一些东西

最后,虽然本文不是技术向的文章,但还是总结一些这次抄写的一些收获吧。仅仅作为个人的总结,真正的技术细节还是参考最开头给出的链接吧。
首先是在基础数据结构方面,主要包括了:
1. Arena分配器
LevelDb对内存的管理方式感觉还是比较松散,虽然提供了Arena分配器,但是仅在比较核心的部分使用的,主要是memtable中的skiplist。其它地方使用线程不安全的引用计数进行内存管理(需要external synchronization),new和delete使用看着比较乱,可能也是因为没有其它的分配器的原因。不过对于内存管理,只要没有出现问题,那么不论哪种方式,我是觉得都ok的。Arena分配器的分配原则就是分配出去的内存不做回收,分配器自身维护这些分配出去的内存的地址,直到整个分配器析构时统一回收,调用者不需要进行内存释放。
2. skiplist
跳表是LevelDb中MemTable的主要实现形式,是一个有序映射。LSM-tree论文中对于这个驻内存结构的描述是各种平衡二叉树都ok,不过使用skiplist也是一种选择。LevelDb的跳表实现比较简单,是个中规中矩的普通跳表,没有对写入的并发进行控制,所以并发写入不是安全的,需要自己做外部同步,而且由于内部实际需求并不需要删除节点,所以并不提供删除操作,因为之前已经详细的看过了,这次直接就跳过了。如果想对跳表有更好的了解,感觉还是从Pugh的两篇论文入手,然后看LevelDb的,再看folly::ConcurrentSkipList比较好(还有Java的ConcurrentSkipListMap和cds的也可以看看)。
3. LRU Cache
好像Leetcode上有一道关于LRU缓存的题,某次N社面试也问到了,当时挂了,所以这次认真的看了一遍。底层维护了一个双向链表和hash表来管理这个LRU Cache,应该是和Java的LinkedHashMap差不多,不过Java的版本并没有看过。如果要理解LRU Cache是个很好的代码吧,以后用空(面试)的时候再捞出来看看吧。在此基础上,为了防止对单个Cache访问太过频繁导致一些并发上的性能损失,LevelDb还进行了分片操作,准备多个Cache,不同的key分到不同的Cache上。
4. hash/crc32c/random
底层的一些数据结构,这些东西现在很多程序语言都作为标准库提供了,代码里面的注释也提到,自己进行简单实现主要是为了增强可移植性。对于这些偏数学的设计我这次就直接跳过了,看不太懂额。
5. atomic pointer/mutex/condition variable
没错前一篇讲条件变量就是因为在这里遇到了。这些东西和上一点一样基本上已经成为了标准库的一部分,C++11也已经全部包含了这些东西,至于C++11会不会在一些产品中使用,超过话题,不说了。也可以稍微看一下这些东西的实现,虽然不是太过数学性的东西(其实本质还是数学),但牵扯到比较底层的东西,所以不是一目了然的,还是可以一看的。
6. bloom filter
这算是一个很经典的结构了,基本原理是知道的,不过代码中bloom filter的hash其实并没有看懂,代码中给出了论文链接,是一种使用移位来减少多个hash函数计算代价的同时保持低false positive的过程,论文没看,这个,有需要的时候再看吧,数学太难。
7. Env
还有一些包括通过Env对文件相关操作进行封装,可以看PosixEnv(继承自Env)来了解这些对应到linux系统时一些系统调用的使用,比如读、写、移动文件、目录,文件大小等
8. log
LevelDb中有两种日志,一种是BigTable中所说的commit log,就是每插入一个key,就写到日志里的提交日志,由于这个日志是顺序写入的,所以写入非常快,但是顺序是用户插入的顺序,所以读取非常慢,一般是用来在出错时进行还原用的,LevelDb专门写了log::Writer, log::Reader来对这个日志进行操作,也有专门的doc描述这个日志的格式;另一种就是纯粹的信息日志,不说了。在抄写代码的时候比较恶心的是一个叫做PrelogNumber的东西,一开始一直不明白是干什么的,后面才发现是兼容之前版本的一个无用的值。所以说再牛的人也不可能在一开始就把东西想得全面,还是会挖坑的,这个东西某种意义上破坏了代码的优雅性,也某种意义上表明了代码界就是一个前人挖坑后人填的前仆后继的过程,完美的代码只存在一个小的数据结构里,而不太可能出现在一个随时代发展的产品中。
9. iterator
LevelDb里面有很多个迭代器,这些迭代器虽然接口就是迭代器的那几个接口,不过起的是核心的功能。包括往数据库里插入数据、遍历sstable中的数据,遍历整个数据库中的数据,都要用到它们。这些迭代器底层的实现是我觉得比较难看懂的地方,有些地方需要费好一些力气,但是这些迭代器封装了复杂的底层操作,对外部调用者来说是非常友好的。迭代器就是这样,外面看着很简单的几个接口,底层一般都是非常复杂,参看SGI STL的红黑树实现...(g++ STL的大部分实现来自于此,虽然作者在代码中写到主要参考来自Introduction to Algorithms,但是实际对比一下发现要封装好接口还是有很多工作量的)。

可以独立出来的数据结构大致如上罗列。下面再稍微白话一下LevelDb的大致执行流程:
1. 提供open/put/get/delete几个接口,和std::map差不多,和map一样也提供了批量插入,插入时提供一个key和一个value。
2. 无论是查找还是插入,总是优先使用驻内存的MemTable,这个过程会比较快。如前所述,一个MemTable底层是一个skiplist。
3. 数据在插入内存之前会打commit log,以防止数据丢失。
4. 为了防止内存占用过多,MemTable达到一定大小之后就被冻结,改名为imm(immutable),此时会创建一个新的MemTable供使用。被冻结的
MemTable仍然提供查询功能。每次查询时先查MemTable,再查imm。
5. 数据最终需要被持久化到磁盘上,被冻结的imm会被CompactMemTable()函数dump到文件中,由于本身Memtable是有序的,所以dump出来的文件中的
Key也是有序的,这就是所谓的SSTable(Sorted String table)。它和commit log不同,是有序的,方便查询,但是显然不方便插入,所以SSTable也是immutable的。查询时的整个过程就是:先查MemTable,查不到查imm,再查不到查SSTable。
6. 所谓的LevelDb,就在与SSTable是使用Level进行管理的(当然skiplist也有level的概念,这可能也是原因之一),一般来说imm首先会被dump到
第0层也就是level0,由于level0的SSTable虽然自身是有序的,但是它们之间没有关联,所以一旦level0文件过多,查询就会变慢;所以这里又有一个compact的概念。沿用BigTable的说法,imm到SSTable的compact叫做minor compact,而这个叫做major compact。由于某一层级文件过多,它将这一层级的文件进行merge(由于文件自身有序,merge类似于merge sort),合成一个新的排好序的SSTable,合成好后移除上一层级中已经多余的文件。这样子一旦某个层级文件过多,就进行compact使它向下一层级移动。
7. 内部的skiplist实现并不提供真正的删除节点的功能,而是通过插入一个记号为删除的节点来表示。这些实际被删除的节点在compact的过程中也会被
移除,同时compact也移除已经被覆盖的key。
8. 每一个用户提供key/value都会被内部带上一个sequence number和type(是数据还是记号为删除),sequence number是一个递增的量,代表了
这条数据何时被插入的,越大说明越晚。LevelDb基于sequence number提供snapshot功能,这个实现感觉还是非常牛的
9. 除了snapshot以外,LevelDb对版本进行控制,这通过Version,VersionSet,VersionEdit三个类来实现。Version就是当前的版本,而
VersionEdit记录数据库发生的所有变动,每次数据操作实际上都会产生一个新的版本,VersionEdit可以作用于一个Version以得到一个新的
Version,这些Version统一在VersionSet中管理,VersionSet某种意义上就是一个Version的双向链表。
10. LevelDb还对SSTable在内存中维护了缓存,用于放置常被访问的SSTable,底层通过LRU Cache实现。

大致上就总结到这里,上述的理解可能存在不足或错误,再重述一下本文是非技术向的orz。其它没有提到的内容估计不再作补充了。就先到此吧。