一种基于通配规则的服务器动态负载均衡设计

夏仕俊

（国网上海市电力公司信息通信公司，上海 200120）

搜索引擎、Web网站、社交网络等大型的在线网站经常需要使用多台服务器以满足大量用户的并发访问，同时提高服务可靠性，对于这些网站来讲，负载均衡几乎是一种必不可少的技术。目前使用的负载均衡常使用使用的方案有：均等地转发客户端请求［1，2］；记录服务器状态，并根据服务器负载动态分配请求转发。这种负载均衡机制都增加了额外的硬件成本并缺少可定制性。

本文提出的优化方案可降低单一负载均衡设备的成本和复杂性，在不需要调整服务器的基础上，该方案允许网络拓扑的灵活性配置，其计算复杂度与客户端请求的数量成线性比例。

OpenFlow［3，4］作为高速网络下的流量转发解决方案，吸引了很多服务商的关注。OpenFlow最初的设计和实现使用一个单一的控制器来保证较低的复杂度。通过在控制器中运行的控制层程序，它可以控制交换机在高速数据层的基础上转发数据流量。通过运用OpenFlow，嵌入式服务系统［5］能够自适应地根据当前的网络和服务器负载分发客户端请求，该系统拦截每一个客户端请求的第一个数据包，匹配独立的独立转发规则，并将后续的数据包做响应转发。虽然嵌入式服务系统根据当前的负载状态提供了自适应的灵活性，但它扩展性有限，每一个客户端连接安装了转发规则程序的方案将带来其它开销及延迟。随着转发规则的增多，这种开销将越发严重。

本文设计的可扩展网络负载均衡器主动地收集服务器负载数据，并在转换器上自动生成配置通配规则，不需引入控制器的前提下实现应答高并发的客户端请求，重新分配网络负载也不复杂。这样使用的通配规则解决了两个问题：针对目标网络分配流量负载生成一组有效的规则集，以及保证在相同TCP连接下，经过规则变化调整，数据包可被传送至同一个服务器上。本文设计的负载均衡属于集中式控制程序，因此可确定其最优的通配规则［6］。在分发流量方面提供高转发速率，具备一定的灵活性，并且在不调整客户端或服务器的前提下，支持根据网络负载分配情况进行定制化设置。

1 方案介绍

如图1所示，数据中心由多台服务器和连接客户端的路由网关组成，每一台服务器对外提供相同服务。每一台服务器拥有独立IP，并被赋予处理客户端请求的权重比例。例如，图1中的初始配置S1，S2所占权重为1／4，S3服务器处理3／8的请求，S4处理1／8请求。客户端通过网关只需要访问一个对外IP以获取相应服务。负载均衡器根据权重客请求数据转发至目标的服务器时，会重写目标IP地址。同时通配规则更新模块会收集服务器的CPU使用率情况，动态更新转发规则中的服务器的处理请求比例。本节首先描述OpenFlow的特征；接着阐述生成通配规则的分隔算法，该算法用以平衡负载；然后解释该算法的优点；最后展示了实现该算法的原型系统。

图1 OpenFlow实现负载均衡架构

OpenFlow提供了一套与其它路由器交互控制程序的API接口，路由器仅包含一个加载了流表的转发层，一个流表中就包含了一系列定义某个数据流中的数据包如何转发的规则。这些规则可以配置与数据包头特定域相匹配的（例如MAC地址、IP地址等），并在匹配的数据包上执行特定行为（例如转发、重写、丢弃等）。规则也可设置超时属性，路由器在一段固定时间间隔后（硬超时）或一段指定的非活动时间间隔后（软超时）删除规则。当数据流中的包头无法匹配相应规则，这个数据包头信息就会发给通配规则控制模块，有它来计算合适的路由方式。此外，路由器为匹配规则的数据包字节数设置计数器，程序根据计数值进行投票。

本文提出的负载均衡解决方案中，首先通用规则生成模块收集所有服务器的CPU负载情况，并更新通配规则。此规则由控制模块加载，路由器重写服务器的IP地址，将数据请求按端口转发至目标服务器上。依靠microflow规则，通配规则根据客户端IP地址，将请求进行转发；超时参数允许microflow规则在一个客户请求连接结束后进行自我式消除。针对每一个通配规则，该方案使用计数器以识别网络负载情况，根据实时负载动态调整规则以重新分配负载。

