经典 TWO-PHASE COMMIT PROTOCOL

本文详细描述经典的 TWO-PHASE COMMIT PROTOCOL (后面简称 2PC 协议).

注意: 本文只描述了经典的 2PC, 没有描述 2PC 的各种变种和优化.

为了更好的理解, 先描述一下无故障时协议怎么工作;

然后再对协议运行过程中可能碰到的各种故障进行讨论, 说明在这些故障的场景下, 怎么处理这些故障来保证协议的正确性.

一, 经典 2PC 协议无故障时的工作流程

一个 commit protocol 需要满足以下特性:

1. 始终保证事务的原子性
2. 能够快速 “forget” 提交的处理结果 (所谓的 forget 就是把内存中这个事务相关的内容全部清除掉)
3. 尽可能的减小写本地日志和进程间消息通讯的代价
4. 优化正常流程的性能 (也就是没有出现故障时的性能)
5. 最大化 “单方面 abort 的能力” (所谓单方面 abort, 也就是某个进程如果知道这个分布式事务肯定会 abort, 那么它无需等待其他进程的通知, 直接进入 abort 流程)

经典 2PC 协议模型中包含两种角色的进程:

1. coordinator (协调者): 只有一个; 接收用户开始事务的请求, 然后会和 多个 subordinates 进行通讯处理事务
2. subordinates (参与者): 有多个; 互相之间不会进行通讯, 只会和 coordinator 通讯处理事务

另外, 特别说明一下, 2PC 协议中, 写日志分两种:

1. force-write 日志: 要保证日志被刷到磁盘上, 而不仅仅是写到操作系统缓存中, 保证系统崩溃恢复后能从磁盘上读到这种日志
2. 一般 write 日志: 写到操作系统缓存中, 系统崩溃后不一定能从磁盘上读到这种日志

下面是正常情况 (无故障场景) 下的 2PC 协议:

第一阶段(提交请求阶段):

1. coordinator 接收到用户的事务开始请求
2. coordinator 并行的向所有 subordinates 发送 PREPARE 消息, 询问这些 subordinates 是否愿意 “commit” 这个事务;
3. 然后, coordinator 进入等待状态, 等待所有 subordinates 返回的消息
4. 每个愿意 commit 这个事务的 subordinate, 先 force-write 一条 prepare 日志, 这个 subordinate 进入 prepared 状态
5. 然后 这个 subordinate 发送 YES VOTE 消息给 coordinator; 等待 coordinator 第二阶段的决定
6. 每个想要 abort 这个事务的 subordinate, 先 force-write 一条 abort 日志
7. 然后这个 subordinate 发送 NO VOTE 消息给 coordinator
8. 之后, 无需等待 coordinator 第二阶段的决定, 这个 subordinate 释放相关资源后, forget 掉这个事务

第二阶段(提交执行阶段):

1. 如果 coordinator 从所有 subordinates 获得的响应消息都是 YES VOTE, coordinator force-write 一条 commit 日志, 进入 committing 状态
2. 然后 coordinator 并行发送 COMMIT 消息给所有的 subordinates; 并开始等待 所有 subordinates 的确认消息
3. 如果 coordinator 从某个 subordinate 获得的响应消息是 NO VOTE, coordinator force-write 一条 abort 日志, 进入 aborting 状态
4. 然后 coordinator 并行发送 ABORT 消息给那些 返回 了 YES VOTE 的 subordinates; 以及那些还没有响应 PREPARE 消息的 subordinates (既没有返回 YES, 也没有返回 NO)
5. 每个 subordinate, 如果收到了 COMMIT 消息, force-write 一条 commit 日志, 进入 committing 状态, 然后返回一个 ACK 消息给 coordinator; 最后 commit, 并 forget 这个事务
6. 每个 subordinate, 如果收到了 ABORT 消息, force-write 一条 abort 日志, 进入 abort 状态; 然后返回一个 ACK 消息给 coordinator; 最后 abort, 并 forget 这个事务
7. coordinator 收到它期望的所有 ACK 消息后 (无需等待之前返回了 NO 的 subordinates 返回 ACK), 使用一般 write (不需要 force-write) 写一条 end 日志, 完成, 并 forget 这个事务

以上描述的协议有一个原则: 任何时候 subordinate 发送一个响应消息给 coordinator 之前, 必须先 force-write 一条日志记录. 一旦遵守了这个原则 subordinate 就不需要去 coordinator 那里获取这些日志中记录的信息.

这个原则保证了分布式事务的原子性. 换句话说, 如果不遵守这个原则, 事务的原子性不能被保证, 可能会出现部分 subordinates 提交了事务, 而部分 subordinates abort 了事务的不一致情况 (后面会详细说为什么).

总结:

• 整个过程中, 每个 subordinate 需要 force-write 两条日志; 发送两条消息给 coordinator.
• 整个过程中, coordinator 需要 force-write 一条日志; 一般 write (非 force-write ) 一条日志
• 整个过程中, coordinator 发送两条消息给 subordinates

最后给出一个示意图:

二, 2PC 协议可能遇到的故障

所谓的故障有两种:

• 机器故障
• 通讯故障

但在 2PC 协议的模型中, 假定这两种故障都是最终会恢复的:

• 机器故障以后, 可以重启起来. 而且之前 force-write 的日志不会被破会, 可以把日志中的信息再读到内存中来
• 某两个机器间的通讯故障一段时间后, 可以恢复通讯

2PC 协议中的故障统一由 recovery process 来处理. 所以每台机器上会起一个 recovery process.

recovery process 负责以下事情:

• 每台机器上的 recovery process 会响应处理其他机器上的 recovery process 发送过来的消息
• 每台机器故障后重启起来后, 这台机器上的 recovery process 会处理之前故障时正在执行的事务

