LevelDb跳表实现

简介: LevelDb跳表实现

引言


跳表对于LSM-Tree存储结构的key/value数据库来说使用还是比较多的,除开本节的LevelDB之外,还有HBase等等。

在之前讨论合并压缩文件使用了归并排序的方式进行键合并,而内部的数据库除了归并排序之外还使用了比较关键的skiplist 跳表进行有序键值管理,在了解LevelDB跳表的细节之前,需要先了解跳表这个数据结构的基本概念。

跳表在Redis和Kafka中都有实现,这里的skiplist其实也是类似的,可以看作C++版本的一个跳表实现样板。

跳表的数据结构这里就略过了,可以直接参考个人之前写的文章,这篇文章直接源码开干.

# 数据结构之跳表理解


基础结构


首先我们需要清楚LevelDB的跳表包含了什么东西?在代码的一开始定义了 Node节点用来表示链表节点,以及 Iterator迭代器的内容进行迭代,内部定义了std::atomic<Node*> next_[1] 长度等于节点高度的数组。 next_[0]是最底层别的节点(用于跳表跨层获取数据),以及一个作者自认为写的一般并且非常简单的Random随机器(通过位操作生成随机的一个位号码)。

LevelDB的整个实现还是十分简洁规范的,所有的代码都可以在skiplist.h找到,在设计上定义了很多函数来简化复杂代码的增加,算是非常易懂的代码了。


重要方法



在了解过跳表之后,我们发现对于跳表这种数据结构来说,核心部分在于查询和插入两个部分,当然查询是理解插入点前提,但是对于插入抛硬币选举的实现有必要深究一下。

在源代码中跳表称为skiplist,后续不再赘述这个概念。


查询操作


SkipList查询操作比较好理解,可以发现和跳表原始的实现方式如出一辙:

  1. 从索引的最高层进行查找,直接找到下一个节点。
  2. 如果当前内容大于节点内容,则直接找下一个节点比较。
  3. 如果当前节点等于查找节点则直接返回。
  4. 如果当前节点大于节点,并且下一个节点大于当前节点,并且层高不为0,则继续往层高更低的一个层级节点查找同时回到更低层级前一个节点,如果层高为0,则返回当前节点,当前节点的key要大于查找的key。


// 返回层级最前的节点,该节点位于键的位置或之后。如果没有这样的节点,返回nullptr。如果prev不是空的,则在[0...max_height_1]中的每一级,将prev[level]的指针填充到前一个 节点的指针来填充[0...max_height_1]中的每一级的 "level"。
template <typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node*
SkipList<Key, Comparator>::FindGreaterOrEqual(const Key& key,
Node** prev) const {
  Node* x = head_;
  // 防止无限for循环
  int level = GetMaxHeight() - 1;
  while (true) {
    Node* next = x->Next(level);
    if (KeyIsAfterNode(key, next)) {
      // 如果当前节点在层级之后,则查找下一个链表节点
      x = next;
    } else {
      if (prev != nullptr) prev[level] = x;
      if (level == 0) {
        return next;
      } else {
        // 层级下沉
        level--;
      }
    }
  }
}


插入操作


插入操作的代码如下:

注意跳表需要在插入之前对于节点进行加锁的操作。


