摘要

Raft 是目前大部分分布式系统的首选共识算法

1. Raft算法成员类型和功能
2. Leader选主流程：候选人、超时计时、投票原则、任期机制
3. 节点状态转换

Raft成员

按照我的理解，Raft 是一种强领导者模型，即一切以领导者为准，实现一系列的共识和各个节点日志一致性的一种共识算法。

Raft 一共有三种成员身份，分别是：领导者（Leader）、跟随者（Follower）、候选人（Candidate）。

跟随者：在 Raft 中只有领导者才会与客户端交互，因此在不发生选举时，跟随者仅默默地处理来自领导者发送的消息，充当数据冗余的作用，当领导者心跳超时，跟随者就会主动推荐自己当选候选人。

候选人：成为候选人之后，就会向其他节点发送请求投票消息，以获取其他节点的投票，如果获得了大多数选票，则当选领导者。

领导者：数据一切以领导者为准，它也是与客户端交互的唯一角色，处理请求，管理日志的复制，同时还不断地发送心跳信息给跟随者，不断刷新跟随者节点的超时时间，以防跟随者发起新的选举。

Leader选举概念

选举过程

下面我以一个刚初始化的 Raft 集群为例：

1、初始状态

Raft 每个节点初始化后的心跳超时时间都是随机的，如上所示，节点 C 的超时时间最短（120ms），任期编号都为 0，角色都是跟随者。

2、请求投票

此时没有一个节点是领导者，节点等待心跳超时后，会推荐自己为候选人，向集群其他节点发起请求投票信息，此时任期编号 +1，自荐会获得自己的一票选票。

3、跟随者投票

跟随者收到请求投票信息后，如果该候选人符合投票要求后，则将自己宝贵（因为每个任期内跟随者只能投给先来的候选人一票，后面来的候选人则不能在投票给它了）的一票投给该候选人，同时更新任期编号。

4、当选领导者

当节点 C 赢得大多数选票后，它会成为本次任期的领导者。

5、领导者与跟随者保持心跳

领导者周期性发送心跳消息给其他节点，告知自己是领导者，同时刷新跟随者的超时时间，防止跟随者发起新的领导者选举。

关于任期

从以上的选举过程看，我们知道在 Raft 中的选举中是有任期机制的，顾名思义，每一任领导者，都有它专属的任期，当领导者更换后，任期也会增加，Raft 中的任期还要注意以下个细节：

1. 如果某个节点，发现自己的任期编号比其他节点小，则会将自己的任期编号更新比自己更大的值；
2. 从上面的选举过程看出，每次推荐自己成为候选人，都会得到自身的那一票；
3. 如果候选人或者领导者发现自己的任期编号比其它节点好要小，则会立即更新自己为跟随者，这点很重要，按照我的理解，这个机制能够解决同一时间内有多个领导者的情况，比如领导者 A 挂了之后，集群其他节点会选举出一个新的领导者 B，在节点 A 恢复之后，会接收来自新领导者的心跳消息，此时节点 A 会立即恢复成跟随者状态；
4. 如果某个节点接收到比自己任期号小的请求，则会拒绝这个请求。

关于随机超时

跟随者如果没有在某个时间内接收到来自领导者的心跳，则会发起新一轮的领导者选举，试想一下，如果全部跟随者都在同一时间发起领导者选举，这是一种怎样的场景？会不会造成同一时间内造成选举混乱呢？如果同时发起选举，会不会因为选票被瓜分导致选举失败的原因？

感觉会出现很多问题，但是 Raft 它利用随机超时巧妙地避开了这些问题。为此为我还在视频号录制了一段 Raft 选举过程的视频：

如果你想自己亲自调试并观摩 Raft 选举过程，你可以访问以下网址：

https://raft.github.io/

Leader选举详解

Raft 源于“Reliable, Replicated, Redundant, And Fault-Tolerant” 是一种用于替代 Paxos 的共识算法。它的目标是确保集群内任意节点的状态保持一致，同时力保整个算法过程易于理解。

注：所有图片除了引自论文，其他均本人所作，想用就拿去用。但转载文章请标明出处：掘金 - 辐射工兵。

读完本文，你将：

• Raft 算法的 Leader 选举会深深印在你的脑海。

相关资料

• 交互演示：Raft (thesecretlivesofdata.com)
• 发布论文：In Search of an Understandable Consensus Algorithm (raft.github.io)

Raft 算法的特点

