一致性算法初探

最近刚看了一篇“程序员之家”订阅号中的一篇文章——程序员是否必须会算法，说的很不错，其实我一直对算法工作都情有独钟，也曾下决心要致力于机器学习的行业，但由于某个不知是谁的操蛋HR的原因，暂时从事了普通的开发工作，幸好干的还算开心。

先不说做专业算法的工程师们，其实广大的研发都应该对算法有所理解和掌握，起码可以通过自己的逻辑，想法，来设计方案，解决遇到的问题。前段时间有所懈怠，也是需求太多的原因，没有经常更新，但看着与日增加的关注人数，倍感惭愧！小弟何德何能啊。所以，我觉得还是应该把日常所得坚持记录一下，几天一悟也好，一周一悟也罢，对我好处不言而喻，万一哪个点让您灵光突显一下呢，那可就阿弥陀佛了！

如今业内常用架构：高并发 -> 异步处理 -> 主/备容灾

最常用的主备措施是使用zookeeper。 然而，zk怎样保证高可用、一致性呢，这就涉及到了其底层使用的一致性协议ZAB（来源于paxos）。曾有人说，paxos算法，是迄今为止唯一正确的一致性算法，其他的算法都是由paxos改进和演变来的。zookeeper也一样，其一致性协议ZAB，虽然和paxos不同，但也有千丝万缕的联系。

概括的说一下，

在协议实现上：ZAB是三阶段的，比paxos是两阶段的多出一个同步阶段，以确保fallower已经对当前周期之前的决议进行提交；

在涉及目的上：ZAB主要用于构建一个高可用的分布式数据主备系统，paxos用于构建一个分布式的一致性状态机系统。今天，就来说说zookeeper中的ZAB。

先来说一下基本paxos算法，他是一种依赖消息传递的一致性算法，包括两个阶段：

1.决议的提出。

当提议者希望提出方案v1，则首先向其他节点(接受者)发送带有序列号sn1的请求。当接受者接受到sn1的提案请求时，检查自己上次回复过的请求的序列号sn0 ,当sn1<sn0时，说明本次接受的提案已过时，直接忽略

如果sn1大，那么检查上次批准过的提议<sn0,v0>,并且回复给该提议者这个决议，如果以前没有批准过其他的提议，那么就直接回复ok

2.决议的批准。

2.1提议者检查收到的回复：

如果多于1半的回复都是ok，那么提议者发出accept请求，内容为提案<sn1,v1>

如果多半的回复中，有<sn2,v2> <sn3,v3>等等，那么就在这些回复中，找到大于一半的那个<snx,vx>，发出accept请求

如果回复不足一半，那么把序列号+1，继续提案。

2.2然后继续检查收到的回复

回复大于一半，则确认v1被接受

回复不足一半，则sn+1 继续提案

paxos算法有可能出现竞争，发生活锁，比如当有三个提案者一起进行提案时，将很难有一个提案者可以有大于一半节点的回复，那么集群就会一直处于第一个阶段

ZAB(fast paxos)算法 是对基本paxos的一个改进。

ZK的两个特点：消息传递(leader选举的新事务广播)和崩溃恢复(leader出问题之后选举leader，恢复系统)。它定义了一个唯一的leader去提出议案，那么按我的理解，问题就变成了对唯一leader的选举和保证。那么,怎样选出leader呢，leader挂了怎么办呢，什么时候发起选举呢，选举中有后进的机器要发起选举怎么办呢，节点挂了又重启了怎么办呢。

何时发起选举？

当节点刚启动时，或者当节点发现leader挂了时发起选举

leader挂了怎么办？

发起选举，进入崩溃恢复模式

节点挂了又重启？

发起投票，但如果发现当前系统中存在leader，那么就进入数据恢复模式，主动连接leader服务器、同步leader信息，加入到消息广播中。

消息广播用来完成leader和fallower之间的交互，采用的是具有先进先出的TCP协议进行网络通信，所以可以很好的确保消息、提案的顺序性。当某一fallower接收到客户端的事务请求时，必须先提交给leader，然后由leader发起广播。

