分布式共识：Raft

07 | Raft算法（一）：如何选举领导者？-分布式协议与算法实战-极客时间
 08 | Raft算法（二）：如何复制日志？-分布式协议与算法实战-极客时间
 09 | Raft算法（三）：如何解决成员变更的问题？-分布式协议与算法实战-极客时间
这几个课程的评论都没有看，实在太多了，无聊的时候再看吧。

Raft 概念

Raft，一个更易理解的共识算法。

相比于 Paxos，Raft 最大的特性就是易于理解。为了达到这个目标，Raft 主要做了两方面的事情：

问题分解。将共识算法分为三个子问题，分别是领导者选举、日志复制、安全性。
状态简化：对算法做出一些限制，减少状态数量和可能产生的变动。

复制状态机

在具体介绍 Raft 之前，我们要先了解一下复制状态机(Replicated state machine)的概念。
复制状态机：相同的初始状态 + 相同的输入 = 相同的结束状态
多个节点上，从相同的初始状态开始，执行相同的一串命令，产生相同的最终状态。
在 Raft 中，leader 将客户端请求(command)封装到一个个 log entry 中，将这些 log entries 复制到所有 follower 节点，然后大家按相同顺序应用 log entries 中的 command。根据复制状态机的理论，大家的结束状态肯定是一致的。

400

可以说，我们使用共识算法，就是为了实现复制状态机。一个分布式场景下的各节点间，就是通过共识算法来保证命令序列的一致，从而始终保持它们的状态一致，从而实现高可用的。(投票选主是一种特殊的命令)
这里稍微拓展一点，复制状态机的功能可以更加强大。比如两个副本一个采用行存储的数据结构存储数据，另一个采用列存储，只要它们初始数据相同，并持续发给他们相同的命令，那么同一时刻从两个副本中读取到的结果也是一样的，这就是一种 HTAP 的实现方法(比如 TiDB)。扩展知识：OLTP、OLAP、HTAP对比

状态简化

三种状态

在任何时刻，每一个服务器节点都处于 leader，follower 或 candidate 这三个状态之一。
相比于 Paxos，这一点就极大简化了算法的实现，因为 Raft 只需考虑状态的切换，而不用像 Paxos 那样考虑状态之间的共存和互相影响。

400

任期

Raft 把时间分割成任意长度的任期(term)，任期用连续的整数标记。
每一段任期从一次选举开始。在某些情况下，一次选举无法选出 leader(比如两个节点收到了相同的票数)，在这种情况下，这一任期会以没有 leader 结束；一个新的任期 (包含一次新的选举)会很快重新开始。Raft 保证在任意一个任期内，最多只有一个 leader。

400

节点通信

Raft 算法中服务器节点之间使用 RPC 进行通信，并且 Raft 中只有两种主要的 RPC：
- RequestVote RPC：由 candidate 在选举期间发起。
- AppendEntries RPC：由 leader 发起，用来复制日志和提供一种心跳机制。
服务器之间通信的时候会交换当前任期号；如果一个服务器上的当前任期号比其他的小，该服务器会将自己的任期号更新为较大的那个值。
如果一个 candidate 或者 leader 发现自己的任期号过期了，它会立即回到 follower 状态。
如果一个节点接收到一个包含过期的任期号的请求，它会直接拒绝这个请求。

领导者选举

Raft 内部有一种心跳机制，如果存在 leader，那么它就会周期性地向所有 follower 发送心跳，来维持自己的地位。如果 follower 一段时间没有收到心跳，那么他就会认为系统中没有可用的 leader 了，然后开始进行选举。
开始一个选举过程后，follower 先增加自己的当前任期号，并转换到 candidate 状态。然后投票给自己，并且并行地向集群中的其他服务器节点发送 RequestVote RPC。

400

最终会有三种结果：
- ① 它获得超过半数选票赢得了选举 → 成为主并开始发送心跳
- ② 其他节点赢得了选举 → 收到新 leader 的心跳后，如果新 leader 的任期号不小于自己当前的任期号，那么就从 candidate 回到 follower 状态。
- ③ 一段时间之后没有任何获胜者 → 每个 candidate 都在一个自己的随机选举超时时间后增加任期号开始新一轮投票。
为什么会没有获胜者？比如有多个 follower 同时成为 candidate，得票太过分散，没有任何一个 candidate 得票超过半数。
论文中给出的随机选举超时时间为 150~300ms。论文较早，现在根据实际情况来调整该超时时间。

