分布式选举算法

为什么需要分布式选举？

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

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

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

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

• 基于序号选举的算法（例如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算法：类似于选优秀班干部，是班干部且票多才可以

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

4-分布式选举算法比较.png