template <typename Key, class Comparator>
void SkipList<Key, Comparator>::Insert(const Key& key) {
  // 因为前置节点最多有kMaxHeight层,所以直接使用kMaxHeight 简单粗暴
  Node* prev[kMaxHeight];
  // 返回层级最前的节点,该节点位于键的位置或之后。如果没有这样的节点,返回nullptr。如果prev不是空的,则在[0...max_height_1]中的每一级,将prev[level]的指针填充到前一个 节点的指针来填充[0...max_height_1]中的每一级的 "level"。
  Node* x = FindGreaterOrEqual(key, prev);
  // 不允许进行重复插入操作(同步加锁)
  assert(x == nullptr || !Equal(key, x->key));
  // **新增层级选举**,使用随机函数和最高层级限制,按照类似抛硬币的规则选择是否新增层级。
  // 随机获取一个 level 值
  int height = RandomHeight();
  // 当前随机level是否大于 当前点跳表层数
  if (height > GetMaxHeight()) {
    // 头指针下探到最低层
    for (int i = GetMaxHeight(); i < height; i++) {
      prev[i] = head_;
    }
    /*
    这部分建议多读读原注释。
    机器翻译:在没有任何同步的情况下突变max_height_是可以的。与并发读取器之间没有任何同步。一个并发的读者在观察到的新值的并发读者将看到max_height_的旧值。的新水平指针(nullptr),或者在下面的循环中设置一个新的值。下面的循环中设置的新值。在前一种情况下,读者将立即下降到下一个级别,因为nullptr会在所有的键之后。在后一种情况下,读取器将使用新的节点
    理解:意思是说这一步不需要并发加锁,这是因为并发读读取到更新的跳表层数,哪怕现在这个节点没有插入,也会返回nullptr,在leveldb的比较器当中的nullpt会在最前面,默认看作比所有的key都要大,所以会往下继续找,这样就可以保证写入和读取都是符合预期的。
    */
    max_height_.store(height, std::memory_order_relaxed);
  }
  // 新增跳表节点
  x = NewNode(key, height);
  for (int i = 0; i < height; i++) {
  // NoBarrier_SetNext()就够了,因为当我们在prev[i]中发布一个指针 "x "时,我们会添加一个障碍。我们在prev[i]中发布一个指向 "x "的指针。
    // 更新指针引用
    // 为了保证并发读的准确性,需要先设置节点指针然后再设置原始表的prev 指针
    x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
    // 内部会强制进行同步
    prev[i]->SetNext(i, x);
  }
}


对于level插入操作来说,跳表实现的难点在于层数的确定,而节点插入的难点在于如何保证并发写入的时候能够正确的并发读。

RandomHeight() 新增层级选举

观察跳表插入数据当中的非常重要的层级选举,在LevelDb中层级选举的核心的代码是:height < kMaxHeight && rnd_.OneIn(kBranching),这里逻辑非常简单,在控制跳表层数最多不超过kMaxHeight层的情况下对于4取余的操作实现构造 P = 3/4 的几何分布,最终判断是否新增层数。

原始情况下跳表增加1层为 1/2,2层为1/4,3层为1/8,4层为1/16。LevelDB的11层最高层限制key的数量,但是11层的节点概率通常会非常非常小。 最终LevelDB选择的结果是3/4 的节点为 1 层节点,3/16 的节点为 2 层节点,3/64 的节点为 3 层节点,依次类推。

所以我们可以结一下层级选举的特点:

  1. 插入新节点的指针数通过独立的计算一个概率值决定,使全局节点的指针数满足几何分布即可。
  2. 插入时不需要做额外的节点调整,只需要先找到其需要放的位置,然后修改他和前驱的指向即可。


template <typename Key, class Comparator>
int SkipList<Key, Comparator>::RandomHeight() {
  // 在kBranching中以1的概率增加高度
  static const unsigned int kBranching = 4;
  int height = 1;
  // rnd_.OneIn(kBranching):"1/n "的时间会返回真没其他情况会返回假
  // 相当于层数会按照4 的倍数减小, 4层是3层的4分之一,简单理解为 每次加一层概率就要乘一个 1/4。
  while (height < kMaxHeight && rnd_.OneIn(kBranching)) {
    height++;
  }
  assert(height > 0);
  assert(height <= kMaxHeight);
  return height;
}


从上面的代码可以看到概率P使用了1/4计算方式,使用1/4的好处是让层数更为分散,典型的时间换空间的操作,虽然会牺牲查询的效率,但是获得更小的内存占用,在此情况下,可以最多支持 n = (1/p)^kMaxHeight 个节点的情况

那么如果一个跳表的节点到了12层会怎么样?那么可以直接使用4^12 计算约等于 16M。当然12层的概率微乎其微


删除操作


LevelDB跳表是没有删除这个概念的,相对应的更新也是针对next指针的变动。

  1. 除非跳表被销毁,跳表节点只会增加而不会被删除,因为跳表对外根本不提供删除接口。
  2. 被插入到跳表中的节点,除了 next 指针其他域都是不可变的,并且只有插入操作会改变跳表。(以此来替代更新)


