分布式理论之分布式选举-创新互联

写在前面

一个国家需要领导人制定各种国家决策,一个军队也需要最高统领来制定各种军事决策,同理,一个分布式集群也需要一个领导,来协调整个集群的事务,比如保证数据一致性(这也是最重要的!),分布式集群的领导,我们一般称之为主节点,这个主节点选择的过程我们就叫做分布式选举,而分布式选举可以有各种不同的方案,这些不同的方案叫做分布式选举算法,本文就是来一起来学习常见的分布式选角算法都有哪些,接下来我们就一起看下吧!

创新互联专注为客户提供全方位的互联网综合服务,包含不限于网站设计制作、网站设计、通辽网络推广、微信小程序开发、通辽网络营销、通辽企业策划、通辽品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等,从售前售中售后,我们都将竭诚为您服务,您的肯定,是我们大的嘉奖;创新互联为所有大学生创业者提供通辽建站搭建服务,24小时服务热线:18980820575,官方网址:www.cdcxhl.com1:分布式选举算法都有哪些

常见的算法有bully,raft,zab,分别来看下。

2:分布式选举算法 2.1:bully

英文[ˈbʊli] 恐吓,伤害,盛气凌人 school bully校园暴力,该算法比较简单粗暴,直接选择id大的一个节点作为主节点。

  • 角色
    普通节点,主节点。
  • 消息类型
Election消息:发起选举
Alive消息:告知自己拥有更大id的消息
Victory消息:自己成为主。告知其它节点的消息
  • 选举过程
    该算法要求知道所有其它节点的id,用来比较大小,当收到其它节点的消息后就能获取其id(为什么不是在消息中携带自己的id?),则过程如下:
1:如果是节点判断自己当前拥有大的id,则直接向其它节点发送Victory消息,宣布自己成为主节点
2:如果是当前节点判断自己并非拥有大id,则向其它节点发送Election消息,发起选举过程,如果是指定的时间内都没有收到Alive消息回复,则宣布自己成为主节点,并再次向其它节点发送Victory消息,如果是在指定的时间内收到了大于等于1个的Alive消息,则等待接收其它节点发送的Victory消息

如下是一个可能的选举过程节点2发起选举最终节点3成为主节点

节点2发起选举最终节点3成为主节点
选主完成后,正常就不会重新选主了,除非主节点故障,或者是主节点与其它节点失去联系。

  • 优缺点

优点:

算法本身简单,容易实现,选举速度快

缺点:

1:每个节点都要存储其它节点的id等信息,占用额外存储空间
2:如果是有id更大的节点加入集群,或者是id更大的节点故障后重新加入集群,都会导致重新选主,如果是频繁发生,则会频繁出现重新选主,影响集群的稳定性

因此该算法适合节点较少的集群,较大集群首先每个节点都要存储大量的信息,其次,当节点增多时,部分节点出现故障的概率也会增大,导致频繁重新选主。

2.2:raft

英文[ræft] 木排;橡皮艇,这是一种少数服从多数的算法。

  • 角色
leader:主节点,负责管理和协调其它节点
candidate:候选节点,只有处于该角色的节点才有资格成为leader
follower:leader的跟随者,当选出leader后,其它节点都是该角色
  • 选主过程

注意:

1:每个节点只能投一票。

2:投票原则是时间优先,即如果是某节点收到投票申请,如果是还没有进行过投票,则直接投票,后续在收到投票申请,因为已经投过票,就不能再次投票了。

集群初始化完成后,每个节点的状态都是follower,如下:

在这里插入图片描述

在经过时间范围在150ms到300ms的Election timeout后,会转换状态follower->candidate,如下图其中一个节点首先到达Election timeout,变为candidate状态,如下图:

在这里插入图片描述

如图节点A,率先变为candidate状态,其term即任期从0变为1,然后先给自己投一票,所以Vote Count变为1。然后其会向NodeB,Node C,发送投票申请,如下图:

在这里插入图片描述

