MIT 6.824 Lab2 Raft Part C

Project Overview

Complete the functions persist() and readPersist() in raft.go by adding code to save and restore persistent state.
Insert calls to persist() at the points where your implementation changes persistent state.
Optimize backing up nextIndex by more than one entry at a time.

Implementation

This part is relatively simple.
Just write the code directly.

Complete functions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func (rf *Raft) persist() {
	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 []LogEntry
	if d.Decode(&currentTerm) != nil || d.Decode(&votedFor) != nil || d.Decode(&log) != nil {
		// ignore error
		return
	} else {
		rf.currentTerm = currentTerm
		rf.votedFor = votedFor
		rf.log = log
	}
}

Insert Method Calls

As currentTerm, votedFor and log[] are needed to be stored persistently, the moments after they are changed, insert rf.persist().

Note that the change of state does not need a rf.persist()

For instance:

1
2
3
	rf.currentTerm++
	rf.votedFor = rf.me
	rf.persist()

Optimize Decreasing `nextIndex`

The follower is supposed to check what is the nextIndex and reply to the leader during a term-conflicted AppendEntries RPC.

We need to add a property to AppendEntriesReply:

1
2
	// 2C page 7-8 gray line optimization
	FirstIndexOfConflictingTerm int

Figure out what is the nextIndex:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
		if rf.log[args.PrevLogIndex-1].Term != args.PrevLogTerm {
			reply.Success = false
			rf.log = rf.log[:args.PrevLogIndex]
			for i := args.PrevLogIndex; i > 0; i-- {
				if rf.log[i-1].Term != args.PrevLogTerm {
					reply.FirstIndexOfConflictingTerm = i
				} else {
					break
				}
			}
			rf.persist()
			return
		}

The leader update nextIndex[server]:

1
2
3
4
5
6
7
8
			} else {
				if reply.FirstIndexOfConflictingTerm != -1 {
					rf.nextIndex[server] = reply.FirstIndexOfConflictingTerm
				} else {
					if rf.nextIndex[server] > 1 {
						rf.nextIndex[server]--
					}
				}

Trick

If you can’t pass Figure8 (unreliable) tests, you can speed up heartbeat check.

1
		heartbeatInterval:      10 * time.Millisecond,

Test

Passed.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
$ go test -run 2C
Test (2C): basic persistence ...
  ... Passed --   3.4  3  450  115818    6
Test (2C): more persistence ...
  ... Passed --  15.2  5 5987 1389550   16
Test (2C): partitioned leader and one follower crash, leader restarts ...
  ... Passed --   1.4  3  132   36137    4
Test (2C): Figure 8 ...
  ... Passed --  28.7  5 3184  737719   43
Test (2C): unreliable agreement ...
  ... Passed --   1.4  5 1400  463965  246
Test (2C): Figure 8 (unreliable) ...
  ... Passed --  28.1  5 25588 36634913   88
Test (2C): churn ...
  ... Passed --  19.0  5 13428 19540624 1391
Test (2C): unreliable churn ...
  ... Passed --  22.7  5 11808 14376116  957
PASS
ok  	github.com/alioth4j/6.824/src/raft	119.893s

Conclusion

Lab2 Raft is done. It is not only a lab to improve code implementing ability, but also a process of understanding of the Raft algorithm.

In summary, Lab2 is a pivotal step in bridging the gap between abstract algorithmic concepts and practival implementation.

Raft is seeking its future, so do I.