算法概述

Raft是一个易于理解的共识算法。它在容错和性能方面与Paxos相当。不同之处在于，它被分解为相对独立的子问题，并且干净地处理了实际系统所需的所有主要部分。我们希望Raft将共识提供给更广泛的用户，并且这个更广泛的用户将能够开发各种比现在可用的更高质量的基于共识的系统。
Raft是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。在这里强调了是在工程上，因为在学术理论界，最耀眼的还是大名鼎鼎的Paxos

共识算法

共识算法是指在分布式场景中，多个节点为了达成相同的数据状态而运行的一种分布式算法。 在分布式场景中，可能出现网络丢包、时钟漂移、节点宕机、节点作恶等等故障情况，共识算法需要能够容忍这些错误，保证多个节点取得相同的数据状态。这些年最为火热的加密货币（比特币、区块链）就需要共识算法，而在分布式系统中，共识算法更多用于提高系统的容错性，比如分布式存储中的复制集

根据可容忍的故障类型分

1、容忍宕机错误类算法（crash fault tolerant consensus algorithm）
可以容忍网络丢包、时钟漂移、部分节点宕机这种节点为良性的错误。常见算法有 Paxos、Raft。
2、容忍拜占庭错误类算法（byzantine fault tolerant consensus algorithm）
可以容忍部分节点任意类型错误，包括节点作恶的情况。常见算法有 PBFT、PoW、PoS等。

根据使用场景分

1、公链共识
公链的特点是节点数量多且节点分布分散，主要使用的共识算法有PoW和PoS，这两种共识的优点是可以支持的节点数量多，缺点是TPS较低和交易确认时间长。
2、联盟链共识
联盟链的特点是节点之间网络较为稳定且节点有准入要求，根据需要容忍的错误类型可以选择Raft和PBFT类算法，这类算法的优点是TPS较高且交易可以在毫秒级确认，缺点是支持的节点数量有限，通常不多于100个节点。

leader选举

名词解释

节点类型

在Raft算法中，每个网络节点只能如下三种身份之一：Leader、Follower以及Candidate

Leader（领导者）

主要负责与外界交互，由Follower节点选举而来，在每一次共识过程中有且仅有一个Leader节点，leader完全负责replicated log的管理。leader负责接受所有客户端更新请求，然后复制到follower节点

Follower（追随者）

以Leader节点为准进行同步，如果leader故障，followes会重新选举出新的leader。

Candidate（候选人）

Follower节点在竞选Leader时拥有的临时身份。候选人将向其他节点发送请求投票（RequestVote）RPC消息，通知其他节点来投票，如果赢得了大多数选票，就晋升当领导者
下图说明了这三种关系：

Followers只响应来自其他服务器的请求。如果一个Follower没有收到任何通信，它就会成为Candidate，并发起选举。从整个集群中获得多数选票的Candidate将成为新的Leader。Leaders通常会一直运作到失败为止。

任期

从上面可以看出，leader是由followers选举出来的，当集群第一次启动或者leader下线了，新的leader将从新在followers中选择，然后由新的leader继续负责。这和民主社会的选举很像，每一届新的履职期称之为一届任期，在raft协议中，也是这样的，对应的术语叫term。如果选举失败，并没有选举出新的单一Leader，则会开启新的Term，重新开始选举。

term（任期）以选举（election）开始，然后就是一段或长或短的稳定工作期（normal Operation）。从上图可以看出，任期是递增的（t1 -> t4），这就充当了逻辑时钟的作用；另外，term 3展示了一种情况，就是说没有选举出leader就结束了，这是因为集群中的出现了两个leader并且leader获取的票数相同了

任期规则

跟随者在等待领导者心跳信息超时后，推举自己为候选人时，会增加自己的任期编号，比如节点一的任期编号为0，那么在推举自己为候选人时，会将自己的任期编号增加为1
如果一个服务器节点，发现自己的任期编号比其他节点小，那么它会更新自己的任期编号到较大的编号值，比如节点B的任期编号是0，当收到来自节点A的请求投票RPC消息时，因为消息中包含了节点A的任期编号，且编号为1，那么节点B将把自己的任期编号更新为1
如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态。比如分区错误恢复后，任期编号为3的领导者节点B，收到来自新领导者的包含任期编号为4的心跳消息，那么节点B将立即恢复成跟随者状态
如果一个节点接收到一个包含较小的任期编号值的请求，那么它会直接拒绝这个请求。比如节点C的任期编号为4，收到包含任期编号为3的请求投票RPC消息，那么它将拒绝这个消息

选举规则

