2006 年，Google 发布了一篇论文Bigtable: A Distributed Storage System for Structured Data^[1]，描述了一个用于管理结构化数据的分布式存储系统 - Bigtable 的数据模型、接口以及实现等内容。随后，市面上出现了以 Apache HBase 为代表的开源分布式实现版本，以及本文要介绍的，由 Google 自家实现（Bigtable 的作者 Jeff Dean^[2] 和 Sanjay Ghemawat^[3] 共同完成）的单机引擎库LevelDB^[4]。

LevelDB 和基于其衍生的 RocksDB 在业界有很广泛的应用。

简介

LevelDB 是一个高效的 key-value 存储引擎库，由 LSM 树实现，具有的随机写和顺序读写性能，大范围随机读性能稍差，适合用于少量随机查询、大量写入的场景，并且对磁盘的利用非常高效。

主要特性如下：

• key-value 面向字节，可以存储任意类型数据
• 数据按 key 顺序存储，用户也可以自定义排序函数来重载这个行为
• 基本操作为Put(key,value), Get(key), Delete(key)
• 支持聚合若干操作的原子性处理
• 允许创建全局快照，进行数据正序/逆序遍历
• 数据使用 snappy 透明压缩
• 文件操作进行了抽象，用户可以自行实现对应接口（如用 HDFS 存储）

当然也有一些局限：

• 不是关系型数据库，不支持 SQL 查询，不支持索引
• 只支持单进程（多线程）访问一个数据库
• 仅提供数据读写操作，上层网络访问需要用户自己封装

整体架构

关键概念

• MemTable，LevelDB 的内存结构，所有写入操作先写入这个区域，不会直接写磁盘
• Immutable MemTable，只读的 MemTable，MemTable 满了之后会转化为只读状态，准备刷盘持久化
• sstable，MemTable 在磁盘上的持久化形态，下文简称 sst
• level，这个其实不是个物理结构，是逻辑上 sstable 的分组，数字越大，代表存在时间越长
• log，WAL（Write Ahead Log），数据持久化能力的关键保障，写 MemTable 之前会先写 log
• manifest，记录 sstable 所在层级、大/小 key 范围等元数据的文件，随着写入的增加，会分裂成多个 manifest，来加速故障恢复
• current，记录了当前的 manifest 是哪个

写入操作

写入内存

在写入内存之前，为了保证意外掉电、重启等操作不丢数据，会先写 log(即 WAL)，写成功之后再写入内存。如果发生意外，可以从 log 中恢复数据。

LevelDB 为了保证写入的高效，所有写入操作会先写内存结构 MemTable，当 MemTable 达到阈值（默认 4M）后，会转变成为只读的 Immutable MemTable，等待压缩线程写入磁盘，此时 LevelDB 会生成新的 MemTable 以供写入。

LevelDB 不仅能写入，还能删除数据，在做删除操作时，不会做物理删除，只是在对应数据上标记删除，等待压缩写盘时忽略掉，这样做是为了减少 MemTable 数据结构维护的代价，以及减少因此带来的并发竞争状态。

为了兼顾 MemTable 的读写速度，以及存储空间使用，采用了 skiplist 结构。skiplist 可以简单理解为一个拥有多级索引的链表，读取的时间复杂度为 O(n)，理论上写入时间复杂度为 O(1)，但是写入前必须找到对应的节点位置，所以写入复杂度也降级到 O(n)。

Immutable MemTable 本质上和 MemTable 是同一个东西，结构一样。

值得一提的是，redis 里的 hash/zset 在容量较小的时候也是用了 skiplist，目的是减少内存使用。

磁盘结构

如前文所述，当 MemTable 达到阈值（默认 4M）后，会转变成为只读的 Immutable MemTable，这时候会顺带触发一个 minor compaction，将 Immutable MemTable 持久化成 sst。

下面着重分析一下 sst

sst 整体结构

sst 文件内部划分成固定大小的 block，每个 block 包含以下几个部分：

• data，承载的数据
• 压缩类型
• CRC 校验码

单个 block 结构

每个 block 可以用来存储不同的内容，有以下几种：

• data block，kv 数据对
• index block，data block 索引
• filter block，布隆过滤器
• meta index blocck，filter block 索引
• footer，整个 block 的索引信息

data block

data block 是 LevelDB 承载数据的部分，每一对 kv 都是一个 entry，一个 data block 中有若干个 entry 和少量 restart point 组成。

一个 entry 由几个部分组成：

• 和前一个 entry 共享 key 长度
• 不共享 key 长度
• value 长度
• 不共享 key 内容
• value 内容

上图可知，并不是每个 entry 都完整保存了 key 的全部内容，大部分 entry 只存了部分 key，以及和前一个公共 key 部分的长度。

当拥有公共部分 key 的 entry 过多的时候，会影响查找效率，所以每隔几段 entry 会重新完整记录当前 entry 的完整 key，这个完整的 entry 所在位置就被称为 restart point。

具体案例如图所示

这个 block 中保存了这几个 kv：

• key=deck, value=v1
• key=dock, value=v2
• key=duck, value=v3

block 尾部记录了 restart point 信息

index block

index block 相对比较简单，内部有若干 entry，分别记录了对应的每个 data block 的大 key，offset 和长度，便于读取 sst 时快速 key 定位

filter block

filter block 的作用为快速判断一个 key 是否可能在当前 sst 内，为什么说可能呢？filter block 是由布隆过滤器实现，布隆过滤器有以下特性：

• 用来快速判断集合中是否包含某个元素
• 如果过滤器报告不存在，则一定不存在
• 如果报告存在，则可能存在

如果 filter block 中没发现 key，那么 key 一定不在当前 sst，否则就有可能在，需要进一步去 index block 查找

写入磁盘

了解了磁盘结构之后，我们可以来看一下 LevelDB 究竟是怎么把 Immutable MemTable 持久化成 sst 了

• 写入 Immutable MemTable 之后开启 minor compact，写入 L0 层，并开启异步删 log
• 便利 skiplist 过程中发现删除标记的 key，则直接跳过
• 如果 L0 文件超过 4 个，触发 major compact（异步）
• major compact 从当前层选出一块 sst 合并到下一层，如果下一层满了，则重复执行操作，直到写入后一层

Log：大 4MB (可配置), 会写入 Level 0；

Level 0：多 4 个 SST 文件；

Level 1：总大小不超过 10MB；

Level 2：总大小不超过 100MB；

Level 3+：总大小不超过上一个 Level ×10 的大小

比如：0 ↠ 4 SST, 1 ↠ 10M, 2 ↠ 100M, 3 ↠ 1G, 4 ↠ 10G, 5 ↠ 100G, 6 ↠ 1T, 7 ↠ 10T

读取操作

读取操作相比写入要简单一点，过程如下

• 读 MemTable 和 Immutable MemTable，如果找到则返回
• 读 cache（如果有），找到则返回
• 读 manifest，大致找到 key 在哪一层
• 遍历每一层的 sst，读 filter block、index block，判断是否存在当前 sst 中，如果找到则返回，否则读下一层
• 如果遍历到后一层也没有，那就真没有了

总结

LevelDB 是单机版的 big table 实现，上层套个 redis 的网络层就可以实现一个兼容 redis 协议的混合存储数据库，如 360 的 SSDB。Facebook 基于 LevelDB 的修改版 RocksDB 被用在了 TiKV 的元数据存储上。理解 LevelDB 对理解其他基于 big table 的分布式存储方案有很大的帮助

参考资料