ABSTRACT

        共识协议是部署在基于云的存储系统中的强一致性复制的核心。已经有许多建议来优化这些协议，其中大多数是通过识别瓶颈节点并将负载转移到未充分利用的节点来实现的。
        我们表明，虽然这些优化提高了吞吐量，但却牺牲了资源效率，这在云环境中至关重要。我们提出了一个新的度量来衡量这些协议的效率，并表明使用该度量，例如，优化的EPaxos协议比未优化的Multi-Paxos协议效率更低。然后，我们证明了Multi-Paxos可以在固定预算资源设置下实现比EPaxos高2倍的吞吐量，这是典型的云。我们的工作强调了在优化共识协议时需要考虑资源效率，因为它们越来越多地部署在云中。

1 INTRODUCTION

        强一致性复制是现代云服务的支柱，从配置管理到云数据存储。为了确保强一致性，这些服务通常使用共识协议（以下称为复制协议）实现状态机复制，该协议需要扩展并向用户提供高吞吐量、低延迟的服务。最近，出现了许多新的复制协议，它们都提高了吞吐量和/或延迟。
        这些优化的复制协议遵循类似的配方：它们识别传统解决方案中的一个或多个瓶颈组件，并尝试通过将工作转移到其他地方来缓解瓶颈。例如，许多传统协议依赖于一个专用的领导者来规定操作及其对跟随者节点的顺序。EPaxos推测单个领导者是吞吐量和延迟的瓶颈，并通过允许任何节点成为机会领导者来消除它；其他最近的系统进一步优化了EPaxos。PigPaxos将很大一部分沟通从领导者转移到追随者。分隔的Paxos将Paxos分为多个不同的角色或隔间；其中许多角色（如批处理节点或通信中继）可以横向扩展，允许它们部署在单独的虚拟机上，以减轻领导者的负担并提高吞吐量。
        尽管上述和类似的解决方案提高了吞吐量，但它们都有一个共同的缺陷：它们以降低效率为代价提高了吞吐量。这是因为它们假设具有相同节点的专用集群，其中一个节点在传统基线协议中处于瓶颈（充分利用），而其余节点未充分利用。因此，优化的协议试图将负载从瓶颈节点分散到剩余节点，而不考虑效率，因为未充分利用的节点中的资源无论如何都是空闲的。然而，对于在“资源密集”的云环境中运行的分片云本机服务来说，这种负载转移技术可能并不理想，因为每单位资源都要花钱。
        考虑一个部署在专用节点上的Multi-Paxos（或Raft，或主备份）复制方案的示例，如图1（a）所示。这些协议依赖于单个领导者，预期领导者比追随者做更多的工作和使用更多的资源，在追随者节点留下一些空闲资源。EPaxos，以及旨在扩展一致复制的类似工作，假设具有相同节点的设置；它们以增加复杂性和最重要的是降低效率为代价，在节点之间均匀分布负载。因此，EPaxos可以利用基于领先者的应用程序未使用的资源，并提供更高的吞吐量。

        然而，现代云服务很少在专用资源上运行；相反，物理资源共享与某些资源隔离是常态。此外，大多数系统通过并行运行多个协议实例来支持不同的数据分区，从而实现水平扩展。在这样的共享环境中，使用某种任务打包来分配和调度资源，在每个节点上只留下有限的空闲资源。
        我们在图1（b）中举例说明了这种任务打包的假设示例，其中三个Multi-Paxos实例共享一组4核服务器，并以一个实例的领导者与其他实例的追随者位于同一位置的方式打包。在我们的示例中，领导者使用两个核心，而追随者使用一个核心。尽管存在资源使用差异，但打包协议的多个实例在所有物理节点上实现了相同的负载。此外，与图1（a）所示的三个专用Multi-Paxos实例相比，这种打包部署需要更少的核心。
        然而，在相同的资源预算下，EPaxos等协议处于劣势，因为它们的效率较低。这是因为这些协议中的资源平衡和瓶颈避免通常以增加协议复杂性和增加总体资源使用为代价。在本文中，我们表明，尽管在给定专用资源的情况下，吞吐量优化的协议比其简单的协议提供更好的吞吐量，但在资源共享环境中，这些相同的协议可能会显著表现不佳。我们的研究结果表明，作为一个社区，我们一直忽视了扩大基于共识的复制的效率方面。我们认为，随着这些协议越来越多地部署在云中，除了传统的性能指标之外，效率也是至关重要的。事实上，在我们的调查中，我们无法找到提出基于共识的优化状态机复制协议的论文，该协议还包括所提出的优化的CPU或内存使用情况。
        我们认为，除了利用更多附加资源的优化之外，还需要进行效率优化，以允许使用相同的资源池处理更多操作。为此，我们建议在更仔细的情况下评估复制算法，避免仅通过最佳或最大性能指标来判断它们。我们建议将一个新的度量标准纳入到典型的协议评估中：限制资源利用的每单位吞吐量。该度量标准化了与约束资源消耗相关的协议性能。
        我们说明了我们对Multi-Paxos和EPaxos协议的度量，并表明它是共享资源共享环境中复制系统性能的良好代理。这是因为与效率较低的协议相比，效率更高的系统可以在相同的云资源池中打包更多的自身副本，尽管当与专用资源一起使用时，效率较高的系统的绝对能力较低。例如，在我们的实验中，我们证明，尽管EPaxos在一组专用VM上的性能优于Multi-Paxos近20%，但当我们在一组固定的共享资源上部署多个协议实例时，Multi-Paxo提供的吞吐量几乎是EPaxos的两倍。
        我们的工作仅将该指标应用于CPU使用情况，但也可以应用于其他限制资源，如内存或网络带宽。借助这一侧重于资源效率而非绝对性能的新指标，我们希望社区将开始优化现代云基础设施的复制协议。

