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

MemTable 是 RocksDB 中所有写入操作首先进入的内存数据结构。除了默认的 SkipListRep 实现外，RocksDB 还提供了多种为特定工作负载（Workload）优化的 MemTableRep。本文旨在深入探讨三种极具特色的 MemTable 实现：VectorRep、HashSkipListRep 和 HashLinkListRep，分析它们的核心设计、实现细节与性能权衡。

1. `VectorRep`：为批量写入优化的简洁实现

VectorRep 是一种基于 std::vector 的 MemTableRep 实现。它的设计哲学是牺牲首次读取性能，换取极致的写入速度和内存效率。

1.1 核心设计思想

VectorRep 的核心数据结构就是一个 std::vector，它存储所有指向键值对内存区域的指针。

// memtable/vectorrep.cc

using Bucket = std::vector<const char*>;
std::shared_ptr<Bucket> bucket_;

这种设计的关键特性是 **“懒加载排序” (Lazy Sort)**：

写入: 插入操作仅是在 std::vector 的末尾进行 push_back，这是一个摊销 O(1) 的操作，速度极快。
读取: 在进行任何查找（Seek）或迭代之前，必须对整个 vector 进行一次全量排序。这次排序的开销是 O(N log N)，可能会导致首次读取的延迟显著增高。

1.2 写入路径与并发优化

VectorRep 提供了两种写入模式以优化不同场景下的性能。

1. 单线程写入 Insert()

逻辑非常直接：获取写锁，然后向 bucket_ 中 push_back。

// memtable/vectorrep.cc

void VectorRep::Insert(KeyHandle handle) {
  auto* key = static_cast<char*>(handle);
  {
    WriteLock l(&rwlock_);
    assert(!immutable_);
    bucket_->push_back(key);
  }
  bucket_size_.FetchAddRelaxed(1);
}

2. 并发写入 InsertConcurrently() 与 BatchPostProcess()

为了解决高并发写入时的锁竞争问题，VectorRep 采用了一种基于线程本地存储（Thread Local Storage）的无锁优化。

InsertConcurrently(): 此函数将写入的 key 存入一个线程独有的 std::vector 中。由于每个线程操作自己的数据，这个过程完全无锁，速度极快。

// memtable/vectorrep.cc

void VectorRep::InsertConcurrently(KeyHandle handle) {
  auto* v = static_cast<TlBucket*>(tl_writes_.Get());
  if (!v) {
    v = new TlBucket();
    tl_writes_.Reset(v);
  }
  v->push_back(static_cast<char*>(handle));
}

BatchPostProcess(): 在一次 WriteBatch 写入的末尾，RocksDB 会调用此函数。它负责获取写锁，并将当前线程在本地缓存的所有数据一次性地合并到主 bucket_ 中。

// memtable/vectorrep.cc

void VectorRep::BatchPostProcess() {
  auto* v = static_cast<TlBucket*>(tl_writes_.Get());
  if (v) {
    {
      WriteLock l(&rwlock_);
      assert(!immutable_);
      for (auto& key : *v) {
        bucket_->push_back(key);
      }
    }
    bucket_size_.FetchAddRelaxed(v->size());
    delete v;
    tl_writes_.Reset(nullptr);
  }
}

这种 “N次无锁写入 + 1次批量加锁合并” 的模式，极大地提升了并发写入的吞吐量。

1.2.1 深入 `BatchPostProcess` 调用时机

BatchPostProcess 的调用与 WriteBatch 的处理流程紧密相关，其背后是精巧的访问者模式应用。

触发: 当用户调用 db->Write() 并提交一个 WriteBatch 时，整个流程开始。
迭代: RocksDB 内部会创建一个 MemTableInserter（一个 WriteBatch::Handler 的实现），并用它来迭代 WriteBatch 中的所有条目。
并发插入: 对于 WriteBatch 中的每一个 Put 操作，MemTableInserter 都会调用 MemTable::Add，进而触发 VectorRep::InsertConcurrently，将数据写入线程本地缓存。
最终合并: 在 WriteBatch 中的所有条目都被 MemTableInserter 处理完毕后，RocksDB 会在写入流程的最后，调用一次 BatchPostProcess() 方法。

