OSDI'23-Consolidating Concurrency Control and Consensus for Commits under Conflicts

摘要

传统的容错分布式事务是在 Paxos 共识协议之上的传统并发控制协议。这种方法提供了可扩展性、可用性和强一致性。然而，当用于广域存储时，这种方法会引发两次跨数据中心的连续协调：一次用于并发控制，然后一次用于共识。在本文中，我们主要观察到并发控制和共识所需的协调高度相似。具体来说，每个都试图确保交易的序列化图是非循环的。我们在 Janus 的设计中利用了这种洞察力，这是一个统一的并发控制和共识协议。 Janus 的目标是编写为存储过程的一次性事务，这是一种常见但受限制的事务类。像 MDCC 和 TAIR 一样，Janus 可以在一次往返中提交此类中的不冲突事务。与 MDCC 和 TAPIR 不同，Janus 避免了由于争用而中止：只要网络运行良好并且每个服务器副本的大多数都处于活动状态，它最多在两次往返中提交此类中的冲突事务。

我们将 Janus 与分层设计和 TAPIR 在此类中的各种工作负载下进行比较。我们的评估表明，在无竞争的微基准测试中，Janus 的吞吐量是分层系统的 5 倍，是 TAPIR 吞吐量的 90%。当工作负载竞争时，Janus 提供比基线低得多的延迟和更高的吞吐量（高达 6.8 倍）。

简介

可扩展、可用且高度一致的分布式事务通常是通过在 Paxos 共识协议复制的数据存储分片之上分层传统并发控制协议来实现的。将数据分片成许多可以由不同服务器存储和服务的小子集提供了可扩展性。尽管服务器出现故障，但通过共识复制每个分片可提供可用性。尽管不同事务的数据访问存在冲突，但使用 USENIX 关联并发控制跨复制分片协调事务可提供强一致性。这种方法在实践中很常用。例如，Spanner 实现了两阶段锁定 (2PL) 和两阶段提交 (2PC)，其中数据和锁都由 Paxos 复制。作为另一个例子，Percolator 实现了机会并发控制 (OCC) 的变体，它在 BigTable 之上使用 2PC，它依赖于主备份复制和 Paxos。

当用于广域存储时，分层方法会导致两次跨数据中心协调，按照顺序是：一次通过并发控制协议确保事务一致性（严格的可串行化），另一次通过共识协议以确保副本一致性（线性化）。这种双重协调是不必要的，可以通过将并发控制和共识合并到一个统一的协议中来消除。 MDCC 和 TAIR 分别展示了统一方法如何提供读取提交和严格的可串行化隔离级别。两种协议都乐观地尝试在一次广域往返中提交和复制事务。但是，如果并发事务之间存在冲突，它们会中止并重试，这会在争用情况下显著降低性能。这种担忧对于广域存储更为明显：由于交易需要更长的时间才能完成，争用的数量也相应增加。

本文提出了构建容错分布式事务的 Janus 协议。与 TAIR 和 MDCC 一样，Janus 可以在没有争用的情况下在一次跨数据中心往返中提交和复制事务。面对并发冲突事务的干扰，Janus 最多需要一个额外的跨数据中心往返来提交。

Janus 的关键洞察力是实现事务一致性的严格序列化和复制一致性的线性化都可以映射到相同的底层抽象。特别是，两者都要求交易的执行历史等价于一些线性的总订单。可以通过基于执行历史构建序列化图来检查这种等价性。图中的每个顶点对应一个事务。由于复制或冲突的数据访问，每条边代表两个事务之间的依赖关系。具体来说，如果事务 $T_{1}$ 和 $T_{2}$ 对某些数据项进行冲突访问，那么如果负责冲突数据项的分片在 $T_{2}$ 之前执行或复制 $T_{1}$ ，则存在一条边 $T_{1} \to T_{2}$ 。如果该图中没有循环，则可以找到严格可串行化和线性化的等效线性总阶。

Janus 以两种方式确保非循环序列化图。首先，Janus 通过跟踪冲突事务到达复制每个分片的服务器时的依赖关系来捕获初步图表。事务 $T$ 的协调器然后从复制每个分片的足够大的仲裁服务器收集和传播 $T$ 的依赖关系。 $T$ 的实际执行被推迟，直到协调者确定 $T$ 的所有参与分片都获得了 $T$ 的所有依赖项。其次，虽然基于事务到达顺序的依赖关系图可能包含循环，但 $T$ 的参与分片重新排序事务以相同的确定顺序循环以确保非循环序列化图。这提供了严格的可串行化，因为所有服务器都以相同的顺序执行冲突的事务。

