Leveldb二三事

内容简介：Leveldb二三事

摘要

阅读这篇文章，希望你首先已经对Leveldb有了一定的了解，并预先知晓下列概念：

• LSM技术
• 跳表
• WAL技术
• Log Compaction

本文不是一篇专注于源代码解析的文章，也不是一篇Leveldb的介绍文。我们更希望探讨的是对于一般的单机数据存储引擎存在哪些问题，Leveldb作为一个经典实现，是采用什么策略并如何解决这些问题的。 Leveldb的解决方案是出于什么考虑，如何高效实现的，做出了哪些权衡以及如何组织代码和工程。你可以先从以下几篇文章对Leveldb有一个基本了解。

Leveldb的实现原理

LevelDB之LSM-Tree

LevelDB设计与实现

Leveldb的基本架构

数据模型和需求

首先提出几个问题：

• Leveldb在用户视图中的基本单元是什么？
• Leveldb一条记录在内存中的形式是什么，记录以怎样的方式被组织？
• Leveldb的记录在文件中的存储格式是什么，多条记录在单文件中是如何被管理的，多文件又是如何被管理的？
• Leveldb向用户做出了怎样的保证，在什么样的场景下提供了优化？

首先，Leveldb所处理的每条记录都是一条键值对，由于它基于sequence number提供快照读，准确来说应该是键，序列号，值三元组，由于用户一般关心最新的数据，可以简化为键值对。

Leveldb对持久化的保证是基于操作日志的，一条写操作只有落盘到操作日志中之后（暂时先这么理解，实际上这里有所出入，后面在优化部分会讲到）才会在内存中生效，才能被读取到。这就保证了对于已经能见到的操作，必定可以从操作日志中恢复。 它对一致性的保障可以认为对于同一键来说是linearity的（这里的一致性不是数据库理论的一致性，不强调从安全状态到另一个安全状态，而是指从各个视图看事件发生的顺序和真实情况一致），这是由于对于单个键值是串行化读写的。 在这里我们可以稍微脱离leveldb的实现放松一下一致性，如果我们不支持追加操作的情形下，写是幂等的，如果确保版本号是按照操作开始时间严格递增分配的，即使并发读写也是可以的，这样做还有一个问题，就是如何支持快照读，那就必须保留每一个写记录，但它们是乱序的，进行查找将是困难的，我们可以通过设置同步点，两个同步点之间的是写缓冲，快照读只有在写缓冲中需要遍历查找，在写缓冲被刷入之前重 排序 记录，刷入的时机是任意小于当前同步点版本号的写操作执行完毕。上述所描述的只可能适合于对热点key的大量并发写。上面所讨论的接近编程语言的内存模型，可以参考JMM内存模型或者C++内存模型。

Leveldb对写操作的要求是持久化到操作日志中，其所应对的数据量也超出了内存范围，或者说其存储内容的存储主体还是在磁盘上，只不过基于最近写的数据往往会被大量访问的假设在内存中存储了较新的数据。leveldb的核心做法就是保存了多个版本的数据以让写入操作不需要在磁盘中查找键的位置，将随机写改为顺序写，将这一部分代价某种程度上转嫁给读时在0层SSTable上的查找。那么它的读性能受到影响了吗？个人认为它的读性能稍显不足主要是受制于LSM的检索方式而非由于多版本共存的问题，当然写的便利也是基于这样的组织方式。

上面这几段主要是个人的一些想法，可能有些混乱，剩余的几个问题将在下面的部分再详细解答。

工程上的层次结构

leveldb的实现大致上可以分成以下几层结构：

• 向用户提供的DB类接口及其实现，主要是DB、DbImpl、iter等
• 中间概念层的memtable、table、version以及其辅助类，比如对应的iter、builder、VersionEdit等
• 更底层的偏向实际的读写辅助类，比如block、BlockBuilder、WritableFile及其实现等
• 最后是它定义的一些辅助类和实现的数据结构比如它用来表示数据的最小单元Slice、操作状态类Status、memtable中用到的SkipList等

可能的性能瓶颈

首先让我们考虑设计一款类似于Leveldb的存储产品，那么面临的主要问题主要是以下几项：