02 分布式选举：Raft-4.png400

对于没有成为 candidate 的 follower 节点，对于同一个任期，会按照先来先得的原则投出自己的选票。
为什么 RequestVote RPC 中要有 candidate 最后一个日志的信息呢，安全性子问题中会给出进一步的说明。

日志复制

Leader 被选举出来后，开始为客户端请求提供服务。
客户端怎么知道新 leader 是哪个节点呢？如果是 leader 正好；如果是 follower，可以告知客户端找谁；如果是宕机的，则重试连接其他节点。
Leader 接收到客户端的指令后，会把指令作为一个新的条目追加到日志中去。
一条日志中需要具有三个信息：状态机指令、leader 的任期号、日志号。

400

Leader 并行发送 AppendEntries RPC 给 follower，让它们复制该条目。当该条目被超过半数的 follower 复制后，leader 就可以在本地执行该指令并把结果返回客户端。
我们把本地执行指令，也就是 leader 应用日志与状态机这一步，称作提交。
在此过程中，leader 或 follower 随时都有崩溃或缓慢的可能性，Raft 必须要在有宕机的情况下继续支持日志复制，并且保证每个副本日志顺序的一致(以保证复制状态机的实现)。具体有三种可能：follower 缓慢、follower 宕机、leader 宕机。

三种日志不一致的情况

① 如果有 follower 因为某些原因没有给 leader 响应，那么 leader 会不断地重发 AppendEntries RPC，哪怕 leader 已经回复了客户端。
② 如果有 follower 崩溃后恢复，这时 Raft 追加条目的一致性检查生效，保证 follower 能按顺序恢复崩溃后的缺失的日志。
Raft 的一致性检查：leader 在每一个发往 follower 的 AppendEntries RPC 中，会放入前一个日志条目的索引位置和任期号，如果 follower 在它的日志中找不到前一个日志，那么它就会拒绝此日志，leader 收到 follower 的拒绝后，会发送前一个日志条目，从而逐渐向前定位到 follower 第一个缺失的日志。
可以选择通过二分法、隔几个询问的方法来加快定位到第一个缺失的日志。在实践中，认为这种优化是没有必要的，因为失败不经常发生并且也不可能有很多不一致的日志条目。
③ 如果 leader 崩溃，那么崩溃的 leader 可能已经复制了日志到部分 follower 但还没有提交，而被选出的新 leader 又可能不具备这些日志，这样就有部分 follower 中的日志和新 leader 的日志不相同。
Raft 在这种情况下，leader 通过强制 follower 复制它的日志来解决不一致的问题，这意味着 follower 中跟 leader 冲突的日志条目会被新 leader 的日志条目覆盖(因为没有提交，所以不违背外部一致性)。
这里补充一个问题：是否存在 leader 和某个 follower 前后日志内容相同，但是中间日志不同的可能性？答案是，不存在。因为 Raft 的一致性检查保证了，如果前面存在日志不一致，后面的日志是不会复制成功的。sure？
下图中情况的解释：
- leader 可以依靠 a, b, e 和自己当选 leader。
- f 也可以投票，日志情况原因是 2, 3 任期内的日志都没有正常复制到大多数节点，即没有提交。没有提交，那么被覆盖了不违背外部一致性。

400

通过上述机制，leader 在当权之后就不需要任何特殊的操作来使日志恢复到一致状态。
Leader 只需要进行正常的操作，然后日志就能在回复 AppendEntries 一致性检查失败的时候自动趋于一致。
Leader 从来不会覆盖或者删除自己的日志条目。(Append-Only)
这样的日志复制机制，就可以保证一致性特性：
- 只要过半的服务器能正常运行，Raft 就能够接受、复制并应用新的日志条目；
- 在正常情况下，新的日志条目可以在一个 RPC 来回中被复制给集群中的过半机器；
- 单个运行慢的 follower 不会影响整体的性能。

02 分布式选举：Raft-7.png400

