对于拓扑变化有弹性的分布式按次序负载分布

摘要

用于以对系统拓扑变化有弹性的方式分配网络负载的方法、装置和系统。在多个负载拆分器上实施分配函数及相关联操作，以使得如果负载拆分器成为无效的，则另一个或其他负载拆分器可以转发对应于以前由无效的负载拆分器处理的流的分组，而无需要求在负载拆分器之间保持流状态同步。通过系统拓扑变化，以将用于相同流的分组分配给相同服务器的方式实施分配函数，解决了当服务器故障和/或离线时，及当这种服务器或替换服务器恢复在线时的情形。经由使用被标记以追踪重分配流的重分配流列表和/或布隆过滤器而部分地促进该技术。还公开了一种新颖的布隆过滤器再循环方案。

说明书

背景技术

自从引入微处理器以来，计算机系统已经变得越来越块。大致按照摩 尔定律(基于预测集成电路上的晶体管数量每两年加倍的公司共同创 始人Gordon Moore的1965年出版物)，在几乎三十年中，速度增大以相当 均匀的速率急速上升。同时，存储器和非易失性储存设备的尺寸也稳定地 增大，使得许多当前个人计算机比仅仅10-15年之前的超级计算机更强大。 另外，类似地见证了网络通信速度的极大增加。

处理器速度、存储器、储存设备和网络带宽技术中的增大导致了具有 不断增大的容量的网络的扩建和部署。最近，诸如由亚马逊(例如，亚马 逊弹性计算云(EC2)和简单储存服务(S3))和微软(例如，Azure和Office 365)所提供的基于云的服务的引入，导致了用于公用网络基础结构的额外 的网络扩建以及大容量数据中心的增加，用以支持使用专用网络基础结构 的这些服务。另外，在不久的进来，预期新一代(例如4G)移动网络数据 服务会相当大地影响陆线网络的使用。这些及其他考虑的结果是预期计算 机网络的使用在可预见的未来以高速继续增长。

诸如电子商务网站、社交网站、内容托管网站和新闻网站之类的用于 云服务及其他在线网站的公共架构使用多层架构，所述多层架构具有耦合 到服务器(诸如应用服务器和数据库或储存服务器)的一层或多层的网络 服务器前端。网络服务器层自身可以使用负载分配方案，其以扇出模型方 式使用多个级。负载分布还通常部署在网络服务器与应用服务器层之间。

在技术上，网络服务器应被更准确地称为HTTP(超文本传输协议)服 务器。HTTP采用使用客户机-服务器模型的请求-应答协议。HTTP是无状 态协议，最初实施它以便在单一应答对后关闭连接。在HTTP 1.1中，增加 了保持活动机制，其中，连接可以用于多个请求；这些连接被称为“持久” 连接。另外，HTTP 1.1引入了分块传输编码以支持使用持久连接的数据流。

每一个服务器都具有其自身的网络地址，公共网络服务器具有公共因 特网协议(IP)网络地址，其被按照使用32位寻址方案的IPv4或者按照使 用128位寻址方案的IPv6进行编码。域名系统(DNS)用于将网站URL 映射到其公共IP地址。典型地，对于诸如www.facebook.com和 www.youtube.com的网站的主页，仅有单一公共IP地址。为了处理每天接 收到的上百万的请求，这些网站实施负载分布方案，根据这个方案，使用 扇出的一级或多级在网站的专用网络内部路由每一个请求。

早期的负载分布方案采用负载平衡器等，其使用简单算法以便跨越多 个服务器而平衡输入请求。例如，鉴于原始HTTP请求/应答预期，采用了 循环法方案等，根据这种方案，如果存在1对n负载平衡器，则每个服务 器就会处理每一第n个请求。根据在树状层级结构中将低层应用服务器耦 合到高层服务器的架构，仅可以经由单一路由路径访问给定应用服务器。 因而，对于这些架构中的流连接，沿着相同路径路由对应于主机的专用网 络内的连接的所有分组。

与专用IP网络相反，因特网由大量相互连接的公用网络组成，并且采 用极其大量的交换元件，例如交换机、路由器、桥接器等。根据因特网的 基本概念，可以使用不同路线在相同源与目的地端点之间路由分组，因而 提供了如果一些交换元件成为被禁用情况下的弹性，并实现了对网络拓扑 的动态变化。但对于流连接等，在路线的公用因特网部分和路线的专用网 络部分上，沿着相同路线路由分组是有利的。

通常优选的是，与流相关联的分组按次序到达目的地。为了便于这样， 典型地将路由器和交换机配置成对给定流选择相同的下一跳。类似地，通 常优选地，负载平衡器和负载拆分器被配置成将属于相同流的分组发送到 相同的服务器。

附图说明

通过结合附图参考以下的详细说明，会更易于意识到本发明的前述方 案和许多伴随优点，并且会更好地理解它，在附图中，除非另外指出，否 则在贯穿各个视图中相似的参考标记指代相似的部分：

图1a是示例性系统架构的示意图，所述系统架构采用多个负载拆分器 来将分组分配给多个服务器，而服务器又反过来提供对到由储存层中的设 备存储的数据的访问；

图1b显示了图1a的系统拓扑中的变化，其中一个服务器成为不可用 的；

图1c显示了图1a和1b的系统拓扑中的变化，其中两个服务器成为不 可用的；

图1d显示了系统拓扑通过使得不可用服务器之一恢复开机而从图1c 的配置返回到图1b的配置。

图1e显示了其中由备用服务器代替有故障的服务器的系统拓扑；

图1f显示了图1c的系统拓扑中的变化，其中负载拆分器之一变为不可 用的；

图2显示了图1a的系统架构的变化，其中，耦合到负载拆分器的服务 器经由LAN连接到应用服务器层中的应用服务器；

图3a-3c示出了采用多个哈希算法和一维位向量的布隆过滤器如何操 作；

图4a-4c示出了采用多个哈希算法和各自的位向量的布隆过滤器如何 操作；

