论文名称：Pegasus: Tolerating Skewed Workloads in Distributed Storage with In-Network Coherence Directories

摘要

高性能分布式存储系统面临着由于偏斜和动态工作负载引起的负载不平衡的挑战。本文介绍了Pegasus，这是一个利用新一代可编程交换机ASIC来平衡存储服务器负载的新型存储系统。Pegasus使用数据存储中最受欢迎的对象的选择性复制来分配负载。通过使用一种新颖的网络内一致性目录，Pegasus交换机跟踪和管理复制对象的位置。这使得它能够实现对复制键的负载感知转发和动态再平衡，同时仍然保证数据的一致性和一致性。Pegasus设计的实施是切实可行的，因为它只在交换机数据平面中存储转发元数据。由此产生的系统将分布式内存键值存储的吞吐量提高了10倍以上，并在具有不同程度的偏斜、读写比率、对象大小和动态性的大量工作负载下保持结果。

1 引言

分布式存储系统的任务是在巨大而不可预测的负载下提供快速、可预测的性能。像Facebook的memcached部署[50]这样的系统存储了数万亿个对象，并在每次用户互动时被访问数千次。为了实现规模，这些系统分布在许多节点上；为了实现性能可预测性，它们主要或完全将数据存储在内存中。

这些系统面临的一个关键挑战是在高度偏斜的工作负载存在下实现负载平衡。就像一个名人可能比普通用户拥有更多的粉丝一样，一些存储的对象每天接收到的请求可能比其他对象少得多[3, 67]。此外，受欢迎对象的集合会随着新趋势的兴起和消失而迅速变化[5]。传统算法如一致性哈希[30]在所有对象的受欢迎程度大致相等时分配负载非常有效，但在这种情况下却不够。对于单个受欢迎对象的请求通常超过任何一个服务器的容量。

复制使得处理请求负载超过一个服务器容量的对象成为可能。尽管每个对象的复制在负载均衡方面很有效[13, 49]，但也引入了很高的存储开销。仅选择复制一组热门对象可以避免这种开销。利用对缓存的先前分析[17]，我们表明只需要复制很少的对象就能实现强大的负载平衡属性。然而，跟踪哪些对象是热门对象以及它们存储在哪里并不是一件简单的事情，特别是当存储系统可能有数十万个客户端时，保持多个副本一致性甚至更加困难[50]。

我们通过Pegasus来解决这些挑战，Pegasus是一个分布式存储系统，它使用一种新的架构进行选择性复制和负载平衡。Pegasus使用可编程数据平面交换机将请求路由到服务器。借鉴CPU高速缓存一致性协议[4, 19, 22, 31, 34, 36, 37, 40]，Pegasus交换机充当网络内一致性目录，用于跟踪复制对象及其位置。利用交换机对请求流量的中央视图，它可以以负载感知的方式转发请求到副本。与以往的方法不同，Pegasus的一致性目录还允许它在每个写操作中动态重新平衡副本集，加速读和写密集型工作负载，同时仍然保持强一致性。

Pegasus引入了一些新技术，超越了网络内一致性目录的概念本身。它使用轻量级基于版本的一致性协议来确保一致性。负载感知调度使用反向网络遥测和交换机内加权轮询策略的组合来实现。最后，为了提供容错性，Pegasus使用简单的链式复制协议在不同机架上创建多个数据副本，每个副本都与其自己的交换机负载均衡。

Pegasus是一个切实可行的方法。我们展示了它可以使用Barefoot Tofino交换机实现，并且在减少开关资源开销的同时提供了有效的负载平衡。尤其是与以往的系统[29, 45]不同，Pegasus在交换机中只存储元数据而不存储应用数据。这将交换机的内存使用量降低到总交换机SRAM的3.5%以下，使其能够与现有的交换机功能共存，从而降低了采用的主要障碍[56]。使用28个服务器和一个Pegasus交换机，我们展示了以下结果：

• Pegasus可以将系统的吞吐量提高多达10倍，或者减少所需服务器数量的90%，在99%延迟SLO的情况下。
• Pegasus可以快速响应动态工作负载，其中热键集合快速变化，并且可以快速从服务器或机架故障中恢复。
• Pegasus可以通过只复制少量对象来提供强大的负载平衡属性。
• Pegasus能够为许多类型的工作负载（包括读重型和写重型），具有不同的对象大小和偏斜程度，实现这些好处。

2 动机

实际存储系统的工作负载通常表现出高度倾斜的对象访问模式[3, 6, 26, 50, 51]。在这种情况下，相对较少的热门对象接收到的请求远远超过其余对象。许多这样的工作负载可以使用Zipfian访问分布来建模[3, 5, 6, 67]；最近的研究表明，一些真实的工作负载展现出前所未有的倾斜水平（例如，α > 1的Zipf分布）[10, 67]。此外，热门对象集合是动态变化的：在某些情况下，平均热门对象在10分钟内就会失去其受欢迎程度[5]。

为了可扩展性和负载分配的目的，存储系统通常将对象划分到多个存储服务器之间。高度倾斜的工作负载意味着存储服务器之间的负载也不均衡：存储最热门对象的少数服务器将接收到比其他服务器更多的流量。访问倾斜度通常足够高，以至于一个对象的负载可能超过单个服务器的处理能力，导致服务器过载。为了减少性能损失，系统需要过度配置，这会大幅增加总体成本。

倾斜工作负载种类繁多。读取密集型工作负载一直是许多最近研究的重点，并且很多系统在对其进行优化（例如，假设> 95%的请求是读取）[21, 29, 41, 45]。虽然许多工作负载确实属于这个类别，但混合或写入密集型的工作负载也很常见[67]。对象大小也有很大的变化，即便在同一个提供商内部也是如此。系统可以存储小值（几个字节）、较大值（千字节到兆字节）或两者的组合[1, 3, 5, 67]。解决倾斜工作负载的理想解决方案应该能够处理所有这些情况。

2.1 现有方法

在请求负载超过单个服务器处理能力的倾斜工作负载中，存储系统应该如何处理？已有的两种方法在这里证明了有效性：在更快的层级中缓存热门对象，以及复制对象以增加总体负载能力。

缓存 缓存长期以来一直是加速基于数据库的Web应用程序的标准方法。最近的研究在理论上和实践上证明了缓存方法的有效性：只需要缓存少数键就可以实现可证明的负载均衡保证[17, 29, 41]。

然而，缓存方法有两个限制。首先，缓存的有效性取决于构建缓存的能力，该缓存能够处理比存储服务器多个数量级的请求。这曾经是一个容易实现的目标，但随着存储系统本身采用内存存储[50, 53, 58]、巧妙的数据结构[42, 46]、新的非易失性内存（NVM）技术[25, 68]和更快的网络栈[38, 42, 48]，这已成为一个严峻的挑战。最近的努力将可编程交换机构建为更快的缓存[29, 45]解决了这个问题，但硬件限制施加了重大限制，例如无法支持大于128字节的值。其次，缓存解决方案只对读取密集型工作负载有益，因为缓存副本必须在写入被存储服务器处理之前失效。

