levelDB

what：

　　概述：

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

　　　　有如下一些特点：

　　　　　　1、是一个持久化存储的KV系统。大部分数据存储到磁盘上；

　　　　　　2、在存储数据时，是根据记录的key值有序存储的；

　　　　　　3、支持数据快照（snapshot）功能，使得读取操作不受写操作影响。即读操作过程中始终看到一致的数据；

　　　　　　4、支持数据压缩等操作；

　　　　　　5、高性能：随机写性能达到40万条记录每秒，而随机读性能达到6万条记录每秒；总体来说，LevelDb的写操作要大大快于读操作，而顺序读写操作则大大快于随机读写操作；

　　整体架构：

　　　　leveldb某个时刻的一个快照，如下图：

 　　　　从图中的静态结构，可以看出包括六个主要部分：内存中的MemTable和Immutable MemTable；磁盘上的几种主要文件：Current文件，Manifest文件，log文件以及SSTable文件

why

　　写入速度极快的主要原因：

　　　　先往log文件里顺序写入（WAL，作用：系统崩溃恢复而不丢失数据），成功后将记录插进Memtable中。即一个记录写入，只涉及一次磁盘顺序写和一次内存写入。

how

　　leveldb中各种数据的变化：

　　　　当Memtable插入的数据占用内存到了一个界限后，LevleDb会生成新的Log文件和Memtable（记录新的数据），原先的Memtable就成为Immutable Memtable。LevelDb后台调度会将Immutable Memtable的数据导出到磁盘，形成一个新的SSTable文件。SSTable就是由内存中的数据不断导出并进行Compaction操作后形成的。

　　　　SSTable中的Key有序的。

　　　　Level 0的SSTable文件（后缀为.sst）和其它Level的文件相比有特殊性：即同level 0层级内.sst不同文件的key重叠现象（其他层不会，key全层唯一）。例如：文件A和文件B，文件A的key范围是：{bar, car}，文件B的Key范围是{blue,samecity}，那么很可能两个文件都存在key=”blood”的记录。

　　Manifest：

　　　　Manifest记载了SSTable各个文件的管理信息，比如属于哪个Level，文件名称叫啥，最小key和最大key各自是多少。下图：

 　　　　

　　Current：

　　　　记载当前的manifest文件名。

　　　　随着Compaction的进行，SSTable文件会发生变化，会有新的文件产生，老的文件被废弃。往往会新生成Manifest文件来记载这种变化，而Current则用来指出哪个Manifest文件才是我们关心的那个Manifest文件。

　　log文件：

　　　　由32K为单位的物理Block组成，每次读取的单位以一个Block作为基本读取单位。如下图：

 　　　　应用看到的是一系列的Key:Value对，而非block块。在LevelDb内部，会将一个Key:Value对看做一条记录的数据，另外在这个数据前增加一个记录头，用来记载一些管理信息，以方便内部处理，如下：

 　　　　记录头包含三个字段：ChechSum是对“类型”和“数据”字段的校验码；“记录长度”记载了数据的大小，“数据”则是上面讲的Key:Value数值对；“类型”字段则指出了每条记录的逻辑结构和log文件物理分块结构之间的关系，具体而言，主要有以下四种类型：FULL/FIRST/MIDDLE/LAST。full表示数据完整地存储在一个物理Block里；若数据被block分开，则用其他三种类型

　　SSTable：

　　　　和log文件类似，文件被划分为固定大小的物理存储块，但是两者逻辑布局大不相同。原因：Log文件中的记录是Key无序的，而.sst文件内部则是根据记录的Key由小到大排列的。

　　　　物理block结构如下：

 　　　　每个Block分为三个部分，前部分是数据存储区， 蓝色的Type区用于标识数据存储区是否采用了数据压缩算法（Snappy压缩或者无压缩两种），CRC部分则是数据校验码。

　　　　逻辑布局，如下图：

 　　　　.sst文件划分为：数据存储区和数据管理区。数据存储区存放实际的Key:Value数据；数据管理区则提供一些索引指针等管理数据，目的是：更快速便捷的查找相应的记录。

　　　　管理数据又分为四种不同类型：灰色的Meta Block，红色的MetaBlock 索引，蓝色的数据索引块以及一个文件尾部块。LevelDb 1.2版对于Meta Block尚无实际使用。下面是数据和数据索引的图：

 　　　　Data Block内的KV记录是按照Key由小到大排列的。数据索引区的每条记录是对某个Data Block建立的索引信息。每条索引信息包含三个内容：对Index i来说来说，红色部分的第一个字段记载大于等于数据块i中最大的Key值的那个Key；第二个字段指出数据块i在.sst文件中的起始位置；第三个字段指出Data Block i的大小（有时候是有数据压缩的）。

　　　　注意：索引里保存的这个Key值未必一定是某条记录的Key。

　　　　文件末尾Footer块：

　　　　　　metaindex_handle指出了metaindex block的起始位置和大小；inex_handle指出了index Block的起始地址和大小。

 　　　　

　　　　Block的数据部分内部布局：

 　　　　分为两个部分：前面是一个个KV记录，其顺序是根据Key值由小到大排列的；在Block尾部则是一些“重启点”（Restart Point）,其实是一些指针，指出Block内容中的一些记录位置。

