分布式数据库（九）

小注

极客时间 - 分布式数据库 30 讲

查询执行引擎

计算引擎在海量数据查询下的一些优化策略，包括计算下推和更复杂的并行执行框架。这些策略对应了从查询请求输入到查询计划这个阶段的工作。那么，整体查询任务的下一个阶段就是查询计划的执行，承担这部分工作的组件一般称为查询执行引擎。

单从架构层面看，查询执行引擎与分布式架构无关，但是由于分布式数据库要面对海量数据，所以对提升查询性能相比单体数据库有更强烈的诉求，更关注这部分的优化。

查询执行引擎是否高效与其采用的模型有直接关系，模型主要有三种：火山模型、向量化模型和代码生成。

火山模型

火山模型（Volcano Model）也称为迭代模型（Iterator Model），是最著名的查询执行模型，早在 1990 年就在论文 "Volcano, an Extensible and Parallel Query Evaluation System" 中被提出。主流的 OLTP 数据库 Oracle、MySQL 都采用了这种模型。

在火山模型中，一个查询计划会被分解为多个代数运算符（Operator）。每个 Operator 就是一个迭代器，都要实现一个 next() 接口，通常包括三个步骤：

1. 调用子节点 Operator 的 next() ，获取一个元组（Tuple）；
2. 对元组执行 Operator 特定的处理；
3. 返回处理后的元组。

通过火山模型，查询执行引擎可以优雅地将任意 Operator 组装在一起，而不需要考虑每个 Operator 的具体处理逻辑。查询执行时会由查询树自顶向下嵌套调用 next() ，数据则自底向上地被拉取处理。所以，这种处理方式也称为拉取执行模型（Pull Based）。

为了更好地理解火山模型的拉取执行过程，这里举一个聚合计算的例子，它来自 Databricks 的一篇文章（Sameer Agarwal et al. (2016)）。

select count(*) from store_sales where ss_item_sk = 1000;

开始从扫描运算符 TableScan 获取数据，通过过滤运算符 Filter 开始推动元组的处理。然后，过滤运算符传递符合条件的元组到聚合运算符 Aggregate。

『元组』这个词大致就是指数据记录（Record），讨论算法时学术文献中普遍会使用元组这个词。

火山模型的优点是处理逻辑清晰，每个 Operator 只要关心自己的处理逻辑即可，耦合性低。但是它的缺点也非常明显，主要是两点：

1. 虚函数调用次数过多，造成 CPU 资源的浪费。
2. 数据以行为单位进行处理，不利于发挥现代 CPU 的特性。

什么是虚函数呢？：

在火山模型中，处理一个元组最少需要调用一次 next() 函数，这个 next() 就是虚函数。这些函数的调用是由编译器通过虚函数调度实现的；虽然虚函数调度是现代计算机体系结构中重点优化部分，但它仍然需要消耗很多 CPU 指令，所以相当慢。

CPU 寄存器和内存：

在火山模型中，每次一个算子给另外一个算子传递元组的时候，都需要将这个元组存放在内存中，以行为组织单位很容易带来 CPU 缓存失效。

循环展开（Loop unrolling）：

当运行简单的循环时，现代编译器和 CPU 是非常高效的。编译器会自动展开简单的循环，甚至在每个 CPU 指令中产生单指令多数据流（SIMD）指令来处理多个元组。

单指令多数据流（SIMD）：

SIMD 指令可以在同一 CPU 时钟周期内，对同列的不同数据执行相同的指令。这些数据会加载到 SIMD 寄存器中。

Intel 编译器配置了 AVX-512（高级矢量扩展）指令集，SIMD 寄存器达到 512 比特，就是说可以并行运算 16 个 4 字节的整数。

在过去大概 20 年的时间里火山模型都运行得很好，主要是因为这一时期执行过程的瓶颈是磁盘 I / O。而现代数据库大量使用内存后，读取效率大幅提升，CPU 就成了新的瓶颈。因此，现在对火山模型的所有优化和改进都是围绕着提升 CPU 运行效率展开的。

改良方法（运算符融合）