选择性复制 复制是另一种解决倾斜工作负载引起的负载不平衡的常见方法。通过选择性复制热门对象[2, 9, 13, 50]，可以将对这些对象的请求发送到任何副本，有效地分散负载到服务器上。

然而，现有的选择性复制方法面临两个挑战。首先，客户端必须能够识别复制的对象及其位置，而这可能随着对象的受欢迎程度变化而改变。这可以通过使用集中式目录服务或将目录复制到客户端来实现。这两种方式都存在可扩展性限制：集中式目录服务很容易成为瓶颈，而在可能涉及数十万个客户端的情况下保持目录同步并非易事。

对于复制对象提供一致性是第二个主要挑战，这是一个相当复杂的挑战，现有系统不尝试解决它。它们要么仅复制只读对象，要么要求用户明确管理复制引起的不一致性[2, 9]。实现强一致性复制所需的解决方案（例如，共识协议[35]）非常复杂，并且会产生显著的协调开销[39]，特别是当对象频繁修改时。

2.2 Pegasus 目标

我们的工作目标是为上述类别的具有挑战性的工作负载提供有效的负载均衡解决方案。具体而言，我们要求我们的系统：1）为具有高度倾斜的动态工作负载提供良好的负载均衡；2）与快速的内存存储系统配合工作；3）处理任意大小的对象；4）保证线性可比性[24]；5）对读取密集型、写入密集型和混合读/写工作负载同样有效。如表1所示，现有的系统都做出了明确的权衡，没有一个同时满足这五个特性。在本文中，我们将介绍一种新的分布式存储负载均衡方法，它不做任何妥协，并使用一个网络内部完整性目录。

现有负载均衡系统与 Pegasus 的比较。在“任意读写比例”列中，我们只考虑提供强一致性的系统。

3 系统模型

Pegasus 是一个机架级存储系统的设计，由多个存储服务器通过单个顶部交换机连接而成，如图1所示。Pegasus 将交换机内部负载均衡逻辑与新型存储系统相结合。Pegasus 系统提供具有读/写接口的键值存储。它不支持读取-修改-写入或原子跨键操作。Pegasus 确保强数据一致性（具体来说，线性可比性）。它使用内存存储提供快速且可预测的性能。

Pegasus 系统模型。Pegasus 是一种机架级存储系统。它通过在顶级交换机中增加一个网络内一致性目录来平衡机架内存储服务器的负载。服务器将数据存储在内存中，以实现快速和可预测的性能。

Pegasus 架构是交换机处理和应用级协议的共同设计。这得益于新型可编程数据平面交换机的能力，如 Barefoot Tofino、Cavium XPliant 或 Broadcom Trident3 系列。广义上讲，这些芯片在三个相关领域提供了可重构性：（1）可编程解析应用特定头部；（2）灵活的数据包处理流水线，通常由 10 到 20 个流水线阶段组成，每个阶段都能进行匹配查找和一个或多个 ALU 操作；以及（3）大约 10 MB 的通用内存。重要的是，所有这些功能都在交换机数据平面上，这意味着它们可以在以太网全速率处理数据包时使用 - 当今总容量以太比特每秒计量。

Pegasus 在机架级别提供负载均衡，即通过单个交换机连接的 32 到 256 台服务器。它不提供机架内的容错保证。更大规模的、具有弹性的系统可以通过多个 Pegasus 机架构建。对于这些系统，Pegasus 使用链式复制协议来跨多个机架复制对象以实现容错性。

4 网络内部目录的案例

正如我们在第2节中讨论的那样，选择性复制热门对象可以为高度倾斜的工作负载提供良好的负载均衡，并且避免缓存方法的某些缺点。然而，现有的选择性复制解决方案在为动态复制对象集提供高效的目录服务和强一致性方面存在不足。我们的关键观察是，在机架级存储系统中（第3节），顶部交换机充当系统的中心点，并处于每个客户端请求和服务器回复的路径上。这使我们能够在顶部交换机中实现一种一致性目录抽象，同时解决这两个挑战。它可以跟踪系统中每个复制对象的位置，并将请求转发到具有可用容量的服务器，甚至通过决定发送写入请求的位置来改变副本的数量或位置。利用这种网络内部一致性目录，我们共同设计了基于版本的一致性协议，该协议保证线性可比性，并且在处理对象更新时非常高效，使我们能够为写入密集型工作负载提供良好的负载均衡。

4.1 复制数据的一致性目录

我们如何设计一个有效的选择性复制方案来实现强一致性呢？在高层次上，系统需要解决以下挑战：首先，它需要跟踪复制的项及其最新数值（即复制集）。其次，对于复制对象的读取请求必须转发到当前复制集中的服务器。第三，完成写请求后，所有后续的读取请求必须返回更新后的数值。

标准的分布式系统方法在这种环境下效果不佳。一个可能的尝试是让客户端联系系统中的任何服务器，然后将查询转发到数据的适当副本，就像分布式哈希表[14, 59, 60]那样。然而，对于内存存储系统来说，接收和转发请求几乎与完全执行请求一样具有负载。客户端直接跟踪每个对象的位置也是不可行的（例如使用配置服务[8, 27]），因为数据中心可能有成千上万甚至百万的客户端，更新每个客户端以使新对象变得流行或对象的复制集被更新是一项昂贵的任务。

在 Pegasus 中，我们采取了不同的方法。我们注意到这些是 CPU 缓存一致性和分布式共享内存系统所面临的相同挑战。为了解决上述问题，这些系统通常运行一个使用一致性目录的缓存一致性协议[4, 19, 22, 31, 34, 36, 37, 40]。 对于每个数据块，一致性目录存储一个条目，其中包含具有共享或独占副本的处理器集合。目录会随着处理器读取和写入数据块而保持最新状态，根据需要使旧副本失效，并始终能指向最新版本的处理器。

一致性目录可以应用于选择性复制。它可以跟踪复制对象的集合，并将读取请求转发到正确的服务器，同时通过从复制集中移除过期的副本来确保数据一致性。然而，要在分布式存储系统中使用一致性目录，则需要目录处理所有客户端请求。如果在传统服务器上实现，它将很快成为延迟和吞吐量的瓶颈。

4.2 在网络中实现一致性目录

如果我们要在哪里实现一个处理所有客户端请求的一致性目录，同时又不成为性能瓶颈？如图 1 所示，ToR 交换机为我们针对机架级存储系统提供了一个可行的选项。交换机 ASIC 被优化用于数据包 I/O：当前的交换机可以支持超过 10 Tb/s 的聚合带宽和数十亿数据包每秒的数据包处理[64, 65]。我们针对的可编程交换机具有固定长度的可重新配置管道，因此任何适合管道的逻辑都可以以交换机的整体速率运行。因此，在机架级存储系统中实现一致性目录的 ToR 交换机既不会成为瓶颈，也不会增加显著的延迟，因为它已经处理了机架上的所有网络流量。

