分布式一致性算法Paxos，Zookeeper的ZAB协议，Raft算法
Paxos算法：
Paxos一直是分布式协议的标准，但是Paxos难于理解，更难以实现，Google的分布式锁系统Chubby作为Paxos实现曾经遭遇到很多坑。
阶段一：
1、Proposer选择一个提案变化Mn,然后向Acceptor的某个超过半数的子集成员发送 编号为Mn的Prepare请求。
2、如果一个Acceptor收到一个编号为Mn的Prepare请求，且编号Mn大于该Acceptor已经响应的所有Prepare请求的编号，那么它就会将它已经批准过的最大编号的提案作为响应反馈给Proposer，同时该Acceptor会承诺不会再批准任何编号小于Mn的提案。
阶段二：
1、如果Proposer收到来自半数以上的Acceptor对于其发出的编号为Mn的Prepare请求的响应，那么它就会发送一个针对[Mn,Vn]提案的Accept请求给Acceptor。注意，Vn的值就是收到的响应中编号最大的提案的值，如果响应中不包含任何提案，那么它就是任意值。
2、如果Acceptor收到这个针对[Mn,Vn]提案的Accept请求，只要该Acceptor尚未对编号大于Mn的Prepare请求做出响应，它就可以通过这个提案。
Zookeeper的ZAB协议
ZAB 是 Zookeeper 原子广播协议的简称，基于该协议，ZooKeeper 实现了一种主备模式的系统架构来保持集群中各个副本之间的数据一致性。
ZAB协议主要实现了：
1.使用一个单一的主进程来接收并处理客户端的所有事务请求，并采用 ZAB 的原子广播协议，将服务器数据的状态变更以事务 Proposal 的形式广播到所有的副本进程上去。
2.保证一个全局的变更序列被顺序应用。
3.当前主进程出现异常情况的时候，依旧能够正常工作。
ZAB 协议的核心：定义了事务请求的处理方式。
所有事务请求必须由一个全局唯一的服务器来协调处理，这样的服务器被称为 Leader服务器，而余下的其他服务器则成为 Follower 服务器。 Leader 服务器负责将一个客户端事务请求转换成一个事务proposal（提议），并将该 Proposal分发给集群中所有的Follower服务器。之后 Leader
服务器需要等待所有Follower 服务器的反馈,一旦超过半数的Follower服务器进行了正确的反馈后，那么 Leader 就会再次向所有的 Follower服务器分发Commit消息，要求其将前一个proposal进行提交。
这种事务处理方式与2PC（两阶段提交协议）区别在于，两阶段提交协议的第二阶段中，需要等到所有参与者的"YES"回复才会提交事务，只要有一个参与者反馈为"NO"或者超时无反馈，都需要中断和回滚事务。
ZAB协议介绍：
ZAB 协议包括两种基本的模式，分别是崩溃恢复和消息广播。
当整个服务框架在启动过程中，或是当 Leader 服务器出现网络中断、崩溃退出与重启等异常情况时， ZAB 协议就会进入恢复模式并选举产生新的 Leader 服务器。当选举产生了新的Leader 服务器同时集群中已经有过半的机器与该 Leader 服务器完成了状态同步之后，ZAB 协议就会退出恢复模式。
当集群中已经有过半的 Follower 服务器完成了和 Leader 服务器的状态同步，那么整个服务框架就可以进入消息广播模式了。当一台同样遵守 ZAB 协议的服务器启动后加入到集群中时，如果此时集群中已经存在一个 Leader 服务器在负责进行消息广播 ， 那么新加人的服务器就会自觉地进人数据恢复模式：找到
Leader 所在的服务器，并与其进行数据同步，然后一起参与到消息广播流程中去。
下面重点讲解崩溃回复和消息广播的过程。
消息广播
ZAB 协议的消息广播过程使用的是一个原子广播协议，类似于一个二阶段提交过程。针对客户端的事务请求，
Leader 服务器会为其生成对应的事务 Proposal ,并将其发送给集群中其余所有的机器，然后再分別收集各自的选票，最后进行事务提交。
在 ZAB 协议的二阶段提交过程中，移除了中断逻辑，所有的 Follower 服务器要么正常反馈 Leader 提出的事务 Proposal ,要么就抛弃Leader 服务器。同时， ZAB 协议将二阶段提交中的中断逻辑移除意味着我们可以在过半的
Follower 服务器已经反馈 Ack 之后就开始提交事务 Proposal 了，而不需要等待集群中所有的 Follower 服务器都反馈响应。这种简化了的二阶段提交模型无法处理 Leader 服务器崩溃退出而带来的数据不一致问题，此时采用崩溃恢复模式来解决这个问题。
在整个消息广播过程中， Leader 服务器会为每个事务请求生成对应的 Proposal来进行广播，并且在广播事务 Proposal 之前， Leader 服务器会首先为这个事务 Proposal 分配一个全局单调递增的唯一事务ID (即 ZXID )。
Leader 服务器会为每一个 Follower 服务器都各自分配一个单独的队列，然后将需要广播的事务 Proposal 依次放入这些队列中去，并且根据 FIFO策略进行消息发送。每一个 Follower 服务器在接收到这个事务 Proposal 之后，都会首先将其以事务日志的形式写入到本地磁盘中去，并且在成功写入后反馈给
Leader 服务器一个 Ack 响应。当 Leader 服务器接收到超过半数 Follower 的 Ack 响应后，就会广播一个Commit 消息给所有的 Follower 服务器以通知其进行事务提交，同时 Leader 自身也会完成对事务的提交。
崩溃恢复
zab协议需要设计的选举算法应该满足：确保提交已经被 Leader 提交的事务 Proposal，同时丢弃已经被跳过的事务 Proposal 。
如果让 Leader 选举算法能够保证新选举出来的 Leader 服务器拥有集群中所有机器最高编号（即ZXID
最大）的事务 Proposal,那么就可以保证这个新选举出来的 Leader —定具有所有已经提交的提案。同时，如果让具有最高编号事务 Proposal 的机器来成为 Leader, 就可以省去 Leader 服务器检查 Proposal 的提交和丢弃工作的这一步操作。
数据同步
Leader 服务器会为每一个 Follower 服务器都准备一个队列，并将那些没有被各 Follower 服务器同步的事务以 Proposal 消息的形式逐个发送给 Follower
服务器，并在每一个 Proposal 消息后面紧接着再发送一个 Commit 消息，以表示该事务已经被提交。等到 Follower 服务器将所有其尚未同步的事务 Proposal 都从 Leader 服务器上同步过来并成功应用到本地数据库中后， Leader 服务器就会将该 Follower 服务器加入到真正的可用 Follower 列表中，并开始之后的其他流程。
下面来看 ZAB 协议是如何处理那些需要被丢弃的事务 Proposal 的。在 ZAB 协议的事务编号 ZXID 设计中， ZXID 是一个 64 位的数字，低 32 位可以看作是一个简单的单调递增的计数器，针对客户端的每一个事务请求， Leader 服务器在产生一个新的事务 Proposal 的时候，都会对该计数器进行加1操作；高
32 位代表了 Leader 周期 epoch 的编号，每当选举产生一个新的 Leader 服务器，就会从这个 Leader 服务器上取出其本地日志中最大事务 Proposal 的 ZXID ,并从该 ZXID 中解析出对应的 epoch 值，然后再对其进行加1操作，之后就会以此编号作为新的 epoch, 并将低 32 位置0来开始生成新的 ZXID 。
基于这样的策略，当一个包含了上一个 Leader 周期中尚未提交过的事务 Proposal的服务器启动加入到集群中，发现此时集群中已经存在leader，将自身以Follower 角色连接上 Leader 服务器之后， Leader 服务器会根据自己服务器上最后被提交的 Proposal来和 Follower
服务器的 Proposal进行比对，发现follower中有上一个leader周期的事务Proposal时，Leader 会要求 Follower 进行一个回退操作——回退到一个确实已经被集群中过半机器提交的最新的事务 Proposal 。
进一步对消息广播和崩溃恢复两个过程进行细分，可以分为三个阶段，分别是Discovery（发现阶段），Synchronization（同步阶段），Broadcast（广播阶段）
ZAB 中的节点有三种状态
- following：当前节点是跟随者，服从 leader 节点的命令
- leading：当前节点是 leader，负责协调事务
- election/looking：节点处于选举状态
Leader进程与所有的Follower进程之间都通过心跳检测机制来感知彼此的情况。
ZAB协议和Paxos协议的区别
- ZAB协议和Paxos算法的本质区别，两者的设计目标不太一样。
- ZAB协议主要用于构建一个高可用的分布式数据主备系统。例如ZooKeeper
- Paxos算法则是用于构建一个分布式的一致性状态机系统。
Raft算法
Raft，它是一个为真实世界应用建立的协议，主要注重协议的落地性和可理解性。Raft大概将整个过程分为三个阶段，leader election，log replication和commit(safety)。
每个server处于三个状态：leader，follower，candidate。正常情况下，所有server中只有一个是leader，其它的都是follower。server之间通过RPC消息通信。follower不会主动发起RPC消息。leader和candidate(选主的时候)会主动发起RPC消息。
Leader election
每个server只会给每个term投一票，具体的是否同意和后续的Safety有关
所有的节点开始时都是follower状态，选举超时是在150~300ms之间的随机值。
一、节点全部正常的情况
1、当follower在选举超时时间内未收到leader的心跳信息，它将变为candidate状态，同时开始一个新的选举期，并给自己投票。（例如Note A，term：1，vote count:1）。
2、然后candidate向其它节点发生投票请求。
3、如果收到投票信息的节点在这个选举期还没有投过票，那么它就投票给这个candidate节点，并重置自己的选举超时时间（记录信息term：1，voted for:A）。
4、如果此candidate获得大部分的投票，则此candidate变为leader。
5、然后leader开始发送append entries 信息给它的follower，这些信息已心跳超时指定的时间间隔发送。
6、follower们回复每个收到的append entries信息。
二、leader节点发生故障的情况
当leader节点故障时（宕机或网络不通），follower在超时时间内未收到leader的心跳时就会发起新的选举（例如：Node B, term:2, vote count:1）。按照《一》选举出新的leader。
三、多个节点同时发起投票的情况
以同时两个节点为例：Node A， Node B
A和B在一个选举期同时开始选举，Node A(term:4,vote count:1), Node B(term:4, vote count:1)，并且经过选举，A和B获得了相同的选票（半数），这时A和B等待超时再发起下一个term的选举，直到有一个节点获取到多数的选票。
四、发生网络分区的情况
假设开始时有五个节点（A, B, C, D, E），B为leader；此时发生了网络分区，C,D,E之间网络连通，A,B之间网络连通，但A,B和C,D,E之间的网络不通，即A,B一个网络分区，C,D,E一个网络分区。这时C,D,E在网络超时后会重新选举出新的leader，假设为C,此时整个分布式系统中有两个leader，为别为B,C。
如果有Client连接到B对分布式系统进行修改，因为B得不到大多数followers（只有A）的日志复制响应，将返回Client失败。
而当Client连接到C对分布式系统进行修改时，由于C可以得到大多数followers（D,E）的日志复制响应，从而客户返回Client正确的结果。
现在让网络恢复，A,B,C,D,E之间网络都可以连通，leader B向所有的follower发送心跳时会收到更新的选举结果的响应（来自C,D或E）,B将改变自己为follow状态，A收到C的心跳信息时发现term大于本地的，A将改选C并更新本地term等信息。
A和B都将回滚它们未提交的日志并且匹配最新的leader（即C）的日志，至此，整个分布式系统的状态达成了一致的状态。
Log Replication
一旦我们选出了一位leader，我们需要将所有的改变都复制到我们的系统中。这是通过基于心跳的同样的append entries信息来完成的。
1、首先客户端向leader发送一个修改命令。
2、这个修改被追加到leader的log中。在下一个心跳时，这个修改被发送到followers。
3、followers收到leader的log 信息时，把修改写入本地log,然后向leader返回信息。
4、leader在收到大多数followers的响应时，向客户端返回结果。
Log Replication细节注意点
当一个新的leader选出来的时候，它的日志和其它的follower的日志可能不一样，这个时候，就需要一个机制来保证日志是一致的。如下图所示，一个新leader产生时，集群状态可能如下：
最上面这个是新leader，a~f是follower，每个格子代表一条log entry，格子内的数字代表这个log entry是在哪个term上产生的。
新leader产生后，log就以leader上的log为准。其它的follower要么少了数据比如b，要么多了数据，比如d，要么既少了又多了数据，比如f。
需要有一种机制来让leader和follower对log达成一致，leader会为每个follower维护一个nextIndex，表示leader给各个follower发送的下一条log entry在log中的index，初始化为leader的最后一条log
entry的下一个位置。leader给follower发送AppendEntriesRPC消息，带着(term_id, (nextIndex-1))， term_id即(nextIndex-1)这个槽位的log entry的term_id，follower接收到AppendEntriesRPC后，会从自己的log中找是不是存在这样的log entry，如果不存在，就给leader回复拒绝消息，然后leader则将nextIndex减1，再重复，直到AppendEntriesRPC消息被接收。
以leader和b为例：
初始化，nextIndex为11，leader给b发送AppendEntriesRPC(6,10)，b在自己log的10号槽位中没有找到term_id为6的log entry。则给leader回应一个拒绝消息。接着，leader将nextIndex减一，变成10，然后给b发送AppendEntriesRPC(6,
9)，b在自己log的9号槽位中同样没有找到term_id为6的log entry。循环下去，直到leader发送了AppendEntriesRPC(4,4)，b在自己log的槽位4中找到了term_id为4的log entry。接收了消息。随后，leader就可以从槽位5开始给b推送日志了。
Leader election的细节注意点
1.哪些follower有资格成为leader?
Raft保证被选为新leader的server拥有所有的已经committed的log entry，这与ViewStamped
Replication不同，后者不需要这个保证，而是通过其他机制从follower拉取自己没有的commited的log entry。
这个保证是在RequestVoteRPC阶段做的，candidate在发送RequestVoteRPC时，会带上自己的最后一条log entry的term_id和index，server在接收到RequestVoteRPC消息时，如果发现自己的日志比RPC中的更新，就拒绝投票。日志比较的原则是，如果本地的最后一条log
entry的term id更大，则更新，如果term id一样大，则日志更多的更新(index更大)。
2. 哪些log entry被认为是commited?
两种情况：
1. leader正在replicate当前term即term2的log entry给其它follower，一旦leader确认了这条log
entry被majority写盘了，这条log entry就被认为是committed。如图a，S1作为当前term即term2的leader，log index为2的日志被majority写盘了，这条log entry被认为是commited。
2. leader正在replicate更早的term的log entry给其它follower。图b的状态是这么出来的：
S1作为term2的leader，给S1和S2 replicate完log index=2的日志后crash，当前状态为：
S1 1 2 宕机
S2 1 2
S3 1
S4 1
S5 1
S5被选为term3的leader(由于S5的最后一条log entry比S3，S4的最后一条log entry更新或一样新，接收到S3，S4，S5的投票)，自己产生了一条term3的日志，没有给任何人复制，就crash了，当前状态如下：
S1 1 2
S2 1 2
S3 1
S4 1
S5 1 3 宕机
接着S1重启后，又被选为term4的leader(接收到S1，S2，S3的投票，文中没有指出S4？)，然后S1给S3复制了log
index为2的log entry，当前状态如下：
S1 1 2
S2 1 2
S3 1 2
S4 1
S5 1 3 宕机
这个时候S5重启，被选为了term5的主(接收了S2，S3，S4，S5的投票)，那么S5会把log index为2的日志3复制给其它server，那么日志2就被overwrite了。
所以虽然这里日志2被majority的server写盘了，但是并不代表它是commited的。
对commit加一个限制：主的当前term的至少一条log entry被majority写盘
如：c图中，就是主的当前term 4的一条log entry被majority写盘了，假设这个时候S1宕机了，S5是不可能变成主的。因为S2和S3的log entry的term为4，比S5的3大。
Cluster membership changes（机器的添加、减少机器）
Raft将有server加入集群或者从集群中删除也纳入一致性协议中考虑，避免由于下线老集群上线新集群而引起的不可用。集群的成员列表重配置也是一条log entry，log内容包含了集群成员列表。
老集群配置用Cold表示，新集群配置用Cnew表示。
当集群成员配置改变时，leader收到人工发出的重配置命令从Cold切成Cnew，leader
给其它server复制一条特殊的log entry给其它的server，内容包括Cold∪Cnew，一旦server收到了这条特殊的配置log
entry，其后的log entry会被replicate到Cold∪Cnew中，一条log
entry被认为是committed的需要满足这条日志既被Cold的majority写盘，也被Cnew的majority写盘。一旦Cold∪Cnew这条log
entry被确认为committed，leader就会产生一条只包含了Cnew的log entry，同样复制给所有server，server收到log后，老集群的server就可以自动下线了。
横坐标代表没有leader的ms数，每条线代表election timeout的随机取值区间。
上图说明只要给个5ms的区间，就能避免反复的投票被瓜分。超过10ms没有leader的情况都是因为投票被瓜分的情况。
150-300ms的election timeout区间，没有主的时间平均287ms。
系统推荐使用150ms~300ms