参考资料：
https://raft.github.io/
https://raft.github.io/raft.pdf
http://thesecretlivesofdata.com/raft/
https://www.cnblogs.com/linbingdong/p/6442673.html

一、Raft基础概念

1. 节点状态

节点的状态有三种：leader、follower和candidate。任何一个时刻，节点都只能处于三种状态中的一种。在正常情况下，集群中只有一个leader并且其他节点全部是follower。

不同状态下节点的行为表现：

• leader：处理所有的客户端请求；日志复制；心跳操作。
• follwer：不会发送任何情况，只是简单的响应来自leader和candidate的请求。当客户端和follower通信，follower会将请求重定向给leader。
• candidate：用来选举一个新的leader。

Raft-节点状态转移图.png

2. 节点RPC通信

Raft 算法中服务器节点之间使用 RPC 进行通信，并且基本的一致性算法只需要两种类型的 RPC：请求投票（RequestVote）RPC和追加条目（AppendEntries）RPC。

• 请求投票（RequestVote）RPC：由candidate在选举期间发起，请求follower给自己投票；
• 追加条目（AppendEntries）RPC：由leader发起，用来复制日志和提供一种心跳机制。

RequestVote RPC

RequestVote RPC.png

RequestVote RPC是被candidate调用以收集投票。

-请求参数

term：候选人的任期号
candidateId：请求投票的候选人id
lastLogIndex：候选人最新日志条目的索引值（槽位）
lastLogTerm：候选人最新日志条目对应的任期号

-返回值

term：当前任期号，用于候选人更新本地的term值
voteGranted：如果候选人得到了Follower的这张选票，则为true，否则为false

-RPC接收者实现

1）如果term < currentTerm，即RPC的第一个参数term的值小于接收方本地维护的term（currentTerm）值，则返回（currentTerm，false），以提醒调用方其term过时了，并且明确地告诉这位候选人这张选票不会投给他；否则执行步骤2。
2）如果之前没把选票投给任何人（包括自己）或者已经把选票投给当前候选人，并且候选人的日志和自己的日志一样新，则返回（term，true），表示在这个任期，选票都投给这位候选人。如果之前已经把选票投给其他人，那么很遗憾，这张选票还是不能投给他，这时就会返回（term，false）。

AppendEntries RPC

AppendEntries RPC.png

AppendEntries RPC被leader调用以复制日志条目；也被用作心跳反应。

-请求参数

term：领导人的任期号
leaderId：领导人的ID，为了其他Raft节点能够重定向客户端请求
prevLogIndex：领导人最新日志前一个位置日志的索引值
prevLogTerm：领导人最新日志前一个位置日志的任期号
entries[]：将要追加到Follower上的日志条目。发生心跳包时为空，有时为了效率而向多个节点并发发送
leaderCommit：leader服务器的commitIndex

-返回值

term：当前的任期号，即AppendEntries RPC参数中term（领导人的）与Follower本地维护的当前任期号的较大值。用于领导人更新自己的任期号。一旦领导人发现当前任期号比自己的要大，就表明自己是一个“过时”的领导人，便停止发送AppendEntries RPC，主动切换回Follower。
success：如果其他服务器包含能够匹配prevLogIndex和preLogTerm的日志，则为真

-RPC接收者实现

1）如果term<currentTerm，则领导人的任期号小于Follower本地维护的当前任期号，则返回（currentTerm，false）；否则继续步骤2。
2）如果Follower在prevLogIndex位置的日志的任期号与prevLogTerm不匹配，则返回（term，false）；否则继续步骤3。
3）Follower进行日志一致性检查。
4）添加任何在已有的日志中不存在的条目，删除多余的条目。
5）如果leaderCommit > commitIndex，则将commitIndex（Follower自己维护的本地已提交的日志条目索引值）更新为min{leaderCommit，Follower本地最新日志条目索引}。即信任Leader的数据，乐观地将本地已提交日志的索引值“跃进”到领导人为该Follower跟踪记录的那个值（除非leaderCommit比本地最新的日志条目索引值还要大）。这种场景通常发生在Follower刚从故障恢复过来的场景。

3. 选举超时时间(electionTimeout)

