Raft 领导选举 Leader election


目录

  1. 心跳机制触发领导人选举
  2. 选举过程
  3. 选举规则
  4. 注意点

从之前的文章中,我们知道,在 Raft 中,所有节点初始都是跟随者,然后通过 Raft 的流程进行角色转换:

图 1

1. 心跳机制触发领导人选举

当领导人成功当选后,会通过心跳机制维持自己的权威。具体细节如下:

  1. 领导者周期性的向所有跟随者发送心跳包(即空白的日志条目)维持自己的权威。
  2. 如果一个跟随者在一段时间里,没有收到任何消息,称之为选举超时,那么,他就会认为没有可用的领导,并且发起重新选举。

2. 选举过程

可以大致分为 2 个过程:

  1. 增加自己当前的任期号,并且转到候选人状态
  2. 并行的向集群中其他节点发送请求投票 的 RPC 消息,让他们给自己投票。这可能会带来 3 种结果。
  • 自己赢得这次选举
  • 其他的服务器赢得选举
  • 一段时间过后,谁也没有获胜 , 例如多个跟随者同时成为候选人,当这种情况发生,每一个候选人都会超时,然后他们会通过增加任期号的方式,继续尝试新一轮的选举。如果不加限制,将无限循环这个操作。为了解决这个问题,Raft 增加了一个“随机时间机制”,这个时间为 150 - 300 毫秒,这样就使得每个节点发送 RPC 请求的时间错开。

3. 选举规则

当然,并不是任何一个节点都可以成为领导人,就像你的team中的 leader一样,必须是符合公司晋升规则的人,才能成为领导人。那么,Raft 的规则是什么呢?

  1. 当一个候选人获得了同一个任期号内的大多数选票,就成为领导人。
  2. 每个节点最多在一个任期内投出一张选票。并且按照先来先服务的原则。
  3. 一旦候选人赢得选举,立刻成为领导,并发送心跳维持权威,同时阻止新领导人的诞生。

4. 注意点

当候选人等待投票时,可能会收到“领导者” 的日志条目 RPC 请求。

怎么处理?

2 种方案。

  1. 如果“领导者”的任期号不小于候选人当前的任期号,那么候选人承认该领导人,并回归到跟随者状态。
  2. 反之,如果领导人的任期号比自己小,候选人会拒绝此次 RPC 并继续保持候选人状态。

Summary

  1. 心跳机制和超时机制触发领导人选举
  2. 选举的 2 个过程:增加任期号,转换状态,发送请求投票的 RPC 消息,有 3 种结果,可能会触发随机时间的机制。
  3. 选举规则:在同一个任期内获得大多数选票。

参考

英文 paper pdf 地址

Raft paper 中文翻译 —— 寻找一种易于理解的一致性算法(扩展版)

Raft 作者讲解视频

Raft 作者讲解视频对应的 PPT

一个简单的讲解 Raft 协议的动画

EOF