# 2PC & 3PC

Two Generals' Problem

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

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

### 路径分析

#### 最好的情况：

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

![](/files/-L_v03gGvN6zNpN2rD5T)

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

#### 最坏的情况：

![](/files/-L_v1ZvRXZ09oByGOJgN)

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

![](/files/-L_v79_M3pE3fi35ygOQ)

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

![](/files/-L_v7Fb_UseC_waeSDzn)

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

![](/files/-L_vHdV9h2AvvYNY2hOm)

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%27_Problem)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhenghe.gitbook.io/open-courses/mit-6.824/2pc-and-3pc.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.