但我们能否在 ToR 交换机中高效地实现一致性目录？要做到这一点，必须解决两个挑战。首先，我们需要在交换机数据平面中实现一致性目录的所有数据结构和功能逻辑。我们展示了最近可编程交换机确实可以做到这一点：我们在交换机的存储器中存储了复制的键和它们的复制集，基于自定义数据包头字段（例如键和操作类型）进行匹配和转发，并应用一致性协议的目录更新规则。我们在第 8 节中详细描述了我们的交换机实现。其次，交换机数据平面的资源有限，而且许多资源已经被基本的交换机功能所消耗。由于一致性目录跟踪每个复制对象的复制集，交换机只能支持有限数量的要复制的对象。我们的设计满足了这一挑战。有趣的是，如果我们只复制最受欢迎的 O(nlogn) 个对象到所有服务器，其中 n 是系统中服务器（而不是键）的数量，那么我们可以实现可证明的负载平衡保证（我们在第 4.5 节中对该结果进行了更详细的分析）。此外，一致性目录只存储诸如键哈希和服务器 ID 等小的元数据。对于一个具有 32-256 个服务器的机架级系统来说，一致性目录的大小只占可用交换机资源的一小部分。

4.3 网络的一致性协议

使用网络中的一致性目录设计一致性协议引发了一些新的挑战。传统的 CPU 缓存一致性协议可以依赖有序和可靠的互连网络，并且通常在一致性更新期间阻塞处理器请求。交换机 ASIC 的缓冲空间有限，因此无法无限期地保存数据包。ToR 交换机和服务器之间的网络连接也是不可靠的：数据包可能会被任意丢弃、重排序或复制。许多实现有序和可靠通信的协议需要复杂的逻辑和大量的缓冲空间，这是交换机所不具备的。

我们设计了一种基于版本的非阻塞一致性协议来解决这些挑战。交换机为每个写请求分配一个单调递增的版本号，并将其插入数据包头中。服务器在每个对象旁边存储这些版本号，并在每个读取和写入回复中附加版本号。交换机还在一致性目录中为每个复制对象存储一个已完成版本号。当接收到读取或写入回复（针对复制对象）时，交换机将回复中的版本与目录中的已完成版本进行比较。如果回复中的版本号较高，交换机将更新已完成版本号，并重置复制集以仅包括源服务器。接下来的读取请求将被转发到具有新数值的服务器。当多个服务器都具有对象的最新数值时，回复中的版本号可以等于已完成版本。在这种情况下，我们将源服务器（如果尚未存在）添加到复制集中，以便将后续读取请求分布在最新的副本之间。

这种协议——我们在第 6 节中详细介绍——保证了线性化[24]。它利用了两个关键的见解。首先，所有存储系统请求和回复都必须经过 ToR 交换机。因此，我们只需要更新网络中的一致性目录来保证数据一致性。这使我们能够避免昂贵的失效流量或服务器间的协调开销。其次，我们使用由交换机应用于数据包头的版本号来处理网络的异步性。

4.4 负载感知调度

在转发读请求时，交换机可以选择当前副本集中的任何服务器。最简单的策略是从集合中随机选择一个服务器，并依靠服务器之间的统计负载平衡。然而，当存储服务器上的处理能力不均匀时（例如由于后台任务或不同的硬件规格），这种方法存在一些问题。为了解决这个问题，我们还实现了加权轮询策略：存储服务器定期向控制器报告其系统负载。控制器根据这些负载信息为每个服务器分配权重，并将它们安装到交换机上。交换机然后按比例将请求转发给副本集中的服务器。请注意，我们的网络内目录方法提供了执行服务器选择的机制。对所有调度策略的全面讨论超出了本文的范围。

令人惊讶的是，这些机制也可用于写请求。乍一看，似乎需要将新写入的数据广播到副本集中的所有服务器，可能会导致负载过重并使某些服务器过载。然而，交换机可以在每次写操作时选择一个新的副本集。它可以将写请求转发给一个或多个服务器，且一致性目录可以确保数据的一致性，无论交换机选择哪个服务器。频繁移动数据的能力使得交换机能够对读和写请求都进行负载感知调度。这是 Pegasus 在提升读写工作负载性能方面的关键。

4.5 网络内一致性目录的可行性

Pegasus 高效利用交换机资源，因为它只跟踪对象元数据（而不是完整的对象内容 [29]），仅对少量对象进行跟踪。我们在第4.2节中声称，为了实现强大的负载平衡保证，Pegasus 只需复制最受欢迎的 O(nlogn) 个对象（其中 n 是服务器数量）。这个结果是先前的研究 [17] 的延伸，该研究表明缓存 O(nlogn) 个最常访问的对象就足以实现可证明的负载平衡。也就是说，如果我们排除这些对象，每个服务器上的剩余负载最多超过平均负载一个松弛因子 α，该因子取决于常数因子，但通常非常小；详见第9.5节。直观地说，高度倾斜的工作负载中的大部分负载（按定义）集中在少数关键字上，因此消除这种负载可以重新平衡系统。

我们的方法与使用缓存吸收负载的方法不同，而是将负载在存储服务器之间重新分配。前面的结果的一个结果是，如果系统的总请求处理容量超过请求负载的 α 倍（α 是一个与常数因子有关但通常很小的松弛因子），那么存在一种方式可以重新分配前 O(nlogn) 个关键字的请求，使得任何服务器都不会超过其容量。

对于只读工作负载，实现这一点的一种简单方法是将这些关键字复制到所有服务器上，然后将请求路由到任何具有多余容量的服务器，例如通过将对复制关键字的请求路由到系统中负载最轻的服务器。

写操作使情况变得更加复杂，因为它们必须由存储该对象的所有服务器进行处理。如第4.4节所述，Pegasus 可以为每个写操作选择一个新的副本集和新的复制因子。Pegasus 通过跟踪每个对象的写入比例，并将复制因子设置为预期的每次写入的读取次数来适应写密集型工作负载，从而产生恒定的开销。

严格来说，我们的初始分析（针对只读工作负载）在这种情况下可能不适用，因为不再可能将读请求发送到任意服务器。然而，由于 Pegasus 可以在每次写入时重新平衡副本集并动态调整复制因子，因此它仍然有效地进行负载平衡，适用于任何读写比例。直观地说，多数为读的工作负载具有许多副本，因此 Pegasus 在选择每个读取请求的服务器时具有很高的自由度，而多数为写的工作负载只有少数副本，但会不断使它们重新平衡以位于负载最轻的服务器上。

5 Pegasus概述

我们在一个新的机架规模的存储系统Pegasus中实现了一个网络内一致性目录。图1展示了Pegasus部署的高层架构。所有存储服务器都位于同一个机架内。连接所有服务器的顶级交换机(Top-of-Rack, ToR)实现了Pegasus的复制对象的一致性目录。

交换机。ToR交换机维护一致性目录：它存储了一组复制的键，以及对于每个键，具有有效数据副本的服务器列表。为了减少交换机资源开销并支持任意大小的键，该目录通过一个小的固定大小的哈希来标识键。

