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

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

组成

  • Raft 算法支持领导者（Leader）: 蛮不讲理的霸道总裁，一切以我为准，平常的主要工作内容就是 3 部分，处理写请求、管理日志复制和不断地发送心跳信息，通知其他节点“我是领导者，我还活着，你们现在不要发起新的选举，找个新领导者来替代我。”
  • 跟随者（Follower）: 就相当于普通群众，默默地接收和处理来自领导者的消息，当等待领导者心跳信息超时的时候，就主动站出来，推荐自己当候选人。
  • 候选人（Candidate）: 候选人将向其他节点发送请求投票（RequestVote）RPC 消息，通知其他节点来投票，如果赢得了大多数选票，就晋升当领导者。

需要你注意的是，Raft 算法是强领导者模型，集群中只能有一个“霸道总裁”。

选举领导者的过程

1. 初始状态都是跟随者

image.png

2. 投票

Raft 算法实现了随机超时时间的特性。也就是说，每个节点等待领导者节点心跳信息的超时时间间隔是随机的。通过上面的图片你可以看到，集群中没有领导者，而节点 A 的等待超时时间最小（150ms），它会最先因为没有等到领导者的心跳信息，发生超时。这个时候，节点 A 就增加自己的任期编号，并推举自己为候选人，先给自己投上一张选票，然后向其他节点发送请求投票 RPC 消息，请它们选举自己为领导者。

image.png

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

image.png

3. 统计结果

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

image.png

4. 心跳

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

image.png

细节

节点间如何通讯？

通过 RPC:

  • 请求投票（RequestVote）RPC，是由候选人在选举期间发起，通知各节点进行投票；
  • 日志复制（AppendEntries）RPC，是由领导者发起，用来复制日志和提供心跳消息。

什么是任期？

  • 在 Raft 算法中约定，如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态。
  • 如果一个节点接收到一个包含较小的任期编号值的请求，那么它会直接拒绝这个请求。

选举有哪些规则

  • 领导者周期性地向所有跟随者发送心跳消息，通知大家我是领导者，阻止跟随者发起新的选举。
  • 如果在指定时间内，跟随者没有接收到来自领导者的消息，那么它就认为当前没有领导者，推举自己为候选人，发起领导者选举。
  • 在一次选举中，赢得大多数选票的候选人，将晋升为领导者。(半数以上)
  • 在一个任期内，领导者一直都会是领导者，直到它自身出现问题（比如宕机），或者因为网络延迟，其他节点发起一轮新的选举。
  • 在一次选举中，每一个服务器节点最多会对一个任期编号投出一张选票，并且按照“先来先服务”的原则进行投票。
  • 日志完整性高的跟随者，拒绝投票给日志完整性低的候选人。

如何理解随机超时时间

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