1、领导者周期性地向所有跟随者发送心跳消息（即不包含日志项的日志复制RPC消息），通知大家我是领导者，组织跟随者发起新的选举
2、如果在指定时间内，跟随者没有接收到来自领导者的消息，那么它就认为当前没有领导者，推举自己为候选人，发起领导者选举
3、在一次选举中，赢得大多数选票的候选人，将晋升为领导者
4、在一个任期内，领导者一直都会是领导者，直到它自身出现问题（比如宕机），或者因为网络延迟，其他节点发起一轮新的选举
5、在一次选举中，每一个服务器节点最多会对一个任期编号投出一张选票，并且按照先来先服务的原则进行投票。比如节点三的任期编号为3，先收到了一个包含任期编号为4的投票请求（来自节点一），然后又收到了一个包含任期编号为4的投票请求（来自节点二）。那么节点三将会把唯一，一张选票投给节点一，当再收到节点二的投票请求RPC消息时，对于编号为4的任期，已没有选票可投了
6、日志完整性高的跟随者（也就是最后一条日志项对应的任期编号值更大，索引号更大）拒绝投票给日志完整性低的候选人。比如节点二的任期编号为3，节点三的任期编号为4，节点二的最后一条日志项对应的任期编号为3，而节点C为2，那么当节点C请求节点B投票给自己时，节点B将拒绝投票

选举过程

假设现在机器情况如下：

步骤一：
Raft算法实现了随机超时时间的特性，每个节点等待领导者心跳信息的超时时间间隔是随机的。上图中，集群中没有领导者，而节点一的等待超时时间最小，它会最先因为没有等到领导者的心跳信息，发生超时
这时，节点一增加自己的任期编号（term），并推举自己为候选节点，先给自己投上一张选票，然后向其他节点发送请求投票RPC消息，请它们选举自己为领导者

如果其他节点接收到候选节点一的请求投票RPC消息，在编号为1的这届任期内，也还没有进行过投票，那么它将把选票投给节点一，并增加自己的任期编号

如果候选节点在选举超时时间内赢得了大多数的选票（节点总数/2 + 1），那么它就会成为本届任期内新的leader。节点一当选领导者后，它将周期性地发送心跳消息，通知其他服务器我是领导者，阻止跟随者发起新的选举

当节点数为偶数个的情况下（即下图情况），很可能出现平票 split vote的情况。这个时候大家都在等啊等，直到超时后重新发起选举。如果出现平票的情况，那么就延长了系统不可用的时间（没有leader是不能处理客户端写请求的），因此raft引入了randomized election timeouts来尽量避免平票情况。同时，leader-based 共识算法中，节点的数目都是奇数个，尽量保证majority的出现。

随机选举超时(randomized election timeouts)是什么？
Raft算法使用随机选举超时时间的方法，把超时时间都分散开来，在大多数情况下只有一个服务器节点先发起选举，而不是同时发起选举，这样就能减少因选票瓜分导致选举失败的情况
在Raft算法中，随机超时时间有2种含义：
1、跟随者等待领导者心跳信息超时的时间间隔是随机的
2、如果候选人在一个随机时间间隔内，没有赢得过半票数，那么选举就无效了，然后候选人发起新一轮的选举，也就是说，等待选举超时的时间间隔是随机的

日志复制

日志结构

副本数据是以日志的形式存在的，日志是由日志项组成，日志项是一种数据格式，它主要包含用户指定的数据，也就是指令（Command），还包含一些附加信息，比如索引值（Log index）、任期编号（Term）

• 指令（正方形中的x <- 3，y <- 1，y <- 9）：一条由客户端请求指定的、状态机需要执行的指令，可以理解成客户端指定的数据
• 索引值（最顶上的数字）：日志项对应的整数索引值，用来标识日志项的，是一个连续的、单调递增的证书号码
• 任期编号(正方形中的1，2，3)：创建这条日志项的领导者的任期编号

  复制步骤

  首先，领导者通过日志复制（AppendEntries）RPC消息，将日志项复制到集群其他节点上。如果领导者接收到大多数的复制成功响应后，它将日志项应用到它的状态机，并返回成功给客户端。如果领导者没有接收到大多数的复制成功响应，那么就返回错误给客户端
  详细步骤

1. 接收到客户端请求后，领导者基于客户端请求中的指令，创建一个新日志项，并附加到本地日志中
2. 领导者通过日志复制RPC，将新的日志复制到其他的服务器
3. 当领导者将日志项成功复制到大多数的服务器上的时候，领导者会将这条日志项应用到它的状态机中
4. 领导者将执行的结果返回给客户端
5. 当跟随者接收到心跳消息，或者新的日志复制RPC消息后，如果跟随者发现领导者已经提交了某条日志项，而它还没应用，那么跟随者就将这条日志项应用到本地的状态机上

领导者将日志项应用到它的状态机，怎么没通知跟随者应用日志项呢？
因为领导者的日志复制RPC消息或心跳消息，包含了当前最大的、将会被提交的日志项索引值。所以通过日志复制RPC消息或心跳消息，跟随者就可以知道领导者的日志提交位置信息

日志一致性

在Raft算法中，领导者通过强制跟随者直接复制自己的日志项，处理不一致日志。也就是说，Raft是通过以领导者的日志为准，来实现各节点日志的一致性的
首先，领导者通过日志复制RPC的一致性检查，找到跟随者节点上与自己相同日志项的最大索引值。也就是说，这个索引值之前的日志，领导者和跟随者是一致的，之后的日志是不一致的
然后，领导者强制跟随者更新覆盖不一致的日志项，实现日志的一致
引入2个新变量：
PrevLogEntry：表示当前要复制的日志项，前面一条日志项的索引值。比如下图中，如果领导者将索引值为8的日志项发送给跟随者，那么此时PrevLogEntry值为7
PrevLogTerm：表示当前要复制的日志项，前面一条日志项的任期编号，比如在图中，如果领导者将索引值为8的日志项发送给跟随者，那么此时PrevLogTerm值为4

