分布式-一致性协议.md

分布式：一致性协议

2PC 与 3PC

在分布式系统中，每一个机器节点虽然能够明确地知道自己在进行事务操作过程中的结果是成功或失败，但却无法直接获取到其他分布式节点的操作结果。

因此，当一个事务操作需要跨越多个分布式节点的时候，为了保持事务处理的 ACID 特性，就需要引入一个称为协调者（Coodinator）的组件来统一调度所有分布式节点的执行逻辑，这些被调度的分布式节点被称为参与者（Participant）。

协调者负责调度参与者的行为，并最终决定这些参与者是否要把事务真正进行提交。

2PC

2PC 是 Two-Phase Commit 的缩写，即二阶段提交，是计算机网络尤其是在数据库领域内，为了使基于分布式架构下的所有节点在进行事务处理过程中能够保持原子性和一致性而设计的一种算法。

绝大部分的关系型数据库都是采用二阶段提交协议来完成分布式事务处理的，利用该协议能够非常方便地完成所有分布式事务参与者的协调，统一决定事务的提交或回滚，从而能够有效地保证分布式数据的一致性。

阶段一：提交事务请求

1. 事务询问：协调者向所有参与者发送事务内容，询问是否可以执行事务提交操作，并开始等待各参与者的响应。
2. 执行事务：各参与者节点执行事务操作，并将 Undo 和 Redo 信息记入事务日志中。
3. 各参与者向协调者反馈事务询问的响应：如果参与者成功执行了事务操作，那么就反馈给协调者 Yes 响应，表示事务可以执行，否则返回 No 响应。

阶段二：执行事务提交

协调者会根据各参与者的反馈情况来决定最终是否可以进行事务提交操作，包含以下两种可能：

• 执行事务提交

  1. 发送提交请求：协调者向所有参与者节点发出 Commit 请求
  2. 事务提交：参与者接收到 Commit 请求后，会正式执行事务提交操作，并在完成提交之后释放在整个事务执行期间占用的事务资源
  3. 反馈事务提交结果：参与者在完成事务提交之后，向协调者发送 Ack 消息
  4. 完成事务：协调者接收到所有参与者反馈的 Ack 消息后，完成事务

• 中断事务

  1. 发送回滚请求：协调者向所有参与者节点发出 Rollback 请求
  2. 事务回滚：参与者接收到 Rollback 请求后，会利用其在阶段一中记录的 Undo 信息来执行事务回滚操作，并在完成回滚之后释放在整个事务执行期间占用的资源
  3. 反馈事务回滚结果：参与者在完成事务回滚之后，向协调者发送 Ack 消息
  4. 中断事务：协调者接收到所有参与者反馈的 Ack 消息后，完成事务中断

优缺点

二阶段提交协议的优点：原理简单，实现方便

二阶段提交协议的缺点：

• 同步阻塞：在二阶段提交的执行过程中，所有参与该事务操作的逻辑都处于阻塞状态，各个参与者在等待其他参与者响应的过程中，将无法进行其他任何操作
• 单点问题：协调者的角色在二阶段提交协议中起到了非常重要的作用，一旦协调者出现问题，那么整个流程将无法运转，更为严重的是，如果在阶段二出现问题的话，那么其他参与者将会一直处于锁定事务资源的状态中，而无法继续完成事务操作
• 数据不一致：执行事务提交的时候，当协调者向所有的参与者发送 Commit 请求之后，发生了局部网络异常或者是协调者在尚未发送完 Commit 之前自身发生了崩溃，导致只有部分参与者收到了 Commit 请求，于是整个分布式系统出现了数据不一致性现象
• 太过保守：如果在协调者指示参与者进行事务提交询问的过程中，参与者出现故障而导致协调者始终无法获取到所有参与者的响应信息的话，这时协调者只能依靠自身的超时机制来判断是否需要中断事务，这样的策略显得比较保守

3PC

3PC 是 Three-Phase Commit 的缩写，即三阶段提交，是 2PC 的改进版，其将二阶段提交协议的"提交事务请求"过程一分为二，形成了 CanCommit，PreCommit 和 DoCommit 三个阶段组成的事务处理协议

阶段一：CanCommit

1. 事务询问：协调者向所有的参与者发送一个包含事务内容的 CanCommit 请求，询问是否可以执行事务提交操作，并开始等待各参与者的响应
2. 各参与者向协调者反馈事务询问的响应：参与者在接收到来自协调者的 CanCommit 请求后，正常情况下，如果其自身认为可以顺利执行事务，那么会反馈 Yes 响应，并进入预备状态，否则反馈 No 响应

