一，Paxos算法

Paxos算法：解决分布式系统中基于消息传递高度容错的一致性算法 ,是目前公认的解决分布式一致性问题最有效的算法之一

Paxos算法解决的问题：快速正确的在一个分布式系统中对某一个数据达成一致，并且保证不论发生任何异常都不会破坏整个系统数据的一致性

一，Paxos产生的背景

在分布式系统中，总会发生如机器宕机或网络异常导致消息的丢失，延迟，重复，乱序等情况，Paxos算法的出现就是为了解决如上问题，Paxos需要在一个可能发生上述情况的分布式系统中快速且正确的在集群内部对某一个数据达成一致，并且保证不论发生以上任何情况，都不会破坏系统的一致性

二，Paxos的描述和流程

在一个Paxos系统中所有节点都被划分成三种角色：

Proposer：提案者
Acceptor：接受者
Learner：学习者

每一个节点可以兼任多种角色

Paxos算法流程分为三个阶段：

1)，Prepare准备阶段

Proposer向多个Acceptor发出Propose请求(无需携带提案内容)Promise(承诺)
Acceptot针对收到的Propose请求进行Promise(承诺)

注：promise就是Acceptor承诺让当前的Proposer当领导者

2)，Accept接受阶段

Proposer收到多数Acceptor承诺的Promise后，向Acceptor发出Propose请求(需要携带提案内容)
Acceptor针对收到的Propose请求进行Accept处理

注：当前Proposer通过多数的Acceptor的Promise成为领导者时，提案或者任务可以得到Accept的授权成为绝议

3)，Learn学习阶段

Proposer将形成的绝议发给所有的Learners

三，Paxos的实现细节

1）Propare阶段：Proposer生成全局唯一且递增的Proposal ID，向所有Acceptor发送Propose请求，这里无需携带提案内容，只携带Proposal ID即可

2）Promise：Acceptor收到Propose请求后，做出"两个承诺，一个应答"

不再接受Proposal ID小于等于(注：这里是<=)当前请求的propose请求
不再接受Proposal ID小于(注：<)当前请求的Accept请求
不违背以前做出的承诺下，回复已经Accept过的提案中Proposal ID最大的那个提案Value和Proposal ID，没有则返回空值

3）Propose：Proposer收到多数Acceptor的Promise应答后，从应答中选择Proposal ID最大的提案的Value，作为本次要发起的提案，如果所有的应答提案Value均为空，则可以自己自定义提案的Value，然后携带当前Proposal ID，向所有Acceptor发送Propose请求

4）Accept：Acceptor收到Propose请求后，在不违背自己之前做出的承诺下，接受并持久化Proposeal ID和提案Value

5）Learn：Proposer收到多数Acceptor的Accept后，绝议形成，将形成的绝议发送给所有的Learner

四，Paxos算法产生的多种情况

设有A,B,C,D,E五位议员，就防疫措施进行绝议

一，情况1

A就防疫措施提出全民普筛的方式，B-E进行表绝

注：相当于有一个Proposer提案者，多个Acceptor接受者

A发起1号Proposal ID 1的Propose(无)，等待Acceptor的Promise承诺
B-E回应Promise承诺
A在收到两个及以上就会发起全民普筛的提案Proposeal
B-E回应Accept表示同意提案
通过Proposal提案
交与Learner执行

二，情况2

A提出全民普筛的防疫措施，D提出全民免疫的防疫措施，B,C,D进行表决

注：有两个Proposer提案者A和D，BCD为接受者

A，D同时发起Proposer请求(Proposeal ID分别为1和2)
B承诺A，E承诺D，C的承诺成为关键

C先收到A的Proposer请求，承诺A

A发起Proposal提案(1,全民普筛)，C和B接受
之后C又收到D的Proposal请求，接受了A的提案，并承诺了D
D发起Proposeal(2,全民免疫)的提案，C和E接受，之后A和D同时广播绝议(将A的提案覆盖)

注：多个Proposer并发请求时，ID大的后请求的会覆盖前者

三，情况3

A提出全民普筛的防疫措施，D提出全民免疫的防疫措施，B,C,D进行表决(角色和情况二一样)

注：有两个Proposer提案者A和D，BCD为接受者

A，D同时发起Proposer请求(Proposeal ID分别为1和2)
B承诺A，E承诺D，C的承诺成为关键

