高可用集群中的选举机制

一个高可用的集群里,一般都会存在主节点的选举机制。这里以elasticsearch集群为例,介绍一下集群的节点选举方法。

如果查看Elasticsearch集群里的节点信息,你会发现里面有一个节点称为master节点,而且一个集群只有一个master节点。那么,什么是master节点呢? 为什么集群一定要有一个master节点?master什么时候产生,又是怎么产生的呢?

什么是master节点?

简单的说,master节点就是集群中的leader,或者管理者。master节点知道所有其它节点的状态,集群中的一些重要的决策交由它来做。

为什么集群里一定要有一个master节点?

我们可以想象一下一个没有master节点的集群是什么样子的。假设我们有这样一个集群:集群中有5个节点,分别是A、B、C、D和E。所有的节点都是普通节点,大家的职责没有任何区别,而且每一个节点都知道其它节点的信息。我们来看看这样的“无政府”状态的集群是否可以正常运行。

在某一时刻,外部系统发来了一个条数据,这个集群要把这条数据存储起来。Elasticsearch在存储数据之前,首先要创建一个索引,而创建索引就要生成分片。那么,分片应该放在哪些节点呢?嗯,这是个问题!如果有个leader在,那么,这个决策直接交给leader决定就好了。可是现在没有,试试发扬民主精神,靠大家群策群力如何?

假设集群需要为这个索引生成2个分片。噢,等等!分片数谁说了算?万一有人认为需要3个分片,有人认为需要2个分片,怎么办?真是寸步难行啊!算了,乐观点,我们姑且认为每个节点在启动的时候都设置的是2个分片,而且一直没有变化,大家在这方面暂时没有分歧,就2个分片吧。下一步就是决定把这两个分片放到哪里。在这个乌合之众的群体中,最简单有效的方法就是投票。假设大家都认为应该存放在负载最轻的节点上。因为每个节点都知道其它节点的信息(包括负载信息),所以大家都知道该把分片放到哪个节点。比如,这一次大家一致认为E节点最轻松,分片就放到E节点了。OK,大功告成!

事情算是搞定了,可是似乎并不轻松。我们来算一下账。这一次投票中,为了检查其它节点到状态,每个节点都和其它所有到节点进行了一次通信。5个节点累计做了4X5=20次通信。这只是一个5节点到集群,如果50个节点,一次投票则需要50X49= 2450次通信。如果每次决策都需要全民投票,那么实在是太重了。这跟现实社会是一样的,如果颁布每条法律都需要做一次全民投票,基本上这个社会就无法运转了。最好的办法是选一个管理者,然后由他来做决策。全民投票仅用于选择谁来当管理者。

另外,如果没有master,会产生脑裂(brain split)问题。

假设我们的集群结构是下面这个样子的。A和B在一个网络里,C、D和E在另一个网络里。如果两个网络之间的连接断了,这个集群就变成了两个小集群,即脑裂。这两个小集群各自处理数据。一段时间后,可能网络又联通了,但是它们之间已经产生了数据冲突,无法解决。

“无政府”状态的集群似乎问题重重,然而,我们仍然不能就此得出结论,说必须有一个master才行,也许存在某种巧妙的方法可以解决裁决问题,可以解决脑裂问题。不过,设置一个master是一个简介有效的方法。

有了master节点,集群会怎样?

假设我们的集群设定了一个master节点,比如节点A。整个集群由它负责管理,它可以决定创建多少分片、在哪里创建分片。

集群中的B节点收到一条数据。B节点先问一下A:“需要创建几个分片?在哪里创建?” A节点扫描一下集群的负载(也可以定时扫描,把集群状态存起来),发现E节点负载最小。然后告诉B:“创建2个分片,在E节点”。就这么简单。

光靠master节点解决不了脑裂问题,还需要引入一个称为法定人数(quorum)的概念。法定人数表示一个集群最少需要几个节点数。比如,设置前面集群的法定人数是3, 那么,当两个交换机的网络断开时,就不会出现问题。左侧两个节点组成的网达不到法定人数,因此A节点这个master必须退休,B也要停止工作。右侧有三个节点,满足法定人数要求,则可以选举master。比如,选举C节点为master,那么右侧3个节点可以继续正常工作。当交换机之间的连接通了以后,A和B会重新加入以C为master的集群。整个集群跟之前一样,只是master从A变成了C。

在交换机断开的那段时间,由于A和B两个节点不满足法定人数,所以它们不做任何数据处理。当它们重新介入集群时,它们当数据和集群中其它节点的数据也就不会有冲突。

法定人数一般设置为N/2+1。N为集群的节点数。

集群是怎么选举master的?

理论上,集群有很多种选举办法。这里介绍两种。

1. Bully 算法 --长幼有序

Bully算法很像古代中国的皇位继承制。皇位的继承一直沿用嫡长继承、顺序嗣位的原则。皇位由长子继承,如长子早死,则立其子,然后是第三子。Bully算法与此类似。它为集群中每个节点设一个唯一编号,用编号的大小表示优先次序。在任何时刻,总是编号最大的节点当master。当master节点挂掉时,下一个节点马上当选新的master。

这种方法的好处是实现起来很简单,不过缺点也很明显。最典型的问题是:当编号最大的节点不稳定时,集群就不稳定。因为master节点需要承担额外当管理任务,所以,该节点的负载会比较大。当负载超过节点的承载能力时,节点就卡住了。这时,编号第二大的节点便当选为新的master。于是,负载便转移到第二个节点。那么,第一个节点的负载就会随之变小。过了一会,它可能又恢复正常运行了。按照规则,第一个节点又会重新当选为master。然后,它又因为负载过大再次被卡住,如此反复循环,导致集群无法正常运行。

