概述

在以前的etcd实现中,“集群节点变更”这一功能,仅支持每次变更一个节点,最新的etcd已经能支持一次变更多个节点配置的功能了。本文将就这部分的实现进行解析。

原理

Raft论文《CONSENSUS: BRIDGING THEORY AND PRACTICE》的第四章”集群成员变更“中,支持两种集群变更方式:

  • 每次变更单节点,即“One Server Config Change”。
  • 多节点联合共识,即“Joint Consensus”。

本文先就这两种实现方式进行原理上的讲解。

集群节点变更的问题

要保证Raft协议的安全性,就是要保证任意时刻,集群中只有唯一的leader节点。如果不加限制条件,那么动态向当前运行集群增删节点的操作,有可能会导致存在多个leader的情况。如下图所示:

集群节点变更问题

图中有两种颜色的配置,绿色表示旧的集群配置(C_old),蓝色表示新的集群配置(C_new),如果不加任何限制,直接将配置启用,由于不同的集群节点之间,存在时间差,那么可能出现这样的情况:

  • Server{1,2}:当前都使用旧的集群配置,所以可能选出server1为集群的leader。
  • Server{3,4,5}:当前都使用新的集群配置,可能选出server3为集群的leader。

由上图可以看到:如果不加任何限制,直接应用新的集群配置,由于时间差的原因,可能导致集群中出现两个不同leader的情况。

单节点成员变更(One Server ConfChange)

“单节点成员变更”,意指每次只添加或删除一个节点,这样就能保证集群的安全性,不会在同一时间出现多个leader的情况。之所以能有这个保证,是因为每次变更一个节点,那么新旧两种配置的半数节点(majorrity)肯定存在交集。以下图来说明:

单节点成员变更

上图演示了向偶数或奇数的集群增删一个节点的所有可能情况。不论哪种情况,新旧配置都有交集,在每个任期只能投出一张票的情况下,是不会出现多leader的情况的。

有了上面的理论基础,下面来看单节点集群变更的全流程,当下发集群节点变更配置时,新的配置会以一种特殊的日志方式进行提交,即:

  • 普通日志:半数通过,提交成功时,会传给应用层的状态机。
  • 配置变更类日志:半数通过,提交成功时,集群节点将以新的集群配置生效。

其流程如下:

  • 将集群配置变更数据,序列化为日志数据,需要将日志类型标记为集群配置变更类的日志,提交给leader节点。
  • leader节点收到日志后,需要存储该日志的索引为未完成的集群配置变更索引,像其它正常日志一样处理:先写本地的日志,再广播给集群的其他节点,半数应答则认为日志达成一致可以提交了。如果提交了这类日志,可以将前面保存的未完成的集群配置变更索引置为空了。
  • 集群配置变更日志提交之后,对照新旧的集群变更数据,该添加到集群的添加到集群,该删除的节点停机。

需要注意的是,同一时间只能有唯一一个集群变更类日志存在,怎么保证这一点?就算是在leader收到该类型日志时,判断未完成的集群配置变更索引是否为空。

多节点联合共识(Joint Consensus)

除了上面的单节点变更,有时候还需要一次提交多个节点的变更。但是按照前面的描述,如果一次提交多个节点,很可能会导致集群的安全性被破坏,即同时出现多个leader的情况。因此,一次提交多节点时,就需要走联合共识

所谓的联合共识,就是将新旧配置的节点一起做为一个节点集合,只有该节点集合达成半数一致,才能认为日志可以提交,由于新旧两个集合做了合并,那么就不会出现多leader的情况了。具体流程如下:

  • leader收到成员变更请求,新集群节点集合为C_new,当前集群节点集合为C_old,此时首先会以新旧节点集合的交集C_{old,new}做为一个集群配置变更类的日志,走正常的日志提交流程。注意,这时候的日志,需要提交到C_{old,new}中的所有节点。
  • C_{old,new}集群变更日志提交之后,leader节点再马上创建一个只有C_new节点集合的集群配置变更类日志,再次走正常的日志提交流程。这时候的日志,只需要提交到C_new中的所有节点。
  • C_new日志被提交之后,集群的配置就能切换到C_new对应的新集群配置下了。而不在C_new配置内的节点,将被移除。

可以看到,多节点联合共识的提交流程分为了两次提交:

  • 先提交新旧集合的交集C_{old,new}
  • 再提交新节点集合C_new

以下图来说明,这几个阶段中,集群的安全性都得到了保证:

