莫那·鲁道

惯于闲看花飞花落, 心念天际云卷云舒.

Coder, 欢迎留言 😆.


GitHub

Raft 拾遗

背景

本文关注实现 Raft 的关键参数。仅做备忘。

1. 跟随者和候选人崩溃

相比较 leader 崩溃,这个要简单的多,当 follower 崩溃,leader 只需要不断重试即可,当 follower 重启,RPC 重试会成功,注意:RPC 重试是幂等的,因此重试不会造成任何问题。

2. 时间和可用性

在 Raft 中,关于时间,有 3 种类型:

  1. 广播时间(broadcastTime):指一个节点并行的发送 RPC 给其他节点并收到响应的平均时间。
  2. 选举超时时间(electionTimeout):如果一个跟随者在一段时间里没有接收到任何消息,也就是选举超时。
  3. 平均故障间隔时间(MTBF):平均故障间隔时间就是对于一台服务器而言,两次故障之间的平均时间。

Raft 规定,只要系统满足下面的时间要求,就可以选举并维持一个稳定的领导人。

 广播时间(broadcastTime) << 选举超时时间(electionTimeout) << 平均故障间隔时间(MTBF)

通常广播时间比选举超时时间小一个数量级,这样 leader 才能发送稳定的心跳来阻止跟随者进入选举状态;

选举超时时间一般比 MTBF 小几个数量级,这样整个系统才能正常运行。当 leader 崩溃后,整个系统的不可用时间,大约相当于选举时间超时时间。

广播时间和 MTBF 是由系统决定的,只有选举超时时间是我们自己选择的,通常广播时间大约是 0.5 毫秒到 20 毫秒(持久化需要时间),那么,选举超时时间通常在 10 毫秒 到 500 毫秒之间。

而 MTBF 时间,通常平均故障时间在几个月甚至更长,君不见美团的服务器可用性达到 7 个九 :)因此很容易满足时间的需求。

3. Raft 算法细节:

1. 状态
  • 所有服务器上持久存在的

  • 所有服务器上经常变的

  • 在领导人里经常变化的(选举后重新初始化)

2. 附加日志 RPC
  • 具体指令 由领导人负责调用来复制日志指令,也会用作心跳

  • 接受者实现
    1. 如果 term < currentTerm 就返回 false
    2. 如果日志在 prevLogIndex 位置处的日志条目的任期号和 prevLogTerm 不匹配,则返回 false
    3. 如果已经存在的日志条目和新的产生冲突(索引值相同但是任期号不同),删除这一条和之后所有的
    4. 附加任何在已有的日志中不存在的条目
    5. 如果 leaderCommit > commitIndex,令 commitIndex 等于 leaderCommit 和 新日志条目索引值中较小的一个
3. 请求投票 RPC
  1. 参数详情

由候选人负责调用用来征集选票

  1. 接收者实现
    1. 如果term < currentTerm返回 false
    2. 如果 votedFor 为空或者就是 candidateId,并且候选人的日志至少和自己一样新,那么就投票给他
4. 所有服务器需遵守的规则
  1. 所有服务器
    • 如果commitIndex > lastApplied,那么就 lastApplied 加一,并把log[lastApplied]应用到状态机中
    • 如果接收到的 RPC 请求或响应中,任期号T > currentTerm,那么就令 currentTerm 等于 T,并切换状态为跟随者
  2. 跟随者
    • 响应来自候选人和领导者的请求
    • 如果在超过选举超时时间的情况之前都没有收到领导人的心跳,或者是候选人请求投票的,就自己变成候选人
  3. 候选人
  • 在转变成候选人后就立即开始选举过程
    • 自增当前的任期号(currentTerm)
    • 给自己投票
    • 重置选举超时计时器
    • 发送请求投票的 RPC 给其他所有服务器
  • 如果接收到大多数服务器的选票,那么就变成领导人
  • 如果接收到来自新的领导人的附加日志 RPC,转变成跟随者
  • 如果选举过程超时,再次发起一轮选举
  1. 领导人
    • 一旦成为领导人:发送空的附加日志 RPC(心跳)给其他所有的服务器;在一定的空余时间之后不停的重复发送,以阻止跟随者超时
  • 如果接收到来自客户端的请求:附加条目到本地日志中,在条目被应用到状态机后响应客户端

  • 如果对于一个跟随者,最后日志条目的索引值大于等于 nextIndex,那么:发送从 nextIndex 开始的所有日志条目: 如果成功:更新相应跟随者的 nextIndex 和 matchIndex 如果因为日志不一致而失败,减少 nextIndex 重试

  • 如果存在一个满足 N > commitIndex 的 N,并且大多数的matchIndex[i] ≥ N 成立,并且 ` log[N].term == currentTerm 成立,那么令 commitIndex` 等于这个 N

4. 日志压缩

中文论文“日志压缩”

因为这这块功能不是核心功能,暂时不考虑实现,后面再说 :)

  1. 快照的设计
  2. 快照的基础思想

参考

英文 paper pdf 地址

Raft paper 中文翻译 —— 寻找一种易于理解的一致性算法(扩展版)

Raft 作者讲解视频

Raft 作者讲解视频对应的 PPT

一个简单的讲解 Raft 协议的动画