分布式:分布式选举算法
发布日期:2022-03-16 03:25:38 浏览次数:14 分类:技术文章

本文共 4092 字,大约阅读时间需要 13 分钟。

引入

在分布式领域中,常听到的一个词是集群。那什么是集群呢?简单来说,集群一般是由两个或者两个以上的服务器组建而成,每个服务器都是一个节点。

问题是,对于一个集群来说,多个节点到底是怎么协调,怎么管理的呢?比如,数据库集群中,如何保证写入的数据在每个节点上都是一致的呢?

解决方法是选出一个“领导”来复杂调度和管理其他节点。这个所谓的“领导”,在分布式中叫做“主节点”,而选“领导”的过程叫做“分布式选举”。

为什么要有分布式选举

主节点,在一个分布式集群中负责对其他节点的协调和管理,也就是说,其他节点都必须服从主节点的安排。

主节点的存在,就可以保证其他节点的有序运行,以及数据库集群中的写入数据在每个节点上的一致性。这里的一致性是指,数据在每个集群节点中都是一样的,不存在不同的情况。

当然,如果主节点故障了集群就会出问题。比如,数据库集群中,可能会导致每个节点上的数据不一致。

也就是说集群来说,主节点是必须的

总的来说,选举的作用就是选出一个主节点,由它来协调和管理其他节点,以保证集群有序运行和节点间数据的一致性。

分布式选举的算法

长者为大:Bully 算法

Bully算法的选举原则是“长者为大”,也就是所有或者的节点中,选取ID最大的节点作为主节点。

在Bully算法中,节点的角色有两种:普通节点和主节点。初始化时,所有节点都是平等的,都是普通节点,并且都有称为主的权利。但是,当选主成功后,有且仅有一个节点成为主节点,其他所有节点都是普通节点。当且仅当主节点故障或者其他节点失去联系后,才会重新选主。

Bully 算法在选举过程中,需要用到以下 3 种消息:

  • Election 消息,用于发起选举;
  • Alive 消息,对 Election 消息的应答;
  • Victory 消息,竞选成功的主节点向其他节点发送的宣誓主权的消息。

Bully 算法选举的原则是“长者为大”,意味着它的假设条件是,集群中每个节点均知道其他节点的ID。在此前提下,其具体的选举过程是:

  • 集群中每个节点判断自己的ID是否为当前活着的节点中ID最大的,如果是,则直接向其他节点发送Victory消息,宣誓自己的主权
  • 如果自己不是当前活着的节点中ID最大的,则向比自己ID大的所有节点发送Election消息,并等待其他节点的回复
  • 如果在给定的时间范围内,本节点没有收到其他节点回复的Alive消息,则认为自己成为主节点,并向其他节点发送Victory消息,宣誓自己成为主节点;如果接收到来自比自己ID大的节点的Alive消息,则等待其他节点发送Victory消息
  • 若本节点收到比自己 ID 小的节点发送的 Election 消息,则回复一个 Alive 消息,告知其他节点,我比你大,重新选举。

在这里插入图片描述

目前已经有很多开源软件采用了 Bully 算法进行选主,比如 MongoDB 的副本集故障转移功能。MongoDB的分布式选举中,采用节点的最后操作时间戳来表示ID,时间戳最新的节点其ID最大,也就是说时间戳最新的、活着的节点是主节点。

总结:Bully算法的选原则简单,谁活着而且谁的ID最大谁就是主节点,其他节点必须无条件服从。这种算法的优点是,选举速度快、算法复杂度低、简单容易实现。

这种算法的缺点在于,需要每个节点有全局的节点信息,因此额外信息存储比较多;其次,任意一个比当前主节点ID大的新节点或节点故障后恢复加入集群的时候,都可能会触发重新选举,成为新的主节点,如果该节点频繁退出、加入集群,就会导致频繁切主。

民主投票:Raft 算法

Raft 算法的核心思想是“少数服从多数”。也就是说,Raft算法中,投票最多的节点称为主。

采用 Raft 算法选举,集群节点的角色有 3 种:

  • Leader:即主节点,同一时刻只有一个leader,负责协调和管理其他节点
  • Candidate:即候选者,每一个节点都可以称为Candidate,节点在该角色下才可以被选为新的Leader
  • Follower:Leader的跟随者,不可以发起选举

Raft 选举的流程,可以分为以下几步:

  • 初始化时,所有的节点均为Follower状态
  • 开始选主时,所有节点的状态由Follower转为Candidate,并向其他节点发送选举请求
  • 其他节点根据接收到的选举请求的先后顺序,回复是否同意成为主。这里需要注意的是,在每一轮选举中,一个节点只能投出一张票
  • 如果发起选举请求的节点获取超过一半的票,则成为主节点,其状态转换为Leader,其他节点的状态则由Candidate降为Follower。Leader节点与Follower节点之间会定期发送心跳包,以检测主节点是否活着
  • 当Leader节点的任期到了,即发现其他服务器开始下一轮选主周期时,Leader节点的状态由Leader降级为Follower,进入新一轮选主。

节点的状态迁移如下所示(图中的 term 指的是选举周期):

在这里插入图片描述