对于 follower 而言，接收到了 leader 日志不能立刻提交，因为无法判断该日志是否被多数节点复制。只能在下一次 AppendEntries 时，即下一次心跳或者新日志的时候，根据 leaderCommit 来判断是否提交。
如果 leaderCommit > commitIndex，那么把 commitIndex 设为 min(leaderCommit, index of last new entry)
success 标志只有在 request 的 term 大于等于自己的 term，且 request 通过了一致性检查之后才会返回 true。
当然存在 leader 在通过 RPC 更新前宕机了，那么 client 认为是已提交，但是 follower 认为未提交。这个是客户端交互，属于应用端的事情，理论上不是 Raft 应该担心的。论文中也没有对这个问题进行讨论。分布式系统在提交阶段的机器宕机是很难处理的，后续 Google Percolator 事务模型会对分布式场景的 commit 进行深入讨论。

安全性

领导者选举和日志复制两个子问题实际上已经涵盖了共识算法的全程，但这两点还不能完全保证每一个状态机会按照相同的顺序执行相同的命令。

所以 Raft 通过几个补充规则完善整个算法，使算法可以在各类宕机问题下都不出错。这些规则包括(不讨论安全性条件的证明过程)：

Leader 宕机处理：选举限制
Leader 宕机处理：新 leader 是否提交之前任期内的日志条目
Follower 和 Candidate 宕机处理
时间与可用性限制

Leader 宕机处理：选举限制

如果一个 follower 落后了 leader 若干条日志(但没有漏一整个任期)，那么下次选举中，按照领导者选举里的规则，它依旧有可能当选 leader。它在当选新 leader 后就永远也无法补上之前缺失的那部分日志，从而造成状态机之间的不一致。
所以需要对领导者选举增加一个限制，保证被选出来的 leader 一定包含了之前各任期的所有被提交的日志条目。
RequestVote RPC 执行了这样的限制：RPC 中包含了 candidate 的日志信息，如果投票者自己的日志比 candidate 的还新，它会拒绝掉该投票请求。
Raft 通过比较两份日志中最后一条日志条目的索引值和任期号来定义谁的日志比较新。

400

如果两份日志最后条目的任期号不同，那么任期号大的日志更“新”。
如果两份日志最后条目的任期号相同，那么日志较长的那个更“新”。

400

上面的流程：

S1 当选 leader，在任期 2 时宕机
S5 凭借 S3、S4、S5 当选 leader，处于任期 3，并宕机
S1 宕机恢复，申请成为 leader，处于任期 4，又宕机。期间，之前的任期 2 日志 RPC 到了 S3 上，并复制到节点上。
S5 宕机恢复，凭借 S2、S3、S4 当选 leader。

Leader 宕机处理：新 leader 是否提交之前任期内的日志条目

一旦当前任期内的某日志已存储到过半节点上，leader 就知道该日志条目可以被提交了。
follower 的提交触发：下一个 AppendEntries RPC，即心跳 or 新日志。
如果某个 leader 在提交某个日志条目之前崩溃了，新 leader 会试图完成未提交日志的复制。什么情况呢？新 leader 是具有老 leader 已提交的日志的，但是老日志可能在新 leader 中还没有提交，这时新 leader 会尝试将这个日志复制给其他 follower。
Raft 永远不会通过计算副本数目的方式来提交之前任期内的日志条目。
为什么不提交呢？如果提交了，那么没有包含这个日志的节点就存在日志丢失了。例如上图从 c 到 d 中，假如 S1 将任期 2 的日志复制给 S2S3S4，但是 S1 宕机、S5 恢复后，S5 的任期 3 日志会覆盖掉其他节点的任期 2 日志，导致丢失。
老日志怎样才能提交？等这个新 leader 在它的任期内新产生一个日志，如下图 c 到 e，在这个日志提交时，老 leader 任期内的日志也就可以提交了。相当于用新 leader 新任期的日志，将老任期的日志保护起来，这样老任期的日志就不会被覆盖了。

400

Follower 和 Candidate 宕机处理

Follower 和 Candidate 崩溃后的处理方式比 leader 崩溃要简单的多，并且两者的处理方式是相同的。
Raft 会无限重试来处理两种 RPC 的失败，直到机器重启后，RPC 就可以成功完成。
由于 Raft 的 RPC 都是幂等的，所以即使 RPC 请求处理完但是没有响应，重启会再次收到相同请求，也不会对一致性有影响。

