MIT 6.824 分布式系统笔记 — Raft

先简单介绍下 Raft 是什么。Raft 是一种共识算法,解决的是分布式系统对某个提案,大部分节点达成一致意见的过程。
上面这样讲感觉很抽象,我们举一个具体的例子。

1
2
3
4
5
        server
_________
c1 -> | (k, v1) |
c2 -> | (k, v2) |
|_________|

假如我们有一个分布式的 KV 系统,有两个客户端 c1, c2,有两个服务端 s1, s2。客户端向服务端发请求修改 k 的值。如上所示,c1 发出将 k 修改为 v1 的请求,c2 发出将 k 修改为 v2 的请求。那么请问这个 KV 系统 k 的值最后为多少呢?

你肯定会说这依赖于 v1 和 v2 的顺序,v1 先 v2 后则最终值为 v2,反之则为 v1。但这要求 v1 和 v2 之间是有顺序关系的。一种做法是给 v1、v2 附上一个顺序,比如 vector clock。

还有一种更简单的做法,就是我们让其中一个 server 作为 leader 处理请求,而在单一 server 上,命令执行是自然有序的,之后我们再把这种次序转发给其他 server 就可以了。

但这又带来了其他的问题,怎么确定这个 leader 呢?简单点的可以直接固定一个,但这就会导致 leader 挂掉后群龙无首。我们也可以让服务器选一个 leader 出来,leader 挂掉后剩下的服务器再次选举就可以了。而这时,就轮到 Raft 出场了,Raft 会选举出一个 leader 出来,leader 执行的命令会以 log 的形式传给剩下的 server,使 server 的状态保持一致。

流程

可以先看 Raft 动画演示 来直观地了解这一过程。

Raft 将时间分阶段,用 term 来表示。我们先说同一个 term 中发生的事,再讲不同 term 之间发生的事。

Raft 把 server 分为三种状态,candidate(候选人),follower(追随者), leader(领导者)。

在 term 1 开始的时候,所有的 server 都是 follower 的状态。follower 会记录接收 leader 消息的最近时间,如果间隔超过 timeout,则会从 follower 变为 candidate 开始新一轮选举。

什么是选举呢?其实就是给其他 server 发消息(RequestVote)让它们投自己当 leader。假设 3 个 server,s1 开始选举,发消息给 s2、s3 让它们投 s1 为 leader。假设 s2 之前没有投过其他人,且 s1 符合条件,s2 就回复给 s1,好的,我投你。s1 一看选我的人(包括自己)超过半数,s1 就将状态改为 leader。

此时 s1 作为 leader 接收客户端的请求。当接收到客户端的请求 cmd1 时,s1 首先在自己的 log 上加上 Entry(cmd1),然后发送包含这条 Entry 的 RPC(AppendEntries RPC,以下简称为 AE)给 s2、s3。

s2、s3 收到 AE(cmd1),发现符合条件,将状态从 candidate 变为 follower,并在自己的 log 上加上 Entry(cmd1),然后回复给 s1 表示收到了。当 s1 收到超过半数(包括自己)的回复时,就可以 commit 这条 Entry(cmd1),之后就可以 apply(执行)了。

当 s1 收到 cmd2 后,会做同样的事情,在 log 上添加 Entry(cmd2),并发送 AE 给 s2、s3。
s2、s3 接收到 AE 之后,除了保存 log 并回复,它们还发现前一条 Entry 已经可以 commit 了。于是他们就追随 leader 的脚步,对 Entry(cmd1) 进行 commit,然后 apply。

