raft 一致性协议

reference

  1. quick learn http://thesecretlivesofdata.com/raft/

  2. home page and visualization https://raft.github.io/

  3. names and princepleimg

理解

简介

raft是由Diego Ongaro and John Ousterhout Stanford University 在一篇名为In Search of an Understandable Consensus Algorithm.从名字中可以看出, 这是一个一致性共识算法并且是一个简单的便于理解的版本.tradeoff更倾向于便于理解.为了达到这个目的, 作者给出了一些名词和一套选举人被选举人这样熟悉的模型.

  1. service 身份有三种: 追随者, 竞选者, 领导人.

  2. 状态变化: 追随者 => 候选人 => 领导人 => 追随者

​ => 追随者

状态

比较稳定状态(也会变)

  1. term: 每个服务器都记录一个任期, 用来保持一致的. 追随者每次开始选举就要使得自己的任期状态+1

  2. voted for: 候选人编号, 用于表示自己给谁投票了, 没有投票为NULL.

  3. log: 日志实体, 包含状态机要执行的command

经常变化的状态

  1. 索引 index: 日志的索引, 从1开始

  2. commit index: 最高被提交的索引, 从0开始

  3. last applied: 最高被状态机执行索引.

领导人每次都要初始化的变量:

  1. nextIndex[]: 保存每一个follower 下一次要接受的日志的索引.初始化是领导人最后一个索引+1.
  2. matchIndex[]: 保存每一个follower, 已经成功复制的最高索引位.初始化是0

原则

ALL:

  1. 对于所有节点, commitIndex > lastApplied 时,执行 log[lastApplied]

    1. apply: 上述行为其实就是 apply 一个日志,apply 是一个将日志中的 command 应用到状态机上的操作.(大多数用法不太需要状态机这个东西, 所以 apply 就可以是更新内存中的值,然后写一下快照)。
  2. 如果 rpc 请求和相应中的任期大于当前任期, 升级为大任期,并且转化为 follower 身份并设置 votedFor=-1

Follwers:

  1. 对于追随者,要回复竞选者和领导人的 RPC 请求,如果一段时间(选举超时时间)后还没有收到leader 或者候选人的请求投票请求,那么就转化身份为竞选者,参与竞选

Candidates

  1. 追随者刚刚变成竞选者时:
    1. 增加 currentTerm
    2. 投票给自己,
    3. 向所有服务器发送 RequestVote 请求
    4. 重置选举超时时间
  2. 竞选者的结局:
    1. 获得大多数人支持转化为 leader
    2. 收到其他 leader 发来的 append enties rpc 则转化为 follower
    3. 如果选举超时时间到达,则开始一次新的选举。

Leaders:

  1. 竞选者成为 leader 时,给其他节点发送空的append enties rpc(心跳),然后重复发送,目的只是阻止竞选超时
  2. 当收到客户端命令时,将条目插入到本地日志。如果该条目稍后,(异步)被 applied 了(不是 commit)就报告客户端。
  3. 当自己的 logIndex >= nextIndex 就发送 append enties RPC 日志是从 nextIndex 对应的那条.
    1. 如果成功,更新记录中的对应节点 nextindex 和 matchindex,
    2. 如果因为日志冲突而失败,则nextIndex-1
  4. 有一个 Index > commitIndex, 而且从 matchIndex 中发现大多数值都大于这个索引, 并且这个索引对应的日志的任期和当前的任期,那么就 commit 这个 log — 设置 commitIndex = Index。