多节点联合共识

  1. C_{old,new}配置提交之前:在做个阶段,集群中的节点,要么处于C_old配置下,要么处于C_new,old配置之下。此时,如果集群的leader节点宕机,那么将会基于C_old或者C_new,old配置来选出新的leader,而不会仅仅基于C_new,因此不会选出不同的leader
  2. C_{old,new}配置提交之后,C_new下发之前:如果这时候leader宕机,只会基于C_{old,new}的配置选出leader,因此也不会选出不同的leader
  3. C_new下发但还未提交时:如果这时候leader宕机,只会基于C_{old,new}或者C_new的配置选出leader,同时也不再会发给仅仅在C_old中的节点了,所以无论是哪个配置,都需要得到C_new的半数同意,因此不会选出不同的leader
  4. C_new提交之后:此时集群中只有一种配置了,安全性得到了保证。

实现

了解了原理之后,可以来具体看etcd 3.5中这部分的实现了。

learner

首先需要了解learner这个概念,在Raft中,这类型节点有以下特点:

  • 与其他节点一样,能正常接收leader同步的日志。
  • 但是learner节点没有投票权,即:投票时会忽略掉这类型节点。

也因为这样,所以learner节点也常被称为non voter类型的节点。

那么,什么时候需要learner节点呢?如果一个节点刚加入集群,此时要追上当前的进度,需要一段时间,但是由于这个新节点的加入,导致集群的不可用风险增加了,即原来三节点的集群,挂了一个还能工作;加入这个新节点之后,新节点还没赶上进度,那么可能挂了一个节点集群就不可用了。

所以,对于新加入的节点,可以先将它置为learner类型,即:只同步日志,不参与投票。等到进度追上了,再变成正常的有投票权的节点。

一个节点,需要添加到集群中变成集群的learner,或者从原集群的voter变成learner,也都不能直接添加,而是必须走前面正常的集群变更流程,即:集群中的learner集合也是集群节点配置的一部分。

数据结构

每个节点的进度数据(Progress结构体)

etcd中,使用Progress结构体来存储集群中每个节点当前的进度数据,包括以下成员:

  • 日志索引类成员:
    • Match索引
    • Next索引。
  • 当前的进度状态:
    • 探针状态(probe):节点刚加入,或者刚恢复都是该状态。
    • 正常同步状态(replicate)。
    • 同步快照状态:当前没有在进行日志同步,而是在同步快照。
  • IsLearner:标记当前该节点是否是learner状态的节点。

其中,进度状态类似于TCP协议中的流控,不在这里做阐述了;两个日志索引也是Raft论文中用于存储节点进度数据的索引,也不在这里阐述了;唯独需要注意的是IsLearner,该成员标记了该节点是否learner节点。

集群配置(Config结构体)

集群配置使用Config结构体来保存,其成员如下:

  • Voters:包括新旧两个配置。新旧两个配置的节点集合合集,成为当前的所有节点集合。
    • [0]:incoming配置,新的集群配置。
    • [1]:outgoing配置,旧的集群配置。一般这个集合为空,这个集合不为空时,存储的是变更之前旧的集群配置,因此不为空时表示当前有未提交的joint consensus
  • Learners:当前的learner集合,learner集合和前面的所有节点集合交集必须为空集。
  • LearnersNext:集群配置提交后,从原集群的voter降级为learner的节点集合。
  • AutoLeave:该配置为true时,自动让新配置生效。

前面原理的部分,只讲解了新旧配置的变更流程,但是在etcd的实现中,集群配置里除了新旧配置,还多了存储Learner节点的两种集合,这会让情况变得更复杂一些。

如果一个节点要在新的集群配置中变成Learner,需要区分两种情况:

  • 该节点原先是集群的voter:并不是直接加入到Learner集合的,而是首先提交到LearnersNext集合中,同样也是等待这个新的集群配置被成功之后,才移动到Learner集合中。否则,如果直接修改加入到Learner集合中,可能导致集群的安全性受到影响。比如一个三节点{a,b,c}的集群,原先有只挂了一个节点还能继续工作;现在由于各种原因,想将节点c降级为learner,将节点d加入到集群中,如果直接将c节点降级为learner,就会导致在这个流程里一旦一个节点不可用,整个集群就不可用了。
  • 该节点原先不是集群中的成员:这种节点由于之前并不存在,并不影响集群的安全性,这时候可以直接移动到Learner中。

单节点成员变更

所以:Voters两个配置,与两种Learner集合,必须满足以下的关系(见函数checkInvariants):

  • LearnersNext中的节点,表示未提交的集群配置中待添加learner节点集合的节点:
    • 必须出现在outgoing中,即必须出现在旧的集群配置中。
    • 该节点的进度数据中,IsLearner为False。
  • Learners中的节点,表示当前集群的learner节点集合:
    • 不能出现在任一个voter集合中(incomingoutgoing)中,即不能出现在新、旧的集群配置中。
    • 该节点的进度数据中,IsLearner为True。

集群整体监控(ProgressTracker结构体)

有了节点的进度数据(Progress结构体),以及集群配置数据(Config结构体),整个集群的进度管控,都放在了结构体ProgressTracker中:

  • Config:存储当前集群的配置。
  • Progress:以节点ID为键,值为Progress结构体的map。