时间与可用性限制

Raft 算法整体不依赖客观时间，也就是说，哪怕因为网络或其他因素，造成后发的 RPC 先到，也不会影响 Raft 的正确性。
只要整个系统满足下面的时间要求，Raft 就可以选举出并维持一个稳定的 leader： 广播时间(broadcastTime) << 选举超时时间(electionTimeout) << 平均故障时间 (MTBF).
广播时间和平均故障时间是由系统决定的，但是选举超时时间是我们自己选择的。Raft 的 RPC 需要接受并将信息落盘，所以广播时间大约是 0.5ms 到 20ms，取决于存储的技术。因此，选举超时时间可能需要在 10ms 到 500ms 之间。大多数服务器的平均故障间隔时间都在几个月甚至更长。

集群成员变更

在需要改变集群配置的时候(如增减节点、替换宕机的机器或者改变复制的程度)，Raft 可以进行配置变更自动化。
自动化配置变更机制最大的难点是保证转换过程中不会出现同一任期的两个 leader，因为转换期间整个集群可能划分为两个独立的大多数。
右图为三节点(S123)集群扩容到五节点(S12345)
S1S2 为老配置集群，S3S4S5 为新配置集群
老配置为三节点，S1S2 处于老配置中，两者同意可以选出一个 leader(2/3)
新配置为五节点，S3S4S5 处于新配置中，三者同意也可以选出一个 leader(3/5)

400

所以配置采用了一种两阶段的方法。
集群先切换到一个过渡的配置，称之为联合一致(joint consensus)。
第一阶段，leader 发起 $C_{o l d, n e w}$ ，使整个集群进入联合一致状态。这时，所有 RPC 都要在新旧两个配置中都达到大多数才算成功。
第二阶段，leader 发起 $C_{n e w}$ ，使整个集群进入新配置状态。这时，所有 RPC 只要在新配置下能达到大多数就算成功。

400

一旦某个服务器将该新配置日志条目增加到自己的日志中，他就会用该配置来做出未来所有的决策。服务器总是使用它日志中最新的配置，无论该配置日志是否已经被提交。这意味着 Leader 不用等待 $C_{o l d, n e w}$ 和 $C_{n e w}$ 返回，就会直接使用其中的新规则来作出决策。
我们假设 leader 可以在集群成员变更任何时候宕机，大概有以下几种可能：
① leader 在 $C_{o l d, n e w}$ 未提交时宕机
② leader 在 $C_{o l d, n e w}$ 已提交但 $C_{n e w}$ 未发起时宕机
③ leader 在 $C_{n e w}$ 已发起时宕机

300

假设最开始是 S1S2S3，S3 为 leader。然后 S4S5 加入，S3 发送 $C_{o l d, n e w}$ 日志，此时复制给了 S4S5 节点。

400

① S3 leader 在 $C_{o l d, n e w}$ 未提交时宕机 - 老配置少部分有 $C_{o l d, n e w}$ (上图)

S1S2 超时，开始进行选举，并且可以产生一个老配置的 leader。
在联合一致状态下，S3S4S5 必须要在老配置(S1S2S3)和新配置(S1S2S3S4S5)下都拿到超过半数选票才能当选。由于 S1S2 都投给了老配置，所以 S3S4S5 都无法在老配置中拿到超过半数的选票。即，集群中只能选出 S1S2 中的一个 leader。
这样集群成员变更就失败了，但不会出现两个 leader。

300

① S3 leader 在 $C_{o l d, n e w}$ 未提交时宕机 - 老配置大部分有 $C_{o l d, n e w}$ (上图)

老配置大部分有 $C_{o l d, n e w}$ 后，新 leader 可能具有 $C_{o l d, n e w}$
但按照安全性限制，这个新 leader 无法提交 $C_{o l d, n e w}$
可以让它继续发送 $C_{n e w}$ ，继续进行集群成员变更。

300

S3 没宕机时的后续过程 (上图)

在这种情况下，leader(S3)的 $C_{o l d, n e w}$ 日志在新旧两种配置的集群中都超过半数了， $C_{o l d, n e w}$ 就可以被提交了。
S2S3/S1S2S3 = 2/3
S2S3S4/S1S2S3S4S5 =3/5