从上面的状态转换图中可以看到，Follower->Candidate和Candidiate->Candidate状态的转变是通过time outs来触发的，这个触发的time outs叫做选举超时时间。具体的来讲就是发生新一轮选举的超时时间，或者是Follower或Candidate状态的维持超时时间。

节点启动，初始都为Follower状态。那么问题来了，什么时候进行选举操作。在解决这个问题前，需要明确的是，选举操作是做些什么。选举操作就是节点从Follower状态变成Candidate状态，然后处于Candidate状态的节点向其他的节点发送请求投票RPC，请求其他的节点将它投为Leader。所以，这里第一步就是节点状态需要从Follower状态转化成Candidate状态，而这个转变的触发条件就是Follower节点的选举时间超时。

处于Follower状态的节点都有权进行Leader的竞争，也就是说都可能从Follower变成Candidate，多个Follower同时成为Candidate，这样就会出现竞争成为Leader的情况发生。 Raft中对这种情况称作瓜分选票。为了减少瓜分选票这种情况的出现，Raft协议对这个选举超时时间的取值是这样处理的：处于Follower状态的节点的选举超时时间是从一个固定的区间（例如150-300毫秒）随机选择的。在固定的区间随机选择一个时间值，这样就可以减少多个节点的选举时间同时超时的情况发生。不过，这里要明确的是这里是减少，但是不能完全避免，因为随机选择也会获取到相同的值。

这里我们选取单Candidate的情况来说明之后选举超时时间的变化。有A、B、C三个服务器节点，启动后，节点的状态如下：

初始节点状态.png

上图中A，B，C三个节点都处于Follower状态，C节点的超时时间最短，所以C的状态最先由Follower转变成Candidate。下图是节点C由Follower变成Candidate那一刻的状态图示：

第一次节点状态转变.png

C节点由Follower状态变成Candidate状态，选举操作开始。上面C节点中的Timeout值是当它处于Follower状态时的选举超时时间，现在变成了0。现在问题就来了，处于Candidate状态的C节点内还有选举超时时间吗？当时是有的，Raft协议对于Candidate节点是这样规定的：每个candidate在开始一次选举的时候会重置一个随机的选举超时时间，然后一直等待直到选举超时。可以说，Follower中选举超时时间控制选举事件的发生，Candidate中的选举超时时间控制选举投票动作的发生。节点成为Candidate之后，就会向其他节点发送请求投票RPC请求，然后就在选举超时时间消逝之前的这段时间内（等待投票期间）等待投票结果。若选举超时，Candidate节点无法成为Leader，并且还是处于Candidate状态（后面说明状态的变化），那么新一轮的选举投票动作发生，Candidate继续发送请求投票RPC，当然在开始选举之前会重置选举超时时间。

A和B节点的选举超时时间如何变化呢？

在等待投票期间，C成为Candidate后会向其他节点发送请求投票RPC请求，处于Follower状态的节点接收到这个请求后就会对选举超时时间进行重置。可以看到，等待投票期间Follower节点选举超时时间的重置可以说是Candidate的RPC请求触发的。

除了等待投票期间，Follower节点的选举超时时间会重置外，当Candidate节点成为Leader之后，也会进行重置。当一个节点成为Leader之后，它会向其他的服务器节点发送心跳（不包含日志条目的AppendEntries RPC）来确定自己的地位并阻止新的选举。Follower节点接收到心跳消息后就会重置自己的选举超时时间。

4. 任期（term）

Leader选举开始到结束，会产生选举出Leader和未选举出Leader这两种结果。未选举出Leader包含一个时间段：选举进行时时间段；选举出Leader这种情况包含有两个时间段：选举进行时时间段和选出Leader到下一次选举开始时间段（Leader在位时间段）。进入到下一次选举，那么时间段就如此反复。

时间段.png

上图描述了选举到下一次选举的时间段图示，若将从左至右看作是时间的流逝，我们会发现时间被分割成任意长度的时间段。这些时间段就是Raft中所定义的"任期（term）"概念。

Term.png

任期是一个全局的、连续递增的的整数。每进行一次选举，任期值加1，每个节点都会记录当前的任期值（currentTerm）。

每一个服务器节点存储一个当前任期号，该编号随着时间单调递增。

那么任期在Raft协议中的具体作用是什么呢？