阶段二：PreCommit

阶段二中，协调者会根据各参与者的反馈情况来决定是否可以进行事务的 PreCommit 操作，包含两种可能：

• 执行事务预提交

  1. 发送预提交请求：协调者向所有参与者节点发出 PreCommit 请求，并进入 Prepared 阶段
  2. 事务预提交：参与者接收到 PreCommit 请求后，会执行事务操作，并将 Undo 和 Redo 信息记录到事务日志中
  3. 各参与者向协调者反馈事务执行的响应：如果参与者成功执行了事务操作，那么就会反馈给协调者 Ack 响应，同时等待最终的指令：提交（Commit）或终止（Abort）

• 中断事务

  1. 发送中断请求：协调者向所有参与者节点发出 abort 请求
  2. 中断事务：无论是收到来自协调者的 abort 请求，或者是在等待协调者请求过程中出现超时，参与者都会中断事务

阶段三：DoCommit

该阶段将进行真正的事务提交，会存在以下两种可能的情况

• 执行提交

  1. 发送提交请求：协调者处于正常工作状态，并且接收到了来自所有参与者的 Ack 响应，那么它将从"预提交"状态转换到"提交"状态，并向所有的参与者发送 DoCommit 请求
  2. 事务提交：参与者接收到 DoCommit 请求后，会正式执行事务提交操作，并在完成提交之后释放在整个事务执行期间占用的事务资源
  3. 反馈事务提交结果：参与者在完成事务提交之后，向协调者发送 Ack 消息
  4. 完成事务：协调者接收到所有参与者反馈的 Ack 消息后，完成事务

• 中断事务

  1. 发送中断请求：协调者向所有的参与者发送 abort 请求
  2. 事务回滚：参与者接收到 abort 请求后，会利用其在阶段二中记录的 Undo 信息来执行事务回滚操作，并在完成回滚之后释放占用的资源
  3. 反馈事务回滚结果：参与者在完成事务回滚之后，向协调者发送 Ack 消息
  4. 中断事务：协调者接收到所有参与者反馈的 Ack 消息后，中断事务

优缺点

三阶段提交协议的优点：降低了参与者的阻塞范围，并且能够在出现单点故障后继续达成一致

缺点：在参与者接收到 PreCommit 消息后，如果网络出现分区，此时协调者所在的节点和参与者无法进行正常的网络通信，在这种情况下，该参与者依然会进行事务的提交，这必然会出现数据的不一致性

Paxos 算法

Paxos 是什么

Paxos 算法是基于消息传递且具有高度容错性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。

问题产生背景

在常见的分布式系统中，总会发生诸如机器宕机或网络异常（包括消息的延迟，丢失，重复，乱序，还有网络分区）等情况。

Paxos 算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中，快速且正确的在集群内部对某个数据值达成一致，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性。

相关概念

在 Paxos 算法中，有三种角色：

• Proposer
• Acceptor
• Learners

在具体的实现中，一个进程可能同时充当多种角色，比如一个进程可能既是 Proposer 又是 Acceptor 又是 Learner。

其中，还有一个重要的概念叫做提案（Proposal），最终要达成一致的 value 就在提案里。

Proposer 可以提出提案，Acceptor 可以接收提案，如果某个提案被选定（chosen），那么该提案里的 value 就被选定了。

在以下情况下会认为 value 被选定：

• Proposer：只要Proposer发的提案被Acceptor接受（刚开始先认为只需要一个Acceptor接受即可，在推导过程中会发现需要半数以上的Acceptor同意才行），Proposer就认为该提案里的value被选定了。
• Acceptor：只要Acceptor接受了某个提案，Acceptor就任务该提案里的value被选定了。
• Learner：Acceptor告诉Learner哪个value被选定，Learner就认为那个value被选定。

问题描述

假设有一组可以提出（propose）value（value 在提案 Proposal 里）的进程集合。一个一致性算法需要保证提出的这么多 value 中，只有一个 value 被选定（chosen）。如果没有 value 被提出，就不应该有 value 被选定。如果一个 value 被选定，那么所有进程都应该学习（learn）到这个被选定的 value。

我们不去精确地定义其活性（liveness）要求。我们的目标是保证最终有一个提出的 value 被选定。当一个 value 被选定后，进程最终也能学习到这个 value。

Paxos 的目标：保证最终有一个 value 会被选定，当 value 被选定后，进程最终也能获取到被选定的 value。

假设不同角色之间可以通过发送消息来进行通信，那么：

