Bully选举算法
节点角色：
- 普通节点
- 主节点
消息通知： - Election通知：表示“我推举谁为主节点”。如A->B表示A推举B为主节点。
- Alive通知：对Election通知的应答
- Victory通知：选举成功后通知所有节点“我成为主节点”的通知。
选举流程：
1.优先发现集群中无主的节点向节点ID比自己大的节点发送Election通知。
2.若当前节点已为集群内节点ID最大节点或未收到Alive通知，则当前节点成为主节点。发送Victory通知宣誓主权。
3.接收到Election通知的节点发送Alive通知反馈。并向节点ID比自己大的节点发送Election通知。重复2步骤。
本算法优缺点：
1.选举快、易实现、算法复杂度低。
2.所有节点需要知道其他节点的节点ID信息。此为前置条件。
3.主节点频繁故障恢复则会触发频繁换主，不稳定。
4.选主过程不如说是寻主过程。
Raft选举算法
节点角色：
- Follower：跟随者，不参与选主的节点，负责投票。
- Candidate：候选人，参与选举的节点，选举成功可称为主节点。
- Leader：领导者，即主节点
消息通知： - 心跳通知：仅有Leader发起，阻止其他节点发起选举，用于宣誓主权。
- 选举通知：Follower发起，为了竞选Leader。
- 响应选举通知：接收选举通知后，若当前任期本节点未投票，则响应选举。一个任期一票。遵循“先来先服务”原则。
选举流程：
1.初始启动时所有节点均为Follower角色，各自随机150ms～300ms等待超时。
2.先超时节点发现集群无主，转为Candidate角色，任期+1，率先发出选举通知请求大家给自己投票，并给自己投一票。
3.其余Follower节点接收到选举通知，若任期内未投票，则复制对方任期并投票，重置超时时间。否则静默不响应。
4.Candidate节点统计得票，遵循“大多数派”原则，超过半数票则当选为Leader，给其他节点推送心跳通知宣誓主权。
5.Leader节点故障不可用或因网络分区原因无法发出心跳通知。重复2～4。
本算法优缺点：
1.使用随机超时时间策略简单又有效地解决了并发竞选可能导致选举无效的场景。
2.对比bully算法相较来说，选主结果随机，交互较复杂。
3.网络分区可能导致脑裂问题。
4.频繁的心跳消息带来的性能开销
Zab选举算法
节点状态
- LOOKING：竞选状态
- FOLLOWING：随从状态，同步leader状态，参与leader选举投票过程
- OBSERVING：观察状态，同步leader状态，不参与leader选举投票过程。
- LEADING：领导者状态
消息通知：
- 心跳通知：仅有Leader发起，阻止其他节点发起选举，用于宣誓主权。
- 选举通知：投票消息，包含节点数据ID（zxID）、节点ID（serverID）、选举周期（epoch），被选举节点ID（voteID）
选举流程：
1.初始启动，节点默认为Following状态。
2.Following状态节点切换为Looking状态，先投票给自己，然后将投票消息广播给其他节点。
3.其他节点收到投票消息后，比较zxID和serverID选出主节点，将选出主节点的消息也广播给其他节点。
4.Looking状态节点计算的票数，遵循“大多数派”原则，若超过集群中节点半数则切换为Leading状态，并向其他节点发送心跳消息宣誓主权。
5.其他节点切换为Following状态。
6.Leading状态节点故障不可用或因网络分区原因无法发出心跳通知。重复2～5。
本算法优缺点：
1.结合了bully和Raft算法，选举leader既跟服务器唯一标识（常量）有关。也跟事务ID（变量）先后顺序有关。
2.为Zookeeper定制化设计的选举算法，因此依赖myid和zxID进行协同选举以减少无效选举的情况。
总结
- Bully选举算法：“霸道”的选主算法，永远遵循“长者”为大原则，集群中ID最大的为主节点。
- Raft选举算法：“随缘”的选主算法。集群所有节点平等。随机超时时间等待后发起选举，遵循“先到先得”原则、“大多数派”原则。
- Zab选举算法：“能力+地位”优先的选主算法。先看zxID，zxID相同时看myid。zxID为事务ID，事务ID越大优先考虑选主。myid为服务器ID，全剧唯一，启动后不变。
扩展
最早的分布式共识算法应当是Paxos算法。以上这些算法基本都有Paxos算法的影子。关于Paxos算法逻辑如下：
节点角色：
- 提案者（proposer）：负责对单个值操作生成提案（proposal，一个提案包括提案号和提案值）。并推送到各个接受者
- 接收者（acceptor）：接收提案，并进行提案确认和值确认
- 学习者（learner）：不参与提案和投票，被动接受提案结果，主要用于读扩展和跨区域同步。
消息通知：
- prepare通知：提案者发出提案号给接收者，并根据接收者响应结果确认提案是否通过。
- accept通知：提案者发出提案号+提案值给接收者，并根据接收者响应结果确认提案值是否达成了共识。
选举（提案）流程：
1.proposer接收到新请求后，生成提案号。
2.proposer发起prepare请求给所有接收者，并传递提案号。等待接收者响应
3.acceptor接收到prepare请求，若从未接收过其他提案或请求提案号大于已接收的提案号，则通过并响应给proposer。
4.proposer接收到prepare响应后，根据“大多数派”原则判断提案是否通过。若通过则继续发送accept通知给所有接收者。
5.acceptor接收到accept请求，若已接收到比请求提案号更大的提案则拒绝，否则通过。
6.proposer接收到accept响应后，根据“大多数派”原则判断提案值是否通过，若通过则表示本提案已达成共识。
由以上选举（提案）过程可知，Paxos是针对单值的共识。若为多值共识，则简单的可以对Paxos进行多次prepare+accept两段式提交即可。基于这个理论思想，无论是Bully、Raft还是Zab省略了两段式提交中的第一段。即优先选举出Leader节点，再由leader节点进行值提交。