考虑下面的一个场景，在第一次选举过后，A成为了Leader，此时各个节点的任期值为1，即currentTerm=1。这时候A会定期地往B和C节点发送心跳反应来维持自己的地位和阻止下一次选举的发生。考虑到网络节点通信的故障A在B的选举超时时间之内，未能及时发送心跳反应，这时候B的选举超时时间过期，使得它的状态变成了Candidate，新的一次选举发生，B的任期加1，变成了2。此时会发生些什么事以及如何处理？

发生的事情如下：

• A继续向B和C发送心跳请求
• B向A和C发送请求投票RPC

如何处理呢？这时候任期的作用就体现出来了。

A向B发送心跳请求：此时B的任期已经为2，比A的任期大，表示已经进入到下一个选举周期了，A是上一任的Leader，B表示你已经无效了，我不可能接受你的请求重置我的选举超时时间了。也就是说A的任期号已经过期了。Raft协议规定如下：如果一个节点接收到一个包含过期的任期号的请求，它会直接拒绝这个请求。

B向C发送请求投票RPC：B的任期为2，C的状态为Follower，任期为1。一个新选举周期的候选人发送投票请求，作为Follower的节点会接受此请求，并且会更新自己的任期为当前的任期。Raft协议规定如下：如果一个服务器的当前任期号比其他的小，该服务器会将自己的任期号更新为较大的那个值。

B向A发送请求投票RPC：A作为老一届的Leader，在新的候选人面前已经是日落西山了，那么就必须接受这种变迁。Raft协议规定如下：如果一个candidate或者leader发现自己的任期号过期了，它会立即回到follower 状态。

从我们上面的时间段的图还可以看出，任期在Raft协议中也起到了逻辑时钟的作用，可以用来区分事件的发生顺序。

二、Raft算法中的状态、规则和关键特性

1. 状态

State.png

currentTerm

当前的任期号（初始启动为0，单调递增）

votedFor

当前任期获得投票的节点的candidatedId，无则为null

log[]

日志条目；每一个条目包含了应用于状态机的命令和leader接收到记录时的任期号（初始索引为1）

commitIndex

当前节点已知的、最大的、已提交的日志索引值（初始为0，单调递增）

lastApplied

当前节点最后一条被应用到状态机中的日志索引值（初始为0，单调递增）

下面的状态只在Leader节点进行维护：Leader节点中不仅需要知道自己的关于日志条目的信息，还需要了解集群中其他Follower节点的这些信息，例如，Leader节点需要了解每个Follower节点的日志复制到哪个位置，从而决定下次发送Append Entries消息中包含哪些日志记录。

nextIndex[]

记录了需要发送个每个Follower节点的下一条日志的索引值（初始为leader最后一条条目索引+1）

matchIndex[]

记录了已经复制给每个Follower节点的最大的日志索引值（初始为0，单调递增）

通过https://raft.github.io中"Raft可视化"示例程序运行截图来对这两个数组有一个初步感知：

nextIndex[] & matchIndex[].png

2. 规则

Rules for Servers.png

所有节点规则

• 如果commitIndex > lastApplied，则增加lastApplied，将log[lastApplied]应用到状态机
• 如果RPC请求或返回包含的任期T>currentTerm，则设置currentTerm = T，节点转换成follower节点。

Followers规则

• 响应candidate和leader节点的RPC请求
• 如果选举超时时间到期未从leader节点收到AppendEntries RPC请求或者未投票给candidate，则节点转换成candidate

Candidates规则

• 关于转换为candidate，开始选举：
  -# 增加currentTerm
  -# 投票给自己
  -# 重置选举计时器
  -# 发送RequestVote RPCs给其他节点
• 如果收到了大多数节点的投票，则成为leader
• 如果从一个新的leader收到AppendEntries RPC，则转变成follower
• 如果选举超时时间过期，则开始一轮新的选举

Leaders规则

• 选举完后，则发送初始的空的AppendEntries RPCs（心跳）给其他节点，定时发送以阻止新的选举产生
• 如果从客户端接收到命令，则将条目追加到本地日志，当条目应用到状态机后再回复给客户端
• 如果对于一个follower来说当前leader的最后一条日志索引值>=nextIndex，则发送从nextIndex开始的日志条目给follower。
  -# 如果成功，则更新follower对应的nextIndex和matchIndex
  -# 如果因为日志不一致导致AppendEntries失败，则减小nextIndex后重试
