使用链接简化 Raft

Raft 是一种共识算法，用于决定在复制状态机上执行的命令序列。 Raft 以其可理解性而闻名（相对于其他共识算法，如 Paxos），但该协议的某些方面仍然需要仔细处理。例如，确定领导者何时可以安全地提交来自前任领导者的命令，或者服务器何时可以安全地删除或覆盖其日志中的命令。最近，Tendermint、Casper FFG 和 HotStuff 等拜占庭协议协议已经利用链的抽象来决定一系列命令。这不是通常的可变复制日志方法，如 Multi-Paxos、Raft 和 PBFT 等协议所使用的那样。之前，我们使用这种基于链的方法描述了一个简单的轮换领导者共识算法 Benign HotStuff。在今天的帖子中，我们通过使用链接描述 Raft 协议来继续研究基于链的共识方法。我们将由此产生的协议称为 Chained Raft，它为我们提供了一个新的（可以说是更简单的）镜头，通过它可以更广泛地查看 Raft 和共识问题。重要的是，从可变状态到不可变状态的切换可以让 Raft 更容易推理。协议内的读取永远不会过时，我们避免了何时可以安全覆盖状态的棘手问题。我们绝不是第一个使用不变性来降低分布式系统复杂性的人。 Raft 和 Chained Raft 的目的是实现状态机复制。具体来说，一组服务器每个维护一个状态机的副本，共识协议必须确保每个状态机接收相同的命令序列。两种算法都采用相同的高级方法来选举一台服务器作为领导者。客户端向领导者发送命令，领导者使用 AppendEntries RPC 将它们复制到大多数服务器上，然后再将它们提交到其状态机并回复客户端。当领导者失败时，使用 RequestVotes RPC 选择另一个服务器作为领导者。这个过程涉及到大多数服务器，以确保新领导者拥有前任领导者执行的所有命令的副本。就像 Raft 一样，Chained Raft 发生在一系列条款中，每个条款至多有一个领导者。每个服务器存储其当前期限，该期限最初为 0，并随时间增加。一个块包含一个命令（实际上是一批命令）和一个指向前一个块的指针。 Chained Raft 中的区块类似于 Raft 中的日志条目。请注意，与 Raft 中的日志条目不同，Chained Raft 中的块不包含索引或术语。

每个服务器都从一个空的创世区块开始，并随着时间的推移添加区块以形成一个链。这个链类似于 Raft 中的日志。下面是一个示例链，它从创世区块（以灰色显示）开始，然后是三个包含命令 A、B 和 C（以蓝色显示）的区块。新块由当前领导者创建，然后使用 AppendEntries RPC 将这些块附加到其追随者的链中。领导者只有在确保所有未来的领导者都这样做时才能向其状态机提交命令。与 Raft 的日志不同，这些链是不可变的，因此服务器永远不会删除或覆盖块。当从领导者失败中恢复时，链可能会分叉成多个分支（甚至子分支），但是，只会提交一个分支。下面的链已经分叉成两个分支，因此只能提交 D 或 E 和 F 之一。链的头部是最近添加的块（也称为尖端）。该区块不会被链中的任何其他区块指向。换句话说，头始终是“树”的叶子之一。最初，每条链的头部是创世块，每次添加一个块（或块序列）时都会更新头部。服务器使用头部来跟踪哪个链分支是最新的。每个服务器维护一个提交标记。提交标记指向链中可以安全提交给状态机的最高块（离创世块最远）。这类似于 Raft 中的提交索引。提交标记最初设置为创世块，并随着时间的推移沿着链前进。从创世区块到提交标记的路径上的所有区块都可以安全提交。在下面的示例中，只能提交命令 A。如果存在从块 $b$ 到块 $b'$ 的路径，那么我们说块 $b$ 扩展了块 $b'$。因此，所有区块都扩展了创世区块。