在没有争用的情况下，所有参与的分片都可以在一次跨数据中心往返中获得 $T$ 的所有依赖项。在存在争用的情况下，可能会出现两种类型的冲突：一种是不同事务之间的冲突，另一种是在同一事务的复制过程中。不同事务之间的冲突仍然可以在单个跨数据中心往返中处理。它们在依赖图中表现为循环，并通过确保确定性执行重新排序来处理。然而，在复制同一事务期间出现的冲突需要第二次跨数据中心往返，以在不同服务器副本之间就事务的依赖项集达成共识。这两种情况都不需要 Janus 中止事务。因此，只要网络和机器故障不会共同阻止每个服务器副本的大多数进行通信，Janus 总是在面对争用时最多提交两次跨数据中心往返。

Janus 的基本协议及其始终提交的能力假设了一类常见的事务性工作负载：编写为存储过程的一次性事务。存储过程经常被使用并将事务逻辑发送到服务器以作为片段执行，而不是让客户端在简单地向服务器读取和写入数据时执行逻辑。一次性事务排除了将一个片段的执行输出用作在不同服务器上执行的片段的输入。一次性事务足以应付许多工作负载，包括流行和规范的 TPC-C 基准。虽然可以扩展 Janus 的设计以支持一般事务，但这样做的代价是额外的服务器间消息和中止的可能性。

这种依赖跟踪和执行重新排序的方法已分别应用于并发控制和共识。 Janus 的洞见是并发控制和共识都可以使用一个通用的依赖图来实现合并而不中止。

我们在事务键值存储系统中实现了 Janus。为了与现有协议进行比较，我们还在同一框架中实现了 2PL + MultiPaxos、OCC + MultiPaxos 和 TAIR。我们使用微基准和流行的 TPC-C 基准在多个可用区域的 Amazon EC2 上运行实验。我们的评估表明，在无竞争的微基准测试中，Janus 的吞吐量是分层系统的 5 倍，是 TAIR 吞吐量的 90%。当工作负载因倾斜或广域延迟而变得有争议时，Janus 通过消除中止提供比现有系统低得多的延迟和更高的吞吐量（高达 6.8 倍）。

概述

本节描述了我们针对的系统设置，回顾了背景和动机，然后提供了 Janus 如何统一并发控制和共识的高级概述。

系统设置

我们的目标是广域设置，其中数据跨服务器分片，每个数据分片复制到几个地理上独立的数据中心以确保可用性。我们假设每个数据中心都维护一个完整的数据副本，这是一种常见的设置。现有协议或 Janus 并不严格需要此假设。但是，它简化了关于提交事务所需的跨数据中心往返次数的性能讨论。

我们采用将事务表示为存储过程的执行模型，这也是常用的。由于数据是跨机器分片的，因此事务由一系列存储过程（称为片段）组成，每个片段都访问属于单个分片的数据项。通过本地锁定，每个片段的执行相对于其他并发片段是原子的。存储过程执行模型对于 Janus 在争用下获得良好性能至关重要。由于 Janus 必须序列化冲突片段的执行，存储过程允许在服务器上执行，这比由客户端通过网络执行的执行效率高得多。

背景和动机

构建容错分布式事务的标准方法是在用于复制的共识协议之上对并发控制协议分层。分层设计解决了分布式事务存储面临的三个最重要的挑战：一致性、可扩展性和可用性。

一致性是指排除并发冲突操作的“不良”交错的能力。有两种冲突：第一种是含多个在不同数据分片上执行不可序列化数据访问的事务；第二种是事务在不同的副本服务器上以不同的顺序将其写入复制到相同的数据分片。并发控制处理第一种冲突以实现严格的可串行化；共识处理第二种以实现线性化。
可扩展性是指通过添加更多机器来提高性能的能力。并发控制协议自然地实现了可扩展性，因为它们对可以跨机器分区的单个数据项进行操作。相比之下，共识协议没有解决可扩展性问题，因为它们的状态机方法复制了副本服务器上的所有操作。
可用性是指从机器和网络故障（包括崩溃和任意消息延迟）中生存和恢复的能力。解决可用性挑战是共识协议的核心，而传统的并发控制并没有解决这个问题。

因为并发控制和共识都只能解决上述三个挑战中的两个，所以很自然地一个在另一个之上以覆盖所有基础。例如，Spanner 在 Paxos 上分层 2PL/2PC。 Percolator 在 BigTable 上分层 OCC 的一个变体，它依赖于主备份复制和 Paxos。

分层设计在概念上很简单，但不能提供最佳性能。当一个协议叠加在另一个协议之上时，一致性所需的协调会连续发生两次；一次在并发控制层，然后再一次在共识层。这会导致额外的延迟，这对于广域存储来说尤其昂贵。这种观察并不新鲜，TAIR 和 MDCC 已经提出了这一观察结果，指出分层存在过度协调的问题。

