背景

Bourbon 基于 WiscKey（比 LevelDB 和 RocksDB 更快的 LSM-Tree 存储系统）实现。本文通过对 WiscKey 的实验分析，总结了五条指南。Bourbon 应用了这些指南，将 WiscKey 与学习索引相结合，利用学习索引实现快速查找。

设计与实现

Five learning guidelines

1. Favor learning files at lower levels (生命周期更长)
2. Wait before learning a file (连续的 compaction 会在每一层生成生命周期非常短的新文件)
3. Do not neglect files at higher levels (可以提供多种内部查询方式)
4. Be workload- and data-aware (在不同的场景中查找会有很大差异)
5. Do not learn levels for write-heavy workloads (变化很快)

Beneficial regimes

学习索引只能缩短检索时间。

Bourbon Learning

Bourbon 使用分段线性回归（PLR）对数据进行建模，PLR 在学习和查找过程中开销较低，而且空间开销也很小。Bourbon 可以学习单个 SSTables文件（File Learning）或整个层级（Level Learning）。层级学习对于只读工作负载收益更高，而对于混合工作负载，层级学习的性能不如文件学习。

为了训练 PLR 模型，Bourbon 使用了 Greedy-PLR 算法，一次处理一个数据点，如果数据点不能在不超出定义的误差限制的情况下被添加到当前的线段中，那么将创建一个新的线段，并将数据点添加到其中，最终 Greedy-PLR 生成了一组代表数据的线段。Greedy-PLR 的运行时间与数据点的数量呈线性关系。

Cost-benefit analyzer (CBA)

成本效益分析（Cost-Benefit Analyzer, CBA）的目的是过滤掉不值得学习的生命周期较短的文件。CBA 在同一层级使用之前文件的统计信息。

为了过滤短生命周期文件，Bourbon 在学习文件之前会等待一个时间阈值 $T_{wait}$。对一个文件进行学习的最大耗时约为 40 毫秒，因此 Bourbon 将 $T_{wait}$ 设置为 50 毫秒。但是，学习一个长期存在的文件也可能没有好处。作者实验发现更低层级的文件通常寿命更长，对于有的工作负载和数据集，他们服务的查询操作比更高层级的文件要少得多。因此，除了考虑模型对应的开销以外，还需要考虑模型可能带来的收益。如果一个模型的收益（$B_{model}$）大于构建该模型的开销（$C_{model}$），那么该模型就是有利的。

Estimating the cost ($C_{model}$)

如果假定学习过程发生在后台（有很多空闲的 core），那么 $C_{model}$ 开销就为 0。不过 Bourbon 采取了保守的做法，假设学习线程会对系统产生干扰，导致性能变慢。因此，论文将 $C_{model}$ 开销定义为与 $T_{build}$ 相等，即文件训练 PLR 模型的时间。由于 $T_{build}$ 与文件中数据点的数量成线性比例，我们将 $T_{build}$ 定义为文件中数据点的数量与训练一个数据点的平均时间的乘积。

Estimating the benefit ($B_{model}$)

Bourbon 定义模型带来的收益如下:

$$
B_{model} = (T_b - T_m) * N
$$

• $T_{b}$: 在基线中查找的平均时间
• $T_{m}$: 在模型路径中查找的平均时间
• $N$: 文件在其生命周期内的查找次数

然后又将查询操作又划分成了 negative 和 positive，因为大多数 negative 的查询操作在 filter 处就终止了，所以最终的收益模型为:

$$
B_{model} = ((T_{n.b} - T_{n.m}) * N_n) + ((T_{p.b} - T_{p.m}) * N_p)
$$

• $N_{n}$ & $N_{p}$: negative 和 positive 的查询数量
• $T_{n.b}$ & $T_{p.b}$: 在基线中 negative 和 positive 查找的平均时间
• $T_{n.m}$ & $T_{p.m}$: 在模型路径中 negative 和 positive 查找的平均时间

为了估计查找次数（$N_{n}$ & $N_{p}$）和查找所需时间（$T_{n.b}$ & $T_{p.b}$），CBA 维护了这些文件在其生命周期内和在同一层级上的文件的统计信息（因为统计信息在不同层级之间存在显著差异）。

这些估算在 $T_{wait}$ 期间完成:

• $T_{n.b}$ & $T_{p.b}$: 在 $T_{wait}$ 期间，查询将通过基线路径，这些查询时间用于估计 $T_{n.b}$ 和 $T_{p.b}$
• $T_{n.m}$ & $T_{p.m}$: 通过同一层级所有其他文件的平均值进行估计
• $N_{n}$ & $N_{p}$: CBA 首先获取该层级中其他文件的平均 negative 查找和 positive 查找，然后，将其按 $f = s / s’$ 的倍数进行缩放，其中 $s$ 是文件的大小，$s’$ 是该层级的文件的平均大小

如果 $C_{model} < B_{model}$，文件将会开始训练。如果多个文件同时开始训练，则将它们放在一个最大优先级队列中，从而使收益最大的文件能够先被训练。

未来可能的改进方向包括：

1. 对 $N_{n}$, $N_{p}$, $T_{n.m}$, $T_{p.m}$ 进行更精确的估计
2. 改进计算 $C_{model}$ 开销的方法，使其不仅仅是 $T_{build}$
3. 使用另外的函数对训练队列进行排序，而非 $B_{model} - C_{model}$

Bourbon: Putting it All Together

评估

参考

1. From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees
2. Presentation video at OSDI ‘20
3. Presentation slides at OSDI ‘20

概述

Octopus 通过 NVM + RDMA 实现了分布式文件系统，主要贡献总结如下：

• 提出了基于 RDMA 的新型 I/O 流，它直接访问持久化共享内存池，而无需经过文件系统层层调用，并在客户端主动获取或发送数据以重新平衡服务器和网络负载。
• 利用 RDMA 原语重新设计元数据机制，包括自标识元数据 RPC 来用于低延迟通知，以及收集-调度分布式事务实现低一致性开销。
• 有效地利用了硬件性能，显著优于现有 RDMA 优化的分布式文件系统。

挑战

1. 之前由于存储介质较慢，访问持久化存储介质的开销几乎占据了文件系统操作的全部，软件栈的优化对整体性能的影响微乎其微，所以之前的存储层与网络层往往采用松耦合的设计模式来使得系统更容易理解与实现。而对于 NVM 上的文件系统来说，由于 NVM 的访问时延接近内存，使得软件栈的开销几乎占据了文件系统操作的全部，现在优化软件栈开销成为优化系统最重要的手段。
2. 现有的文件系统利用新硬件高带宽的效率低下。这主要有四个原因：(1)数据在应用缓冲区、文件系统页缓存、网卡缓冲等区域之间来回拷贝，增加了软件开销；(2)服务器每秒需要处理的大量请求，server 端 CPU 成为瓶颈；(3)基于事件驱动模型的传统 RPC 具有相对较高的延迟；(4)分布式文件系统中使用到的分布式事务等需要多次的网络来回，处理逻辑较为复杂，使得分布式文件系统用在一致性上的开销较大。

设计

总体架构

Octopus 文件系统数据分散在集群节点中，一个文件根据路径名使用一致性哈希保存在一个节点中，文件没有做冗余，RDMA 与存储层紧耦合设计。
每个节点的 NVM 分为私有部分和共享部分。私有部分保存该节点文件的元数据，只允许本节点内访问，客户端通过 RPC 访问；共享部分保存该节点中文件的数据，客户端可以通过 RDMA 单边原语直接读写。Octopus 使用 RDMA write-with-imm 进行 RPC。

数据布局

Octopus 每个节点的 NVM 划分为 6 个区域，每个区域是共享的或私有的。这六个区域的内容为：

• Super Block：用于存储文件系统的超级块
• Message Pool：元数据 RPC 的通信缓冲区
• Metadata Index Zone：使用哈希表保存文件索引
• Metadata Zone：具体的文件元数据保存区域
• Data Zone：文件数据的保存区域
• Log Zone：事务日志区域

High-Throughput Data I/O

Octopus 引入了共享持久化内存池来减少数据拷贝以获得更高的带宽，并且在客户端主动执行 I/O 来重新平衡服务器和网络开销以获得更高的吞吐量。

Shared Persistent Memory Pool

如图所示，GlusterFS 里同一个数据在传输过程中拷贝了 7 次，Octopus 利用共享持久化内存池取消层次抽象，以及通过 RDMA 取消缓存，将数据拷贝降低到了 4 次。

Client-Active Data I/O

Octopus 提出了 Client-Active Data I/O 数据访问模式，充分发挥了 RDMA 的优势，降低了服务端 CPU 的负载。

传统的数据交互为 Server-Active Data I/O 方式，如图中的(a)所示，客户端给服务端发送数据访问请求，服务端查找到数据的位置后读取对应的数据，并把最终的数据返回给客户端。而 Client-Active Data I/O 方式则与此不同，如图中的(b)所示，客户端使用自标识元数据 RPC 发送读写请求和访问元数据，然后根据元数据信息使用 RDMA Read/Write 直接读写文件数据。
Client-Active 与 Server-Active 相比，服务端 CPU 执行一个请求的操作较少，将读数据操作转移给了客户端进行，从而降低了服务端 CPU 的负载。

Low-Latency Metadata Access

RDMA 为远程数据访问提供微秒级访问延迟。为了在文件系统发挥这一优势，Octopus 通过合并 RDMA 写入和原子原语重构了元数据 RPC 和分布式事务。

Self-identified metadata RPC

