两阶段提交算法详解

标签: 分布式

保留所有版权,请引用而不是转载本文(原文地址 https://yeecode.top/blog/115/ )。

前面的文章中我们详细介绍了线性一致性,包括线性一致性的约束等。并且,我们说两阶段提交就是一个常用的满足线性一致性的算法。

接下来我们介绍下两阶段提交算法。

1、 背景

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

一致性操作中的角色划分

具体实现似乎很简单,作为协调者的节点A只要在更新自身数据的同时将变更操作通知各个参与者,参与者收到协调者的变更通知后各自完成自身变更即可,如下图所示。这样,用户再从系统中读取该数据时,无论读请求落在哪个节点上,读取到的结果都是一致的。系统便满足了一致性。

节点间的一致性操作

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

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

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

类比后面要介绍的两阶段提交和三阶段提交,我们可以将上图所示的操作称为“一阶段提交”,因为整个一致性操作过程中只有一个“提交”阶段。

显然我们的“一阶段提交”并不能够很好地实现一致性操作。接下来我们要学习的就是更好的也更为实用的一致性算法:两阶段提交算法。

2、 2PC的实现

两阶段提交(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”消息、提交或回滚事务等。

上面就是两阶段提交算法的实现过程,还是十分简单的。我们可以方便地实现它。

3、 缺点

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

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

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

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

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

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

4、 展望

两阶段提交算法是满足线性一致性的,《分布式系统原理与工程实践》一书给出了证明。想要详细了解的同学可以翻看该书的相关章节。

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

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

书籍对各种一致性算法都进行了介绍,包括两阶段提交算法、三阶段提交算法等,并进行了详细分析。对大家体系化地掌握这些知识很有帮助。

书籍部分目录

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

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


好了,我是程序员易哥。

这回就说这么多!

可以关注我!等我下回接着说!

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

作者书籍推荐