机器故障后重启起来时, recovery process 先从本地日志中读取之前故障时正在执行的事务的相关信息到内存中.

这些在内存中的信息的用处:

• 当 coordinator 接收到其他机器上的 subordinates 发送过来的 query 请求 (这些 query 是做什么用的? 后面会讲) 时, coordinator 会根据内存中的信息做响应
• 当 coordinator 主动发送通知 (这些通知做什么用? 后面会讲) 给其他机器上的 subordinates 时, coordinator 会直接根据内存中的信息发送通知

把这些信息读入到内存中, 可以提高整个协议的性能 (不需要到日志中获取这些信息).

下面分别介绍机器故障和通讯故障的恢复动作.

三, 2PC 协议有机器故障时的场景

下面逐一介绍当遇到机器故障时, 2PC 协议中的 recovery process 需要做的恢复动作.

1. subordinate 的 recovery process 发现没有本地日志和当前执行的事务相关

恢复动作: 直接回滚这个事务. 然后写一条 abort 日志, 最后 forget 这个事务

解释:

• subordinate 的本地没有日志, 就说明没有发送过任何消息给 coordinator. 直接把这个事务 abort 不会造成任何不一致
• 如果之后收到 coordinator 的 PREPARE 消息, 直接返回 NO VOTE (对于还没有到 prepared 状态的 subordinate. 只要是被 forget, 内存不存在的事务, 都认为是被 abort 了的事务)

2. subordinate 的 recovery process 发现当前的状态是 prepared

恢复动作: recovery process 周期性的给 coordinator 发送 query, 询问下一步需要做 commit 还是 abort.

解释:

• 如果是 prepared 状态, 说明这台机器是一个 subordinate, 之前它已经发送了 YES VOTE 消息给 coordinator
  • 所以现在要恢复故障, 必须从 coordinator 获取事务的最终的决定

3. coordinator 的 recovery process 发现没有本地日志和当前执行的事务相关

恢复动作: 直接回滚这个事务. 然后写一条 abort 日志, 最后 forget 这个事务

解释:

• coordinator 的本地没有日志, 就说明没有进入第二阶段. 直接把这个事务 abort 不会造成任何不一致
• 如果之后收到 subordinate 的 query 消息, 询问事务的最终决定, 直接返回 ABORT (coordinator 对已经被 forget, 内存不存在的事务, 都认为是被 abort 了的事务)

4. coordinator 的 recovery process 发现当前的状态是 committing 或者 aborting

恢复动作: recovery process 周期性的主动发送 COMMIT 或 ABORT 通知给所有的 subordinates.

解释:

• 发现 coordinator 已经在 committing 或者 aborting 状态, 说明已经开始第二阶段, 最终决定已经做出, 不得再变更. 只能通知所有 subordinates, 并等待所有的 ACK 消息来结束事务

---

最后, 回答一下之前提出的问题:

Q: 为什么任何时候 subordinate 发送一个响应消息给 coordinator 之前, 必须先 force-write 一条日志记录?

A: 从上面的机器故障恢复过程可以看出, 所有的恢复必须依靠 force-write 的日志. 如果先发消息, 再写日志, 就可能出现消息发出之后, 机器故障, 日志没有写成功的场景, 最后造成没有办法从机器故障中恢复, 破坏事务的原子性.

四, 2PC 协议有通讯故障时的场景

下面逐一介绍当遇到通讯故障时, 2PC 协议中的 recovery process 需要做的恢复动作:

1. coordinator 已经发送了 PREPARE 消息, 等待 subordinates 的响应时, 发现和某个 subordinate 的通讯故障

恢复动作: coordinator 直接判断这个事务可以被 abort, 开始 abort 流程 (直接回滚这个事务. 然后写一条 abort 日志, 最后 forget 这个事务)

解释:

• 没有进入第二阶段. 直接把这个事务 abort 不会造成任何不一致
• 如果之后收到 subordinate 的 query 消息, 询问事务的最终决定, 直接返回 ABORT (coordinator 对已经被 forget, 内存不存在的事务, 都认为是被 abort 了的事务)

2. coordinator 已经发送了 COMMIT 或 ABORT 消息给所有的 subordinates, 等待 ACK 的响应时, 发现和某个 subordinate 的通讯故障

恢复动作: coordinator 把相关工作转交给 recovery process 来处理 (反复获取 subordinates 的 ACK)

解释:

• 已经开始第二阶段, 最终决定已经做出, 不得再变更. 只能等待 ACK 消息来结束事务;

3. subordinate 在 prepared 状态之前和 coordinator 通讯故障

恢复动作: 直接回滚这个事务. 然后写一条 abort 日志, 最后 forget 这个事务

解释:

• 没有发送过任何消息给 coordinator. 直接把这个事务 abort 不会造成任何不一致
• 如果之后收到 coordinator 的 PREPARE 消息, 直接返回 NO VOTE (对于还没有到 prepared 状态的 subordinate. 只要是被 forget, 内存不存在的事务, 都认为是被 abort 了的事务)

4. subordinate 在 prepared 状态之后和 coordinator 通讯故障

恢复动作: subordinate 把相关工作转交给 recovery process 来处理 (反复询问 coordinator 事务的最终结果, 然后走相应的流程)

解释:

• subordinate 已经在 prepared 状态, 只能等待 coordinator 关于这个事务的最终决定来结束事务

最后要强调一下:

• 对于还没有到 prepared 状态的 subordinate. 只要是被 forget, 内存不存在的事务, 都认为是被 abort 了的事务
• coordinator 对已经被 forget, 内存不存在的事务, 都认为是被 abort 了的事务

五, 参考

• Transaction Management in the R* Distributed Database Management System