2 REPLICATION IN THE WILD

        状态机复制协议部署在跨越各种环境的许多系统和应用程序中。这些环境从内部数据中心的专用硬件部署到完全管理的公共云解决方案。然而，由于成本的原因，大多数状态机即使在本地环境中也会远离完全专用的集群。当本地集群有大量未使用的硬件时，很可能会将所有系统部署在各自独立的环境中。然而，随着时间的推移，随着系统数量的增长而不扩大内部数据中心，这将变得更具挑战性。因此，资源共享（图1（b））变得越来越重要，特别是考虑到现代服务器的多核特性。在考虑从内部部署到公共云的迁移时，在资源共享环境中部署状态机复制协议的需求也会增加。公共云模型进一步鼓励资源共享，其按需付费模式对分配或使用的资源进行收费。
        许多最先进的存储系统利用了资源共享。像Spanner、CockroachDB和YugabyteDB这样的系统都使用Multi-Paxos或Raft的小实例，这样每个物理机器或VM都支持来自不同分区的许多副本。例如，CockrochDB依赖64MB分区，允许在同一物理服务器上创建数百个副本（如果不是数千个）。DocumentDB，现在被称为Azure Cosmos DB，也声称采用了一种负载平衡方法，即将主备份副本战略性地分配给服务器，以平衡联合中的负载。