Leveldb的内存管理

什么应该在内存中

在内存中存放的数据主要包含当前数据库的元信息、memtable、ImmutableMemtable，前者显然是必要的，后两者存放的都是最新更新的数据。那么为什么需要有ImmutableMemtable呢。这是为了在持久化到磁盘上的同时保持对外服务可用，如果没有这样一个机制，那么我们要么需要持久化两次，并在第一次持久化的中途记录增量日志，第二次应用上去，这是CMS垃圾回收器的做法，但是显然十分复杂；还有一种选择是我们预留一定的空间，直接将要持久化的memtable拷贝一份，这样做显然会浪费大量可用内存，对于一个数据库来说，这是灾难性的。

那么元信息具体应该包含哪些信息呢？

• 当前的操作日志句柄
• 版本管理器、当前的版本信息（对应compaction）和对应的持久化文件标示
• 当前的全部db配置信息比如comparator及其对应的memtable指针
• 当前的状态信息以决定是否需要持久化memtable和合并sstable
• sstable文件集合的信息

上面列出了一些比较重要的元信息，可能还有遗漏

memtable详解

memtable的结构

memtable的键包含三个部分：

• Slice user ley
• sequence number
• value type

键的比较器首先按照递增顺序比较user key，然后安装递减顺序比较sequence number，这两个足以唯一确定一条记录了。把user key放到前面的原因是，这样对同一个user key的操作就可以按照sequence number顺序连续存放了，不同的user key是互不相干的，因此把它们的操作放在一起也没有什么意义。用户所传入的是LookupKey，它也是由User Key和Sequence Number组合而成的，其格式为：

| Size (int32变长)| User key (string) | sequence number (7 bytes) | value type (1 byte) |

这里的Size是user key长度+8，也就是整个字符串长度了。value type是kValueTypeForSeek，它等于kTypeValue。由于LookupKey的size是变长存储的，因此它使用kstart_记录了user key string的起始地址，否则将不能正确的获取size和user key。

memtable本身存储同一键的多个版本的数据，这一点从刚刚指出的键的格式也可以看出。这里为什么不直接在写的时候直接将原有值替换并使用用户键作为查找键呢？毕竟在memtable中add和update都需要先进行查找。个人认为除了需要支持快照读也没有别的解释了，虽然这样做会使得较老的记录没有被compact而较新的记录已经compact了的奇怪现象发生，但并不影响数据库的读写，在性能上也没有损害。那么快照读为何是必要的呢？这个问题我目前也没有很好的回答，读者可以自行思考。

memtable的追加

memtable的追加操作主要是将键值对进行编码操作并最后委托给跳表处理，代码很简单，就放上来吧。

// KV entry字符串有下面4部分连接而成  
   //  key_size     : varint32 of internal_key.size()  
//  key bytes    : char[internal_key.size()]  
//  value_size   : varint32 of value.size()  
//  value bytes  : char[value.size()]  
size_t key_size = key.size();  
size_t val_size = value.size();  
size_t internal_key_size = key_size + 8;  
const size_t encoded_len =  
    VarintLength(internal_key_size) + internal_key_size +  
    VarintLength(val_size) + val_size;  
char* buf = arena_.Allocate(encoded_len);  
char* p = EncodeVarint32(buf, internal_key_size);  
memcpy(p, key.data(), key_size);  
p += key_size;  
EncodeFixed64(p, (s << 8) | type);  
p += 8;  
p = EncodeVarint32(p, val_size);  
memcpy(p, value.data(), val_size);  
assert((p + val_size) - buf == encoded_len);  
table_.Insert(buf);

有关跳表可以参考下列文章：

Skip List（跳跃表）原理详解与实现

memtable的查找

根据传入的LookupKey得到在memtable中存储的key，然后调用Skip list::Iterator的Seek函数查找。Seek直接调用Skip list的FindGreaterOrEqual(key)接口，返回大于等于key的Iterator。然后取出user key判断时候和传入的user key相同，如果相同则取出value，如果记录的Value Type为kTypeDeletion，返回Status::NotFound(Slice())。本质上依然委托跳表处理。

内存分配和释放