要对火山模型进行优化，一个最简单的方法就是减少执行过程中 Operator 的函数调用。比如，通常来说 Project 和 Filter 都是常见的 Operator，在很多查询计划中都会出现。OceanBase1.0 就将两个 Operator 融合到了其它的 Operator 中。这样做有两个好处：

1. 降低了整个查询计划中 Operator 的数量，也就简化了 Operator 间的嵌套调用关系，最终减少了虚函数调用次数。
2. 单个 Operator 的处理逻辑更集中，增强了代码局部性能力，更容易发挥 CPU 的分支预测能力。

分支预测能力：

分支预测是指 CPU 执行跳转指令时的一种优化技术。当出现程序分支时 CPU 需要执行跳转指令，在跳转到目的地址之前无法确定下一条指令，就只能让流水线等待，这就降低了 CPU 效率。为了提高效率，设计者在 CPU 中引入了一组寄存器，用来专门记录最近几次某个地址的跳转指令。

这样，当下次执行到这个跳转指令时，就可以直接取出上次保存的指令，放入流水线。等到真正获取到指令时，如果证明取错了则推翻当前流水线中的指令，执行真正的指令。

这样即使出现分支也能保持较好的处理效率，但是寄存器的大小总是有限的，所以总的来说还是要控制程序分支，分支越少流水线效率就越高。

刚刚说的运算符融合是一种针对性的优化方法，优点是实现简便而且快速见效，但进一步的提升空间很有限。

因此，学术界还有一些更积极的改进思路，主要是两种。一种是优化现有的迭代模型，每次返回一批数据而不是一个元组，这就是向量化模型（Vectorization）；另一种是从根本上消除迭代计算的性能损耗，这就是代码生成（Code Generation）。

向量化：TiDB&CockroachDB

向量化模型最早提出是在 MonerDB-X100（Vectorwise）系统，已成为现代硬件条件下广泛使用的两种高效查询引擎之一。

向量化模型与火山模型的最大差异就是，其中的 Operator 是向量化运算符，是基于列来重写查询处理算法的。所以简单来说，向量化模型是由一系列支持向量化运算的 Operator 组成的执行模型。

看一下向量化模型怎么处理聚合计算：

通过这个执行过程可以发现，向量化模型依然采用了拉取式模型。它和火山模型的唯一区别就是 Operator 的 next() 函数每次返回的是一个向量块，而不是一个元组。向量块是访问数据的基本单元，由固定的一组向量组成，这些向量和列 / 字段有一一对应的关系。

向量处理背后的主要思想是：按列组织数据和计算，充分利用 CPU，把从多列到元组的转化推迟到较晚的时候执行。这种方法在不同的操作符间平摊了函数调用的开销。

向量化模型首先在 OLAP 数据库中采用，与列式存储搭配使用可以获得更好的效果，例如 ClickHouse。

这里定义的分布式数据库都是面向 OLTP 场景的，所以不能直接使用列式存储，但是可以采用折中的方式来实现向量化模型，也就是在底层的 Operator 中完成多行到向量块的转化，上层的 Operator 都是以向量块作为输入。这样改造后，即使是与行式存储结合，仍然能够显著提升性能。在 TiDB 和 CockroachDB 的实践中，性能提升可以达到数倍，甚至数十倍。

向量化运算符示例

以 Hash Join 为例，来看下向量化模型的执行情况。

Hash Join 的执行逻辑，就是两表关联时，以 Inner 表的数据构建 Hash 表，然后以 Outer 表中的每行记录，分别去 Hash 表查找。

Class HashJoin
  Primitives probeHash_, compareKeys_, bulidGather_;
  ...
  int HashJoin::next()
  // 消费构建侧的数据构造 Hash 表，代码省略
  ... 
  // 获取探测侧的元组
  int n = probe->next()
  // 计算 Hash 值
  vec<int> hashes = probeHash_.eval(n)
  // 找到 Hash 匹配的候选元组
  vec<Entry*> candidates = ht.findCandidates(hashes)
  vec<Entry*, int> matches = {}
  // 检测是否匹配
  while(candidates.size() > 0)
    vec<bool> isEqual = compareKeys_.eval(n, candidates)
    hits, candidates = extractHits(isEqual, candidates)
    matches += hits
  // 从 Hash 表收集数据为下个 Operator 缓存
  buildGather_.eval(matches)
  return matches.size()

