RocksDB源码学习：MemTable实现之SkipList

源码解读关于RocksDB中MemTable的SkipList实现，Generated by AI。

前言

本文主要是 RocksDB 的 MemTable 核心实现的学习笔记。我们将从 memtable/skiplistrep.cc 的上层封装开始，层层深入，直至 memtable/inlineskiplist.h 中跳表的实现。

第一部分：`SkipListRep` - `MemTable` 的接口与工厂

memtable/skiplistrep.cc定义了 MemTable 的默认实现。MemTable 是 RocksDB 用于在内存中缓存写入的有序数据结构。SkipListRep 便是基于跳表（Skip List）的 MemTable 表示（Representation）。

1.1 `SkipListRep` 类的结构

SkipListRep 继承自 MemTableRep，它是一个接口类，定义了 MemTable 必须具备的行为。

// in memtable/skiplistrep.cc  
class SkipListRep : public MemTableRep {  
  InlineSkipList<const MemTableRep::KeyComparator&> skip_list_;  
  const MemTableRep::KeyComparator& cmp_;  
  const SliceTransform* transform_;  
  const size_t lookahead_;  
  
  friend class LookaheadIterator;  
  
 public:  
  explicit SkipListRep(const MemTableRep::KeyComparator& compare,  
                       Allocator* allocator, const SliceTransform* transform,  
                       const size_t lookahead)  
      : MemTableRep(allocator),  
        skip_list_(compare, allocator),  
        cmp_(compare),  
        transform_(transform),  
        lookahead_(lookahead) {}  
  
  // ... Methods like Insert, Get, GetIterator ...  
};

skip_list_: 核心数据成员，一个 InlineSkipList 的实例，所有数据和主要操作都在这里。我们将在第二部分深入它。
cmp_: 键比较器，决定了数据在跳表中的排序方式。
lookahead_: 用于 LookaheadIterator 的优化参数，我们将在迭代器部分详述。

SkipListRep 的方法大多是简单的“转发器”，将调用直接委托给 skip_list_，例如：

// in memtable/skiplistrep.cc  
void SkipListRep::Insert(KeyHandle handle) {  
  skip_list_.Insert(static_cast<char*>(handle));  
}  
  
bool SkipListRep::Contains(const char* key) const {  
  return skip_list_.Contains(key);  
}

1.2 `SkipListFactory`：可插拔的工厂模式

RocksDB 使用工厂模式来创建 MemTable。

// in memtable/skiplistrep.cc  
class SkipListFactory : public MemTableRepFactory {  
 public:  
  explicit SkipListFactory(size_t lookahead = 0) : lookahead_(lookahead) {}  
  
  MemTableRep* CreateMemTableRep(  
      const MemTableRep::KeyComparator& compare, Allocator* allocator,  
      const SliceTransform* transform, Logger* /*logger*/) override {  
    return new SkipListRep(compare, allocator, transform, lookahead_);  
  }  
  // ...  
 private:  
  const size_t lookahead_;  
};

CreateMemTableRep 方法清晰地展示了如何实例化一个 SkipListRep，并将配置参数 lookahead_ 传递进去。

第二部分：`InlineSkipList` - 高性能数据结构核心

InlineSkipList的实现在 memtable/inlineskiplist.h。

2.1 核心优化：内联存储、Arena 与无锁并发

InlineSkipList 的性能源于三大优化设计的协同工作：

1. 内联数据存储 (Inline Data Storage): 这是为了最大化 CPU 缓存命中率的优化。它通过 C++ 的柔性数组成员（Flexible Array Member）技巧实现，将节点元数据和 Key-Value 数据放在一块连续的内存中。

// in memtable/inlineskiplist.h  
struct Node {  
  // Array of next pointers. next_[0] is lowest level link.  
  std::atomic<Node*> next_[1];  
  
  // Key contents are stored after the Node structure in the memory.  
  char key[0];  
};

next_[1] 是一个占位符，实际分配内存时会根据节点高度动态扩展此数组的大小。
key[0] 标记了 Key 数据的起始地址，它紧跟在 next_ 数组之后。
这种布局意味着当 CPU 读取 Node 的指针时，Key 的数据也被一同加载到缓存，极大地加速了后续的 Key 比较操作。
内存布局示意： [ Node 结构(next 指针等) | Key 的数据 | Value 的数据 ]

2. Arena 内存分配: 所有 Node 都通过 Arena（内存池）进行分配，避免了 malloc 的系统调用开销，减少了内存碎片，并因物理内存的连续性进一步提升了缓存友好性。

3. 无锁并发: next_ 指针是 std::atomic<Node*> 类型，所有修改都通过原子的 CAS（Compare-And-Swap） 操作完成，无需使用重量级的互斥锁。这使得多线程可以高效地并发插入，是 RocksDB 高写入吞- 吞吐量的关键。

第三部分：迭代器 - 遍历与 `Seek`

3.1 `InlineSkipList::Iterator` 的实现

迭代器封装了遍历逻辑，其实现非常轻量。

// in memtable/inlineskiplist.h  
class Iterator {  
 public:  
  explicit Iterator(const InlineSkipList* list);  
  bool Valid() const;  
  const char* key() const;  
  void Next();  
  void Prev();  
  void Seek(const char* target);  
  void SeekToFirst();  
  void SeekToLast();  
  
 private:  
  const InlineSkipList* list_;  
  Node* node_;  
};

状态: 仅包含 list_ 和 node_ 两个指针，node_ 指向当前位置。
Next(): O(1) 操作，原子地读取 node_->Next(0)。
Prev(): O(log N) 操作，因跳表是单向的，需调用 list_->FindLessThan(key()) 从头查找前驱。
Seek(target): O(log N) 操作，直接调用 list_->FindGreaterOrEqual(target) 来定位。