上面讲的就是同一个 term 中发生的事了。leader 接收请求,通过 log 发送给 follower,如果半数以上的 follower 收到,就 commit 该条 log,之后 apply。follower 会在之后的请求中了解 leader 的 commit 情况,进行 commit 之后 apply。
如果某个 follower 在 timeout 之内没有接收到 leader 的消息,就会将 term + 1,开始新的选举。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
s1 start election
s1 -> s2 RequestVote RPC(term 1, latest log info)
s1 -> s3 RequestVote RPC(term 1, latest log info)
s1 <- s2 say yes
s1 <- s3 network loss
s1 become leader
c -> s1 cmd1
s1 add Entry(index 1, cmd1, term 1) in its log
s1 -> s2 AE(cmd1, term 1, leaderCommit 0) RPC
s1 -> s3 AE(cmd1, term 1, leaderCommit 0) RPC
s1 <- s2 received, add Entry(index 1, cmd1, term 1) in its log, s2 change to follower
s1 <- s3 received, add Entry(index 1, cmd1, term 1) in its log, s3 change to follower
s1 commit Entry(index 1, cmd1, term 1), later apply
c -> s1 cmd2
s1 add Entry(index 2, cmd2, term 1) in its log
s1 -> s2 AE(cmd2, term 1, leaderCommit 1) RPC
s1 -> s3 AE(cmd2, term 1, leaderCommit 1) RPC
s1 <- s2 received, add Entry(index 2, cmd2, term 1) in its log, commit Entry(index 1, cmd1, term 1), later apply
s1 <- s3 received, add Entry(index 2, cmd2, term 1) in its log, commit Entry(index 1, cmd1, term 1), later apply

细节

了解了流程之后,我发现 Raft 还是挺容易理解的。但在写了 Lab 2 Raft 之后,我才发现里面隐藏了那么多的细节。
下面使用 FAQ 来举例说明 Raft 的细节。

  1. 选举一定会成功吗?不成功会怎样?

选举不一定会成功。比如有 5 个 server, 同一时刻 s1、s2、s3 都开始新的选举,s1 获得 s4 的支持,s2 获得 s5 的支持,在这时候没有一个 server 获得的票数超过半数,选举没有成功。server 会在 timeout 后重新开始新一轮的选举。同时为了减少同时开始选举造成的选票分散的情况,server 会在每一次判断是否需要选举时设置一个随机的 timeout 而不是一直使用固定的 timeout。

  1. server 接收到其他 server 的选举请求时,会拒绝吗?

Raft 的选举不像现实中的选举,它采取的是先到先得的策略,你先告诉我让我投你,符合条件的话我就投你,不再投其他人。
这边详细说明会拒绝的情况, RequestVote 表示选举请求:

  • 1) RequestVote.term < server.currentTerm。选举请求的 term 落后了,server 会拒绝,并返回 server.currentTerm 以供其他 server 更新。
  • 2) server 暂未投票给其他人或者投的正是 RequestVote 中的 candidate,并且 candidate 的 log 不能落后于 server 的 log,即 lastCandidateLog.term > lastserverLog.term || (lastCandidateLog.term == lastserverLog.term && lastCandidateLog.index >= lastserverLog.index),返回 yes。
    这里我们说明下第 2 点对于 log 的要求,它保证了不会有不符合条件的 server 选举成为 leader。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# log 下面的 1 表示该 log entry 的 term 为 1
(1)
index 1 2
server log
------------------------
s1 1
s2 1
s3 1

(2)
index 1 2
server log
------------------------
s1 1 1
s2 1 1
s3 1

(3)
index 1 2
server log
------------------------
s1 1 1
s2 1
s3 1

假设 s1 为 leader,Entry(index 1, term 1) 已经全部复制到 3 个 server 上了,如 (1) 所示。

s1 又添加了 Entry(index 2, term 1),该 Entry 只被复制到 s2 上,s1 就挂了,示例 (2)。在这种情况下,s1 有可能已经 apply 过 Entry(index 2, term 1)。所以 Entry(index 2, term 1) 不能被覆盖。
而第 2 点对 log 的要求,使得 s3 不可能成为 leader。即使 s3 开始了新一轮选举,s2 由于 s3 的 log 落后于自己,不会投票给 s3。在 s1 挂了的情况下只有 s2 有可能成为新的 Leader,从而使得 Entry(index 2, term 1) 被保留。

