ZAB协议

1、定义

ZAB 协议全称：Zookeeper Atomic Broadcast（Zookeeper 原子广播协议）。

ZAB 协议是为分布式协调服务 Zookeeper 专门设计的一种支持 崩溃恢复 和 原子广播 协议，基于该协议，Zookeeper 实现了一种 主备模式 的系统架构来保持集群中各个副本之间数据一致性。

2、角色

• Leader
  一个ZooKeeper集群同一时间只会有一个实际工作的Leader，它会发起并维护与各Follwer及Observer间的心跳。所有的写操作必须要通过Leader完成再由Leader将写操作广播给其它服务器。

• Follower
  一个ZooKeeper集群可能同时存在多个Follower，它会响应Leader的心跳。Follower可直接处理并返回客户端的读请求，同时会将写请求转发给Leader处理，并且负责在Leader处理写请求时对请求进行投票。

• Observer
  角色与Follower类似，但是无投票权

3、leader选举规则

zxid最大表示服务器的日志是最全的，zxid相同情况下，myid最大

ZXID

ZXID 是 Zookeeper 集群中事务的唯一标识，保证全局有序。
ZXID 是一个 64 位整数, 高32位为周期号(epoch), 每个 Leader 被选举后都会增加 epoch 与上任 Leader 区分。低32位是 Leader 开始事务时分配的递增编号。
ZXID 中的 epoch 可以保证 Leader 崩溃重新选举后被丢弃的事务不会继续执行。

mid

每个ZooKeeper服务器，都需要在数据文件夹下创建一个名为myid的文件，该文件包含整个ZooKeeper集群唯一的ID（整数）。

例如，某ZooKeeper集群包含三台服务器，hostname分别为zoo1、zoo2和zoo3，其myid分别为1、2和3，则在配置文件中其ID与hostname必须一一对应，如下所示。在该配置文件中，server.后面的数据即为myid

4、zk服务器状态

• Leading: 当前节点为集群 Leader，负责协调事务
• Following: 当前节点为 Follower ，Follower与Leader处于数据同步阶段
• Looking: 系统刚启动时或者Leader崩溃， 集群没有正在运行的 Leader, 正处于选举过程
• Observing: 节点跟随 Leader 保存系统最新的状态提供读服务，但不参与选举和事务投票

5、投票

选票数据结构

每个服务器在进行领导选举时，会发送如下关键信息：

• logicClock 每个服务器会维护一个自增的整数，名为logicClock，它表示这是该服务器发起的第多少轮投票

• state 当前服务器的状态

• self_id 当前服务器的myid

• self_zxid 当前服务器上所保存的数据的最大zxid

• vote_id 被推举的服务器的myid

• vote_zxid 被推举的服务器上所保存的数据的最大zxid

投票流程

1. 自增选举轮次

ZooKeeper规定所有有效的投票都必须在同一轮次中。每个服务器在开始新一轮投票时，会先对自己维护的logicClock进行自增操作。

2. 初始化选票

每个服务器在广播自己的选票前，会将自己的投票箱清空。该投票箱记录了所收到的选票。
例：服务器2投票给服务器3，服务器3投票给服务器1，则服务器1的投票箱为(2, 3), (3, 1), (1, 1)。票箱中只会记录每一投票者的最后一票，如投票者更新自己的选票，则其它服务器收到该新选票后会在自己票箱中更新该服务器的选票。

3. 发送初始化选票

每个服务器最开始都是通过广播把票投给自己。

4. 接收外部投票

服务器会尝试从其它服务器获取投票，并记入自己的投票箱内。如果无法获取任何外部投票，则会确认自己是否与集群中其它服务器保持着有效连接。如果是，则再次发送自己的投票；如果否，则马上与之建立连接。

5. 判断选举轮次

收到外部投票后，首先会根据投票信息中所包含的logicClock来进行不同处理：

• 外部投票的logicClock大于自己的logicClock。
  说明该服务器的选举轮次落后于其它服务器的选举轮次，立即清空自己的投票箱并将自己的logicClock更新为收到的logicClock，然后再对比自己之前的投票与收到的投票以确定是否需要变更自己的投票，最终再次将自己的投票广播出去。

• 外部投票的logicClock小于自己的logicClock。当前服务器直接忽略该投票，继续处理下一个投票。

• 外部投票的logickClock与自己的相等。当时进行选票PK。

6. 选票PK

选票PK是基于(self_id, self_zxid)与(vote_id, vote_zxid)的对比：

• 外部投票的logicClock大于自己的logicClock，则将自己的logicClock及自己的选票的logicClock变更为收到的logicClock

• 若logicClock一致，则对比二者的vote_zxid，若外部投票的vote_zxid比较大，则将自己的票中的vote_zxid与vote_myid更新为收到的票中的vote_zxid与vote_myid并广播出去，另外将收到的票及自己更新后的票放入自己的票箱。如果票箱内已存在(self_myid,
  self_zxid)相同的选票，则直接覆盖

• 若二者vote_zxid一致，则比较二者的vote_myid，若外部投票的vote_myid比较大，则将自己的票中的vote_myid更新为收到的票中的vote_myid并广播出去，另外将收到的票及自己更新后的票放入自己的票箱

7. 统计选票

如果已经确定有过半服务器认可了自己的投票（可能是更新后的投票），则终止投票。否则继续接收其它服务器的投票。

8. 更新服务器状态

投票终止后，服务器开始更新自身状态。若过半的票投给了自己，则将自己的服务器状态更新为LEADING，否则将自己的状态更新为FOLLOWING。

6、工作模式

广播模式

当集群正常运行过程中，Leader 使用广播模式保证各 Follower 节点的一致性

