分布负载平衡器中的不对称封包流

摘要

一种分布负载平衡器，其中路由器从至少一个客户端接收封包，并且将封包流路由至多个进入服务器。针对未知封包流，进入服务器配合主要流量跟踪器和次要流量跟踪器来建立至服务器节点的连接。针对已知封包流，所述进入服务器将所述封包发送至目标服务器节点。所述服务器节点随机地选择用于所述封包流的传出封包的外出服务器。所述进入服务器、流量跟踪器和外出服务器通过负载平衡器节点层中的多个负载平衡器节点实现。用于给定封包流的所述进入服务器和外出服务器可处于不同的负载平衡器节点上。所述负载平衡器节点可使用一致哈希函数来根据封包流客户端/公共端点对计算用于所述节点的一致哈希环，从而可以定位与给定封包流相关联的节点。

说明书

背景技术

常规负载平衡器通常为单一、专门盒，其包括多个网络接口控制 器(NIC)，例如八个NIC，其中NIC中的一些操控来自客户端的进入 流量/到客户端的外出流量而其他NIC操控来自正在负载平衡的主机 装置(例如，服务器如网络服务器)的传出流量/到主机装置的传入流 量。这些常规负载平衡器上的带宽或通量通常在客户端侧上为40吉 比特/秒(Gbps)而在服务器侧上为40Gbps的范围。随着基于网络的应 用和基于网络的服务如云计算服务的规模和范围增加，数据中心可容 纳数百或甚至数千个需要负载平衡的主机装置(例如，网络服务器)。 常规负载平衡器在这类环境中可能不会较好地调整。

此外，常规负载平衡器通常使用应用于从主机装置收集的数据以 选择哪一个主机装置将操控连接的技术例如最大连接(或maxconns)、 循环和/或最小连接(leastconns)。另外，常规负载平衡器通常充当其 在前面的主机装置的代理，且因而终止来自客户端的连接(例如，传 输控制协议(TCP)连接)并且在主机装置与负载平衡器之间建立的 TCP连接上将客户端流量发送至主机装置。因此，在使用这些常规负 载平衡器时，主机装置和客户端不在直接TCP连接上通信。

附图说明

图1是根据至少一些实施方案的示例性分布负载平衡系统的方 框图。

图2是根据至少一些实施方案的可由图1的分布负载平衡器系统 实施的负载平衡法的较高水平流程图。

图3示出根据至少一些实施方案的包括进入、外出和流量跟踪器 部件的示例性负载平衡器节点。

图4示出根据至少一些实施方案的分布负载平衡器中的路由和 封包流。

图5示出根据至少一些实施方案的将进入节点向边缘路由器公 布。

图6是根据至少一些实施方案的多路径路由方法的流程图。

图7图形化示出根据至少一些实施方案的不对称封包流。

图8示出根据至少一些实施方案的分布负载平衡系统中的封包 流。

图9A和9B提供根据至少一些实施方案的在分布负载平衡系统 中建立连接时的封包流的流程图。

图10A至10G示出根据至少一些实施方案的分布负载平衡系统 中的封包流。

图11A至11D示出根据至少一些实施方案的影响负载平衡器节 点一致哈希环中的成员关系的事件的操控。

图12是根据至少一些实施方案的可根据健康检查间隔由每个负 载平衡器节点执行的健康检查方法的较高水平流程图。

图13示出根据至少一些实施方案的从另一个负载平衡器节点对 一个负载平衡器节点进行健康检查的方法。

图14图形化示出根据至少一些实施方案的一个负载平衡器节点 对一个或多个其他负载平衡器节点进行健康检查。

图15示出根据至少一些实施方案的负载平衡器节点对服务器节 点进行健康检查。

图16图形化示出根据至少一些实施方案的可由负载平衡器节点 110保持的另一个节点的健康状况的视图。

图17示出根据至少一些实施方案的可由每个负载平衡器节点保 持的健康信息。

图18A和18B示出根据至少一些实施方案的操控负载平衡器节 点失效。

图19A和19B图形化示出根据至少一些实施方案的连接发布技 术。

图20是根据至少一些实施方案的可由每个负载平衡器模块执行 的连接发布方法的较高水平流程图。

图21是根据至少一些实施方案的将在连接发布封包中接收的活 动连接信息分配至目标负载平衡器节点的方法的流程图。

图22示出根据至少一些实施方案的将在连接发布封包中接收的 活动连接信息分配至目标负载平衡器节点的替代方法。

图23示出根据至少一些实施方案的负载平衡器节点的示例性软 件堆栈架构。

图24示出可在实施方案中使用的核心封包处理技术的方面。

图25示出根据至少一些实施方案的处理负载平衡器节点上的数 据流的示例性多核心封包处理器。

图26示出根据至少一些实施方案的处理负载平衡器节点上的数 据流的另一个示例性多核心封包处理器。

图27示出根据至少一些实施方案的通过负载平衡器节点过程对 传入封包的处理。

图28示出根据至少一些实施方案的通过负载平衡器节点过程对 传出封包的处理。

图29示出根据至少一些实施方案的包括生产环境中的分布负载 平衡器的负载平衡系统。

图30示出根据至少一些实施方案的分布负载平衡器测试系统， 其并入消息总线机构，所述机构使得多个分布负载平衡系统部件能够 配置并执行于单一过程中或作为单一过程。

图31和32示出根据至少一些实施方案的消息总线封包适配器和 封包管线。

图33A示出根据至少一些实施方案的示例性提供者网络环境。

图33B示出根据至少一些实施方案的如图33A展示的示例性提 供者网络环境中的分布负载平衡器实行方案。

图34A示出根据至少一些实施方案的分布负载平衡器和服务器 节点的示例性物理机架实行方案。

图34B示出根据至少一些实施方案的分布负载平衡器和服务器 节点的另一个示例性物理机架实行方案。

图35示出根据至少一些实施方案的一个、两个或更多个分布负 载平衡器实施于网络中的示例性连网环境。

图36是示出可以在一些实施方案中使用的示例性计算机系统的 框图。

虽然在本文中通过列举若干实施方案和示意性附图的实例的方 式描述了实施方案，本领域的技术人员应认识到，实施方案并不限于 所描述的实施方案或附图。应理解，附图和对其的详细描述并非意图 将实施方案限于所公开的特定形式，而是相反，其意图在于涵盖落入 由所附权利要求书所界定的精神和范围内的所有修改、等同物以及替 代方案。本文中使用的任何标题都仅用于组织目的，并且并不意图用 于限制描述或权利要求书的范围。如贯穿本申请所用，词语“可”是以 允许意义(即，意味着有可能)而不是强制意义(即，意味着必须)使用。 类似地，词语“包括(include/including/includes)”表示包括但不限于。

具体实施方式

描述网络环境中的分布负载平衡的方法和系统的各种实施方案。 描述可根据各种网络环境中的分布负载平衡器的实施方案来实施的 分布负载平衡法和系统的实施方案。分布负载平衡器的实施方案可例 如用于促进和保持外部网络如互联网上的客户端与局部网络，例如如 图33A和33B示出的提供者网络1900上的目的地，通常为服务器(例 如，网络服务器、应用服务器、数据服务器等)之间的封包流，例如 传输控制协议(TCP)技术封包流。虽然本文主要关于处理TCP封包流 来描述实施方案，但是应注意实施方案可应用于除了TCP以外的其 他数据通信协议，以及除了处理封包流以外的其他应用。

分布负载平衡器可用于促进和保持具体客户端与选定服务器(例 如，网络服务器)之间的TCP封包流。然而，分布负载平衡器并不终 止来自客户端的TCP流并且并非如在常规负载平衡器中所进行的那 样充当服务器的代理。替代地，分布负载平衡器的负载平衡器节点将 从客户端接收的TCP封包依路由传递至目标服务器，并且服务器使 用其TCP堆栈来管理至客户端的TCP连接。换句话说，服务器终止 来自客户端的TCP封包流。

另外，并非如在常规负载平衡器技术中所进行的那样，负载平衡 器节点基于应用于从服务器收集的信息的负载平衡技术或算法来作 出关于哪一个服务器为连接请求提供服务的决定，负载平衡器节点可 随机选择服务器来接收新的连接请求，并且分布负载平衡器的驻留于 服务器节点上的部件基于相应服务器的当前状态的一个或多个量度 来局部作出关于是否选定服务器接受或拒绝新的连接请求的决定。因 此，关于哪些服务器接受连接请求的决定从负载平衡器节点移动至将 操控连接的服务器节点。换句话说，决定被移动至更接近于将为连接 请求提供服务的位置和时机。

为了促进和保持客户端与服务器之间的封包流，分布负载平衡器 的实施方案可使用各种技术或技艺，包括但不限于多路径路由技术、 一致哈希技术、分布哈希表(DHT)技术、边界网关协议(BGP)技术、 成员关系跟踪、健康检查、连接发布和封包封装和解封。分布负载平 衡系统的这些以及其他方面于下文相对于附图来描述。

分布负载平衡系统

图1是根据至少一些实施方案的示例性分布负载平衡系统的方 框图。分布负载平衡器的实施方案可实施于网络100，例如如图33A 和33B示出的服务提供者的提供者网络1900中。作为分布负载平衡 器系统中的客户端封包操控的较高水平概述，网络100的一个或多个 客户端160可例如经由外部网络150如互联网连接至网络100的边界 路由器102。边界路由器102可将来自客户端160的传入封包(例如， TCP封包)依路由传递至分布负载平衡器的边缘路由器104部件，其 将传入封包依路由传递至分布负载平衡器系统的负载平衡器节点层 中的负载平衡器(LB)节点110。在至少一些实施方案中，边缘路由器 104可根据每流哈希多路径路由技术，例如等价多路径(ECMP)哈希技 术来作出路由决定。负载平衡器节点110进而封装封包(例如，根据 用户数据报协议(UDP))并且经由网络100上的网络结构120(例如， L3网络)将封装封包依路由传递至服务器节点130上的局部负荷平衡 器模块132。结构120可包括一个或多个连网装置或部件包括但不限 于交换机、路由器和电缆。在服务器节点130上，局部负荷平衡器模 块132将封包解封并且将客户端TCP封包发送至服务器134的TCP 堆栈。服务器节点130上的服务器134然后使用其TCP堆栈来管理 至客户端160的连接。

图2是根据至少一些实施方案的可由图1的分布负载平衡器系统 实施的负载平衡法的较高水平流程图。如在常规负载平衡器中所发生 的那样，分布负载平衡器系统的实施方案可能无法解决在多个目的地 (例如，网络服务器)之间分配负载的疑难问题。举例来说，常规负载 平衡器通常使用技术或算法如最大连接、循环和/或最小连接技术来 选择哪一个服务器应操控连接。然而，这些技术具有缺点，并且在其 中用于作出负载平衡决定的数据经常几乎立即过时的分布式系统中 尤其难以成功地执行。在分布负载平衡器系统的至少一些实施方案 中，并非如在常规负载平衡器中所进行的那样使用负载平衡技术中的 一种或多种来尝试选择服务器节点130以满足连接请求，负载平衡器 节点层中的负载平衡器节点110可随机确定服务器节点130来接收客 户端连接的请求。如果此服务器节点130考虑自身超载，服务器节点 130可将连接请求发送回到负载平衡器节点110，由此通知负载平衡 器节点110服务器节点130当前不能操控连接。然后，负载平衡器节 点层可随机确定另一个服务器节点130来接收连接请求，或替代地可 向请求客户端160传回错误消息以通知客户端160当前不能建立连 接。

如图2的10指示，分布负载平衡器系统的负载平衡器节点层接 收来自来源的通信会话(例如，TCP连接)的请求。来源可为例如相对 于实施分布负载平衡器系统的网络100的外部网络150上的客户端 160。在至少一些实施方案中，可在网络100的边界路由器102处接 收来自客户端160的请求，并且其依路由传递至边缘路由器104，所 述边缘路由器例如使用每流等价多路径(ECMP)哈希技术将传入封包 依路由传递至负载平衡器节点层中的负载平衡器(LB)节点110以伪随 机选择来自客户端160的具体连接请求依路由传递所到达的负载平 衡器节点110。

如20指示，负载平衡器节点层随机选择目的节点并且将连接请 求转发至选定目的节点。目的节点可为例如前面有负载平衡器的多个 服务器节点130中的一个。在至少一些实施方案中，负载平衡器层中 的负载平衡器节点110可从所有已知服务器节点130之中随机选择服 务器节点130来接收连接请求。然而，除了从所有已知服务器节点 130之中纯粹地随机选择以外的其他方法可在一些实施方案中使用以 选择接收连接请求的服务器节点130。举例来说，在一些实施方案中， 关于服务器节点130的信息可由负载平衡器节点110用于将服务器节 点130的随机选择加权。举例来说，如果负载平衡器节点110知道不 同服务器节点130为不同类型装置或配置有不同CPU，因而具有不 同能力或容量，此信息可用于使随机选择偏向(或远离)服务器节点 130的具体类型或配置。

如30指示，目的节点确定是否它可接受通信会话。在至少一些 实施方案中，服务器节点130上的局部负荷平衡器(LB)模块132基于 相应服务器134的当前状态的一个或多个量度来确定是否服务器节 点130上的相应服务器134可接受新的连接。

在40处，如果接受连接请求，然后如50指示，目的节点通知负 载平衡器节点层目的节点可操控连接。如60指示，然后经由负载平 衡器节点层在来源(例如，客户端160)和目的节点(例如，服务器节点 130上的服务器134)之间建立通信会话。在至少一些实施方案中，服 务器节点130上的服务器134使用TCP堆栈来管理至客户端160的 连接。

在40处，如果未接受连接请求，然后如70指示，目的节点通知 负载平衡器节点层，并且方法可返回到元件20。然后，负载平衡器 节点层可随机选择另一个目的节点20，或替代地可通知请求客户端 160当前不能建立连接。注意客户端160可但是不一定重新提交连接 请求来再次在元件10处开始此方法。

再次参看图1，分布负载平衡器系统的至少一些实施方案可使用 商用硬件以将在网络100上的边缘路由器104处接收的客户端流量依 路由传递至网络100上的服务器节点130。分布负载平衡器的至少一 些实施方案可包括负载平衡器节点层，其包括多个负载平衡器节点 110。在至少一些实施方案中，每个负载平衡器节点110可在负载平 衡器节点层中以多个角色中的一个或多个来提供服务。负载平衡器节 点110的这些角色可包括角色进入节点和外出节点和流量跟踪器节 点(作为给定封包流的主要流量跟踪器或次要流量跟踪器)。在至少一 些实施方案中，每个负载平衡器节点110可在负载平衡器节点层中实 施为单独计算装置或在单独计算装置上，例如商用机架安装计算装 置。在至少一些实施方案中，每个负载平衡器节点110可以进入节点、 外出节点和流量跟踪器节点(作为封包流的主要或次要流量跟踪器) 的三个角色中的每一个来提供服务，并且对于具体封包流来说，负载 平衡器节点110总体上仅以一个(但是可能两个或三个)角色来提供服 务。然而，应注意，在至少一些实施方案中，不允许负载平衡器节点 110同时充当具体封包流的主要流量跟踪器和次要流量跟踪器。或者， 在一些实施方案中，每个负载平衡器节点110可仅以三个角色中的一 个来提供服务。在此实施方案中，独立多组计算装置可在负载平衡器 节点层中专门实施为进入节点、外出节点和流量跟踪器节点。

在至少一些实施方案中，可采用一致哈希和一致哈希环技术来确 定封包流的主要和次要流量跟踪器。来自客户端的每个封包流可例如 通过由以下组成的4元组来唯一地识别：客户端IP地址、客户端端 口、服务器(公共)IP地址和服务器端口。此识别符可缩写为CP或 CcPp，其指示客户端和公共端点对。由于来自边缘路由器104的哈 希多路径(例如，ECMP)流量分布，与任何给定TCP流(或CP对)相关 联的封包可出现于作为进入服务器112操作的任何负载平衡器节点 110上。使用一致哈希以使得当封包到达充当进入节点的负载平衡器 节点110时，进入节点可确定哪一个负载平衡器节点110负责保持封 包流的状态(即，主要流量跟踪器节点)。CP对可通过进入节点哈希成 一致哈希环来确定哪一个负载平衡器节点110负责保持封包流的状 态信息。一致哈希环中的根据封包流的CP对的一致哈希确定的节点 110是充当封包流的主要流量跟踪器的节点110。在至少一些实施方 案中，一致哈希环中的后续节点充当封包流的次要流量跟踪器。

图3示出根据至少一些实施方案的示例性负载平衡器(LB)节点 110，其包括实施所有三个角色(进入、外出和流量跟踪器)的部件。在 此实施例中，进入服务器112部件执行接收来自客户端的传入TCP 封包并且将TCP封包作为封装封包发送至服务器的进入角色。外出 服务器114部件执行接收来自服务器的传出封装封包并且将解封 TCP封包发送至客户端的外出角色。流量跟踪器116部件充当在客户 端160与服务器134之间建立的一个或多个封包流的主要或次要流量 跟踪器。进入服务器112还可与负载平衡器节点110上的流量跟踪器 116，或与另一个负载平衡器节点110上的流量跟踪器116通信以响 应于从相应客户端160接收的连接请求来启始客户端与服务器134中 的一个之间的TCP连接，或获得封包流的映射信息。

负载平衡器节点

再次参看图1，在至少一些实施方案中，负载平衡器节点层中的 负载平衡器节点110接收来自网络上的一个或多个路由器104的客户 端流量(封包，例如TCP封包)并且根据结构120上的分布负载平衡器 系统所使用的协议(例如，用户数据报协议(UDP))将封包封装。然后， 负载平衡器节点层经由结构120将封装封包转发至目的地服务器节 点130。每个服务器节点130包括作为负载平衡器系统的部件的局部 模块132。模块132可在本文中称为负载平衡器模块或简称为LB模 块，并且可以软件、硬件或其组合形式实施于服务器节点130上。在 每个服务器节点130处，相应负载平衡器模块132将封包解封并且将 TCP封包发送至局部TCP堆栈以正常TCP处理。在至少一些实施方 案中，负载平衡器节点层可保持每一个客户端-服务器TCP流的状态 信息；然而，负载平衡器节点层中的负载平衡器节点110可能不解释 关于TCP流的任何事项。管理相应服务器节点130上的服务器134 与客户端160之间的每个流。分布负载平衡器系统确保TCP封包到 达正确目的地服务器134。每个服务器节点130处的负载平衡器模块 132响应于从负载平衡器节点110接收的客户端连接请求来作出关于 是否相应服务器134接受或拒绝新连接的决定。

在至少一些实施方案中，分布负载平衡系统可使用一致哈希技术 来例如确定哪一个(些)负载平衡器节点110应记忆哪一个服务器节点 130负责具体TCP封包流。通过使用一致哈希技术，负载平衡器节点 层中的负载平衡器节点110可被视为一致哈希环，并且负载平衡器节 点110可跟踪环中的成员关系并且根据一致哈希函数来确定环中的 负责具体封包流的具体成员。在至少一些实施方案中，存在负责跟踪 客户端160与服务器134之间的每个封包流的两个负载平衡器节点 110；这些节点110可被称为主要流量跟踪器(PFT)节点和次要流量跟 踪器(SFT)节点。在至少一些实施方案中，主要流量跟踪器为此流的 一致哈希环上的第一负载平衡器节点110，并且次要流量跟踪器为一 致哈希环上的不同于主要流量跟踪器节点的下一个或后续负载平衡 器节点110。在此布置中，如果主要流量跟踪器节点失效，那么次要 流量跟踪器节点可成为新的主要流量跟踪器，并且另一个负载平衡器 节点110(例如，一致哈希环上的下一个节点110)可承担次要流量跟踪 器的角色。应注意，在至少一些实施方案中，不允许负载平衡器节点 110同时充当给定封包流的主要流量跟踪器和次要流量跟踪器。一致 哈希环上的这和其他成员关系变化稍后在此文件中论述。在至少一些 实施方案中，负载平衡器实行方案的配置信息(例如，当前实行的负 载平衡器节点110和服务器节点130的权威列表)可由分布负载平衡 系统的配置服务122部件保持，所述部件可例如实施于经由结构120 耦接至负载平衡器节点110的一个或多个服务器装置上。

在至少一些实施方案中，除了充当主要和次要流量跟踪器节点以 外，负载平衡器节点110还可以给定流的两个其他角色中的一个来执 行：进入节点角色和外出节点角色。封包流的进入节点是接收来自边 缘路由器104的相应封包流并且经由结构120将封包流(作为封装封 包)转发至服务器节点130上的选定服务器134的负载平衡器节点 110。进入节点是将实际客户端数据(TCP数据封包)移动至相应目的 地服务器节点130的唯一负载平衡器节点110。进入节点保持TCP流 与目的地服务器节点130上的相应负载平衡器模块132的映射以使得 进入节点知道将客户端流量转发至哪一个负载平衡器模块132。外出 节点是负责将封包流的经由结构120从服务器节点130接收的响应流 量经由边界网络转发至相应客户端160的负载平衡器节点110。负载 平衡器模块132根据负载平衡器协议(例如，UDP)将从服务器134获 得的响应封包封装并且经由结构120将封装响应封包发送至此流的 相应外出节点。外出节点是无状态的并且仅将封包解封并且将响应封 包(例如，TCP封包)发送至边界网络直至边界路由器102以便经由外 部网络150递送至相应客户端160。

