关于分布式:分布式状态机共识协议-Copilot

前言

定义 slowdown
为什么现有的共识协定无奈容忍 slowdown
Copilot 如何解决 slowdown

设计

模型
排序
- Client 同时发送指令至 pilot 与 copilot
- Pilot 提议指令与其初始依赖
- 节点回复 FastAccept
- Pilot 尝试通过 fast path 来 commit 该指令
- Pilot 在 Accept 阶段最终确定依赖
执行
- Copilot 最终合并后的指令程序
- 依序执行
- 去重执行并回复
Fast Takeover
- entry 内容的复原过程
- 触发 Fast Takeover
额定设计
Copilot 能达到 1-slowdown-tolerant 的起因

优化

Ping-Pong Batching
Null Dependency Elimination

总结

论文原文：Tolerating Slowdowns In Replicated State Machines Using Copilots
以下内容是对这篇论文的 浏览总结 ，以及局部 重要章节（§3 Design、§5 Optimizations）的翻译。

现有的分布式状态机共识协定，不管其是何种流派，何种实现，都在模型中将节点状态形象为仅有“在线”与“下线”两种状况。然而在实践上，节点状态并非只有这两种互斥的状态 —— 节点可能因配置谬误，节点侧网络问题，局部硬件呈现问题，垃圾回收事件，以及其它很多起因而导致响应速度变慢（slowdown）。因为现有的共识算法没有很好地解决这一状态，零碎内一个节点 slowdown 可能导致整个零碎的响应速度变慢。Copilot 协定旨在解决这一问题：它能够在任何状况下能够容忍零碎中 1 个节点产生 slowdown（1-slowdown-tolerant）。

要想解决这一问题，首先要对 slowdown 进行明确的定义。

首先要定义一个节点的处理速度。一个节点从收到一条音讯开始，到其解决这条音讯结束，将回复送出为止，这段时间的长短就是一个节点的处理速度。这段时间不蕴含音讯在网络链路上的传输工夫，仅蕴含音讯在节点本机处理所需的工夫。假如一个节点解决一条音讯的典型工夫为 1ms，而设置超时阈值 t = 10ms，那么如果该节点解决一条音讯破费了大于 10ms，就阐明该节点呈现了 slowdown。出错（failed）的节点肯定是 slowdown 的，但 slowdown 的节点不肯定 failed—— 它只是响应速度变慢，而不是进行响应。

上面定义 s-slowdown-tolerance。当一个零碎中有 s 个节点产生 slowdown 时，零碎仍能失常地提供服务，那么这个零碎就是 s-slowdown-tolerance。假如一个分布式状态机零碎有节点集 {r1, …, rs, …, rn}，且依据目前的“slowdown”定义排序，其中 {r1, …, rs} 是最慢的节点。定义以后整个零碎的处理速度为 T，并定义 T’ 为将零碎中节点 {r1, …, rs} 全副替换为 rs + 1 时整个零碎的处理速度。如果 T 与 T’ 的差值靠近 0，那么该零碎就是 s-slowdown-tolerance。换句话讲，就是零碎中呈现 s 个节点 slowdown 不会影响整个零碎的处理速度。

一个分布式状态机零碎在解决一条客户端指令时，如果在处理过程中的任意工夫点，只有一条门路可走，那么该零碎就存在“单点故障”的可能性 —— 在这点处负责解决的节点产生 slowdown 会影响整个节点的处理速度。

Multi-Paxos

在 Multi-Paxos 零碎中，所有客户端指令会通过 leader 解决，而 leader 可能会 slowdown 甚至 failed，此时零碎的整体处理速度就会升高。

EPaxos

在 EPaxos 零碎中，客户端指令会通过与之通信的节点解决，如果此节点 slowdown，零碎的整体处理速度就会升高。

依据上一节，只有保障在解决一条客户端指令过程中的任意工夫点，都有大于等于 s + 1 条门路解决该条客户端指令，那么该零碎就是 s-slowdown-tolerant。

Copilot 容忍一个节点 slowdown，因而须要在解决客户端指令时有两条门路。

本节内容是对论文 §3 Design 的翻译。

Copilot 的设计外围是同时应用两个 leader 互为冗余地解决每一条 client 指令。两个 leader 为 pilot (P) 与 copilot (P’)。

crash failure model – 出错的节点会进行发送与相应信息，无拜占庭谬误
异步 – 执行指令与传递音讯所需的工夫没有限度，音讯可能会提早、乱序甚至失落
容忍 2f + 1 个节点中呈现 f 个谬误并保障指令执行的线性程序
可容忍 1 个节点产生 slowdown

