2PC & 3PC
Last updated
Last updated
Two Generals' Problem
Two Generals' Problem 是一个思想实验，模拟的是网络中两个节点如何通过不可靠的连接通信的问题。
问题描述：有两支军队在两个山坡上安营扎寨，准备进攻处在两个山坡之间山谷的敌军。两支军队的将军需要协商一个相同的时间点同时发起进攻，若只有一方发起进攻，就会全军覆没。两位将军只能通过信使来通信，然而信使必须通过山谷才能到达对面军营，信使有可能在半道被敌军俘虏。两位将军只能发送消息、接收消息，是否存在一种协议或策略能使得两位将军协调到一致的进攻时间？
假设一切顺利，信使成功穿越敌军军营：
将军 B 收到将军 A 发送的 "确认收到" 的消息后，两位将军就在进攻时间上达成共识（consensus)。
任何一次通信过程中，信使都有可能被俘虏，将军A 与将军 B 永远也无法达成一致。
Two Generals' 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)。
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 的正确性，我们还需要深入理解其中的细节：
当应用想要启动一个分布式事务时，它需要从 coordinator 处获得一个全局唯一的 transactionID
应用在每个节点上分别启动单节点事务，并将 transactionID 传入其中，单节点所涉及的所有读写操作都应该在一个事务中进行，在这个过程中任意节点出问题，coordinator 或节点本身都可以 abort
当应用已经为 commit 做好准备时，coordinator 发送 prepare 请求到所有节点，并带上 transactionID 信息，其中任何一个请求失败或者超时，coordinator 就发送 abort 请求到所有节点，并带上 transactionID 信息。
当任意一个节点收到 prepare 请求时，它必须保证在未来发生任何事情时都能成功 commit 这个事务，包括节点崩溃、违反约束、断电、磁盘空间不足等等。因此节点实际上需要预留出相关的资源保证事务可以推进。一旦该节点回复 yes 给 coordinator，就意味着他一定可以完成这个事务，尽管当下不完成。
当 coordinator 收到所有 prepare 请求的回复后，就做出 commit 或者 abort 的决定。coordinator 必须将该决定写入日志并落盘后，才能继续推进。决定日志落盘被称为 commit point。
一旦 coordinator 的决定落盘，commit/abort 决定被发送给所有其它节点，任何请求失败或者超时都必须被永久重试直到成功为止。过了 commit point 就没有回头路，必须执行。有节点崩溃则 coordinator 会等待它恢复后才 commit。
因此 2PC 实际上包括 2 个无法反悔的决定：
voter 回复 yes
coordinator 决定 commit/abort
节点可能会崩溃，通常有两种崩溃的方式：
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 崩溃而出现停滞的现象。
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，两个小组可能得出不同的结论，当分区恢复时，系统的状态就出现了不一致。
为了解决网络分区问题，我们只希望某个小组能够继续推进，直觉告诉我们少数人应当服从多数人，这也是后续研究者思考的方向，并提出了以 Paxos、Raft 为代表的一致性协议，来解决 Consensus Problem。
