通常在实际使用 Raft 过程中，难免会遇到节点变更的问题。

Raft 论文[1] 提出了如何进行节点变更的方法，也就是使用joint consensus，在论文第六章有详细的说明，并且有正确性的证明。

单节点变化

同时在作者的博士论文[2]中，提出了一种简化版本，即单节点变化的流程，具体可见论文第4章。

1620711351-370263-image.png
图来源参考文献[2]

因为如果直接进行节点状态变化，上述例子是从3个节点扩展为5个，那么可能在中间某个时间段会存两种 majorities，会有两个 leader，不满足 Election Safety。究其原因是因为这两个 majorities 不存在交集。所以为了简化，可以将节点变化减少为一个，每次进行节点变化一个一个进行。

1620711562-148397-image.png
图来源参考文献[2]

如果是一个节点的变化，那么老配置和新配置的 majorities 之间肯定存在交集，从而避免上述问题的产生。

单节点变化的BUG

但是这样是否就一定没有问题？具体的单节点变化流程，大家可以参考文献[2]的描述，在此不详细展开。在论文所描述的步骤中，当节点接受到新的配置后，就立即转向新的配置，无论该配置是否已经committed了，当然这是没有问题的。问题出在按照论文所描述的步骤，会导致已经提交的日志被覆盖。作者也是在发现这个问题后，将它及时公布出来，完整细节参考文献[3]。

这里举其中的一个例子：

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
从4个节点移除一个节点,并且移除一个节点

0. 初始状态:

S1 (L1): [C]
S2 (F1): [C]
S3 (F1): [C]
S4 (F1): [C]
S5 (F1): []

其中C的配置是 {S1,S2,S3,S4}.

1. S5 赶上了S1的状态

S1 (L1): [C, D]
S2 (F1): [C]
S3 (F1): [C]
S4 (F1): [C]
S5 (F1): [C]

其中D的配置是 {S1,S2,S3,S4,S5}，代表增加 S5

2. S1将日志D复制给S5，然后宕机离线

S1 (L1): [C, D] X
S2 (F1): [C]
S3 (F1): [C]
S4 (F1): [C]
S5 (F1): [C, D]

3. 此时S2获得来自 {S2, S3, S4} 的投票，成为 leader

S1 (L1): [C, D] X
S2 (L2): [C]
S3 (F2): [C]
S4 (F2): [C]
S5 (F1): [C, D]

4. S2开始复制日志E

S1 (L1): [C, D] X
S2 (L2): [C, E]
S3 (F2): [C]
S4 (F2): [C]
S5 (F1): [C, D]

其中日志E为 {S2, S3, S4} 代表删除 S1

5. S2 复制到了S3，满足大多数原则，标志为提交状态

S1 (L1): [C, D] X
S2 (L2): [C, E]
S3 (F2): [C, E]
S4 (F2): [C]
S5 (F1): [C, D]

6. S1 恢复后，得到 {S1 S4 S5} 的投票，也满足大多数（老配置D），成为 leader

S1 (L3): [C, D]
S2 (L2): [C, E]
S3 (F2): [C, E]
S4 (F3): [C]
S5 (F3): [C, D]

注意 S1 没有已经提交的日志 E

7. S1 此时复制日志 D 给其他节点，D 会覆盖日志 E（
（因为 D 是 leader ，其他节点同位置的日志 E 和 leader 不一致，会被覆盖）

S1 (L3): [C, D]
S2 (L2): [C, D]
S3 (F2): [C, D]
S4 (F3): [C, D]
S5 (F3): [C, D]

原始讨论中还提了其他例子，可以深入看看。

解决方法

作者给出了一种解决方法，即节点成为 leader 后，必须先发送一个 NO_OP 日志，避免当前配置下，其他未提交的日志不会覆盖当前已经提交的日志。例如上述步骤 3，S2 发送 NO_OP 后，待NO_OP 提交，那么老配置下的大多数都接受到了，那么据可以阻止没有接受到 NO_OP 当选为 leader，避免覆盖已经提交的日志。

其实NO_OP的原本作用就是这个：

In a typical Raft implementation, a leader appends a no-op entry to the log when it is elected. This change would mean rejecting or delaying membership change requests until the no-op entry is committed.

也就是在文献[2]提及的这种情况，日志 2 已经被复制到大多数了，但是可能会被日志3覆盖。
1620713307-467346-5a36498f-f74c-4997-bba5-40bf12356959.png
图来源参考文献[2]

当然除了上述的方法，那就是老老实实用 join consensus的方法。

其他的讨论

关于这个问题还有很多有趣的讨论，可以扩展阅读

  1. TiDB 在 Raft 成员变更上踩的坑
  2. 关于 Raft 算法的 Single MemberShip 算法的疑问？
  3. braft-节点变更文档

参考文献

[1]. Ongaro, Diego, 和John Ousterhout. 《In Search of an Understandable Consensus Algorithm》, 不详, 18.
[2]. Ongaro, Diego. 《Consensus: Bridging Theory and Practice》, 不详, 258.
[3]. 《bug in single-server membership changes》. 见于 2021年5月11日. https://groups.google.com/g/raft-dev/c/t4xj6dJTP6E.