在 Copilot 排序中，pilot 与 copilot 都会收到 client 的指令并各自放入其 log 记录中，两者协调后失去最终程序。pilot log 与 copilot log 通过依赖进行排序。依赖是指：应在执行某条指令前实现执行的指令。在提议阶段，pilot 与 copilot 会提出被排序指令的初始依赖。节点要么批准收到提议中的依赖程序，要么回复其认为正确的依赖程序。最终，每一条指令都会有其最终的依赖，以用于被执行。最终依赖可能会成环，这将在被执行时解决。执行时，pilot 与 copilot 的 log 记录通过上述排序过程被整合，在成环的依赖中 pilot 的指令会被优先执行以突破环。Copilot 排序会将指令与最终依赖长久化至其它节点以用于谬误复原。与 EPaxos 相似，每次排序操作都会通过 FastAccept 阶段，又是会通过 Accept 阶段。以下是排序的具体过程（临时省略 fast takeover 与 view-change）。

每个 client 都领有 ID：cliid。client 会为每一个指令调配一个递增且不反复的 ID：cid。发送指令时，client 也会附加 cliid 与 cid 以标识指令，以便在执行阶段去重。

当一 pilot 收到 client 发来的一条指令时会将其追加至本身 log 记录中，同时将最初收到的来自另一 pilot 的指令作为该指令的初始依赖。该 pilot 向其它节点（包含本人与另一 pilot）发送 FastAccept 音讯提议这条指令与其初始依赖。

当一节点收到 FastAccept 音讯时，它会查看收到的指令初始依赖是否与其之前已 Accept 的其它 entry 抵触。若不抵触，节点会回复此 FastAcceptOk。若抵触，节点会回复其认为正确的依赖程序。

compability check：

对于两个依赖，如果其中至多有一个的 entry 位于另一个的 entry 之后，则两依赖不抵触。在上图 a 中示意了抵触与未抵触的依赖：依赖于 P.1 的 P’.1 与依赖于 P’.1 的 P.2 没有抵触，因为 P.2 位于 P’.1 之后。依赖于 P.2 的 P’.3 与依赖于 P’.2 的 P.3 抵触，因为它们都不位于对方 entry 之后。因为抵触的依赖可能导致指令执行程序不统一，所以必须防止，如有节点会先执行 P.3 再执行 P’.3，有节点会反之。

节点会应用 compatibility check 查看 pilot 提供的初始依赖是否抵触。依赖于 P’.j 的 entry P.i 与 P.i 与 P’.j 之前 accept 的 entry 不抵触，所以 compatibility check 只须要查看该依赖是否与另一 pilot 之后的 log 是否抵触。若节点已 accept 另一 pilot 的 entry P’.k (k> j)，且 P’.k 依赖位于 P.i 之前的 entry，则依赖抵触。

如果节点：

还未收到之后的对于之后 entry 的依赖
已收到之后的 entry P’.k，但其依赖为 P.i 或在其后，如 P’.j, P.i, … , P’.k

它会认为依赖不抵触，以 FastAcceptOk 回复，而雷同的规定会阻止另一 pilot 之后的依赖抵触。否则节点会回复 FastAcceptReply 并附加其收到的最初一条来自另一 pilot 的 entry。

与 EPaxos 相似，若 pilot 收到至多 f + (f + 1) / 2（fast quorum，包含该 pilot 自身）个节点的 FastAcceptOk 回复，就足以从之后可能产生的节点谬误中复原。此时 pilot 会通过 fast path 间接 commit 该指令与其依赖，向其它节点发送 commit 音讯（无需期待回复）。

可能有两种起因导致 pilot 无奈收到 fast quorum 的 FastAcceptOk 回复：

有其它节点出错，导致残余节点有余 fast quorum
有其它节点检测到依赖抵触，回复 FastAcceptReply 与其认为正确的依赖程序

不管那种起因，pilot 都须要期待有至多 f + 1 个节点回复，能力进入下一步。

pilot 将上一步中收到的举荐依赖（包含本身，且 FastAcceptOk 即初始依赖）以升序排序，并抉择第 f + 1 个举荐依赖作为最终依赖。抉择第 f + 1 个是为了保障该依赖与任何曾经 commit 的命令有交加以确保线性，不抉择第 f + 1 个之后的依赖是为了避免之后的依赖与该依赖有依赖关系。

之后 pilot 应用 Accept 音讯发送最终依赖到其它节点。最终依赖可能会导致成环，但这能够承受，因为执行时所有节点都会依照雷同的办法突破环。其它节点收到该最终依赖后回复 AcceptOk。当 pilot 收到 f + 1 个 AcceptOk 回复后（包含其自身），即可 commit 该命令与最终依赖。

