最近在学习关于一致性算法的相关知识，重点学习了Paxos算法以及Zab协议。Paxos算法是Lamport提出来的，主要为了解决分布式系统的一致性问题，即每台机子看到的值应该是一致的。Zab协议主要使用在zk上，主要场景在故障恢复与信号广播。
Paxos协议
主要目标
多个节点之间就某个值（提案value）达成一致（决议）的通信协议，也就是说，每个节点 提出的提案 会 对 同一个提案内容 达成一。下面简称提案ID为 ProposalID，提案内容为value。
主要过程
在Paxos协议中，主要有两个角色Proposal和Acceptor，除此之外还有Learners。一台机器同时都会有这三个角色。它在提交提案时是Proposer，接受别人的提案时候是Acceptor。当达成一致时，又是Learners。
Paxos算法分为两个阶段
- prepare阶段
1.1
proposer生成全局唯一的ProposalId m，将m发送给所有的Acceptor
1.2
所有的Acceptor收到提案后，将该提案与已经接受的最大提案Id n进行判断
（1）如果 n不存在，即acceptor第一次接受提案，则接受该提案（minProposalID=m），返回空
（2）如果n存在，且n < m，则接受该提案，将m记录下来，并将m记录下来。（minProposalID=m)，返回最近一个接受的提案及其值（n，v1)
（3）如果n存在，且n >m， 则拒绝该提案，不返回。
此外acceptor作出承诺，拒绝接受小于m的提案 -
Acceptor阶段
经过一段时间后，Processor接受到Acceptor的回复。
2.1
如果回复数量大于一半机器，则第一阶段成功，proposer向acceptor发出accept请求<m, value>，value等于回复中最大ProposalId对应的value，如果所有的机器都没有回复值，则value由propossor进行指定
2.2
如果回复数量没有超过一半机器，则proposer重新生成proposalId，重新进行提案。
DX-20200308@2x.png
Zab协议
zab协议应用于zk系统，zk是分布式系统一致性的解决方案。而zk本身依赖zab协议进行一致性保证。
zab协议中，有个关键概念：zxid。zxid是一个64位的数字，高32位是当前leader周期的编号，也即用来当前是哪一个leader周期。低32位为事务Id，随着事务提交而递增。
zk机器被分为三种：leader，follower以及observer。其中leader负责处理写请求，follower负责处理读请求，并将写请求转发给leader，以及在故障恢复阶段参与选举，而observer与follower类似，但是没有选举权。
当leader失联时，整个集群进入leader选举阶段。在leader选举阶段，所有的机子将状态标记为looking。
1.每台follower机子都申请自己为leader，传播自身的zxid
2.收到其他机子的回复后，选择zxid最大机子，并在下一轮投票中，将票投给该机子。
- 在每轮投票中，票数超过一半的机器胜出，当选准leader。
当前阶段的leader其实还只是准leader，此后需要进行同步阶段，follower将最大的zxid同步给准leader，leader收到zxid后确定同步点，并同步给其他follower，补齐缺失的日志，最终达到整个集群状态一致。最后leader通知follower进入update状态，又开始接受请求。