1. 领导者通过日志复制RPC消息，发送当前最新日志项到跟随者，这个消息的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复制并更新覆盖该索引值之后的日志项（也就是不一致的日志项），最终实现了集群各节点日志的一致

领导者通过日志复制RPC一致性检查，找到跟随者节点上与自己相同日志项的最大索引值，然后复制并更新覆盖该索引值之后的日志项，实现了各节点日志的一致。跟随者中的不一致日志项会被领导者的日志覆盖，而且领导者从来不会覆盖或者删除自己的日志

异常检查

在任何系统模型下，都需要满足safety属性，即在任何情况下，系统都不能出现不可逆的错误，也不能向客户端返回错误的内容。比如，raft保证被复制到大多数节点的日志不会被回滚，那么就是safety属性。而raft最终会让所有节点状态一致，这属于liveness属性。

选举安全

选举安全性，即任一任期内最多一个leader被选出。这一点非常重要，在一个复制集中任何时刻只能有一个leader。系统中同时有多余一个leader，被称之为脑裂（brain split），这是非常严重的问题，会导致数据的覆盖丢失。在raft中，两点保证了这个属性：

• 一个节点某一任期内最多只能投一票；
• 只有获得多数节点投票才会成为leader。

因此，某一任期内一定只有一个leader。

日志匹配

首先，leader在某一term的任一位置只会创建一个log entry，且log entry是追加的。其次再安全检查，leader在追加的log entries中包含最新log entry之前的一个log 的term和index，如果follower在对应的term index找不到日志，那么就会告知leader不一致。比如以下情况

上图的a、b、c、d、e、f是一个follower节点的六种可能不同的状态，上图的状态分别如下：

• 比leader日志少，如上图中的ab（将缺少的数据补上）
• 比leader日志多，如上图中的cd（删除多余的数据）
• 某些位置比leader多，某些日志比leader少，如ef（删除与自己不同的数据，再将数据与自己对齐）

只要当出现了leader与follower不一致的情况，leader强制follower复制自己的log

”脑裂“问题

raft保证Election safety，即一个任期内最多只有一个leader，但在网络分割（network partition）的情况下，可能会出现两个leader，但两个leader所处的任期是不同的。如下图所示

其中 Node 1 是当前的 raft leader，当出现网络分区时，在 Node 5 的 raft lease 任期还没结束的一段时间内，Node 1 仍然认为自己是当前 term 的 leader，但是此时，另外一边分区已经在新的 term 中选出了新的 leader。

如果此时，客户端在新的 leader 上更新了某个值 x，此时是可以更新成功的（因为还是可以复制到多数派）。但是在分区的另一端，此时一个客户端去读取 x 的值，Node 5 还会返回老的值，这样就发生了 stale read。

这里引入一个新的概念, region leader。region leader 是一个逻辑上的概念, 任意时刻对于某一个 region 来说, 一定只拥有一个 region leader, 每个 region leader 在任期之内尝试每隔 t 时间间隔, 在 raft group 内部更新一下 region leader 的 lease。所有的读写请求都必须通过 region leader 完成
但是值得注意的是， region leader 和 raft leader 可能不是一个节点，当 region leader 和 raft leader 不重合的时候，region leader 会将请求转发给当前的 raft leader，当网络出现分区时，会出现以下几种情况：
情况一：
region leader 落在多数派，老 raft leader 在多数派这边
结果：
对于这种情况读写都在一个leader上（因为分区二无法产生leader，无法大于三个节点投票，而新的region leader 重新投票，因为包括自身一共三票所以获取leader角色），所以不会产生stale

情况二：
region leader 落在多数派，老 raft leader 在少数派这边
结果：
因为所有的读写请求都会找到 region leader 进行，即使在原来没有出现网络分区的情况下，客户端的请求也都是要走 node 1 ，经由 node 1 转发给 node 3，客户端不会直接访问 node 3，所以此时即使网络出现分区，新 leader 也正好在多数派这边，读写直接就打到 node 1 上，皆大欢喜，没有 stale read。

情况三：
region leader 落在少数派，老 raft leader 在多数派这边
结果：
少数派中无法选举出leader节点。此时因为老的 region leader 没办法成功的写入，所以也不会出现 stale read。但是付出的代价是在 region leader lease 期间的系统的可用性。

情况四：
region leader 落在少数派，老 raft leader 在少数派这边
结果：
少数派中无法选举出leader节点。同时整个集群变成了不可读，不可写的状态

参考文章：
http://thesecretlivesofdata.com/raft/
https://raft.github.io/raft.pdf
https://www.cnblogs.com/xybaby/p/10124083.html
https://blog.csdn.net/qq_40378034/article/details/117404484
https://www.cnblogs.com/mindwind/p/5231986.html