Paxos,Raft,Zab强一致性协议-Zab篇

Zab也是一个强一致性算法,也是(multi-)Paxos的一种,全称是Zookeeper atomic broadcast protocol,是Zookeeper内部用到的一致性协议。相比Paxos,也易于理解。其保证了消息的全局有序和因果有序,拥有强一致性。Zab和Raft也是非常相似的,只是其中有些概念名词不一样。

Role(or Status)

节点状态:

Leading:说明当前节点为Leader

Following:说明当前节点为Follower

Election:说明节点处于选举状态。整个集群都处于选举状态中。

Epoch逻辑时钟

Epoch相当于paxos中的proposerID,Raft中的term,相当于一个国家,朝代纪元。

Quorums:

多数派,集群中超过半数的节点集合。

节点中的持久化信息:

history:a log of transaction proposals accepted; 历史提议日志文件

acceptedEpoch:the epoch number of the last NEWEPOCH message accepted; 集群中的最近最新Epoch

currentEpoch:the epoch number of the last NEWLEADER message accepted; 集群中的最近最新Leader的Epoch

lastZxid:zxid of the last proposal in the history log; 历史提议日志文件的最后一个提议的zxid

在 ZAB 协议的事务编号 Zxid 设计中,Zxid是一个 64 位的数字,

低 32 位是一个简单的单调递增的计数器,针对客户端每一个事务请求,计数器加 1;

高 32 位则代表 Leader 周期 epoch 的编号,每个当选产生一个新的 Leader 服务器,就会从这个 Leader 服务器上取出其本地日志中最大事务的ZXID,并从中读取 epoch 值,然后加 1,以此作为新的 epoch,并将低 32 位从 0 开始计数。

epoch:可以理解为当前集群所处的年代或者周期,每个 leader 就像皇帝,都有自己的年号,所以每次改朝换代,leader 变更之后,都会在前一个年代的基础上加 1。这样就算旧的 leader 崩溃恢复之后,也没有人听他的了,因为 follower 只听从当前年代的 leader 的命令。

ZAB协议

Zab协议分为四个阶段

Phase 0: Leader election(选举阶段,Leader不存在)

节点在一开始都处于选举阶段,只要有一个节点得到超半数Quorums节点的票数的支持,它就可以当选prospective leader。只有到达 Phase 3 prospective leader 才会成为established leader(EL)。

这一阶段的目的是就是为了选出一个prospective leader(PL),然后进入下一个阶段。

协议并没有规定详细的选举算法,后面我们会提到实现中使用的Fast Leader Election。

Phase 1: Discovery(发现阶段,Leader不存在)

在这个阶段,PL收集Follower发来的acceptedEpoch(或者),并确定了PL的Epoch和Zxid最大,则会生成一个NEWEPOCH分发给Follower,Follower确认无误后返回ACK给PL。

这个一阶段的主要目的是PL生成NEWEPOCH,同时更新Followers的acceptedEpoch,并寻找最新的historylog,赋值给PL的history。

这个阶段的根本:发现最新的history log,发现最新的history log,发现最新的history log。

一个 follower 只会连接一个 leader,如果有一个节点 f 认为另一个 follower 是 leader,f 在尝试连接 p 时会被拒绝,f 被拒绝之后,就会进入 Phase 0。

Phase 2: Synchronization(同步阶段,Leader不存在)

同步阶段主要是利用 leader 前一阶段获得的最新提议历史,同步集群中所有的副本。只有当 quorum 都同步完成,PL才会成为EL。follower 只会接收 zxid 比自己的 lastZxid 大的提议。

这个一阶段的主要目的是同步PL的historylog副本。

Phase 3: Broadcast(广播阶段,Leader存在)

到了这个阶段,Zookeeper 集群才能正式对外提供事务服务,并且 leader 可以进行消息广播。同时如果有新的节点加入,还需要对新节点进行同步。

这个一阶段的主要目的是接受请求,进行消息广播

值得注意的是,ZAB 提交事务并不像 2PC 一样需要全部 follower 都 ACK,只需要得到 quorum (超过半数的节点)的 ACK 就可以了。

zookeeper中zab协议的实现

协议的 Java 版本实现跟上面的定义有些不同,选举阶段使用的是 Fast Leader Election(FLE),它包含了 Phase 1 的发现职责。因为FLE 会选举拥有最新提议历史的节点作为 leader,这样就省去了发现最新提议的步骤。实际的实现将 Phase 1 和 Phase 2 合并为 Recovery Phase(恢复阶段)。所以,ZAB 的实现只有三个阶段:

Phase 1:Fast Leader Election(快速选举阶段,Leader不存在)

前面提到 FLE 会选举拥有最新提议历史(lastZixd最大)的节点作为 leader,这样就省去了发现最新提议的步骤。这是基于拥有最新提议的节点也有最新提交记录的前提。

每个节点会同时向自己和其他节点发出投票请求,互相投票。

选举流程:

选epoch最大的

epoch相等,选 zxid 最大的

epoch和zxid都相等,选择serverID最大的(就是我们配置zoo.cfg中的myid)

节点在选举开始都默认投票给自己,当接收其他节点的选票时,会根据上面的条件更改自己的选票并重新发送选票给其他节点,当有一个节点的得票超过半数,该节点会设置自己的状态为 leading,其他节点会设置自己的状态为 following。

Phase 2:Recovery Phase(恢复阶段,Leader不存在)

这一阶段 follower 发送它们的 lastZixd 给 leader,leader 根据 lastZixd 决定如何同步数据。这里的实现跟前面 Phase 2 有所不同:Follower 收到 TRUNC 指令会中止 L.lastCommittedZxid 之后的提议,收到 DIFF 指令会接收新的提议。

Phase 3:Broadcast Election(广播阶段,Leader存在)

同上

Leader故障

如果是Leader故障,首先进行Phase 1:Fast Leader Election,然后Phase 2:Recovery Phase,恢复阶段保证了如下两个问题,这两个问题同时也和Raft中的Leader故障解决的问题是一样的,总之就是要保证Leader操作日志是最新的

已经被处理的消息不能丢

被丢弃的消息不能再次出现

总结

Zab和Raft都是强一致性协议,但是Zab和Raft的实质是一样的,都是mutli-paxos衍生出来的强一致性算法。简单而言,他们的算法都都是先通过Leader选举,选出一个Leader,然后Leader接受到客户端的提议时,都是先写入操作日志,然后再与其他Followers同步日志,Leader再commit提议,再与其他Followers同步提议。如果Leader故障,重新走一遍选举流程,选取最新的操作日志,然后同步日志,接着继续接受客户端请求等等。过程都是一样,只不过两个的实现方式不同,描述方式不同。实现Raft的核心是Term,Zab的核心是Zxid,反正Term和Zxid都是逻辑时钟。

引用

https://www.cnblogs.com/bangerlee/p/5991417.html

https://github.com/CNiceToUpp/notes/blob/master/paxos%2Craft%2Czab/paper/A%20simple%20totally%20ordered%20broadcast%20protocol.pdf

https://github.com/CNiceToUpp/notes/blob/master/paxos%2Craft%2Czab/paper/ZooKeeper%E2%80%99s%20atomic%20broadcast%20protocol.pdf

https://www.bilibili.com/video/av21667358/

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180701G1CWZW00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

同媒体快讯

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励