vlambda博客
学习文章列表

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

微软MVP实验室研究员

李帅

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

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

Bully 算法

由于 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 算法和集群节点的网络拓扑有较大关系，它的特点是，所有的节点组成一个环，而每个节点知道下游节点，并能与之通信，如下：

现在集群中出现了一些故障, 导致主节点 P6 下线，位于上游的 P3 节点首先发现了（通过心跳检查），然后 P3 节点重新发起选举，当下游的 P3 节点无法连接时，会尝试连接下游的下游节点 P5，发送选举消息，并带上自己的节点 Id，消息逐步往下游传递。

ZAB - ZooKeeper

的原子广播协议 

• 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 定时发送心跳进行检查。