Raft 算法之选举篇

前面我们介绍了Raft算法，接下来会分篇讲述每一个部分，今天讲述选举的细节。



在讲述选举之前，先介绍下Raft算法基础。



一、Raft基础

1、节点角色

在Raft中，在任意时刻，服务器节点只能是以下3个角色之一：



Follower（跟随者）：系统启动时默认的角色，一般来说不参与客户端读、写请求，接受Leader发送过来的心跳追加日志，在Leader挂了之后转变为Candidate；



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、状态

上面的状态是所有节点都要保存的，并且要持久化的，即每次变更马上要写入磁盘。



上面的状态是保存在内在中，每次重启后都0开始，即不需要持久化到磁盘上。



上述只有在Leader节点才会需要保存，并且是也是保存在内存中，不需要持久化，重启后从0开始。



领导人选举发生的条件为Follower没收到Leader的心跳，具体场景一般如下：



1、系统启动时

2、Leader挂了或网络分区了



具体细节如下：

1、请求投票 RPC

由候选人发起



接收请求投票的节点响应规则如下：

如果term < currentTerm返回 false；

如果 votedFor 为空或者为 candidateId，并且候选人的日志至少和自己一样新，那么就投票给他；



候选人的日志至少和自己一样新：这里说的就比较笼统了，这里的意思是要看下各自最后1条日志，即两者的索引号和term都对的上，我们看一个实际的例子：





上面的例子从上往下假设分别为A、B、C、D、E节点，A当前为Leader，各节点日志索引如下：



B：5

C：8

D：2

E：7



如果这时候A挂了，如果D最先升级为Candidate，B、C、E收到请求后都不会为D投票，拿B来说，B发现D的最后一条日志索引为2，而自己的日志索引为8，因此拒绝B的请求。



关于选举还有其它一些规则：



如果在超过选举超时时间的情况之前都没有收到Leader的心跳，或者是Candidate请求投票的，就自己变成Candidate;



2、针对Candidate

开始选举后的动作如下：

自增当前的任期号（currentTerm）; 

给自己投票; 

重置选举超时计时器;

发送请求投票的 RPC 给其他所有服务器; 



收到响应后的规则：

如果接收到大多数服务器的选票，那么就变成Leader；

如果接收到来自新的领导人的心跳信息，则转变成Leader；

如果选举过程超时，再次发起一轮选举; 



3、针对Leader

一旦成为领导人：发送空的附加日志 RPC（心跳）给其他所有的服务器；

在一定的空余时间之后不停的重复发送，以阻止跟随者超时。