MIT6.824 Raft实现
文章目录
概述
本文是与MIT6.824 Lab2 Raft的实现有关。但笔者并不想按照Part A/B/C 来分别给出对应的代码实现,而是与figure2一一对应,给出实现的思路。实现的方式有很多种,在实现过程中,每个人遇到的bug与处理方式也各有不同。希望笔者的实现,对于读者修改代码有所帮助。笔者代码已全部通过测试,并且对于Part B的Backup和Part C的Figure8Unreliable,均测试300次,无错。测试脚本如下:
#!/bin/bash
for ((a=1, b=100; a<=300; a++))
do
echo ".............................index = $a"
#go test -run 2B > ./test_res/test_$a.txt
go test -run TestFigure8Unreliable2C > ./test_res/test_$a.txt
done
测试通过:
提示
- faithfully following Figure 2!
- 反复、认真阅读Students' Guide to Raft,Figure 2屏蔽了太多实现细节,会引导读者理所当然地加入自己的想法,而做不到第一步,所以学生指导手册很重要!
Raft的五大特性
- Election Safety :一个时期最多一个leader。
- Leader Append-Only : leader只添加日志,不重写或删除日志。
- Log Matching : 当两份日志在同一个index上的term相同时,index之前的日志也相同。
- Leader Completeness :如果一个日志条目在某个时期被提交,那么这个日志条目会出现在往后的term的leader日志里面。
- State Machine Safety :如果一个服务器apply了某个index位置的日志条目,那么其他的服务器在同一个index上不能apply其他的日志。
代码实现
整体设计,整体代码主要通过channel+timer定时器,去响应事件的发生。
func (rf *Raft) startLoop() {
for {
select {
case <- rf.deadChan: // 如果调用Kill()函数,会发送一个chan给主循环,然后主循环退出。
return
default:
switch rf.state { // 0 follower / 1 candidate / 2 leader
case 0:
select {
case flag := <- rf.appendChan: // 1
if flag {
rf.resetTimer()
}
case flag := <- rf.voteChan: // 2
if flag {
rf.resetTimer()
}
case <- rf.timer.C:
rf.changeState(1)
rf.startElection()
}
case 1:
select {
case flag := <- rf.appendChan: // 3
if flag {
rf.changeState(0)
rf.resetTimer()
}
case <- rf.timer.C:
rf.startElection()
default:
if rf.votedCount > len(rf.peers)/2 {
rf.mu.Lock()
for i, _ := range rf.peers {
if i != rf.me {
rf.nextIndex[i] = rf.log[len(rf.log)-1].Index+1
rf.matchIndex[i] = 0
}
}
rf.changeState(2)
rf.mu.Unlock()
}
}
case 2:
rf.broadcastAppendEntries(rf.currentTerm)
go rf.updateCommited() // 提交
time.Sleep(HeartbeatInterval) // HeartbeatInterval 为100毫秒
}
}
}
}
注释中有三个点需要注意的,笔者分别标注了1、2、3。先来看Figure2原文
If eletion timeout elapses without receiving AppendEntries RPC from current leader or granting vote to candidate: convert to candidate.
If AppendEntries RPC receiving from new leader: convert to follower.
- 收到当前leader的AppendEntries RPC或者同意给candidate投票时,才重置定时器。
- 当candidate收到来自新的leader的RPC时,才转换回follower。
这两个点很重要,笔者一开始实现以偏概全,只要收到RPC就重置了时间,结果测试300次Figure8Unreliable的时候出现少些fail to reach agreement的错误。
接着来看投票,RequestVote RPC。
type RequestVoteArgs struct {
Term int
CandidateId int
LastLogIndex int
LastLogTerm int
}
type RequestVoteReply struct {
Term int
VoteGranted bool
}
func (rf *Raft) RequestVote(args *RequestVoteArgs, reply *RequestVoteReply) {
rf.mu.Lock()
defer rf.mu.Unlock()
if args.Term < rf.currentTerm { // Reply false if term < currentTerm,并要返回当前term。
reply.Term = rf.currentTerm
reply.VoteGranted = false
rf.sendChannel(rf.voteChan, false)
return
} else if rf.currentTerm < args.Term { // 当收到更高的term的RPC,修改当前term,并重置投票。
rf.votedFor = -1
rf.currentTerm = args.Term
rf.persist()
rf.changeState(0)
}
if rf.votedFor == -1 || rf.votedFor == args.CandidateId {
if args.LastLogTerm > rf.log[len(rf.log)-1].Term ||
(args.LastLogTerm == rf.log[len(rf.log)-1].Term &&
args.LastLogIndex >= rf.log[len(rf.log)-1].Index) { // If votedFor is null or candidateId, and candidate's log is at least as up-to-date as receiver's log, grant vote
rf.votedFor = args.CandidateId
rf.persist()
reply.VoteGranted = true
reply.Term = -1
rf.sendChannel(rf.voteChan, true)
return
}
}
reply.VoteGranted = false
reply.Term = -1
rf.sendChannel(rf.voteChan, false)
}
up-to-date在论文给出解释。
- 如果两份日志最后条目的任期号不同,那么任期号更大的日志更新。
- 如果两份日志最后条目的任期号相同,那么日志更长的更新。
选举代码如下
rf.mu.Lock()
rf.currentTerm++ // Increment currentTerm
rf.votedFor = rf.me //vote for self
rf.mu.Unlock()
rf.persist()
rf.resetTimer() // Reset election timer
LastLogIndex := rf.log[len(rf.log)-1].Index
LastLogTerm := rf.log[len(rf.log)-1].Term
args := RequestVoteArgs{rf.currentTerm, rf.me, LastLogIndex, LastLogTerm}
rf.votedCount = 1 // 计算自己的票
// Send RequestVote RPCs to all other servers
for i, _ := range rf.peers {
if i != rf.me {
go func(server int) {
reply := RequestVoteReply{}
if rf.state == 1 && rf.sendRequestVote(server, &args, &reply){
rf.mu.Lock()
if rf.currentTerm == args.Term { // 1
if reply.VoteGranted { // 收到赞同票,票数加一
rf.votedCount += 1
} else {
if reply.Term != -1 { // 如果当前term小于reply的term,修改,并convert to follower
rf.currentTerm = reply.Term
rf.votedFor = -1
rf.persist()
rf.changeState(0)
}
}
}
rf.mu.Unlock()
}
}(i)
}
}
}
注释1很重要,笔者在debug(肉眼看print)的过程中,发现一种场景。3个serverA、B、C。B发起投票,A投赞同,C投反对。B重复投票几轮下来,B成了leader。两次投票中,假如A的投票回复延迟了,就会导致第二轮收到两个A的赞同票,从而B变成了leader。当然此错误与整体实现有关,如若读者有相同错误,可以借鉴。AppendEntries RPC和broadcastAppendEntries(广播RPC)。这两处代码与Figure2有些出入,主要对nextIndex做了优化。Figure2原文:
If AppendEntries fails because of log inconsistency: decrement nextIndex and matchIndex for follower
如果只是对nextIndex进行递减,Figure8Unreliable是通过不了的。具体优化可以看学生指导手册,我也会给出我的具体实现。
type AppendEntriesArgs struct {
Term int
LeaderId int
PrevLogIndex int
PrevLogTerm int
Entries []Entry
LeaderCommit int
}
type AppendEntriesReply struct {
Term int
Success bool
ConflictFirstIndex int // 冲突时期的第一个条目
ConflictTerm int // 冲突时期
}
func (rf *Raft) AppendEntries(args *AppendEntriesArgs, reply *AppendEntriesReply) {
rf.mu.Lock()
defer rf.mu.Unlock()
if args.Term < rf.currentTerm { // Reply false if term < curremtTerm
reply.Success = false
reply.Term = rf.currentTerm
rf.sendChannel(rf.appendChan, false)
return
}
if args.Term > rf.currentTerm {
rf.currentTerm = args.Term
rf.votedFor = -1
rf.changeState(0)
rf.persist()
}
// Reply false if log doesn't contain an entry at prevLogIndex whose term matches prevLogTerm.
if rf.log[len(rf.log)-1].Index < args.PrevLogIndex {
// If a follower does not have`prevLogIndex`in its log,
// it should return with`conflictIndex = len(log)`and`conflictTerm = None`
reply.ConflictFirstIndex = len(rf.log);
reply.ConflictTerm = -1
reply.Success = false
reply.Term = -1
rf.sendChannel(rf.appendChan, true)
return
}
if rf.log[len(rf.log)-1].Index >= args.PrevLogIndex && rf.log[args.PrevLogIndex].Term != args.PrevLogTerm {
// If a follower does have`prevLogIndex`in its log, but the term does not match,
// it should return`conflictTerm = log[prevLogIndex].Term`,
// and then search its log for the first index whose entry has term equal to`conflictTerm`.
reply.ConflictTerm = rf.log[args.PrevLogIndex].Term
reply.ConflictFirstIndex = args.PrevLogIndex
for i := reply.ConflictFirstIndex - 1; i >= 0; i-- {
if rf.log[i].Term != reply.ConflictTerm {
break
} else {
reply.ConflictFirstIndex -= 1
}
}
reply.Success = false
reply.Term = -1
rf.sendChannel(rf.appendChan, true)
return
}
// If an existing entry conflicts with a new one (same index but different terms), delete the existing entry and all that follow it
// 笔者的实现并不算忠于Figure2,但笔者实现默认了PrevLogIndex之后的日志都是冲突日志,可以删除。故并无什么问题。
if args.Entries != nil { // 如果心跳非空
// Append any new entries not already in log
rf.log = rf.log[:args.PrevLogIndex+1]
rf.log = append(rf.log, args.Entries...)
rf.persist()
}
// If leaderCommit > commitIndex, set commitIndex = min(leaderCommit, index of last new entry)
if args.LeaderCommit > rf.commitIndex {
if args.LeaderCommit <= rf.log[len(rf.log)-1].Index {
rf.commitIndex = args.LeaderCommit
} else {
rf.commitIndex = rf.log[len(rf.log)-1].Index
}
rf.updateApplied <- struct{}{} // If commitIndex > lastApplied,发送channel,具体实现之后给出。
}
reply.Success = true
reply.Term = -1
rf.sendChannel(rf.appendChan, true)
}
func (rf *Raft) broadcastAppendEntries(thisTerm int) {
for i, _ := range rf.peers {
if i != rf.me {
go func(i int, term int) {
args := &AppendEntriesArgs{}
reply := &AppendEntriesReply{}
args.Term = rf.currentTerm
args.LeaderId = rf.me
args.LeaderCommit = rf.commitIndex
args.PrevLogIndex = rf.log[rf.nextIndex[i]-1].Index
args.PrevLogTerm = rf.log[rf.nextIndex[i]-1].Term
args.Entries = nil
// If last log index >= nextIndex for a follower: send AppendEntries RPC with log entries starting at nextIndex
if rf.log[len(rf.log)-1].Index >= rf.nextIndex[i] {
args.Entries = rf.log[rf.nextIndex[i]:]
}
var ok bool
if args.Term == term { // 防止term发生变化后,还发送RPC
ok = rf.sendAppendEntries(i, args, reply)
}
if ok {
if reply.Term != -1 {
rf.mu.Lock()
rf.currentTerm = reply.Term
rf.votedFor = -1
rf.persist()
rf.changeState(0)
rf.mu.Unlock()
}
if rf.state == 2 {
rf.mu.Lock()
if reply.Success {
if args.Entries != nil {
// If successful :update nextIndex and matchIndex for follower
rf.nextIndex[i] = args.Entries[len(args.Entries)-1].Index+1
rf.matchIndex[i] = args.Entries[len(args.Entries)-1].Index
}
} else {
// If appendEntries fails because of log inconsistency: decrement nextIndex and retry
nextIndex := rf.nextIndex[i]
rf.nextIndex[i] = rf.getNextIndex(*reply, nextIndex)
}
rf.mu.Unlock()
}
}
}(i, thisTerm)
}
}
}
// If there exists an N such that N < commitIndex, a majority of matchIndex[i] >= N,and log[N].term == currentTerm: set
// commitIndex = N
func (rf *Raft) updateCommited() {
rf.mu.Lock()
defer rf.mu.Unlock()
if rf.state == 2 {
N := rf.commitIndex
for i := rf.commitIndex+1; i <= rf.log[len(rf.log)-1].Index; i++ {
cnt := 1
for j, _ := range rf.peers {
if j != rf.me {
if rf.matchIndex[j] >= i && rf.log[i].Term == rf.currentTerm {
cnt++
}
}
}
if cnt > len(rf.peers)/2 {
N = i
}
}
if N > rf.commitIndex {
rf.commitIndex = N
rf.updateApplied <- struct{}{}
}
}
}
// If commitIndex > lastApplied : increment lastApplied, apply log[lastApplied] to state machine
func (rf *Raft) updatelastApplied() {
for {
select {
case <- rf.updateApplied:
rf.mu.Lock()
for rf.lastApplied < rf.commitIndex {
rf.lastApplied++
msg := ApplyMsg{true, rf.log[rf.lastApplied].Command, rf.lastApplied}
rf.applyCh <- msg
}
rf.mu.Unlock()
}
}
}
最后是nextIndex的算法
func (rf *Raft) getNextIndex(reply AppendEntriesReply, nextIndex int) int {
if reply.ConflictTerm == -1 { // 当冲突位置没有日志的时候
nextIndex = reply.ConflictFirstIndex
} else {
conflictIndex := reply.ConflictFirstIndex
conflictTerm := rf.log[conflictIndex].Term
if conflictTerm == reply.ConflictTerm { // 在冲突的index, term相同,该term的最后一个Entry作为nextIndex
for i := conflictIndex+1; i < nextIndex; i++ {
if rf.log[i].Term != reply.ConflictTerm {
break
}
conflictIndex += 1
}
nextIndex = conflictIndex + 1
} else if conflictTerm > reply.ConflictTerm { // 在冲突的index, term > reply.ConflicTerm
for i := conflictIndex; i > 0; i-- { // 往前寻找,直到term == reply.ConflictTerm
if rf.log[i].Term == reply.ConflictTerm {
break
}
conflictIndex -= 1
}
if conflictIndex == 0 { // 如果日志没有reply.ConflictTerm
nextIndex = reply.ConflictFirstIndex
} else {
nextIndex = conflictIndex+1
}
} else { // conflictTerm < reply.ConflictTerm,并且必须往前搜索,所以一定找不到任期相等的entry
nextIndex = reply.ConflictFirstIndex
}
}
return nextIndex
}
对于Election Safety,我们要确保只有改变term的时候,才能改变votedFor,重置投票。
lab2Part C的实现很简单,只要currentTerm, votedFor, log,任何一个发生变化,都需要持久化。
剩余代码
func (rf *Raft) persist() {
// Your code here (2C).
w := new(bytes.Buffer)
e := labgob.NewEncoder(w)
e.Encode(rf.currentTerm)
e.Encode(rf.votedFor)
e.Encode(rf.log)
data := w.Bytes()
rf.persister.SaveRaftState(data)
}
func (rf *Raft) readPersist(data []byte) {
if data == nil || len(data) < 1 { // bootstrap without any state?
return
}
r := bytes.NewBuffer(data)
d := labgob.NewDecoder(r)
var currentTerm int
var votedFor int
var log []Entry
if d.Decode(¤tTerm) != nil ||
d.Decode(&votedFor) != nil ||
d.Decode(&log) != nil {
DPrintf("decode error")
return
} else {
rf.currentTerm = currentTerm
rf.votedFor = votedFor
rf.log = log
}
}
func (rf *Raft) sendChannel(channel chan bool, flag bool) {
go func() {
channel <- flag
}()
}
func (rf *Raft) Start(command interface{}) (int, int, bool) {
index := -1
term := -1
isLeader := true
// Your code here (2B).
rf.mu.Lock()
term, isLeader = rf.GetState()
if isLeader {
index = rf.log[len(rf.log)-1].Index+1
newLog := Entry{command, term, index}
rf.log = append(rf.log, newLog)
rf.persist()
}
rf.mu.Unlock()
return index, term, isLeader
}
func (rf *Raft) Kill() {
rf.deadChan <- struct{}{}
rf.deadChan <- struct{}{}
}
func (rf *Raft) changeState(nState int) {
rf.state = nState
}
func (rf *Raft) resetTimer() {
rf.timer.Reset(randTimeDuration(ElectionTimeoutLower, ElectionTimeoutUpper))
}
func randTimeDuration(lower, upper time.Duration) time.Duration {
num := rand.Int63n(upper.Nanoseconds()-lower.Nanoseconds()) + lower.Nanoseconds()
return time.Duration(num) * time.Nanosecond
}
func Make(peers []*labrpc.ClientEnd, me int,
persister *Persister, applyCh chan ApplyMsg) *Raft {
rf := &Raft{}
rf.peers = peers
rf.persister = persister
rf.me = me
// Your initialization code here (2A, 2B, 2C).
rf.applyCh = applyCh
rf.currentTerm = 0
rf.votedFor = -1
rf.state = 0
first := Entry{nil, 0, 0}
rf.log = append(rf.log, first)
rf.commitIndex = 0
rf.lastApplied = 0
rf.timer = time.NewTimer(randTimeDuration(ElectionTimeoutLower, ElectionTimeoutUpper))
rf.voteChan = make(chan bool)
rf.deadChan = make(chan struct{},2)
rf.appendChan = make(chan bool)
rf.updateApplied = make(chan struct{})
for i := 0; i < len(rf.peers); i++ {
rf.nextIndex = append(rf.nextIndex, 0)
rf.matchIndex = append(rf.matchIndex, 0)
}
// initialize from state persisted before a crash
rf.readPersist(persister.ReadRaftState())
go rf.startLoop()
go rf.updatelastApplied()
return rf
}
不过一千人有一千种实现方法,遇到的问题也各有不同,良好的设计能事半功倍。用来调试,思考的时间远多于写代码的时间。
在整个过程中,应不断提醒自己faithfully following Figure 2, 和反复阅读Students' Guide to Raft。
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论