节点应用两 pilot 的 log 合并后的程序执行。合并后的 log 中，每个 client 指令都会呈现两次。节点会在发现已执行过的指令时跳过该指令。执行指令后，pilot 与 copilot 都会将后果返回给 client。

最终合并后的指令程序由以下因素决定：

各 pilot 内各自的 log 程序
两 pilot 指令间的依赖关系
pilot 优先级，用于解决成环依赖

最终程序蕴含各 pilot 内各自的 log 程序。上图，P.0 < P.1 < P.2。该程序可能成环
当依赖不成环时，依赖程序即为最终程序。上图，P.1 < P’.0 < P’.1 < P.2
当依赖成环时，最终程序由 pilot 优先级决定，pilot 的指令会在 copilot 的指令前执行。上图，P.4 < P.5 < P’.5

各节点在失去每条指令的最终依赖后就会依照雷同的程序执行。当一条指令 commit，且对应 entry 前的所有指令已都被执行后，节点会执行这条指令。

以下规定决定何时能够执行一条 entry 为 P.i、依赖为 P’.j 的指令：

P.i 已 commit
P.(i – 1) 已被执行
P’.j 已被执行，或 P.i 与 P’.j 成环且 P 为 pilot 指令

节点能够乱序承受指令的 commit 音讯，如节点可能先得悉一指令 commit，之后再得悉该指令的依赖 commit。为了达到所有指令的执行程序统一，节点必须在执行一条指令前执行过该指令的依赖以及该指令 entry 前的所有指令。例如在执行一条 entry 为 P.i、依赖为 P’.j 的指令时，须要：

P.i 之前 entry 的所有指令都已被执行
P’.j 已被执行
P’.j 之前 entry 的所有指令都已被执行

能力执行 P.i。Copilot 的 Fast Takeover 机制能够避免失常运行的 pilot 期待 slowdown 的 pilot。

若排序过程按失常状况执行，每一条指令在 log 合并后都会呈现两次。节点只会在一条命令呈现第一次时执行该命令。cliid 与 cid 组成的元组在这里能够用来标识指令。若该节点是 pilot 或 copilot，执行实现一条命令后会将后果返回给客户端。客户端收到一个返回的后果后，会疏忽之后由另一 pilot 返回的后果。

为了达到执行程序统一，有时一 pilot 须要期待另一 pilot 的 commit 音讯。失常工作的 pilot 期待另一 slowdown 的 pilot 会耗费大量工夫，因而须要 Fast Takeover 机制。

每个节点 log 中的每一个 entry 都会附有一 ballot number。与 Paxos 的 proposal number 相似，Copilot 协定过程中的每条音讯都会带有 ballot number。通过这些序列号能够让 pilot 平安地进行与 Paxos 相似的所有权竞争的 Fast Takeover。

当一个节点被选举为 pilot 或 copilot，所有节点中该 pilot log 的 entry ballot number 都会被设置为 b。节点只会承受附加 ballot number 大于等于对应 entry 的 ballot number 的音讯。在 pilot 失常工作时，其收回的所有音讯的 ballot number 值都为 b。

当一 pilot 发现另一 pilot slowdown，心愿代替其实现某 entry 的 commit 时，失常工作的 pilot 会向所有其它节点发送对于该 entry 的 Prepare 音讯并附加大于 b 的 ballot number 值 b’。如果其它节点确认 b’ 大于该 entry 本来的 ballot number 值 b 时会回复 PrepareOk 音讯，并将该 entry 的 ballot number 值设置为 b’。PrepareOk 音讯中会蕴含该 entry 目前的状态（not-accepted、fast-accepted、accepted 或 committed），同时蕴含该 entry 之前最大的 ballot number、指令与依赖。

在失常 pilot 发送 Prepare 音讯后，它须要期待接管到至多 f + 1（蕴含它自身）个 PrepareOk 音讯。如果通过某 PrepareOk 音讯得悉该指令已被 commit，该 pilot 会立刻进行期待并 commit 该指令与其依赖，完结 Fast Takeover 过程。否则，该 pilot 会通过如下过程抉择该指令与其依赖，并通过 Accept 音讯发送，期待 f + 1 个 AcceptOk 回复，而后继续执行。

Fast Takeover 与 view-change 都应用了本过程，以正确复原任意可被 commit 并执行的 entry。本过程十分复杂，细节可参阅 Technical Report TR-004-20。

在附加正确 ballot number 的 PrepareOk 回复汇合中：

