Zookeeper学习笔记-入门(3)-Paxos和ZAB协议

Paxos协议

Paxos是一种基于消息传递且具有高度容错性的一致性算法，它主要解决的问题是如何快速正确地在一个分布式系统中对某个数据值达成一致，并且保证无论发生任何异常，都不会破坏整个系统的一致性

在一个Paxos系统中，节点角色有Proposer、Acceptor和Learner。我们可以将一致性问题简化为集群中所有节点对一个值value达成一致。一个完整的Paxos算法流程分为三个阶段，提案生成、提案接受和Learn学习：

这里首先明确，Acceptor在整个过程中需要完成的工作就是响应请求和接受提案，一个Acceptor需要保存它响应过的最大请求编号ResN以及接受过的最大提案编号AcceptN和对应的提案值AcceptV。

1. 提案生成阶段：
   1. Proposer向多个Acceptor发送Propose请求，proposal编号为N
   2. 如果一个Acceptor收到编号为N的proposal，那么它会比较该编号N和自己的ResN的大小，只有当N>ResN的时候，Acceptor才会响应这个请求，并在响应中返回已经接受过的Pok，最大请求编号和对应的值(Pok,AcceptN,AcceptV)，如果该Acceptor没有接受过提案，则返回null。
2. 提案接受阶段：
   1. 如果Proposer接受了超过半数的Acceptor的响应，那么就会生成一个提案，编号为N，值为获取到的响应中编号最大的Value。如果都返回null，则Value为Proposer自己生成的值。之后Proposer将提案发生给Acceptor
   2. 如果没有收到超过半数的Acceptor，则重新获取编号，并回到提案生成阶段
   3. 如果Acceptor收到了一个编号为N的提案，也会比较ResN和N的大小，只有N>ResN，才会接受该提案，并返回Aok
   4. 如果Proposer收到超过半数的Aok，则表示提案被接受，形成决议；否则重新发起请求
3. Learn学习阶段：Proposer将形成的决议发送给所有的Learners

ZAB协议

由于Paxos系统中可以存在多个Proposer，在网络复杂的情况下，可能很久无法收敛，甚至陷入活锁的情况。这是因为可能出现多个Proposer相互争夺Acceptor，造成迟迟无法达成一致。

ZAB协议，全称为Zookeeper Atomic Broadcast，借鉴了Paxos算法，是特别为Zookeeper设计的支持崩溃恢复的原子广播协议。

基于该协议，Zookeeper设计为只有一台客户端，即Leader负责处理外部的写事务请求，然后Leader客户端将数据同步到其他的Follower节点。也就是说，Zookeeper中只有一个Leader可以发起提案。

Zookeeper 客户端会随机的链接到 zookeeper 集群中的一个节点，如果是读请求，就直接从当前节点中读取数据；如果是写请求，那么节点就会向 Leader 提交事务，Leader 接收到事务提交，会广播该事务，只要超过半数节点写入成功，该事务就会被提交。

ZAB协议主要包括两种基本的模式：消息广播和崩溃恢复。

消息广播是ZAB协议的正常工作模式：

1. 客户端发起一个写请求操作
2. Leader服务器将客户端的请求转化为事务proposal提案，同时为每个proposal分配一个全局的zxid
3. Leader服务器为每个Follower服务器分配一个单独的队列，然后将需要广播的Proposal依次放入队列，并根据FIFO策略进行消息发送
4. Follower接收到proposal后，会首先将其以事务日志的方式写入本地磁盘，写入成功之后向Leader反馈一个ack响应
5. Leader接收超过半数以上的Follower的ack响应之后，即认为消息发送成功，继续发送commit消息
6. Leader向所有Follower广播commit消息，同时自身也会完成事务提交。Follower接收到commit消息之后，会将上一条事务提交

消息广播的处理类似于一个两阶段提交的机制，但是这里仅要求超过半数的Acceptor返回了ack即可。

Zookeeper 采用 Zab 协议的核心，就是只要有一台服务器提交了 Proposal，就要确保所有的服务器最终都能正确提交 proposal。这也是 CAP/BASE 实现最终一致性的一个体现。

Leader 服务器与每一个 Follower 服务器之间都维护了一个单独的 FIFO 消息队列进行收发消息，使用队列消息可以做到异步解耦。 Leader 和 Follower 之间只需要往队列中发消息即可。如果使用同步的方式会引起阻塞，性能要下降很多。

崩溃恢复则是ZAB协议在异常情况下的工作模式。如果Leader服务器崩溃，或者由于网络原因导致Leader服务器失去了与过半Follower的联系，则进入崩溃恢复模式。在异常情况下，proposal的执行情况会受到影响，ZAB协议中遵循以下原则：

1. 已经被Leader commit提交的proposal，必须最终被所有的follower服务器提交
2. 被Leader提出的但是没有被提交的proposal，则丢弃

崩溃恢复模式中主要完成的工作是Leader选举以及数据恢复。

在Leader选举阶段中，ZAB协议需要保证选举出来的Leader满足以下条件：

1. 新选举出来的Leader不能包含未提交的proposal。即新Leader必须都是已经提交了proposal的follower的服务器节点
2. 新选举的Leader节点中含有最大的zxid（事务id）

在数据同步阶段中，新选举出来的Leader服务器会首先确认事务日志中的所有proposal是否已经被集群中过半的服务器commit。等到Follower将所有尚未同步的事务proposal都从Leader同步过并应用到内存数据之后，Leader才会把该Follower加入到真正可用的Follower列表当中。

ZAB协议中，zxid设计成为一个64位的整型数字。其中低32位可以看成是一个简单的递增计数器，表示事务请求；而高32位则代表了Leader周期的epoch编号。

当选举产生了一个新Leader之后，会从该服务器上读取出本地事务日志中最大编号proposal的zxid，从中解析出对应的epoch编号之后，对其+1作为目前Leader的epoch，并将低32位数字归零，重新生成zxid

参考文章

1. Zookeeper——一致性协议:Zab协议 - 简书 (jianshu.com)