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