LevelDB 完全解析（1）：MemTable
LevelDB 完全解析（1）：MemTable
前文回顾
MemTable 介绍
MemTable，顾名思议，就是内存表。每个 LevelDB 实例最多会维护两个 MemTable： mem_ 和 imm_。mem_ 可以读写，imm_ 只读。
在 LevelDB 中，最新写入的数据都会保存到 mem_ 中。当 mem_ 的大小超过 write_buffer_size 时，LevelDB 就会将其切换成 imm_，并生成新的 mem_。
LevelDB 的后台线程会将 imm_ compact 成 SSTable 保存在磁盘上。
如果前台的写入速度很快，有可能出现 mem_ 的大小已经超过 write_buffer_size，但是前一个 imm_ 还没有被 compact 到磁盘上，无法切换 MemTable，此时就会出现 stall write（阻塞写请求）。
leveldb::MemTable 主要支持的操作有：
- 插入单条记录：Add。
- 查询单条记录：Get。
- 遍历（范围查询）：MemTableIterator。
LevelDB 的 MemTable 的主要功能是将内部编码、内存分配（Arena）和 SkipList 封装在一起。
MemTable 的内部编码
MemTable 中保存的数据是 key 和 value 编码成的一个字符串，由四个部分组成：
- klength: 变长的 32 位整数（varint 的编码），表示 internal key 的长度。
- internal key: 长度为 klength 的字符串。
- vlength: 变长的 32 位整数，表示 value 的长度。
- value: 长度为 vlength 的字符串。因为 value 没有参与排序，所以相关的讨论暂时可以忽略。
MemTable 的 KeyComparator 负责从 memkey 中提取出 internalkey，最终排序逻辑是使用 InternalKeyComparator 进行比较，排序规则如下：
- 优先按照 user key 进行排序。
- User key 相同的按照 seq 降序排序。
- User key 和 seq 相同的按照 type 降序排序（逻辑上不会达到这一步，因为一个 LevelDB 的 sequence 是单调递增的）。
所以，在一个 MemTable 中，相同的 user key 的多个版本，新的排在前面，旧的排在后面。
MemTable 的内存分配
MemTable 通过 Arena 进行内存分配和使用统计。Arena 其实就是一个简化的内存池。它只提供分配内存的接口，不提供释放内存的接口。只有当整个 Arena 对象销毁的时候才会将之前申请的内存释放掉。
Arena 提供了两个内存分配接口：
一般情况下，Allocate 每次从操作系统申请一块大小为 kBlockSize 的内存，默认是 4KB。之后，在 block 剩余内存足够的情况下，内存申请都可以直接从这个 block 划一部分出去（参考代码）。如果 block 剩余的内存不够，并且申请的内存大于 kBlockSize / 4，则直接 new 一块内存给这个请求（参考代码），避免造成太多的内部碎片。否则，就直接再申请一个 block，并从这个 block 划分一部分（参考代码）。
因为 SkipList 中会涉及一些原子操作，所以 AllocateAligned 分配的内存需要和指针的大小（一般是 8 字节）对齐。其他逻辑和 Allocate 一样。
Skip List
Skip List 简介
skip list
图片来自 skip list 的维基百科
1990 年，William Pugh 发表了 skip list 的论文：Skip Lists: A Probabilistic Alternative to
Skip list 是一种可以用于替代查找树的内存数据结构，其基本原理是在一个有序的链表之上增加一些索引，通过一个随机规则（保证一定概率）来“模拟”二分查找。
直观上可以将整个 skip list 看成是一条地铁线。每个节点就是一个地铁站，比如上图的 1~10。假设 (1) 是始发站，(NIL) 是终点站。这条地铁线有多种快车、慢车的线路，每个条线路经停的地铁站都不一样。比如上图就有四种不同线路（用向右的箭头表示），从上往下：
线路1：只停始发站(1) 和终点站(NIL)
线路2：始发站(1) => (4) => (6) => 终点站(NIL)
线路3：始发站(1) => (3) => (4) => (6) => (9) =>终点站(NIL)
线路4：每一站都停。
注意，skip list 这里的主要成本是经过的站点数量，而在某个站点进行转线的成本是零。我们可以合理转换不同线路来减少经过的站点数量。假如我们要去地铁站(9)，可以先坐线路 2 到地铁站(6)，再转线路 3 到地铁站(9)：经过的站点有 (1)、(4)、(6)、(9)。
Skip List 原理
image
Skip list 的基础是一个有序的链表。但是因为链表在内存中是离散存储的，我们无法在一个有序链表上执行二分查找。
image
所以，我们决定在这个有序的链表上增加一层索引，用于将这个有序链表一分为二。通过第一层索引可以将查找量减少一半。
image
同理，我们可以对左边的链表(1->2->3->4) 建一层索引，将左边一分为二。对右边的链表(6->7->8->9->10)也可以进行一样的操作。如此递归下去……
这样通过付出一些指针的开销，可以将有序链表的查找时间复杂度从 O(n) 降低到和二分查找一样的 O(logn)。
如果每次都要“精准地一分为二”，插入、删除某个节点的时候会可能会涉及到调整其它节点的指针索引高度。这会让逻辑变得复杂许多，就像红黑树插入、删除节点可能会涉及子树的“旋转”一样。
Skip list 放弃了精确控制每个节点的索引高度来实现“二分查找”，转而采用一个随机概率规则来确定一个节点的高度。这样，一个节点的插入和删除，只会和它的相邻节点有关，逻辑简单，并且修改范围非常有限（锁粒度可以做到很细），可以实现更高的并发。
要实现随机近似二分查找，我们需要保证一个高度为 h 的节点，有 1/2 的概率是高度为 h+1 的节点 ：
- 高度 >= 1 的节点概率为 1。
- 高度 >= 2 的节点概率为 1/2。
- 高度 >= 3 的节点概率为 1/4。
- ...
- 高度 >= h 的节点概率为 1 / 2^(h-1)。
更通用一点，假设一个高度为 h 的节点，有概率 p 是高度为 h+1 的节点。那么一个长度为 n 的 skip list，需要的指针数量为：N = p^0 * n + p^1 * n + p^2 * n + ... = n * (p^0 + p^1 + p^2 + ....) = n*(1-p^n) / (1 - p) 因为 p < 1，当 n 趋近无穷的时候，p^n 趋近于 0，因此 N = n/(1-p)。Skip list 的空间复杂度是 O(n)。
如果我们想节省内存空间，可以适当的调低 1/2 这个概率，比如 1/3、1/4，从而减少索引指针个数。
LevelDB 的 SkipList 实现
LevelDB 的 SkipList 支持无锁的一写多读，并且只支持查找和插入。LevelDB 通过维护一个写队列来保证同一时刻只有一个线程会写 MemTable。
根据 RandomHeight 的实现，LevelDB 将上面分析的每个元素高度增长的概率设置为 1/4 ，以节省内存。
template <typename Key, class Comparator>
int SkipList<Key, Comparator>::RandomHeight() {
// Increase height with probability 1 in kBranching
static const unsigned int kBranching = 4;
int height = 1;
while (height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)) {
height++;
}
assert(height > 0);
assert(height <= kMaxHeight);
return height;
}FindGreaterOrEqual 查找并返回第一个大于等于 key 的节点。如果是查找后需要进行插入，需要记录下这个节点的 prev 指针。
template <typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node*
SkipList<Key, Comparator>::FindGreaterOrEqual(const Key& key,
Node** prev) const {
Node* x = head_;
int level = GetMaxHeight() - 1;
while (true) {
Node* next = x->Next(level);
if (KeyIsAfterNode(key, next)) {
// Keep searching in this list
x = next;
} else {
if (prev != nullptr) prev[level] = x;
if (level == 0) {
return next;
} else {
// Switch to next list
level--;
}
}
}
}FindLessThan 查找并返回最后一个小于 key 的节点。
FindLast 查找并返回最后一个节点。
Contains 查找 SkipList 是否包含某个 key。
Insert 插入一个 key。前面说了，LevelDB 保证这里同一时刻只会有一个线程在写入，并通过原子地修改指针（SetNext）来保证不影响并发执行的读请求。
template <typename Key, class Comparator>
void SkipList<Key, Comparator>::Insert(const Key& key) {
// TODO(opt): We can use a barrier-free variant of FindGreaterOrEqual()
// here since Insert() is externally synchronized.
Node* prev[kMaxHeight];
Node* x = FindGreaterOrEqual(key, prev);
// Our data structure does not allow duplicate insertion
assert(x == nullptr || !Equal(key, x->key));
int height = RandomHeight();
if (height > GetMaxHeight()) {
for (int i = GetMaxHeight(); i < height; i++) {
prev[i] = head_;
}
// It is ok to mutate max_height_ without any synchronization
// with concurrent readers. A concurrent reader that observes
// the new value of max_height_ will see either the old value of
// new level pointers from head_ (nullptr), or a new value set in
// the loop below. In the former case the reader will
// immediately drop to the next level since nullptr sorts after all
// keys. In the latter case the reader will use the new node.
max_height_.store(height, std::memory_order_relaxed);
}
x = NewNode(key, height);
for (int i = 0; i < height; i++) {
// NoBarrier_SetNext() suffices since we will add a barrier when
// we publish a pointer to "x" in prev[i].
x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
prev[i]->SetNext(i, x);
}
} void SetNext(int n, Node* x) {
assert(n >= 0);
// Use a 'release store' so that anybody who reads through this
// pointer observes a fully initialized version of the inserted node.
next_[n].store(x, std::memory_order_release);
}