二夕说废话の地方

分布式 004——选举策略

 4061  9 分钟

分布式选举

前言

既然提到了分布式，集群就是绕不开的话题。简单来说，集群一般是由两个或两个以上的服务器组建而成，每个服务器都是一个节点。我们经常会听到数据库集群、管理集群等概念，也知道数据库集群提供了读写功能，管理集群提供了管理、故障恢复等功能。

那么问题，对于一个集群来说，多个节点到底是怎么协同，怎么管理的呢。比如，数据库集群如何保证写入的数据在每个节点都一致呢？比如上一篇博客中谈到的分布式各个服务之间可能会打架——互斥。

这个时候，你也许会说，这还不简单，选一个”领导“来负责调度和管理其他节点不就可以了嘛。诶，很不错。这就是我们常说的”主从“架构设计。这个”领导“在分布式叫做主节点，而选”领导“的过程在分布式领域中叫作分布式选举。

关于如何选主这个过程，就是我们本篇的重点咯。

为什么要有分布式选举？

主节点，在一个分布式集群中负责对其他节点的协调和管理，也就是说，其他节点都必须听从主节点的安排。主节点的存在，就可以保证其他节点的有序运行，以及需要保证写入每个节点的数据一致性。这里的一致性是指，数据在每个集群节点中都是一样的，不存在不同的情况。

当然，如果主节点发生故障，集群就会处于一个混乱的状态，比如数据库集群中主节点故障后，可能导致每个节点上的数据一致性得不到保证。就好比，某个公司的 CEO 突然被辞退了，公司短时间可能就会出现人心不稳的情况。

**这，就应那句话“国不可一日无君”，对应到分布式系统中就是“集群不可一刻无主”。**总结来说，选举的作用就是选出一个主节点，由它来协调和管理其他节点，以保证集群有序运行和节点间数据的一致性。

分布式选举的算法

那么，如何在集群中选出一个合适的“领导者”呢？目前常见的选主方法有基于序号选举的算法，比如 Bully 算法、多数派算法，比如 Raft 算法、ZAB 算法等。下面的内容，我们一个一个来看。

Bully 算法

Bully 算法是一种极为主观的集群选主算法，为什么说是非常主观呢？因为它的选举原则是“长者”为大，简单来说，就是在所有活着的节点中，选取 ID 最大的节点作为主节点。

在 Bully 算法中，节点的角色有两种，分别是普通节点和主节点。初始化时，所有节点都是平等的，都是普通节点，并且都有资格成为领导者。但是，当选主成功后，有且仅有一个节点成为主节点，其他所有节点都是普通节点。当且仅当主节点故障或与其它节点失去联系后，才会重新选主。

Bully 算法在选举过程中，需要用到以下 3 种消息：

  • Election 消息，用于发起选举；
  • Alive 消息，对 Election 消息的应答；
  • Victory 消息，竞选成功的主节点向其他节点发送的宣誓主权的消息。

Bully 算法选举的原则是“长者为大”，意味着它的假设条件是，集群中每个节点均知道其他节点的 ID。在此前提下，其具体的选举过程是：

  1. 集群中每个节点判断自己的 ID 是否为当前活着的节点中 ID 最大的，如果是，则直接向其他节点发送 Victory 消息，宣誓自己的主权；
  2. 如果自己不是当前活着的节点中 ID 最大的，则向比自己 ID 大的所有节点发送 Election 消息，并等待其他节点的回复；
  3. 若在给定的时间范围内，当前节点没有收到其他节点回复的 Alive 消息，则会判定自己成为主节点，并向其他节点发送 Victory 消息，宣誓自己成为主节点；若接收到来自比自己 ID 大的节点的 Alive 消息，则等待其他节点发送 Victory 消息；
  4. 若该节点收到比自己 ID 小的节点发送的 Election 消息，则回复一个 Alive 消息，告知其他节点，我比你大，重新选举。

bully

Bully 算法的选择是比较霸道直接的。谁活着且谁的 ID 最大谁就是主节点，其他节点必须无条件服从。这种算法的优点是：选举速度快、算法复杂度低，而且实现起来比较简单。缺点也很明显，主要在于：需要每个节点有全局的节点信息，就造成存储了大量的重复数据；其次，任意一个比当前节点 ID 大的新节点或节点故障后恢复加入集群的时候，都可能会触发重新选举，成为新的主节点，如果该节点频繁退出、加入集群，就会导致集群频繁换主。

Raft 算法

Raft 算是是典型的多数派投票选举算法，其选举机制有点类似于我们日常生活中的民主投票机制，其核心思想是“少数服从多数”。简单来说就是，Raft 算法中，获得投票最多的节点成为主节点。

采用 Raft 算法选举，集群节点的角色有 3 种：

  • Leader，即主节点，同一时刻只有一个 Leader，负责协调和管理其他节点；
  • Candidate，即候选者，每一个节点都可以成为 Candidate，节点在该角色下才可以被选为新的 Leader；
  • Follower，Leader 的跟随者，不可以发起选举。

Raft 选举的流程，可以分为以下几步：

  1. 初始化时，所有节点均为 Follower 状态；
  2. 开始选主时，所有节点的状态由 Follower 转化为 Candidate，并向其他节点发送选举请求；
  3. 其他节点根据接收到的选举请求的先后顺序，回复是否同意成为主。这里需要注意的是，在每一轮选举中，一个节点只能投出一张票；
  4. 若发起选举请求的节点获得超过一半的投票，则成为主节点，其状态转化为 Leader，其他节点的状态则由 Candidate 降为 Follower。Leader 节点与 Follower 节点之间会定期发送心跳包，以检测主节点是否存活；
  5. 当 Leader 节点的任期到了，即发现其他服务器开始下一轮选主周期时，Leader 节点的状态由 Leader 降级为 Follower，进入新一轮选主。

