选举算法

选举算法

常用的选举算法有比较简单的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中的读取一致性。