关于数据库:条分缕析-Raft-算法

本文整顿自 Ongaro 在 Youtube 上的视频。

指标

Raft 的指标（或者说是分布式共识算法的指标）是：保障 log 完全相同地复制到多台服务器上。

只有每台服务器的日志雷同，那么，在不同服务器上的状态机以雷同程序从日志中执行雷同的命令，将会产生雷同的后果。

共识算法的工作就是治理这些日志。

零碎模型

咱们假如：

• 服务器可能会宕机、会进行运行过段时间再复原，然而 非拜占庭的（即它的行为是非歹意的，不会篡改数据等）；
• 网络通信会中断，音讯可能会失落、提早或乱序；可能会网络分区；

Raft 是基于 Leader 的共识算法，故次要思考：

• Leader 失常运行
• Leader 故障，必须选出新的 Leader

长处：只有一个 Leader，简略。

难点：Leader 产生扭转时，可能会使零碎处于不统一的状态，因而，下一任 Leader 必须进行清理；

咱们将从 6 个局部解释 Raft：

1. Leader 选举；
2. 失常运行：日志复制（最简略的局部）；
3. Leader 变更时的安全性和一致性（最辣手、最要害的局部）；
4. 解决旧 Leader：旧的 Leader 并没有真的下线怎么办？
5. 客户端交互：实现线性化语义(linearizable semantics)；
6. 配置变更：如何在集群中减少或删除节点；

开始之前

开始之前须要理解 Raft 的一些术语。

服务器状态

服务器在任意工夫只能处于以下三种状态之一：

• Leader：解决所有客户端申请、日志复制。同一时刻最多只能有一个可行的 Leader；
• Follower：齐全被动的（不发送 RPC，只响应收到的 RPC）——大多数服务器在大多数状况下处于此状态；
• Candidate：用来选举新的 Leader，处于 Leader 和 Follower 之间的临时状态；

零碎失常运行时，只有一个 Leader，其余都是 Followers.

状态转换图：

任期

工夫被划分成一个个的 任期(Term)，每个任期都由一个数字来示意任期号，任期号枯燥递增并且永远不会反复。

一个失常的任期至多有一个 Leader，通常分为两局部：

• 任期开始时的选举过程；
• 失常运行的局部；

有些任期可能没有选出 Leader（如图 Term 3），这时候会立刻进入下一个任期，再次尝试选出一个 Leader。

每个节点保护一个 currentTerm 变量，示意零碎中以后任期。currentTerm必须长久化存储，以便在服务器宕机重启时将其复原。

任期十分重要！任期可能帮忙 Raft 辨认过期的信息。例如：如果 currentTerm = 2 的节点与 currentTerm = 3 的节点通信，咱们能够晓得第一个节点上的信息是过期的。

咱们只应用最新任期的信息。前面咱们会遇到各种状况，去检测和打消不是最新任期的信息。

两个 RPC

Raft 中服务器之间所有类型的通信通过两个 RPC 调用：

• RequestVote：用于选举；
• AppendEntries：用于复制 log 和发送心跳；

1. Leader 选举

启动

• 节点启动时，都是 Follower 状态；
• Follower 被动地承受 Leader 或 Candidate 的 RPC；
• 所以，如果 Leader 想要放弃权威，必须向集群中的其它节点发送心跳包（空的AppendEntries RPC）；

• 期待选举超时 (electionTimeout，个别在 100~500ms) 后，Follower 没有收到任何 RPC：

  • Follower 认为集群中没有 Leader
  • 开始新的一轮选举

选举

当一个节点开始竞选：

• 减少本人的currentTerm
• 转为 Candidate 状态，其指标是获取超过半数节点的选票，让本人成为 Leader
• 先给本人投一票
• 并行地向集群中其它节点发送 RequestVote RPC 索要选票，如果没有收到指定节点的响应，它会重复尝试，直到产生以下三种状况之一：

1. 取得超过半数的选票：成为 Leader，并向其它节点发送 AppendEntries 心跳；
2. 收到来自 Leader 的 RPC：转为 Follower；
3. 其它两种状况都没产生，没人可能获胜 (electionTimeout 已过)：减少currentTerm，开始新一轮选举；

流程图如下：

选举安全性

选举过程须要保障两个个性：安全性 (safety) 和活性(liveness)。

安全性(safety)：一个任期内只会有一个 Leader 被选举进去。须要保障：

• 每个节点在同一任期内只能投一次票，它将投给第一个满足条件的投票申请，而后回绝其它 Candidate 的申请。这须要长久化存储投票信息 votedFor，以便宕机重启后复原，否则重启后votedFor 失落会导致投给别的节点；
• 只有取得超过半数节点的选票能力成为 Leader，也就是说，两个不同的 Candidate 无奈在同一任期内都取得超过半数的票；

