09 | Raft算法（三）：如何解决成员变更的问题？

Mar 2, 2020

09 | Raft算法（三）：如何解决成员变更的问题？-极客时间



下载APP





关闭

讲堂部落提薪训练营云原生训练营架构实战营企业版极客商城兑换中心 App下载浏览器插件

渠道合作

推荐作者

09 | Raft算法（三）：如何解决成员变更的问题？

2020-03-02 韩健来自北京

《分布式协议与算法实战》

课程介绍



讲述：于航

时长13:13大小12.11M



你好，我是韩健。
在日常工作中，你可能会遇到服务器故障的情况，这时你就需要替换集群中的服务器。如果遇到需要改变数据副本数的情况，则需要增加或移除集群中的服务器。总的来说，在日常工作中，集群中的服务器数量是会发生变化的。
讲到这儿，也许你会问：“老韩，Raft 是共识算法，对集群成员进行变更时（比如增加 2 台服务器），会不会因为集群分裂，出现 2 个领导者呢？”
在我看来，的确会出现这个问题，因为 Raft 的领导者选举，建立在“大多数”的基础之上，那么当成员变更时，集群成员发生了变化，就可能同时存在新旧配置的 2 个“大多数”，出现 2 个领导者，破坏了 Raft 集群的领导者唯一性，影响了集群的运行。
而关于成员变更，不仅是 Raft 算法中比较难理解的一部分，非常重要，也是 Raft 算法中唯一被优化和改进的部分。比如，最初实现成员变更的是联合共识（Joint Consensus），但这个方法实现起来难，后来 Raft 的作者就提出了一种改进后的方法，单节点变更（single-server changes）。
为了帮你掌握这块内容，今天我除了带你了解成员变更问题的本质之外，还会讲一下如何通过单节点变更的方法，解决成员变更的问题。学完本讲内容之后，你不仅能理解成员变更的问题和单节点变更的原理，也能更好地理解 Raft 源码实现，掌握解决成员变更问题的方法。
在开始今天内容之前，我先介绍一下“配置”这个词儿。因为常听到有同学说，自己不理解配置（Configuration）的含义，从而不知道如何理解论文中的成员变更。
的确，配置是成员变更中一个非常重要的概念，我建议你这么理解：它就是在说集群是哪些节点组成的，是集群各节点地址信息的集合。比如节点 A、B、C 组成的集群，那么集群的配置就是[A, B, C]集合。
理解了这一点之后，咱们先来看一道思考题。
假设我们有一个由节点 A、B、C 组成的 Raft 集群，现在我们需要增加数据副本数，增加 2 个副本（也就是增加 2 台服务器），扩展为由节点 A、B、C、D、E， 5 个节点组成的新集群：
那么 Raft 算法是如何保障在集群配置变更时，集群能稳定运行，不出现 2 个领导者呢？带着这个问题，我们正式进入今天的学习。
老话说得好，“认识问题，才能解决问题”。为了帮你更好地理解单节点变更的方法，我们先来看一看，成员变更时，到底会出现什么样的问题？
成员变更的问题在我看来，在集群中进行成员变更的最大风险是，可能会同时出现 2 个领导者。比如在进行成员变更时，节点 A、B 和 C 之间发生了分区错误，节点 A、B 组成旧配置中的“大多数”，也就是变更前的 3 节点集群中的“大多数”，那么这时的领导者（节点 A）依旧是领导者。
另一方面，节点 C 和新节点 D、E 组成了新配置的“大多数”，也就是变更后的 5 节点集群中的“大多数”，它们可能会选举出新的领导者（比如节点 C）。那么这时，就出现了同时存在 2 个领导者的情况。
如果出现了 2 个领导者，那么就违背了“领导者的唯一性”的原则，进而影响到集群的稳定运行。你要如何解决这个问题呢？也许有的同学想到了一个解决方法。
因为我们在启动集群时，配置是固定的，不存在成员变更，在这种情况下，Raft 的领导者选举能保证只有一个领导者。也就是说，这时不会出现多个领导者的问题，那我可以先将集群关闭再启动新集群啊。也就是先把节点 A、B、C 组成的集群关闭，然后再启动节点 A、B、C、D、E 组成的新集群。
在我看来，这个方法不可行。 为什么呢？因为你每次变更都要重启集群，意味着在集群变更期间服务不可用，肯定不行啊，太影响用户体验了。想象一下，你正在玩王者荣耀，时不时弹出一个对话框通知你：系统升级，游戏暂停 3 分钟。这体验糟糕不糟糕？
既然这种方法影响用户体验，根本行不通，那到底怎样解决成员变更的问题呢？最常用的方法就是单节点变更。
如何通过单节点变更解决成员变更的问题？单节点变更，就是通过一次变更一个节点实现成员变更。如果需要变更多个节点，那你需要执行多次单节点变更。比如将 3 节点集群扩容为 5 节点集群，这时你需要执行 2 次单节点变更，先将 3 节点集群变更为 4 节点集群，然后再将 4 节点集群变更为 5 节点集群，就像下图的样子。
现在，让我们回到开篇的思考题，看看如何用单节点变更的方法，解决这个问题。为了演示方便，我们假设节点 A 是领导者：
目前的集群配置为[A, B, C]，我们先向集群中加入节点 D，这意味着新配置为[A, B, C, D]。成员变更，是通过这么两步实现的：
第一步，领导者（节点 A）向新节点（节点 D）同步数据；
第二步，领导者（节点 A）将新配置[A, B, C, D]作为一个日志项，复制到新配置中所有节点（节点 A、B、C、D）上，然后将新配置的日志项应用（Apply）到本地状态机，完成单节点变更。
在变更完成后，现在的集群配置就是[A, B, C, D]，我们再向集群中加入节点 E，也就是说，新配置为[A, B, C, D, E]。成员变更的步骤和上面类似：
第一步，领导者（节点 A）向新节点（节点 E）同步数据；
第二步，领导者（节点 A）将新配置[A, B, C, D, E]作为一个日志项，复制到新配置中的所有节点（A、B、C、D、E）上，然后再将新配置的日志项应用到本地状态机，完成单节点变更。
这样一来，我们就通过一次变更一个节点的方式，完成了成员变更，保证了集群中始终只有一个领导者，而且集群也在稳定运行，持续提供服务。
我想说的是，在正常情况下，不管旧的集群配置是怎么组成的，旧配置的“大多数”和新配置的“大多数”都会有一个节点是重叠的。 也就是说，不会同时存在旧配置和新配置 2 个“大多数”：
从上图中你可以看到，不管集群是偶数节点，还是奇数节点，不管是增加节点，还是移除节点，新旧配置的“大多数”都会存在重叠（图中的橙色节点）。
需要你注意的是，在分区错误、节点故障等情况下，如果我们并发执行单节点变更，那么就可能出现一次单节点变更尚未完成，新的单节点变更又在执行，导致集群出现 2 个领导者的情况。
如果你遇到这种情况，可以在领导者启动时，创建一个 NO_OP 日志项（也就是空日志项），只有当领导者将 NO_OP 日志项应用后，再执行成员变更请求。这个解决办法，你记住就可以了，可以自己在课后试着研究下。具体的实现，可参考 Hashicorp Raft 的源码，也就是 runLeader() 函数中：
noop := &logFuture{
        log: Log{
               Type: LogNoop,
        },
}
r.dispatchLogs([]*logFuture{noop})
当然，有的同学会好奇“联合共识”，在我看来，因为它难以实现，很少被 Raft 实现采用。比如，除了 Logcabin 外，未见到其他常用 Raft 实现采用了它，所以这里我就不多说了。如果你有兴趣，可以自己去阅读论文，加深了解。
内容小结以上就是本节课的全部内容了，本节课我主要带你了解了成员变更的问题和单节点变更的方法，我希望你明确这样几个重点。
成员变更的问题，主要在于进行成员变更时，可能存在新旧配置的 2 个“大多数”，导致集群中同时出现两个领导者，破坏了 Raft 的领导者的唯一性原则，影响了集群的稳定运行。
单节点变更是利用“一次变更一个节点，不会同时存在旧配置和新配置 2 个‘大多数’”的特性，实现成员变更。
因为联合共识实现起来复杂，不好实现，所以绝大多数 Raft 算法的实现，采用的都是单节点变更的方法（比如 Etcd、Hashicorp Raft）。其中，Hashicorp Raft 单节点变更的实现，是由 Raft 算法的作者迭戈·安加罗（Diego Ongaro）设计的，很有参考价值。
除此之外，考虑到本节课是 Raft 算法的最后一讲，所以在这里，我想多说几句，帮助你更好地理解 Raft 算法。
有很多同学把 Raft 当成一致性算法，其实 Raft 不是一致性算法而是共识算法，是一个 Multi-Paxos 算法，实现的是如何就一系列值达成共识。并且，Raft 能容忍少数节点的故障。虽然 Raft 算法能实现强一致性，也就是线性一致性（Linearizability），但需要客户端协议的配合。在实际场景中，我们一般需要根据场景特点，在一致性强度和实现复杂度之间进行权衡。比如 Consul 实现了三种一致性模型。
default：客户端访问领导者节点执行读操作，领导者确认自己处于稳定状态时（在 leader leasing 时间内），返回本地数据给客户端，否则返回错误给客户端。在这种情况下，客户端是可能读到旧数据的，比如此时发生了网络分区错误，新领导者已经更新过数据，但因为网络故障，旧领导者未更新数据也未退位，仍处于稳定状态。
consistent：客户端访问领导者节点执行读操作，领导者在和大多数节点确认自己仍是领导者之后返回本地数据给客户端，否则返回错误给客户端。在这种情况下，客户端读到的都是最新数据。
stale：从任意节点读数据，不局限于领导者节点，客户端可能会读到旧数据。
一般而言，在实际工程中，Consul 的 consistent 就够用了，可以不用线性一致性，只要能保证写操作完成后，每次读都能读到最新值就可以了。比如为了实现幂等操作，我们使用一个编号 (ID) 来唯一标记一个操作，并使用一个状态字段（nil/done）来标记操作是否已经执行，那么只要我们能保证设置了 ID 对应状态值为 done 后，能立即和一直读到最新状态值就可以了，也就通过防止操作的重复执行，实现了幂等性。
总的来说，Raft 算法能很好地处理绝大部分场景的一致性问题，我推荐你在设计分布式系统时，优先考虑 Raft 算法，当 Raft 算法不能满足现有场景需求时，再去调研其他共识算法。
比如我负责过多个 QQ 后台的海量服务分布式系统，其中配置中心、名字服务以及时序数据库的 META 节点，采用了 Raft 算法。在设计时序数据库的 DATA 节点一致性时，基于水平扩展、性能和数据完整性等考虑，就没采用 Raft 算法，而是采用了 Quorum NWR、失败重传、反熵等机制。这样安排不仅满足了业务的需求，还通过尽可能采用最终一致性方案的方式，实现系统的高性能，降低了成本。
课堂思考在最后，我给你留了一个思考题，强领导者模型会限制集群的写性能，那你想想看，有什么办法能突破 Raft 集群的写性能瓶颈呢？欢迎在留言区分享你的看法，与我一同讨论。
最后，感谢你的阅读，如果这篇文章让你有所收获，也欢迎你将它分享给更多的朋友。

