LevelDB系统结构与设计思路分析

LevelDB整体架构

LevelDB可以看作是Google BigTable的单机kv存储引擎，它是一个kv型持久性存储的C++程序库。关于它的整体架构这里不在详述，可以参考文章LevelDB的设计与实现，文章主要讲述了LevelDB的全局结构，数据扭转流程，系统中的数据布局，以及一些重要的结构等，可以通过这篇文章从宏观上了解LevelDB。下面主要讲述自己通过阅读LevelDB源码后，对它的一些理解。

源码结构分析

源码结构

下图为阅读LevelDB源码后，对它的各个模块之间的关系的一个抽象化的理解

下面首先来了解各模块，然后来通过一些重要流程来把各个模块串联起来

模块说明

DB 和 DBImpl

DB是leveldb对外的模块，它提供了对leveldb数据库进行操作的接口。它提供的访问数据库的接口有：

Open: 打开数据库，获取操作数据库的对象指针。同时leveldb只能单进程访问，进程间通过lock文件来保证这一点，同时进程内通过记录打开的db name来保证这一点
Put: 将（key，value）写入数据库
Write: 提供原子的批量写操作
Delete: 删除某个key对应的entry，leveledb内部当作写操作，用类型字段区分正常写入操作和删除操作
Get: 获取key对应的value
NewIterator: 数据库的迭代器，可以用它进行scan操作

同时它还提供了一些其它操作接口，比较重要的有两个：

GetSnapshot: 获取当前DB状态的快照，这样使得读操作能在DB当前状态下进行，不受后续写操作的影响
compactRange: 提供manual compact的接口，可以制定range去做compaction

DBImpl则提供了DB各个接口的具体实现，这里就不在细述

Env

Env抽象化和操作系统相关的环境，这样方便用户定制。它主要提供了和文件系统相关的接口，比如文件创建，读写等。还提供了和线程相关的接口，主要用在使用background线程去做compaction的时候

VersionSet, Version, VersionEdit

• Version保存当前磁盘以及内存中的文件信息，一般只有一个version为”current version”。同时还保存了一系列的历史version，这些version的存在是因为有读操作还在引用（iterator和get，Compaction操作后会产生新的version作为current version
• VersionSet就是一系列Version的集合
• VersionEdit表示Version之间的变化，表示增加了多少文件，删除了多少文件

Snapshot

• 快照提供了一个当前KV存储的一个可读视图，使得读取操作不受写操作影响，可以在读操作过程中始终看到一致的数据
• 一个快照对应当前存储的最新数据版本号

MemTable, Immutable MemTable

• MemTable是leveldb的内存缓存。它也提供了数据的写入，删除，读取等操作接口。它内部采用Skiplist作为数据组织结构，同时它使用自己实现的Arena作为内存分配器。
• Immutable MemTable和MemTable结构是完全一样的，只不过它是只读的，当MemTable中的数据量达到一定程度时会转换成Immutable MemTable。

TableBuilder, BlockBuilder

TableBuilder: 将数据按照sst文件的格式组织后，写入sst文件
BlockBuilder: 将数据按照Block的格式组织起来，被TableBuilder使用
BuildTable: 在将MemTable的数据写入sst时调用，使用TableBuilder来实现

TableCache, BlockCache

TableCache和BlockCache底层都是用了LRUCache的数据结构

• TableCache: 缓存了Table相关的信息，包括Table对应的File指针，以及Table对象的指针，Table对象包含了Table的元数据，索引信息等。可以防止过多的文件open
• BlockCache: 缓存块数据

重要流程分析

下面我们通过一些重要流程的分析，将上述模块串联起来

Open

下图为Open流程的简要流程图

它的主要流程为：

1. New DBImpl: 创建DBImpl对象
2. DBImpl::Recover: 恢复数据库，主要流程就是通过manifest文件来恢复出VersionSet，表示当前数据库的文件信息；然后再恢复未记录在manifest中的log文件，将log文件的数据重新写入MemTable中。
3. VersionSet::LogAndApply: 如果DBImpl在恢复过程中产生了新的文件，那么就会产生VersionEdit，需要将VersionEdit记录在manifest文件中，同时将VersionEdit Apply在VersionSet中，产生新的version。
4. DBImpl::DeleteObsoleteFiles：将一些不需要的文件删除
5. DBImpl::MaybeScheduleCompaction：尝试是否需要进行Compaction

Put

下图为Put流程的简要流程图

1. Put操作会将(key,value)转化成writebatch后，通过write接口来完成
2. 在write之前需要通过MakeRoomForWrite来保证MemTable有空间来接受write请求，这个过程中可能阻塞写请求，以及进行compaction。
3. BuildBatchGroup就是尽可能的将多个writebatch合并在一起然后写下去，能够提升吞吐量
4. AddRecord就是在写入MemTable之前,现在操作写入到log文件中
5. 最后WriteBatchInternal::InsertInto会将数据写入到MemTable中