并发控制和共识的统一可以减少协调的开销。这种统一是可能的，因为并发控制的一致性模型（严格的可串行化）和共识（线性化的）具有很大的相似性。具体来说，两者都试图满足冲突操作之间的排序约束，以确保与线性总排序等价。表 1 对现有系统用于处理事务执行/提交期间和复制期间发生的冲突的技术进行了分类。如图所示，乐观方案依赖于中止和重试，而保守方案旨在避免代价高昂的中止。在保守的方案中，共识协议依赖（Paxos）领导者来分配复制操作的顺序，而事务协议使用逐项锁定。

为了统一并发控制和共识，必须使用通用的协调方案以相同的方式处理这两种类型的冲突。这种设计要求排除了基于领导者的协调，因为依赖单个领导者分配排序的分布式事务不能很好地扩展。 MDCC 和 TAPIR 通过依赖中止和重试来实现并发控制和共识的统一。这种乐观的方法最适合低竞争的工作负载。我们工作的目标是开发一种统一的方法，该方法可以通过避免中止而在竞争中很好地工作。

并发控制和共识的统一方法

我们能否设计一个统一的并发控制和共识，并使用一个通用的协调策略来最小化代价高昂的中止？一个关键的观察是并发控制和复制所需的排序约束都可以通过相同的序列化图抽象来捕获。在序列化图中，顶点表示事务，有向边表示由于两种类型的冲突而导致的事务之间的依赖关系。严格的可串行化和线性化都可以简化为检查该图是否没有循环。

Janus 试图通过跟踪冲突操作的依赖关系来显式捕获初步序列化图，而不立即执行它们。潜在的复制或事务冲突都表现为初步图中的循环。图 2a 中的循环是由于复制期间的冲突：在服务器 $S_{x}$ 上， $T_{1}$ 对数据项 $X$ 的写入在 $T_{2}$ 对 $X$ 的写入之前到达，导致 $T_{1} \to T_{2}$ 。相反的到达顺序发生在不同的服务器副本 $S_{x}^{'}$ 上，导致 $T_{1} \leftarrow T_{2}$ 。图 2b 中的循环是由于事务冲突造成的：服务器 $S_{x}$ 在 $T_{2}$ 对 item-x 的写入之前收到 $T_{1}$ 对 item-x 的写入，而服务器 $S_{y}$ 以相反的顺序接收对 item-y 的写入。为了确保无周期序列化图和无中止执行，Janus 在执行之前确定性地对周期中涉及的事务进行重新排序。

为了理解统一的优势和挑战，我们通过一个具体的例子来对比 Janus 的工作流程和 OCC + MultiPaxos 的工作流程。示例交易， $T_{1}$ ：x++; y++;，由两部分组成，每一部分都是一个递增 item-x 或 item-y 的存储过程。

图 1a 显示了 OCC + MultiPaxos 如何执行和提交 $T_{1}$ 。首先， $T_{1}$ 的协调者将这两部分分派给 item-x 和 item-y 各自的 Paxos 领导者，它们恰好位于不同的数据中心。领导者执行片段并在本地缓冲写入。为了提交 $T_{1}$ ，协调器向 Paxos 领导者发送 2PC-prepare 请求，Paxos 领导者执行 OCC 验证并将 x 和 y 的新值复制给其他人。因为这些片段是存储过程，我们可以结合调度和 2PC-prepare 消息，以便协调器可以在没有冲突的情况下在两个跨数据中心往返中执行和提交 $T_{1}$ 。假设并发事务 $T_{2}$ 也尝试增加相同的两个计数器。 $T_{1}$ 和 $T_{2}$ 的调度消息（或 2PC-prepares）可能由不同的 Paxos 领导者以不同的顺序处理，导致 $T_{1}$ 和/或 $T_{2}$ 中止并重试。另一方面，因为 Paxos 领导者对复制施加了排序，所以 item-x（或 item-y）的所有副本都一致地处理 $T_{1}$ 或 $T_{2}$ 的写入，但代价是额外的广域往返。

图 1b 显示了 Janus 的工作流程。为了提交和执行 $T_{1}$ ，协调器经过三个阶段：PreAccept、Accept 和 Commit，其中 Accept 阶段可以跳过。在 PreAccept 中，协调器将 $T_{1}$ 的片段分派到其相应的副本服务器。与 OCC+MultiPaxos 不同，服务器不会立即执行这些片段，而只是在其本地依赖图中跟踪它们的到达顺序。服务器用 $T_{1}$ 的依赖信息回复协调器。如果有足够多的副本服务器回复相同的依赖关系，协调器可以跳过接受阶段，这发生在服务器副本之间没有争用时。否则，协调器将与服务器进行另一轮通信，以确保它们为 $T_{1}$ 获得相同的依赖关系。在 Commit 阶段，每个服务器根据它们的依赖关系执行事务。如果存在涉及 $T_{1}$ 的依赖循环，则服务器在循环中执行事务时遵循确定性顺序。一旦协调器从最近的服务器副本（通常位于本地数据中心）收到回复，它就可以将结果返回给用户