遍历操作


之前的源码分析解释过整个跳表的遍历通过Iterator完成,内部使用了归并排序对于key进行排序,同时nullptr作为特殊值永远排在最前面。

LevelDB的迭代器实现较为丰富,除开迭代器经典的remove(),next()、haseNext()之外,还有Seek,SeekToFirst,SeekToLast、以及Prev向前遍历的操作


// Advances to the next position.
// REQUIRES: Valid()
void Next();
// Advances to the previous position.
// REQUIRES: Valid()
void Prev();
// Advance to the first entry with a key >= target
void Seek(const Key& target);
// Position at the first entry in list.
// Final state of iterator is Valid() iff list is not empty.
void SeekToFirst();
// Position at the last entry in list.
// Final state of iterator is Valid() iff list is not empty.
void SeekToLast();


这里需要特意强调的是向前遍历这个操作并不是通过增加prev指针反向迭代的,而是从head开始查找,也是时间换空间,当然是向遍历开销比较小的情况。

最后有两个比较频繁的使用操作FindLastFindLessThan,注释写的简单明了,就不多介绍了。


// Return the latest node with a key < key.
// Return head_ if there is no such node.
Node* FindLessThan(const Key& key) const;
// Return the last node in the list.
// Return head_ if list is empty.
Node* FindLast() const;


总结


LevelDB的跳表设计难点主要体现在并发读写的维持以及节点的层级选举上面,这一部分是和原始的跳表差别比较大的地方,而其他地方基本可以看作找着跳表的特点进行设计的,所以把 LevelDB作为跳表的模板代码学习也是十分推荐的。

相关文章
|
存储 JSON NoSQL
Node.js使用数据库LevelDB:超高性能kv存储引擎
Node.js被设计用来做快速高效的网络I/O。它的事件驱动流使其成为一种智能代理的理想选择,通常作为后端系统和前端之间的粘合剂。Node的设计初衷就是为了实现这一目的,但与此同时,它已成功用于构建传统的Web应用程序:一个HTTP服务器,提供为HTML页面或JSON消息响应,并使用数据库存储数据。
808 0
Node.js使用数据库LevelDB:超高性能kv存储引擎
|
7月前
|
NoSQL Redis 数据库
LSM-Tree - LevelDb Skiplist跳表
LSM-Tree - LevelDb Skiplist跳表
83 0
|
7月前
|
消息中间件 存储 NoSQL
LevelDb跳表实现
LevelDb跳表实现
50 0
|
7月前
|
NoSQL Redis 数据库
LSM-Tree - LevelDb Skiplist跳表
LSM-Tree - LevelDb Skiplist跳表
59 0
LSM-Tree - LevelDb Skiplist跳表
|
NoSQL 算法 分布式数据库
LSM-Tree - LevelDb Skiplist跳表(上)
LSM-Tree - LevelDb Skiplist跳表(上)
297 0
|
消息中间件 存储 NoSQL
LSM-Tree - LevelDb Skiplist跳表(下)
LSM-Tree - LevelDb Skiplist跳表(下)
286 0
|
Web App开发 存储 算法
|
16天前
|
SQL 关系型数据库 MySQL
12 PHP配置数据库MySQL
路老师分享了PHP操作MySQL数据库的方法,包括安装并连接MySQL服务器、选择数据库、执行SQL语句(如插入、更新、删除和查询),以及将结果集返回到数组。通过具体示例代码,详细介绍了每一步的操作流程,帮助读者快速入门PHP与MySQL的交互。
30 1
|
18天前
|
SQL 关系型数据库 MySQL
go语言数据库中mysql驱动安装
【11月更文挑战第2天】
31 4
|
25天前
|
监控 关系型数据库 MySQL
数据库优化:MySQL索引策略与查询性能调优实战
【10月更文挑战第27天】本文深入探讨了MySQL的索引策略和查询性能调优技巧。通过介绍B-Tree索引、哈希索引和全文索引等不同类型,以及如何创建和维护索引,结合实战案例分析查询执行计划,帮助读者掌握提升查询性能的方法。定期优化索引和调整查询语句是提高数据库性能的关键。
135 1
下一篇
无影云桌面