RDMA 具有低延迟高带宽的优势，在 RPC 中使用 RDMA 能够提高吞吐量。以往的 RDMA RPC 大多使用双边 RDMA 原语，而双边 RDMA 具有相对较高的延迟和较低的吞吐量，减小了 RDMA 的优势。而单边 RDMA 原语不会在完成时通知 CPU，若使用单边 RDMA 进行 RPC，服务器需要有单独的线程轮询消息缓冲区，使 CPU 的负载进一步增大。
为了保持 RDMA 低延迟的优势并减少 CPU 的负载，Octopus 提出了 Self-identified metadata RPC（自标识元数据 RPC）。自标识元数据 RPC 使用 RDMA write_with_imm 命令将发送者的标识信息附加到 RDMA 请求中。write_with_imm 与传统的 RDMA Write 相比有以下两点不同：(1) 它能够在消息中携带一个立即数；(2)它能够在服务器网卡接收到该请求后立即通知服务器 CPU，这会消耗服务器的 QP 中的一个 Recv WR。因此，使用 write_with_imm 能够让服务器及时收到 RPC 请求，且无需 CPU 进行轮询。立即数字段中附加有客户端标识符 node_id 和客户端接收缓冲区的 offset。node_id 可帮助服务器定位对应消息而无需扫描整个缓冲区。请求处理完成之后，服务器使用 RDMA Write 原语将数据返回到标识符为 node_id 的客户端中偏移量地址 offset 处。

Collect-Dispatch Transaction

在文件系统中，某些操作可能会使用分布式事务进行，如 mkdir，mknod，rmnod 和 rmdir 等等。这些操作需要在多个服务器之间原子性地更新元数据。在之前的分布式文件系统中，往往使用两阶段提交（2PC）完成事务操作。然而两阶段提交由于其分布式的日志以及对锁和日志的协调而导致高昂的开销。
Octopus 设计了一个新的分布式事务协议：Collect-Dispatch Transaction，该协议分为收集阶段（Collect Phase）和分发阶段（Dispatch Phase）。该事务协议利用了 RDMA 原语进行服务器间的交互，关键思想在于两个方面，分别是崩溃一致性和并发控制：

1. 带有远程更新的本地日志来实现崩溃一致性。在收集阶段，Octopus 从参与者收集读写集合，并在协调者中执行本地事务，记录日志。由于参与者不需要保留日志记录，因此无需为协调者和参与者之间的持久化日志进行复杂的协商，从而减少了协议的开销。在分发阶段，协调者使用 RDMA write 将更新的写集合分发给参与者，并使用 RDMA atomic 原语释放相应的锁，而不涉及到参与者 CPU。
2. 混合使用 GCC 和 RDMA 锁来实现并发控制。在 Collect-Dispatch 事务中，协调者和参与者使用 GCC 的 Compare-and-Swap 命令在本地添加锁。解锁时，协调者使用 GCC 的 Compare-and-Swap 命令释放本地锁，并使用 RDMA 的 Compare-and-Swap 命令释放远端每个参与者的锁，解锁操作不涉及到参与者的 CPU，因此优化了解锁阶段。

总的来说，Collect-Dispatch Transaction 需要一次 RPC（COLLECT-REQ 和 WRITE-SET）、一次 RDMA Write（UPDATE WRITESET）和一次 RDMA Atomic（REMOTE UNLOCK），而两阶段提交需要两次 RPC。Collect-Dispatch Transaction 与 2PC 相比具有较低的开销，这是因为：(1) 一次 RPC 比一次 RDMA Write/Atomic 原语具有更高的延迟；(2) RDMA Write/Atomic 原语不需要服务端 CPU 的介入。

总结

Octopus 其核心思想是 RDMA 与 NVM 紧耦合设计，设计了一系列机制来实现高吞吐量的数据 I/O 以及低延迟的元数据访问。但在分布式方面该文件系统没有做冗余，也没有考虑负载均衡等内容，只是通过一致性哈希将数据分散到不同节点上。

参考

1. Lu, Youyou, et al. “Octopus: An RDMA-Enabled Distributed Persistent Memory File System.” USENIX ATC ’17 Proceedings of the 2017 USENIX Conference on Usenix Annual Technical Conference, 2017, pp. 773–785.

RDMA（Remote Direct Memory Access）指的是远程直接内存访问，这是一种通过网络在两个应用程序之间搬运缓冲区里的数据的方法。

• Remote：数据通过网络与远程机器间进行数据传输。
• Direct：没有内核的参与，有关发送传输的所有内容都卸载到网卡上。
• Memory：在用户空间虚拟内存与网卡直接进行数据传输不涉及到系统内核，没有额外的数据移动和复制。
• Access：send、receive、read、write、atomic 等操作。

RDMA 与传统的网络接口不同，因为它绕过了操作系统内核。这使得实现了 RDMA 的程序具有如下特点：

1. 绝对的最低时延
2. 最高的吞吐量
3. 最小的 CPU 足迹 （也就是说，需要 CPU 参与的地方被最小化）

RDMA 工作原理

RDMA 通信过程中，发送和接收，读/写操作中，都是网卡直接和参与数据传输的已经注册过的内存区域直接进行数据传输，速度快，不需要 CPU 参与，RDMA 网卡接替了 CPU 的工作，节省下来的资源可以进行其它运算和服务。

RDMA 的工作过程如下:

1. 当一个应用执行 RDMA 读或写请求时，不执行任何数据复制。在不需要任何内核内存参与的条件下，RDMA 请求从运行在用户空间中的应用中发送到本地网卡。
2. 网卡读取缓冲的内容，并通过网络传送到远程网卡。
3. 在网络上传输的 RDMA 信息包含目标机器虚拟内存地址和数据本身。请求完成可以完全在用户空间中处理（通过轮询用户空间的 RDMA 完成队列）。RDMA 操作使应用可以从一个远程应用的内存中读数据或向这个内存写数据。

因此，RDMA 可以简单理解为利用相关的硬件和网络技术，网卡可以直接读写远程服务器的内存，最终达到高带宽、低延迟和低资源利用率的效果。应用程序不需要参与数据传输过程，只需要指定内存读写地址，开启传输并等待传输完成即可。

RDMA 数据传输

1. RDMA Send/Recv
   跟 TCP/IP 的 send/recv 是类似的，不同的是 RDMA 是基于消息的数据传输协议（而不是基于字节流的传输协议），所有数据包的组装都在 RDMA 硬件上完成的，也就是说 OSI 模型中的下面 4 层（传输层，网络层，数据链路层，物理层）都在 RDMA 硬件上完成。

2. RDMA Read
   RDMA 读操作本质上就是 Pull 操作，把远程系统内存里的数据拉回到本地系统的内存里。

3. RDMA Write
   RDMA 写操作本质上就是 Push 操作，把本地系统内存里的数据推送到远程系统的内存里。

4. RDMA Write with Immediate Data（支持立即数的 RDMA 写操作）
   支持立即数的 RDMA 写操作本质上就是给远程系统 Push 带外数据，这跟 TCP 里的带外数据是类似的。可选地，Immediate 4 字节值可以与数据缓冲器一起发送。该值作为接收通知的一部分呈现给接收者，并且不包含在数据缓冲器中。

RDMA 编程基础

使用 RDMA，我们需要有一张支持 RDMA 通信（即实现了 RDMA 引擎）的网卡。我们把这种卡称之为 HCA（Host Channel Adapter，主机通道适配器）。通过 PCIe（peripheral component interconnect express）总线， 适配器创建一个从 RDMA 引擎到应用程序内存的通道。一个好的 HCA 将执行的 RDMA 协议所需要的全部逻辑都在硬件上予以实现。这包括分组，重组以及流量控制和可靠性保证。因此，从应用程序的角度看，只负责处理所有缓冲区即可。

如上图所示，在 RDMA 编程中我们使用命令通道调用内核态驱动建立数据通道，该数据通道允许我们在搬运数据的时候完全绕过内核。一旦建立了这种数据通道，我们就能直接读写数据缓冲区。建立数据通道的 API 是一种称之为 verbs 的 API。verbs API 是由一个叫做 Open Fabrics Enterprise Distribution（OFED）的 Linux 开源项目维护的。

关键概念

RDMA 操作开始于操作内存。当你在操作内存的时候，就是告诉内核这段内存“名花有主”了，主人就是你的应用程序。于是，你告诉 HCA，就在这段内存上寻址，赶紧准备开辟一条从 HCA 卡到这段内存的通道。我们将这一动作称之为注册一个内存区域 MR（Memory Region）。注册时可以设置内存区域的读写权限（包括 local write，remote read，remote write，atomic，and bind）。调用 Verbs API ibv_reg_mr 即可实现注册 MR，该 API 返回 MR 的 remote 和 local key。local key 用于本地 HCA 访问本地的内存。remote key 是用于提供给远程 HCA 来访问本地的内存。一旦 MR 注册完毕，我们就可以使用这段内存来做任何 RDMA 操作。在下面的图中，我们可以看到注册的内存区域（MR）和被通信队列所使用的位于内存区域之内的缓冲区（buffer）。

RDMA 通信基于三条队列 SQ（Send Queue），RQ（Receive Queue）和 CQ（Completion Queue）组成的集合。其中， 发送队列（SQ）和接收队列（RQ）负责调度工作，他们总是成对被创建，称之为队列对 QP（Queue Pair）。当放置在工作队列上的指令被完成的时候，完成队列（CQ）用来发送通知。

