2PC之踵？是时候升级二阶段提交协议了

2019 年 1 月 28 日 高可用架构

两阶段提交协议（2PC）已经在企业软件系统中使用了三十多年。它是一种非常有影响力的协议，用于确保访问多个分区或分片中的数据的事务的原子性和持久性。它无处不在 - 无论是在旧的“古老的”分布式系统、数据库系统和文件系统，如Oracle，IBM DB2，PostgreSQL 和 Microsoft TxF（支持事务的 NTFS）还是在较年轻的“千禧”系统如 MariaDB、TokuDB、VoltDB、Cloud Spanner、Apache Flink、Apache Kafka 和 Azure SQL 数据库。如果您的系统支持跨分片/分区/数据库的 ACID 事务，那么它很可能会在后台运行 2PC（或其某些变体）。有时它甚至出现在“前台” - 旧版本的 MongoDB 要求用户在应用程序代码中为多文档事务实现 2PC。

在这篇文章中，我们将首先介绍一下 2PC：它是如何工作的以及它解决了什么问题。然后，我们将展示 2PC 的一些主要问题以及现代系统如何试图解决它。不幸的是，这些尝试的解决方案也带来了一些其他问题。在文章最后，我将说明下一代分布式系统应该避免使用 2PC，以及如何实现这一点。

2PC 协议概述

2PC 有很多变种，但基本协议的工作原理如下：

背景假设：一个事务相关的工作已经划分给存储该事务数据的分片节点。我们将在每个分片中执行的工作，称为节点“参与者”的工作。当事务准备好“提交”时，每个参与者都能够独立于彼此完成事务相应的职责。2PC 协议由单个独立的、可协调的节点发起（可能是参与者之一）。

2PC 协议的基本流程如下图所示。（协议从图的顶部开始，然后向下进行。）

阶段1：协调者询问每个参与者，是否已成功完成其对该事务的职责，并达到可以提交的状态。每个参与者都回答“同意”或“反对”。

阶段2：协调者统计所有回应，如果每个参与者都回答“同意”，那么就提交事务，否则就中止事务。协调者向每个具有提交最终决策权力的参与者发送消息，并接收参与者的确认消息。

此机制确保事务的原子性属性：整个事务将反映在系统的最终状态中，或者不反映在系统的最终状态中。即使只有一个参与者没有提交，那么整个事务将会被中止。换句话说：每个参与者对事务都有“否决权”。

它还确保了事务的持久性。每个参与者确保在阶段1响应“同意”之前，已将所有事务持久地写入存储。这使协调者对事务做出最终决定时，无需担心参与者在投票“同意”之后写入失败。在这篇文章中，当使用术语“持久写入”时，我们有目的地模糊化了两个区别 - 本地临时性存储，或是分布式的写入到多个分片以“持久化”。

除了持久地写入事务相关的数据之外，协议本身还需要额外的写入，在处理消息之前必须使其持久化。例如，一名参与者在第一阶段投票“同意”之前拥有否决权，但在此之后，它不能改变其投票结果。但如果它在投票“同意”后立即崩溃怎么办？当它恢复时，它可能不知道它投了“同意”，仍然认为它拥有否决权，并继续流程并中止事务。为了防止这种情况，它必须在“同意”投票发给协调者之前，持久化相关投票结果。（除了这个例子，在标准的 2PC 流程中，还有另外两种消息需要发送前持久化操作。）

2PC 的问题

2PC 存在两个主要问题。第一个是众所周知的，并在所有讲述 2PC 的教科书中都进行了讨论。第二个不太知名，但仍然是一个大的问题。

众所周知的问题被称为“阻塞（block）问题”。当每个参与者都投了“同意”，但协调者在将最终决定的消息未能发送给至少一参与者之前就挂了，就会出现这种情况。问题的原因是，通过投票“同意”，每个参与者已经取消了否决事务的权力。但是，协调者仍有绝对权力来决定事务的最终状态。如果协调者在向至少一名参与者发送最终决定的消息之前挂了，那么参与者就无法做出最终决定 - 他们不能中止，因为协调者可能会在挂掉之前决定提交，并且他们无法提交，因为协调者可能决定在失败之前中止。因此，他们必须等待---等到协调者恢复---以便得到最终决定。与此同时，他们无法处理与停滞冲突的事务，因为该事务的写入的最终结果尚未确定。

