raft

raft 一致性协议

reference

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

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

###简介

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]

2. 1. apply: 上述行为其实就是 apply 一个日志，apply 是一个将日志中的 command 应用到状态机上的操作.(大多数用法不太需要状态机这个东西， 所以 apply 就可以是更新内存中的值，然后写一下快照）。

3. 如果 rpc 请求和相应中的任期大于当前任期， 升级为大任期，并且转化为 follower 身份并设置 votedFor=-1

Follwers:

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

Candidates

1. 追随者刚刚变成竞选者时：
2. 1. 增加 currentTerm
   2. 投票给自己，
   3. 向所有服务器发送 RequestVote 请求
   4. 重置选举超时时间
3. 竞选者的结局：
4. 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。