如前所述，在至少一些实施方案中，每个负载平衡器节点110可 对于不同封包流执行进入节点、外出节点和/或流量跟踪器节点(作为 主要或次要流量跟踪器)的角色。负载平衡器节点层中的单一负载平 衡器节点110可以任何一个角色来执行，取决于节点处理什么封包 流。举例来说，在至少一些实施方案中，负载平衡器节点110可对于 一个封包流作为进入节点来执行，对于另一个封包流作为主要或次要 流量跟踪器来执行，并且对于另一个封包流作为外出节点来执行。另 外，在至少一些实施方案中负载平衡器节点110可对于同一封包流执 行多个角色，例如作为给定封包流的进入节点和主要(或次级)流量跟 踪器节点。然而，在至少一些实施方案中，出于冗余和恢复目的，不 允许负载平衡器节点110对于同一封包流同时充当主要和次要流量 跟踪器节点。

上述实施方案，其中每个负载平衡器节点110可以进入服务器、 外出服务器和流量跟踪器的三个角色中的任何一个来提供服务。然 而，在一些实施方案中，不同组的计算装置可分配至负载平衡系统中 的不同角色。举例来说，在一些实施方案中，可存在不同组的进入节 点、外出节点和流量跟踪器节点，其各自实施于单独计算装置上。作 为另一个实例，在一些实施方案中，一组计算装置可同时充当进入节 点和流量跟踪器节点，而另一组计算装置只可作为外出节点来提供服 务。

负载平衡器模块

如前所述，每个服务器节点130包括作为负载平衡器系统的部件 的局部负载平衡器模块132。模块132可以软件、硬件或其组合形式 实施于服务器节点130上。在至少一些实施方案中，服务器节点130 上的负载平衡器模块132可执行三个主要角色：封装传出和解封传入 封包，对于节点130上的服务器134作出局部负荷平衡决定，和连接 发布。这些三个角色于下文简单描述，并且稍后在此文件中更详细地 描述。

分布负载平衡系统的至少一些实施方案不终止TCP连接并且不 伪造封包；经由负载平衡器节点层发送的所有封包的来源和目的地IP 地址是封包流中所涉及的端点(即，客户端160和服务器134)的实际 IP地址。代替伪造，这些实施方案将负载平衡器节点110与结构120 上的服务器节点130之间发送的所有封包例如作为UDP封包封装。 由于封包流中的从充当此流的进入节点的负载平衡器节点110到达 服务器节点130的进入封包由负载平衡器节点110来封装，封包需要 解封并且重定向至节点130上的服务器134的局部主机TCP流。节 点130上的负载平衡器模块132执行此解封。类似地，来自服务器 134的封包流的传出封包由负载平衡器模块132封装并且经由结构 120发送至充当封包流的外出节点的负载平衡器节点110。

在至少一些实施方案中，服务器节点130上的负载平衡器模块 132还作出涉及相应服务器节点130上的服务器134的负载平衡的局 部决定。具体来说，节点130上的负载平衡器模块132响应于接收新 TCP连接的请求决定是否相应服务器134接受另一个TCP流。如以 前提及，负载平衡器节点110封装发送至负载平衡器模块132的所有 封包，以使得负载平衡器模块132实际上并不接收来自客户端160的 TCP同步(SYN)封包；替代地，负载平衡器模块132接收根据封装协 议(例如，UDP)来自流量跟踪器116的连接请求消息，负载平衡器模 块132可接受或拒绝。如果负载平衡器模块132接受连接请求消息， 那么负载平衡器模块132产生前往局部主机的SYN封包。当局部主 机接受连接时，此变成操控相应客户端连接的实际TCP堆栈。

在至少一些实施方案中，为了作出关于是否应接受连接请求消息 的决定，负载平衡器模块132考察关于服务器节点130上的当前资源 消耗的一个或多个量度，并且如果存在可用于操控新连接的足够资 源，负载平衡器模块132接受连接。在至少一些实施方案中，可由负 载平衡器模块132考虑的资源量度可包括但是不限于以下中的一个 或多个：CPU利用、近期带宽消耗和所建立连接的数目。在一些实 施方案中，其他量度可代替或附加于这些量度来考虑。举例来说，在 一些实施方案中，负载平衡器模块可考虑服务器延时(即，请求在服 务器连接积压中耗费的时间量)作为量度，并且如果服务器延时高于 阈值，可拒绝连接请求。通过使用这些和/或其他量度，负载平衡器 模块132可针对相应服务器134来决定是否服务器134接受或拒绝新 封包流。在至少一些实施方案中，资源利用率(例如，N％利用)可个 别地或组合地从量度确定并且与阈值(例如，90％利用)比较。如果确 定资源利用率等于或高于阈值，或如果添加连接将比率移至高于阈 值，那么可拒绝连接请求。

在至少一些实施方案中，负载平衡器模块132可实施概率方法来 确定是否应拒绝连接请求消息。代替当如上所述资源利用等于或高于 阈值时拒绝所有连接请求，此方法可在两个或更多个不同利用水平下 以不同概率拒绝连接请求。举例来说，如果资源利用为80％，负载平 衡器模块132可以20％概率拒绝连接请求；如果资源利用为90％， 负载平衡器模块132可以25％概率拒绝连接请求；如果资源利用为 95％，负载平衡器模块132可以50％概率拒绝连接请求；并且在98％ 或以上，负载平衡器模块132可拒绝所有连接请求。

在至少一些实施方案中，每个连接请求消息可包括连接请求消息 已经由负载平衡器模块132拒绝多少次的指示。如果由负载平衡器模 块130接收的连接请求消息指示它被拒绝超过阈值次数，负载平衡器 模块130可接受连接，即使服务器节点130的性能量度指示应拒绝连 接请求也如此。

在一些情况下，有可能连接请求消息发送到达的所有负载平衡器 模块132可拒绝连接请求。在至少一些实施方案中，为了防止连接请 求消息在从负载平衡器模块132到负载平衡器模块132之间被拒收无 限的时间，可将每个连接请求消息指定存续时间。如果此存续时间到 期，流量跟踪器节点可终止请求并且通告相应客户端160当前不能为 请求提供服务。

在至少一些实施方案中，服务器节点130上的负载平衡器模块 132还执行针对负载平衡器节点110的连接发布。在至少一些实施方 案中，为了执行连接发布，定期或不定期地(例如，每秒一次)每个负 载平衡器模块132考察服务器节点130上的选路表(例如，netstat选 路表)并且将活动连接(TCP流)列表发布回到负载平衡器节点110。需 要获得关于存在给定封包流的通知的负载平衡器节点110是充当相 应封包流的进入节点和主要和次要流量跟踪器的负载平衡器节点 110。在一些实施方案中，负载平衡器模块132可使用一致哈希技术 来过滤需要获得关于服务器节点130上的活动TCP流的通知的负载 平衡器节点110的列表。举例来说，负载平衡器模块132可确定哪些 负载平衡器节点110根据一致哈希环充当给定封包流的主要和次要 流量跟踪器。在一些实施方案中，对于每个封包流，负载平衡器模块 132跟踪哪一个负载平衡器节点110最近将数据封包发送至负载平衡 器模块132，并且使用此信息确定哪些负载平衡器节点110充当封包 流的进入节点，因为仅进入节点将客户端数据转发至负载平衡器模块 132。在一些实施方案中，然后，负载平衡器模块132为它已经确定 需要获得关于封包流的通知的负载平衡器节点110中的每一个制定 消息并且将消息发送至负载平衡器节点110以通知节点110相应服务 器节点130仍然保持至客户端160的连接。此通过负载平衡器模块 132向负载平衡器节点110的连接发布可视为延长负载平衡器节点 110的租约。如果负载平衡器节点110在一段时间(例如，十秒)内没 有收到指示具体封包流的连接发布消息，那么负载平衡器节点110能 够自由不考虑相应封包流。

至负载平衡器节点的多路径路由

图4示出根据至少一些实施方案的分布负载平衡器中的路由和 封包流的方面。在至少一些实施方案中，每个进入节点(进入节点在 图4中展示为进入服务器112)例如经由边界网关协议(BGP)公布其将 一个或多个公共端点(例如，IP地址和端口)依路由传递至分布负载平 衡器的边缘路由器104的能力。在至少一些实施方案中，并非每个进 入节点经由BGP会话将自身公布至边缘路由器104，一个或多个其 他进入节点，例如两个邻近节点，可与边缘路由器104建立BGP会 话以公布进入节点，如图5示出。

常规负载平衡器通常只可服务单一公共端点。相比之下，分布负 载平衡器的实施方案使得多个负载平衡器节点110能够服务单一公 共端点。取决于路由器能力，此情形允许以下配置，其中依路由传递 至所有进入服务器112的单一公共IP地址可经由边缘路由器104来 操控整个带宽(例如，160Gbps)。在至少一些实施方案中，为了实现 此目标，边缘路由器104可利用层4每流哈希多路径路由技术，例如 等价多路径(ECMP)路由技术，来将流量分配于多个进入服务器112， 所述进入服务器各自公布相同公共IP地址。通过使用所述流的层4 来源和目的地端口作为边缘路由器104流哈希的一部分来将传入封 包分配至所有进入服务器112可总体上保持依路由传递至充当进入 服务器112的同一负载平衡器节点110的每个连接的封包以避免无序 封包。然而，应注意，在一些实施方案中，边缘路由器104可使用其 他技术来将流量分配于进入服务器112。

图4还示出两个或更多个分布负载平衡器可实施于网络100中。 两个或更多个分布负载平衡器可各自充当在多个服务器130的前面 并且各自公布不同公共IP地址的独立负载平衡器，或替代地如图4 示出，两个或更多个分布负载平衡器可各自公布相同IP地址，并且 哈希技术(例如，层4每流哈希多路径路由技术)可在边界路由器102 处使用以分割封包流以便送至边缘路由器104，所述边缘路由器进而 将封包流分配至其相应进入服务器112。

图5示出根据至少一些实施方案的使用边界网关协议(BGP)向边 缘路由器公布进入节点。在此实施例中，存在充当负载平衡器实行方 案中的进入节点110A至110D的四个负载平衡器节点。边缘路由器 104将来自客户端(未展示)的传入封包依路由传递至负载平衡器节点 110。在至少一些实施方案中，边缘路由器104可根据层4每流哈希 多路径路由技术，例如等价多路径(ECMP)路由技术来作出路由决定。

在至少一些实施方案中，经由通过进入节点110启始的边界网关 协议(BGP)技术公布会话，边缘路由器104获知当前在负载平衡器实 行方案中可用于接收客户端流量的进入节点110。每个进入节点110 可使用BGP来将自身公布至边缘路由器104。然而，BGP通常耗费 相对较长时间来收敛(三秒或更长)。在使用其中每个进入节点110经 由BGP公布自身的此技术的情况下，如果进入节点110停用，那么 边缘路由器104上的BGP会话超时，进而边缘路由器104获知失效 关闭并且将当前TCP流重新依路由传递至进入节点110可能在连网 方面耗费相当长时间(三秒或更长)。

为了避免使用BGP的收敛问题并且在节点110失效时更迅速地 恢复，在至少一些实施方案中，代替进入节点110经由BGP会话将 自身向边缘路由器104公布，负载平衡器实行方案中的至少一个其他 进入节点110负责经由BGP将进入节点110向边缘路由器104公布。 举例来说，在如图5示出的一些实施方案中，给定进入节点110中的 左和右邻近进入节点110，例如在节点110的有序列表，例如由节点 110形成的一致哈希环中的左和右近邻，可将给定进入节点110向边 缘路由器104公布。举例来说，在图5中，进入节点110A公布进入 节点110B和110D，进入节点110B公布进入节点110A和110C，进 入节点110C公布进入节点110B和110D，并且进入节点110D公布 进入节点110C和110A。进入节点110检查并传播彼此的健康状况， 如稍后在此文件中所描述。通过使用如所描述的健康检查方法，可检 测到不健康节点并且信息可在少于一秒内，例如在100毫秒(ms)内在 节点110之间传送。在确定进入节点110不健康后，公布不健康节点 的进入节点110可立即停止公布不健康节点110。在至少一些实施方 案中，进入节点110通过将BGP会话的TCP关闭或类似消息发送至 边缘路由器104来终止与边缘路由器104的BGP会话。因此，并非 需要等待由失效节点110建立的BGP会话超时来检测节点110失效， 当代表失效节点110来进行公布的其他进入节点110在检测到节点 110不健康后终止与公布节点110的边缘路由器104的BGP会话时， 边缘路由器104可发现失效节点110。负载平衡器节点失效的操控稍 后在此文件中相对于图18A和18B进一步论述。

图6是根据分布负载平衡系统的至少一些实施方案的多路径路 由方法的流程图。如900指示，负载平衡器实行方案中的进入节点 110将其邻近节点110公布至边缘路由器104。在至少一些实施方案 中，进入节点110可根据节点110的有序列表如一致哈希环来确定其 邻近节点110。在至少一些实施方案中，进入节点110使用BGP会话 将其邻近节点110公布至边缘路由器104，并且对于每个公布节点110 来说，建立与边缘路由器104的一个BGP会话。

如902指示，根据每流哈希多路径路由技术，例如等价多路径 (ECMP)路由技术，边缘路由器104将从客户端160接收的流量分布 至活动(公布)进入节点110。在至少一些实施方案中，边缘路由器104 将公共IP地址暴露至客户端160；进入节点110都将相同公共IP地 址公布至边缘路由器104。边缘路由器使用层4来源和目的地端口作 为边缘路由器104流哈希的一部分来在进入节点110之间分配传入封 包。这总体上保持依路由传递至同一进入节点110的每个连接的封 包。

如902指示，进入节点将数据流转发至目标服务器节点130。在 至少一些实施方案中，进入节点110与数据流的主要和次要流量跟踪 器节点相互作用来将数据流与目标服务器节点130进行映射。因此， 每个进入节点110可保持经由节点110的活动数据流的映射，其可用 于适当地将接收封包转发至目标服务器节点130。

元件906至910涉及检测进入节点110失效并且从中恢复。如 906指示，进入节点110可检测到进入节点110停用，例如根据如本 文描述的健康检查技术。在检测节点110停用后，其邻近节点110停 止将节点110公布至边缘路由器104。在至少一些实施方案中，此涉 及将TCP关闭发送至相应BGP会话的边缘路由器104。

如908指示，边缘路由器104，在检测到进入节点110经由关闭 BGP会话而停用后，根据每流哈希多路径路由技术将来自客户端160 的传入流量重新分布至其余进入节点110。因此，至少一些数据流可 依路由传递至不同进入节点110。

如910指示，进入节点110可在必要时恢复映射并且将数据流转 发至适当目标服务器节点。从进入节点110上的节点110失效中恢复 的方法在此文件中别处论述。作为一个实例，进入节点110，在收到 它不具有当前映射的封包后，可根据一致哈希环使用一致哈希函数来 确定数据流的流量跟踪器节点并且从流量跟踪器节点中恢复映射。

不对称的封包流

在至少一些实施方案中，为了在传出流量与传入数据的比率大于 1时有效地利用进入节点带宽和CPU使用，分布负载平衡系统将来 自服务器节点130的传出封包转发至多个外出节点，如图7示出。在 至少一些实施方案中，对于每个连接，相应服务器节点130上的负载 平衡器模块132哈希客户端端点/公共端点元组并且使用一致哈希算 法来选择负载平衡器节点110以充当相应外出封包流的外出服务器 114。然而，在一些实施方案中，其他方法和/或数据可用于选择连接 的外出服务器114。选定外出服务器114可通常但是不一定为与充当 连接的进入服务器112的负载平衡器节点110相比不同的负载平衡器 节点110。在至少一些实施方案中，除非此负载平衡器节点110/外出 服务器114失效，否则具体连接的所有外出封包转发至同一外出服务 器114以便避免无序封包。

在至少一些实施方案中，用于通过服务器节点130选择外出服务 器114的方法和数据可不同于用于由边缘路由器104执行的选择进入 服务器112的方法和数据。使用不同方法和数据可总体上导致与被选 择为连接的进入节点的负载平衡器节点110相比，不同负载平衡器节 点110被选择为给定连接的外出节点，并且对于穿过充当进入节点的 单一负载平衡器节点110的连接来说，还可导致多个负载平衡器节点 110被选择为操控传出流量的外出节点。

图7图形化示出根据至少一些实施方案的不对称封包流。已经建 立从外部网络150上的客户端160穿过进入服务器112到达服务器节 点130A、130B、130C和130D中的每一个的至少一个连接。在至少 一些实施方案中，为了选择连接的外出节点，对于每个连接，相应服 务器节点130上的负载平衡器模块132哈希客户端端点/公共端点元 组并且使用一致哈希算法来选择负载平衡器节点110以充当相应外 出封包流的外出服务器114。举例来说，服务器节点130A具有连接 的选定外出服务器114A，并且服务器节点114B具有用于一个连接的 选定外出服务器114A和用于另一个连接的外出服务器130B。然而， 在一些实施方案中，其他方法和/或数据可用于选择连接的外出节点。

在不丢弃客户端连接的情况下从负载平衡器节点失效中恢复

虽然负载平衡器节点110可使用一致哈希来确定哪一个服务器 节点130应接收客户端流量，但是归因于一些连接的长寿命，如果新 服务器节点130加入一致哈希成员关系并且随后出现进入负载平衡 器节点110失效，那么此方法可能无法保持现有流量。在此情况下， 接管来自失效节点110的流量的负载平衡器节点110可能不能够确定 选定原始映射，因为服务器130的一致哈希环具有不同成员关系。因 此，在至少一些实施方案中，分布哈希表(DHT)技术可由负载平衡器 节点110用于选择连接的服务器节点130并且将封包依路由传递至选 定服务器节点130。一旦服务器节点130已经根据DHT选定来接收 具体连接，并且假定服务器节点130保持健康并且负载平衡器模块 132服务器节点130继续通过定期地将此活动连接的状态传输至 DHT(例如，经由连接发布)来延长租约，DHT保持映射直到连接完成 为止。进入节点110失效影响封包从边缘路由器104至其余负载平衡 器节点110的分配，导致负载平衡器节点110接收来自不同组客户端 连接的流量。然而，因为DHT跟踪所有活动连接，所以负载平衡器 节点110可查询DHT以获得任何活动映射的租约。因此，所有负载 平衡器节点110将流量传递至正确的服务器节点130，由此甚至在进 入负载平衡器节点110失效时防止活动客户端连接失效。

分布负载平衡系统中的封包流

图8示出根据至少一些实施方案的分布负载平衡系统中的封包 流。注意图8中的具有箭头的实线代表TCP封包，而具有箭头的虚 线代表UDP封包。在图8中，进入服务器112经由边缘路由器104 接收来自一个或多个客户端160的TCP封包。在接收TCP封包后， 进入服务器112确定是否其具有TCP封包流与服务器节点130的映 射。如果进入服务器112具有TCP封包流的映射，那么服务器112 封装TCP封包(例如根据UDP)并且发送封装封包至目标服务器节点 130。如果进入服务器112不具有TCP封包流的映射，那么进入服务 器112可将包括从TCP封包提取的关于TCP封包流的信息的UDP 消息发送至主要流量跟踪器116A以建立至服务器节点130的连接且 /或获得TCP封包流的映射。图9A和9B和图10A至10G示出在客 户端160与服务器节点130之间建立连接的方法。服务器节点130上 的负载平衡器模块132随机选择负载平衡器节点110充当服务器节点 130上的TCP连接的外出服务器114并且经由外出服务器114将UDP 封装TCP响应封包发送至客户端160。

图9A和9B提供根据至少一些实施方案的在分布负载平衡系统 中建立连接时的封包流的流程图。如图9A的200指示，进入服务器 112经由边缘路由器104接收来自客户端160的TCP封包。在202 处，如果进入服务器112具有TCP流与服务器节点130的映射，那 么进入服务器112封装并发送TCP封包至相应服务器节点130，如 204指示。注意进入服务器112可连续接收并处理来自一个、两个或 更多个客户端160的一个、两个或更多个TCP流的封包。

在202处，如果进入服务器112不具有TCP流的映射，封包可 为来自客户端160的TCP同步(SYN)封包。如206指示，在接收SYN 封包后，进入服务器112从SYN封包提取数据并且将数据转发至主 要流量跟踪器116A，例如在UDP消息中。在至少一些实施方案中， 进入服务器112可根据一致哈希函数来确定TCP流的主要流量跟踪 器116A和/或次要流量跟踪器116B。在208处，主要流量跟踪器116A 将数据存储于例如哈希表中，产生TCP连接的服务器节点130侧的 初始TCP序号，并且将数据和TCP序号转发至次要流量跟踪器116B。 在210处，次要流量跟踪器116B也可存储数据，并且编制并发送 SYN/ACK封包至客户端160，SYN/ACK封包含有至少TCP序号。

如212指示，进入服务器112经由边缘路由器104接收来自客户 端160的TCP确认(ACK)封包。进入服务器112在此时间不具有TCP 流与服务器130节点的映射，因此在214处进入服务器112将包括从 ACK封包提取的数据的消息发送至主要流量跟踪器116A。如216指 示，在接收消息后，主要流量跟踪器116A根据存储数据来证实TCP 流，并且证实来自ACK封包的确认序号(+1)匹配在SYN/ACK中发 送的值。然后，主要流量跟踪器116A选择服务器节点130来接收TCP 流，并且将含有数据、TCP序号和选定服务器节点130上的局部负荷 平衡器模块132的IP地址的消息发送至次要流量跟踪器116B。如218 指示，次要流量跟踪器116B也证实数据和TCP序号，编制SYN消 息，并且将编制SYN消息发送至选定服务器节点130上的局部负荷 平衡器模块132。方法在图9B的元件220处继续。

