分布式一致性协议在实践过程中产生了许多优秀的协议和算法，其中就包括两阶段提交、三阶段提交协议和Paxos算法。

2PC：两阶段提交

两阶段提交，主要由协调者和参与者组成，协调者负责协调所有参与者是否提交最后结果，并保证各参与者之间的结果一致（提交或者回滚）。

阶段一：提交事务请求阶段

• 协调者向所有参与者发送事务内容，询问是否可以执行事务提交操作，并等待各参与者的回应
• 各参与者节点执行事务操作，并将undo和redo信息记录事务日志中
• 如果参与者执行了事务操作，那么就反馈给协调者yes响应，表示事务可以执行，否则返回no，表示事务不可以执行。

阶段二：执行事务提交阶段

阶段二主要是对各参与者反馈的情况决定是否继续进行事务提交操作，或者回滚。 主要包括两种情况：

第一种：执行事务提交

假如协调者从所有的参与者获得的反馈都是yes，那么就执行事务提交。

• 发送提交请求，协调者向所有参与者节点发送commit请求
• 事务提交，参与者接收到commit请求后，会正式执行事务提交，并在完成后释放整个事务执行期间占用的资源
• 反馈事务提交结果，提交完成后，向协调者发送ack信息
• 完成事务，协调者接收到所有参与者的ack信息后，完成事务。

第二种：中断事务

假如任何一个参与者向协调者反馈了no，或者在等待超时之后，协调者仍然没有接收到所有参与者的反馈，那么就中断事务。

• 发送回滚请求，协调者向所有参与者节点发送rollback请求
• 事务回滚，参与者接收到rollback请求后，利用第一阶段中记录的undo信息来执行事务回滚，并在完成回滚后释放在整个事务期间占用的资源
• 反馈事务回滚结果，参与者在完成事务回滚之后，向协调者发送ack信息
• 中断事务，协调者接收到所有的参与者反馈的ack信息后，完成事务中断

两阶段提交优缺点

• 优点：原理简单，实现方便
• 缺点：同步阻塞，单点问题、脑裂、容错机制简单

3PC：三阶段提交

三阶段提交可说是2PC的改进版，其将二阶段提交协议的提交事务请求过程一分为二，形成了CanCommit、PreCommit和do Commit三个阶段组成的事务处理协议。

阶段一：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算法

Paxos算法是一种基于消息传递且有高度容错特性的一致性算法。

在Paxos算法中有三种参与角色，分别是Proposer，Acceptor和Learner。在具体实现时，一个节点可能充当不止一种角色。 同时，每个角色也可能不止一个。 这其中:

• Proposer 是提案者，负责产生提案
• Acceptor 负责批准提案，且只能批准一个提案
• Learner 获取选定提案的信息

推导过程

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

P2：如果编号为M0、Value值为V0的提案（即[M0,V0]）被选定了，那么所有比编号M0更高的，且被选定的提案，其Value值必须也是V0。

P2a：如果编号为M0、Value值为V0的提案（即[M0,V0]）被选定了，那么所有比编号M0更高的，且被Acceptor批准的提案，其Value值也必须是V0。

P2b：如果一个提案[M0，V0]被选定后，那么之后任何Proposer产生的编号更高的提案，其Value值都是V0。

因为一个提案必须在被Proposer提出后才能被Acceptor批准，因此P2b包含了P2a，进而包含了P2，于是，接下去的重点就是论证P2b成立即可：

假设某个提案[M0, V0]已经被选定了，证明任何编号Mn>M0的提案，其Value值都是V0。

P2c：对于任意的Mn和Vn，如果提案[Mn, Vn]被提出，那么肯定存在一个由半数以上的Acceptor组成的集合S，满足以下两个条件中的任意一个

• S中不存在任何批准过编号小于Mn的提案的Acceptor
• 选取S中所有Acceptor批准的编号小于Mn的提案，其中编号最大的那个提案其Value值是Vn。

至此，只需要通过保持P2c,我们就能够满足P2b。

实际上，P2c规定了每个Proposer如何产生一个提案：对于产生的每个提案[Mn, Vn]，需要满足如下条件：

• 要么S中没有Acceptor批准过编号小于Mn的任何提案。
• 要么S中的所有Acceptor批准的所有编号小于Mn的提案中，编号最大的那个提案的Value值为Vn。

当每个Proposer都按照这个规则产生提案时，就可以保证满足P2b了

对Acceptor逻辑处理的约束条件，大体可以定义如下：

Acceptor批准提案

一个Acceptor可能会收到来自Proposer的两种请求，分别是Prepare和Accept请求。

• Prepare请求：Acceptor可以在任何时候响应一个Prepare请求
• Accept请求：在不违背Accept现有承诺的前提下，可以任意响应Accept请求。

因此，对Acceptor逻辑处理的约束条件大致如下：

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

算法优化

忽略不必要的Prepare请求响应

假设一个Acceptor收到了一个编号为Mn的Prepare请求，但此时该Acceptor已经对编号大于Mn的Prepare请求做出了响应，因为它肯定不会再批准任何新的 编号为Mn的填，那么很显然，Acceptor就没有必要对这个Prepare请求做出响应，于是Acceptor可以选择忽略这样的Prepare请求。同时，Acceptor也可以忽略掉那些它已经批准过的提案的Prepare请求。

算法陈述

阶段一

• 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都可以在任何时刻丢弃一个提案，哪怕针对该提案的请求和响应在提案被丢弃后会到达，但根据Paxos算法的一系列规约，依然可以保证其在提案选定上的正确性。

因此，如果一个Acceptor因为已经收到过更大编号的Prepare请求而忽略某个编号更小的Prepare或者Accept请求，那么它也应当通知其对应的Proposer， 以便该Proposer也能够将该提案进行丢弃。

提案的获取

方案一

Learner获取一个已经被选定的提案的前提是，该提案已经被半数以上的Acceptor批准。因此最简单的做法就是一旦Acceptor批准了一个提案，就将该提案发送给所有的Learner。

很显然，这种做法虽然可以让Learner尽快地获取被选定的提案，但是却需要让每个Acceptor与所有的Learner逐个进行一次通信，通信的次数至少为二者个数的乘积。

方案二

让所有的Acceptor将它们对提案的批准情况，统一发送给一个特定的Learner，在不考虑拜占庭将军问题的前提下，我们假定Learner之间可以通过消息通信来相互感知提案的选定情况，基于这个 前提，当主Learner被通知一个提案已经被选定时，它会负责通知其他的Learner。

这种方案，Acceptor首先会将得到批准的提案发送给主Learner，再由其同步给其他Learner，因此比方案一通信次数大大减少，通常只是Acceptor和Learner的个数总和。但同时，主Learner可能故障。

方案三

对方案二进行改进，可以将主Learner的范围扩大，即Acceptor可以将批准的提案发送给一个特定的Learner集合，该集合中的每个Learner都可以在一个提案被选定后通知其他所有Learner。 这个Learner集合中的Learner个数越多，可靠性越好。但同时网络通信复杂度越高。