Lecture7 Raft(2)
讲义:http://nil.csail.mit.edu/6.824/2020/notes/l-raft2.txt
视频:https://www.bilibili.com/video/BV1qk4y197bB?p=7
参考笔记:https://mit-public-courses-cn-translatio.gitbook.io/mit6-824/lecture-07-raft2
对应raft论文第七章至结束
选举约束
Raft的核心思想:在选举时保证成为leader的节点一定有最新的committed日志(而不是最长的)
候选人最后一条Log条目的任期号大于本地最后一条Log条目的任期号;
或者,候选人最后一条Log条目的任期号等于本地最后一条Log条目的任期号,且候选人的Log记录长度大于等于本地Log记录的长度
快速回退
如果Log有冲突,Leader每次会回退一条Log条目。但如果冲突较多,开销会很大,这里Morris教授总结了几个快速回退的方法。
回顾:AppendEntriesRPC的请求体中会带有
previousTerm
和previousIndex
可以让Follower在回复Leader的AppendEntries消息中,携带3个额外的信息,来加速日志的恢复。这里的回复是指,Follower因为Log信息不匹配,拒绝了Leader的AppendEntries之后的回复。这里的三个信息是指:
- XTerm:这个是Follower中与Leader冲突的Log对应的任期号;如果Follower在对应位置没有Log,那么这里会返回 -1。
- XIndex:这个是Follower中,对应任期号为XTerm的第一条Log条目的槽位号。
- XLen:如果Follower在对应位置没有Log,那么XTerm会返回-1,XLen表示Follower log的长度。
用快速回退来解决上述三个case
case1:Follower(S1)会返回XTerm=5,XIndex=2。Leader(S2)发现自己没有任期5的日志,它会将自己本地记录的,S1的nextIndex设置到XIndex。
case2:Follower(S1)会返回XTerm=4,XIndex=1。Leader(S2)发现自己其实有任期4的日志,它会将自己本地记录的S1的nextIndex设置到本地在XTerm位置的最后一条Log条目后面,也就是槽位2。
case3:Follower(S1)会返回XTerm=-1,XLen=1。Leader(S2)会将自己本地记录的S1的nextIndex设置到本地在XLen+1的位置,也就是槽位2。
持久化
Raft server 中有些数据被标记为持久化的(Persistent),有些信息被标记为非持久化的(Volatile)
Persistent
- log
- currentTerm
- votedFor:为了保证在每个term只投票给一位candidate
日志压缩和快照
InstallSnapshotRPC
线性一致性Linearizability
什么是正确的?
参考:https://tanxinyu.work/consistency-and-consensus/
- 例一:
满足线性一致性
- 例二:
存在环,不满足线性一致性