OpenFlow存在一些不足之处，它当前不支持多条路径下扩展负载的哈希式路由，OpenFlow只支持排序无关的情况，而本次提出的算法根据通配规则匹配客户端IP地址，由于IP地址的低阶排序bit较高阶排序big有更高的熵值，本算法基于客户端IP地址的低阶排序bit位实现负载分流。OpenFlow的另一个限制是它不支持TCP标签，后者有助于区分新到来的网络连接和已持续连上的网络连接，这种算法就可以应对Open-Flow这一点的不足。

为支持来自同一个TCP连接的数据包被转发至同一个服务器上进行处理，本算法设置的规则根据客户端的IP地址进行配置。不同的IP请求量可能不同，因此主要目标是为整个客户端IP地址空间集生成一个较小的通配规则结果集，同时使得所有服务器副本的CPU负载较均衡。负载分配的重新调整需要新的通配规则，并要求变化最小化。

如图2所示，二叉树可较直观地展现IP地址的前缀，树上每一个节点对应一个IP前缀，距叶子节点越近，对应表明IP前缀长度越长。叶子节点的个数等于幂次方（例如，如图2所示，3个前缀情况下的二叉树拥有8个叶子节点）。每一个服务器副本与多个叶子节点相关联（例如，在初始状态，S1和S2服务器各对应2个叶子节点，其他服务器各对应一个流量节点）。但在实际情况中，aj的值不一定等于幂次方值，同时每个节点对应的流量和请求计算量也未必平均。本文提出的方案设定的值约等于幂次方并相应地设置权重正态化。权重值与实际分布十分接近，可简易有效地分配IP地址空间。

1.1 通配规则合并节点

为每一个叶子节点创建通配规则的策略生成的规则数量十分巨大。本算法通过聚合关联至同一服务器的兄弟节点以降低规则的数量，如图2所示，单一的通配规则00＊可以同时代表关联服务器S1的叶子节点000＊和001＊。类似地，01＊可以同时代表关联服务器R2的叶子节点010＊和011＊，通配规则的数量从8减少至5。

1.2 通配规则动态调整

二叉图中每一条边的权重值说明了如何最好地将叶子节点分配给服务器，如图2所示，S3对应权重a3=3，生成一个带两个叶子节点的规则和另一个带一个叶子节点的规则，但是由于服务器群中的部分服务器需要不定期进行维护，并且各个客户端IP的请求并不均匀，且所需要消耗的服务器计算量也不尽相同。因此随着时间变化，服务器的CPU消耗会出现不平衡的状态，在图2中S2和S3的CPU负载就偏大，而S1和S4的计算量偏小。

针对这种情况，通配规则生成模块会定时从服务器集群获取CPU负载数据。并按照二叉树向上检索是否有叶子节点所处服务器的CPU较低，处于非均衡状态。这里采用服务器CPU负载的信息熵作为判断均衡的标准：

其中p1，p2分别代表此节点左右两边所有服务器的平均CPU负载，CPU负载越加不均衡的二叉树子节点，其熵值越小，如图2各节点中所示。对于低于一定阈值的节点，可以调整｛aj｝的权重，将负载较高的服务器部分流量分给负载较低的服务器，并重新生成通配规则。生成规则集的算法应该能够最小化根据IP地址空间碎片以适应服务器的变化调整，如果服务器关联的叶子节点没有发生变化，对应的规则集也就无需调整

（见图3）。

图3 流量负载发生变化后的二叉树模型

在图3中，由于11＊，0＊两个节点熵值过小，将其下S3的部分流量重新分到S4，S1下部分流量分给S2，而原本00＊和10＊两个规则集不需改变，而通配置规则010＊需要转变至新的服务器上，重新分配后由于负载有所均衡，所有各节点的熵值均上升到阈值以上。

由于S4的两个规则集可以合并，而S1需要生成一个新的规则集，所以整体规则集数量依然为5。

1.3 通配规则切换

表1为数据包包头各域值。

表1 数据包包头各域值

控制器不能因更改路由器配置而破坏已有的TCP连接，后者至少需要向客户端请求返回应答后再断开。新的请求连接将TCP同步标签设置在第一个数据包中，所以本文设计的算法利用TCP同步标记来区分新的请求连接和已有的请求连接。OpenFlow路由器无法匹配TCP标记，控制器可以检查数据包的同步位并相应配置规则。识别一个连接的结束符更加复杂，因为FIN或RST标签无法清晰标识网络连接的结束符；异常中断连接的客户端并不并发送FIN或RST标签。基于以上因素，通过客户端在一段指定的时间（比如60s）内无活动来推断连接断开。

