介绍

对Raft Figure2 中需要持久化的字段进行保存。

  • 完成persist()和readPersist()函数，编码方式参照注释
  • 优化nextIndex[]回退方式，否则无法通过所有测试

提示:

  • 需要持久化的部分包括currentTerm、votedFor、log。
  • 有关nextIndex[]回退优化

逻辑如下：

  1. 若 follower 没有 prevLogIndex 处的日志，则直接置 conflictIndex = len(log)，conflictTerm = None；
  • leader 收到返回体后，肯定找不到对应的 term，则设置nextIndex = conflictIndex；
  • 其实就是 leader 对应的 nextIndex 直接回退到该 follower 的日志条目末尾处，因为 prevLogIndex 超前了
  1. 若 follower 有 prevLogIndex 处的日志，但是 term 不匹配；则设置 conlictTerm为 prevLogIndex 处的 term，且肯定可以找到日志中该 term出现的第一个日志条目的下标，并置conflictIndex = firstIndexWithTerm；
  • leader 收到返回体后，有可能找不到对应的 term，即 leader 和 follower 在conflictIndex处以及之后的日志都有冲突，都不能要了，直接置nextIndex = conflictIndex
  • 若找到了对应的term，则找到对应term出现的最后一个日志条目的下一个日志条目，即置nextIndex = lastIndexWithTerm+1；这里其实是默认了若 leader 和 follower 同时拥有该 term 的日志，则不会有冲突，直接取下一个 term 作为日志发起就好，是源自于 5.4 safety 的安全性保证

如果还有冲突，leader 和 follower 会一直根据以上规则回溯 nextIndex

持久化

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

func (rf *Raft) persist() {
	// Your code here (2C).
	// Example:
	// w := new(bytes.Buffer)
	// e := labgob.NewEncoder(w)
	// e.Encode(rf.xxx)
	// e.Encode(rf.yyy)
	// data := w.Bytes()
	// rf.persister.SaveRaftState(data)
	rf.persister.SaveRaftState(rf.encodeState())
}

func (rf *Raft) encodeState() []byte {
	buf := new(bytes.Buffer)
	enc := labgob.NewEncoder(buf)
	// figure2 Persistent state on all servers
	enc.Encode(rf.currentTerm)
	enc.Encode(rf.votedFor)
	enc.Encode(rf.logs)
	return buf.Bytes()
}

// restore previously persisted state.
func (rf *Raft) readPersist(data []byte) {
	if len(data) < 1 {
		return
	}

	buf := bytes.NewBuffer(data)
	dec := labgob.NewDecoder(buf)

	var currentTerm, votedFor int
	var logs []Entry

	if dec.Decode(&currentTerm) != nil || dec.Decode(&votedFor) != nil ||
		dec.Decode(&logs) != nil {
		DPrintf("[readPersist] - {Node: %v} restore persisted data failed", rf.me)
	}

	rf.currentTerm, rf.votedFor, rf.logs = currentTerm, votedFor, logs

	rf.lastApplied, rf.commitIndex = rf.logs[0].Index, rf.logs[0].Index
	// Your code here (2C).
	// Example:
	// r := bytes.NewBuffer(data)
	// d := labgob.NewDecoder(r)
	// var xxx
	// var yyy
	// if d.Decode(&xxx) != nil ||
	//    d.Decode(&yyy) != nil {
	//   error...
	// } else {
	//   rf.xxx = xxx
	//   rf.yyy = yyy
	// }
}

nextIndex 优化

Lab 2B 中对于失败的AppendEntries请求，让nextIndex自减，这样效率是比较慢的。方法上可以以Term 为单位返回，不在一个一个Index 自减。 这需要添加 ConflicTerm, ConflictIndex 字段 去记录出现冲突的位置和任期。然后在 HanleAppendEntries RPC 中，在 Leader 的log 中检查 ConflictIndex 位置的日志一致性。

  • 优化点1 如果follower.log不存在prevLog，让Leader下一次从follower.log的末尾开始同步日志。
  • 优化点2 如果是因为prevLog.Term不匹配，记follower.prevLog.Term为conflictTerm。
  • 如果leader.log找不到Term为conflictTerm的日志，则下一次从follower.log中conflictTerm的第一个log的位置开始同步日志。
  • 如果leader.log找到了Term为conflictTerm的日志，则下一次从leader.log中conflictTerm的最后一个log的下一个位置开始同步日志。

nextIndex的正确位置可能依旧需要多次RPC才能找到，改进的流程只是加快了找到正确nextIndex的速度。