Pegasus在L4负载中嵌入了应用层数据包头，如图2所示。Pegasus为交换机保留了一个特殊的UDP端口用于匹配Pegasus数据包。应用层头部包含一个OP字段，可以是READ、WRITE、READ-REPLY或WRITE-REPLY。KEY-HASH是应用生成的键的固定大小哈希值。VER是由交换机分配的对象版本号。SERVERID包含服务器的唯一标识，并由服务器在回复中填充。如果需要最多一次语义（§6.4），头部还将包含REQID，即客户端分配的请求的全局唯一ID。非Pegasus数据包使用标准的L2/L3路由进行转发，使得交换机与现有网络协议完全兼容。

Pegasus数据包格式。Pegasus应用层头部嵌入在UDP负载中。OP表示请求或回复类型。KEYHASH包含键的哈希值。VER是对象的版本号。SERVERID包含唯一的服务器标识符。

为了保持空间使用低，Pegasus交换机仅为一小组复制对象保留目录条目。复制键的读写请求按照Pegasus负载均衡和一致性协议进行转发。其他键通过固定的算法（如一致性哈希[30]）映射到主服务器上。尽管该算法可以在交换机中实现，但我们通过让客户端将其数据包发送到相应的服务器来避免这样做；对于非复制键，Pegasus交换机只是根据标准的L2/L3转发策略转发它们。

控制器。Pegasus控制平面决定哪些键应该被复制。它负责更新一致性目录，存储最流行的O(nlogn)个键。为此，交换机实现了一个请求统计引擎，使用数据平面和交换机CPU跟踪每个键的访问率。控制器可以在交换机CPU上运行，也可以在远程服务器上运行，从引擎中读取访问统计信息以找到最流行的键。控制器仅保留软状态，如果出现故障，可以立即替换。

6 Pegasus协议

为了简化阐述，我们首先描述核心的Pegasus协议（§6.2），假设流行键集合是固定的，并展示它提供了线性一致性。然后我们展示如何处理流行键的变化（§6.3），以及如何提供恰好一次语义（§6.4）。最后，我们讨论服务器选择策略（§6.5）和其他协议细节（§6.6）。

此外，我们在公共代码库中提供了对该协议进行安全性验证的TLA+规范[55]。

6.1 交换机状态

为了实现网络内一致性目录，Pegasus在交换机数据平面中维护少量元数据，如图3所列。计数器ver_next保存下一个要分配的版本号。查找表rkeys使用数据包头中的KEYHASH作为查找键来存储O(nlogn)个复制的热键。对于每个复制键，交换机维护具有有效副本的服务器集合rset，并保存最新已完成写操作的版本号ver_completed。在§8中，我们详细说明了如何存储这个状态并在交换机数据平面中实现这个功能。

6.2 核心协议：请求和回复处理

核心的Pegasus协议通过跟踪流行对象的副本集来平衡负载。它可以通过选择一个现有副本来平衡读操作的负载，并且可以通过选择哪个副本处理写操作来更改对象的副本集。在确保线性一致性的同时提供这种负载平衡，需要确定网络内目录跟踪每个复制键的最新成功写入值的位置。Pegasus通过为传入的请求分配版本号并监视传出的回复，以检测何时写入了新的版本来实现这一点。

6.2.1 处理客户端请求

Pegasus 交换机为每个写入请求分配一个版本号，方法是将 ver_next 写入其标头并递增 ver_next（算法 1 第 1-3 行）。它通过将请求的键哈希与 rkeys 表匹配来确定如何转发请求。如果该键没有被复制，交换机简单地将请求转发到原始目的地——键的主服务器。对于被复制的键，它通过从键的 rset 中选择一个服务器来转发读取请求。对于复制的写入请求，它从所有服务器的集合中选择一个或多个目的地。在这两种情况下，此选择是根据服务器选择策略进行的（§6.5）。

存储服务器为每个键维护一个版本号以及其值。处理写入请求时，服务器将标头中的 VER 与存储中的版本号进行比较，并仅在数据包具有更高的 VER 时才更新值和版本号。它还在 READ-REPLY 和 WRITE-REPLY 消息的标头中包括读取或写入的版本号。

6.2.2 处理服务器回复

当交换机收到 READ-REPLY 或 WRITE-REPLY 时，它在交换机的 rkeys 表中查找回复的键哈希。如果该键被复制，交换机会将数据包标头中的 VER 与 ver_completed 中键的最新完成版本进行比较。如果回复具有更高的版本号，交换机会更新 ver_completed 并重置键的副本集，只包括源服务器（算法 2 第 1-4 行）。如果两个版本号相等，交换机会将源服务器添加到键的副本集中（算法 2 第 5-7 行）。

此算法的效果是，写入请求被发送到一个新的副本集，可能与之前的副本集重叠或不重叠。一旦一个服务器完成并确认写入，交换机就会将所有未来的读取请求定向到该服务器，从而足以确保线性可实现性。随着其他副本也确认写入的相同版本，它们开始接收读取请求负载的份额。

6.2.3 正确性

Pegasus 提供了线性可实现性[24]。其背后的直觉是，Pegasus 目录监视所有流量，并跟踪键的最新观察版本的位置。一旦任何客户端看到对象的新版本——如 READ-REPLY 或 WRITE-REPLY 中包含更高版本号的情况——交换机就会更新目录，以便将将来的读取请求发送到持有该版本的服务器。

关键不变性是 Pegasus 目录至少包含一个存储最新写入副本的副本地址，以及该写入的版本号。当写入的值可以在 Pegasus 系统外部观察时，即完成外部化写入。写入可以以两种方式完成。通常情况下，WRITE-REPLY 被发送，表示写入已完成。如果先前和当前的副本集重叠，也可能会发生一个服务器在交错的 READ 中响应新版本，而在 WRITE-REPLY 到达之前。Pegasus 通过监视 WRITE-REPLY 和 READ-REPLY 消息，并且如果 VER 超过最新已知兼容版本号，则更新目录来检测这两种情况。

此不变性，结合 Pegasus 将读取转发到目录副本集中的服务器的策略，足以确保线性可实现性：

• WRITE 操作可以按其版本号排序。
• 如果在 WRITE 操作 w 完成后提交了 READ 操作 r，则 r 按照操作表面顺序出现在 w 之后，因为它要么被转发到由 w 写入版本的副本，要么被转发到具有更高版本号的副本。
• 如果在另一个 READ r1 完成后提交了 READ 操作 r2，则 r2 按照操作表面顺序出现在 r1 之后，因为它要么被转发到 r1 所见版本的副本，要么被转发到具有更新版本号的副本。

6.3 添加和移除复制的键

键的流行程度不断变化。Pegasus 控制器不断监视访问频率，并使用 O(nlogn) 最受欢迎的键更新一致性目录。我们在 §8 中详细说明了如何维护访问统计信息。

当一个新键变得受欢迎时，Pegasus 必须为其创建一个目录条目。Pegasus 控制器通过将键的主服务器添加到 rset 来完成此操作。它还在 ver_completed 中为该键添加映射，将其与 ver_next−1 关联，即可以分配给该键的写入的最大版本号。最后，控制器将该键添加到 rkeys 中。该过程不会立即移动或复制对象。但是，稍后的 WRITE 请求将被发送到一个新的（可能更大）副本集，版本号必然大于直接添加到目录中的版本号。一旦这些新写入的值外部化，它们将像正常情况一样添加到目录中。

