分布式选举算法之Paxos、Raft与Bully-创新互联

  在大型分布式系统中,会存在多个特定功能的集群。最常见的就是协调者集群,如提供分布式锁,分布式事务的协调者集群。集群中的多个机器对外提供统一的状态、一致的数据,这就需要在集群中选择一个主节点(领导者),来管理集群中的其他节点(跟随者)。这个选择主节点的过程就叫做分布式选举。

成都创新互联公司10多年成都企业网站定制服务;为您提供网站建设,网站制作,网页设计及高端网站定制服务,成都企业网站定制及推广,对成都房屋鉴定等多个方面拥有丰富建站经验的网站建设公司。

分布式选举的算法有Paxos算法、Raft算法、Bully算法等。

Paxos算法

  Paxos算法是Leslie Lamport在1990年提出的一种基于消息传递的一致性算法。基于Paxos协议的数据同步与传统主备方式大的区别在于:Paxos只需超过半数的副本在线且相互通信正常,就可以保证服务的持续可用,且数据不丢失。

Paxos将系统中的角色分为提议者 (Proposer),决策者 (Acceptor),和最终决策学习者 (Learner):

  • Proposer: 提出提案 (Proposal)。Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。
  • Acceptor:参与决策,回应Proposers的提案。收到Proposal后可以接受提案,若Proposal获得多数Acceptors的接受,则称该Proposal被批准。
  • Learner:不参与决策,从Proposers/Acceptors学习最新达成一致的提案(Value)。

在多副本状态机中,每个副本同时具有Proposer、Acceptor、Learner三种角色。

Paxos算法通过一个决议分为两个阶段(Learn阶段之前决议已经形成):

  • 第一阶段:Prepare阶段。Proposer向Acceptors发出Prepare请求,Acceptors针对收到的Prepare请求进行Promise承诺。
  • 第二阶段:Accept阶段。Proposer收到多数Acceptors承诺的Promise后,向Acceptors发出Propose请求,Acceptors针对收到的Propose请求进行Accept处理。
  • 第三阶段:Learn阶段。Proposer在收到多数Acceptors的Accept之后,标志着本次Accept成功,决议形成,将形成的决议发送给所有Learners。
Basic-Paxos

  Basic-Paxos解决的问题:在一个分布式系统中,如何就一个提案达成一致。

Mulit-Paxos

  Mulit-Paxos解决的问题:在一个分布式系统中,如何就一批提案达成一致。

应用场景举例:

Zookeeper(zookeeper选举机制)

Raft算法

  Raft算法是Paxos算法的一种简化实现。包括三种角色:leader,candidate和follower。


Raft算法过程
  • Leader选举: 每个candidate随机经过一定时间都会提出选举方案,最近阶段中的票最多者被选为leader。
  • 同步log: leader会找到系统中log(各种事件的发生记录)最新的记录,并强制所有的follow来刷新到这个记录。
应用场景举例:

Etcd、Consul


Raft和Multi-Paxos的区别

Raft是基于对Multi-Paxos的两个限制形成的:

发送的请求的是连续的, 也就是说Raft的append 操作必须是连续的, 而Paxos可以并发 (这里并发只是append log的并发, 应用到状态机还是有序的)。
Raft选主有限制,必须包含最新、最全日志的节点才能被选为leader. 而Multi-Paxos没有这个限制,日志不完备的节点也能成为leader。

Raft可以看成是简化版的Multi-Paxos。

Multi-Paxos允许并发的写log,当leader节点故障后,剩余节点有可能都有日志空洞。所以选出新leader后, 需要将新leader里没有的log补全,在依次应用到状态机里。

Bully算法 

  Garcia-Monila 在 1982 年的一篇论文中发明了所谓的霸道选举算法(Bully Algorithm)。其基本思想是:当一个进程P发现协调者不再响应请求时,就判定协调者出现故障,于是它就发起选举,选出新的协调者,即当前活动进程中进程号大者。

三种消息类型:

  • Election消息:表示发起一次选举
  • Answer(Alive)消息:对发起选举消息的应答
  • Coordinator(Victory)消息:选举胜利者向参与者发送选举成功消息
选举流程:

  1. 如果P是大的ID,直接向所有人发送Victory消息,成为新的Leader;否则向所有比它大的ID的进程发送Election消息
  2. 如果P在发送Election消息后没有收到Alive消息,则P向所有人发送Victory消息,成为新的Leader
  3. 如果P收到了从比自己ID还要大的进程发来的Alive消息,P停止发送任何消息,等待Victory消息(如果过了一段时间没有等到Victory消息,重新开始选举流程)
  4. 如果P收到了比自己ID小的进程发来的Election消息,回复一个Alive消息,然后重新开始选举流程
  5. 如果P收到Victory消息,把发送者当做Leader
应用场景举例:

mongodb、elasticsearch(Master选举)

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


分享标题:分布式选举算法之Paxos、Raft与Bully-创新互联
文章源于:http://myzitong.com/article/eihci.html