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

测试通过:655922242.jpg

提示

  • faithfully following Figure 2!
  • 反复、认真阅读Students' Guide to Raft,Figure 2屏蔽了太多实现细节,会引导读者理所当然地加入自己的想法,而做不到第一步,所以学生指导手册很重要!

Raft的五大特性

  1. Election Safety :一个时期最多一个leader。
  2. Leader Append-Only : leader只添加日志,不重写或删除日志。
  3. Log Matching : 当两份日志在同一个index上的term相同时,index之前的日志也相同。
  4. Leader Completeness :如果一个日志条目在某个时期被提交,那么这个日志条目会出现在往后的term的leader日志里面。
  5. 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.
  1. 收到当前leader的AppendEntries RPC或者同意给candidate投票时,才重置定时器。
  2. 当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在论文给出解释。

  1. 如果两份日志最后条目的任期号不同,那么任期号更大的日志更新。
  2. 如果两份日志最后条目的任期号相同,那么日志更长的更新。

选举代码如下

    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(&currentTerm) != 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。

评论

暂无评论