Node B,Node C,收到Node A的投票请求后,发现自己的term小于当前收到请求term,会从0更新为1,另外因为都还未投过票,所以会返回同意票,如下图:

在这里插入图片描述
此时,Node A的得票数是3,超过了集群总节点数3的多半,成为新的主节点,其它节点都成为follower节点,主节点会以heartbeat timeout时间间隔发送心跳包到所有follower节点,以供follower检测主节点状态,此时如下图:

在这里插入图片描述

接下来当其中一个follower变为candidate状态时,就代表主节点任期结束,此时转换为candidate状态节点,会发起重新选举,如下是发起投票,和接受投票,如下图:

在这里插入图片描述

Node C成为term 2的新主节点。

接下来我们看下raft是如何保证数据一致性的,如下当前主节点是Node A:

在这里插入图片描述

假设此时客户端向主节点发送了set 5,如下图:

在这里插入图片描述

然后主节点会将set 5同步给所有的follower,只有当主节点收到大多数follower数据写入确认后,才会提交数据,返回给客户端数据写入成功,这样就保证了数据的安全性,如下图:

在这里插入图片描述
后续有数据更新也是这个流程。

以上我们可以看到,节点状态在不断的转换,如下状态转换图:

在这里插入图片描述

  • 优缺点
    优点:
1:选举速度快,复杂度低。
2:节点退出后重新加入,虽然会触发重新选主,但是因为超过半数投票才能成为主节点,一般一会导致更换主,所以稳定性好

缺点:

1:要求所有节点可通信,因为超过半数才能选主成功,所以通信量大
2:重新选主产生的主节点数据比较旧,从而导致大量数据丢失,即数据安全性低
2.3:zab

英文全程zookeeper atomic broadcast,是zookeeper提出的一种带有优先级的少数服从多数选主算法,该算法和raft相比增加了优先级,而非简单的先到先得选票,这里的优先级主要是数据的最新程度

  • 角色
leader:主节点
follower:跟随节点
observer:观察者,无权投票

节点可能的状态如下:

looking状态:选举状态,无主节点时处于该状态
leader状态:主节点状态,代表是主节点,即处于leader角色
follower状态:跟随者状态,选主成功后从looking状态,变更为该状态,即处于follower角色
observer状态:观察者状态,即处于observer角色
  • 选主过程
    因为要根据优先级来决定是否投票,因此发起投票时增加了三元组(server_id, server_zxID, epoch),含义如下:
server_id:服务器id
server_zxID:服务节点数据id,越大说明数据越新
epoch:选举轮数(为了便于理解,该值可先忽略)

对比过程是取server_zxID大的投票,相同的则取server_id投票。

初始状态时,epoch=1,即第一轮投票,server_zxID=0,因为此时还没有任何数据,因此先投自己一票,将投自己的三元组投票发给其它节点,如下图:

在这里插入图片描述

接着server1,server2,都发现server3按照优先级,应该投一票,因此将vote_id都改为server3的serverID,即3,然后将其放到投票箱中,并广播出去,如下:

在这里插入图片描述

server3成为主节点后开始和follower节点发送heartbeat,follower回复ACK,即开始心跳,如下图:

在这里插入图片描述

  • 优缺点
    优点:
1:算法稳定性好,新节点加入,故障节点恢复,不会造成频繁选主

缺点:

1:需要额外比较server_zxID,server_id,选举时间长
2:广播方式发送消息,容易产生广播风暴
2.4:各种算法对比

参考下图:

在这里插入图片描述

在这里插入图片描述

少数服从多数算法为什么要奇数个节点?

偶数时,容易出现,相同个数的选票,从而无法选择主节点,即便重新选主,出现相同选票的概率也比较大,但奇数个节点,更容易出现某个节点获取大多数选票,从而成为主节点。

写在后面

参考文章列表:

raft动画演示 。

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


本文标题:分布式理论之分布式选举-创新互联
当前链接:http://scyanting.com/article/deposh.html