负责提交配置流程(Changer结构体)

Changer属于提交流程中存储中间状态的数据结构,对其输入:

  • 当前的ProgressTracker结构体数据,即当前的配置和进度数据。
  • 要进行的变更数据。

输出:

  • 需要提交的配置数据。

Raft最终以其输入的配置数据,来生成集群配置类型的日志,走正常的日志提交流程。提交成功之后,配置生效。

流程

按照前面原理部分的分析,多节点联合共识的提交分为两步:

  • 先提交新旧集合的交集C_{old,new}
  • 再提交新节点集合C_new

实际在etcd中,也是这样做的,分为:

  • EnterJoint:将新旧集合的交集提交。
  • LeaveJoint:提交新节点集合。

EnterJoint

该流程在Changer::EnterJoint中实现:

  • 拷贝当前ProgressTracker结构体当前的进度(Progress)和配置数据(Config)。
  • 如果当前有在提交的配置,就返回退出,因为同一时间只能有一个未提交的配置变更。如何判断当前是否有未提交的配置?看Config中的outgoing(即voters[1])是否为空。我们下面再详细解释。
  • 下面,以第一步拷贝的配置数据,生成新的配置数据:
    • Config中的incoming数据拷贝到outgoing中,即先保存当前的配置到outgoing
    • 遍历需要修改的配置,根据不同的操作类型做操作,生成新的配置:
    • 如果要删除某节点,调用Changer::remove函数:
      • incoming中删除该节点。
      • Learner以及LearnerNext集合中删除该节点。
    • 如果增加voter,调用Changer::makeVoter函数:
      • 该节点的进度数据中,IsLearner变为false
      • Learner以及LearnerNext集合中删除该节点。
      • 将节点ID加入incoming集合中。
    • 如果增加learner,调用Changer::makeLearner函数:
      • 调用Changer::remove函数先删除该节点。
      • 判断是否在outgoing配置中有该节点,表示该节点是降级节点:
      • 有:表示在新配置下变成了learner,但是此时并不能直接变成learner,所以这种情况下该节点加入到了配置的LearnersNext
      • 否则,说明是新增节点,直接加入到Learner集合中。
    • 上面生成了新旧配置的交集配置,以这个配置数据生成日志来进行提交,生效后应用该配置。

LeaveJoint

  • 拷贝当前ProgressTracker结构体当前的进度(Progress)和配置数据(Config)。
  • 下面,以第一步拷贝的配置数据,生成新的配置数据:
    • 遍历LearnersNext集合,将其中的节点:
    • 加入Learner集合。
    • IsLearner置为true。
    • 清空LearnerNext集合。
    • 遍历outgoing节点集合:
    • 如果一个节点,既不在incoming集合中,也不在Learner集合中,则认为在新的配置中没有该节点了,删除其进度数据。
    • 清空outgoing节点集合。
  • 上面生成了新旧配置的交集配置,以这个配置数据生成日志来进行提交,生效后应用该配置。

例子

以一个例子来说明上面的流程,假设集群当前的配置为:

  • 投票节点:{1,2}。
  • Learner节点:{}。

新提交的配置中有以下三个操作:

  • 新增投票节点:{3}。
  • 降级节点{2}为learner节点。
  • 新增Learner节点:{4}。

需要再次强调:无论是EnterJoint还是LeaveJoint操作,都并不会让配置马上生效,而是生成了一份待提交的配置,Raft拿到这份配置生成一个提交配置变更的日志,走正常的日志提交流程,待这条日志被半数通过时,才生效该配置。

阶段 incoming节点集合 outgoing节点集合 Learner节点集合 LearnerNext节点集合
提交之前 {1,2} {} {} {}
EnterJoint {1,3} {1,2} {4} {2}
LeaveJoint {1,3} {} {2,4} {}

读者可以对着上面的流程,以这个例子来理解一下。

自动提交

这里还有一个细节,即多节点联合共识是一个两阶段的提交流程:

  • EnterJoint之后,outgoing节点集合变为一个非空集合,这时候不再能提交新的配置,需要到LeaveJoint之后,才会清空这个集合。
  • 在etcd中,LeaveJoint操作,并不见得会自动执行。

是否在EnterJoint之后自动执行LeaveJoint,取决于当前提交的Config结构体中的AutoLeave字段,它有两种可能,见ConfChangeTransition枚举类型的定义:

  • ConfChangeTransitionAutoConfChangeTransitionJointImplicit:如果是这两种情况,都会自动做转换。
  • ConfChangeTransitionJointExplicit:需要用户手动执行LeaveJoint操作。

(见函数ConfChangeV2::EnterJoint的实现。)

参考资料

  • 《CONSENSUS: BRIDGING THEORY AND PRACTICE》chapter4”Cluster membership changes“
  • Learner | etcd