RocksDB 源码阅读——SkipList

References

• RocksDB 源码 inlineskiplist.h

SkipList::Node 的实现

RocksDB 分配了一块连续的空间来存储节点在不同 level 的 next 指针。同时，使用 std::atomic 保证可以在无锁的情况下更新链表。其伪代码如下所示，可以说是把内存空间利用得严严实实。

#include <atomic>
#include <cstring>
#include <memory>

// https://github.com/facebook/rocksdb/blob/ef67339175c1aebe039c0671560b608e22656612/memtable/inlineskiplist.h
class SkipList {
public:
  struct Node {
  private:
    std::atomic<Node *> next_[1];

  public:
    void StashHeight(size_t h) { memcpy(&next_[0], &h, sizeof(h)); }

    size_t UnstashHeight() {
      size_t rv;
      memcpy(&rv, &next_[0], sizeof(rv));
      return rv;
    }

    Node *Next(size_t level) {
      return (&next_[0] - level)->load(std::memory_order_acquire);
    }
  };

  Node *AllocateNode(size_t height, size_t key_size) {
    size_t prefix = sizeof(std::atomic<Node *>) * height - 1;
    char *raw = new char[prefix + sizeof(Node) + key_size];
    Node *node = reinterpret_cast<Node *>(raw + prefix);

    node->StashHeight(height);

    return node;
  }
};

此处有个很有意思的点，在 AllocateNode 生成一个随机高度的节点的时候，会把他的高度通过 StashHeight 的方式暂时存储在 next_[0] 中。在后续的操作中，可以通过 UnstashHeight 读取存储的高度，并进行后续的 next 指针的更新（毕竟这些更新需要知道高度），可以说是不浪费任何内存空间。

其内存布局大概如下图所示（此处我做了简化，&next_[0] - n 其实就是相当于 next_[-n]，但是数组不支持负数）：