LevelDB深入浅出之整体架构
longzuo 2019-05-27
LevelDB是一个可持久化的KV数据库引擎，由Google传奇工程师Jeff Dean和Sanjay Ghemawat开发并开源。无论从设计还是代码上都可以用精致优雅来形容，非常值得细细品味。本文将从整体特性、架构和使用等几方面做一个解释，试图通过本文的介绍让大家对LevelDB有个整体的认识并能够使用。
设计思路
做存储的同学都很清楚，对于普通机械磁盘顺序写的性能要比随机写大很多。比如对于15000转的SAS盘，4K写IO， 顺序写在200MB/s左右，而随机写性能可能只有1MB/s左右。而LevelDB的设计思想正是利用了磁盘的这个特性。
LevelDB的数据是存储在磁盘上的，采用LSM-Tree的结构实现。LSM-Tree将磁盘的随机写转化为顺序写，从而大大提高了写速度。为了做到这一点LSM-Tree的思路是将索引树结构拆成一大一小两颗树，较小的一个常驻内存，较大的一个持久化到磁盘，他们共同维护一个有序的key空间。写入操作会首先操作内存中的树，随着内存中树的不断变大，会触发与磁盘中树的归并操作，而归并操作本身仅有顺序写。如下图所示：
图1 数据存储原理
图中2个红色区域是要进行归并的数据块，计算出顺序后会存储到如图下面的磁盘空间，而这种存储方式是追加式的，也就是顺序写入磁盘。
随着数据的不断写入，磁盘中的树会不断膨胀，为了避免每次参与归并操作的数据量过大，以及优化读操作的考虑，LevelDB将磁盘中的数据又拆分成多层，每一层的数据达到一定容量后会触发向下一层的归并操作，每一层的数据量比其上一层成倍增长。这也就是LevelDB的名称来源。主要特性
下面是LevelDB官方对其特性的描述，主要包括如下几点：
- key和value都是任意长度的字节数组；
- entry（即一条K-V记录）默认是按照key的字典顺序存储的，当然开发者也可以重载这个排序函数；
- 提供的基本操作接口：Put()、Delete()、Get()、Batch()；
- 支持批量操作以原子操作进行；
- 可以创建数据全景的snapshot(快照)，并允许在快照中查找数据；
- 可以通过前向（或后向）迭代器遍历数据（迭代器会隐含的创建一个snapshot）；
- 自动使用Snappy压缩数据；
- 可移植性；
编译和使用
LevelDB的编译也是比较简单的，可以从官网直接克隆代码。https://github.com/google/leveldb，具体操作步骤如下(可以参考源代码中的README文件)：
git clone https://github.com/google/leveldb.git cd leveldb mkdir -p build && cd build cmake -DCMAKE_BUILD_TYPE=Release .. && cmake --build .
完成上述几步，就可以编译出一个静态库、一个动态库和一些测试程序。我们可以自己写一个测试代码进行测试。比如我们在leveldb目录下面创建一个test目录， 然后将静态库libleveldb.a拷贝进来，然后在其中创建一个名为test.cpp的文件，文件内容如下：
测试程序功能很简单，就是向KV数据库添加1000个KV数据。后续我们还会用到这个程序，这里了解一下就行。具体通过如下命令可以编译成可执行程序。
g++ -o leveldbTest test.cpp libleveldb.a -lpthread -lsnappy
如果运行一下该程序，可以看到在当前目录会生成一个名为testbd1的目录，其中的内容如下所示：
图2 LevelDB的主要文件
整体结构
对LevelDB有一个整体的认识之后，我们分析一下它的架构。这里面有一个重要的概念（或者模块）需要理解，分别是内存数据的Memtable，分层数据存储的SST文件，版本控制的Manifest、Current文件，以及写Memtable前的WAL。这里简单介绍各个组件的作用和在整个结构中的位置，更详细的介绍本号将另外写文章进行介绍。在介绍之前，我们先看一下整体架构示意图：
图3 LevelDB整体架构图
如图3所示，对于写数据，接口会同时写入内存表（MemTable）和日志中。当内存表达到阈值时，内存表冻结，变为Immutable MemTable，并将数据写入SST表中，其中SST表时在磁盘上的文件。下面是涉及到主要模块的简单介绍：
- Memtable：内存数据结构，跳表实现，新的数据会首先写入这里；
- Log文件：写Memtable前会先写Log文件，Log通过append的方式顺序写入。Log的存在使得机器宕机导致的内存数据丢失得以恢复；
- Immutable Memtable：达到Memtable设置的容量上限后，Memtable会变为Immutable为之后向SST文件的归并做准备，顾名思义，Immutable Mumtable不再接受用户写入，同时会有新的Memtable生成；
- SST文件：磁盘数据存储文件。分为Level 0到Level N多层，每一层包含多个SST文件；单层SST文件总量随层次增加成倍增长；文件内数据有序；其中Level0的SST文件由Immutable直接Dump产生，其他Level的SST文件由其上一层的文件和本层文件归并产生；SST文件在归并过程中顺序写生成，生成后仅可能在之后的归并中被删除，而不会有任何的修改操作。
- Manifest文件： Manifest文件中记录SST文件在不同Level的分布，单个SST文件的最大最小key，以及其他一些LevelDB需要的元信息。
- Current文件: 从上面的介绍可以看出，LevelDB启动时的首要任务就是找到当前的Manifest，而Manifest可能有多个。Current文件简单的记录了当前Manifest的文件名，从而让这个过程变得非常简单。
写流程简析
了解了整体流程和架构后，我们分析两个基本的流程，也就是LevelDB的写流程和读流程。我们这里首先分析一下写流程，毕竟要先有数据后才能读数据。
LevelDB的写操作包括设置key-value和删除key两种。需要指出的是这两种情况在LevelDB的处理上是一致的，删除操作其实是向LevelDB插入一条标识为删除的数据。下面我们先看一下LevelDB插入值的整体流程，具体如图4所示。
图4 LevelDB写数据流程
具体代码请自行阅读，本文不贴过多的代码。这里需要重点说明的是DBImpl::Write函数，如图5是该函数的代码片段，从这段代码中我们可以很清楚的看到数据被分别写入日志和内存2个地方。其它代码都比较简单，大家请自行对照流程图阅读。
图5 DBImpl::Write代码片段
读流程简析
读流程要比写流程简单一些，核心代码逻辑如图6所示。首先，生成内部查询所用的Key，该Key是由用户请求的UserKey拼接上Sequence生成的。其中Sequence可以用户提供或使用当前最新的Sequence，LevelDB可以保证仅查询在这个Sequence之前的写入。然后，用生成的Key，依次尝试从 Memtable，Immtable以及SST文件中读取，直到找到。
图6 LevelDB读流程
- 从SST文件中查找需要依次尝试在每一层中读取，得益于Manifest中记录的每个文件的key区间，我们可以很方便的知道某个key是否在文件中。Level0的文件由于直接由Immutable Dump 产生，不可避免的会相互重叠，所以需要对每个文件依次查找。对于其他层次，由于归并过程保证了其互相不重叠且有序，二分查找的方式提供了更好的查询效率。
- 可以看出同一个Key出现在上层的操作会屏蔽下层的。也因此删除Key时只需要在Memtable压入一条标记为删除的条目即可。被其屏蔽的所有条目会在之后的归并过程中清除。
好了，今天就先到这，后续我们在深入的介绍LevelDB的其它部分的，并且逐步深入，理解其内部的精髓。