当用户把指令放置到工作队列的时候，就意味着告诉 HCA 那些缓冲区需要被发送或者用来接受数据。这些指令是一些小的结构体，称之为工作请求 WR（Work Request）或者工作队列元素 WQE（Work Queue Element）。一个 WQE 主要包含一个指向某个缓冲区的指针。一个放置在发送队列（SQ）里的 WQE 中包含一个指向待发送的消息的指针；一个放置在接受队列里的 WQE 里的指针指向一段缓冲区，该缓冲区用来存放待接受的消息。

RDMA 是一种异步传输机制。因此我们可以一次性在工作队列里放置好多个发送或接收 WQE。HCA 将尽可能快地按顺序处理这些 WQE。当一个 WQE 被处理了，那么数据就被搬运了。一旦传输完成，HCA 就创建一个状态为成功的完成队列元素 CQE（Completion Queue Element）并放置到完成队列（CQ）中去。如果由于某种原因传输失败，HCA 也创建一个状态为失败的 CQE 放置到（CQ）中去。

简单示例（Send/Recv）

第 1 步：系统 A 和 B 都创建了他们各自的 QP 和 CQ，并为即将进行的 RDMA 传输注册了相应的内存区域（MR）。系统 A 识别了一段缓冲区，该缓冲区的数据将被搬运到系统 B 上。系统 B 分配了一段空的缓冲区，用来存放来自系统 A 发送的数据。

第 2 步：系统 B 创建一个 WQE 并放置到它的接收队列（RQ）中。这个 WQE 包含了一个指针，该指针指向的内存缓冲区用来存放接收到的数据。系统 A 也创建一个 WQE 并放置到它的发送队列（SQ）中去，该 WQE 中的指针执行一段内存缓冲区，该缓冲区的数据将要被传送。

第 3 步：系统 A 上的 HCA 总是在硬件上干活，看看发送队列里有没有 WQE。HCA 将消费掉来自系统 A 的 WQE，然后将内存区域里的数据变成数据流发送给系统 B。当数据流开始到达系统 B 的时候，系统 B 上的 HCA 就消费来自系统 B 的 WQE，然后将数据放到该放的缓冲区上去。在高速通道上传输的数据流完全绕过了操作系统内核。

注：WQE 上的箭头表示指向用户空间内存的指针（地址）。receive/send 模式下，通信双方需要事先准备自己的 WQE（WorkQueue），HCA 完成后会写（CQ）。

第 4 步：当数据搬运完成的时候，HCA 会创建一个 CQE。这个 CQE 被放置到完成队列（CQ）中，表明数据传输已经完成。HCA 每消费掉一个 WQE，都会生成一个 CQE。因此，在系统 A 的完成队列中放置一个 CQE，意味着对应的 WQE 的发送操作已经完成。同理，在系统 B 的完成队列中也会放置一个 CQE，表明对应的 WQE 的接收操作已经完成。如果发生错误，HCA 依然会创建一个 CQE。在 CQE 中，包含了一个用来记录传输状态的字段。

在 IB 或 RoCE 中，传送一个小缓冲区里的数据耗费的总时间大约在 1.3µs。通过同时创建很多 WQE, 就能在 1 秒内传输存放在数百万个缓冲区里的数据。

RDMA 操作细节

在 RDMA 传输中，Send/Recv 是双边操作，即需要通信双方的参与，并且 Recv 要先于 Send 执行，这样对方才能发送数据，当然如果对方不需要发送数据，可以不执行 Recv 操作，因此该过程和传统通信相似，区别在于 RDMA 的零拷贝网络技术和内核旁路，延迟低，多用于传输短的控制消息。

Write/Read 是单边操作，顾名思义，读/写操作是一方在执行，在实际的通信过程中，Write/Read 操作是由客户端来执行的，而服务器端不需要执行任何操作。RDMA Write 操作中，由客户端把数据从本地 buffer 中直接 push 到远程 QP 的虚拟空间的连续内存块中（物理内存不一定连续），因此需要知道目的地址（remote addr）和访问权限（remote key）。RDMA Read 操作中，是客户端直接到远程的 QP 的虚拟空间的连续内存块中获取数据 pull 到本地目的 buffer 中，因此需要远程 QP 的内存地址和访问权限。单边操作多用于批量数据传输。

可以看出，在单边操作过程中，客户端需要知道远程 QP 的 remote addr 和 remote key，而这两个信息是可以通过 Send/Recv 操作来交换的。

RDMA 单边操作（RDMA READ/WRITE）

READ 和 WRITE 是单边操作，只需要本端明确信息的源和目的地址，远端应用不必感知此次通信，数据的读或写都通过 RDMA 在网卡与应用 Buffer 之间完成，再由远端网卡封装成消息返回到本端。

对于单边操作，以存储网络环境下的存储为例，READ 流程如下：

1. 首先 A、B 建立连接，QP 已经创建并且初始化。
2. 数据被存档在 B 的 buffer 地址 VB，注意 VB 应该提前注册到 B 的网卡（并且它是一个 memory region），并拿到返回的 remote key，相当于 RDMA 操作这块 buffer 的权限。
3. B 把数据地址 VB，key 封装到专用的报文传送到 A，这相当于 B 把数据 buffer 的操作权交给了 A。同时 B 在它的 WQ 中注册进一个 WR，以用于接收数据传输的 A 返回的状态。
4. A 在收到 B 的送过来的数据 VB 和 remote key 后，网卡会把它们连同自身存储地址 VA 到封装 RDMA READ 请求，将这个消息请求发送给 B，这个过程 A、B 两端不需要任何软件参与，就可以将 B 的数据存储到 A 的 VA 虚拟地址。
5. A 在存储完成后，会向 B 返回整个数据传输的状态信息。

WRITE 流程与 READ 类似。单边操作传输方式是 RDMA 与传统网络传输的最大不同，只需提供直接访问远程的虚拟地址，无须远程应用参与其中，这种方式适用于批量数据传输。

RDMA 双边操作（RDMA SEND/RECEIVE）

RDMA 中 SEND/RECEIVE 是双边操作，即必须要远端的应用感知参与才能完成收发。在实际中，SEND/RECEIVE 多用于连接控制类报文，而数据报文多是通过 READ/WRITE 来完成的。

对于双边操作为例，主机 A 向主机 B（下面简称 A、B）发送数据的流程如下：

1. 首先，A 和 B 都要创建并初始化好各自的 QP，CQ。
2. A 和 B 分别向自己的 WQ 中注册 WQE，对于 A，WQ = SQ，WQE 描述指向一个等到被发送的数据；对于 B，WQ = RQ，WQE 描述指向一块用于存储数据的 Buffer。
3. A 的网卡异步调度轮到 A 的 WQE，解析到这是一个 SEND 消息，从 buffer 中直接向 B 发出数据。数据流到达 B 的网卡后，B 的 WQE 被消耗，并把数据直接存储到 WQE 指向的存储位置。
4. A、B 通信完成后，A 的 CQ 中会产生一个完成消息 CQE 表示发送完成。与此同时，B 的 CQ 中也会产生一个完成消息表示接收完成。每个 WQ 中 WQE 的处理完成都会产生一个 CQE。

双边操作与传统网络的底层 Buffer Pool 类似，收发双方的参与过程并无差别，区别在零拷贝、kernel bypass，实际上对于 RDMA，这是一种复杂的消息传输模式，多用于传输短的控制消息。

参考

1. RDMA 简介与编程基础
2. RDMA技术详解（一）：RDMA 概述
3. RDMA技术详解（二）：RDMA Send Receive操作

背景

论文基于 Orca 对非递归的 CTE 进行了形式化表达和优化，贡献总结如下：

• 在查询中使用 CTE 的上下文中优化 CTE
• 对于查询中的每个 CTE 引用，CTE 不会每次重新优化，仅在需要的时候才进行，例如下推 fitlers 或者 sort 操作
• 基于 cost 来决定是否对 CTE 进行内联
• 减少 plan 的搜索空间，加速查询执行，包括下推 predicates 到 CTE，如果 CTE 被引用一次则始终内联，消除掉没有被引用的 CTE
• 避免死锁，保证 CTE producer 在 CTE consumer 之前执行

REPRESENTATION OF CTEs

1. CTEProducer：一个 CTE 定义对应一个 CTEProducer
2. CTEConsumer：query 中引用 CTE 的地方
3. CTEAnchor：query 中定义 CTE 的 node，CTE 只能被该 CTEAnchor 的子树中引用
4. Sequence：按序执行它的孩子节点，先执行左节点，再执行右节点，并把右节点做为返回值

对于此查询：

1
2
3

WITH v AS (SELECT i_brand FROM item WHERE i_color = ’red’)
SELECT * FROM v as v1, v as v2
WHERE v1.i_brand = v2.i_brand;

它的 Logical representation 如下所示：

它的 Execution plans 如下所示：

PLAN ENUMERATION

CTE 是否内联需要取决于 cost，因此需要枚举出 CTE 在不同引用地方内联前后的计划代价。Orca 中定义了 Memo，下图是初始的逻辑查询在 Memo 中的结构，每个编号就是一个 Memo Group：

Transformation Rules

Transformation Rules 可以看做 Memo Group 一个输入（或者一个函数），Memo Group 根据这个规则展开产生另一些 expression 放在同一个 Memo Group 中。对于每个 CTE，我们生成内联或不内联 CTE 的备选方案。

• 第一条规则应用于 CTEAnchor 运算符。它在 Group 0 中生成一个 Sequence 操作符，这样序列的左节点就是表示 CTE 定义的整个 Plan Tree —— 根据需要创建尽可能多的新 Group (Group 4、5和6) —— 序列的右节点就是 CTEAnchor (Group 1) 的原始节点。

• 第二条规则也应用于 CTEAnchor，生成 Group 0 中的 NoOp 运算符，其孩子节点是 CTEAnchor 的孩子节点（Group 1）。

