共识算法
Raft 是一种共识算法，共识算法是一种在分布式系统中非常重要的算法，他允许在一个节点集合中，即使某些节点挂了，对外的服务仍然还是一致的。
最经典的模型是拜占庭问题，假设现在有几个将军和他们的军队围攻一个城市，这些将军必须通过传令兵来通信。他们需要对攻击还是撤退达成一致的决定，只有半数以上的军队进行进攻才能胜利。然而，通信可能不可靠，且可能有少数叛徒将军（少于一半）传递错误信息。问题在于，如何确保忠诚的将军们能够达成一致的决策，即使在这些不确定和不可信的情况下。只要忠诚的将军达成一致的进攻决策，这个任务就能成功。
Raft 就是一种用来解决分布式系统共识问题的共识算法。Raft 本质上是 Paxso 的子集，但是由于 Paxso 过于复杂，导致应用困难。Raft 的提出的主要目的就是为了简化，使共识算法以一种更易理解的方式实现。
一个官方可互动的网页和相关资料： https://raft.github.io/
Raft 基本概念
Raft 的核心概念在于 Leader 选举和 replicated log 机制。我们假设将集群内的每个节点看作是一个单独的状态机，问题就转化为如何保证每个状态机的状态相同。我们进一步假设，状态机执行的指令是具有确定性，也就是说只要给定一个确定的输入，输出就一定也是确定的。在这种假设下，只要每个节点执行的指令是相同的，那么他们的状态就一定能保持一致。
通常来说确定性的指令有算术运算，例如加减乘除，在输入确定的情况下，输出一定相同。非确定的指令有获取当前时间、随机数生成等等，如何处理非确定的指令会在后续提到。
那么如何让每个节点所执行的指令是一致的呢？这就引出了 replicated log，这部分的 log 中记录的是所有节点所要执行的命令。也就是说每个节点要先获得一个 log 文件，随后再根据 log 文件中的指令执行。那么为了保证 replicated log 的一致性，也就是所有节点中的 log 都是一样的，Raft 提出了 Leader。所有 log 必须通过 Leader 进行复制，也就是所有节点所执行指令的顺序是由 Leader 决定的，这也就是确定了所有状态机的一致性。
简单做一个 Raft 的流程总结：
- 选取一个 Leader
- Leader 决定指令执行顺序
- Leader 将 log 复制到其他节点上
- 执行指令
每个节点存在三种状态：
- Leader：作为集群中的 Leader，负责处理响应来自客户端的请求
- Candidate：想要竞选为 Leader，是一种中间状态，当 Leader 宕机后一些 Follower 节点会变为 Candidate 节点，当 Leader 确定后，只有一个 Candidate 节点会变为 Leader，其他则变回 Follower
- Follower：跟随者，不会发出任何请求，只会响应来自 Leader 和 Candidate 的请求，如果收到来自客户端的请求，则会转发给 Leader
所以从宏观来看，所有客户端请求都是交给 Leader 的，在并发请求中，最终由 Leader 决定执行顺序，并强制所有 Follower 按照该顺序执行，来保证一致性。
以上前提是当 Leader 是可靠且只有一个的时候，整个系统的确能保证一致性，但是如果 Leader 不可靠呢，有没有可能有多个节点都认为自己是 Leader？
假设这样一个情况，一个 Leader 产生网络错误，和其他节点断开连接，这时候其他节点已经选举出了一个新 Leader，此时旧 Leader 网络恢复。这个时候就出现了两个 Leader，该怎么协调？
为了解决多 Leader 问题，提出了 term 任期的概念，本质上是一种逻辑时钟，能够使节点判断自身状态是否落后。在 Raft 中，每一次 Leader 选举都会使 term 号递增，只有最新 term 号的 Leader 才有权力对其他节点进行管控。
Leader 选举
为了方便，我们假设集群一共有五个节点，Raft 要求节点数是奇数，如果是偶数的话有可能出现平票，无法选出 Leader。
初始时，所有节点都是 Follower，由于此时没有 Leader，所以没有 Follower 会收到来自 Leader 的心跳信息，当等待时间超过 election timeout 之后，Follower 就会变成 Candidate，尝试竞选。
election timeout 是一个一定范围内的随机数，每个节点都不一样，防止同时有大量节点同时竞选
首先，A 节点将自己状态改为 Candidate，同时使自己的 term 号加一，并向自己投一票。同时向其他所有节点发出请求，请求其他节点为自己投票。这会出现以下几种情况：
- 假设在该 term 内，A 节点收集到半数以上的投票，A 就可以将自身状态设置为 Leader，成为 Leader 节点。一旦 A 成为 Leader 节点，他就会在集群内广播心跳信息，维持集群的运作。
- 假设在该 term 内，A 节点没有收集到半数以上的投票，在等待时间超过 election timeout 之后重新发起一轮新的选举。
每个 Follwer 在一个 term 中只会投出一张选票，采取先到先得的策略；需要注意的是一个 term 中并不一定会产生一个 Leader，Raft 保证的是一个 term 中至多存在一个 Leader。可以简单证明，一个 Follwer 在一个 term 中最多投出一张选票，那么得到半数以上选票的至多有一个。
第二点通常是因为多个 Follower 成为 Candidate，所以导致会出现平票的情况，无法拿到半数以上的投票。在这一点上 Raft 通过将 election timeout 随机化来解决，尽可能避免 Follower 同时变成 Candidate 产生分票。
除此之外，还有一种异常情况，选举 Leader 是默认 Leader 不存在或宕机了。但假设在选票过程中 Leader 恢复了，此时怎么办？
通过 term 号。节点之间的信息传递会包含 term 号，假设来自 Leader 的信息的 term 号大于等于节点 A 的，则 A 承认 Leader，退化为 Follower；反之，则拒绝该 Leader 的请求，维持自己的 Candidate 状态。
假设 A 和 Leader 之间的通信断开了，但和其他节点的通信仍然正常，此时 A 认为 Leader 宕机，应该进行 Leader 的选举，发起了一个新的 term，但实际上 Leader 是在正常运作，此时会发生什么？
由于此时 term 号大家都是最新的，无法根据 term 号来分辨，所以进一步需要使用 log 是否最新来判断，由于 A 与 Leader 断开连接，他显然得不到最新的 log 信息，而其他 Follower 就可以根据这个 log 文件的新旧来判断是否要拒绝投票。
所以接下来我们就要将 log 的具体实现。
Command log
一旦 Leader 确定之后，集群就可以接收来自外界的请求了。假设一个集群的 log 状态如下：
假设 A 是 Leader，其余四个节点都是 Follower，可以看到目前一共经过了三个任期。
日志中的每一条记录都包含了以下信息：
- 要执行的指令（例如上表中设置某个变量的值）
- 创建记录的 term 号
- 创建记录的索引号
- 指令是否可以执行（commited）
指令是否能执行反映的本质是否已经实现了一致性分发，如果有半数以上节点达成一致，则认为实现了一致性分发。在 Raft 中，一条指令是否能执行取决于该指令日志是否被复制到半数以上的节点中，如果已经复制了半数以上，则可以执行，否则不能执行。在节点数为 5 时，需要至少复制到 3 个节点上才可以被标记为 commited。
Leader 会记录当前可执行指令的最大索引，并通知所有 Follwer，从而使 Follower 执行指令。
为了实现上述的目标，Raft 定义了 log 的一致性，它要求：
- 如果两份 log 在索引为 n 的记录的 term 号相同，那么前 n-1 条记录也一定相同。换句话说，如果某条记录完全相同，则此前的记录也一定完全相同。
所以它进一步要求：
- 如果两份 log 的任意一条记录拥有相同的 index 值和相同的 term 号，那么他们存储的指令是一样的，也就是完全相同。
- 如果两份 log 的任意一条记录拥有相同的 index 值和相同的 term 号，那么他们此前的记录也是完全相同的。
由于一个 term 号中至多存在一个 Leader，Leader 保证一个 index 只会存在一条记录，且不会修改已经创建的记录，所以第一条可以得到保证。为了保证此前的记录也完全一致，Leader 在同步当前指令记录时，会附带上一条记录的 index 和 term，只有当 Follwer 最新的指令记录和 Leader 的上一条记录一样时，才会接收，否则拒绝。通过这样的机制就可以保证第二条成立。
可以简单归纳证明两份 index 为 n 且 term 号相同的记录，他们的前一条也必然相同，那么前前一条也必然相同，因为前一条相同。
这样就保证了，只要当前指令实现了一致性分发，那么就可以执行，并且保证了此前的指令序列也一定是一致的，进一步就保证了半数以上的节点的状态一致。
接下来我们就要考虑剩下那不一致的部分怎么处理了，我们考虑一种网络情况非常差的情况：
每个格子内的数字表示的是 term 号，指令在这里省略了。可以注意到 Follower 中产生了非常严重的不一致，但是半数以上的节点实现了一致性，Leader 和 A、C、D 在 index 为 9 处都实现了一致性分发。
以上的不一致可以分为两种情况：
- Missing Entries 比较好理解，Leader 的状态总是领先于 Follower，所以有的 Follower 可能还来不及同步
- Extraneous Entries 则是在 Leader 更换的时候发生的，也许此前的 Leader 是节点 F，它接受了许多指令，但是还来不及同步给其他 Follower 就宕机了，此后 Leader 变成其他人，这部分指令就变成了 Extraneous Entries
这部分中，Raft 认为没有实现一致性分发的记录可以丢弃，所以 Extraneous Entries 直接丢弃，Missing Entries 进行补全。
Leader 会强制用自己的 log 内容去覆盖 Follower 的 log 内容：当日志同步产生拒绝时，Leader 会找到 Follower 记录中最后实现同步的地方，也就是这个位置之前能保证记录完全一致，然后在这个位置之后，Leader 将自己的记录覆盖掉 Follower 的记录。
这样简单粗暴的做法可以保证正确性吗？这样就必须假设 Leader 拥有的是全局最新最全面的信息。
假设 Leader A 在一条记录上完成了 commit，分别在 B、C、D 上，唯独 F 没有完成同步，但此时 A 宕机，F 又恰好竞选上 Leader，这条已经被 commit 的记录就会被删除。但是已经执行的指令却无法撤销，就会导致节点状态产生不一致。
为了使这个问题可以简单地解决，Raft 需要再对 Leader 竞选添加一些额外的规则。
额外的选举规则
在竞选 Leader 时，Candidate 必须保存所有已经 commited 的指令记录，保证该节点竞选为 Leader 后，所管理的节点可以实现状态一致性。
Raft 基于这样的推导：
- 要成功竞选 Leader，必须要得到半数以上的投票
- 要成功 commit 一条指令，必须半数以上节点完成同步
- 所以可以知道，半数以上的选票中，一定有一个节点是存在最新 commited 的指令
只要投票节点中最新的 commited 记录不比 Candidate 最新的 commited 记录新，也就是 Candidate 最新的 commited 指令是最新的，则说明 Candidate 可以竞选为 Leader。这里的新旧是通过 term 号和 index 号来判断的，term 号大则新，term 号相同，index 号大则新。
额外的 Commit 规则
虽然此前定义半数以上达成一致就可以看作是实现了一致性，但是在 Leader 更换的过程中仍然有可能违背这一要求。
假设：以下指令用 index 号来表示
- 在 term 号为 2 时，S1 为 Leader，并且分发给 S2 指令 3，随后宕机
- 在 term 号为 3 时，S5 为 Leader，接受了三个指令 3、4、5 之后宕机
- 在 term 号为 4 时，S1 为 Leader，继续分发指令 3，满足半数要求，并 commit 指令 3，同时接收到一个新指令 4，然后又宕机了
- 在 term 号为 5 时，S5 有可能被选为 Leader，但由于他的记录中就不存在过指令 3，在覆盖其他 Follower 的过程中就会导致不一致
再次说明，commit 代表节点执行了某指令，虽然最后日志可以保持一致，但是节点执行的指令序列却不一致了，导致了节点状态的不一致。
为什么 S5 有可能被选为 Leader？在 term 号为 5 的选举中，S2、S3 最新的 commited 的指令的 term 号是 2，而 S5 最新的指令 term 号是 3，是最新的，就可以参加选举。
也就是说，在 term 号为 4 时，S1 就不应该 commit 指令 3，否则就有可能出现这种情况。
这就需要进一步对 commit 规则进行要求：
- 当前 term 号的 Leader 不能对旧 term 号的记录进行 commit，除非当前 term 号的指令得到了 commit
也就是说，在上述假设的情况下，虽然指令 3 已经在半数以上节点上存在了，但由于当前 term 号 4 的指令没有得到 commit，所以指令 3 不能 commit。此时发生宕机，S5 当选 Leader 覆盖掉其他节点就没问题，因为指令 3 没有被执行过。
而假设指令 3 已经被 commit 了，说明 term 号为 4 的指令也得到 commit 了，此时 S5 就不可能选举成功，因为他最新的记录 term 号为 3。
Reference
[1] https://zhuanlan.zhihu.com/p/344781101
[2] https://blog.csdn.net/qq_37026934/article/details/121509220
[3] https://www.youtube.com/watch?v=vYp4LYbnnW8&ab_channel=DiegoOngaro
[4] https://raft.github.io/slides/riconwest2013.pdf
[5] Ongaro D, Ousterhout J. In search of an understandable consensus algorithm[C]//2014 USENIX annual technical conference (USENIX ATC 14). 2014: 305-319.