若有至多一个回复 entry 状态为 accepted，则采纳该回复的指令与依赖
当有小于 (f + 1) / 2 个回复状态为 fast-accepted 时，设置该 entry 为 no-op 且依赖为空
当有大于等于 f 个回复状态为 fast-accepted 时，采纳该回复的指令与依赖

在第一种状况中，该 entry 可能曾经被 commit 并附加了更小的 ballot number，所以必须采纳原值与依赖。在第二种状况中，该 entry 不可能已被 commit，所以采纳 no-op 是平安的。在第三种状况下，该 entry 可能曾经被 commit 并附加了更小的 ballot number，所以能够采纳原值与依赖，因为 f 个 fast-accepted 回复与该 pilot 自身已形成了一个 majority quorum。

除上述情况外，还有一种可能，有大于等于 (f + 1) / 2 且小于 f 个回复状态为 fast-accepted。这种状况下，该 entry 可能已被 commit，也可能有另一 pilot 已提案另一与之抵触的指令，且有其它节点已收到了该 fast-accept。为了确定状况，发动这次复原过程的节点须要查看另一 pilot log 中是否存在抵触的 entry。若发现抵触的 entry 但还未 commit，则对此 entry 反复整个上述过程，最终平安地实现复原。

当 pilot 得悉一条 entry 为 P.i、依赖为 P’.j 的指令被 commit 时，如果：

P.i 之前 entry 有指令未被 commit
P’.j 未被 commit
P’.j 之前 entry 有指令未被 commit

pilot 就会启动一个 timer。若 timer 达到了 takeover-timeout 且仍有执行 P.i 所需的指令没有被 commit，该 pilot 就会进行期待，被动接过 commit 所需指令与排序的工作，fast takeover 另一 pilot log 中所有可能为该指令执行前置条件的 entry。在该 Copilot 实现中，所有 entry 的 fast takeover 过程是被批量合并且是并行的。

如果 takeover-timeout 设置的工夫太短，就会产生没有必要的谬误 fast takeover，从而导致 proposal 竞争。proposal 竞争问题能够应用指数退却随机化 timeout 来防止。为了防止必要的谬误 fast takeover，能够将 takeover-timeout 设置为一个中等大小的值（如 10ms）。中等大小的 takeover-timeout 可能导致处理速度变慢，然而应用 Null Dependency Elimination 能够防止这个问题。

Fast takeover 与 leader 选举看起来非常相似，它们都是通过期待某节点相应时超时触发的。Leader 选举是因为某节点无奈在设定 timeout 内收到另一节点的某种音讯（如心跳或新指令提议）触发的。然而有时尽管 leader 仍可失常发送心跳，但其理论解决指令的速度会因为一些因素而变慢。Fast takeover 是由指令解决门路上某点的 slowdown 触发的，配合指令同时有两条互不依赖的解决门路，能够在产生 slowdown 时总会由较快的 pilot 解决实现指令。当一个 pilot slowdown 时，另一个 pilot 会通过 fast overtake 解决所有指令，无需期待较慢的 pilot。

本节未提到的 Copilot 设计都与其它分布式状态机的设计统一。

保障指令仅被执行一次是通过查看 cliid 与 cid 实现的。记录一条指令已被执行一次的 cliid 与 cid 容器会在第二次遇到雷同指令时清空。

对于后果非确定的指令（如波及随机数生成，每次执行后果都不同），能够由两 pilot 实现非确定局部（随机数生成），此时该指令的执行后果变为可确定的值，再进行排序与执行等操作。两 pilot 在实现非确定局部时可能不同，所以最终的指令可能的执行后果会有两个版本，但执行的去重机制能够保障只有一个后果无效。

与 Multi-Paxos 的 leader 选举相似，pilot 与 copilot 选举应用 view-change。view-change 选举失去的新的 pilot 与 copilot 应用之前提到的 entry 对应内容的复原过程。因为两 pilot 有各自独立的 log，在从新选举一个 leader 时另一 pilot 能够不间断地为 client 提供服务。在这个过程中，失常的 pilot 不会将另一 pilot 的 entry 作为依赖，所以能够始终在 fast path 上 commit，直到另一 pilot 选举结束。

Copilot 通过保障任何客户端指令在任意工夫节点都在两条不同的解决门路上。两条门路的处理速度不同，处理速度快的门路失去的后果必然先返回客户端。

当两 pilot 都为失常状态时，就算有最多 f 个其它节点 slowdown 时，1-slowdown-tolerant 仍成立，因为在 regular path 上 commit 只须要 f + 1 个节点回复。