活性(liveness)：确保最终能选出一个 Leader。

问题是：原则上咱们能够有限反复宰割选票，如果选举同一时间开始，同一时间超时，同一时间再次选举，如此循环。

解决办法很简略：

• 节点随机抉择超时工夫，通常在 [T, 2T] 之间（T =electionTimeout）
• 这样，节点不太可能再同时开始竞选，先竞选的节点有足够的工夫来索要其余节点的选票
• T >> broadcast time(T 远大于广播时间)时成果更佳

2. 日志复制

日志构造

每个节点存储本人的日志正本(log[])，每条日志记录蕴含：

• 索引：该记录在日志中的地位
• 任期号：该记录首次被创立时的任期号
• 命令

日志必须长久化存储。一个节点必须先将记录平安写到磁盘，能力向零碎中其余节点返回响应。

如果一条日志记录被存储在超过半数的节点上，咱们认为该记录 已提交(committed)——这是 Raft 十分重要的个性！如果一条记录已提交，意味着状态机能够平安地执行该记录。

在上图中，第 1-7 条记录被提交，第 8 条尚未提交。

揭示：多数派复制了日志即已提交，这个定义并不准确，咱们会在前面稍作批改。

失常运行

• 客户端向 Leader 发送命令，心愿该命令被所有状态机执行；
• Leader 先将该命令追加到本人的日志中；
• Leader 并行地向其它节点发送AppendEntries RPC，期待响应；

• 收到超过半数节点的响应，则认为新的日志记录是被提交的：

  • Leader 将命令传给本人的状态机，而后向客户端返回响应
  • 此外，一旦 Leader 晓得一条记录被提交了，将在后续的 AppendEntries RPC 中告诉曾经提交记录的 Followers
  • Follower 将已提交的命令传给本人的状态机
• 如果 Follower 宕机 / 超时：Leader 将重复尝试发送 RPC；
• 性能优化：Leader 不用期待每个 Follower 做出响应，只须要超过半数的胜利响应（确保日志记录曾经存储在超过半数的节点上）——一个很慢的节点不会使零碎变慢，因为 Leader 不用等他；

日志一致性

Raft 尝试在集群中放弃日志较高的一致性。

Raft 日志的 index 和 term 惟一标示一条日志记录。（这十分重要！！！）

1. 如果两个节点的日志在雷同的索引地位上的任期号雷同，则认为他们具备一样的命令；从头到这个索引地位之间的日志完全相同；
2. 如果给定的记录已提交，那么所有后面的记录也已提交。

AppendEntries一致性查看

Raft 通过 AppendEntries RPC 来检测这两个属性。

• 对于每个 AppendEntries RPC 蕴含新日志记录 之前那条记录的 索引 (prevLogIndex) 和任期(prevLogTerm)；
• Follower 查看本人的 index 和 term 是否与 prevLogIndex 和prevLogTerm匹配，匹配则接管该记录；否则回绝；

3. Leader 更替

当新的 Leader 上任后，日志可能不会十分洁净，因为前一任领导可能在实现日志复制之前就宕机了。Raft 对此的解决形式是：无需采取任何非凡解决。

当新 Leader 上任后，他不会立刻进行任何清理操作，他将会在失常运行期间进行清理。

起因是当一个新的 Leader 上任时，往往意味着有机器故障了，那些机器可能宕机或网络不通，所以没有方法立刻清理他们的日志。在机器复原运行之前，咱们必须保证系统失常运行。

大前提是 Raft 假如了 Leader 的日志始终是对的。所以 Leader 要做的是，随着时间推移，让所有 Follower 的日志最终都与其匹配。

但与此同时，Leader 也可能在实现这项工作之前故障，日志会在一段时间内堆积起来，从而造成看起来相当凌乱的状况，如下所示：

因为咱们曾经晓得 index 和 term 是日志记录的惟一标识符，这里不再显示日志蕴含的命令，下同。

如图，这种状况可能呈现在 S4 和 S5 是任期 2、3、4 的 Leader，但不知何故，他们没有复制本人的日志记录就解体了，零碎分区了一段时间，S1、S2、S3 轮流成为了任期 5、6、7 的 Leader，但无奈与 S4、S5 通信以进行日志清理——所以咱们看到的日志十分凌乱。

惟一重要的是，索引 1-3 之间的记录是已提交的(已存在多数派节点)，因而咱们必须确保留下它们。

其它日志都是未提交的，咱们还没有将这些命令传递给状态机，也没有客户端会收到这些执行的后果，所以不论是保留还是抛弃它们都无关紧要。

安全性

一旦状态机执行了一条日志里的命令，必须确保其它状态机在同样索引的地位不会执行不同的命令。

Raft 安全性(Safety)：如果某条日志记录在某个任期号已提交，那么这条记录必然呈现在更大任期号的将来 Leader 的日志中。

