目的

为解决大型分布式系统中多个副本日志及状态机一致性问题。

Raft介绍

协议由三部分组成:Leader election、Log Replication、Safety。分别对应着三种状态的身份:
leader(工作时的首要进程)、candidate(选举时可能会成为leader)、follower(副本).

Raft选举

选举的时机一般有两种:

  • 初始化时,系统中不存在 Leader 角色。所有节点均为 candidate 角色
  • follower 在 election timeout 后没有收到 leader心跳,follower 变为 candidate 角色

candidate向其他节点发起 leader election 请求,得到超过半数其他 candidate 的回复后成为leader. 同时选举的过程存在极端情况:

  • 所有选票被多个节点瓜分,没有选出leader。

为避免发生多个 candidate 同时发生选举,而导致的多次选举。raft采用 random election timeout 机制,使每个节点的超时时间不同。
一般来说需要保证 election timeout > broadcast 的间隔时间,否则,election timeout 无法说明与leader断开连接.

安全性

两个限制条件保证日志复制的安全

限制一:选举阶段节点 m 向节点 n 发送了 RequestVote RPC,如果节点 n 发现节点 m 的数据没有自己新,则节点 n 拒绝节点 m 的投票请求。
这里的“新”包含两个方面,term 更大的数据更新,term 相同,index更大的数据更新。

选举时,只有日志最新的candidate才有机会得到超过半数的投票。其中有这两个条件:

  • term越大的节点越容易成为leader
  • term相同的情况下,index越大的节点越容易成为leader

限制二:不直接提交之前 term 的log,必须通过提交本 term 的 log,间接的提交之前 term 的 log。
选举时,在条件1的情况下,term不同,可能选举出来的leader不包含所有过半提交的日志。要解决这个问题,需要在 那么就需要对过半提交通过限制二来约束。
一旦加上了这个限制意味着含有所有过半提交的日志的几个节点必然拥有目前最大的term,这样的话再次进行leader选举时,就避免了条件1的误判。

Raft 对比 Zab

Leader election 阶段

IssueRaftZab
Leader检测通过Follower心跳leader: 维护Quorum集合;
follower: 通过长链接
过期leader判断term_idepoch
leader投票过程每个节点每轮只投一次票每次选举节点可能产生多次投票,选出最新的
  • leader 可用性检查:Raft 协议 leader 宕机仅仅由 folower 进行检测,当 folower 收不到 leader 心跳时,则认为 leader 宕机,
    变为 candidate。Zk 的 leader down 机分别由 leader 和 folower 检测,leader 维护了一个 Quorum 集合,当该 Quorum 集合不再超过半数,
    leader 自动变为 LOOKING 状态。folower 与 leader 之间维护了一个超链接,连接断开则 folower 变为 LOOKING 状态。
  • 过期 leader 的屏蔽:Raft 通过 term 识别过期的 leader。Zk 通过 Epoch识别过期的 leader。这点两者是相似的。
  • leader 选举的投票过程:Raft 每个选举周期每个节点只能投一次票,选举失败进入下次周期才能重新投票。
    Zk 每次选举节点需要不断的变换选票以便选出数据最新的节点为 leader。
  • 保证 commited 的数据出现在未来 leader 中:Raft选取 leader 时拒绝数据比自己旧的节点的投票。
    Zk 通过在选取 leader 时不断更新选票使得拥有最新数据的节点当选 leader。

Zab在leader选举出来后会立即进行数据同步过程,同步下最新的epoch(相当于term),数据同步之后就不会存在Raft(经过几个term变更后)日志错乱的现象。
Zab是正式对外提交服务之前先清理好数据的不一致问题,Raft是延迟清理的,在后续的复制过程中不断的进行纠正更新。

Log Replication 阶段

IssueRaftZab
新leader数据同步通过AppendEntry Rpc每次同步通过 Recovery Phase 同步
新leader数据同步量增量同步增量或全量同步
之前未commit数据处理commit 当前term时,会将未提交数据一起commitRecovery Phase阶段commit
新加入集群节点数据同步不阻塞写请求Recovery Phase 会阻塞写请求
  • 选取新 leader 后数据同步:Raft 没有固定在某个特定的阶段做这件事情,通过每个节点的 AppendEntry RPC 分别做数据同步。
    Zk 则在新leader 选举之后,有一个 Recovery Phase 做这个件事情。
  • 选取新 leader 后同步的数据量:Raft 只需要传输和新 leader 差异的部分。Zab 的原始协议需要传输 leader 的全部数据,Zk 优化后,
    视情况而定,最坏情况下需要传输 leader 全部数据。
  • 新 leader 对之前 leader 未 commit 数据的处理:Raft 不会直接 commit 之前 leader 的数据,通过 commit 本 term 的数据间接的 commit 之前 leader 的数据。
    Zk 在 Recovery Phase直接 commit 之前 leader 的数据。
  • 新加入集群节点的数据同步:Raft 对于新加入集群的节点数据同步不会影响客户端的写请求。Zk 对于新加入集群的节点,需要单独走一下 Recovery Phase,
    目前是通过读写锁同步的,因此会阻塞客户端的写请求。(Zk 可以在这里使用 copy-on-write 机制避免阻塞问题??)

脑裂问题

RaftZab
通过增加region leader角色 + lease机制,每个请求通过region leader转发至raft leader通过Quorum过半机制避免

Tips: Etcd 不存在脑裂

Reference

https://niceaz.com/2018/11/03/raft-and-zab/
https://www.jianshu.com/p/072380e12657