Raft 共识算法学习笔记 一：领导者选举
Raft 算法是现在分布式系统开发首选的共识算法。文章 《图解 Paxos 算法》 介绍了 Paxos 共识算法，绝大多数选用 Paxos 算法的系统（比如 Cubby），都是在 Raft 算法发布前开发的，当时没得选。新系统绝大多数选择了 Raft 算法，例如，Etcd，Consul，等。就像作者 Diego Ongaro 在 Raft 论文 In Search of an Understandable Consensus Algorithm 说的，Paxos 太难理解了，无论是对于学生还是系统开发者来说，因此 Diego Ongaro 提出了易于理解和实现的 Raft 算法。
本文讲述 Raft 算法如何进行领导者选举。
节点状态
在 Raft 中，节点有以下三种状态：
- leader（领导者）：接收 client （客户端）的所有请求，霸道总裁，一切以我为准。领导者平常的工作包括 3 个部分：处理写请求，管理日志复制，不断发送心跳信息通知其他节点”我是领导者，我还活者，你们现在不要发起新的选举“。Raft 保证任何时刻只有一个 leader
- follower（跟随者）：相当于普通群众，被动接收和处理来自领导者的消息。当领导者心跳超时时，就主动站出来，推荐自己当选候选人
- candidate（候选人）：用于选举出一个新的 leader。候选人向其他节点发送投票 （RequestVote，参考下文 Raft RPX 通信的描述）RPC 消息，通知其他节点来投票，如果赢得子大多数选票，就升级为领导者
节点状态转换示意图如下图所示：
任期
Raft 将时间划分为一个一个的任期（term），每个任期由单调递增的数字（任期编号）标识，例如，节点 A 的任期编号为 1。任期编号随着选举的举行变化而变化，即每个任期始于一个新的选举。
任期变化的示意图如下图所示：
从上图可以看出，任期一般包含两阶段，第一阶段是选举阶段，第二阶段为已选举出领导者的阶段。但任期也可能只包含选举阶段。可以看到 任期 3 由于并没有成功选举出领导者（即论文所说的 a split vote，两个节点同时成为候选人同时发起选举，导致无法成功选出领导者），只包含了选举阶段。接下来马上进入 任期 4，接着进行新一轮的选举。
Raft 保证在一任期内，最多只有一个领导者。
Raft 任期具有如下特点：
- 跟随者在等待领导者心跳消息超时后，推举自己为候选人时，会增加自己的任期编号，比如节点 A 的当前任期编号为 0，那么在推举自己为候选人时，会将自己的任期编号增加为 1
- 如果一个节点，发现自己的任期编号比其他节点小，那么它会更新自己的编号到较大的编号值。比如，节点 B 的任期编号为 0，当收到来自节点 A 的请求投票 RPC 消息，消息中包含节点的任期编号为 1，那么节点 B 将把自己的任期编号更新为 1
- 如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态（可以参考上面的节点状态转换示意图）。比如网络分区错误，导致出现两个领导者，当分区错误恢复后，任期编号为 3 的领导者 B 接收到领导者 A 任期编号为 4 的心跳消息，那么节点 B 将立即恢复成跟随着状态，接受节点 A 为领导者
- 如果一个节点接收到一个包含较小任期编号值的请求，那么它会直接拒绝这个请求。例如，节点 C 的任期编号为 4，接收到任期编号为 3 的 RPC 消息，那么节点 C 将拒绝这个消息
领导者选举
以三个节点的集群为例，说明 Raft 如何进行领导者的选举。
初始状态下，所有节点都是跟随者状态：
Raft 实现了随机超时时间的特性，上图可以看到，每个跟随者的等待超时时间是随机的。节点 A 跟随者等待超时时间最短为 150 ms，会最先发生超时，变成候选人。有关 Raft 超时时间的特性，下文会进行更详细的说明。
开始新的一轮选举后，节点 A 同时也增加自己的任期编号为 1，推举自己为候选人，并给自己投上一票，然后向其他节点发送请求投票 RPC 消息，请它们选举自己为领导者：
其他节点接收到候选人 A 的请求投票 RPC 消息，由于在任期编号为 1 的任期内，没有进行过投票，故都将选票投票给 A，同时更新自己的任期编号为 1:
候选人 A 在选举超时时间内赢得了大多数的选票，那么它将会成为本届任期内新的领导者：
节点 A 成为领导者后，会周期性地向其他跟随者发送心跳消息，通知其他节点我是领导者，以防止其他节点发起新的选举篡权：
选举规则
为了顺利选举出领导者，Raft 约定了选举规则：
- 领导者周期性地向所有跟随者发送心跳消息（心跳超时时间），用于通知大家我是领导者，阻止跟随者发起新的选举
- 如果在指定的时间内（选举超时时间），跟随者没有接收到领导者的消息，那么它就认为当前没有领导者，推举自己为候选人，发起新的选举
- 在一次选举中，赢得大多数选票的候选人，将晋升为领导者
- 在一个任期内，领导者会一直都是领导者，直到自身出现问题（例如节点宕机），或者出现网络延迟，其他节点发起新的一轮选举
- 在一次选举中，每个节点最多只能对一个任期编号投出一张选票，并按照先来先服务的原则进行投票。比如节点 C 的任期编号为 3，先收到节点 A 的投票请求，节点 A 的任期编号为 4；然后又接收到节点 B 的投票请求，节点 B 的任期编号为 4。那么，节点 C 会将任期 4 的唯一一张选票投给节点 A，当节点 C 再接收到节点 B 的投票请求时，节点 C 已经没有任期 4 的选票了
- 日志完整性高的跟随者（即，最后一条日志项对应的任期编号更高，索引号更大），拒绝投票给日志完整性低的候选人。例如，节点 B 的任期编号为 3，节点 C 的任期编号为 4，节点 B 最后一条日志项对应的任期编号为 3，节点 C 最后一条日志项对应的任期编号为 2。那么，当节点 C 请求节点 B 投票给自己时，节点 B 将拒绝投票。有关 Raft 日志的细节，可以参考 《Raft 共识算法学习笔记 二：日志复制》
节点通信
在 Raft，节点之间采用 RPC 进行通信，且包含两类 RPC：
- RequestVote RPC：请求投票 RPC，候选人在选举期间发起，用于通知其他节点投票
- AppendEntries RPC：日志复制 RPC，由领导者发起，用于复制日志和提供心跳消息。其中，心跳消息即为不包含日志项的日志复制 RPC 消息
超时时间
在选举中，可能会出现这种情况：在同一个任期内，多个候选人同时发起选举，选票被瓜分，导致没有一个候选人获得大多数的选票成为领导者，选举失败，即出现所谓的 a split vote。
为了降低出现 a split vote 的概率，Raft 引入了随机超时时间的方法，把超时时间分散开来，大多数情况下只有一个节点发起选举，避免同时发起选举的情况出现。在 Raft 中，包含两种超时时间：
- election timeout: 选举超时时间，跟随者等待成为候选人的超时时间，即跟随者在一段时间内没有接收到任何消息，那么它就假定集群内没有领导者，并开始新一轮的选举。选举超时时间为随机值 150 ~ 300 ms
- heartbeat timeout: 心跳超时时间，领导者发送心跳的时间间隔
Raft 算法以领导者为中心，选举出领导者后，一切以领导者为准，以达成值的共识，实现各节点日志的一致。下一篇文章讲述 Raft 日志复制的有关内容。