• 第三条规则应用于 CTEConsumer 运算符，生成 CTE 定义的副本，该副本与 CTEConsumer 属于同一 Group。例如，Group 2 中的 CTEConsumer，添加了 CTE 定义 Select 操作符，并将其子操作符 TableScan 添加到新Group（Group 7）。

该方法产生的 Plan Tree 的组合中并不都是有效的，比如：

a 和 b 都没有 CTEProducer；c 有一个 CTEProducer，没有 CTEConsumer；d 中的 Plan 是有效的，但是只有一个 CTEConsumer 对应于包含的 CTEProducer，是一个失败的 Plan。

通过 Memo 的机制来表达不同的 Plan，基于 cost 选择是否内联。在一个 query 中，CTE 可能有的内联，而有的不内联。内联的好处是能进行普通 query 的优化，比如：下推 predicates，distribution，sorting 等。例如：

CTEConsumer 上游有 predicate: i_color=’red’，Orca在默认情况下会将谓词下推，使其从表达式 c 变为表达式 d。

Avoiding Invalid Plans

上述产生的 Plan Tree 会很多，所以需要裁剪掉一些无效的 Plan，例如，使用了 CTEConsumer 却没有 CTEProducer。裁剪算法如下：

CTESpec 表示一个 CTE 的属性对(id, type)，比如：(1, ‘c’)，cteid = 1，type 是 CTEConsumer。该算法简单来说就是遍历 Tree，检查 CTEConsumer 和 CTEProduct 是否配对。具体描述如下：

1. 先计算自身的 CTESpec；
2. 遍历所有子节点：
   1. 计算对于该子节点的 CTESpec 的 Request，输入是：前面兄弟节点以及父节点的 specList，来自父节点的 reqParent，得到该子节点应该满足的 reqChild；
   2. 子节点调用该函数 DeriveCTEs(child, reqChild)，递归返回子节点的有效的 CTESpecs，即 specChild；
   3. 把子节点 DeriveCTE 返回的 specChild 追加到 specList。如果发现有一对 CTEProducer 和 CTEConsumer就从 specList 中去除掉。
3. 对比遍历所有子节点后得到的 specList 与传入的 reqParent 是否 match。如果匹配，则返回当前的 specList。

Optimizations Across Consumers

上述算法可以枚举出所有 CTE 是否内联的 Plan，另外还有一些其他优化 CTE 的方法。

Predicate Push-down

1
2
3
4
5
6

WITH v as (SELECT i_brand, i_color FROM item
           WHERE i_current_price < 50)
SELECT * FROM v v1, v v2
WHERE v1.i_brand = v2.i_brand
AND v1.i_color = ’red’
AND v2.i_color = ’blue’;

把一个 CTEProducer 对应所有的 CTEConsumer 的 predicates，下推到该 CTEProducer 上，条件通过 OR 组合起来，减少物化的数据量。（注意：因为下推到 CTEProducer 的 predicate 是通过 OR 连接的，因此 CTEConsumer 仍然需要执行原来的 predicate。）

Always Inlining Single-use CTEs

1
2
3
4

WITH v as (SELECT i_color FROM item 
WHERE i_current_price < 50)
SELECT * FROM v
WHERE v.i_color = ’red’;

如果只有一个 CTEConsumer，则始终内联 CTE。

Elimination of unused CTEs

1
2
3
4

WITH v as (SELECT i_color FROM item 
WHERE i_current_price < 50)
SELECT * FROM item
WHERE item.i_color = ’red’;

CTE v 在上述 query 中没有被使用，这种情况可以消除 CTE。另外，对于如下 query：

1
2
3
4
5
6

WITH v as (SELECT i_current_price p FROM item
           WHERE i_current_price < 50),
     w as (SELECT v1.p FROM v as v1, v as v2
           WHERE v1.p < v2.p)
SELECT * FROM item
WHERE item.i_color = ’red’;

CTE v 被引用了两次，而 CTE w 从未被引用。因此，我们可以消除 w 的定义。并且，这样做去掉了对 v 的唯一引用，这意味着我们还可以消除 v 的定义。

CONTEXTUALIZED OPTIMIZATION

对 CTE 是否内联进行枚举之后，Plan 中不同的 CTEConsumer 可能使用不同的优化方案（内联或不内联、下推等）。

Enforcing Physical Properties

Orca 通过 top-down 发送处理 Memo Group 中的优化请求来优化候选计划。优化请求是一组表达式要满足的 Physical Properties 上的要求，包括 sort order, distribution, rewindability, CTEs 和 data partitioning 等，也可以没有（即 ANY）。下图以 distribution 为例子，CTE 需要在不同的上下文中满足不同的 Physical Properties。

1. Sequence 算子对 CTEProducer 发射 ANY 的 prop 请求，返回 Hashed(i_sk) 的 prop（表 item 按 i_sk 这一列进行哈希分布）；
2. 上述的 prop 发送到右子树中（结合自身 prop 和父节点的 prop），右子树中的 HashJoin 节点的连接条件需要子节点的数据基于 i_brand 哈希分布，发送请求到 group 2 和 group 3 的 CTEConsumer 中，而 CTEConsumer 并不满足 i_brand 哈希分布的要求，而父节点又需要此 prop，这时就需要在两个 CTEConsumer 分别添加 Redistribute 的算子，把数据按 i_brand 进行哈希，这样才能满足 HashJoin 的要求。

与 (a) 相比，(b) 中可以一开始就要求 CTE 按 i_brand 哈希分布，CTEProducer 会发现数据分布不满足要求，然后就可以在 group 5 中添加 Redistribute 的算子，CTEProducer 返回 Hashed(i_brand)，这样 CTEConsumer 就不需要加上 Redistribute 的算子，最终得到一个最优的计划（CTEProducer 只需要计算一遍并保存数据，两个 CTEConsumer 意味着需要读取两遍数据）。

Cost Estimation

CTEProducer 和 CTEConsumer 的 cost 分开计算：

• CTEProducer 的 cost 是 CTE 自身的 cost，加上物化写磁盘的 cost
• CTEConsumer 的 cost 是读取物化结果的 cost，类似 scan 算子

参考

1. El-Helw A, Raghavan V, Soliman M A, et al. Optimization of common table expressions in mpp database systems[J]. Proceedings of the VLDB Endowment, 2015, 8(12): 1704-1715.
2. 《Optimization of Common Table Expressions in MPP Database Systems》论文导读

背景

读写放大

LSM-Tree key-value 存储存在读写放大的问题，例如对于LevelDB来说：

• 写放大：假如每一层的大小是上一层的 10 倍，那么当把 i-1 层中的一个文件合并到 i 层中时，LevelDB 需要读取 i 层中的文件的数量多达 10 个，排序后再将他们写回到 i 层中去。所以这个时候的写放大是 10。对于一个很大的数据集，生成一个新的 SSTable 文件可能会导致 L0-L6 中相邻层之间发生合并操作，这个时候的写放大就是50（L1-L6中每一层是10）。

• 读放大：(1) 查找一个 key-value 对时，LevelDB 可能需要在多个层中去查找。在最坏的情况下，LevelDB 在 L0 中需要查找 8 个文件，在 L1-L6 每层中需要查找 1 个文件，累计就需要查找 14 个文件。(2) 在一个 SSTable 文件中查找一个 key-value 对时，LevelDB 需要读取该文件的多个元数据块。所以实际读取的数据量应该是：index block + bloom-filter blocks + data block。例如，当查找 1KB 的 key-value 对时，LevelDB 需要读取 16KB 的 index block，4KB的 bloom-filter block 和 4KB 的 data block，总共要读取 24 KB 的数据。在最差的情况下需要读取 14 个 SSTable 文件，所以这个时候的写放大就是 24*14=336。较小的 key-value 对会带来更高的读放大。

WiscKey 论文中针对 LevelDB 测试的读写放大数据：

存储硬件

在 SSD 上，顺序和随机读写性能差异不大。对于写操作而言，由于随机写会对 SSD 的寿命造成影响，顺序写的特性应该保留，对于读操作来说，顺序读和随机读的性能测试如下图所示：

每次请求数据的 size 越大，SSD 的随机读与顺序读差距越小，并发数越大，SSD 的随机读与顺序读差距也越小。

WiscKey

WiscKey 包括四个关键思想：

(1) KV 分离，只有 key 在 LSM-Tree 上。
(2) 在 KV 分离后，value 采用顺序追加写，不保序。因此范围查询中，WiscKey 使用并行 SSD 设备的随机读特性查询 value。
(3) 使用 crash-consistency 和 garbage-collection 有效管理 value log。
(4) 通过删除 LSM-Tree 日志而不牺牲一致性来优化性能。

KV 分离

KV 分离的设计要点如下：

• key 存在 LSM-Tree 上。
• value 存在单独的 value log 中。
• 插入/更新数据的时候，首先将 value 追加到value log，然后将 key 插入 LSM-Tree 中。
• 删除数据的时候，只是将 key 在 LSM-Tree 中删除，value log 的数据不需要改变，因为 WiscKey 会有垃圾回收机制处理对应的 value。
• 读取数据时，先读 LSM-Tree，然后读 value log。

KV 分离对应的 Challenges

Parallel Range Query

1. 范围查询时，WiscKey 从 LSM-Tree 中读取多个 key 的元数据信息 <key, address>。
2. 将这些 <key, address> 放入队列。
3. 预读线程（默认32个）会从队列中获取 value 的地址，然后并行读取 value 数据。

Garbage Collection

