>

字数 923 阅读 12 评论 6

在分布式系统中，需要在多个节点之间保持数据的一致性，通常需要有一个协调者，这个协调者（Coodinator）作为整个集群的出口单独对外提供服务。
通常，我们需要在集群中的所有节点中选出这么一个节点，作为所有节点的 Leader 来承担这个工作。Leader 只能有一个，其他节点为 Follower。

Leader election 需要满足两点：

  • Safety 每一个节点要么不知道结果，要么就知道正确结果。不存在中间结果。
  • Liveness 选举过程最终会结束，每一个节点都清晰的知道选举结果。

几种不同的选举算法简介


#### Ring leader election 环算法 processes组成了一个环，第i个 process `p_i` 可以和 `p_(i+1)` modN 通信。

如果进程 i 发现原来的 leader 挂了，它就会发起选举，发送一个包含自己 ID a_i “Election” 的信息。
然后当某个进程 j 收到了这个信息的时候，会将这个 a_i 与自己的 ID a_j 比，如果 a_i > a_j，继续转发这条消息，如果 a_i < a_j 且它之前没有转发过消息，就把 a_i 取代掉然后把消息发送出去。
如果发现收到的标识符和自己的一样，代表自己成为 leader，然后把自己当选的信息发送出去。

最坏情况分析：一个进程发起选举，如果它的上一个进程具有最大标识符，则选举消息到达上一个进程需要（N—1）次传递，然后消息又要 N 次才能宣布它当选，最后需要N个消息告诉大家它当选了，所以需要（3N-1）个消息。最好情况就是发起选举的进程就是 leader，只需要（2N）个消息。
如果有多个进程同时发起选举，那么只有具有最大ID的进程会完成选举。

上述的环算法实用价值很少，因为在选举过程中如果有进程崩溃，选举就无法完成，不符合 liveness 的要求。

实际生产环境中的 Leader Election 使用 Paxos 或者 Raft 的方式来选举。


#### Google Chubby A system for locking 每个 process 最多选举一次，得到最多选票且大于某一数值的 process 当选。 chubby 中的锁服务使用 paxos 作为 chubby cell 中的一致性算法
#### Zookeeper Atomic Broadcas

Paxos的变种Zab (Zookeeper Atomic Broadcast)。必须始终保持有leader。
每个进程都向ZK文件系统中写入自己的ID,只要保证写入是原子性的，就把最大ID的进程选为 leader.
每个进程都监视着正好比自己ID高的进程，如果那个进程是leader然后挂掉了，那么它就成为新的 leader.
Apache Zookeeper Centralized service for maintaining configuration information


#### Bully Algorithm 霸道算法 假设系统是同步的，所有进程都可以互相通信。

当某一进程发现 leader 挂掉，如果自己 ID 最大，就宣布自己是 leader，否则向 ID 比自己高的进程发起选举。
发起选举如果没有收到回应，就宣布自己是 leader，收到了回应就等待比自己ID大的进程宣布结果。当一个进程收到从ID比自己低的进程发来的选举消息时，就向更高的进程发起选举。

最坏时间复杂度分析：只需5个消息传递时间

  • 最小ID进程发起选举
  • 第二大ID进程回应
  • 第二大ID进程向最大ID进程发起选举
  • 最大ID进程无回应，timtout
  • 第二大ID进程宣布当选