从两阶段提交算法到三阶段提交算法

保留所有版权，请引用而不是转载本文（原文地址 https://yeecode.top/blog/118/ ）。

现在，分布式系统越来越多。不理解分布式系统，都不好意思说自己会编程。而说起分布式系统，则绕不开各种一致性问题。

假设我们要在一个分布式系统中实现一致性，应该怎样做？

大家可能脱口而出：用两阶段提交算法或者三阶段提交算法。

那大家对这些算法的细节了解的清楚吗？知道两者的区别么？为什么它们可以满足顺序一致性？

本文将会解答这些问题。接下来，带大家详细了解这两个算法。

背景

假设一个分布式系统中存在多个节点，如下图所示，其中的节点A收到了数据变更请求。如果系统要满足一致性，那节点A在完成自身数据变更的同时必须协调其他节点完成数据变更。这种情况下，我们将发起操作的节点称为协调者(Coordinator)，而将接受操作的节点称为参与者(Participants)。在图中，节点A是协调者，节点B和节点C都是参与者。

具体实现似乎很简单，作为协调者的节点A只要在更新自身数据的同时将变更操作通知各个参与者，参与者收到协调者的变更通知后各自完成自身变更即可,如下图所示。

这样，用户再从系统中读取该数据时，无论读请求落在哪个节点上，读取到的结果都是一致的。系统便满足了一致性。

可在实际中并没有这么理想：协调者和参与者之间的通讯可能不可靠，参与者也可能因为各种内部原因导致更新失败。

协调者更新了自身状态后通知参与者，假设某个参与者因为通讯原因或者节点自身原因更新失败，则那用户便可能从集群中读取到不一致的结果。这时系统的一致性便被打破。

发生这种不一致的根源是每个节点都能知道自身是否操作成功，但却无法知道其他节点是否更新成功。

类比后面要介绍的两阶段提交和三阶段提交，我们可以将上图所示的操作称为“一阶段提交”，因为整个一致性操作过程中只有一个“提交”阶段。显然我们的“一阶段提交”并不能够很好地实现一致性操作。

接下来我们要学习的就是一些更好的也更为实用的一致性算法。也就是两阶段提交算法和三阶段提交算法。

两阶段提交算法和三阶段提交算法能够实现的一致性是指线性一致性。而弱一致性算法，例如我们常听说的最终一致性算法，都是在线性一致性的基础上放宽约束实现的。所以，实现线性一致性的算法十分重要，例如各种分布式事务就要用到它！

两阶段提交

两阶段提交（Two-phase Commit，简称2PC）是一种比较简单的一致性算法（或者说协议）。它将整个提交过程分成了准备阶段（Prepare）、提交阶段（Commit）这两个阶段。

具体实现

在准备阶段中，可以细分成如下的操作步骤：

1. 协调者给参与者发送“Prepare”消息，“Prepare”消息中包含了此次更新要进行的所有操作。然后协调者等待各个参与者的响应。
2. 参与者收到“Prepare”消息后将消息中的操作封装为一个事务并执行，但不要提交。
3. 参与者在执行事务的过程中如果遇到任何问题导致事务中的操作无法完成，则向协调者回应“No”消息；如果事务中的全部操作能够完成，则向协调者回应“Yes”消息。

经过准备阶段，所有的参与者已经尝试完成了所有的操作，但是没有把这些操作提交。并且，根据将自身能否完成操作的结果回应给了协调者。接下来，便进入了第二个阶段：提交阶段。

在提交阶段中，协调者会根据收集到的各个参与者的回应执行不同的操作。

如果协调者收到了所有参与者的“Yes”消息，则进行如下操作：

1. 协调者向参与者发送“Commit”消息。
2. 参与者收到“Commit”消息后，提交在准备阶段已经完成但尚未提交的事务。
3. 参与者向协调者发送“Done”消息。
4. 协调者收到所有参与者的“Done”消息，表明该一致性操作以成功的形式结束。

如果协调者在一定时间内没有收齐所有参与者的消息，或者收到的消息中有“No”消息，则进行如下操作：

1. 协调者向参与者发送“Rollback”消息。
2. 参与者收到“Rollback”消息后，回滚在准备阶段已经完成但尚未提交的事务。
3. 参与者向协调者发送“Done”消息。
4. 协调者收到所有参与者节点的“Done”消息，表明该一致性操作以回滚的形式结束。

可见在提交阶段，无论是决定要“Commit”还是“Rollback”，整个一致性操作都能结束。

