Raft 算法——Leader选举

标签：分布式系统首次发布：2023-11-29最近修改：2023-11-29

引言

大名鼎鼎的 Paxos 算法可能不少人都听说过，几乎垄断了一致性算法领域，在 Raft 协议诞生之前，Paxos 几乎成了一致性协议的代名词。但是对于大多数人来说，Paxos 算法太难以理解了，而且难以实现。因此斯坦福大学的两位教授 Diego Ongaro 和 John Ousterhout 决定设计一种更容易理解的一致性算法，最终提出了 Raft 算法！

如果要用一句话概括 Raft 算法，我觉得是这样的：从本质上说，Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。这句话比较抽象，举个例子：领导者就是 Raft 算法中的总裁，通过“一切以我为准”的方式，决定了日志中命令的值，也实现了各节点日志的一致。

Raft 基础

成员身份

成员身份，又叫做服务器节点状态，Raft 算法支持领导者（Leader）、跟随者（Follower）和候选人（Candidate） 3 种状态。为了方便讲解，我们使用不同的图形表示不同的状态。在任何时候，每一个服务器节点都处于这 3 个状态中的 1 个。

跟随者：就相当于普通群众，默默地接收和处理来自领导者的消息，当等待领导者心跳信息超时的时候（主观的认为领导者挂了），就主动站出来，推荐自己当候选人。Raft 保证任何时刻只有一个 Leader。
候选人：候选人将向其他节点发送请求投票，通知其他节点来投票，如果赢得了大多数选票，就晋升当领导者。
领导者：蛮不讲理的总裁，一切以我为准，平常的主要工作内容就是 3 部分，处理写请求、管理日志复制和不断地发送心跳信息，通知其他节点：我是领导者，我还活着，你们现在不要发起新的选举，找个新领导者来替代我。

名词解释

然后在进行选举过程中，还有几个重要的概念：

领导人选举（Leader Election）：简称选举，就是从候选人中选出领袖；
选举超时（Election Timeout）：就是一个超时时间，当群众超时未收到领袖的心跳时，会重新进行选举。
任期（Term）：Raft 将时间划分为一个一个的任期，每个任期由单调递增的数字（任期编号）标识。任期编号随着选举的举行变化而变化，即每个任期始于一个新的选举。任期变化的示意图如下图所示：

从上图可以看出，任期一般包含两阶段，第一阶段是选举阶段，第二阶段为已选举出领导者的阶段。但任期也可能只包含选举阶段。可以看到任期 3 由于并没有成功选举出领导者（即论文所说的 a split vote，两个节点同时成为候选人同时发起选举，导致无法成功选出领导者），只包含了选举阶段。接下来马上进入任期 4，接着进行新一轮的选举。

Raft 任期具有如下特点：

跟随者在等待领导者心跳消息超时后，推举自己为候选人时，会增加自己的任期编号，比如节点 A 的当前任期编号为 0，那么在推举自己为候选人时，会将自己的任期编号增加为 1。
如果一个节点，发现自己的任期编号比其他节点小，那么它会更新自己的编号到一个较大的编号值。比如，节点 B 的任期编号为 0，当收到来自节点 A 的请求投票的 RPC 消息，消息中包含节点的任期编号为 1，那么节点 B 将把自己的任期编号更新为 1。
如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态。比如网络分区错误，导致出现两个领导者，当分区错误恢复后，任期编号为 3 的领导者 B 接收到领导者 A 任期编号为 4 的心跳消息，那么节点 B 将立即恢复成跟随着状态，接受节点 A 为领导者。
如果一个节点接收到一个包含较小任期编号值的请求，那么它会直接拒绝这个请求。例如，节点 C 的任期编号为 4，接收到任期编号为 3 的 RPC 消息，那么节点 C 将拒绝这个消息。

Leader 选举

选举过程

首先，在初始状态下，集群中所有的节点都是跟随者的状态。

Raft 算法实现了随机超时时间的特性。也就是说，每个节点等待领导者节点心跳信息的超时时间间隔是随机的。通过上面的图片你可以看到，集群中没有领导者，而节点 A 的等待超时时间最小（150ms），它会最先因为没有等到领导者的心跳信息，发生超时。

这个时候，节点 A 就增加自己的任期编号，并推举自己为候选人，先给自己投上一张选票，然后向其他节点发送请求投票 RPC 消息，请它们选举自己为领导者。

如果其他节点接收到候选人 A 的请求投票 RPC 消息，在编号为 1 的任期内，也还没有进行过投票，那么它将把选票投给节点 A，并增加自己的任期编号。

候选人 A 在选举超时时间内赢得了大多数的选票，那么它将会成为本届任期内新的领导者。