图5显示了根据一个实施例的用于一对布隆过滤器的位向量数据的时 间流，用于示出采用当前和下一布隆过滤器的布隆过滤器方案的实现方式；

图6是示出根据一个实施例的有利于根据图1a-1f中所示的实施例的通 用分组分配/再分配方案的操作和逻辑的流程图；及

图7是示出被配置为实施本文公开的实施例的方案的装置的架构的示 意图。

具体实施方式

本文说明了用于以对于拓扑变化有弹性的方式来分配网络负载的系 统、装置、方法的实施例。在以下说明中，阐述了许多具体细节，例如负 载拆分器的示例性实施例，以提供对本发明的实施例的透彻理解。但相关 领域技术人员会认识到，可以无需一个或多个具体细节，或者借助其他方 法、组件、材料等来实践本发明。在其他实例中，没有详细显示或说明公 知的结构、材料或操作以避免使得本发明的方案模糊不清。

在本说明书通篇中对“一个实施例”或“实施例”的提及表示结合实 施例说明的特定特征、结构或特性包括在本发明的至少一个实施例中。因 而，短语“在一个实施例中”或“在实施例中”在本说明书通篇中多个位 置的出现不一定全都指代相同的实施例。而且，可以在一个或多个实施例 中以任何适合的方式组合特定特征、结构或特性。

如上所述，在网络中通常沿相同路径来路由与相同流相关联的分组。 更具体地，也可以称为负载拆分器(本文所使用的)的负载平衡器被配置 为将属于相同流的分组转发到相同的服务器。对于将前端服务器连接到其 他层上的服务器的树状层级而言，应总是将与给定服务和相同流相关联的 分组发送到用于实施该服务的相同服务器。例如，基于云的数据上载或下 载可以沿包括前端网络服务器、被配置为服务数据文件访问请求的应用服 务器和在其上存储数据的储存服务器的路径来路由分组。可选地，可以在 相同服务器上实现网络服务器和应用服务器功能。结合数据文件请求，打 开持久连接，使用运行在应用服务器上的应用程序并结合使用在网络服务 器上实施的HTTP数据分块而从储存服务器流送数据或向储存服务器流送 数据。由于HTTP数据分块实际上涉及多个请求/应答，每一个请求都由相 同的网络服务器和应用服务器来服务。

为了支持使用相同的路由/转发路径，当前使用的有两个基本机制。本 文所述的这些机制适用于负载拆分器，但是可以由其他网络元件(例如交 换机)来使用类似的机制。根据第一机制，负载拆分器为每个当前流保持 状态：(流标识符、选择来转发流的服务器)。这存在两个问题；一个是， 尤其是借助分布式拒绝服务(DDOS)攻击，该状态或许变为耗尽的。另一 个问题是如果服务器选择是任意的(即，在流开始时选择最小负载的服务 器)，如果网络路径改变且将流路由到不同负载拆分器，则第二负载拆分器 就会无法获知由第一负载拆分器所做出的选择(在负载拆分器之间没有极 为昂贵的状态同步)。

第二个机制采用分组中选定字段值的哈希，以做出无状态确定选择。 这允许另一负载拆分器计算相同的选择。但如果服务器组变化，就会不同 地哈希处理所有流，从而不必要移动流(不仅仅是前往现在的废弃选择的 流)。

根据本文所公开实施例的方案，解决了前述两个问题，实现了网络拓 扑改变，同时确保由指定给给定请求的原始应用服务器或者其他服务器服 务于该请求以进行完成。另外，该技术是可缩放的，使得多个负载拆分器 可以实施相同的分配逻辑，如果这些负载拆分器之一发生故障，则另一负 载拆分器可以接管处理由故障的负载拆分器先前处理的流的分配。此外， 这可以以在负载拆分器之间无需昂贵的状态同步的方式来完成。

图1a示出了系统100，包括n个运行服务器S(标记为S1、S2、……、 Sn)和两个备用服务器102-1与102-2，其耦合到三个负载拆分器L(标记 为L1、L2和L3)。每一个服务器S和备用服务器102还耦合到包括多个大 容量储存设备106的储存层104和储存访问服务器或前端等(未示出)，其 提供对存储在大容量储存设备上的数据的访问。负载拆分器L1、L2和L3 从系统外部的客户端经由适用的网络基础结构(为了简单和清楚而没有示 出)接收输入请求108。例如，系统100可以是基于云的储存服务的部分， 用户使用URL门户经由因特网进行访问。在由图2中的系统200所示的另 一配置中，服务器S包括网络服务器，其经由局域网(LAN)103耦合到应 用服务器层105，应用服务器层105包括多个应用服务器107。另外，如果 在应用服务器层或者其他中间层中实现服务器S，则可以从诸如前端网络服 务器层(未示出)的系统100中的另一层接收输入请求108，或者否则就在 系统架构中的层之间放置多个负载拆分器。

每一个负载拆分器L都包括分配逻辑110，其被配置为将输入请求路由 /转发到服务器S。更具体地，配置分配逻辑110，以使得将对应于给定流的 所有分组转发到用于服务相关联请求的相同服务器S，包括通过系统拓扑变 化，除非在流期间服务器变为被禁用的或者变为不可用的。根据常用术语， 将可用于支持服务的服务器称为“在线”、“开机”或“活动”，而将不可用 的服务器称为“离线”或“停机”或禁用的、有故障的等。其他服务器可 以处于备用，同时在技术上为在线且运行中(尽管以减小的级别)，但不可 用于服务请求。出于在这个详细说明及以下权利要求书中的目的，将运行 中的、在线的和/或以其它方式可用于服务请求的服务器称为“可用的”服 务器，而将停机的、离线的、被禁用的和/或以其它方式不可用于服务请求 的服务器称为“不可用的”服务器。