Value log 结构如图所示，其由 value_entry 组成，每个value_entry 是一个四元组 (key size, value size, key, value)。另外，Value log 有两个指针 head 和 tail，tail 指向 Value log 的起点；head 指向文件的尾部，所有新的数据都将追加到 head 位置。

垃圾回收时，线程将从 tail 指向的位置开始，每次读取一个 chunk 的数据（比如几MB），对于 chunk 中的每一个 value_entry，在 LSM-Tree 中查找 key 以便判断该 value_entry 是否仍然有效。如果有效，则将该条目追加到 head 指针指向的位置，并且需要更新 LSM-Tree 的记录，因为 value 的地址已经变了；如果无效，则将其舍弃。

同时，为了避免出现数据不一致（如在垃圾回收过程中发生了 crash），需要保证在释放对应的存储空间之前追加写入的新的有效 value 和新的 tail 指针持久化到了设备上。具体的步骤如下：

• 垃圾回收在将 value 追加到 vLog 之后，在 vLog 上调用 fsync()
• 同步地将新的 value 地址和 tail 指针地址写入到 LSM-Tree 中。（tail 指针的存储形式为 <‘‘tail’’, tail-vLog-offset>）
• 最后回收 vLog 旧的数据空间

Crash Consistency

1. 如果不能在 LSM-Tree 中查询到对应的 key，那么处理方式和传统的 LSM-Tree 一样，返回空或者 key 不存在，即便其 value 已经写入到了 vLog 文件中，也会对其进行垃圾回收。
2. 如果 LSM-Tree 中存在要查询的 Key，则会进行校验。校验首先校验从 LSM-Tree 中查询到的 value 地址信息是否在有效的 vLog 文件范围内；其次校验该地址对应的 value 上存取的 key 和要查询的 key 是否一致。如果校验失败，则删除 LSM-Tree 中相应 key，并返回 key 不存在。
3. 另外，还可以引入 magic number 或 checksum 来校验 key 和 value 是否匹配。

总结

WiscKey 基于 LevelDB，设计了一个针对 SSD 进行优化的持久化 KV 存储方案，它的核心思想就是将 key 和 value 分离，key 存储在 LSM-Tree 中，value 存储在 value log 中，保留了 LSM-Tree 的优势，减少读写放大，发挥了 SSD 顺序写与并行随机读性能好的优势，但在小 value 场景以及大数据集范围查询下，WiscKey 的性能比 LevelDB 差。

参考

1. Lu L, Pillai T S, Arpaci-Dusseau A C, et al. WiscKey: separating keys from values in SSD-conscious storage[C] 14th USENIX Conference on File and Storage Technologies (FAST 16). 2016: 133-148.
2. LevelDB 源码分析（一）：简介
3. WiscKey: Separating Keys from Values in SSD-conscious Storage

本文对 RocksDB 6.7.3 版本的 WriteImpl 流程进行分析。

概述

RocksDB 写入实现主要在 DBImpl::WriteImpl 中，过程主要分为以下三步：

• 把 WriteBatch 加入队列，多个 WriteBatch 成为一个 WriteGroup
• 将该 WriteGroup 所有的记录对应的日志写到 WAL 文件中
• 将该 WriteGroup 所有的 WriteBatch 中的一条或者多条记录写到内存中的 Memtable 中

其中，每个 WriteBatch 代表一个事务的提交，可以包含多条操作，可以通过调用 WriteBatch::Put/Delete 等操作将对应多条的 key/value 记录加入 WriteBatch 中。

源码分析

WriteThread::JoinBatchGroup

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

static WriteThread::AdaptationContext jbg_ctx("JoinBatchGroup");
void WriteThread::JoinBatchGroup(Writer* w) {
  TEST_SYNC_POINT_CALLBACK("WriteThread::JoinBatchGroup:Start", w);
  assert(w->batch != nullptr);

  bool linked_as_leader = LinkOne(w, &newest_writer_);

  if (linked_as_leader) {
    SetState(w, STATE_GROUP_LEADER);
  }

  TEST_SYNC_POINT_CALLBACK("WriteThread::JoinBatchGroup:Wait", w);

  if (!linked_as_leader) {
    /**
     * Wait util:
     * 1) An existing leader pick us as the new leader when it finishes
     * 2) An existing leader pick us as its follewer and
     * 2.1) finishes the memtable writes on our behalf
     * 2.2) Or tell us to finish the memtable writes in pralallel
     * 3) (pipelined write) An existing leader pick us as its follower and
     *    finish book-keeping and WAL write for us, enqueue us as pending
     *    memtable writer, and
     * 3.1) we become memtable writer group leader, or
     * 3.2) an existing memtable writer group leader tell us to finish memtable
     *      writes in parallel.
     */
    TEST_SYNC_POINT_CALLBACK("WriteThread::JoinBatchGroup:BeganWaiting", w);
    AwaitState(w, STATE_GROUP_LEADER | STATE_MEMTABLE_WRITER_LEADER |
                      STATE_PARALLEL_MEMTABLE_WRITER | STATE_COMPLETED,
               &jbg_ctx);
    TEST_SYNC_POINT_CALLBACK("WriteThread::JoinBatchGroup:DoneWaiting", w);
  }
}

每个事务提交请求都会生成一个 WriteBatch 对象，进入 WriteImpl 函数后各自的线程首先调用 JoinBatchGroup 来加入到队列。该队列主要核心的实现在于 LinkOne 函数，通过 CAS 无锁将多个线程的请求组成请求链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

bool WriteThread::LinkOne(Writer* w, std::atomic<Writer*>* newest_writer) {
  assert(newest_writer != nullptr);
  assert(w->state == STATE_INIT);
  Writer* writers = newest_writer->load(std::memory_order_relaxed);
  while (true) {
    // If write stall in effect, and w->no_slowdown is not true,
    // block here until stall is cleared. If its true, then return
    // immediately
    if (writers == &write_stall_dummy_) {
      if (w->no_slowdown) {
        w->status = Status::Incomplete("Write stall");
        SetState(w, STATE_COMPLETED);
        return false;
      }
      // Since no_slowdown is false, wait here to be notified of the write
      // stall clearing
      {
        MutexLock lock(&stall_mu_);
        writers = newest_writer->load(std::memory_order_relaxed);
        if (writers == &write_stall_dummy_) {
          stall_cv_.Wait();
          // Load newest_writers_ again since it may have changed
          writers = newest_writer->load(std::memory_order_relaxed);
          continue;
        }
      }
    }
    w->link_older = writers;
    if (newest_writer->compare_exchange_weak(writers, w)) {
      return (writers == nullptr);
    }
  }
}

write_group 链表结构如下：

每个 writer 在头部插入，插入时如果发现 link_older 为空，则此 writer 成为 write_group 的 Leader（即链表尾为 Leader）。

在 JoinBatchGroup 中，如果 writer 不是 Leader（在后文把不是 Leader 的 writer 称为 Follower），则会调用 AwaitState 等待被唤醒。

PS：由于条件锁 Context Switches 代价高，Rocksdb 在 AwaitState 也做了优化，将 pthread_cond_wait 拆成 3 步来做，本文不对该优化进行详细描述。

WriteImpl 写日志

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

if (w.state == WriteThread::STATE_GROUP_LEADER) {
  ...

  last_batch_group_size_ =
      write_thread_.EnterAsBatchGroupLeader(&w, &wal_write_group);
  const SequenceNumber current_sequence =
      write_thread_.UpdateLastSequence(versions_->LastSequence()) + 1;
  ...

  if (w.status.ok() && !write_options.disableWAL) {
    PERF_TIMER_GUARD(write_wal_time);
    stats->AddDBStats(InternalStats::kIntStatsWriteDoneBySelf, 1);
    RecordTick(stats_, WRITE_DONE_BY_SELF, 1);
    if (wal_write_group.size > 1) {
      stats->AddDBStats(InternalStats::kIntStatsWriteDoneByOther,
                        wal_write_group.size - 1);
      RecordTick(stats_, WRITE_DONE_BY_OTHER, wal_write_group.size - 1);
    }
    w.status = WriteToWAL(wal_write_group, log_writer, log_used,
                          need_log_sync, need_log_dir_sync, current_sequence);
  }

  ...

  write_thread_.ExitAsBatchGroupLeader(wal_write_group, w.status);
}

成为 Leader 的 writer，负责批量写入 WAL。在写 WAL 前，首先调用 EnterAsBatchGroupLeader 函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