可以看到这段处理逻辑中的变量都是 Vector，还有事先定义一些专门处理 Vector 的元语（Primitives）。

总的来说，向量化执行模型对火山模型做了针对性优化，在以下几方面有明显改善：

1. 减少虚函数调用数量，提高了分支预测准确性；
2. 以向量块为单位处理数据，利用 CPU 的数据预取特性，提高了 CPU 缓存命中率；
3. 多行并发处理，发挥了 CPU 的并发执行和 SIMD 特性。

代码生成：OceanBase

与向量化模型并列的另一种高效查询执行引擎就是『代码生成』，这个名字听上去可能有点奇怪，但确实没有更好翻译。代码生成的全称是以数据为中心的代码生成（Data-Centric Code Generation），也被称为编译执行（Compilation）。

在解释『代码生成』前，先来分析一下手写代码和通用性代码的执行效率问题。还是继续使用讲火山模型时提到的例子，将其中 Filter 算子的实现逻辑表述如下：

class Filter(child: Operator, predicate: (Row => Boolean))
  extends Operator {
  def next(): Row = {
    var current = child.next()
    while (current == null || predicate(current)) {
      current = child.next()
    }
    return current
  }
}

如果专门对这个操作编写代码（手写代码），那么大致是下面这样：

var count = 0
for (ss_item_sk in store_sales) {
  if (ss_item_sk == 1000) {
    count += 1
  }
}

在两种执行方式中，手写代码显然没有通用性，但 Databricks 的工程师对比了两者的执行效率，测试显示手工代码的吞吐能力要明显优于火山模型。

手工编写代码的执行效率之所以高，就是因为它的循环次数要远远小于火山模型。而代码生成就是按照一定的策略，通过即时编译（JIT）生成代码可以达到类似手写代码的效果。

此外，代码生成是一个推送执行模型（Push Based），这也有助于解决火山模型嵌套调用虚函数过多的问题。与拉取模型相反，推送模型自底向上地执行，执行逻辑的起点直接就在最底层 Operator，其处理完一个元组之后，再传给上层 Operator 继续处理。

Hyper 是一个深入使用代码生成技术的数据库，Hyper 实现的论文（Thomas Neumann (2011)）中有一个例子，这里用来理解它的执行过程。

要执行的查询语句是这样的：

select * from R1,R3, 
(select R2.z,count(*) 
  from R2 
  where R2.y=3 
  group by R2.z) R2 
where R1.x=7 and R1.a=R3.b and R2.z=R3.c

SQL 解析后会得到一棵查询树，就是下图的左侧的样子，可以找到 R1、R2 和 R3 对应的是三个分支。

要获得最优的 CPU 执行效率，就要使数据尽量不离开 CPU 的寄存器，这样就可以在一个 CPU 流水线（Pipeline）上完成数据的处理。但是，查询计划中的 Join 操作要生成 Hash 表加载到内存中，这个动作使数据必须离开寄存器，称为物化（Materilaize）。所以整个执行过程会被物化操作分隔为 4 个 Pipeline。而像 Join 这种会导致物化操作的 Operator，在论文称为 Pipeline-breaker。

通过即时编译生成代码得到对应 Piepline 的四个代码段，可以表示为下面的伪码：

代码生成消除了火山模型中的大量虚函数调用，让大部分指令可以直接从寄存器取数，极大地提高了 CPU 的执行效率。

代码生成的基本逻辑清楚了，但它的工程实现还是挺复杂的，所以会有不同粒度的划分。比如，如果是整个查询计划的粒度，就会称为整体代码生成（Whole-Stage Code Generation），这个难度最大；相对容易些的是代码生成应用于表达式求值（Expression Evaluation），也称为表达式代码生成。在 OceanBase 2.0 版本中就实现了表达式代码生成。

小结

