levelDB学习

一直想提笔写，却看到朗格科技整理的levelDB日知录，感觉自己写的东西难出其右，又没有动力写下去了。直到过了段时间，把基本原理基本全忘了，才决定就算抄一遍也要自己整理下，落实到笔头上。
本文内容只是帮助自己温故levelDB原理，参考《日知录》基于自己的理解进行了删减，要了解详细的levelDB原理建议移步《levelDB日知录》(http://www.samecity.com/blog/Index.asp?SortID=12
或
http://www.kuqin.com/database/20121101/333161.html)。

一、概述

LevelDb是能够处理十亿级别规模Key-Value型数据持久性存储的C++程序库。

1.1 特点

• LevelDb是一个持久化存储的KV系统，和Redis这种内存型的KV系统不同，LevelDb不会像Redis一样狂吃内存，而是将大部分数据存储到磁盘上。
• LevleDb在存储数据时，是根据记录的key值有序存储的，就是说相邻的key值在存储文件中是依次顺序存储的，而应用可以自定义key大小比较函数，LevleDb会按照用户定义的比较函数依序存储这些记录。
• 像大多数KV系统一样，LevelDb的操作接口很简单，基本操作包括写记录，读记录以及删除记录。也支持针对多条操作的原子批量操作。
• LevelDb支持数据快照（snapshot）功能，使得读取操作不受写操作影响，可以在读操作过程中始终看到一致的数据。
• LevelDb还支持数据压缩等操作，这对于减小存储空间以及增快IO效率都有直接的帮助

1.2 性能

随机写：40万条记录/秒
随机读:  6万条记录/秒。
总体来说，LevelDb的写操作要大大快于读操作，而顺序读写操作则大大快于随机读写操作。

二、架构



    levelDB主要组成部分：

• Memtable及Immutable MemTable
• current文件
• Manifest文件
• log文件
• SSTable

结合一次写操作说明这些组件的功能。
当应用写入一条Key:Value记录的时候，LevelDb会先往log文件里写入，成功后将记录插进Memtable中，这样基本就算完成了写入操作，因为一次写入操作只涉及一次磁盘顺序写和一次内存写入，所以这是为何说LevelDb写入速度极快的主要原因。同时采用“先写log,再插入内存”的方式保证数据的安全。
当memtable占用内存到一个界限后，需将内存中数据dump到硬盘中。此时levelDB将memtable变为只读的immutable memtable,重新开辟一块memtable，新记录存入memtable及新日志文件。后台调度将immutable memtable中的数据导出到磁盘中，形成一个新的SSTable。SSTable就是由内存中的数据不断导出并进行Compaction操作后形成的，而且SSTable的所有文件是一种层级结构，第一层为Level 0，第二层为Level 1，依次类推，层级逐渐增高，这也是为何称之为LevelDb的原因。
每个SSTable文件属于特定level，其中存储的记录是key有序的，由Manifest文件记录每个SSTable文件中key的范围、所属level等SSTable相关管理信息。
Current文件记录当前所用manifest文件名。因为在LevleDb的运行过程中，随着Compaction的进行，SSTable文件会发生变化，会有新的文件产生，老的文件被废弃，Manifest也会跟着反映这种变化，此时往往会新生成Manifest文件来记载这种变化，而Current则用来指出哪个Manifest文件才是我们关心的那个Manifest文件。

三、组件详述

3.1 log文件

levelDB对于一个log文件会将它分割成以32K为单位的物理block,每次读取的单位以block为基本读取单位，因此从物理布局来讲，一个log文件就是由连续的32K大小Block构成的。


在应用的视野里是看不到这些Block的，应用看到的是一系列的Key:Value对，在LevelDb内部，会将一个Key:Value对看做一条记录的数据，另外在这个数据前增加一个记录头，用来记载一些管理信息，以方便内部处理，每条record的结构如下：


如果记录长度大于一个block长度，记录被分割成不同片段，以FULL/FIRST/MIDDLE/LAST标记这些片段。
记录头包含三个字段，ChechSum是对“类型”和“数据”字段的校验码，为了避免处理不完整或者是被破坏的数据，当LevelDb读取记录数据时候会对数据进行校验，如果发现和存储的CheckSum相同，说明数据完整无破坏，可以继续后续流程。“记录长度”记载了数据的大小，“数据”则是上面讲的Key:Value数值对，“类型”字段则指出了每条记录的逻辑结构和log文件物理分块结构之间的关系，具体而言，主要有以下四种类型：FULL/FIRST/MIDDLE/LAST。应用一次物理读取一个block，然后根据类型情况拼接出逻辑记录。

3.2 SSTable

SSTable也一样会将文件划分为固定大小的物理存储块，但是两者逻辑布局大不相同，根本原因是：Log文件中的记录是Key无序的，即先后记录的key大小没有明确大小关系，而.sst文件内部则是根据记录的Key由小到大排列的


上图展示了一个.sst文件的物理划分结构，每个block分为数据存储区、Type(是否采用了数据压缩算法)，CRC用于验证数据完整性


上图为.sst文件的逻辑布局。数据存储区存放实际的key:value数据，数据管理区提供一些索引指针等管理数据。两个区域都是在上述的分块基础上的，就是说文件的前面若干块实际存储KV数据，后面数据块存储管理数据。管理数据又分为四种不同类型：灰色的Meta Block，红色的MetaBlock 索引和蓝色的数据索引块以及一个文件尾部块。
数据索引块如下：


    Data Block内的KV记录是按照Key由小到大排列的，数据索引区的每条记录是对某个Data Block建立的索引信息，每条索引信息包含三个内容，以图4.3所示的数据块i的索引Index i来说：红色部分的第一个字段记载大于等于数据块i中最大的Key值的那个Key，第二个字段指出数据块i在.sst文件中的起始位置，第三个字段指出Data Block i的大小（有时候是有数据压缩的）。后面两个字段好理解，是用于定位数据块在文件中的位置的，第一个字段需要详细解释一下，在索引里保存的这个Key值未必一定是某条记录的Key,以图4.3的例子来说，假设数据块i 的最小Key=“samecity”，最大Key=“the best”;数据块i+1的最小Key=“the fox”,最大Key=“zoo”,那么对于数据块i的索引Index i来说，其第一个字段记载大于等于数据块i的最大Key(“the best”)同时要小于数据块i+1的最小Key(“the fox”)，所以例子中Index i的第一个字段是：“the c”，这个是满足要求的；而Index i+1的第一个字段则是“zoo”，即数据块i+1的最大Key。
文件末尾Footer块的内部结构见图4.4，metaindex_handle指出了metaindex block的起始位置和大小；inex_handle指出了index Block的起始地址和大小；这两个字段可以理解为索引的索引，是为了正确读出索引值而设立的，后面跟着一个填充区和魔数。


数据区的一个Block的数据部分内部布局：


从图中可以看出，其内部也分为两个部分，前面是一个个KV记录，其顺序是根据Key值由小到大排列的，在Block尾部则是一些“重启点”（Restart Point）,其实是一些指针，指出Block内容中的一些记录位置。
“重启点”是干什么的呢？我们一再强调，Block内容里的KV记录是按照Key大小有序的，这样的话，相邻的两条记录很可能Key部分存在重叠，比如key i=“the Car”，Key i+1=“the color”,那么两者存在重叠部分“the c”，为了减少Key的存储量，Key i+1可以只存储和上一条Key不同的部分“olor”，两者的共同部分从Key i中可以获得。记录的Key在Block内容部分就是这么存储的，主要目的是减少存储开销。“重启点”的意思是：在这条记录开始，不再采取只记载不同的Key部分，而是重新记录所有的Key值，假设Key i+1是一个重启点，那么Key里面会完整存储“the color”，而不是采用简略的“olor”方式。Block尾部就是指出哪些记录是这些重启点的。


在Block内容区，每个KV记录的内部结构如上图所示，每个记录包含5个字段：key共享长度，比如上面的“olor”记录， 其key和上一条记录共享的Key部分长度是“the c”的长度，即5；key非共享长度，对于“olor”来说，是4；value长度指出Key:Value中Value的长度，在后面的Value内容字段中存储实际的Value值；而key非共享内容则实际存储“olor”这个Key字符串。

3.3 MemTable

跳表组织的有序kv

四、动态操作
1. 插入
如前所述
2.删除
异步删除，添加一条记录“Key:删除标记”
3.查询
没什么好说的，就是相比写入时麻烦点，由内存到硬盘，level由低到高逐级查找
4.合并

• minor compaction

按照immutable memtable中记录由小到大遍历，并依次写入一个level 0 的新建SSTable文件中，写完后建立文件的index 数据
• major compaction

当某个level下的SSTable文件数目超过一定设置值后，levelDb会从这个level的SSTable中选择n个文件（level>0时，n=1;level=0时因key有重叠，n>=1），将其和高一层级的level+1的SSTable文件合并，这就是major compaction。
具体哪个文件与上一level合并呢？levelDB采用轮流的策略，比如这次是文件A进行compaction，那么下次就是在key range上紧挨着文件A的文件B进行compaction，这样每个文件都会有机会轮流和高层的level 文件进行合并。
如果选好了level L的文件A和level L+1层的文件进行合并，那么问题又来了，应该选择level L+1哪些文件进行合并？levelDb选择L+1层中和文件A在key range上有重叠的所有文件来和文件A进行合并。
也就是说，选定了level L的文件A,之后在level L+1中找到了所有需要合并的文件B,C,D…..等等。剩下的问题就是具体是如何进行major 合并的？就是说给定了一系列文件，每个文件内部是key有序的，如何对这些文件进行合并，使得新生成的文件仍然Key有序，同时抛掉哪些不再有价值的KV数据。


Major compaction的过程如下：对多个文件采用多路归并排序的方式，依次找出其中最小的Key记录，也就是对多个文件中的所有记录重新进行排序。之后采取一定的标准判断这个Key是否还需要保存，如果判断没有保存价值，那么直接抛掉，如果觉得还需要继续保存，那么就将其写入level L+1层中新生成的一个SSTable文件中。就这样对KV数据一一处理，形成了一系列新的L+1层数据文件，之前的L层文件和L+1层参与compaction 的文件数据此时已经没有意义了，所以全部删除。这样就完成了L层和L+1层文件记录的合并过程。

    那么在major compaction过程中，判断一个KV记录是否抛弃的标准是什么呢？其中一个标准是:对于某个key来说，如果在小于L层中存在这个Key，那么这个KV在major compaction过程中可以抛掉。因为我们前面分析过，对于层级低于L的文件中如果存在同一Key的记录，那么说明对于Key来说，有更新鲜的Value存在，那么过去的Value就等于没有意义了，所以可以删除。