• 每个角色以任意的速度执行，可能因出错而停止，也可能会重启。一个 value 被选定后，所有的角色可能失败然后重启，除非那些失败后重启的角色能记录某些信息，否则等他们重启后无法确定被选定的值。
• 消息在传递过程中可能出现任意时长的延迟，可能会重复，也可能丢失。但是消息不会被损坏，即消息内容不会被篡改。

推导过程

只有一个 Acceptor

假设只有一个 Acceptor（可以有多个 Proposer），只要 Acceptor 接收它收到的第一个提案，则该提案被选定，该提案里的 value 就是被选定的 value，这样就保证只有一个 value 会被选定。

但是，如果这个唯一的 Acceptor 宕机了，那么整个系统就无法工作了，因此必须要有多个 Acceptor。

多个 Acceptor

如果我们希望即使只有一个 Proposer 提出了一个 value，该 value 也最终被选定。那么，得到下面的约束：

P1：一个 Acceptor 必须接收它收到的第一个提案。

但是，这又会引出另一个问题：如果每个 Proposer 分别提出不同的 value，发给不同的 Acceptor。根据 P1，Acceptor 分别接收自己收到的 value，就导致不同的 value 被选定，出现了不一致。

因此，我们需要加一个规定：

规定：一个提案被选定需要被半数以上的 Acceptor 接受。

最开始讲的[提案=value]已经不能满足需求了，于是重新设计提案，给每个提案加上一个提案编号，表示提案被提出的顺序，令[提案=提案编号+value]。

虽然允许多个提案被选定，但必须保证所有被选定的提案都具有相同的 value 值，否则又会出现不一致。于是有了下面的约束：

P2：如果某个 value 为 v 的提案被选定了，那么每个编号更高的被选定提案的 value 必须也是 v。

一个提案只有被 Acceptor 接受才可能被选定，因此我们可以把 P2 约束改写成对 Acceptor 接受的提案的约束 P2a。

P2a：如果某个 value 为 v 的提案被选定了，那么每个编号更高的被 Acceptor 接受的提案的 value 必须也是 v。

考虑如下的情况：假设总的有 5 个 Acceptor。Proposer2 提出[M1,V1]的提案，Acceptor2～5（半数以上）均接受了该提案，于是对于 Acceptor2～5 和 Proposer2 来讲，它们都认为 V1 被选定。

Acceptor1 刚刚从宕机状态恢复过来（之前 Acceptor1 没有收到过任何提案），此时 Proposer1 向 Acceptor1 发送了[M2,V2]的提案（V2≠V1 且 M2>M1），对于 Acceptor1 来讲，这是它收到的第一个提案。根据P1（一个 Acceptor 必须接受它收到的第一个提案。）,Acceptor1 必须接受该提案。

同时 Acceptor1 认为 V2 被选定。这就出现了两个问题：

1. Acceptor1 认为 V2 被选定，Acceptor2～5 和 Proposer2 认为 V1 被选定。出现了不一致。
2. V1 被选定了，但是编号更高的被 Acceptor1 接受的提案[M2,V2]的 value 为 V2，且 V2≠V1。这就跟 P2a（如果某个 value 为 v 的提案被选定了，那么每个编号更高的被 Acceptor 接受的提案的 value 必须也是 v）矛盾了。

所以要对 P2a 约束进行强化，得到 P2b：

P2b：如果某个 value 为 v 的提案被选定了，那么之后任何 Proposer 提出的编号更高的提案的 value 必须也是 v。

那么，如何确保在某个 value 为 v 的提案被选定后，Proposer 提出的编号更高的提案的 value 都是 v 呢？

只要满足 P2c 即可：

P2c：对于任意的 N 和 V，如果提案[N,V]被提出，那么存在一个半数以上的 Acceptor 组成的集合 S，满足以下两个条件中的任意一个： S 中每个 Acceptor 都没有接受过编号小于 N 的提案 S 中 Acceptor 接受过的最大编号的提案的 value 为 V

Proposer 生成提案

为了满足 P2b，这里有个比较重要的思想：Proposer 生成提案之前，应该先去"学习"已经被选定或者可能被选定的 value，然后以该 value 作为自己提出的提案的 value。

如果没有 value 被选定，Proposer 才可以自己决定 value 的值，这样才能达成一致。这个学习的阶段是通过一个"Prepare 请求"实现的。

于是我们得到了如下的提案生成算法：