1. Zookeeper 集群中每个节点都会存储系统数据的完整副本，可以独立处理读请求。
2. 当 Follower 收到写请求时会将其转发给 Leader, 或者 Leader直接收到写请求；

Leader 为每个写请求分配唯一的全局有序的事务ID(Zookeeper Transaction Id, ZXID)， 并转化为事务 Proposal 提案发送到队列中（Leader为每个 Follower 服务器分配一个单独的队列），然后将需要广播的 Proposal 依次放到队列中取，并且根据 FIFO 策略进行消息发送。

3. Follower 从队列中收到Proposal提案后写事务日志（本地磁盘）但不提交，成功后返回 ACK 告知 Leader 可以进行提交。
4. Leader 收到过半 Follower 的 ACK 响应后（包括Leader自己，Leader对自己默认有一个ACK）发出 commit 请求执行提交
5. Follower收到commit命令后，按队列的顺序（zxid）进行提交，只有上一个事物提交完成之后才能进行下个事物的提交
6. Leader 收到过半 Follower 对 commit 请求的 ACK 响应后便认为事务已完成。
7. 剩余的 Follower 则会放弃执行此次事务，进入数据同步阶段，与集群达成一致。Leader接收Follower发送过来的FOllOWERINFO（含有当前节点的Last的ZXID）然后往Follower发送NEWLEADER；

同步策略

Leader根据Follower发送过来的LastZXID根据数据更新策略向Follower发送更新指令。

• SNAP ：如果Follower数据太老，Leader将发送快照SNAP指令给Follower同步数据；

• DIFF ：Leader发送从Follower.lastZXID到Leader.lastZXID议案的DIFF指令给Follower同步数据；

• TRUNC ：当Follower.lastZXID比Leader.lastZXID大时，Leader发送从Leader.lastZXID到Follower.lastZXID的TRUNC指令让Follower丢弃该段数据；

恢复模式

集群启动或 Leader 崩溃时系统进入恢复模式，选举 Leader 并将集群中各节点的数据同步到最新状态

集群启动leader选举

1. 初始状态下每个服务器互相广播（logicClock,mid,zxid)，初始化自身选票池（服务器A, 服务器A所选票的服务器B）
2. 接收到其他服务器投票信息进行选票PK更新选票池。

• server1接收到（1,2,0)、（1,3,0) 选票PK后选票池由（1，1）更新为（1，3）更新的票，（3，3）收到的票

• server2接收到（1,1,0)、（1,3,0) 选票PK后选票池由（2，2）更新为（2，3），（3，3）

• server3接收到（1,1,0)、（1,2,0) 选票PK后选票池（3，3）不变更

根据上述选票，三个服务器一致认为此时server3应该是Leader。因此server1和server2都进入FOLLOWING状态，而server3进入LEADING状态。之后Leader发起并维护与Follower间的心跳。

follower恢复选举

1. Follower重启，或者发生网络分区后找不到Leader，会进入LOOKING状态并发起新的一轮投票。
2. 识别leader

• 服务器3收到服务器1的投票后，将自己的状态LEADING以及选票返回给服务器1。
• 服务器2收到服务器1的投票后，将自己的状态FOLLOWING及选票返回给服务器1。
  此时服务器1知道服务器3是Leader，并且通过服务器2与服务器3的选票可以确定服务器3确实得到了超过半数的选票。
  因此服务器1进入FOLLOWING状态。

Leader重启选举

1. Leader（服务器3）宕机后，Follower（服务器1和2）发现Leader不工作了， 因此进入LOOKING状态并发起新的一轮投票，并且都将票投给自己。
2. 广播更新选票，服务器1和2根据外部投票确定是否要更新自身的选票。这里有两种情况：

• 服务器1和2的zxid相同。例如在服务器3宕机前服务器1与2完全与之同步。此时选票的更新主要取决于myid的大小

• 服务器1和2的zxid不同。在旧Leader宕机之前，其所主导的写操作，只需过半服务器确认即可，而不需所有服务器确认。换句话说，服务器1和2可能一个与旧Leader同步（即zxid与之相同）另一个不同步（即zxid比之小）。此时选票的更新主要取决于谁的zxid较大

如图所示：
服务器1的zxid为9，而服务器2的zxid为8，因此服务器2将自身选票更新为（2, 1, 9）3、
经过上一步选票更新后，服务器1与服务器2均将选票投给服务器1，因此服务器2成为Follower，
而服务器1成为新的Leader并维护与服务器2的心跳。
旧的Leader恢复后，进入LOOKING状态并发起新一轮领导选举，并将选票投给自己。
此时服务器1会将自己的LEADING状态及选票（3, 3, 9）返回给服务器3，
而服务器2将自己的FOLLOWING状态及选票（3, 1, 11）返回给服务器3。
服务器3了解到Leader为服务器1，且根据选票了解到服务器1确实得到过半服务器的选票，因此自己进入FOLLOWING状态。

leader commit后宕机，follower部分commit

c1、c2 表示对提案P1、P2 对应的commit

1. A提交了C1、C2，P3未commit后宕机
2. FastLeaderElection算法选出B作为新的Leader，C、D、E、F、G 会主动将自己最大的zxid发送给B
3. B会将Follower的zxid与自身zxid间的所有被Commit过的消息同步给Follower，P3由于未被A Commit，同时幸存的所有服务器中P3未存在于大多数据服务器中，因此它不会被同步到其它Follower，已存在P3的需发送trunc通知follower丢弃该数据
4. 同步完数据后，B会向Followers发送NEWLEADER命令并等待大多数服务器的ACK（包含自身，无需等待全部ack），然后向所有服务器广播UPTODATE命令。收到该命令后的服务器即可对外提供服务。