3 CURRENT APPROACHES TO SCALING STATE MACHINE REPLICATION

        鉴于复制状态机在分布式系统和应用程序中的普遍存在，提高复制吞吐量在过去十年中一直是一个重要问题。一些解决方案要求同时提高吞吐量和减少延迟，而另一些解决方案则主张用一些延迟来换取更好的吞吐量。然而，这两个阵营都采取了类似的高水平方法来提高性能。他们首先确定传统系统中的瓶颈，然后通过将其转移到其他地方来消除瓶颈。通常，瓶颈在领导者，因为它用于与客户机通信并协调复制。
        像EPaxos和Atlas这样的系统避免了一个节点瓶颈，因为没有一个单独的领导者将所有通信集中在它周围。相反，这些系统扩展了Fast Paxos的思想，并尝试使用快速法定人数在一个往返网络延迟内从系统中的任何节点提交/复制操作。这种方法通常称为无领导共识，允许任何节点成为操作的机会主义领导者，希望该操作不会与其他节点发起的任何其他并发复制发生冲突。当冲突确实发生时，无领导解决方案会退回到更传统的Paxos协议来解决排序问题。机会协议的另一个好处是减少了延迟，因为系统可以立即开始复制并避免将所有操作路由到集中的领导者。
        一些解决方案（如SDPaxos）在实现复制状态机时将复制与操作排序分开。这允许系统中的每个节点接受和复制有效负载。然而，轻量级的任命领导者或定序器仍然用于在所有复制操作之间建立顺序。
        其他协议保持一个集中的领导者，以避免确定和解决冲突的复杂性，而是尽可能多地从领导者那里卸载工作；他们使用某种形式的中间节点来处理领导者的大部分通信和处理责任，将瓶颈从领导者转移到其他Paxos组件上。分隔的Paxos可以追溯到Paxos协议的根源，并将所有标准Paxos角色（提议者、接受者、学习者等）作为独立的组件，称为分隔。它添加了一些额外的角色，例如用于中继领导者通信的领导者代理和用于聚合操作的批处理节点。这样的角色分离加上额外的角色，允许像提议者一样的串联隔间在自己的专用虚拟机上运行，给他们留下更多的备用资源。另一方面，PigPaxos保留了在Multi-Paxos和Raft的实际实现中流行的组合复制角色，而是委派一些追随者代表领导者充当通信代理。另一种类似的方法，Linearizable Quorum Reads，将处理从Paxos组件转移到客户端；更具体地说，它允许客户直接从法定人数的追随者那里阅读，完全绕过领导者。
        将处理从瓶颈组件移开的一般方法允许协议通过利用先前由于瓶颈而未使用的资源来达到更高的吞吐量。为了证实这一点，我们在5个AWS EC2 m5a.large实例上运行了EPaxos和Multi-Paxos，这些实例具有2个vCPU和8 GiB的RAM。我们使用50%的写工作负载，以内存中的键值存储为目标，在该存储中，项目是随机选择的。我们的实验使用了多达90个并发的闭环客户端来饱和集群并观察其最大吞吐量。对于EPaxos，我们使用冲突比率高达10%的工作负载。如图2（a）所示，EPaxos优于Multi-Paxos约20%，这与最初的EPaxos评估结果一致。
        与EPaxos类似，所有改进协议的原始评估仅关注通过避免瓶颈和利用专用节点的空闲资源而解锁的绝对最佳性能。然而，如今的系统越来越多地部署在云上，使得此类评估不适合资源共享环境。

4 EFFICIENCY METRIC

        我们前面描述的新协议采用的通用可伸缩性方法有一个主要缺点。消除瓶颈并将处理转移到其他地方并不是免费的，需要更复杂和细致的算法才能使这些系统正常工作。因此，虽然这些系统可以解锁专用节点的未使用资源，但它们这样做是以使用更多资源为代价的。
        我们通过测量先前实验中EPaxos的CPU使用情况来证实这一点。如图2（b）所示，运行EPaxos副本的所有节点都得到了充分利用。（由于EPaxos中的所有节点都有统一的角色，我们称它们为副本，而不是领导者或追随者。）令我们惊讶的是，EPaxos、其衍生产品和类似工作中的评估都没有提供实验期间资源使用（CPU、内存、网络带宽）的测量。
        获取有关协议资源消耗的信息可以帮助确定避免瓶颈的额外成本，并评估其对资源密集云环境的适用性。例如，与EPaxos不同，Multi-Paxos消耗更少的CPU，如图2（c）所示。更具体地说，MultiPaxos仅充分利用前导节点，而每个跟随节点仅使用其节点的四分之一的CPU，有效地在集群中留下了0.75*4=3个节点的CPU未使用。虽然这些未使用的资源对于协议自身的负载平衡并不理想，但也意味着MultiPaxo仅使用40%的CPU就可以实现EPaxos吞吐量的80%。
        为了了解复制协议的效率，我们提出了一个新的性能指标：每单位约束资源利用率的吞吐量。我们可以将该度量应用于协议使用的任何集群资源，例如所有节点的内存或CPU使用情况。然而，要研究的最有用的资源是在一台或多台机器上造成瓶颈的限制性或约束性资源。在复制小负载的情况下（图2），这种限制性资源很可能是CPU，因为我们看到两种协议在至少一个节点上的利用率都接近100%。在其他设置中，在不同的工作负载下，约束资源可能会发生变化。
        少数云和数据库系统考虑使用价格/成本作为系统效率的代理。成本度量标准化了每花费一美元的性能。然而，这是协议真正资源效率的间接度量，因为每单位资源的成本可能因供应商而异，并且随着时间的推移而变化。此外，成本度量通常包括捆绑在一起的多个资源的价格，隐藏了单个资源可能对限制协议的可扩展性的影响。例如，如果一个成本度量包含多个不同的资源，如RAM、存储IOPS和CPU，则不清楚这些捆绑资源中的哪一个是约束资源，必须进行优化以固定成本提高性能。此外，对于某些系统或部署，成本估计基于分配的资源，而不是实际消耗的资源，这同样有利于可以使用所有分配的资源而不是更高效的资源的协议。出于这些原因，我们选择关注每资源的效率，而不是成本衡量，特别是考虑到如果资源费率已知，效率可以在云中转换为成本。资源效率指标也有助于改进现场部署，因为估计这些环境中的货币成本可能更困难。
        我们现在根据所提出的度量重新审视EPaxos和MultiPaxos协议的效率。为此，我们每秒钟测量一次每个节点上的CPU利用率百分比，并将这些利用率相加，以获得集群中的总CPU利用率值。然后，我们将滚动吞吐量测量值与该聚合值对齐，以获得CPU标准化性能，表示为每单位聚合CPU利用率的吞吐量（ops/s/CPU%）。如图2（d）所示，与图2（a）所示的原始性能数据相比，这个新的效率指标描绘了一幅截然不同的画面。后者显示EPaxos在专用集群中具有比Multi-Paxos更高的吞吐量，本质上说明了在分配资源的情况下EPaxos更高效。图2（d）中用我们的新效率度量表示的相同实验运行表明，考虑到消耗的资源，Multi-Paxos的效率几乎是EPaxos的两倍。这证实了我们的直觉，即EPaxos的额外处理需求（它需要对照依赖关系图检查每个操作是否存在可能的冲突）极大地影响了其效率。另一方面，Multi-Paxos是一种不那么复杂的协议，只需要简单的比较就可以确定每个操作的有效性。
        虽然我们只关注两个协议和一个资源，但该指标适用于任何复制协议和各种资源。例如，由于消息传递要求稍有不同，主备份的某些实现可能比共识协议在领先位置的CPU效率更高。类似地，使用磁盘绑定状态机而不是内存绑定状态机可能会给存储子系统带来更大的压力。效率度量也可用于以复制为核心的其他数据驱动协议和系统，例如分布式队列或日志、发布子系统和事务处理协议。

