Fault-tolerant Key/Value Service（二）

具有快照功能的Key/Value service

LAB 3B在LAB 3A的基础上增加了快照的功能，随着Key/Value服务的运行，其底层的Raft日志会越来越多，当超过某一阈值时，Key/Value服务就需要创建一个快照，然后把快照传给Raft，Raft收到快照后就能够丢弃快照点之前的日志了。

Key/Value服务也必须在崩溃重启后仍然能够过滤重复请求，这意味着LAB 3A中用来实现过滤重复请功能的数据结构也必须持久化到快照中。这样，当Key/Value服务重启后，Key/Value服务会首先读取持久化存储的快照，恢复在快照点的状态和客户端请求记录，之后再一条条执行快照点之后的日志，因此快照点之后的重复操作仍然可以被过滤。

LAB 3B 中遇到的问题

Bug 1

第一个遇到的问题是 TestSnapshotUnreliableRecoverConcurrentPartitionLinearizable3B 测试没有通过，错误信息中显示客户端的写操作不是线性一致的。

截取的错误日志片段如下：

1
2
3
4
5
6
7
8
9
10
11
// ............
188282 SNAP S4 receives snapshot: &{term: 22 index: 1576}
188282 INFO S4 lastApplied: 0, kvTable: map[], clientReqTable: map[]
188283 SNAP S4 applies a snapshot: &{term: 22 index: 1576}
// ............
nfo: wrote history visualization to /tmp/503826179.html
--- FAIL: TestSnapshotUnreliableRecoverConcurrentPartitionLinearizable3B (29.60s)
    test_test.go:385: history is not linearizable
FAIL
exit status 1
FAIL	6.824/kvraft	29.606s

日志中显示S4收到了Raft发来的一个空的快照，并且S4应用了这个快照，这导致S4的状态被清空，因此违反了线性一致性。

在我的Raft实现中，快照会被保存在Raft结构体中：

1
2
3
type Raft struct {
    snapshot	[]byte //最近的快照
}

当上层的Server传递快照给Raft时，Raft除了会把快照持久化存储起来之外，还会更新自己的 snapshot 字段的值。当 Leader 发送快照时会直接发送 rf.snapshot 的值而不会去读取持久化存储的快照。

但是在Raft初始启动时，我没有读取持久化存储的快照来初始化 rf.snapshot，而这就是问题的所在。当一个重新启动的节点被当选为 Leader 后，这个节点会向落后于它的快照点的其他节点发送快照，而此时快照是空的。当其他节点收到这个快照后，如果应用了这个快照，复制状态机的状态将会被清空，最终导致错误。

因此，需要在初始化Raft时读取持久化存储的快照来设置 rf.snapshot 的值：

1
2
3
4
5
6
7
8
func Make(peers []*labrpc.ClientEnd, me int,
	// ....
	rf.snapshot = rf.persister.ReadSnapshot()
	// ....

	return rf
}

Bug 2

第二个遇到的问题是 TestSnapshotUnreliable3B 测试没有通过。这个 Bug 是我在 LAB 3 中遇到的最难解决的一个Bug。

起初，我在测试时加了竞争检测器：go test --run TestSnapshotUnreliable3B--race，得到了如下的错误日志：

1
2
3
4
// ....
race: limit on 8128 simultaneously alive goroutines is exceeded, dying
exit status 66
FAIL	6.824/kvraft	589.365s

错误日志中显示存在的Go程太多了，超过了8128个。我检查代码之后，没有找到哪里出了问题，所以就去搜了一下看别人有没有遇到这个问题，最终在知乎上看到了一篇文章有讲这个Bug。在那篇文章中作者提到是因为心跳太过频繁导致Go程开的太多，最终超过了竞争检测器的上限。

因此，我把心跳间隔设置为200MS（原来是100MS）再去测试，但是这个错误还是出现了，只是出现错误次数比之前少了很多。之后，我把竞争检测器去掉（go test --run TestSnapshotUnreliable3B），再并发跑500次测试，最终有一次测试发生了超时报错：

1
2
3
4
5
6
7
8
9
// ....
panic: test timed out after 10m0s

goroutine 79839 [running]:
testing.(*M).startAlarm.func1()
	/usr/lib/go-1.13/src/testing/testing.go:1377 +0xdf