raft

请注意，每一轮选举，每个节点只能投一次票。这种选举就类似人大代表选举，正常情况下每个人大代表都有一定的任期，任期到后会触发重新选举，且投票者只能将自己手里唯一的票投给其中一个候选者。对应到 Raft 算法中，选主时周期进行的，包括选主和任值两个时间段，选主阶段对应投票阶段，任值阶段对应节点成为主之后的任期。但也有例外的时候，如果主节点故障，会立马发生选举，重新选出一个主节点。

Google 开源的 Kubernetes，擅长容器管理与调度，为了保证可靠性，通常会部署 3 个节点用于数据备份。这 3 个节点中，有一个会被选为主，其他节点作为备。Kubernetes 的选主采用的是开源的 etcd 组件。而，etcd 的集群管理器 etcds，是一个高可用、强一致性的服务发现存储仓库，就是采用了 Raft 算法来实现选主和一致性的。

Raft 算法具有选举速度快、算法复杂度低、易于实现的优点；缺点是，它要求系统内每个节点都可以相互通信，且需要获得过半的投票数才能选主成功，因此通信量大。该算法选举稳定性比 Bully 算法好，这是因为当有新节点加入或故障恢复后，会触发选主，但不一定会真正切主，除非新节点或故障后恢复的节点获得投票数过半，才会导致切主。

ZAB 算法

ZAB（Zookeeper Atomic Broadcast）选举算法是 Zookeeper 实现分布式协调功能而设计的。相较于 Raft 算法的投票机制，ZAB 算法增加了通过节点 ID 和数据 ID 作为参考进行选主，节点 ID 和数据 ID 越大，表示数据越新，优先成为主。相比较于 Raft 算法，ZAB 算法尽可能保证数据的最新性。所以，ZAB 算法可以说是对 Raft 算法的改进。

使用 ZAB 算法选举时，集群中每个节点拥有 3 种角色：

  • Leader，主节点；
  • Follower，跟随者节点；
  • Observer，观察者，无投票权。

选举过程中，集群中的节点拥有 4 个状态：

  • Looking 状态，即选举状态。当节点处于该节点时，它会认为当前集群中没有 Leader，因此自己进入选举状态；
  • Leading 状态，即领导者状态，表示已经选出主，且当前节点为 Leader；
  • Following 状态，即跟随者状态，集群中已经选出主后，其他非主节点状态更新为 Following，表示对 Leader 的追随；
  • Observeing 状态，即观察者状态，表示当前节点为 Observer，持观望态度，没有投票权和选举权。

投票过程中，每个节点都有一个唯一的三元组（server_id，server_zxID，epoch），其中 server_id 表示本节点的唯一 ID；server_zxID 表示本节点存放的数据 ID，数据 ID 越大表示数据越新，选举权重越大；epoch 表示当前选取轮数，一般用逻辑时钟表示。

ZAB 选举算法的核心是“少数服从多数，ID 大的节点优先成为主”，因此选举过程中通过 vote_id，vote_zxID 来表明投票给哪个节点，其中 vote_id 表示投票节点的 ID，vote_zxID 表示被投票节点的服务器 zxID。ZAB 算法选主的原则是：server_zxID 最大者成为 Leader；若 server_zxID 相同，则 server_id 最大者成为 Leader。

下面就以 3 个 Server 的集群为例，此处每个 Server 代表一个节点，来介绍 ZAB 选主的过程。

第一步：当系统刚启动时（三个服务器同时启动），3 个服务器当前投票均为第一轮投票，即 epoch = 1，且 zxID 均为 0。此时每个服务器都会优先推选自己，并将投票信息 <epoch, voted_id, vote_zxID> 广播出去。

zab01

第二步：根据判断规则，由于 3 个 Server 的 epoch、zxID 都相同，因为比较 server_id，较大者即为推选对象，因此 Server1 和 Server2 将 vote_id 改为 3，更新自己的投票信息，并重新广播自己的投票。

zab02

第三步：此时系统内所有的服务都推选 Server3，超过半数，因此 Server3 当选 Leader，处于 Leading 状态，向其他服务器发送心跳包并维护连接；Server1 和 Server2 处于 Following 状态。

zab03

简单来说，ZAB 算法性能高，对系统无特殊要求，采用广播方式发送信息，若节点中有 n 个节点，每个节点同时广播，则集群中信息量为 n*(n-1) 个消息，同意出现广播风暴；且除了投票，还增加了对比节点 ID 和数据 ID，这就意味着还需要知道所有节点的 ID 和数据 ID，所以选举时间相对较长。但该算法选举稳定性比较好，当有新节点加入货节点故障后，出触发选主，但不一定真正切主，除非新节点或故障后恢复的节点数据 ID 和节点 ID 最大，且获得投票数过半，才会导致切主。

小结

本篇内容讲解了什么是分布式选举，以及为什么需要分布式选举。然后走马观花地介绍了 Bully 算法、Raft 算法以及 ZooKeeper 中的 ZAB 算法，并通过实例展示了各类方法的选举流程。

最后聊一聊为什么“多数派”选主算法通常采用奇数节点，而不是偶数节点呢？

多数派选主算法的核心是少数服从多数，获得投票多的节点胜出。想象一下，如果现在采用偶数节点集群，当两个节点均获得一半投票时，到底应该选谁为主呢？

答案是，在这种情况下，无法选出主，必须重新投票选举。但即使重新投票选举，两个节点拥有相同投票数的概率也会很大。

因此，多数派选主算法通常采用奇数节点。这，也是大家通常看到 ZooKeeper、 etcd、Kubernetes 等开源软件选主均采用奇数节点的一个关键原因。