2PC & 3PC

Two Generals' Problem

Two Generals' Problem 是一个思想实验,模拟的是网络中两个节点如何通过不可靠的连接通信的问题。

问题描述:有两支军队在两个山坡上安营扎寨,准备进攻处在两个山坡之间山谷的敌军。两支军队的将军需要协商一个相同的时间点同时发起进攻,若只有一方发起进攻,就会全军覆没。两位将军只能通过信使来通信,然而信使必须通过山谷才能到达对面军营,信使有可能在半道被敌军俘虏。两位将军只能发送消息、接收消息,是否存在一种协议或策略能使得两位将军协调到一致的进攻时间?

路径分析

最好的情况:

假设一切顺利,信使成功穿越敌军军营:

将军 B 收到将军 A 发送的 "确认收到" 的消息后,两位将军就在进攻时间上达成共识(consensus)。

最坏的情况:

任何一次通信过程中,信使都有可能被俘虏,将军A 与将军 B 永远也无法达成一致。

小结

Two Generals' Problem 是被证明无法解决的计算机通信问题,两个节点无法在面临崩溃及不可靠网络下达成共识,它决定了分布式系统中的一致性协议的天花板。

Consensus Problem

Two Generals' Problem 模拟了两个节点在不可靠网络下达成共识的问题,这个问题可以进一步被泛化:

多个节点如何在可能出现节点崩溃、网络不可靠的情况下达成共识,即 Consensus Problem。

Consensus Problem 是分布式系统实现可靠性的基石,典型的应用包括:

  • commit a transaction to a database

  • leader election

  • state machine replication

  • atomic broadcasts

本文要讨论的是 consensus problem 的子问题:

achieving atomic transaction commit across multiple nodes

即分布式事务问题:如何保证涉及多个节点的写操作的原子性。两种典型的方案就是 Two Phase Commit (2PC) 和 Three Phase Commit (3PC)。

Two Phase Commit

2PC 的过程看起来很简单,分为两个阶段,Propose 和 Commit。在 2PC 中除了执行写操作的节点之外 (voters),还需要一个新的角色 --- coordinator/transaction manager,负责协调事务推进。以足球队为例,教练为 coordinator,队员为 voter,教练组织队员比赛时,他可以先一个一个地给队员打电话,询问是否能参加,即 Propose 阶段。若所有队员同意,则一个一个地给队员打电话,告知确认其它队员都能参赛;若有至少一名队员不同意,则一个一个地给队员打电话,告知比赛因有队员缺席而取消。整个过程如下图所示:

在网络中,假设其中一个节点想要在某个点上与其它节点达成共识,就成为 coordinator,而其它节点自动成为 voter。进入到 Propose Phase,coordinator 向其它节点发送 propose 消息;若 voters 都同意,则再进入到 Commit Phase,向 voters 发送 commit 消息。

若有任意 voter 反对,则进入到 Commit Phase,coordinator 向 voters 发送 abort 消息。

以上就是 2PC 的概述,但这样就能保证跨节点分布式事务的原子性了吗?光从以上的描述中似乎并不能让我们说服自己:

  • voter 同意以后崩溃了怎么办?

  • coordinator 在 commit phase 中刚告诉一个 voter 消息后崩溃了怎么办?

  • 期间任何消息超时怎么办?

  • ...

一切可能导致事务的中间状态的情况都似乎依然有可能出现!要理解 2PC 的正确性,我们还需要深入理解其中的细节:

  1. 当应用想要启动一个分布式事务时,它需要从 coordinator 处获得一个全局唯一的 transactionID

  2. 应用在每个节点上分别启动单节点事务,并将 transactionID 传入其中,单节点所涉及的所有读写操作都应该在一个事务中进行,在这个过程中任意节点出问题,coordinator 或节点本身都可以 abort

  3. 当应用已经为 commit 做好准备时,coordinator 发送 prepare 请求到所有节点,并带上 transactionID 信息,其中任何一个请求失败或者超时,coordinator 就发送 abort 请求到所有节点,并带上 transactionID 信息。

  4. 当任意一个节点收到 prepare 请求时,它必须保证在未来发生任何事情时都能成功 commit 这个事务,包括节点崩溃、违反约束、断电、磁盘空间不足等等。因此节点实际上需要预留出相关的资源保证事务可以推进。一旦该节点回复 yes 给 coordinator,就意味着他一定可以完成这个事务,尽管当下不完成。

  5. 当 coordinator 收到所有 prepare 请求的回复后,就做出 commit 或者 abort 的决定。coordinator 必须将该决定写入日志并落盘后,才能继续推进。决定日志落盘被称为 commit point。

  6. 一旦 coordinator 的决定落盘,commit/abort 决定被发送给所有其它节点,任何请求失败或者超时都必须被永久重试直到成功为止。过了 commit point 就没有回头路,必须执行。有节点崩溃则 coordinator 会等待它恢复后才 commit。

因此 2PC 实际上包括 2 个无法反悔的决定:

  • voter 回复 yes

  • coordinator 决定 commit/abort

Crash and Failures

节点可能会崩溃,通常有两种崩溃的方式:

  • fail-stop:崩溃以后再也无法恢复

  • fail-recover:崩溃一段时间后恢复正常

考虑两种情况:voter 崩溃和 coordinator 崩溃:

voter 崩溃

  • prepare 请求失败或超时,coordinator 可以 abort 事务

  • abort/requests 请求失败或超时,coordinator 就不断重试直到成功执行

coordinator 崩溃

  • 在 voter 回复 prepare 请求之前就崩溃,每个 voter 各自可以 abort 事务(如超时自动 abort)

  • 一旦 voter 回复 prepare 请求 yes 后,voter 就放弃了主动 abort 事务的权力。它必须等待 coordinator 的下一步指令。如果 coordinator 宕机或者网络中断,voter 无能为力。解决这种问题必须等待 coordinator 故障恢复。

小结

2PC 是人们可以想象到的最简单的共识协议,如果系统中有 N 个节点,它可以通过 2N 次通信达成一次共识,效率很高。但它的缺点就是可能因为 coordinator 和 voters 崩溃而出现停滞的现象。

Three Phase Commit

2PC 的问题本质在于,在 propose 阶段结束后,只有 coordinator 知道结果,voters 之间并不知道其它人心里怎么想,如果在 propose 阶段后,增加一个 pre-commit 阶段,让 coordinator 告诉 voters 大家的意思,大家都知道后,在出现节点崩溃的情况后,幸存的 voters 就能够恢复协议的状态。来看下面几种情况:

  • 在任何时候 coordinator 崩溃,一个 voter 可以转化成 recovery node,向其它 voters 了解情况后,推进 3PC。

  • 如果一个 voter 在 commit 后崩溃了,由于其它 voters 都已经完成了 pre-commit 阶段,此时 coordinator/recovery node 就知道可以继续完成 commit 阶段。

  • 如果一个 voter 在 pre-commit 阶段崩溃时,coordinator/recovery node 可以悲观地 abort

3PC 通过增加 N 次通信,解决了 2PC 遇到的问题。但 3PC 真的彻底解决了这个问题吗?事实并非如此,当出现网络分区时,可能出现两组 voters 和 coordinator,两个小组可能得出不同的结论,当分区恢复时,系统的状态就出现了不一致。

Beyond 2PC & 3PC

为了解决网络分区问题,我们只希望某个小组能够继续推进,直觉告诉我们少数人应当服从多数人,这也是后续研究者思考的方向,并提出了以 Paxos、Raft 为代表的一致性协议,来解决 Consensus Problem。

参考