如图9B的220指示，响应于编制SYN消息，负载平衡器模块 132可检查服务器节点130的一个或多个量度以确定是否服务器节点 130可接受连接。在222处，如果负载平衡器模块132确定服务器节 点130当前不能接受连接，那么在224处负载平衡器模块132向次要 流量跟踪器116B发讯。次要流量跟踪器116B可删除它以前存储的 关于此流的信息。在226处，次要流量跟踪器116B向主要流量跟踪 器116A发讯。然后，主要流量跟踪器116A可选择新目标服务器节 点130并且向次要流量跟踪器116B发讯，如图9A的216指示。

在222处，如果负载平衡器模块132确定服务器节点130可接受 连接，然后如图9B的228指示，局部负荷平衡器模块132从所编制 SYN来构建TCPSYN封包并且将TCPSYN封包发送至服务器节点 130上的服务器134。TCPSYN封包的来源IP地址用客户端160的 实际IP地址填充以使得服务器134相信它已经接收至客户端160的 直接TCP连接。负载平衡器模块132将关于TCP流的相关细节存储 于例如局部哈希表中。如230指示，服务器134用负载平衡器模块 132截取的SYN/ACK封包来作出响应。如232指示，负载平衡器模 块132然后将包括连接信息的消息发送至次要流量跟踪器116B以指 示已经接受连接。在接收此消息后，在234处，次要流量跟踪器116B 记录与服务器134的映射，并且将类似消息发送至主要流量跟踪器 116A，其也记录映射信息。如236指示，主要流量跟踪器116A然后 将映射消息转发至进入服务器112。进入服务器112现在具有TCP流 从客户端160至服务器130的映射。

在238处，进入服务器112封装数据流的任何缓冲数据封包并且 将其转发至服务器节点130上的局部负荷平衡器模块132。将由进入 服务器112接收的来自客户端160的数据流的额外传入封包封装并且 直接转发至负载平衡器模块132，其将封包解封并且发送数据封包至 服务器134。

在240处，负载平衡器模块132随机选择数据流的外出服务器 114。来自服务器134的后续外出TCP封包由负载平衡器模块132截 取，根据UDP封装，并且转发至任意选定外出服务器114。外出服 务器114将传出封包解封并且将TCP封包发送至客户端160。

如以上提及，在202处，如果进入服务器112不具有所接收封包 的TCP流的映射，那么封包可为来自客户端160的TCP同步(SYN) 封包。然而，封包可不为TCPSYN封包。举例来说，如果负载平衡 器节点110成员关系由于负载平衡器节点110增加或失效而变化，边 缘路由器104可开始将一个或多个TCP流的封包依路由传递至进入 服务器112不具有映射的进入服务器112。在至少一些实施方案中， 在接收进入服务器112不具有映射的这类封包后，进入服务器112可 根据一致哈希环、使用一致哈希函数来确定TCP流的主要流量跟踪 器116A和/或次要流量跟踪器116B并且向主要流量跟踪器116A或 次要流量跟踪器116B发讯以请求映射。在从流量跟踪器116接收TCP 流的映射后，进入服务器112可存储映射并且开始封装TCP流的TCP 封包并且将其转发至正确目的地服务器节点130。

负载平衡器节点细节

在至少一些实施方案中，负载平衡器节点110各自具有三个角 色：

·进入-在客户端连接中接收来自客户端160的所有传入封包， 如果映射已知，那么将封包依路由传递至服务器节点130，或如果映 射未知，那么向流量跟踪器发讯。来自进入节点的传出封包由进入节 点封装(例如，根据UDP)。

·流量跟踪-跟踪连接状态(例如已经分配哪一个服务器节点130/ 服务器134来为每个客户端连接提供服务)。流量跟踪器还参与在客 户端160与服务器134之间建立连接。

·外出-解封从服务器134接收的外出封包并且将其转发至客户 端160。

在至少一些实施方案中，在进入角色中，负载平衡器节点110负 责在客户端->服务器映射已知时将封包转发至服务器134，或在映射 未知时将请求转发至流量跟踪器。在至少一些实施方案中，充当具体 客户端连接/数据流的进入节点的负载平衡器节点110还可充当客户 端连接的主要流量跟踪器或次要流量跟踪器，但是不可同时充当这两 种角色。

在至少一些实施方案中，在流量跟踪器角色中，负载平衡器节点 110负责保持仍然建立的连接的状态，以及保持所建立连接的客户端 ->服务器映射。两种流量跟踪器涉及每个个别客户端连接，被称为主 要流量跟踪器和次要流量跟踪器。在至少一些实施方案中，与客户端 连接相关联的流量跟踪器可使用一致哈希算法来确定。流量跟踪器还 执行负载平衡功能，包括但不限于对于每个新客户端连接，伪随机选 择服务器节点130。注意如果选择服务器节点130上的局部负荷平衡 器模块132确定服务器134不能操控连接，那么它可拒绝连接请求。 如果此情况发生，那么流量跟踪器可选择另一个服务器节点130并且 将连接请求发送至其他服务器节点130。在至少一些实施方案中，给 定连接的主要流量跟踪器角色和次要流量跟踪器角色由不同负载平 衡器节点110执行。

在至少一些实施方案中，在外出角色中，负载平衡器节点110是 无状态的并且将从服务器节点130接收的传入封包解封，执行一些验 证，并且将外出TCP封包转发至相应客户端160。在至少一些实施方 案中，服务器节点130上的局部负荷平衡器模块132可任意选择给定 连接的负载平衡器节点110。

负载平衡器节点一致哈希环形拓扑

在至少一些实施方案中，负载平衡器节点110基于输入密钥空间 (客户端端点、公共端点)的一致哈希来形成环形拓扑。输入密钥空间 可在可利用流量跟踪器节点之间划分，并且每个流量跟踪器节点可负 责应答对应于其密钥空间的查询。在至少一些实施方案中，数据可基 于一致哈希环中的继承者来复制至主要和次要流量跟踪器节点(例 如，次要流量跟踪器节点是主要流量跟踪器节点或一致哈希环中的下 一个节点的继承节点)。如果流量跟踪器节点出于某种原因停用，那 么一致哈希环中的下一个负载平衡器节点获得失效节点的密钥空间。 当新流量跟踪器节点加入时，节点记录其端点(例如，通过如图1示 出的配置服务122)以使得其他负载平衡器节点可获知负载平衡器实 行方案以及由此一致哈希环中的配置变化。一致哈希环中的流量跟踪 器的添加和失效的操控参照图11A至11D来更详细地论述。

进入节点<->流量跟踪器节点通信

在至少一些实施方案中，充当进入节点的负载平衡器节点110可 从配置服务122获知充当流量跟踪器节点的负载平衡器节点110。进 入节点可针对负载平衡器实行方案以及由此一致哈希环中的成员关 系变化来监测配置服务122。当进入节点从客户端160接收进入节点 不具有映射的封包，进入节点可使用一致哈希函数来确定哪一个流量 跟踪器节点应为封包提供服务。在至少一些实施方案中，哈希函数的 输入是封包的(客户端端点、公共端点)对。在至少一些实施方案中， 进入节点和流量跟踪器节点使用UDP消息来通信。

当主要流量跟踪器节点从进入节点接收新封包流的消息时，主要 流量跟踪器节点随机确定TCP序号并且将另一个消息转发至次要流 量跟踪器节点。次要流量跟踪器节点产生客户端的TCPSYN/ACK消 息。两种流量跟踪器记忆客户端连接端点对和TCP序号，并且保持 此信息直到存储器压力或期满导致状态被清除为止。

当主要流量跟踪器节点从进入节点接收TCPACK封包已经被接 收的消息时，主要流量跟踪器节点验证所确认的TCP序号匹配在 SYN/ACK封包中发送的存储值，选择服务器节点130来为请求提供 服务，并且将消息转发至次要流量跟踪器节点。次要流量跟踪器节点 将消息发送至选定服务器节点130上的负载平衡器模块132以启始与 服务器节点130上的TCP堆栈的实际TCP连接，然后等待来自服务 器节点130的确认响应。

当次要流量跟踪器节点接收来自服务器节点130上的负载平衡 器模块132的连接确认时，触发经由主要流量跟踪器至进入节点的反 向消息流，其将关于相关联服务器节点130的信息存储于两个节点 中。从此点向前，在进入节点处接收的额外TCP封包直接转发至服 务器节点130上的负载平衡器模块132。

负载平衡器模块<->负载平衡器节点通信

在至少一些实施方案中，每个负载平衡器模块132通过配置服务 122来记录其端点并且针对负载平衡器节点层中的成员关系变化来连 续监测配置服务122。以下描述根据至少一些实施方案的负载平衡器 模块132的功能：

·连接发布-定期(例如，每秒一次)或不定期地将相应服务器节点 130上的一组活动连接(客户端端点、公共端点)发布至负责那些连接 的主要和次要流量跟踪器节点，以及最近向那些连接的负载平衡器模 块132发送封包的进入节点。连接发布功能更新负责负载平衡器节点 110的连接状态的租约。

·监测负载平衡器层中的成员关系变化。如果成员关系变化，负 载平衡器模块132可使用此变化信息来立即将活动连接发送至现在 负责连接的负载平衡器节点。

分布负载平衡系统中的封包流-细节

分布负载平衡系统可包括多个负载平衡器节点110。在至少一些 实施方案中，分布负载平衡系统中的每个负载平衡器节点110可以客 户端160与服务器134的连接的流量跟踪器节点、外出节点和进入节 点的角色来提供服务。分布负载平衡系统还可包括每个服务器节点 130上的负载平衡器模块132。

图10A至10G示出根据至少一些实施方案的分布负载平衡系统 中的封包流。在图10A至10G中，在负载平衡器节点110之间交换 的封包和在负载平衡器节点110与服务器节点130之间交换的封包是 UDP消息或UDP封装客户端TCP封包。在至少一些实施方案中，客 户端TCP封包只在网络100上以解封形式存在于负载平衡器节点110 的北侧，在前往和来自边界路由器102的运送过程中(参见图1)。注 意图10A-10G中的具有箭头的实线代表TCP封包，而具有箭头的虚 线代表UDP封包。

在至少一些实施方案中，万一单一负载平衡器节点110失效，分 布负载平衡系统可试图保持所建立的连接。在至少一些实施方案中， 此目标可通过在主要流量跟踪器节点和次要流量跟踪器节点中复制 连接细节来实现以使得如果这些节点失效，连接的客户端->服务器映 射可由其余流量跟踪器节点来恢复。在至少一些实施方案中，万一节 点失效，可发生一些封包损失；然而，客户/服务器TCP封包重新传 输可恢复损失的封包。

来自客户端的每个TCP连接可被称为TCP流，并且通过由以下 组成的4元组来唯一地识别：客户端IP地址、客户端端口、服务器(公 共)IP地址和服务器端口。此识别符可缩写为CP或CcPp，其指示客 户端和公共端点对。由于来自上游边缘路由器104的哈希等价多路径 (ECMP)流量分布，与任何给定TCP流(或CP对)相关联的封包可出现 于作为进入服务器112操作的任何负载平衡器节点110上。然而，TCP 流的封包可总体上继续到达同一负载平衡器节点110，除非存在导致 TCP流重定向的链路或负载平衡器节点110失效。从上游路由器104 接收TCP流封包的负载平衡器节点110被称为TCP流的进入节点。

在至少一些实施方案中，使用一致哈希以使得当封包到达充当 TCP流的进入节点的负载平衡器节点110时，进入节点可确定哪一个 负载平衡器节点110含有TCP流的状态(即，流量跟踪器节点)。CP 对可通过进入节点哈希成一致哈希环来确定哪一个负载平衡器节点 110负责保持关于TCP流的状态。此节点充当TCP流的主要流量跟 踪器。一致哈希环中的后续节点充当TCP流的次要流量跟踪器。

在至少一些实施方案中，所有负载平衡器节点110可充当进入节 点、主要流量跟踪器节点和次要流量跟踪器节点。取决于TCP流的 一致哈希结果，充当TCP流的进入节点的负载平衡器节点110还可 充当TCP流的主要或次要流量跟踪器节点。然而，在至少一些实施 方案中，不同物理负载平衡器节点110执行TCP流的主要和次要流 量跟踪器角色。

建立连接

参看图10A，来自客户端160的新连接可由客户端TCP同步(SYN) 封包触发。在接收SYN封包后，负载平衡器节点110实际上不建立 与服务器节点130的连接，也不立即选择接收连接的服务器节点130。 替代地，负载平衡器节点110存储来自客户端SYN封包的相关数据， 并且代表仍待选择的服务器节点130来产生SYN/ACK封包。参看图 10C，一旦客户端160在TCP三向握手中以第一ACK封包作出响应， 负载平衡器节点110选择服务器节点130，产生此服务器节点130的 等效SYN封包，并且试图建立与服务器节点130的实际TCP连接。

再次参看图10A，在充当TCP流的进入服务器112的负载平衡 器节点110处接收客户端SYN封包后，进入服务器112从SYN封包 提取数据场并且将数据转发至TCP流的主要流量跟踪器116A。主要 流量跟踪器116A将数据存储于例如哈希表中，产生初始TCP序号(用 于TCP连接的服务器侧)，并且将相同数据转发至次要流量跟踪器 116B。次要流量跟踪器116B为客户端160编制含有服务器TCP序号 的SYN/ACK封包。

在图10A中，进入服务器112、主要流量跟踪器116A，和次要 流量跟踪器116B角色各自由不同负载平衡器节点110执行。然而， 在一些情况下，充当TCP流的进入服务器112的负载平衡器节点110 可为充当TCP流的主要流量跟踪器116A或次要流量跟踪器116B的 同一节点110(但是并非同时充当这两种角色的节点)。封包流的进入 服务器112可在与此流的流量跟踪器116相同节点110上的原因是边 缘路由器104根据每流哈希多路径路由技术(例如，ECMP路由技术) 来伪随机选择此流的进入服务器112，同时封包流的流量跟踪器116 根据应用于封包流地址信息的一致哈希函数、在一致哈希环上确定。 如果封包流的进入服务器112在与封包流的流量跟踪器116相同节点 110上，SYN封包的数据可只从实施进入服务器112的节点110转发 到其他流量跟踪器116节点110。举例来说，在图10B中，主要流量 跟踪器116A在与TCP流的进入服务器112相同负载平衡器节点110A 上，而次要流量跟踪器116B在不同负载平衡器节点110B上，因而 来自SYN封包的数据从节点110A(经过流量跟踪器116A)转发至负载 平衡器节点110B上的次要流量跟踪器116B。

参看图10C，当非SYN封包到达进入服务器112时，进入服务 器112知道或不知道将封包转发至哪一个服务器节点130。到达TCP 流的进入服务器112的第一非SYN封包应TCP三向握手中的第一 TCP确认(ACK)封包(或可能后续数据封包)，其中TCP确认数域匹配 在图10A中的SYN/ACK封包中发送的服务器序号(+1)。当进入服务 器112接收其不具有服务器映射的非SYN封包时，它将消息转发至 TCP流的主要流量跟踪器116A，所述消息包括来自ACK封包的信息 如序号，或替代地含有ACK封包本身。在至少一些情况下，主要流 量跟踪器116A记忆TCP流的存储数据并且证实确认序号(+1)匹配在 SYN/ACK封包中发送至客户端160的值。主要流量跟踪器然后选择 TCP流的服务器节点130并且将含有TCP流的以前存储数据、服务 器序号和选定服务器节点130上的负载平衡器模块132的IP地址的 另一个消息转发至次要流量跟踪器116B。次要流量跟踪器116B证实 服务器序号，记录信息，并且将编制SYN消息发送至选定服务器节 点130上的负载平衡器模块132。TCP流的CP端点对现在映射至负 载平衡器模块132/服务器节点130。服务器节点130上的负载平衡器 模块132负责在它接收来自次要流量跟踪器116B的编制SYN消息 时，产生服务器节点130上的服务器134的合法TCPSYN封包。在 产生SYN封包中，来源IP地址用客户端160的实际IP地址填充以 使得服务器134相信它已经接收来自客户端160的直接TCP连接请 求。负载平衡器模块132将关于TCP流的相关细节存储在例如局部 哈希表中，并且将TCPSYN封包发送至服务器134(例如，将SYN封 包注入服务器134的Linux内核中)。

在图10C中，进入服务器112、主要流量跟踪器116A和次要流 量跟踪器116B角色各自由不同负载平衡器节点110执行。然而，在 一些情况下，充当TCP流的进入服务器112的负载平衡器节点110 是充当TCP流的主要流量跟踪器116A或次要流量跟踪器116B的相 同节点110(但是并非同时充当这两种角色的节点)。举例来说，在图 10D中，次要流量跟踪器116B在与TCP流的进入服务器112相同负 载平衡器节点110A上，同时主要流量跟踪器116A在不同负载平衡 器节点110B上。

参看图10E，服务器134(例如，Linux内核)以负载平衡器模块 132另外截取的SYN/ACK封包作出响应。SYN/ACK封包可含有与 最初在来自次要流量跟踪器116B的所产生SYN/ACK中递送至客户 端160的序号不同的TCP序号(参见图10A)。负载平衡器模块132负 责将序号δ施加至传入和传出封包。SYN/ACK封包服务器134还触 发从负载平衡器模块132回到次要流量跟踪器116B的消息(例如， UDP消息)以指示选定服务器节点130/负载平衡器模块132/服务器 134的连接成功。在接收此消息后，次要流量跟踪器116A可记录如 提交的客户端160与服务器134之间的客户端和公共端点对(CP)映 射，并且将类似消息发送至主要流量跟踪器116A，其也记录CP映射。 然后，主要流量跟踪器116A可将CP映射消息转发至进入服务器112， 其导致进入服务器112将此连接的任何缓冲数据封包作为封装数据 封包转发至服务器节点130上的局部负荷平衡器模块132。

参看图10F，此连接的CP映射为进入服务器已知，因此由此连 接的进入服务器112接收的传入TCP封包可加以封装(例如，根据 UDP)并且作为封装数据封包直接转发至服务器节点130上的局部负 荷平衡器模块132。负载平衡器模块132将数据封包解封并且将TCP 封包发送至服务器节点130上的服务器134，例如通过将TCP封包注 入内核的TCP堆栈。来自服务器134的传出封包由服务器节点130 上的负载平衡器模块132截取，封装(例如，根据UDP)，并且转发至 负载平衡器模块132随机选择为此连接的外出服务器114的任意负载 平衡器节点110。外出服务器114将封包解封并且将解封封包发送至 客户端116。选定负载平衡器节点110的外出功能是无状态的，因此 万一充当外出服务器的负载平衡器节点110失效，不同负载平衡器节 点110可选择为此连接的外出服务器114。然而，在连接的持续时间 内总体上同一负载平衡器节点110用作外出服务器114以减少或消除 外出封包的重新排序。

参看图10G，在至少一些实施方案中，如果由主要流量跟踪器 116A选择的服务器节点130A上的负载平衡器模块132A(参见图10C) 确定它超载，它可选择拒绝从次要流量跟踪器116B接收的编制SYN 消息(参见图10C)。在至少一些实施方案中，编制SYN消息包括存续 时间(TTL)值或允许最大拒绝数的计数器。在至少一些实施方案中， 如果此TTL值达到零，那么负载平衡器模块132A可接受连接或丢弃 连接以去除负载。如果负载平衡器模块132A决定拒绝连接，那么它 将TTL值递减并且将拒绝消息发送至次要流量跟踪器116B。次要流 量跟踪器116B重新设定CP映射并且将释放消息发送至主要流量跟 踪器116A以执行相同操作。主要流量跟踪器116A选择另一个服务 器节点130B上的新负载平衡器模块132B并且将新目标消息发送回 到次要流量跟踪器116B，其将新编制SYN消息发送至新选择负载平 衡器模块132B。注意封包丢弃可导致此序列未能完成；然而，从客 户端160重新传输可再次在主要流量跟踪器116A处触发负载平衡器 模块选择过程，如果所述主要流量跟踪器未获知编制SYN封包的以 前拒绝，那么它可能但是不一定选择同一负载平衡器模块132用于此 连接。

在至少一些实施方案中，TTL计数器可用于防止连续发送连接请 求至服务器节点130，此情况可例如在所有服务器节点130占用时发 生。在至少一些实施方案中，每当负载平衡器模块132代表相应服务 器节点130拒绝连接请求时，负载平衡器模块132将TTL计数器递 减。流量跟踪器节点116可监测TTL计数器并且，只要TTL计数器 不为零(或高于某一指定阈值)，可选择另一个服务器节点130并且再 次尝试。如果TTL计数器达到零(或达到指定阈值)，那么将连接请求 丢弃并且流量跟踪器节点116不进一步试图将连接请求发送至此连 接的服务器节点130中的选定一个。在至少一些实施方案中，错误消 息可发送至相应客户端160。

在至少一些实施方案中，分布负载平衡器系统支持多个公共IP 地址。因此，客户端160可启始从同一客户端端口编号至两个不同公 共IP地址的两个TCP连接。从客户端160的观点来看，这些TCP连 接是不同的，但是在内部分布负载平衡器可将连接映射至同一服务器 节点130，从而产生冲突。在至少一些实施方案中，为了检测和操控 可能冲突，负载平衡器模块132，在如图10C和10D示出接收来自次 要流量跟踪器116B的编制SYN封包后，可将地址信息与其活动连接 比较并且，如果此连接导致冲突，就拒绝连接请求，如图10G示出。

操控负载平衡器节点失效和添加