C先收到A的消息承诺A，之后立刻收到D的消息承诺D

A发起Proposal提案(1,全民普筛)，无响应，A重新发送Propose请求，C再次承诺A
D发起Proposal提案(2,全民免疫)，无响应，D重新发送Propose请求，C再次承诺D
A再次发起Proposal提案(1,全民普筛)，无响应，A重新发送Propose请求，C再次承诺A
D再次发起Proposal提案(2,全民免疫)，无响应，D重新发送Propose请求，C再次承诺D
……………最终形成死循环…………………

Paxos算法的多个Proposer并发请求Acceptor，相互争夺Accept，造成死循环的情况，是Paxos的一个注意弊端，针对这种情况，一种改进的Paxos算法被提出：从系统中只选一个Proposer提案者作为Leader，只有Leader可以发起请求和提案，这样就不会发生死锁的情况

二 , ZAB协议

ZAB借鉴了Paxos算法，是特的为Zookeeper设计的支持崩溃恢复的原子广播协议，基于改协议，Zookeeper设计了只为一台客户端(Leader)负责处理外部的写事务请求，然后将数据同步到Follower节点，即Zookeeper只有Leader可以发起提案

一，ZAB协议的模式

ZAB协议包括两种基本的模式：消息广播，崩溃恢复

一，消息广播

客户端发起一个写操作请求
Leader服务器将客户端的请求转化为事务Proposal提案，同时为每一个Proposal分配一个全局ID，即ZXID
Leader服务器为每个Follower服务器分配一个单独的队列，然后将需要广播的Proposal依次放到队列中，并且根据FIFO策略进行消息发送
Follower收到Proposal后，会首先将其以事务日志的方式写入本地磁盘中，写入成功后向Leader反馈一个ACK响应消息
Leader接受超过半数以上的Follower的ACK响应后，即认为消息发送成功，可以发送commit消息
Leader向所有的Follower广播commit消息，同时自身也会完成事务提交，Follower收到commit后，会将上一条事务提交

注：Zookeeper采用ZAB协议的核心，就是只要有一台服务器提交了Proposal，就要确保所有的服务器最终都正确提交Propseal

ZAB协议针对事务请求的处理过程类似于一个两阶段提交过程：

广播事务阶段
广播提交阶段

这个过程有可能因Leader宕机带来数据不一致：比如

Leader发起一个事务Proposal 1后就宕机，Follower都没有Proposeal 1
Leader收到半数Follower的ACK后就宕机，没有来得及发送Commit

二，崩溃恢复

一旦Leader服务器出现崩溃或者由于网络原因导致Leader服务器失去了过半Follower的联系，那么就会进入崩溃恢复模式

1, 服务器两种异常情况：

假设一个Proposal事务提案提出之后，Leader挂了
一个事务在Leader上提交了，并且过半的Follower都响应ACK，但是Leader在Commit消息发出之前挂了

2, Zab崩溃恢复要求满足以下两个要求：

确保已经被Leader提交的提案Proposal，必须被所有的Follower服务器提交(已经产生提案，Follower必须执行)
确保丢弃已经被Leader提出的，但没有被提交的Proposal(丢弃没有被提交的)

崩溃恢复主要包括两个部分：Leader选举和数据恢复

1，Leader选举：ZAB协议需要保证选举出来的Leader需要满足以下条件

新选举出来的Leader不能包含未提交的Proposal，即新Leader必须都是已经提交了Proposal的Follower节点
新选举的Leader节点中含义最大的ZXID，这样的好处可以避免Leader服务器检查Proposal的提交和丢弃工作

2，ZAB数据恢复：

完成Leader选举后，在正式开始工作之前(接收事务请求，然后提出新的Proposal)，Leader服务器会首先确定事务日志的所有Proposal是否都已经被集群中过半的服务器Commit(处理上一个Leader的残留的任务)
Leader服务器需要确保所有的Follower服务器能够接收到每一条事务的Proposal，并且能够将所有已经提交的事务Proposal应用到内存数据中，等到Follower将所有的尚未同步的事务Proposal都从Leader服务器上同步过，并且应用到内存数据中以后Leader才会把该Follower加入到真正的Follower列表中

WQL

Paxos算法和ZAB协议