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

由领导人负责调用来复制日志指令,也会用作心跳

3. 请求投票 RPC
  1. 参数详情

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

  1. 接收者实现
    1. 如果term < currentTerm返回 false
    2. 如果 votedFor 为空或者就是 candidateId,并且候选人的日志至少和自己一样新,那么就投票给他
4. 所有服务器需遵守的规则
  1. 所有服务器
  1. 跟随者
  1. 候选人
  1. 领导人
    • 一旦成为领导人:发送空的附加日志 RPC(心跳)给其他所有的服务器;在一定的空余时间之后不停的重复发送,以阻止跟随者超时

4. 日志压缩

中文论文“日志压缩”

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

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

参考

英文 paper pdf 地址

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

Raft 作者讲解视频

Raft 作者讲解视频对应的 PPT

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

EOF