• 如果存在一个这样的N，N>commitIndex，大部分的match[i]>=N，并且log[N].term == currentTerm，则设置commitIndex == N。

3. 关键特性

关键特性.png

• Election Safety：在任意一个任期内，最多只有一个leader。
• Leader Append-Only：Leader从来不会覆盖或者删除自己的日志条目，只追加新的日志条目。
• Log Matching：如果不同日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也都相同。
• Leader Completeness：对于给定的任意任期号， leader都包含了之前各个任期所有被提交的日志条目。
• State Machine Safety：如果有任何的服务器节点已经应用了一个特定的日志条目到它的状态机中，那么其他服务器节点不能在同一个日志索引位置应用一条不同的指令。

三、Leader选举

关于Leader选举的流程上面介绍"选举超时时间"的时候有所涉及，此章节对于选举中涉及到的一些重要点进行描述。

1. Candidate节点

Raft协议中对Candidate节点有这样的描述：

要开始一次选举过程，follower 先增加自己的当前任期号并且转换到 candidate 状态。然后投票给自己并且并行地向集群中的其他服务器节点发送 RequestVote RPC（让其他服务器节点投票给它）。Candidate 会一直保持当前状态直到以下三件事情之一发生：(a) 它自己赢得了这次的选举（收到过半的投票），(b) 其他的服务器节点成为 leader ，(c) 一段时间之后没有任何获胜者。

根据上面的描述然后结合节点状态转换图，Candidate节点的状态转变就有下面这三种情况：

Candidate节点状态变化.png

• (a) 赢得了选举成为Leader
  当一个candidate获得集群中过半服务器节点针对同一个任期的投票，它就赢得了这次选举并成为 leader 。
• (b) 其他的服务节点成为Leader
  上面在描述 "选举超时时间" 的时候说到过，它是触发新一次选举开始的触发器，同时通过选取一定区间内的随机时间来保证很少出现选票瓜分的请求，也就是保证很少出现多个Candidate的情况，但是很少并不意味着不出现，当出现多个Candidate存在的情况下，通过投票规则的保证最终还是可以选择出一个Leader，这是这个Leader就会发送心跳反应给之前与其竞争的Candidate，那么这些Candidate就会接受结果，变成Follower状态。
• (c) 一段时间内没有任何获胜者
  在一次选举周期内没有选出Leader，那么就会进入下一次选举。也就是说Candidate状态不变进入下一个选举周期。如果存在多个Candidate，那么进入下一个选举周期，通过随机的选举超时时间设置最终还是会选出一个Leader。

2. 选举限制

Candidate发送请求投票RPC到其他节点申请投票，当存在多个Candidate的时候，对于某一个节点来说如何处理投票RPC请求呢？

Raft协议的规定是这样的：对于同一个任期，每个服务器节点只会投给一个candidate ，按照先来先服务（first-come-first-served）的原则。

也就是说虽然存在多个Candidate发送请求投票RPC，但是接收的节点按照先来先服务的原则最终也只投给一个Candidate。

但是仅仅按照这个规则，会不会有问题呢？考虑这种情况：一个 follower可能会进入不可用状态，在此期间，leader可能提交了若干的日志条目，然后这个follower可能会被选举为leader 并且用新的日志条目覆盖这些日志条目；结果，不同的状态机可能会执行不同的指令序列。

在这例子中已经缺失大部分日志条目的follower可能按照先来先服务的原则被选为了leader，而leader强制其他follower复制它的日志来到达一致性，这样就导致了日志条目缺失的问题。也就是说，leader选举在先来先服务原则的基础上要增加限制才能保证选举的安全性。

Raft协议当然对选举的安全性做了保证，这里再来看一下RequestVote RPC中的下面的两个参数：

lastLogIndex：候选人最新日志条目的索引值（槽位）
lastLogTerm：候选人最新日志条目对应的任期号

这两个参数对选举做了限制，通过这两个参数与参与选举的节点中相对应的属性进行比较来确定谁的日志更新，如果投票者自己的日志比 candidate 的还新，它会拒绝掉该投票请求。

RequestVote RPC执行了这样的限制： RPC中包含了candidate的日志信息，如果投票者自己的日志比candidate的还新，它会拒绝掉该投票请求。