Google 开源的 Kubernetes,擅长容器管理与调度,为了保证可靠性,通常会部署三个节点用于数据备份。这三个节点中,有一个会被选为主,其他节点作为备。Kubernetes的选主采用的是开源的etcd组件。而etcd的集群管理器etcds,是一个高可用、强一致性的服务发现存储仓库,就是采用了Raft算法来实现选主和一致性的。

小结:Raft算法具有选举速度快、算法复杂度低、易于实现的优点;缺点是,它要求系统内每个节点都可以相互通信,而且需要获得过半的投票数来能选主成功,因此通信量大。该算法的稳定性比Bully算法好,这是因为当有新节点加入或者节点故障恢复后,会触发选主,但不一定会真正切主,除非新节点或者故障后恢复的节点获得投票数过半,才会导致切主。

具有优先级的民主投票:ZAB算法

ZAB(ZooKeeper Atomic Broadcast)选举算法是为了ZooKeeper实现分布式协调功能而设计的。相较于Raft算法的投票机制,ZAB算法增加了通过节点ID和数据ID作为参考进行选主,节点ID和数据ID越大,表示数据越新,优先成为主。相比较于 Raft 算法,ZAB 算法尽可能保证数据的最新性。所以,ZAB 算法可以说是对 Raft 算法的改进。

使用 ZAB 算法选举时,集群中每个节点拥有 3 种角色:

  • Leader,主节点;
  • Follower,跟随者节点;
  • Observer,观察者,无投票权

选举过程中,集群中的节点拥有 4 个状态:

  • Looking 状态,即选举状态。当节点处于该状态时,它会认为当前集群中没有 Leader,因此自己进入选举状态。
  • Leading状态,即领导者状态,表示已经选出主,而且当前节点为Leader
  • Following状态,即跟随者状态,集群中已经选出主之后,其他非主节点状态更新为Following,表示对Leader的追随
  • Observing状态,即观察者状态,表示当前节点为Observer,持观望状态,没有投票权和选举权

投票过程中,每个节点都有一个唯一的三元组 (server_id, server_zxID, epoch),其中server_id表示本节点的唯一ID;server_zxID表示本节点存放的数据ID,数据ID越大表示数据越新,选举权重越大;epoch表示当前选取轮数,一般用逻辑时钟表示。

ZAB 选举算法的核心是**“少数服从多数,ID大的节点称为主”**,因此选举过程中通过(vote_id, vote_zxID) 来表明投票给哪个节点,其中 vote_id 表示被投票节点的 ID,vote_zxID 表示被投票节点的服务器 zxID。ZAB 算法选主的原则是:server_zxID 最大者成为 Leader;若 server_zxID 相同,则 server_id 最大者成为 Leader。

下面以3 个 Server 的集群为例,此处每个 Server 代表一个节点,介绍ZAB选举的过程:

  • 第一步,当系统刚启动时,3个服务器当前投票均为第一轮投票即epoch=1,且 zxID均为0。此时每个服务器都推选自己,并将投票信息< epoch, vote_id, vote_zxID>广播出去。

在这里插入图片描述

  • 第二步:根据判断规则,由于 3 个 Server 的 epoch、zxID 都相同,因此比较 server_id,较大者即为推选对象,因此 Server 1 和 Server 2 将 vote_id 改为 3,更新自己的投票箱并重新广播自己的投票。

在这里插入图片描述

  • 第三步:此时系统内所有服务器都推选了 Server 3,因此 Server 3 当选 Leader,处于Leading 状态,向其他服务器发送心跳包并维护连接;Server1 和 Server2 处于Following 状态。

在这里插入图片描述

小结:ZAB算法性能高,对系统无特殊要求,采用广播的方式发送消息,如果节点中有n个节点,每个节点同时广播,则集群中信息量为 n*(n-1)个消息,容易出现广播风暴;而且除了投票,还增加了对比节点ID和数据ID,这就意味着还需要知道所有节点ID和数据ID,所以选举时间相对较长。但是该算法选举稳定性较好,当有新节点加入或者节点故障恢复后,会触发选主,但不一定会真正切主,除非新节点或者故障后恢复的节点数据ID和节点ID最大,而且获得投票数过半,才会导致切主。

问题:为什么“多数派”选主算法通常采用奇数节点,而不是偶数节点呢

多数派选主算法的核心是少数服从多数,获得投票多的节点胜出。想象一下,如果现在采用偶数节点集群,当两个节点均获得一半投票时,到底应该选谁为主呢?

答案是,在这种情况下,无法选出主,必须重新投票选举。但即使重新投票选举,两个节点拥有相同投票数的概率也会很大。因此,多数派选主算法通常采用奇数节点。

这也是大家通常看到 ZooKeeper、 etcd、Kubernetes 等开源软件选主均采用奇数节点的一个关键原因。

总结

在这里插入图片描述

在这里插入图片描述

转载地址:https://blog.csdn.net/zhizhengguan/article/details/122813757 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Unix/Linux编程:主线程和工作线程的分工
下一篇:分布式:如何实现分布式互斥

发表评论

最新留言

初次前来,多多关照!
[***.217.46.12]2024年03月02日 22时18分32秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章