当一 pilot 产生 slowdown 或出错时，另一个失常的 pilot 仍能够失常 commit 其 entry，如果有对 slowdown pilot 指令的依赖，失常 pilot 会执行 fast takeover 解决这个问题。在 slowdown 产生后，失常 pilot 会通过 fast takeover 迅速的解决对 slowdown pilot 指令的依赖，之后即可按失常流程持续解决。此时该分布式状态机的总体执行速度取决于此失常的 pilot，所以 1-slowdown-tolerant 成立。

本节内容是对论文 §5 Optimizations 的翻译。

当两个 pilot 都在失常运行时，如果几条指令同时以乱序达到两个 pilot，就可能因程序不统一导致无奈通过 compability check。Ping-Pong Batching 通过协调两 pilot 的提案程序从而防止上述情况，使提案总会通过 fast path 实现。

在 Ping-Pong Batching 过程中，各 pilot 会打包（batching）在肯定时间段内达到的指令。在此期间该 pilot 每收到一条指令都会将其放入本人的下一个 entry 中，因而打包后的指令会是一组间断的 entry。当该 pilot 收到另一 pilot 的 FastAccept 音讯，或达到设定的打包最长时间段（ping-pong-
wait timeout），就会完结以后的打包操作。

当两 pilot 都未呈现 slowdown 的失常状况下，打包操作会因收到另一 pilot 的 FastAccept 音讯完结。如此，两 pilot 的 FastAccept 会如 ping-pong 个别进行。Pilot 完结其对第一批指令的打包并发送 FastAccept 音讯，copilot 收到该音讯后也会完结打包并发送这批指令的 FastAccept 音讯，pilot 收到该音讯后又会完结其对第二批指令的打包并发送 FastAccept 音讯，如此往返。

上述流程能够保障每个 pilot 会在收回 FastAccept 前都会收到另一 pilot 的 entry 程序，因而能够防止收回有依赖抵触的音讯，因而其它节点在收到 FastAccept 音讯后进行的 compability check 都会胜利，使得每一次提案都能够在 fast path 上实现。

当有一 pilot 呈现 slowdown 时，另一 pilot 会在达到 ping-pong-
wait timeout 后完结打包操作。这防止了因一个 pilot 呈现 slowdown 导致整个零碎 slowdown。

当一 pilot 发现自己将要执行的指令有依赖位于另一 pilot log 中，且还未 commit，这时它会查看本身是否已执行过该依赖所对应的指令，若发现已执行过，则无需期待另一 pilot 的 commit 音讯，可间接跳过。满足以上条件的依赖称为 null dependency，该机制名为 Null Dependency Elimination。在 null dependency 呈现时，pilot 无需期待该未 commit 的依赖，因为该依赖不会对最终的执行后果产生影响，pilot 只需将该依赖标记为已执行而后持续。

当有一 pilot 呈现继续的 slowdown 时，Null Dependency Elimination 能够让失常的 pilot 省去 fast takeover 的步骤。因为 slowdown 的 pilot 的提案比失常的 pilot 慢，所以其 entry 都是 null dependency，失常 pilot 能够间接跳过期待。若一 pilot 在提案后才产生 slowdown，fast takeover 仍是必要的。在失常 pilot fast takeover 过 slowdown pilot 的提案后，就能够通过 Null Dependency Elimination 跳过期待产生 slowdown 的 pilot 了。因而 1-slowdown-tolerant 仍是成立的。

Copilot 协定借鉴了之前各协定的长处，其排序局部与 EPaxos 相似，fast takeover 过程与 Paxos 相似，pilot 选举与 Multi-Paxos 统一。同时，Copilot 排序不依赖客户端指令自身是否 interfere，而将指令达到工夫作为排序的惟一根据，这也减小协定的实现难度。通过文中提到的优化，Copilot 在无节点 slowdown 时尽管无奈达到 Multi-Paxos 或 EPaxos 性能程度，但仍有肯定竞争力。在有节点 slowdown 时，Copilot 是惟一能防止整个零碎速度收到影响的协定。综上，在抉择分布式状态机零碎的共识协定时，Copilot 协定不失为一个好的抉择。

前言

定义 slowdown

为什么现有的共识协定无奈容忍 slowdown

Copilot 如何解决 slowdown

设计

模型

排序

Client 同时发送指令至 pilot 与 copilot

Pilot 提议指令与其初始依赖

节点回复 FastAccept

Pilot 尝试通过 fast path 来 commit 该指令

Pilot 在 Accept 阶段最终确定依赖

执行

Copilot 最终合并后的指令程序

依序执行

去重执行并回复

Fast Takeover

entry 内容的复原过程

触发 Fast Takeover

额定设计

Copilot 能达到 1-slowdown-tolerant 的起因

优化

Ping-Pong Batching

Null Dependency Elimination

总结