阻塞问题有两种解决方案。方案一是修改核心协议以消除阻塞问题。不幸的是，这些修改降低了性能 - 通常通过添加额外的一轮通信来实现 - 因此很少在实践中使用。

方案二是保持协议不变，但降低协调者失败从而引发阻塞的可能性 - 例如，通过在副本共识协议上运行 2PC 并确保协议的重要状态被复制。不幸的是，这些解决方案再一次降低了性能，因为协议要求这些副本共识轮次按顺序进行，因此它们可能会给协议增加显著的延迟。

鲜为人知的问题是我称之为“拥堵(cloggage)问题”。在处理事务之后进行 2PC，必然增加事务的等待时间，它等于运行协议所花费的时间。延迟的增加对于许多系统来说已经是一个问题，但更大的问题是，工作节点必须到第二阶段中期才知道事务的最终结果。在他们得到最终结果之前，他们必须为可能中止事务的可能性做好准备，因此在事务得到确认之前，他们通常会暂停其他有冲突的事务进行。这些阻塞的事务同样会进一步阻止其他事务运行，依此类推，直到 2PC 完成，所有被阻止的事务才可以恢复。这些拥堵问题进一步增加了事务平均延迟，并且降低了整体的事务吞吐量。

总结我们上面讨论的问题：2PC 在四个方面污染了系统架构：

延迟（协议的时间加上冲突事务的停顿时间）
吞吐量（因为它碰到冲突的事务会停顿）
可扩展性 （系统越大，事务更需要多分区的支持，并且必须付出 2PC 的吞吐量和延迟成本以及
可用性（前面提到的阻塞问题）。

没有人喜欢 2PC，但几十年来，人们都认为它是一种必要的妥协。

是时候改变了

三十多年来，业界一直在分布式系统中使用两阶段提交。我们已经意识到引入 2PC 会带来性能、可伸缩性和可用性问题，但在没有更好的替代方案之前，仍需要选择使用它。

真相就是，如果有更好的方案，2PC 就没必要存在了。为了实现这一目标，无论是在学术界（如SIGMOD 2016论文）和工业界都在进行尝试。通常的做法是避免分布式事务，例如通过在提交事务之前将数据重新分片，使得事务不再是分布式事务。不幸的是，这种重新分片的做法降低了系统的性能。

我倡导对分布式系统架构进行更深层次的优化。我坚持认为系统可以使用更简单和高效的提交协议，在保证 ACID 的同时，能够处理分布式事务。

一切问题的根源来自一个存在数十年的假设：事务可能随时以任何理由中止。即使我在相同的初始系统状态下运行相同的事务，在下午 2:00 它可能可以成功提交，但在 3:00 时却会提交失败。

为什么需要该假设？大多数架构师认为有以下几个原因。首先，节点可能在任何时候失败，包括在事务处理过程中。系统故障恢复过程中，由于无法获取故障前的内存状态，因此也无法恢复事务失败之前的现场。因此系统需要中止故障出现时所有相关事务。由于任何时候都可能发生故障，这意味着事务可能随时中止。

其次，大多数并发控制协议都需要能够随时中止事务。乐观协议在处理事务后执行“验证”，如果验证失败，则中止事务。悲观协议通常使用锁来防止并发异常，这种锁的使用可能会导致死锁，然后又需要通过中止（至少）事务的方法来解决死锁问题。由于可能随时出现死锁，因此事务需要保留随时中止的能力。

如果来重新审视两阶段提交协议，您将看到随时中止事务的可能性，是 2PC 协议中复杂和延迟的主要原因。参与者不能轻易地告诉其他方是否同意提交，因为他可能在此之后（在事务提交前）出现故障，然后在故障恢复期间中止此事务。因此，他们必须等到事务结束（当所有重要状态都已经持久化）并且严格按照两个阶段进行处理：在第一阶段，每个参与者公开放弃其控制以中止事务，然后才能进入第二阶段，作出最终决定并进行广播。