1. 火山模型自 1990 年提出后，是长期流行的查询执行模型，至今仍在 Oracle、MySQL 中使用。但面对海量数据时，火山模型有 CPU 使用率低的问题，性能有待提升。
2. 火山模型仍有一些优化空间，比如运算符融合，可以适度减少虚函数调用，但提升空间有限。学术界提出的两种优化方案是向量化和代码生成。
3. 简单来说，向量化模型就是一系列向量化运算符组成的执行模型。向量化模型首先在 OLAP 数据库和大数据领域广泛使用，配合列式存储取得很好的效果。虽然 OLTP 数据库的场景不适于列式存储，但将其与行式存储结合也取得了明显的性能提升。
4. 代码生成是现代编译器与 CPU 结合的产物，也可以大幅提升查询执行效率。代码生成的基础逻辑是，针对性的代码在执行效率上必然优于通用运算符嵌套。代码生成根据算法会被划分成多个在 Pipeline 执行的单元，提升 CPU 效率。代码生成有不同的粒度，包括整体代码生成和表达式代码生成，粒度越大实现难度越大。

向量化和代码生成是两种高效查询模型，并没有最先出现在分布式数据库领域，反而是在 OLAP 数据库和大数据计算领域得到了更广泛的实践。ClickHouse 和 Spark 都同时混用了代码生成和向量化模型这两项技术。目前 TiDB 和 CockroachDB 都应用向量化模型，查询性能得到了一个数量级的提升。OceanBase 中则应用了代码生成技术优化了表达式运算。

RUM 猜想

RUM 猜想来自论文 "Designing Access Methods: The RUM Conjecture"（Manos Athanassoulis et al.(2016)），同时被 SIGMOD 和 EDBT 收录。它说的是，对任何数据结构来说，在 Read Overhead（读）、Update Overhead（写） 和 Memory or Storage Overhead（存储） 中，同时优化两项时，需要以另一项劣化作为代价。论文用一幅图展示了常见数据结构在这三个优化方向中的位置。

在这张图中，可以看到两个非常熟悉的数据结构 B-Tree 和 LSM，它们被用于分布式数据库的存储引擎中，前者（实际是 B+Tree，B-Tree 的变体）主要用于 PGXC，后者则主要用于 NewSQL。这是不是代表 PGXC 就是要针对读操作，而 NewSQL 是针对写操作呢？并没有这么简单，还是要具体分析数据结构的使用过程。

存储结构

B+Tree

B+Tree 是对读操作优化的存储结构，能够支持高效的范围扫描，叶节点之间保留链接并且按主键有序排列，扫描时避免了耗时的遍历树操作。它是单体数据库广泛使用的数据结构。

用一个例子来演示下 MySQL 数据库的 B+Tree 写操作过程：

下面这张图中展示了一棵高度为 2 的 B+Tree，数据存储在 5 个页表中，每页可存放 4 条记录。为了方便理解，略去了叶子节点指向数据的指针以及叶子节点之间的顺序指针。

B+Tree 由内节点（InterNode）和叶节点（LeafNode）两类节点构成，前者仅包含索引信息，后者则携带了指向数据的指针。当插入一个索引值为 70 的记录，由于对应页表的记录已满，需要对 B+Tree 重新排列，变更其父节点所在页表的记录，并调整相邻页表的记录。完成重新分布后的效果如下：

在这个写入过程中存在两个问题：

1、写放大

本来仅需要一条写入记录（黄色标注），实际上更新了 3 个页表中的 7 条索引记录，额外的 6 条记录（绿色标注）是为了维护 B+Tree 结构产生的写放大。

为了度量写放大的程度，相关研究中引入了写放大系数（Write Amplification Factor，WAF）这个指标，就是指实际写入磁盘的数据量和应用程序要求写入数据量之比。对于空间放大有类似的度量单位，也就是空间放大系数（Space Amplification Factor, SAF）。

这个例子中的 WAF 是 7。

2、存储不连续

虽然新增叶节点会加入到原有叶节点构成的有序链表中，整体在逻辑上是连续的，但是在磁盘存储上，新增页表申请的存储空间与原有页表很可能是不相邻的。这样，在后续包含新增叶节点的查询中，将会出现多段连续读取，磁盘寻址的时间将会增加。

也就是说，虽然 B+Tree 结构是为读取做了优化，但如果进行大量随机写还是会造成存储的碎片化，从而导致写放大和读放大。

填充因子

填充因子（Factor Fill）是一种常见的优化方法，它的原理就是在页表中预留一些空间，这样不会因为少量的数据写入造成树结构的大幅变动。但填充因子的设置也很难拿捏，过大则无法解决写放大问题；过小会造成页表数量膨胀，增大对磁盘的扫描范围，降低查询性能。

