共识解耦 Compartmentalized Consensus

在状态机复制系统中，人们试图通过引入更多的技术来提高系统的吞吐量。这些技术并不总是有帮助的。有些技术在某些情况下会提高系统性能，而有些技术在其他情况下会损害系统。

本文介绍了围绕着解耦和缩放的分块技术。解耦组件是指将组件分成若干个子组件，然后扩大子组件的规模。

在Compartmentizated共识协议中，有三个启发式方法。

启发式-1：将控制流与数据流解耦。
启发式-2：将不可扩展的节点与可扩展的节点解耦。
启发式-3：独立处理独立的命令。

MultiPaxos、Mencius和S-Paxos中应用的分隔技术。

Step 1: Proxy Leaders 代理 leaders

本文引入了一组至少 f+1 个代理领导者，如图4所示。leader 负责对命令进行排序，而代理领导者负责获得命令的选择并将选择的命令广播给副本。这种技术已经在 PigPaxos 中引入，称为中继节点。

在收到 2a 阶段消息后，代理领导者将其广播给接受者，收集 (f + 1)2b 阶段响应的法定人数，并通知 replicas 所选择的值。在没有代理领导者的情况下，领导者每条命令要处理 3f+4 条消息，但有了代理领导者，领导者只需处理2条。这使得领导者的吞吐量瓶颈大大降低。

Step 2: Multiple Acceptor Groups 多个接受者 Groups

用于选择第一条命令的acceptors 可以与用于选择第二条命令的acceptors 不相干。本文介绍了多个acceptors 组，每个acceptors 组有2f+1个acceptor。这在图5中得到了说明。日志条目在acceptors 组中被轮流分割。给定n个acceptors 组，当代理 leader 收到 slot s的第二阶段a消息时，它联系acceptors 组（i），其中（i）mod n≡s。

Step 3: Scaling Replicas

replicas 的某些方面是不能扩展的。例如，每个副本必须接收和执行每个状态机命令。这是不可避免的，增加更多的副本并不能减少这种开销。然而，回顾一下，对于每个状态机命令，只有一个副本必须将执行命令的结果发回给客户端。因此，在有n个副本的情况下，每个副本只需要发送（1/n）个命令的结果。如果我们增加复制体的数量，我们就会减少每个复制体必须发送的信息数量。这就减少了副本的负载，有助于防止它们成为吞吐量的瓶颈。这在图6中得到了说明。

分区的MultiPaxos每秒可处理20万条命令，比没有分区的MultiPaxos多8倍。

Step 4: Batching

Step 5: Batchers

分批处理是一种著名的技术，通过摊销处理命令的通信和计算成本来提高吞吐量。在没有分批的情况下，代理 leader 每条命令至少要处理 3f+4 条消息。然而，有了批处理，代理leader每 batch 必须处理3f+4条消息。

为了处理单个批次的 n 条命令，领导者必须接收 n 条消息并发送一条消息。理想情况下，它只需要接收一条消息和发送一条消息。这使得领导者成为潜在的吞吐量瓶颈。为了消除这个瓶颈，本文应用启发式1和启发式2，对领导者进行解耦。

leader 有两个责任：形成batches 和 排序batches 。我们通过引入一组至少f+1个batchers来解耦这两项职责，如图8所示。batchers 负责接收来自客户端的命令并形成batches ，而领导者则负责对batches 进行排序。

客户端将命令发送给一个随机选择的batcher。在从客户端接收到足够多的命令后（或超时过后），batcher将命令放在一个batches 中，并将其转发给领导者。当领导者收到一批命令时，它给它分配一个日志条目，形成一个2a 阶段消息，并将2a 阶段消息发送给代理 leader。在没有批处理程序的情况下，领导者必须在每一批n个命令中接收n条消息。有了批处理程序，领导者只需要接收一条。这要么减少了瓶颈领导者的负荷，要么完全消除了它的瓶颈。

Step 6: Unbatchers

在执行了一批n个命令后，一个 replica 必须向n个客户发送n个消息。因此，replica （像没有批处理程序的领导者）遭受的通信开销与命令的数量而不是批次的数量成线性。为了解决这个问题，本文应用启发式方法，将 replica 解耦，如图9所示。

复制体负责执行命令，而非批处理者负责将执行命令的结果发回给客户端。有了批处理、批处理者和非批处理者，区块化MultiPaxos能够每秒处理90万个命令。

Mencius without Compartmentalization

没有区块化的 Mencius

Mencius是MultiPaxos的一个变体，它试图通过使用一个以上的领导者来消除这个瓶颈。Mencius不是让一个领导者对日志中的所有命令进行排序，而是在多个领导者之间对日志进行轮流分区。当一个客户想要提出一个状态机命令x时，它向任何一个服务器发送x。收到命令x后，一个服务器s1扮演领导者的角色。它将命令x分配到一个槽（i）中，并向包括x和i在内的其他服务器发送2a阶段消息。在收到2a阶段消息后，服务器 si 扮演接受者的角色，并以2b阶段消息作为回复。

Mencius with Compartmentalization

区块化的 Mencius

我们可以通过解耦服务器来解决这个问题。与其部署一组重载的服务器，我们不如将Mencius看作是MultiPaxos的变体，并将其部署为一组提议者、一组接受者和一组复制者。这在图13中有所说明。现在，Mencius等同于MultiPaxos，但有以下关键区别。首先，每个提议者都是一个领导者，日志轮流在所有提议者之间进行分配。如果一个客户想提出一个命令，它可以把它发送给任何一个提议者。第二，提议者定期向对方广播他们的下一个可用时段。每个服务器都使用这些信息来衡量自己是否落后。如果是的话，它就在自己的空闲位置上选择空位。

