Raft算法之选举篇
前面我们介绍了Raft算法，接下来会分篇讲述每一个部分，今天讲述选举的细节。
在讲述选举之前，先介绍下Raft算法基础。
一、Raft基础
1、节点角色
在Raft中，在任意时刻，服务器节点只能是以下3个角色之一：
Follower（跟随者）：系统启动时默认的角色，一般来说不参与客户端读、写请求，接受Leader发送过来的心跳追加日志，在Leader挂了之后转变为Candidate；
Candidate（候选人）：如果当前没有Leader，Follower就转变为这个角色，这个角色会向其它节点发起投票请求，如果多数节点同意投票，则晋升为Leader；
Leader（领导人）：接受客户端的读、写请求，协调整个日志的持久化和推进；
下面讲节点角色时统一用英文描述。
2、节点角色状态迁移图
系统启动时，大家都是Follower，然后启动定时器，如果在指定时间没有收到Leader的心跳，则将自己变成Candidate，然后向其它成员发起投票请求，如果收到过半以上成员的投票则Candidate晋升为Leader；
Leader发送心跳给其它成员时如果收到的响应中term比自己的大，则退化成Follower；
3、逻辑时钟(term)
选举过程有个term参数，这个参数就是逻辑时钟，这是一个整数，全局递增；Raft 把时间分割成任意长度的任期，用term来标识每一届leader的任期，这样可以保证在一个任期内只有一个Leader。
逻辑时钟规则如下：
Candidate发起选举时就将自己的term加1，然后发起投票请求；
收到投票请求的节点比较请求的term和自己的term，如果请求的term比自己的大，则更新自己的term；
这样在即使每个节点的时间不一样的情况下也可以推进逻辑时钟；
4、状态
状态 | 所有服务器上持久存在的 |
|---|---|
currentTerm | 服务器最后一次知道的任期号（初始化为 0，持续递增） |
votedFor | 在当前获得选票的候选人的 Id |
log[] | 日志条目集；每一个条目包含一个用户状态机执行的指令，和收到时的任期号 |
上面的状态是所有节点都要保存的，并且要持久化的，即每次变更马上要写入磁盘。
状态 | 所有服务器上经常变的 |
|---|---|
commitIndex | 已知的最大的已经被提交的日志条目的索引值 |
lastApplied | 最后被应用到状态机的日志条目索引值（初始化为 0，持续递增） |
上面的状态是保存在内在中，每次重启后都0开始，即不需要持久化到磁盘上。
状态 | 在领导人里经常改变的 （选举后重新初始化） |
|---|---|
nextIndex[] | 对于每一个服务器，需要发送给他的下一个日志条目的索引值（初始化为领导人最后索引值加一） |
matchIndex[] | 对于每一个服务器，已经复制给他的日志的最高索引值 |
上述只有在Leader节点才会需要保存，并且是也是保存在内存中，不需要持久化，重启后从0开始。
二、领导人选举
领导人选举发生的条件为Follower没收到Leader的心跳，具体场景一般如下：
1、系统启动时
2、Leader挂了或网络分区了
具体细节如下：
1、请求投票 RPC
由候选人发起
参数 | 解释 |
|---|---|
term | 候选人的任期号 |
candidateId | 请求选票的候选人的 Id |
lastLogIndex | 候选人的最后日志条目的索引值 |
lastLogTerm | 候选人最后日志条目的任期号 |
返回值
返回值 | 解释 |
|---|---|
term | 当前任期号，以便于候选人去更新自己的任期号 |
voteGranted | 候选人赢得了此张选票时为真 |
接收请求投票的节点响应规则如下：
- 如果term < currentTerm返回 false；
- 如果 votedFor 为空或者为 candidateId，并且候选人的日志至少和自己一样新，那么就投票给他；
第1条规则好理解，第2条规则前面部分是为了保证在一个任期内每个节点只投1票，前面也说过这个信息是要持久化的；
候选人的日志至少和自己一样新：这里说的就比较笼统了，这里的意思是要看下各自最后1条日志，即两者的索引号和term都对的上，我们看一个实际的例子：
上面的例子从上往下假设分别为A、B、C、D、E节点，A当前为Leader，各节点日志索引如下：
A：8
B：5
C：8
D：2
E：7
如果这时候A挂了，如果D最先升级为Candidate，B、C、E收到请求后都不会为D投票，拿B来说，B发现D的最后一条日志索引为2，而自己的日志索引为8，因此拒绝B的请求。
关于选举还有其它一些规则：
1、针对Follower
如果在超过选举超时时间的情况之前都没有收到Leader的心跳，或者是Candidate请求投票的，就自己变成Candidate;
2、针对Candidate
开始选举后的动作如下：
自增当前的任期号（currentTerm）;
给自己投票;
重置选举超时计时器;
发送请求投票的 RPC 给其他所有服务器;
收到响应后的规则：
如果接收到大多数服务器的选票，那么就变成Leader；
如果接收到来自新的领导人的心跳信息，则转变成Leader；
如果选举过程超时，再次发起一轮选举;
3、针对Leader
一旦成为领导人：发送空的附加日志 RPC（心跳）给其他所有的服务器；
在一定的空余时间之后不停的重复发送，以阻止跟随者超时。