相对于 PGXC，NewSQL 风格分布式数据库的底层存储引擎则主要采用 LSM-Tree。

LSM-Tree

LSM-Tree（Log Structured-Merge Tree）由 Patrick O’Neil 在 1996 年的 同名论文中首先提出。而后 Google 在 Bigtable（Fay Chang et al.(2008)）中使用了这个模型，它的大致处理过程如下图所示：

系统接收到写操作后会记录日志（Tablet Log）并将数据写入内存（Memtable），这时写操作就可以返回成功了。而在系统接收到读操作时，会在内存和磁盘文件中查找对应的数据。

LSM 是分成三步完成了数据的落盘：

1. 第一步是写入 Memtable，同时记录 Tablet Log；
2. 当 Memtable 的数据达到一定阈值后，系统会把其冻结并将其中的数据顺序写入磁盘上的有序文件（Sorted String Table，SSTable）中，这个操作被称为 Flush；当然，执行这个动作的同时，系统会同步创建一个新的 Memtable，处理写入请求。
3. 根据第二步的处理逻辑，Memtable 会周期性地产生 SSTable。当满足一定的规则时，这些 SSTable 会被合并为一个大的 SSTable。这个操作称为 Compact。

与 B+Tree 的最大不同是 LSM 将随机写转换为顺序写，这样提升了写入性能。另外，Flush 操作不会像 B+Tree 那样产生写放大。

真正的写放大就发生在 Compact 这个动作上。Compact 有两个关键点，一是选择什么时候执行，二是要将哪些 SSTable 合并成一个 SSTable。这两点加起来称为『合并策略』。

刚刚在例子中描述的就是一种合并策略，称为 Size-Tiered Compact Strategy，简称 Tiered。BigTable 和 HBase 都采用了 Tiered 策略。它的基本原理是，每当某个尺寸的 SSTable 数量达到既定个数时，将所有 SSTable 合并成一个大的 SSTable。这种策略的优点是比较直观，实现简单，但是缺点也很突出。下面从 RUM 的三个角度来分析下：

1、读放大

执行读操作时，由于单个 SSTable 内部是按照 Key 顺序排列的，那么查找方法的时间复杂度就是 O(logN)。因为 SSTable 文件是按照时间间隔产生的，在 Key 的范围上就会存在交叉，所以每次读操作都要遍历所有 SSTable。如果有 M 个 SSTable，整体时间复杂度就是 O(MlogN)。执行 Compact 后，时间复杂度降低为 O(log(MN))。在只有一个 SSTable 时，读操作没有放大。

2、写放大

Compact 会降低读放大，但却带来更多的写放大和空间放大。其实 LSM 只是推迟了写放大，短时间内，可以承载大量并发写入，但如果是持续写入，则需要一部分 I / O 开销用于处理 Compact。

如果是采用 Tiered 策略，LSM 的写放大比 B+Tree 还严重。此外，Compact 是一个很重的操作，占用大量的磁盘 I / O，会影响同时进行的读操作。

3、空间放大

从空间放大的角度看，Tiered 策略需要有两倍于数据大小的空间，分别存储合并前的多个 SSTable 和合并后的一个 SSTable，所以 SAF 是 2，而 B+Tree 的 SAF 是 1.33。

LSM 还有另一种合并策略，Leveled Compact Strategy，简称 Leveled 策略。

Leveled Compact Strategy

Tiered 策略之所以有严重的写放大和空间放大问题，主要是因为每次 Compact 需要全量数据参与，开销自然就很大。那么如果每次只处理小部分 SSTable 文件，就可以改善这个问题了。

Leveled 就是这个思路，它的设计核心就是将数据分成一系列 Key 互不重叠且固定大小的 SSTable 文件，并分层（Level）管理。同时，系统记录每个 SSTable 文件存储的 Key 的范围。Leveled 策略最先在 LevelDB 中使用，也因此得名。后来从 LevelDB 上发展起来的 RocksDB 也采用这个策略。

接下来，详细说明一下这个处理过程：