size_t WriteThread::EnterAsBatchGroupLeader(Writer* leader,
                                            WriteGroup* write_group) {
  assert(leader->link_older == nullptr);
  assert(leader->batch != nullptr);
  assert(write_group != nullptr);

  size_t size = WriteBatchInternal::ByteSize(leader->batch);

  // Allow the group to grow up to a maximum size, but if the
  // original write is small, limit the growth so we do not slow
  // down the small write too much.
  size_t max_size = max_write_batch_group_size_bytes;
  const uint64_t min_batch_size_bytes = max_write_batch_group_size_bytes / 8;
  if (size <= min_batch_size_bytes) {
    max_size = size + min_batch_size_bytes;
  }

  leader->write_group = write_group;
  write_group->leader = leader;
  write_group->last_writer = leader;
  write_group->size = 1;
  Writer* newest_writer = newest_writer_.load(std::memory_order_acquire);

  // This is safe regardless of any db mutex status of the caller. Previous
  // calls to ExitAsGroupLeader either didn't call CreateMissingNewerLinks
  // (they emptied the list and then we added ourself as leader) or had to
  // explicitly wake us up (the list was non-empty when we added ourself,
  // so we have already received our MarkJoined).
  CreateMissingNewerLinks(newest_writer);

  // Tricky. Iteration start (leader) is exclusive and finish
  // (newest_writer) is inclusive. Iteration goes from old to new.
  Writer* w = leader;
  while (w != newest_writer) {
    w = w->link_newer;

    if (w->sync && !leader->sync) {
      // Do not include a sync write into a batch handled by a non-sync write.
      break;
    }

    if (w->no_slowdown != leader->no_slowdown) {
      // Do not mix writes that are ok with delays with the ones that
      // request fail on delays.
      break;
    }

    if (w->disable_wal != leader->disable_wal) {
      // Do not mix writes that enable WAL with the ones whose
      // WAL disabled.
      break;
    }

    if (w->batch == nullptr) {
      // Do not include those writes with nullptr batch. Those are not writes,
      // those are something else. They want to be alone
      break;
    }

    if (w->callback != nullptr && !w->callback->AllowWriteBatching()) {
      // dont batch writes that don't want to be batched
      break;
    }

    auto batch_size = WriteBatchInternal::ByteSize(w->batch);
    if (size + batch_size > max_size) {
      // Do not make batch too big
      break;
    }

    w->write_group = write_group;
    size += batch_size;
    write_group->last_writer = w;
    write_group->size++;
  }
  TEST_SYNC_POINT_CALLBACK("WriteThread::EnterAsBatchGroupLeader:End", w);
  return size;
}

在这里，通过 CreateMissingNewerLinks 函数来生成一个双向链表，使得可以从 Leader 开始顺序写。创建完成反向写请求链表之后，则开始计算有多少个写请求可以批量的进行，同时更新 write_group 中的批量写尺寸以及个数等信息，EnterAsBatchGroupLeader 取队列时会把此刻所有的 writer 一次性全取完。

该操作完成之后，则进入写 WAL 的流程了。调用 WriteToWAL，在 MergeBatch 函数中，将根据 write_group 生成一个 merged_batch，该 merged_batch 中记录着应当被写入 WAL 的内容。接着就通过 WriteToWAL 将 merged_batch 写入 WAL 中，这里会根据是否设置了 sync 来决定是否对 WAL 进行落盘操作。

PS：这里有一个优化点，在生成 merged_batch 的时候，假设该写请求的尺寸为一并且该请求需要写 WAL，则 merged_batch 直接复用了该写请求；反之则会复用一个 tmp_batch_ 对象避免频繁的生成 WriteBatch 对象。在写完 WAL 之后，假设复用了 tmp_batch_，则会清空该对象。

最后，调用 ExitAsBatchGroupLeader，该函数会决定该 Leader 是否为 STATE_MEMTABLE_WRITER_LEADER（MEMTABLE_WRITER_LEADER数量 <= GROUP_LEADER数量），从而进行写 Memtable 流程。

WriteImpl 写 Memtable

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

WriteThread::WriteGroup memtable_write_group;
  if (w.state == WriteThread::STATE_MEMTABLE_WRITER_LEADER) {
    PERF_TIMER_GUARD(write_memtable_time);
    assert(w.ShouldWriteToMemtable());
    write_thread_.EnterAsMemTableWriter(&w, &memtable_write_group);
    if (memtable_write_group.size > 1 &&
        immutable_db_options_.allow_concurrent_memtable_write) {
      write_thread_.LaunchParallelMemTableWriters(&memtable_write_group);
    } else {
      memtable_write_group.status = WriteBatchInternal::InsertInto(
          memtable_write_group, w.sequence, column_family_memtables_.get(),
          &flush_scheduler_, &trim_history_scheduler_,
          write_options.ignore_missing_column_families, 0 /*log_number*/, this,
          false /*concurrent_memtable_writes*/, seq_per_batch_, batch_per_txn_);
      versions_->SetLastSequence(memtable_write_group.last_sequence);
      write_thread_.ExitAsMemTableWriter(&w, memtable_write_group);
    }
  }

  if (w.state == WriteThread::STATE_PARALLEL_MEMTABLE_WRITER) {
    assert(w.ShouldWriteToMemtable());
    ColumnFamilyMemTablesImpl column_family_memtables(
        versions_->GetColumnFamilySet());
    w.status = WriteBatchInternal::InsertInto(
        &w, w.sequence, &column_family_memtables, &flush_scheduler_,
        &trim_history_scheduler_, write_options.ignore_missing_column_families,
        0 /*log_number*/, this, true /*concurrent_memtable_writes*/,
        false /*seq_per_batch*/, 0 /*batch_cnt*/, true /*batch_per_txn*/,
        write_options.memtable_insert_hint_per_batch);
    if (write_thread_.CompleteParallelMemTableWriter(&w)) {
      MemTableInsertStatusCheck(w.status);
      versions_->SetLastSequence(w.write_group->last_sequence);
      write_thread_.ExitAsMemTableWriter(&w, *w.write_group);
    }
  }

RocksDB 有一个 allow_concurrent_memtable_write 的配置项，开启后可以并发写 memtable（memtable 能设置并发写，但是 WAL 文件不能，因为 WAL 是一个追加写的文件，多个 writer 必须要串行化），所以接下来分为串行写和并行写来进行分析。

串行写 Memtable

Leader 调用 InsertInto，对 write_group 进行遍历，将 Leader 和 Follower 的 WriteBatch 写入。之后调用 ExitAsMemTableWriter，把所有 Follower 的状态设置为 STATE_COMPLETED，将它们唤醒，最后再把 Leader 的状态设置为 STATE_COMPLETED。

并行写 Memtable

调用 LaunchParallelMemTableWriters，遍历 write_group 把 Leader 和 Follower 的状态都设置为 STATE_PARALLEL_MEMTABLE_WRITER，将等待的线程唤醒。最后所有 writer 通过调用 InsertInto 来将 WriteBatch 写入 MemTable 中。writer 完成了 MemTable 的写操作之后，都会调用 CompleteParallelMemTableWriter 函数。该函数会将该 write_group 中运行的任务数减一，当运行中的任务数为零的时候就代表了所有的线程都完成了操作，调用 ExitAsMemTableWriter 把 Leader 的状态设置为 STATE_COMPLETED，反之则会进入等待状态，等待当前其他的写任务完成。

无论是串行写还是并行写，写入 MemTable 完成之后，还有一项工作，就是在取队列时获取 newest_writer_ 和当前时间点处，可能又有很多的写请求产生了，所以批量任务中最后一个完成的线程必须负责重新指定 Leader 给堆积写请求链表的尾部，让其接过 Leader 角色继续进行批量提交。可以看到，串行写和并行写最后都会调用 ExitAsMemTableWriter，正是在该函数中完成了该项工作。

PS：在高并发场景下，Follow 调用 AwaitState 的平均等待时延差不多是写 WAL 时延的两倍。因为获取 newest_writer_ 后，可能又来了许多写请求，这些写请求先要等待此时的 Leader 完成写流程，还要等待下个 Leader，也就是和这些写请求是同一个 write_group 的 Leader 完成写 WAL 才能被唤醒。

回顾

参考

1. Rocksdb Source Code 6.7.3
2. rocksdb写流程DBImpl::WriteImpl()源代码分析
3. RocksDB写入流程
4. RocksDB 写流程分析

当代 CPU 特性

超标量流水线与乱序执行

CPU指令的执行可以分为5个阶段：取指令、指令译码、执行指令、访存取数、结果写回。

流水线：一套控制单元可以同时执行多条指令，不需要等到上一条指令执行完就可以执行下一条指令。

超标量：一个 CPU 核有多套控制单元，因此可以有多条 pipeline 并发执行。CPU 还会维护一个乱序执行的指令窗口，窗口中的无数据依赖的指令就可以被取来并发执行。并发指令越多越好，因为这样指令之间没有依赖，并发流水线的执行会更加的流畅。

分支预测

遇到 if/switch 这种判断跳转的指令时会产生分支预测，分支预测系统会决定流水线接下来是载入紧挨着判断指令的下一条指令，还是载入跳转到另一个地址的指令。如果 CPU 的预测是正确的，那么判断指令结果出来的那一刻，真正需要执行的指令已经执行到尾声了，这时候只需要继续执行即可；如果CPU的预测是错误的，那么会把执行到尾声的错误指令全部清空，恢复到从未执行过的状态，然后再执行正确的指令。

程序分支越少或者是分支预测成功率越高，对流水线的执行就越有利，因为如果预测失败了，是要丢弃当前 pipeline 的所有指令重新 flush，这个过程往往会消耗掉十几个 CPU 周期。

多级存储与数据预取

当数据在寄存器，cache 或者内存中，CPU 取数据的速度并不是在一个个数量级上的。CPU 取指令/数据的时候并不是直接从内存中取的，通常 CPU 和内存中会有多级缓存，分别为 L1，L2，L3 cache，其中 L1 cache 又可以分为 L1-data cache，L1-instruction cache。先从 cache 中取数据，若不存在，才访问内存。访问内存的时候会同时把访问数据相邻的一些数据一起加载进 cache 中。

预取指的是若数据存在线性访问的模式，CPU会主动把后续的内存块预先加载进cache中。

SIMD

单指令多数据流，对于数据密集型的程序来说，可能会需要对大量不同的数据进行相同的运算。SIMD 引入了一组大容量的寄存器，比如 128 位，256 位。可以将这多个数据按次序同时放到一个寄存器。同时，CPU 新增了处理这种大容量寄存器的指令，可以在一个指令周期内完成多个数据的运算。

早期解释执行模型