2. Paxos -- 少数服从多数

Paxos是希腊的一个小岛,考古学家发现这个岛上在古代就有关于议会制度的记录。岛上的居民通过民主提议和投票的方式选出一个最终决议。不过,城邦居民都不愿意把全部时间和精力放在这件事情上,只愿意不定期来参与提议和投票。但他们制度能够按照少数服从多数的原则,使得提议者最终达成一致意见。计算机科学家Leslie Lamport借鉴了这个议会制度,设计了分布式系统选举的算法,并直接称之为Paxos算法。

Paxos算法中有两个角色,一个是提议者(Proposer), 另一个是接受者(Acceptor)。当然,一个节点可以同时拥有这两个角色,真实情况通常也都是如此。

Paxos选举过程总共有两个阶段。

阶段一

a) 提议者给一半以上的接受者发送一个预提案(prepare proposal),预提案中带一个唯一编号n。

b) 接受者接收到一个编号为n的预提案后,就拿它跟之前接收到的预提案比较。

b-1) 如果n大于其它提案编号,它就发送“接受”反馈,并承诺以后不再接受编号<n的提案(含预提案和正式提案)。同时,把它曾经接受过的编号最大的提案信息也反馈回去。

b-2)如果n小于等于其它提案,它就发送“拒绝”反馈。同时,把它曾经接受过的编号最大的提案信息也反馈回去。

阶段二

a) 如果提议者从大多数(集群一半以上)接受者那里得到了“接受”反馈,那么它就发送一个正式提案(proposal)给所有节点。正式提案中包含两项内容:编号n和v。其中,n是它之前预提案的编号,而v是它得到的所有反馈中,编号最大的提案的v值(v表示建议谁当master,可以是参选节点的机器名等)

b) 如果接受者收到正式提案(编号n), 他就接受这个提议,除非它已经给编号>n的预提案发送了“接受”反馈。

下面是一个例子以帮助理解,例子中里有两个提议者和3个接受者。

第一步,提议者1向3个接受者发送预提案#1.

第二步,接受者之前从没有接受过其它预提案,所以提案编号1就是最大编号,因此三个都接受预提案#1.

第三步,提议者1向接受者1发送正式提案,编号=1,v=A (它建议A节点做master节点)

第四步,接受者1之前没有给任何编号>1的提案反馈过,所以接受提案1,并把v值设置为提案1的值,即v=A。注意:此后,接受者1永远不可能改变它的v值,也就是说它的v值永远都是A。

第五步,提议者2给两个接受者发送预提案。

第六步,接受者1发现这个预提案编号(2)大于之前的最大编号(1) , 于是接受该预提案。同时,把它接受过的编号最大的正式提案(#1)的v值也反馈回去。见规则 b-1。 提议者2改变自己提案中的v值,从B变为A。接受者2因为之前没有收到过正式提案,所以只返回“接受”。

第七步,提议者1给接受者2和接受者3发送正式提案,编号=1,v=A (它建议A节点做master节点)

第八步,接受者2发现提案#1的编号小于它接受过的最大编号(#2),就拒绝该提案。

接受者3发现它接受过的最大编号是1,于是就接受该提案,并将提案值v=A记下来。

第九步,提议者2给接受者1和接受者2发送正式提案。编号=2,v值=A。注意,现在提议者2已经不是发送它最初的提案,而是发送新提案。它的新提案来自第六步,从接受者1那里得到的新提案(v=A)。

第十步,接受者接受1和接受者2都发现之前最大的编号是2,于是接受提案。至此,选举结束。所有的接受者得到的提案都是v=A,于是A当选为master。

如果任何一个接受者的v值不是A而是其它值,那么集群就会出现问题。相当于集群出现了多个master。而Paxos是不会让这样的情况发生的。

不过,Paxos算法理论上会出现“活锁”的问题。具体什么是“活锁”,有兴趣的读者可以自己去研究一下。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏村雨

Python知识点总结篇(一)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

8220
来自专栏c#Winform自定义控件系列

(四十五)c#Winform自定义控件-水波图表

GitHub:https://github.com/kwwwvagaa/NetWinformControl

8220
来自专栏AI科技大本营的专栏

我的一年AI算法工程师成长记

【导语】经常有朋友私信问,如何学python?如何敲代码?如何进入AI行业?正好回头看看自己这一年走过的路,进行一次经验总结。这是一篇关于如何成为一名AI算法工...

16320
来自专栏c#Winform自定义控件系列

(四十)c#Winform自定义控件-开关

GitHub:https://github.com/kwwwvagaa/NetWinformControl

8620
来自专栏c#Winform自定义控件系列

(四十三)c#Winform自定义控件-Listview

GitHub:https://github.com/kwwwvagaa/NetWinformControl

11520
来自专栏c#Winform自定义控件系列

(三十九)c#Winform自定义控件-面包屑导航

GitHub:https://github.com/kwwwvagaa/NetWinformControl

10420
来自专栏c#Winform自定义控件系列

(四十九)c#Winform自定义控件-下拉框(表格)

GitHub:https://github.com/kwwwvagaa/NetWinformControl

17810
来自专栏前端自习课

【算法】342- JavaScript常用基础算法

一个算法只是一个把确定的数据结构的输入转化为一个确定的数据结构的输出的function。算法内在的逻辑决定了如何转换。

11540
来自专栏c#Winform自定义控件系列

(四十一)c#Winform自定义控件-进度条

GitHub:https://github.com/kwwwvagaa/NetWinformControl

8520
来自专栏村雨

JAVA知识点总结篇(三)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

8620

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励