1. 第一步处理 Leveled 和 Tiered 是一样的。当内存的数据较多时，就会 Flush 到 SSTable 文件。对应内存的这一层 SSTable 定义为 L0，其他层的文件我们同样采用 Ln 的形式表示，n 为对应的层数。因为 L0 的文件仍然是按照时间顺序生成的，所以文件之间就可能有重叠的 Key。L0 不做整理的原因是为了保证写盘速度。

2. 通常系统会通过指定 SSTable 数量和大小的方式控制每一个层的数据总量。当 L0 超过预定文件数量，就会触发 L0 向 L1 的 Compact。因为在 L0 的 SSTable 中 Key 是交叉的，所以要读取 L0 的所有 SSTable，写入 L1，完成后再删除 L0 文件。从 L1 开始，SSTable 都是保证 Key 不重叠的。

3. 随着 L1 层数据量的增多，SSTable 可能会重新划分边界，目的是保证数据相对均衡的存储。

4. 由于 L1 的文件大小和数量也是受限的，所以随着数据量的增加又会触发 L1 向 L2 的 Compact。因为 L1 的文件是不重叠的，所以不用所有 L1 的文件都参与 Compact，这就延缓了磁盘 I / O 的开销。而 L2 的单个文件容量会更大，通常从 L1 开始每层的存储数据量以 10 倍的速度增长。这样，每次 Ln 到 L(n+1) 的 compact 只会涉及少数的 SSTable，间隔的时间也会越来越长。

说完处理流程，再从 RUM 三个角度来分析下：

1、读放大

因为存在多个 SSTable，Leveled 策略显然是存在读放大的。因为 SSTable 是有序的，如果有 M 个文件，则整体计算的时间复杂度是 O(MlogN)。这个地方还可以优化。通常的方法是在 SSTable 中引入 Bloom Filter（BF），这是一个基于概率的数据结构，可以快速地确定一个 Key 是否存在。这样执行 Get 操作时，先读取每一个 SSTable 的 BF，只有这个 Key 存在才会真的去文件中查找。

那么对于多数 SSTable，时间复杂度是 O(1)。L0 层的 SSTable 无序，所有都需要遍历，而从 L1 层开始，每层仅需要查找一个 SSTable。那么优化后的整体时间复杂度就是 O(X+L-1+logN)，其中 X 是 L0 的 SSTable 数量，L 是层数。

2、写放大

Leveled 策略对写放大是有明显改善的，除了 L0 以外，每次更新仅涉及少量 SSTable。但是 L0 的 Compact 比较频繁，所以仍然是读写操作的瓶颈。

3、空间放大

数据在同层的 SSTable 不重叠，这就保证了同层不会存在重复记录。而由于每层存储的数据量是按照比例递增的，所以大部分数据会存储在底层。因此，大部分数据是没有重复记录的，所以数据的空间放大也得到了有效控制。

分布式数据库的实现

在分布式数据库中，数据存储是在每个数据节点上各自进行的，所以原理和过程是完全一样的。因此，TiDB 和 CockroachDB 干脆直接使用 RocksDB 作为单机存储引擎。在这两个分布式数据库的架构中，RocksDB 都位于 Raft 协议之下，承担具体的数据落地工作。

他们为什么选择 RocksDB 呢？CockroachDB 的官方解释是，他们的选择完全不是因为要考虑 LSM 的写优化能力，而是因为 RocksDB 作为一个成熟的单机存储引擎，可以加速 CockroachDB 的开发过程，而 RocksDB 本身也非常优秀，是他们能找到的最好选择。另一方面，TiDB 虽然没有提到选择一个写优化的存储引擎是否有特殊意义，但同样也认为 RocksDB 是一个非常优秀开源项目，可以满足他们对单机引擎的各种要求。

不过，很有意思的地方是，经过了早期版本的演进，TiDB 和 CockroachDB 不约而同都推出了自己的单机存储引擎。

OceanBase

OceanBase 选择了自研方式，也就没有直接引用 RocksDB，但它的存储模型基本上也是 LSM，也就同样需要面对 Compact 带来的一系列问题。来看看 OceanBase 是怎么优化的。

宏块与微块

在 Compact 过程中，被合并文件中的所有数据都要重写到新文件中。其实，对于那些没有任何修改的数据，这个过程是可以被优化的。

