【IT老齐057】Raft选举算法

用途

Raft 算法是分布式系统开发首选的共识算法
主要在分布式集群架构下进行领导者 (主节点)的确认。
比如现在流行的组件 Etcd、Consul、Nacos、RocketMQ、Redis Sentinel 底层都是采用Raft算法来确认集群中的主节点，再通过主节点向其他节点下发指令

如果掌握了这个算法，就可以较容易地处理绝大部分场景的容错和一致性需求。比如分布式配置系统、分布式 NOSQL 存储等等，轻松突破系统的单机限制。
Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。

角色

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

选举过程

初始状态

初始状态下，集群中所有节点都是跟随者的状态。如下图所示，有三个节点(Node)a、b、c，任期 (Term) 都为 0。

Raft 算法实现了随机超时时间的特性，每个节点等待领导者节点心跳信息的超时时间间隔是随机的。比如A 节点等待超时的时间间隔 150 ms，B 节点 200 ms，C 节点 300 ms。那么 a 先超时，最先因为没有等到领导者的心跳信息，发生超时。如下图所示，三个节点的超时计时器开始运行.

发起投票

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

Node A: Term = 1, Vote Count = 1.
Node B: Term = 0.
Node C: Term = 0.

成为领导

节点 A 成为候选者后，向其他节点发送请求投票 RPC 信息，请它们选举自己为领导者、
节点 B 和 节点C 接收到节点A 发送的请求投票信息后，在编号为 1 的这届任期内，还没有进行过投票，就把选票投给节点 A，并增加自己的任期编号
节点A收到3 次投票，得到了大多数节点 (n/2+1)的投票，从候选者成为本届任期内的新的领导者。
节点A 作为领导者，固定的时间间隔给 节点 B 和节点 C 发送心跳信息，告诉节点 B 和 C，我是领导者，组织其他跟随者发起新的选举
节点 B 和节点 C 发送响应信息给节点 A，告诉节点 A 我是正常的。

任期

自动增加: 跟随者在等待领导者心跳信息超时后，推荐自己为候选人，会增加自己的任号，如上图所示，节点 A 任期为 0，推举自己为候选人时，任期编号增加为 1。

更新为较大值：当节点发现自己的任期编号比其他节点小时，会更新到较大的编号值。比如节点 A 的任期为 1，请求投票，投票消息中包含了节点 A 的任期编号，且编号为 1，节点 B 收到消息后，会将自己的任期编号更新为 1。
恢复为跟随者：如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态。这种场景出现在分区错误恢复后，任期为 3 的领导者受到任期编号为 4的心跳消息，那么前者将立即恢复成跟随者状态。
拒绝消息: 如果一个节点接收到较小的任期编号值的请求，那么它会直接拒绝这个请求，比如任期编号为 6 的节点 A，收到任期编号为 5 的节点 B 的请求投票 RPC 消息，那么节点A 会拒绝这个消息。
一个任期内，领导者一直都会领导者，直到自身出现问题 (如宕机)，或者网络问题 (延迟)，其他节点发起一轮新的选举。

防止多节点同时发起投票

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

出发新一轮选举

如果领导者节点出现故障，则会触发新的一轮选举。如下图所示，领导者节点 A 发生故障，节点 B和 节点 C 就会重新选举 Leader。

节点A 发生故障，节点 B 和节点 C 没有收到领导者节点 A 的心跳信息，等待超时
节点 C 先发生超时，节点 C 成为候选人。
节点 C 向节点A 和节点 B 发起请求投票信息
节点 C 响应投票，将票投给了 C，而节点A 因为发生故障了，无法响应 C 的投票请求。
节点 C 收到两票 (大多数票数) ，成为领导者。
节点 C 向节点A和 B 发送心跳信息，节点 B 响应心跳信息，节点A 不响应心跳信息
节点 A 恢复后，收到节点 C 的高任期消息，自身将为跟随者，接收节点 C 的消息。

关键机制

保证了一个任期只有一位领导，极大减少了选举失败的情况。

任期机制
领导者心跳信息
随机选举超时时间
先来先服务的投票原则
大多数选票原则

__EOF__

本文作者： 石一歌 本文链接： https://www.cnblogs.com/faetbwac/p/18096859 关于博主： 评论和私信会在第一时间回复。或者直接私信我。 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！ 声援博主： 如果您觉得文章对您有帮助，可以点击文章右下角【推荐】一下。