本文采用两套算法来迁移流量到新的服务器：第一套算法将数据包转发至控制器以交换更快的数据包传递；第二套算法允许路由器处理所有的数据包，但转换速率比第一种算法低。为了减少路由器中额外规则集的数量，可以同时限制IP地址空间的传递碎片率。例如，可以分阶段地将规则111＊从服务器R3转移至R1，首先传递规则1110＊，再传递规则1111＊。

2 原型实现和评估

利用OpenVswitc和OSE（OpenFlow控制器平台）实现本文解决方案的原型并运行在MNet执行测试，使用MNet构建图1中的网络拓扑结构，包含3个服务器、2个路由器以及一系列客户端。服务器运行在 Mongoose［8］的web服务器上。原型中的OSE应用程序在两个路由器中配置规则，其中一个路由器充当网关的角色，负责分发客户端请求负载的转发工作，另一个路由器承担将请求转发至目标的服务器上的角色。本文的性能评估展现了该原型系统满足了负载均衡的自适应变化原则。

适应新的负载均衡权重值：原型使用的4个服务器主机硬盘均拥有16MB大小的文件空间，36个客户端在有效的单一地址突然间内被随机分配IP地址。每一个客户端发出wget命令请求以从服务器下载文件；在下载文件完成后，客户端在发送新请求之前需要随机地等待0至10秒。参照图2，原型假定a1=2，a2=2，a3=3，a4=1。75秒过去后，系统将a3从3更改成0，以模仿服务器S3从服务器群中拆除。当客户端开始发送请求，网络吞吐量上升，服务器S3处理了大多数的请求。负载的分发十分接近于2∶2∶3∶1，小部分客户端请求会产生可分析的偏差，网络负载的波动也随着时间而变化。75s后，S3上的流量开始下降，所以的请求被转发至S1，S2和S4上。60秒后，控制器配置新的通配规则。S3上的负载最终随着少量的已有连接中断后而下降至0。S3未被拆除前，系统配置了5个通配规则；S3拆除后，系统重新调整生成3个通配规则，其中4个聚合至一个单独的通配规则，原来为S2设置的规则同时被消除。

3 结语

目前实现的原型中，假定网络中只有两个路由器和均匀分布的客户端IP地址空间。在后续的研究工作中，还可以将算法进行延展，以解决非均匀的网络负载以及任意的网络拓扑结构，已有的分割和转换算法是开展后续研究工作的基石。

网络中的在线有服务依赖于负载均衡以有效利用所有主机服务器，本文设计的负载均衡架构将源IP地址映射至服务器上，客户端的请求可以通过负载均衡器以最小成本被转发。本文提出的分割算法可以动态调整流量负载，并生成一套最小通配规则集，传递算法负责调整规则以适应服务器群的变化。本文实现的原型系统展现了算法可以最低吞吐量的影响变化而自适应网络拓扑结构和流量负载的调整变化。

［1］ Foundry ServerIron load balancer.http：／／www.foundrynet.com／products／webswitches／serveriron／.

［2］ Microsoft network load balancing.http：／／technet／microsoft.com／en-us／library／bb742455.aspx.

［3］ The OpenFlow Switch Consortium.http：／／www.openflowswitch.org.

［4］ MCKEOWN N，ANDERSON T，BALAKRISHNAN H，et al.Openflow：Enabling innovation in campus networks.ACM SIGCOMM Computer Communications Review，38（2）：69-74，2008.

［5］ HANDIGOL N，SEETHARAMAN S，FLAJSLIK M，et al.Plug-n-Serve：Load-balancing web traffic using Open-Flow，Aug.2009.Demo at ACM SIGCOMM.

［6］ MOGUL J C，TOURRILHES J，YALAGANDULA P，et al.Devoflow：Cost-effective flow management for high performance enterprise networks.In ACM SIGCOMM Hot-Nets Workshop，Monterey，CA.

［7］ LANTZ B，HELLER B，MCKEOWN N.A network in a laptop：Rapid prototyping for software-defined networks.In ACM SIGCOMM HotNets Workshop，2010.

［8］ SCHLANSKER M，TURNER Y，TOURRILHES J，et al.Ensemble routing for datacenter networks.In ACM ANCS，La Jolla，CA，2010.

［9］ Mongoose-easy to use web server.http：／／code.google.com／p／mongoose／.