将键从复制状态转换为非复制状态同样简单。控制器简单地标记交换机的目录条目进行转换。该键的下一个 WRITE 将被发送到其主服务器；一旦接收到匹配的 WRITE-REPLY，该键将从目录中移除。

只读对象和虚拟写入。上述协议仅在下一次写入时将对象移动到新的副本集（或返回到其主节点）。尽管这简化了设计，但这对于只读或很少修改的对象提出了问题。从概念上讲，Pegasus通过执行一个在需要移动对象时不改变对象的值的写入操作来解决这个问题。更准确地说，控制器可以通过向键的主服务器发出虚拟写入来强制复制，指示其递增其存储的版本号到 ver_completed，并将该值转发到其他副本，以便它们可以添加到 rset 并帮助提供读取服务。

6.4 避免重复请求

不重复执行重复或重试的写入请求的最多一次语义是可取的。关于这些语义是否被线性可实现性所要求还存在一些争论[18, 28]，而许多键-值存储则不具备这一属性。Pegasus 通过可选地支持至多一次语义来同时满足这两方面。

Pegasus 使用经典机制来维护每个客户端的最新请求表[43]，以检测重复请求。这要求相同的服务器处理原始请求和重试请求，类似于经典负载均衡器中的“粘性”要求。实现这一点的简单方法是最初将每个写入请求发送到对象的主服务器。但是，这牺牲了写入的负载平衡。我们通过注意到一个服务器无需看到对象的所有请求——只需要重试请求发送到之前处理它的相同服务器，从而在不牺牲负载平衡的情况下提供重复检测。因此，Pegasus 最初将请求转发到单个检测器节点——由请求的唯一 REQID 决定的服务器确定性选择，而不是键的哈希。它还在数据包标头中写入了应该发送到其他选择的服务器的副本。检测器节点确定请求是否是重复；如果不是，它会处理请求并将其转发到其他选定的服务器。

当键从不受欢迎到受欢迎状态或反之时，需要额外小心地迁移客户端表状态。我们可以通过在过渡期间暂停对该键的 WRITE 来实现这一点。当一个新键变得受欢迎时，控制器从主服务器中检索现有客户端表条目，并将它们传播到所有服务器。当一个受欢迎的键变得不受欢迎时，它会查询所有服务器以获取它们的客户端表，并将它们的聚合（对每个客户端取最新条目）发送到主服务器。完成后，系统可以恢复为该键处理 WRITE。

6.5 服务器选择策略

对于一个请求，应该选择哪个副本？这是一个策略问题，其回答不会影响正确性（即线性可操作性），但会影响 Pegasus 负载均衡的效率。正如第 4.4 节所述，我们当前实现了两种这样的策略。第一个策略是简单地随机选择一个副本，并依靠统计负载平衡。更复杂的策略是使用加权轮询：控制器根据从服务器收集的负载统计信息为每个服务器分配权重，并指示交换机按照权重比例选择副本。

编写复制策略。读操作将被发送到一个副本。写请求可以发送到一个或多个服务器，无论它们是否在当前副本集中。

较大的副本集大小通过为未来的读请求提供更多选项来改善负载平衡，但会增加写操作的成本。对于写操作密集型的工作负载，增加写入成本可能很容易抵消任何负载平衡的好处。

正如第 4.5 节所讨论的那样，交换机跟踪每个复制对象的平均 READs/WRITEs 比率。通过将复制因子设置为与此比率成比例，Pegasus 可以限制开销，而不考虑写入分数。

6.6 额外协议详情

哈希冲突。Pegasus 一致性目录对小键哈希值进行操作，而不是完整的键。如果复制键和非复制键存在哈希冲突，则非复制键的请求可能被错误地转发到不是其主服务器的服务器。为了解决这个问题，每个服务器跟踪当前复制键的所有集合（根据第 6.3 节的控制器保持最新）。有了这些信息，服务器可以将未正确转发的请求转发到正确的主服务器。这种请求链接方法几乎没有性能影响：它只影响到小集合中的哈希冲突。此外，我们只转发访问率较低的未复制键的请求。在极少数情况下，涉及 O(nlogn) 个最受欢迎键之一的哈希冲突中，Pegasus 仅复制其中一个以保证正确性。

版本号溢出。版本号必须单调递增。Pegasus 使用 64 位版本号，使溢出不太可能：需要以我们交换机的全速处理事务超过 100 年。寿命极长的系统或更喜欢较短版本号的系统可以使用标准技术进行版本号绕组。

垃圾回收。在处理复制键的写入时，Pegasus 不会显式地使旧版本无效或删除它。虽然这不会影响正确性-一致性目录将所有请求转发到最新版本-但永久保留过时的副本会浪费服务器上的存储空间。我们通过垃圾回收来解决这个问题。Pegasus 控制器已经通知服务器哪些键是复制的，并定期报告最后完成的版本号。然后，每个服务器都可以检测并安全地删除一个键，如果它具有过时的版本，或者如果键不再被复制（且该服务器不是该键的主节点）。

7 超越单机架

到目前为止，我们已经讨论了单机架、单交换机的 Pegasus 部署。当然，更大的系统需要超越单个机架的扩展性。此外，单机架体系结构在服务器或机架故障时不提供可用性保证：尽管 Pegasus 复制流行对象，但大多数对象仍只有一个副本。这种选择是有意的，因为整个机架故障非常常见，使得在机架内复制对象不足以实现真正的容错。

我们通过一个多机架部署模型来解决这两个问题，其中每个存储服务器的机架及其 ToR 交换机运行一个单独的 Pegasus 实例。工作负载在不同的机架之间进行分区，并使用链式复制[66]将对象复制到多个机架。使用两层一致性哈希来做对象布置。全局配置服务[8, 27]将每个键空间范围映射到一系列 Pegasus 机架的链。在每个机架内，这些键被映射到服务器，如第 5 节所述。实际上，每个键都被映射到一系列服务器，每个服务器都位于不同的机架中。

我们提倡使用此部署模型，因为它仅在每个机架的 ToR 交换机中使用 in-switch 处理。数据中心网络的其余部分保持不变，特别是它不需要任何进一步的数据包路由更改，这已经被认为是网络运营商采用的障碍[56]。其结果是它不能在不同的机架之间平衡流行的键。但是，我们的模拟表明，在所有高工作负载偏差水平之外，这种效果是可以忽略不计的：单个服务器很容易超载，但机架级别的超载不太常见。

复制协议。与原始的链式复制一样，客户端将 WRITE 发送到链的头服务器。每个服务器将请求转发到链中的下一个服务器，直到到达尾服务器，然后回复客户端。客户端将 READ 发送到链的尾部；该服务器直接响应客户端。在每种情况下，如果该对象在该机架中是流行的，则 Pegasus 交换机可以重定向或复制它。