这个机制保证了对于一个 WriteBatch 的 N 次写入，仅有一次最终的加锁合并操作，从而将锁竞争降至最低。

1.3 读取与迭代器机制

VectorRep 的读取逻辑完全服务于其“懒加载排序”的设计。

写时复制 (Copy-on-Write): 当为一个可变 (mutable) 的 VectorRep 创建迭代器时，为了保证快照一致性（防止在迭代时有新的写入），它会完整地拷贝一份当前的 bucket_ 数据供迭代器使用。这是一个 O(N) 的昂贵操作。如果 VectorRep 已被标记为**不可变 (immutable)**，则迭代器可以直接共享原始数据，无需拷贝。

// memtable/vectorrep.cc

MemTableRep::Iterator* VectorRep::GetIterator(Arena* arena) {
  // ...
  ReadLock l(&rwlock_);
  if (immutable_) {
    // ... 直接使用 bucket_
  } else {
    // 对可变 memtable，创建一份拷贝
    std::shared_ptr<Bucket> tmp;
    tmp.reset(new Bucket(*bucket_));  // make a copy
    // ... 使用 tmp
  }
}

DoSort(): 迭代器的几乎所有操作（如 Valid(), Seek()）都会首先调用 DoSort()。该函数确保数据在被访问前是排序的。值得注意的是，为了保证修改 sorted_ 状态位的线程安全，这里需要获取写锁。

// memtable/vectorrep.cc

void VectorRep::Iterator::DoSort() const {
  if (!sorted_ && vrep_ != nullptr) {
    WriteLock l(&vrep_->rwlock_); // 获取写锁以修改状态
    if (!vrep_->sorted_) {
      std::sort(bucket_->begin(), bucket_->end(),
                stl_wrappers::Compare(compare_));
      cit_ = bucket_->begin();
      vrep_->sorted_ = true;
    }
    sorted_ = true;
  }
  // ...
}

SeekForPrev() 的缺失: VectorRep 的迭代器并未实现 SeekForPrev 功能。这是一个重要的设计权衡。
```
// memtable/vectorrep.cc
void VectorRep::Iterator::SeekForPrev(const Slice& /*user_key*/,
                                      const char* /*memtable_key*/) {
  assert(false);
}
```
这意味着 VectorRep 不支持高效地“反向查找”（即查找第一个小于或等于目标 Key 的条目）。如果业务场景需要频繁进行此类操作，VectorRep 将不是一个合适的选择。这再次凸显了其为“快速写入、简单正向读取”场景的深度优化。

1.5 小结

VectorRep 是一个特点鲜明的实现。

优点: 写入速度极快、内存占用低、非常适合批量加载（Bulk Loading）场景。
缺点: 首次读取延迟高，对可变 MemTable 的迭代成本高昂，且不支持反向 Seek。

2. Prefix-Based Hashing：为前缀查找而生

HashSkipListRep 和 HashLinkListRep 共享一个核心设计：它们都是基于前缀哈希的 MemTable。它们通过 SliceTransform 组件从用户 Key 中提取一个“前缀”，然后仅对前缀进行哈希，将所有具有相同前缀的 Key 定位到同一个“桶” (Bucket) 中。

这种设计使得“查找具有相同前缀的所有 Key”这类操作的性能得到极大提升，因为查找范围从整个数据集缩小到了一个桶内。

3. `HashSkipListRep`：简单高效的前缀哈希方案

这是两种前缀哈希实现中较为直接的一种。

3.1 核心设计思想

HashSkipListRep 的数据结构是一个哈希表（通过指针数组实现），其中每一个桶都是一个完整的 **SkipList**（跳表）。

// memtable/hash_skiplist_rep.cc

class HashSkipListRep : public MemTableRep {
  // ...
  using Bucket = SkipList<const char*, const MemTableRep::KeyComparator&>;
  std::atomic<Bucket*>* buckets_;
  // ...
};

3.2 实现解析

懒加载: 哈希表中的桶（SkipList实例）并不会在 MemTable 创建时就全部分配好。只有当一个 Key 首次落入某个桶时，对应的 SkipList 才会被创建。这在哈希空间利用率较低时能有效节省内存。

// memtable/hash_skiplist_rep.cc

