leveldb 源码分析 1¶

本系列《leveldb 源码分析》共有 22 篇文章，这是第一篇。

leveldb，除去测试部分，代码不超过 1.5w 行。这是一个单机 k/v 存储系统，决定看完它，并把源码分析完整的写下来，还是会很有帮助的。我比较厌烦太复杂的东西，而 Leveldb 的逻辑很清晰，代码不多、风格很好，功能就不用讲了，正合我的胃口。 BTW，分析 Leveldb 也参考了网上一些朋友写的分析 blog，如【巴山独钓】。

leveldb 源码分析¶

2012 年 1 月 21 号开始研究下 leveldb 的代码，Google 两位大牛开发的单机 KV 存储系统，涉及到了 skip list、内存 KV table、LRU cache 管理、table 文件存储、operation log 系统等。先从边边角角的小角色开始扫。

不得不说，Google 大牛的代码风格太好了，读起来很舒服，不像有些开源项目，很快就看不下去了。

开始之前先来看看 Leveldb 的基本框架，几大关键组件，如图 1-1 所示。

图 1-1

leveldb 是一种 基于 operation log 的文件系统，是 Log-Structured-Merge Tree 的典型实现。LSM 源自 Ousterhout 和 Rosenblum 在 1991 年发表的经典论文<<The Design and Implementation of a Log-Structured File System >>。

由于 采用了 op log，它就可以把随机的磁盘写操作，变成了对 op log 的 append 操作，因此提高了 IO 效率，最新的数据则存储在内存 memtable 中。

当 op log 文件 大小超过限定值时，就定时做 check point。Leveldb 会生成新的 Log 文件和 Memtable，后台调度会将 Immutable Memtable 的数据导出到磁盘，形成一个新的 SSTable 文件。SSTable 就是由内存中的数据不断导出并进行 Compaction 操作 后形成的，而且 SSTable 的所有文件是一种层级结构，第一层为 Level 0，第二层为 Level 1，依次类推，层级逐渐增高，这也是为何称之为 LevelDb 的原因。

1. 一些约定¶

先说下代码中的一些约定：

1.1 字节序¶

Leveldb对于数字的存储是 little-endian 的，在把 int32 或者 int64 转换为 char* 的函数中，是按照先低位再高位的顺序存放的，也就是 little-endian 的。

1.2 VarInt¶

把一个 int32 或者 int64 格式化到字符串中，除了上面说的 little-endian 字节序外，大部分还是变长存储的，也就是 VarInt。对于 VarInt，每 byte 的有效存储是 7bit 的，用最高的 8bit 位来表示是否结束，如果是 1 就表示后面还有一个 byte 的数字，否则表示结束。直接见 Encode 和 Decode 函数。

在操作 log 中使用的是 Fixed 存储格式。

1.3 字符比较¶

是基于 unsigned char 的，而非 char。

2. 基本数据结构¶

别看是基本数据结构，有些也不是那么简单的，像 LRU Cache 管理和 Skip list 那都算是 leveldb 的核心数据结构。

2.1 Slice¶

Leveldb 中的基本数据结构：

包括 length 和一个指向外部字节数组的指针。
和 string 一样，允许字符串中包含’\0’。

提供一些基本接口，可以把 const char 和 string 转换为 Slice；把 Slice 转换为 string，取得数据指针 const char。

2.2 Status¶

Leveldb 中的 返回状态，将错误号和错误信息封装成 Status 类，统一进行处理。并定义了几种具体的返回状态，如成功或者文件不存在等。

为了节省空间 Status 并没有用 std::string 来 存储错误信息，而是将返回码 (code), 错误信息 message 及长度打包存储于一个字符串数组中。

成功状态 OK 是 NULL state_，否则 state_ 是一个包含如下信息的数组:

state_[0..3] == 消息message长度 

state_[4]    == 消息code

state_[5..]  ==消息message

2.3 Arena¶

Leveldb 的简单的内存池，它所作的工作十分简单，申请内存时，将申请到的内存块放入 std::vector blocks_ 中，在 Arena 的生命周期结束后，统一释放掉所有申请到的内存，内部结构如图 2.3-1 所示。

Arena 主要提供了两个申请函数：其中一个直接分配内存，另一个可以申请对齐的内存空间。