在许多常规负载平衡器中，万一负载平衡器失效，一些或所有现 有连接丢失。在至少一些实施方案中，万一单一负载平衡器节点110 失效，分布负载平衡系统可保持至少一些建立连接以使得客户端和服 务器可继续经由连接交换封包直到连接正常地完成为止。另外，分布 负载平衡系统可继续为在失效发生时在建立过程中的连接提供服务。

在分布负载平衡系统的至少一些实施方案中，可实施失效恢复协 议，其可在万一单一负载平衡器节点110失效时恢复现有客户端连 接。然而，多个负载平衡器节点110失效可导致丢失客户端连接。在 至少一些实施方案中，客户端160与服务器134之间的TCP重新传 输可用作负载平衡器节点110失效之后的恢复手段。

除了潜在负载平衡器节点110失效以外，新负载平衡器节点110 可添加至分布负载平衡器系统。这些新节点110可添加至负载平衡器 层并且由此添加至一致哈希环，并且必要时，关于现有客户端连接的 负载平衡器节点110角色可根据变化来调整。

操控流量跟踪器节点失效和添加

在至少一些实施方案中，当每个连接建立时(参见，例如，图10A 至10G)，连接状态信息经由被称为主要和次要流量跟踪器的两个负 载平衡器节点110传递，其可使用例如利用(客户端IP：端口，公共IP： 端口)元组作为哈希函数输入的一致哈希算法来确定。万一单一负载 平衡器节点110失效，幸存负载平衡器节点110中的至少一个可继续 经由一致哈希函数来映射并且可含有将封包引导至针对连接的选定 服务器节点130的针对连接的必要状态信息。另外，在将负载平衡器 节点110添加至一致哈希环的情况下，可为适当流量跟踪器刷新连接 的状态信息。

图11A至11D示出根据至少一些实施方案的影响负载平衡器节 点一致哈希环中的成员关系的事件的操控。这些事件可包括但不限于 添加新的主要流量跟踪器节点、添加新的次要流量跟踪器节点、主要 流量跟踪器节点失效，和次要流量跟踪器节点失效。

图11A示出将新的主要流量跟踪器节点添加至一致哈希环的操 控。图11A的顶端行示出流量跟踪器116A为一个或多个客户端连接 的主要流量跟踪器并且流量跟踪器节点116B为相同连接的次要流量 跟踪器。在图11A的底端行中，新流量跟踪器节点116C已经添加， 并且变成客户端连接的主要流量跟踪器。以前为主要流量跟踪器的流 量跟踪器节点116A变成次要流量跟踪器，而以前为次要流量跟踪器 的流量跟踪器节点116B变成一致哈希环中的下一个流量跟踪器。由 流量跟踪器116A和116B保持的客户端连接的状态信息可提供至新 的主要流量跟踪器116C。另外，在次要流量跟踪器角色中，流量跟 踪器116B可能“忘记”其以前跟踪的连接。

图11B示出将新的次要流量跟踪器节点添加至一致哈希环的操 控。图11B的顶端行示出流量跟踪器116A为一个或多个客户端连接 的主要流量跟踪器并且流量跟踪器节点116B为相同连接的次要流量 跟踪器。在图11B的底端行中，新流量跟踪器节点116C已经添加， 并且变成客户端连接的次要流量跟踪器。流量跟踪器节点116A保持 为连接的主要流量跟踪器，而以前为次要流量跟踪器的流量跟踪器节 点116B变成一致哈希环中的下一个流量跟踪器。由流量跟踪器116A 和116B保持的客户端连接的状态信息可提供至新的次要流量跟踪器 116C。另外，在次要流量跟踪器角色中，流量跟踪器116B可能“忘 记”其以前跟踪的连接。

图11C示出一致哈希环中的主要流量跟踪器节点失效的操控。图 11C的顶端行示出流量跟踪器116A为一个或多个客户端连接的主要 流量跟踪器，流量跟踪器节点116B为相同连接的次要流量跟踪器， 并且流量跟踪器节点116C为一致哈希环中的下一个流量跟踪器。在 图11C的底端行中，主要流量跟踪器节点116A已经失效。流量跟踪 器节点116B变成连接的主要流量跟踪器，而流量跟踪器节点116C 变成连接的次要流量跟踪器。客户端连接的状态信息由流量跟踪器 116B保持并且可提供至新的次要流量跟踪器116C。

图11D示出一致哈希环中的次要流量跟踪器节点失效的操控。 图11D的顶端行示出流量跟踪器116A为一个或多个客户端连接的主 要流量跟踪器，流量跟踪器节点116B为相同连接的次要流量跟踪器， 并且流量跟踪器节点116C为一致哈希环中的下一个流量跟踪器。在 图11D的底端行中，次要流量跟踪器节点116B已经失效。流量跟踪 器节点116A保持为连接的主要流量跟踪器，而流量跟踪器节点116C 变成连接的次要流量跟踪器。客户端连接的状态信息由流量跟踪器 116B保持并且可提供至新的次要流量跟踪器116C。

在至少一些实施方案中，服务器节点130上的负载平衡器模块 132执行针对负载平衡器节点110的连接发布。在至少一些实施方案 中，连接发布定期(例如，每秒一次)或不定期地将来自服务器节点130 的当前连接状态信息推送至充当流量跟踪器节点和进入节点的负载 平衡器节点110，其用于刷新或恢复连接的主要和次要流量跟踪器节 点的连接映射。在至少一些实施方案中，负载平衡器模块132可检测 流量跟踪器成员关系变化，例如如图11A至11D示出。作为响应， 负载平衡器模块132可执行连接发布以将连接的状态信息填充于主 要和次要流量跟踪器节点中，当成员关系改变时，所述连接状态信息 可能改变。注意连接发布可允许万一多个负载平衡器节点失效时恢复 至少一些所建立连接。

失效相关消息流

在至少一些实施方案中，主要与次要流量跟踪器节点之间的协议 可包括校正或同步功能。举例来说，参看图11A，当新的主要流量跟 踪器节点116C加入一致哈希环时，新的节点116C可为一定数目的 连接(～1/N)要求一致哈希密钥空间并且开始从边缘路由器104接收与 这些连接相关的流量。然而，新的主要流量跟踪器节点116C不具有 针对这些连接存储的任何状态，因此它可对于每个封包操作如同它是 从客户端160接收的第一封包。主要流量跟踪器负责响应于SYN封 包产生服务器TCP序号(参见，例如，图10A)并且响应于来自客户端 160的第一ACK封包选择服务器节点130(参见，例如，图1)，并且 这些产生值可与由以前主要流量跟踪器选择的值不一致(图11A中的 流量跟踪器节点116A)。然而，在至少一些实施方案中一致哈希算法 将以前主要流量跟踪器(图11A中的流量跟踪器节点116A)指定为次 要流量跟踪器角色，并且此流量跟踪器仍然保留连接的以前存储状 态。因此，在至少一些实施方案中，在次要流量跟踪器(图11A中的 流量跟踪器节点116A)检测从主要流量跟踪器116C接收的信息不符 合时，它可将更新消息发送回到主要流量跟踪器116C以使充当连接 的流量跟踪器的两个负载平衡器节点110同步。相似方法可用于在一 致哈希环成员关系的其他变化之后使流量跟踪器同步。

负载平衡器模块细节

在至少一些实施方案中，负载平衡器模块132是分布负载平衡器 系统的驻留于每个服务器节点130中的部件。负载平衡器节点132的 角色包括但不限于将从负载平衡器节点110接收的封包解封并且将 解封封包发送至服务器节点130上的服务器134，并且将来自服务器 134的传出封包封装并将封装封包发送至负载平衡器节点110。

在至少一些实施方案中，从充当进入服务器112的负载平衡器节 点110至服务器节点130上的负载平衡器模块132的传入封包是封装 实际客户端数据封包的无状态协议(例如，UDP)封包。每个封装客户 端数据封包具有相应客户端160的原始客户端IP：端口作为源地址以 及服务器134公共IP：端口作为目的地址。负载平衡器模块132从客 户端数据封包除去封装并且将封包发送至服务器节点130上的相应 服务器134，例如通过将封包重定向至局部主机TCP流。

在至少一些实施方案中，从服务器134至充当外出服务器114的 负载平衡器节点110的传出封包是封装传出IP封包的无状态协议(例 如，UDP)封包。负载平衡器模块132封装传出IP封包并且经由结构 120将封装封包发送至外出服务器114。每个封装传出IP封包具有服 务器134公共IP：端口作为源地址以及相应客户端160的客户端IP： 端口作为目的地址。

负载平衡器模块功能

在至少一些实施方案中，服务器节点130上的负载平衡器模块 132的功能可包括以下一个或多个但是不限于：

·终止来自负载平衡器节点110，例如来自操控至客户端160的 连接的进入服务器112的UDP隧道。这包括从进入服务器112接收 的传入客户端数据封包剥离UDP封装。

·选择外出服务器114来接收连接的传出流量。

·截取至相应服务器134的连接上的传出IP封包，将连接的传 出IP封包封装，并且将封装封包发送至外出服务器114。

·改编传入和传出封包中的序号以使得此序号与在流量跟踪器 节点116将SYN/ACK发送至客户端160时由流量跟踪器节点116产 生的序号对准。

·作出是否接受或拒绝相应服务器134的连接的决定，例如基于 指示相应服务器134的当前负载的一个或多个量度。

·检测并拒绝从同一客户端IP：端口地址至相应服务器134的连 接以在存在此客户端IP：端口地址的活动连接时避免冲突。

·连接跟踪和连接发布。

负载平衡器模块配置信息

在至少一些实施方案中，每个负载平衡器模块132可针对其配置 来获得并局部存储以下组信息中的一个或多个但是不限于：一组负载 平衡器节点110端点；其服务的一组有效公共IP地址；和相应服务 器134接受传入连接的端口编号。在至少一些实施方案中，此信息可 通过访问或查询分布负载平衡器系统的配置服务122部件来获取或 更新，如图1示出。获得信息的其他方法可在一些实施方案中使用。

负载平衡器模块封包操控

以下描述根据至少一些实施方案的进入流量和外出流量的负载 平衡器模块132操作。在至少一些实施方案中，在进入数据封包由负 载平衡器模块132接收时，数据封包从UDP封包解封，并且解封TCP 封包中的目的地址首先针对一组配置有效公共IP地址来验证。如果 没有匹配，将封包丢弃或忽略。在至少一些实施方案中，负载平衡器 模块132可通过常数δ来调整TCP报头中的序号以使得此序号匹配 由将SYN/ACK封包发送至客户端160的流量跟踪器节点116产生的 随机选择序号。负载平衡器模块132将从[客户端：公共]端点到[客户 端：服务器]端点的映射记录为内部状态。

在至少一些实施方案中，对于来自服务器134的外出TCP封包， 负载平衡器模块132首先检查其内部状态以确定是否封包用于负载 平衡器模块所管理的活动连接。如果不是用于此活动连接，负载平衡 器模块132仅将封包传递通过。如果是用于此活动连接，负载平衡器 模块132将传出TCP封包封装，例如根据UDP，并且将封装封包转 发至选择为此连接的外出服务器114的负载平衡器节点110。在至少 一些实施方案中，负载平衡器模块134可通过常数δ来调整传出TCP 封包中的TCP序号以使得其与由将SYN/ACK封包发送至客户端160 的流量跟踪器节点116产生的序号对准。

连接跟踪

在至少一些实施方案中，每个服务器节点130上的负载平衡器模 块132管理哈希表，其含有至相应服务器134的每个活动客户端连接 的连接细节。在至少一些实施方案中，哈希表的密钥是(客户端Ip：端 口，公共Ip：端口)元组。在至少一些实施方案中，每个客户端连接的 连接状态可包括以下一个或多个但是不限于：

·客户端IP：端口

·公共IP：端口

·由流量跟踪器116节点提供的初始服务器TCP序号。

·服务器TCP序号δ。

·原始主要流量跟踪器IP地址。

·原始次要流量跟踪器IP地址。

·最近检测的进入服务器112的IP地址。

·此条目的期满时间

·最近最少使用(LRU)/冲突指数。

在至少一些实施方案中，每个负载平衡器模块132定期为所有活 动客户端连接的主要和次要流量跟踪器节点产生连接发布消息。在至 少一些实施方案中，将/proc/net/tcp的内容扫描并且与负载平衡器模 块的哈希表中的活动连接相交以使得其继续发布至流量跟踪器节点 直到Linux内核停止跟踪连接为止。连接发布稍后在此文件中更详细 地论述。

序号改编

如前所述，在至少一些实施方案中负载平衡器节点110代表服务 器134响应于客户端160SYN封包来产生SYN/ACK封包。仅在客户 端160发送ACK封包(TCP三向握手)之后，负载平衡器模块110将 任何数据发送至服务器节点130上的负载平衡器模块132。当首次指 示负载平衡器模块132建立客户端连接时，负载平衡器模块132局部 编制SYN封包以开始与服务器节点130上的服务器134的TCP连接， 并且截取服务器134的相应SYN/ACK封包。典型地，服务器134(例 如，服务器节点130上的Linux内核)选择与客户端在来自负载平衡 器节点110的SYN/ACK封包中所接收的序号完全不同的TCP序号。 因此，在至少一些实施方案中，负载平衡器模块132可校正客户端 160与服务器134之间的TCP连接中的所有封包的序号。在至少一些 实施方案中，负载平衡器模块132计算由负载平衡器节点110产生的 序号与由服务器134产生的序号之间的差异并且将差异作为δ值存储 于TCP连接的哈希表条目中。当传入数据封包从此连接上的客户端 160到达时，TCP报头含有与由服务器134使用的序号未对准的确认 编号，因此负载平衡器模块132将δ值(例如，使用二进制补码)从TCP 报头中的序号值减去。负载平衡器模块还将δ值添加至从服务器134 至此连接上的客户端130的外出封包中的序号。

分布负载平衡器系统中的健康检查

在分布负载平衡器系统的至少一些实施方案中，每个负载平衡器 节点110至少出于以下原因需要负载平衡器实行方案中的健康成员 (即，健康负载平衡器节点110和服务器节点130)的一致视图：

·负载平衡-负载平衡器节点110需要检测服务器节点130失效并 且收敛于可接受客户端流量的一组健康服务器节点130上。

·分布式状态管理-负载平衡器是状态在多个负载平衡器节点 110上共有/复现的分布式系统(例如，根据一致哈希机制)。为了正确 地操控客户端流量，每个负载平衡器节点110需要具有负载平衡器实 行方案中的健康成员节点110的最终一致视图。

为了实现此目标，至少一些实施方案分布负载平衡器系统可实施 监测负载平衡器实行方案中的节点并且尽可能快地检测不健康节点 的健康检查协议的实施方案。健康检查协议可在负载平衡器实行方案 中的节点之间传送健康信息，并且可提供使得节点能够收敛于一组健 康节点的方法。另外，健康检查协议可提供报道负载平衡器实行方案 中的健康/不健康节点和状态变化的机制。

在至少一些实施方案中，健康检查协议可基于以下假设的一个或 多个，但是不限于：

·负载平衡器实行方案中的所有节点已知。(即，健康检查协议 不可执行发现)。

·所有节点失效是失效停止。

·节点之间的所有消息是无状态的协议(例如，UDP)消息，并且 消息可丢弃、延迟、复制或损坏。没有关于消息交付的保证。

在至少一些实施方案中，负载平衡器实行方案中的节点(例如， 负载平衡器节点110或服务器节点130)在以下条件下可被认为是健 康的：

·所有节点的内部部件处于准备状态(准备操控客户端流量)。

·节点的传入/传出网络链路是健康的(至少对于客户端流量在其 上流动的网络接口控制器(NIC)来说)。

图12是根据至少一些实施方案的可根据健康检查间隔由每个负 载平衡器节点执行的健康检查方法的较高水平流程图。如1000指示， 在每个负载平衡器间隔下，例如每100毫秒，每个负载平衡器(LB) 节点110可对于至少一个其他LB节点110和至少一个服务器节点130 进行健康检查。如1002指示，负载平衡器节点110可根据健康检查 来更新其局部存储健康信息。如1004指示，然后，负载平衡器节点 110可随机选择至少一个其他负载平衡器节点110并且将其健康信息 发送至选定负载平衡器节点110。在至少一些实施方案中，节点110 还可将健康负载平衡器节点110的列表发送至一个或多个服务器节 点130，例如由节点110健康检查的相同服务器节点130。图12的元 件在以下论述中更详细地解释。

在健康检查协议的至少一些实施方案中，负载平衡器节点110不 向其他负载平衡器节点110断言其自身健康。替代地，一个或多个其 他负载平衡器节点110可对于节点110进行健康检查。举例来说，在 至少一些实施方案中，每个负载平衡器节点110可定期或不定期地随 机选择一个或多个其他节点110来健康检查。作为另一个实例，在至 少一些实施方案中，一个或多个其他负载平衡器节点110，例如节点 110的有序列表如一致哈希环上的给定负载平衡器节点110的两个最 近的近邻，可各自定期或不定期地检查给定节点110的健康状况。在 至少一些实施方案中，对于节点110进行健康检查可包括使用发送至 节点110上的NIC1114的健康ping，如图23示出。在至少一些实施 方案中，如果第一节点110经由健康检查确定第二节点110是健康的， 第一节点110可更新(例如，递增)存储于负载平衡器节点110的局部 健康信息中的第二节点110的心跳计数器。第一节点110定期或不定 期地将其局部健康信息发送至负载平衡器实行方案中的一个或多个 其他负载平衡器节点110，其可相应地更新其自身局部健康信息(例 如，通过递增第二节点的心跳计数器)并且将其更新局部健康信息发 送至一个或多个其他节点110。因此，第二节点110的心跳信息可传 送至负载平衡器实行方案中的其他节点110。只要第二节点110是健 康的，可从第二节点110到达的所有其他节点110将由此发现第二节 点110的心跳计数器一致地获得增加，例如每秒一次或每十秒一次。 如果第二节点110由检查其健康的节点110检测为不健康，健康检查 节点110不发送节点110的心跳，并且在某一时间阈限之后，负载平 衡器实行方案110中的其他节点110认为所讨论的节点110是不健康 的，或停用。

在至少一些实施方案中，负载平衡器节点110可检查其自身内部 状态的一个或多个方面并且如果节点110检测到它出于某种原因是 不健康的，节点110可停止对于来自其他节点110的检查其健康的健 康ping作出响应。因此，检查不健康节点110的健康状况的节点110 可认为节点110是不健康的，并且可不代表节点110来传送心跳增量。

健康检查协议细节

在至少一些实施方案中，健康检查协议可利用心跳计数器技术和 传播协议技术。健康检查协议可被认为具有两个主要部分-健康检查 和传播/失效检测。

健康检查-负载平衡器实行方案中的每个负载平衡器节点110可 定期或不定期地对于实行方案中的一个或多个其他节点110进行健 康检查。藉以确定一个或多个其他节点的方法稍后论述。健康检查的 核心观念是如果节点110对于另一个节点110进行健康检查并且确定 其他节点110是健康的，那么检查节点110通过增加和传送其他节点 110的心跳计数器来断言其他节点110是健康的。换句话说，节点110 不向其他节点断言其自身健康状况；替代地，一个或多个其他节点 110检查和断言负载平衡器实行方案中的每个节点110的健康状况。

传播/失效检测-在至少一些实施方案中，健康检查协议可利用传 播协议来在负载平衡器实行方案中的成员负载平衡器节点110之间 传送负载平衡器节点110健康信息。传播协议快速收敛，并且提供对 于分布负载平衡系统的用途来说足够的最终一致性保证。在至少一些 实施方案中，通过使用传播协议，每个负载平衡器节点110将负载平 衡器实行方案中的每个其他节点110的心跳计数器保持于例如心跳 列表中。每个负载平衡器节点110定期或不定期地如上所述执行至少 一个其他负载平衡器节点110的健康检查，并且在经由健康检查来确 定所检查节点110是健康的之后，增加节点110的心跳计数器。在至 少一些实施方案中，每个负载平衡器节点110定期或不定期地随机选 择负载平衡器实行方案中的至少一个其他节点110，所述负载平衡器 节点向所述其他节点发送其当前心跳列表。在接收来自另一个节点 110的心跳列表后，负载平衡器节点110将所接收的列表中的心跳信 息与其自身心跳列表合并，所述合并是通过确定两个列表(所接收的 列表和其自身列表)中的每个节点110的最大心跳计数器并且在其自 身心跳列表中使用所确定的最大心跳计数器来实现的。进而，此心跳 列表被发送至另一个随机选择节点110，其相应地更新其自身心跳列 表，依此类推。使用此技术，每个健康节点110的心跳信息最终(例 如，在几秒内)传送至负载平衡器实行方案中的所有其他负载平衡器 节点110。只要给定负载平衡器节点110的心跳计数器保持增加，它 被其他节点110认为是健康的。如果通过健康检查和传播方法，负载 平衡器节点110的心跳计数器在指定期限内未增加，那么其他负载平 衡器节点110可收敛于被认为不健康的负载平衡器节点110。

对负载平衡器节点进行健康检查

以下描述根据至少一些实施方案的可由另一个负载平衡器节点 110执行的对负载平衡器节点110进行健康检查的方法。参照图23， 在至少一些实施方案中，如果确定节点110的一个或多个以下条件， 那么负载平衡器节点110可被认为是健康的：

·节点110的处理器线程(例如，核心封包处理代码1108线程) 处于准备状态(内部)。

·节点110知道边缘路由器104的IP地址和/或MAC地址(内部)。