Pegasus 与原始的链式复制协议不同之处在于，它不能假定服务器之间存在可靠的 FIFO 通道。为了处理网络异步性，它重用 Pegasus 交换机提供的版本号来确保一致性。具体而言，我们通过以下方式增强算法 1：当 Pegasus 交换机收到 WRITE 请求时，仅在数据包头中的 VER 不为 null 时，才将 ver_next 加到请求中；否则，它会保持请求中的版本号不变，并将其 ver_next 设置为比该值更大的值（如果尚未）。此修改的效果是，WRITE 请求仅携带来自该链的头服务器 ToR 交换机的版本号；并且在传播沿着链时，编号不会改变。这确保了所有副本以相同的顺序应用 WRITE。

重新配置链。如果 Pegasus 机架故障，可以使用标准的链式复制协议[66]进行替换。注意到故障时，通知配置服务删除该机架所参与的所有链，并添加一个替换。此方法利用了底层链式复制协议的正确性，将 Pegasus 机架视为功能上等效于单个副本。

如果系统重新配置更改了键范围的头机架的身份，则后续的 WRITE 将从不同的头交换机获得版本号。如果新的头机架在旧链中存在，则这些版本号必须大于任何先前完成的写入。如果向链中添加机架作为头，则必须首先更新该机架交换机中的 ver_next，使其大于或等于链中的其他交换机。

如果单个服务器故障，则安全的解决方案是将其整个机架视为有故障并相应地更换它。虽然是正确的，但这种方法很明显是低效的。Pegasus 具有优化的重新配置协议（由于空间限制而省略）。

8 交换机实现

一致性目录（§6）在 Pegasus 中起着核心作用： 它跟踪热门对象及其副本集；分发负载平衡请求；实现基于版本的一致性协议；根据动态工作负载信息更新复制对象集合。在本节中，我们详细介绍了 Pegasus 一致性目录在可编程交换机的数据平面中的实现。

8.1 交换机数据平面实现

图 4 显示了一致性目录数据平面设计的示意图。当一个 Pegasus 数据包进入交换机入口流水线时，查找表会检查该数据包是否引用一个复制对象。然后数据包经过版本号引擎和副本集目录，它们实现基于版本的一致性协议（算法 1 和算法 2）。对于请求数据包，从副本集目录中选择一个或多个服务器，并通过地址重写表更新数据包的目的地。最后，所有 Pegasus 数据包在进入出口流水线之前都要经过统计引擎。

Pegasus一致性目录的交换机数据平面设计

我们利用可编程交换芯片（如 Barefoot 的 Tofino [63]）上提供的两种类型的有状态存储器原语来构建目录：精确匹配查找表和寄存器数组。查找表可以匹配数据包头中的字段，并执行简单的操作，如算术计算、头部重写和元数据操作。然而，查找表只能从控制平面更新。另一方面，寄存器数组通过索引访问，并且可以在数据平面以线速率读取和更新。本节的其余部分详细介绍了每个组件的设计。

复制键查找表：当添加复制键（§6.3）时，控制器将其 KEYHASH 安装到一个精确匹配查找表中。这个表只需要维护 O(nlogn) 个条目，其中 n 是机架中的服务器数量。交换机将每个 Pegasus 数据包头的 KEYHASH 与表中的条目进行匹配。如果匹配成功，将与该条目关联的索引号存储在数据包元数据中，以便在后续阶段选择相应的复制键。

版本号引擎：我们使用两个寄存器数组来构建版本号引擎，如图 5 所示。第一个寄存器数组包含一个单独的元素——下一个版本号。如果数据包是写入请求，寄存器中的版本号会递增，并且交换机会将该版本号写入数据包头中。第二个寄存器数组存储每个复制键的完成版本号，并使用数值 ALU 进行比较和更新版本号（按照算法 2）。比较结果传递到下一阶段。

交换机版本号引擎的设计。一个包含单个元素的寄存器数组用于跟踪下一个版本号。该寄存器在每次写操作时递增。第二个寄存器数组存储了每个复制对象的最新完成版本号。数值运算逻辑单元比较该数组中的值与回复头部中的版本号。

副本集目录：如图 6 所示，我们使用三个寄存器数组构建副本集目录，分别用于存储：(i) 每个副本集的大小，(ii) 指示每个副本集当前包含哪些服务器的位图，以及 (iii) 每个集合中的服务器 ID 列表。在选择 Pegasus 的读取请求的副本时，会读取副本集的大小，并输入选择逻辑单元以计算用于定位列表中的服务器 ID 的索引（选择逻辑可以为写入请求选择任意服务器）。注意，我们将所有复制键的服务器 ID 列表折叠成一个单独的寄存器数组，利用每个键最多可以在 n 台服务器上复制的事实。因此，要定位第 k 个键的第 i 个副本，索引计算为 k ∗ n+i（为简洁起见，我们将在后续讨论中使用相对索引，即公式中的 i）。

交换机复制集目录的设计。该目录使用三个寄存器数组：一个数组用于存储每个复制集的大小；另一个数组维护每个集合的位图，跟踪当前在集合中的哪些服务器；最后一个数组存储每个集合中的服务器ID列表。

如果版本号引擎表明 Pegasus 回复具有更高的版本号，则将副本集的大小重置为 1，并将副本集位图和服务器 ID 列表重置为仅包含回复数据包中的服务器 ID。如果版本号引擎表明版本号相等，则交换机使用位图检查服务器是否已经在副本集中。如果没有，它会更新位图，增加副本集的大小，并将服务器 ID 追加到服务器列表的末尾。

要添加一个新的复制键，控制器将副本集的大小设置为 1，并且将位图和服务器 ID 列表设置为仅包含主服务器。

地址重写表：地址重写表将服务器 ID 映射到相应的 IP 地址和端口，并由控制器保持最新状态以添加服务器。当副本集目录选择单个服务器作为目标时，地址重写表会相应地更新头部。如果副本集目录选择多个服务器（对于写入请求），我们使用交换机上的数据包复制引擎将数据包转发到相应的组播组。

统计引擎：为了检测工作负载中最热门的 O(nlogn) 个键，我们构建了一个统计引擎来跟踪每个键的访问速率。对于复制键，交换机在一个寄存器数组中维护计数器。对于大量非热门键，这种方法显然是不可行的。统计引擎改为对未复制键的请求进行采样，并将其转发到交换机 CPU。交换机 CPU 上的专用程序从采样数据包构建一个访问频率表。采样组件有两个作用：减少对交换机 CPU 的流量和作为高通滤波器，过滤掉访问频率较低的键。控制器扫描两个统计表，确定何时需要复制新的热门键或停止为现有键进行复制，并根据§6.3中的协议进行这些更改。

两个单独的寄存器数组跟踪每个复制键的读取和写入计数。控制器使用这些计数来计算读取/写入比例，而副本集目录中的选择逻辑则使用该比例来决定每个写入请求使用多少个副本。

9 评估

我们的Pegasus实现包括交换机数据平面和控制平面，Pegasus控制器以及内存中的键-值存储。交换机数据平面采用P4 [7]实现，并在Barefoot Tofino可编程交换ASIC [63]上运行。Pegasus控制器采用Python编写。它通过由P4 SDE生成的Thrift API [62]读取并更新交换机数据平面。键-值存储客户端和服务器采用C++实现，使用Intel DPDK [15]进行优化的I/O性能。

