一致性算法——Raft

Raft角色

任期/term

皿煮社会领导一般都是有一定任职期限，任命到期后要重新再次选举，Raft算法中的领导者也是有任期的，每个任期有单调递增的数字作为任期编号，任期编号随着选举的举行而变化
1 当跟随者等待领导者心跳超时，会选举自己当前候选人，会增加自己的任期编号。
2候选者节点的 Term 大于自己的 Term，且自己尚未投票给其它节点，则接受请求，把票投给候选者；并且term加1。
任期编号的大小会影响领导者的选举和日志请求的处理：
1如果一个候选人或者领导者发现自己的任期编号比其他节点小，那么它会立即变成跟随者状态。任期为1的领导出现宕机或者网络延时，这期间通过选举出现了任期编号为2的领导，等分区故障修复了，任期id是1的领导会收到任期id是2的心跳消息时，那么任期编号是1的领导会变成追随者角色。
2如果一个节点收到一个包含较小的任期编号的值，它会直接拒绝这个请求。

随机超时机制

在Raft算法中，随机超时时间会出现在2个很重要的地方：
1每个追随者监听领导者的心跳超时的时间间隔是随机的，尽量不会发生多个候选者的情况。
2 当没有候选者赢了半数以上的选票时，选举无效了需要等待选举超时，这个超时等待的时间间隔也是随机的

选举过程/Leader election

Raft 算法是通过一切以领导者为准的方式，实现看了一系列值的共识和各节点日志的一致。raft重要的就是选领导，一个应用 Raft 协议的集群在刚启动时，所有节点的状态都是 Follower，由于没有 Leader，Followers 无法与 Leader 保持心跳（Heart Beat），因此，Followers 会认为 Leader 已经 down，进而转为 Candidate 状态。然后，Candidate 将向集群中其它节点请求投票，同意自己升级为 Leader，如果 Candidate 收到超过半数节点的投票（N/2 + 1），它将获胜成为 Leader。

初始状态Follower

一个应用 Raft 协议的集群在刚启动时，所有节点的状态都是 Follower，初始 Term（任期）为 0，为了避免同时发起选举，Raft算法实现了随机超时机制，也就是每个节点的等待领导者心跳的节点的心跳信息的超时时间间隔是随机不一样的，时间都在 100-500 毫秒之间且并不一致。

发起投票

等待时间最短的foller会最先转为 Candidate 状态，开始发起投票。它会将自己的Term 自增，并给自己投一票，并向集群中所有节点发送RPC投票请求选它当领导并且重置选举定时器。

投票策略

节点收到候选者投票请求后会根据以下情况决定是否接受投票请求：

1. 候选者节点的 Term 大于自己的 Term，且自己尚未投票给其它节点，则接受请求，把票投给候选者；并且term加1
2. 候选者节点的 Term 小于自己的 Term，且自己尚未投票，则拒绝请求，将票投给自己。
3. 选举期间，一个追随者只能对一个候选者投一张票，投完了就不能再投了。而且是按照先来的候选者只要器任期大于自己就投给他。
4. 任期编号相同时，日志完整性高的追随者拒绝投票给日志完整性低的候选者，日志完整性指的的是每个日志会带着当前领导者的任期编号。

Candidate 转为 Leader

如果候选人在选举超时时间内获取到了一半以上的选票，就成为本届任期的领导者，当选领导者后，周期性的开始发送心跳数据

复制日志/Log replication

在一个 Raft 集群中只有 Leader 节点能够处理客户端的请求（如果客户端的请求发到了 Follower，Follower 将会把请求重定向到 Leader），客户端的每一个请求都包含一条被复制状态机执行的指令。Leader 把这条指令作为一条新的日志条目（entry）附加到日志中去，然后并行的将附加条目发送给 Followers，让它们复制这条日志条目。当这条日志条目被 Followers 安全的复制，Leader 会应用这条日志条目到它的状态机中，然后把执行的结果返回给客户端。如果 Follower 崩溃或者运行缓慢，再或者网络丢包，Leader 会不断的重复尝试附加日志条目（尽管已经回复了客户端）直到所有的 Follower 都最终存储了所有的日志条目，确保强一致性。
raft中所有的副本数据是以日志形成存在的，日志是由日志项组成的，日志项本质上就是一种数据结构，它包含以下数据信息
1 指令command 客户端请求的数据指令
2 索引项 标示日志位置信息，是一个连续单调递增的整数
3 任期编号 创建这条日志的领导者任期编号

阶段1客户端请求提交到 Leader

Leader 收到客户端的请求：如存储一个数据5；Leader 收到请求后，会将它作为日志条目（entry）写入本地日志中。需要注意的是，此时该 entry 的状态是未提交（uncommitted），Leader 并不会更新本地数据，因此它是不可读的。

阶段2：Leader 将entry发送到其它 Follower

Leader 与 Floolwers 之间保持者心跳联系，随心跳 Leader 将追加的 entry（AppendEntries）并行的发送到其它的 Follower，并让它们复制这条日志条目，这一过程称为复制（replicate）。有几点需要注意：

AppendEntries

Leader 向 Follower 发送的 entry 是 AppendEntries 因为 Leader 与 Follower 的心跳是周期性的，而一个周期间 Leader 可能接收到多条客户端的请求，因此，随心跳向 Followers 发送的大概率是多个 entry，即 AppendEntries。

PrevLogIndex&PreLogTerm

在发送追加日志条目的时候，Leader 会把新的日志条目紧接着前一条的日志条目的索引位置（prevLogIndex）和 Leader 任期号（preLogterm）包含在里面。如果领导者将索引值为8的日志项发送给跟随者，前一条日志就是索引值为的7的，那么PrevLogEntry 值为 7。 PrevLogTerm 值为 4

Leader 与 Follower 一致性