5 INEFFECTIVENESS OF CURRENT APPROACHES PER NEW METRIC

        状态机复制的专用服务器或虚拟机部署浪费了已分配但未使用的资源，使得EPaxos或PigPaxos等更均衡的协议更受欢迎。然而，许多云原生系统依赖共享环境来更好地利用可用资源。更重要的是，这些共享环境通常受到预算的限制，这使得效率对于从固定资源池中获取同样多的价值至关重要。在本节中，我们将演示更高效的协议（如MultiPaxos）如何在具有更差的协议级负载平衡特性的情况下实现更高的聚合吞吐量。
        在现代数据中心中，大型存储系统通过使用复制状态机的独立实例在不同数据分区中提供强大的一致性，以数据并行方式横向扩展。这允许进行更全面的资源平衡，而不局限于单个复制状态机实例的范围。例如，给定适当的资源分配和调度策略，一个实例未使用的资源可以由另一个实例使用。幸运的是，现代集装箱化基础设施促进了这种资源调度。
        作为一个具体的示例，为了简单起见，让我们考虑在五节点集群上进行任务打包设置。这组机器可能代表我们可能愿意在复制和存储基础架构上花费的固定预算。在这个设置中，我们可以“任务包”五个Multi-Paxos实例，这样在无故障的情况下，每个节点都有一个Multi-Paxos领导者和四个追随者，每个人都属于不同的Multi-Paxo实例（类似于图1，但有五个Multi-Paxos，而不是三个）。尽管这种简单的部署依赖于领导者和跟随者节点之间资源使用不成比例的协议，但通过将资源重的角色与资源轻的角色配对，实现了良好的资源利用率。
        我们通过在AWS EC2集群上模拟这种“资源共享云”场景来演示这一点，该集群使用五个m5a.2x大型虚拟机，每个虚拟机具有8个vCPU和32 GiB的RAM。我们使用前面提到的任务打包设置部署了五个MultiPaxos实例，并在重复前面的实验（§3）的同时，测量每个MultiPaxo实例的吞吐量和虚拟机的CPU利用率。我们分别针对五个实例中的每一个，最多100个并发闭环客户端，并聚合所有协议实例的吞吐量数据。图3（a）显示了每个Multi-Paxos实例的吞吐量约为30 kops/s，图3（b）确认了所有节点上的CPU都得到了充分利用。（在这种情况下，由于VM更强大，单个Multi-Paxos实例的吞吐量高于图2（a）中的吞吐量。）
        为了进行比较，我们还在同一集群上部署了五个EPaxos实例，并重复该实验。为了公平比较，这模拟了在相同集群上运行相同数量碎片的两个系统。理论上，由于EPaxos能够使节点的资源饱和，我们可以将其作为一个单独的分区在大型计算机集群上运行。然而，在实践中，扩展系统以在高芯数机器上高效工作是具有挑战性的，并且很少产生完美的加速。分区部署在这方面更好，因为在不同进程中运行的不同分区对共享软件资源（如锁、队列和原子计数器）的争用点更少。图3（c）显示了EPaxos的每个实例在所有节点上的CPU都充分利用的情况下仅实现了15kop/s的吞吐量（为了节省空间，省略了该图）。与我们的专用设置相比，这种碎片化和打包环境中EPaxos的每实例吞吐量有所下降。这是因为五个EPaxos实例中的每一个在每个服务器上都有8个5 vCPU可用（假设操作系统调度合理），这在专用实验中略低于2个vCPU可用。

        总之，图3（d）显示，五个Multi-Paxos实例的总吞吐量几乎是五个EPaxos实例的两倍。因此，与专用资源实验（图2）相比，在具有适当任务打包的共享环境中，更高效的协议具有显著优势。

