引言：以前阅读Raft大论文的时候，对“集群变更”这部分内容似懂非懂。于是最近又重读了大论文这部分的内容，以下是重读时做的一些记录。这部分内容打算分为两篇文章，上篇讲解成员变更流程的理论基础，下篇讲解实践中存在的问题。

重读Raft论文中的集群成员变更算法（一）：理论篇

“集群成员变更（cluster membership change）”意指一个集群内节点的增、删操作，这在一个分布式系统中是必不可少的操作，因为并不能保证一个集群的所有节点都一直能工作的很好。Raft大论文《Consensus: Bridging Theory and Practice^[1]》中有专门的一节来讲解这部分内容。

安全性

首先，Raft算法中要求所有操作都需要保证安全性（safety），即：任何时候都不能在集群中同时存在两个leader节点。“集群成员变更”算法也必须保证安全性这个大前提不能被破坏，于是论文中阐述了为什么直接变更多个节点是不被允许的：

在上图的图示中：

• • 旧集群有1、2、3这三个节点，而需要将这个三节点的集群新增节点4、5变更到5节点集群去。

• • 如果直接如图中这样变更，由于每个节点的时间窗口并不一致，可能就会出现这种情况：

• • 在某一时刻，节点1、2还使用的是旧集群（只含有{1,2,3}）的成员配置，而3、4、5已经是新集群（含有{1,2,3,4,5}）的成员配置了。

• • 这样就可能出现还使用旧集群节点配置的1、2选出了一个leader，以及已经使用了新集群配置的节点3、4、5选出了另一个leader的情况，于是违反了上面阐述的“安全性”要求。

需要说明的是，在上面这个错误的示例中，是由于有两类行为同时出现才导致的错误：

• • 一次性变更多个节点。在例子中，一次性把4、5两个节点加入到集群中。

• • 直接（directly）变更。直接变更由于集群中不同节点的步子不一样，而不一样的节点如果出现了两个不同的集群，那么就可能导致选出两个不同的leader。

于是，由于这两个错误操作是一起发生才会导致错误，论文中给出了两种方案：

• • 要么一次性严格限制只变更一个节点。

• • 如果实在想一次变更多个节点，那就不能直接变更，需要经过一个中间状态的过渡之后才能完成同时变更多个节点的操作。

以下分别来阐述这两种不同的实现。

一次变更单个节点

如果限制每次只变更一个节点，那么就能保证“新、旧集合的quorum集合是有重合的”，由于有重合，这样就能保证新旧两个集群的集合不会选出不同的leader，就能间接保证安全性。

论文中以下面几个例子来说明这样操作的正确性：

这几个图，是在两个维度上做示范的：

• • 增、删操作。

• • 原集群节点数量是奇数还是偶数。

两个维度的组合一共就是上面的4中情况，但是无论哪一种情况，由于都保证了“新、旧集合的quorum集合是有重合的”这个条件，于是不会选出不一样的leader来。

一次变更多个节点

从上面的例子中可以看到：只要能保证一次只变更一个节点，是可以直接（directly）变更的。即：无需中间状态，直接从A集合变更到A+1集合，因为这两个集合的quorum肯定有重合。

但是，在一次需要变更多个节点的情况下，就不能这样直接变更，因为会出现最开始示例的那样同时选出两个leader的情况。于是，为了解决这个问题，需要引入一个中间状态：

• • 假设原先的集群节点集合为C_Old，新的集群节点集合为C_New，那么首先变更配置到{C_Old,C_New}，也就是新旧集群节点集合的并集。

• • 上面这次变更提交之后，再向集群变更配置到C_New。在这次变更提交之后，那些不在C_New节点集合中的节点，收到这个变更时，自动下线退出集群。

可以证明：上面两个步骤中，都不会出现“同时存在两个leader”的情况。

从本质上来说，这种变更算法，属于一种两阶段的成员变更算法，Raft大论文中称之为“Joint Consensus（联合共识）”算法。下图中演示了Joint Consensus算法这两个阶段的流程：

Failover

我们来看看Joint Consensus算法，在变更过程中如果出错，是如何failover选出新leader的。

第一阶段，这时候选出来的leader只有可能有两种情况，还是旧的C_Old节点集合，或者已经收到了{C_Old,C_New}节点集合：

• • 只有C_Old节点集合的节点：由于这时候这个leader并没有第一阶段提交的{C_Old,C_New}节点集合变更，因此那些已有{C_Old,C_New}节点集合的follower这部分的日志将被截断，成员变更失败，回退回C_Old集合。