大多数的 query 解释器模型都是使用基于迭代器的火山模型，如下图所示。每个算子看成一个 iterator，iterator 会提供一个 next 方法，每个 next 方法只会产生一个 tuple，可以理解为一行数据。查询执行的时候，查询树自顶向下调用 next 接口，数据则自底向上被拉取处理，层层计算返回结果。所以火山模型属于 pull 模型。

Volcano 模型简单灵活，且这种设计不用占用过多的内存。火山模型将更多的内存资源用于磁盘 IO 的缓存设计而没有优化 CPU 的执行效率，这在当时的硬件基础上是很自然的权衡。但是现在 CPU 的硬件环境与大数据场景下，性能表现却差强人意。主要有如下几点原因：

1. 时间都花在了query plan上，而不是计算上
   next 函数实现为虚函数，调用虚函数的时候要去查虚函数表，编译器无法对虚函数进行 inline 优化。同时会带来分支预测的开销，导致一次错误的 CPU 分支预测，需要多花费十几个 CPU 周期的开销。

2. CPU cache利用率低
   next 方法一次只返回一个元组，元组通常采用行存储，如果仅需访问其中某个字段但是每次都将整行数据填入 CPU cache，将导致那些不会被访问的字段也放在了 Cache 中，使得 cache 利用率非常低。

编译执行

编译执行指的是运行时期的代码生成生成技术。在执行过程中生成编译执行代码，避免过多的虚函数调用和解析执行，因为在执行之初我们是知道关系代数的 Schema 信息。在具备 Schema 信息的情况下，事先生成好的代码，可以有效减少很多执行分支预测开销。

上图右边的代码非常紧凑，有效消除了字段个数，字段大小，字段类型，对于数据量特别多的处理场景，可以大大减少CPU开销，提高性能。

编译执行以数据为中心，消灭了火山模型中的大量虚函数调用开销。甚至使大部分指令执行，可以直接从寄存器取数，极大提高了执行效率。

在 Java 中通过 JIT 来实现，在 C++ 中通过 LLVM 来实现 codegen，对于 OLAP 这种运行时间较长的 query 来说，通常编译的时间是可以忽略的。

向量化执行

向量可以理解为按列组织的一组数据，连续存储的一列数据，在内存中可以表示为一个向量。

向量模型和火山模型的本质区别就在于，数据处理的基本单元不再是按行组织的 tuple，而是按列组织的多个向量，我们常说的一个 chunk 其实就是多个 vector 的集合，就是多个列的意思。

向量化执行好处是：由于每次 next 都是处理一批数据，那么大大减少了虚函数调用的次数，分支预测的成功概率会提升，减少了分支预测的开销，并且充分发挥 SIMD 指令并行计算的优势；还可以和列式存储有效结合在一起，减少数据额外转换的 overhead。

向量化和编译执行比较

向量化执行的主要访存开销在于像 join 这种算子的物化开销，物化就是从寄存器把数据读到内存中。而编译执行，tuple 可以一直留在寄存器中，一个 operator 处理完后，给另外一个 operator 继续处理。除非遇到不得不物化的情况。

向量化执行模型的循环较短，并发度高，可以同时有更多的指令等待取数。编译执行循环内部会包含多个 operator 的运算，这些有依赖关系的指令占据了大部分的乱序执行窗口，并发度低。

参考

1. Sompolski, J. , M. Zukowski , and P. A. Boncz . “Vectorization vs. Compilation in Query Execution.” International Workshop on Data Management on New Hardware ACM, 2011.
2. S. Wanderman-Milne and N. Li, “Runtime Code Generation in Cloudera Impala,” IEEE Data Eng. Bull., vol. 37, no. 1, pp. 31–37, 2014.
3. 向量化与编译执行浅析

概述

在设计与开发高性能的系统时，基本都离不开缓存的设计。没有缓存对系统的加速和阻挡大量的请求直接落到系统的底层，系统是很难撑住高并发的冲击。无论是在 CPU 的 L1,L2,L3 缓存，数据库的 sql 语句执行缓存，系统应用的本地缓存，缓存总是解决性能的一把利器。本文主要探讨缓存带来的问题以及缓存方案的设计。

缓存带来的问题

缓存一致性

引入缓存后，主要是解决读的性能问题，但是数据总是要更新的，会存在操作隔离性和更新原子性的问题，是先更新缓存还是先更新数据库呢？

• 操作隔离性：一条数据的更新涉及到存储和缓存两套系统，如果多个线程同时操作一条数据，并且没有方案保证多个操作之间的有序执行，就可能会发生更新顺序错乱导致数据不一致的问题

  

• 更新原子性：引入缓存后，我们需要保证缓存和存储要么同时更新成功，要么同时更新失败，否则部分更新成功就会导致缓存和存储数据不一致的问题

  

1. 先更新缓存再更新数据库：更新缓存后，后续的读操作都会先从缓存获取从而获取的是最新的数据，但是如果第二步更新数据库失败，那么数据需要回滚，导致先前获取的数据是脏数据来带不可逆的业务影响
2. 先更新数据库后更新缓存：先更新数据库，但是缓存没有更新，再将数据从数据库同步到缓存这一过程中，所有的读操作读的都是旧数据，会带来一定问题，牺牲小概率的一致性

缓存击穿

缓存击穿是指：业务操作访问缓存时，没有访问到数据，又去访问数据库，但是从数据库也没有查询到数据，也不写入缓存，从而导致这些操作每次都需要访问数据库，造成缓存击穿。

解决办法一般有两种：

1. 将每次从数据库获取的数据，即使是空值也先写入缓存，但是过期时间设置得比较短，后续的访问都直接从缓存中获取空值返回即可
2. 通过 Bloom filter 记录 key 是否存在，从而避免无效数据的查询

缓存雪崩

缓存雪崩是指：由于大量的热数据设置了相同或接近的过期时间，导致缓存在某一时刻密集失效，大量请求全部转发到数据库，或者是某个冷数据瞬间涌入大量访问数据库。

主要解决方法：

1. 所有数据的过期时间不要设置成一样，防止出现数据批量失效，导致缓存雪崩的情况
2. 采用互斥锁的方式：这里需要使用到分布式锁，在缓存失效后，如果访问同一数据的操作需要访问数据并去更新缓存时，对这些操作都加锁，保证只有一个线程去访问数据并更新缓存，后续所有操作还是从缓存中获取数据，如果一定时间没有获取到就返回默认值或返回空值。这样可以防止数据库压力增大，但是用户体验会降低
3. 后台更新：业务操作需要访问缓存没有获取到数据时，不访问数据库更新缓存，只返回默认值。通过后台线程去更新缓存，这里有两种更新方式：
   • 启动定时任务定时扫描所有缓存，如果不存在就更新，该方法导致扫描 key 间隔时间过长，数据更新不实时，期间业务操作一直会返回默认值，用户体验比较差
   • 业务线程发现缓存失效后通过消息队列去更新缓存，这里因为是分布式的所以可能有很多条消息，需要考虑消息的幂等性。这种方式依赖消息队列，但是缓存更新及时，用户体验比较好，缺点是系统复杂度增高了

缓存方案的设计

读取

读数据流程很简单，先去缓存读取数据，如果缓存 MISS，则需要从存储中读取数据，并将数据更新到缓存系统中，整个流程如下所示：

更新

通常选择以下方案，保障数据可靠性，尽量减少数据不一致的出现，通过 TTL 超时机制在一定时间段后自动解决数据不一致现象：

1. 更新数据库，保证数据可靠性
2. 更新缓存，有以下 2 个策略：
   • 惰性更新：删除缓存中对应的 item，等待下次读 MISS 再缓存（推荐）
   • 积极更新：将最新的数据更新到缓存

淘汰

缓存的作用是将热点数据缓存到内存实现加速，内存的成本要远高于磁盘，因此我们通常仅仅缓存热数据在内存，冷数据需要定期的从内存淘汰，数据的淘汰通常有两种方案：

1. 主动淘汰。通过对 Key 设置 TTL 的方式来让 Key 定期淘汰，以保障冷数据不会长久的占有内存（推荐）
2. 被动淘汰。当缓存已用内存超过 Maxmemory 限定时触发淘汰，在 Maxmemory 的场景下缓存的质量是不可控的，因为每次缓存一个 Key 都可能需要去淘汰一个 Key

参考

1. 翻越缓存的三座大山

TiDB是支持MySQL语法的开源分布式混合事务/分析处理（HTAP）数据库。TiDB 可以提供水平可扩展性、强一致性和高可用性。它主要由 PingCAP 公司开发和支持，并在 Apache 2.0 下授权。TiDB 从 Google 的 Spanner 和 F1 论文中汲取了最初的设计灵感。

HTAP 是 Hybrid Transactional / Analytical Processing 的缩写。这个词汇在 2014 年由 Gartner 提出。传统意义上，数据库往往专为交易或者分析场景设计，因而数据平台往往需要被切分为 TP 和 AP 两个部分，而数据需要从交易库复制到分析型数据库以便快速响应分析查询。而新型的 HTAP 数据库则可以同时承担交易和分析两种智能，这大大简化了数据平台的建设，也能让用户使用更新鲜的数据进行分析。作为一款优秀的 HTAP 数据数据库，TiDB 除了优异的交易处理能力，也具备了良好的分析能力。