节点 A 成为领导者后，会周期性地向其他跟随者发送心跳消息，通知其他节点我是领导者，以防止其他节点发起新的选举篡权。

总结一下 Raft 算法的 Leader 选举规则：

领导者周期性地向所有跟随者发送心跳消息（心跳超时时间），用于通知大家我是领导者，阻止跟随者发起新的选举。
如果在指定的时间内（选举超时时间），跟随者没有接收到领导者的消息，那么它就认为当前没有领导者，推举自己为候选人，发起新的选举。
在一次选举中，赢得大多数选票（半数以上）的候选人，将晋升为领导者。
在一个任期内，领导者会一直都是领导者，直到自身出现问题（例如节点宕机），或者出现网络延迟，其他节点发起新的一轮选举。
在一次选举中，每个节点最多只能对一个任期编号投出一张选票，并按照先来先服务的原则进行投票。比如节点 C 的任期编号为 3，先收到节点 A 的投票请求，节点 A 的任期编号为 4；然后又接收到节点 B 的投票请求，节点 B 的任期编号为 4。那么，节点 C 会将任期 4 的唯一一张选票投给节点 A，当节点 C 再接收到节点 B 的投票请求时，节点 C 已经没有任期 4 的选票了。
日志完整性高的跟随者（每一个日志项都有一个任期编号，最后一条日志项对应的任期编号更高，拿索引号更大，日志也就更完整），拒绝投票给日志完整性低的候选人。这是因为 Raft 算法要确保选出的领导者具有所有已提交条目的完整信息，以此来维护数据的一致性。例如，节点 B 的任期编号为 3，节点 C 的任期编号为 4，节点 B 最后一条日志项对应的任期编号为 3，节点 C 最后一条日志项对应的任期编号为 2。那么，当节点 C 请求节点 B 投票给自己时，节点 B 将拒绝投票。

节点通信

在 Raft 算法中，服务器节点间的沟通联络采用的是远程过程调用（RPC），在领导者选举中，需要用到这样两类的 RPC：

请求投票（RequestVote）RPC，是由候选人在选举期间发起，通知各节点进行投票；
日志复制（AppendEntries）RPC，只能由领导者发起，用来复制日志和提供心跳消息。

超时时间

在选举中，可能会出现这种情况：在同一个任期内，多个候选人同时发起选举，选票被瓜分，导致没有一个候选人获得大多数的选票成为领导者，选举失败，即出现所谓的 a split vote。

为了降低出现 a split vote 的概率，Raft 引入了随机超时时间的方法，把超时时间分散开来，大多数情况下只有一个节点发起选举，避免同时发起选举的情况出现。在 Raft 中，包含两种超时时间：

选举超时时间：跟随者等待成为候选人的超时时间，即跟随者在一段时间内没有接收到任何消息，那么它就假定集群内没有领导者，并开始新一轮的选举。选举超时时间为随机值 150 ~ 300 ms。
心跳超时时间：领导者发送心跳的时间间隔。

Raft 算法以领导者为中心，选举出领导者后，一切以领导者为准，以达成值的共识，实现各节点日志的一致。

注意：领导者广播心跳的周期必须要短于选举超时时间，因为要考虑到网络消息传输的延迟等问题。如果这两个时间间隔刚好相等，那么群众会频繁成为候选者，也就会出现频繁发生选举，切换 Leader 的情况。

出现多个候选者

在以下情况下可能会出现多个候选者：

选举超时：每个跟随者都有一个随机的选举超时计时器，如果在该计时器结束前没有收到当前领导者的心跳，该跟随者将变成候选者并开始新一轮的选举。如果多个跟随者几乎同时达到选举超时，它们都会成为候选者。
消息延迟：网络延迟可能导致候选者的选举请求或者领导者的心跳迟迟不到，这可能导致跟随者因为超时而变成新的候选者。

如果出现多个候选者，会发生以下情况：

竞争选举投票：每个候选者都会为自己投票，并向其他所有节点发送投票请求。每个节点只会在给定的任期内投票一次，这意味着在同一轮选举中，一个节点只能给一个候选者投票。跟随者会根据先来先服务的原则进行投票，但并不是先到的投票请求就一定有票，还要看跟随者和候选者之间的日志完整性，如果候选者的日志完整性低于跟随者，那么跟随者将拒绝对这个候选者投票。
冲突解决：获得多数（超过半数）节点投票的候选者将成为新的领导者。如果由于选票的瓜分，导致没有一个候选者能够获得多数票，那么这一轮选举将失败，相关节点将等待一个随机的时间后再次开始新一轮的选举。