·节点110的所有线程和/或协议操控器处于准备状态(内部)。

·来自北侧(边缘路由器104/边界网络)和南侧(服务器130/生产网 络)的传入和传出链路是活动的(外部)。

·节点110可经由在负载平衡器实行方案中使用的网络接口控制 器(NIC)接收并发送封包。举例来说，在如图23示出的示例性负载平 衡器节点110实施方案中，节点110应经由朝北NIC1114A和朝南 NIC1114B成功地接收和发送封包。

如果这些健康条件中的一个或多个对于给定节点110无效，那么 节点110可被认为是不健康的。注意，在一些实施方案中，仅在所有 上述条件对于节点110有效时，节点110才被认为是健康的。

在至少一些实施方案中，除了上述健康条件以外，每个负载平衡 器节点110上的可例如用于控制平面通信的在图23中展示为NIC 1114C的第三NIC也可由健康检查节点110通过向NIC发送封包并 且接收来自NIC的封包来检查，并且如果检查第三NIC不合格，那 么所检查的节点110可被认为是不健康的。

图13示出根据至少一些实施方案的从另一个负载平衡器节点对 一个负载平衡器节点进行健康检查的示例性方法。在此实施例中，负 载平衡器节点110A是健康检查负载平衡器节点110B。每个节点110A 和110B具有朝北NIC(图23中的NIC1114A)和朝南NIC(图23中的 NIC1114B)。在1处，节点110A将封包(例如，ping封包)从其朝北 NIC经由边缘路由器104发送至节点110B的朝北NIC。节点110B 在其朝北NIC上接收封包，并且在2处将响应从其朝北NIC经由结 构120发送至节点110A的朝北NIC，只要满足以上列表给定的条件。 在其朝北NIC上接收响应之后，在3处，节点110A将封包(例如， ping封包)从其朝南NIC经由结构120发送至节点110B的朝南NIC。 节点110B在其朝南NIC上接收封包，并且在4处将响应从其朝南 NIC经由边缘路由器104发送至节点110A的朝南NIC，只要满足以 上列表给定的条件。在其朝南NIC上接收响应后，节点110A认为节 点110B是健康的并且增加节点110B的局部心跳计数器，其可然后 根据如前所述的传播协议传送至其他节点110。

作为上述情况的替代方案，在一些实施方案中，负载平衡器节点 110B可经由其朝南NIC发送至节点110A的朝南NIC来对于在其朝 北NIC处接收的第一ping消息作出响应，并且经由其朝北NIC发送 至节点110A的朝北NIC来对于在其朝南NIC处接收的第二ping消 息作出响应。

另外，在一些实施方案中，节点110A还可对于用于控制平面通 信的节点110B的第三NIC(在图23中展示为NIC1114C)进行健康检 查，所述健康检查通过从其自身第三NIC对于节点110B的第三NIC 执行ping并且如果节点110B是健康的，在其第三NIC上接收来自节 点110B的第三NIC的对于ping消息的响应来实现的。ping消息和响 应可经由一个或多个控制平面装置170，例如网络交换机来传递。

上述健康检查机制运用节点110B的在所有方向(北、南和经由控 制平面)上的所有传入和传出链路和数据路径以及节点110B的所有 NIC，并且当ping封包如同客户端封包一样横穿节点110B的内部队 列和发送时还验证节点110B的内部健康状况。

向负载平衡器节点指派健康检查责任

在至少一些实施方案中，负载平衡器实行方案中的每个负载平衡 器节点110可访问列表(例如，分类列表)负载平衡器实行方案中的所 有其他负载平衡器节点110，例如经由配置功能和/或经由如图1示出 的配置服务122部件。在至少一些实施方案中，每个负载平衡器节点 110可随机选择列表上的一个或多个其他节点110以在每个健康检查 间隔下进行健康检查，如果确定为健康的，就增加其心跳计数器。注 意列表包括负载平衡器实行方案中的所有负载平衡器节点110，不论 经由健康检查机制当前被认为是健康或不健康的，并且当前不健康节 点110以及健康节点110可从列表中随机选择并且进行健康检查。因 此，当前不健康节点110可被对于节点110进行健康检查的一个或多 个节点110确定为健康的，其心跳计数器可增加并且传送至其他节点 110，并且不健康节点110可由此返回到健康状态。

或者，在一些实施方案中，每个负载平衡器节点110可承担对于 列表中的一个或多个其他节点110进行健康检查并且如果确定为健 康的，增加其心跳计数器的责任。举例来说，在一些实施方案中，每 个节点110可承担对于两个其他节点，例如列表中的其“左”(或前一 个)和“右”(或下一个)最近的邻近节点110的责任。注意列表可被认为 是圆形的并且列表“末尾”的节点110可承担对于列表“开头”的节点 110进行健康检查的责任，并且反之亦然。在一些实施方案中，两个 其他节点110可另外选择例如为列表上后续的两个最近的近邻。在一 些实施方案中，每个节点110可承担对于列表上的两个以上其他节点 110，例如三个或四个其他节点110进行健康检查的责任。在至少一 些实施方案中，如果被节点110检查的邻近节点110确定为不健康的， 那么节点110可承担对于列表上的由不健康邻近节点110负责检查的 至少一个节点进行健康检查的责任。在至少一些实施方案中，除了对 于其邻近节点110(例如，“左”和“右”邻近节点)健康检查以外，每个负 载平衡器节点110还可定期或不定期地随机选择环中的节点110并且 执行此随机选择节点110的健康检查并且如果健康，就增加并且传送 随机节点110的心跳。在至少一些实施方案中，有序列表中的所有其 他节点110可考虑随机选择和健康检查，不论是否其他节点110以前 被认为健康与否。

在至少一些实施方案中，每个节点110在可被称为健康检查间隔 的有规律间隔下执行一个或多个随机选择节点110，或替代地其邻近 节点110和随机选择节点的健康检查。举例来说，在一些实施方案中， 心跳间隔可为100毫秒，但是可使用更短或更长间隔。另外，在至少 一些实施方案中，每个节点110在可被称为传播间隔的有规律间隔下 将其当前心跳列表发送或“传播”至至少一个其他随机选择节点110。 在一些实施方案中，健康检查间隔和传播间隔可相同，但是其不一定 相同。

图14图形化示出根据至少一些实施方案的一个负载平衡器节点 对一个或多个其他负载平衡器节点进行健康检查。在此实施例中，在 负载平衡器实行方案中存在八个负载平衡器节点110A-110H。虚线圆 圈代表实行方案中的所有节点110的有序列表。在一些实施方案中， 每个节点110可在每个间隔下随机选择列表上的一个或多个其他节 点110来进行健康检查。作为替代方案，在一些实施方案中，每个负 载平衡器节点110可承担检查有序列表中的一个或多个具体节点110 的责任，例如节点110A可根据如图14示出的有序列表承担对于其 两个最近的邻近节点110B和110H进行健康检查的责任。另外，负 载平衡器节点还可在每个健康检查间隔下随机选择有序列表中的另 一个节点110。如在此实施例中示出，节点110A还随机选择节点110F 来进行健康检查。在传播间隔下，节点110A随机选择某个其他健康 节点110，例如节点110D，并且将其当前心跳列表例如在UDP消息 中发送至选定其他节点110。节点110，在从另一个节点110接收心 跳列表后，可相应地更新其自身心跳列表并且在下一个传播间隔将心 跳列表传送至一个或多个随机选择节点110。

对于服务器节点进行健康检查

除了如上所述对于负载平衡器节点110进行健康检查以外，健康 检查协议的实施方案可执行服务器节点130的健康检查，包括那些节 点130上的负载平衡器模块132和服务器134。在至少一些实施方案 中，如果确定节点130的一个或两个以下条件，服务器节点130可被 认为是健康的：

·负载平衡器模块132是健康的。

·服务器节点130对于健康ping(例如，L7健康ping)成功地作出 响应。

图15示出根据至少一些实施方案的负载平衡器节点对服务器节 点进行健康检查。在至少一些实施方案中，负载平衡器实行方案中的 每个负载平衡器节点110可访问负载平衡器实行方案中的所有其他 负载平衡器节点110的列表，以及负载平衡器实行方案中的所有服务 器节点130的列表。可例如经由配置功能和/或经由如图1示出的配 置服务122部件来获得并且更新列表。在至少一些实施方案中，服务 器节点130可相对于健康负载平衡器节点110来一致哈希以形成如图 15示出的一致哈希环。在至少一些实施方案中，环中的每个服务器 节点130由环中的两个健康负载平衡器节点110来健康检查。举例来 说，在图15中，服务器节点130A由负载平衡器节点110A和110C 来健康检查。这两个节点110可被称为一致哈希环中的服务器节点 130的第一(节点110A)和第二(节点110B)健康检查节点110。注意给 定健康负载平衡器节点110可对于一个以上服务器节点130进行健康 检查。举例来说，在图15中，负载平衡器节点110A还对于服务器 节点130B和130C进行健康检查。另外，给定节点平衡器节点110 可为一个或多个服务器节点130的第一健康检查节点110和一个或多 个其他服务器节点130的第二健康检查节点110。举例来说，在图15 中，负载平衡器节点110A是服务器节点130A和130B的第一健康检 查节点以及服务器节点130C和130D的第二健康检查节点。

在至少一些实施方案中，如果负载平衡器节点110失效，一致哈 希环中的成员关系变化，并且仍然健康并且由此仍然在一致哈希环上 的一个或多个其他负载平衡器节点110可承担对于以前由失效节点 110进行健康检查的服务器节点130进行健康检查的责任。

在至少一些实施方案中，每个健康节点110在可被称为服务器检 查间隔的有规律间隔下执行其指定服务器节点130的健康检查。在至 少一些实施方案中，服务器检查间隔可大于或等于以前提到的传播间 隔。

在至少一些实施方案中，为了执行服务器节点130的健康检查， 健康负载平衡器节点110(例如，图15中的节点110A)向服务器节点 130(例如，图15中的服务器节点130A)启始健康ping消息(例如，L7 HTTP健康ping消息)。如果健康，服务器节点130将ping响应发送 回到负载平衡器节点110。在至少一些实施方案中，ping消息由服务 器节点130上的负载平衡器模块132接收并处理，因此健康检查ping， 如果成功，证实服务器节点130上的模块132是健康的。在接收ping 的响应后，负载平衡器节点110认为服务器节点130是健康的，并且 增加服务器节点130的心跳计数器。

在至少一些实施方案中，由给定健康负载平衡器节点110健康检 查的所有服务器节点130的心跳计数器可传送至其他负载平衡器节 点110，例如根据以前对于负载平衡器节点110心跳计数器所描述的 传播技术，其中每个节点110在有规律间隔(传播间隔)下将其心跳列 表发送至至少一个其他随机选择节点110，并且接收节点110根据两 个列表中的最大值来更新其自身心跳列表。

失效检测和传播

在至少一些实施方案中，经由如上所述的负载平衡器节点110健 康检查和服务器节点130健康检查获得的信息可能需要传送至负载 平衡器实行方案中的所有节点110以使得所有负载平衡器节点110可 保持负载平衡器实行方案的一致视图。如上所述，在至少一些实施方 案中，负载平衡器节点110可根据传播协议来彼此通信以交换并传送 此健康信息并且检测负载平衡器节点110和服务器节点130失效。

在至少一些实施方案中，在有规律间隔(被称为传播间隔)下，每 个负载平衡器节点110随机选择另一个负载平衡器节点110并且向其 他节点110发送其健康负载平衡器节点110和服务器节点130的视图 与负载平衡器节点110和服务器节点130的心跳计数器。只要负载平 衡器节点或服务器节点130是健康的，节点将在其健康检查中合格并 且其心跳计数器保持增加。如果节点的心跳计数器在指定间隔(可被 称为失效时间间隔)内未变化，那么节点被负载平衡器节点110怀疑 已经失效。一旦怀疑节点失效，负载平衡器节点110可在确定节点不 健康之前等待指定间隔(可被称为不健康时间间隔)。此不健康时间间 隔允许负载平衡器节点110等候直到所有负载平衡器节点110获知节 点失效为止。

图16图形化示出根据至少一些实施方案的可由负载平衡器节点 110保持的另一个节点(负载平衡器节点110或服务器节点130)的健康 的状态或视图。假设负载平衡器节点110开始于所讨论的节点是健康 的视图，如300指示。这表明此节点的心跳计数器一直增加。然而， 如果如302指示，节点的心跳计数器在指定间隔(失效时间间隔)内未 增加，那么负载平衡器节点110怀疑节点已经失效，如304指示。如 果如306指示，节点的心跳计数器在指定间隔(不健康时间间隔)内未 增加，那么负载平衡器节点110认为节点不健康，如308指示。然而， 如果如310指示，心跳计数器节点在不健康时间间隔终止之前增加， 负载平衡器节点110再次认为节点是健康的300。类似地，如312指 示，接收不健康节点的心跳增加可导致节点被认为是健康的300。

确定节点不健康可涉及负载平衡器节点110的不同操作，取决于 是否不健康节点是负载平衡器节点110或服务器节点130，并且还取 决于负载平衡器节点110与不健康节点的关系，如本文中别处描述。

负载平衡器节点数据

在至少一些实施方案中，每个负载平衡器节点110可保持关于负 载平衡器实行方案的状态的数据。在至少一些实施方案中，此数据可 以一种或多种数据结构来保持于每个负载平衡器节点110上，包括但 不限于健康负载平衡器节点列表、怀疑负载平衡器节点列表和心跳列 表。图17示出示例性负载平衡器节点110，其保持健康负载平衡器 节点列表320、怀疑负载平衡器节点列表322、不健康负载平衡器节 点列表324和负载平衡器节点心跳列表326。

在至少一些实施方案中，每个负载平衡器节点110可保持健康负 载平衡器节点列表320，其为可例如用于确定哪些节点110是健康的 并且因此参与传播协议的健康负载平衡器节点110的列表。仅列表 320上的节点110涉及经由传播协议来传送负载平衡器信息，仅列表 320上的节点110被认为是一致哈希环，并且仅此列表上的节点110 对于服务器节点130进行健康检查。节点110可从此列表320中随机 选择发送其心跳信息所到达的另一个节点110。另外，仅对于当前在 健康负载平衡器节点列表320中的节点110，交换心跳计数器。在至 少一些实施方案中，负载平衡器节点N可添加至另一个负载平衡器 节点110的健康负载平衡器节点列表320，只要节点N由负载平衡器 节点110健康检查合格或只要负载平衡器节点110从列表320上的某 个其他负载平衡器节点110接收关于节点N的传播消息。

在至少一些实施方案中，每个负载平衡器节点110可保持怀疑负 载平衡器节点列表322，其为其心跳计数器(参见心跳列表326)在指 定间隔(被称为失效时间间隔)内未增加的负载平衡器节点列表。如果 负载平衡器节点E在负载平衡器节点110的怀疑负载平衡器节点列表 322中，那么负载平衡器节点110不关于节点E进行传播。如果与节 点110的心跳列表326中的关于节点E的计数器相比，健康列表320 上的某个其他负载平衡器节点110向负载平衡器节点110传播关于节 点E具有较高心跳计数器，那么节点E从怀疑列表322移动至健康 列表320。如果节点E在指定间隔(被称为不健康时间间隔)内保持于 负载平衡器节点110的怀疑列表322上，节点E被负载平衡器节点 110认为不健康并且移动至不健康节点列表324上。不健康节点列表 324上的节点110(在此实施例中，节点G)可移动至负载平衡器节点 110的健康节点列表320，只要节点G由节点110健康检查合格或从 另一个节点110接收节点G的更新心跳计数器。

在至少一些实施方案中，每个负载平衡器节点110可保持所有已 知负载平衡器节点110的心跳列表326。对于每个节点110，此列表 326可包括心跳计数器和指示心跳计数器最近何时改变的时间戳。

在至少一些实施方案中，每个负载平衡器节点110还可保持所有 已知服务器节点的心跳列表，未在图17中展示。此列表可类似于负 载平衡器节点心跳列表326。在一些实施方案中，两个列表可组合。 在至少一些实施方案中，服务器节点130的心跳信息可例如根据传播 协议连同或附加于负载平衡器节点110的心跳信息在负载平衡器节 点110之间传送。

虽然图17示出四个单独列表，但是应注意两个或更多个列表可 组合于单一列表中。举例来说，在一些实施方案中，所有节点110的 单一列表可保持于每个负载平衡器节点110上，并且位标志或其他数 据结构可用于指示是否每个节点当前是健康、怀疑或不健康的。

服务器节点数据

在至少一些实施方案中，服务器节点130和节点130上的局部负 荷平衡器模块132不参与负载平衡器节点110的传播协议。负载平衡 器节点110将通过负载平衡器节点健康检查方法获得的关于其他负 载平衡器节点110的心跳信息和通过服务器节点健康检查方法获得 的关于服务器节点130的心跳信息只在本身之间传播(具体来说，每 个负载平衡器节点110只向当前在其健康负载平衡器节点列表320中 的节点传播)。

然而，每个服务器节点130/负载平衡器模块132可能需要关于负 载平衡器实行方案中的健康负载平衡器节点110的信息以使得服务 器节点130可确定服务器节点130可将传出客户端流量转发至哪些负 载平衡器节点110(具体来说，外出节点)并且确定将连接发布信息发 送至哪些负载平衡器节点。在至少一些实施方案中，为了将此信息提 供至服务器节点130，负载平衡器节点110可定期或不定期地用识别 当前健康负载平衡器节点110(例如，图17中的健康负载平衡器节点 列表320)的信息来更新服务器节点130。在至少一些实施方案中，负 责对于给定服务器节点130进行健康检查的负载平衡器节点110(参 见图15)负责将识别当前健康负载平衡器节点的信息提供至服务器 130。举例来说，参看图15，负载平衡器节点110A可将其健康负载 平衡器节点列表320发送至服务器节点130A、130B、130C和130D， 负载平衡器节点110B可将其健康负载平衡器节点列表320发送至服 务器节点130C、130D和130E，依此类推。

操控负载平衡器节点失效

图18A和18B示出根据至少一些实施方案的操控负载平衡器节 点失效。图18A示出示例性负载平衡器实行方案。当前在负载平衡 器实行方案中存在四个负载平衡器节点110A至110D。边缘路由器 104将来自客户端(未展示)的传入封包依路由传递至负载平衡器节点 110。在至少一些实施方案中，边缘路由器104可根据层4每流哈希 多路径路由技术，例如等价多路径(ECMP)路由技术来作出路由决定。 在至少一些实施方案中，边缘路由器104经由负载平衡器节点110公 布来获知当前在负载平衡器实行方案中可用于接收客户端流量的负 载平衡器节点110，例如经由由负载平衡器节点110启始的边界网关 协议(BGP)技术会话来公布。然而，在至少一些实施方案中，代替负 载平衡器节点110经由BGP会话将本身公布至边缘路由器104，负载 平衡器实行方案中的至少一个其他节点110承担经由BGP将节点110 公布至边缘路由器104的责任。举例来说，在如图18A示出的一些 实施方案中，给定节点110的左和右邻近节点110将给定节点110公 布至边缘路由器104。举例来说，负载平衡器节点110A公布节点110B 和110D，负载平衡器节点110B公布节点110A和110C，并且负载平 衡器节点110C公布节点110B和110D。

如图18A的实例中示出，每个负载平衡器节点110还定期对于 一个或多个其他负载平衡器节点110进行健康检查，例如一个或多个 随机选择节点110、如由负载平衡器节点的有序列表确定的一个或多 个邻近节点110，或一个或多个邻近节点和一个或多个随机选择节点。 另外，每个负载平衡器节点110可定期对于至少一个服务器节点130 进行健康检查并且还可将其健康负载平衡器节点110列表发送至它 健康检查的服务器节点。负载平衡器节点110和服务器节点130的健 康信息可在节点110之间传送，例如根据传播协议。

图18B示出在图18A的示例性负载平衡器实行方案中操控单一 负载平衡器节点110的失效。在此实施例中，负载平衡器节点110B 出于某种原因失效。举例来说，节点110A和110C可对于节点110B 进行健康检查，并且同时可检测到节点110B在其健康检查中不合格。 因此，节点110A和110C不增加节点110B的心跳计数器。来自节点 110A和110B的心跳信息根据传播协议传送至其他健康负载平衡器 节点110(在此实施例中，唯一的其他负载平衡器节点是节点110D)。 只要所有健康负载平衡器节点110(在此实施例中，节点110A、110C 和110D)收敛于节点110B失效，可发生但是不限于以下事件中的一 个或多个。注意这些事件不一定以此顺序发生。

·节点110A和110C停止将节点110B公布至边缘路由器104。 在至少一些实施方案中，这涉及终止节点110与边缘路由器104建立 以公布节点110B的BGP会话。注意每个节点110针对它公布的每个 其他节点110来建立与边缘路由器104的单独BGP会话，因此结束 节点110B的BGP会话并不影响所公布的其他节点110。在至少一些 实施方案中，节点110通过将BGP会话的TCP关闭或类似消息发送 至边缘路由器104来终止与边缘路由器104的BGP会话。

·响应于检测到节点110B不再由任何节点公布，边缘路由器104 停止将客户端数据封包依路由传递至节点110B。边缘路由器104还 调整多路径(例如，ECMP)哈希以将来自客户端的封包流重新分布至 其余健康负载平衡器节点110，尤其分布至节点110上的进入服务器 112。对于依路由传递至进入服务器112不具有客户端->服务器映射 的进入服务器112的任何封包流来说，映射可从客户端->服务器连接 的流量跟踪器节点获得，或替代地新的客户端->服务器连接可根据如 图10A至10G示出的技术来建立。