Leveldb自己实现了基于引用计数的垃圾回收和一个简单的内存池Arena，其实现预先分配大内存块，划分为不同对齐的内存空间，其机制乏善可陈，在这里就不多言，放张图吧。

Arena主要提供了两个申请函数：其中一个直接分配内存，另一个可以申请对齐的内存空间。Arena没有直接调用delete/free函数，而是由Arena的析构函数统一释放所有的内存。应该说这是和leveldb特定的应用场景相关的，比如一个memtable使用一个Arena，当memtable被释放时，由Arena统一释放其内存。

另外就是对于许多类比如memtable、table、cahe等leveldb都加上了引用计数，其实现也非常简单，就是在对象中加入数据域refs，这也非常好理解。比如在迭代的过程中，已经进入下一个block中了，上一个block理应可以释放了，但它有可能被传递出去提供某些查询服务使用，在其计数不为0时不允许释放，同理对于immutable_memtable，当它持久化完毕时，如果还在为用户提供读服务，也不能释放。不得不说Leveldb的工程层次很清楚，几乎没有循环引用的问题。

Leveldb的磁盘存储

需要存储的内容

对于一个db，大致需要存储下列文件

• db的操作日志
• 存储实际数据的SSTable文件
• DB的元信息Manifest文件
• 记录当前正在使用的Manifest文件，它的内容就是当前的manifest文件名
• 系统的运行日志，记录系统的运行信息或者错误日志。
• 临时数据库文件，repair时临时生成的。

SSTable详解

SSTable文件组织

单个SSTable文件的组织如下图所示：

大致分为几个部分：

• 数据块 Data Block，直接存储有序键值对
• Meta Block，存储Filter相关信息
• Meta Index Block，对Meta Block的索引，它只有一条记录，key是meta index的名字（也就是Filter的名字），value为指向meta index的位置。
• Index Block，是对Data Block的索引，对于其中的每个记录，其key >=Data Block最后一条记录的key，同时<其后Data Block的第一条记录的key；value是指向data index的位置信息
• Footer，指向各个分区的位置和大小，示意图如下：

所有类型的block格式是一致的，主要包含下面几部分：

其中type指的是采用哪种压缩方式，当前主要是snappy压缩，接下来主要讲讲block data部分的组织：

snappy是前缀压缩的，为了兼顾查找效率，在构建Block时，每隔几个key就直接存储一个重启点key。Block在结尾记录所有重启点的偏移，可以二分查找指定的key。Value直接存储在key的后面，无压缩。

普通的kv对存储结构如下：

• 共享前缀长度
• 非共享键部分的长度
• 前缀之后的字符串
• 值

总体的Block Data如下：

总体来看Block可分为k/v存储区和后面的重启点存储区两部分，后面主要是重启点的位置和个数。Block的大小是根据参数固定的，当不能存放下一条记录时多余的空间将会闲置。

SSTable逻辑表达

SSTable在代码上主要有负责读相关的Table、Block和对应的Iterator实现；在写上主要是BlockBuilder和TableBuilder。可以看出来这也是个典型的二层委托结构了，上面的层次将操作委托给下面层次的类执行，自己管控住progress的信息，控制当前的下层实体。这里我们主要关心Table和Block中应该存放哪些信息以支持它们的操作。

先讲讲简单的Block，毫无疑问除了数据（char*+size）本身以外就是重启点了，重启点可是查询的利器啊，直接的思路是解析重启点部分成一个vector等，实际上Leveldb不是这样做的，只是保留了一个指向重启点部分的指针，至于为什么我们在查询一节里再详谈。

再说说Table，

SSTable的写入

首先，我们考虑在内存中构建一个连续的内存区域代表一个block的内容，它又可以分为两部分：1. 数据的写入 2. 数据写入完毕后附加信息的添加。 先考虑追加一条记录，我们需要知道哪些东西？

• 当前block提供给数据的剩余空间以确定是否需要换block
• 当前的重启点以确定共享前缀
• 当前重启点已有的key数量以确定是否将本次写入作为新的重启点
• 确保key的有序性，所以必须知道上次添加的key