② leader 在 $C_{o l d, n e w}$ 已提交但 $C_{n e w}$ 未发起时宕机 (上图)

这时候选举限制安全性规则决定了选出的新 leader 一定具有 $C_{o l d, n e w}$ ，也就是符合在两种配置集群中都超过半数，已经不存在脑裂的可能了。

300

联合一致状态下，也是可以正常执行命令的，但也需要在两个配置集群中都达到大多数才能提交

300

准备发起 $C_{n e w}$ 提交

$C_{o l d, n e w}$ 提交后，leader 就会发起 $C_{n e w}$ ，这时 leader 只要满足新配置中的条件，就可以提交日志。
S3S4S5/S1S2S3S4S5 = 3/5
要 $C_{n e w}$ 发起，意味着 $C_{o l d, n e w}$ 已经被复制到了大多数节点，就不需要再去管老配置，只需要在新配置中 $C_{n e w}$ 达到大多数就可以了。

③ leader 在 $C_{n e w}$ 已发起时宕机

已经复制了 $C_{n e w}$ 的节点会只按新配置选举，没有复制 $C_{n e w}$ 的节点会按新老配置选举。
没有复制 $C_{n e w}$ 的节点选举成功也会发 $C_{n e w}$ 。
进而最终都会转变为新配置。

300

③ leader 在 $C_{n e w}$ 已发起时宕机 & 缩减节点情况

由 S1S2S3S4S5 缩减为 S1S2S3
这时如果 leader S3 宕机了， $C_{n e w}$ 会不会被覆盖呢？
不会的，因为处于联合一致状态的节点，也就是只复制了 $C_{o l d, n e w}$ 没有复制 $C_{n e w}$ 的节点，必须要在新老配置中都得到大多数选票才能选举成功；而处于 $C_{n e w}$ 的节点，在新配置中达到大多数就可以选举成功。
而 S2S3 不会投票给 S1S4S5 中的一个，所以 S3 宕了，只有 S2 才能当选，已提交的 $C_{n e w}$ 不会被覆盖。

300

① S3 leader 在 $C_{o l d, n e w}$ 未提交时宕机，新 leader 继续发送 $C_{n e w}$ 的情况

选出的新 leader 具有 $C_{o l d, n e w}$ 但这个新 leader 无法提交 $C_{o l d, n e w}$ (安全性限制)
可以让它继续发送 $C_{n e w}$ ，继续进行集群成员变更。
S1S4S5 都有 $C_{n e w}$ ，满足新配置的大多数， $C_{n e w}$ 能提交吗? 仍然不能提交。因为没有满足 $C_{o l d, n e w}$ 的提交规则，如果提交了 $C_{n e w}$ ，那么 $C_{o l d, n e w}$ 会被间接提交，这时不安全的。
论文中没有给出这种情况的处理办法。在某些实现中，强制 $C_{n e w}$ 按照联合一致的规则来提交。如果当前 leader 在一段时间后还满足不了条件，自动退位。

集群节点变更回顾

在 $C_{o l d, n e w}$ 发起但未提交时，Raft 集群还未进入联合一致状态。这时 leader 宕机，可以仅靠老配置选出来的新 leader。
一旦 $C_{o l d, n e w}$ 提交，Raft 集群就进入了联合一致状态，这时 leader 宕机，选出的新 leader 也要符合联合一致的选票规则了。
$C_{o l d, n e w}$ 提交后，leader 就可以发起 $C_{n e w}$ ，从发起 $C_{n e w}$ 开始，集群就可以仅靠新配置进行选举和日志复制了。
如果是缩减集群的情况下，leader 可能自身就是缩减的对象，那么它会在 $C_{n e w}$ 复制完成后自动退位，这点我们接下来会进行补充说明。

集群成员变更还有三个补充规则需要说明一下