Get

下图为Get流程的简要流程图

1. 首先判断options.snapshot是否为空，如果为不为空，快照值就取这个值，否则取最新数据的版本号

2. 然后依次尝试去MemTable, Immutable MemTable, VersionSet中去查找。VersionSet中的查找流程:

   1. 逐层查找，确定key可能所在的文件
   2. 然后根据文件编号,在TableCache中查找，如果未命中，会将Table信息Load到cache中
   3. 根据Table信息，确定key可能所在的Block
   4. 在BlockCache中查找Block，如果未命中，会将Block load到Cache中。然后在Block内查找key是否命中
3. 更新读数据的统计信息，作为一根文件是否应该进行Compaction的依据，后面讲述Compaction时会说明
4. 最后释放对Memtable，Immutable MemTable，VersionSet的引用

Compaction

在leveldb中compaction主要包括Manual Compaction和Auto Compaction，在Auto Compaction中又包含了MemTable的Compaction和SSTable的Compaction。

Manual Compaction

leveldb中manual compaction是用户指定需要做compaction的key range，调用接口CompactRange来实现，它的主要流程为：

1. 计算和Range有重合的MaxLevel
2. 从level 0 到 MaxLevel依次在每层对这个Range做Compaction
3. 做Compaction时会限制选择做Compaction文件的大小，这样可能每个level的CompactRange可能需要做多次Compaction才能完成

SSTable Compaction

1. 启动条件

   • 每个Level的文件大小或文件数超过了这个Level的限制（L0对比文件个数，其它Level对比文件大小。主要是因为L0文件之间可能重叠，文件过多影响读访问，而其它level文件不重叠，限制文件总大小，可以防止一次compaction IO过重）。
   • 含有被寻道次数超过一定阈值的文件(这个是指读请求查找可能去读多个文件，如果最开始读的那个文件未查找到，那么这个文件就被认为寻道一次，当文件的寻道次数达到一定数量时，就认为这个文件应该去做compaction)
   • 条件1的优先级高于条件2

2. 触发条件

   • 任何改变了上面两个条件的操作，都会触发Compaction，即调用MaybeScheduleCompaction
   • 涉及到第一个条件改变，就是会改变某层文件的文件数目或大小，而只有Compaction操作之后才会改变这个条件
   • 涉及到第二个条件的改变，可能是读操作和scan操作(scan操作是每1M数据采样一次，获得读最后一个key所寻道的文件，1M数据的cost大约为一次寻道)

3. 文件选取

   • 每个level都会记录上一次Compaction选取的文件所含Key的最大值，作为下次compaction选取文件的起点
   • 对于根据启动条件1所做的Compaction，选取文件就从上次的点开始选取，这样保证每层每个文件都会选取到
   • 对于根据启动条件2所做的Compaction，需要做compaction的文件本身就已经确定了
   • Level + 1层文件的选取，就是和level层选取的文件有重合的文件

   在leveldb中在L层会选取1个文件，理论上这个文件最多覆盖的文件数为12个（leveldb中默认一个文件最大为2M，每层的最大数据量按照10倍增长。这样L层的文件在未对齐的情况下最多覆盖L+1层的12个文件），这样可以控制一次Compaction的最大IO为（1+12）* 2M读IO，总的IO不会超过52M

MemTable Compaction

MemTable Compaction最重要的是产出的文件所在层次的选择，它必须满足如下条件： 假设最终选择层次L，那么文件必须和[0, L-1]所有层的文件都没有重合，且对L+1层文件的覆盖不能超过一定的阈值（保证Compaction IO可控)

Compaction 文件产出

1. 什么时候切换产出文件

   • 文件大小达到一定的阈值
   • 产出文件对Level+2层有交集的所有文件的大小超过一定阈值

2. key丢弃的两个条件

   • last_sequence_for_key <= smallest_snapshot (有一个更新的同样的user_key比最小快照要小）
   • key_type == del && key <= smallest_snapshot && IsBaseLevelForKey（key的类型是删除，且这个key的版本比最小快照要小，并且在更高Level没有同样的user_key)

总结与思考

1. LSM存储模型：牺牲读性能，提高随机写性能
2. Level存储架构：尽可能地优化读性能，同时减少对写性能的影响。假设没有Level的概念，每次读请求都要去访问多个文件，于是才有Level的概念去做compaction，尽可能减少读取的文件数，同时又保证了每次Compaction IO的数据量，保证对正常的写请求影响不会太大。
3. LSM和Level之间是相互均衡的关系，它们决定了读写性能。在不同的应用场景下，我们需要在两者间有所取舍。

参考文献

[1]. https://github.com/google/leveldb/tree/master/doc.

[2]. https://dirtysalt.github.io/html/leveldb.html#orgheadline88.

[3]. https://blog.csdn.net/anderscloud/article/details/7182165.

[4]. https://www.atatech.org/articles/65485