Raft算法

Raft算法属于Multi-Paxos算法，它是在Multi-Paxos思想的基础上，做了一些简化和限制，比如增加了日志必须是连续的，只支持领导者、跟随者和候选人三种状态，在理解和算法实现上都相对容易许多

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

1、领导者选举
1）、成员身份
Raft算法支持领导者（Leader）、跟随者（Follower）和候选人（Candidate）3种状态：

跟随者：接收和处理来自领导者的消息，当等待领导者心跳信息超时的时候，就主动站出来，推荐自己当候选人
候选人：候选人将向其他节点发送请求投票（RequestVote）RPC消息，通知其他节点来投票，如果赢得了大多数选票，就晋升当领导者
领导者：负责处理写请求、管理日志复制和不断地发送心跳信息，通知其他节点“我是领导者，我还活着，你们现在不要发起新的选举，找个新领导者来替代我”
Raft算法是强领导者模型，集群中只能有一个领导者

2）、选举领导者的过程
在初始状态下，集群中所有的节点都是跟随者状态

Raft算法实现了随机超时时间的特性，每个节点等待领导者心跳信息的超时时间间隔是随机的。上图中，集群中没有领导者，而节点A的等待超时时间最小，它会最先因为没有等到领导者的心跳信息，发生超时

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

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

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

节点A当选领导者后，它将周期性地发送心跳消息，通知其他服务器我是领导者，阻止跟随者发起新的选举

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

请求投票（RequestVote）RPC：是由候选人在选举期间发起，通知各节点进行投票
日志复制（AppendEntries）RPC：是由领导者发起，用来复制日志和提供心跳消息
4）、什么是任期？
Raft算法中每个任期由单调递增的数字（任期编号）标识，任期编号是随着选举的举行而变化的

跟随者在等待领导者心跳信息超时后，推举自己为候选人时，会增加自己的任期编号，比如节点A的任期编号为0，那么在推举自己为候选人时，会将自己的任期编号增加为1
如果一个服务器节点，发现自己的任期编号比其他节点小，那么它会更新自己的任期编号到较大的编号值，比如节点B的任期编号是0，当收到来自节点A的请求投票RPC消息时，因为消息中包含了节点A的任期编号，且编号为1，那么节点B将把自己的任期编号更新为1
如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态。比如分区错误恢复后，任期编号为3的领导者节点B，收到来自新领导者的包含任期编号为4的心跳消息，那么节点B将立即恢复成跟随者状态
如果一个节点接收到一个包含较小的任期编号值的请求，那么它会直接拒绝这个请求。比如节点C的任期编号为4，收到包含任期编号为3的请求投票RPC消息，那么它将拒绝这个消息
5）、选举有哪些规则？
领导者周期性地向所有跟随者发送心跳消息（即不包含日志项的日志复制RPC消息），通知大家我是领导者，组织跟随者发起新的选举

如果在指定时间内，跟随者没有接收到来自领导者的消息，那么它就认为当前没有领导者，推举自己为候选人，发起领导者选举

在一次选举中，赢得大多数选票的候选人，将晋升为领导者

在一个任期内，领导者一直都会是领导者，直到它自身出现问题（比如宕机），或者因为网络延迟，其他节点发起一轮新的选举

在一次选举中，每一个服务器节点最多会对一个任期编号投出一张选票，并且按照先来先服务的原则进行投票。比如节点C的任期编号为3，先收到了一个包含任期编号为4的投票请求（来自节点A），然后又收到了一个包含任期编号为4的投票请求（来自节点B）。那么节点C将会把唯一一张选票投给节点A，当再收到节点B的投票请求RPC消息时，对于编号为4的任期，已没有选票可投了

日志完整性高的跟随者（也就是最后一条日志项对应的任期编号值更大，索引号更大）拒绝投票给日志完整性低的候选人。比如节点B的任期编号为3，节点C的任期编号为4，节点B的最后一条日志项对应的任期编号为3，而节点C为2，那么当节点C请求节点B投票给自己时，节点B将拒绝投票

选举是跟随者发起的，推举自己为候选人；大多数选票是指集群成员半数以上的选票；大多数选票规则的目标，是为了保证在一个给定的任期内最多只有一个领导者

6）、随机超时时间是什么？
Raft算法使用随机选举超时时间的方法，把超时时间都分散开来，在大多数情况下只有一个服务器节点先发起选举，而不是同时发起选举，这样就能减少因选票瓜分导致选举失败的情况

在Raft算法中，随机超时时间有2种含义：

跟随者等待领导者心跳信息超时的时间间隔是随机的
如果候选人在一个随机时间间隔内，没有赢得过半票数，那么选举就无效了，然后候选人发起新一轮的选举，也就是说，等待选举超时的时间间隔是随机的

7）、补充
1）Raft算法的强领导者模型选举限制和局限如下：

读写请求和数据转发压力落在领导者节点，相当于单机，性能和吞吐量也会受到限制
大规模跟随者的集群，领导者需要承担大量元数据维护和心跳通知的成本
领导者单点问题，故障后直到新领导者选举出来期间集群不可用
随着候选人规模增长，收集半数以上投票的成本更大
2）强领导者模型会限制集群的写性能，有什么办法能突破Raft集群的写性能瓶颈呢？

参考Kafka的分区和ES的主分片副本分片这种机制，虽然写入只能通过Leader写，但每个Leader可以负责不同的片区，来提高写入的性能

原文链接：https://blog.csdn.net/qq_40378034/article/details/117404484