我们的实验平台由28个节点组成，每个节点装有双路2.2 GHz英特尔Xeon Silver 4114处理器（共20个核心）和48 GB RAM，运行Ubuntu Linux 18.04。它们连接到一台Arista 7170-64S（基于Barefoot Tofino）可编程交换机，使用Mellanox ConnectX-4 25 Gbit NICs。16个节点充当键-值服务器，12个节点产生客户端负载。

为了评估Pegasus在实际工作负载下的有效性，我们使用并发的开环客户端生成负载，其到达间隔时间遵循泊松分布。总键空间包括一百万个随机生成的键，客户端请求根据均匀分布或倾斜（Zipf）分布选择键。我们将Pegasus与另外两种负载均衡解决方案进行了比较：用于分割键空间的传统静态一致性哈希方案以及NetCache [29]。一致性哈希方案为每个存储服务器分配了16个虚拟节点，以改善负载均衡。此外，我们还评估了支持至多一次语义的Pegasus版本（如§6.4中所述的Pegasus-AMO）。为了与NetCache进行比较，我们通常将键限制在64字节，值限制在128字节，因为这是它可以支持的最大对象值大小。NetCache在交换机数据平面为128字节的值保留了多达1万个空间，占据了交换机内存的相当大部分。相比之下，Pegasus仅消耗总交换机SRAM的不到3.5%。在更大的键和值尺寸下，Pegasus保持相似的性能和内存使用，而NetCache则完全无法运行。

9.1 倾斜的影响

为了测试并比较Pegasus在倾斜工作负载下的性能，我们测量了四个系统在满足99%延迟SLO的条件下的最大吞吐量。我们相对任意地将SLO设置为中位数未负载延迟的5倍（我们看到在不同的SLO下获得了类似的结果）。图7显示了在只读请求不断增加的工作负载倾斜情况下的系统吞吐量。Pegasus即使在工作负载从均匀到高再到极端倾斜（Zipf α = 0.9–1.2）变化时，也能维持相同的吞吐量水平，证明了它在高度倾斜的访问模式下平衡负载的有效性。由于工作负载是只读的，具有至多一次支持的Pegasus（Pegasus-AMO）表现出完全相同的性能。相比之下，一致性哈希系统的吞吐量在更倾斜的工作负载下下降至低至10%。在α = 1.2时，Pegasus的吞吐量比一致性哈希提高了10倍。NetCache提供类似的负载均衡效益。事实上，它的吞吐量随着倾斜而增加，超过了Pegasus。这是因为缓存键的请求直接由交换机处理，而不是存储服务器，尽管这会导致更高的交换机资源开销。

在满足50微秒的99%延迟服务水平目标的前提下，可实现的最大吞吐量。Pegasus成功地重新平衡了请求负载，保持了均匀和不均衡工作负载的类似性能水平。

9.2 读写比率

Pegasus不仅针对读密集型工作负载，还针对写密集型和读写混合工作负载。图8显示了在运行高度倾斜工作负载（Zipf-1.2）时，最大吞吐量在不同写比率下的情况。Pegasus一致性协议允许任何存储服务器处理写请求，并提供强一致性，因此Pegasus可以负载平衡读写请求。因此，Pegasus能够保持高吞吐量水平，无论写比率如何。即使采用至多一次语义，Pegasus-AMO在所有写比率下表现一样好，通过利用请求的REQID（§6.4）的随机性将写请求分发给所有服务器。这与NetCache形成对比，NetCache只能平衡读密集型工作负载；它需要存储服务器处理写操作。因此，随着写比率的增加，NetCache的吞吐量迅速下降，接近静态一致性哈希的水平。即使只有10%的请求是写操作，其吞吐量也下降了80%以上。对于写密集型工作负载，它完全失去了负载均衡的能力。相比之下，Pegasus即使对于写密集型工作负载也能保持高吞吐量，其吞吐量相较于NetCache高出多达11.8倍。需要注意的是，Pegasus的吞吐量随着较高的写比率而下降。这是由于存储服务器上写冲突和缓存失效的增加所导致的。

吞吐量与写入比之间的关系。在各种写入比率范围内，Pegasus保持其负载均衡优势，而NetCache在即使是10%的写入比率下也会遭受显著惩罚。

9.3 可扩展性

为了评估Pegasus的可扩展性，我们在一个倾斜的工作负载（Zipf 1.2）下，逐渐增加存储服务器的数量，并测量其最大吞吐量，同时将其与一致性哈希系统进行比较。如图9所示，随着服务器数量的增加，Pegasus的可扩展性几乎完美。另一方面，一致性哈希的吞吐量在两个服务器后停止扩展：由于严重的负载不平衡，过载的服务器迅速成为整个系统的瓶颈。增加更多的服务器并不能进一步增加总体吞吐量。 我们还评估了使用Pegasus协议的终端主机一致性目录实现的性能，其中使用服务器替代交换机。由于目录需要处理每个客户端请求的两倍数据包（请求和响应），这个实现甚至无法跟上单个服务器的速度 - 这突显了使用像交换机ASIC这样的加速平台作为一致性目录的重要性。

可扩展性。Pegasus在高达16个服务器的情况下几乎呈线性扩展，因为即使在不均衡的工作负载下，没有单个服务器成为瓶颈。

9.4 对象大小

为了测试Pegasus是否能处理不同大小的对象，我们将值的大小从64字节变化到1 KB，并在相同的倾斜工作负载下测量Pegasus的最大吞吐量，以满足99%延迟SLO。我们还绘制了一致性哈希系统在均匀工作负载下的吞吐量。如图10所示，Pegasus在小型和大型对象的负载均衡方面同样有效。在高度倾斜的工作负载下，其吞吐量几乎等同于零倾斜工作负载下一致性哈希的吞吐量。需要注意的是，图中的吞吐量以每秒操作次数表示（随着对象大小增加而自然降低），而不是每秒比特数。

吞吐量与对象大小之间的关系。Pegasus在各种对象大小上提供了有效的负载均衡。传统设计在均匀工作负载下的性能被作为基准线显示出来。

9.5 复制键的数量的影响

保持一致性目录的小规模对于交换机来说是至关重要的，因为交换机的资源非常有限。我们的分析（§4.5）表明，在任意访问模式下，Pegasus只需复制O(nlogn)个最流行的键，以实现负载均衡。这里隐藏了什么常数因子？对于对抗性工作负载而言，它们并不高（例如，8nlogn）[17]。如图11所示，我们展示了在非对抗性Zipf工作负载下它们甚至更低的情况。具体而言，Pegasus只需复制8-16个键即可获得吞吐量的好处，远少于nlogn。虽然这些数字预计会随着更多服务器的增加而增加，但它们仍然轻松保持在交换机寄存器内存的容量范围内。

吞吐量与复制键数量之间的关系。对于这些工作负载，只需要8-16个复制键就可以实现Pegasus的大部分负载均衡优势。