在确定这些需要的信息后，追加的过程就是查找和维护这些信息以及单纯的memcpy了。

第二步，让我们考虑在数据写入完毕之后需要为block添加其他信息的过程：

• 我们需要记录所有的重启点和重启点位置，我们不得不在追加的时候来维护它们，看来得回去改上面的代码了
• 我们得从配置元数据中得到压缩类型
• 最后我们得记录CRC

现在，我们可以把这么一段char[]的数据转换成Slice表达的block了。接下来，让我们考虑如何批量的把数据写入单个SSTable文件中。这同样分为三个步骤：1. 追加数据 2. 附加信息 3. Flush到文件。 我们依次考虑。

追加数据需要做哪些：

• 知道当前block及当前block能否再添加一条数据
• 维护有序性，需要上一次的key和新加key比较
• 如果生成新的block，为了维护索引，需要为将被替换的block生成索引记录，所以必须维护一个index Block
• 维护过滤器信息（这一部分将在布隆过滤再详细解释，可以暂时忽略）
• 为了决定是否需要刷到文件中去，需要知道已写的block数

实际上向文件写入是以Block为单位的，当我们完成一个Block时，在将它写入文件时需要做什么呢？

• 检查工作，确定block确实需要写入
• 压缩工作
• 通知工作，告知index Block和Filter Block的维护方
• 重置工作，将当前block重置，准备下一次追加

最后，当数据全部添加完毕，该SSTable文件从此将不可变更，这一步需要执行的是：

• 写入最后一块data block
• 写入Meta Block
• 根据上文写入时留存的位置信息构建Meta Index Block
• 写入Meta Index Block
• 将最后的data block位置信息写入Index Block中，并将Index Block写入文件
• 写入Footer信息

SSTable的遍历

SSTable的遍历主要委托给一个two level iterator处理，我们只需要弄清楚它的Next操作就能明白其工作原理。所谓的two level，指的是索引一层，数据一层。在拿到一个SSTable文件的时候，我们先解析它的Index block部分，然后根据当前的index初始化data block层的iterator。接下来我们主要关注Next的过程。

分为两种情形：

1. 当前记录不是当前Data Block的最后一条，只需要data iter向前进一步即可
2. 当前记录是最后一条，这时就要先前进一步index iter，得到data block的位置信息
3. 读取data block，此处先暂时省略table cache的优化，简单起见都是从文件中读
4. 创建新的data iter

当然，二级迭代器还做了许多的其他工作，比如允许你传入block function，但这和我们讨论的主线无关，这里就不过多陈述了。

SSTable的查询

SSTable的查询也委托给iter处理，其主要过程就是对key的定位，也是主要分为三部分：

• 定位到哪个block
• 迁移到该block上
• 定位到block中的哪一条

无论是index block还是data block，它们的iter实现是一致的，其查找都遵循以下过程：

• 通过重启点进行二分查找
• 跳到最大的不比目标大的重启点，遍历查找，一直到一个不比目标小的key出现

这里最绝妙的是两点

• index block的设计和二级迭代器，一方面通过这种手段进行快速定位，另一方面将遍历和查找统一到一个框架下，不可谓不妙
• 重启点的设计，避免解析数据内容快速使用二分查找定位key的大致区域

我们都知道磁盘的读写是十分耗时的，索引的手段大量减少了磁盘读的必要。当然，还有许多加速的手段比如过滤器和缓存，我们将在最后一节详细解释。

元信息存储与管理

元信息文件的格式

元信息的逻辑表达

元信息的修改和维护

操作日志存储与管理

Leveldb的交互流程

db相关操作

recovery过程

读过程

写过程

Leveldb的Log Compaction

Log Compaction的经典问题

在解释Leveldb的log compaction过程之前我们先回顾几个关于如何做compaction的重要问题：

• 何时需要做compaction
• 具体怎么做compaction
• 如何在compaction的同时保证服务可用
• compaction对性能的影响
• 如何在服务的延迟和单次compaction的收益做trade off

我们接下来将主要围绕这些问题给出Leveldb的答案。

compaction的时机

Leveldb的工程优化

write batch

table cache

布隆过滤器

总结

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

• Leveldb二三事

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。