专栏首页linjinhe的专栏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 主要支持的操作有:

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);
  }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LevelDB:整体架构

    上图简单展示了 LevelDB 的整体架构。LevelDB 的静态结构主要由六个部分组成:

    linjinhe
  • Linux常用命令:free

    linjinhe
  • LevelDB 完全解析(3):SSTable

    SSTable 全称 Sorted String Table,顾名思义,里面的 key-value 都是有序保存的。除了两个 MemTable,LevelDB ...

    linjinhe
  • Angular里useExisting和useClass的使用场景

    StackOverflow上的一个帖子:https://stackoverflow.com/questions/45152995/useclass-vs-use...

    Jerry Wang
  • 如何打造一款高质量的Android移动应用

    顾翔老师开发的bugreport2script开源了,希望大家多提建议。文件在https://github.com/xianggu625/bug2testscr...

    小老鼠
  • 过度设计的问题

    前几天碰到了一个严重的硬件问题导致服务受到影响,我在总结思考的时候,脑袋里冒出了一个观点:过度设计。

    jeanron100
  • RunTime 之其他实践运用

    有关Runtime的知识总结,我本来想集中写成一篇文章的,但是最后发现实在是太长,而且不利于阅读,最后分成了如下几篇:

    進无尽
  • 打击换脸技术滥用,谷歌发布大型数据集对抗deepfake

    deepfake 出现以来引发了大量争议,也带来了诸多伦理和社会问题。最近,Facebook、微软等巨头已开始着手打击 deepfake 滥用,斥资 1000 ...

    机器之心
  • Win10下Docker容器开发调试EasySwoole

    北溟有鱼QAQ
  • iOS Runtime面试题(一个objc对象的isa的指针指向什么?有什么作用?)

    1.Root class (class)其实就是NSObject,NSObject是没有超类的,所以Root class(class)的superclass指向...

    iOSSir

扫码关注云+社区

领取腾讯云代金券