共识解耦 Compartmentalized Consensus

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

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

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

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

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

Step 1: Proxy Leaders 代理 leaders

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

共识解耦 Compartmentalized Consensus-即刻学术

在收到 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。

共识解耦 Compartmentalized Consensus-即刻学术

Step 3: Scaling Replicas

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

共识解耦 Compartmentalized Consensus-即刻学术

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

Step 4: Batching

共识解耦 Compartmentalized Consensus-即刻学术

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条消息。有了批处理程序,领导者只需要接收一条。这要么减少了瓶颈领导者的负荷,要么完全消除了它的瓶颈。

共识解耦 Compartmentalized Consensus-即刻学术

Step 6: Unbatchers

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

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

共识解耦 Compartmentalized Consensus-即刻学术

Mencius without Compartmentalization

没有区块化的 Mencius

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

共识解耦 Compartmentalized Consensus-即刻学术

Mencius with Compartmentalization

区块化的 Mencius

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

共识解耦 Compartmentalized Consensus-即刻学术

为了支持分批处理,本文介绍了作为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 提议者、接受者和副本的角色。它还扮演着传播者和稳定者的角色,这两个角色很快就会变得清晰起来。

共识解耦 Compartmentalized Consensus-即刻学术
共识解耦 Compartmentalized Consensus-即刻学术

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

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

共识解耦 Compartmentalized Consensus-即刻学术

讨论

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 实现不如我们其他两个实现优化,因此其绝对性能较低。如上所述,展示绝对性能是展示相对加速的次要目标。

共识解耦 Compartmentalized Consensus-即刻学术
共识解耦 Compartmentalized Consensus-即刻学术

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

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

共识解耦 Compartmentalized Consensus-即刻学术

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

为TA充电
共{{data.count}}人
人已赞赏
分布式

PigPaxos 共识协议

2021-6-1 16:31:23

分布式

Bipartisan Paxos 两党Paxos

2021-6-2 15:26:31

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索