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空间。写入操作会首先操作内存中的树,随着内存中树的不断变大,会触发与磁盘中树的归并操作,而归并操作本身仅有顺序写。如下图所示:

LevelDB深入浅出之整体架构

图1 数据存储原理

图中2个红色区域是要进行归并的数据块,计算出顺序后会存储到如图下面的磁盘空间,而这种存储方式是追加式的,也就是顺序写入磁盘。

随着数据的不断写入,磁盘中的树会不断膨胀,为了避免每次参与归并操作的数据量过大,以及优化读操作的考虑,LevelDB将磁盘中的数据又拆分成多层,每一层的数据达到一定容量后会触发向下一层的归并操作,每一层的数据量比其上一层成倍增长。这也就是LevelDB的名称来源。主要特性

下面是LevelDB官方对其特性的描述,主要包括如下几点:

  1. key和value都是任意长度的字节数组;
  2. entry(即一条K-V记录)默认是按照key的字典顺序存储的,当然开发者也可以重载这个排序函数;
  3. 提供的基本操作接口:Put()、Delete()、Get()、Batch();
  4. 支持批量操作以原子操作进行;
  5. 可以创建数据全景的snapshot(快照),并允许在快照中查找数据;
  6. 可以通过前向(或后向)迭代器遍历数据(迭代器会隐含的创建一个snapshot);
  7. 自动使用Snappy压缩数据;
  8. 可移植性;

编译和使用

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的文件,文件内容如下:

LevelDB深入浅出之整体架构

测试程序功能很简单,就是向KV数据库添加1000个KV数据。后续我们还会用到这个程序,这里了解一下就行。具体通过如下命令可以编译成可执行程序。

g++ -o leveldbTest test.cpp libleveldb.a -lpthread -lsnappy

如果运行一下该程序,可以看到在当前目录会生成一个名为testbd1的目录,其中的内容如下所示:

LevelDB深入浅出之整体架构

图2 LevelDB的主要文件

整体结构

对LevelDB有一个整体的认识之后,我们分析一下它的架构。这里面有一个重要的概念(或者模块)需要理解,分别是内存数据的Memtable,分层数据存储的SST文件,版本控制的Manifest、Current文件,以及写Memtable前的WAL。这里简单介绍各个组件的作用和在整个结构中的位置,更详细的介绍本号将另外写文章进行介绍。在介绍之前,我们先看一下整体架构示意图:

LevelDB深入浅出之整体架构

图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所示。

LevelDB深入浅出之整体架构

图4 LevelDB写数据流程

具体代码请自行阅读,本文不贴过多的代码。这里需要重点说明的是DBImpl::Write函数,如图5是该函数的代码片段,从这段代码中我们可以很清楚的看到数据被分别写入日志和内存2个地方。其它代码都比较简单,大家请自行对照流程图阅读。

LevelDB深入浅出之整体架构

图5 DBImpl::Write代码片段

读流程简析

读流程要比写流程简单一些,核心代码逻辑如图6所示。首先,生成内部查询所用的Key,该Key是由用户请求的UserKey拼接上Sequence生成的。其中Sequence可以用户提供或使用当前最新的Sequence,LevelDB可以保证仅查询在这个Sequence之前的写入。然后,用生成的Key,依次尝试从 Memtable,Immtable以及SST文件中读取,直到找到。

LevelDB深入浅出之整体架构

图6 LevelDB读流程

  • 从SST文件中查找需要依次尝试在每一层中读取,得益于Manifest中记录的每个文件的key区间,我们可以很方便的知道某个key是否在文件中。Level0的文件由于直接由Immutable Dump 产生,不可避免的会相互重叠,所以需要对每个文件依次查找。对于其他层次,由于归并过程保证了其互相不重叠且有序,二分查找的方式提供了更好的查询效率。
  • 可以看出同一个Key出现在上层的操作会屏蔽下层的。也因此删除Key时只需要在Memtable压入一条标记为删除的条目即可。被其屏蔽的所有条目会在之后的归并过程中清除。

好了,今天就先到这,后续我们在深入的介绍LevelDB的其它部分的,并且逐步深入,理解其内部的精髓。

相关推荐

江沐涵 / 0评论 2013-06-29