分散式 transaction 和共识 (Distributed Transactions and Consensus)

共识是分散式计算中重要的基础问题，目标是 让所有节点一致同意某些事情，共识会用在这 2 种情形上面：

• Leader election

  在 single-leader 资料库中，成为 leader 需要所有节点同意，如此就能在节点故障时，避免不好的 failover 发生（形成 split brain 情况）。

• Atomic commit

  若资料库能支援多节点的 transaction，我们会就可能会面临有些节点 commit 成功，有些节点 commit 失败的情形，如果我们要维持 transaction 原子性 (Day 1)，势必要让所有节点同意 transaction 的结果才行，这个共识问题就是 atomic commit 问题。

首先要来介绍 二阶段 commit (two-phase commit)，一个常用来解决 atomic commit 问题的共识演算法。

Atomic Commit and Two-Phase Commit (2PC)

从单一节点到分散式 atomic commit

ACID 的原子性 (Day 1)，能使资料库避免一半成功的结果，这在多物件更新 (Day 2) 情况上尤为重要。

transaction 执行在单一资料库节点上时，当使用者询问资料库是他们想 commit transaction，资料库为了让 transaction 更有耐用性，它会先预写 log 到硬碟上，然後再写入 commit 记录到硬碟上，如果资料库在过程中故障，transaction 就能在节点重启时从 log 中恢复状态。

因此，单一资料库节点的 transaction commit 的关键是依赖在资料写入硬碟的顺序上，若 commit 记录在故障前成功写入到硬碟上，就可视为成功 commit ，在此之前，transaction 都有机会中止。

那麽，多节点怎麽办呢？因为原子性的关系，我们无法只发送 commit 讯息到各节点上就好了（因为有些可能失败），所以要透过某种机制协调 & 强制的让所有节点都 commit 成功。

二阶段 commit (two-phase commit)

二阶段 commit 是一个实现多节点原子 transaction commit 的算法，能确保所有节点都 commit 或 中止 transaction，二阶段 commit 的基础流程如下图 9-9，让 commit 的过程拆分成二阶段，且多了一个新的元件角色：协调者 (coordinator)。

二阶段 commit 跟 Day 6 的二阶段锁不一样喔，别搞混了。

协调者的工作就是在阶段 1 发生 prepare request 给所有的节点（也称为参与者）问它们是否准备好要 commit 了没，依据节点们的回答，阶段 2 会有两个不同任务：

• 当所有的参与者都回 yes ，协调者就会发送 commit request 给所有节点。
• 若有任一节点回 no，协调者就会发送 abort request 给所有节点。

承诺制度 (A system of promises)

因为 Day 8 ~ Day 13 讲过的鬼故事，prepare 或 commit request 都有机会遗失，所以接下来就来细看 二阶段 commit 究竟为什麽可以做到所有节点同意某种结果。

1. 当应用系统开始一个分散式 transaction 时，它会从协调者要求一个唯一的 transaction ID。
2. 每一个参与者节点都使用该 transaction ID 开始一个 transaction，所有读取跟写入都在该单一节点上完成，若在此阶段有任何错误发生，协调者或任一参与者都能中止 (abort)。
3. 当应用系统准备要 commit，协调者发送 prepare request 到每一个参与者中，并标注该 transaction ID，若有任何 request 失败或 timeout，协调者就发送 abort request 到所有参与者中。
4. 当参与者节点接收 prepare request ，它要做好是否能 commit 的确认，包含写入 transaction 资料到硬碟、检查资料是否有冲突或违反限制；当它回覆 yes 给协调者，代表参与者放弃中止 transaction 的权利，但还没实际 commit。
5. 当协调者接收到所有参与者的回覆，协调者能做 commit 或 abort 的决定，协调者必须把它的决定写到 transaction log 里（当故障时可知道自己的决定是什麽），这称为 commit point。
6. 一旦协调者的决定写入到硬碟上了，相对应的 request 就会发生给所有参与者，如果 request 失败或 timeout，协调者会 一直重试 直到成功，这也意味者没有回头路了；如果参与者在此时故障，该 transaction 也会在节点恢复时 commit。

因此，这个协定包含 2 个无法回头的关键点：

• 当参与者投给 yes，它就是保证它之後一定能 commit （虽然协调者可能选择 abort）。
• 一旦协调者做决定了，这决定不可撤回。

这些承诺确保了 二阶段 commit 的原子性。

协调者故障

如果协调者在发送 prepare request 前故障，参与者可以安全的中止 transaction，但是一旦参与者接收到了 prepare request 共投了 yes，它就不能单方面中止，它必须等待协调者给它 commit 或 abort 的讯息，如果协调者故障或网路延迟，该参与者什麽也不能做，只能等待，这个状态的参与者称为 in doubt 或 uncertain。

这个情况如下图 9-10，协调者决定 commit 并成功发送 commit request 给 Database 2， 但在发送给 Database 1 前故障了，所以 Database 1 不知道发生什麽状况只能等待。

原则上，参与者节点可以跟其他参与者节点互相沟通问结果，但那不在 二阶段 commit 协定的范畴。

这唯一的解决方法就是协调者节点要恢复，所以协调者才会写它的决定在 transaction log 中，以防从故障中恢复并检测所有在 in-dobut 的参与者节点，当协调者节点恢复时，协调者 log 中所有没有 commit 记录的 transaction 将会中止，所以，2PC 的 commit point 可被归在常规的协调者单一节点上 atomic commit 。