MIT 6.824 lab2 Raft
话不多说,先做下Raft的学习笔记吧
学习资料
论文:Raft
中文翻译:Raft 一致性算法论文译文
动画解释:Raft动画
我的代码:MIT6.824
Raft理解
Raft最重要的内容就是论文的Figure2,如下:
读懂这张图,就能大概理解Raft的具体流程,我开头读paper的时候以为弄懂了,但是真的做lab的时候发现又不是那么理解,有非常多的地方很晕。更多细节还要参考paper后面的内容。
state
从state这个图说起吧,首先就是前三个参数
-
currentTerm
是当前的轮数,只有当一个新开始一轮选举的时候,currentTerm
才会加1。下面简称Term
当Candidate
在一轮中,没有变成Leader
也没有变回Follower
的时候,它开始新一轮选举的时候同样会把Term
加1。 -
votedFor
是你投票给谁了,可以想到,这个值应该在某个情况下被重置,因为在新的一次选举中,初始状态下votedFor
必须是被重置的。可以看图中说明,votedFor
表示的是当前轮中被选的Candidate
,我们知道Raft的两个机器在交互后,Term
较小的那台机器的Term
会修改成较大的那个,所以Term
发生变化的时候,votedFor
就需要被重置。也就是当一个rpc
来的时候,如果Sender
的Term
更大,Receiver
的Term
和votedFor
都要修改。 -
log
是一个结构体,里面存放着每个log entry
的Term
和Command
这三个参数都是需要被持久化到一个稳定的存储容器中,比如disk
,但是lab中没用用到disk
,我们主要是把这三个参数储存到一个persister
结构中。
图中下面是两个易变的参数,比较好理解,就不多说了,但是其实还需要记录一个参数state
,表示当前机器的身份。
这三个参数不需要持久化。因为当一个机器重启后,只要它的Term
和log
都在,如果它的Term
更新,它就可以当选Leader
,或者是Follower
,然后通过AppendEntries RPC
来提升自己的commitIndex
,以及会有lastApplied
会多次应用log
,只需要检测幂等性就可以防止多次apply
。
还有两个只有Leader
才有的参数nextIndex
和matchIndex
,只有在刚成为Leader
以及AppendEntries RPC
成功的时候才会修改。
RequestVote RPC
这是Candidate
才会发出的RPC
,目的是为了成为Leader
,几个参数就如字面意思那样。
-
lastLogIndex
就是Candidate
当前log
中的最后一个的Index
-
lastLogTerm
就是最后一个log
的Term
这个RPC
的判断条件不复杂,当Candidate
的Term
或者是log
不是最新的情况下会被拒绝,怎么才算最新的log
呢?
就是Candidate
最后一个log
的Term
比别人的最后一个Term
都要大,或者是最后一个Term
相同时,Candidate
的log
比别人的都要长。这是论文5.4部分讲到的,但是论文里表述不清楚,原文说:
Raft uses the voting process to prevent a candidate from winning an election unless its log contains all committed entries.
其实论文中说的没有错误,我们可以思考一下,最新最长的log
是否意味着就是拥有所有commit log entries
的。
在Leader
没有挂之前,肯定有多数派拥有最新最长的log
,当Leader
挂了之后,因为要满足拥有所有commit log entries
,所以肯定是有最新最长log
的机器当选Leader
,所以这个说法并没有错误。
AppendEntries RPC
这个是Leader
发给其他机器,用来阻止其他机器进行选举以及同步log
的RPC
,主要参数比较重要的是:
-
pervLogIndex
记录的是需要发到Follower
的log entries
的前面一个,就是nextIndex[i]-1
,用来和Follower
的log
比较,确定返回true or false
-
entries[]
记录的是prevLogIndex
后面一个到最后的log entries
,就是log[nextIndex[i]:]
,当prevLogIndex
匹配成功时,就可以直接把entries[] append
到Follower
的log
后面
返回的参数里需要返回一个nextIndex
用于优化,优化在论文第7页底部到第8页顶部有提到,后续再分析。
AppendEntries RPC
的规则其实弄清楚了也一点都不复杂,就是在Leader Term
较小或者是prevLogTerm
不匹配的时候返回false
,匹配的时候把entries[]
放到最后并且修改commitIndex
。
这个修改commitIndex
其实不是在append entries[]
的这个RPC
里做的,因为先要log
匹配,append log
,然后Leader
修改对应Follower
的nextIndex
和matchIndex
,然后通过后面一个增加commitIndex
的规则来增加Leader
自己的commitIndex
,然后下一个RPC
的时候因为LeaderCommit
变大了,Follower
根据规则来变化自己的commitIdex
。
Rules for Servers
这里面讲述了其他一些运行的规则,主要有几个需要前面没有提到,需要注意:
- 当
commitIndex > lastApplied
的时候,需要把log[lastApplied]
应用到状态机上,这个操作应该要和接收rpc
,发送rpc
的操作并行,所以我们可以额外开一个goroutine,专门用来接收操作这个情况。 - 所有的交互中,机器都要把
Term
修改为较大的那个值,并且Term
较小的那个机器身份会变为Follower
,重置votedFor
-
Candidate
如果在一轮选举中没有当选,会重新开始一轮选举,并且Term
增加1 -
AppendEntries RPC
成功的时候修改nextIndex
和matchIndex
,失败的时候nextIndex
会减小,通过后面的优化可以加快减小速度。 -
Leader
修改commitIndex
的方法是在每轮广播AppendEntries RPC
之前,扫描所有Follower
的matchIndex
,对于一个index
,如果matchIndex[i]>=index
的个数超过一半,并且log[index].term == currentTerm
,就有commitIndex = index
论文细节
Raft的特性
- 每个
Term
最多选出一个Leader
-
Leader log
只会append
不会被删除 - 如果两个
log entry
有同样的index
和term
,那么它们必定相同,并且它们之前的所有的log entry
都相同
上面第三点为啥能够保证呢?为啥不可能是同一个term
的但是不同命令的log
呢?
因为Leader
要把当前Term
的log
复制给其他机器,也就是去找一个匹配的点,然后把这个点后的都复制到其他机器,只要确定那个匹配的点之前的都相同,那后面的肯定相同,这个匹配的点肯定也是之前一个Leader
要复制给其他机器,再往前找一个匹配点这么做的。这样就可以递推到开头都是空的log
,就能说明肯定是正确的。
回退优化
这个优化是优化当log entry
不匹配的时候,nextIndex
递减太慢的情况。
For example, when rejecting an AppendEntries request, the follower can include the term of the conflicting entry and the first index it stores for that term. With this information, the leader can decrement nextIndex to bypass all of the conflicting entries in that term; one AppendEntries RPC will be required for each term with conflicting entries, rather than one RPC per entry.
原文中是这么描述这个优化的,意思就是当不匹配的时候,reply
中附带冲突的term
中的第一个log
的index
,这样Leader
下次发送RPC
就可以跳过这个term
。
虽然不能证明这个冲突的term
中的log
都是不正确的,但是可以提高效率。因为每次只要比较一个term
里的最后一个log
是否匹配,如果匹配,说明前面的term
都匹配了,就可以直接复制,减少RPC
次数
Commit entries from previous terms
只有当前term
里的log entry
可以被commit
,之前term
里没有commit
的log
只能通过后面term
的log commit
来commit
了
当一个term
的log commit
了,前面所有term
的log
都被commit
了,因为当前term
的log
复制到多数派,说明前面term
的log
也会被复制到多数派,间接的commit
了
为什么要这么间接的commit
呢?因为你很难判断之前term
中被复制到多个机器上的log
是否已经被commit
了,为了简化问题,所以就使用了这样的间接commit
的方法
lab2
lab2主要分成了三部分,先完成选举的实现,然后实现log
的复制和应用,最后完成状态的持久化。
大部分细节上面说的比较详细了,基本实现的条件都说了,我开头不太会写的部分是如何写这个election timeout
部分,后来知道了这边可以使用golang
中的select
语法,开一个channel
专门监听是否收到RequestVote RPC
,一个channel
专门监听是否收到AppendEntries RPC
,一个channel
专门监听是否收到成为Leader
的消息,同时可以用time.After
语法来实现timeout
,这个语法会在一段时间后返回一个<-chan Time
类型的值,下面是After
函数的定义:
func After(d Duration) <-chan Time
这样我们就可以很容易的实现出,对于每一个机器,开一个goroutine
,对应它是某个身份的时候,监听相关channel
的消息,或者是超时,或者是执行广播RPC
的操作。
因为log apply
到状态机的操作和处理RPC
应该是并行的,所以我们可以给每个机器再开一个goroutine
来监听相关channel
是否可以apply log
raft.go代码
这个代码极为难调,本来手动跑了几轮都通过了,但是发现跑个十几轮就会出错,然后强迫症强行debug,发现了有很多很坑的地方,主要思路应该都很熟悉了,反而不是最关键的错误。
- 首先是锁的问题,我对锁的使用非常不熟练,就各种yy怎么加锁,后来打算凡是在读或者写到共享变量的地方都加锁
- 其次是
timeout
的实现,由于这里使用了channel
来实现timeout
,很容易发生,1
变成candidate
给2
发rpc
,2
加锁,2 timeout
,卡在获取锁那边,然后2
给1
投票,term
变成和1
的term
一样大,然后2
的vote channel
里放了一个信息,表明接收到rpc
,然后2
解锁。这时候就出问题了,首先是2
的channel
里有信息了,但是2
已经timeout
了,这时候2
就会也变成candidate
,然后term
比1
的term
还大,并且channel
里还保留了一个信息,这时候就要做判断,如果channel
里有东西,就清空并且不变成candidate
。每次term
发生变化的时候或者是channel
收到信息的之后,都需要清空appendentry rpc
和request vote rpc
的channel
,这样才能保证不出现接受了rpc
还变成leader
或者candidate
的问题。 - 还有许多地方比如收到了
rpc reply
的时候要判断这个reply
是不是本次的,以及自己当前的身份是否正确,否则都可能会出错,凡是读取到当前rf
的变量的地方都加锁,并且不要发生死锁的话应该就都行。 - 测试的时候使用并行脚本来测试效果更佳:
#!/bin/bash
do_test_all(){
for ((i=0;i<100;i++))
do
go test > aaa$1_$i.log
done
}
do_test_all 0 &
do_test_all 1 &
do_test_all 2 &
do_test_all 3 &
do_test_all 4 &
上一篇: MIT 6.824 lab1
下一篇: 分布式事务解决方案
推荐阅读
-
MIT-6.824 Lab 3: Fault-tolerant Key/Value Service
-
MIT6.824 远程过程调用RPC使用
-
MIT-6.828 Lab2实验报告
-
MIT 6.824 Lab1 MapReduce
-
MIT6.824 Lab1 MapReduce
-
MIT 6.824 2020 分布式系统 Lab1 Mapreduce 实验思路和代码分析
-
MIT 6.824 lab1: mapreduce 学习总结
-
[MIT 6.824: Distributed Systems] LEC 1: Introduction之Preparation
-
MIT6.824 lab1 MapReduce 2018版本Part1 Map/Reduce input and output
-
MIT6.824 mapReduce lab1 reduce过程实现