除了当前期限外，每个服务器还存储最后一个附加期限，即服务器上次将区块附加到其链时所处的期限。换句话说，这是附加当前头部时的术语。最后附加的项最初为 0，并随时间增加。最后附加的术语始终等于或小于当前术语。 Chained Raft 中的最后一个附加项与 Raft 中的最后一个 log 项具有相同的功能。领导者通过首先创建一个包含命令和指向其当前头部的指针的新块来提交命令，新创建的块被添加到领导者的链中，并且头部被更新为新块。然后领导者使用 AppendEntries RPC（如在 Raft 中）将此块复制到其追随者。请注意，Raft 的 AppendEntries RPC 中的日志条目被块替换。 Raft 的 AppendEntries RPC 中的先前日志索引和先前日志项可以省略，因为块指针现在具有相同的用途。在检查 AppendEntries RPC 的条款后，如果追随者已经拥有第一个新区块所指向的区块，则它会将接收到的区块添加到其链中。否则，follower 将回复 false，leader 将重试 AppendEntries RPC，这次也是使用前一个块。这个过程将一直持续到追随者成功添加新区块。每当追随者向链中添加新块时，其头部就会相应地更新。如果这是这个追随者第一次在这个任期内附加区块，那么它也会更新最后一个附加的任期。 Raft 中领导者用来跟踪追随者日志状态的下一个索引和匹配索引被类似的下一个标记和匹配标记替换。一旦领导知道大多数服务器已经附加了一个块，就可以更新提交标记。更新的提交标记包含在后续的 AppendEntries RPC 中。下面的示例显示了三个服务器的链。第一个服务器是一个领导者，它添加了一个新块（命令 C）但还没有将 AppendEntries RPC 发送给它的追随者。下面显示了领导者与追随者完成 AppendEntries RPC 后的相同示例。两个追随者现在都有一个命令 C 的副本，领导者因此更新了它的提交标记。追随者还了解到，由于领导者在 AppendEntries RPC 中包含了其提交标记，因此可以提交前一个块（命令 B）。 Chained Raft 中的领导人选举的工作方式与 Raft 中的工作方式大致相同。当追随者成为候选人时，它为自己投票并向所有服务器发送 RequestVote RPC。 RequestVote RPC 不包括最后一个日志术语和最后一个日志索引，而是包括候选人的头部和最后一个附加术语。

像 Raft 一样，只有当追随者在这个任期内还没有为其他候选人投票并且候选人的链（或日志）至少与追随者的链（或日志）一样时，追随者才会投票给候选人。候选人的链至少是最新的，前提是：候选人的最后附加任期大于追随者的最后附加任期，或者候选人的最后附加任期等于追随者的最后附加任期，并且：一旦候选人收到来自大多数追随者然后成为领导者。下面的示例显示了三个服务器的状态。只有第一和第二服务器可以成为领导者。第一个服务器可以接收来自任何服务器的投票。第二台服务器可以收到来自第三台服务器的投票，因为它具有更大的最后附加期限，但不会收到来自第一台服务器的投票。第一台服务器或第二台服务器都不会投票给第三台服务器。考虑如果第二台服务器成为领导者，接下来会发生什么。新的领导者将下一个块（命令 D）添加到它的头部（命令 B）并使用 AppendEntries RPC 复制它。如下所示，这将在第一台服务器上创建一个分支。 A newly elected leader may have uncommitted blocks from the previous leaders.在这种情况下，当它添加当前术语中的第一个新块时，它使用 AppendEntries RPC 将它们复制到跟随者。按照 Raft 中的惯例，一旦这个新块被复制到大多数服务器上，领导者可以更新其提交标记，从而也提交来自以前领导者的块。请注意，领导者因此将始终发送包含至少一个来自其当前任期的新块的 AppendEntries RPC。

每台服务器上的链都会随着时间的推移而增长。实际上，一旦提交标记通过链中的一个分叉，其他分支就可以安全地进行垃圾回收。这些分支，应该是非常罕见的，代表了Chained Raft的“未走的路”。这些分叉仅在领导者失败并且新领导者的链不包含失败领导者添加的所有块时才会发生。重要的是要注意，这些“丢失的块”在失败之前不可能由前任领导提交。考虑下面的例子。在提交标记通过分叉之前，链包括两个分支，命令 D 和命令 E/F。稍后，一旦提交标记已更新为命令 E，则可以安全地删除包含命令 D 的分支。 Raft 论文（图 3）确定了五个有助于证明 Raft 安全性的属性。 Chained Raft 的类似属性如下： 换句话说，领导者只会沿着链向前移动他们的头。请注意，这与 Raft 的 leader append-only 略有不同，后者指出“leader 永远不会覆盖或删除其日志中的条目；它只附加新条目。”。在 Chained Raft 中，所有服务器只附加新块。日志匹配属性：如果两条链包含相同的块，那么从创世块到两条链上的块的路径将相同。这是通过要求服务器仅在它们已经拥有新块指向的块时才附加新块来实现的。领导者完整性：如果在给定期限内提交了一个块，那么所有更大期限的领导者的头要么是该块，要么将扩展该块。