·节点110A和110C可各自打开至边缘路由器104的BGP会话 以彼此公布。注意，因为节点110A和110C通过负载平衡器节点110D 以及节点110B来公布至边缘路由器104，节点110B在它失效时可停 止将节点110A和110B公布至边缘路由器104的事实未导致边缘路 由器104停止将封包依路由传递至这两个节点110。

·在至少一些实施方案中，节点110A和110C可承担彼此健康 检查的责任，因为其现在是邻近节点110。注意节点110B，虽然被认 为是不健康的，可仍然通过一个或多个其他节点110来随机健康检 查。

·其余健康负载平衡器节点110中的一个或多个可承担对于以前 由节点110B进行流量跟踪的连接进行流量跟踪的责任。举例来说， 对于节点110B作为主要或次要流量跟踪器的一个或多个连接，节点 110C和/或节点110D可接管为主要或次要流量跟踪器，如图11C和 11D示出。

·其余健康负载平衡器节点110中的一个或多个可承担对于以前 由节点110B进行健康检查的服务器节点130进行健康检查的责任。 服务器节点130通过其余负载平衡器节点110用健康负载平衡器节点 列表(现在不包括节点110B)来更新。举例来说，在图18B中，负载 平衡器节点110A开始对于服务器节点130C进行健康检查和更新， 并且负载平衡器节点110C开始对于服务器节点130B进行健康检查 和更新。

·在边缘路由器104上，来自失效节点110B的BGP会话最终超 时。或者，边缘路由器104可在识别节点110B已经失效后停止BGP 会话。

