共识算法

2024-04-01 17:31:16

ZAB 协议
Raft 协议
参考文献

ZAB 协议

ZooKeeper Automic Broadcast，原子广播
quorum 法定数量，一般设置为集群节点数的半数以上。
looking 服务器刚启动，或者超时内没收到 heartbeat。
leading 服务器作为 leader。

处理事务请求，leader 为每个 follower 单独维护一个队列，通过队列异步发送，能保证 follower 收到顺序的 proposal。
定时广播心跳，如果没收到 quorum 的 ack，则进入 looking。

following 服务器作为 follower

处理非事务请求、转发事务请求给 leader。
如果超时没收到 leader 的心跳，则进入 looking。

observing 服务器作为 observer，可以处理非事务请求，但不参与投票。
myid 每个节点都会维护一个 myid 文件，该文件记录了集群所有节点的唯一ID。
logicClock 等价于 electionEpoch，表示该服务器发起的第N轮投票。
epoch 等价于 peerEpoch，表示该事务生成时，所在的轮次。
zxid ZooKeeper transaction id，long型，高32位表示 epoch，低32位表示 递增事务id。

广播模式

和 2PC 不同，ZAB 只需 quorum 的 ack 即可提交，缩短阻塞 client 的时间，但由于没有回滚操作，ZAB 只能保证 顺序一致性。

leader 收到写请求，转换为 proposal，写入发送队列，异步发送给 follower 并等待 ack。
follower 收到 proposal 后返回 ack。
leader 收到 quorum 的 ack 后提交 proposal，响应 client 写入成功，同时广播 commit。
follower 收到 commit 后提交本地 proposal。

恢复模式

looking 默认给自己投一票，并广播，此时票箱中只有投给自己的一张选票。
looking 收到外部选票，如果外部选票的 logicClock 大于自己的 logicClock，则更新自己的 logicClock、选票，并广播。
如果 logicClock 一致，则比较 zxid，若外部选票的 zxid 更大，则更新自己的选票并广播。
如果 zxid 一致，则比较 myid，若外部选票的 myid 更大，则将更新自己的选票并广播。
如果 node 的票箱已经出现 quorum 的投票，则根据投票情况更新自己的状态为 leading 或 following。
如果成为 follower，向 leader 发送最大 zxid，等待 leader 增量同步日志。
leader 完成日志同步后，丢弃、提交上一个 leader 遗留的 proposal，最后通知 follower 对外服务。

建议奇数节点个数

一致性 保证分区后的集群只有一个 leader 可用，保证整个集群的一致性。
可用性 3个节点的集群、4个节点的集群都只能容忍宕机1个节点，可用性相同的情况下，奇数个节点可以少维护一个节点。

Raft 协议

follower 可读，收到写请求转发给 leader，节点启动默认是 follower。
candidate 有 被选举权 的 follower，把第一票给自己，尝试收集过半选票成为 leader。
leader 读写，每隔 heartbeat timeout 发送 Append Entries RPC。
election timeout 选举超时：

如果 follower 在超时内没收到RPC，会自增 term 并成为 candidate。
如果 candidate 在超时内没成为 leader，会自增 term 并发起下一轮投票。

heartbeat timeout 心跳超时，超时内 leader 会发送一个 Append Entries RPC。
Append Entries RPC 同步日志、心跳检测请求。
Request Vote RPC 收集选票请求。
term node 的属性，在选举的时候用地上。
entry leader 将一个写请求记录为日志条目。
split vote 各个 candidate 都没有收到过半的投票，那么这一个 term 的选举失败

Log Replication

leader 收到写请求，先转换为 entry 写入本地日志
leader 等待 heartbeat timeout，通过 Append Entries RPC 把 entry 同步给 follower
leader 等待过半 ack 后提交 entry
leader 等待 heartbeat timeout，通过 Append Entries RPC 通知 followers 提交 entry

Leader Election

follower 在 election timeout 没收到心跳包，自增 term 并成为 candidate 并重置 election timeout
candidate 发送 Request Vote RPC 给其它 candidate、follower，选票内容 (term, entry index)
在一个 term 中，节点只能投一票，candidate 把票投给自己后，就要等下一个 term 才能投票了
follower 收到 Request Vote RPC，先比较 term，假如 term 相同再比较 entry index，大才给选票。
follower 给出选票后，重置 election timeout。如果没给选票，等待 election timeout 后亲自参选。
成为 leader 后，每隔 heartbeat timeout 发送 Append Entries messages 给 followers

分区

解除分区后，集群有2个 leader。有效leader 广播 Append Entries RPC，无效leader 收到后，比较发现 有效leader 拥有更大的 term，于是降级为 follower，并同步落后的数据。

码农公寓