Zookeeper ZAB协议
words: 3.6k views: time: 12minZookeeper Atomic Broadcast protocol是为分布式协调服务Zookeeper专门设计的一种支持崩溃恢复的原子广播协议。基于该协议，Zookeeper实现了一种主备模式的系统架构来保持集群中各个副本的数据一致性。
最早起源于雅虎内部的一个研究小组，当时希望开发一个通用的分布式协调框架，来统一解决内部系统的分布式协调问题，由于很多项目都习惯使用动物名字来命名，所以最后项目取名为动物园管理员ZooKeeper
ZAB协议
ZAB协议可以简单概括为两个阶段：恢复阶段、广播阶段
恢复阶段不能对外提供服务，恢复的目的是要选举出一个Leader节点（zxid最大的节点），选举完成后再给其它节点同步缺失的事务数据；
广播阶段可以对外提供服务，其中所有的写请求都转发给Leader，其通过两阶段提交（2PC）的方式广播提案并收集ACK，当多数节点确认后，Leader提交事务并返回客户端。
对照CAP理论，ZooKeeper可以理解为CP系统，支持强一致性(C)，和分区容错(P)，但可用性(A)在网络分区场景下会被牺牲
ZAB节点状态
- Leading：当前节点是 Leader，负责协调事务
- Following：当前节点是跟随者，服从 Leader 节点的命令
- Election/Looking：节点处于选举状态，正在寻找 Leader
- Observing：Zookeeper引入Observer之后加入的，Observer不参与选举，是只读节点，跟Zab协议没有关系
ZAB四个阶段
- 选举阶段 Leader Election: 主要是节点之间进行信息同步，选择出一个leader
选票信息包括vote(zxid,id,state,round)；id是myid文件中节点的编号；state表示节点的状态(leader,follower,election)；round表示当前节点是第几轮投票；zxid表示最新一次已提交事务的编号，zxid是一个64位的数字，低32位用来计数事务请求，高32位则表示leader选择周期，也称为Epoch。
节点一开始都处于选举阶段，当一个节点得到超过半数节点的投票，它就可以成为准Leader。如图，T1时刻开始选举，三个节点都给自己投一票，再广播给其他两个节点。T2时刻，各自收到其它节点的选票，比较得出node1最大，于是节点2和节点3更新选票并重新广播。最终在T3时刻完成选举，各个节点都认为节点1是准Leader。
过程中可能会存在一些问题，比如T1时刻，node1发给node2的投票出现延迟，在node2完成投票决策之后才到达。这样在T1时候，node2只收到自己和node3的投票，比较后会选择node3作为leader（zxid相等，比较id），而node3会选择node1进行投票，因此会存在冲突。
实际上会维护一个超时时间Finalize Wait Time，当某一个节点收到投票信息后发送了一次投票结果，但是在这段时间内如果还收到其他的投票信息且需要变更投票结果，那么这个节点会重新发送一个新的投票进行广播。这样如果在FWT的时间内，node2收到了延迟的node1投票信息，发现之前的投票结果需要变更，那么会重新广播。当然FWT也不能完全解决问题，它的数值设置也只是概率性的降低delay message导致的问题。在后续Dicovery阶段进行leader版本信息比较时，如果发现leader的版本号比follower版本号更低时会触发重新选举。
- 发现阶段 Discovery: Leader获取最新的history信息（这里的history信息是整个集群最新的事务版本zxid以及其对应的数据）
- Follower节点知道准Leader节点之后，会发送一个FOLLOWERINFO的信息携带自己的f.acceptedEpoch内容
- 准leader节点收到超过半数的FOLLOWERINFO之后，会从中选择一个最大的，并在最大的Epoch基础上+1，即max{f.acceptedEpoch} + 1
- 准Leader将准备好的NEWEPOCH发送到follower, 表示自己的年号已经更新，等待quorum的成员回复ACK
- follower收到NEWEPOCH之后和自己本地epoch进行比对：
如果leader发送过来的epoch > acceptedEpoch,更新自己的acceptedEpoch为新的epoch,并回复一个ACKEPOCH消息，这个消息中携带上个currentEpoch, history和lastZxid(history最近提交的proposal的zxid)
如果leader发送过来的epoch <= acceptedEpoch ，则回退到阶段0，重新进行leader选举（集群中存在节点异常）
- Leader收到所有quorum中follower的ACKEPOCH, 从所有的消息中找出currentEpoch最大的或者lastZxid最大的follower,然后把该follower的history作为自己的history（pull history）。如果本地的currentEpoch或者lastZxid最大，那直接用本地的history即可
- 同步阶段 Synchronization: Leader将获取到的最新的数据同步到其他的从节点，并补全老数据，删除新数据
Leader这个阶段已经有了最新的history数据
- Leader向所有的follower发送NEWLEADER信息，其中包括leader自己最新的epoch和最新的history数据
- follower收到leader的消息之后判断当前轮次自己的acceptedEpoch和leader发送过来的epoch是否一样（discovery阶段已经对follower自己的acceptedEpoch进行了更新）
follower的acceptedEpoch和新epoch相同，表示自己已经跟上了新的epoch, 那么
1.更新自己的currentEpoch为新的epoch，表示进入新的朝代了
2.按照zxid的大小逐一进行本地proposed，此时这些transaction还未commit
3.更新自己的history为最新的history
4.返回一个ACKNEWLEADER 给leader, 表示这个follower已经完成数据同步follower收到的epoch和本地的acceptedEpoch不同，那么回退到阶段0，重新选主
- Leader收到follower节点的ACKNEWLEADER消息之后，对proposal的数据进行提交commit，所有的follower节点也会收到commit请求（落盘）
- follower节点收到leader的COMMIT请求，会对自己本地已经proposed但还未commit的事务，按照zxid进行从小到大的排序，优先commit zxid较小的节点
- Leader和Follower都完成同步之后进入第四阶段
- 广播阶段 BroadCast: 到了这个阶段，集群就可以对外提供读写服务了，正常状态下集群都处于该阶段
到了这个阶段，整个集群已经能够对外提供读写服务
- Leader收到一个写请求，会生成一个Proposal: zxid = lastZxid + 1，对quorum中的follower节点发起propose请求，并携带生成的Proposal
- follower节点收到propose的proposal，将其加入到history队列，并向leader回复ACK，表示已经收到propsal
- leader收到超过半数节点的ACK之后，认为可以进行commit，则向quorum发送COMMIT请求
- follower收到propose的commit之后开始进行提交
为了满足zxid的全局一致性，这里会检查follower本地是否有未提交的proposal，保证比当前zxid小的propose先提交，当所有小于zxid的propose都完成commit之后再提交当前的zxid
- BroadCast阶段也能够接受新的Follower或者Observer的加入
1.新加入的节点会给Leader发送一个FOLLOWERINFO信息
2.Leader收到后会回复给他一个NEWEPOCH和NEWLEADER, 告诉这个节点集群最新的epoch和history数据
3.新节点收到NEWLEADER后，如果正常逻辑处理完成后（将history中的数据并发propose），回一个ACKNEWLEADER给Leader
4.Leader收到ACK回复之后告诉他可以进行本地proposal的提交了,会发送一个COMMIT请求
5.新节点收到这个请求，对本地完成proposed的数据按照zxid从小到达进行commit（落盘）
6.新节点完成commit之后，leader会将新的节点加入到自己的quorum列表中
对于ZAB协议各个阶段的细节，在zookeeper的实际实现中，会进行一些优化。比如zookeeper将leader election和discovery变更为FLE(Fast Leader Election)阶段，在完成Leader选举之后，leader就已经拥有了最新的history数据，这样能省去一些rpc和数据交互。
另外，不论是leader还是follower，节点在进行propose的过程都是可以并发进行的。对于leader来说，一个proposal的发起不会等待上一个commit完成之后才会发起，当前proposal和上一个proposal是可以并行处理，保证了zookeeper的更新接口可以提供wait-free的能力。但是，commit时需要保证本地比当前zxid更小的事务优先提交，以便保证顺序一致性
Zookeeper实现
DataTree
zk对外暴露的数据模型是一个基于路径的树形结构，类似于文件系统的目录结构，内部实现了一个内存数据库DataTree，每个路径节点都是一个 ZNode。但DataTree本质上是一个巨大的哈希表，虽然单次查询非常快，但在创建、删除ZNode时，需要多次查询哈希表，会增加写操作延迟，降低写入性能。
SnapLog
SnapLog是zk的持久化存储模块，用于将Zookeeper的内存数据备份到磁盘上。SnapLog 由两部分组成：事务日志（Transaction Log）和快照文件（Snapshot File）。事务日志用于记录所有的数据变更操作，快照文件会定期全量备份DataTree中的所有数据。当Server启动时，会先加载最近日期的快照文件，然后逐个加载事务日志文件，最终恢复到最新的状态。
客户端的每次写入操作都会同步到磁盘，这会增加写操作的延迟，因此事务日志的写入性能基本决定Zookeeper Server对请求的响应速度，为了增加写入性能，Zookeeper采用磁盘预分配的策略，在事务日志文件创建之初就向操作系统预分配一个很大的磁盘块，默认是64M，而一旦已分配的文件剩余空间不足4KB时，那么将会再次进行预分配。
但Zookeeper的所有数据都存储在内存中，包括DataNode、Key Path、Watcher等，因此内存上限就是Zookeeper的数据存储上限，只能存储GB级别的数；另外数据量增加也会导致GC压力，降低哈希表查询的性能。
Session
Zookeeper的Session是一个全局的概念，每个客户端首先会与服务器建立一个TCP连接，从连接建立开始，客户端会话的生命周期也开始了，并为该Session分配一个全局唯一的SessionId，标识客户端的身份。通过这个连接，客户端能够通过心跳检测与服务器保持有效的会话，也能够向Zookeeper发送请求和接受响应，还能够通过该连接接收来自服务器的Watch事件通知。
全局Session会带来一些问题，每个客户端实例同一时刻只能有一个Session，这意味着如果一个客户端实例同时创建了多个临时节点，那么这些临时节点的生命周期是一致的。如果我们想要显式地删除某个临时节点，那么我们只能通过delete操作来删除，而不能通过关闭Session来让ZNode失效。
Watcher
Watcher机制是Zookeeper提供的一种事件通知机制，当我们在某个ZNode上注册了Watcher，如果这个ZNode发生了变化，Zookeeper会通知客户端，客户端可以通过Watcher机制来实现一些高级特性，比如分布式锁、配置管理等。
WatchManager负责管理所有的 Watcher，其内部维护了两个哈希表：watchTable和watch2Paths，watchTable是一个从ZNode到Watcher的映射表，watch2Paths是一个从Watcher到ZNode的映射表。
当ZNode发生变化时，通过watchTable找到所有注册在这个ZNode上的Watcher，然后通知这些Watcher。但Watcher通知是一次性的，果我们想要继续监听ZNode的变化，就需要重新注册Watcher。
另外，Watcher与客户端的Session绑定，当Session超时或关闭时，所有的Watcher都会失效，客户端需要重新注册Watcher，在重新建立连接前，任何ZNode的变化都不会通知客户端。我们在接收到通知后，或出现网络故障，都需要重新注册Watcher，如果我们在重新注册Watcher之前，ZNode发生了变化，那么我们就会错过这次变化，从而导致客户端观测到的数据变化过程少于真实的数据变化过程，因此 Zookeeper的Watcher机制只能保证最终一致性，而不能保证线性一致性。
Zookeeper局限性
ZooKeeper基于ZAB协议实现能够满足：
- 可用性：以集群方式部署，采用Leader-Follower模式，能够保证在节点故障时进行自动选举Leader，恢复可用
- 一致性：使用ZAB协议保证了数据的一致性，所有写操作都由Leader处理，通过2PC方式广播给Followers，确保集群数据一致
- 可靠性：使用持久化日志来记录所有的写操作，保证数据的可靠性和可恢复性，即使Leader节点宕机，新的Leader也可以从日志中恢复数据
- 性能：使用内存数据库存储数据，能快速地响应读操作，Leader-Follower之间的提议也会并行处理，提高写操作的吞吐量
- 易用性：提供了简单的API和数据模型，易于使用和理解，适用于各种分布式应用场景
但是也存在很多局限性
- 单点故障：如果Leader节点宕机，会导致整个集群的不可用，虽然会尽快选举出新的Leader，但仍然存在短暂的不可用性，而且集群的稳定性依赖网络的稳定，对网络延迟敏感。
- 单点瓶颈：所有写操作都由Leader处理，然后同步给Follower并等待超半数的ACK，Leader可能成为性能瓶颈，特别是在高负载情况下。而且Leader需要维护超半数follower的心跳，follower增多也就让选举过程更慢，这对集群规模会有所限制，所以zk引入Observer，减轻选举过程。
参考：