根据图1a中的系统100的配置，n个服务器是可用的，而两个服务器 是离线的处于备用模式中，由“Sb”标记。因此，分配逻辑110采用n路 确定性分配函数(例如，在一个实施例中是n路哈希函数)来将输入请求 分配到n个可用服务器。在所示的示例中，在每一个输入分组报头中的字 段的元组上进行哈希处理，例如用于IP分组报头的公知的5元组哈希。这 个方案通常称为k元组哈希。也可以使用其他公知的哈希函数。出于说明 性目的，随后使用n作为除数，计算k元组哈希结果的余数R，其中，R识 别将分组路由到哪个服务器S。相应的查找表(未示出)用于将分配函数结 果(例如余数R)映射到相应服务器S的地址，随后将分组转发到该服务 器。由于用于属于给定流的所有分组的元组字段值会是相同的(借助定义， 根据标准流分类方案)，所以哈希计算和余数结果同样总是相同的，为相同 流中的所有分组产生相同的余数R。

图1b显示了系统100的配置，其中服务器S2成为无效的或者成为不 可用的，由“X”标记。结果，当前有n-1个服务器S可用。根据传统方案， 将重新配置每一个负载拆分器L1、L2和L3中的分配逻辑，以将新的输入 请求分配到(当前)n-1个可用服务器。例如，这可以使用与图1a中所示 的相同的哈希函数来完成，其中，以n-1代替模数n。而这通过在n-1个可 用服务器S中拆分输入请求108，而有利于负载平衡目的，(n-1)路确定性哈 希函数可以为给定流产生与为n路确定性哈希函数所获得的结果不同的结 果R。

前述是存在问题的，因为会将配置变化后的输入分组不必要地转发到 不同服务器。本应前往保持开机的服务器的流仍会被路由到那些服务器， 但本应路由到不可达的服务器的流会被重新定向到不同的服务器。此外， 一旦服务器恢复，从该服务器重新定向的流会保持重新定向到替换服务器， 直到流完成。典型地，将对应于在前请求的分组转发到不同服务器会导致 请求的服务不得不重新开始，或者至少产生额外的开销，这取决于所请求 的服务的类型。尽管有可能构造系统以在无需请求重新开始的情况下支持 中游传输，但这引起大量开销(例如状态同步、负载拆分器上额外的状态 信息等)，并且不可缩放。相反，实施了技术，以确保不管配置如何变化， 都将与给定流相关联的分组转发到相同服务器，只要该服务器在整个流中 保持可用。根据传统实践，这通过使用辅助信息(例如流识别和映射、流 状态数据等)和逻辑来完成，这会在DDOS攻击下被压制和/或增大负载拆 分器复杂性和成本。

根据图1a-1c中所示的实施例的方案，使用了不同的成本较低的方案。 不是将确定性分配函数从n路哈希函数改变为(n-1)路哈希函数，而是在第 一分配迭代期间使用相同的n路哈希函数。在一个实施例中，每一个负载 拆分器L保留服务器S及其可用状况的列表。如果n路分配函数的结果导 致到可用服务器S的映射(称为“命中”)，则将分组简单地转发到该服务 器。但如果n路分配函数导致到不可用服务器的映射(称为“未命中”)， 例如图1b中的服务器S2，则执行第二(n-1)路确定性分配函数，其会导致将 分组分配给可用的n-1个服务器S之一。如图1c进一步所示的，如果(n-1) 路分配函数导致另一个未命中，则执行第三(n-2)路分配函数。如果(n-2)路 分配函数导致未命中，则执行第四(n-3)路分配函数，以此方式继续，直至 分配函数结果映射到可用服务器。

前述方案确保了将对应于现有流的分组转发到借助对应于图1a中所示 的原始系统100配置的n路分配函数将流原始分配到的相同服务器(只要 该服务器可用)。此外，这在无需要求负载拆分器保留传统方案所需的流状 态的级别和映射信息的情况下实现了这个结果。另外，这个方案对于DDOS 攻击更具有弹性，因为它无需为每一个流保持相同级别的状态信息。

尽管图1a-1c中所示的和以上论述的技术实现了在无需相当大的流级 别追踪信息的情况下，将分组流分配给相同服务器，但它没有解决当由于 (以前)不可用服务器恢复在线(因而再次成为可用的)而引起可用服务 器的数量增大时的分配。例如，如果图1b和1c中的无效服务器S2或者S4 的任意一个恢复在线时，会发生这种增大。

假定服务器S2恢复在线，并且可再次用于服务输入请求。在服务器S2 不可用时，一个或多个负载拆分器L(如果适用的话)将正常情况下哈希处 理到服务器S2(假定原始的n个服务器可用)的流分配给一个或多个其他 服务器S。期望的是，负载拆分器104能够开始将对应于新请求的流分配给 服务器S2，而不是移动在服务器S2不可用时重新分配给另一服务器的现有 流。因此，每一个负载拆分器104应能够识别它在服务器S2不可用时分配 给其他服务器的流，并实施这样的流分配机制：其将对应于重新定向的流 的分组转发到在服务器S2不可用时将每一个重新定向的流所重新定向到的 服务器，直至该流完成。如本文所用的，将转发到其他服务器的流称为“重 分配的”流，因为它们被转发到与由分组的分配函数的初始迭代所识别出 的服务器不同的服务器(换句话说，分组必须从不可用服务器重分配给另 一个服务器)。

根据各个实施例，每一个负载拆分器保留重分配流的一个或多个列表， 使用一个或多个布隆过滤器，或者使用二者的组合，其中，使用具有预定 或可变尺寸的列表或表格，随后在没有更多空间来将额外重分配的流添加 到列表/表格时，使用布隆过滤器。当流哈希处理到服务器S2时，处理分组 的负载拆分器核对以查看它是否对应于在服务器S2不可用时重分配给另一 服务器S的流的列表中的流(或者由布隆过滤器标记的流)。如果流在列表 中，那么更新与何时最后见到来自流的分组相关联的计时器，并按照重分 配的结果重新定向流。对于下述的当前/下一个布隆过滤器方案，如果流在 当前布隆过滤器中，那么将相应的位设定在下一个布隆过滤器中，并重新 定向流。如果流既不在列表中也不在布隆过滤器中，那么将它发送到由分 配函数所识别的服务器。