为了支持分批处理，本文介绍了作为MultiPaxos的batchers 和 unbatchers 。在没有分区的情况下，Mencius在没有batchers 的情况下每秒可以处理30,000条命令，在有批处理的情况下可以处理200,000条。分区的Mencius在没有批处理的情况下每秒可以处理250,000条命令，在有批处理的情况下每秒可以处理850,000条命令。

S-Paxos

S-Paxos 将命令分发与命令排序分离——将控制与数据流分离——并在所有节点上分发命令分发。更具体地说，一个可以容忍 f 个错误的 S-Paxos 部署由 2f + 1 个服务器组成，如图 15 所示。每个服务器都扮演 MultiPaxos 提议者、接受者和副本的角色。它还扮演着传播者和稳定者的角色，这两个角色很快就会变得清晰起来。

尽管 S-Paxos 解除了 MultiPaxos leader 广播命令的职责，leader 仍然需要广播命令 id。换句话说，leader 不再是数据路径上的瓶颈，而是控制路径上的瓶颈。此外，传播器和稳定器是潜在的瓶颈。

我们可以通过划分 S-Paxos 来解决这些问题，类似于划分 MultiPaxos 的方式。 Paper 介绍了代理领导者、多个接受者组和更多副本。如图 17 所示。

讨论

Paper 测量了三种协议在具有 1、10、50、100、300、600、1000、2000 和 4000 个客户端的工作负载下的吞吐量和中值延迟。每个客户端在闭环中发出状态机命令。在发出另一个命令之前，它等待接收执行其最近提议的命令的结果。

实验结果如图 18 所示。在图 18a 中，我们看到了没有批处理的三种协议的中值延迟和吞吐量。MultiPaxos 每秒最多可以处理 25,000 个命令。分隔的 MultiPaxos 能够每秒处理大约 200,000 个命令，吞吐量提高了 8 倍。此外，在峰值吞吐量下，MultiPaxos 的中位延迟是 Compartmentalized MultiPaxos 的三倍。

图 18b 显示了三种批处理协议的中位延迟和吞吐量。有了 4,000 个客户端，MultiPaxos、Compartmentalized MultiPaxos 和非复制状态机分别达到每秒 200,000、900,000 和 1,100,000 个命令。通过批处理，Compartmentalized MultiPaxos 更接近于匹配未复制状态机的吞吐量，因为批处理可以分摊领导者的开销。

图 18c 显示了三种协议在承受 1、10 和 100 个客户端生成的负载时的中位延迟。我们将客户端在提出命令 x 和接收到执行 x 的结果之间必须等待的网络延迟数称为提交延迟。参考图 6，我们看到 Compartmentalized MultiPaxos 的提交延迟为 6，而 MultiPaxos 的提交延迟仅为 4。只有一个客户端，这种较小的提交延迟直接转化为较低的延迟。

与 Compartmentalized MultiPaxos 的 0.38 毫秒相比，MultiPaxos 的中位延迟为 0.27 毫秒。然而，对于快速网络和中到重负载，排队时间（而不是网络遍历）成为提交延迟的决定因素。

只需 10 或 100 个客户端，Compartmentalized MultiPaxos 就能够实现比 MultiPaxos 更低的延迟。但我们注意到，这个结果对于我们在单个数据中心内的部署来说是特别的。对于部署在 WAN 上的异地复制协议，提交延迟是提交延迟的决定因素。分隔协议不适合这种情况。另请注意，此实验的主要目标是测量划分所提供的相对加速。虽然我们实现的绝对性能数字很重要，但它们不是我们的主要关注点。

Mencius 延迟吞吐量

Compartmentalized Mencius 使用与 Compartmentalized MultiPaxos 相同数量的机器，除了它使用三个提议者而不是两个。结果如图 19 所示。在没有批处理的情况下，Mencius 每秒可以处理大约 30,000 个命令。分区化的 Mencius 每秒可以处理大约 250,000 个命令，提高了 8.3 倍。

Compartmentalized Mencius 的性能优于 Compartmentalized MultiPaxos，并且通过避免单一领导者瓶颈接近于匹配非复制状态机的性能。通过批处理， Mencius 和 Compartmentalized Mencius 分别实现了每秒近 200,000 和 850,000 个命令的峰值吞吐量，提高了 4.25 倍。

图 18c 中报告的延迟证实了 Compartmentalized Mencius 在低负载下比 Mencius 具有更高的延迟，但在中到重负载下具有更低的延迟。

S-Paxos 延迟吞吐量

在没有批处理的情况下，与 S-Paxos 的吞吐量为 22,000（提高 8.2 倍）相比，Compartmentalized S-Paxos 实现了每秒 180,000 个命令的峰值吞吐量。通过批处理，Compartmentalized SPaxos 实现了每秒 750,000 个命令的峰值吞吐量，而 S-Paxos 的吞吐量为 180,000（提高了 4.16 倍）。

请注意，我们的 S-Paxos 实现不如我们其他两个实现优化，因此其绝对性能较低。如上所述，展示绝对性能是展示相对加速的次要目标。

实验描述 前面的实验证实，划分可以将状态机协议的吞吐量增加多达 8.3 倍，而不使用批处理，使用批处理可以增加多达 4.5 倍。

结果 unbatched ablation study  结果显示在图 20a 中。MultiPaxos 实现了每秒大约 25,000 个命令的吞吐量。如果我们将协议解耦——分离提议者、接受者和副本——并引入代理领导者，我们将实现每秒大约 55,000 个命令的吞吐量。这个解耦的 MultiPaxos 使用最少数量的提议者 (2)、代理领导者 (2)、接受者 (3) 和副本 (2)。

本文技术将应用于三个现有协议 MultiPaxos、Mencius 和 S-Paxos——将它们的吞吐量提高多达 8.3 倍。