9.6 服务器选择策略

我们实现了两种选择复制对象服务器的策略：随机和加权轮询。我们评估了这两种策略：图12显示了它们在不同工作负载下的最大吞吐量。 当我们使用一组具有相同负载能力的专用同质服务器时，这两种策略在均匀和高度倾斜的工作负载下都非常有效地分配负载。然而，当某些服务器的能力超过其他服务器或者后台进程耗尽其可用容量时，随机策略开始变得不足够。我们通过将一半服务器的处理能力减少50%来评估这一点。如图12所示，随机策略的吞吐量下降了50%，因为较慢的服务器成为性能瓶颈，即使速度较快的服务器仍具有多余的处理能力。通过从服务器收集负载信息并相应地设置权重，加权轮询策略允许较慢和较快的服务器充分利用其处理能力。

比较Pegasus服务器选择策略：在99%延迟服务水平目标为50微秒的情况下的吞吐量。当服务器容量均匀时，随机选择策略提供良好的统计负载平衡；否则，Pegasus的负载感知策略表现更佳。

9.7 处理动态工作负载

最后，我们评估了Pegasus在具有不断变化的键流行度的动态工作负载下，这类工作负载类似于SwitchKV [41]和NetCache [29]。具体来说，我们每10秒选择100个键，并在Zipf分布中改变它们的流行度排名。这里我们考虑了两种动态模式：

• 热榜升温（Hot-in）：将流行度排名中100个最冷门的键提升至榜单顶部，立即使它们成为最热门的对象。这种工作负载代表了对象流行度出现极端波动，我们假设在真实世界的工作负载中很少见。
• 随机（Random）：从10,000个最热门的键中随机选择100个键，并将它们与另一组随机选择的键的流行度进行交换。由于最热门的键更不可能被更改，这种动态性代表了对对象流行度的更为适度的改变。

我们使用Zipf-1.2工作负载和80%利用率来评估这些工作负载下的Pegasus性能。

动态工作负载。Pegasus对对象流行度的变化作出快速反应。

热榜升温（Hot-in）：所有最热门键的流行度突然变化会导致尾部延迟增加。然而，Pegasus能够立即检测到流行度的变化并更新交换机内的一致性目录。这种剧烈的工作负载变化是不太可能发生的，但Pegasus仍能快速做出反应。在100毫秒内，客户端观察到的尾部延迟恢复正常。

随机（Random）：在随机动态模式下，只有少量最热门的键发生变化。因此，Pegasus可以继续为未受影响的键平衡负载，并利用负载感知调度来避免服务器过载。没有观察到99%端到端延迟的变化。

9.8 多机架配置

为了测试多机架配置，我们使用了一个更大（但速度较慢）的集群，其中包含72台配备双1.8 GHz英特尔Xeon E5-2450处理器的服务器。这些服务器分为两个机架，每个机架有24台存储服务器和一个Pegasus交换机，另外还有第三个机架用于客户端机器。每个节点的性能明显较低，主要是因为这些服务器使用不支持DPDK的10 Gbit网卡。

两个包含24台服务器的机架被配置为2副本配置：每个机架为一半的键充当链的头部，另一半的键充当链的尾部。因为两个副本都需要处理写操作，但只有尾部处理读操作，因此添加第二个机架不仅提供了容错性，而且将读吞吐量翻倍；写吞吐量保持不变。图14通过比较单机架和双机架配置来展示这一点，在Zipf α = 1.2的只读工作负载下运行时，双机架配置的吞吐量为单机架配置的1.7倍。在t = 0时，一台机架发生故障。双机架部署能够继续以剩余机架的一半速度处理。当然，单机架部署则完全不可用。

在机架发生故障期间，单机架与多机架配置的吞吐量比较。在故障发生后（t = 0），多机架配置继续处理请求，但会损失一些容量。

10 相关工作

负载均衡。在大规模键值存储中，过去的系统通过三种方式解决了负载不均衡的问题。一致性哈希[30]和虚拟节点[12]被广泛使用，但在工作负载变化时表现不佳。基于迁移[11、32、61]和随机性[49]的解决方案可用于平衡动态工作负载，但这些技术引入了额外的开销，并且对处理高偏斜度的能力有限。EC-Cache [57]使用纠删码来平衡负载，将值分割和复制，但最适合于数据密集型集群中的大键。SwitchKV [41]通过使用交换机将负载平衡到基于闪存的存储层，并路由到内存缓存层；但当存储层在内存中时，它无法对变化的负载做出足够快速的反应。NetCache [29]直接在可编程数据平面交换机中缓存值；虽然这提供了出色的吞吐量和延迟，但值的大小受到交换机硬件限制。

另一类负载均衡器旨在平衡第4层流量，如HTTP，在一组动态后端服务器之间。这些系统可以作为服务器集群实现，如Ananta [54]、Beamer [52]和Maglev [16]；或者使用交换机，如SilkRoad [47]或Duet [20]。这些系统旨在平衡长时间存在的流量，在服务器之间分配负载，而Pegasus则平衡单个请求数据包的负载。

Prism [23]通过迁移TCP和TLS连接提供了一种执行请求级负载平衡的方法，这种方法作为Pegasus的一种替代UDP协议的方式可能是有用的。

几个新系统使用可编程交换机进行应用特定的负载平衡协议。R2P2 [33]为无状态服务负载均衡RPC，其中任何请求都可以由任何服务器处理。Harmonia [69]允许在复制系统中针对读请求进行优化转发，通过跟踪并发写操作的进行情况。

基于目录的一致性。目录式一致性协议已经被用于各种共享内存多处理器和分布式共享内存系统[4、19、22、31、34、36、37、40]。这些系统可以被视为具有固定大小键（地址）和值（缓存行或页面）的键值存储。目录协议也已经被用于一般的键值存储；IncBricks [44]使用分布式目录在连接到数据中心交换机的网络处理器中缓存值来实现网络中的键值存储。键具有指定的主节点，参与写操作和一致性操作，限制了写密集型工作负载的负载平衡机会。Pegasus仅在服务器中存储键和值，并且其一致性协议允许任何存储服务器处理写请求，因此Pegasus可以平衡读和写密集型工作负载。这两个系统都可以扩展到机架外并容忍故障：IncBricks在单个服务器级别上实现；Pegasus在机架级别上实现。

11 结论

通过Pegasus，我们已经证明可编程交换机可以改善存储应用程序的负载均衡。使用我们的网络内一致性目录协议，交换机负责放置最受欢迎的键。这使得可能采用传统方法无法实现的新的数据放置策略，例如在每次写入时重新分配副本集合或基于细粒度负载测量选择读取副本。最终结果是，相对于一致性哈希工作负载，Pegasus将可达到满足延迟SLO的吞吐量水平提高了10倍。这使得支持特定工作负载所需的集群规模大幅减小。更广泛地说，我们相信Pegasus提供了可编程数据平面交换机非常适合的应用类别的示例。它将网络设备的经典用例——负载均衡——推向了下一个级别，并将其与应用层协议集成在一起。