下图展示了两阶段提交的消息流。其中图的左侧部分表示一致性操作成功情况下的消息流；图的右侧部分表示因部分参与者不回应导致的一致性操作失败情况下的消息流。

上述过程中，协调者可以是一个专门起到协调作用而不参与一致性操作的节点，也可以是一个参与一致性操作的节点。如果它是后者，那它不仅要完成协调者的工作，还要作为参与者完成所有参与者要进行的工作，即它也要将操作封装成事务执行、回应“No”消息或“Yes”消息、提交或回滚事务等。

优劣

两阶段提交的操作步骤比较简单，但也有几个明显的问题。

首先，两阶段提交存在同步阻塞问题。参与者收到协调者发出的“Prepare”消息后，会开启事务完成消息中的操作。事务的开启意味着参与者的并发处理能力将受到很大的影响。而且，参与者不是一个节点而是一群节点，所以整个系统中的节点都会因为事务的开启而阻塞。这个过程可能很长，要等待协调者收集完参与者的消息并发布进一步的消息后，该过程才能结束。

其次，两阶段提交高度依赖协调者发出的消息，因此存在单点故障。如果协调者在两阶段提交的过程中出现问题，则会导致系统失控。尤其是在准备阶段和提交阶段之间，如果此时协调者宕机，则会导致已经开启了事务的各个参与者既不能收到“Commit”消息，也不能收到“Rollback”消息。这样事务会一直开启，导致系统全局阻塞。

第三，两阶段提交其实设置了一个假设：如果参与者能够收到和正常回应“Prepare”消息，那它应该也能正常收到“Commit”消息或者“Rollback”消息。通常，这个假设是成立的。因为参与者在准备阶段和提交阶段之间宕机的概率很小。但是，再小的概率也有可能发生，尤其是在高并发和多节点的情况下。一旦因为网络抖动导致部分参与者无法收到“Commit”消息，则会出现部分参与者提交了事务，部分参与者未提交事务这种不一致情况的发生。

第四，两阶段提交存在状态丢失问题。如果协调者在发出“Commit”消息或者“Rollback”消息后宕机，部分参与者收到了这条消息后提交或者回滚了事务，部分参与者没有收到这条消息。那即使重新选举出一个新的协调者，新的协调者也无法确定各个参与者到底处在哪个状态。

为了解决两阶段提交的缺陷，出现了三阶段提交。

三阶段提交

三阶段提交（Three-phase Commit，简称3PC）是二阶段提交的改进，它修复了二阶段提交的一些缺陷，但也使得整个一致性操作过程多出了一个阶段，更为复杂。此外，三阶段提交还引入了一些超时机制，以便于节点在失去或者部分失去与外界联系时做出一些操作。

三阶段提交一共分为三个阶段：CanCommit阶段、PreCommit阶段、DoCommit阶段。

具体实现

CanCommit阶段可以细分为以下步骤：

1. 协调者向参与者发送“CanCommit”消息，询问参与者能否完成消息中的操作。然后协调者等待各个参与者的响应。
2. 参与者接收到“CanCommit”消息后，判断自身是否能够顺利完成操作。如果自身可以，则向协调者回应“Yes”消息；如果自身不可以，则向协调者回应“No”消息。

在CanCommit阶段，协调者和参与者只是就能否完成操作进行了交流，并没有进行实际的工作。接下来进入PreCommit阶段。

PreCommit阶段则根据协调者收到的参与者的反馈不同而不同。

如果协调者收到了所有参与者的“Yes”消息，则进行如下操作：

1. 协调者向参与者发送“PreCommit”消息。然后协调者等待各个参与者的响应。
2. 参与者收到“PreCommit”消息后，将此次要进行的操作封装成事务执行，但不要提交。
3. 如果参与者完成了各项操作，则向协调者回应“ACK”消息。

在这种情况下，一致性操作则会进入DoCommit阶段。

如果协调者在一定时间内没有收齐所有参与者的消息，或者收到的消息中有“No”消息，则进行如下操作：

1. 协调者向所有参与者发送“Abort”消息，表明此次一致性操作取消。
2. 参与者收到“Abort”后，中止当前的操作。如果参与者在一定时间内没有收到协调者发来的操作消息，也中止当前的操作。

这种情况下一致性操作结束，无需再进入DoCommit阶段，

在DoCommit阶段中，协调者会根据参与者的回应采取不同的操作。

如果协调者收到了所有参与者的“ACK”消息，则进行如下的操作：

