跳表

跳表是一种可以取代平衡树的数据结构
跳表使用概率均衡而非严格均衡策略，从而相对于平衡树，大大简化和加速了元素的插入和删除

跳表的结构

最底下一层都包含完整的数据，从第二层开始，节点的高度是随机产生的
越往上的节点，其出现的概率越低

  • 作者从链表讲起，一步步引出了跳表这种结构的由来。
  • 图a中，所有元素按序排列，被存储在一个链表中，则一次查询之多需要比较N个链表节点；
  • 图b中，每隔2个链表节点，新增一个额外的指针，该指针指向间距为2的下一个节点，如此以来，借助这些额外的指针，一次查询至多只需要⌈n/2⌉ + 1次比较；
  • 图c中，在图b的基础上，每隔4个链表节点，新增一个额外的指针，指向间距为4的下一个节点，一次查询至多需要⌈n/4⌉ + 2次比较；
  • 作者推论，若每隔2^ i个节点，新增一个辅助指针，最终一次节点的查询效率为O(log n)。但是这样不断地新增指针，使得一次插入、删除操作将会变得非常复杂。
  • 一个拥有k个指针的结点称为一个k层结点（level k node）。按照上面的逻辑，50%的结点为1层节点，25%的结点为2层节点，12.5%的结点为3层节点。若保证每层节点的分布如上述概率所示，则仍然能够相同的查询效率。图e便是一个示例。

查找和插入

查找 12

  • 通过头结点，找到 6，再后面是null，所以 6 下降一层
  • 6下降一层，下一个节点时 25，大于 12，6这个节点再下降一层
  • 6的下一个是9,9的下一个是25，所以 9这个节点再下降一层
  • 9的 下一个是12，找到

插入17

  • 首先要定位到 17 的前面一个，这个过程跟上面的一样
  • 再将 17放到 12后面

LevelDB 的 插入实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

template <typename Key, class Comparator>
void SkipList<Key, Comparator>::Insert(const Key& key) {
  // 这里的 kMaxHeight 固定为 12，最大高度
  // 然后找到前一个节点
  Node* prev[kMaxHeight];
  Node* x = FindGreaterOrEqual(key, prev);
  assert(x == nullptr || !Equal(key, x->key));
  // 随机产生一个高度
  int height = RandomHeight();
  // 如果这个高度 > skip-list的当前高度，则多出来的那部分，其 next 指向 head_.next
  // 再保存
  if (height > GetMaxHeight()) {
    for (int i = GetMaxHeight(); i < height; i++) {
      prev[i] = head_;
    }
    max_height_.store(height, std::memory_order_relaxed);
  }
  // 创建一个新节点
  x = NewNode(key, height);
  for (int i = 0; i < height; i++) {
	// 串联的方式跟单链表类似
    x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
    prev[i]->SetNext(i, x);
  }
}

随机产生的高度

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

template <typename Key, class Comparator>
int SkipList<Key, Comparator>::RandomHeight() {
  // Increase height with probability 1 in kBranching
  // 生产 高度为1 的节点概率为 3/4，高度为 2的节点概率为 1/4
  // 层高为3的概率是3/16（1/4×3/4），层高为4的概率是3/64（1/4×1/4×3/4）
  static const unsigned int kBranching = 4;
  int height = 1;
  while (height < kMaxHeight && rnd_.OneIn(kBranching)) {
    height++;
  }
  assert(height > 0);
  assert(height <= kMaxHeight);
  return height;
}

查找前一个节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

template <typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node*
SkipList<Key, Comparator>::FindGreaterOrEqual(const Key& key, Node** prev) const {
  // 从头结点开始查找，并获取 skip-list 当前最大高度
  Node* x = head_;
  int level = GetMaxHeight() - 1;
  while (true) {
    // 假设 level 为4，x->Next(4) 就是头结点高度为 4 层的下一个节点
    Node* next = x->Next(level);
	// 如果当前节点 key > 下一个，则继续往后查找
    if (KeyIsAfterNode(key, next)) {
      x = next;
    } else {
	  // 假设当前 level 为 4，x[4] 发现 小于 x->Next(4)
	  // prev[4] = x->Next(4)
      if (prev != nullptr) prev[level] = x;
	  // level等于0，就是最下面一层
      if (level == 0) {
        return next;
      } else {
        // 下降一层，level 由 4 变成 3
        level--;
      }
    }
  }
}

由于 LSM 树的特性，跳表中没有删除操作，只有 插入、查找操作
同时也提供了 遍历操作
包括 向前、向后遍历，由于 LevelDB的跳表是单链表结构，所以向前操作的成本比较高

LevelDB的跳表中，使用了很多 内存屏障的操作，都是 C++11 中的标准

  • std::memory_order_relaxed：不对重排做限制，只保证相关共享内存访问的原子性。
  • std::memory_order_acquire: 用在 load 时，保证同线程中该 load 之后的对相关内存读写语句不会被重排到 load 之前，并且其他线程中对同样内存用了 store release 都对其可见。
  • std::memory_order_release：用在 store 时，保证同线程中该 store 之后的对相关内存的读写语句不会被重排到 store 之前，并且该线程的所有修改对用了 load acquire 的其他线程都可见。

