LevelDB关键实现图解

LevelDB是Google开源出的一个Key/Value存储引擎，它采用C++编写的，支持高并发访问和写入，特别适合对于高写入业务环境。 对于LevelDB的概览可以参考数据分析与处理之二（Leveldb 实现原理）对LevelDB的一个描述，本文的图解更多的是LevelDB的一个实现层的纠缠，版本为LevelDB 1.7.02。

LevelDB存储主要分为SSTable和MemTable，前者为不可变且存储于持久设备上，后者位于内存上并且可变(在LevelDB中有两个MemTable，一个为当前写入MemTable，另一个为等待持久化的不可变MemTable)。首先来看SSTable的实现层分析。

(黄色代表方法，蓝色代表变量或者对象成员，橙色代表类，白色为说明或者外部源)

SSTable的访问实现

点击看大图

从SSTable中可以发现，LevelDB中SSTable的访问使用一个抽象类Iterator来实现，不管是一个Level的Table还是一个Block的记录都实现了Iterator的接口，对于某个键的访问通过一个Level的Table的键值范围确定，再深入一个Table的Block范围确定。另外，对于一个Table，LevelDB还提供了表级的缓存和块级的缓存。

SSTable的建立

点击看大图

由于SSTable是不可变，一旦建立就无需修改，而且要么是通过MemTable转换而来要么就是Table合并而成，只需要不断的写入然后Build Block即可。

SSTable内部格式

点击看大图

该图展现的是一个SSTable的内部格式，SSTable中存在几个固定大小划分的区域，每个区域都有自己的校验码，而逻辑上的Block存在于这些区域的数据域(图中最下面的蓝色Block)。每个逻辑Block中分为Data Block和Meta Block、MetaIndex Block、Index Block和Footer，当LevelDB初始化时会读取逻辑块的信息时，它会从Footer块读取Index Block和MetaIndex Block的偏移，再通过读取Index Block和MetaIndex Block的偏移来得到Data Block和Meta Block。其中Data Block和Index Block具有相同的Block格式，不同在于Data Block的Record存储一个key/value，而Index Block存储的是Key和对应Key的Data Block偏移。

MemTable解析

点击看大图

MemTable的访问同样是实现了Iterator的接口进行，索引采用SkipList实现，在MemTable中，LookupKey代表了一个键值在访问和写入时在内存中的表示，它的三个方法分别表示三种不同的键表示。

转载请注明：爱开源 » LevelDB关键实现图解