1. 协调者向参与者发送“Commit”消息。
2. 参与者收到“Commit”消息后，提交在准备阶段已经完成但尚未提交的事务。
3. 参与者向协调者发送“Done”消息。
4. 协调者收到所有参与者的“Done”消息，表明该一致性操作以成功的形式结束。

如果协调者在一定时间内没有收齐参与者的“ACK”消息，则进行如下的操作：

1. 协调者向参与者发送“Rollback”消息。
2. 参与者收到“Rollback”消息后，回滚在准备阶段已经完成但尚未提交的事务。
3. 参与者向协调者发送“Done”消息。
4. 协调者收到所有参与者的“Done”消息，表明该一致性操作以失败的形式结束。

下图展示了三阶段提交的消息流。其中图的左侧部分表示一致性操作成功情况下的消息流；图的右侧部分表示因部分参与者在CanCommit阶段回应“No”消息导致的一致性操作失败情况下的消息流。

在DoCommit阶段中，如果参与者在一定时间内没有收到“Commit”消息或者“Rollback”消息，则参与者会提交事务。这是因为既然能够进入DoCommit阶段，说明所有的参与者在CanCommit都回应了“Yes”。此时，所有的参与者都应该可以正确地提交事务，从而完成该一致性操作。

DoCommit阶段中参与者会在无法收到“Commit”消息或者“Rollback”消息时提交事务，这解决了两个问题。首先，整个一致性操作不会因为协调者的突然宕机而导致参与者开启的事务无法关闭，从而阻塞整个系统。其次，如果协调者在发送“Commit”指令前后宕机，则整个系统的状态是确定的，因为各个参与者都会默认提交事务。

三阶段提交也同样存在一个同步时刻，其线性一致性证明和两阶段提交类似，我们不再赘述。

优劣

当然，这个机制仍然存在漏洞。如果协调者在发送“Rollback”消息后宕机，部分参与者收到了“Rollback”消息回滚了事务；部分参与者因为没有收到“Rollback”消息便会默认提交事务。这将导致系统的一致性被打破。而且即使选举出新的协调者，新协调者也无法判断哪些参与者回滚了事务，哪些参与者提交了事务。

不过，这种漏洞的发生概率极小。“Rollback”消息在DoCommit阶段发出，既然能够进入该阶段，说明所有参与者在CanCommit阶段都回复了“Yes”消息，则大概率会在PreCommit阶段正常回复“ACK”消息。因此，协调者因为无法收起“ACK”消息而发出“Rollback”消息的概率很低，而在发出“Rollback”消息后恰好宕机的概率则更低。

因此，三阶段提交通过加入一个新的阶段和引入超时机制减少了两阶段提交的同步阻塞问题，减弱了对协调者的依赖，降低了系统状态丢失的概率。然而，正如我们上面所分析的，三阶段提交依然存在漏洞，并不完美。

总体而言，两阶段提交和三阶段提交的实现比较简单，且能够实现线性一致性。尤其是三阶段提交，其故障概率很低，在实践中应用十分广泛。

拓展：线性一致性证明

两阶段提交算法和三阶段提交算法都可以实现线性一致性。

那能不能证明一下呢？

下面我们以两阶段提交算法为例，证明这一点。三阶段提交算法的证明方法是一样的。

阅读这里需要大家对一致性的概念、线性一致性的约束有较好的理解。不太清楚的同学可以参考书籍《分布式系统原理与工程实践》。

在证明之前，我们首先确认两点：

• 考虑到网络延迟、节点处理速度等的不同，各个节点收到“Prepare”消息并创建事务是有先后的。
• 考虑到网络延迟、节点处理速度等的不同，各个节点收到“Commit”消息并提交事务是有先后的。

在一次成功的二阶段提交操作中一定存在一个全局锁时段。这一时段从准备阶段的最后一个“Yes”消息发出开始，到提交阶段的第一个“Commit”消息被接收结束。在这一时段中，所有的节点都已经创建事务但未提交事务。

在全局锁时段之后，是提交时段。这一时段从提交阶段的第一个“Commit”消息被接收开始，到提交阶段的最后一个“Done”消息发出为止。在这一时段中，各个节点陆续完成事务提交，如图所示。

这里我们假设参与者开启事务和发出Yes消息是同时进行的，参与者收到Commit消息和提交事务是同时进行的。这两个假设都不会影响最终的结论。

在全局锁时段和提交时段之间存在一个同步时刻。同步时刻在全局历史中是唯一确定的，且这一时刻具有以下特点：