假定系统100配置是图1d中所示的，而在前配置(在服务器S2恢复 在线之前)是图1c中所示的。在保留重分配流列表114和/或布隆过滤器 116的负载拆分器L1处接收新的分组112。在所示的实施例中，重分配流 列表114为每一个服务器S，或者可任选地，为近来不可用的每一个服务器 存储重分配流条目的列表。在一个实施例中，重分配流由它们的FlowID识 别。通常，可以使用用于定义并确定FlowID的几个公知的技术的任意一个 来确定用于给定流的FlowID，诸如在多个分组报头字段值上执行哈希函数， 例如在前述n元组哈希中所使用的，或者简单地串联多个字段值。在一个 实施例中，哈希函数与用于流分配的类似或相同，但没有模数运算。例如， 在一个实施例中，分配函数是在分组的相关联FlowID上执行的简单模数运 算。如下所述的，典型地在分组分类过程中执行用于分组的FlowID。此外， 可以缓存分组，以使得可以取回它们的(已经确定的)FlowID，而无需在 流分配函数中执行类似的哈希函数。

继续分组112的处理，假定在分组112上的n路分配哈希处理导致将 分组转发到不可用的服务器S4。如前所述，将执行第二(n-1)路分配哈希处 理，如有必要则重复，直至分配哈希处理导致将分组转发到可用服务器。 现在假定在分组120上的n路分配哈希处理导致将分组转发到服务器S2。 由于这个服务器近来不可用，所以可以有在重新哈希处理的流列表114中 的一个或多个条目或者布隆过滤器116之一中的标记，其识别如果服务器 S2可用时会分配给它的、但需要一个或多个重新哈希处理的一个或多个以 前的流，导致将一个或多个流被重分配给不同的一个或多个服务器。

考虑到与重分配流相关联的分组的可能性，在一个实施例中，为每一 个接收到的分组执行重分配流列表114的查找。由于重分配流列表可以存 储为表格，所以可以使用例如对应于服务器S2的ServerID执行针对表格的 相应查询，ServerID是针对包含ServerID值的索引(或者简单地，包含 ServerID值的列)而查询的，或者计算或取回FlowID，并用作用于查找的 输入值。取决于恢复开机或被代替的以前不可用服务器的数量，可能需要 执行分配函数的额外迭代。以下参考图6中的流程图600论述用于处理多 个服务器可用性配置的更普遍过程。

响应于服务器故障等(例如，为了维护、重配置等而离线)，一般惯例 是用备用服务器代替有故障的或不可用的服务器。图1e中示出了这种代替 的示例，其中，故障服务器S2由备用服务器102-1代替。通常，在服务器 变为不可用的时间与替换服务器被配置和开机并运行和使其可用以接管由 不可用服务器提供的服务及其他操作的时间之间会存在某一时间段。在这 个时间段，可以将分组流重分配给其他服务器，如前所述。但不是故障服 务器(例如服务器S2)恢复开机并使其可用以再次接收流，而是那些流现 在会转发到替换服务器。

在一个实施例中，希望服务器替换的实现方式对于与实际中同样多的 系统是透明的。在图1e所示的实施例中，保留了服务器映射表120，其将 ServerID映射到物理或虚拟服务器及其相应的IP地址。可任选地，可以将 服务器映射到用于使用层2转发的系统的MAC地址。从分配函数的一个实 施例的角度来看，函数输出整数，使用该服务器的IP地址将流分配到与所 述整数相关联的服务器。通过更新要被替换的服务器的映射信息，以使得 ServerID现在映射到替换服务器的IP地址，可以部分地有利于服务器替换。 如图1e所示的，用于ServerID 2的IP地址从分配给服务器S2的10.0.10.102 更新为分配给替换服务器102-1的10.0.10.110。

如上所述，在一些实施例中，布隆过滤器用于追踪被重分配的流。布 隆过滤器是空间高效的数据结构，其用于概率性地测试元素是否是集合的 成员。最简单形式的布隆过滤器采用单一哈希算法，其用于在适用的位位 置为元素的单行或列产生位值，通常称为一维位向量。另一个布隆过滤器 方案采用多个哈希算法，其具有映射到一维位向量的位结果。根据更高级 的布隆过滤器，用于多个哈希算法中每一个的位向量存储在各自的位向量 中，其也可以称为多维位向量。

在图3a-3c中显示了使用具有映射到一维位向量中的位值的多个哈希 算法来实施的布隆过滤器的示例。在这个示例中，存在三个哈希算法，示 为H₁(x)、H₂(x)和H₃(x)，其中，元素x是输入值。对于给定输入x₁，计算 每一个哈希算法H₁(x₁)、H₂(x₁)和H₃(x₁)的结果，并在对应于哈希结果的位 位置标记(例如设置为1)相应的位。例如，如图3a所示的，哈希函数H₁(x₁) 的结果是26，H₂(x₁)是43、H₃(x₁)是14。因此，设置在位置26、43和14 的位(例如将位值从“0”(清除)翻转为“1”(置位))。随后为后续输入 x_i值重复这个过程，结果得到图3b中所示的位向量，其中，设置的位以灰 色和黑色示出。图3b还示出了对于输入x₂的命中的结果(以黑色示出的位)。 通过使用x₂作为输入值来应用每一个布隆过滤器的哈希算法来验证命中 (也称为对元素x₂的查询)，随后确认对于每一个哈希算法结果，在位位置 是否存在位设置。例如，如果对于每一个哈希算法结果的位置存在位设置， 则结果就是命中，表示元素x_k对应于应用了哈希算法并设置了相应位的以 前输入值x_j的概率很高(取决于位向量的稀疏性)。