• 强领导者：Raft 推出一个 Leader 的角色，同时赋予该角色非常强的领导能力，所有数据的管理都交由该角色。
• Leader 选举：Raft 使用了一个随机计时器来选举领导者。通过简单地在心跳机制的基础上加上一个随机计时器，避免了大部分同时选举的发生。
• 成员关系调整：Raft 使用一种共同一致的方法来处理集群成员变换的问题，在这种方法下，处于调整过程中的两种不同的配置集群中大多数机器会有重叠，这就使得集群在成员变换的时候依然可以继续工作。

Raft 定义的角色

Raft 定义了三种角色：领导者（Leader）、跟随者（Follower） 和 候选人（Candidate）。这三种状态不是一成不变的，每个节点都会在这三种状态中进行转换。

• 领导者：当节点作为领导者时，所有集群接收的数据都将通过他接收，再由他决定对数据的处理。他将和所有其他节点保持一个心跳连接，以维护自己的领导状态。心跳连接通过发送一个个的心跳包实现，如果要对其他节点发出命令，就会将命令和数据携带在心跳包中。

• 跟随者：当节点作为跟随者时，只会负责执行领导者的决策，或者响应领导者发送过来的心跳包，以显示自己仍处于连接。

• 候选人：当发现领导者下线之后，跟随者节点会马上转变为候选人，并开始组织竞选，通过拉票的方式竞选成为新一任的领导者。

本文所作的演示图尽量与交互演示中的样式保持一致：

节点的状态

节点有两个必须属性：

• currentTerm：节点当前所处的任期。
• votedFor 　：节点当前任期所跟随的其他节点的 ID。如果是投票阶段，表示节点所投的候选人。如果已经竞选结束，就是当前的领导人。

超时计时器

Raft 定义了超时计时器来控制选举，分别是选举超时时间、投票超时时间和竞选等待超时时间。

选举超时时间

领导者会通过周期性地向跟随者发送心跳包来维持自己的统治地位。每个跟随者都会有一个选举超时时间，这个时间是随机的（如 150-300 ms），就是上文所说的随机计时器。每次接收到心跳包之后，跟随者都会重置该超时时间。如果在超时之前没有收到心跳包，跟随者就会判定领导者已下线，此时跟随者就会转变为候选人，开始准备竞选。

选举超时时间的设置让每个节点都有机会能够成为领导者，彷佛每个节点都是蓄势待发的夺权者。超时时间是随机的，超时时间越短，就能越快地变成候选人，野心就越大。一旦当权者失去掌控（断开心跳），节点的野心无法得到遏制就会马上夺权（展开竞选）。

投票超时时间

当跟随者变成候选人时，会开启投票超时的倒计时，并邀请所有其他节点为自己投票。在倒计时结束之前如果得票超一半节点数，候选人就竞选成功。如果到了投票超时时间还没攒够票数，该候选人就会宣告这一轮竞选失败，会等一段时间之后再参与竞选。

其他节点响应投票邀请时，只会回复是否投票给发起者，所有发起投票的候选人是无法得知其他人的得票情况的，只能统计自己的得票数。因此候选人失败时是不知道其他候选人是否成功的，甚至不知道其他候选人的存在。

竞选等待超时时间

当候选人选举失败时，会等待一段时间之后再次参与竞选，这段等待时间就是竞选等待超时时间。

此时其他节点可以参加竞选，也可能已经在竞选了，如果候选人在等待投票超时时间或者竞选等待超时时间时其他节点竞选成功，则候选人会马上转变为跟随者跟随该新晋的领导者。

超时时间重置

只要跟随者收到请求，就会重置自身的选举超时时间，因此领导者会不断地周期性地发送心跳包控制跟随者。同时候选人的投票邀请也会重置跟随者的请求超时时间，让收到投票但是还没参加竞选的跟随者不参与竞选。

Raft 定义的 RPC 请求

Raft 使用 RPC 方式进行通讯，Raft 只定义了两种请求就能够完成所有的通讯。分别是日志追加请求和投票请求。

在 Raft 协议中，通常说的是日志，但实际上传输的数据类型可以是各种各样的，不过由于日志的特性，日志比普通的数据更为复杂和难以协调。本文直接用数据替代日志，因为 Leader 选举这一过程对日志的涉及非常少。

数据追加请求

当领导者接收到客户端的数据，就会发送数据追加请求将数据复制给所有的跟随者，因此保证所有节点的数据统一。当传输的数据为空，该请求就变成了保持连接的心跳包。该请求的定义为：