相比于平衡树，LevelDB采用跳表的优势

  • dump的时候需要快速的顺序扫描，链表更有优势
  • 不需要删除操作，平衡树的功能显得多余了
  • 最大限度的并行，使用了内存屏障，如果要在平衡树中最类似功能，代价会更大

MemTable

MemTable 内部维护了一个跳表的迭代器

1
2

MemTable::Table::Iterator iter_;
typedef SkipList<const char*, KeyComparator> Table;

还有内存分配类，向前、向后迭代器

1
2
3
4

Arena arena_;
friend class MemTableIterator;
friend class MemTableBackwardIterator;
KeyComparator comparator_;

一些重要的函数

1
2
3
4

size_t ApproximateMemoryUsage();
Iterator* NewIterator();
void Add(SequenceNumber seq, ValueType type, const Slice& key, const Slice& value);
bool Get(const LookupKey& key, std::string* value, Status* s);

插入 和 查询 都是调用 sikp-list 实现的 SkipList中单条数据存放一条Key-Value数据，定义为：

1
2
3
4
5

SkipList Node := InternalKey + ValueString
InternalKey := KeyString + SequenceNum + Type
Type := kDelete or kValue
ValueString := ValueLength + Value
KeyString := UserKeyLength + UserKey

插入操作，源码中给出的 一条记录格式

1
2
3
4
5
6

  // Format of an entry is concatenation of:
  //  key_size     : varint32 of internal_key.size()
  //  key bytes    : char[internal_key.size()]
  //  tag          : uint64((sequence << 8) | type), type:insert or delete
  //  value_size   : varint32 of value.size()
  //  value bytes  : char[value.size()]
  • 获取编码后的一条记录长度
  • Arena分配对应的内存
  • 将 一条记录 拷贝到Arena 分配的内存中
  • 调用 SkipList 完成插入

插入时的 key，value结构

查找

  • 根据传入的 key，去 skip-list 中查找
  • 比较传入的 key 和 找到的 key 是否相等
  • 如果相等，检查 type，如果是 delete，则返回空
  • 否则 解析出 value，存入 str::string 中并返回

查询时，函数参数封装的 key结构

生成SSTable

mem-table 写 sstable的过程，在 db/db_impl.cc 的 WriteLevel0Table 函数中
调用过程：

1

后台线程BackgroundCall  -->  BackgroundCompaction  -->  CompactMemTable  -->  WriteLevel0Table

CompactMemTable 还会调用 RemoveObsoleteFiles，用来删除无用的 LOG 文件
根据代码中的注释，文件类型包括：

1
2
3
4
5
6
7

// Owned filenames have the form:
//    dbname/CURRENT
//    dbname/LOCK
//    dbname/LOG
//    dbname/LOG.old
//    dbname/MANIFEST-[0-9]+
//    dbname/[0-9]+.(log|sst|ldb)

CompactMemTable过程：

  • 获取当前版本 Version* base = versions_->current();
  • 执行 WriteLevel0Table
  • 设置 VersionEdit 的log编号，并将此次修改增加到 VersionSet 中
  • 调用 RemoveObsoleteFiles

RemoveObsoleteFiles 过程：

  • 去 DB 路径下拿到文件列表，然后解析这些文件
  • 主要解析出这些文件的 number：dbname/MANIFEST-[0-9]+、dbname/[0-9]+.(log|sst|ldb)
  • 如果 number < 当前日志 && number < 前一个版本日志，这个日志就可以删除了
  • 如果 manifest 小于 当前 manifest 编号，这个 manifest 文件也可以删除了
  • 获取 VersionSet 中所有的活跃文件，对于 kTableFile、kTempFile 如果不在活跃文件中，也可以删除

获取活跃文件的过程：

  • Version是通过双链表组织的
  • 获取每层的元数据集合 std::vector<FileMetaData*>，默认最大层为 7，也就是遍历 7 次
  • 对每层的元数据列表，将其插入到 活跃列表中 std::set<uint64_t>*

WriteLevel0Table过程

  • 得到一个新的 FileMetaData 编号，就是 VersionSet->next_file_number_++
  • 调用 BuildTable，其生成的 TableFileName 是根据 FileMetaData的编号得到的
  • 获取 min、max key，然后确定将 ss-table 推入哪个层级，调用 PickLevelForMemTableOutput
  • 将 压缩状态存入 CompactionStats[level] 中，这里的 level 固定为 PickLevelForMemTableOutput 返回的层级

BuildTable 过程：

  • 从 skip-list 的第一个元素开始遍历，一直到结束，将这些 key-value 加入到 TableBuilder
  • 同时记录 FileMetaData 的最大、最小、key数量、文件size
  • 将数据写入到磁盘

PickLevelForMemTableOutput

  • 如果跟 0层的有重叠，则推入 0层
  • 检查方式是，对于 level0，需要遍历所有文件，检查每个文件跟min、max key 是否有重叠
  • 非 level 0的，则使用 二分查找 当前层的所有文件
  • 还会检查 level 0、level 1 在其祖父层级(对应的就是 level 2、level 3中，是否重叠太多
  • 默认的最大单个文件大小为 2M，如果一次重叠的数量 > 20M，PickLevelForMemTableOutput 会继续往更深层级查找
  • 不过限制了最大查找层级为 2，这也是做了一个权衡

后台压缩合并过程

min、max-key在不同层级的查找

PickLevelForMemTableOutput的检测过程

参考