1. Proposer 选择一个新的提案编号 N，然后向某个 Acceptor 集合（半数以上）发送请求，要求该集合中的每个 Acceptor 做出如下响应（response）：

   • 向 Proposer 承诺保证不再接受任何编号小于 N 的提案
   • 如果 Acceptor 已经接受过提案，那么就向 Proposer 响应已经接受过的编号小于 N 的最大编号的提案。我们将该请求称为编号为 N 的 Prepare 请求。

2. 如果 Proposer 收到了半数以上的 Acceptor 的响应，那么它就可以生成编号为 N，Value 为 V 的提案[N,V]。这里的 V 是所有的响应中编号最大的提案的 Value。如果所有的响应中都没有提案，那么此时 V 就可以由 Proposer 自己选择。生成提案后，Proposer 将该提案发送给半数以上的 Acceptor 集合，并期望这些 Acceptor 能接受该提案。我们称该请求为 Accept 请求。（注意：此时接受 Accept 请求的 Acceptor 集合不一定是之前响应 Prepare 请求的 Acceptor 集合）

Acceptor 接受提案

Acceptor 可以忽略任何请求（包括 Prepare 请求和 Accept 请求）而不用担心破坏算法的安全性。

我们对 Acceptor 接受提案给出如下约束：

P1a：一个 Acceptor 只要尚未响应过任何编号大于 N 的 Prepare 请求，那么它就可以接受这个编号为 N 的提案。

如果 Acceptor 收到一个编号为 N 的 Prepare 请求，在此之前它已经响应过编号大于 N 的 Prepare 请求。根据 P1a，该 Acceptor 不可能接受编号为 N 的提案。因此，该 Acceptor 可以忽略编号为 N 的 Prepare 请求。当然，也可以回复一个 error，让 Proposer 尽早知道自己的提案不会被接受。

因此，一个 Acceptor 只需记住：

1. 已接受的编号最大的提案
2. 已响应的请求的最大编号

Paxos 算法描述

Paxos 算法分为两个阶段，具体如下：

• 阶段一：
  • Proposer 选择一个提案编号 N，然后向半数以上的 Acceptor 发送编号为 N 的 Prepare 请求。
  • 如果一个 Acceptor 收到一个编号为 N 的 Prepare 请求，且 N 大于该 Acceptor 已经响应过的所有 Prepare 请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给 Proposer，同时该 Acceptor 承诺不再接受任何编号小于 N 的提案。
• 阶段二：
  • 如果 Proposer 收到半数以上 Acceptor 对其发出的编号为 N 的 Prepare 请求的响应，那么它就会发送一个针对[N,V]提案的 Accept 请求给半数以上的 Acceptor。注意：V 就是收到的响应中编号最大的提案的 value，如果响应中不包含任何提案，那么 V 就由 Proposer 自己决定。
  • 如果 Acceptor 收到一个针对编号为 N 的提案的 Accept 请求，只要该 Acceptor 没有对编号大于 N 的 Prepare 请求做出过响应，它就接受该提案。

Learner 学习被选定的 value

Learner 学习被选定的 value 有如下三种方案：

1. Acceptor 接受一个提案，就将该提案发送给所有 Learner。
   • 优点：Learner 能快速获取被选定的 value
   • 缺点：通信的次数为 M*N
2. Acceptor 接受一个提案，就将该提案发送给主 Learner，主 Learner 再通知其他 Learner
   • 优点：通信次数减少（M+N-1）
   • 缺点：单点问题（主 Learner 可能出现故障）
3. Acceptor 接受一个提案，就将该提案发送给一个 Learner 集合，Learner 集合再通知其他 Learner
   • 优点：集合中 Learner 个数越多，可靠性越好
   • 缺点：网络通信复杂度越高

如何保证Paxos算法的活性

假设有两个 Proposer 依次提出编号递增的提案，最终会陷入死循环，没有 value 被选定（无法保证活性）：

• Proposer P1 发出编号为 M1 的 Prepare 请求，收到过半响应，完成了阶段一的流程。
• 同时，Proposer P2 发出编号为 M2（M2>M1）的 Prepare 请求，也收到过半响应。也完成了阶段一的流程。于是 Acceptor 承诺不再接受编号小于 M2 的提案。
• P1 进入第二阶段的时候，发出 Accept 请求被 Acceptor 忽略，于是 P1 再次进入阶段一并发出编号为 M3（M3>M2）的 Prepare 请求。
• 这又导致 P2 在阶段二的 Accept 请求被忽略。P2 再次进入阶段一，发出编号为 M4（M4>M3）的 Prepare 请求
• 陷入死循环，都无法完成阶段二，没有 value 被选定

所以只有通过选取主 Proposer，就可以保证 Paxos 算法的活性。