etcd 3.5版本的joint consensus实现解析

2022-01-01
13分钟阅读时长
分布式

概述

在以前的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集合中（incoming和outgoing）中，即不能出现在新、旧的集群配置中。
    • 该节点的进度数据中，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枚举类型的定义：

  • ConfChangeTransitionAuto和ConfChangeTransitionJointImplicit：如果是这两种情况，都会自动做转换。
  • ConfChangeTransitionJointExplicit：需要用户手动执行LeaveJoint操作。

（见函数ConfChangeV2::EnterJoint的实现。）

参考资料

  • 《CONSENSUS: BRIDGING THEORY AND PRACTICE》chapter4”Cluster membership changes“
  • Learner | etcd
#raft #分布式
下一页 sqlite3.36版本 btree实现（三）- journal文件备份机制

相关

为什么Raft协议不能提交之前任期的日志？
Etcd Raft库的日志存储
Etcd Raft库的工程化实现
Etcd存储的实现
etcd Raft库解析
Raft算法原理