raft study

Paper

• 英文
• 中文

名词

• replicated state machine
• 拜占庭问题
• apply a log, commit a lo: commted的log最终会反应到每个server

和其他一致性算法的区别

• Strong Leader
• Leader election : 引用随机的timer,避免竞选冲突
• Membership changes : cluster中添加、删除时候，使用new joint consensus来过渡

其他replicated state machine例子

• Chubby
• ZooKeeper

一致性算法需要满足的特点

• Safty(永远不返回不一致结果): 在非拜占庭条件下，包括network delay,partitions等等
• Available : 当多数server可用时，即可用

raft从3个角度分解一致性问题

• Leader election
• Log replication
• Safty : 每个server run log以后一定保证状态机一致

三个状态

• Leader
• Follower

• Candidate

  
  image.png

Term

image.png

Term起到了logical clock的作用

Timeout

• Election timout: 150~300ms, timeout后，从Follower=>Candidate
• Heartbeat timeout

RPC

• RequestVote
• AppendEntries
• InstallSnapshot

Leader election

• Leader周期的发送不带log的AppendEntries RPC
• Follower如果在Heartbeat timeout后没收到心跳，follower转换成candidate
  1. term自增
  2. 为自己投一票
  3. 发送RequestVoteRPC给其他server
• Follower遇到下列状况变换状态
  1. 赢得竞选
  2. 其他人赢得竞选
  3. 一定时间内没有人赢得竞选

Follower赢得选票

Majority rule保证在某一个term中，最多有一个candidate赢得竞选

其他人赢得竞选

1. Follower接到>=的term的AppendEntries，立刻从candidate=>Follower
2. Follower接到<的term的AppendEntries，立刻reject请求

没有人赢得竞选

1. Election timout后，会开启新的一轮term,并发起竞选
2. Election timout对于每个server是随机值，避免冲突（150~300ms）

Raft guarantees

image.png

Log内容

1. 状态机的更新值
2. Term号(用来检测是否一致)

3. 每条Log以log index标识

   
   image.png

Log replication

1. Client发到Leader端，leader先自己写log
2. Leader发送带log的AppendEntries
3. the leader applies the entry to its state machine and returns the result of that execution to the client

Leader决定何时apply log entry

1. 这个log entry的状态被称作committed。
2. committed过的log entry，一定会反应到所有状态机上。
3. Leader创建的log entry一旦有majority的数量的复制，就可以commit了。
4. 上图中log1~7都已经commmited了
5. leader记录着下一条要被commit的log entry,在以后的AppendEntries会带上这个值。
6. follower会根据这个值，来apply相应的log entry
7. commit会保证前面log entry也commit，如果不满足，先commit前面的log entry

Leader端保存的变量

• 自己下一个要commit的log的位置
• 其他Follower要复制的nextIndex

Log Matching Property

1. 有相同的index和term的两个log entry,存储相同命令

2. 有相同的index和term的两个log entry,这之前内容一定一样

   
   image.png

AppendEntries Consistency Check

AppendEntries发送log的同时，会带着上一条log的index和term，如果follower不能找到index和term相同的log,则reject。reject后，Lead会试图发一个带着前一个log的AppendEntries，如果再失败，就再找更前一个log

image.png
Leader向follower发送AppendEntries返回成功，一定说明这个append操作log entry(包括之前的)一定严格和Leader的log一致。

如何解决log不一致

1. 当leader没有复制完所有log entry时候，其他follower竞选成新的leader后，会产生log 不一致问题
2. Leader端为每个follower维护一个position,nextIndex。初始时候，每个follower的这个值设置为Leader的最新log entry position。每次发送AppendEntries的时候，用这个position的log entry。如果被reject了，则减一再试。
3. AppendEntries Consistency Check会保证AppendEntries的log entry(包括之前)一定和leader一致
4. Leader一定不会删除、修改自己的log，只会append log

Leader Completeness Property

• Log一旦commit, 以后的Leader一定有这条log
• 有imcomplted log的Server不能当选Leader

Election restriction

• Candidate发送RquestVote给其他server时候，会发送其最近的log，如果这个log比server的还晚，server会拒绝掉这个RPC
• RquestVote会携带lastLogIndex，
• 先判断lastLogTerm，看谁的term最新。如果都一样，再继续看lastLogIndex，看谁的最长。
  image.png

如何commit

• 对于log entry是自己任期内的term，达到majority就可以commit
• 对于log entry不是自己任期内的term，不去判断是否达到majority
• 当前任期的term的log entry被commit，一定保证以前任期的log entry被commit
• 每个server都会有 commitIndex,如果AppendEntries中的 leaderCommit > commitIndex，则更新commitIndex， set commitIndex =min(leaders commit, index of last new entry)
• 每个server都会有 lastApplied, Server会不停的判断commitIndex > lastApplied，一旦为真就去apply log

结论

• 在某个term里，最多只有一个Leader
• Leader绝不修改自己的log,只是Append
• Follower的log和Leader不一致时，被强迫overwrite成和leader一致
• Commmit过的log，不管怎么切换Leader,都一定在Leader的log里

具体规则

image.png image.png image.png image.png

动画演示

https://raft.github.io/
http://thesecretlivesofdata.com/raft/
http://kanaka.github.io/raft.js/

https://www.zhihu.com/question/54997169
https://www.zhihu.com/question/29597104/answer/128443409