关于分布式系统:算法领头羊丨分布式系统如何选举领导

大家好，我是本期的实验室研究员——李帅。领导选举是分布式系统中最辣手的事件之一。同时，了解 Leader 是如何选举产生的以及 Leader 的职责，是了解分布式系统的要害。

在分布式系统中，通常一个服务由多个节点或实例组成服务集群，提供可扩展性、高可用的服务。

这些节点能够同时工作，晋升服务解决、计算能力，然而，如果这些节点同时操作共享资源时，那就必须要协调它们的操作，避免每个节点笼罩其余节点所做的更改，从而产生数据错乱的问题。

所以，咱们须要在所有节点中选出一个领导者 Leader，来治理、协调集群的所有节点，这种也是最常见的 Master-Slave 架构。

在分布式环境中的多个节点中选取主节点 Leader，通常会应用以下几种策略：

1. 依据过程 Id 或者实例 Id，抉择最大值，或者最小值作为主节点。
2. 实现一种常见的领导者选举算法，比方 Bully 等。
3. 通过分布式互斥锁，保障只有一段时间只有一个节点能够获取到锁，并成为主节点。

在本文中，我会介绍几种常见的选举算法，包含 ZAB、Bully、Token Ring Election。

Bully 算法

Garcia-Monila 在 1982 年的一篇论文中创造了 Bully 算法，这是分布式系统中很常见的选举算法，它的选举准则是“长者”为大，也就是在所有存活的节点中，选取 ID 最大的节点作为主节点。

如果有一个集群，各个节点能够相互连接，并且每个节点都晓得其余节点的信息（Id 和节点地址），如下：

集群初始化时，各个节点首先判断本人是不是存活的节点中 ID 最大的，如果是，就向其余节点发送 Victory 音讯，发表本人成为主节点，依据规定，此时，集群中的 P6 节点成为 Master 主节点。

当初集群中呈现了一些故障，导致节点下线。如果下线的是从节点，集群还是一主多从，影响不大，然而如果下线的是 P6 主节点，那就变成了一个群龙无首的局面。

当初咱们须要从新选举一个主节点！

咱们的节点是能够相互连接，并且节点间定时进行心跳查看，此时 P3 节点检测到 P6 主节点失败，而后 P3 节点就发动了新的选举。

首先 P3 会向比本人 ID 大的所有节点发送 Election 音讯。

因为 P6 曾经下线，申请无响应，而 P4,P5 能够接管到 Election 申请，并响应 Alive 音讯。P3 节点收到音讯后，进行选举，因为当初有比本人 Id 大的节点存活，他们接管了选举。

接下来，P4 节点向 P5 和 P6 节点发送选举音讯。

P5 节点响应 Alive 音讯，并接管选举。

同样，P5 节点向 P6 节点发送选举音讯。

此时，P6 节点没有响应，而当初 P5 是存活节点中 ID 最大的节点，所以 P5 理所应当成为了新的主节点，并向其余节点发送 Victory 音讯，发表本人成为 Leader！

一段时间后，故障复原，P6 节点从新上线，因为本人是 ID 最大的节点，所以间接向其余节点发送 Victory 音讯，发表本人成为主节点，而 P5 收到比本人 ID 大的节点发动的选举申请后，降级变成从节点。

Token Ring 算法

Token Ring Election 算法和集群节点的网络拓扑有较大关系，它的特点是，所有的节点组成一个环，而每个节点晓得上游节点，并能与之通信，如下：

集群初始化的时候，其中一个节点会向下一个节点先发动选举音讯，其中蕴含了以后节点的 ID，下一个节点收到音讯后，会在音讯中附加上本人的 ID，而后持续往下传递，最终造成闭环。

本次选举从 P3 节点发动。

P3 节点收到 P4 的音讯后，发现音讯中蕴含本人的节点 ID，能够确定选举音讯曾经走了整个环，这时还是依照“长者为大”的准则，从音讯 “3,6,5,2,1,4” 中选取最大的 Id 为主节点，也就是选举 P6 为 Leader。

