# Maglev：一种快速可靠的软件网络负载均衡器

丹尼尔·E·艾森布德，程逸，卡洛·孔塔瓦利，科迪·史密斯，

罗曼·科诺诺夫，埃里克·曼 - 希尔舍，阿尔达斯·奇林吉罗格鲁，本·切尼，

尚文涛†\* 和吉纳·迪伦·侯赛因‡\*

谷歌公司 †加利福尼亚大学洛杉矶分校 ‡ SpaceX

[[e-mail]](mailto:[e-mail])

> Maglev 是谷歌的网络负载均衡器，它是运行在普通 Linux 服务器上的大型分布式软件系统。与传统的硬件网络负载均衡器不同，它不需要专门的物理机架部署，其容量可以通过增加或减少服务器进行轻松调整。网络路由器通过等价多路径（ECMP）将数据包均匀分配到 Maglev 机器；每台 Maglev 机器然后将数据包匹配到相应的服务并均匀分配到服务端点。为了适应高并且不断增长的流量，Maglev 特别优化了数据包处理性能。单台 Maglev 机器能够承载 10Gbps 链路饱和小包。Maglev 还配备了一致性哈希和连接跟踪功能，以尽量减少意外故障和失败对面向连接的协议的负面影响。Maglev 自 2008 年以来一直在为谷歌的流量服务。它支持了谷歌服务的全球快速增长，并为谷歌云平台提供了网络负载均衡。

## 1 引言