在我看来，我们需要从参与者中移除否决权，并且以系统无法在执行期间随时中止事务的假设来进行架构设计。只接受以业务逻辑需要来否决事务的情况。如果在给定数据库当前状态下，理论上可以提交事务情况下，无论发生何种类型的故障，该事务都必须可以提交。此外也不接受由于其他并发运行导致的竞争条件而不能最终提交或中止事务。

消除随意中止事务的灵活性听起来很难。我们将很快讨论如何实现这一目标。但首先让我们观察在不能随意中止事务的情况下，提交协议会如何变化。

当事务不能随意中止时，提交协议是什么样的

我们来看两个例子：

在第一个例子中，假设存储变量 X 的节点需要执行一个任务：将 X 的值更改为 42。假设在 X 上没有定义完整性约束或触发器（这可能会阻止系统将 X 设为 42）。在这种情况下，该参与方永远没有中止事务的权力。无论发生什么，该参与方必须将 X 更改为42，如果修改过程中出现系统故障，则必须在故障恢复后将 X 设成 42。由于参与方没有随意中止事务的能力，因此在提交协议期间，不需要检测参与方是否可以提交。

在第二个例子中，假设存储变量 Y 和 Z 值的节点接收到两个事务任务：从前一个 Y 值中减去 1 并将 Z 设置为 Y 的新值。此外，假设 Y 上存在完整性约束，表明 Y 永远不会低于 0（例如它代表零售应用程序中的库存）。因此，此参与方必须运行以下代码：

IF (Y > 0)

Subtract 1 from Y

ELSE

ABORT the transaction

Z = Y

因为应用程序的逻辑需要这样做，所以必须赋予参与者中止事务的权力。但是这种权力是受限的。只有当 Y 的初始值为 0 时，才能中止该事务，否则必须提交。因此，参与方不必等到完成事务之后才知道它是否需要提交。相反：一旦它完成了事务中第一行代码的执行，它就已经知道了最终需要提交还是中止。这意味着相比于 2PC 而言，提交协议将能够更早地启动。

现在让我们将这两个例子组合成一个例子，其中一个事务由两个参与者执行 - 其中一个参与者正在完成第一个例子中描述的工作，另一个参与者正在完成第二个例子中描述的工作。由于我们保证原子性，第一个参与者不能简单地将 X 设置为 42，相反，它自己的工作依赖于 Y 的值。实际上，第一个参与者的事务代码变为：

temp = Do_Remote_Read(Y)

if (temp > 0)

X = 42

请注意，如果第一个参与者的代码如上的话，那么另一个参与者的代码可以简化为：

IF (Y > 0)

Subtract 1 from Y

Z = Y

通过以这种方式编写事务代码，两个参与方都删除了显式中止逻辑。相反，两个参与方都有 if 语句来检查是否会导致原始事务中止的约束。如果原始事务中止，两个参与方最终都无所作为。否则，两个参与方都会根据事务逻辑更改其本地状态。

此时需要注意的一点是，在上面的代码中完全消除了对提交协议的需求。除了应用程序代码在给定数据状态下定义的条件逻辑以外的任何原因，系统都不允许中止事务。并且所有参与者都在这个相同的条件上调整他们的动作，这样他们就可以独立地决定，在由于当前系统状态而无法完成事务的情况下“什么也不做”。因此，已经消除了事务中止的所有可能性，并且在事务处理结束时不需要任何类型的分布式协议来做出关于事务组合的最终决定。2PC 的所有问题都已消除。因为没有协调者，所以也没有阻塞（block）问题。因为所有必要的检查都与事务处理时候完成，而非在事务完成之后检查，所以没有拥堵（cloggage）问题。