这保障了安全性要求：

• Leader 不会笼罩日志中的记录；
• 只有 Leader 的日志中的记录能力被提交；
• 在利用到状态机之前，日志必须先被提交；

这决定咱们要批改选举程序：

• 如果节点的日志中没有正确的内容，须要防止其成为 Leader；
• 略微批改 committed 的定义（_即后面提到的要稍作批改_）：后面说多数派存储即是已提交的，但在某些时候，咱们必须提早提交日志记录，直到咱们晓得这条记录是平安的，所谓平安的，就是咱们认为后续 Leader 也会有这条日志。

提早提交，选出最佳 Leader

问题来了：咱们如何确保选出了一个很好地保留了所有已提交日志的 Leader？

这有点辣手，举个例子：假如咱们要在上面的集群中选出一个新 Leader，但此时第三台服务器不可用。

这种状况下，仅看前两个节点的日志咱们无奈确认是否达成多数派，故无奈确认第五条日志是否已提交。

那怎么办呢？

通过比拟日志，在选举期间，抉择最有可能蕴含所有已提交的日志：

• Candidate 在 RequestVote RPCs 中蕴含日志信息（最初一条记录的 index 和 term，记为 lastIndex 和lastTerm）；
• 收到此投票申请的服务器 V 将比拟谁的日志更残缺：(lastTermV > lastTermC) ||
(lastTermV == lastTermC) && (lastIndexV > lastIndexC)将回绝投票；（即：V 的任期比 C 的任期新，或任期雷同但 V 的日志比 C 的日志更残缺）；
• 无论谁博得选举，能够确保 Leader 和超过半数投票给它的节点中领有最残缺的日志——最残缺的意思就是 index 和 term 这对惟一标识是最大的。

举个例子

Case 1: Leader 决定提交日志

任期 2 的 Leader S1 的 index = 4 日志刚刚被复制到 S3，并且 Leader 能够看到 index = 4 已复制到超过半数的服务器，那么该日志能够提交，并且平安地利用到状态机。

当初，这条记录是平安的，下一任期的 Leader 必须蕴含此记录，因而 S4 和 S5 都不可能从其它节点那里取得选票：S5 任期太旧，S4 日志太短。

只有前三台中的一台能够成为新的 Leader——S1 当然能够，S2、S3 也能够通过获取 S4 和 S5 的选票成为 Leader。

Case 2: Leader 试图提交之前任期的日志

如图所示的状况，在任期 2 时记录仅写在 S1 和 S2 两个节点上，因为某种原因，任期 3 的 Leader S5 并不知道这些记录，S5 创立了本人的三条记录而后宕机了，而后任期 4 的 Leader S1 被选出，S1 试图与其它服务器的日志进行匹配。因而它复制了任期 2 的日志到 S3。

此时 index=3 的记录时是不平安的。

因为 S1 可能在此时宕机，而后 S5 可能从 S2、S3、S4 取得选票成为任期 5 的 Leader。一旦 S5 成为新 Leader，它将笼罩 index=3-5 的日志，S1-S3 的这些记录都将隐没。

咱们还要须要一条新的规定，来解决这种状况。

新的 Commit 规定

新的选举不足以保障日志平安，咱们还须要持续批改 commit 规定。

Leader 要提交一条日志：

• 日志必须存储在超过半数的节点上；
• Leader 必须看到：超过半数的节点上还必须存储着至多一条本人任期内的日志；

如图，回到下面的 Case 2: 当 index = 3 & term = 2 被复制到 S3 时，它还不能提交该记录，必须等到 term = 4 的记录存储在超过半数的节点上，此时 index = 3 和 index = 4 能够认为是已提交。

此时 S5 无奈博得选举了，它无奈从 S1-S3 取得选票。

联合新的选举规定和 commit 规定，咱们能够保障 Raft 的安全性。

日志不统一

Leader 变更可能导致日志的不统一，这里展现一种可能的状况。

能够从图中看出，Raft 集群中通常有两种不统一的日志：

• 缺失的记录(Missing Entries)；
• 多进去的记录(Extraneous Entries)；

咱们要做的就是清理这两种日志。

修复 Follower 日志

新的 Leader 必须使 Follower 的日志与本人的日志保持一致，通过：

• 删除 Extraneous Entries；
• 补齐 Missing Entries；

Leader 为每个 Follower 保留nextIndex：

• 下一个要发送给 Follower 的日志索引；
• 初始化为：1 + Leader 最初一条日志的索引；

Leader 通过 nextIndex 来修复日志。当 AppendEntries RPC 一致性查看失败，递加 nextIndex 并重试。如下图所示：

对于 a：

