Raft 选举算法

• Raft 算法是分布式系统开发首选的共识算法。
• 主要在分布式集群架构下进行领导者（主节点）的确认，比如现在流行的组件 Etcd, Consul, Nacos, RocketMQ, RedisSentinel 底层都是采用 Raft 算法来确认集群中的主节点，再通过主节点向其他节点下发指令。
• Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。

Raft 角色

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

Raft 选举过程

1. 初始状态：初始状态下，集群中所有节点都是跟随者的状态，任期（Term）都为 0
2. 发起投票: Raft 算法中每个节点等待领导者节点心跳信息的超时时间间隔是随机的，如果 NodeA 因为没有等到领导者的心跳信息先超时，则 A 节点成为候选者，并增加自己的任期编号，Term 值从 0 更新为 1，并给自己投了一票。
3. 成为领导者
   1. 节点 A 成为候选者后，向其他节点发送请求投票 RPC 信息，请它们选举自己为领导者。
   2. 节点 B 和节点 C 接收到节点 A 发送的请求投票信息后，在编号为 1 的这届任期内，还没有进行过投票，就把选票投给节点 A，并增加自己的任期编号。
   3. 节点 A 收到了大多数节点（n/2+1）的投票，从候选者成为本届任期内的新的领导者。
4. 与其他节点通讯：节点 A 作为领导者，固定的时间间隔给节点 B 和节点 C 发送心跳信息，告诉节点 B 和 C，我是领导者，节点 B 和节点 C 发送响应信息给节点 A，告诉节点 A 我是正常的。

选举中遇到的问题

1. 领导者的任期
   • 自动增加：跟随者在等待领导者心跳信息超时后，推荐自己为候选人，会增加自己的任期号，节点 A 任期为 0，推举自己为候选人时，任期编号增加为 1
   • 更新为较大值：当节点发现自己的任期编号比其他节点小时，会更新到较大的编号值，比如节点 A 的任期为 1，请求投票，投票消息中包含了节点 A 的任期编号，且编号为 1，节点 B 收到消息后，会将自己的任期编号更新为 1
   • 恢复为跟随者：如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态，这种场景出现在分区错误恢复后，任期为 3 的领导者受到任期编号为 4 的心跳消息，那么前者将立即恢复成跟随者状态。
   • 拒绝消息：如果一个节点接收到较小的任期编号值的请求，那么它会直接拒绝这个请求，比如任期编号为 6 的节点 A，收到任期编号为 5 的节点 B 的请求投票 RPC 消息，那么节点 A 会拒绝这个消息。
   • 一个任期内，领导者一直都会领导者，直到自身出现问题（如宕机），或者网络问题（延迟），其他节点发起一轮新的选举。
2. 防止多个节点同时发起投票：为了防止多个节点同时发起投票，会给每个节点分配一个随机的选举超时时间，这个时间内，节点不能成为候选者，只能等到超时，比如上述例子，节点 A 先超时，先成为了候选者，这种巧妙的设计，在大多数情况下只有一个服务器节点先发起选举，而不是同时发起选举，减少了因选票瓜分导致选举失败的情况。
3. 领导者节点下线：如果领导者节点出现故障，则会触发新的一轮选举。