HashSkipListRep::Bucket* HashSkipListRep::GetInitializedBucket(
    const Slice& transformed) {
  size_t hash = GetHash(transformed);
  auto bucket = GetBucket(hash);
  if (bucket == nullptr) { // 如果桶不存在
    auto addr = allocator_->AllocateAligned(sizeof(Bucket));
    // 创建一个新的 SkipList 实例
    bucket = new (addr) Bucket(compare_, allocator_, skiplist_height_,
                               skiplist_branching_factor_);
    buckets_[hash].store(bucket, std::memory_order_release);
  }
  return bucket;
}

读写路径: 所有操作（Insert, Get, Contains）都遵循“提取前缀 -> 哈希定位 -> 在桶内 SkipList 中操作”的路径。桶内的操作就是标准的跳表操作，性能稳定在 O(log N)。

3.3 小结

HashSkipListRep 的设计简单明了，性能可预测。它适用于大部分前缀下的 Key 数量都较多的场景。其主要缺点是在稀疏前缀场景下（大量桶只有一个或零个元素），为每个桶都维护一个 SkipList 结构会带来一定的内存开销。

4. `HashLinkListRep`：精巧的自适应哈希方案

HashLinkListRep 是对 HashSkipListRep 的一种极致优化，其核心在于桶内数据结构的自适应性。

4.1 核心设计思想

HashLinkListRep 的桶会根据其中元素的数量动态地改变其自身结构，以在内存占用和查询性能之间达到最佳平衡。

4.2 桶的四种形态与状态转换

一个桶的生命周期会经历以下几种形态：

空桶: 初始状态，指针为 nullptr。
单个节点: 当第一个 Key 落入时，桶指针直接指向该 Node。此设计旨在为稀疏桶节省头节点开销。
有序链表: 当第二个 Key 落入时，桶会“升级”为一个由 BucketHeader 管理的有序链表。此时插入和查找是 O(N) 的。
跳表: 当链表长度超过预设阈值 threshold_use_skiplist 时，HashLinkListRep 会认为该桶已成为热点。它会将**整条链表一次性地转换成一个全新的 SkipList**，以保证后续的查找性能为 O(log N)。

Insert 函数中的逻辑清晰地展示了这种状态机：

// memtable/hash_linklist_rep.cc



void HashLinkListRep::Insert(KeyHandle handle) {
  // ...
  if (first_next_pointer == nullptr) {
    // Case 1. empty bucket -> Case 2. single entry
  }

  BucketHeader* header = nullptr;
  if (first_next_pointer->load(std::memory_order_relaxed) == nullptr) {
    // Case 2. single entry -> Case 3. linked list
    // ... 创建 BucketHeader ...
  } else {
    header = reinterpret_cast<BucketHeader*>(first_next_pointer);
    if (header->IsSkipListBucket()) {
      // Case 4. Bucket is already a skip list
      // ... 直接插入 SkipList ...
      return;
    }
  }

  if (header->GetNumEntries() == threshold_use_skiplist_) {
    // Case 3. linked list -> Case 4. skip list
    // ... 将链表所有元素插入到新创建的 SkipList 中 ...
  } else {
    // Case 5. 插入到已有的有序链表中
    // ...
  }
}

4.3 小结

HashLinkListRep 是一个非常精巧的设计。

优点: 在大量前缀桶内元素稀少时，内存效率极高。
缺点: 实现非常复杂，且在链表向跳表转换的瞬间，单次插入的延迟会较高，可能造成性能抖动。

5. 对比与总结

特性	`VectorRep`	`HashSkipListRep`	`HashLinkListRep`
核心结构	`std::vector`	哈希表 + 跳表	哈希表 + (节点/链表/跳表)
数据有序性	全局懒排序	桶内有序	桶内有序
写入性能	极快 (摊销 O(1))	稳定 (O(log N))	有波动 (O(N) 或 O(log N)，含转换开销)
读取性能	首次慢 (O(N log N))	稳定 (O(log N))	有波动 (O(N) 或 O(log N))
内存占用	低	中等	最低 (在稀疏场景下)
适用场景	批量加载，写多读少	通用的前缀查找	稀疏的前缀查找，内存敏感

KV数据库

KV数据库 RocksDB

转载请注明出处

RocksDB中Cuckoo Table技术内幕解析上一篇

RocksDB源码学习：MemTable实现之SkipList 下一篇