• 除当前的2PC操作外，没有其他操作正在集群中开展。全局锁时段中在各个节点创建的锁可以共同保证这一点。
• 对于任何一个节点而言，该时刻之后进行的第一个操作都是当前2PC的提交操作。

那我们可以等价地认为2PC操作引发的变更就是在同步时刻发生的。这样，2PC提交操作在全局历史中的位置就被确定了下来。因此，任何通过2PC操作开展的事件都可以唯一地映射到全局历史中，就像是在全局历史中开展的事件一样，那这样的操作自然可以保证线性一致性。

接下来，我们再用一个更为宏观视角的示例来理解这一过程。

在下图中，节点A作为协调者发起了一次两阶段提交操作A2，并触发了参与者节点B和节点C的B2和C1操作。

可以看出，两阶段提交事件A2和另外的B1、B3事件是并发的。我们可以给出线性一致性要求的全局历史：

• A1-A2、B1、B3并发- C2

根据线性一致性的约束，A1事件发生在A2事件之前，读到的变量x必须为旧值；C2事件发生在A2事件之后，读到的变量x必须为新值。显然在二阶段提交中这两者都是满足的。

线性一致性要求单个节点的事件历史在全局历史上符合程序的先后顺序，但是对于并发事件没有约束。因此，关于B1、B2读取变量x的操作存在以下几种情况，且都满足线性一致性的所有约束。

• B1和B3都读取到A2变更前的旧值
• B1读取到A2变更前的旧值、B3读取到A2变更后的新值
• B1和B3都读取到A2变更后的新值

进一步地，我们可以把A2操作的两阶段提交细节步骤标注出来，如图所示。

这时我们可以得出结论：

• 在同步时刻，一定不会发生读取变量x的操作
• 在同步时刻之前，读变量x一定会读取到旧值
• 在同步时刻之后，读变量x一定会读取到新值

上述A2操作的两阶段提交细节步骤是我们臆想绘制出来的。在实际的2PC操作中，同步时刻在2PC中的具体位置是难以确定。

可见，两阶段提交不对并发事件给出保证。但我们知道，一定存在一个同步时刻，将两阶段提交映射到全局历史上。这个时刻可能在B1之前，可能在B1和B3之间，可能在B3之后，如下图所示。

本质上，两阶段提交是通过给各个节点同时加锁来实现了一个全局同步的时钟，这个时钟并不能够用来记录时间的长短，但足以标定出两阶段提交在全局历史中的位置，借此实现了线性一致性。

到这里，我们就证明了两阶段提交算法能够实现线性一致性。

当然，实现这一全局同步的时钟的代价也是很高的，它直接导致了所有节点的阻塞，影响了分布式系统的并发性能。这也正是三阶段提交算法的改进点。

三阶段提交也同样存在一个同步时刻，其线性一致性证明和两阶段提交类似，我们不再赘述。

总结

说到这里，可能有人会说，还有一个重要的一致性算法——Paxos算法——我们没有讲！

如果问出这个问题，则说明他对一致性的概念是混乱的。因为：Paxos算法是一个共识算法，而不是一致性算法。虽然，确实很多网上的资料都讲Paxos算法当做一致性算法。这种错误的认识，应该就是大家在学习分布式系统时容易感到混乱的原因。

关于共识算法、一致性算法的区别，以及共识算法（包括Paxos算法、Raft算法）的详解，大家可以参考下面的书籍。会帮助大家对分布式系统的一致性建立更全面系统的认识。

《分布式系统原理与工程实践》

书中对各种一致性算法都进行了详细的介绍。还详细阐述了共识算法，给出了Paxos算法的推导过程、理解分析、具体示例。应该是最简单易懂的Paxos讲解书籍了。

另外这本书对分布式系统相关的理论、实践、工程知识均进行了详细的介绍，层层递进，有助于大家建立完整的分布式系统知识体系。涉及一致性、共识、Paxos、分布式事务、服务治理、微服务、幂等、消息系统、Zookeeper等。并且还发行了繁体版！

再次提醒大家，在学习分布式系统时，因为涉及到的理论、框架很多。所以大家一定要理清知识脉络，否则容易学得越多越混乱。

这是一篇近万字的长文，希望能帮助到大家！

别忘了点赞……

也欢迎关注我！

我是程序员易哥。

可以访问个人知乎阅读更多文章：易哥（https://www.zhihu.com/people/yeecode），欢迎关注。

作者书籍推荐