谷歌是全球互联网流量的主要来源 [[29,](#bookmark1) [30](#bookmark2)]。它提供了数百个面向用户的服务，此外还在快速增长的*云平台*[[6](#bookmark3)] 上托管了更多的服务。谷歌的热门服务，如*谷歌搜索*和*Gmail*，每秒钟都会从全球各地接收到数百万的查询请求，对底层服务基础设施提出了巨大的需求。

为了满足这样高的需求并保持低延迟，谷歌服务托管在世界各地的多个服务器集群上。在每个集群内，将流量负载均匀分配到这些服务器上是至关重要的，以便有效地利用资源，使得没有单个服务器过载。因此，网络负载均衡器成为谷歌生产网络基础设施的一个关键组件。


图 1: 硬件负载均衡器与 Maglev。

网络负载均衡器通常由多个设备组成，这些设备在逻辑上位于路由器和服务端点（通常是 TCP 或 UDP 服务器）之间，如图 [1](#bookmark4) 所示。负载均衡器负责将每个数据包与其对应的服务匹配，并将其转发到该服务的一个端点。

传统的网络负载均衡器一般是作为专用硬件设备实现的 [[1,](#bookmark5) [2,](#bookmark6) [3,](#bookmark7) [5,](#bookmark8) [9,](#bookmark9) [12,](#bookmark10) [13](#bookmark11)]，这种方式有几个限制。首先，它们的可扩展性通常受到单个单元最大容量的限制，使得无法跟上谷歌的流量增长。其次，它们不能满足谷歌对高可用性的需求。虽然它们通常成对部署以避免单点故障，但它们只提供*1+1 冗余*。第三，它们缺乏快速迭代所需的灵活性和可编程性，因为即使可能也通常很难修改硬件负载均衡器。第四，它们的升级成本高昂。增加硬件负载均衡器的容量通常涉及购买新硬件以及物理部署。由于所有这些限制，我们研究并寻求了替代解决方案。

由于所有服务都托管在充满商品服务器的集群中，我们可以将网络负载均衡器构建为在这些服务器上运行的分布式软件系统。软件负载均衡系统比其硬件对应物有许多优点。我们可以通过采用*扩展出*模型来解决可扩展性问题，其中负载均衡器的容量可以通过增加系统中的机器数量来提升：通过 ECMP 转发，流量可以均匀分布在所有机器上。系统提供*N+1 冗余*，从而提高了可用性和可靠性。通过我们自己控制整个系统，我们可以快速添加、测试和部署新功能。与此同时，负载均衡器本身的部署大大简化：系统只使用集群内现有的服务器。我们还可以将服务分配到同一集群中的多个负载均衡器*碎片*之间，以实现性能隔离。

尽管所有这些优点，软件网络负载均衡器的设计和实现都非常复杂和挑战性。首先，系统中的每台单独的机器都必须提供高吞吐量。设*N*为系统中的机器数量，*T*为单台机器的最大吞吐量。系统的最大容量由*N* × *T*决定。如果*T*不够高，系统为所有服务提供足够容量将是不经济的 [[22](#bookmark12)]。整个系统还必须提供 *连接持久性*：属于同一连接的包应始终被定向到同一服务端点。这确保了服务质量，因为集群非常动态，故障相当常见 [[23,](#bookmark13) [40](#bookmark14)]。

本文介绍了 Maglev，一种快速可靠的软件网络负载均衡系统。自 2008 年以来，Maglev 一直是谷歌前端服务基础设施的关键组成部分，目前几乎为谷歌的所有入站用户流量提供服务。通过利用最近的高速服务器网络技术的进步 [[18,](#bookmark15) [41,](#bookmark16)[35,](#bookmark17)[31](#bookmark18)]，每台 Maglev 机器都能以小包达到线速吞吐量。通过*一致性哈希*和*连接跟踪*，Maglev 在频繁变化和意外故障中提供可靠的包传送。尽管本文描述的一些技术已存在多年，但本文展示了如何使用这些技术构建一个运行的系统。本文的主要贡献是：1）介绍 Maglev 的设计和实现，2）分享在全球范围内运行 Maglev 的经验，以及 3）通过广泛的评估展示 Maglev 的能力。

## 2 系统概述

本节提供了 Maglev 作为网络负载均衡器的工作概述。我们首先简要介绍了谷歌的前端服务架构，然后描述了如何配置 Maglev 系统。


图 2：Maglev 数据包流。

### 2.1 前端服务架构

Maglev 部署在谷歌的前端服务地点，包括各种大小的集群。为简单起见，本文只关注在较小的集群中的设置，下面简要描述了较大集群的设置。图 [2](#bookmark19) 显示了谷歌在小集群设置中的前端服务架构概览。

每个谷歌服务都有一个或多个*虚拟 IP 地址*（VIP）。VIP 与物理 IP 不同，它不是分配给特定网络接口，而是由 Maglev 后面的多个服务端点提供服务。Maglev 将每个 VIP 与一组服务端点关联，并通过 BGP 向路由器宣告它；路由器反过来向谷歌的骨干网宣告 VIP。VIP 网络的聚合被宣告到 Internet 上，使它们全球可访问。Maglev 处理 IPv4 和 IPv6 流量，下面的所有讨论对两者都同样适用。

当用户试图访问托管在谷歌的一个服务时，他们首先通过 DNS 解析服务的域名。Google 公共 DNS[[38](#bookmark20)]（和其他 DNS 服务）返回 VIP 作为响应。用户的客户端根据得到的 IP 地址发起连接，数据包由因特网中的路由器导向谷歌的骨干网。路由器在骨干网上的尽可能靠近用户的地方将数据包转交给 Maglev。

当路由器接收到 VIP 数据包时，它通过 ECMP 将数据包转发给集群中的一个 Maglev 机器，因为所有 Maglev 机器都以相同的成本声明 VIP。当 Maglev 机器接收到数据包时，它从与 VIP 关联的服务端点集合中选择一个端点，并使用*通用路由封装*（GRE）封装数据包，外部 IP 头部目标指向端点。

当数据包到达所选的服务端点时，它被解封装并消耗掉。准备好的响应被放入一个 IP 数据包中，源地址是 VIP，目标地址是用户的 IP。我们使用*直接服务器返回*（DSR）直接将响应发送给路由器，这样 Maglev 就不需要处理返回的数据包，这些数据包通常更大。本文关注的是用户进入流量的负载均衡。DSR 的实现超出了本文的范围。


图 3：Maglev 配置（BP 代表后端池）。

对于大型集群的设置更为复杂：为了在大规模构建集群，我们希望避免需要将 Maglev 机器放置在与路由器相同的第二层域中，因此在路由器后面部署了硬件封装器，它将数据包从路由器隧道到 Maglev 机器。

### 2.2 Maglev 配置

如上一小节所述，Maglev 负责向路由器声明 VIP，并将 VIP 流量转发到服务端点。因此，每台 Maglev 机器都包含一个控制器和一个转发器，如图 [3](#bookmark21) 所示。控制器和转发器都从配置对象中了解要服务的 VIP，这些配置对象可以从文件中读取，也可以通过 RPC 从外部系统接收。

在每台 Maglev 机器上，控制器定期检查转发器的健康状态。根据结果，控制器决定是否通过 BGP 宣告或撤销所有 VIP。这确保路由器只将数据包转发给健康的 Maglev 机器。

Maglev 机器接收到的所有 VIP 数据包都由转发器处理。在转发器处，每个 VIP 都配置有一个或多个后端池。除非另有说明，Maglev 的后端为服务端点。后端池可能包含服务端点的物理 IP 地址；也可能递归包含其他后端池，这样就不需要重复指定频繁使用的后端集合。每个后端池，根据其特定的需求，都与一个或多个健康检查方法关联，所有的后端都通过这些方法进行验证；数据包只会被转发到健康的后端。由于同一服务器可能包含在多个后端池中，健康检查通过 IP 地址进行去重，以避免额外的开销。


图 4：Maglev 转发器结构。

转发器的*配置管理器*负责在改变转发行为之前解析和验证配置对象。所有配置更新都是原子提交的。由于配置推送或健康检查的延迟，同一集群内的 Maglev 机器的配置可能会暂时失去同步。然而，一致性哈希将使得在这些非常短的窗口期间，Maglev 与类似后端池之间的连接重叠大部分成功。

在同一集群中可能部署多个*碎片*（shards）的 Maglev。不同的 Maglev 碎片配置不同，服务不同的 VIP 集合。碎片对于提供性能隔离和确保服务质量非常有用。它也适用于在不干扰常规流量的情况下测试新功能。为了简单起见，我们在这篇文章中假设每个集群有一个碎片。

## 3 转发器的设计和实现

转发器是 Maglev 的一个关键组件，因为它需要快速且可靠地处理大量的数据包。本节将解释 Maglev 转发器的关键模块的设计和实现细节，以及设计背后的原理。

### 3.1 总体结构

图 [4](#bookmark22) 展示了 Maglev 转发器的总体结构。转发器从 NIC（网络接口卡）接收数据包，用适当的 GRE/IP 头部重写它们，然后将它们送回 NIC。Linux 内核不参与此过程。

NIC 接收的数据包首先被转发器的*定向模块*处理，该模块计算数据包的*5 元组哈希*[1](#bookmark23)，并根据哈希值将它们分配到不同的*接收队列*。每个接收队列都连接到一个数据包重写线程。数据包线程首先尝试将每个数据包匹配到配置的 VIP。这个步骤过滤掉目标不是 VIP 的无关数据包。然后它重新计算数据包的 5 元组哈希，并在*连接跟踪表*中查找哈希值（在第 [3.3](#bookmark24) 节中介绍）。我们不重用定向模块的哈希值以避免跨线程同步。

连接表存储了近期连接的后端选择结果。如果找到匹配且选定的后端仍然健康，结果就直接重用。否则线程会查询*一致性哈希模块*（在第 [3.4](#bookmark25) 节中介绍）并为数据包选择一个新的后端；它还会在连接表中添加一个条目，以供具有相同 5 元组的未来数据包使用。如果没有可用的后端，数据包将被丢弃。转发器为每个数据包线程维护一个连接表以避免访问冲突。在选择了后端之后，数据包线程将数据包用适当的 GRE/IP 头部封装，并将它发送到连接的*发送队列*。然后*复用模块*轮询所有的发送队列，并将数据包传递给 NIC。

定向模块执行 5 元组哈希，而不是轮询调度有两个原因。首先，它有助于降低由于不同的数据包线程处理速度变化而在连接内部引起的数据包重排序的概率。其次，有了连接跟踪，转发器只需要为每个连接执行一次后端选择，从而节省时钟周期并消除由后端健康更新的竞态条件引起的后端选择结果的不同可能性。在少数情况下，给定的接收队列可能会填满，在这种情况下，定向模块会回落到轮询调度，并将数据包传播到其他可用的队列。这种后备机制在处理具有相同 5 元组的大量数据包时特别有效。

### 3.2 快速数据包处理

Maglev 转发器需要尽可能快地处理数据包，以便以成本效益的方式将服务能力扩展到满足 Google 流量的需求。我们设计它以线速（在 Google 的集群中通常为 10Gbps）转发数据包。这对于 1500 字节的 IP 数据包来说，相当于 813Kpps（每秒数据包）。然而，我们的要求要严格得多：我们必须有效地处理非常小的数据包，因为传入的请求通常体积较小。假设 IP 数据包的平均大小为 100 字节，转发器必须能够以 9.06Mpps 的速度处理数据包。这一小节描述了我们采用的关键技术，以达到并超过这个数据包处理速度。

> 1 数据包的 5 元组指的是源 IP，源端口，目标 IP，目标端口和 IP 协议号。


图 5：数据包进入和离开转发器的流动。

Maglev 是在商用 Linux 服务器上运行的用户空间应用程序。由于 Linux 内核网络堆栈相当消耗计算资源，而 Maglev 并不需要内核堆栈的任何功能，因此让 Maglev 完全绕过内核进行数据包处理是很有必要的。在 NIC 硬件的适当支持下，我们开发了一种机制，可以在转发器和 NIC 之间移动数据包，而不涉及内核，如图 [5](#bookmark26) 所示。当 Maglev 启动时，它预先分配一个数据包池，该池在 NIC 和转发器之间共享。定向模块和复用模块都维护一个*环形队列*的指针，指向数据包池中的数据包。

定向模块和复用模块都维护环形队列的三个指针。在接收端，NIC 将新接收的数据包放在*接收*指针处并推进它。定向模块将接收的数据包分发给数据包线程，并推进*处理*指针。它还从数据包池中预留未使用的数据包，将它们放入环形队列并推进*预留*指针。这三个指针如箭头所示的追逐。类似地，在发送端，NIC 发送指针指向的数据包并推进它。复用模块将由数据包线程重写的数据包放入环形队列，并推进*就绪*指针。它还将 NIC 已发送的数据包返回到数据包池，并推进*回收*指针。注意，转发器并不在任何地方复制数据包。

为了减少昂贵的边界穿越操作，我们尽可能批量处理数据包。此外，数据包线程彼此之间不共享任何数据，防止了它们之间的竞争。我们将每个数据包线程固定到一个专用的 CPU 核心，以确保最佳性能。有了所有这些优化，Maglev 能够以小数据包的线速进行处理，如第 [5.2](#bookmark27) 节所示。

此外，Maglev 对每个数据包路径的延迟增加很小。通常情况下，数据包线程处理每个数据包大约需要 350ns。有两种特殊情况可能使数据包处理时间更长。因为转发器批量处理数据包，所以当每批数据包达到足够大或定时器到期时，每批数据包就会被处理。在实践中，我们将定时器设置为 50μs。因此，如果 Maglev 显著地未负载满，每个数据包最坏情况下将会增加 50μs 的延迟。这种情况下的一个可能的优化是动态调整批量大小 [[32]](#bookmark28)。Maglev 可能增加额外处理延迟的另一个情况是当 Maglev 过载时。Maglev 可以缓冲的最大数据包数量是数据包池的大小；超过这个数量的数据包将会被 NIC 丢弃。假设数据包池大小为 3000，转发器可以处理 10Mpps，处理所有缓冲数据包大约需要 300μs。因此，如果 Maglev 严重过载，每个数据包可能增加最多 300μs 的延迟。幸运的是，这种情况可以通过适当的容量规划和按需添加 Maglev 机器来避免。

### 3.3 后端选择

一旦数据包与 VIP 匹配，我们需要从 VIP 的后端池中为该数据包选择一个后端。对于像 TCP 这样的面向连接的协议，将连接的所有数据包发送到同一个后端是至关重要的。我们采用了两部分策略来实现这一目标。首先，我们使用一种新型的一致性哈希来选择后端，这种方法可以非常均匀地分发流量。然后，我们在本地连接跟踪表中记录选择结果。

Maglev 的连接跟踪表使用固定大小的哈希表来映射数据包的 5 元组哈希值到后端。如果数据包的哈希值在表中不存在，Maglev 会为该数据包指定一个后端，并在表中存储该分配。否则，Maglev 将简单地复用先前分配的后端。这确保了属于同一连接的数据包总是被发送到相同的后端，只要该后端仍然能够服务它们。当后端集合发生变化时，例如后端上下线、增加或移除，或者后端权重改变时，连接跟踪非常方便。

然而，仅依靠 Maglev 的连接跟踪在我们的分布式环境中是不够的。首先，它假设具有相同 5 元组的所有数据包总是被发送到同一个 Maglev 机器。由于 Maglev 前面的路由器通常不提供连接亲和性，当 Maglev 机器集合改变时，这个假设就不成立了。不幸的是，这样的变化是无法避免的，可能会出于各种原因而发生。例如，在升级集群中的 Maglev 时，我们会逐个重启机器，先从每台机器上排空流量，然后在 Maglev 开始再次服务时恢复它。这个过程可能会持续超过一个小时，期间 Maglev 集合会不断变化。我们也有时会添加、移除或替换 Maglev 机器。所有这些操作都会使标准的 ECMP 实现在大规模上洗牌流量，导致连接在中途切换到不同的 Maglev。新的 Maglev 将没有正确的连接表条目，所以如果后端同时发生变化，连接就会断开。

第二个理论上的限制是，连接跟踪表的空间有限。在高负载或 SYN 洪水攻击下，表可能会填满。由于 Maglev 只在条目过期时从连接表中清除条目，所以一旦表满了，我们将需要为每个无法放入表中的数据包选择一个后端。虽然在实践中，现代机器上的内存充足，但在我们与

其他服务共享机器的部署中，我们可能需要严格限制连接表的大小。

如果发生了上述任何一种情况，我们就不能再依赖连接跟踪来处理后端变化。因此，Maglev 还提供了一致性哈希来确保在这种情况下可靠地传送数据包。

### 3.4 一致性哈希

解决连接跟踪限制的一种可能方法是在所有 Maglev 机器之间共享连接状态，例如在分布式哈希表中，如 [[34](#bookmark29)] 所建议的。然而，这将对转发性能产生负面影响——请记住，即使在同一 Maglev 机器的不同数据包线程之间也不共享连接状态，以避免争用。

一个性能更好的解决方案是使用本地一致性哈希。一致性哈希 [[28](#bookmark30)] 或者称为会合哈希 [[38](#bookmark31)] 的概念首次在 1990 年代被引入。其思想是生成一个大的查找表，每个后端在表中占据一定数量的条目。这些方法提供了两个 Maglev 也需要的后端选择的可靠性特性：

• *负载均衡*：每个后端将接收几乎相等数量的连接。

• *最小化干扰*：当后端集合变化时，一个连接可能会被发送到和之前相同的后端。

Pseudocode 1 Populate Maglev hashing lookup table.
1: function POPULATE
2:    for each i < N do next[i] ← 0 end for
3:    for each j < M do entry[ j] ← −1 end for
4:    n ← 0
5:    while true do
6:      for each i < N do
7:          c ← permutation[i][next[i]]
8:          while entry[c] ≥ 0 do
9:             next[i] ← next[i] +1
10:            c ← permutation[i][next[i]]
11:         end while
12:         entry[c] ← i
13:         next[i] ← next[i] +1
14:         n ← n+1
15:         if n = M then return end if
16:      end for
17:   end while
18: end function

[28](#bookmark30) 和 [38](#bookmark31) 都将最小化干扰优先于负载均衡，因为它们的设计是为了优化少量服务器上的 web 缓存。然而，Maglev 采取了相反的方法，原因有两个。首先，对 Maglev 来说，尽可能均匀地平衡后端负载至关重要。否则，后端必须过度配置以适应峰值流量。Maglev 可能有数百个后端对于某些 VIP，我们的实验表明，[[28]](#bookmark30) 和 [[38](#bookmark31)] 都需要对每个 VIP 提供过大的查找表，以提供 Maglev 所期望的负载均衡水平。其次，虽然最小化查找表的破坏很重要，但 Maglev 可以容忍小量的破坏。在稳态下，查找表的变化不会导致连接重置，因为连接对 Maglev 机器的亲和性不会同时改变。当连接对 Maglev 的亲和性改变时，重置与查找表破坏的数量成正比。

考虑到这些因素，我们开发了一种新的一致性哈希算法，我们称之为*Maglev 哈希*。Maglev 哈希的基本思想是为每个后端指定所有查找表位置的优先列表。然后所有的后端轮流填充他们最喜欢的还空着的表位置，直到查找表完全填满。因此，Maglev 哈希为每个后端提供了查找表的几乎相等的份额。可以通过改变后端的轮换相对频率来达到异构后端权重；具体的实现细节在这篇论文中没有描述。

| |B0|B1|B2|
|--|--|--|--|
|0 | 3| 0| 3|
| 1| 0| 2| 4|
| 2| 4| 4| 5|
| 3| 1| 6| 6|
| 4| 5| 1| 0|
| 5| 2| 3| 1|
| 6| 6| 5| 2|

*后端的排列表*

| | Before | After |
|----| ------ | ----- |
|0 | B1 | B0 |
|1 | B0 | B0 |
|2 | B1 | B0 |
|3 | B0 | B0 |
|4 | B2 | B2 |
|5 | B2 | B2 |
|6 | B0 | B2 |

*在后端B1 被移除之前和之后的查找表。*

设*M*是查找表的大小。后端*i*的优先列表储存在*permutation*[ *i*] 中，它是数组 (0 ..*M* - 1) 的一个随机排列。作为生成*permutation*[ *i*] 的一个高效方式，每个后端被分配一个唯一的名字。我们首先使用两种不同的哈希函数来哈希后端的名字，生成两个数*offset*和*skip*。然后我们使用以下方法生成*permutation*[ *i*]：

*offset*-*h*1 (*name*[ *i*]) mod *M*

*skip*-*h*2 (*name*[ *i*]) mod (*M* - 1) + 1

*permutation*[ *i*][ *j*] (*offset*+ *j* × *skip*) mod *M*

*M*必须是一个质数，这样所有的*skip*都和它互质。设*N*是 VIP 后端池的大小。其查找表是使用伪代码 [1.](#bookmark32) 填充的。我们使用*next*[ *i*] 来追踪在后端*i*的排列中要考虑的下一个索引；最终的查找表存储在数组*entry*中。在外部*while*循环的主体中，我们遍历所有的后端。对于每个后端*i*，我们从*permutation*[ *i*] 中找到一个尚未被填充的候选索引*c*，并用该后端填充它。循环继续进行，直到表中的所有条目都被填充。

该算法保证能够完成。其最坏情况的时间复杂度是*O*(*M*^2)，这只在后端数量和查找表条目数量一样多，并且所有的后端都哈希到同一种排列的情况下发生。为了避免这种情况发生，我们总是选择*M*使得*M* >> *N*。平均时间复杂度是*O*(*M*log*M*)，因为在步骤*n*，我们预计算法需要*M/M−n*次尝试才能找到一个空的候选索引，所以总的步骤数是Σ*M/n=1 M/n*。每个后端在查找表中将占据⌊M/N⌋或⌈M/N⌉个条目。因此，不同后端占据的条目数量最多相差 1。在实践中，我们选择*M*比 100 × *N*大，以确保后端被分配到的哈希空间的差异最多为 1%。生成随机排列的其他方法，如 Fisher-Yates Shuffle [[20](#bookmark34)]，使用更多的状态生成更好的排列，并且也可以在这里工作。

我们使用表 [1](#bookmark33) 中的例子来说明 Maglev 哈希是如何工作的。假设有 3 个后端，查找表的大小是 7，三个后端的 (offset, skip) 对是 (3, 4)，(0, 2) 和 (3, 1)。生成的排列表显示在左列，而在后端*B*1 被移除之前和之后的查找表显示在右列。如例子所示，查找表在*B*1 存在和不存在的情况下都在后端之间平均分配。在*B*1 被移除后，除了需要更新所有包含*B*1 的条目外，只有一个其他条目（行 6）需要被改变。在实践中，对于更大的查找表，Maglev 哈希对后端的变化具有相当的抵抗力，我们在第 [5.3](#bookmark35) 节中展示了这一点。

## 4 运营经验

Maglev是一个高度复杂的分布式系统，已经为Google服务超过六年。我们在全球范围内运营它时学到了很多。本节描述了Maglev如何随着年月的推移而适应我们不断变化的需求，以及我们建立了一些什么工具来监控和调试系统。

### 4.1 Maglev的演变

现今的Maglev在许多细节上与原始系统有所不同。大部分的变化，比如IPv6支持的添加，都是因为软件架构的可扩展性而顺利进行的。这个小节讨论了Maglev自诞生以来对实现和部署的两个重大改变。

#### 4.1.1 故障切换

Maglev机器最初是以活动-被动配对的形式部署的，以提供故障恢复能力，就像它们替代的硬件负载均衡器一样。在正常情况下，只有活动机器才会服务流量。当一个活动机器变得不健康时，其被动伙伴会接管并开始服务。由于Maglev散列，连接在这个过程中通常不会中断，但这种设置也有一些缺点。它使资源利用率低下，因为一半的机器总是处于闲置状态。它也阻止我们将任何VIP的规模扩大到超过单个Maglev机器的容量。最后，活动和被动机器之间的协调非常复杂。在这种设置中，机器的通告者会监视彼此的健康状况和服务优先级，如果它们失去了对彼此的视线，就会提升自己的BGP优先级，并采用各种平局破解机制。
通过转移到ECMP模型，我们获得了大量的容量、效率和运营简单性。虽然Maglev散列继续保护我们免受偶然的ECMP抖动的影响，但我们可以将一个VIP的容量乘以路由器的最大ECMP集大小，并且所有的机器都可以得到充分的利用。


图6：MaglevVIP匹配。

#### 4.1.2 数据包处理

Maglev最初使用Linux内核网络栈进行数据包处理。它必须使用内核套接字与NIC进行交互，这给数据包处理带来了显著的开销，包括

硬件和软件中断、上下文切换和系统调用[26]。每个数据包还必须从内核复制到用户空间，然后再复制回去，这也带来了额外的开销。Maglev不需要TCP/IP堆栈，但只需要为每个数据包找到一个适当的后端，并使用GRE进行封装。因此，当我们引入内核绕过机制时，我们没有失去任何功能，而且大大提高了性能——每个Maglev机器的吞吐量提高了五倍以上。

### 4.2 VIP Matching

在谷歌的生产网络中，每个集群被分配一个可以全球路由的外部 IP 前缀。例如，图 [6](#bookmark36) 中的集群 C1 有前缀 74.125.137.0/24。同一个服务在不同的集群中被配置为不同的 VIP，用户通过 DNS 被引导到其中一个。例如，Service1 在 C1 中配置为 74.125.137.1，在 C2 中配置为 173.194.71.1。

谷歌有几种不同的集群类别，服务于不同的 VIP 集。对于同一类别的集群，外部前缀长度是相同的，但对于不同的集群类别可能是不同的。有时，在紧急情况下，我们需要通过 Maglev 封装将流量重定向到不同的集群。因此，我们需要目标 Maglev 能够正确地分类任意其他集群的流量。一个可能的解决方案是在所有可能接收到重定向流量的集群中定义所有的 VIP，但这会引起同步和可扩展性问题。

相反，我们实现了一个特殊的编号规则和一个新颖的 VIP 匹配机制来处理这个问题。对于每个集群类别，我们在该类别的所有集群中为每个 VIP 分配相同的后缀。然后我们使用一个前缀/后缀匹配机制进行 VIP 匹配。首先，进来的数据包通过最长前缀匹配，确定它是为哪个集群类别准备的。然后，它通过特定于那个集群类别的最长后缀匹配，确定它应该发送到哪个后端池。为了减少在紧密的时间范围内在全球范围内保持配置同步的需要，我们预先为每个集群类别配置一个大的前缀组，从中为同一类别的新集群分配前缀。这样，一个 Maglev 可以正确地为它从未听说过的集群原本应该服务的流量服务。

因此，每个 VIP 被配置为一个\<前缀组，IP 后缀，端口，协议\>元组。以图 [6](#bookmark36) 为例。假设 C2 和 C3 属于同一类别，如果一个向<173.194.71.1>的包在 C2 接收，但 Maglev 确定 C2 的端点都不能为这个包服务，它会将包封装并通过隧道向 C3 中相同服务的 VIP 地址（173.194.72.1）发送。然后，C3 中的一个 Maglev 将解封装这个包，并使用前缀/后缀匹配将内部包匹配到 Service1，这个包将由 C3 中的一个端点来服务。

这个 VIP 匹配机制是特定于 Google 的生产设置的，但它提供了一个软件负载均衡器可以提供的快速原型制作和迭代的价值的好例子。

**4.3 碎片处理**

迄今为止所描述的系统并未覆盖碎片 (IP fragmentation) 的特殊情况。碎片需要特殊处理，因为 Maglev 对大多数 VIP 执行 5 元组哈希，但碎片并不都包含完整的 5 元组。例如，如果将一个大数据报分割为两个碎片，第一个碎片将包含 L3 和 L4 首部，而第二个碎片仅包含 L3 首部。因此，当 Maglev 接收到非第一个碎片时，仅凭该数据包的首部无法做出正确的转发决策。

为了正确处理碎片，Maglev 必须满足两个要求。首先，同一个数据报的所有碎片必须由同一个 Maglev 接收。其次，Maglev 必须对非第一个碎片、第一个碎片和非第一个碎片做出一致的后端选择决策。

通常情况下，我们不能依赖 Maglev 前面的硬件单独满足第一个要求。例如，某些路由器在第一个碎片使用 5 元组哈希，而对于非第一个碎片则使用 3 元组哈希。因此，我们在 Maglev 中实现了一种通用解决方案来应对任何碎片哈希行为。每个 Maglev 都配置了一个特殊的后端池，包含了集群中的所有 Maglev。当接收到一个碎片时，Maglev 使用 L3 首部计算其 3 元组哈希，并根据哈希值将其转发给后端池中的一个 Maglev。由于同一个数据报的所有碎片包含相同的 3 元组，它们将被重定向到同一个 Maglev。我们使用 GRE 递归控制字段来确保碎片只被重定向一次。

为了满足第二个要求，Maglev 使用相同的后端选择算法来为非碎片数据包和第二跳第一个碎片选择后端（通常在不同的 Maglev 实例上）。它维护一个固定大小的碎片表，记录第一个碎片的转发决策。当同一台机器接收到第二跳非第一个碎片时，Maglev 在碎片表中查找并立即转发，如果找到匹配项；否则，它会将其缓存在碎片表中，直到接收到第一个碎片或条目过期。

这种方法有两个限制：它会引入对碎片数据包的额外跳数，这可能导致数据包重新排序。它还需要额外的内存来缓冲非第一个碎片。由于数据包重新排序可能发生在网络的任何位置，我们依赖端点来处理乱序数据包。在实践中，只允许少数 VIP 接收碎片，我们可以轻松地提供足够大的碎片表来处理它们。

**4.4 监控和调试**

我们始终像对待任何其他生产系统一样，持续监控 Maglev 的健康状况和行为。例如，我们同时使用黑盒和白盒监控。我们的黑盒监控由分布在世界各地的代理程序组成，定期检查已配置的 VIP 的可达性和延迟。对于白盒监控，我们通过 HTTP 服务器从每个 Maglev 机器导出各种指标，并且监控系统定期查询每个服务器以了解最新的 Maglev 服务状态详情。当观察到异常行为时，系统会发送警报。

由于 Maglev 具有分布式特性，从路由器经过 Maglev 到服务端点存在多个路径。然而，当我们能够确定特定数据包在网络中的精确路径时，调试就变得更加容易。因此，我们开发了名为*packettracer*的工具，类似于 X-trace [[21]](#bookmark38)。Packet-tracer 构造并发送带有指定 L3 和 L4 首部的特殊标记的 Maglev 可识别负载。负载包含 Maglev 发送调试信息的接收器 IP 地址。这些数据包通常针对特定的 VIP，并以正常路由方式发送到我们的前端位置。当 Maglev 机器接收到 packet-tracer 数据包时，它会像往常一样转发数据包，并同时发送调试信息（包括机器名称和所选的后端）到指定的接收器。


图 7：典型日子中一个集群中所有服务端点上标准化负载的平均值、标准差和变异系数。

由于处理 packet-tracer 数据包的成本很高，Maglev 对其进行了速率限制。这个工具在调试生产问题时非常有帮助，尤其是当路径中有多台 Maglev 机器时，比如碎片重定向的情况。

## 5 评估

本节中，我们评估 Maglev 的效率和性能。我们提供了 Google 一个生产集群的结果，以及一些微基准测试。

### 5.1 负载均衡

作为网络负载均衡器，Maglev 的主要责任是将流量均匀分布到多个服务端点。为了说明 Maglev 的负载均衡性能，我们从欧洲一个集群的 458 个端点收集了每秒连接数（cps）的数据。数据是从多个 HTTP 服务（包括 Web 搜索）汇总而来的。数据采集的粒度为 5 分钟，负载按照一天内的平均 cps 进行归一化。图 [7](#bookmark39) 显示了典型一天内所有端点的负载平均值和标准差。流量负载呈现明显的日变化模式。标准差始终相对于平均负载很小，变异系数大部分时间在 6% 至 7% 之间。

图 [7](#bookmark39) 还显示了在每个时间点上最大负载相对于平均负载的过度供应因子。这是一个重要的指标，因为我们必须确保即使是最繁忙的端点也始终具有足够的容量来服务所有的流量。过度供应因子在 60% 的时间内小于 1.2。在非高峰时段，过度供应因子明显更高，这是预期的行为，因为在流量较少时负载均衡更加困难。此外，在非高峰时段增加过度供应因子不需要添加 Maglev 机器。这为在特定位置进行过度供应提供了指导。


图 8：使用和不使用内核旁路的吞吐量。

### 5.2 单机吞吐量

由于每个 Maglev 机器通过 ECMP 接收大致相等的流量，Maglev 的整体吞吐量可以估算为 Maglev 机器的数量乘以每台单机的吞吐量。每台机器能处理的流量越大，就需要更少的机器来提供相同的前端容量。因此，单机吞吐量对于系统的效率至关重要。

Maglev 机器的吞吐量受多种因素影响，包括数据包线程的数量、NIC 速度和流量类型。在本小节中，我们报告了在不同条件下评估 Maglev 机器的数据包处理能力的一些小规模测试结果。除非另有说明，所有实验均在配置有两个 8 核最新服务器级 CPU、一个 10Gbps NIC 和 128GB 内存的服务器上进行。我们只使用一个 CPU 来运行 Maglev。其他所有内容，包括操作系统，都运行在另一个 CPU 上。测试平台由两个发送器、两个接收器和一台位于相同以太网域中的 Maglev 机器组成。发送器逐渐增加其发送速率，记录 Maglev 的吞吐量作为在开始丢包之前 Maglev 可以处理的最大每秒数据包数（pps）[2](#bookmark40)。我们使用两个发送器以确保 Maglev 最终超负荷。

#### 5.2.1 内核旁路

在这个实验中，我们同时运行 Maglev 在纯粹的 Linux 网络堆栈模式下以及内核旁路模式下，以评估内核旁路对 Maglev 吞吐量的影响。发送器被配置为从不同的源端口发送最小大小的 UDP 数据包，以便它们不会被定向模块分配到同一个数据包线程。由于测试环境的限制，发送器能够发送的最小大小的 UDP 数据包为 52 字节，稍大于以太网的理论最小值。我们变化每次实验中的数据包线程数。每个数据包线程被固定在一个专用的 CPU 核心上（与我们在生产中的做法相同），以确保最佳性能。我们使用一个核心进行定向和复用，因此最多可以有 7 个数据包线程。我们测量了具有和不具有内核旁路的 Maglev 的吞吐量，并在图 [8](#bookmark41) 中呈现了结果。

> 2 需要注意的是，我们报告的是每秒数据包数（pps），而不是比特率（bps），因为数据包大小对于每秒数据包数的吞吐量影响可以忽略不计。因此，我们使用最小大小数据包来测量每秒数据包数的吞吐量。比特率的吞吐量等于*min*（*pps*× *packet*-*size*，*line*-*rate*-*bps*）。


图 9：使用不同的 TCP 数据包类型的吞吐量。

从图中可以清楚地看出，在内核旁路模式下运行 Maglev 具有明显的优势。当数据包线程不超过 4 个时，Maglev 是瓶颈，其吞吐量随着数据包线程数的增加而增加。然而，当有 5 个或更多的数据包线程时，网络接口卡成为瓶颈。另一方面，在使用纯粹的 Linux 网络堆栈时，Maglev 始终是瓶颈，最大吞吐量不到内核旁路的 30%。

#### 5.2.2 流量类型

根据数据包线程内的代码执行路径的不同，Maglev 在处理不同类型的流量时的速度也不同。例如，数据包线程需要为 TCP SYN 数据包选择后端并将其记录在连接跟踪表中；对于非 SYN 数据包，它只需要在连接跟踪表中进行查找。在这个实验中，我们测量 Maglev 处理不同类型 TCP 数据包的速度。

我们考虑了三种流量类型：SYN、非 SYN 和常量 5 元组。对于 SYN 和非 SYN 实验，只发送 SYN 和非 SYN TCP 数据包，分别进行测试。

SYN 实验显示了 Maglev 在 SYN 洪水攻击中的行为，而非 SYN 实验显示了 Maglev 在常规 TCP 流量下的工作方式，它在进行一次后端选择后，之后使用连接跟踪。对于常量 5 元组实验，所有数据包包含相同的 L3 和 L4 首部。这是一个特殊情况，因为定向模块通常尝试将具有相同 5 元组的数据包发送到相同的数据包线程，并且只有在选择的线程已满时才会将其发送到其他线程。发送器根据需要为 SYN 和非 SYN 实验生成不同的源端口，以生成不同的 5 元组，但常量 5 元组实验始终使用相同的源端口。发送器始终发送最小大小的 TCP 数据包，即在我们的测试环境中为 64 字节。


图 10：使用不同的 NIC 速度的吞吐量。

与前面的实验一样，当存在 5 个数据包线程时，Maglev 在非 SYN 和常量 5 元组实验中达到了 NIC 的容量上限。然而，对于 SYN 数据包，我们发现 Maglev 需要 6 个数据包线程才能饱和 NIC。这是因为 Maglev 需要为每个 SYN 数据包执行后端选择。在常量 5 元组流量下，Maglev 的表现最佳，表明定向模块能够有效地定向分布不均的数据包模式。由于所有数据包具有相同的 5 元组，它们的连接跟踪信息始终保持在 CPU 缓存中，确保了最高的吞吐量。对于非 SYN 数据包，连接跟踪查找存在零星的缓存未命中，因此在数据包线程少于 5 个时，吞吐量略低于常量 5 元组流量。

#### 5.2.3 NIC 速度

在之前的实验中，网络接口卡是瓶颈，因为 5 个数据包线程使其饱和。为了了解 Maglev 的完整能力，这个实验评估了使用更快的网络接口卡时的吞吐量。我们在 Maglev 机器上安装了一块 40Gbps 的网络接口卡，使用与 [5.2.1节](#bookmark42) 中相同的设置进行评估。结果如图 [10](#bookmark43) 所示。当数据包线程不超过 5 个时，40Gbps 的网络接口卡提供了稍高的吞吐量，因为其芯片比 10Gbps 的芯片更快。然而，直到使用了 7 个数据包线程，吞吐量的增长才变缓。


图 11：不同哈希方法的负载均衡效率。M、K 和 R 分别表示 Maglev、Karger 和 Rendezvous。对于*small*，查找表大小为 65537，对于*large*，查找表大小为 655373。

由于网络接口卡不再是瓶颈，这个图显示了 Maglev 在当前硬件条件下的吞吐量的上限，略高于 15Mpps。实际上，瓶颈在于 Maglev 的定向模块，当我们在未来切换到 40Gbps 的网络接口卡时，这将是我们优化的重点。

### 5.3 一致性哈希

在这个实验中，我们评估了 Maglev 的哈希方法，并将其与 Karger [[28](#bookmark30)] 和 Rendezvous [[38](#bookmark31)] 哈希进行比较。我们关注两个指标：负载均衡效率和对后端更改的韧性。

为了评估方法的负载均衡效率，我们使用每种方法填充一个查找表，并计算分配给每个后端的表项数。我们将总后端数设为 1000，查找表大小设为 65537 和 655373[3](#bookmark45)。对于 Karger，我们将视图数设置为 1000。图 [11](#bookmark44) 展示了每种方法和表大小的最大和最小后端占比。

正如预期的那样，Maglev 哈希在不管表大小如何时都提供几乎完美的负载均衡。当表大小为 65537 时，Karger 和 Rendezvous 需要对后端进行超过 29.7% 和 49.5% 的过度供应，以适应不均衡的流量。随着表大小增加到 655373，这些数字分别下降到 10.3% 和 12.3%。由于每个 VIP 都有一个查找表，表的大小必须受限，以便扩展 VIP 的数量。因此，Karger 和 Rendezvous 不适合 Maglev 的负载均衡需求。

另一个一致性哈希的重要指标是对后端更改的韧性。Karger 和 Rendezvous 都保证当一些后端失败时，剩余后端的表项不会受到影响。因此，我们只评估 Maglev 的这个指标。图 [12](#bookmark46) 以并发后端故障百分比的函数，展示了表项更改的百分比。我们将后端数设为 1000。对于每个故障数*k*，我们随机从池中移除*k*个后端，重新生成查找表，并计算更改的表项百分比。我们对每个*k*值重复实验 200 次，并报告平均结果。


图 12：Maglev 哈希对后端更改的韧性。

图 [12](#bookmark46) 显示，随着并发故障数的增加，更改的表项比例也增加。当表大小较大时，Maglev 哈希对后端更改的韧性更强。在实践中，我们将默认表大小设置为 65537，因为我们预计并发后端故障的情况很少，并且我们仍然有连接跟踪作为主要的保护手段。此外，微基准测试显示，查找表生成时间从表大小增加到 655373 时，从 1.8 毫秒增加到 22.9 毫秒，这阻止我们无限增加表大小。

## 6 相关工作

与传统的硬件负载均衡器 [[1]，[2]，[3]，[5]，[9]，[12]，[13]] 不同，Maglev 是一个运行在通用服务器上的分布式软件系统。硬件负载均衡器通常以主备方式部署。Maglev 通过将所有服务器都运行在主动模式下，提供更高的效率和可靠性。此外，升级硬件负载均衡器的容量需要购买新硬件并进行物理部署，使得按需调整容量变得困难。另一方面，Maglev 的容量可以轻松地上下调整，而不会造成任何服务中断。一些硬件供应商还提供在虚拟化环境中运行的负载均衡软件。Maglev 比这些虚拟负载均衡器提供更高的吞吐量。

Ananta [[34](#bookmark29)] 是一个分布式软件负载均衡器。与 Maglev 类似，它采用 ECMP 来扩展系统，并使用低位表实现连接关联。然而，它没有提供处理负载均衡器池变化的具体机制，并且对单机性能没有进行特别优化。Maglev 没有类似于 Ananta 的 HostAgent 组件，提供 NAT 服务，但有一个外部系统（未在此处描述）提供类似的功能。Ananta 允许大部分内部 VIP 流量绕过负载均衡器。Maglev 没有提供类似的功能，因为它对内部流量有足够的容量。Embrane [[4](#bookmark47)] 是一个为虚拟环境开发的类似系统。然而，由于虚拟化的限制，它的吞吐量优化可能会困难。Duet [[22](#bookmark12)] 是一个混合硬件和软件负载均衡器，旨在解决纯软件负载均衡器的低吞吐量问题。Maglev 能够实现足够高的吞吐量，因此混合解决方案变得不必要。

还有许多通用的负载均衡软件包，其中最流行的是 NGINX [[14](#bookmark48)]，HAProxy [[7](#bookmark49)] 和 Linux Virtual Server [[11](#bookmark50)]。它们通常在单个服务器上运行，但也可以在一个 ECMP 组后面的路由器后部署多个服务器以实现扩展模型。它们都提供了一致性哈希机制。与 Maglev 相比，它们更注重最小化中断，而不是像 [[28](#bookmark30)] 和 [[38](#bookmark31)] 那样实现负载均衡。由于它们设计为可移植，它们在性能方面并没有进行积极优化。

一致性哈希 [[28](#bookmark30)] 和 Rendezvous 哈希 [[38](#bookmark31)] 最初是为了分布式缓存协调而引入的。这两种方法都提供了可靠性保证，即当一些后端被移除时，只有指向这些后端的表项会被更新。然而，它们无法对后端进行良好的负载均衡，而负载均衡对于负载均衡器来说是一个基本要求。相反，Maglev 的一致性哈希方法在略微降低可靠性的情况下实现了对后端的完美平衡，在与连接跟踪配合使用时效果良好。实现一致性哈希的另一种选择是使用分布式哈希表，例如 Chord [[37](#bookmark51)]，但这将增加系统的额外延迟和复杂性。

自 1990 年以来，许多用于性能优化的技术已经得到广泛研究。Smith 等人 [[36](#bookmark52)] 建议通过减少中断和内存拷贝来提高应用程序的吞吐量。Mogul 等人 [[33](#bookmark53)] 开发了一种基于轮询的机制，以避免中断引起的接收死锁。Edwardset al[[19](#bookmark54)] 探索了用户空间网络的想法，但没有完全绕过内核。Marinos 等人 [[31](#bookmark18)] 展示了具有内核绕过的专用用户空间网络堆栈可以显著提高应用程序的吞吐量。Hanford 等人 [[25](#bookmark55)] 建议将分散的数据包处理任务分布到多个 CPU 核心中，以提高 CPU 缓存命中率。CuckooSwitch [[41](#bookmark16)] 是一个高性能的软件 L2 交换机。它的关键技术之一是通过批处理和预取来屏蔽内存访问延迟。RouteBricks [[18](#bookmark15)] 解释了如何有效利用多核 CPU 进行并行数据包处理。

近年来，出现了几种内核绕过技术，包括 DPDK [[8](#bookmark56)]，OpenOnload [[15](#bookmark57)]，netmap [[35](#bookmark17)] 和 PF-RING [[17](#bookmark58)] 等等。[[10](#bookmark59)] 中提供了流行的内核绕过技术的良好总结。这些技术可以有效加速数据包处理速度，但它们都有一定的限制。例如，DPDK 和 OpenOnload 与特定的 NIC 供应商绑定，而 netmap 和 PF-RING 都需要修改过的 Linux 内核。在 Maglev 中，我们实现了一个灵活的 I/O 层，不需要修改内核，并允许我们方便地在不同的 NIC 之间切换。与其他技术一样，Maglev 一旦启动就接管了 NIC。它使用 TAP 接口将内核数据包注入到内核中。

最近，GPU 在高速数据包处理中开始变得流行起来 [[24](#bookmark60)，[39](#bookmark61)]。然而，Kalia 等人 [[27](#bookmark62)] 最近的研究表明，如果正确实现，基于 CPU 的解决方案能够以更高效的资源利用实现类似的性能。

## 7 结论

本文介绍了 Maglev，一种快速、可靠、可扩展和灵活的软件网络负载均衡器。我们通过 ECMP 实现了 Maglev 的扩展性，并在每台机器上可靠地以 10Gbps 的线速率提供服务，以满足快速增长的服务需求的成本效益性能。我们通过连接跟踪和 Maglev 哈希的组合，将连接一致地映射到相同的后端。多年来，在规模上运行这个软件系统使我们能够有效地运营我们的网站，迅速应对需求增长和新功能需求。

## 致谢

我们衷心感谢 Adam Lazur、Alex Tumko、Amin Vahdat、Angus Lees、Aspi Siganporia、Ben Treynor、Bill Coughran、Brad Calder、Craig Bergstrom、Doug Orr、Dzevad Trumic、Elliott Karpilovsky、Jeff Mogul、John T. Reese、Kyle Moffett、Luca Bigliardi、Mahesh Kallahalla、Mario Fanelli、Mike Dalton、Mike Shields、Natalya Etina、Nori Heikkinen、Pierre Imai、Roberto Peon、Simon Newton、Tina Wong、Trisha Weir、Urs H¨olzle 等人对本文和 Maglev 的成功做出的重要贡献表示感谢。我们还要感谢我们的 shepherd Nathan Bronson 和匿名审稿人对本文的有益反馈。

## 参考

[1] A10. <http://www.a10networks.com>.

[2] Array networks. <http://www.arraynetworks.com>.

[3] Barracuda. <http://www.barracuda.com>.

[4] Embrane. <http://www.embrane.com>.

[5] F5. <http://www.f5.com>.

[6] Google cloud platform. <http://cloud.google.com>.

[7] Haproxy. <http://www.haproxy.org>.

[8] Intel dpdk. <http://www.dpdk.org>.

[9] Kemp. <http://www.kemptechnologies.com>.

[10] Kernel bypass. <http://blog.cloudlare.com/kernel-bypass>.

[11] Linux virtual server. <http://www.linuxvirtualserver.org>.

[12] Load balancer .org. <http://www.loadbalancer.org>.

[13] Netscaler. <http://www.citrix.com>.

[14] Nginx. <http://www.nginx.org>.

[15] Openonload. <http://www.openonload.org>.

[16] F. Chen, R. K. Sitaraman, and M. Torres. End-user mapping: Next generation request routing for content delivery. In *Proceedings of SIGCOMM*, 2015.

[17] L. Deri. Improving passive packet capture: Beyond device polling. In *Proceedings of SANE*, 2004.

[18] M. Dobrescu, N. Egi, K. Argyraki, B.-G. Chun, K. Fall, G. Iannaccone, A. Knies, M. Manesh, and S. Ratnasamy. Routebricks: Exploiting parallelism to scale software routers. In *Proceedings of SOSP*, 2009.

[19] A. Edwards and S. Muir. Experiences implementing a high performance tcp in user-space. In *Proceedings of SIGCOMM*, 1995.

[20] R. A. Fisher and F. Yates. *Statistical tables for biological, agricultural and medical research*. Edinburgh: Oliver and Boyd, 1963.

[21] R. Fonseca, G. Porter, R. H. Katz, S. Shenker, and I. Stoica. Xtrace: A pervasive network tracing framework. In *Proceedings of NSDI*, 2007.

[22] R. Gandhi, H. H. Liu, Y. C. Hu, G. Lu, J. Padhye, L. Yuan, and M. Zhang. Duet: Cloud scale load balancing with hardware and software. In *Proceedings of SIGCOMM*, 2014.

[23] P. Gill, N. Jain, and N. Nagappan. Understanding network failures in data centers: Measurement, analysis, and implications. In *Proceedings of SIGCOMM*, 2011.

[24] S. Han, K. Jang, K. Park, and S. Moon. Packetshader: A gpuaccelerated software router. In *Proceedings of SIGCOMM*, 2010.

[25] N. Hanford, V. Ahuja, M. Balman, M. K. Farrens, D. Ghosal, E. Pouyoul, and B. Tierney. Characterizing the impact of endsystem afinities on the end-to-end performance of high-speed lows. In *Proceedings of NDM*, 2013.

[26] V. Jacobson and B. Felderman. Speeding up networking.

<http://www.lemis.com/grog/Documentation/vj/lca06vj>.pdf.

[27] A. Kalia, D. Zhou, M. Kaminsky, and D. G. Andersen. Raising the bar for using gpus in software packet processing. In *Proceedings of NSDI*, 2015.

[28] D. Karger, E. Lehman, T. Leighton, R. Panigrahy, M. Levine, and D. Lewin. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web. In *Proceedings of ACM Symposium on Theory of Computing*, 1997.

[29] C. Labovitz. Google sets new internet record.

<http://www.deepield.com/2013/07/google-sets-new-internet>record/.

[30] C. Labovitz, S. Iekel-Johnson, D. McPherson, J. Oberheide, and F. Jahanian. Internet inter-domain trafic. In *Proceedings of SIGCOMM*, 2010.

[31] I. Marinos, R. N. Watson, and M. Handley. Network stack specialization for performance. In *Proceedings of SIGCOMM*, 2014.

[32] J. C. McCullough, J. Dunagan, A. Wolman, and A. C. Snoeren. Stout: An adaptive interface to scalable cloud storage. In *Proceedings of USENIX ATC*, 2010.

[33] J. C. Mogul and K. K. Ramakrishnan. Eliminating receive livelock in an interrupt-driven kernel. In *Proceedings of USENIX ATC*, 1996.

[34] P. Patel, D. Bansal, L. Yuan, A. Murthy, A. Greenberg, D. A. Maltz, R. Kern, H. Kumar, M. Zikos, H. Wu, C. Kim, and N. Karri. Ananta: Cloud scale load balancing. In *Proceedings of SIGCOMM*, 2013.

[35] L. Rizzo. netmap: A novel framework for fast packet i/o. In *Proceedings of USENIX Security*, 2012.

[36] J. Smith and C. Traw. Giving applications access to gb/s networking. *Network, IEEE*, 7(4):44–52, 1993.

[37] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In *Proceedings of SIGCOMM*, 2001.

[38] D. G. Thaler and C. V. Ravishankar. Using name-based mappings to increase hit rates. *IEEE/ACM Transactions on Networking*, 6(1):1–14, 1998.

[39] M. Varvello, R. Laufer, F. Zhang, and T. Lakshman. Multi-layer packet classiication with graphics processing units. In *Proceedings of CoNEXT*, 2014.

[40] K. V. Vishwanath and N. Nagappan. Characterizing cloud com-

puting hardware reliability. In *Proceedings of SoCC*, 2010.

[41] D. Zhou, B. Fan, H. Lim, M. Kaminsky, and D. G. Andersen. Scalable, high performance ethernet forwarding with cuckooswitch. In *Proceedings of CoNEXT*, 2013.