此外，只要不允许系统因应用程序逻辑之外的任何原因而中止事务，总是可以像上面那样重写任何事务以替换代码中的中止逻辑，即 if 语句有条件地检查中止条件。此外，可以在重写应用程序代码的情况下实现此目的。（有关如何执行此操作的详细信息超出了本文的范围，但可以高屋建瓴地总结为：当一个节点执行了导致中止的条件逻辑时，它可以设置特殊的标记，其他节点可以在远程读取这些标记。）

实质上：在事务处理系统中有两种类型中止：（1）由数据状态引起的中止和（2）由系统本身引起的中止（例如故障或死锁）。如上所述，类别（1）总是可以根据数据的条件逻辑来编写。因此，如果您可以消除类别（2）中止，则可以消除提交协议。

所以现在，我们所要做的就是解释如何消除类别（2）中止。

消除系统本身中止

我花了将近十年的时间来设计没有系统引发中止的系统。此类系统的示例是 Calvin，CalvinFS，Orthrus，PVW 以及惰性处理事务系统。这一特性的推动力来自于--- Calvin ---因为它是一个确定性数据库系统。确定性数据库保证在给定一组定义的输入请求的情况下，数据库中只有一个可能的最终数据状态。因此，如果将相同的输入发送到系统的两份不同的副本，两份副本将独立地处理该输入，并将最终达到一致的结果。

系统本身中止，例如系统故障或并发控制竞态条件，从根本上说是不确定性事件。一个副本很可能碰见系统调用失败或进入竞态条件，而另一个副本则不会。如果允许这些非确定性事件导致事务中止，则一个副本会中止事务而另一个副本将提交事务 - 这是对确定性的违背。因此，我们必须以系统故障和竞态条件不能导致事务中止的方式设计 Calvin。对于并发控制，Calvin 使用了避免死锁技术的悲观锁定，该技术确保系统永远不会陷入由于死锁导致的事务中止的状况。面对系统故障，Calvin 无法从中断的位置重启事务（因为在故障期间失去了内存状态）。尽管如此，通过从相同的原始输入重新启动事务，它依然能够完成该事务的处理而不必中止它。

这些解决方案（包括防止死锁以及故障重启恢复事务），都不局限于在确定性数据库系统中使用。在非确定性系统中，如果失败期间，丢失的事务状态被其他非故障节点侦测到，那么事务重启变得略微棘手。但是也有一些简单的方法来解决这个问题，但这些方法已经超出了本文讨论的范围。实际上，我上面提到的其他系统都是非确定性系统。一旦我们意识到消除系统本身故障所带来的威力，我们就将设计植入到 Calvin 之后构建的每个系统中 - 甚至是非确定性系统。

结论

系统架构师继续在分布式系统中使用 2PC 的好处微乎其微。我认为，忽略系统本身中止以及状态写入故障是更好的前进方法。确定性数据库系统（如 Calvin 或 FaunaDB）总是会规避系统本身中止，因此通常可避免 2PC。但是这种优势仅发挥在确定性数据库是一个巨大的浪费。从非确定性系统中消除系统本身引起的中止并不困难。最近的项目表明，甚至可以在不使用悲观并发控制技术的系统中消除系统引起的中止。例如，我们上面链接的 PVW 和惰性事务处理系统都使用多版本并发控制（MVCC）的变体。FaunaDB 使用乐观并发控制的变体。

在我看来，几乎没有理由坚持过时的系统性中止假设，当系统在单台机器上运行时，这种假设是合理的。然而，很多现代系统已经扩展到到多台可以故障隔离的机器上。维持该假设就需要成本高昂类似 2PC 的协调和提交协议。2PC 的性能问题一直是非 ACID 系统兴起的主要推动力，这些系统放弃了强一致性保证，以达到更好的可扩展性、可用性和性能。2PC 太慢了！它增加了所有事务的延迟，不仅仅是协议本身的时间占用，还阻止了访问相同数据的其他事务的并发执行。此外，2PC 还限制了可伸缩性（通过降低并发性）和可用性（我们上面讨论的阻塞问题）。前进的道路已经很明确：我们需要在设计系统时重新审视过时的假设，并对两阶段提交说“再见”！

英文版地址：

http://dbmsmusings.blogspot.com/2019/01/its-time-to-move-on-from-two-phase.html