ToplingDB 的去虚拟化(devirtualization)

背景

ToplingDB 是 topling 开发的 KV 存储引擎，fork 自 RocksDB，进行了很多改造，也修改了很多 RocksDB 的 bug，其中有几十个修改也给上游 RocksDB 发了 Pull Request，让即便不使用 ToplingDB 的用户也能受益，虽然 RocksDB 接受得不够积极，但是我们确实已经尽力了！

本文主要来讲 ToplingDB 的去虚拟化(devirtualization) ，我们知道，在 C++ 中，虚函数是一个核心 Feature，它是运行时多态的基础，既然是运行时多态，必然有相应的虚函数调用开销。在编译器层面上，有自动的 devirtualization，就是当编译器“知道”某个对象的实际类型时，它就“知道”调用的虚函数具体是哪个，此时就可以直接调用该函数，不用访问虚表，甚至将该函数进行内联(inline)，C++11 新加的 final 关键字，除了语言层面上让代码更严格，也帮助编译器更好地进行这种优化。

在 RocksDB 中，虚函数的使用无处不在，一个典型的例子就是比较器 Comparator，用来确定 Key 的排序方式。默认的比较器是 BytewiseComparator，另一个常用的比较器是 ReverseBytewiseComparator。本文描述的去虚拟化，就以 Comparator 为例来展开。

Comparator vs Encoding

在大多数情况下，我们使用的都是默认的 BytewiseComparator，只有在特定场景下才会自定义 Comparator。

另一方面，即便在这些需要自定义 Comparator 的特殊场景下，我们也还有其它方案：

不自定义 Comparator，仍然使用默认的 BytewiseComparator，通过将 Key 进行编码，使其编码后的形式，在 BytewiseComparator 的作用下，等效于使用自定义 Comparator 对原始 Key 进行比较。

1. 在 Todis 中，我们就使用了**编码**的方案\
2. 在 MyTopling 中，复用了 MyRocks 的编码方案，使用 BytewiseComparator。

为什么是 BytewiseComparator

BytewiseComparator，其行为等价于 std::string 的比较方式，从形式上讲，跟自定义的各种特殊的比较器相比，并没有什么特别之处。在辩证法中，形式与内容是非常重要的主题，它们是辩证法的一对基本范畴，内容是事物一切内在要素的总和，形式是这些内在要素的结构和组织方式。

所以，从内容上，我们看，BytewiseComparator 有什么特殊之处：

// 将 x, y 调换位置，就是 ReverseBytewiseComparator
int compare(Slice x, Slice y) {
  int c = memcmp(x.data(), y.data(), min(x.size(), y.size()));
  if (c) return c;
  else return x.size() < y.size() ? -1 :
              x.size() > y.size() ? +1 : 0;
}

第一：简单，并且利用了所有必要的信息，从信息论的角度讲，它的墒是最低的。

第二：高效，使用的都是系统原语，其它任何“通用”的比较方式都不可能比它更高效。

其次，从概念外延的角度看，BytewiseComparator 定义的 Key 次序，是很多数据的“天然”次序：

1. 按 BigEndian 存储的无符号整数，不限位数（8位，16位，32位，64位……）
2. 单词表(包括但不限于英文单词)，所以 BytewiseComparator 定义的次序又叫“字典序”

数据结构

数据结构包含数据的存储方案和处理算法，RocksDB 作为存储引擎界的事实标准，其数据结构的实现精妙绝伦，并且处于不断的改善与演进中，如果我们要按照与其相同的思路和方法，去进行“改进”，是很难有所突破的。

所以，必须另辟蹊径。ToplingDB 最大的核心竞争力在于核心性能组件：

1. Topling CSPP MemTable & CSPP WBWI
2. Topling ZipTable

其核心思想在于：使用特殊数据结构(Trie&Succinct)，仅支持 BytewiseComparator，一切为了性能。

所以，Todis 和 MyTopling 使用与 BytewiseComparator 等效的编码方案，完美地适配了 ToplingDB 的性能组件。

热点转移

代码中的多个步骤，每个步骤都会消耗一定的时间，其中的热点(HotSpot)是最值得优化的，例如，有个热点消耗了 80% 的执行时间，我们对这个热点进行优化，把这个热点代码的速度提高(到)了 10 倍，我们看看优化的总体效果，好像还可以：

