[TOC]

Raft 选举的用途

Raft 算法是分布式系统开发首选的共识算法。

主要在分布式集群架构下进行领导者（主节点）选举。

比如现在流行的组件：Etcd、Consul、Nacos、RocketMQ、Redis Sentinel 底层都是采用 Raft 算法来选举集群中的主节点，再通过主节点向其他节点下达指令。

如果掌握了这个算法，就可以比较容易地处理绝大部分场景的容错和一致性需求。比如分布式配置系统、分布式 NoSQL 存储等等，轻松突破系统的单机限制。

Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各个节点日志的一致。

Raft 角色

• 领导者（Leader）：霸道总裁，一切以我为准。处理写请求、管理日志复制和不断地发送心跳信息，通知其他节点“我是领导者，我还活着，你么不要发起新的选举”。
• 候选人（Candidate）：候选人将向其他节点请求投票 RPC 消息，通知其他节点来投票，如果赢得大多数选票，就晋升当领导。
• 跟随者（Follower）：普通群众，默默接收来自领导的消息，当领导者心跳信息超时的时候，就主动站出来，推荐自己当候选人。

Raft 选举过程

1.初始状态

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

如下图所示：有三个节点（Node）a、b、c，任期（Term）都为 0

Raft 算法实现了**随机超时时间特性。**每个节点等待领导者心跳信息的超时时间间隔是随机的。比如 A 节点等待的超时时间间隔为 150ms， B 节点 200ms，C 节点 300ms。那么节点 A 先超时，最先因为没有等到领导的心跳信息，发生超时，因而节点 A 变为候选者，发起选举。

2.发起投票

当 A 节点的超时时间到了后，A 节点成为候选者，并增加自己的任期编号，Term 值从 0 更新为 1，并给自己投了一票。

• Node A：Term = 1，Vote Count = 1
• Node B：Term = 0
• Node C：Term = 0

选举过程

1. 节点 A 成为候选者后，向其他节点发送投票请求 RPC 信息，请他们选举自己为领导者。
2. 节点 B 和 节点 C 接收到节点 A 发送的请求投票信息后，在编号为 1 的任期内，节点 B 和 节点 C 还没有进行过投票，就把选票投给节点 A，并增加自己的任期编号。每个节点在一个任期内只能投一票。
3. 节点 A 收到 3 次投票（包括自己的一票），得到了大多数节点$\frac{n}{2}+1$ 的投票，从候选者成为本届任期内的新的领导者。
4. 节点 A 作为领导者，固定的时间间隔给节点 B 和节点 C 发送心跳信息，告诉节点 B 和节点 C ，我是领导者。
5. 节点 B 和节点 C 发送相应信息给节点 A ，告诉节点 A 我是正常的。

3.领导者的任期

英文单词是 term，领导者是由任期的。

• 自动增加：跟随者在等待领导者心跳信息超时后，推荐自己为候选人，会自动增加自己的任期号。
• 更新为较大值：当节点发现自己的任期编号比其他节点小时（自己的编号过时了），会跟新到较大的编号。比如：节点 A 的任期是 1，请求投票时，节点 B 收到消息后，发现自己任期编号小，会更新为1
• 恢复为跟随者状态：如果一个候选人或者领导者，发现自己的任期编号比其他节点小（改朝换代了），那么它会立即恢复成跟随者状态。比如领导者任期为 3，由于自己不健康，产生了新的领导者，那么前者将立即恢复成跟随者。
• 拒绝消息：如果一个节点接收到较小的任期编号的请求，那么它会直接拒绝这个请求。可能这个请求是已经被废弃的领导者发过来的。
• 一个任期内，领导者一直都会是领导者，直到自身出了问题（如宕机）或者网络延迟，其他节点会发起新一轮的选举。

4. 防止多个节点同时发起投票

为了防止多个节点同时发起投票，会给每个节点分配一个随机的选举超时时间。这个时间内，节点不能成为候选者，只能等待超时。比如上述例子中的 节点 A 率先超时，先成为了候选者。这种巧妙的设计，在大多数情况下只有一个服务器节点先发起选举，而不是同时发起选举，减少了因选票瓜分导致选举失败的情况。

如果发生选票瓜分： 如果有多个 Follower 同时成为 Candidate，那么选票可能会被瓜分以至于没有 Candidate 可以赢得半数以上的投票。当这种情况发生的时候，每一个 Candidate 都会竞选超时，然后通过增加当前 Term 号来开始一轮新的选举。 在选票瓜分的情况下：每一个 Candidate 在开始一次选举的时候会**重置一个随机的选举超时时间**，然后在超时时间内等待投票的结果；这样减少了在新的选举中另外的选票瓜分的可能性。

5. 触发新的一轮选举

如果领导者节点出现故障了，则会触发新的一轮选举。

如下图：领导者节点 A 发生故障，节点 B 和节点 C 就会重新选举 Leader。

选举过程：

1. 节点 A 发生故障，节点 B 和节点 C 没有收到领导者节点 A 的心跳信息，等待超时。
2. 节点 C 先发生超时，节点 C 成为候选人。
3. 节点 C 向节点 A 和节点 B 发起请求投票。
4. 节点 A 因为故障，无法相应节点 C 的投票请求。
5. 节点 C 收到两票（大多数票数），成为新的领导者。
6. 节点 C 向节点 A 和节点 B 发送心跳信息，节点 B 响应心跳信息，节点 A 不响应心跳信息。
7. 节点 A 恢复后，收到节点 C 的高任期消息（心跳），自身降级为跟随者，接收节点 C 的消息。

总结

Raft 算法通过以下几个关键机制，保证了一个任期只有一位领导者，极大减少了选举失败的情况。

• 任期机制：自增，低任期作废。
• 领导者心跳信息
• 随机选举超时时间
• 先来先服务的投票原则：同一任期只投票，过期任期拒绝投票。
• 大多数选票原则