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

江沐涵 2018-07-24

LevelDB整体架构

LevelDB可以看作是Google BigTable的单机kv存储引擎,它是一个kv型持久性存储的C++程序库。关于它的整体架构这里不在详述,可以参考文章LevelDB的设计与实现,文章主要讲述了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流程的简要流程图

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

它的主要流程为:

  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流程的简要流程图

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

  1. 首先判断options.snapshot是否为空,如果为不为空,快照值就取这个值,否则取最新数据的版本号
  2. 然后依次尝试去MemTable, Immutable MemTable, VersionSet中去查找。VersionSet中的查找流程:
  3. 逐层查找,确定key可能所在的文件
  4. 然后根据文件编号,在TableCache中查找,如果未命中,会将Table信息Load到cache中
  5. 根据Table信息,确定key可能所在的Block
  6. 在BlockCache中查找Block,如果未命中,会将Block load到Cache中。然后在Block内查找key是否命中
  7. 更新读数据的统计信息,作为一根文件是否应该进行Compaction的依据,后面讲述Compaction时会说明
  8. 最后释放对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层选取的文件有重合的文件

4.在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之间是相互均衡的关系,它们决定了读写性能。在不同的应用场景下,我们需要在两者间有所取舍。

本文作者:神手不痴

相关推荐

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