前文回顾

• LevelDB 完全解析（0）：基本原理和整体架构

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 编码成的一个字符串，由四个部分组成：

1. klength: 变长的 32 位整数（varint 的编码），表示 internal key 的长度。
2. internal key: 长度为 klength 的字符串。
3. vlength: 变长的 32 位整数，表示 value 的长度。
4. value: 长度为 vlength 的字符串。因为 value 没有参与排序，所以相关的讨论暂时可以忽略。

MemTable 的 KeyComparator 负责从 memkey 中提取出 internalkey，最终排序逻辑是使用 InternalKeyComparator 进行比较，排序规则如下：

1. 优先按照 user key 进行排序。
2. User key 相同的按照 seq 降序排序。
3. User key 和 seq 相同的按照 type 降序排序（逻辑上不会达到这一步，因为一个 LevelDB 的 sequence 是单调递增的）。

所以，在一个 MemTable 中，相同的 user key 的多个版本，新的排在前面，旧的排在后面。

MemTable 的内存分配

MemTable 通过 Arena 进行内存分配和使用统计。Arena 其实就是一个简化的内存池。它只提供分配内存的接口，不提供释放内存的接口。只有当整个 Arena 对象销毁的时候才会将之前申请的内存释放掉。 Arena 提供了两个内存分配接口：

1. Allocate(size_t bytes)
2. AllocateAligned(size_t bytes)

一般情况下，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 Balanced Trees。

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 的节点概率为 1。
2. 高度 >= 2 的节点概率为 1/2。
3. 高度 >= 3 的节点概率为 1/4。
4. ...
5. 高度 >= 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)<br />因为 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);
  }