Zookeeper纸上谈兵——ZAB协议

罪恶啊罪恶，一时惰性，好久没有写了。国庆也浪费了好几天了，赶紧抓住尾巴学习整理啊。

一、ZAB协议简介

之前介绍的Paxos 算法是基本算法，这就意味着它在实际的应用过程中存在着诸多的不便，所以有很多基于Paxos算法的优化算法，ZAB协议就是其中的一种，其他还有Fast Paxos等，对了，Zookeeper的Leader选举算法，FastLeaderElection就是Fast Paxos的工程应用。

ZAB的全称是Zookeeper Atomic Broadcast，翻译过来就是zk原子广播协议，可见ZAB是专为Zookeeper设计的，它是用于奔溃恢复（例如leader选举）的。在Zookeeper中，主要就是依赖ZAB实现的分布式数据一致性。

Zookeeper使用一个单一的主进程接受并处理客户端的事务请求（如写请求），当服务器数据状态发生变更时，leader通过ZAB协议以事务提案Proposal的方式广播到所有的副本进程上，ZAB协议能够为每一个事务分配一个全局唯一递增的编号xid。

对于Zookeeper集群中的节点，当它收到一个客户端的请求时，如果是读请求，则直接返回节点中的数据，如果是写请求且当前节点不是Leader节点时，它会将这个请求转发给Leader，之后Leader会以提案的方式广播这个写请求，如果有超过半数的节点同意，那么这个写请求就会被提交，然后Leader会再次广播给所有的订阅者，也就是Learner，让他们同步操作数据。

二、相关概念

2.1 三个角色

在Paxos中有三个角色，ZAB中也有相应的三个角色。

• Leader：在zk集群中，leader和follower是最常见的了，leader作为领导者，处理写请求，它是十分名著的，收到写请求后会先根据请求发出提议，如果自己的follower超过半数同意它才会向外表示同意。他还可以进行投票、发起决议，更新系统状态等。
• Follower：接收客户端的读请求时，直接处理，将结果返回客户端；接收客户端的写请求时，将写请求转给leader；在Leader的选举中可以进行投票。
• Observer：观察者，就是站一边看的墙头草，没有投票权，主要是为了协助Follower处理读请求。当集群读请求很多，需要增加处理读请求的服务器时，如增加的服务器都是Follower，这会使得写操作的效率变得很低，因为Leader发出的写操作请求需要超过半数的通过票。过多的Follower会增加Leader与Follower的通信成本和压力，降低写操作效率，同时也会延长Leader的选举时长，降低整个集群的可用性，因此Observer角色就出现了，保持法定人数的不变，集群决策效率就不容易受影响。

2.2 三种模式

ZAB协议对于zkServer（Zookeeper 服务器）的状态描述有三种模式，分别为：恢复模式、同步模式、广播模式。

• 恢复模式。服务重启过程中或Leader崩溃后会进入到恢复模式，使zk恢复到正常的服务状态。
• 同步模式。在所有的zkServer都启动完毕或者Leader奔溃重选完成时，就进入同步模式，各个Follower需要马上将Leader中的数据同步到自己的主机中，当大多数的zkServer完成了同步后，恢复模式也就结束了。所以，同步模式是包含在恢复模式之中的。
• 广播模式。当Leader的提议被大多数zkServer通过后，Leader会修改自身的数据，并将修改后的数据广播给其他Follower。

2.3 zxid

之前我们说Paxos中要有一个唯一递增的提案编号，这个zxid就是来做这个事情的。它是64位长度的Long类型的数据，其中高32位表示纪元epoch，低32位表示事务标识xid。也就是zxid由epoch和xid两部分组成。

每一个Leader都会有一个不同的epoch值，用来表示一个时期、时代。每一次新的选举开启时都会有一个新的epoch生成，新的Leader产生，则会更新所有zkServer中的zxid中的epoch，也就是高32位。

xid是事务id，每一个写操作都是一个事务，有一个xid，这是一个依次递增的流水号。每一个写操作都需要一个Leader来发起一个提案，由所有的Follower来表决是否通过写操作，而每一个提案都拥有一个zxid。

2.4 消息广播算法

如果集群中已经有了超过半数的Follower和Leader完成了状态同步，那么整个zk集群就可进入到消息广播模式了。

前面我们已经说过了只有Leader可以处理事务，其他类型节点收到事务会转发给Leader，Leader会为其生成对应的事务提案Proposal，并将其发给集群中其余所有的主机，然后再分别收集它们的选票，在选票过半后进行事务提交，具体过程如下：

• Leader接收到消息请求后，为请求赋予一个zxid，通过zxid的大小比较，即可实现事务的有序性管理。
• 为了保证Leader想Follower发送提案的有序，Leader会为每一个Follower创建一个FIFO队列，并将提案的副本写入到各个队列，之后再通过这些队列将提案发送给各个Follower。
• 接下来，当Follower接收到提案后，会将提案的zxid与本地记录的事务日志中的最大的zxid比较，若前者大，则将其当前提案记录到本地事务日志中，并给Leader返回一个ACK。
• 当Leader接受到过半 的ACK后，会向之前回复过Leader的Follower（已经保存了提案消息）发送COMMIT信息，批准各个Follower在本地执行该消息。对于之前未回复过Leader的Follower，Leader会将这些Follower对应的队列中的提案消息一并发给它们，当它们接受到COMMIT消息后就会执行该消息。

