一  引言

分布式系统运行过程中节点经常会出现故障，需要支持节点的动态增加、删除和替换。
成员变更是分布式系统绕不开的话题，特别是在一致性系统中，对于提升运维能力和服务可用性都有很大的帮助。
Raft提出的两阶段成员变更Joint Consensus是业界主流的成员变更方法，极大的推动了成员变更的工程应用。但Joint Consensus成员变更采用两阶段，一次变更需要提议两条日志， 在一些系统中直接使用时有些不便。虽然Raft也提出了单步成员变更方法，但单步成员变更方法一次只能增加或减少一个成员，限制较大，并且容易踩坑，一般不推荐使用。
那么很自然的想到，Joint Consensus成员变更能否只使用单步实现呢？本文对这个问题进行了深入探讨。

二  成员变更

我们先来回顾下一致性协议中的成员变更问题。成员变更是在集群运行过程中改变运行一致性协议的节点，如增加、减少节点、节点替换等。成员变更过程不能影响系统的可用性。
成员变更也是一个一致性问题，即所有节点对成员配置达成一致。但是成员变更又有其特殊性，因为在成员变更的过程中，参与投票的成员会发生变化。
图1 成员变更的某一时刻Cold和Cnew中同时存在两个不相交的多数派
如果将成员变更当成一般的一致性问题，成员变更过程中，各节点从旧成员配置Cold切换到新成员配置Cnew的时刻可能有差异，可能在某一时刻Cold和Cnew中同时存在两个不相交的多数派，形成双Quorum，破坏一致性。
为了解决这个问题，Raft提出了两阶段的成员变更方法Joint Consensus。

1  Joint Consensus成员变更

Joint Consensus成员变更为了避免双Quorum问题，引入一个联合成员配置Cold,new作为过渡配置， Cold,new是Cold和Cnew的组合。Cold与Cold,new的Quorum有交集，Cold,new与Cnew的Quorum也有交集。成员变更先从Cold切换到Cold,new，待Cold,new提交后，再切换到Cnew，保证Cold与Cnew不同时使用，因而不会形成双Quorum，保障安全性。
图2 Cold与Cold, new与Cnew三者的Quorum集合之间的关系
Joint Consensus使用两条日志完成成员变更过程。Leader收到成员变更请求后，先向Cold和Cnew同步一条Cold,new日志，此后所有日志都需要Cold和Cnew两个多数派的确认。Cold,new日志在Cold和Cnew都达成多数派之后才能提交，此后Leader再向Cold和Cnew同步一条只包含Cnew的日志，此后日志只需要Cnew的多数派确认。Cnew日志只需要在Cnew达成多数派即可提交，此时成员变更完成，不在Cnew中的成员自动下线。
图3 Joint Consensus成员变更过程
成员变更过程中如果发生Failover，老Leader宕机，Cold,new中任意节点都可能成为新Leader，如果新Leader上没有Cold,new日志，则继续使用Cold，Follower上如果有Cold,new日志会被新Leader截断，回退到Cold，成员变更失败；如果新Leader上有Cold,new日志，则继续将未完成的成员变更流程走完。

2  单步成员变更

Joint Consensus成员变更之所以需要两个阶段，是因为对Cold与Cnew的关系没有做任何假设，为了避免Cold和Cnew各自形成不相交的多数派而形成双Quorum，才引入了两阶段方案。
如果增强成员变更的限制，假设Cold与Cnew的Quorum交集不为空，Cold与Cnew就无法形成双Quorum，则成员变更就可以简化为一阶段。
实现单步的成员变更，关键在于限制Cold与Cnew，使Cold与Cnew的Quorum交集不为空。那么怎么样限制Cold与Cnew，才能使Cold与Cnew的Quorum交集不为空呢？方法就是每次成员变更只允许增加或删除一个成员。
图4 增加或删除一个成员时Cold与Cnew的Quorum
增加或删除一个成员时的情形，如图4所示，可以从数学上严格证明，只要每次只允许增加或删除一个成员，Cold与Cnew不可能形成两个不相交的Quorum。因此只要每次只增加或删除一个成员，从Cold可直接切换到Cnew，无需过渡成员配置，实现单步成员变更。
单步成员变更一次只能变更一个成员，如果需要变更多个成员，如实现替换成员等，可以通过执行多次单步成员变更来实现。
单步成员变更理论虽然简单，但却埋了很多坑，实际用起来并不是那么简单。先前的文章Raft成员变更的工程实践中有详细介绍。