整个程序的速度提高(到)了多少倍	100/28=	3.57142857
新的代码占总执行时间的比例	8/28=	0.28571429
原先剩余 20% 现在的时间占比	20/28=	0.71428571

如果这个热点的速度是提高了 100 倍呢？这就有点悲观了：

整个程序的速度提高(到)了多少倍	100/20.8=	4.80769231
新的代码占总执行时间的比例	0.8/20.8=	0.03846154
原先剩余 20% 现在的时间占比	20/20.8=	0.96153846

所以，优化了一个热点之后，原先不是热点的代码，就成了新的热点，并且优化得越彻底，新的热点就越突出！

正题：去虚拟化(Devirtualization)

Comparator 是抽象接口，可以实现运行时多态，而真正的运行时多态，大多数情况下是 BytewiseComparator，并且 ToplingDB 的一些性能组件，仅支持 BytewiseComparator。这些性能组件消除了相应的热点，然后新的热点就冒出来了。

在 RocksDB 的整个执行栈中，Comparator 往往是最下面一层，从而最容易成为耗时大户，用到 Comparator 的地方，除了具体的组件模块（例如 MemTable，SST），还有很多管理、调度模块，我们在火焰图中可以看到，这些管理、调度模块就是新的热点，例如：

FindFileInRange	在 LSM 每层中查找命中的 SST 文件
MergingIterator	合并多层（再加 MemTable）数据

它们的耗时都来源于 Comparator 的开销，这其中单纯的调用链开销甚至大于必要的计算(memcmp...)，调用链开销就是我们去虚拟化的目标。首先，我们要识别在什么情况下可以去虚拟化，自然是前面讲的，BytewiseComparator(以及 ReverseBytewiseComparator) 的场景，这个很简单，每个具体的 Comparator 都有自己的名字，我们判断名字就可以了。然后是怎么实现去虚拟化，我们使用模板，只需要极少的代码修改，就可以实现去虚拟化。

FindFileInRange: 去虚拟化 V1

....... 省略 省略 省略 省略 省略 省略 省略 省略

+template<class Cmp>
+size_t FindFileInRangeTmpl(const FdWithKeyRange* a, size_t lo, size_t hi,
+                           Slice key, Cmp cmp) {
+  while (lo < hi) {
+    size_t mid = (lo + hi) / 2;
+    if (cmp(a[mid].largest_key, key))
+      lo = mid + 1;
+    else
+      hi = mid;
+  }
+  return lo;
+}
+
@@ -96,6 +142,16 @@ int FindFileInRange(const InternalKeyComparator& icmp,
     const Slice& key,
     uint32_t left,
     uint32_t right) {
+  if (IsForwardBytewiseComparator(icmp.user_comparator())) {
+    BytewiseCompareInternalKey cmp;
+    return (int)FindFileInRangeTmpl(file_level.files, left, right, key, cmp);
+  }
+  else if (IsBytewiseComparator(icmp.user_comparator())) {
+    RevBytewiseCompareInternalKey cmp;
+    return (int)FindFileInRangeTmpl(file_level.files, left, right, key, cmp);
+  }
   auto cmp = [&](const FdWithKeyRange& f, const Slice& k) -> bool {
     return icmp.InternalKeyComparator::Compare(f.largest_key, k) < 0;
   };

关键的代码改动，就是这么简单！省略的部分：

BytewiseCompareInternalKey RevBytewiseCompareInternalKey	inline 的，stl 风格的 comparator
IsForwardBytewiseComparator IsBytewiseComparator	顾名思义，判断 Comparator 的具体类型

MergingIterator 的去虚拟化，方法是类似的。

FindFileInRange: 去虚拟化 V2

很快，我们在火焰图中发现了新的热点：IsForwardBytewiseComparator ！

这又是怎么回事？原来，IsForwardBytewiseComparator 是通过 Comparator Name 来判断的，因为 FindFileInRange 中这个判断只执行一次，并且 Comparator Name 是和常量字符串比较的，所以一直以来我们认为它几乎是零成本的，然而事实打脸了！

好在这个问题只要发现了，处理起来还是很简单的：

- private:
-  size_t timestamp_size_;
+  bool IsForwardBytewise() const noexcept { return 0 == opt_cmp_type_; }
+  bool IsReverseBytewise() const noexcept { return 1 == opt_cmp_type_; }
+  bool IsBytewise() const noexcept { return opt_cmp_type_ <= 1; }
+
+ protected:
+  uint16_t timestamp_size_;
+  // 0: forward bytewise, 1: rev byitewise, others: unknown
+  uint8_t opt_cmp_type_ = 255;
 };
 
 // Return a builtin comparator that uses lexicographic byte-wise