Raft通过比较两份日志中最后一条日志条目的索引值和任期号来定义谁的日志比较新。如果两份日志最后条目的任期号不同，那么任期号大的日志更新。如果两份日志最后条目的任期号相同，那么日志较长的那个更新。

四、日志复制

日志复制的大致流程：Leader一旦被选举出来，就开始为客户端请求提供服务。客户端的每一个请求都包含一条将被复制状态机执行的指令。Leader把该指令作为一个新的条目追加到日志中去，然后并行的发起 AppendEntries RPC给其他的服务器，让它们复制该条目。当该条目被安全地复制（下面会介绍），leader会应用该条目到它的状态机中（状态机执行该指令）然后把执行的结果返回给客户端。如果follower崩溃或者运行缓慢，或者网络丢包，leader会不断地重试AppendEntries RPC（即使已经回复了客户端）直到所有的 follower 最终都存储了所有的日志条目。

1. 日志条目

Raft协议中每个日志条目包含三部分：

• 指令：应用到状态机的指令
• 任期号：leader收到该指令时的任期号
• 索引值：表明它在日志中的位置

日志是由顺序编号的日志条目组成，可以将日志看成是一个存储日志条目的数组。

2. 已提交的日志条目

leader创建的日志条目最终是会被应用到状态机中的，那么何时应用？Raft规定只有已提交的日志条目，才能安全地被应用到状态机中。而日志条目成为已提交的日志条目的前提是它被创建它的leader复制到了过半的服务器中。

已提交日志条目还有以下的特点：

• 所有已提交的日志条目都是持久化的并且最终会被所有可用的状态机执行；
• leader日志中该已提交的日志条目之前的所有日志条目也都会被提交，包括由其他 leader 创建的条目。

3. 与日志复制相关的属性和参数

在"Raft算法中的状态、规则和关键特性"章节和讲述RPC章节我们可以看到很多关于日志相关的属性和参数，比如说commitIndex、nextIndex[]等等。这些属性和参数跟日志的复制息息相关，这个小节再重点梳理一下这些属性和参数。

log[]

所有节点都具有的数据结构，用于存储日志条目。leader从客户端获取到指令，创建相对应的日志条目，真实的leader实现中就需要有一个数据结构来存储这些日志条目，log[]数组就是这样的数据结构。同样，leader将日志条目复制给其他的follower节点，follower节点同样用log[]这样的数据结构来存储从leader节点复制过来的日志条目。

commitIndex

上面在讲到已提交日志条目的时候说到过，只有已提交的日志条目才能被安全地应用到状态机中，那么这个commitIndex不论是在leader还是在followers中都是用来记录已提交的日志条目的最大索引。

lastApplied

节点将已提交的日志条目应用到状态机中，假如此时已记录了commitIndex，但是此时节点崩溃了，那么已提交的日志条目就并没有真正的应用到状态机中，那么怎么知道真实应用到状态机的日志是哪些呢？那么就需要lastApplied这个属性的协助，这个属性记录了最后一条应用到状态机中的日志条目的索引值，此索引值和索引值之前的所有日志条目都是已经应用到状态机中的。那么像日志已提交，但是还未真正应用的情景，lastApplied就会与commitIndex不同，commitIndex就会比lastApplied大，也就是说lastApplied+1 到 commintIndex这个编号区间的日志条目都没有应用到状态机，所以当commitIndex > lastApplied时，就将lastApplied做加1处理，然后将新的lastApplied对应的日志条目应用到状态机，重复处理直到lastApplied与commitIndex相等。

nextIndex[] 和 matchIndex[]

所有的客户端指令都由leader直接或间接处理。leader负责将客户端接收的指令包装成日志条目，除了存储到本地日志中，还需要将这些日志条目复制给其他的节点。那么leader节点就需要知道follower节点日志复制情况，比如说要了解每个follower节点的日志复制到哪个位置了，了解这个那么就可以决定下次发送Append Entreis消息中包含哪些日志记录。

leader节点维护了nextIndex[]和matchIndex[]两个数组来记录follower节点日志条目复制的相关信息，这两个数组中记录的都是索引值。nextIndex[]根据我们上面的描述已经知道记录的是需要发送给每个Follower节点的下一条日志的索引值。那么matchIndex[]是其什么作用呢？