图3c显示了对于输入x₃的未命中的结果。在此情况下，没有设置对应 于哈希算法结果的位向量中的一个或多个位位置。图3b和3c示出了布隆 过滤器所固有的几个特点。首先，布隆过滤器可能产生错误肯定。这是因 为通过相对于多个输入x评价哈希算法所形成的位向量是对于每一个输入x 的单个结果的合并。因此，可以存在设置位位置的组合，该设置位位置对 于在针对布隆过滤器的位向量应用时的测试输入x_i产生命中结果，而输入 x_i不用于产生位向量。这称为错误肯定。布隆过滤器的另一个固有特点是它 们不产生错误否定。如果在应用于布隆过滤器的位向量时的输入x_i的评价 得到未命中，则必然会知道x_i不是以前布隆过滤器输入的集合的成员。

图4a-4c示出了为每一个布隆过滤器哈希算法保留单独的表格行(和一 维位向量)的布隆过滤器的示例。尽管将每一行示出为具有相同的长度， 但可以是不同哈希算法会产生不同长度的位向量。在针对输入x值(例如 图4a中针对x₁)评价哈希算法时，在对应于哈希算法结果的表格行的位位 置处设置相应的位。如同以前一样，输入x₂导致命中(无论是真实命中还 是错误肯定)，而输入x₃导致未命中。

由于哈希算法对于两个或更多个不同输入可以产生相同的结果(因而 在布隆过滤器位向量中设置相同位)，所以不可能在保证不清除对应于其他 输入结果的位的同时，去除单个集合成员(通过清除它们的位)。因而，传 统布隆过滤器技术是单向的：仅对应于将额外成员添加到集合，而将额外 的位添加到位向量。

添加额外集合成员的问题是减小了位向量稀疏性，这导致错误肯定的 增加，如上所述。同时，期望在持续的基础上继续添加新的集合成员，以 有效地存储便于确定是否重分配流的标记。根据采用布隆过滤器的一些实 施例的方案，提供了一种新颖的技术，其实现了布隆过滤器追踪重分配的 流，同时保持布隆过滤器稀疏。

更具体地，如下实施技术的一个实施例。参考图5，为根据传统方案会 使用的每一个单一布隆过滤器保留两个布隆过滤器。例如，在一个实施例 中，存在每个服务器S保留一对布隆过滤器。布隆过滤器的目的是保持追 踪从服务器S重新定向到另一个服务器的重新定向的流。根据一个方案， 以循环方式交换布隆过滤器的状态，一个布隆过滤器的状态称为“当前” 布隆过滤器，而另一个布隆过滤器的状态称为“下一个”布隆过滤器。当 服务器S停机时，随着重分配新的流，在当前和下一个布隆过滤器中设置 相同的位(或者将相同的位添加到下一个布隆过滤器，用于属于在当前布 隆过滤器中已经标记的流的分组)，同时仅针对当前布隆过滤器应用命中测 试。当服务器S开机时，当前布隆过滤器仅用于测试分组是否属于重新定 向的流；不将新的位添加到当前布隆过滤器。只有在分组属于进行中的重 新定向的流时，才在下一个布隆过滤器中设置用于该分组的布隆过滤器位， 如以下进一步详细解释的。

最初，清除在第一当前布隆过滤器和第一下一个布隆过滤器中的所有 位，如图5中在时间t₀所示的。正是对于这些第一当前和第一下一个布隆 过滤器，随着在第一时间段中处理新的重分配流，将新设置位(以灰色示 出)仅添加到第一当前布隆过滤器。此时(时间t₁)，在如由在时间t₁和t₂之间的时间差所示的第二时间段中，将新的设置位添加到第一当前和第一 下一个布隆过滤器。在一个实施例中，第一和第二(及随后的)时间段相 同。以黑色显示在第二时间段中已经添加到第一当前和第一下一个布隆过 滤器中的位向量的设置位。由于在比第一下一个布隆过滤器更长的时间段 中将设置位添加到第一当前布隆过滤器中的位向量(在下一个和当前布隆 过滤器中的填充位在时间上偏移)，所以在第一当前布隆过滤器(及随后的 当前布隆过滤器)中的位向量会总是不如第一下一个布隆过滤器(及随后 的下一个布隆过滤器)中的稀疏，除非在给定循环周期中没有将设置位添 加到任一布隆过滤器。

在此阶段，如在时间t₂₊所示的(“+”指示刚刚在时间t₂之后)，将第一 下一个布隆过滤器提生成为第二当前布隆过滤器，而第一布隆过滤器再循 环并再用作第二下一个布隆过滤器。结合当前布隆过滤器的再循环，清除 其位向量。如果在时间t₁和t₂之间的时间段中已经将设置位添加到第一当 前和第一下一个布隆过滤器，那么当第一当前布隆过滤器再循环时，新的 当前布隆过滤器位向量将包括设置的至少一些位，而新的下一个布隆过滤 器位向量将不包括设置位，如图5所示。

随后在进行中的基础上重复前述布隆过滤器提升和再循环过程，当前 布隆过滤器再循环并以下一个布隆过滤器代替。例如，借助在时间t₃和t₃₊所示的布隆过滤器位向量，在图5中示出了从第二当前与下一个布隆过滤 器到第三当前与下一个布隆过滤器的序列。

使用重分配流列表和布隆过滤器的组合可以提供优于单独的重分配流 列表或者布隆过滤器的优点。与借助布隆过滤器不同，由于重分配流列表 中的每一个条目都对应于各自的重分配流，所以错误肯定是不可能的。如 上所述，布隆过滤器为验证条目是否是由布隆过滤器位向量数据所标记的 条目集合的成员提供了极为有效的机制。通过组合两个方案，重分配流列 表可以用于主要命中测试，如果空间可用则将FlowID或其他标记添加到重 分配流列表，同时布隆过滤器可以用于溢出情况(例如，当重分配流列表 空间耗尽时)。与布隆过滤器不同，当条目不再相关时，例如当流完成时， 条目可以并且优选地应从重分配流列表中去除。可以使用几个公知的技术 之一来确定流完成的指示，在一个实施例中，响应于确定已经完成重分配 流，从重分配流列表中去除用于该流的FlowID或其他标记。