/**
 *
 * @param term          发送节点的任期
 * @param leaderId      领导者 ID，用于重定向回领导者，因为有时客户端会直接把数据发给跟随者
 * @param prevLogIndex  上一个数据（日志）条目的索引         （非 Leader 选举阶段）
 * @param prevLogTerm   上一个数据（日志）条目的任期         （非 Leader 选举阶段）
 * @param entries       需要保存的数据，如果是心跳包的话，为空
 * @param leaderCommit  领导者的已知已提交的最高数据条目的索引（非 Leader 选举阶段）
 */
Result appendEntries(term, leaderId, prevLogIndex, prevLogTerm, entries[], leaderCommit) {}

返回结果结构为：

Result {
    term,       响应节点的任期
    success     请求成功或者失败
}

投票请求

当候选人发起投票时，会将投票请求发现所有其他节点，请求其他节点进行投票。每个接收投票请求的节点都会返回自己的投票结果。

/**
 * 投票请求
 *
 * @param term          发送候选人的任期
 * @param candidateId   发送候选人的 ID
 * @param lastLogIndex  上一个数据（日志）条目的索引（非 Leader 选举阶段）
 * @param lastLogTerm   上一个数据（日志）条目的任期（非 Leader 选举阶段）
 */
Result requestVote(term, candidateId, lastLogIndex, lastLogTerm) {}

返回结果结构为：

Result {
    term,           响应节点的任期
    voteGranted     boolean，若为 true 表示支持发出请求的候选人
}

任期概念

Raft 定义了 任期（Term） 这一概念，所有节点都会有 currentTerm 这个属性，就是该节点当前所处的任期。

任期在 Raft 算法里起一个逻辑时钟的作用，第几个任期，即第几个 term 就类似于我国的第几个朝代这种概念，而领导人，就仿佛是朝代的君王。

选举规则

Leader 选举有以下规则：

1. 每一轮任期中，只会出现一位领导者，或者没有领导者。就像某些朝代群雄割据，并没有统一的帝王。

   如果候选人要晋升为领导者，必须获得超过一半的票数（N/2 + 1），总票数是集群中节点的数量。

   如果集群中投票节点数为偶数个，那么可能会由于平票的原因而导致一轮任期中没有领导者的产生。此时就会等待竞选超时计时器超时后进入下一个任期，继续选举领导人。

   
   （从论文图示可以看，并非每一任能选出领导人）

2. 当领导者下线之后，集群开始进入新的任期。就像一个皇帝的退位标志着朝代的更迭。

   由于选举超时计时器和心跳机制的存在，节点的计时器如果发生超时，就会发现领导者下线，此时节点就会让 currentTerm 加一，同时 votedFor 指向自己，然后马上展开竞选。

   

3. 任何节点收到任期比自身任期大的请求时，需要马上跟随对方并更新自己的任期。

   无论是投票请求还是数据追加请求，只要请求中的 term 大于节点自身的任期，就表明对方比自身要更先进，此时节点无条件跟随对方，将自己的 votedFor 设置为对方的 ID，并更新自身任期为 term。

   • 如果是投票请求，表示对方先于自己发现领导人已下线和先于其他人来拉票，根据这个信息从节点的角度出发该候选人有比较大的概览胜选，因此跟随它并给他投票。
   • 如果是数据追加请求，表明对方是最新任期的竞选获胜者，同时表示节点自身没有参加该任期的选举，可能是节点临时掉线或投票请求丢包。此时直接跟随领导人即可。

   

4. 任何节点收到任期等于自身任期的数据追加请求时，需要马上跟随对方。

   对方任期等于节点自身任期，并且能够发送数据追加请求（心跳包），就表明对方是领导者。而我们知道，一轮选举只能选出一位领导者，因此该发送方必定是此轮选举获胜者，因此，如果节点的 votedFor 不是它，表示当前节点可能是获选候选人的跟随者或者落选候选人本人，此时需要马上将自身的 votedFor 设置为对方的 ID 来跟随他。

5. 在一轮任期的选举中，任何一个节点都只能投给一个候选人。

   从上文我们知道，当节点收到 term 比自身任期大的投票请求时，会更新自身任期并跟随该候选人。而且，在本轮选举中（term == currentTerm），无论是什么投票请求，都只会投给自己跟随的候选人。

   同时从上文我们也知道，如果节点自己就是候选人，那么他在成为候选人是会更新自己的任期，因此同样的，在本轮选举中，他只会给自己投票。

   votedFor 在任期发生更新时就确定了，要么是自己，要么是第一个来拉票的候选人。只有在自己或者跟随的候选人选举失败时，才会发生更改来跟随获胜的领导人，否则一直都不会变。