分享给需要的人，Ta购买本课程，你将得18元

生成海报并分享

赞 22

提建议

08 | Raft算法（二）：如何复制日志？

10 | 一致哈希算法：如何分群，突破集群的“领导者”限制？

 写留言

精选留言(56)

每天晒白牙
2020-03-02
可以参考Kafka的分区和ES的主分片副本分片这种机制，虽然写入只能通过leader写，但每个leader可以负责不同的片区，来提高写入的性能
作者回复: 加一颗星:)
共 5 条评论
58
XHH
2020-03-02
1、leader可以合并请求 2、leader提交日志和日志复制RPC两个步骤可以并行和批量处理 3、leader可以并发和异步对所有follower 并发日志复制，同时可以利用pipeline的方式提高效率 4、每个节点启动多个raft实例，对请求进行hash或者range后，让每个raft实例负责部分请求
展开
作者回复: 加一颗星:)
共 2 条评论
34
竹马彦四郎的好朋友影...
2020-05-04
韩老师您好~ (A,B,C) 三个旧配置A是leader，然后加入D，然后网络分区为(A,B)和(C,D), 那么A依旧赢得大多数选票而是leader. C因为分区，所以也开始发起选举，赢得了C、D的选票，注意哦~ ，C也是旧配置哦~ 那么C不也就成为leader了么? 所以不就出现了2个leader了么? 也就是D作为新配置固然无法成为leader，但是C作为旧配置还是可以成为leader的呀~ 希望您能指点一下. 但是我说一下我的看法，我的看法是——您一开始在"成员变更的问题"中举的例子貌似有点问题——应该是C、D、E中的D或者E会成为新配置中的leader而不是C节点会成为新配置中的leader，因为C的（旧）配置中原本就没有D、E，它即便获取到D、E的选票也不能认为自己得票过半，这样就能解释的通了。
展开
作者回复: 加一颗星:)，C如果属于旧配置，它无法得到D的投票，因为旧配置不包括D，所以C不会成为leader。
共 2 条评论
24
kylexy_0817
2020-04-19
韩老师，有个问题，其实在实际生产环境中，是不是应该尽量避免网络分区才是重点，例如把某个集群的机器，尽量放在同一个内网中。举个我想到的例子，ABC三个节点，A在网络1，BC在网络2，初始化时，A成为了领导者，后来在网络2的单节点D加入集群，此时正好出现网络分区，BCD重新重新选举，得到B是领导者，后面网络通讯恢复了，这样即使采用单节点变更的方式，不也同样会出现了脑裂了吗？不知道我的理解正不正确，求解答。
展开
作者回复: 加一颗星:)，问题1：集群一般放在同一个机房中的，公网存在网络抖动、消息丢失等问题，网络分区，更准确的说，是指任意数量的消息丢失或者高延迟，这在同一个机房内，也是无法避免，比如进程崩溃了、机器高负载等。问题2：不会，旧领导者A会退位，在leader lease（比如Hashicorp raft的默认值是500ms）到期后，而且即使在leader lease期间，旧领导者也无法执行领导者的功能，因为他无法联系上大多数节点，所以，这时，准确来说，只有一个领导者，B，也就是，不存在脑裂问题的。
16
黄海峰
2020-03-03
老师，这种共识算法只是用于p2p的分布式系统吧，像hadoop/spark这些大数据分布式系统都是主从模式，部署就决定了谁是master，根本就不用这些共识算法了。。。相对比主从模式更可靠更可控啊，因为没有这些这么复杂的选举逻辑。。除了区块链，其他系统用p2p是不是有什么不可取代的必要性呢？
作者回复: 加一颗星:)，如果主节点是静态配置的，宕机了怎么办呢？选择哪个节点作为从节点呢？副本数据不一致，怎么处理呢？共识算法，实现的是强一致性和分区容错能力。场景决定了系统形态。
共 2 条评论
11
达子不一般
2021-09-28
我的理解：单节点变更是如何解决同时出现多个主的每次仅扩(缩)容一个节点，扩(缩)容多个节点需进行多次(非并行)。 - 扩容 1. 假设当前集群有2n+1个节点多数是n+1，扩容一个节点到2n+2，多数是n+2，按旧集群多数n+1和新集群多数n+2相加，共需要2n+3个节点才能选举出2个主，扩容后的节点数只有2n+2,所以不会出现多个主 2. 假设当前集群有2n个节点多数是n+1，扩容一个节点到2n+1，多数是n+1，按旧集群多数n+1和新集群多数n+1相加，共需要2n+2个节点才能选举出2个主，扩容后的节点数只有2n+1,所以不会出现多个主 - 缩容 1. 假设当前集群有2n+1个节点多数是n+1，缩容一个节点到2n，多数是n+1，按旧集群多数n+1和新集群多数n+1相加，共需要2n+2个节点才能选举出2个主，缩容后的节点数只有2n,所以不会出现多个主 2. 假设当前集群有2n个节点多数是n+1，缩容一个节点到2n-1，多数是n，按旧集群多数n+1和新集群多数n相加，共需要2n+1个节点才能选举出2个主，缩容后的节点数只有2n-1,所以不会出现多个主
展开
共 2 条评论
8
朱东旭
2020-03-03
一致性算法与共识算法的区别是啥，raft以领导者的日志为准，不就是保证了数据的最终一致吗。
作者回复: 在中文中，很多资料将Consensus翻译成了一致性，和Consistency同义，其实应该翻译成共识，共识算法是实现一系列值的共识的。可以这么理解，但基于Raft，能实现强一致性，也就是线性一致性。后续规划了一篇，会具体说说这些内容。
共 2 条评论
9
约书亚
2020-03-02
一般而言，在实际工程中，Consul 的 consistent 就够用了，可以不用线性一致性，这句话是不是笔误了？
作者回复: 关于Raft的一些高级特性，比如客户端协议、uncommited log丢失、指令重复执行等，在加餐篇，规划了一讲，统一补充，所以这里关于线性一致性没有展开聊。需要客户端协议的配合，才能实现“exactly once”，实现线性一致性，但很多时候，只要指令重复执行，对最终的结果没有影响，就够用了。更多细节，我会在加餐篇，具体说说。
共 5 条评论
9
Kvicii.Y
2020-06-21
NO_OP这个空日志项该怎么理解呢，为了防止出现多个领导者？怎么防止的呢
作者回复: 加一颗星:)，一次单节点变更完成后，再执行下一次单节点变更，是能保证只有一个领导者的正确性的，而引入NO_OP 日志项，是为了确保可能的在执行的单节点变更，已执行完成。
共 2 条评论
7
static
2020-03-21
老师好，想请教一个困扰我很久的关于Raft算法的一个问题。在分布式锁场景下（使用Raft算法），A客户端向leader申请获取锁（set lock），此时leader应用lock信息日志，并RPC复制日志信息给follower节点，此时follower节点还没应用到状态机，leader收到大部分follower成功信息，自己应用了状态机并返回客户端说set lock成功，但此时leader宕机了，其中一个follower变为leader，此时客户端B来获取锁，发现leader没有lock信息（因为follower将lock信息应用到状态机靠leader心跳传递，但刚刚leader宕机了没来得及传递），客户端B此时获取锁也成功了，这不就破坏了锁的同步性吗？Raft算法是如何保证这种场景下的强一致性（线性一致性）？
展开
作者回复: 加一颗星:)，我后面会做个补充:)
共 5 条评论
7
ξ！
2020-11-17
老师，在配置单节点加入的时候，是怎么发现当前集群的呢，难道是在配置的时候就将集群的节点信息写入了么，即便这样的话，当前节点是怎么发现当前集群的领导者呢，在新节点加入的时候他是怎么知道当前集群的领导者的呢，这个发现领导者的过程是新节点主动发起的rpc还是领导者的心跳发现的呢
作者回复: 加一颗星:)，1. 向领导者“申请”，由领导者完成节点添加。2. 如何发现领导者，与实现有关，一般来说，可以采用这么两种实现：a. 若非领导者节点接收到“添加节点”请求时，返回领导者信息给新节点，然后新节点重新发送请求；b. 若非领导者节点接收到“添加节点”请求时，将该请求转发给领导者。具体实现，可参考19、20讲的代码。
6
慢动作
2020-06-04
老师好，有个疑问，集群加入节点都是通过leader处理的，那文章开头3节点到5节点，为什么a还是旧配置，c却是新配置？
作者回复: 加一颗星:)，主要在于成员变更是一个过程，比如，C是领导者，它在处理D、E的配置变更，而此时C与A、B发生了分区错误，那么，A、B仍是旧配置，C、D、E组成了新配置，此时新、旧的都满足“大多数”，都会选举出的领导者。
共 3 条评论
5
刘学
2020-03-11
韩老师你好，我想到的可以解决因为强领导者导致的写性能瓶颈的办法是多分片，这样多个raft流程并发执行，不同的分片的master落在不同的机器上就可以很好的解决这个问题。在加入新节点后的第一步时，主节点向新加入的节点同步数据，那就意味着主节点需要支持向非本组成员的节点同步数据的功能对么？
作者回复: 加一颗星:)，是的。但在实现上，还有另外一种方式，也是Diego Ongaro设计的，先变更配置，新节点不具有投票权（领导者选举、日志提交），领导者向新节点同步日志，新节点的日志追赶上后，赋予新节点投票权。
共 2 条评论
5
Infinite_gao
2020-03-07
老师讲的深入浅出，可是有个疑问，为什么配置从老的阶段到中间阶段再到新阶段的这个过程没有进行阐述呢，配置的自动转换过程对于理解细节非常重要。C(old)->C(old,new)->C(new)。还有就是新加入的节点开始是通过什么类型的消息与原leader通信的，通信的信息细节是什么，是选举请求吗？
作者回复: 上面那个配置变更，是联合共识，在实际中使用的少，文中介绍的是常用的，也是Raft作者后来设计补充的一个方法，单节点变更。新加入的节点，先同步日志，日志复制rpc。
共 2 条评论
3
华子
2020-04-18
1. 所谓的＂配置＂就是指集群中的节点要知道新加入节点的IP地址等信息吗？ 2. 而之所以不能一次性加入两台或以上的节点，是因为无法保证＂同时＂加入？
作者回复: 加一颗星:)，问题1：配置是指集群各节点地址信息的集合，加入新节点时，是需要知道新节点的地址信息的。问题2：一次加入两台或以上，会出现2个“大多数”，也就是可能同时出现2个领导者，联合共识算法可以解决这个问题。
共 2 条评论
3
旅途
2020-03-09
老师麻烦解答下如果旧配置的大多数和新的大多数数量相等并且有重叠的这时候为什么不会产生两个领导者呢是因为只能选重叠的做领导者吗?如果新的大多数数量大于旧配置 ,领导者就会在新的大多数中产生吗?
作者回复: 加一颗星:)，领导者必须有“大多数”选票，才能当选，如果不存在2个“大多数”，就无法产生2个领导者。
3
岁月如歌
2020-03-09
我想说的是，在正常情况下，不管旧的集群配置是怎么组成的，旧配置的“大多数”和新配置的“大多数”都会有一个节点是重叠的。 ----------------------------------------------------------- 对于老师上述说法和配图有点不理解为何会发生这样的情况？以及非正常情况下出现两个主节点呢需要怎么处理？
作者回复: 加一颗星:)，问题1：所谓“重叠”，是指不会同时存在2个“大多数”。问题2：这个情况是需要避免和保证不出现的，具体方法是联合共识、单节点变更。
共 3 条评论
2
岁月如歌
2020-03-09
提升写性能需要单机限制，修改为多主节点形式，分片负载均衡。如redis集群方式 jedis-cluster 使用一致性hash分片负载提升读写能力。
作者回复: 加一颗星:)
2
EidLeung
2020-03-03
老师，有个地方没懂： “consistent：客户端访问领导者节点执行读操作，领导者在和大多数节点确认自己仍是领导者之后返回本地数据给客户端，否则返回错误给客户端。在这种情况下，客户端读到的都是最新数据。”和“一般而言，在实际工程中，Consul 的 consistent 就够用了，可以不用线性一致性，只要能保证写操作完成后，每次读都能读到最新值就可以了。”这两句话有点矛盾，没懂。第一句说读数据时需要向节点确认自己是领导者，应该是客户端读的时候领导者再向其他节点确认自己还是领导者，确认完成后再返回客户端数据。第二句说，写的时候确认是领导者（写完成），读的时候就是最新的值。这样第二句话在“写后出现网络分区导致已经选取了新的领导者，新的领导者又写入了数据，而旧的领导者还没退位的情况，此时读的数据应该不是最新的”（这个应该是default模型啊：写的时候保证写入，读的时候直接读）。
展开
作者回复: 第一句话，说的是如何保证每次都能读取到最新值。第二句话，说的是，在很多场景中，我们不需要线性一致性，能保证写操作完成后，每次读都能读到最新值就可以了，比如，指令重复执行，对最终的结果没有影响。因为线性一致性实现复杂，需要客户端协议的配合，才能实现“exactly once”，实现线性一致性。关于Raft的一些高级特性，比如客户端协议、uncommited log丢失、指令重复执行等，在加餐篇，规划了一讲，所以这里关于线性一致性没有展开聊。更多细节，我会在加餐篇，具体说说。
共 2 条评论
2
振超
2020-03-02
既然一个 raft 集群只能有一个 leader 节点，那么可以缩小集群的粒度，即将一个大的 raft 集群分成若干个 group，这样每个 group 范围内都有一个能够支持写操作的 leader 节点，整体上就有多个节点能够响应写操作，从而提升写性能，上层可以采取路由策略对数据进行分片。
作者回复: 加一颗星:)
2