还存在将经由布隆过滤器标记的现有重分配流“添加”到重分配流列 表是有利的情况。如果在用于不可用服务器的重分配流列表已满的同时， 重分配用于重分配流的第一分组，则将用于流的相应标记(设置位)添加 到与服务器相关联的布隆过滤器(或者在使用布隆过滤器再循环方案的情 况下，添加到当前和下一个布隆过滤器两者)。如果在重分配流列表中具有 FlowID或其他标记的重分配流完成，则可以从列表去除那些条目，从而释 放空间以添加新的条目。如果是对应于在布隆过滤器中标记的、但不在重 分配流列表中的现有重分配流的分组，并且列表中有空间，则可以将相应 的标记添加到重分配流列表，同时不影响布隆过滤器位。最后，对应于布 隆过滤器中的流的位会老化移出，仅留下与重分配流列表中的流相关的标 记。

在一个实施例中，使用了以下技术。响应于将用于流的分组哈希处理 到服务器Si，执行以下操作。

针对重分配流的列表检查分组。如果它被列出，那么按照列表中所指 示的重分配流(或者如果你没有标记将特定流重新定向到的服务器的列表 条目，则进行重新哈希处理)。

否则(列表中没有)，就针对布隆过滤器检查它。如果布隆过滤器指示 不存在流，那么将流转发到服务器Si。

否则(不在列表中，但在当前布隆过滤器中)，那么(不修改下一个布 隆过滤器)将用于该特定流的标记(例如FlowID)添加到重分配流的列表。

最后，如果你运气好，从Si重新定向的仅有的流会是几个极其长时间 的流，在再循环布隆过滤器一次或多次后，布隆过滤器将保持全为零，因 为识别所有长时间流的标记都将进入到重分配流列表中。

图6是示出了使用架构100并根据图1a-1f中所示实施例来促进通用分 组分配/重分配方案的操作和逻辑的流程图600。首先，在块602中，确定 初始数量的可用服务器n。如由开始和结束循环块604和624所示的，在由 负载拆分器接收并属于要转发到服务器S之一的流的每一个分组上执行在 流程图的外循环内所示的操作和逻辑。在块606中，将整数计数i初始化为 n；i用作整数变量，其借助由开始和结束循环块610和616所示的内循环 中的分配函数的每一次迭代而倒计数。

在块608中，执行流分类操作以分类分组。流分类是本领域中公知的， 可以使用各种不同的流分类方案，包括上述的n元组哈希分类方案。在所 示的实施例中，为每一个流确定FlowID，并利用FlowID将分组与流相关 联。例如，可以以通过指针或其他类型的链接机制将每一个分组链接到其 FlowID的方式缓存分组。优选地，用于得到FlowID的技术应保证每一个 流都具有唯一的FlowID(在预期的操作参数内)。

如上提及的，开始和结束循环块610和616描绘了内循环，重复执行 该内循环，直至循环退出到块622。更具体地，在开始循环块610中，将分 组的FlowID用作函数输入以识别应将分组分配到的服务器S，来实施使用 当前值的i路分配函数。在决策块612中，确定所识别的服务器是否是可用 服务器。如果所识别的服务器不可用，则不能将分组转发到该服务器。因 而，对决策块612的回答是“否”，逻辑前进到块614，其中，要么将FlowID 添加到用于所识别的不可用服务器的重分配流列表，要么将相应的位添加 到当前和下一个布隆过滤器。在一个实施例中，如果存在可用空间以添加 新的条目，则将FlowID添加到不可用服务器的重分配流列表，如果不存在 可用空间，那么就将适用的位标记(添加)到当前和下一个布隆过滤器。 逻辑随后前进到结束循环块616，其中，i递减1，循环返回到开始循环块 610，以使用分组FlowID作为函数输入来执行下一个i路分配函数，其中， 随着每一次循环迭代，i减小1。

返回到决策块612，如果所识别的服务器是可用服务器，则回答为“是”， 逻辑流动到决策块618，其中，确定分组是否对应于重分配流。在一个实施 例中，通过使用分组的FlowID作为用于所识别的服务器的重分配流列表的 查找以检查FlowID是否在列表中，来执行这个确定。如果查找检查结果得 到未命中，那么就针对当前布隆过滤器，通过使用FlowID作为到命中测试 的输入来执行第二检查。如果重分配流列表检查或者当前布隆过滤器检查 结果得到命中，则分组就属于重分配流(对于决策块618的“是”结果)， 逻辑前进到块620，其中，如果FlowID在重分配流列表中，则更新用于 FlowID的时间戳以反映当前时间(时间戳表示重分配流的最近的分组)，或 者，如果不在列表中，则将从FlowID得到的相应位添加到用于下一个布隆 过滤器的位向量数据；无需将这些位添加到当前布隆过滤器，因为以前在 块614中为流中较早的分组已经添加了它们。逻辑随后前进到结束循环块 616，使得i递减1，且在开始循环块610开始循环的下一迭代。

这个循环迭代继续，直至由i路分配函数所识别的服务器是没有为其重 分配分组的流的可用服务器，结果得到在决策块612的“是”和在决策块 618的“否”。这导致逻辑退出循环，并前进到块622，其中，将分组转发 到所识别的服务器。这完成了分组的处理，并且逻辑循环从结束循环块624 返回到开始循环块604，以开始处理由负载拆分器接收到的下一分组。

在一个实施例中，在周期性基础上检查用于重分配流列表中的FlowID 的时间戳，以确定在当前时间与FlowID时间戳之间的差是否超过某一预定 值。这个时间差表示自接收到给定重分配流的最后分组以来的时间；超过 预定值表示完成了流。结果，从用于适用服务器的重分配流列表去除 FlowID。