　　　　“重启点”：在这条记录开始，不再采取只记载不同的Key部分，而是重新记录所有的Key值。Block内容里的KV记录是按照Key大小有序的，相邻的两条记录很可能Key部分存在重叠，比如key i=“the Car”，Key i+1=“the color”，那么两者存在重叠部分“the c”，为了减少Key的存储量，主要目的是：减少存储开销。

　　Memtable：

　　　　LevelDb的Memtable类只是一个接口类，真正的操作是通过背后的SkipList来做的，包括插入操作和读取操作等，所以Memtable的核心数据结构是一个SkipList。SkipList对于树的平衡的实现是基于一种随机化的算法的（即：从哪一层开始插入该结点，其后的各层都插入）。

　　写入：

　　　　插入操作插入的是Key:Value 值，而删除操作插入的是“Key:删除标记”，并不真正去删除记录，而是后台Compaction的时候才去做真正的删除操作。

　　读取：

　　　　读取过程如下图：

 　　　　如上图：读取过程，是从信息的更新时间来说，很明显Memtable存储的是最新鲜的KV对。

　　　　在level 0中找时，存在sst文件中key重叠的情况，所以需要将所有含该key的sst文件找到（manifest文件中记载了level和对应的文件及文件里key的范围信息，LevelDb在内存中保留这种映射表），之后按照文件的新鲜程度排序，新的文件排在前面，之后依次查找，读出key对应的value。其他层，就只从一个sst文件找。

　　　　levelDb一般会先在内存中的Cache中查找是否包含这个文件的缓存记录。如果包含，则从缓存中读取；如果不包含，则打开SSTable文件，同时将这个文件的索引部分加载到内存中并放入Cache中。

　　compaction：

　　　　包含其中两种，minor和major。minor Compaction，就是把memtable中的数据导出到SSTable文件中；major compaction就是合并不同层级的SSTable文件。

　　　　minor Compaction的过程如下图：

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

在minor compaction的时候并不做删除，只是将这个key作为一个记录写入文件中，至于真正的删除操作，在以后更高层级的compaction中会去做。

  　　　　major compaction：

　　　　　　level 0层的：

　　　　　　　　指定某个文件后，在本level中很可能有其他SSTable文件的key范围和这个文件有重叠。这种情况下，要找出所有有重叠的文件和level 1的文件进行合并。　

　　　　　　level n（n>0）层的major compaction：

　　　　　　　　选择其中一个文件就行（没有sst文件的key重叠情况）。

　　　　　　levelDb选择L+1层中和文件A在key range上有重叠的所有文件来和文件A进行合并。

　　　　KV记录是否抛弃的标准：

　　　　　　对于某个key来说，如果在小于L层中存在这个Key，那么这个KV在major compaction过程中可以抛掉（level越低，说明数据越新鲜）。

　　Cache：

　　　　如果在memtable和Immutable memtable没找到，那么最少需要2次磁盘读，一次读level 0的index，第二次读入这个block。

　　　　levelDb中引入了两个不同的Cache：Table Cache和Block Cache。其中Block Cache是配置可选的，即在配置文件中指定是否打开这个功能。

 　　　　上面的table cache的结构。在Cache中，key值是SSTable的文件名称，Value部分包含两部分，一个是指向磁盘打开的SSTable文件的文件指针，这是为了方便读取内容；另外一个是指向内存中这个SSTable文件对应的Table结构指针，table结构在内存中，保存了SSTable的index内容以及用来指示block cache用的cache_id ,当然除此外还有其它一些内容。

　　　　具体操作：比如在get(key)读取操作中，如果levelDb确定了key在某个level下某个文件A的key range范围内，那么需要判断是不是文件A真的包含这个KV。此时，levelDb会首先查找Table Cache，看这个文件是否在缓存里，如果找到了，那么根据index部分就可以查找是哪个block包含这个key。如果没有在缓存中找到文件，那么打开SSTable文件，将其index部分读入内存，然后插入Cache里面，去index里面定位哪个block包含这个Key 。如果确定了文件哪个block包含这个key，那么需要读入block内容，这是第二次读取。

　　　　Block Cache是为了加快上面的这个过程。

　　　　　　其中的key是文件的cache_id加上这个block在文件中的起始位置block_offset。而value则是这个Block的内容。

　　Version、VersionEdit、VersionSet：

　　　　Version 保存了当前磁盘以及内存中所有的文件信息，一般只有一个Version叫做"current" version（当前版本）。Leveldb还保存了一系列的历史版本。

　　　　当一个Iterator创建后，Iterator就引用到了current version(当前版本)，只要这个Iterator不被delete那么被Iterator引用的版本就会一直存活。

　　　　当一次Compaction结束后（会生成新的文件，合并前的文件需要删除），Leveldb会创建一个新的版本作为当前版本，原先的当前版本就会变为历史版本。

　　　　思路和双buff类似：新的请求用新的，老的没有引用了，才清理。

　　　　VersionSet 是所有Version的集合，管理着所有存活的Version。

　　　　VersionEdit 表示Version之间的变化，相当于delta 增量，表示有增加了多少文件，删除了文件。下图表示他们之间的关系。

　　　　　　Version0 +VersionEdit-->Version1

　　　　　　VersionEdit会保存到MANIFEST文件中，当做数据恢复时就会从MANIFEST文件中读出来重建数据。