raft 算法中的集群成员变更问题
前言
在上一篇文章中我们讲解了 raft 算法的领导者选举以及日志复制的问题，同时通过一个具体实例讲解了 raft 是如何通过“一切以领导者”为准来解决日志不一致的情况的。同时在文章结尾笔者也讲到 raft 算法包含的内容远不止这么多，甚至上述的一些问题都是 raft 中的 base（基础）问题。接下来，我们将会用一篇文章来继续讲解 raft 需要解决的另外一个难题 -- 成员变更问题。
为什么会有成员变更
首先我们要有一个常识：一台服务器不可能永远无故障地运行下去，即使服务器不会发生问题，那么也许是因为网络问题、亦或是集群本身的 bug，都有可能导致某个节点不可用。在这个时候，我们往往会选择新增一个或多个节点来替换掉不可用的节点，从而产生了成员变更。同时，一家公司的发展不可能永远不变，我们的业务规模也就不可能永远不变，这个时候，集群规模的变更也就是顺理成章的事情了。
也许有的同学会说，想要新增节点的话，那就直接新增好了，反正 raft 会通过日志一致性算法将新节点不存在的日志复制过去。但是事实果真如此吗？
成员变更会产生什么问题
不妨我们假设原始集群中有 3 个节点 A、B、C，它们当前的日志状态如下：
我们要意识到，基于日志复制“大多数”原则，上述的日志情况是完全有可能存在的，因为对于三节点的集群来说，最新的那条日志项已经被成功复制到了大多数集群，那么它便可用被领导者应用到状态机。
假设我们现在想要往集群中新增两个节点 D、E，大家可用想一下，假设我们直接将两个节点添加到集群中，会产生什么问题？
我们都了解到 raft 算法具有领导者唯一性，这是实现数据一致性的首要保证，一旦集群中有两个领导者节点，那么将会产生及其严重的数据不一致，这显然对于保证严格一致性的 raft 算法是无法接受的。而像上述那样直接添加两个节点，由于每个节点新旧配置更新的时间不同，导致在某一时刻可能存在新旧配置两个大多数情况的存在，便很有可能使集群发生“脑裂”，也就是出现两个领导者。比如在进行成员变更的时候，节点 A 和 B、 C 产生了网络分区，如果此时新增的节点 D、E 和 A 在同一个分区，那么对于新配置中的领导者 A 而言，集群中依然有大多数节点在正常运行，它依然是领导者，而对于维护了旧配置的节点 B、C 来说，由于接收不到领导者的心跳请求，那么通过领导者选举算法，节点 B 会变成此分区的领导者，此时，整个集群中便产生了两个领导者，分别是节点 A 和节点 B：
当然，以上是针对往集群中添加节点的情况，其实从集群中同时移除多个节点也同样会发生上述问题，这个大家不妨按照相同的思路来自己推理一下（提示：从 5 节点集群中移除两个日志相对完整的节点）。
因此通过上面的分析我们可以发现，当新增多个新的节点的时候，我们不能直接将所有新节点添加到集群中。
那么有没有什么办法可以解决上述问题呢？
解决成员变更问题
raft 解决成员变更问题主要有两个方法，分别是联合共识算法和单节点变更算法。
方法一 -- 联合共识（Joint Consensus）
联合共识算法是 raft 作者首先提出的一种方法。此方法允许一次性向集群中插入多个节点而不会出现脑裂等 (safety) 问题，并且整个集群在配置转换的过程中依然能够接收用户请求，从而实现配置切换对集群调用方无感知。
在联合共识阶段，集群工作需要考虑到新旧两种配置，具有如下约束或者约定:
•约定一：日志会被复制到新老配置的所有节点；•约定二：新老配置的节点都可以被选举为领导者；•约定三：选举和日志复制阶段需要在新老配置上面都超多半数才能被提交生效。
下图是官方论文中出现的图，代表联合共识阶段配置变更的时间线：
其中，虚线代表已创建但是未提交的配置项，实线代表最新的已提交的配置项。领导人会首先创建 Cold_new 日志项，并复制到新旧配置中的大多数，此时所有的日志项都需要被联合共识。然后创建 Cnew 日志项，并复制到 Cnew (新配置) 中的大多数。这样旧配置和新配置就不会存在可以同时做出决策的时间点。
假设之前一共有三个节点 A、B、C，现在要往集群中添加两个节点 D、E。我们一起来看一下联合共识的流程。
1.首先领导者向集群中发送一条配置变更日志，告诉其他节点集群中要新增两个节点。根据约定一，日志会被复制到新老配置的所有节点。需要注意的是，raft 算法在日志复制过程中会保证日志完整性，所以新节点在复制 Cold_new 之前会同步领导者的数据。
1.根据约定三，这条日志需要在新老配置中都达到超过半数节点复制成功，它才能被成功应用。也就是说需要老配置 (A,B,C) 和新配置 (A,B,C,D,E) 都达到半数以上，如下图所示，老配置的大多数 (A,B) 和新配置的大多数 (A,B,D) 已经复制成功：
1.Cold_new 被应用成功之后，领导者会生成一条新的日志 Cnew 复制到集群，告诉集群现在可用应用新的配置项了。跟随者节点收到这条日志之后，会马上切换到新集群配置（这里同样要注意 raft 的一致性检查机制，会保证在复制 Cnew 之前，Cold_new 会首先被复制），由于此时领导者已经处于新配置状态，因此它只要被复制到新配置的大多数节点即可提交，而不需要联合共识了。
在联合共识阶段，整个集群依然能够对外提供服务，只是日志需要像上述流程那样被新老配置同时应用才行。对于新的节点 D、E，raft 会通过日志一致性检查来复制领导者的所有日志项，从而保证它们同样能够保持日志完整性。
以上就是往集群中新增节点的流程，我们来看一下按照上述流程为什么不会产生脑裂。我们依然假设集群产生了 2，3 分区，分别是 (A,B) 和 (C,D,E)：
•如果此时领导者 A 还没有复制任何一条 Cold_new，那么领导者 A 不会应用 Cold_new，(A,B) 分区依然是旧配置，A 是领导者；而 (C,D,E) 分区由于 C 会接收心跳超时而发起选举，但是它不会感知到 D、E 的存在，无法获取到大多数节点的投票。因此两个分区只会有一个领导者，符合预期。•如果领导者复制了 Cold_new 之后发生了网络分区。如果 Cold_new 没有被大多数节点确认，那么领导者 A 无法应用 Cold_new，(A,b) 依然处于旧配置状态，对外提供服务，此时 (C,D,E) 分区无论谁发起领导者选举，都无法获取到大多数选票(旧配置状态的 C)或者被联合共识 (新配置状态的 D)。如果 Cold_new 已经被大多数节点复制，那么领导者 A 会应用此日志，然后复制 Cnew，但是 Cnew 日志无法被联合共识，领导者 A 后续不会提交任何日志（在一些实现中会自动退位为跟随者）；对于分区 (C,D,E)，C 无法获取到大多数选票，如果它没有复制 Cold_new，也不会投票给 D / E，此分区也无法选举出领导者。符合预期。•如果在 Cnew 阶段产生了分区，由于 raft 算法具有持久性，已经提交的 Cold_new 会永久生效，此时 (A,B) 分区无法获取大多数选票，不会选出新领导者，也就不可能发生脑裂，符合预期。
看到这里，相信很多读者都是云里雾里的（包括笔者本人=。=），因为这种方式确实具有很大的理解和实现难度，因此作者提出了第二种方法。
方法二 -- 单节点成员变更
单节点变更是 raft 作者提供的第二种方法，顾名思义，每次变更的时候都只新增一个节点。也就是说假设我们想新增两个节点 D、E，我们可用先将节点 D 添加到集群中，然后再添加节点 E。与方法一不同，单节点变更的方式在集群配置变更的过程中是不能对外提供工作的。
接下来让我们来具体看一下单节点变更是如何解决脑裂的问题的。
还是拿节点 A、B、C 为例，现在我们想要往集群中添加节点 D、E，与上述方法不同的是，我们这次选择一个一个地执行节点变更。
假设我们先添加节点 D，将集群变成 4 节点集群：
单节点变更的具体流程是：
•节点 D 向领导者申请加入集群；•领导者 A 向新节点 D 同步数据；•领导者 A 将新配置 [A、B、C、D] 作为一个日志项，复制到配置中的所有节点，然后应用新的配置项（这里需要注意的是，每个节点接收到新的配置项肯定是有时差的）；•如果新的日志项应用成功（被大多数节点复制成功），那么新节点添加成功。
然后针对节点 E，同样走一次上述流程，完成新增节点。
我们不妨来看一下只添加一个节点为什么不会出现脑裂问题。假设新增节点 D 的过程中产生了分区，我们以以下几种分区情况分别讨论一下：
•网络分区成 (A,B) 和 (C,D) 两部分，如果节点 A、B 此时维护的还是旧的配置，那么 A 依旧是领导者，节点 C 因为分区开始发起领导者选举，此时如果 C 维护的是旧的配置 (A,B,C)，那么此时它不会得到节点 D 的投票，无法成为领导者；节点 C 如果维护的是新的配置，那么分区中节点个数不超过一半，它依然不会变成领导者，符合预期。当分区消失之后，节点 D 由于发现自己还没有完成入集群操作，从而会继续向领导者发起“进入集群申请”，领导者便会继续走一遍上述流程。
•网络分区成 (A,B) 和 (C,D) 两部分，如果节点 A、B 此时维护的是新配置，那么 (A,B) 分区由于无法获取到大多数选票而无法选出领导者，(C,D) 分区同情况 1， 这样的话两个集群都不会成功选举出新的领导者。此时便可能需要人工进行介入，但是集群中依然不会存在两个领导者。
•A、B、C 在同一个分区，剩余的一个节点 D 在另外一个分区，此时只有包含三节点的分区能选举出领导者，正常处理请求，符合预期。当分区消失了之后，节点 D 会正常接收自己缺失的日日志项，从而更新自己维护的配置信息（在这里我们可用发现，节点 D 虽然已经在集群中，但是在它自己看来，自己确是被孤立的节点）。同样的当分区消失之后，节点 D 会再次申请“进群”。
对于新增节点 E 或者从集群中删除一个节点的情况也是一样的，大家可以自己来推导一下看看。
其实单节点变更体现了一个最基本的数学知识：
就是一个数字肯定小于两个超过数字一半的数字之和。对于 raft 集群来说，旧配置的大多数与新配置的大多数之和一定大于新配置的节点个数。由于 raft 算法的领导者选举需要获得超过大多数选票，而当我们只新增一个节点的时候，旧配置的大多数和新配置的大多数不可能同时存在（否则必定有至少一个节点同时属于两个分区，这显然是不可能存在的），因此两个分区只有一个分区可能选举出领导者。正如下图所示（来自《CONSENSUS: BRIDGING THEORY AND PRACTICE》[1]）：
当然有的同学可能会问了：还有一种情况是一个分区里面既包含旧配置也包含新配置，这个时候会有什么现象发生呢，会不会存在两个分区选出了两个维护旧配置的领导者节点呢？答案是不会的。原因就是维护旧配置的节点不会向新节点发起投票请求，也不会投票给新的节点，因为它并不知道集群中有新的节点；同时按照“日志完整性原则”，维护了新配置的节点（日志更完整）也不会投票给维护旧配置的节点。所以这种情况反而降低了分区中旧配置节点获取选票的可能性。大家不妨自己按照上面的方式来推导一下看看。
结语
从原理和实现上来看，单节点变更的复杂度要比联合共识算法低的多，因此单节点变更的方式也就成了很多 raft 实现的首选算法。
到此为止，我们通过两篇文章以及具体示例大致了解了 raft 算法的领导者选举、日志复制以及节点变更等问题，这是 raft 最基础也是最重要的几个点。其实我们了解 raft 算法并不是为了了解其实现细节，而是管中窥豹，通过 raft 算法本身，来提炼出它所蕴含的丰富的理论基础，这些理论基础才是对我们大有裨益的，因为我们在工作中，自己去实现一个 raft 算法基本是不可能的，反而“如何将数据变更同步到集群其他节点”诸如此类的问题我们倒是有可能会遇到。
当然由于笔者能力有限，本文只是笔者在读了论文和其他一些资料之后的总结，有些地方并不是很全面，如果有任何纰漏，欢迎大家评论指正。
参考
•《CONSENSUS: BRIDGING THEORY AND PRACTICE》[2]•分布式协议与算法实战[3]