Raft 共识算法学习笔记 三:成员变更

文章 《Raft 共识算法学习笔记 一:领导人选举》《Raft 共识算法学习笔记 二:日志复制》 分别讲述了 Raft 算法如何进行领导人选举和如何进行日志复制。

这篇文章继续讲述 Raft 算法如何处理集群成员节点变更的问题。

考虑一种场景,原来 Raft 集群中存在三个节点,现在需要增加2 个节点。那么,在这种情况下, Raft 算法如何能保证同一个任期内,只有一个领导者呢?

Raft 论文中,作者使用配置(configuration)来表示集群由哪些节点组合,即集群所有节点的信息集合。在稳定状态下,所有节点的配置都是一致的。

由于集群存在多个节点,因此,一次性原子地更新所有节点的配置是不可能的,集群在更新配置的过程中,可能会出现新旧配置的两个大多数:

例如,上图中,集群的节点数量 由 3 个增加至 5 个。由于各个节点可能在不同的时间进行新旧配置的转换,因此,可能存在一段时间,集群中在同一个任期内,存在两个领导者。一个领导者由使用旧配置的大多数选举产生,即图中节点 1, 2;一个领导者由使用新配置的大多数选举产生,即图中节点 3,4,5。
这显然是跟 Raft 算法的规定相悖的。

为解决成员变更时领导者选举的问题,Raft 作者提出了几种方法。例如,可以先将集群原来所有节点关闭,更新其配置后,再启动新的集群。由于所有节点的配置都是固定的,Raft 可以保证同一任期只有一个领导者。不过此方法会导致每次成员变更时都需要关闭集群,导致集群无法对外提供服务。

Raft 作者还提出一种“联合共识”(joint consensus)的方法,不过此方法实现起来比较复杂,本文也不再赘述,有兴趣可以参考 Raft 论文 有关联合共识的描述。

本文重点讲述单节点变更(single-server change)的方法。

单节点变更,即每次只允许增加或者删除一个节点,如果集群需要增加或者删除多个节点,可以通过执行多步的单节点操作实现。例如,如果需要将集群节点数量从 3 调整到 5 ,可以执行 2 次单节点变更操作,先将节点数量从 3 调整到 4,再从 4 调整到 5。

为什么单节点变更方法可以解决成员变更可能带来的同一个任期存在多个领导者的问题呢?

这是由于,不管集群节点数量是偶数,还是奇数,不管是增加节点,还是删除节点,集群中新旧配置的大多数都会存在重叠的情况,如下图所示:

上图蓝色区域表示采用旧配置的大多数,红色区域表示采用新配置的大多数。对于单节点变更来说,新旧配置的大多数都会存在节点重叠的情况。在 Raft 中,节点在同一个任期只有一张选票,因此,重叠的节点在同一个任期内不会投出两张选票,这样就不会出现同一任期存在两个领导者的现象。

需要指出的是,在出现分区错误,节点故障的情况下,如果并发执行单节点变更,可能会出现一次单节点变更还没完成,新一次单节点变更已经执行,导致集群出现 2 个领导者的问题。
为解决此问题,可以在领导者启动时,创建一个 O_OP 志项,只有当领导者将 O_OP 日志项应用后,再执行成员变更请求。

参考资料