1. 新增节点时，需要等新增的节点完成日志同步再开始集群成员变更
这点是防止集群在新增节点还未同步日志时就进入联合一致状态或新配置状态，影响正常命令日志提交。
1. 缩减节点时，leader 本身可能就是要缩减的节点，这时它会在完成 $C_{n e w}$ 的提交后自动退位。
在发起 $C_{n e w}$ 后，要退出集群的 leader 就会处在操纵一个不包含它本身的 Raft 集群的状态下。这时它可以发送 $C_{n e w}$ 日志，但是日志计数时不计自身。
1. 为了避免下线的节点超时选举而影响集群运行，服务器会在它确信集群中有 leader 存在时拒绝 Request Vote RPC。
因为 $C_{n e w}$ 的新 leader 不会再发送心跳给要退出的节点，如果这些节点没有及时下线，它们会超时增加任期号后发送 Request Vote RPC。虽然它们不可能当选 leader，但会导致 Raft 集群进入投票选举阶段，影响集群的正常运行。
为了解决这个问题，Raft 在 Request Vote RPC 上补充了一个规则：一个节点如果在最小超时时间之内收到了 Request Vote RPC，那么它会拒绝此 RPC。
这样，只要 follower 连续收到 leader 的心跳，那么退出集群节点的 Request Vote RPC 就不会影响到 Raft 集群的正常运行了。

扩展知识

分布式存储与复制状态机

Raft 基本概念总结

集群成员变更扩展

日志压缩机制

Raft 采用的是一种快照技术，每个节点在达到一定条件之后，可以把当前日志中的命令都写入自己的快照，然后就可以把已经并入快照的日志都删除了。
快照中一个 key 只会留有最新的一份 value，占用空间比日志小得多。
如果一个 follower 落后 leader 很多，如果老的日志被清理了，leader 怎么同步给 follower 呢？直接向 follower 发送自己的快照。

02 分布式选举：Raft-21.png|400

只读操作处理

直观上讲，raft 的读只要直接读取 leader 上的结果就行了。
直接从 leader 的状态机取值，实际上并不是线性一致性读，一般也称作强一致性读。
我们对线性一致性读的定义：读到的结果要是读请求发起时已经完成提交的结果（快照）。
在 leader 和其他节点发生了网络分区情况下，其他节点可能已经重新选出了一个 leader，而如果老 leader 在没有访问其他节点的情况下直接拿自身的值返回客户端，这个读取的结果就有可能不是最新的。

02 分布式选举：Raft-22.png|400

要追求强一致性读的话，就需要让这个读的过程或结果，也在大多数节点上达到共识。
稳妥的方法：把读也当做一个 log，由 leader 发到所有的所有节点上寻求共识，这个读的 log 提交后，得到的结果是一定符合线性一致性的。
优化后的方法，要符合以下规则：
① 线性一致性读一定要发往 leader。
② 如果一个 leader 在它的任期内还没有提交一个日志，那么它要在提交了一个日志后才能反馈 client 读请求。（可以通过 no-op 补丁来优化这一点）
因为只有在自己任期内提交了一个日志，leader 才能确认之前任期的哪些日志已被提交，才不会出现已提交的数据读取不到的情况。
安全性规则能保证被选出的 leader 一定具有所有已被提交的日志，但它可能有的日志还没有提交，它并不能确定哪些日志是已提交的，哪些日志没提交，而在它任期内提交一个日志，就能确定这一点。
③ 在进行读操作前，leader 要向所有节点发送心跳，并得到大多数节点的反馈。（为了确保自己仍是 leader）
④ leader 把自己已提交的日志号设为 readIndex，只要 leader 应用到了 readIndex 的日志，就可以查询状态机结果并返回 client 了。

优化过后的线性一致性读，也至少需要一轮 RPC（leader 确认的心跳）。并不比写操作快多少（写操作最少也就一轮 RPC）。
所以，还可以更进一步，因为读的这轮 RPC 仅仅是为了确认集群中没有新 leader 产生。那么如果 leader 上一次心跳发送的时间还不到选举超时时间的下界，集群就不能选出一个新 leader，那么这段时间就可以不经过这轮心跳确认，直接返回读的结果。（但不建议使用这种方法）
如果不要求强一致性读，怎么样利用 follower 承载更大的读压力呢?
① follower 接收到读请求后，向 leader 请求 readIndex。
② follower 等待自身状态机应用日志到 readIndex。
③ follower 查询状态机结果，并返回客户端。

🪴 Obsidian Publish

探索