分布式一致性算法04 ZAB协议
一、基本概念
ZAB（Zookeeper Atomic Broadcast）协议是为Apache Zookeeper框架设计的一致性协议。
与Paxos仅能保证事务的一致性不同，ZAB可以同时保证事务的顺序性和一致性。
二、ZAB算法涉及三种角色和四种状态
三种角色：
1、领导者（Leader）： 在同一时间，集群只会有一个领导者。所有的写请求都必须在领导者节点执行。
2、跟随者（Follower）：集群可以有多个跟随者，它们会响应领导者的心跳，并参与领导者选举和提案提交的投票。跟随者可以直接处理来自客户端的读请求，但会将写请求转发给领导者处理。
3、观察者（Observer）：与跟随者类似，但不参与竞选和投票权。
节点有四种状态：
LOOKING：选举状态，该状态下的节点认为当前集群中没有领导者，会发起领导者选举。
LEADING ：领导者状态，意味着当前节点是领导者。
FOLLOWING ：跟随者状态，意味着当前节点是跟随者。
OBSERVING： 观察者状态，意味着当前节点是观察者。
三、关键概念
1、Epoch（纪元）
定义：Epoch是ZXID的高32位，表示领导者的任期编号。每次新的领导者被选举出来时，Epoch都会增加。
作用：
标识领导者的任期。不同的Epoch代表不同的领导者任期，确保了领导者的唯一性。
当发生分区或领导者故障时，新的领导者会具有更高的Epoch，从而确保了新的领导者具有最新的状态。
2、ZXID（事务ID）
定义：ZXID是一个64位的数字，用于唯一标识Zookeeper中的每个事务。
组成：ZXID的高32位表示Epoch，低32位表示事务计数器（XID）。
作用：
确保事务的全局顺序性。每个事务都有一个唯一的ZXID，保证了事务在所有服务器上的处理顺序一致。
通过比较ZXID，服务器可以确定事务的先后顺序，以及是否已经处理过某个事务。
四、ZAB选举流程
1、初始化：
集群中的每个服务器（Server）启动时，都处于“Looking”状态，即寻找Leader状态。
2、投票：
每个处于“Looking”状态的服务器都会发送投票（Vote）给其他服务器，尝试将自己选举为Leader。
投票格式大概为：
（新Leader节点的ID, 新Epoch编号, 当前最新的ZXID，投票节点的ID）
3、收集选票：
收到各节点的选票后，各节点会根据以下规则，判定如何投票：
优先检查任期编号Epoch，任期编号大的节点作为领导者；
如果任期编号Epoch相同，比较事务标识符ZXID的最大值，值大的节点作为领导者；
如果事务标识符的最大值相同，比较节点ID，节点ID大的节点作为领导者；
通过这样的规则，首先保证了数据最新的节点，获取更高的票数。
4、确定Leader
如果没有任何节点获取了过半选票，则要开始下一轮选举，回到步骤2，但此时不再会投票给自己，而是会投票给上一轮最合适的节点。
如果某个服务器获得了超过半数的投票，它就认为自己被选举为新的Leader。
5、同步：
新Leader会与集群中的Follower进行数据同步，确保所有Follower的数据与Leader一致。
数据同步完成，Leader就可以接收客户端的事务请求了。
五、ZAB选举示例
假设我们有一个Zookeeper集群，包含5个节点（P1~P5），所有节点都处于“Looking”状态。
Epoch=2；XID=5；ZXID=（2，5）
投票信息格式为：
（新Leader的ID, 新Leader的Epoch编号, 新Leader的最新的ZXID，选举轮次，投票节点的ID）
1、初始化
P1~P5开始寻找Leader，并发送投票请求，并投票给自己。
2、投票
P1：（新Leader=P1, 新Leader的Epoch=2, 新Leader的最新的ZXID=（2，5），选举轮次=1，投票节点=P1）
P2：（新Leader=P2, 新Leader的Epoch=2, 新Leader的最新的ZXID=（2，5），选举轮次=1，投票节点=P2）
P3：（新Leader=P3, 新Leader的Epoch=2, 新Leader的最新的ZXID=（2，3），选举轮次=1，投票节点=P3）
P4：（新Leader=P4, 新Leader的Epoch=2, 新Leader的最新的ZXID=（2，2），选举轮次=1，投票节点=P4）
P5：（新Leader=P5, 新Leader的Epoch=1, 新Leader的最新的ZXID=（1，1），选举轮次=1，投票节点=P5）
3、收集选票
对于同一轮的选票，节点自行对比判定选举结果：
P1：新Leader=P2，因为P2节点ID更大
P2：新Leader=P2，不变
P3：新Leader=P2，因为P2 ZXID更大
P4：新Leader=P2，因为P2 ZXID更大
P5：新Leader=P2，因为P2 Epoch更大
但如果一个节点收到了更小选举轮次（logicalclock）的投票，该投票会被忽略。
4、再次投票，这样P2会获得全部5票
5、确定Leader
P2认为被选举为Leader。其余节点，会主动与P2交换最大的ZXID，如果P2的更新则承认P2的领导地位，否则重新发起选举。
当过半节点承认P2的领导地位时，P2正式成为Leader。
同时P2会将Epoch+1，此时：
Epoch=3；ZXID=（3，0）
6、同步
P2根据之前各节点反馈的最大ZXID，开始与其他节点进行数据同步，强制要求所有Follower的数据与自己的数据一致。
数据同步完成后，P2告知全部Follower数据同步完毕，P2开始接收提案，各节点开始同步P2的提案。
六、ZAB同步算法的工作流程
延续上面的例子，Zookeeper集群，包含5个节点（P1~P5），P2是Leader
Epoch=3；XID=0；ZXID=（3，0）
1、客户端请求：
客户端向P3发送写请求，P3会将写请求转交给Leader P2。
2、事务提案：
Leader接收到请求后，会生成一个事务提案Proposal，分配一个全局唯一的ZXID，并进行持久化。
3、广播提案：
Leader将事务提案发送给所有Follower。
4、Follower投票：
Follower接收到提案后，会将Proposal写入本地日志，并根据自身的数据状态进行投票（必须按ZXID顺序提交），并将投票结果发送回Leader。
5、Leader决策
当Leader收到超过半数Follower的同意投票后，提交事务。同时将通知所有Follower更新状态。
如果提案被拒绝，事务将被回滚。
6、客户端响应
P3收到Leader事务提交的消息，P3会向客户端返回操作结果，客户端根据结果进行相应的处理。
七、ZAB协议的关键点：
1、顺序一致性：ZAB协议通过全局唯一的ZXID，保证了客户端请求的顺序性。
2、可靠性：即使在部分节点宕机的情况下（投票数可以过半），ZAB协议也能够保证系统的可靠性和数据的一致性。
3、防止分区：当新Leader选举成功后，如果旧Leader恢复过来，由于新Leader有更高的Epoch，旧Leader的请求不再会被接受；一个节点，如果与Leader失联，则是无法处理读写请求的；
可以看出，ZAB算法与RAFT算法整体的考虑方向是一致的，就是先选择一个Leader，通过Leader控制事务提交的顺序。
但就具体的实现而言，RAFT的实现更简单可以实现强一致性，ZAB的实现更复杂一些可以实现最终一致性。