图7显示了示例性负载拆分器700的示意性框图架构，其可以被配置 为实施本文公开的实施例的方案。负载拆分器700包括多个网络端口702， 每一个都包括物理(PHY)层块704、出口缓冲器E和入口缓冲器I。每一 个网络端口702还可以包括其他组件，它们是网络技术领域中技术人员所 公知的，为了简单和清楚而没有示出这些组件。多个网络端口702的每一 个都包括标记为U(上游)、D(下游)或M(管理)的块。当部署并运行 于负载拆分器位于网络705与网络服务器层之间的系统中时，全部或部分 上游端口将连接到服务器S，一个或多个下游端口将连接到网络705。在另 一系统环境中(未示出)，负载拆分器700将在不同服务器层之间实施，例 如在网络服务器层与应用服务器层之间。因此，上游端口会连接到应用服 务器层中的服务器，而下游端口会连接到网络服务器层中的服务器。

管理端口通常可以用于管理的目的，例如从管理计算机706等将软件 下载到负载拆分器，配置负载拆分器，从负载拆分器接收数据，等等。可 选地，可以经由上游端口或下游端口中的一个传送管理操作。在一些实施 例中，管理端口(或另一端口，未示出)可以耦合到另一负载拆分器L，实 现多个负载拆分器共享信息，例如关于重分配流的信息、布隆过滤器数据、 统计数据等。注意，由于用于布隆过滤器的位向量可以作为整数传送到另 一负载拆分器，所以用于在负载拆分器之间共享布隆过滤器数据的开销极 低。

负载拆分器700进一步包括主缓冲器708、存储器710、存储器控制器 712、指令存储器714、互连716和处理器718。出口缓冲器E和入口缓冲 器I中的每一个都可操作地耦合到主缓冲器708，它们可以实施为存储器710 的部分，或者可以单独实施。存储器710包括一类动态随机存取存储器 (DRAM)，在所示实施例中经由存储器控制器712进行访问。可选地，处 理器718可以具有一个或多个集成的存储器控制器或者代理，其被配置为 支持对存储器710的访问。在运行时间操作期间，出于多个目的，分配存 储器710的地址空间内的存储器的块，包括储存重分配流列表720、布隆过 滤器722和一个或多个应用，如由应用空间724所示的。对应于服务器可 用性历史725的数据也可存储在存储器710中，如果此类数据被追踪的话。

处理器718通常可以包括通用处理器，包括一个或多个核心726，或者 专用处理器，例如网络处理单元(NPU)，包括诸如核心、微引擎等的多个 处理元件。处理器718还可以包括哈希单元728，如图所示。在运行时间操 作期间，将指令从指令存储器714载入应用空间724，或者直接载入与核心 或微引擎726相关联的高速缓冲存储器级，并在核心或微引擎上执行以实 现为其配置指令的操作。通过示例而非限制，将指令存储器714示出为存 储用于多个模块的指令，包括分组识别/流分类模块730、分配逻辑732、统 计引擎734和网络堆栈736。公知的，负载拆分器等通常可以包括其他指令， 以实现通常由负载拆分器执行的其他操作；为了清楚，没有显示这些指令。

分组识别/流分类模块730包括被配置为识别和/或分类从网络705接收 到的输入分组的指令。例如，如上所述，基于在分组的报头字段中的信息， 可以使给定分组与FlowID相关联。流分类和/或分配函数可以采用哈希单元 728，它是基于硬件的组件，被配置为使用一个或多个哈希算法执行哈希运 算。可选地，可以经由由处理器718执行软件指令，或者经由分离的基于 硬件的组件(未示出)来实施全部或部分哈希算法。

分配逻辑732包括被配置为实施本文所述的分组分配和重分配操作的 指令。在一些实施例中，这个模块传送用于分组的FlowID，随后使用诸如 本文所述的哈希函数的可适用的确定性分配函数将分组分配给适当的服务 器S。分配逻辑还被配置为实现重分配流列表720和布隆过滤器722。在一 些实施例中，使用以上参考图5所述的当前/下一个布隆过滤器再循环方案 来实施布隆过滤器。

统计引擎734包括被配置为实施统计运算的指令，包括但不限于收集 用于分组流的统计信息，并计算由负载拆分器700使用的各种配置参数。 例如，统计引擎734可以被配置为响应于相应分组流数据的处理，动态重 配置布隆过滤器再循环频率。另外或者可选地，统计引擎734可以被配置 为从管理计算机706和/或从另一负载拆分器接收统计数据。此外，统计引 擎734可以被配置为从一个或多个服务器S接收统计数据。例如，可以采 用使用专用逻辑端口的管理通道，以便于在负载拆分器700与服务器S之 间的非业务数据的传送。

网络堆栈736包括用于传送源自负载拆分器700或者以负载拆分器700 为目的地的数据的指令。例如，这种传送可以在负载拆分器700与管理计 算机706、另一负载拆分器L、和/或服务器S之间。在一些实例中，可以 使用公知的TCP/IP网络堆栈来实施这种传送。另外，可以使用其他公知的 协议。

在一个实施例中，指令存储器714包括非易失性储存设备，例如闪存 或大容量储存设备(例如硬盘)。可任选地，用于一个或多个前述模块的指 令可以结合负载拆分器的初始化而从管理计算机706或通过网络705下载。 另外，可以经由管理端口或另一端口下载对这些模块的更新。

除了经由在通用或专用处理器上执行指令来实施操作以外，可以使用 嵌入式逻辑等来实施由本文所述实施例执行的各种操作。此外，负载拆分 器700可以采用多个处理器，包括一个或多个通用处理器和专用处理器的 组合。另外，一个或多个网络端口702可以采用嵌入式逻辑，以执行本文 所述的一个或多个操作。例如，可以使用被配置为执行分组识别和/或流分 类的高级单端口或多端口网络接口控制器(NIC)，以代替经由在处理器718 上执行指令而执行的这些操作。