6 CONCLUSION AND FUTURE DIRECTIONS

        云计算的出现极大地改变了我们构建系统的方式，但这种转变远未结束。许多存储系统依赖于高度一致的复制协议。然而，这些协议比云早了几十年，许多针对它们提出的优化仍然忽略了云计算给我们带来的不同现实。在这项工作中，我们提出了重新设计云复制协议的理由。
        我们工作的关键见解是，虽然目前提出的优化显著提高了事务吞吐量，但它们忽略了资源效率，这在云计算的现收现付实用模型中至关重要。更具体地说，这些优化将在具有相同节点的专用集群上运行的Multi-Paxos实例作为基线，其中领导节点是瓶颈，而跟随节点未充分利用。然后，他们发明了一种更复杂、资源效率更低的协议，将负载分散到未充分利用的跟随节点。我们表明，当部署在具有固定资源预算的典型云环境中时，与“未优化协议”相比，这些“优化协议”明显表现不佳。
        这就引出了设计更适合资源共享环境（特别是云）的协议和系统的问题。为此，我们引入了一个新的度量，通过标准化吞吐量和资源消耗来考虑资源效率。该度量可以很好地代表协议在碎片化、任务密集环境中的相对性能。
        使用此度量，我们可以识别复制协议中的瓶颈，并针对现代环境对其进行优化。优化的一个潜在来源是新兴的硬件和软件技术。当一种资源的效率提高而牺牲了其他更丰富的资源时，这些技术可以提供进一步的效率优化或效率权衡的机会，Odyssey认为，在设计复制协议时，应考虑到服务器的多核特性以及绕过CPU的新通信技术（如RDMA）的可用性。其他现代实现驱动方法，如内核旁路（即DPDK），也可用于减少协议的CPU占用。
        优化不一定要停止使用新的实现技术；我们仍然可以在协议级别上做很多工作来限制资源使用。例如，一些较老的技巧，如Cheap Paxos可能会方便地限制不必要的交流。特定于用例的优化也是可能的。例如，在一个经常覆盖一些数据对象子集的系统中，领导者可能会立即放弃复制一个操作，因为预计很快就会出现一些隐藏操作。
        更激进或有疑问的想法也值得探索。例如，在数据中心中使用不断改进的时间同步作为始终保持的隐式通信和同步源，可能会导致协议避免某些显式同步并节省一些资源。
        这些和其他潜在的解决方案需要了解协议和系统的资源效率。在大数据平台的背景下，在不牺牲效率的情况下进行扩展的重要性已经被提出，在复制协议中，尤其是基于共识的复制中，效率问题在很大程度上被忽略了。我们认为，在云上运行的协议中，研究效率更为重要，我们希望看到为云设计的新一代资源高效复制协议的出现。