• • 有{C_Old,C_New}节点集合的节点：这意味这个leader已经有第一阶段提交的{C_Old,C_New}节点集合变更，可以继续将未完成的成员变更流程走完。

类似的，也可以去推导一下在第二阶段出现leader宕机时，选出来的leader只可能具备两种情况，但是这两种情况都不可能选出多个leader。

集群变更何时生效？

以上讲解完毕两种不同的集群变更方式，下面来聊一聊集群变更何时生效。

在Raft、Paxos这类状态机模型的一致性算法中，将任何变更操作都认为是一个命令（Command），命令的处理流程是这样的：

• • 状态机收到命令，首先在自己本地将命令持久化。

• • 然后广播给集群中的其他节点。

• • 当收到集群半数以上节点的应答时，认为命令是可以被提交（commit）的，于是可以生效将这些已经被提交的日志传给应用层的状态机使用了。

以上流程可以看到：一条命令，只有在“提交（commit）”之后才能“生效（apply）”。

在Raft中，“成员变更”这个操作，也是一类命令，即：

struct Command {
    LogEntry,
    MembershipChange,
};

这样设计的好处在于：处理成员变更操作，和一般的日志并没有区别，于是不存在一个特定的时间被称为“处理成员变更的时间”，在这个时间里停止响应一般的命令。

但是与一般命令不同的是，“成员变更”操作并不需要等到多数通过才能生效。注意，对于一般命令而言，要“生效”必须首先“提交”，而集群变更类命令的生效没有这个依赖关系。

即，在Raft的成员变更流程中，节点在收到一个新集群节点配置之后，是马上生效的，无需等待半数以上通过。

这是在阅读Raft论文这一部分内容时，经常被忽略的部分。为什么集群变更类指令，可以这么做，以及这样做会不会出问题？

为了安全性，Raft在进行集群变更操作时，无论是“单次变更一个节点”还是“一次变更多个节点”，在不同的阶段都不能有重叠（overlap）的情况出现，因为重叠意味着可能违反前面提到的安全性。比如将一个集群节点集合从{1,2,3}变更为{1,4,5}，如果使用这两种方式，步骤分别是：

• • 单次变更一个节点：{1,2,3}->{1,2,3,4} （增加节点4）->{1,2,3,4,5} （增加节点5）->{1,3,4,5} （删除节点2）-> {1,4,5} （删除节点3）。

• • 单次变更多个节点：{1,2,3}（C_Old）-> {1,2,3,4,5}（{C_Old,C_New}）-> {1,4,5}（C_Old,C_New）。

可以看到，无论采用哪一种方式，都会有多个步骤。由leader来决定当前的步骤，其判断的标准是：前一步修改的日志，是否已经被提交（半数以上同意）。所以，如果成员变更类的日志在提交之后才生效的话，leader就需要再多一个步骤：

• • 首先确认日志已经被提交到半数以上节点。

• • 在这之后，再确认这个成员变更已经在节点上生效。

而后面的这个确认，是可以避免的。因为根据前面failover部分的分析，无论哪一种情况出现，即便在变更的过程中leader宕机，也不会出现选出多个leader的情况。

于是，对于成员变更类的日志来说，Raft的规则是：

• • 多次提交不能重叠（overlap），即如果当前已经有还未提交的成员变更日志，在它提交之前不允许提交新的成员变更修改。

• • 成员变更的生效，无需等待提交，每个节点在收到这类日志的时候，就能马上修改本节点上的成员为最新的这个配置。

总结

• • Raft算法要求任何时候都要保证安全性（safety）：不能在同一时间在集群中存在两个不同的leader节点。

• • 如果以下两个操作同时发生，就有可能违反安全性：

• • 一次变更多个节点。

• • 直接变更集群的节点集合。

• • 由这两个限制出发，分别有以下两种实现成员变更的算法：

• • 限制每次只变更一个节点，这种情况下可以直接变更成员。

• • 每次可以变更任意数量的节点，但是必须通过两阶段提交完成才能生效：第一次从C_Old变成{C_Old,C_New}节点集合，第二次从{C_Old,C_New}变成C_New。

• • “成员变更”类命令，在Raft算法看来也是一条日志。但是与普通日志命令不同的是，成员变更类日志的生效，无需等待这条日志提交了才能生效，可以在收到之后马上生效。

引用链接

[1] Consensus: Bridging Theory and Practice: https://web.stanford.edu/~ouster/cgi-bin/papers/OngaroPhD.pdf

往期推荐：