OceanBase 引入了宏块与微块的概念，微块是数据的组织单元，宏块则由微块组成。这样在进行 Compact 操作时，可以在宏块和微块两个级别判断，是否可以复用。如果在这两个级别数据没有发生实质变化，则直接进行块级别的拷贝，这样就省去了更细粒度的数据解析、编码以及计算校验和（Checksum）等操作。

轮转合并

OceanBase 还在多副本基础上设计了轮转合并机制。根据 Raft 协议或者 Paxos 协议，总有多个副本同时存储着最新的数据，那么就可以用多副本来解耦 Compact 操作和同时段的查询操作，避免磁盘 I/O 上的竞争。

它的大致设计思路是这样的，将 Compact 操作放在与 Leader 保持数据同步的 Follower 上执行，而 Leader 节点则保持对外提供查询服务。当 Compact 完成后，改由那个 Follower 对外提供查询服务，Leader 和其他副本则去执行 Compact。

OceanBase 的这两项优化虽然没有降低写放大系数，但却有效减少了 Compact 过程中的 I/O 竞争。

TiDB：WiscKey

OceanBase 的优化还停留在工程层面，那么还有没有更好的理论模型呢?

2016 年真的出现了新的模型，这就是 WiscKey。论文 "WiscKey: Separating Keys from Values in SSD-conscious Storage"（Lanyue Lu et al.(2016)）阐述了这种模型的设计思想。WiscKey 提出的改进是通过将 value 分离出 LSM-Tree 的方法来降低写放大。

WiscKey 的主要设计思想是，在 SSTable 的重写过程中，核心工作是对 Key 进行整理，保证多个 SSTable 的 Key 范围不重叠，且内部有序。而这个过程中 Value 的重写是没有太大价值的，而从实践看，Value 占用的存储空间远远大于 Key。这意味着大量的写操作和空间成本被浪费了。所以 WiscKey 提出将 Value 从 SSTable 中分离出来单独存储，这样就降低了写放大系数。

Value 单独存储的问题是按照 Key 连续读取数据时，对应的 Value 并不是连续存储，磁盘寻址成本增大。而 WiscKey 的设计前提是使用 SSD 替换 HDD，SSD 的随机读写效率接近于顺序读写，所以能够保持较高的整体效率。事实上，过高的写放大也会严重缩短 SSD 的使用寿命。WiscKey 就是针对 SSD 提出的存储模型。

TiDB 的新存储引擎 TiTan 就是受到 WiscKey 的启发，它目标之一就是将 Value 从 LSM-Tree 中分离出来单独存储，以降低写放大。

CockroachDB：Pebble

CockroachDB 的单机存储引擎 Pebble。Pebble 并不是由于 WiscKey 的模型改进，它的出现完全是工程因素。首先是 Go 与 C 之间的调用障碍（CGo barrier）。

CGo barrier

CockroachDB 采用 Go 作为编程语言，而 RocksDB 是由 C++ 编写的。所以 CockroachDB 要面临 Go 到 C 的之间的调用障碍。测试表明，每一次对 RocksDB 的调用都要额外付出 70 纳秒的延迟。这个数字虽然看上去并不大，但是由于 K / V 操作非常频繁，总体成本仍然很可观。CockroachDB 也通过一些设计来降低延迟，比如将多次 K / V 操作合并成一次对 RocksDB 的操作，但是这一方面带来设计的复杂性，另外也无法从根本上解决问题。

值得一提的是，TiDB 也使用了 Go 语言作为主力开发语言，同样面临了这个问题。TiDB 最终是在底层存储 TiVK 放弃 Go 而选择 Rust 的，部分原因就是 Rust 与 C++ 之间的调用成本要低得多。

代码膨胀

CockroachDB 替换存储引擎的另一个原因是，RocksDB 的代码量日益膨胀。早期 RocksDB 的代码行数仅是 30k，而今天已经增加到 350k+。这很大程度是由于 RocksDB 的成功，很多软件选择了 RocksDB 作为存储引擎，包括 MySQL（MyRocks）、Flink 等，这驱动 RocksDB 增加了更丰富的特性，也导致体量越来越大。但这些丰富的特性对 CockroachDB 来说并不是必须的，反而引入了不必要的变更风险。而 Cockraoch 开发的 Pebble，代码行数则仅有 45k，的确是小巧得多了。