考虑一个区块 $b$，它首先由领导者在 $t$ 期间提交。至少大多数服务器在某个时候都会有最后附加的 $t$ 条款和 $b$ 或扩展 $b$ 的头。我们将在 $t$ 之后的项上使用归纳证明来显示领导者的完整性。基本情况 考虑下一项 $t+1$ 会发生什么。如果在 $t+1$ 任期内有领导者，那么它会收到来自大多数服务器的投票。至少有一个最后附加的任期为 $t$ 并且头部也是 $b$ 或扩展 $b$ 的服务器必须投票给领导者。由于领导者的最后附加条款不能大于 $t$，领导者必须具有相同的最后附加条款 ($t$) 和等于服务器头部或扩展它的头部。因此，如果术语 $t+1$ 有一个领导者，那么 $b$ 将出现在从创世块到领导者头部的路径中。归纳案例 考虑在某个项 $t+k$ 中会发生什么。我们假设领导者完整性在 $t+k-1$ 期间成立。如果 $t+k$ 有领导者，那么它会收到大多数服务器的投票。至少有一个服务器曾经有最后一个附加的任期 $t$ 和一个头也是 $b$ 或扩展 $b$ 必须投票给领导者。此后的任何领导者都将添加扩展 $b$ 的块。因此，如果术语 $t+k$ 有一个领导者，那么领导者的头部将是 $b$ 或扩展它。状态机安全：复制状态机的每个副本都以相同的顺序接收相同的命令。结合之前的属性以及服务器仅在领导者指示时提交命令的事实，为我们提供了状态机安全性。与 Raft 一样，Chained Raft 保证同步后的活跃度，前提是至少大多数服务器已启动并可靠地通信（注意事项适用）。

我们现在将跳过的活性证明与 Raft 和 Chained Raft 大致相同，但是，以下想法很有用。从 leader append-only 属性我们知道，如果两台服务器具有相同的最后一个附加项，那么它们的头部要么相同，要么一个头部扩展另一个。这意味着对于任何一对服务器，至少有一个服务器可以投票给另一个，因此任何多数中的至少一个服务器可以被选为领导者。 Benign HotStuff 是一个轮换领导者协议，其中每个领导者（也称为 Benign HotStuff 中的主要）在将领导权移交给下一个服务器之前添加一个区块。相比之下，Chained Raft 是一个稳定的领导者协议，领导者添加区块直到它失败（或者至少直到另一个服务器认为它失败了）。在良性 HotStuff 中，leader 的角色以循环方式在服务器之间轮换，而在 Raft 和 Chained Raft 中，服务器必须获得大多数服务器的投票才能成为领导者。 Benign Hotstuff 采用“Raft 风格”的方法来达成共识，即为区块的生命周期分配条款，因此区块不会像“Paxos 风格”共识那样被后续领导者“提升”为更高的条款。 Chained Raft 通过仅存储头部的术语（使用最后一个附加术语）来避免将什么术语分配给先前术语中的块的问题。与 Benign HotStuff 一样，Chained Raft 要求领导者将未提交的块（在 Benign Hotstuff 中称为状态转移）复制到其追随者，同时在当前任期内添加新块。这个限制有助于简化这两种算法，因为这意味着最近添加的块，头，总是来自最新的领导者。请注意，Benign HotStuff 中的 proposal 消息类似于 Chained Raft 中的 AppendEntries RPC 请求，Benign HotStuff 中的投票消息类似于 AppendEntries RPC 响应和 RequestVote RPC 响应的组合。 Benign HotStuff 为每个块存储一个 term，而 Chained Raft 只跟踪当前 head 的 term（使用最后一个附加的 term）。

我们已经使用 append-only 链而不是可变日志来描述 Raft。有趣的是，Chained Raft 和 Raft 是非常相似的协议。 Raft 可以使用链来自然地表达，因为它已经严格按顺序决定命令（与其他一些共识协议如 Multi-Paxos 不同）。所以你怎么看？ Chained Raft 比原来的 Raft 协议简单吗？您是否有兴趣看到其他基于日志的共识算法，例如使用链描述的 Multi-Paxos 或 Fast Paxos？在推特上告诉我们您的想法。确认。我们要感谢 Kartik Nayak 对这篇博文的反馈。