2.5 恢复模式下的两个原则

当集群处在启动过程中或者Leader与半数以上的主机失联后，集群就会进入到恢复模式。对于要恢复的数据状态需要遵循以下两个原则。

(1) 已经被处理过的消息不能够丢弃。

前面说Leader会给Follower发送COMMIT信息，但是如果在非全部Follower收到COMMIT信息之前，Leader就挂了，就会出现部分Follower已经执行了COMMIT信息而其他Follower还没有收到信息。当新的Leader被选出后，集群经过了恢复模式，需要保证所有的Server上都要执行那些已经被部分Server执行了的事务。所以不能丢弃已经被处理的消息。ZAB的恢复模式使用了以下策略：

• 选举拥有最大zxid，即Proposal的id最大的节点（保存了所有已经被COMMIT的proposal状态）作为新的Leader。
• 新的Leader将自身有而并非所有Follower都有的Proposal发送给Follower，再将这些Proposal的COMMIT命令发送给Follower，以保证所有的Follower都保存并执行了所有的Proposal。

(2) 被丢弃的消息不能够再现。

当Leader接收到了事务请求并生成了Proposal，但还没有向Follower发送时Leader就挂了，这样，Follower从来没有接收到过这个请求，当通过恢复模式产生了新的Leader后，这个事务会被跳过。在整个集群尚未进入正常服务状态时，之前挂了的Leader重启成为了一个Follower，由于保存了被跳过的Proposal，这时为了与系统状态保持一致，需要把这个Proposal删除。

ZAB通过zxid来实现这一点，每一次选举epoch的值都会加一；每产生一个事务，xid的值都会加一。这样，旧的Leader挂了后重启，它不会被选举为新的Leader，因为此时它的xid肯定小于当前新的epoch，当它接入新的Leader后，新的Leader会让它把所有旧的epoch号的未COMMIT的Proposal清除。

三、Leader选举算法

当集群处在启动过程中或者Leader与超过半数的主机断联后，集群就会进入恢复模式，其中最重要的就是Leader选举。

集群启动过程中和Leader断联两者的Leader选举基本相同，有一点小小的区别。

3.1 启动过程中的Leader选举

要选Leader，当然是针对两台以及以上机器数所言的，这里以三台机器为例。

在集群的初始化阶段，第一台服务器S1启动时，会给自己投票并发布自己的投票结果，投票包含所推举的服务器的myid和zxid，使用（myid, zxid）来表示，此时S1的投票是（1,0），由于其他服务器还没有启动，所以它收不到反馈，状态就会一直是LOOKING，即属于非服务状态。

当第二台服务器S2启动以后，两台机器可以互相通信，双方都试图找到Leader，选举过程如下：

• 双方都投票，S1为（1, 0），S2为（2, 0）。然后分别将自己的投票发到集群中的其他机器（目前就是彼此）。
• 各个服务器接收来自其他服务器的投票，首先判断投票的有效性，例如检查是否来自本轮投票、是否来自LOOKING状态的服务器.

• 针对每一个投票，将她与自己的投票进行比较，规则如下：

  优先比较zxid，zxid比较大的服务器优先作为Leader。

  如果zxid相同，则比较myid，myid较大的服务器作为Leader。

  所以显然S1会将自己的投票改为（2, 0）。

• 统计投票。每次投票后，服务器都会统计投票信息，判断是否有过半的机器接受到相同的投票信息。对于S1和S2而言，显然两者都接受了（2, 0），此时认为已经选出了新的Leader，也就是S2。
• 改变服务器状态。一旦选定了Leader，服务器就会更新自己的 状态，如果是Follower就变为FOLLOWING，如果是Leader，就变更为LEADING。
• 添加主机。选出S2以后，S3启动加入进来，它想发起新一轮选举，但由于集群中的其他服务器都不是LOOKING的状态，而是正常服务，所以S3只能以Follower的身份加入集群。

3.2 断联过程中的Leader选举

假如在当前三台机器正常运行的过程中，作为Leader的S2突然挂了，这时候其他的非Observer服务器（就是Follower）会立马更新自己的状态未LOOKING，开始新一轮的选举：

• 每个服务器投票，依然首先投自己，不过运行期间每个Server上的zxid可能不同，假定S1的zxid为11，S3的zxid为33，那么双方产生的投票分别为（1, 11）和（3, 33），然后将投票发出去。

  -后续过程与启动过程相同。所以S3会成为新的Leader。然后各个服务器更新自己的状态，S1变为FOLLOWING，S3变为LEADING。

3.3 Leader选举后的数据同步

选举完成后，需要进行集群的数据同步。Leader会为每一个Follower准备一个队列，并将那些没有被Follower同步的事务以Proposal形式逐条发给Follower，并跟上一个COMMIT消息，表示Follower需要立即执行，不必表决。当Follower将所有尚未同步的事务都从Leader同步过来并成功执行后，会给Leader发一个ACK，Leader收到后将该Follower加入到真正可用的Follower列表。

好了，至此，ZAB协议总算是大致码完了。