所以，总的来说，CockraochDB 替换存储引擎是工程原因，而其中 CGO barrier 的这个问题更像是在偿还技术债。

TiFlash

到这里，分布式数据库下典型的存储引擎就介绍完了，它们都适用于 OLTP 场景，要求在小数据量下具有高效的读写能力。而 OLAP 下的存储引擎则有很大的不同，通常不会对单笔写入有太高的要求，但也有例外，OLAP 存储引擎 TiFlash，由于实时分析的要求，它必须及时落盘来自 TiKV 的数据，同样需要很高的写入速度。

高效写入的秘密就在于它的存储模型 Delta Tree 采用了类似 LSM 的结构。其中的 Delta Layer 和 Stable Layer，分别对应 LSM Tree 的 L0 和 L1，Delta Layer 可以顺序写入。

小结

1. RUM 猜想提出读负载、写负载、空间负载这三者之间只能优化两个目标，另外一个目标只能被弱化。在典型数据结构中，B+Tree 是读取优化，LSM 是写入优化，这两种存储结构正好对应了两种风格分布式数据库的存储引擎。
2. PGXC 和单体数据库采用了 B+Tree，随机写会带来页表分裂和存储不连续，导致写放大和读放大。常用的优化方式是通过填充因子预留页空间。LSM 将随机写转换为顺序写提升了写入速度，但只是延缓了写放大并没有真正减少写放大。如果采用 Tiered 策略，LSM 的写放大和空间放大都高于 B+Tree。不过，LSM 可以很好地控制读放大，读操作的时间复杂度是 O(logN)。
3. Level 策略，降低了写放大和空间放大，同时读操作的成本也没有大幅增加，是一个比较广泛使用的存储模型。RocksDB 采用了这种存储模型，加上优秀的工程实现，被很多软件引用。TiDB 和 CockroachDB 也使用 RocksDB 作为单机存储引擎。OceanBase 在工程层面对 LSM 进行了优化。
4. WiscKey 是对 LSM 的理论模型优化，通过 Key/Value 分离存储的方式降低写放大，但这种设计会增加随机读写，要以使用 SSD 为前提。TiDB 受到 WiscKey 的启发，自研了 TiTan。
5. CockroachDB 也推出了自己的存储引擎 Pebble，主要目的是解决工程问题，包括解决 CGo barrier 问题和避免 Rust 功能膨胀带来的变更风险。

加餐：Scan 操作是否可以使用 Bloom Filter 来加速，如果可以又该如何设计呢？

Bloom Filter 是很有意思的数据结构，通过多个 Hash 函数将一个数值映射到某几个字节上。这样用少量的字节就可以存储大量的数值，同时能快速地判断某个数值是否存在。虽然没有做映射的数值会有一定概率的误报，但可以保证“数值不存在”是绝对准确的，这就是假阳性。

这种模式显然是不能直接支持 Scan 操作的，这是需要将数值做一定的转化。这个方法在 RocksDB 中称为『Prefix Bloom Filter』，也就是取 Key 的左前缀（Prefix）进行判断。因为 K / V 系统是按照 Key 字典序排列的，那就是说相邻的 Key 通常具有相同的 Prefix，这种匹配方式相当于对一组 Key 做了检验，可以更好地适应 Scan 的特点。

学习资料

Goetz Graefe: Volcano, an Extensible and Parallel Query Evaluation System

Peter Boncz et al.: MonetDB/X100: Hyper-Pipelining Query Execution

Sameer Agarwal et al.: Apache Spark as a Compiler: Joining a Billion Rows per Second on a Laptop

Thomas Neumann: Efficiently Compiling Efficient Query Plans for Modern Hardware

Fay Chang et al.: Bigtable: A Distributed Storage System for Structured Data

Lanyue Lu et al.: WiscKey: Separating Keys from Values in SSD-conscious Storage

Manos Athanassoulis et al: Designing Access Methods: The RUM Conjecture

Patrick O’Neil et al.: The Log-Structured Merge-Tree (LSM-Tree)