周刊（第14期）：重读Raft论文中的集群成员变更算法（二）：实践篇
引言：以前阅读Raft大论文的时候，对“集群变更”这部分内容似懂非懂。于是最近又重读了大论文这部分的内容，以下是重读时做的一些记录。这部分内容打算分为两篇文章，上篇讲解成员变更流程的理论基础，下篇讲解实践中存在的问题。
重读Raft论文中的集群成员变更算法（二）：实践篇
单步成员变更存在的问题
正确性问题
单步变更成员时，可能出现正确性问题。如下面的例子所示，最开始时，系统的成员是{a,b,c,d}这四个节点的集合，要将节点u和v加入集群，按照单步变更成员的做法，依次会经历：{a,b,c,d}->{a,b,c,d,u}->{a,b,c,d,u,v}的变化，每次将一个节点加入到集群里。
上面的步骤看起来很美好，但是考虑下面的例子，在变更过程中leader节点发生了变化的情况：
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₈
（引用自TiDB 在 Raft 成员变更上踩的坑 - OpenACID Blog）
上面的流程中，纵坐标是集群中的节点，横坐标是不同的时间（注意不是任期），Li表示在任期i时候的leader节点，Fi表示在任期i时候的follower节点。
上图的流程阐述如下：
- t1：a节点被选为任期0的leader，而b、c节点为follower。
- t2：将节点u加入集群，但是这条加入集群的日志，仅达到了a和u节点，由于这条日志并没有半数以上通过，所以这时候节点u还并未成功加入集群。
- t3：节点a宕机。
- t4：由于原先的leader宕机，于是集群需要选出新的leader，选出来的新leader是节点d，这是任期1时候的leader。
- t5：节点v加入集群，加入集群的日志，到达了节点c、d、v上面，可以看到由于这条日志到了此时集群的半数以上节点上（因为这时候节点a宕机，因此只有三个节点在服务，于是只有有2个节点同意就认为可被提交），所以实际是已经提交的，即v加入集群的操作是成功的。
- t6：leader d宕机。
- t7：宕机的节点a恢复服务，看到本地有将节点u加入到集群的日志，于是它认为节点u、b是这个任期的follower节点。
- t8：此时节点d恢复服务，而leader a将之前把节点u加入集群的日志同步给当前集群的所有节点，这造成了之前v加入集群且已被提交的日志丢失。
出现这个问题，本质是因为：上一任leader的变更日志，还未同步到集群半数以上节点就宕机，这时候新一任leader就进行成员变更，这样导致了形成两个不同的集群，产生脑裂将已经提交的日志被覆盖。
Raft作者在bug in single-server membership changes描述了这一现象。
解决的办法也很简单：即每次新当选的leader不允许直接提交在它本地的日志，而必须先提交一个no-op日志，才能开始同步。这个问题的描述，在之前的博客有描述：为什么Raft协议不能提交之前任期的日志？ - codedump的网络日志
可用性问题
除了以上正确性问题，单步变更还有可能出现可用性问题：当需要替换的节点在同一机房的时候，如果这个机房网络与集群中其他机房的网络断开，就会导致无法选出leader，以致于集群无法提供服务。来看下面的例子。
在上图中，原先集群中有三个节点分别位于三个机房：机房1的节点a、机房2的节点b、机房3的节点c。现在由于各种原因，想把机房1的节点a下线，换成同机房的节点d到集群中继续服务。
可以看到，这个替换操作涉及到一个节点的加入和一个节点的离开，可能有如下两种可能的步骤：
- 先加入新节点d再删除节点a：
{a,b,c}->{a,b,c,d}->{b,c,d}。 - 先删除节点a再加入新节点d：
{a,b,c}->{b,c}->{b,c,d}。
两种步骤各有优劣，第二种方案的问题是：中间只有两个节点在服务，一旦这时候又发生宕机，则集群就不可用了。
第一种方案中，按照上图中的例子，如果正好要替换的a、d节点都位于同一个机房里面，那么假如这个机房的网络也与其它机房隔离，那么只有两个节点在服务，这时候在四节点（中间步骤）的条件下也无法服务。
以上是单步变更中可能出现的两类问题。可以看到，尽管单步变更算法看起来实现简单，但是实则有很多细节需要注意。虽然Raft论文中认为单步变更是更简单的办法，但是现在主流的实现都使用了Joint Consensus（联合共识）算法。
Joint Consensus算法如何解决可用性问题
针对上面提到的：替换同一机房中的不同节点，中间过程中可能由于这个机房被网络隔离，导致的集群不可用（选不出leader）问题，来看看Joint Consensus算法是如何解决的。
先来回顾一下步骤，如果使用Joint Consensus算法，需要经历两阶段提交：
- 首先提交
C_Old$\bigcup$C_New。 - 然后提交
C_New。
把集合换成这里的例子，就是：
- 首先提交
{a,b,c}$\bigcup${a,b,c,d}。 - 然后提交
{a,b,c,d}。
来看这两阶段中可能出现宕机的情况：
- 第一阶段时leader节点宕机，这个leader节点只有可能是两种情况，其集群配置还是
C_Old，或者已经收到了C_Old$\bigcup$C_New：C_Old：由于这时候这个leader并没有第一阶段提交的C_Old$\bigcup$C_New节点集合变更，因此那些已有C_Old$\bigcup$C_New节点集合的follower这部分的日志将被截断，成员变更失败，回退回C_Old集合。C_Old$\bigcup$C_New：这意味这个leader已经有第一阶段提交的C_Old$\bigcup$C_New节点集合变更，可以继续将未完成的成员变更流程走完。
类似的，在第二阶段时leader节点宕机，也不会导致选不出leader的情况，可以类似推导。
可见：直接使用Joint Consensus算法并不会存在单步变更时的可用性问题。
总结
- Raft集群的单步变更算法，虽然看起来”简单“，但是实践起来有不少细节需要注意。
- 虽然论文里提到单步变更算法比之Joint Consensus算法更为简单，很多开源的Raft实现都已经以Joint Consensus算法做为默认的实现了。
（之前写过etcd 3.5版本的实现解析，见：etcd 3.5版本的joint consensus实现解析 - codedump的网络日志）