根据本文公开的实施例的原理和教导的分配逻辑及相关联操作的实现 方式提供了比当前技术更显著的优势。例如，根据在相同层中使用多个负 载拆分器的系统架构，在其中可以由两个或更多个不同负载拆分器接收与 相同流相关联的分组，传统方案要求相当大程度的流状态信息在负载拆分 器之间同步。这个流状态信息通常包括与由负载拆分器处理的每一个流相 关的状态信息。作为简化示例，这种信息可以表述(大意是)属于FlowID 3 的分组要被输送到ServerID S5。尽管这个技术对于处理在连接到单一负载 拆分器的上游层中的拓扑变化适用，但它不能很好地缩放，因为相同的信 息需要在其他负载拆分器可用，以便那些负载拆分器获知将属于流的分组 转发到何处，所述流包括已经或将要由另一负载拆分器处理的分组。

根据本文的实施例，由于考虑到系统拓扑变化，结合适于分配函数的 方案使用分配函数来转发分组，所以每一个负载拆分器都可以将分组转发 到适当的服务器，而无需共享流状态信息，或者甚至无需预先获知这种流 状态信息。

在图1f中示出了这个功能的示例，其将负载拆分器L1示为有故障且 不可用于转发输入分组。如由分组112a和118a所示的，与以前由负载拆分 器L1在它成为不可用之前处理的流相关联的分组(例如，分组112和118) 现在示出为由负载拆分器L2处理。由于每一个负载拆分器L1和L2都使用 相同的分配函数和逻辑，所以负载拆分器L2会将相同的分组转发到适当的 服务器，其被指定为处理与分组相关联的流。此外，在需要重分配的情况 下，两个负载拆分器L1和L2会将对应于相同流的分组重分配给相同的服 务器。尽管未示出，但负载拆分器L3也被配置为以类似的方式将分组转发 到适当的服务器。

除了在负载拆分器上实现外，实施例的方案可以更普遍地在任意类型 的网络交换或转发元件上实施，其利用流分配和/或转发分组，其中将与相 同流相关联的分组分配和/或转发出相同的网络端口，朝向相同的下一跳(如 另一网络元件)或者到相同的端点(例如，服务器、计算机等)。

除了使用物理负载拆分器或者其他物理交换元件实现外，该技术也可 以部署在虚拟环境中，例如通常用于数据中心和服务器群中的那些环境。 例如，服务器平台可以被配置为从网络接收分组，并将那些分组分配给由 服务器平台托管的多个虚拟服务器实例。根据此类实现方式，交换元件以 软件实现为虚拟交换机、负载拆分器、负载平衡器等。

尽管参考特定实现方式描述了一些实施例，但根据一些实施例，其他 实现方式也是可能的。另外，无需以附图所示和本文所述的特定方式布置 所示和/或所述的元件或其他特征的布置和/或顺序。根据一些实施例，许多 其他布置是可能的。

在附图中所示的每一个系统中，在一些情况下，元件中的每一个都可 以具有相同的参考标记或不同的参考标记，以暗示所示元件可以是不同的 和/或相似的。但元件可以足够灵活以具有不同实现方式，并与本文所示或 所述的一些或全部系统工作。附图中所示的各种元件可以是相同的或不同 的。将哪一个称为第一元件和将哪一个称为第二元件是任意的。

在说明书和权利要求书中，可以使用术语“耦合”和“连接”及其派 生词。应理解，这些术语并非旨在作为彼此的同义词。相反，在特定实施 例中，“连接”可以用于指示两个或更多个元件彼此直接物理或电气接触。 “耦合”可以表示两个或更多个元件直接物理或电气接触。但“耦合”也 可以表示两个或更多个元件彼此没有直接接触，但仍彼此协作或相互作用。

实施例是本发明的实现方式或示例。说明书中对“实施例”、“一个实 施例”、“一些实施例”或者“其他实施例”的提及表示结合实施例说明的 特定特征、结构或特性包括在本发明的至少一些实施例中，但不一定是所 有实施例中。“实施例”、“一个实施例”或“一些实施例”的多次出现不一 定全都指代相同的实施例。

本文所述和所示的全部组件、特征、结构、特性等并非都需要包括在 特定的一个或多个实施例中。例如，如果说明书表述“可以”、“或许”、“能 够”或者“可能”包括了组件、特征、结构或特性，则该特定组件、特征、 结构或特性不是必需被包括。如果说明书或权利要求书提及“一(a)”或 “一(an)”元件，其并非表示仅有一个元件。如果说明书或权利要求书提 及“另外的”元件，其不排除存在多于一个另外的元件。

如上所述，通过相应的软件和/或固件组件和应用可以便于本文实施例 的多个方案，例如由在负载拆分器上的处理器或NPU执行的软件或固件。 因而，本发明的实施例可以用作或者支持在某一形式的处理核心(例如处 理器或NPU，或者多核处理器的一个或多个核心)上执行的软件程序、软 件模块、固件、和/或分布式软件、运行在处理器或核心上的或者在机器可 读介质上或内实施或实现的虚拟机。机器可读介质包括用于存储或发送以 机器(例如计算机)可读形式的信息的任何机制。例如，机器可读介质可 以包括只读存储器(ROM)；随机存取存储器(RAM)；磁盘储存介质；光 储存介质；和闪存设备等。

本发明的所示实施例的以上说明，包括在摘要中所述的，并非旨在是 穷举性的，或者将本发明局限于公开的准确形式。尽管在此出于示例性目 的说明了本发明的特定实施例和示例，但如相关领域技术人员会认识到的， 在本发明的范围内的多个等效修改是可能的。

按照以上的详细说明可以做出这些修改。用于以下权利要求书中的词 语不应解释为将本发明局限于在说明书和附图中公开的特定实施例。相反， 本发明的范围由以下权利要求书整体上确定，其应按照权利要求解释的既 定原则来解释。