崩溃恢复，在leader失去半数支持者的情况下，重新确定新的leader，确保系统中只有一个”决策者“，并且，确保已经在leader上提交的事务被所有服务器都提交，并确保丢弃只在leader上提出的事务。比如，

leader有行为：p1-->p2-->commit 1-->p3-->comit 2。

leader提出了p1,p2,commit p1,自己提出p3,commit p2,

此时的ZAB，需要让另外N个fallower 也能够正常commit 2。

但是p3是leader自己提出的，又没有commit，则保证另外的fallower丢弃p3,达到数据一致性。

leader选举的过程别人比我说的好多了，就盗个图来说明一下（以防版权问题特此说明。以下选举实例来源原作者：雷明）：

节点1、2、3启动后，都进入looking状态，开始leader选举。每个节点推荐的leader都是自己；逻辑时钟logicalclock值都为1；proposedZxid值都为1；proposedEpoch波次值都为1；投票列表为每个节点投自己的一票（1->1,2->2,3->3）。节点1首先向2、3发送自己的投票消息

节点2、3收到节点1的投票消息，首先查看1的状态，发现1处于looking状态。接下来，判断1发来的electionEpoch和本地逻辑时钟logicalclock的大小，发现两者相等（都为1）。接着判断leader、zxid、peerEpoch和本地proposedLeader、proposedZxid、proposedEpoch的大小，节点2发现节点1推荐的leader的id比自己小（1<2），节点3也发现节点1推荐的leader的id比自己的小（1<3），因此不用更新自己的投票。接下来，节点2、3把节点1的投票放入自己的投票列表中，这样，节点2收到的投票的列表为：

1->1

2->2

节点3的为：

1->1

3->3

节点2、3再判断此次投票是否可以结束，发现不能结束。

节点2向节点1、3发送自己的投票信息，节点3由于发送线程的故障原因，投票信息一直没有出去

在2发出的投票信息中，选择的leader是它自己。

节点1、3收到节点2的投票消息。节点1比较自己的logcalclock和节点2发来的electionEpoch的大小，二者相等，接下来比较leader、zxid、peerEpoch和本地proposedLeader、proposedZxid、proposedEpoch的大小，发现节点2推荐的leader的id（2）比自己的proposedLeader（1）大，于是更新自己的选票，将proposedLeader改为2。然后，节点1将2的选票（2->2）放入自己收到的投票箱中，接着判断投票是否可以结束，由于节点2被超过半数的节点选择（1、2），因此选举可以结束，由于自己不是leader，节点1将自己的状态改为following。

节点3比较自己的logcalclock和节点2发来的electionEpoch的大小，二者相等，接下来比较leader、zxid、peerEpoch和本地proposedLeader、proposedZxid、proposedEpoch的大小，发现节点2推荐的leader的id（2）比自己的proposedLeader（3）小，不用更新自己的选票。然后，节点3将2的选票（2->2）放入自己收到的投票箱中，接着判断投票是否可以结束，由于没有节点获得超过半数的选票，因此选举继续。

此时，节点1选的leader已经变为2，而且节点1的状态已经变成following。

节点2在收到节点1的选票信息后，判断节点1的状态，发现为following，这表明，节点1已经认为leader选出来了，并且是2。节点2首先更新自己的收票箱，将1的投票改为2，接着，判断选举是否结束，发现确实可以结束，节点2就更新自己的状态，由于发现自己是被半数以上人推荐的leader，因此把自己的状态改为leading。

同样，节点3在收到节点1的投票信息后，判断节点1的状态，发现为following，这表明，节点1已经认为leader选出来了，并且是2。节点3首先更新自己的收票箱，将1的投票改为2，接着，判断选举是否结束，发现确实可以结束，节点3就更新自己的状态，由于发现自己不是被半数以上人推荐的leader，因此把自己的状态改为following。