接下来，P3 节点向上游节点发送音讯，发表 P6 是主节点，直到音讯走了整个环，回到 P3，至此，本次选举实现。

当初集群中呈现了一些故障, 导致主节点 P6 下线，位于上游的 P3 节点首先发现了（通过心跳查看），而后 P3 节点从新发动选举，当上游的 P3 节点无奈连贯时，会尝试连贯上游的上游节点 P5，发送选举音讯，并带上本人的节点 Id，音讯逐渐往上游传递。

直到选举音讯从新回到 P3 节点，从 “3，5，2，1，4” 节点列表中选取最大的 ID，也就是当初 P5 成为主节点。

接下来，P3 节点向上游节点发送音讯，发表 P5 是主节点。

直到音讯走了整个环，回到 P3，至此，本次选举实现。

ZAB – ZooKeeper 的原子播送协定

家喻户晓，Apache ZooKeeper 是云计算的分布式框架，它的外围是一个基于 Paxos 实现的原子播送协定（ZooKeeper Atomic Broadcast），但实际上它既不是 Basic-Paxos 也不是 Multi-Paxos。

目前在 ZooKeeper 中有两种领导选举算法：LeaderElection 和 FastLeaderElection（默认）, 而 FastLeaderElection 选举算法是规范的 Fast-Paxos 算法实现。

上面我会介绍 ZAB 协定中的领导选举的实现。

首先，咱们有三个节点，S1,S2,S3 , 每个节点在本地都有一份数据和投票箱，数据包含 myid, zxid 和 epoch。

• myid 每个节点初始化的时候须要配置本人的节点 Id，不反复的数字。
• epoch 选举的轮数，默认为 0，选举时做累加操作。epoch 的大小能够示意选举的先后顺序。
• zxid ZooKeeper 的全局事务 Id，64 位不反复的数字，前 32 位是 epoch，后 32 位是 count 计数器，zxid 是怎么做到全局惟一的呢？实际上集群选中 Leader 后，一个写的操作，首先会对立在 Leader 节点递增 zxid，而后同步到 Follower 节点，在一个节点上保障一个数字递增并且不反复就简略多了，zxid 的大小能够示意事件产生的先后顺序。

当初开始投票，投票内容就是下面说的节点的本地数据，【myid,zxid,epoch】, 每个节点先给本人投一票，并放到本人的投票箱，而后把这张票播送到其余节点。

一轮投票替换后，当初，每个节点的投票箱都有所有节点的投票。

依据投票箱里的投票的节点信息，进行竞争，规定如下：

首先会比照 zxid，zxid 最大的胜出（zxid 越大，示意数据越新）, 如果 zxid 雷同，再比拟 myid (也就是 节点的 serverId)，myid 较大的则胜出，而后更新本人的投票后果，再次向其余节点播送本人更新后的投票。

节点 S3：依据竞争规定，胜出的票是 S3 本人，就无需更新本地投票和再次播送。

节点 S1 和 S2: 依据竞争规定，从新投票给 S3，笼罩之前投给本人的票，再次把投票播送进来。

留神，如果接管到同一个节点同一轮选举的屡次投票，那就用最初的投票笼罩之前的投票。

此时，节点 S3 收到节点 S1 和 S2 的从新投票，都是投给本人，合乎 “ 过半准则 ”，节点 S3 成为 Leader，而 S1 和 S2 变成 Follower, 同时 Leader 向 Follower 定时发送心跳进行查看。

总结

本文次要介绍了分布式系统中几个经典的领导选举算法，ZAB、Bully、Token Ring Election, 选举规定有的是 “ 长者为大 ”，而有的是 “ 专制投票 ”，多数遵从少数, 大家能够比照他们的劣势和毛病，在理论利用中抉择适合的选举算法。

为什么没有介绍 Paxos 算法呢？因为 Paxos 是共识算法，而 Basic-Paxos 中，是不须要 Leader 节点即可达成共识，堪称 “ 众生平等 ”, 而在 Multi-Paxos 中提到的 Leader 概念，也仅仅是为了提高效率。当然 Paxos 是十分重要的，能够说它是分布式系统的根基。

微软 MVP，期待你退出