编者按
本文系中国人民大学在读硕士生张倩所著，本篇也是 OceanBase 学术系列稿件第四篇。
「张倩：中国人民大学信息学院在读硕士生，硕士期间在中国人民大学数据库与智能信息检索实验室从事分布式事务与 RDMA 新硬件的相关研究，目前在并发控制算法优化与分布式事务执行优化方向取得了一定进展，之后将继续在分布式事务领域努力探索。」
今天分享的论文是 ACM TOCS2018《Building Consistent Transactions with Inconsistent Replication》——使用不一致的复制策略来保障事务的一致性。希望阅读完本文，你可以对事务一致性有新的收获，当然也可以有不同看法，欢迎在底部留言探讨。
现代的存储系统通常将数据划分为分片来实现系统的可扩展性，并且通过将每个数据分片复制多份存储在不同的节点上来实现容错，保障系统的可用性。现有的事务性存储系统通过采用分布式事务协议+复制协议的两层体系，通过上层的分布式事务协议如 2PC 和并发控制协议来保障分布式事务的原子性和一致性，而下层的复制协议（如 Paxos 等）通常用来保障系统的容错性及每个副本上的数据一致性。
在这种体系架构之下，上层的分布式事务协议在执行过程中不需要处理下层数据分片的副本同步时的内部逻辑，仅有上层协议将修改请求交给分片的主副本Leader，由 Leader 来完成从副本的同步，最终也由 Leader 将副本之间的同步结果返回给事务的协调者。此时，同一个数据分片对外可以作为一个整体被访问，上层协议在设计时无需考虑下层副本结构。但由于这种架构：1）需要事务的协调者及 Leader 来进行两层的协调 2）分布式事务协议与复制协议都需要进行强一致性的保证，因此会产生较高的网络延迟，造成性能瓶颈。
本篇论文提出 IR（Inconsistent Replication， 不一致复制），使复制协议仅提供容错能力，而不提供一致性保证；并在此基础之上设计 TAPIR（The Transactional Application Protocol For Inconsistent Replication, 基于不一致复制的事务应用程序协议），使得事务的执行可以在保障一致性的基础之上，在 Prepare 及 Commit 阶段减少一轮的网络通信开销，凸显 IR 策略的性能优势。
方法介绍
（一）新的复制协议——IR
本文首先介绍了新的复制协议 IR（Inconsistent Replication， 不一致复制），它与一般复制协议不同的是：它允许操作在每个副本上以不同的顺序执行，只要求这些操作造成的结果一致，而不要求这些操作有序。IR 只为系统提供容错能力（2f+1 个副本的系统，当不多于 f 个副本故障时，系统仍然可用），而不提供一致性保障。
IR 将操作分为两类：
Inconsistent：允许操作以任意顺序执行，成功后可持久化，在不同副本上执行顺序可能不同，当产生冲突时由应用程序进行解决。其具体流程如下：
1. InvokeInconsistent(op)
2. client给所有的replicas发送<PROPOSE, op_id, op>
3. 各replica将(op_id,op)写入record,并把op标记为TENTATIVE后，向client回复<REPLY, op_id>
4. 一旦 client 收到 f+1 个回复(有必要可重试)，立即向应用程序返回成功信号，同时异步地给所有的replicas发送<FINALIZE, op_id>(此消息也可 piggy-backed 在 client 的下一消息上)
5. 各 replica 收到 FINALIZE 消息后，执行 ExecInconsistent(op)，并把 op 标记更新为FINALIZED
Consensus：允许操作以任意顺序执行，执行后返回唯一的一致结果，成功后可持久化，在不同副本上执行顺序可能不同，当产生冲突时由应用程序进行解决。与 Inconsistent 的区别是，当 replicas 之间有冲突时，会在客户端引入一个 decide 过程来对决定最终的结果，相应的，会在服务端增加一个 merge 过程来解决 Consensus 操作的副本冲突。其具体流程如下：
1. InvokeConsensus(op,decide(results))
2. client 给所有的 replicas 发送 <PROPOSE, op_id, op>
3. 各 replica 执行 ExecConsensus(op) 以得到本地 result，将 (op_id,op,result) 写入 record,并把 op 标记为 TENTATIVE
4. 各 replica 向 client 回复<REPLY,op_id,result>
此时当 client 可以较快的收到一致的回复时，采用 fast path，只用一轮 round-trip Time 便可将结果返回给应用程序：
5. 如果 client 在一定时间内收到≥⌈3/2 f⌉+1个一致的 results,采用 fast path: 向应用程序返回这个一致的result，同时异步地给所有的 replicas 发送<FINALIZE, op_id, result>.
6. 各 replica 收到 FINALIZE 消息后，更新 record 中的本地 result (如不同)，并把 op 标记更新为 FINALIZED。之后向 client 回复<CONFIRM, id>
当 client 收到回复的速度较慢，则采用 slow path，当收到超过 f+1 个回复时，用 decide 函数决定一个一致的结果，然后再用一轮 round-trip Time 将一致的结果同步到所有的副本上，因此这种 slow path 的方式需要两轮 round-trip Time。Slow path 的流程如下：
5. 如果 client 在一定时间内收到 <⌈3/2 f⌉+1 个一致的 results，采用 slow path: 一旦它收到 f+1 个回复(有必要可重试)，执行 decide(results) 得到一致的 result
6. 之后 client 给所有的 replicas 发送<FINALIZE, id, result>
7. 各 replica 收到 FINALIZE 消息后，更新 record 中的本地 result(如不同)，并把 op 标记更新为 FINALIZED。之后向 client 回复 <CONFIRM, id>
8. 一旦 client 收到 f+1 个 CONFIRM，立即向应用程序返回 result
在 IR 中，将成功的操作定义为返回到应用程序协议的操作，任何 IR 的操作集中包括所有成功的操作。当一个执行操作 Y 的副本已经执行过 X，则称操作 X 对操作 Y 是可见的。基于以上定义，IR 确保了操作集的以下属性：
容错性：在任何时候，操作集中的每个操作都在 f+1 个非失败的副本的至少一个副本中有记录。
可见性：对于操作集中的任意两个操作，至少一个对另一个是可见的。
共识结果：在任何时候，一个成功的 Consensus 操作 deside 并返回给应用程序的结果在至少一个副本的记录中。
（二）基于IR的事务协议——TAPIR
IR 通过提供较弱的一致性保障来获得性能优势，并依赖于应用协议来解决不一致性，因此，在 IR 之上设计应用协议时需要满足一些要求。
1. 在进行 Consensus 操作时需要严格的检查，例如 2PL 的加锁或者 OCC 的验证；
2. 应用程序可以在 Consensus 操作 decide 统一的结果之后，修改副本中不一致的操作结果；
3. 应用程序协议不期望操作以相同的顺序执行；
4. 应用程序应该尽可能使用代价更低的 Inconsistent 操作，而不是 Consensus 操作。
基于以上原则，本文设计 TAPIR（The Transactional Application Protocol For Inconsistent Replication, 基于不一致复制的事务应用程序协议），用于有效利用 IR 实现高性能的可串行化事务。
首先在读写阶段，图 2 中的传统方案需要读取 Leader 副本，而图 3 中的 TAPIR 消除了主从副本的地位，所有的副本都是等价的，客户端可以选择离自己更近的副本去读取。
图 2 使用Leader作为协调的事务执行流程
在两阶段提交阶段，客户端等价的向所有的副本发送 Consensus 类型的 Prepare请求。当副本收到来自客户端的 Prepare 请求之后，在副本上进行基于 OCC 的验证，如果验证通过，则发送 PREPARE-OK 的回复给客户端（如果验证失败则发送 PREPARE-ABORT）。当客户端收到所有回复后，如果全为PREPARE-OK则进一步向所有副本发送 Inconsistent 的 Commit 的消息完成提交（如果回复中有 PREPARE-ABORT 则发送 Abort 消息进行回滚）。当副本收到 Commit 消息（或 Abort 消息）则修改日志，并将修改内容写入存储（Abort 则不用），最终将结果返回给客户端。
与图 2 中的方式相比，TAPIR 有以下优点：
1. TAPIR 没有 Leader 或副本之间的集中协调；
2. TAPIR 在读时可以读最近的副本；
3. 在大多数情况下，TAPIR 的 Prepare 和 Commit 阶段只需要一轮 Round-trip Time（由于 Prepare 阶段是 Consensus 的方式，如果进行 slow path，则需要两轮 Round-trip Time）。
实验结果
本文首先将提出的基于 IR 的 TAPIR 与基于 Paxos 的 OCC 及基于 Paxos 的 LOCK 方法在单数据中心内进行比较。在本实验中，共有 10 个数据分片，每个数据分片有三个副本，客户端和数据均位于美国。图 4 中显示了在不同吞吐量下事务的平均延迟。但负载较低时，TAPIR-KV 拥有较低的延迟，因为它能够在一次 Round-trip Time 下完成 Prepare 或 Commit，而其他的方式需要两次，因此，它的提交延迟减少了 50%。并且由于 IR 的弱保证，TAPIR-KV 能够提供大约三倍的峰值吞吐量。
为了检验广域网络延迟对事务性能的影响，本文将一个数据分片的三个副本分别放在美国、欧洲和亚洲，在 OCC-STORE 和 LOCK-STORE 中将 Leader 副本固定在美国，然后在三个地区之间移动客户端的位置来对比事务时延。
当客户端和 Leader 位于同一个地区时，对比的两个系统的时延低于 TAPIR-KV。但是当 Leader 位于不同的地区时，LOCK-STORE 会受到较为严重的影响，因为它必须在 Leader 上进行锁，而 OCC-STORE 可以像 TAPIR-KV 一样读本地的副本。
TAPIR 是一种乐观协议，因此系统依然可能会因为冲突而回滚。本文测量了不同争用程度下事务的回滚率并与传统的 OCC-STORE 比较。当冲突率较低的情况下，TAPIR-KV 与 OCC-STORE 的回滚率都很低，但 TAPIR-KV 依然比 OCC-STORE 低接近一个数量级。当竞争程度特别激烈（Zipf=0.95）时，TAPIR-KV 与 OCC-STORE 的回滚率接近，均为 40% 左右。
本文还将 TAPIR-KV 与其他三种使用最终一致性的系统 MongoDB、Cassandra 与 Redis 进行了性能比较。图7中表明，TAPIR-KV 的延迟与吞吐量与这些系统相当，它的性能优于 MongoDB，吞吐量在 Cassandra 和 Redis 的两倍之内。但是与这些系统相比，它支持分布式事务且具有强一致性保障。
本文通过提出 IR 复制协议与 TAPIR 分布式事务协议证明了使用不一致的复制协议实现强一致性的分布式事务是可行的，并且通过实验证明了与其他主流强一致性方案相比本文的方案具有明显的性能优势，与最终一致性方案相比本文的吞吐差距也在两倍以内。因此本文实现了在保障事务强一致性的基础之上提升了分布式事务的执行性能。
*参考文献：[1] Irene Zhang, Naveen Kr. Sharma, Adriana Szekeres, Arvind Krishnamurthy, and Dan R. K. Ports. 2018. Building Consistent Transactions with Inconsistent Replication. ACM Trans. Comput. Syst. 35, 4, Article 12 (November 2017), 37 pages. https://doi.org/10.1145/3269981.[2] Irene Zhang, Naveen Kr. Sharma, Adriana Szekeres, Arvind Krishnamurthy, and Dan R. K. Ports. 2015. Building consistent transactions with inconsistent replication. In Proceedings of the 25th Symposium on Operating Systems Principles (SOSP '15). Association for Computing Machinery, New York, NY, USA, 263–278. https://doi.org/10.1145/2815400.2815404.