两个负载平衡器节点110可同时或接近同时失效。如果两个失效 负载平衡器节点不彼此相邻，那么失效是独立的并且可根据图18B 示出的方法作为单独单一节点110失效来操控。然而，如果两个失效 节点彼此相邻(例如，图18A中的节点110B和110C，那么只要所有 健康负载平衡器节点110(在此实施例中，节点110A和110D)检测到 并且收敛于此失效，那么可发生但是不限于以下事件中的一个或多 个。注意这些事件不一定以此顺序发生。

·节点110A针对节点110B来终止与边缘路由器104的BGP会 话。

·节点110D针对节点110C来终止与边缘路由器104的BGP会 话。

·节点110A和110D起始与边缘路由器104的BGP会话以彼此 公布。

·节点110A和110D可开始彼此健康检查。注意节点110A和 110D还可继续对于失效节点110进行健康检查。

·其余健康节点110用健康负载平衡器节点列表来更新服务器节 点130。

·流量可继续从边缘路由器104流至节点110B和/或节点110C， 因为这两个节点110可继续向边缘路由器104彼此公布。然而，这些 BGP会话最终超时，并且边缘路由器104相应地将流量重新分布至 其余公布节点110。

·如果节点110B和110C认为其仍然健康，节点110B和110C 可关闭其与边缘路由器104的BGP会话，在所述会话中，这些节点 分别公布节点110A和110D。

连接发布

再次参看图1，在至少一些实施方案中，负载平衡器实行方案中 的负载平衡器节点110保持至服务器130的客户端TCP连接的状态 信息。此状态信息允许负载平衡器节点110将来自边缘路由器104的 传入客户端流量依路由传递至负责TCP连接的服务器节点130。服务 器节点130上的负载平衡器模块132保持至其相应服务器134的活动 TCP连接的列表。连接发布是服务器节点130上的负载平衡器模块 132可藉以将其活动客户端TCP连接列表发布至负载平衡器节点110 的机制。在至少一些实施方案中，在可被称为连接发布间隔的有规律 间隔下，由负载模块132形成连接发布封包并且将其发布至负载平衡 器节点110。

在至少一些实施方案中，由负载平衡器节点110保持的连接状态 信息可视为一种形式的缓存，并且保持具体连接的状态信息可视为保 持此连接的负载平衡器节点110上的租约。除非缓存条目得到更新， 负载平衡器节点110可能不能够将客户端数据流依路由传递至操控 数据流的服务器节点130。连接发布机制定期地用来自服务器节点 130的当前连接状态信息来更新缓冲，并且由此更新负载平衡器节点 110上的租约，从而保持TCP封包从客户端160流至适当服务器节点 130。当客户端160终止至服务器134的TCP连接时，与此连接相关 联的服务器节点130上的负载平衡器模块132从其活动连接列表中丢 弃此连接，并且由此不再经由连接发布机制来发布此TCP连接。因 此，与此连接相关联的负载平衡器节点110(具体来说，此连接的进入 服务器112以及主要和次要流量跟踪器116)上的此连接的连接状态信 息(一个或多个缓存条目)不再更新，并且此连接被负载平衡器节点 110丢弃。在至少一些实施方案中，此连接的一个或多个缓存条目可 保持于负载平衡器节点110上的缓存中直到某个其他活动连接需要 存储器为止。

因此，连接发布机制定期或不定期地延长进入服务器112和主要 和次要流量跟踪器116上的连接租约以保持客户端流量流动。另外， 连接发布机制可帮助从至少一些负载平衡器节点110失效中恢复。当 保持客户端连接的状态信息的一个或多个负载平衡器节点110失效 时，通过连接发布来提供至其余负载平衡器节点110的活动连接信息 可在一些情况下用于恢复连接。

使用连接发布机制，服务器节点130是服务器134与客户端160 之间连接的状态的权威来源。另外，关闭至服务器134的连接通过服 务器节点130上的负载平衡器模块132和负载平衡器节点110来被动 地操控。服务器节点130与负载平衡器节点110之间不需要握手。换 句话说，负载平衡器模块132不需要将消息发送至负载平衡器节点 110以主动地通知节点具体连接已经关闭。当服务器134关闭连接时， 服务器134清除其关于此连接的内部状态。负载平衡器模块132使用 服务器134的内部状态以填充连接发布封包。由于连接不再在服务器 134的内部状态中，因此连接不被发布至负载平衡器节点110。负载 平衡器节点110上的连接的租约由此终止，并且负载平衡器节点110 被动地忘记此连接。然后，用于此连接的负载平衡器节点110的缓存 中的存储器在必要时可用于其他连接。

在一些实施方案中，由负载平衡器节点110保持的连接的租约可 涉及缓存中的关于连接的时间戳条目。当连接的租约通过连接发布封 包来更新时，时间戳可更新。如果因为连接不再由服务器节点130上 的负载平衡器模块132发布而导致连接的租约不被更新，那么时间戳 不再更新。在至少一些实施方案中，可使用懒惰的无用项目收集方法， 其中此连接的条目可保持于缓存中直到需要存储器为止。举例来说， 在至少一些实施方案中，缓存条目上的时间戳可与租约更新时间阈限 比较；如果缓存条目的时间戳比阈值旧，那么条目过时并且可重新使 用。然而，在一些实施方案中，过时条目可主动地作为无用项目来收 集。

连接发布接受者

在至少一些实施方案中，对于每个客户端TCP连接，存在保持 连接状态的三个负载平衡器节点110-充当进入服务器112的节点 110、充当主要流量跟踪器116的节点110和充当次要流量跟踪器116 的节点。对于给定TCP流，主要和次要流量跟踪器116可例如由负 载平衡器节点110通过向TCP流应用一致哈希函数以发现主要流量 跟踪器116节点和其在一致哈希环中的后续节点来确定。充当TCP 流的进入服务器112的负载平衡器节点110是基于边缘路由器104的 内部多路径(例如，ECMP)哈希函数从边缘路由器104接收此流的流 量的节点110。如果节点110失效或添加，对于许多活动TCP流来说， 充当进入服务器112的负载平衡器节点110可变化；并且充当至少一 些活动TCP流的流量跟踪器的负载平衡器节点110可变化(参见，例 如，图11A至11D)。对于至服务器节点130上的服务器132的每个 TCP流来说，服务器节点130上的负载平衡器模块132保持指示哪一 个负载平衡器节点110是此TCP流的进入服务器112的状态信息， 因为它接收来自此负载平衡器节点110的流量。然而，在至少一些实 施方案中，负载平衡器模块132可能不知道和可能不能够确定哪一个 负载平衡器节点110充当TCP流的主要和次要流量跟踪器，因为负 载平衡器模块132可能不知道所使用的一致哈希函数。换句话说，在 至少一些实施方案中，负载平衡器模块132不执行一致哈希。

发布活动连接信息

图19A和19B图形化示出根据至少一些实施方案的连接发布技 术。图19A示出向负载平衡器节点发布活动连接信息的负载平衡器 (LB)模块。在至少一些实施方案中，每个负载平衡器模块132将每个 活动TCP流的信息收集于服务器节点130上并且形成连接发布封包。 给定TCP流的信息包括识别充当此流的进入服务器112的负载平衡 器节点110的信息。当连接发布封包准备时(例如，当已经达到连接 发布间隔时)，负载平衡器模块132例如从健康负载平衡器节点110 列表来随机选择负载平衡器节点110，所述列表从如前所述对于服务 器节点130进行健康检查的负载平衡器节点110定期发送至服务器节 点130。负载平衡器模块132然后将连接发布封包发送至选定节点 110。举例来说，在图19A中，负载平衡器模块132A将一个连接发 布封包发送至负载平衡器节点110A，并且稍后将另一个连接发布封 包发送至负载平衡器节点110B。

图20是根据至少一些实施方案的可由每个负载平衡器模块132 执行的连接发布方法的较高水平流程图。如500指示，负载平衡器(LB) 模块132产生相应服务器节点130上的每个活动TCP流的连接发布 条目。在至少一些实施方案中，负载平衡器模块132例如从服务器节 点130上/proc/net/tcp来检索服务器节点130上的服务器134操控的 一组活动TCP连接。对于每个活动TCP连接，负载平衡器模块132 查看(例如，在局部保持的活动连接表中)充当TCP流的进入服务器 112的负载平衡器节点110并且产生连接发布条目，其指示此连接的 TCP元组(例如，由以下组成的4元组：客户端IP地址、客户端端口、 服务器(公共)IP地址和服务器端口)和此连接的进入服务器112。注意 每个负载平衡器模块132保持每个活动TCP连接的信息，其指示发 送此连接的封包的最后一个负载平衡器节点110，并且此信息可由负 载平衡器模块132用于识别每个活动连接的进入节点110。

如502指示，负载平衡器模块132随机选择接收连接发布封包(含 有一个或多个连接发布条目，其中一个条目针对每个活动TCP连接) 的负载平衡器节点110。在至少一些实施方案中，当负载平衡器模块 132确定连接发布封包准备发送时，可随机选择负载平衡器模块110。 在至少一些实施方案中，此确定根据连接发布间隔来作出。作为非限 制实例，连接发布间隔可为100毫秒(ms)，或一秒。在至少一些实施 方案中，负载平衡器模块110选自以前从负载平衡器节点110中的一 个接收的健康负载平衡器节点110列表。如504指示，负载平衡器模 块然后将连接发布封包发布至选定负载平衡器节点110。在至少一些 实施方案中，连接发布封包是无状态的封包，例如UDP封包。在一 些实施方案中，连接发布封包可在将封包发送至目标负载平衡器节点 110之前加以压缩。在至少一些实施方案中，连接发布信息可在两个 或更多个封包中发送至目标负载平衡器节点110。

如从元件504回到元件500的箭头所指示，负载平衡器模块132 可连续建立连接发布封包、选择随机节点110，并且将封包发送至选 定节点。如以上提及，这可根据连接发布间隔来执行以使得负载平衡 器节点110相对有规则地用当前活动连接信息刷新以保持负载平衡 器节点110上的连接租约。

在至少一些实施方案中，因为连接发布封包由负载平衡器模块随 机分配至负载平衡器节点110，接收连接发布封包的负载平衡器节点 110负责将连接发布封包中的活动连接信息分配至这些连接的正确进 入/主要/次级节点110。图19B和图21和22示出可在至少一些实施 方案中使用的分配活动连接信息的方法。

图19B示出根据至少一些实施方案的在负载平衡器节点110之间 分配活动连接信息。当负载平衡器节点110从负载平衡器模块132接 收连接发布封包时，负载平衡器节点110可分析其中指示的每个TCP 流的信息以确定此流的进入节点和主要和次要流量跟踪器节点。如果 负载平衡器节点110以针对某一流的那些角色中的一个来服务，负载 平衡器节点110消耗此流的信息(例如，通过更新其状态信息缓存)。 在至少一些实施方案中，负载平衡器节点110还可将此流的信息置于 将要发送至以针对此流的其他角色来服务的一个或多个其他节点110 的封包中。对于由连接发布封包指示的其余流，负载平衡器节点110 将活动连接信息划分成两个或更多个较小封包并且将每个封包发送 至一个或多个其他负载平衡器节点110。举例来说，在至少一些实施 方案中，含有一个或多个流的活动连接信息的封包可发送至充当所述 一个或多个流的进入服务器112、主要流量跟踪器116A和次要流量 跟踪器116B的负载平衡器节点110。

图21是根据至少一些实施方案的将在连接发布封包中接收的活 动连接信息分配至目标负载平衡器节点110的方法的流程图。如520 指示，负载平衡器节点110接收来自负载平衡器模块132的连接发布 封包。负载平衡器模块132产生封包并且选择负载平衡器节点110来 接收封包，例如如上参照图19A和20所述。连接发布封包可包括识 别发送封包的服务器节点130的信息(例如，服务器节点130上的负 载平衡器模块132的IP地址)和识别活动TCP连接的条目的列表(例 如，由以下组成的4元组：每个连接的客户端IP地址、客户端端口、 服务器(公共)IP地址和服务器端口)。

在图21的元件522-530中，负载平衡器模块110重复处理在所 接收的连接发布封包中指示的活动TCP连接信息。如522指示，负 载平衡器节点110分析封包中的下一个TCP流的条目以确定相应 TCP流的进入节点110和主要和次要流量跟踪器节点110。在至少一 些实施方案中，负载平衡器节点110从连接发布条目得到进入节点 110的身份。在至少一些实施方案中，TCP流的主要和次要流量跟踪 器节点110可根据一致哈希函数来确定。在524处，如果负载平衡器 节点110以针对所检查的TCP流的角色中的一个来服务，那么526 负载平衡器节点110消耗此流的信息，例如通过更新其状态信息缓 存。如528指示，负载平衡器节点110可将TCP流的连接发布条目 添加至所构建的将要发送至另一个负载平衡器节点110的封包。在 530处，如果在连接发布封包中存在多个流的更多连接发布条目，那 么方法返回到522以处理下一个条目。否则，负载平衡器节点将各自 含有来自原始连接发布封包的连接发布条目的子集的新构建封包发 送至目标负载平衡器节点110封包，如532指示。在至少一些实施方 案中，发送至目标负载平衡器节点110的封包是无状态的封包，例如 UDP封包。在一些实施方案中，封包可在将封包发送至目标负载平 衡器节点110之前加以压缩。

因此，在至少一些实施方案中，在图21的元件522-528中，流 量跟踪器节点110根据在522处从所接收连接发布封包中的连接发布 条目确定的信息来构建各自将要发送至其他节点110中的具体一个 的一个或多个封包(例如，UDP封包)。在至少一些实施方案中，发送 至另一个节点110的封包含有目标节点110充当进入节点110、主要 流量跟踪器节点110或次要流量跟踪器节点110的TCP流的条目。 注意在一些实施方案中给定负载平衡器节点110可充当TCP流的进 入和主要流量跟踪器节点，或作为TCP流的进入和次要流量跟踪器 节点。

图22示出根据至少一些实施方案的将在连接发布封包中接收的 活动连接信息分配至目标负载平衡器节点110的替代方法。如550指 示，负载平衡器节点110接收来自负载平衡器模块132的连接发布封 包。在此方法中，如552指示，负载平衡器模块110上的过程分析封 包中的连接发布条目并且相应地将所接收的封包划分成一个或多个 较小封包。在此过程期间，负载平衡器模块110不局部消耗此流信息。 一旦连接发布封包划分成一个或多个封包，封包然后如554-560指示 来处理。在554处，如果封包的目标节点110是此负载平衡器节点 110，那么负载平衡器节点110局部消耗封包，如556指示。否则， 封包发送至目标负载平衡器节点110。在560处，如果存在将要处理 的更多封包，那么方法返回到554。否则，方法完成。

因此，接收来自负载平衡器模块132的连接发布封包的负载平衡 器节点110可将连接发布封包划分成对于其他负载平衡器节点110中 的具体节点来说特定的两个或更多个较小封包并且相应地分配封包， 同时在内部消耗当前由负载平衡器节点110操控的任何TCP流的流 信息。在此期间，其他负载平衡器节点110还可接收来自负载平衡器 模块132的连接发布封包，将连接发布条目划分成多个较小封包，并 且将较小封包发送至目标节点110，由此将活动连接信息在节点110 之间分配。

连接发布触发

在至少一些实施方案中，连接发布可在负载平衡器模块132上通 过一个或多个不同事件来触发。如以前提及，在一些实施方案中，可 根据连接发布间隔，例如100ms或一秒间隔来产生连接发布封包并 且将其发送至随机选择负载平衡器节点110，以恢复负载平衡器节点 110上的TCP连接的租约。在一些实施方案中，负载平衡器节点110 的成员关系变化可触发立即连接发布事件。在至少一些实施方案中， 负载平衡器模块132可从健康负载平衡器节点110列表获知变化，所 述列表从对于相应服务器节点130进行健康检查的负载平衡器节点 110中的一个发送。在根据列表检测到变化(缺失或添加)后，负载平 衡器模块132可产生连接发布封包并且发送至负载平衡器节点110以 使得受变化影响的TCP连接可由负载平衡器节点110更迅速地恢复。

防止封包环

如果在处理连接发布封包时负载平衡器层成员关系变化，可发生 连接发布封包循环。第一节点110可接收来自负载平衡器模块132的 连接发布封包并且将较小封包发送至第二节点110。然而，如果成员 关系改变，第二节点110可确定封包应转到第一节点110，并且可由 此将封包转发至第一节点110。在至少一些实施方案中，为了防止此 循环发生，不同端口编号可用于从负载平衡器模块132接收的连接发 布封包和从负载平衡器节点110接收的那些封包，并且负载平衡器节 点110不重新分布从其他负载平衡器节点110接收的连接发布封包。

连接发布封包分布替代方案

在如上所述的连接发布方法中，负载平衡器模块132随机选择接 收连接发布封包的负载平衡器节点110。然而，在一些实施方案中， 其他方法可用于选择负载平衡器节点110。举例来说，在一些实施方 案中，负载平衡器节点132可构建各自靶向操控一个或多个活动TCP 流的具体进入节点110的一个或多个连接发布封包，并且将封包发送 至目标进入节点110。进入节点110然后将活动连接信息重新分布至 这些连接的主要和次要流量跟踪器。作为另一个实例，在一些实施方 案中，代替将连接发布封包发送至单一、随机选择节点110，每个连 接发布封包可由负载平衡器模块132发送至两个或更多个健康节点 110，或所有健康节点110。

负载平衡器节点架构

图23示出根据至少一些实施方案的负载平衡器节点110的示例 性软件堆栈架构，并且不意欲具有限制性。在此示例性软件堆栈架构 中，负载平衡器节点110在单一Java^TM技术过程1102中运作，所述 过程使用Java原生接口(JNI^TM)1104技术以管理原生代码层，其可包 括负载平衡器服务器原生代码1106和核心封包处理代码1108，例如 Intel^TM数据平面开发工具包(DPDK)技术代码。原生代码可介接至两 个网络接口控制器(NIC1114A和1114B)。第一NIC(NIC1114A)可朝 “北”；也就是说，朝向边缘路由器104。第二NIC(NIC1114B)可朝“南”； 也就是说，朝向服务器节点130。在至少一些实施方案中，NIC1114A 和1114B可不保持TCP堆栈。因此，至少一些实施方案可包括支持 TCP连接的第三NIC1114C以使得负载平衡器节点110可经由控制平 面与过程通信，并且反之亦然。或者，在一些实施方案中，仅第一、 朝北NIC1114A和第二、朝南NIC111B可实施于负载平衡器节点110 中，并且第二、朝南NIC1114B可实施TCP，负载平衡器节点110 可通过所述堆栈经由控制平面来与过程通信。除了OS技术软件1112 和JNI1104技术以外，负载平衡器节点110还包括操作系统(OS)技术 软件1112，例如Linux^TM内核，和Java虚拟机(JVM^TM)技术软件1110 层。

在至少一些实施方案中，分布负载平衡系统中的负载平衡器节点 110可各自需要同时以较高封包速率处理许多数据流。在至少一些实 施方案中，为了获得所需通量水平，负载平衡器节点110可利用Intel^TM数据平面发展工具包(DPDK)技术以便高效能封包处理。DPDK技术 允许用户空间程序直接向网络接口控制器(NIC)读取/写入封包并且 绕过许多Linux内核连网堆栈层(除了Linusixgbe基础NIC驱动器以 外)。DPDK封包处理方法拒绝有利于专门CPU核心的基于中断处理 程序的输入，所述核心在忙循环中直接轮询NIC硬件。此方法可允 许高得多的封包速率，以在忙循环中连续运行专门CPU核心而导致 热输出增加为代价。DPDK技术还可提供封包处理工具，包括CPU 核心管理、无锁队列、存储器池和同步基元。如图24示出，在DPDK 技术中，专门CPU核心600可用于每个具体任务，并且使用非阻断 队列602将工作从一个CPU核心600A传递至另一个CPU核心600B。

DPDK队列602可使用快速2次幂循环缓冲器来实施，并且可支 持单一和多个生产者/消耗者变体。多个生产者/消耗者变体并非真实 无锁，因为其含有比较并交换(CAS)循环以使访问同步。所有封包缓 冲存储器可预分配至存储器池，以使得仅缓冲器的指针读取并写入队 列602。存储器池可实施为队列，可优化以将存储器分配于存储器通 道和秩，并且可支持非均匀存储器访问(NUMA)优化分配。在至少一 些实施方案中，封包缓冲器可使用将足够净空间和尾空间在每个封包 缓冲器中过度分配以支持封装/解封操作的方法例如Mbuf范式，所述 操作可添加/移除外部网络层报头而不需要缓冲器复本。

在负载平衡器节点110的至少一些实施方案中，可实施利用 DPDK技术的核心封包处理架构。每个负载平衡器节点110可包括根 据核心封包处理架构实施的至少一个多核心封包处理器。核心封包处 理架构可经由多核心封包处理器的队列和核心来使用封包流的单一 生产者/单一消耗者范式。在此范式中，每个队列向唯一的一个核心 输入，并且每个核心对于其馈送封包的每个其他核心来说向唯一的一 个核心输出。另外，由多核心封包处理器中的核心使用的存储器并非 共用；每个核心具有其自身、单独存储区域。因此，在核心之间没有 存储器或队列共用，没有存储器或队列竞争，并且不需要存储器或队 列共用机制如所有权请求(RFO)或比较并交换(CAS)。图25和26示 出根据核心封包处理架构的实施的示例性多核心封包处理器。

图25示出根据至少一些实施方案的根据核心封包处理架构实施 的利用DPDK技术来处理数据流的示例性多核心封包处理器。核心 封包处理架构可实施为根据单一生产者/单一消耗者范式的多核心封 包处理器。在至少一些实施方案中，如图23示出，负载平衡器节点 110各自具有两个网络接口控制器(NIC)-朝向边界网络/边缘路由器 104的朝北NIC1114A和朝向产生网络/服务器节点130的朝南NIC 1114B。在至少一些实施方案中，NIC1114可为10GpbsNIC。流经负 载平衡器节点110的大部分封包接收于这两个NIC中的一个(NIC 1114A或1114B)、处理(例如，封装或解封)，并且从另一个NIC(NIC 1114B或1114A)传输出来。

参看图25，在至少一些实施方案中，对于每个NIC1114，负载 平衡器节点110热启动两个CPU核心，接收(RX)核心610和传输(TX) 核心630。负载平衡器节点110还热启动在两个方向上处理两个NIC 1114的封包的若干工作核心620；在此实例中使用四个工作核心620A 至620D。在来自其输入队列的多批次传入封包到达NIC1114时，接 收核心610对其进行读取并且将封包分配至对于每个封包执行大部 分工作的工作核心620，并且每个接收核心610将封包馈给至每个工 作核心620的相应工作输入队列612。在至少一些实施方案中，接收 核心610可对于每个传入封包执行层4“流量哈希”技术(类似于如前所 述可由边缘路由器104使用的每流哈希多路径路由技术)以将封包分 配至工作核心620，同时确保任何具体客户端连接(由其IP地址和端 口区分)由同一工作核心620处理。这意味着每个工作核心620可总 是发现封包的同一子集，并且消除对于由工作核心620管理的状态数 据的竞争以使得不需要锁定。所接收封包的指针可分布于工作核心 620针对新的输入来连续监测的工作队列622上。工作核心620负责 管理每个连接的状态(例如所指定服务器节点130)，并且可在将封包 转发至其外出队列632中的一个之前对于封包执行UDP封装或解封。 传输核心630通过工作核心620外出队列632循环并且在输出封包出 现于队列632上时将其写入其相应NIC1114。

图26示出根据至少一些实施方案的根据核心封包处理架构实施 的利用DPDK技术来处理数据流的另一个示例性多核心封包处理器。 核心封包处理架构可实施为根据单一生产者/单一消耗者范式的多核 心封包处理器。在至少一些实施方案中，除了处理高通量客户端TCP 流以外，负载平衡器节点110上的DPDK核心架构还可用于针对其 他协议如ARP、DHCP和BGP在朝北和朝南NIC1114上发送并接收 封包。在图26示出的实施方案中，工作核心620A专用于操控这些 其他协议的封包。此工作核心620A可被称为“缓慢”工作核心，因为 处理这些封包总体上以比客户端TCP流慢的速率发生，同时只处理 客户端TCP流的其他工作核心620B-620D可被称为快速工作核心。 分别操控朝北和朝南NIC1114上的传入封包的接收核心610A和 610B可识别由缓慢工作核心620A操控的封包并且将封包引导至缓 慢工作核心620A的输入队列622。缓慢工作核心620A还可针对由 Java/JNI产生的封包来监测输入队列622，并且针对Java/JNI的输出 封包来监测输出队列634。缓慢工作核心620A还向快速工作核心 620B至620D中的每一个的输入队列622输出以使得缓慢工作核心 620A可将封包发送至快速工作核心620B至620D中的每一个，例如 连接发布封包。缓慢工作核心620A还具有馈给至传输核心630A和 630B中每一个的外出队列632。

在至少一些实施方案中，每个快速工作核心620B至620D的第 三输入队列622是来自缓慢工作核心620A的输出队列。在至少一些 实施方案中，此第三输入队列622可例如用于通过快速工作队列620B 至620D来接收并处理连接发布封包，其各自含有连接状态信息。对 于这些连接发布封包中的至少一些，可能没有至传输核心630的输 出。替代地，连接状态信息封包可由快速工作核心620，例如通过更 新相应快速工作核心620保持的一个或多个封包流的存储状态来消 耗。因此，来自缓慢工作核心620A的向快速工作核心620B至620D 输入的输出队列可提供除了直接来自接收核心610的输入队列622以 外的路径以便更新快速工作核心的存储状态。

在至少一些实施方案中，图25和26的多核心封包处理器可过滤 传入封包并且只处理并输出有效的封包。举例来说，在至少一些实施 方案中，接收核心610可滤出涉及不由任何工作核心620支持的协议 并且由此不向工作核心620发送封包的封包。在至少一些实施方案 中，工作核心620，在处理封包时，可每一个首先分析从其相应工作 输入队列622读取的封包以确定是否封包对于进一步处理并输出至 传输核心630是可接受的，并且可只完成可接受的封包处理和输出至 传输核心630；不可接受的封包可予以丢弃。举例来说，工作核心620 可观察每个封包的地址信息并且只接受针对正在负载平衡的有效地 址的封包，丢弃任何其他封包。

操控边界网关协议(BGP)数据

在至少一些实施方案中，进进出出核心架构的与BGP客户端相 关联的封包流可操控如下。由于NIC1114A和1114B未结合至Linux 内核，因此至边缘路由器104的TCP连接由如图26示出的核心架构 截取并且由缓慢工作核心622A处理，所述核心将BGP封包经由输 出队列634传递至Java空间。这些TCP封包在递送至BGP客户端之 前进一步由负载平衡器节点110上的一个或多个模块处理，包括由 Linux内核处理以管理TCP连接并且将封包有效地翻译至TCP流。 此设计允许BGP客户端使用标准JavaTCP套接字库来编写。

图27示出根据至少一些实施方案的通过负载平衡器(LB)节点过 程650对传入BGPTCP封包的处理。来自边缘路由器104的封包到 达朝北NIC640并且进入接收核心652的输入队列640。接收核心652 读取来自队列640的封包，将封包识别为BGP封包，并且将封包放 置于缓慢工作核心656的输入队列654上。缓慢工作核心656验证封 包并且将它放置在JNI输出队列658上。JNI封包接收器660经由JNI 读取来自队列658的封包，改编来源/目的地地址，并且将封包写入 原始套接644。Linux内核646接收原始封包，根据TCP协议来操控 它，并且将有效负载数据追加至TCP套接输入流。然后，来自封包 的数据递送至BGP客户端662中的JavaTCP套接。

图28示出根据至少一些实施方案的通过负载平衡器(LB)节点过 程650对传出BGPTCP封包的处理。BGP客户端662将数据写入 Linux内核646的JavaTCP套接。Linux内核646根据TCP协议来操 控数据并且将数据转化成TCP封包。在至少一些实施方案中，TCP 封包匹配127.x.x.xiptables规则。TCP封包安置于输出队列648中， 例如NetfilterLOCAL_OUT队列。经由JNI监测队列648的JNI封包 接收器670的Java线程接收TCP封包并且将每个标记NF_STOLEN 以使得内核646不考虑其。Java线程改编来源/目的地地址并且将封 包经由JNI添加至缓慢工作核心656的JNI输入队列672。缓慢工作 核心656接收来自其JNI输入队列672的TCP封包并且将封包放置 于朝北NIC640传输核心666的外出队列664上。传输核心666读取 来自其输入队列664的TCP封包并且将其写入朝北NIC640。TCP 封包由NIC640发送至边缘路由器104。

分布负载平衡器摸拟和测试

本文描述的负载平衡器是分布式系统，其需要许多独立部件(例 如，路由器、负载平衡器节点、负载平衡器模块等)的相互作用。为 了执行分布部件、逻辑和协议的测试，以及模拟场景如节点失效、消 息丢弃和延迟，描述使得分布负载平衡器能够在单一过程中运行的测 试系统的实施方案，其中可在不需要将代码部署至复杂网络拓扑(例 如，生产网络)中的多个主机的情况下测试相互作用。为了完成此举， 描述使得多个负载平衡器部件能够在单一过程中或作为单一过程来 配置并执行的被称为消息总线的软件机制；单一过程可执行于单一主 机系统上。消息总线机制允许分布负载平衡器系统作为单一过程例如 在单一主机系统上测试，同时对于负载平衡器部件(例如，负载平衡 器节点和负载平衡器模块)来说，似乎其运行于实际生产网络中。

消息总线提供允许分布负载平衡器作为单一过程运行的框架。此 过程中的一个或多个消息总线层中的每一个模拟分布负载平衡器的 部件之间的网络(例如，以太网)区段。分布负载平衡器系统的软件部 件不需要以特殊方式编写以允许部件在消息总线环境内操作。替代 地，消息总线框架提供部件(可被称为消息总线NIC或封包适配器)， 所述部件截取分布负载平衡器系统的部件所产生的封包，将封包引导 至由消息总线层提供的模拟网络而非实际物理网络，并且将封包递送 至目标部件。对于部件之间的通信，消息总线层不实施TCP/IP堆栈。 替代地，消息总线层与主机系统的操作系统(OS)介接并且使用主机系 统的TCP/IP堆栈。消息总线层利用由OS提供的TCP/IP堆栈以将客 户端和服务器期待的TCP流转化成消息总线截取并递送的个别封包 并且将所述封包转化成TCP流。

在至少一些实施方案中，为了与消息总线介接，负载平衡器部件 可具备分别具有有效媒体访问控制(MAC)地址的至少一个消息总线 网络接口控制器(NIC)，其将封包发送至消息总线模拟网络环境并且 接收来自所述环境的封包而非将封包发送至物理网络和接收来自物 理网络的封包。消息总线NIC是连接至消息总线而非物理网络的虚 拟网络接口控制器。需要经由消息总线通信的每个负载平衡器部件需 要至少一个消息总线NIC。消息总线NIC充当消息总线的管线出口 和部件的管线入口。组件可体现每个消息总线NIC的多个消息总线 网络接口。

消息总线网络接口是使部件经由消息总线NIC连接至消息总线 的机制。消息总线网络接口可与Linux技术中的接口配置(ifconfig)接 口同义，差异为消息总线网络接口连接至消息总线而非物理网络。消 息总线网络接口具有IP地址，并且坐落于消息总线NIC顶端。消息 总线网络接口暴露可由部件使用来接收来自消息总线的封包的封包 来源接口，和可由部件使用来将封包发送至消息总线的封包接收器接 口。

每个负载平衡器节点处理经由封包来源和封包接收器接口的实 行方案来递送并发送的个别网络封包。当在消息总线环境中运行时， 这些接口由添加或移除层2以太网报头的消息总线网络接口来实施 (对于预期此举由内核网络堆栈执行的负载平衡器节点来说)。在如图 29示出的生产环境中，封包来源和封包接收器接口的实行方案在实 际网络接口上接收并传输封包。在如图30示出的消息总线环境中， 实行方案封包来源和封包接收器接口接收来自一个或多个消息总线 层的封包并且将封包传输至所述层。

为了简单起见，消息总线NIC和消息汇流排介面可共同地被称 为消息总线封包适配器，或简称为封包适配器。参见例如图31和32。

图29示出根据至少一些实施方案的包括生产环境中的分布负载 平衡器700的负载平衡系统。负载平衡器700已经对于此描述加以简 化。负载平衡器700可经由实施负载平衡器700的网络设备如数据中 心的边界路由器702来连接至外部网络740上的客户端742。负载平 衡器700包括多个类型部件-至少一个边缘路由器704，两个或更多 个负载平衡器(LB)节点710，分别实施于单独服务器节点(未展示)上 的两个或更多个负载平衡器(LB)模块732，形成结构720如路由器或 开关的一个或多个连网部件，以及在至少一些实施方案中配置服务 722。在至少一些实施方案中，负载平衡器700的每个部件可作为单 独计算装置或在单独计算装置上实施，例如商用机架安装计算装置。

图30示出根据至少一些实施方案的分布负载平衡器测试系统 800，其并入消息总线机构，所述机构使得多个分布负载平衡系统部 件能够配置并执行于单一过程中或作为单一过程。在图29示出的负 载平衡器700中，每个负载平衡器软件部件安装并执行于单独计算装 置上(例如，负载平衡器节点710上的负载平衡器软件，和服务器节 点上的负载平衡器模块732)。为了使得这些负载平衡器软件部件能够 在单一过程中执行，每个负载平衡器软件部件(在图30中展示为负载 平衡器(LB)节点810和负载平衡器(LB)模块832)可包括代码，所述代 码提取部件的网络连接性以使得进进出出负载平衡器软件部件的封 包也可被截取并且经由消息总线机制来依路由传递而非发送并接收 于物理网络中。

在至少一些实施方案中，在分布负载平衡器测试系统800中，消 息总线机制对于部件之间的通信不实施TCP堆栈。替代地，消息总 线机制与主机系统的操作系统(OS)介接并且使用主机系统的TCP堆 栈。在至少一些实施方案中，消息总线功能经由作为内核的功能的IP 表来关联至主机系统的OS在用户层下方的内核(例如，Linux内核)。 消息总线功能挂钩至内核水平的IP表，截取封包，并且将封包发送 至消息总线过程以便依路由传递。

如图30中的模拟边缘路由器862和模拟结构864示出，如同客 户端860、服务器834和配置服务866，物理网络部件(例如，图29 的边缘路由器704和结构720)的功能可在软件中模拟。然而，应注意， 在至少一些实施方案中实际而非模拟服务器834可在分布负载平衡 器测试系统800中使用。图30中的消息总线层850取代物理网络基 础设施。因此，负载平衡器软件部件(负载平衡器节点810和负载平 衡器模块832)可在负载平衡器测试系统800中运行，同时不知道其并 未在如图29示出的生产网络环境中执行。

一些部件(例如，模拟路由器)可连接至一个以上消息总线层850 以便将封包传递至模拟网络区段的不同消息总线层850并且接收来 自所述层的封包。

在分布负载平衡试验系统800的消息总线层850中实施的消息总 线机制模拟网络区段的“导线”。在至少一些实施方案中，消息总线机 制基于部件的MAC地址将封包递送至分布负载平衡试验系统800中 的目的地部件。因此，每个负载平衡器软件部件(负载平衡器节点810 和负载平衡器模块832)将MAC地址提供至其连接的消息总线层850 以使得负载平衡器软件部件可接收从分布负载平衡试验系统800中 的其他部件向它发送的封包。

消息总线封包适配器

图31和32示出根据至少一些实施方案的消息总线封包适配器。 在至少一些实施方案中，每个负载平衡器(LB)软件部件处理经由封包 来源和封包接收器接口的实行方案递送并发送的个别网络封包。参看 图31，当在分布负载平衡试验系统800中运行时，这些接口(展示为 封包来源接口862和封包接收器接口864)可通过消息总线层850与负 载平衡器软件部件870之间的封包适配器860来实施，所述适配器针 对预期此举由内核网络堆栈执行的负载平衡器软件部件870来添加 或移除层2以太网报头。在如图29示出的生产环境中，负载平衡器 软件部件的封包来源和封包接收器的实行方案在部件实施于其上的 物理装置的实际网络接口上接收并传输封包。

参看图31，在至少一些实施方案中，在负载平衡器软件部件870 传输封包时，调用封包接收器接口864的发送封包方法的执行线程横 穿封包适配器860以及消息总线层850内的功能链以便通过将封包添 加至部件的输入队列来最终将封包递送至目的地部件。在至少一些实 施方案中，当负载平衡器软件部件870接收封包时，负载平衡器软件 部件870调用封包来源接口862的接收封包方法并且从其输入队列读 取封包。在至少一些实施方案中，消息总线机制不需要其自身的任何 额外线程来递送封包。

消息总线封包管线

参看图32，在至少一些实施方案中，封包来源接口862和封包 接收器接口864的消息总线850侧提供封包管线特征。当负载平衡器 软件部件870经由封包接收器接口864发送封包时，封包数据在到达 消息总线层850之前可横穿一系列阶段(封包管线880)。这些阶段可 修改封包、丢弃封包、复制封包、延迟封包等。一旦封包横穿封包管 线880并且消息总线层850选择目的地部件870，在将封包添加至目 的地部件870的输入队列之前，还可横穿与目的地部件870相关联的 第二系列管线阶段(封包管线882)。

示例性提供者网络环境

这部分描述分布负载平衡方法和装置的实施方案可实施于其中 的示例性提供者网络环境。然而，这些示例性提供者网络环境不意欲 具有限制性。

图33A示出根据至少一些实施方案的示例性提供者网络环境。 提供者网络1900可经由一个或多个虚拟化服务1910为客户端提供资 源虚拟化，所述虚拟化服务允许客户端访问、购买、租用或另外获得 在一个或多个数据中心中的一个或多个提供者网络内的装置上实施 的虚拟化资源的实例1912，包括但不限于计算和存储资源。私用IP 地址1916可与资源实例1912相关联；私用IP地址是提供者网络1900 上的资源实例1912的内部网络地址。在一些实施方案中，提供者网 络1900还可提供客户端可从提供者1900获得的公共IP地址1914和 /或公共IP地址范围(例如，互联网协议版本4(IPv4)或互联网协议版 本6(IPv6)地址)。

通常，提供者网络1900，经由虚拟化服务1910，可允许服务提 供者的客户端(例如，操作客户端网络1950A的客户端)将分配或分派 至客户端的至少一些公共IP地址1914与分配至客户端的具体资源实 例1912动态地相关联。提供者网络1900还可允许客户端将以前映射 至分配至客户端的一个虚拟化计算资源实例1912的公共IP地址1914 重新映射至也分配至客户端的另一个虚拟化计算资源实例1912。使 用由服务提供者提供的虚拟化计算资源实例1912和公共IP地址 1914，服务提供者的客户端如客户端网络1950A的操作者可，例如， 在中间网络1940如互联网上实施客户端特定应用程序并且呈现客户 端的应用程序。然后，中间网络1940上的其他网络实体1920可产生 流量以传递至由客户端网络1950A发布的目的地公共IP地址1914； 流量依路由传递至服务提供者数据中心，并且在数据中心经由网络底 层依路由传递至当前映射至目的地公共IP地址1914的虚拟化计算资 源实例1912的私用IP地址1916。类似地，来自虚拟化计算资源实例 1912的响应流量可经由网络底层依路由传递回到中间网络1940直至 来源实体1920。

如本文使用，私用IP地址是指提供者网络中的资源实例的内部 网络地址。私用IP地址只可在提供者网络内依路由传递。源于提供 者网络外部的网络流量不直接依路由传递至私用IP地址；替代地， 流量使用映射至资源实例的公共IP地址。提供者网络可包括提供网 络地址翻译(NAT)或类似功能以执行公共IP地址至私用IP地址的映 射和反之亦然的网络装置或设备。

如本文使用，公众IP地址是由服务提供者或客户端分配至资源 实例的互联网可依路由传递网络地址。依路由传递至公共IP地址的 流量例如经由1：1网络地址翻译(NAT)来翻译，并且转发至资源实例 的相应私用IP地址。

一些公共IP地址可由提供者网络基础设施分配至具体资源实例； 这些公共IP地址可被称为标准公共IP地址，或简称为标准IP地址。 在至少一些实施方案中，将标准IP地址映射至私用IP地址资源实例 是所有资源实例类型的默认启动配置。

至少一些公共IP地址可分派至提供者网络1900的客户端或由所 述客户端获得；客户端可然后其所分派公共IP地址分配至分派至客 户端的具体资源实例。这些公共IP地址可被称为客户端公共IP地址， 或简称为客户端IP地址。代替如在标准IP地址的情况下，由提供者 网络1900分配至资源实例，客户端IP地址可通过客户端，例如经由 服务提供者提供的API来分配至资源实例。不同于标准IP地址，客 户端IP地址分派至客户端帐户并且在必要或需要时可由相应客户端 重新映射至其他资源实例。客户端IP地址与客户端的帐户，而非具 体资源实例的相关联，并且客户端控制此IP地址直到客户端选择释 放它为止。不同于常规静态IP地址，客户端IP地址允许客户端通过 将客户端的公共IP地址重新映射至与客户端帐户相关联的任何资源 实例来掩蔽资源实例或可用性区域失效。客户端IP地址，例如，使 得客户端能够通过将客户端IP地址重新映射至替代资源实例来精明 地处理客户端的资源实例或软件的问题。

图33B示出根据至少一些实施方案的如图33A展示的示例性提 供者网络环境中的分布负载平衡器实行方案。提供者网络1900可向 客户端1960提供服务1910，例如虚拟化存储服务。客户端1960可 例如经由服务1910的一个或多个API来访问服务1910，以获得在提 供者网络1900的生产网络部分中的多个服务器节点1990中实施的资 源(例如，存储资源或计算资源)的使用。服务器节点1990可分别实 施服务器(未展示)，例如网络服务器或应用程序服务器，以及局部负 荷平衡器(LB)模块1992。一个或多个分布负载平衡器1980可实施于 边界网络与生产网络之间的负载平衡器层中。边界路由器1970可经 由中间网络1940如互联网来接收来自客户端1960的封包流中的封包 (例如，TCP封包)，并且经由边界网络将封包转发至分布负载平衡器 1980的边缘路由器。封包可靶向由分布负载平衡器1980的边缘路由 器发布的公共IP地址。每个分布负载平衡器1980的边缘路由器可将 封包流在相应分布负载平衡器1980的负载平衡器节点之间分配。在 至少一些实施方案中，充当进入节点的每个负载平衡器节点将同一公 共IP地址公布至边缘路由器，并且边缘路由器根据每流哈希多路径 路由技术，例如等价多路径(ECMP)哈希技术将来自客户端1960的封 包流在进入服务器之间分布。负载平衡器节点可使用本文描述的连接 协议来确定封包流的目标服务器节点1990和促进服务器与客户端 1960之间的连接。一旦连接建立，进入节点将对于此流所接收的封 包封装并发送至生产网络上的目标服务器节点1990，同时流量跟踪 器节点保持连接的状态。服务器节点1990上的负载平衡器模块1992 可作出关于是否服务器节点1960上的相应服务器接受连接的决定。 负载平衡器模块接收并且解封来自进入节点的封包，并且将解封封包 (例如，TCP封包)发送至服务器节点1990上的相应服务器。负载平 衡器模块1992还可选择作为封包流的外出节点的负载平衡器节点， 并且封装这些流的传出封包并且将其经由生产网络发送至选定外出 节点。外出节点进而将封包解封并且将解封封包发送至边界网络上以 递送至相应客户端1960。

图34A示出根据至少一些实施方案的分布负载平衡器和服务器 节点的示例性物理机架实行方案并且不意欲具有限制性。在至少一些 实施方案中，分布负载平衡器的各种部件可实施于商用机架安装计算 装置上或作为所述装置来实施。机架190可包括分别充当负载平衡器 节点(LB节点110A-110F)的多个计算装置，和分别充当服务器节点(服 务器节点130A-130L)的多个计算装置。机架190还可包括至少一个 边缘路由器104，形成结构120的一个或多个机架安装连网装置(路由 器、交换机等)，和一个或多个其他部件180(其他连网装置、插线面 板、电源、冷却系统、总线等)。实施图33A和33B的提供者网络1900 的网络100设备如一个或多个数据中心可包括一个或多个机架190。

图34B示出根据至少一些实施方案的分布负载平衡器和服务器 节点的另一个示例性物理机架实行方案并且不意欲具有限制性。图 34B示出在机架190中实施为插槽安装计算装置，例如刀片服务器的 LB节点110和服务器节点130。

图35示出根据至少一些实施方案的一个、两个或更多个分布负 载平衡器可实施于网络中的示例性连网环境，其中服务器节点单独实 施。在此实施例中，示出两个分布负载平衡器1980A和1980B。分布 负载平衡器1980分别可经由边界网络接收来自客户端1960的封包流 并且执行本文描述的负载平衡方法以将封包流分配于多个服务器节 点1990上。在一些实行方案中，每个分布负载平衡器1980可为类似 于图34A和34B示出的机架190的机架实行方案，但是没有安装于 负载平衡器机架中的服务器节点。服务器节点1990可为安装于数据 中心内的一个或多个分离机架中的机架安装计算装置如刀片服务器。 在一些实行方案中，服务器节点1990可实施由提供者网络提供的两 个或更多个不同服务，并且在每个服务的前面是负载平衡器1980中 的不同一个或多个。

说明性系统

在至少一些实施方案中，实施如本文描述的分布负载平衡方法和 装置的一部分或全部的服务器可包括包含或被配置来访问一个或多 个计算机可访问介质的通用计算机系统，如图36示出的计算机系统 2000。在示出的实施方案中，计算机系统2000包括经由输入/输出(I/O) 接口2030耦接至系统存储器2020的一个或多个处理器2010。计算 机系统2000还包括耦接到I/O接口2030的网络接口2040。

在各种实施方案中，计算机系统2000可为包括一个处理器2010 的单一处理器系统，或包括若干处理器2010(例如两个、四个、八个 或另一合适数量)的多处理器系统。处理器2010可为能够执行指令的 任何合适处理器。例如，在各种实施方案中，处理器2010可为实施 各种指令集架构(ISA)中任何一种架构的通用或嵌入式处理器，所述 架构例如x86、PowerPC、SPARC、或MIPSISA或任何其他合适ISA。 在多处理器系统中，每一个处理器2010可通常但不一定实施相同的 ISA。

系统存储器2020可以被配置来存储可由处理器2010访问的指令 和数据。在各种实施方案中，系统存储器2020可使用任何合适存储 器技术来实施，所述存储器技术例如静态随机存取存储器(SRAM)、 同步动态RAM(SDRAM)、非易失性/快闪型存储器或任何其他类型的 存储器。在示出的实施方案中，实施一个或多个所需功能的程序指令 和数据(如上述用于分布负载平衡方法和装置的那些方法、技术以及 数据)被示出作为代码2024和数据2026存储在系统存储器2020内。

在一个实施方案中，I/O接口2030可被配置来协调处理器2010、 系统存储器2020和装置中的任何外围装置之间的I/O流量，所述外 围装置包括网络接口2040或其他外围接口。在一些实施方案中，I/O 接口2030可执行任何必需协议、时序或其他数据转换以便将来自一 个部件(例如，系统存储器2020)的数据信号转换成适合于由另一个部 件(例如，处理器2010)使用的格式。在一些实施方案中，I/O接口2030 可包括对于通过各种类型的外围总线附接的装置的支持，所述外围总 线例如外围组件互连(PCI)总线标准或通用串行总线(USB)标准的变 化形式。在一些实施方案中，I/O接口2030的功能可分成两个或更多 个单独的部件中，例如北桥和南桥。另外，在一些实施方案中，I/O 接口2030的一些或所有功能，例如至系统存储器2020的接口，可直 接并入处理器2010中。

网络接口2040可以被配置来允许数据在计算机系统2000与附接 到一个或多个网络2050的其他装置2060(例如像图1至35中所示的 其他计算机系统或装置)之间进行交换。在各个实施方案中，网络接 口2040可以支持经由任何合适的有线或无线通用数据网络(例如像以 太网网络类型)进行通信。另外，网络接口2040可以支持经由电信/ 电话网络(如模拟语音网络或数字光纤通信网络)、经由存储区域网络 (如光纤信道SAN)或经由任何其他合适类型的网络和/或协议进行通 信。

在一些实施方案中，系统存储器2020可为被配置来存储如上对 于图1至35所述用于实施分布负载平衡系统的实施方案的程序指令 和数据的计算机可访问介质的一个实施方案。然而，在其他实施方案 中，可以在不同类型的计算机可访问介质上接收、发送或存储程序指 令和/或数据。一般来说，计算机可访问的介质可包括非临时性的存 储介质或存储器介质，例如磁性介质或光学介质，例如经由I/O接口 2030耦接至计算机系统2000的磁盘或DVD/CD。非暂时性计算机可 访问存储介质还可以包括可作为系统存储器2020或另一类型的存储 器被包括在计算机系统2000的一些实施方案中的任何易失性或非易 失性介质，如RAM(例如，SDRAM、DDRSDRAM、RDRAM、SRAM 等)、ROM等。另外，计算机可访问介质可以包括传输介质或信号， 诸如经由通信介质(网络和/或无线链路)传送的电信号、电磁信号或数 字信号，例如可以经由网络接口2040来实施。

本公开的实施方案可基于以下条款来描述：

1.一种分布负载平衡器系统，其包括：

多个负载平衡器节点，其中所述多个负载平衡器节点中的至少两 个被配置为进入服务器，并且其中所述多个负载平衡器节点中的至少 两个被配置为流量跟踪器节点；

多个服务器节点；和

路由器，其被配置来根据哈希多路径路由技术将来自一个或多个 客户端的封包流分布至所述进入服务器；

其中每一个进入服务器被配置来：

从所述路由器接收客户端的封包流中的封包；

确定所述进入服务器不具有所述封包流至所述多个服务器节点 的映射；

根据应用于所述封包的来源和目的地地址信息的一致哈希函数 来确定所述封包流的至少一个流量跟踪器节点；

从所述至少一个流量跟踪器节点获得至所述封包流的所述多个 服务器节点中的特定一个的连接的映射；并且

将所述封包流中的一个或多个封包发送至所述特定服务器节点。

2.如条款1中所述的分布负载平衡器系统，其中所述封包流为 传输控制协议(TCP)封包流。

3.如条款1中所述的分布负载平衡器系统，

其中所述多个负载平衡器节点中的至少两个被配置为外出服务 器，所述外出服务器被配置来将传出封包从所述服务器节点发送至所 述一个或多个客户端，

其中所述服务器节点被配置来：

选择所述外出服务器中的一个以用于所述封包流；并且

将所述封包流的一个或多个传出封包发送至所述所选择的外出 服务器；

其中所述外出服务器被配置来将所述传出封包发送至所述客户 端；并且

其中用于所述封包流的所述所选择的外出服务器是与用于所述 封包流的所述进入服务器不同的负载平衡器节点。

4.如条款3中所述的分布负载平衡器系统，其中所述进入服务 器在将所述封包发送至所述服务器节点之前根据用户数据报协议 (UDP)封装所述一个或多个封包，其中所述服务器节点在将所述传出 封包发送至所述外出服务器之前根据UDP封装所述传出封包，并且 其中所述外出服务器在将所述传出封包发送至所述客户端之前从所 述传出封包除去所述UDP封装。

5.如条款4中所述的分布负载平衡器系统，其中所述服务器节 点包括负载平衡器模块，所述负载平衡器模块被配置来：

选择所述外出服务器以用于所述封包流；

从所述进入服务器接收所述传入封装封包；

从所述封包除去所述UDP封装，并且将所述封包递送至所述服 务器节点上的服务器；

从所述服务器节点上的所述服务器获得所述传出封包；

根据UDP封装所述传出封包；并且

将所述封装传出封包发送至所述外出服务器。

6.如条款1中所述的分布负载平衡器系统，其中，为从所述至 少一个流量跟踪器节点获得至所述封包流的所述多个服务器节点中 的特定一个的连接的映射，

所述进入服务器将包括所述封包流的信息的消息发送至用于所 述封包流的主要流量跟踪器；

所述主要流量跟踪器将消息发送至用于所述封包流的次要流量 跟踪器，所述消息包括所述封包流的所述信息，其中用于所述封包流 的所述主要流量跟踪器和所述次要流量跟踪器是不同的负载平衡器 节点；

所述次要流量跟踪器将对所述封包流的确认发送至所述客户端；

所述进入服务器从所述客户端接收确认封包，并且将所述确认封 包转发至所述主要流量跟踪器；

所述主要流量跟踪器从所述多个服务器节点中随机地选择所述 特定服务器节点作为所述服务器节点来接收所述封包流，并且将消息 发送至指示所述特定服务器节点的所述次要流量跟踪器；

所述次要流量跟踪器编制同步消息，并且将所述所编制的同步消 息发送至所述特定服务器节点；

所述次要流量跟踪器从所述特定服务器节点接收用于所述封包 流的连接信息，并且将包括所述连接信息的消息发送至所述主要流量 跟踪器；并且

所述主要流量跟踪器将包括用于所述封包流的所述连接信息的 消息发送至所述进入服务器，其中所述连接信息将所述封包流映射至 所述特定服务器节点。

7.如条款6中所述的分布负载平衡器系统，其中所述服务器节 点包括负载平衡器模块，所述负载平衡器模块被配置来：

从所述次要流量跟踪器接收所述所编制的同步消息；

确定所述服务器节点上的服务器可接受连接；

根据所述所编制的同步消息产生同步封包，并且将所述同步封包 递送至所述服务器节点上的所述服务器；

截取通过所述服务器节点上的所述服务器产生的确认封包；并且

将包括所述连接信息的消息发送至所述次要流量跟踪器。

8.一种方法，其包括：

通过多个负载平衡器节点中的一个上的进入服务器执行：

接收客户端的封包流中的封包，其中所述封包从路由器接收，所 述路由器根据一致哈希函数将来自一个或多个客户端的封包流分布 至所述多个负载平衡器节点；

根据应用于所述封包的来源和目的地地址信息的一致哈希函数 来确定负载平衡器节点，所述负载平衡器节点充当所述封包流的流量 跟踪器节点；

从用于所述封包流的所述流量跟踪器节点获得至所述封包流的 多个服务器节点中的一个的连接的映射；并且

将所述封包流中的一个或多个封包发送至由所述映射指示的所 述服务器节点。

9.如条款8中所述的方法，其中所述封包流为传输控制协议 (TCP)封包流。

10.如条款8中所述的方法，其还包括所述进入服务器在所述将 所述封包流的所述一个或多个封包发送至所述服务器节点之前根据 用户数据报协议(UDP)封装所述封包。

11.如条款8中所述的方法，其还包括：

通过所述服务器节点选择所述多个负载平衡器节点中的一个作 为用于所述封包流的外出服务器，其中用于所述封包流的所述所选择 的外出服务器是处于与用于所述封包流的所述进入服务器不同的负 载平衡器节点上；

通过所述服务器节点将所述封包流的一个或多个传出封包发送 至所述所选择的外出服务器；并且

通过所述外出服务器将所述传出封包发送至所述封包流的所述 客户端。

12.如条款11中所述的方法，其还包括：

所述服务器节点在所述将所述传出封包发送至所述外出服务器 之前根据用户数据报协议(UDP)封装所述传出封包；并且

所述外出服务器在所述将所述传出封包发送至所述客户端之前 从所述传出封包除去所述UDP封装。

13.如条款8中所述的方法，其中所述流量跟踪器节点为用于所 述封包流的主要流量跟踪器节点，并且其中根据所述一致哈希函数的 一致哈希环中的下一个负载平衡器节点是用于所述封包流的次要流 量跟踪器节点。

14.如条款13中所述的方法，其中所述从用于所述封包流的所 述流量跟踪器节点获得至所述封包流的多个服务器节点中的一个的 连接的映射包括：

通过所述进入服务器将至少一个消息发送至用于所述封包流的 所述主要流量跟踪器节点，每一个消息包括从所述路由器接收的所述 封包流的封包；

通过所述主要流量跟踪器节点从所述多个服务器节点中选择用 于所述封包流的所述服务器节点；

通过所述主要流量跟踪器节点将包括所述所选择的服务器节点 的指示的封包流信息发送至所述次要流量跟踪器节点；

通过所述次要流量跟踪器节点、通过与所述服务器节点和所述客 户端通信来促进至用于所述封包流的所述所选择的服务器节点的所 述连接的建立；并且

通过所述次要流量跟踪器节点将用于所述封包流的连接信息经 由所述主要流量跟踪器节点发送至所述进入服务器，其中所述连接信 息将所述封包流映射至所述所选择的服务器节点。

15.如条款14中所述的方法，其中所述服务器节点包括负载平 衡器模块，其中所述通过与所述服务器节点和所述客户端通信来促进 至用于所述封包流的所述所选择的服务器节点的所述连接的建立包 括：

通过所述次要流量跟踪器节点将所编制的同步消息发送至所述 服务器节点上的所述负载平衡器模块；并且

通过所述服务器节点上的所述负载平衡器模块执行：

确定所述服务器节点上的服务器可接受连接；

根据所述所编制的同步消息产生同步封包；

将所述同步封包递送至所述服务器节点上的所述服务器；

截取通过所述服务器节点上的所述服务器产生的确认封包；并且

将包括所述连接信息的消息发送至所述次要流量跟踪器节点。

16.一种非暂态计算机可存取存储介质，其存储计算机可执行的 程序指令以在多个负载平衡器节点中的每一个上实现进入服务器和 流量跟踪器，每一个进入服务器被配置来：

接收客户端的封包流中的封包，其中所述封包从路由器接收，所 述路由器根据一致哈希函数将来自一个或多个客户端的封包流分布 至所述多个负载平衡器节点；

根据应用于所述封包的来源和目的地地址信息的一致哈希函数 来确定所述多个负载平衡器节点中的一个，其充当所述封包流的流量 跟踪器节点；

从用于所述封包流的所述流量跟踪器节点获得至所述封包流的 多个服务器节点中的一个的连接的映射；并且

将所述封包流中的一个或多个封包发送至由所述映射指示的所 述服务器节点。

17.如条款16中所述的非暂态计算机可存取存储介质，其中所 述程序指令还为计算机可执行的，以在所述负载平衡器节点中的每一 个上实现外出服务器并且在所述多个服务器节点中的每一个上实现 负载平衡器模块，每一个负载平衡器模块被配置来：

选择所述多个负载平衡器节点中的一个作为用于封包流的外出 服务器，其中用于所述封包流的所述所选择的外出服务器是处于与用 于所述封包流的进入服务器不同的负载平衡器节点上；并且

将所述封包流的一个或多个传出封包发送至所述所选择的外出 服务器；

其中每一个外出服务器被配置来将从负载平衡器模块接收的封 包流中的传出封包发送至所述封包流的客户端。

18.如条款17中所述的非暂态计算机可存取存储介质，

其中每一个进入服务器还被配置来在所述将所述封包流的所述 一个或多个封包发送至所述服务器节点之前根据用户数据报协议 (UDP)封装所述封包；

其中每一个负载平衡器模块还被配置来：

从接收自进入服务器的所述封包除去所述UDP封装，并且将所 述封包递送至所述相应服务器节点上的服务器；

从所述相应服务器节点上的所述服务器截取所述传出封包；并且

在所述将所述传出封包发送至外出服务器之前根据UDP封装所 述传出封包；

其中每一个外出服务器还被配置来在所述将所述传出封包发送 至所述封包流的所述客户端之前从所述传出封包除去所述UDP封 装。

19.如条款16中所述的非暂态计算机可存取存储介质，其中所 述流量跟踪器节点为用于所述封包流的主要流量跟踪器节点，并且其 中根据所述一致哈希函数的一致哈希环中的下一个负载平衡器节点 是用于所述封包流的次要流量跟踪器节点，并且其中，为从用于所述 封包流的所述流量跟踪器节点获得至所述封包流的多个服务器节点 中的一个的连接的映射：

所述进入服务器被配置来将至少一个消息发送至用于所述封包 流的所述主要流量跟踪器节点，每一个消息包括从所述路由器接收的 所述封包流的封包；

所述主要流量跟踪器节点被配置来：

从所述多个服务器节点中选择用于所述封包流的所述服务器节 点；并且

将包括所述所选择的服务器节点的指示的封包流信息发送至所 述次要流量跟踪器节点；

所述次要流量跟踪器节点被配置来：

通过与所述服务器节点和所述客户端通信来促进至用于所述封 包流的所述所选择的服务器节点的所述连接的建立：并且

将用于所述封包流的连接信息经由所述主要流量跟踪器节点发 送至所述进入服务器，其中所述连接信息将所述封包流映射至所述所 选择的服务器节点。

20.如条款19中所述的非暂态计算机可存取存储介质，其中所 述程序指令还为计算机可执行的，以在所述多个服务器节点中的每一 个上实现负载平衡器模块，并且其中，为通过与所述服务器节点和所 述客户端通信来促进至用于所述封包流的所述所选择的服务器节点 的所述连接的建立：

所述次要流量跟踪器节点被配置来将所编制的同步消息发送至 所述服务器节点上的所述负载平衡器模块；并且

所述服务器节点上的所述负载平衡器模块被配置来：

确定所述服务器节点上的服务器可接受连接；

根据所述所编制的同步消息产生同步封包；

将所述同步封包递送至所述服务器节点上的所述服务器；

截取通过所述服务器节点上的所述服务器产生的确认封包；并且

将包括所述连接信息的消息发送至所述次要流量跟踪器节点。

结论

各个实施方案可以还包括根据前面的描述实施的在计算机可访 问介质上接收、发送或存储指令和/或数据。一般来说，计算机可访 问介质可以包括存储介质或存储器介质(如磁性介质或光学介质，例 如磁盘或DVD/CD-ROM)、易失性或非易失性介质(如RAM(例如， SDRAM、DDR、RDRAM、SRAM等)、ROM等)以及传输介质或信 号(如经由通信介质(如网络和/或无线链路)传送的信号(如电信号、电 磁信号或数字信号))。

如在图中所示和本文所描述的各种方法表示方法的示例性实施 方案。所述方法可以在软件、硬件或其组合中实施。方法的顺序可以 改变，并且各个元素可以被添加、重新排序、组合、省略、修改等。

受益于本公开的本领域技术人员将清楚可进行各种修改和变化。 旨在包含所有这些修改和变化，并且相应地，以上描述应视为具有说 明性而非限制性意义。