三  两阶段成员变更的单步实现

Joint Consensus成员变更虽然通用但是采用两阶段，一次变更需要提交两条日志，单步成员变更虽然只需要提交一条日志，但是限制较大，一次只能变更一个成员。两者的优势能否结合呢？Joint Consensus成员变更能否只用单步实现呢？
Joint Consensus成员变更过程中，Cold,new日志的提交已经让各节点对Cnew配置达成了一致，那么Cnew日志有什么作用呢？能否在Cold,new日志提交后就从Cold,new配置切换到Cnew配置呢？这样是不是就可以不需要Cnew日志，变成单步实现了呢？
考虑Joint Consensus成员变更中Cnew日志的作用，Cnew日志在Cold,new日志提交之后发起提议，节点收到并持久化Cnew日志后从Cold,new配置切换到Cnew配置，不在Cnew配置中的成员在Cnew日志提交后下线。根据这个过程，可以总结出Cnew日志的作用：
  1. 通知节点在收到并持久化Cnew日志后从Cold,new配置切换到Cnew配置。
  2. 通知不在Cnew配置中的节点在Cnew日志提交后下线。
  3. 成员变更过程中发生Failover后，本地有Cnew日志的节点具有优先选举权。
如果能不使用Cnew日志同时又完成Cnew日志的工作，不就可以用单步实现两阶段的Joint Consensus成员变更吗？事实上已经有系统探索过这条路。

1  ZooKeeper成员变更

ZooKeeper从3.5.0版本开始在Zab的基础上支持了成员变更。ZooKeeper具有Primary Order特性，而使用两条日志的Joint Consensus成员变更无法保证Primary Order特性，为了既满足成员变更的通用性，又不丧失Primary Order特性，ZooKeeper在论文《Dynamic Reconfiguration of Primary/Backup Clusters》中提出了自己的成员变更方法，并在ZooKeeper中应用了此方法，比Raft的提出还早。
如图5是ZooKeeper成员变更协议，图中旧成员配置用S表示，新成员配置用S‘表示，P为Leader节点，图5展示了将B1和B2节点替换成B3和B4节点的过程：
图5 ZooKeeper成员变更协议
  • 为了让新节点追上最新数据，新成员配置S’中的新节点B3、B4先连接到当前的主节点P，P会向它们传输自己当前的状态作为他们的初始状态。在Zab协议中当备节点连接上主节点时这样的状态传输就会自动发生，并且会继续从主节点P接收所有后续的操作日志（例如图中的Op1和Op2），这个过程中节点B3、B4不参与投票。
  • 主节点P向连接到它的所有备节点（S U S‘）发送成员变更日志COP，COP日志中携带旧成员配置S和新成员配置S‘，并等待旧成员配置S中的节点确认。一旦S中的多数派确认了COP日志，就对S’达成了共识。
  • 在COP日志之前的日志只需要旧成员配置S中的多数派确认，可以在旧成员配置和新成员配置（S U S‘）中提交；在COP命令之后且在S’的激活消息ACTIVATE之前的日志需要新旧成员配置（S U S‘）两个多数派确认，并且只能在S’中提交；在S’的激活消息ACTIVATE后的日志，只需要在S‘中确认和提交。
  • 主节点P等待COP日志以及S'中COP之前的日志的确认。
  • 一旦新旧成员配置（S U S1）两个多数派都确认了COP日志，主节点P就提交COP日志，并广播一条激活消息ACTIVATE来激活新成员配置S’从而完成成员变更。与日志同步消息类似，ACTIVATE消息包含主节点P的Epoch，携带过时的Epoch的ACTIVATE消息将被忽略。
