LevelDB 的原理

LevelDB是Google传奇工程师Jeff Dean和Sanjay Ghemawat开源的KV存储引擎。国内各大互联网公司都有基于leveldb 开发的缓存系统，我们今天就简单介绍下这个存储引擎为什么会受大家青睐，

原理：LevelDB的数据是存储在磁盘上的，采用LSM-Tree的结构实现。LSM-Tree将磁盘的随机写转化为顺序写，从而大大提高了写速度。

为了做到这一点LSM-Tree的思路是将索引树结构拆成一大一小两颗树，较小的一个常驻内存，较大的一个持久化到磁盘，他们共同维护一个有序的key空间。写入操作会首先操作内存中的树，随着内存中树的不断变大，会触发与磁盘中树的归并操作，而归并操作本身仅有顺序写。随着数据的不断写入，磁盘中的树会不断膨胀，为了避免每次参与归并操作的数据量过大，以及优化读操作的考虑，LevelDB将磁盘中的数据又拆分成多层，每一层的数据达到一定容量后会触发向下一层的归并操作，每一层的数据量比其上一层成倍增长。这也就是LevelDB的名称来源

---------------------

存储模型内存数据的Memtable，分层数据存储的SST文件，版本控制的Manifest、Current文件，以及写Memtable前的WAL。

WAL: Write-Ahead Logging预写日志系统

数据库中一种高效的日志算法，对于非内存数据库而言，磁盘I/O操作是数据库效率的一大瓶颈。在相同的数据量下，采用WAL日志的数据库系统在事务提交时，磁盘写操作只有传统的回滚日志的一半左右，大大提高了数据库磁盘I/O操作的效率，从而提高了数据库的性能。

---------------------

可以类比HBase的WAL机制，它提供了一种高并发、持久化的日志保存与回放机制。每一个业务数据的写入操作（PUT / DELETE）执行前，都会记账在WAL中。如果出现HBase服务器宕机，则可以从WAL中回放执行之前没有完成的操作。今天暂不讨论WAL机制。下图是leveldb 的原理图：

Memtable：

对应Leveldb中的内存数据，LevelDB的写入操作会直接将数据写入到Memtable后返回。读取操作又会首先尝试从Memtable中进行查询，允许写入和读取。当Memtable写入的数据占用内存到达指定数量，则自动转换为Immutable Memtable，等待Dump到磁盘中，系统会自动生成新的Memtable供写操作写入新数据。

Log文件：

当应用写入一条Key:Value记录的时候，LevelDb会先往log文件里写入，成功后将记录插进Memtable中，这样基本就算完成了写入操作，Log文件在系统中的作用主要是用于系统崩溃恢复而不丢失数据，假如没有Log文件，因为写入的记录刚开始是保存在内存中的，此时如果系统崩溃，内存中的数据还没有来得及Dump到磁盘，所以会丢失数据（Redis就存在这个问题，所以要开启持久化，例如AOF）。

---------------------

Immutable Memtable

当Memtable插入的数据占用内存到了一个界限后，需要将内存的记录导出到外存文件中，LevleDb会生成新的Log文件和Memtable，Memtable会变为Immutable，为之后向SST文件的归并做准备。顾名思义，Immutable Mumtable不再接受用户写入，只能读不能写入或者删除，同时会有新的Log文件和Memtable生成，LevelDb后台调度会将Immutable Memtable的数据导出到磁盘，形成一个新的SSTable文件。

---------------------

SST文件

SSTable就是由内存中的数据不断导出并进行Compaction操作(压缩操作，下文会讲到)后形成的，而且SSTable的所有文件是一种层级结构，第一层为Level 0，第二层为Level 1，依次类推，层级逐渐增高，这也是为何称之为LevelDb的原因。

磁盘数据存储文件。分为Level 0到Level N多层，每一层包含多个SST文件；单个SST文件容量随层次增加成倍增长；文件内数据有序；其中Level 0的SST文件由Immutable直接Dump产生，其他Level的SST文件由其上一层的文件和本层文件归并产生；SST文件在归并过程中顺序写生成，生成后仅可能在之后的归并中被删除，而不会有任何的修改操作。

---------------------

Manifest文件

Manifest文件中记录SST文件在不同Level的分布，单个SST文件的最大最小key，以及其他一些LevelDB需要的元信息。

SSTable中的某个文件属于特定层级，而且其存储的记录是key有序的，那么必然有文件中的最小key和最大key，这是非常重要的信息，LevelDb应该记下这些信息。Manifest就是干这个的

---------------------

Current文件

从上面的介绍可以看出，LevelDB启动时的首要任务就是找到当前的Manifest，而Manifest可能有多个。Current文件简单的记录了当前Manifest的文件名，从而让这个过程变得非常简单。

Current文件的内容只有一个信息，就是记载当前的manifest文件名。因为在LevleDb的运行过程中，随着Compaction的进行，SSTable文件会发生变化，会有新的文件产生，老的文件被废弃，Manifest也会跟着反映这种变化，此时往往会新生成Manifest文件来记载这种变化，而Current则用来指出哪个Manifest文件才是我们关心的那个Manifest文件。

---------------------

接下来看下这个存储引擎有哪些优缺点：

优点：

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；

---------------------

读写过程：

写操作流程：

1、顺序写入磁盘log文件；

2、写入内存memtable（采用skiplist结构实现）；

3、写入磁盘SST文件(sorted string table files)，这步是数据归档的过程（永久化存储）；

读操作流程：

1、在内存中依次查找memtable、immutable memtable；

2、如果配置了cache，查找cache；

3、根据mainfest索引文件，在磁盘中查找SST文件；

综上，想要深入了解原理，还需熟读源码，严格意义上leveldb并不算是个数据库，它只是kv存储系统，别的系统可以用它来做存储引擎。 通过动态链接或者静态链接的方式集成进来如果你写程序，需要存放数据，你可以用leveldb来存。然后编译你的代码的时候将leveldb的静态库或者动态库引进来就行，facebook将leveldb做了很多扩展，然后用作了mysql的一个存储引擎。