raft Leader 选举

raft 协议是当前分布式系统开发的首选共识算法。raft 协议是一个一切以领导者为主，实现一系列值的共识和节点日志的一致性。

raft 协议将共识问题拆分成三个子问题

1. Leader 选举，Leader 故障后集群能快速选出新 Leader；
2. 日志复制， 集群只有 Leader 能写入日志， Leader 负责复制日志到 Follower 节点，并强制 Follower 节点与自己保持相同；
3. 安全性，一个任期内集群只能产生一个 Leader、已提交的日志条目在发生 Leader 选举时，一定会存在更高任期的新 Leader 日志中、各个节点的状态机应用的任意位置的日志条目内容应一样等

首先介绍下 Raft 的 Leader 选举流程

Leader 是集群中的独裁者，当 Leader 发布 A=3 的命令时，其余的节点都将会追加最新的 A=3 的指令到自身的日志中。

因此，一个集群中只能有一个 Leader，由唯一的 Leader 发出指令。这里我将会介绍 raft 是如何在一个多节点的集群中选出 Leader 的。

成员身份

在介绍选举算法前，先介绍下集群中节点的身份有哪几种。在 raft 集群中，节点的身份有三种，分别是 Leader，Candidate 和 Follower。

• Follower: 接收和处理来自 Leader 的信息，当 Leader 的心跳超时时，成为 Candidate

• Candidate: 向其他节点发送 RequestVote 的 RPC 请求，通知其他节点投票，当得票数超过 2/3 时成为 Leader

• Leader: 负责处理写请求，管理日志的复制（AppendEntries）和不断发送心跳消息，通知其他节点 Leader 还是存活的

选举过程

首先，在初始节点，集群的所有节点都是 Follower。每个节点都有一个随机的心跳超时时间。

A: 150ms, Term:0
B: 200ms, Term:0
C: 250ms, Term:0

A 会最先因为没有等到 Leader 心跳信息而发生超时，此时，A 会将自己的任期（Term）增加 1，成为 Candidate，为自己投一票，然后向其他的节点发送 RequestVote。

B，C 收到 A 的投票请求，并且它们在没有在 Term1 投过票，那么它们就会给 A 投票，同时将自己的任期加 1.

A: 150ms, Term:1
B: 200ms, Term:1
C: 250ms, Term:1

在投票超时时间内（每次投票的超时时间也是随机的），A 获得了半数的投票，A 成为了本届任期的新 Leader。并向其他节点发送心跳消息。

什么是任期

raft 将时间划分成一个个任期，任期用连续的整数表示，每个任期从一次选举开始，赢得选举的节点在该任期内充当 Leader 的职责，随着时间的消逝，集群可能会发生新的选举，任期号也会单调递增。

通过任期号，可以比较各个节点的数据新旧、识别过期的 Leader 等，它在 Raft 算法中充当逻辑时钟，发挥着重要作用。

Follower 在等待 Leader 心跳信息超时后，推举自己为 Candidate 时，会增加自己的任期号，比如节点 A 的当前任期编号为 0，那么在推举自己为候选人时，会将自己的任期编号增加为 1。

如果一个服务器节点，发现自己的任期编号比其他节点小，那么它会更新自己的编号到较大的编号值。

在 raft 中，如果 Candidate 或者 Leader 发现自己的任期小于其他节点（任期过期），那么就会立刻恢复成 Follower。

如果一个节点接受到了一个任期值较低的请求，那么就会直接拒绝这个请求。

选举的规则

1. 在一次选举中，每一个服务器节点最多会对一个任期编号投出一张选票，并且按照“先来先服务”的原则进行投票。
2. 日志完整性高的 Follower（也就是最后一条日志项对应的任期编号值更大，索引号更大），拒绝投票给日志完整性低的 Candidate

raft 的日志格式如下

索引：  1   2   3   4
任期：| 1 | 1 | 2 | 3 |
指令：|x=1|y=2|x=2|z=4|