摘要
maglev是谷歌的一个网络负载均衡器。它是一个运行在linux服务器上的大型的分布式的软件。不同于传统的硬件负载均衡设备，它不需要特殊的物理设备，并且可以很方便的通过增加或者减少服务来进行扩缩容。核心路由通过ECMP协议来将网络包均匀的发送给maglev节点。maglev再将这些网络包均匀的分发给后端实际服务节点。为了容纳不断增长的流量,maglev针对包处理做了特别的优化。一个maglev节点可以处理10Gbps的小包。为了最小化面向连接协议在发生预期外错误和失败时产生的负面影响，maglev支持了一致性hash以及连接跟踪(connection tracking)的特性。2008年起 maglev承载了谷歌的大部分流量，同时也为谷歌云提供服务。
介绍
谷歌承载了非常大的全球化的流量，提供了数以百计的面向用户的产品。同时，越来越多的服务迁移到了谷歌云上。一些谷歌的重要服务如谷歌搜索，谷歌邮箱每秒要处理上百万次请求,这对基础设施提出了巨大的需求。
为了能够低延迟的处理海量请求，一个谷歌服务部署在世界各地不同区域的服务器上。在每个区域内，需要将流量均匀的分发给所有服务器以高效的利用资源并且保证不超过单个服务器的负载上限。所以，网络负载均衡是谷歌非常重要的一个基础设施。
如图一所示，一个负载均衡器是由多个逻辑上部署在核心路由与服务节点(通常是tcp或者udp服务器)间的设备组成的。
传统意义上，负载均衡器被理解成一种专用的硬件设备,这种设备有很多的局限性。
首先，这种设备的扩展性受限于单个设备的最大承受上限，无法承载谷歌日益增长的流量。其次，这种设备无法满足谷歌对高可用性的要求，它们通常是成对部署来避免单点故障，这只能提供 1+1的冗余。第三，很难做到甚至无法做到修改一个专用的硬件设备，这就无法在日新月异的今天提供灵活性和可编码性。第四，在升级时非常的贵,想要提升硬件设备的性能通常只能购买新款并重新部署。基于以上的局限性，我们决定寻求替代方案。
我们可以通过一个分布式的软件系统来构建一个负载均衡器。软件负载均衡器(以下简称为slb)相对于硬件拥有很多优点。首先，我们能够非常方便的进行扩缩容:我们简单的添加maglev节点后，核心路由通过ECMP协议将流量均匀的转发给所有maglev节点。同时，可用性和可靠性也被提升了 因为slb拥有N+1的冗余。这个系统对我们都是可控的，我们可以更方便的添加，测试以及发布新的特性。同时，发布新版的slb是非常简单的。因为slb只使用同区域的机器,我们可以将服务分给多个同区域的slb来实现隔离。
设计和实现一个slb是有很高复杂度和挑战性的。首先，每台机器都必须能够提供高吞吐量。设N为机器数，T为每台机器的最大吞吐量。则这个slb的容量为N * T 。 如果T不够高，那就需要更多的机器，slb就不具有性价比了.其次 slb必须提供连接持久化的能力，同一个连接的数据包必须分发给同一台后端机器。这样才能确保服务质量，因为服务是动态的，而且故障是非常常见的。
这篇文章介绍了maglev，一个快速可信赖的slb系统。08年以来，maglev已经成为了谷歌前台服务的重要组件，并且为谷歌几乎所有流量提供服务。使用最新的高速网络技术，maglev节点可以达到线性的吞吐量。通过一致性hash以及连接跟踪技术，maglev能够在服务发生快速变化或者产生异常错误时提供可信赖的服务。本文中有些技术已经诞生很多年了，下文将会展示如何使用这些技术来构建一个slb。
本文的主要内容为
- 展示maglev的设计与实现
- 分享maglev在全球范围使用的经验
- 展示maglev的性能
2.系统概述
本节主要阐述了maglev是如何工作的。在介绍maglev是如何工作之前我们将会介绍谷歌前台业务的架构。
2.1 前台服务架构
图二展示了一个小集群下谷歌服务的架构。
每一个谷歌服务拥有一个或者多个虚拟ip(以下简称vip). vip不同于物理ip，并不分配给一个特定的网卡，而是由maglev之后的多个服务节点来提供服务。maglev将vip与一批服务节点关联，并且通过BGP协议通知给核心路由。路由将这个ip发布到谷歌骨干网，最终，所有的vip都会全球可用。maglev同时支持ipv4和ipv6的流量，以下讨论的内容对这两者都是一致的。
当一个用户尝试去请求一个谷歌服务www.google.com.浏览器首先发送了一次DNS请求，谷歌DNS服务器会挑选离用户最近的区域，并且返回一个该区域的vip。浏览器则会尝试与vip建立一个新连接。
当核心路由收到VIP的包时，通过ECMP协议分发给本区域内的maglev节点（因为所有maglev的链路cost都是一致的）。 当maglev接受到一个包，它会从VIP对应的服务节点列表中选择一个节点,将目标ip改为节点ip后使用GRE协议
封装数据包。
当包到达实际节点时，需要解包。当响应就绪时，会将ip来源设置为vip，而目标ip为用户ip。我们使用DSR来绕过maglev节点来发送相应给核心路由以免maglev需要处理通常更大的返回包。DSR的实现则超出了本文的范围。
在大型集群中则更加复杂，我们需要避免将maglev节点和核心路由部署在同一个2层网内，所以需要一个封装器部署在核心路由之后来将核心路由的包通过隧道发送给maglev节点。
2.2 Maglev 配置
如前文所述，maglev接受来自核心路由的已声明的vip包然后转发给服务节点。如图三所示，每个maglev节点包含一个controller和一个forwarder,controller和forwarder从图中的configuration objects获取vip。configuration objects可以从文件中读取也可以接受外部系统的rpc请求。
maglev节点上，controller会定时检查forwarder的健康状态。根据检查结果，controller决定是否通过BGP协议向核心路由注册VIP，这就保证核心路由仅会向健康的maglev节点转发数据(controller挂了怎么办？)
maglev节点接受到的所有vip的数据都会由forwarder来处理。每个vip都会包含一个或者多个bp(backend pool) 。除非特别说明，否则maglev的backend是服务节点。
一个bp可能包含服务节点的真实ip，也有可能包含其他的bp，这样就能够重利用已声明的bp而不用重复声明。每个bp，根据实际需要，都会拥有一个或者更多的健康检查方法来保证数据包只会转发给健康的服务节点。由于一个服务节点可能存在于多个bp中，健康检查需要根据ip去重来避免重复检查。
forwarder有一个config manager，负责解析和检查config object。所有配置更新都具有原子性。在推送配置或者健康检查时，maglev节点间可能会出现不同步，然而，一致性hash能够保证连接在短窗口期内也能大多数成功(疑)。
我们可以在一个区域内发布多组maglev。不同组的maglev使用不同的配置，服务不同的vip。这种方式可以提供一种隔离性，并且保证服务的质量。也是一种非常适合尝试新特性的方式，它不会干扰正常的流量。下文中，每个区域仅包含一组maglev。
3. Forwarder的设计与实现
forwarder是maglev的一个重要组件，它需要快速可信赖的处理非常大的数据包。本节阐述了设计理念和forwarder一些核心模块的实现以及设计理念背后的原理。
3.1 整体架构
图四展示了forwarder的整体架构。forwarder从NIC中接受数据，将数据包的GRE/IP重写为合适的值后发回NIC，而不需要经过linux内核态。
从NIC获取的数据包首先由steering module处理，计算五元组的hash值来将数据包投放到不同的receiving queues中，每个receiving queues有一个数据包重写线程处理。处理线程首先尝试为数据包匹配一个vip，会将没有匹配到vip的数据包抛弃。
然后计算五元组hash，根据hash从connection tracking table（以下简称连接表）中获取服务节点。为了避免线程间同步，我们不使用steering module中计算的hash值
连接表保存了连接所对应的服务节点、如果连接表中存在该hash的数据，并且服务节点还是健康的，仍将数据转发给该服务节点。否则将调用一致性hash模块选取为该数据包选择一个新的服务节点，并将该结果写连接表。如果没有可用的服务节点，数据包将被抛弃。每个处理线程都有一张连接表来避免多线程读写。当服务节点选择完成后。处理线程将为数据包添加GRE/IP头，然后发送到对应的transmission queues 。muxing module来从transmission queues中获取数据发送到NIC。
steering module使用五元组hash来替代轮询有两个原因。第一，避免由于不同线程处理速度差异导致的同一连接的数据包顺序错乱。第二, forwarder只需要为每个连接计算一次hash，节省时间并且消除由于服务节点更新的竞态条件导致的选取不同服务节点。在少数情况下，如果选中的receiving queues已经满了，会使用轮询算法来作为补充，这种fallback机制可以很好的解决针对同一五元组的syn flood攻击。
3.2 高速处理数据包
maglev forwarder需要尽可能快的处理数据包来节约所需要的节点数。forwarder能够达到线性速率，精确的说10Gbps(8c机器)。可以每秒处理813k的1500byte大小的ip包。然而，我们的要求更加严格，我们必须能够处理非常小的数据包。假定每个数据包平均大小为100byte，forwarder必须能够每秒处理9.06百万个数据包。本节将会描述一些核心技术来达到这个目标。
maglev是一个运行在商用linux服务器上的用户态应用。因为linux内核网络栈处理代价非常高昂，maglev不使用任何linux网络栈的功能。这就需要maglev能够绕过内核来处理数据。如图五所示，在NIC硬件的支持下，我们开发了一套方法在NIC和forwarder中传输数据而不需要任何内核介入。当maglev启动后，提前申请了一块packet pool在NIC和forwarder中共享。steering模块和muxing模块都有一个环形队列，队列中是packet pool的指针。
steering和muxing模块都持有了环形队列的三个指针。在接受侧，NIC将新的数据包放在receivied指针处然后将指针向前推。steering模块分发数据包给处理线程然后推动processed指针。因为steeing模块和muxing模块共用一个packet pool 所以还需要一个reserved指针，当packet pool有可用unused块时，加入环形队列并推动reserved指针。在发送端，当NIC发送了一个包时，会推动send指针。当处理线程将数据包重写完成时 会推动ready指针。当NIC发送完成后会推动recycled指针释放packet。注意，在所有环节都没有packet 拷贝操作。
为了减少昂贵的越界操作，我们尽可能的成批的处理数据包。此外，处理线程所有数据都是独享的，来避免线程安全问题以及锁损耗。我们会将每个线程与cpu进行绑定，来避免上下文切换来带的损耗以获得最佳的性能。基于这些优化，maglev可以做到小包下的线性速率，如图5.2所示(并没有这张图)。
进一步，maglev处理每个数据包的延迟是非常短的，一个标准服务器上通常只需要350ns。有两种特殊情况下可能会需要更长时间。第一，因为forwarder是以批处理的方式转发数据包，每一批数据包会在达到批大小或者超时时被处理，在实践中我们采取了一个50us的定时器。因此，如果maglev处于低负载时，最坏情况下数据包会有50us的延迟。动态调整批大小是一个可行的改进策略。第二，当maglev处于过载情况下，每个数据包可能会有额外的延迟，maglev能够缓存的数据包最大数量就是packet pool的大小。超出的部分数据包将会被NIC所抛弃。假定packet pool的大小为3000，forwarder每秒能处理一千万个包，那处理所有缓存包将需要300us。包将获得一个最大300us的延迟。幸运的，这种情况可以通过合理的容量规划和添加maglev节点来解决。
3.3 服务节点选择
当一个数据包匹配到一个VIP后，我们需要从该VIP的BP中选择一个服务节点。对于面向连接的协议如TCP，我们必须要把同一个连接的数据发送给同一个服务节点。首先我们通过一致性hash算法来选择一个服务节点，这种算法能够非常均匀的分配流量。然后我们将这个连接和服务节点的对应关系记录在本地的连接跟踪表中。
maglev的连接跟踪表采用一个固定大小的hash表，key为五元组的hash值，value为对应的服务节点。如果表中没有对应的hash值，maglev将会选取一个服务节点，并且保存到表中。如果存在就直接复用之前的节点选择。只要服务节点存活，这能够保证同一个连接的包被发送到同一个服务节点。在BP发生变化时，连接追踪就能够排上用场了。
然而，在分布式情况下，独立的maglev节点连接追踪是不够的。首先，这需要所有相同五元组的数据包发送到同一个maglev节点。因为核心路由通常不提供连接亲和的功能，当maglev节点组变化时这个就无法做到了。不幸的是，这种变化是非常常见的。例如，当升级maglev时，我们需要逐个重启maglev节点，这个过程通常需要持续最少一个小时的时间。有时我们也会添加移除替换maglev节点。当新的maglev节点启动时，没有正确的连接追踪表，旧连接就会中断(疑)。
第二个理论上的限制是连接追踪表空间有限，当发生syn flood攻击时，这个表可能会被填满。因为maglev只会在记录超时时移除，一旦表被填满，我们需要选择一个为在表中没有记录的数据包选择服务节点。虽然服务器通常具有较大的内存，但是我们通常会将maglev和其他服务混布，所以我们需要限制追踪表的大小。
一旦以上任何一个情况发生，我们不再能够再支持链接追踪功能。因此，maglev提供了一致性hash算法来保证这种情况下也可以可信赖的分发数据。
3.4 一致性hash
一种可能的解决方式是在所有maglev机器间共享追踪表，例如一张分布式的hash table。然而，这会影响转发的性能表现，要知道maglev节点上的处理线程都不共享数据。
一个更佳的解决方式是使用本地一致性hash算法。一致性hash的概念第一次出现于二十世纪九十年代。它能够生成一张大的查找表。这种方式提供了两个maglev需要的特性。
- 负载均衡: 每个服务节点会收到几乎一样的连接。
- 最小影响: 当服务节点集变化时，连接绝大多数情况下仍然会被发送到原来的服务节点上。
现有的hash算法都将最小影响的优先级放在了负载均衡之上，因为它们设计出来是为了解决小规模服务下的缓存问题。然而,maglev更重视负载均衡。首先，将所有流量尽可能均匀的打到服务节点上对maglev是非常重要的，否则服务节点就需要更高的性能来处理高峰期的流量。对于一个VIP，maglev可能有数百个服务节点。我们的经验显示，这种情况下现有的hash算法需要一个巨大的hash表来达到我们需要的负载均衡程度。其次，虽然最小影响是非常重要的，但是小概率的影响对于maglev是可容忍的。大部分情况下，hash表的改变不会导致连接重置，因为连接追踪表中原有数据。而当两者同时发生时，连接重置的数量与表中影响记录数成正比。
基于以上考虑，我们实现了一套新的一致性hash，称作maglev hashing。首先，为每个服务节点生成一个偏好数组，接下来每个节点轮流填充他们的偏好位置，知道表被填满。这样，maglev hashing为每个服务节点提供了几乎一样的机会。节点权重的区别可以通过填充频率来实现。这个实现细节本文不描述。
设M为表的大小，每个服务节点的偏好列表被保存在permutation[i]中，偏好列表是一个随机的序列，取值为[0,m-1]。为了生成这个序列，我们首先为每个服务节点起一个unique的名字。然后用两种不同的hash算法计算名字的hash值，分别作为offset和skip。最后用这两个值来生成序列，如下
offset ← h1(name[i]) mod M
skip ← h2(name[i]) mod (M −1) +1
permutation[i][ j] ← (offset+ j ×skip) mod M
M必须是一个素数以保证skip的值是和M互质的。设N为一个VIP的BP的节点数。
我们使用伪码1来生成表
# 伪码1
01: function POPULATE
02: for each i < N do next[i] ← 0 end for
03: for each j < M do entry[ j] ← −1 end for
04: n ← 0
05: while true do
06: for each i < N do
07: c ← permutation[i][next[i]]
08: while entry[c] ≥ 0 do
09: 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
我们用next[i]来记录i节点的偏好序列下一个值，最后表被存在entry数组中。然后我们依个用偏好序列填充entry数组直到填充满为止
这个算法必然会结束。最差情况下性能为O(m²)，这仅当所有服务节点的偏好序列全部一致时发生。为了避免这种情况，我们通常选取M值需要保证M>>N。这种情况下性能为O(MlogM) 。第n步时我们需要消耗 M/(M-n)次来找到一个空的位置。所以总的尝试次数为M/n 从n=1到M的和。每个服务节点占据表中M/N个条目。因此 不同服务节点占据的条目数最多相差1。实践中，我们选取的M要大于100*N来保证不超过1%的服务节点间的差异。Fisher-Yates Shuffle这种序列生成算法可以生成更好的随机序列。
我们使用表1来展示maglev是如何工作的。假设存在三个服务节点，表的大小为7，offset和skip的值分别为(3,4),(0,2)和(3,1)。最终生成的偏好序列如左列所示。
B1节点移除之前，整个表如右列所示。当B1移除后，B1占据的条目将会均分给其他节点。同时只有第六行收到了影响。而实践中，当我们使用更大的表时，影响会更小，会在5.3节做详细论述。
