LevelDB原理分析

在网上看了很久的LevelDB相关文章,大多都写的不错,但是每一篇侧重点都不同,偶然发现了一片原理和实现都写的不错的,好文章不应该被埋没,个人感觉想要初步了解LevelDB的话,这篇文章就够了。

 注:我对文章进行了少许修改,主要包括原文的错别字、关键字重点加粗、引入其他解释下图片。

概述

Level DB(http://code.google.com/p/leveldb/)是google开源的Key/Value存储系统,它的committer阵容相当强大,基本上是bigtable的原班人马,包括像jeff dean这样的大牛,它的代码合设计非常具有借鉴意义,是一种典型的LSM Tree的KV引擎的实现,从它的数据结构来看,基本就是sstable的开源实现,而且针对各种平台作了port,目前被用在chrome等项目中。

LSM Tree

Level DB是典型的Log-Structured-Merge Tree的实现,它通过延迟写入以及Write Log Ahead技术来加速数据的写入并保障数据的安全。LevelDB的每个数据文件(sstable)中的记录都是按照Key的顺序进行排序的,但是随机写入时,key的到来是无序的,因此很难将一条记录插入到其排序位置。于是需要它采取一种延迟写入的方式,批量攒集一定量的数据,将它们在内存中排好序,一次性写入到磁盘中。但是这期间一旦系统断电或其他异常,则可能导致数据丢失,因此需要将数据先写入到log的文件中,这样便将随机写转化为追加写入,对于磁盘性能会有很大提升,如果进程发生中断,重启后可以根据log恢复之前写入的数据

Write Batch

Level DB只支持两种更新操作:

1. 插入一条记录 

2. 删除一条记录

代码如下:

同时还支持以一种批量的方式写入数据:

其实,在Level DB内部,单独更新与批量更新的调用的接口是相同的,单独更新也会被组织成为包含一条记录的Batch,然后写入数据库中。Write Batch的组织形式如下:

              

Log Format

每次更新操作都被组织成上图所示的数据包,并作为一条日志写入到log文件中,同时也会被解析为一条条内存记录,按照key排序后插入到内存表中的相应位置。LevelDB使用Memory Mapping的方式对log数据进行访问:如果前一次映射的空间已写满,则先将文件扩展一定的长度(每次扩展的长度按64KB,128KB,…的顺序逐次翻倍,最大到1MB),然后映射到内存,对映射的内存再以32KB的Page进行切分,每次写入的日志填充到Page中,攒积一定量后Sync到磁盘上(也可以设置WriteOptions,每写一条日志就Sync一次,但是这样效率很低),内存映射文件的代码如下:

但是,一个Batch的数据按上面的方式组织后,如果作为一条日志写入Log,则很可能需要跨两个或更多个Page;为了更好地管理日志以及保障数据安全,LevelDB对日志记录进行了更细的切分,如果一个Batch对应的数据需要跨页,则会将其切分为多条Entry,然后写入到不同Page中,Entry不会跨越Page,我们通过对多个Entry进行解包,可以还原出Batch数据。最终,LevelDB的log文件被组织为下面的形式:

            

这里,我们可以看一下log_writer的代码:

Write Log Ahead

Level DB在更新时,先写log,然后更新memtable,每个memtable会设置一个最大容量,如果超过阈值,则采用双buffer机制,关闭当前log文件并将当前memtable切换为slave memtable,然后新建一个log文件以及memtable,将数据写进新的log文件与memtable,并通知后台线程对从memtable进行处理,及时将其dump到磁盘上,或者启动compaction流程。Write的代码分析如下:

Skip List

Level DB内部采用跳表结构来组织Memtable,每插入一条记录,先根据跳表通过多次key的比较,定位到记录应该插入的位置,然后按照一定的概率确定该节点需要建立多少级的索引,跳表结构如下:

            

Level DB的SkipList最高12层,最下面一层(level0)的链是全链,即每条记录必须在此链中插入相应的索引节点;从level1到level11则是按概率决定是否需要建索引,概率按照1/4的因子等比递减。下面举个例子,说明一下这个流程:
1. 看上图,假定我们链不存在record3,level0中,record2的下一条记录是record4,level1中,record2的下一条记录是record5。
2. 现在,我们插入一条记录record3,通过key的比较,我们定位到它应该在record2与record4之间。
3. 然后,我们按照下面的代码确定一条记录需要在跳表中建立几重索引:

按照上面的代码,我们可以得出,建立x级索引的概率是0.25 ^(x – 1) * 0.75,所以,建立1级索引的概率为75%,建立2级索引的概率为25%*75%=18.75%,…(个人感觉,google把分支因子定为4有点高了,这样在绝大多数情况下,跳表的高度都不大于3)。

4.  在level0 ~ level (x-1)中链表的合适位置插入record3,假定根据上面的公式,我们得到需要为record3建立2级索引,即x=2,因此需要在level0与level1中的链中插入record3:在level 0的链中,record3插在record2与record4之间,在level 1的链中,record3插入在record2与record5之间,形成了现在的索引结构,在查询一个记录时,可以从最高一级索引向下查找,节约比较次数

Record Format

Level DB将用户的每个更新或删除操作组合成一个Record(记录),其格式如下:

            

从图中可以看出,每个Record会在原用key的基础上添加版本号以及key的类型(更新 or 删除),组成internal key。插入跳表时,是按照internal key进行排序而非用户key。这样,我们只可能向跳表中添加节点,而不可能删除和替换节点。

Internal Key在比较时,按照下面的算法

根据上面的算法,我们可以得知Internal Key的比较顺序:

1. 如果User Key不相等,则User Key比较小的记录的Internal Key也比较小,User Key默认采用字典序(lexicographic)进行比较,可以在建表参数中自定义comparator。
2. 如果type也相同,则比较Sequence Num,Sequence Num大的Internal Key比较小。
3. 如果Sequence Num相等,则比较Type,type为更新(Key Type=1)的记录比的type为删除(Key Type=0)的记录的Internal Key小。

在插入到跳表时,一般不会出现Internal Key相等的情况(除非在一个Batch中操作了同一条记录两次,这里会出现一种bug:在一个Write Batch中,先插入一条记录,然后删除这条记录,最后把这个Batch写入DB,会发现DB中这条记录存在。因此,不推荐在Batch中多次操作相同key的记录),User Key相同的记录插入跳表时,Sequence Num大的记录会排在前面。
设计Internal Key有个以下一些作用:
1. Level DB支持快照查询,即查询时指定快照的版本号,查询出创建快照时某个User Key对应的Value,那么可以组成这样一个Internal Key:Sequence=快照版本号,Type=1,User Key为用户指定Key,然后查询数据文件与内存,找到大于等于此Internal Key且User Key匹配的第一条记录即可(即Sequence Num小于等于快照版本号的第一条记录)。
2.如果查询最新的记录时,将Sequence Num设置为0xFFFFFFFFFFFFFF即可。因为我们更多的是查询最新记录,所以让Sequence Num大的记录排前面,可以在遍历时遇见第一条匹配的记录立即返回,减少往后遍历的次数。

文件结构

文件组成

Level DB包含一下几种文件:

文件类型 说明
dbname/MANIFEST-[0-9]   清单文件            
dbname/[0-9] .log db日志文件
dbname/[0-9] .sst dbtable文件
dbname/[0-9] .dbtmp db临时文件
dbname/CURRENT  记录当前使用的清单文件名
dbname/LOCK   DB锁文件
dbname/LOG info log日志文件
dbname/LOG.old 旧的info log日志文件

以各种文件在计算机中的分布位置来看,如下图所示:

               

上面的log文件,sst文件,临时文件,清单文件末尾都带着序列号,序号是单调递增的(随着next_file_number从1开始递增),以保证不会和之前的文件名重复。另外,注意区分db log与info log:前者是为了防止保障数据安全而实现的二进制Log,后者是打印引擎中间运行状态及警告等信息的文本log。

随着更新与Compaction的进行,Level DB会不断生成新文件,有时还会删除老文件,所以需要一个文件来记录文件列表,这个列表就是清单文件的作用,清单会不断变化,DB需要知道最新的清单文件,必须将清单准备好后原子切换,这就是CURRENT文件的作用,Level DB的清单过程更新如下:

1. 递增清单序号,生成一个新的清单文件。

2. 将此清单文件的名称写入到一个临时文件中。
3. 将临时文件rename为CURRENT。

代码如下:

Manifest

在介绍其他文件格式前,先了解清单文件,MANIFEST文件是Level DB的元信息文件,它主要包括下面一些信息:
1. Comparator的名称

2. 

其格式如下:

                

我们可以看看其序列化的代码:

Sortedtable

Level DB间歇性地将内存中的SkipList对应的数据集合Dump到磁盘上,生成一个sst的文件,这个文件的格式如下:

                

按照SSTable的结构,可以正向遍历,也可以逆向遍历,但是逆向遍历的代价要远远高于正向遍历的代价,因为每条record都是变长的,且其没有记录前一条记录的偏移,因此逆向Group遍历时,只能先回到group(代码中称为一个restart,为了便于理解,下面都称为group)开头(一个Data Block的group一般为16条记录,每个Data Block的尾部有group起始位置偏移索引),然后从头开始正向遍历,直至找到其前一条记录,如果当前位置为group的第一条记录,则需要回到上一个group的开头,遍历到其最后一条记录。另外,内存中跳表反向的遍历效率也远远不如正向遍历

Sparse Index

一个sst文件内部除了Data Block,还有Index Block,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”;这样的分割串可以有很多,只要保证Data Block1中的所有Key都小于等于此索引,Data Block2中的所有Key都大于此索引即可。这种优化缩减了索引长度,查询时可以有效减小比较次数。我们可以看看默认comparator如何实现这种分割的:

从上面可以看出,FindShortestSeparator方法并不严格,有些时候没有找出最短分割的key(比如第一个不等的字符已经为0xFF时),它只是一种优化,我们自定义Comparator时,既可以实现,也可以不实现,如果不实现,将始终使用Data Block的最大Key作为索引,并不影响功能正确性。

Operations

在介绍了数据结构后,我们看看Level DB一些基本操作的实现:

创建一个新表

创建一个新的表大概分为几步,包括建立各类文件以及内存中的数据结构,线程同步对象等,关键代码如下:

打开一个已存在的表

上面的步骤中,其实还遗漏了一个的重要流程,那就是DB的Open方法。Level DB无论是创建表,还是打开现有的表,都是使用Open方法。代码如下:

 

从上面可以看出,其实到底是新建表还是打开表都是取决与DBImpl::Recover()这个方法的行为,它的流程如下:

关闭一个已打开的表

Level DB设计成只要删除DB对象就可以关闭表,其关键流程如下:

由上可见,delete一个db对象可能会阻塞调用线程一段时间,必须让其完成一些必须完成的工作,才能进一步保障数据的安全。

随机查询

Level DB可能dump多个sst文件,这些文件的key范围可能重叠。按照Level DB的设计,其会将sst分为7个等级,可以视为代龄,其中,只有Level 0中的sst可能存在key的区间重叠的情况,而level1 – level6中,同一level中的sst可以保证不重叠,但不同level之间的sst依然可能key重叠。因此,如果查询一个key,其最多可能在6 n个sst中同时存在,n为level0中sst的个数;同时,由于这些文件的生成有先后关系,查询时还需要注意顺序,Get一个key的流程如下:

                

 

 

参考链接:

https://my.oschina.net/fileoptions/blog/903206

 

 

 

 

 

 

Leave a Reply

Your email address will not be published.