# LevelDB简单介绍
------
LevelDB是Google开源的持久化KV单机数据库，具有很高的随机写，顺序读/写性能，但是随机读的性能很一般，也就是说，LevelDB很适合应用在查询较少，而写很多的场景。LevelDB应用了`LSM (Log Structured Merge)` 策略，`lsm_tree`对索引变更进行延迟及批量处理，并通过一种类似于归并排序的方式高效地将更新迁移到磁盘，降低索引插入开销，关于LSM，本文在后面也会简单提及。
根据Leveldb官方网站的描述，LevelDB的特点和限制如下：
特点：
1、key和value都是任意长度的字节数组；
2、entry（即一条K-V记录）默认是按照key的字典顺序存储的，当然开发者也可以重载这个排序函数；
3、提供的基本操作接口：Put()、Delete()、Get()、Batch()；
4、支持批量操作以原子操作进行；
5、可以创建数据全景的snapshot(快照)，并允许在快照中查找数据；
6、可以通过前向（或后向）迭代器遍历数据（迭代器会隐含的创建一个snapshot）；
7、自动使用Snappy压缩数据；
8、可移植性；
限制：
1、非关系型数据模型（NoSQL），不支持sql语句，也不支持索引；
2、一次只允许一个进程访问一个特定的数据库；
3、没有内置的C/S架构，但开发者可以使用LevelDB库自己封装一个server；
下面展示了一个db文件夹下的文件内容
1. .log
2. CURRENT
3. LOCK
4. LOG
5. MAINFEST
这几个文件是leveldb在磁盘上的最主要的表现形式，还有一些比较重要的文件`.sst文件`没有展示出（这是因为当前db没有数据写入，或是数据量太小还在LOG文件中）
leveldb在内存中还存在两种数据存储形式`MemTable`和`Immutable MemTable`,以上的文件和数据结构组成了leveldb基本存储框架
下图是LevelDB运行一段时间后的存储模型快照：
下面我将一一讲解这些文件的作用
###**MAINFEST文件**
SSTable中的某个文件属于特定层级，而且其存储的记录是key有序的，那么必然有文件中的最小key和最大key，这是非常重要的信息，Manifest 就记载了SSTable各个文件的管理信息，比如属于哪个Level，文件名称叫啥，最小key和最大key各自是多少。下图是Manifest所存储内容的示意：
###**CURRENT文件**
随之SSTable的不断合并，新文件不断产生，老文件合并后被丢弃Manifest也会跟着反映这种变化，此时往往会新生成Manifest文件来记载这种变化，而Current则用来指出哪个Manifest文件才是我们关心的那个Manifest文件。
.log文件和SSTable文件以及MemTable都是K-V（[]byte-[]byte）形式存储的。
###**LOCK文件**
LOCK文件主要是用于获取文件锁，或者给文件上锁用。（在fabric中peer节点就是以互斥锁的形式打开文件，使得外部打开文件只能以read-only+不获取文件锁的形式去做）
###**sst文件**
sst文件并不是分散在leveldb中存储，而是以层级结构存储的，每个level存在许多sst文件，每个sst文件大小上限为2MB,而一个sst文件又是由若干个block组成，每个block的大小为4K，这些block是读写的最小单元。SST文件的最后一个block是一个index，指向每个datablock的起始位置，以及每个block第一个entry的key值（block内的key有序存储）
由log直接读取的entry会写到Level 0的SST中（最多4个文件）；
当Level 0的4个文件都存储满了，会选择其中一个文件Compact到Level 1的SST中
注意：
>* Level 0的SSTable文件和其它Level的文件相比有特殊性：这个层级内的.sst文件，两个文件可能存在key重叠，比如有两个level 0的sst文件，文件A和文件B，文件A的key范围是：{bar, car}，文件B的Key范围是{blue,samecity}，那么很可能两个文件都存在key=”blood”的记录。对于其它Level的SSTable文件来说，则不会出现同一层级内.sst文件的key重叠现象，就是说LevelL中任意两个.sst文件，那么可以保证它们的key值是不会重叠的。
Log：最大4MB (可配置), 会写入Level 0；
Level 0：最多4个SST文件,；
Level 1：总大小不超过10MB；
Level 2：总大小不超过100MB；
Level 3+：总大小不超过上一个Level ×10的大小。
比如：0 ↠ 4 SST, 1 ↠ 10M, 2 ↠ 100M, 3 ↠ 1G, 4 ↠ 10G, 5 ↠ 100G, 6 ↠ 1T, 7 ↠ 10T
在读操作中，要查找一条entry，先查找log，如果没有找到，然后在Level 0中查找，如果还是没有找到，再依次往更底层的Level顺序查找；如果查找了一条不存在的entry，则要遍历一遍所有的Level才能返回"Not Found"的结果。
在写操作中，新数据总是先插入开头的几个Level中，开头的这几个Level存储量也比较小，因此，对某条entry的修改或删除操作带来的性能影响就比较可控。
可见，SST采取分层结构是为了最大限度减小插入新entry时的开销
##**写操作**
1、顺序写入磁盘log文件；
2、由log文件写入内存memtable（采用skiplist结构实现）；
3、写入磁盘SST文件(sorted string table files)，这步是数据归档的过程（永久化存储）；
注意：
>* log文件的作用是是用于系统崩溃恢复而不丢失数据，假如没有Log文件，因为写入的记录刚开始是保存在内存中的，此时如果系统崩溃，内存中的数据还没有来得及Dump到磁盘，所以会丢失数据；
>* 在写memtable时，如果其达到checkpoint（满员）的话，会将其改成immutable memtable（只读），然后等待dump到磁盘SST文件中，此时也会生成新的memtable供写入新数据；
>* memtable和sst文件中的key都是有序的，log文件的key是无序的；
>* LevelDB删除操作也是插入，只是标记Key为删除状态，真正的删除要到Compaction的时候才去做真正的操作；
>* LevelDB没有更新接口，如果需要更新某个Key的值，只需要插入一条新纪录即可；或者先删除旧记录，再插入也可以；
##**读操作**
1、在内存中依次查找memtable、immutable memtable；
2、如果配置了cache，查找cache；
3、根据mainfest索引文件，在磁盘中查找SST文件；
举个例子：我们先往levelDb里面插入一条数据 {key="www.samecity.com" value="我们"}，过了几天，samecity网站改名为：69同城，此时我们插入数据{key="www.samecity.com"value="69同城"}，同样的key,不同的value；逻辑上理解好像levelDb中只有一个存储记录，即第二个记录，但是在levelDb中很可能存在两条记录，即上面的两个记录都在levelDb中存储了，此时如果用户查询 key="www.samecity.com"，我们当然希望找到最新的更新记录，也就是第二个记录返回，因此，查找的顺序应该依照数据更新的新鲜度来，对于SSTable文件来说，如果同时在level L和Level L+1找到同一个key，level L的信息一定比level L+1的要新。
##**Compaction操作**
对于LevelDb来说，写入记录操作很简单，删除记录仅仅写入一个删除标记就算完事，但是读取记录比较复杂，需要在内存以及各个层级文件中依照新鲜程度依次查找，代价很高。为了加快读取速度，levelDb采取了compaction的方式来对已有的记录进行整理压缩，通过这种方式，来删除掉一些不再有效的KV数据，减小数据规模，减少文件数量等。
LevelDb的compaction机制和过程与Bigtable所讲述的是基本一致的，Bigtable(Google设计的分布式数据存储系统)中讲到三种类型的compaction: minor ，major和full()：
>* minor Compaction，就是把memtable中的数据导出到SSTable文件中；
>* major compaction就是合并不同层级的SSTable文件；
>* full compaction就是将所有SSTable进行合并；
LevelDb包含其中两种，minor和major。
Minor compaction 的目的是当内存中的memtable大小到了一定值时，将内容保存到磁盘文件中，如下图：
immutable memtable其实是一个SkipList，其中的记录是根据key有序排列的，遍历key并依次写入一个level 0 的新建SSTable文件中，写完后建立文件的index数据，这样就完成了一次minor compaction。从图中也可以看出，对于被删除的记录，在minor compaction 过程中并不真正删除这个记录，原因也很简单，这里只知道要删掉key记录，但是这个KV数据在哪里？那需要复杂的查找，所以在minor compaction的时候并不做删除，只是将这个key作为一个记录写入文件中，至于真正的删除操作，在以后更高层级的compaction中会去做。
当某个level下的SSTable文件数目超过一定设置值后，levelDb会从这个level的SSTable中选择一个文件（level>0），将其和高一层级的level+1的SSTable文件合并，这就是major compaction。
### LSM Tree（Log-Structured Merge Tree）
存储引擎和B树存储引擎一样，同样支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。当然凡事有利有弊，LSM树和B+树相比，LSM树牺牲了部分读性能，用来大幅提高写性能。
LSM树的设计思想非常朴素：将对数据的修改增量保持在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘，不过读取的时候稍微麻烦，需要合并磁盘中历史数据和内存中最近修改操作，所以写入性能大大提升，读取时可能需要先看是否命中内存，否则需要访问较多的磁盘文件。
LSM树原理把一棵大树拆分成N棵小树，它首先写入内存中，随着小树越来越大，内存中的小树会flush到磁盘中，磁盘中的树定期可以做merge操作，合并成一棵大树，以优化读性能。
LSM Tree，对于最简单的二层LSMTree而言，内存中的数据和磁盘中的数据merge操作如下：
