# 2PC & 3PC

Two Generals' Problem

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

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

### 路径分析

#### 最好的情况：

假设一切顺利，信使成功穿越敌军军营：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_unTiqAnYqcd4MQk5Y%2F-L_v03gGvN6zNpN2rD5T%2FScreen%20Shot%202019-03-14%20at%203.04.24%20PM.jpg?alt=media\&token=8808af2d-b2b5-4103-a6a4-53286f6a850a)

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

#### 最坏的情况：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_unTiqAnYqcd4MQk5Y%2F-L_v1ZvRXZ09oByGOJgN%2FScreen%20Shot%202019-03-14%20at%203.10.59%20PM.jpg?alt=media\&token=45d28a3d-da4e-4eed-8f48-29fe90d67139)

任何一次通信过程中，信使都有可能被俘虏，将军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 阶段。若所有队员同意，则一个一个地给队员打电话，告知确认其它队员都能参赛；若有至少一名队员不同意，则一个一个地给队员打电话，告知比赛因有队员缺席而取消。整个过程如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_unTiqAnYqcd4MQk5Y%2F-L_v79_M3pE3fi35ygOQ%2FScreen%20Shot%202019-03-14%20at%203.35.25%20PM.jpg?alt=media\&token=0630366c-7079-474b-87ea-1eb198a0b2cc)

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

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_unTiqAnYqcd4MQk5Y%2F-L_v7Fb_UseC_waeSDzn%2FScreen%20Shot%202019-03-14%20at%203.35.48%20PM.jpg?alt=media\&token=637bf59e-ff79-47a8-8fab-05a4826a004c)

若有任意 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

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_unTiqAnYqcd4MQk5Y%2F-L_vHdV9h2AvvYNY2hOm%2FScreen%20Shot%202019-03-14%20at%204.21.12%20PM.jpg?alt=media\&token=d982f6ad-0c1f-4260-8379-f420034e903f)

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

### Beyond 2PC & 3PC

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

## 参考

* [The Paper Trail - Consensus Protocols: Two-Phase Commit](https://www.the-paper-trail.org/post/2008-11-27-consensus-protocols-two-phase-commit/)
* [The Paper Trail - Consensus Protocols: Three-Phase Commit](https://www.the-paper-trail.org/post/2008-11-29-consensus-protocols-three-phase-commit/)
* [Wikipedia: Two-Phase Commit Protocol](https://en.wikipedia.org/wiki/Two-phase_commit_protocol)
* [Wikipedia: Three-Phase Commit Protocol](https://en.wikipedia.org/wiki/Three-phase_commit_protocol)
* [Wikipedia: Two Generals' Problem](https://en.wikipedia.org/wiki/Two_Generals'_Problem)