分布式一致性算法

• 为什么需要一致性算法
• 两阶段提交2PC
• • 算法思路
  • 算法过程
  • 2PC的缺点
• 三阶段提交3PC
• • 算法思路
  • 算法过程
• Paxos算法
• • 算法过程
  • 死循环问题
• ZAB协议
• • 崩溃恢复模式
  • 崩溃恢复需要满足的要求
  • 消息广播模式

如果一个系统将转账业务拆分成了两部分，一部分是自己扣钱，另一部分是对方加钱，这两个服务部署在不同的机器上，万一在消息的传播过程中某个系统宕机了，我们需要保证两边的数据的一致性

还有一种情况，比如CAP中如果满足CP的话，在一定时间内应该保证所有机器都拥有相同的数据，我们也可以通过一致性算法来解决

我们一般使用两阶段提交协议来完成分布式事务的处理，而且一般都是数据库使用

参与者将操作成败告诉协调者，协调者根据所有参与者结果的返回情况来决定该事务是否提交，亦或是回滚

两阶段指准备阶段和提交阶段

准备阶段：事务发起者首先向协调者发起事务请求，然后协调者会给所有参与者发送prepare请求（其中包括事务内容），参与者收到prepare消息后，他们会开始执行事务（但不提交），并将Undo和Redo信息记入事务日志中，之后参与者就向协调者反馈是否准备好了

提交阶段：如果所有的参与者都返回了准备好了的消息，这个时候就进行事务的提交，协调者此时会给所有的参与者发送Commit请求 ，当参与者收到Commit请求的时候会执行前面执行的事务的 提交操作 ，提交完毕之后将给协调者发送提交成功的响应；如果并不是所有参与者都返回了准备好了的消息，那么此时协调者将会给所有参与者发送回滚事务的rollback请求

1，单点故障问题：如果协调者挂了那么整个系统都处于不可用的状态了

2，同步阻塞问题：即当协调者发送prepare请求，参与者收到之后如果能处理那么它将会进行事务的处理但并不提交，这个时候会一直占用着资源不释放，如果此时协调者挂了，那么这些资源都不会再释放了，这会极大影响性能

3，数据不一致问题：提交阶段协调者只发送了一部分的commit请求就挂了，那么也就意味着，收到消息的参与者会进行事务的提交，而后面没收到的则不会进行事务提交，那么这时候就会产生数据不一致性问题

首先询问参与者是否可以完成该事务，根据收到的反馈决定进行2PC或者取消事务

CanCommit阶段：协调者向所有参与者发送CanCommit请求，参与者收到请求后会根据自身情况查看是否能执行事务，如果可以则返回YES响应并进入预备状态，否则返回NO

PreCommit阶段：协调者根据参与者返回的响应来决定是否可以进行下面的PreCommit操作。如果上面参与者返回的都是YES，那么协调者将向所有参与者发送PreCommit预提交请求，如果在第一阶段协调者收到了 任何一个 NO 的信息，或者在一定时间内并没有收到全部的参与者的响应，那么就会中断事务

DoCommit阶段：如果协调者收到了所有参与者在PreCommit阶段的YES响应，那么协调者将会给所有参与者发送DoCommit请求，参与者收到DoCommit请求后则会进行事务的提交工作，DoCommit阶段参与者如未收到协调者发送的提交事务的请求，它会在一定时间内进行事务的提交，因为在第一阶段所有的协调者全部返回了可以执行事务的响应，所以它认为其他机器都可以执行

Paxos算法是基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一，其解决的问题就是在分布式系统中如何就某个值（决议）达成一致

准备阶段：每个提案者在提出提案时都会首先获取到一个具有全局唯一性的、递增的提案编号N，然后将该编号赋予其要提出的提案，在第一阶段是只将提案编号发送给所有的表决者；

表决者在收到某提案后，会将该提案编号N记录在本地，每个表决者仅会通过编号大于自己本地增大编号的提案，在批准提案时表决者会将以前接受过的最大编号的提案作为响应反馈给Proposer

执行阶段：如果提案者收到了超过半数的批准，那么此时提案者会给所有的参与者发送真正的提案，这个时候提案者会发送提案的内容和提案编号

表决者收到提案请求后会再次比较本身已经批准过的最大提案编号和该提案编号，如果该提案编号大于等于已经批准过的最大提案编号，那么就执行该提案（此时执行提案内容但不提交），随后将情况返回给提案者，如果不满足则不回应或者返回NO

当提案者收到超过半数的accept，那么它这个时候会向所有的参与者发送提案的提交请求让它们强制执行该提案；提案者如果没有收到超过半数的accept，那么它将会将递增该提案的编号，然后重新进入准备阶段

该算法有一个死循环问题，有多个提案者时，它们会互相递增提案编号导致谁也执行不了，解决方法就是只设定一个提案者即可

ZooKeeper在解决分布式数据一致性问题自己写了一个协议叫ZAB，该协议可以更好的支持崩溃恢复

当新建一个集群或者Leader挂掉之后会进入该模式，流程如下：

开始时我们按一定顺序启动集群中的机器，被启动的机器会首先投票给自己 ，投票内容为服务器的myid和ZXID（服务器保存的最大提案id），然后将消息广播出去， 所有机器在收到投票信息后会将投票信息与自己的作比较。首先它会比较ZXID，ZXID大的优先为Leader，如果相同则比较myid，myid大的优先作为Leader

执行以上过程直到某台机器的票数超过半数，该机器成为Leader

Zab 协议崩溃恢复要求满足以下两个要求：
1）确保已经被Leader提交的提案必须最终被所有的Follower服务器提交
2）确保丢弃已经被Leader提出的但是没有被提交的提案

当集群中存在Leader时，自动进入消息广播模式，流程如下：

客户端发起一个写操作请求，从机收到请求后会将该请求发给主机

Leader服务器将求转化为事务提案，同时为每个提案分配一个全局的ID，Leader 服务器为每个Followe 服务器分配一个单独的队列，然后将需要广播的提案依次放到队列中，并且根据FIFO策略进行消息发送

Follower接收到提案后，会首先将其以事务日志的方式写入本地磁盘中，写入成功后Leader反馈一个响应消息

Leader接收到超过半数以上Follower的成功响应消息后，即认为消息发送成功，发送提交消息，自身也会完成事务提交

Leader服务器与每一个Follower服务器之间都维护了一个单独的FIFO 消息队列进行收发消息，使用队列消息可以保证数据传输的顺序性。请求处理的顺序不同就会导致数据的不同，从而 产生数据不一致问题