3.2 `LookaheadIterator` 的优化

SkipListRep 在 GetIterator 时，如果 lookahead_ > 0，会创建一个 LookaheadIterator。这是一个优化版本，它的 Seek 方法很智能：

// in memtable/skiplistrep.cc  
void Seek(const Slice& internal_key, const char* memtable_key) {  
  // ...  
  if (prev_.Valid() && rep_.cmp_(encoded_key, prev_.key()) >= 0) {  
    // 如果目标 key 在上一个位置之后，尝试进行短距离线性扫描  
    iter_ = prev_;  
    size_t cur = 0;  
    while (cur++ <= rep_.lookahead_ && iter_.Valid()) {  
      if (rep_.cmp_(encoded_key, iter_.key()) <= 0) {  
        return; // 找到了！避免了一次完整的 Seek  
      }  
      Next();  
    }  
  }  
  
  // 如果线性扫描失败，再执行完整的 Seek  
  iter_.Seek(encoded_key);  
  prev_ = iter_;  
}

这种设计利用了访问的局部性原理，用很小的代价优化了常见的连续 Seek 场景。

3.2 核心查找算法: `FindGreaterOrEqual` 源码剖析

Iterator->Seek()就是调用的是InlineSkipList的FindGreaterOrEqual函数。

template <typename Key, class Comparator>
inline void SkipList<Key, Comparator>::Iterator::Seek(const Key& target) {
  node_ = list_->FindGreaterOrEqual(target);
}

此函数是跳表查找的核心，完美展现了其 O(log N) 的查找效率。

// in memtable/inlineskiplist.h  
template <class Comparator>  
inline typename InlineSkipList<Comparator>::Node*  
InlineSkipList<Comparator>::FindGreaterOrEqual(const char* key, Node** prev) const {  
  // 1. 初始化：从虚拟头节点的最高层开始  
  Node* x = head_;  
  int level = GetMaxHeight() - 1;  
  
  // 2. 主循环：从高层向低层逐级逼近  
  while (level >= 0) {  
    // 3. 内部循环：在当前层向右前进，直到下一个节点不小于 key  
    Node* next = x->Next(level);  
    while (next != nullptr && KeyIsAfterNode(key, next)) {  
      x = next;  
      next = x->Next(level);  
    }  
  
    // 4. 记录前驱节点（为插入做准备），并下降一层  
    if (prev != nullptr) {  
      prev[level] = x;  
    }  
    level--;  
  }  
  
  // 5. 返回结果：在最底层找到的前驱节点的下一个节点  
  return x->Next(0);  
}

这个阶梯式的查找路径（高层大步前进，低层精细查找）是跳表高效的根源。

3.3 `Seek`为什么是“大于或等于”？

Seek 找到“第一个大于或等于 target 的节点”是完全正确的，这与 RocksDB 的内部键（Internal Key）设计密切相关。

内部键结构: [ User Key | Sequence Number | Operation Type ]
排序规则: 1. 按 User Key 升序； 2. 若 User Key 相同，则按 Sequence Number 降序。

最新的操作（Sequence Number 最大）反而排在最前面。当 Seek("my_key") 时，RocksDB 查找的是 ("my_key" | MAX_SEQ_NUM)，FindGreaterOrEqual 会根据排序规则精确地找到 "my_key" 的最新版本，一步到位。

第四部分：工程实践 - `UniqueRandomSample` 的自适应算法

SkipListRep::UniqueRandomSample 用于数据采样，这个功能对于数据库收集统计信息、进行查询优化等非常重要。

// in memtable/skiplistrep.cc  
void SkipListRep::UniqueRandomSample(...) {  
  // ...  
  if (target_sample_size > static_cast<uint64_t>(std::sqrt(1.0 * num_entries))) {  
    // 采样数较大时，遍历一遍，按概率采样  
    // ...  
  } else {  
    // 采样数较小时，执行多次随机跳转来采样  
    // ...  
  }  
}

它内部根据输入参数，动态地选择了两种不同的采样算法，以追求最佳性能。

当采样数 m 比较大时 (m > sqrt(N)):
- 它会从头到尾完整地遍历一遍跳表。
- 对于遍历到的第 i 个元素，它以 (m' / (N-i)) 的概率决定是否将其放入样本集（其中 m' 是还需要采样的数量）。这是一种经典的“水塘采样”变体，保证了遍历一遍后能得到一个近似大小的无偏样本集。
1. 当采样数 m 比较小时 (m < sqrt(N)):
  - 完整遍历一遍的成本太高了。
  - 此时，它会执行 m次 RandomSeek()（随机跳转），直接随机跳到 m 个节点来作为样本。
  - 它使用一个 unordered_set 来自动处理随机跳转时可能产生的重复。

它根据采样数量和数据总量的关系，动态选择成本更低的算法，体现了在真实场景中对算法性能的深刻理解和权衡。

KV数据库

KV数据库 RocksDB

转载请注明出处

RocksDB源码学习：MemTable实现之VectorRep、HashLinkListRep与HashSkipListRep 上一篇

kubernetes部署中文版llama3模型下一篇

RocksDB源码学习：MemTable实现之SkipList

前言

第一部分：SkipListRep - MemTable 的接口与工厂

1.1 SkipListRep 类的结构

1.2 SkipListFactory：可插拔的工厂模式

第二部分：InlineSkipList - 高性能数据结构核心

2.1 核心优化：内联存储、Arena 与无锁并发

第三部分：迭代器 - 遍历与 Seek

3.1 InlineSkipList::Iterator 的实现

3.2 LookaheadIterator 的优化

3.2 核心查找算法: FindGreaterOrEqual 源码剖析

3.3 Seek为什么是“大于或等于”？

第四部分：工程实践 - UniqueRandomSample 的自适应算法