• 一开始nextIndex= 11，带上日志 index = 10 & term = 6，查看失败；
• nextIndex= 10，带上日志 index = 9 & term = 6，查看失败；
• 如此重复，直到nextIndex= 5，带上日志 index = 4 & term = 4，该日志当初匹配，会在 a 中补齐 Leader 的日志。如此往下补齐。

对于 b：
会始终查看到nextIndex= 4 才匹配。值得注意的是，对于 b 这种状况，当 Follower 笼罩不统一的日志时，它将删除所有后续的日志记录（任何无关紧要的记录之后的记录也都是无关紧要的）。如下图所示：

4. 解决旧 Leader

实际上，老的 Leader 可能不会马上隐没，例如：网络分区将 Leader 与集群的其余部分分隔，其余部分选举出了一个新的 Leader。问题在于，如果老的 Leader 从新连贯，也不晓得新的 Leader 曾经被选出来，它会尝试作为 Leader 持续提交日志。此时如果有客户端向老 Leader 发送申请，老的 Leader 会尝试存储该命令并向其它节点复制日志——咱们必须阻止这种状况产生。

任期就是用来发现过期的 Leader(和 Candidates)：

• 每个 RPC 都蕴含发送方的任期；
• 如果发送方的任期太老，无论哪个过程，RPC 都会被回绝，发送方转变到 Follower 并更新其任期；
• 如果接管方的任期太老，接管方将转为 Follower，更新它的任期，而后失常的解决 RPC；

因为新 Leader 的选举会更新超过半数服务器的任期，旧的 Leader 不能提交新的日志，因为它会分割至多一台多数派集群的节点，而后发现自己任期太老，会转为 Follower 持续工作。

这里不打算持续探讨别的极其状况。

5. 客户端协定

客户端只将命令发送到 Leader：

• 如果客户端不晓得 Leader 是谁，它会和任意一台服务器通信；
• 如果通信的节点不是 Leader，它会通知客户端 Leader 是谁；

Leader 直到将命令记录、提交和执行到状态机之前，不会做出响应。

这里的问题是如果 Leader 宕机会导致申请超时：

• 客户端从新收回命令到其余服务器上，最终重定向到新的 Leader
• 用新的 Leader 重试申请，直到命令被执行

这留下了一个命令可能被执行两次的危险——Leader 可能在执行命令之后但响应客户端之前宕机，此时客户端再去寻找下一个 Leader，同一个命令就会被执行两次——这是不可承受的！

解决办法是：客户端发送给 Leader 的每个命令都带上一个惟一 id

• Leader 将惟一 id 写到日志记录中
• 在 Leader 接受命令之前，先查看其日志中是否曾经具备该 id
• 如果 id 在日志中，阐明是反复的申请，则疏忽新的命令，返回旧命令的响应

每个命令只会被执行一次，这就是所谓的线性化的要害因素。

6. 配置变更

随着时间推移，会有机器故障须要咱们去替换它，或者批改节点数量，须要有一些机制来变更系统配置，并且是平安、主动的形式，无需进行零碎。

系统配置是指：

• 每台服务器的 id 和地址
• 系统配置信息是十分重要的，它决定了多数派的组成

首先要意识到，咱们不能间接从旧配置切换到新配置，这可能会导致矛盾的多数派。

如图，零碎以三台服务器的配置运行着，此时咱们要增加两台服务器。如果咱们间接批改配置，他们可能无奈齐全在同一时间做到配置切换，这会导致 S1 和 S2 造成旧集群的多数派，而同一时间 S3-S5 曾经切换到新配置，这会产生两个集群。

这阐明咱们必须应用一个两阶段 (two-phase) 协定。

如果有人通知你，他能够在分布式系统中一个阶段就做出决策，你应该十分认真地询问他，因为他要么错了，要么发现了世界上所有人都不晓得的货色。

独特统一(Joint Consensus)

Raft 通过独特统一 (Joint Consensus) 来实现两阶段协定，即：新、旧两种配置上都取得多数派选票。

第一阶段：

• Leader 收到 Cnew 的配置变更申请后，先写入一条 Cold+new 的日志，配置变更立刻失效，而后将日志通过 AppendEntries RPC 复制到 Follower 中，收到该 Cold+new 的节点立刻利用该配置作为以后节点的配置；
• Cold+new 日志复制到多数派节点上时，Cold+new 的日志已提交；

Cold+new 日志已提交保障了后续任何 Leader 肯定有 Cold+new 日志，Leader 选举过程必须取得旧配置中的多数派和新配置中的多数派同时投票。

第二阶段：

• Cold+new 日志已提交后，立刻写入一条 Cnew 的日志，并将该日志通过 AppendEntries RPC 复制到 Follower 中，收到 Cnew 的节点立刻利用该配置作为以后节点的配置；
• Cnew 日志复制到多数派节点上时，Cnew 的日志已提交；在 Cnew 日志提交当前，后续的配置都基于 Cnew 了；