分布式共识：ZAB

ZAB 背景

ZAB 设计的时候，multi-paxos 算法无法保证操作的有序性。即，假设客户端有两个指令 X 和 Y，需要先执行 X 再执行 Y。对于 multi-paxos 算法来说无法做到。具体例子参考：15 | ZAB协议：如何实现操作的顺序性？ - 极客时间已完结课程限时免费阅读。

需要注意，在 Zookeeper 设计的时候，Raft 还没有出现，所以没法使用 Raft 算法。

ZAB 共识方式

ZAB 如何实现操作的顺序性？

写操作必须在主节点(比如节点 A)上执行。如果客户端访问的节点是备份节点(比如节点 B)，它会将写请求转发给主节点。
主节点收到请求后，会创建一个提案(Proposal)，并用唯一 ID 来标识提案。这个 ID 就是事务 ID(代码里的 zxid)。
事务 ID 是一个 64 位的 long 型变量，高 32 位为任期编号，低 32 位为计数器。新领导者当选时，任期编号自增，计数器归零。新提案出现时，计数器自增。
在创建完提案之后，主节点会基于 TCP 协议，并按照顺序将提案广播到其他节点。这样就能保证先发送的消息，会先被收到，保证了消息接收的顺序性。
当主节点接收到指定提案的“大多数”的确认响应后，该提案将处于提交状态，主节点会通知备份节点提交该提案。

为了提升读并发能力，Zookeeper 提供的是最终一致性，也就是读操作可以在任何节点上执行，客户端会读到旧数据。
如果客户端想要读取最新数据，可以先执行 ZooKeeper 提供的 sync 指令，再执行操作。

ZAB Leader 选取

ZAB 三种成员角色

Leader：主节点，同一时刻中唯一，写操作只在 Leader。
Follower：响应领导者的心跳，并参与领导者选举和提案提交的投票，可以响应客户端读请求。
Observer：类似跟随者，但是没有投票权。

ZAB 四种成员状态

LOOKING：选举状态，该状态下的节点认为当前集群中没有领导者，会发起领导者选举。
FOLLOWING ：跟随者状态，意味着当前节点是跟随者。
LEADING ：领导者状态，意味着当前节点是领导者。
OBSERVING：观察者状态，意味着当前节点是观察者。

选举消息

假设投票信息的格式是 <proposedLeader, proposedEpoch, proposedLastZxid，node>
proposedLeader，节点提议的，领导者的集群 ID，也就是在集群配置时指定的 ID。
proposedEpoch，节点提议的，领导者的任期编号。
proposedLastZxid，节点提议的，领导者的事务标识符最大值(也就是最新提案的事务标识符)。
node，投票的节点。

选举过程

当跟随者检测到连接领导者节点的读操作等待超时了，将自己状态变更成 LOOKING，然后发起领导者选举。
每个节点会创建一张选票，推荐自己，并将投票信息广播给所有节点。
每个节点读取接受到的选票信息，然后进行领导力 PK，根据 PK 结果判断是否更新选票。若更新选票，则重新广播自己的选票。
若提议的领导者赢得了大多数选票，则变更节点状态为 Leader 或者 Follower，退出选举。

领导力 PK 方法

优先检查任期编号(Epoch)，任期编号大的节点作为领导者；
如果任期编号相同，比较事务标识符的最大值，值大的节点作为领导者；
如果事务标识符的最大值相同，比较集群 ID，集群 ID 大的节点作为领导者。

ZAB 故障恢复

节点的运行状态

ELECTION(选举状态)：表明节点在进行领导者选举；
DISCOVERY(成员发现状态)：表明节点在协商沟通领导者的合法性；
SYNCHRONIZATION(数据同步状态)：表明集群的各节点以领导者的数据为准，修复数据副本的一致性；
BROADCAST(广播状态)：表明集群各节点在正常处理写请求。只有当集群大多数节点处于广播状态的时候，集群才能提交提案。

如何确认领导者的领导关系?

B 会主动联系 C，发送给它包含自己接收过的领导者任期编号最大值的 FOLLOWINFO 消息。
当 C 接收来自 B 的信息时，它会将包含自己事务标识符最大值的 LEADINFO 消息发给跟随者。要注意，领导者进入到成员发现阶段后，会对任期编号加 1，创建新的任期编号，然后基于新任期编号，创建新的事务标识符
当接收到领导者的响应后，跟随者会判断领导者的任期编号是否最新，如果不是，就发起新的选举；如果是，跟随者返回 ACKEPOCH 消息给领导者，并设置 ZAB 状态为数据同步状态。
当领导者接收到来自大多数节点的 ACKEPOCH 消息时，就设置 ZAB 状态为数据同步状态。

如何处理冲突数据?

当进入到数据同步状态后，Leader 会根据跟随者的事务标识符最大值，选择数据同步方案。
Leader 将要修复或处理的数据和 NEWLEADER 消息发送给 Follower。
需要注意的是，在 ZooKeeper 实现中，节点退出跟随者状态时(也就是在进入选举前)，所有未提交的提案都会被提交。
Follower 修复数据完成后，返回 NEWLEADER 消息的 ACK 响应给 Leader。
当 Leader 收到来自大多数节点的 NEWLEADER 消息的 ACK 后，将设置 ZAB 状态为广播，并发送 UPTODATE 消息给所有 Follower，通知它们数据同步已经完成了。
Follower 收到 UPTODATE 消息时，设置 ZAB 状态为广播。

