`
huangyongxing310
  • 浏览: 494106 次
  • 性别: Icon_minigender_1
  • 来自: 广州
文章分类
社区版块
存档分类
最新评论

选举算法

 
阅读更多
选举算法

常用的选举算法有比较简单的Bully算法和复杂而强大的Paxos算法。

Bully算法
每个节点有一个唯一ID,然后对集群中所有的节点ID进行排序,选取其中最小的ID所属的节点作为Master。
Bully算法的问题: 假设当前Master因为负载过重而假死,然后ID第二大的被选举为新的Master,这时旧的Master恢复然后又被选举为Master然后又会因为负载过重而假死......

https://zhuanlan.zhihu.com/p/237710254
在集群开始启动的时候,或者主挂了之后会发起选举,节点间通过发消息来进行选举,消息分为三种:
Election Message: 选举消息 A->B 发送选举消息,表示 A 支持 B 当 Leader。
Alive Message: 响应选举消息,刚才 A->B 选举 B,B 给 A 回复 Answer Messge。
Victory Message: 宣布胜利消息,如果 B 最终当选为 Leader,则 B 向其他节点发送 Victory Message。



Paxos算法
Paxos实现起来非常复杂,但非常强大,尤其在什么时机,以及如何进行选举方面的灵活性比简单的Bully算法有很大的优势,因为在现实生活中,存在比网络链接异常更多的故障模式。

某个周的议员通过开会决定电费价格,议会有一个目标:保证所有的议员对于提议都能达成一致的看法。

现在议会开始运作,所有议员开始记事本上面记录的编号都是0。有一个议员发了一个提议:将电费设定为1元/度。他首先看了一下记事本,当前提议编号是0,那么我的这个提议的编号就是1,于是他给所有议员发消息:1号提议,设定电费1元/度。其他议员收到消息以后查了一下记事本:当前提议编号是0,这个提议可接受,于是他记录下这个提议并回复:我接受你的1号提议,同时他在记事本上记录:当前提议编号为1。发起提议的议员收到了超过半数的回复,立即给所有人发通知:1号提议生效!收到的议员会修改他的记事本,将1号提议由记录改成正式的法令,当有人问他电费为多少时,他会查看法令并告诉对方:1元/度。

现在看冲突的解决:假设总共有三个议员S1-S3,S1和S2同时发起了一个提议:1号提议,设定电费。S1想设为1元/度,S2想设为2元/度。结果S3先收到了S1的提议,于是他做了和前面同样的操作。紧接着他又收到了S2的提议,结果他一查记事本,咦,这个提议的编号小于等于我的当前编号1,于是他拒绝了这个提议:对不起,这个提议先前提过了。于是S2的提议被拒绝,S1正式发布了提议:1号提议生效。S2向S1或者S3打听并更新了1号法令的内容,然后他可以选择继续发起2号提议。
————————————————
版权声明:本文为CSDN博主「宇泽希」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/weixin_49149614/article/details/123177812


第一次启动集群(此时无版本,无历史数据)
服务器1启 动,发起一次选举。服务器1投自己一票。此时服务器1票数一票,不够半数以上(3票),选举无法完成,服务器1状态保持为LOOKING;

服务器2启动,再发起一次选举。服务器1和2分别投自己一票并交换选票信息:此时服务器1发现服务器2的myid比自己目前投票推举的(服务器1) 大,更改选票为推举服务器2。此时服务器1票数0票,服务器2票数2票,没有半数以上结果,选举无法完成,服务器1,2状态保持LOOKING

服务器3启动,发起一次选举。此时服务器1和2都会更改选票为服务器3。此次投票结果:服务器1为0票,服务器2为0票,服务器3为3票。此时服务器3的票数已经超过半数,服务器3当选Leader。服务器1,2更改状态为FOLLOWING,服务器3更改状态为LEADING;

服务器4启动,发起一次选举。此时服务器1,2,3已经不是LOOKING状态,不会更改选票信息。交换选票信息结果:服务器3为3票,服务器4为1票。此时服务器4服从多数,更改选票信息为服务器3,并更改状态为FOLLOWING;

首次启动集群的leader选举很好理解,即选择超过半数时myid最大的节点作为leader
————————————————
版权声明:本文为CSDN博主「宇泽希」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/weixin_49149614/article/details/123177812

zab协议
zab协议是基于paxos进行的简化

Zab协议有两种模式,它们分别是恢复模式(选主)和广播模式(同步)。
在 ZAB ( ZooKeeper Atomic Broadcast , ZooKeeper 原子消息广播协议)
https://blog.csdn.net/weixin_46369022/article/details/122831151


Paxos、Raft分布式一致性算法应用场景
https://zhuanlan.zhihu.com/p/31780743 (试图用通俗易懂的语言讲述Paxos算法。)

Multi-Paxos算法
原始的Paxos算法(Basic Paxos)只能对一个值形成决议,决议的形成至少需要两次网络来回,在高并发情况下可能需要更多的网络来回,极端情况下甚至可能形成活锁。如果想连续确定多个值,
Basic Paxos搞不定了。因此Basic Paxos几乎只是用来做理论研究,并不直接应用在实际工程中。

Chubby和Boxwood均使用Multi-Paxos。ZooKeeper使用的Zab也是Multi-Paxos的变形。

从 ZooKeeper 一致性,Leader选举讲到 ZAB 协议与 PAXOS 算法(下)
https://blog.csdn.net/weixin_43798841/article/details/125117475
ZAB协议和Paxos算法
在ZooKeeper在处理事务型请求的时候有提到一个协议,就是ZAB协议,然后在Leader选举时,ZooKeeper也是基于这个协议来进行实现的。所以实际上在整个ZooKeeper集群模式里面,这个ZAB协议是非常重要的。

ZAB 协议全称:Zookeeper Atomic Broadcast(Zookeeper 原子广播协议)。ZAB协议是为分布式协调服务 ZooKeeper 专门设计的一种支持 崩溃恢复和原子广播协议,
基于这个协议,ZooKeeper 实现了各个副本之间数据一致性,并且集群初始化的时候,或者主节点发生故障的话,需要通过这个协议来选举Leader节点,这里我们来看一下这个问题:
对于zookeeper来说,它实现了A可用性、P分区容错性、C中的写入强一致性,丧失的是C中的读取一致性。
















分享到:
评论

相关推荐

    用java实现HS和LCR选举算法

    在分布式系统中,选举算法是确保一致性、容错性和稳定性的重要工具。HS(Hunt-Szymanski)算法和LCR(Lamport's Cluster Membership)算法是两种经典的领导者选举算法,常用于分布式环境中的主节点选择或者一致性...

    分布式选举算法

    分布式选举算法是分布式系统中一个重要的概念,它用于在节点之间选择一个领导者或者协调者。在分布式环境中,尤其是在集群或网络中的多个同等地位的节点中,可能会遇到需要一个节点来承担特殊职责的情况,如资源分配...

    自动动手写zookeeper选举算法与心跳同步

    本文将深入探讨Zookeeper中的选举算法和心跳同步机制,这两个概念对于理解Zookeeper如何保证集群的一致性和高可用性至关重要。 首先,让我们从选举算法开始。在Zookeeper中,最常用的选举算法是Fast Paxos,它是在...

    分布式超级节点选举算法.pdf

    分布式超级节点选举算法是一类在分布式系统中用于从一组节点中选择一个或多个节点来担任特定角色(如超级节点)的算法。超级节点通常在系统中扮演着领导者的角色,负责管理普通节点、提供资源、路由信息等。如果超级...

    自组网的网关选举算法的分布式实现

    ### 自组网的网关选举算法的分布式实现 #### 移动自组网络(MANET)概述 移动自组网络(Mobile Ad Hoc Network,简称MANET)是一种特殊的对等式网络,它依赖于无线通信技术,网络中的节点能够动态地自组织形成网络...

    论文研究-分布式超级节点选举算法.pdf

    提出分布式超级节点选举算法,通过洪泛过程构造底层的生成树,叶子节点沿此树进行消息的传递,消息中包含着关于节点和边的信息,根节点根据这些信息构造最小生成树。根节点选出能力最强的节点作为超级节点,并沿着...

    电信设备-基于Gossip通信协议和Raft选举算法的优化方法.zip

    在电信设备领域,为了实现高效、可靠的分布式系统,Gossip通信协议和Raft选举算法是两种重要的技术。本文将深入探讨这两种技术,并介绍基于这两种协议的优化方法。 首先,Gossip通信协议是一种去中心化的消息传播...

    一种基于无线网络的改进自稳定领导者选举算法 (2015年)

    对IISLE算法进行了分析,IISLE算法的时间复杂度为O(n),针对无线网络环境的高断接概率,改进了IISLE算法,提出了一种适用于无线网络的改进自稳定领导者选举算法( ISLEABWN) .该算法结合移动主机断接概率模型,修改了IISLE...

    光纤通道主交换机选举算法的优化 (2008年)

    为了消除现有选举算法中因选举优先级设置不当而造成的选举时间长、网络流量大等问题,提出一种光纤通道主交换机选举优化算法。在交换机中保存了其他交换机优先级信息的前提下,通过建立选举时间优化函数模型和消息...

    研究论文-分簇水声传感器网络簇头选举算法优化.pdf

    改进分布式簇头选择机制,每轮中簇头选举由一次选举改为多次选举,引入最优成簇规模控制策略,实现簇头节点的位置分布优化,提高簇头数目稳定性,实现均衡网络能量。仿真结果表明,该改进LEACH协议能解决水声传感器网络分...

    bully-election:分布式系统的恶霸选举算法

    恶霸选举算法 在Go中实现的用于在Kubernetes集群中部署的分布式系统的恶霸选举算法。 监视器 /metrics使用指标端点获取有关副本状态的信息, Bully选举仪表板-Web应用程序,用于监视整个集群。 建造 make build # ...

    sobhuza:Stable Leader选举算法的实现

    【标题】:“sobhuza:Stable Leader选举算法的实现” 在分布式系统中,领导者选举是一个关键的组件,用于确保一致性并协调集群中的节点操作。sobhuza项目是基于Erlang语言实现的一个稳定领导者选举算法。Erlang是一...

    算法与数据结构 分布式算法课程 第04章 通用同步网络的集群领导选举 共69页.pdf

    综上所述,《算法与数据结构:分布式算法课程》第04章“通用同步网络的集群领导选举”深入探讨了领导选举算法的设计与分析,特别是在环形网络中的应用。通过对不同算法的对比分析,以及对时间和消息复杂度下限的讨论...

     基于双机热备机制的一种簇头选举算法

    文中针对物联网簇头节点无法有效处理数据或者失效导致网络可靠性下降的问题,提出了一种基于双机热备机制的簇头选举算法。该算法首先根据阈值在网络中选举出服务簇头,然后以服务簇头为基准选举出备用簇头,服务簇头...

    基于AGNES聚类的能耗均衡WSNs优化路由算法.pdf

    然后,详细介绍了基于AGNES聚类的能耗均衡WSNs优化路由算法的实现方法,包括AGNES聚类算法、簇头选举算法和路由优化算法。最后,通过仿真实验,比较了EBRAA算法与LEACH和KBE-CRA算法的性能,结果表明EBRAA算法的簇...

    Distributed-Algorithm-Coursework:树算法和选举算法的建模

    树算法和选举算法的建模 建立树模型 我建立了一个HashMap 对象来存储不同树的形状。 该HashMap中的键是每个节点的ID,而对应的值是该节点的邻居列表。 我总共有3种树木: 平衡二叉树:除最后一个级别外,每个级别均...

Global site tag (gtag.js) - Google Analytics