@@ -150,12 +156,21 @@ extern const Comparator* BytewiseComparator();
 // ordering.
 extern const Comparator* ReverseBytewiseComparator();
 
-bool IsForwardBytewiseComparator(const Comparator* cmp);
 bool IsForwardBytewiseComparator(const Slice& name);
-bool IsReverseBytewiseComparator(const Comparator* cmp);
 bool IsReverseBytewiseComparator(const Slice& name);
-
-bool IsBytewiseComparator(const Comparator* cmp);
 bool IsBytewiseComparator(const Slice& name);
 
+inline bool IsForwardBytewiseComparator(const Comparator* cmp) {
+  assert(cmp->IsForwardBytewise() == IsForwardBytewiseComparator(cmp->Name()));
+  return cmp->IsForwardBytewise();
+}
+inline bool IsReverseBytewiseComparator(const Comparator* cmp) {
+  assert(cmp->IsReverseBytewise() == IsReverseBytewiseComparator(cmp->Name()));
+  return cmp->IsReverseBytewise();
+}
+inline bool IsBytewiseComparator(const Comparator* cmp) {
+  assert(cmp->IsBytewise() == IsBytewiseComparator(cmp->Name()));
+  return cmp->IsBytewise();
+}

我们新增了一个成员 opt_cmp_type_，用来标记 comparator 的实际类型。

RocksDB Comparator 中增加 timestamp_size_ 已经很久了（用来支持用户层 timestamp），因为 timestamp_size_ 是很短的（一般8字节），我们把它从 size_t 改成 uint16，从而即便增加了 opt_cmp_type_ 成员，Comparator 的实际尺寸也不会改变（实际上仍然有 5 字节的 padding）。

这个修改之后，我们甚至还因此发现了 RocksDB 的一个 bug，虽然这个 bug 无关痛痒，但我们还是给 RocksDB 提交了相应的 Pull Request。这里也体现除了单元测试的重要性，我们的这些修改，只关乎性能，不关乎行为，所以，只需要跑通已有的单元测试，代码的正确性就有了基本的保证。

FindFileInRange: 去虚拟化 V3

在 FindFileInRangeTmpl 中参数 key 总是热的（在 L1 Cache 中），但是文件的 largest_key 未必，这就是一个极佳的 prefetch 场景：

@@ -128,6 +128,7 @@ size_t FindFileInRangeTmpl(const FdWithKeyRange* a, size_t lo, size_t hi,
                            Slice key, Cmp cmp) {
   while (lo < hi) {
     size_t mid = (lo + hi) / 2;
+    __builtin_prefetch(a[mid].largest_key.data_);
     if (cmp(a[mid].largest_key, key))
       lo = mid + 1;
     else

在 prefetch 和 memcmp 访问 largest_key 之间，(inline 后)有不少代码要执行，可以有效掩盖 cache miss 延迟。

FindFileInRange: 去虚拟化 V4

到目前为止，在 FindFileInRangeTmpl 中，仍然要调用 memcmp，仍然要通过指针间接访问 file.largest_key 的内容，还可能怎样进一步优化呢？

我们知道，BytewiseComparator 总是从前往后比较的，只要到某个点为止的前缀不同，后面的内容就不用比较了，所以，我们可以进行固定长度前缀搜索优化：

1. 比较固定前缀时不调用 memcmp，固定前缀 8 字节，使用 uint64 比较，完全内联
2. 将固定前缀拷贝到一个单独的(uint64)数组中，消除间接访问
3. 该 uint64 数组与 file 数组平行，先在 uint64 数组中搜索 equal range，然后精确搜索
4. 1. 在 uint64 数组中搜索时 CPU Cache 利用率达到最大化

@@ -113,6 +113,9 @@ struct BytewiseCompareInternalKey {
     if (x.size_ != y.size_) return x.size_ < y.size_;
     return GetUnalignedU64(x.data_ + n) > GetUnalignedU64(y.data_ + n);
   }
+  FORCE_INLINE bool operator()(uint64_t x, uint64_t y) const noexcept { return x < y; }
 };
@@ -122,12 +125,31 @@ struct RevBytewiseCompareInternalKey {
     if (x.size_ != y.size_) return x.size_ > y.size_;
     return GetUnalignedU64(x.data_ + n) > GetUnalignedU64(y.data_ + n);
   }
+  FORCE_INLINE bool operator()(uint64_t x, uint64_t y) const noexcept { return x > y; }
 };
 template<class Cmp>
