脑裂
在多副本的分布式系统中，通常会存在一个 Primary 节点，由它来决定整个系统的决策，这样可以简化一致性的实现，因为 Priamry 只需要强迫其他节点与它保持一致即可。
但是 Primary 节点本身会发生故障，之后我们需要选出一个新的 Primary 节点，这样就可能会面临脑裂的场景。
现在我们以 VMware FT 为例，来说明为什么会出现脑裂。假设在一个网络中有两台服务器 S1 和 S2 ，这两台服务器是 Test-and-Set 服务的副本，这个网络中还有两个客户端 C1 和 C2 ，现在它们需要通过 Test-and-Set 服务确定谁是 Primary。
在正常情况下，Test-and-Set 服务中的数据记录从0开始。一个客户端会向两台服务器发送 Test-and-Set 指令，这个指令会把两台服务器中的数据记录设置为1，之后返回 Success 响应。如果服务器中的数据记录已经被设置，那么另一个客户端发送 Test-and-Set 指令后，则会收到一个 Fail 响应。因此，其本质上就是一个互斥锁服务。
我们希望 Test-and-Set 具有容错特性，当一个客户端只能与一个 Test-and-Set 服务器通信时，也可以正常工作。例如 C1 可以和 S1 通信，但不能和 S2 通信，C1 也可以正常工作。反之，如果 C1 必须和 S2 通信，而恰好 C1 和 S2 之间的网络出现了故障，这就导致 C1 为了等待 S2 的响应将永远无法继续工作，这就失去了多副本的意义。
因此为了具备容错特性，我们允许一个客户端只与它能连通的服务器交互。在这种情况下，如果发生了网络分区，例如 C1 只能与 S1 通信，C2 只能与 S2 通信，则会导致脑裂：
C1 发送 Test-and-Set 指令给 S1，S1将自己的数据记录设置为1，并返回 Success 给 C1。同时，C2 发送 Test-and-Set 指令给 S2，S2 将自己的数据记录为1，并返回 Success 给 C2。因此，C1 和 C2 都获得了 Success 响应，C1 和 C2 都会认为自己是 Primary，而不需要与另一个虚拟机进行协调，从而进入错误的场景。
因此，在这种有两个副本的服务中，我们似乎只有两种选择：要么等待两个服务器响应，那么这个时候就没有容错能力；要么只等待一个服务器响应，那么就会进入错误的场景，而这种错误的场景，通常被称为脑裂。
在上世纪八十年代，对于脑裂并没有什么好的解决办法。但是，当时又的确有多副本系统的需要，为了解决脑裂问题，有两种技术：
过半投票
当网络出现故障，将网络分割成两半，网络的两边独自运行，且不能访问对方，这通常被称为网络分区。而网络分区可能会导致进入上面提到的脑裂场景，从而导致多副本服务出现不一致。
随着技术的发展，人们发现即使出现分区，也能正确地实现能够自动完成故障切换的系统。在构建能自动恢复，同时又避免脑裂的多副本系统时，关键点在于过半投票。
首先服务器的数量必须是奇数，那么当出现网络分区时，必然只可能最多有一个分区拥有半数以上的服务器。我们可以规定，如果要完成任何操作，必须要凑够半数以上的服务器的投票。这样，在任何情况下只可能有一个分区能够完成操作，这也就避免了脑裂的场景。
在这种过半投票的思想的支持下，在上世纪九十年代，有两个系统被同时提出：Paxos 和 ViewStamped Replication，这两个系统都使用过半购票的原理来避免脑裂的问题。
Raft 领导人选举
Raft 也应用了过半投票的思想来解决脑裂问题。Raft 会通过过半投票选举出一个领导人，然后给予他全部的管理复制日志的责任来实现一致性。
领导人从客户端接收日志条目，把日志条目复制到其他服务器上，并告诉其他的服务器什么时候可以安全地将日志条目应用到他们的状态机中。拥有一个领导人大大简化了对复制日志的管理。例如，领导人可以决定新的日志条目需要放在日志中的什么位置而不需要和其他服务器商议，并且数据都从领导人流向其他服务器。一个领导人可能会发生故障，或者和其他服务器失去连接，在这种情况下一个新的领导人会被选举出来。
具体的领导人选举算法，在 Raft 论文中说的非常详细：Raft paper（第5节和5.2节）。
Lab 2A 中遇到的问题
最后说一说，在实现 6.824 的 LAB 2A 时遇到一个死锁 Bug。
在 6.824 的 LAB 2A 中，是需要大量使用互斥锁的，这非常容易出错。在我第一次实现完 LAB 2A 并运行测试的时候，报了大量的数据竞争错误，把这个错误改完就花了十几分钟~~。
之后继续运行测试的时候，又卡在了 “election after network failure” 的测试中，但奇怪的是整个测试并没有报错，只是“卡住了”，我就猜到可能出现了死锁。使用博客 Debugging by Pretty Printing 中的测试框架，得到了如下的日志记录：
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| S0 starts running
S1 starts running
S2 starts running
S0 starts election
S0 becomes Candidate
S0 change term from 0 to 1
S0 votes for S0
S1 receives VoteRequestRpc from S0
S1 becomes Follower
S1 changes term from 1 to 1
S1 votes for S0
S0 becomes Leader
S0 sends hearbeat
S1 receives AppendEntriesRpc from S0
S1 reply AppendEntriesRpc from S0: &{Term:1}
S2 receives AppendEntriesRpc from S0
S2 becomes Follower
S2 changes term from 1 to 1
S2 reply AppendEntriesRpc from S0: &{Term:1}
S0 sends hearbeat
S1 receives AppendEntriesRpc from S0
S1 reply AppendEntriesRpc from S0: &{Term:1}
S2 receives AppendEntriesRpc from S0
S2 reply AppendEntriesRpc from S0: &{Term:1}
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S2 starts election
S2 becomes Candidate
S2 change term from 1 to 2
S2 votes for S2
S1 starts election
S1 becomes Candidate
S1 change term from 1 to 2
S1 votes for S1
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S2 receives VoteRequestRpc from S1
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S1 receives VoteRequestRpc from S2
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
S0 sends hearbeat
|
在第25到28行的记录中，可以看到 S0 发送了四次心跳，但是都没有收到 S1 和 S2 的答复，可以推测出发生了网络分区，这时候 S1 和 S2 无法与 S0 通信。
之后 S1 和 S2 触发选举超时，发起选举投票，它们首先都为自己投票，因此 S1 和 S2 都不会得到过半投票。按照理论来说，过一会之后又会触发选举超时，S1 或 S2 会再次发起选举投票，但是整个系统卡住了，只有 S0 还在打印消息。
根据上面的分析，可初步定位是在选举投票的实现中出了问题，之前的实现如下：
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
| func (rf *Raft) startElection() {
receivedVotes := 1
for i := range rf.peers {
if i == rf.me {
continue
}
go func(peerId int) {
rf.mu.Lock()
defer rf.mu.Unlock()
if rf.role != CANDIDATE {
return
}
if electionStartTerm != rf.currentTerm {
return
}
args := &RequestVoteArgs{
Term: electionStartTerm,
CandidateId: rf.me,
}
reply := &RequestVoteReply{}
if !rf.sendRequestVote(peerId, args, reply) {
return
}
}(i)
}
rf.electionStart = time.Now()
rf.electionTimeout = rf.randomElectionTimeout()
go rf.ticker()
}
|
在循环中，对每个节点我们都会开一个 Go 程去“拉票”，在 Go 程最开头的时候我们申请了锁，然后使用 defer rf.mu.Unlock() 在 Go 程返回的时候释放锁，而这恰恰就导致了死锁。
在这个实现中，S1 和 S2 在发起投票 RPC 的时候是持有自己的锁的（假设 S1 的锁为锁A，S2 的锁为锁B）。而 S1 和 S2 在收到投票 RPC 后需要读取自己的一些状态，因此 S1 会申请锁A，S2 会申请锁B，但是此时锁A和锁B已经被 S1 和 S2 持有了，这样整个系统就卡住了，无法继续执行下去，因此 S1 和 S2 自然就不可能再次发起选举，很显然这就是一个死锁Bug。
解决方法也很简单，只要 S1 和 S2 在发起投票 RPC 之前是否释放掉持有的锁即可：
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
| func (rf *Raft) startElection() {
receivedVotes := 1
for i := range rf.peers {
if i == rf.me {
continue
}
go func(peerId int) {
rf.mu.Lock()
if rf.role != CANDIDATE {
rf.mu.Unlock()
return
}
if electionStartTerm != rf.currentTerm {
rf.mu.Unlock()
return
}
rf.mu.Unlock()
args := &RequestVoteArgs{
Term: electionStartTerm,
CandidateId: rf.me,
}
reply := &RequestVoteReply{}
if !rf.sendRequestVote(peerId, args, reply) {
return
}
}(i)
}
rf.electionStart = time.Now()
rf.electionTimeout = rf.randomElectionTimeout()
go rf.ticker()
}
|
再次运行 Lab 2A 的测试，就能完美通过了：
1
2
3
4
5
6
7
8
| Test (2A): initial election ...
... Passed -- 3.0 3 110 11914 0
Test (2A): election after network failure ...
... Passed -- 4.5 3 130 9694 0
Test (2A): multiple elections ...
... Passed -- 5.6 7 852 69742 0
PASS
ok 6.824/raft 14.129s
|
参考