Raft 成员变更的陷阱
问题所在
前段时间，喝咖啡时，一位朋友描述了他们团队遇到的一个问题筏子正在生产中。看起来像个小细节。这让他们损失了一整团。
它们的实现用途单服务器变更要更改副本集，你一次添加或删除一个节点。从中转abc到bcd只需两步。第一次添加d，得到abcd.然后移除a，得到bcd.
麻烦就在中间的台阶上。虽然集群有四个节点，但网络形状被分割ad | bc这使得它无法选举领导人。当节点分布在不同的数据中心时，这种分裂的形状很容易实现。说a,b以及c每个数据中心各自运行：
a b c
---- ---- ----
DC-1 DC-2 DC-3
| add `d` in DC-1
v
a b c partitioned a | b c
d no leader! d |
---- ---- ---- ------------> ---- | ---- ----
DC-1 DC-2 DC-3 DC-1 | DC-2 DC-3
| remove `a`,
| healthy again
v
b c
d
---- ---- ----
DC-1 DC-2 DC-3
- 在稳态下，集群有三个节点。如果任何一个数据中心与外界失去联系，另外两个仍然占据多数。他们选举领导人，继续服役。
- 在中间状态下，DC-1 包含两个节点，
a以及d.四个节点的大多数需要三个节点。DC-1只有两名领导人，因此无法单独选举领导人。DC-2和DC-3加起来也只有两台，所以它们也不能。现在一个数据中心沉默，整个集群都会停止。
看看DC-1发生了什么。在四节点中间状态下，每个多数都必须包括DC-1的一个节点。DC-1成为了单点故障，仅仅因为成员变更正在进行中。
根本原因是单一服务器的变更在一件事上很僵化：法定人数总是多数，绝不意味着其他任何事。一旦我们放开这个规则，问题就会消失。因此，我们将通过法定人数集来分析成员变动，这种观点直接引导我们达成联合共识。
如果你对法定人数不熟悉，我之前的文章少数实现的多数读写介绍我们下面所用的思维方式。
通过法定人数集来研究问题
不要用节点来描述集群，而是用其法定人数来描述。法定人数是一组被允许提交某项事务的节点。所有此类组的列表即为法定人数集。
有一条规则可以保证法定人数的设定：其中任意两个组必须至少共享一个节点。这个共享节点阻止了两个不同值同时提交，也是Paxos和Raft真正需要的法定人数。
以下是我们故事中的法定人数情况：
- 起始状态
abc使用所有多数数的abc： M（abc） = {ab， ac， bc}。完整组abc也是法定人数，但它已经包含ab，任何包含法定人数的组都是法定人数。所以列出较大的群体并不会增加任何内容，我们只列出最小的群体。 - 最终状态
bcd使用 M（bcd） = {bc， cd， bd}。 - 中间州
abcd单个服务器的变更同样是多数集：M（abcd） = {abc， abd， acd， bcd}。
因此，单一服务器的变动就是对三个法定人数组进行巡查：
M（abc） → M（abcd） → M（bcd）
现在，可用性问题有了一句话的解释。中间集的每个法定人数都需要三个节点。当网络分裂为ad | bc，两边都没有三个节点。双方都无法选举领导人，混乱就此停止。
第一个补丁：让
bc提交
中间那套才是最痛的地方，所以我们换中间那套。假设我们也允许bc承诺。中间的法定人数集变为：
Q（abcd） = M（abcd） ∪ {bc}
简单来说：一旦到达，条目即被提交bc，或四个节点中的任意三个。
这样很安全，检查也很快。bc与 M（abcd） 中的每个群共享一个节点，因为bc有两个节点，每个三节点多数只需省略一个节点，且不能同时省略两个节点b以及c.所以共享规则在整个系列中依然适用。Paxos和Raft在中间状态上运行得与以往完全一致，一致性保持不变。
变更现在为：M（abc） → M（abcd） ∪ {bc} → M（bcd）。
这仍然是合法的成员变更。Raft 关于单服务器变更的安全论证要求一件事：旧节点集的每个定额数必须与新节点集的每个定额共享一个节点。我们新增的团队bc比赛ab在b，遇见ac在c，并且相遇bc两者都一样。所以如果筏子对M（abc）→M（abcd）安全，则对M（abc）→M（abcd）∪{bc}同样安全。.第二步也同样检验，M（abcd） ∪ {bc} → M（bcd）。
这能治标。该集群现存于......ad | bc在变更过程中分开。
为什么大多数人空间不够
四节点态存在这种弱点，原因值得一提：M（abcd） 并不是四个节点的最大安全法定人数集。
节点数为奇数时，多数节点是最好的选择。取三个节点abc： 你不能向 {ab， ac， bc} 添加任何更小的群，因为单个节点如a未能见面bc.多数已经是最大值了，所以没有损失。
节点数为偶数时，大多数人会留下法定人数。一个四节点系统有四个三节点的多数。除此之外，还可以安全地容纳另外三个两节点组：
Q'（abcd） = M（abcd） ∪{AB， BC， AC}
Q'（abcd）中的每对节点共享一个节点。ab以及bc分享b.ab以及ac分享a.bc以及ac分享c.每个两节点群也要满足每个三节点群，因为二加三比四多。Paxos和Raft运行在Q'（abcd）上，完全没有任何变化，而且它容忍的失败率严格高于M（abcd）。
大多数是Raft设计中的第一个弱点。通过将多数写入算法，Raft 泄露了偶数集群可能拥有的可用性。
如何扩大多数
这是通用的食谱。设节点集为C，例如C = {a，b，c}。
- 对于奇节点计数，n = 2k+1，保留多数。它们已经是极大了的：
- 对于偶数节点数，n = 2k，注意任意 n/2 节点必须与任意 n/2+1 节点共享一个节点：它们共同计数 n+1 个节点，组成仅 n 个的簇。因此，我们可以将大小为 n/2 的群添加到 M（C）。唯一需要额外检查的是新增的组是否共享节点。在我们的四节点示例中：
- Q' = M（abcd） ∪ {ab， bc， ca} 可行：这三个添加的群成对共享一个节点。
- Q' = M（abcd） ∪ {bc， cd， bd} 也出于同样的理由工作。
- Q' = M（abcd） ∪ {ab， bc， cd} 不起作用：
ab以及cd不共享任何东西，因此可以同时选举两位领导人。
中等州真正需要的东西
这些例子说明了一件事。成员变更的中间状态不必是多数票。它只需要安全，而对于我们的数据中心问题，它必须包含内在bc.
几个中部州符合条件：
- M（abcd） ∪ {ab， bc， ac}，
- {abc， abd， acd， bcd， bc}，
- 甚至 {abd， acd， bcd， bc}，其中
abc掉落。
联合共识也符合条件。纸面上看起来很复杂，结果却是最简单的。
正确性条件
在比较算法之前，先写下成员变更能保证什么。用我们之前的方法描述每个状态的定额集，然后让变化从 Q₁ 到 Q₂。它必须满足三个条件：
- 坚定的改变会保持可见。如果一个变更已经提交，所有未提交的变更都必须被识别为未提交。否则新领导无法决定保留哪一个。
- 同时进行的变更相互排除。多个并发变更中只有一个成功，因此每个提出变更的进程都必须对同一法定人数集合提交变更。所有进程唯一已经达成一致的就是Q₁。因此，变更必须承诺到Q₁，或者对Q₁的展开，每个进程都以相同方式导出。
- 变更会传达到新的配置。它还必须承诺达到Q₂的法定人数。否则，在Q₂下选出的领导人可能永远见不到它。
Raft最初的单服改动忽略了第一个条件。作者后来修正了这个问题，我们稍后会再谈。
联合共识正是给了我们这一点
联合共识满足这三个条件。它还能解决我们的数据中心问题，无需有人为此设计。
在abc到bcd，联合中间态是两个多数集的乘积：
Q = M（abc） x M（bcd）
联合法定人数是指同时包含一个M（abc）和一个M（bcd）法定人数的群体。当M（abc） = {ab， bc， ca} 和 M（bcd） = {bc， cd， bd} 时，乘积为：
M(abc) x M(bcd) = {
ab ∪ bc,
ab ∪ cd,
ab ∪ bd,
bc ∪ bc,
bc ∪ cd,
bc ∪ bd,
ac ∪ bc,
ac ∪ cd,
ac ∪ bd,
} = {
abc,
abcd,
abd,
acd,
bc,
bcd,
}
这正是 M（abcd） ∪ {bc}——正是我们几节前亲手建立的法定人数组。
所以，联合共识给了我们想要的一切：
- 它能容忍一次节点故障。
- 它总是包含
bc，因此它存活于ad | bc这部分内容引发了这篇文章。 - 整个变更以两个已提交的日志条目结束，无论领导者是否在途中更换。
单服变更中的漏洞
单服务器更换还有第二个问题，这个问题比可用性更严重。最初发表时，它完全错误。
当领导更换和成员更换同时进行时，就会出现这个bug。作者于2015年宣布：
很遗憾，我需要宣布论文版关于会员变更的一个bug（是单服务器变更，不是联合共识）。这个bug可能很严重，但我提出的修复方案很容易实现。
事情出错的地方是这样的。集群从四个节点开始abcd.有一种流程想补充u另一位想补充v.中间领导者变更将失去一个已承诺的条目：
C₀ = {a, b, c, d}
Cᵤ = C₀ ∪ {u}
Cᵥ = C₀ ∪ {v}
Lᵢ: Leader in term `i`
Fᵢ: Follower in term `i`
☒ : crash
|
u | Cᵤ F₂ Cᵤ
--- | ----------------------------------
a | C₀ L₀ Cᵤ ☒ L₂ Cᵤ
b | C₀ F₀ F₁ F₂ Cᵤ
c | C₀ F₀ F₁ Cᵥ Cᵤ
d | C₀ L₁ Cᵥ ☒ Cᵤ
--- | ----------------------------------
v | Cᵥ time
+-------------------------------------------->
t₁ t₂ t₃ t₄ t₅ t₆ t₇ t₈
- T₁：四个节点
abcd选出a作为第0任期的领导人，拥有追随者b以及c. - t₂：
a附加变更条目Cᵤ切换到新配置Cᵤ马上。入口仅延伸至此a以及u，因此不提交。 - t₃：
a撞击声。 - t₄：
d在第一届选举中当选领导人，拥有众多支持者b以及c. - T₅
d附加另一个变更条目Cᵥ并切换到Cᵥ.入口延伸c,d以及v，即五个节点中的多数Cᵥ，因此是commitped。 - t₆：
d撞击声。 - t₇：
a回归后在第二任期当选领导人。它从下面流过Cᵤ，它在自己的日志中看到的配置，并从中收集投票u以及b. - t₈：
a向所有人和已提交的日志复制Cᵥ已经消失了。
把t₅和t₈一起读，因为伤害就在那儿。Cᵥ根据Raft给出的每一条规则都被强制执行，然后它被覆盖了。原因是a被允许以一种从未有人参与过的配置进行选举。
作者的修正很简短，呼应了Raft对普通条目的一条规则：
我提出的解决方案与论文描述的完全相同，只不过领导者在提交当前术语的条目之前，不能添加新的配置条目。
在我们的时间线上，d必须在第一学期提交无操作记录，才能附加Cᵥ.曾经b以及c等等，No-op，a无法再赢得第二任期选举：b看到了a的日志落后，拒绝投票支持。所以a永远不会成为L₂，且承诺的Cᵥ幸存。
仔细看看那个修正
修复方案悄然将单服变更转变为共同共识。
两者最终都做了同样的工作。变更必须先通过旧配置的法定人数，因此在多个并发变更中只有一个可被视为提交。单服务器的变更达到该点时会多一条条目：如果方便则是普通应用条目，如果不方便则是no-op。联合共识直接达成，因为它的中间状态已经是旧构型和新构型同时存在。
正确的单一服务器更改每次需要两次日志提交。
曾有人提出单服务器改动以简化流程，但事实并非如此。变化abc到bcd单服务器更换时，需要2到4个日志条目。如果大家一致同意，成本是2。
这里有合理的反对意见：单服务器变更通常只需两个条目，因为领导者通常已经有一个自己期限内的已提交条目，不需要无操作。这是真的，但这并没有帮助。代码不是靠概率下注。每个能运行的分支都必须被编写、测试和维护，包括那个每万次变更中触发一次的分支。所以正确的单服务器变更逻辑几乎和联合共识一样，实现的是两步变更，运行时也没有任何收益。
结语
Raft是理论与实际代码之间美丽的桥梁，正是这种美感让其中一个设计失误传播得如此之远。
如果你正在构建或维护Raft的实现，建议很简短：使用联合共识。它能填补中间状态的可用性漏洞，消除漏洞，而且代码比正确的单服务器更改还少。
参考资料：
- 多数派读写的少数派实现 : https://blog.openacid.com/algo/quorum/
- 筏子：https://raft.github.io/
- 单一服务器成员变动：https://gist.github.com/ongardie/a11f32b70581e20d6bcd
点赞
收藏
点踩
分享