ZooKeeper 三种数据同步方案

TRUNC：当 peerLastZxid 大于 maxCommittedLog 时，领导者会通知跟随者丢弃超出的那部分提案。
DIFF：当 peerLastZxid 小于 maxCommittedLog，但 peerLastZxid 大于 minCommittedLog 时，领导者会同步给跟随者缺失的已提交的提案，
SNAP：当 peerLastZxid 小于 minCommittedLog 时，也就是说，跟随者缺失的提案比较多，那么，领导者同步快照数据给跟随者，并直接覆盖跟随者本地的数据。

其中，peerLastZxid 是 Follower 事务 ID 最大值。maxCommittedLog、minCommittedLog 与 ZooKeeper 的设计有关。在 ZooKeeper 中，为了更高效地复制提案到 Follower 上，Leader 会将一定数量(默认值为 500)的已提交提案放在内存队列里。maxCommittedLog 和 minCommittedLog 分别是 Leader 内存队列中，已提交提案的事务 ID 最大值和最小值。

在 ZooKeeper 中，一个提案进入提交状态，有两种方式：

被复制到大多数节点上，被领导者提交或接收到来自领导者的提交消息而被提交。在这种状态下，提交的提案是不会改变的。
另外，在 ZooKeeper 的设计中，在节点退出跟随者状态时，会将所有本地未提交的提案都提交。需要你注意的是，此时提交的提案，可能并未被复制到大多数节点上，而且这种设计，就会导致 ZooKeeper 中出现，处于“提交”状态的提案可能会被删除。

Zookeeper 读写请求处理

处理读写请求的原理

在 ZooKeeper 中，与领导者“失联”的节点，是不能处理读写请求的。
当大多数节点进入到广播阶段的时候，领导者才能提交提案，因为提案提交，需要来自大多数节点的确认。
写请求只能在 leader 上处理，follower 收到了写请求，会转发到 leader 节点。所以 ZooKeeper 集群写性能约等于单机。除此之外，若 follower 收到了写请求，会在收到 leader 的 commit 消息后，返回成功给客户端。
读请求是可以在所有的节点上处理的，所以，读性能是能水平扩展的，即最终一致性。

扩展问题

TCP 是否可能消息乱序？

不会的。虽然可能接受的时候是乱序，但是 TCP 基于消息中的 seq 序号实现了 TCP 重组，能保证数据被严格按照顺序处理。

ZAB 能否使用 UDP 进行广播？

TCP 协议本身支持按序确认，而 UCP 只能支持尽最大可能交付。除非自己在 UDP 基础上，对于消息内部增加更多处理。

TCP 只能保证消息接受的顺序性，如何保证事务的顺序性？

上一个事务 ID 没提交，当前事务 ID 需要等待才能提交，核心判断代码：outstandingProposals.containsKey(zxid - 1)

Raft 和 ZAB 在 Leader 选举上的区别？

ZAB 通过领导力 PK 来选举 Leader，并且每个人可以更改自己的选票。
Raft 一般来说先收到谁的选票，就选择谁。如果同时多个在同一任期，会比较日志情况。每个人只有一张选票，所以存在一轮选不出结果进而重新选举的情况。

Raft 和 ZAB 的对比

领导者选举：ZAB 采用的“见贤思齐、相互推荐”的快速领导者选举(Fast Leader Election)，Raft 采用的是“一张选票、先到先得”的自定义算法。在我看来，Raft 的领导者选举，需要通讯的消息数更少，选举也更快。
日志复制：Raft 和 ZAB 相同，都是以领导者的日志为准来实现日志一致，而且日志必须是连续的，也必须按照顺序提交。
读操作和一致性：ZAB 的设计目标是操作的顺序性，在 ZooKeeper 中默认实现的是最终一致性，读操作可以在任何节点上执行；而 Raft 的设计目标是强一致性(也就是线性一致性)，所以 Raft 更灵活，既可以提供强一致性，也可以提供最终一致性。
写操作：Raft 和 ZAB 相同，写操作都必须在领导者节点上处理。
成员变更：Raft 和 ZAB 都支持成员变更，其中 ZAB 以动态配置(dynamic configuration)的方式实现的。那么当你在节点变更时，不需要重启机器，集群是一直运行的，服务也不会中断。
其他：相比 ZAB，Raft 的设计更为简洁，比如 Raft 没有引入类似 ZAB 的成员发现和数据同步阶段，而是当节点发起选举时，递增任期编号，在选举结束后，广播心跳，直接建立领导者关系，然后向各节点同步日志，来实现数据副本的一致性。在我看来，ZAB 的成员发现，可以和领导者选举合到一起，类似 Raft，在领导者选举结束后，直接建立领导者关系，而不是再引入一个新的阶段；数据同步阶段，是一个冗余的设计，可以去除的，因为 ZAB 不是必须要先实现数据副本的一致性，才可以处理写请求，而且这个设计是没有额外的意义和价值的。

🪴 Obsidian Publish

探索