created by time.goFunc
	/usr/lib/go-1.13/src/time/sleep.go:168 +0x44
// ....

这个时候我才意识到有可能发生了死锁，当一个服务器发生死锁后，这个服务器就会被永久阻塞，在测试超时10分钟后就会发生panic。

没办法，只能硬着头皮去看这几万行的日志了/(ㄒoㄒ)/~~。经过一顿操作后，终于定位到了发生错误的日志：

1
2
100223 INFO S2 success changes lastApplied from 237 to 238
100223 SNAP S2 generates snapshot: &{index: 238}

服务器S2在日志索引号238处想要生成一个快照，但是之后没有打印生成快照成功的日志。正常的生成快照得日志是这样的：

1
2
3
102268 INFO S1 success changes lastApplied from 247 to 248
102268 SNAP S1 generates snapshot: &{index: 248}
102270 INFO S1 generates snapshot success

生成快照的函数实现如下：

1
2
3
4
5
6
7
8
9
func (kv *KVServer) genSnapshot() {
	w := new(bytes.Buffer)
	e := labgob.NewEncoder(w)
    
	// ....

	data := w.Bytes()
	kv.rf.Snapshot(kv.LastApplied, data)
}

生成快照完毕后会调用Raft的Snapshot函数并把快照作为参数传入。Snapshot 的函数实现如下：

1
2
3
4
5
6
7
8
9
10
func (rf *Raft) Snapshot(index int, snapshot []byte) {
	// Your code here (2D).
	rf.mu.Lock()
	defer rf.mu.Unlock()
	
    //....
    //....

	rf.persister.SaveStateAndSnapshot(state, snapshot)
}

在Snapshot函数中需要首先获取Raft的锁才能继续向下执行，所以我在rf.mu.Lock()后面加了一行日志以便于Debug：

1
2
3
rf.mu.Lock()
log.Printf("S%d acquire lock successful")
rf.mu.Unlock()

之后，再并发跑500次测试。检查出现的错误的测试日志，我发现某个服务器在最后一次生成快照的时候没有打印这条消息，这说明直到10分钟后测试超时这个服务器一直没有拿到锁，即这个服务器执行 rf.mu.Lock() 语句被阻塞住了。

我猜测这很可能是死锁造成的，经过一顿代码筛查，终于定位到了错误代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Raft 中安装快照RPC的handler
func (rf *Raft) InstallSnapshot(args *InstallSnapshotArgs, reply *InstallSnapshotReply) {
	// ....
    rf.mu.Lock()
    defer rf.mu.Unlock()
	
    msg := ApplyMsg{}
    rf.applyCh <- msg
}

// KvServer 中一个单独运行的Go程
func (kv *KVServer) applyMsgToStateMachine() {
	for !kv.killed() {
		msg := <-kv.applyCh
        // ....

		if msg.CommandValid {
			// ....
			kv.genSnapshot()
			// ....
		}
        // ....
	}
}

假设这样一个场景，S 收到了 Leader 发来的快照并执行 rf.mu.Lock()获取了 Raft 锁，之后 S 在会把快照发送给上层 Key/Value服务：rf.applyCh <- msg。

如果 Key/Value 服务正在执行 kv.genSnapshot，那么 Key/Value 服务也会尝试获取 Raft 锁，那么 rf.applyCh 就没有接收方。由于 applyCh 是同步管道，InstallSnapshot RPC会一直被阻塞住不会释放 Raft 锁，所以 kv.genSnapshot 也无法获取 Raft 锁，导致无法生成快照。

解决方法很简单，把发送快照给上层 Key/Value服务的操作放在锁的外面即可：

1
2
3
4
5
6
7
8
func (rf *Raft) InstallSnapshot(args *InstallSnapshotArgs, reply *InstallSnapshotReply) {
	// ....
    rf.mu.Lock()
    msg := ApplyMsg{}
    rf.mu.Unlock()
    
    rf.applyCh <- msg
}

解决完所有的 Bug 后，并发跑500次测试全部通过：

参考

distributed system
#distributed #Fault-tolerant #Key/Value Service
Fault-tolerant Key/Value Service（二）
https://night-cruise.github.io/2022/08/22/Fault-tolerant-Key-Value-Service-2/
作者
Night Cruise
发布于
2022年8月22日
许可协议