如果 Follower 在它的日志中找不到包含相同索引位置和任期号的条目，那么它就会拒绝接收新的日志条目，因为出现这种情况说明 Follower 和Leader 是不一致的。
1. 如果领导者将索引值为8的日志项发送给跟随者，这个消息的 PrevLogEntry值为7，PrevLogTerm 值为 4。
2. 如果跟随者在它的日志中，找不到与 PrevLogEntry 值为 7、PrevLogTerm 值为4的日志项，也就是说它的日志和领导者的不一致了，那么跟随者就会拒绝接收新的日志项， 并返回失败信息给领导者。
3. 领导者会递减要复制的日志项的索引值，并发送新的日志项到跟随者，此时的 PrevLogEntry 值为6，PrevLogTerm值为 3。
4. 如果跟随者在它的日志中，找到了 PrevLogEntry 值为 6、PrevLogTerm 值为3的日志项，那么日志复制 RPC 返回成功，领导者就知道在 PrevLogEntry 值为 6、 PrevLogTerm 值为 3 的位置，跟随者的日志项与自己相同。
5. 领导者通过日志复制 RPC，复制并更新覆盖该索引值之后的日志项（也就是不一致的日志项），最终实现了集群各节点日志的一致。

阶段3Leader 等待 Followers 回应

Followers 接收到 Leader 发来的复制请求后，有两种可能的回应：

1. 写入本地日志中，返回 Success；
2. 一致性检查失败，拒绝写入，返回 false，原因和解决办法上面已经详细说明。

需要注意的是，此时该 entry 的状态也是未提交（uncommitted）。完成上述步骤后，Followers 会向 Leader 发出回应 - success，当 Leader 收到大多数 Followers 的回应后，会将第一阶段写入的 entry 标记为提交状态（committed），并把这条日志条目应用到它的状态机中。

阶段4Leader 回应客户端

完成前三个阶段后，Leader 会回应客户端 -OK，写操作成功。

阶段5通知 Followers entry 已提交

Leader 回应客户端后，将随着下一个心跳通知 Followers，Followers 收到通知后也会将 entry 标记为提交状态。至此，Raft 集群超过半数节点已经达到一致状态，可以确保强一致性。需要注意的是，由于网络、性能、故障等各种原因导致 “反应慢” 、“不一致” 等问题的节点，也会最终与 Leader 达成一致。

安全机制

一个 Follower 可能处于不可用状态，同时 Leader 已经提交了若干的日志条目；然后这个 Follower 恢复（尚未与 Leader 达成一致）而 Leader 故障；如果该 Follower 被选举为 Leader 并且覆盖这些日志条目，就会出现问题：不同的状态机执行不同的指令序列。
鉴于此，在 Leader 选举的时候需增加一些限制来完善 Raft 算法。这些限制可保证任何的 Leader 对于给定的任期号（Term），都拥有之前任期的所有被提交的日志条目（所谓 Leader 的完整特性）。关于这一选举时的限制，下文将详细说明。

选举限制

对于所有基于 Leader 机制的一致性算法，Leader 都必须存储所有已经提交的日志条目。为了保障这一点，Raft 使用了一种简单而有效的方法，以保证所有之前的任期号中已经提交的日志条目在选举的时候都会出现在新的 Leader 中。换言之，日志条目的传送是单向的，只从 Leader 传给 Follower，并且 Leader 从不会覆盖自身本地日志中已经存在的条目。
Raft 使用投票的方式来阻止一个 Candidate 赢得选举除非这个 Candidate 包含了所有已经提交的日志条目。Candidate 为了赢得选举必须联系集群中的大部分节点，这意味着每一个已经提交的日志条目在这些服务器节点中肯定存在于至少一个节点上。如果 Candidate 的日志至少和大多数的服务器节点一样新（这个新的定义会在下面讨论），那么它一定持有了所有已经提交的日志条目（多数派的思想）。投票请求的限制： 请求中包含了 Candidate 的日志信息，然后投票人会拒绝那些日志没有自己新的投票请求。
Raft 通过比较两份日志中最后一条日志条目的索引值和任期号确定谁的日志比较新。如果两份日志最后的条目的任期号不同，那么任期号大的日志更加新。如果两份日志最后的条目任期号相同，那么日志比较长的那个就更加新。

提交之前任期内的日志条目

如同 4.1 节介绍的那样，Leader 知道一条当前任期内的日志记录是可以被提交的，只要它被复制到了大多数的 Follower 上（多数派的思想）。如果一个 Leader 在提交日志条目之前崩溃了，继任的 Leader 会继续尝试复制这条日志记录。然而，一个 Leader 并不能断定一个之前任期里的日志条目被保存到大多数 Follower 上就一定已经提交了。这很明显，从日志复制的过程可以看出。
鉴于上述情况，Raft 算法不会通过计算副本数目的方式去提交一个之前任期内的日志条目。只有 Leader 当前任期里的日志条目通过计算副本数目可以被提交；一旦当前任期的日志条目以这种方式被提交，那么由于日志匹配特性，之前的日志条目也都会被间接的提交。在某些情况下，Leader 可以安全的知道一个老的日志条目是否已经被提交（只需判断该条目是否存储到所有节点上），但是 Raft 为了简化问题使用一种更加保守的方法。
当 Leader 复制之前任期里的日志时，Raft 会为所有日志保留原始的任期号, 这在提交规则上产生了额外的复杂性。但是，这种策略更加容易辨别出日志，因为它可以随着时间和日志的变化对日志维护着同一个任期编号。此外，该策略使得新 Leader 只需要发送较少日志条目。

参考

http://thesecretlivesofdata.com/raft/
https://zhuanlan.zhihu.com/p/27207160
极客时间 08 | Raft算法（二）：如何复制日志？