TiDB在整体架构基本是参考 Google Spanner 和 F1 的设计，上分两层为 TiDB 和 TiKV。 TiDB 对应的是 Google F1，是一层无状态的 SQL Layer，兼容绝大多数 MySQL 语法，对外暴露 MySQL 网络协议，负责解析用户的 SQL 语句，生成分布式的 Query Plan，翻译成底层 Key Value 操作发送给 TiKV，TiKV 是真正的存储数据的地方，对应的是 Google Spanner，是一个分布式 Key Value 数据库，支持弹性水平扩展，自动的灾难恢复和故障转移（高可用），以及 ACID 跨行事务。值得一提的是 TiKV 并不像 HBase 或者 BigTable 那样依赖底层的分布式文件系统，在性能和灵活性上能更好，这个对于在线业务来说是非常重要。

• TiDB Server：SQL 层，对外暴露 MySQL 协议的连接 endpoint，负责接受客户端的连接，执行 SQL 解析和优化，最终生成分布式执行计划。TiDB 层本身是无状态的，实践中可以启动多个 TiDB 实例，通过负载均衡组件（如 LVS、HAProxy 或 F5）对外提供统一的接入地址，客户端的连接可以均匀地分摊在多个 TiDB 实例上以达到负载均衡的效果。TiDB Server 本身并不存储数据，只是解析 SQL，将实际的数据读取请求转发给底层的存储节点 TiKV（或 TiFlash）。
• PD (Placement Driver) Server：整个 TiDB 集群的元信息管理模块，负责存储每个 TiKV 节点实时的数据分布情况和集群的整体拓扑结构，提供 TiDB Dashboard 管控界面，并为分布式事务分配事务 ID。PD 不仅存储元信息，同时还会根据 TiKV 节点实时上报的数据分布状态，下发数据调度命令给具体的 TiKV 节点，可以说是整个集群的“大脑”。此外，PD 本身也是由至少 3 个节点构成，拥有高可用的能力。建议部署奇数个 PD 节点。
• 存储节点
  • TiKV Server：负责存储数据，从外部看 TiKV 是一个分布式的提供事务的 Key-Value 存储引擎。存储数据的基本单位是 Region，每个 Region 负责存储一个 Key Range（从 StartKey 到 EndKey 的左闭右开区间）的数据，每个 TiKV 节点会负责多个 Region。TiKV 的 API 在 KV 键值对层面提供对分布式事务的原生支持，默认提供了 SI (Snapshot Isolation) 的隔离级别，这也是 TiDB 在 SQL 层面支持分布式事务的核心。TiDB 的 SQL 层做完 SQL 解析后，会将 SQL 的执行计划转换为对 TiKV API 的实际调用。所以，数据都存储在 TiKV 中。另外，TiKV 中的数据都会自动维护多副本（默认为三副本），天然支持高可用和自动故障转移。
  • TiFlash：TiFlash 是一类特殊的存储节点。和普通 TiKV 节点不一样的是，在 TiFlash 内部，数据是以列式的形式进行存储，主要的功能是为分析型的场景加速。

TiKV 基于 RocksDB，采用了 Raft 协议来实现分布式的一致性。TiKV 的系统架构如下图所示：

优点：

• 纯分布式架构，拥有良好的扩展性，支持弹性的扩缩容
• 支持 SQL，对外暴露 MySQL 的网络协议，并兼容大多数 MySQL 的语法，在大多数场景下可以直接替换 MySQL
• 默认支持高可用，在少数副本失效的情况下，数据库本身能够自动进行数据修复和故障转移，对业务透明
• 支持 ACID 事务，对于一些有强一致需求的场景友好，例如：银行转账
• 具有丰富的工具链生态，覆盖数据迁移、同步、备份等多种场景
• 智能的行列混合模式，TiDB 可经由优化器自主选择行列。这套选择的逻辑与选择索引类似：优化器根据统计信息估算读取数据的规模，并对比选择列存与行存访问开销，做出最优选择

缺点：

• 虽然兼容MySQL，但是不支持存储过程，触发器，自定义函数，窗口功能有限
• 不适用数据量小的场景，专门为大数据量设计

背景

分布式数据库 Schema 变更时，由于 Server 获取 Schema 元数据的时机不是同步的，不可避免地会使同一时刻一些 Server 上的 Schema 是旧的，如下图所示。而若变更时禁止 DML 让所有的 Server 都暂停服务，对于大规模分布式数据库，基本没法做到，因为 Schema 变更操作需要花费大量时间，而数据库需要保证 24 小时在线。

例如，增加一个索引 E，Schema 从 S1 变为 S2，有两个节点 A 和 B 分别使用 S1 和 S2：

1. B 添加一行数据，由于它按照 Index E 已经创建完成的 Schema，它会插入两个 KV，RowKV 和 IndexKV
2. A 删除该行数据，由于它按照 Index E 未创建的 Schema，它只会删除 RowKV，IndexKV 就成了孤儿，破坏了数据的完整性

论文思路

论文提出了一种 Schema 演进的协议，协议有两个特点：

1. Online——Schema 变更期间，所有 Server 仍然可以读写全部数据
2. Asynchronous——允许不同 Server 在不同时间点开始使用新版本 Schema

论文把从 Schema 0 到 Schema 1 的突变，替换为一系列相互兼容的小状态变化：

• 任意两个相邻的小状态（版本）都是兼容的
• 只有一个 Server 负责 DDL 的执行，其他 Server 只是定期刷新状态（拉取 Schema）
• 每次 Schema 版本变化间隔不小于一个 Lease 时间，任意时刻，集群中 Server 至多存在两个版本的 Schema。也就是说所有 Server 使用的 Schema 状态都相邻，都是兼容的，经过一系列小状态的转换，就可以实现 Schema 0 到 Schema 1 的变更

schema elements

• 包括 tables，columns，indexes，constraints，和 optimistic locks
• 每个 schema element 都有一个与之关联的 state

states

1. Absent 状态

• 完全不感知该 schema element，任何 DML 都不会涉及该 schema element

2. Delete Only 状态

• Select 语句不能使用该 schema element
• Delete 语句在删除时，如果​该 schema element​ 对应的条目存在，要一并删除
• Insert 语句在插入​时，不允许插入该 schema element​ 对应的条目
• Update 语句在修改时，只允许删除既存的该 schema element​ 对应的条目，但不能插入新的该 schema element​ 对应的条目

3. Write Only 状态

• Select 语句不能使用该 schema element
• 其他 DML 语句可以正常使用该 schema element、修改该 schema element​ 对应的条目

4. Reorg

• 不是一种 schema 状态，而是发生在 write-only 状态之后的一系列操作，保证在索引变为 public 之前所有旧数据的 schema element 都被正确地生成
• reorg 要做的就是取到当前时刻的 snapshot，为每条数据补写对应的 schema element 条目即可。当然 reorg 开始之后数据可能发生变更，这种情况下底层 Spanner 提供的一致性能保证 reorg 的写入操作要么失败（说明新数据已提前写入），要么被新数据覆盖

5. Public 状态

• 该 schema element 正常工作，所有 DML 都正常使用该 schema element

状态兼容说明

破坏一致性（兼容性）的场景有两种：

• orphan data anomaly：数据库中包含了按照当前 schema 下不应存在的 KV
• integrity anomaly：数据库中缺少当前 schema 下应该存在的 KV

1. 为什么 “Absent” 和 “Delete Only” 能够兼容

• Absent 状态的 Server 不知道该 schema element 因此不需要该 schema element，不会产生该 schema element 的条目
• Delete Only 状态的 Server 知道该 schema element（非 public）但也不需要该 schema element，不会产生该 schema element 的条目

2. 为什么 “Delete Only” 和 “Write Only” 能够兼容

• Delete Only 状态和 Write Only 状态的 Server 都知道该 schema element（非 public）但都不需要该 schema element

3. 为什么 “Write Only” 和 “Public” 能够兼容

• Write Only 状态的 Server 在该 schema element 的所有已经完整的情况下（通过 Reorg），可以与 Public 兼容

4. 为什么 “Absent” 和 “Write Only” 不兼容

• 因为 Write Only 会产生新的条目，破坏了 Absent 的条件

5. 为什么 “Delete Only” 和 “Public” 不兼容

• 因为 Public 有要求所有历史数据有完整的 schema element，Delete Only 状态下并不具备

6. 通俗点举例

• 假设在增加一个索引 E 的过程中，有如下执行顺序：1）Server A 插入一行 x；2) Server B 删除了行 x；3）Server A 查询 y；4) Server B 查询 y：
  (1) A 为 Delete Only 状态，B 为 Absent 状态：A 插入了一个 KV（RowKV），B 将 RowKV 删除，A 和 B 在查询时都不会用到 Index E，是兼容的
  (2) A 为 Write Only 状态，B 为 Delete Only 状态：A 插入了两个 KV（RowKV 和 IndexKV），B 将 RowKV 和 IndexKV 删除，A 和 B 在查询时都不会用到 Index E，是兼容的
  (3) A 为 Public 状态，B 为 Write Only 状态：A 插入了两个 KV（RowKV 和 IndexKV），B 将 RowKV 和 IndexKV 删除；查询时，A 会用到 Index E，B 虽然不会用到 Index E，但数据库中存在 A 的 schema 下应该存在的 IndexKV，所以是兼容的
  (4) A 为 Write Only 状态，B 为 Absent 状态：A 插入了两个 KV（RowKV 和 IndexKV），B 感知不到 IndexKV，因此只会删除 RowKV，这一行的 IndexKV 就成了孤儿数据，所以不兼容
  (5) A 为 Public 状态，B 为 Delete Only 状态：A 会用到 Index E，B 不会用到 Index E，并且数据库中也不存在 A 的 schema 下的 IndexKV，所以不兼容

参考

1. Ian Rae, Eric Rollins, Jeff Shute, Sukhdeep Sodhi and Radek Vingralek, Online, Asynchronous Schema Change in F1, VLDB 2013.