-size_t FindFileInRangeTmpl(const FdWithKeyRange* a, size_t lo, size_t hi,
+size_t FindFileInRangeTmpl(const LevelFilesBrief& brief, size_t lo, size_t hi,
                            Slice key, Cmp cmp) {
+  const uint64_t* pxcache = brief.prefix_cache;
+  const uint64_t  key_prefix = HostPrefixCache(key);
+  const FdWithKeyRange* a = brief.files;
+  size_t mid;
+  while (lo < hi) {
+    mid = (lo + hi) / 2;
+    if (cmp(pxcache[mid], key_prefix))
+      lo = mid + 1;
+    else if (cmp(key_prefix, pxcache[mid]))
+      hi = mid;
+    else
+      goto exact_search;
+  }
+  return lo;
+
   while (lo < hi) {
-    size_t mid = (lo + hi) / 2;
+    mid = (lo + hi) / 2;
+  exact_search:
     __builtin_prefetch(a[mid].largest_key.data_);
     if (cmp(a[mid].largest_key, key))

HostPrefixCache 的实现也非常简单直接：

inline uint64_t HostPrefixCache(const Slice& ikey) {
  uint64_t data = 0; // 下面这个 memcpy 调用编译器也优化掉了，__bswap_64 更不必说
  memcpy(&data, ikey.data_, std::min<size_t>(ikey.size_ - 8, 8));
  if (port::kLittleEndian) return __bswap_64(data); else return data;
}

---

经过这么多优化，FindFileInRange 从一开始在火焰图中最高超过 40%，到现在，已经在火焰图中看不到了！

其实后面两个改进并不是去虚拟化，只是因为一开始从去虚拟化的思路一路走来而已。

对于 MergingIterator 的去虚拟化，思路和方法跟 FindFileInRange 是类似的，甚至后面的前缀搜索优化，思路也类似（仅列出关键修改）：

+struct MgHeapElem {
+  IteratorWrapper* iter;
+  uint64_t key_prefix;
+  MgHeapElem() : iter(nullptr), key_prefix(0) {}
+  MgHeapElem(std::nullptr_t) : iter(nullptr), key_prefix(0) {}
+  MgHeapElem(IteratorWrapper* i) : iter(i) { key_prefix = HostPrefixCache(i->key()); }
+  IteratorWrapper* operator->() const noexcept { return iter; }
+};
+inline void UpdateIterElem(MgHeapElem&x){x.key_prefix = HostPrefixCache(x.iter->key());}
+inline void UpdateIterElem(IteratorWrapper*) {} // do nothing
@@ -60,50 +85,66 @@ static FORCE_INLINE bool RevBytewiseCompareInternalKey(Slice x,
  struct MaxInlineBytewiseComp {
-  bool operator()(const IteratorWrapper* a, const IteratorWrapper* b) const noexcept {
-    return BytewiseCompareInternalKey(a->key(), b->key());
+  bool operator()(const MgHeapElem& a, const MgHeapElem& b) const noexcept {
+    if (a.key_prefix < b.key_prefix)      return true;
+    else if (a.key_prefix > b.key_prefix) return false;
+    else return BytewiseCompareInternalKey(a->key(), b->key());
   }
   MaxInlineBytewiseComp(const InternalKeyComparator*) {}
 };
@@ -259,6 +300,7 @@ class MergingIterTmpl : public MergingIterator {
     // as the current points to the current record. move the iterator forward.
     current_->Next();
     if (current_->Valid()) {
+      UpdateIterElem(current_);
@@ -301,6 +343,7 @@ class MergingIterTmpl : public MergingIterator {
     current_->Prev();
     if (current_->Valid()) {
+      UpdateIterElem(current_);

最后，MergingIterator 在火焰图中始终是能看到的，因为它下层 iterator 函数耗时很多。

总结

编译器可以帮我们执行最基本的去虚拟化(Devirtualization)，但是，更高层次的去虚拟化，其带来的收益要大得多，但这需要我们多动脑，多分析，多思考，找到相应的解决方案。