如果 Entry(index 2, term 1) 如 (3) 所示,在这种情况下,s1 不可能 apply 过 Entry(index 2, term1)。s2、s3 都有可能成为新的 leader。

  1. 如果一条 log entry 被复制到超过半数以上的机子上,是否可以认为这个 log entry 是可以被 commit 的?

绝大部分情况是的。但存在一个例外,也就是 Raft Exteded 里 Figure 8 所提到的。如果这个 log entry 的 term 比 currentTerm 小,存在被覆盖的可能。

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
(1)
index 1 2
server log
------------------------
s1(l) 1 2
s2 1 2
s3 1
s4 1
s5 1

(2)
index 1 2
server log
------------------------
s1 1 2
s2 1 2
s3 1
s4 1
s5(l) 1 3

(3)
index 1 2 3
server log
------------------------
s1(l) 1 2 4
s2 1 2
s3 1 2
s4 1
s5 1 3

(4)
index 1 2
server log
------------------------
s1 1 3
s2 1 3
s3 1 3
s4 1 3
s5(l) 1 3

(3)
index 1 2 3
server log
------------------------
s1(l) 1 2 4
s2 1 2 4
s3 1 2 4
s4 1
s5 1 3

(1) s1 成为 term 2 的 leader,添加了 Entry(index 2, term 2) 到 s1,s2。
(2) s1 挂了,s5 成为 term 3 的 leader,添加了 Entry(index 2, term 3) 到 s5。
(3) s5 挂了,s1 成为 term 4 的 leader,添加了 Entry(index 3, term 4) 到 s1。
下面有两种可能
(4) s1 挂了,s5 成为 term 5 的 leader,将 Entry(index 2, term 2) 复制到所有 server。
(5) s1 没挂,将 Entry(index 2, term 2)Entry(index 3, term 4) 复制到所有 server。

我们分析下,如果 s1 在 (3) 的情况下把 Entry(index 2, term 2) commit 并且 apply 了,之后又出现 (4) 的情况,就会导致 server 之间状态的不一致,s1 执行了 Entry(index 2, term2),而其他 server 都没有。
因此 server 不能依赖于过去 term 中的 log entry 进行 commit。

做 Lab 2 时一定要多看看论文的 Figure 2,等我踩了无数的坑之后,才发现这上面讲的真是字字珠玑,漏一个条件多 Debug 半天。
Debug 时一定要打详细的日志,不然排查问题只能靠猜想了。下面是我日志的示例。

1
2
3
4
5
6
7
8
9
10
11
12
13
252403ms 0 read persist[term 0, votedFor -1, log length 0]
252406ms 1 read persist[term 0, votedFor -1, log length 0]
252408ms 2 read persist[term 0, votedFor -1, log length 0]
253015ms 0 begin term 1 election, before state follower
253018ms 0->1 Vote[id 1, term 1, lastLogIndex 0, lastLogTerm 0]
253022ms 0->2 Vote[id 2, term 1, lastLogIndex 0, lastLogTerm 0]
253027ms 0->2 Vote[id 2, term 1, lastLogIndex 0, lastLogTerm 0] Reply[true, term 1]
253028ms 0 now I'm the leader with term 1
253029ms 0->1 Vote[id 1, term 1, lastLogIndex 0, lastLogTerm 0] Reply[true, term 1]
253030ms 0->1 AE[id 3, term 1, prevLogIndex 0, prevLogTerm 0, commit 0, cmd 0]
253030ms 0->2 AE[id 4, term 1, prevLogIndex 0, prevLogTerm 0, commit 0, cmd 0]
253036ms 0->2 AE[id 4, term 1, prevLogIndex 0, prevLogTerm 0, commit 0, cmd 0] Reply[true, term 1, XTerm 0, XIndex 0, XLen 0]
253036ms 0->1 AE[id 3, term 1, prevLogIndex 0, prevLogTerm 0, commit 0, cmd 0] Reply[true, term 1, XTerm 0, XIndex 0, XLen 0]

参考