Arena 没有直接调用 delete/free 函数，而是由 Arena 的析构函数统一释放所有的内存。

应该说这是和 leveldb 特定的应用场景相关的，比如一个 memtable 使用一个 Arena，当 memtable 被释放时，由 Arena 统一释放其内存。

2.4 Skip list¶

Skip list(跳跃表）是一种可以代替平衡树的数据结构。Skip lists 应用概率保证平衡，平衡树采用严格的旋转（比如平衡二叉树有左旋右旋）来保证平衡，因此 Skip list 比较容易实现，而且相比平衡树有着较高的运行效率。

从概率上保持数据结构的平衡比显式的保持数据结构平衡要简单的多。对于大多数应用，用 skip list 要比用树更自然，算法也会相对简单。由于 skip list 比较简单，实现起来会比较容易，虽然和平衡树有着相同的时间复杂度 (O(logn))，但是 skip list 的常数项相对小很多。skip list 在空间上也比较节省。一个节点平均只需要 1.333 个指针（甚至更少），并且不需要存储保持平衡的变量。

如图 2.4-1 所示。

在 Leveldb 中，skip list 是实现 memtable 的核心数据结构，memtable 的 KV 数据都存储在 skip list 中。

2.5 Cache¶

Leveldb 内部通过双向链表实现了一个标准版的 LRUCache，先上个示意图，看看几个数据之间的关系，如图 2.5-1。

Leveldb 实现 LRUCache 的几个步骤¶

接下来说说 Leveldb 实现 LRUCache 的几个步骤，很直观明了。

S1¶

定义一个 LRUHandle 结构体，代表 cache 中的元素。它包含了几个主要的成员：

void* value;

这个存储的是 cache 的数据；

void (*deleter)(const Slice&, void* value);

这个是数据从 Cache 中清除时执行的清理函数；

后面的三个成员事关 LRUCache 的数据的组织结构：

> LRUHandle *next_hash;

指向节点在 hash table 链表中的下一个 hash(key) 相同的元素，在有碰撞时 Leveldb 采用的是链表法。最后一个节点的 next_hash 为 NULL。

> LRUHandle *next, *prev;

节点在双向链表中的前驱后继节点指针，所有的 cache 数据都是存储在一个双向 list 中，最前面的是最新加入的，每次新加入的位置都是 head->next。所以 每次剔除的规则就是剔除 list tail。

S2¶

Leveldb 自己实现了一个 hash table：HandleTable，而不是使用系统提供的 hash table。这个类就是基本的 hash 操作：Lookup、Insert 和 Delete。

Hash table 的作用是根据 key 快速查找元素是否在 cache 中，并返回 LRUHandle 节点指针，由此就能快速定位节点在 hash 表和双向链表中的位置。

它是通过 LRUHandle 的成员 next_hash 组织起来的。

HandleTable 使用 LRUHandle list_ 存储所有的 hash 节点，其实就是一个二维数组，**一维是不同的 hash(key)，另一维则是相同 hash(key) 的碰撞 list。

每次当 hash 节点数超过当前一维数组的长度后，都会做 Resize 操作：

LRUHandle** new_list = new LRUHandle*[new_length];

然后复制 list_ 到 new_list 中，并删除旧的 list_。

S3¶

基于 HandleTable 和 LRUHandle，实现了一个标准的 LRUcache，并内置了 mutex 保护锁，是线程安全的。

其中存储所有数据的双向链表是 LRUHandle lru_，这是一个 list head；

Hash 表则是 HandleTable table_；

S4¶

ShardedLRUCache 类，实际上到 S3，一个标准的 LRU Cache 已经实现了，为何还要更近一步呢？答案就是速度！

为了多线程访问，尽可能快速，减少锁开销，ShardedLRUCache 内部有 16 个 LRUCache，查找 Key 时首先计算 key 属于哪一个分片，分片的计算方法 是取 32 位 hash 值的高 4 位，然后在相应的 LRUCache 中进行查找，这样就大大减少了多线程的访问锁的开销。

LRUCache shard_[kNumShards]

它就是一个包装类，实现都在 LRUCache 类中。

2.6 其它¶

此外还有其它几个 Random、Hash、CRC32、Histogram 等，都在 util 文件夹下，不仔细分析了。