一致性协议
2PC与3PC
在分布式系统中，每一个机器节点虽然都能够明确地知道自己在进行事务操作过程中的结果是成功或失败，但却无法直接获取到其他分布式节点的操作结果。因此，当一个事务操作需要跨越多个分布式节点的时候，为了保持事务处理的ACID特性，就需要引入一个称为“协调者（Coordinator）”的组件来统一调度所有分布式节点的执行逻辑，这些被调度的分布式节点则被称为“参与者”（Participant）。协调者负责调度参与者的行为，并最终决定这些参与者是否要把事务真正进行提交。基于这个思想，衍生出了二阶段提交和三阶段提交两种协议，在本节中，我们将重点对这两种分布式事务中涉及的一致性协议进行讲解。
2PC
2PC，是Two-Phase Commit的缩写，即二阶段提交，是计算机网络尤其是在数据库领域内，为了使基于分布式系统架构下的所有节点在进行事务处理过程中能够保持原子性和一致性而设计的一种算法。
协议说明
顾名思义，二阶段提交协议是将事务的提交过程分成了两个阶段来进行处理，其执行流程如下。
阶段一：提交事务请求
- 事务询问。
协调者向所有的参与者发送事务内容，询问是否可以执行事务提交操作，并开始等待各参与者的响应。 - 执行事务。
各参与者节点执行事务操作，并将Undo和Redo信息记入事务日志中。 - 各参与者向协调者反馈事务询问的响应。
如果参与者成功执行了事务操作，那么就反馈给协调者 Yes 响应，表示事务可以执行；如果参与者没有成功执行事务，那么就反馈给协调者No响应，表示事务不可以执行。
由于上面讲述的内容在形式上近似是协调者组织各参与者对一次事务操作的投票表态过程，因此二阶段提交协议的阶段一也被称为“投票阶段”，即各参与者投票表明是否要继续执行接下去的事务提交操作。
阶段二：执行事务提交
在阶段二中，协调者会根据各参与者的反馈情况来决定最终是否可以进行事务提交操作，正常情况下，包含以下两种可能。
执行事务提交
假如协调者从所有的参与者获得的反馈都是Yes响应，那么就会执行事务提交。
- 发送提交请求。
协调者向所有参与者节点发出Commit请求。 - 事务提交。
参与者接收到 Commit 请求后，会正式执行事务提交操作，并在完成提交之后释放在整个事务执行期间占用的事务资源。 - 反馈事务提交结果。
参与者在完成事务提交之后，向协调者发送Ack消息。 - 完成事务。
协调者接收到所有参与者反馈的Ack消息后，完成事务。
中断事务
假如任何一个参与者向协调者反馈了No响应，或者在等待超时之后，协调者尚无法接收到所有参与者的反馈响应，那么就会中断事务。
- 发送回滚请求。
协调者向所有参与者节点发出Rollback请求。 - 事务回滚。
参与者接收到 Rollback 请求后，会利用其在阶段一中记录的 Undo 信息来执行事务回滚操作，并在完成回滚之后释放在整个事务执行期间占用的资源。 - 反馈事务回滚结果。
参与者在完成事务回滚之后，向协调者发送Ack消息。 - 中断事务。
协调者接收到所有参与者反馈的Ack消息后，完成事务中断。
以上就是二阶段提交过程中，前后两个阶段分别进行的处理逻辑。简单地讲，二阶段提交将一个事务的处理过程分为了投票和执行两个阶段，其核心是对每个事务都采用先尝试后提交的处理方式，因此也可以将二阶段提交看作一个强一致性的算法，图2-1和图2-2分别展示了二阶段提交过程中“事务提交”和“事务中断”两种场景下的交互流程。
图2-1.二阶段提交“事务提交”示意图
图2-2.二阶段提交“事务中断”示意图
优缺点
二阶段提交协议的优点：原理简单，实现方便。
二阶段提交协议的缺点：同步阻塞、单点问题、脑裂、太过保守。
- 同步阻塞
二阶段提交协议存在的最明显也是最大的一个问题就是同步阻塞，这会极大地限制分布式系统的性能。在二阶段提交的执行过程中，所有参与该事务操作的逻辑都处于阻塞状态，也就是说，各个参与者在等待其他参与者响应的过程中，将无法进行其他任何操作。 - 单点问题
在上面的讲解过程中，相信读者可以看出，协调者的角色在整个二阶段提交协议中起到了非常重要的作用。一旦协调者出现问题，那么整个二阶段提交流程将无法运转，更为严重的是，如果协调者是在阶段二中出现问题的话，那么其他参与者将会一直处于锁定事务资源的状态中，而无法继续完成事务操作。 - 数据不一致
在二阶段提交协议的阶段二，即执行事务提交的时候，当协调者向所有的参与者发送Commit请求之后，发生了局部网络异常或者是协调者在尚未发送完Commit请求之前自身发生了崩溃，导致最终只有部分参与者收到了Commit请求。于是，这部分收到了Commit请求的参与者就会进行事务的提交，而其他没有收到Commit请求的参与者则无法进行事务提交，于是整个分布式系统便出现了数据不一致性现象。 - 太过保守
如果在协调者指示参与者进行事务提交询问的过程中，参与者出现故障而导致协调者始终无法获取到所有参与者的响应信息的话，这时协调者只能依靠其自身的超时机制来判断是否需要中断事务，这样的策略显得比较保守。换句话说，二阶段提交协议没有设计较为完善的容错机制，任意一个节点的失败都会导致整个事务的失败。
3PC
在上文中，我们讲解了二阶段提交协议的设计和实现原理，并明确指出了其在实际运行过程中可能存在的诸如同步阻塞、协调者的单点问题、脑裂和太过保守的容错机制等缺陷，因此研究者在二阶段提交协议的基础上进行了改进，提出了三阶段提交协议。
协议说明
3PC，是Three-Phase Commit的缩写，即三阶段提交，是2PC的改进版，其将二阶段提交协议的“提交事务请求”过程一分为二，形成了由CanCommit、PreCommit和do Commit三个阶段组成的事务处理协议，其协议设计如图2-3所示。
图2-3.三阶段提交协议流程示意图注 1
阶段一：CanCommit
- 事务询问。
协调者向所有的参与者发送一个包含事务内容的 canCommit请求，询问是否可以执行事务提交操作，并开始等待各参与者的响应。 - 各参与者向协调者反馈事务询问的响应。
参与者在接收到来自协调者的 canCommit请求后，正常情况下，如果其自身认为可以顺利执行事务，那么会反馈Yes响应，并进入预备状态，否则反馈No响应。
阶段二：PreCommit
在阶段二中，协调者会根据各参与者的反馈情况来决定是否可以进行事务的PreCommit操作，正常情况下，包含两种可能。
执行事务预提交
假如协调者从所有的参与者获得的反馈都是Yes响应，那么就会执行事务预提交。
- 发送预提交请求。
协调者向所有参与者节点发出preCommit的请求，并进入Prepared阶段。 - 事务预提交。
参与者接收到preCommit请求后，会执行事务操作，并将Undo和Redo信息记录到事务日志中。 - 各参与者向协调者反馈事务执行的响应。
如果参与者成功执行了事务操作，那么就会反馈给协调者Ack响应，同时等待最终的指令：提交（commit）或中止（abort）。
中断事务
假如任何一个参与者向协调者反馈了No响应，或者在等待超时之后，协调者尚无法接收到所有参与者的反馈响应，那么就会中断事务。
- 发送中断请求。
协调者向所有参与者节点发出abort请求。 - 中断事务。
无论是收到来自协调者的abort请求，或者是在等待协调者请求过程中出现超时，参与者都会中断事务。
阶段三：doCommit
该阶段将进行真正的事务提交，会存在以下两种可能的情况。
执行提交
- 发送提交请求。
进入这一阶段，假设协调者处于正常工作状态，并且它接收到了来自所有参与者的Ack响应，那么它将从“预提交”状态转换到“提交”状态，并向所有的参与者发送doCommit请求。 - 事务提交。
参与者接收到 doCommit 请求后，会正式执行事务提交操作，并在完成提交之后释放在整个事务执行期间占用的事务资源。 - 反馈事务提交结果。
参与者在完成事务提交之后，向协调者发送Ack消息。 - 完成事务。
协调者接收到所有参与者反馈的Ack消息后，完成事务。
中断事务
进入这一阶段，假设协调者处于正常工作状态，并且有任意一个参与者向协调者反馈了No响应，或者在等待超时之后，协调者尚无法接收到所有参与者的反馈响应，那么就会中断事务。
- 发送中断请求。
协调者向所有的参与者节点发送abort请求。 - 事务回滚。
参与者接收到abort请求后，会利用其在阶段二中记录的Undo信息来执行事务回滚操作，并在完成回滚之后释放在整个事务执行期间占用的资源。 - 反馈事务回滚结果。
参与者在完成事务回滚之后，向协调者发送Ack消息。 - 中断事务。
协调者接收到所有参与者反馈的Ack消息后，中断事务。
需要注意的是，一旦进入阶段三，可能会存在以下两种故障。
· 协调者出现问题。
· 协调者和参与者之间的网络出现故障。
无论出现哪种情况，最终都会导致参与者无法及时接收到来自协调者的doCommit或是abort请求，针对这样的异常情况，参与者都会在等待超时之后，继续进行事务提交。
优缺点
三阶段提交协议的优点：相较于二阶段提交协议，三阶段提交协议最大的优点就是降低了参与者的阻塞范围，并且能够在出现单点故障后继续达成一致。
三阶段提交协议的缺点：三阶段提交协议在去除阻塞的同时也引入了新的问题，那就是在参与者接收到preCommit消息后，如果网络出现分区，此时协调者所在的节点和参与者无法进行正常的网络通信，在这种情况下，该参与者依然会进行事务的提交，这必然出现数据的不一致性。
Paxos算法
Proposer生成提案
对于一个Proposer来说，获取那些已经被通过的提案远比预测未来可能会被通过的提案来得简单。因此，Proposer在产生一个编号为 Mn的提案时，必须要知道当前某一个将要或已经被半数以上 Acceptor批准的编号小于 Mn但为最大编号的提案。并且，Proposer 会要求所有的 Acceptor 都不要再批准任何编号小于Mn的提案——这就引出了如下的提案生成算法。
- Proposer 选择一个新的提案编号 Mn，然后向某个 Acceptor 集合的成员发送请求，要求该集合中的Acceptor做出如下回应。
· 向Proposer承诺，保证不再批准任何编号小于Mn的提案。
· 如果 Acceptor 已经批准过任何提案，那么其就向 Proposer 反馈当前该Acceptor已经批准的编号小于Mn但为最大编号的那个提案的值。
我们将该请求称为编号为Mn的提案的Prepare请求。 - 如果Proposer收到了来自半数以上的Acceptor的响应结果，那么它就可以产生编号为Mn、Value值为Vn的提案，这里的Vn是所有响应中编号最大的提案的Value值。当然还存在另一种情况，就是半数以上的Acceptor都没有批准过任何提案，即响应中不包含任何的提案，那么此时Vn值就可以由Proposer任意选择。
在确定提案之后，Proposer就会将该提案再次发送给某个Acceptor集合，并期望获得它们的批准，我们称此请求为Accept请求。需要注意的一点是，此时接受Accept请求的Acceptor 集合不一定是之前响应 Prepare 请求的 Acceptor 集合——这点相信读者也能够明白，任意两个半数以上的Acceptor集合，必定包含至少一个公共Acceptor。
Acceptor批准提案
在上文中，我们已经讲解了Paxos算法中Proposer的处理逻辑，下面我们来看看Acceptor是如何批准提案的。
根据上面的内容，一个Acceptor可能会收到来自Proposer的两种请求，分别是 Prepare请求和Accept请求，对这两类请求做出响应的条件分别如下。
- Prepare请求：Acceptor可以在任何时候响应一个Prepare请求。
- Accept请求：在不违背Accept现有承诺的前提下，可以任意响应Accept请求。
因此，对Acceptor逻辑处理的约束条件，大体可以定义如下。
P1a：一个Acceptor只要尚未响应过任何编号大于Mn的Prepare请求，那么它就可以接受这个编号为Mn的提案。
从上面这个约束条件中，我们可以看出，P1a 包含了 P1。同时，值得一提的是，Paxos算法允许Acceptor忽略任何请求而不用担心破坏其算法的安全性。
算法优化
假设一个 Acceptor收到了一个编号为 Mn的 Prepare请求，但此时该 Acceptor已经对编号大于 Mn的 Prepare 请求做出了响应，因此它肯定不会再批准任何新的编号为 Mn的提案，那么很显然，Acceptor 就没有必要对这个 Prepare 请求做出响应，于是Acceptor可以选择忽略这样的Prepare请求。同时，Acceptor也可以忽略掉那些它已经批准过的提案的Prepare请求。
算法陈述
综合前面讲解的内容，我们来对Paxos算法的提案选定过程进行一个陈述。结合Proposer和Acceptor对提案的处理逻辑，就可以得到如下类似于两阶段提交的算法执行过程。
阶段一
- Proposer选择一个提案编号Mn，然后向Acceptor的某个超过半数的子集成员发送编号为Mn的Prepare请求。
- 如果一个Acceptor收到一个编号为Mn的Prepare请求，且编号Mn大于该Acceptor已经响应的所有 Prepare 请求的编号，那么它就会将它已经批准过的最大编号的提案作为响应反馈给Proposer，同时该Acceptor会承诺不会再批准任何编号小于Mn的提案。
阶段二
- 如果Proposer收到来自半数以上的Acceptor对于其发出的编号为Mn的Prepare请求的响应，那么它就会发送一个针对[Mn，Vn]提案的Accept请求给Acceptor。注意，Vn的值就是收到的响应中编号最大的提案的值，如果响应中不包含任何提案，那么它就是任意值。
- 如果Acceptor收到这个针对[Mn，Vn]提案的Accept请求，只要该Acceptor尚未对编号大于Mn的Prepare请求做出响应，它就可以通过这个提案。
当然，在实际运行过程中，每一个 Proposer 都有可能会产生多个提案，但只要每个Proposer都遵循如上所述的算法运行，就一定能够保证算法执行的正确性。值得一提的是，每个Proposer都可以在任意时刻丢弃一个提案，哪怕针对该提案的请求和响应在提案被丢弃后会到达，但根据Paxos算法的一系列规约，依然可以保证其在提案选定上的正确性。事实上，如果某个Proposer已经在试图生成编号更大的提案，那么丢弃一些旧的提案未尝不是一个好的选择。因此，如果一个 Acceptor 因为已经收到过更大编号的Prepare请求而忽略某个编号更小的Prepare或者Accept请求，那么它也应当通知其对应的Proposer，以便该Proposer也能够将该提案进行丢弃——这和上面“算法优化”部分中提到的提案丢弃是一致的。
提案的获取
在上文中，我们已经介绍了如何来选定一个提案，下面我们再来看看如何让 Learner 获取提案，大体可以有以下几种方案。
方案一
Learner 获取一个已经被选定的提案的前提是，该提案已经被半数以上的 Acceptor批准。因此，最简单的做法就是一旦Acceptor批准了一个提案，就将该提案发送给所有的Learner。
很显然，这种做法虽然可以让Learner尽快地获取被选定的提案，但是却需要让每个Acceptor与所有的Learner逐个进行一次通信，通信的次数至少为二者个数的乘积。
方案二
另一种可行的方案是，我们可以让所有的Acceptor将它们对提案的批准情况，统一发送给一个特定的 Learner（下文中我们将这样的 Learner 称为“主 Learner”），在不考虑拜占庭将军问题的前提下，我们假定Learner之间可以通过消息通信来互相感知提案的选定情况。基于这样的前提，当主Learner被通知一个提案已经被选定时，它会负责通知其他的Learner。
在这种方案中，Acceptor首先会将得到批准的提案发送给主 Learner，再由其同步给其他 Learner，因此较方案一而言，方案二虽然需要多一个步骤才能将提案通知到所有的 Learner，但其通信次数却大大减少了，通常只是 Acceptor 和Learner 的个数总和。但同时，该方案引入了一个新的不稳定因素：主 Learner随时可能出现故障。
方案三
在讲解方案二的时候，我们提到，方案二最大的问题在于主 Learner存在单点问题，即主 Learner随时可能出现故障。因此，对方案二进行改进，可以将主 Learner的范围扩大，即 Acceptor 可以将批准的提案发送给一个特定的 Learner 集合，该集合中的每个 Learner 都可以在一个提案被选定后通知所有其他的 Learner。这个 Learner集合中的 Learner个数越多，可靠性就越好，但同时网络通信的复杂度也就越高。
##
