聊聊 Leader Election

在分布式计算中，领导者选举是指定单个进程作为在多台计算机之间分发的某些任务的组织者的过程。在任务开始之前，所有网络节点要么不知道哪个节点将充当任务的“领导者”，要么无法与当前的协调者进行通信。但是，在运行领导者选举算法之后，整个网络中的每个节点都将一个特定的唯一节点识别为任务领导者

定义

领导者选举的问题是让每个进程最终决定自己是否是领导者，同时确保仅有一个进程最终确定自己是领导者。一个算法解决了领导者选举问题，需满足以下条件：

  • 进程的状态分为已选和未选状态。一旦被选为领导者，就保持为已选状态（同样，如果未被选中也保持为未选状态）。
  • 在每次执行中，恰好有一个进程被选为领导者，而其他进程确定自己未被选为领导者。

一个有效的领导者选举算法必须满足以下条件：

  • Termination终止性：一旦选出领导者，算法应在有限时间内完成
  • 唯一性：只有一个进程认为自己是领导者
  • 一致性：所有其他进程都知道谁是领导者
  • 稳定性：稳定的领导者有助于避免所有参与者的状态同步，减少信息交换的数量

ps：与分布式锁的区别

  • 分布式锁 不需要知道目前持有锁的进程是谁，只要保证持有者最终释放锁即可

算法

Bully Algorithm

Bully Algorithm，他使用了进程的排名来选择新的领导者。每个进程都会被分配一个唯一的排名。在选举的过程中，具有最高排名的进程会成为领导者。

这个算法因为他的简易性而广为人知，而他被命名为 Bully 是因为最高排名的节点 Bullies 强制其他的节点接受他成为领导者。他同时也被称为 Monarchial 领导者选举：最高排名的邻接节点会在前一个领导者退出后成为leader。

这个算法的一个明显的问题是他在产生网络分区的时候会违反了唯一性的保证，产生Split Brain 脑裂

这个算法的另一个问题是对高排名的节点具有严重的偏向性，当这些节点不稳定的时候可能会导致无限的进行选举的情形。一个不稳定的高排名的节点会选择自己成为领导者，然后短时间内又出故障，然后又再次赢得选举，又再次故障，导致这个过程会无限的重复下去 - 违反稳定性原则

ps：

  • zab协议在zxid相同时，选择myid较大的为leader，是不是有点儿类似于Bully Algorithm😄

Next-in-Line Failover

针对Bully Algorithm 算法的稳定性问题，有一种改进方案

每个选举出的leader都提供一个故障转移节点的list。当检测到leader出现故障，可以向list里的排名最高的备选进程发送消息，发起新一轮选举。来减少对高排名的节点具有严重的偏向性

Candidate / Ordinary Optimization

针对节点众多的集群leader election，一个尝试降低vote消息数量的算法是将节点分割成两个子集，一个是 Candidate 候选人，另一个是 Ordinary 普通节点，并且只有Candidate节点最终才能够成为领导者 -- 突然想起了Kafka ISR😄

普通节点通过联系候选人节点来初始化一个选举，收集候选人的信息，选择排名最高的活跃候选人作为新的领导者，然后将这个选举的结果通知给其他的节点。

为了解决同时发生多个选举的问题，算法的进程会使用一个变量局点 δ 来决定进程发起投票的延迟，将节点之间显著的区分开来，这样就能够让一个节点在其他节点之前来启动这个选举

Ring Algorithm

在 Ring Algorithm 中，系统中所有的节点都以一种环的拓扑方式进行构建 (比如每个节点的前驱跟后驱都在环中)。当进程检测到领导者故障时，他会启动新的一轮选举。选举的消息会沿着环往前递进：每个进程会联系他的后驱 (即在环中跟他最接近的下一个节点)，如果这个节点不可用，这进程会跳过这个节点，尝试去联系这个节点的下一个节点，直到最终能够得到响应为止

这个算法会完整的绕着环进行处理，当消息重新回到发起选举的节点时，仍然活跃且具有最高排名的节点会被选为领导者

因为这个环可能会被分成两个或更多的分区，并在每个分区中都选出了自己的领导者，因此这种实现方式也是不满足唯一性

其他算法

许多的一致性算法，包括 Multi-Paxos / Raft / Zab，都依赖于领导者来进行协调。

但领导者的选举与共识算法时相通的。为了选出一个领导者，我们需要对他的标识符达成共识。如果我们能够对leader达成共识，那我们就可以使用相同的方式为任意的数据达成共识

这里不再展开，留待下一篇blog

leader模式应用总结

优点：

  • 单个leader将系统中的所有并发性集中在一起，有利于解决顺序性的问题
  • 单个leader效率更高。它通常将相关更改通知其他系统即可，而无需就将要进行的更改达成共识

缺点：

  • 单个领导成为单点故障。如果系统无法检测到或修复无效领导，整个系统可能会不可用
  • 单个领导意味着单点扩展，无论是在数据大小还是请求速率方面
  • 单个领导成为单点信任。如果leader在没有检查的情况下出错，可能很快就会在整个系统中引起问题
  • 容易出现脑裂问题

参考

  • Database Internal
  • Wiki