最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

《分布式技术原理与算法解析》学习笔记Day04

来源:博客园

分布式选举算法

为什么需要分布式选举?

分布式意味着我们的应用部署在一个集群中,集群包含多个节点或者服务器,对于一个集群来说,多个节点是怎么协同工作的呢?我们需要有一个主节点来负责对其他节点的协调和管理。

分布式选举是为了选出一个主节点,由它来协调和管理其他节点,以保证集群有序运行和节点间数据的一致性。


(资料图片仅供参考)

常见的分布式选举算法有哪些?

分布式选举算法一般会分为两类:

  • 基于序号选举的算法(例如Bully算法)
  • 多数派算法(Raft,ZAB等)

Bully算法

Bully算法中,节点的角色有两种:普通节点和主节点。初始化时,所有节点都是平等的,都是普通节点,并且都有成为主节点的权利,但是当选主结束后,有且仅有一个节点成为主节点,其他所有节点变为普通节点。

Bully算法在选举的过程中,需要使用3种消息:

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

Bully算法选举的原则是“长者为大”,它假设集群中的每个节点都知道其他节点的ID。整个选举过程如下:

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

Bully算法的优点是选举速度快、算法复杂度低、简单易实现。它的缺点在于需要每个节点都保存全局的节点信息,因此额外信息存储比较多,其次,任意一个比当前主节点ID大的新节点或者节点故障后回复加入集群的时候,都会触发重新选举,成为新的主节点,如果该节点频繁退出、加入集群,就会导致频繁切主。

Raft算法

Raft算法是典型的多数派投票选举算法,它的核心思想是“少数服从多数”。

在Raft算中,集群节点的角色有3种:

  1. Leader,主节点,同一时刻只有一个Leader
  2. Candidate,候选者,每一个节点都可以成为Candidate,节点在该角色下才可能被选为新的Leader
  3. Follower,跟随者,不可以发起选举。

Raft选举的流程如下:

  1. 初始化时,所有节点都是Follower状态。
  2. 开始选主时,所有节点的状态由Follower转化为Candidate,并向其他节点发送选举请求。
  3. 其他节点根据收到的选举请求的先后顺序,回复是否同意成为主,在每一轮选举中,一个节点只能投出一张票。
  4. 如果发起选举请求的节点获得超过一半的投票,则成为主节点,其状态转化为Leader,其他节点的状态则由Candidate变为Follower。
  5. Leader节点和Follower节点之间会定期发送心跳包,来检测主节点是否正常。
  6. 当Leader节点的任期到了,即发现其他服务器开始下一轮选主周期时,Leader节点的状态也会由Leader降级为Follower,进入新一轮选主。

Raft算法的优点是选举速度快、算法复杂度低、易于实现。它的缺点是要求系统内每个节点都可以相互通信,其需要获得过半的投票数才能选主成功,因此通信量大。

Kubernetes的选主采用开源组件etcd,etcd的集群管理器etcds,是一个高可用、强一致性的服务发现存储仓库,就是采用了Raft算法实现选主和一致性的。

http://thesecretlivesofdata.com/raft/#election对Raft算法做了很好的动画演示,可以很好的帮助我们理解Raft算法的选举过程。

ZAB算法

ZAB选举算法是为ZooKeeper实现分布式协调功能而设计的,和Raft算法相比,ZAB算法增加了通过节点ID和数据ID作为参考进行选主,节点ID和数据ID越大,标识数据越新,优先成为主节点。

ZAB选举算法的核心是“少数服从多数,ID大的节点优先成为主节点”。

ZAB算法中,集群里的每个节点拥有三种角色:

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

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

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

投票过程中,每个节点都有一个唯一的三元组(service_id, service_zxID, epoch):

  • servier_id:该节点唯一ID
  • service_zxID:该节点存放的数据ID,数据ID越大,表示数据越新,选举权重越大
  • epoch:当前选举论数,一般用逻辑时钟表示。

选举的原则:server_zxID最大者成为Leader,如果server_zxID相同,则service_id最大者成为Leader。

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

ZAB算法适合大规模分布式场景,例如ZooKeeper。

关于Bully算法、Raft算法和ZAB算法,有一个比较形象的比喻:

  • Bully算法:类似于选武林盟主,谁武功最高,谁来当
  • Raft算法:类似于选总统,谁票数最高,谁来当
  • ZAB算法:类似于选优秀班干部,是班干部且票多才可以

更加详细的比较信息如下表所示。

关键词: 少数服从多数