前文回顾
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 中保存的数据是 key 和 value 编码成的一个字符串,由四个部分组成:
MemTable 的 KeyComparator 负责从 memkey 中提取出 internalkey,最终排序逻辑是使用 InternalKeyComparator 进行比较,排序规则如下:
所以,在一个 MemTable 中,相同的 user key 的多个版本,新的排在前面,旧的排在后面。
MemTable 通过 Arena 进行内存分配和使用统计。Arena 其实就是一个简化的内存池。它只提供分配内存的接口,不提供释放内存的接口。只有当整个 Arena 对象销毁的时候才会将之前申请的内存释放掉。 Arena 提供了两个内存分配接口:
一般情况下,Allocate 每次从操作系统申请一块大小为 kBlockSize 的内存,默认是 4KB。之后,在 block 剩余内存足够的情况下,内存申请都可以直接从这个 block 划一部分出去(参考代码)。如果 block 剩余的内存不够,并且申请的内存大于 kBlockSize / 4,则直接 new 一块内存给这个请求(参考代码),避免造成太多的内部碎片。否则,就直接再申请一个 block,并从这个 block 划分一部分(参考代码)。
因为 SkipList 中会涉及一些原子操作,所以 AllocateAligned 分配的内存需要和指针的大小(一般是 8 字节)对齐。其他逻辑和 Allocate 一样。
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)。
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 的节点 :
更通用一点,假设一个高度为 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 通过维护一个写队列来保证同一时刻只有一个线程会写 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); }
本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。
我来说两句