6. 如果收到任期比自身小的请求直接丢弃，否则必须回复。

   如果请求的任期比节点自身任期小，无论是数据追加请求还是投票请求，都表明对方已经有一段时间没有和其他节点沟通了，应该是掉线了的领导者或者竞选者。此时对方的状态是过时的，一切请求都直接丢弃。

选举过程

基于以上的规则，实际上 Leader 选举的过程就变得非常简单了，一句话概括为：候选人只会给自己投票，跟随者会一直投给第一个找他的候选人，只有得票超出一半的候选人才能成为领导者，所有人都必须跟随胜选的领导者。

仅有一个候选人

1. 节点 A 发现领导人下线，currentTerm 加一，并将 votedFor 指向自己，并开始向其他节点发送投票请求。
2. 其他节点收到投票请求，发现选票上的任期比自己任期大，因此跟随 A 并投票给 A，并重置超时计时器。
3. 节点 A 每收到一个投票回复，就累计自己当前任期的得票数。
4. 当累计得票数超过 1/2 节点总数时，节点 A 转变为领导者，向所有节点发送心跳包宣告选举胜利。

多个候选人同时选举

Raft 已经通过随机超时计时器来防止大部分多候选人同时选举的情况发生了，但再小的几率也会发生。同时，如果集群间数据延迟很大，也很容易发生多候选人同时选举的情况。

假如 A、B、C 三节点选 Leader，多候选人的情况有：

1. 节点 A、B 同时展开竞选。或者节点 A 先展开竞选，但是投票请求到达节点 B 前，节点 B 超时变成候选人。
2. 节点 A、B、C 同时展开选举。或者各节点投票请求在到达其他节点时，目标节点超时变成候选人。

其实这两种情况都是一样的：

1. 节点 A、B 同时展开竞选，发送投票请求，
2. A 的请求到达 B，B 的请求到达 A，双方都不给对方投票。
3. A 的请求到达 C，C 投给 A，C 发送回复给 A。
4. 在回复达到 A 之前，B 的请求到达 C，C 不给 B 投票。
5. B 收到所有回复，发现只有 1/3 的选票，竞选失败，过一段时间后再参选。
6. A 收到 C 的回复时，发现票数已超 1/2，宣布竞选成功。

ABCA 成为候选人，term = 3B 成为候选人，term = 3C 跟随 A，term = 3A 成为领导者requestVote(3, A, 0, 0)falserequestVote(3, B, 0, 0)falserequsetVote(3, A, 0, 0)requestVote(3, B, 0, 0)falsetrueappendEntries(3, A, 0, 0, null, 0)appendEntries(3, A, 0, 0, null, 0)ABC

或者：

1. 节点 A、B、C 同时展开竞选。
2. 所有节点竞选完毕发现选票都是 1/3，都进入竞选超时计时器，随机一段时间后进行下一任期竞选。
3. 下一轮 A 比其他人早超时，任期加一，率先发送投票请求。
4. 由于投票请求的 term 都比自身大，因此 B、C 投票给 A。
5. A 收到 B 或 C 的选票时就会直接宣告胜利了。

ABCA 成为候选人，term = 3B 成为候选人，term = 3C 成为候选人，term = 3A 竞选超时，term = 4C 跟随 A，term = 4B 跟随 A，term = 4A 成为领导者requestVote(3, A, 0, 0)requestVote(3, B, 0, 0)requestVote(3, A, 0, 0)requestVote(3, C, 0, 0)requestVote(3, B, 0, 0)requestVote(3, C, 0, 0)falsefalsefalsefalse等待竞选超时false等待竞选超时false等待竞选超时requsetVote(4, A, 0, 0)truerequestVote(4, A, 0, 0)trueappendEntries(3, A, 0, 0, null, 0)appendEntries(3, A, 0, 0, null, 0)ABC

节点的状态转换

依据上文，可以推导出节点的状态转移过程：

候选人：

• 当计时器超时，将变为候选人参加竞选。

候选人：

• 当投票超时，候选人会等待一段时间重新参加竞选。
• 当投票获胜，侯选人会晋升为领导人。
• 当收到同任期的数据追加请求或者更高任期的请求，候选人会转变为跟随者跟随对方。

领导者：

• 当收到更高任期的请求，领导者会转变为跟随者跟随对方。