思考一下，leader发送日志复制请求给follower节点，能一定保证复制成功吗？或者说是怎么样判断复制是否成功了？不能保证复制一样成功，比如说follower节点崩溃或者运行缓慢，或者网络丢包，这样follower节点是没有成功响应复制请求的，当然了leader节点会不断地发送重试 AppendEntries RPC（即使已经回复了客户端）直到所有的follower最终都存储了所有的日志条目。除了这个，leader节点当然需要知晓到底哪些日志是成功被复制了，matchIndex[]正是用于记录这个信息。matchIndex[]记录了已经复制给每个follower节点的最大的日志索引值。

这里简单看一下leader节点和某一个follower节点复制日志时，对应nextIndex和matchIndex值的变化：follower节点中最后一个日志的索引值大于等于该follower节点对应的nextIndex值，那么Append Entries消息发送从nextIndex开始的所有日志。之后，leader节点会检测该follower节点返回的相应响应，如果成功则更新相应该follower节点对应的nextIndex值和matchIndex值；如果因为日志不一致而失败，则减少nextIndex值重试。

要使得 follower的日志跟自己一致，leader 必须找到两者达成一致的最大的日志条目（索引最大），删除 follower日志中从那个点之后的所有日志条目，并且将自己从那个点之后的所有日志条目发送给follower 。所有的这些操作都发生在对AppendEntries RPCs 中一致性检查的回复中。Leader针对每一个follower都维护了一个nextIndex ，表示leader要发送给 follower 的下一个日志条目的索引。当选出一个新leader时，该leader将所有nextIndex的值都初始化为自己最后一个日志条目的index加1。如果follower的日志和leader的不一致，那么下一次AppendEntries RPC 中的一致性检查就会失败。在被follower拒绝之后，leader就会减小 nextIndex值并重试AppendEntries RPC 。最终nextIndex会在某个位置使得leader和follower 的日志达成一致。此时，AppendEntries RPC 就会成功，将follower中跟leader冲突的日志条目全部删除然后追加leader中的日志条目（如果有需要追加的日志条目的话）。一旦AppendEntries RPC成功，follower的日志就和leader一致，并且在该任期接下来的时间里保持一致。

AppendEntries RPC - prevLogIndex、prevLogTerm、entries[]和leaderCommit

- entries[]

这个参数存储的是将要追加到Follower上的日志条目。

- prevLogIndex和prevLogTerm

prevLogIndex表示的是leader所认为的follower与leader保持一致的最后一个日志index。prevLogTerm是与prevLogIndex对应的term。

而leader对这两个参数取值是：

prevLogIndex：领导人最新日志前一个位置日志的索引值
prevLogTerm：领导人最新日志前一个位置日志的任期号

根据上面的描述我们就可以知道，leader传递这个两个参数用来给follower端检查日志是否一致。

关于这两个参数，AppendEntries RPC的接收方实现中有这样的描述：

Reply false if log doesn't contain an entry at preLogIndex whose term matches prefLogTerm

也就是接收方有这样的一个逻辑：

if (log[preLogIndex].term == preLogTerm)
    return true;
else
    return false;

- leaderCommit

主节点的CommitIndex。

对于这个参数的作用，AppendEntries RPC的接收方实现中有这样的描述：

If leaderCommit > commitIndex, set commitIndex = min(leaderCommit, index of last new entry)

4. 日志复制流程

1）客户端向Leader发送写请求。
2）Leader将写请求解析成操作指令追加到本地日志文件中。
3）Leader为每个Follower广播AppendEntries RPC。
4）Follower通过一致性检查，选择从哪个位置开始追加Leader的日志条目。
5）一旦日志项提交成功，Leader就将该日志条目对应的指令应用（apply）到本地状态机，并向客户端返回操作结果。
6）Leader后续通过AppendEntries RPC将已经成功（在大多数节点上）提交的日志项告知Follower。
7）Follower收到提交的日志项之后，将其应用到本地状态机。

五、Raft协议Java版实现

https://github.com/sofastack/sofa-jraft
https://github.com/hazelcast/hazelcast/tree/master/hazelcast/src/main/java/com/hazelcast/cp/internal/raft