成员变更过程中如果发生Failover，可能出现下面几种情况：
如果在COP日志发送之前Failover，那么成员变更失败，在旧成员配置中重新选主后继续工作；
如果在COP日志发送之后并且在ACTIVATE之前Failover，新旧成员配置中任意节点都可能成为新Leader，如果新Leader上没有COP日志，则成员变更失败；如果新Leader上有COP日志，则继续将未完成的成员变更流程走完。
如果在ACTIVATE后Failover，成员变更已经完成，但还无法保证新Leader一定在新成员配置中，此时不在新成员配置中的节点还不能下线。因此在发送ACTIVATE消息后还需要在新成员配置中提交一条no-op日志，no-op日志提交后可保证新Leader一定在新成员配置中，不在新成员配置中的节点可以安全下线。
ZooKeeper利用异步的Commit消息，也即ACTIVATE消息来通知节点从新旧成员配置切换到新成员配置。使用异步的no-op日志让不在新成员配置中的节点安全下线。ZooKeeper的ACTIVATE消息和异步的no-op日志起到了Joint Consensus成员变更中Cnew日志的作用。

2  改进的单步实现

ZooKeeper成员变更协议不如Joint Consensus成员变更那么简洁，Joint Consensus成员变更通过两阶段可以利用协议本身而不需要做过多的限制来保证成员变更的安全性。那么ZooKeeper成员变更协议是否可以改进呢？
ZooKeeper成员变更协议中异步的ACTIVATE消息和no-op日志其实就是为了完成Joint Consensus成员变更中Cnew日志的作用，明白了这一点后那么也可以将Joint Consensus成员变更的Cnew日志改为异步的，在Cold,new日志提交后就认为成员变更完成，然后异步的提交Cnew日志。之所以可以将Cnew日志改为异步的，在Cold,new日志提交后就认为成员变更完成，是因为Cold,new日志一旦提交，各节点已经对新成员配置达成了一致，再也不会回退到旧成员配置了，剩下的过程最终一定会执行完成，Cnew日志最终一定会提交。
还有一种改进方法是继续保留ACTIVATE消息，但不使用no-op日志，那么怎么样保证切换到新成员配置的节点具有优先选举权呢？根据选举的安全性，具有最新日志的节点具有优先选举权，那么可以在选举的时候携带节点当前的成员配置，在日志一样新的情况下，优先给已经切换到新成员配置的节点投票，即可保证切换到新成员配置的节点具有优先选举权。新成员配置中的大多数节点切换到新成员配置后，不在新成员配置中的节点可以安全下线。

四  总结

Joint Consensus成员变更的提出极大的推动了成员变更的工程应用，其简洁优美并且通用，但是采用两阶段，一次变更需要提交两条日志。本文探讨了两阶段的Joint Consensus成员变更的单步实现方法，并做了一些改进，为成员变更的工程应用提供了更多的选择。

五  思考

  1. 为什么Cold,new日志提交后，Cnew日志最终一定会提交？
  2. 使用ACTIVATE消息让节点切换到新成员配置后，如果节点重启，如何保证继续使用新成员配置？
  3. 两阶段成员变更的单步实现还有没有其它实现方法？

分布式文件存储系统技术及实现

本课程针对分步式文件存储系统的实现进行讲解，首先分析为什么要使用这种分步式存储系统，以及这种系统在设计时需要注意的问题，并比较现在市面常见的分步式存储系统（HDFS、Ceph等），展示阿里Pangu系统针对其中问题的解决方法，并结合Pangu系统说明分步式存储系统的设计要点。
点击阅读原文查看课程～
继续阅读
阅读原文