面向JCF中间件的亲和性动态负载均衡算法

曹卫东，孙晓君，周 原，王 静

(1.中国民航大学 计算机科学与技术学院, 天津 300300； 2.中国民航大学 天津市智能信号与图像处理重点实验室，天津 300300)

0 引 言

逐年增长的航空旅客运输量产生大量的订票需求，新一代旅客服务系统(passenger service system，PSS)等大规模分布式集群系统能够共同分担海量用户请求，其上部署的负载均衡算法可以提供一种有效透明的方法，提高集群系统中服务器的带宽、吞吐量、数据处理能力等[1]。

民航业一直在积极建设新一代PSS，JCF(java core framework)中间件平台是Java环境后台交易平台，也是新一代PSS的核心模块之一。在JCF中间件平台上，由于系统结构和业务需求原因，部分服务的上下文环境被存储在处理该服务请求的服务器上，不被其它服务器共享，而在处理同一个用户后续请求过程中需要用到这些环境，此外在处理同一个用户的后续请求时，需要用到前面请求的处理结果，所以该类用户请求需分配到同一服务器上按时间顺序进行处理，称之为服务的亲和性。

若服务的亲和性无法满足，会出现用户请求分配不合理、请求无法响应等问题。因此，本文在研究JCF平台负载均衡机制及多种负载均衡算法基础上，提出一种亲和性动态负载均衡算法，算法提取用户标识信息作为哈希映射键值，并使不同用户请求均匀分布，保证了服务的亲和性、系统负载均衡性能和稳定性。

1 相关工作

负载均衡的主要功能是缩短请求响应时间以及能够动态适应集群中单个服务器状态的变化。早期的负载均衡算法较简单考虑因素较少，随着研究的深入，提出一些适用于不同场景的算法[2]。从民航业务服务的亲和性角度，按照用户请求分配方式，对已有算法进行了如下分析和总结。

一类是以轮询机制分配请求。将用户的请求依次分配给集群系统中的服务节点，循环往复，如轮询算法[3]。在其基础上，通过为服务器分配比例因子或权值的方式，调配服务器接受请求的比例，如固定比例因子算法[4]、加权轮询算法[5]。另一类是按照特定规则分配请求。例如，文献[6]提出最小未完成交易数算法，选择当前未完成交易数最小的服务器分配用户请求；文献[7]提出改进的动态告警负载均衡算法，综合考虑请求类型、节点工作能力和实时负载值，再确定转发的目标服务器；文献[8]提出基于空间填充曲线的动态负载均衡算法，使均衡器根据实时收集的各项负载指标快速定位到最优编码的服务器；文献[9]提出一种数据段交换算法，将内存带宽负载不均衡服务器上的数据段进行相互交换，使集群的带宽负载达到均衡。

以上多种负载均衡算法，对于来自同一用户的连续请求，可能会被分配到不同的服务器上，不能有效满足服务的亲和性需求。结合民航业务服务的亲和性以及负载均衡需求，本文设计了一种亲和性动态负载均衡算法。

2 面向JCF的亲和性动态负载均衡算法

为了使集群系统在进行用户请求分配过程中，满足服务的亲和性需求。面向JCF中间件平台，提出了一种亲和性动态负载均衡算法，该算法在进行用户请求分配过程中，优先满足服务的亲和性需求，其次通过引入虚拟节点，有效保证了集群系统负载均衡性能，并结合实际应用情景，设计集群规模动态调整策略。

2.1 JCF中间件

JCF中间件平台位于服务管理平台和新一代PSS核心组件之间，Java语言编写的各种应用可以部署到JCF中间件平台上运行。基于该平台可以实现不同系统之间的信息交换，并最终达到资源实时调度。JCF架构中的分布式运行系统是由多个服务器组成的分布式环境，允许通过扩展服务器个数进行集群规模扩展，在进行调用分布部署的服务时提供负载均衡功能[10-12]。JCF负载均衡功能模型如图1所示，用户的各类服务请求通过TSI(travelsky service integration)总线接入到内部集群系统，再分发到相应的集群中。

图1 JCF负载均衡功能模型

2.2 算法设计

亲和性动态负载均衡算法基于带有虚拟节点的一致性哈希算法，其基本原理如下：首先根据键值的比特数N(一般取N=32)可以得到一个0～232-1的哈希环；接着定义虚拟节点个数，一个实际服务器节点对应若干个虚拟节点；再计算虚拟节点的哈希值，映射到哈希环上；然后计算用户请求的哈希值再映射到环上，按顺时针映射到距离其最近的虚拟节点，该虚拟节点所对应的实际服务器节点，即为该用户请求的实际处理节点。

本文在处理用户请求时，对用户请求的头部携带的具体标识，进行信息提取和转化得到用户标识信息，作为哈希函数的输入。由于民航系统实际应用中，同一航空公司的用户请求的标识是固定的，哈希环上的服务器节点也固定，因此，同一个用户请求的键值映射到哈希环上以后，会映射到相同的服务器节点，以此保证服务的亲和性。

本文算法引入虚拟节点机制，并使用运算性能高、碰撞率低和随机分布特征更良好的MurmurHash3算法进行具体哈希值计算。可以使得哈希环上更加均匀的分布更多的虚拟节点，用户请求将更加均匀的映射到每一个实际服务器节点上，这样可以有效减少服务器过载和轻载问题出现。保证集群系统的负载均衡性能。

算法如图2所示，实际服务器节点Server A对应图中Server A1和Server A2两个虚拟节点，实际服务器节点Server B对应图中Server B1和Server B2两个虚拟节点，req1通过哈希函数计算得到key1，并顺时针映射到距离其最近的虚拟节点Server A2上，根据对应关系，最终分配到Server A处理，req2、req3、req4同理，根据算法映射到各个节点进行处理。

图2 算法

2.3 算法流程

算法流程如图3所示。

首先定义虚拟节点数量记为VNN，将实际服务器节点

图3 算法流程

与虚拟节点进行映射，即一个实际服务器节点对应VNN个虚拟节点

(1)

其中，N为当前集群中实际服务器节点总数，k为常数，W为整个集群的权重之和，wi为第i个服务器的权重。

(1)根据式(1)计算出虚拟节点个数，对于每个虚拟节点其编号Virtual_Nodeit，(1≤i≤N)，(1≤t≤VNN)，表示第i个实际服务器节点对应的第t个虚拟节点；

(2)建立虚拟节点和实际服务器节点之间的对应关系，一个实际服务器节点对应VNN个虚拟节点；

(3)计算实际服务器节点的哈希值。在JCF中间件平台的服务库中，每个服务器注册一个元数据表，根据表中服务器节点配置的server_name，通过MurmurHash3算法计算得到每个服务器节点的哈希值Node_hashi，(1≤i≤N)；

(4)计算虚拟节点的哈希值。对于某个虚拟节点，将Node_hashi加Virtual_Nodeit的值作为MurmurHash3算法输入，计算得到每个虚拟节点的哈希值，记为Virtual_Node_hashit，(1≤i≤N),(1≤t≤VNN)，表示第i个实际服务器节点对应的第t个虚拟节点的哈希值；

(5)根据Virtual_Node_hashit的值将虚拟节点映射到环上；

(6)用户请求的处理。用户根据设定规则设置请求内容，算法解析用户发送的http请求，从用户请求的消息头headers中获取请求头部的host值，若值的类型为字符串，首先要应用函数将字符串类型数据转换成整形数据。使用Fowler-NOll-Vo函数完成这个目的

keyuser=Fowler-NOLL-Vo(host)

(2)

(7)计算用户请求的哈希值，根据keyuser通过MurmurHash3算法计算用户请求的哈希值User_hash；

(8)处理用户请求，将User_hash映射到环上，按顺时针方向映射到距离最近的虚拟节点上，根据实际服务器节点和虚拟节点的对应关系，该请求实际是映射到对应的实际服务器节点上去处理；

(9)当有新的请求发送到集群时，重复(6)～(8)步。

2.4 集群规模动态调整

在实际的使用中，集群中能够正常提供服务的服务器的个数可能会发生变化。分为以下两类情况：当业务量增加，需要增加新的服务器以满足新的业务需求，或者已宕机服务器经过维护重新投入使用，会造成集群规模扩展。另外，由于服务器性能下降，负载量长时间过大，运行的程序出现死循环，线路或者服务器发生物理故障时，会造成集群规模缩减。

当集群规模发生动态变化时，需要对服务请求做平滑处理，保证集群负载均衡的同时，最大程度减少受影响的用户个数，保证绝大部分用户服务的亲和性能够得到满足，保证系统的稳定性。本文算法针对集群规模变化，设计了如下动态调整策略：

(1)集群规模扩展。当需要增加服务器时，首先将服务器信息添加到服务库中。再根据规则生成新的服务器节点的虚拟节点，并映射到环上。服务请求根据规则映射到新服务器上进行处理。

如图4所示，原先集群系统中有服务器Server A、Server B、Server C，req1映射到Server A处理，req4映射到Server B处理，req2和req3映射到Server C处理，当集群中增加一个服务器Server D后，此时req2顺时针寻找到距离其最近的服务器节点为Server D，则req2映射到Ser-ver D处理。其余用户请求不受影响。

图4 增加Server D节点

(2)集群规模缩减。当需要删除服务器时，将服务器从服务库中删除，并从环中删除该服务器的所有虚拟节点映射，原来发送到该服务器上的用户请求，沿顺时针再继续寻找离自己最近的服务器作为新的服务器节点，由新的服务器节点处理请求。

图5中显示集群中原先有4个服务器，请求映射情况为req1映射到Server A，req2映射到Server D，req3 映 射 到Server C，req4映射到Server B，此时Server B发生故障，req4按顺时针方向映射到与其距离最近的Server D，其它请求映射关系不变。

图5 删除Server B节点

如图4、图5所示，当增加服务器ServerD和删除服务器ServerB后，重分布的用户分别为req2和req4，环上其余用户不受影响。由此表明，当集群规模发生动态变化时，受影响的用户仅包括，从变化服务器逆时针到距离其最近的服务器节点之间这一段哈希环上的用户，其余用户不受影响，这保证了绝大部分用户服务的亲和性，避免了大部分用户重分布带来的损失。当服务器减少时，集群系统的负载均衡性能相对减弱，使得部分服务器负载增大。但从总体上来看，由于动态调整策略的存在，服务的亲和性受影响的用户较少，且受影响的用户能够得到及时有效的调整，集群系统的负载均衡性能受到的冲击较小，系统相对稳定。

3 系统仿真和算法性能分析

3.1 实验环境与过程

实验模拟JCF中间件平台，搭建了一套仿真实验环境，由7台Dell服务器组成一个小型集群系统。其中一台作为服务库，一台作为适配器，其它作为处理用户请求的目标服务器，服务器的配置为：CPU型号：Intel(R) Core 2 Duo E7500;CPU内核：2 core；RAM：6 GB，硬盘：300 G；操作系统：Ubuntu 14.04；运行环境Myeclipse，jdk1.8，相关软件：Apache JMeter。

服务库上安装服务注册表，包含各台服务器节点的信息，适配器上安装Nginx反向代理服务器，为了进行算法对比，在Nginx反向代理服务器上部署了4种算法，分别为固定比例因子算法、最小未完成交易数算法、轮询算法和本文算法，其中固定比例因子算法和最小未完成交易数算法为JCF平台上原有算法。

实验中使用Apache JMeter软件，构造大量的http请求，在一定的时间周期内发送到适配器上，适配器根据当前配置的负载均衡算法，将请求转发给后端服务器。

3.2 实验场景与性能分析

根据本文算法的特点，并且结合实际的应用需求，本文实验场景分为4个部分：

(1)场景一：系统处于稳定状态，集群中有4个服务器处理用户请求，使用Apache JMeter构造大量用户请求，在一定的时间周期内，发送到集群系统，通过适配器上部署的4种不同的负载均衡算法，分配到服务器上去处理。观察实验结果，统计实验数据，计算4种算法的亲和率。

亲和率计算方法如下，在一个实验时间周期内，一共有num个用户访问了集群系统，第i个用户共发送NRi(1≤i≤N)个连续请求，记该用户首次映射的服务器为目标服务器，则第i个用户的所有连续请求命中目标服务器的总次数记为NOi(1≤i≤N)，则第i个用户命中目标服务器的命中率记为Hi

(3)

则整个集群系统的亲和率记为A

(4)

式(4)表示，在一个实验时间周期内，所有访问该集群系统的用户，命中目标服务器的命中率之和，取其平均数，即为该集群系统的亲和率。

在配置了负载均衡算法的集群系统中，亲和率为所有用户的连续请求发送到其目标服务器次数占其发送请求总次数的比率。亲和率越高，即表示越多的用户连续请求被分配到相同服务器处理，则更加满足服务的亲和性需求。通过亲和率的大小，可以观察当前集群系统在满足服务的亲和性方面的表现。

如图6所示为在不同用户请求总数情况下，4种算法的亲和率。系统的亲和率随着请求数量的增加基本处于稳定状态，对于固定比例因子算法、轮询算法和最小未完成交易数算法，当请求总数为200时，亲和率分别为23.5%、26.5%和25.5%；当请求总数为800时，亲和率分别为26.6%、23.4%和22.6%；当请求总数为2000时，亲和率分别为25.3%、26.2%和26.6%；实验结果表明，以上3种算法的亲和率基本稳定在24%、25%和25%左右。本文算法的亲和率在不同请求总数情况下均为99%。对比实验结果表明，本文算法的亲和率比其它3种算法的亲和率高很多，这表示本文算法能够将绝大部分的用户连续请求发送到目标服务器上去处理，有效满足服务的亲和性需求。

图6 4种算法的亲和率

(2)场景二：系统处于稳定状态，集群中有4个服务器处理用户请求，使用Apache JMeter构造大量用户请求，在一定时间周期内，发送到集群系统，模拟不同的请求并发数，并发数由少至多。统计请求总响应时间和系统吞吐量，请求总响应时间为系统处理请求并响应的总时间，系统吞吐量表示每秒完成的请求数。

如图7所示，当请求并发数递增时，固定比例因子算法的请求响应时间从0.09 s增加到0.26 s；轮询算法的请求响应时间从0.076 s增加到0.275 s；最小未完成交易数算法的请求响应时间从0.02 s增加到0.2 s；本文算法的请求相应时间从0.02 s增加到0.18 s，4种算法的请求总响应时间，随着请求并发数的增加不断增加，其中本文算法请求响应时间相对较短。

图7 4种算法的请求总响应时间

这是由于固定比例因子算法、轮询算法和最小未完成交易数算法，这3种算法的请求分配机制均不能保证连续请求被分配到同一服务器。由于此时未满足服务的亲和性，会导致该请求无法及时响应或者无法响应，增加系统的请求总响应时间。

本文算法在处理同一用户的连续请求时，由于标识固定，会将这些连续请求发送到同一服务器的服务队列中，按照时间顺序处理，避免由于服务所需资源与服务器绑定，而导致的请求无法响应问题，同时减少由于后续请求需要前面请求处理结果的等待时间，因此使得服务的亲和性得以保证，负载均衡情况下请求响应时间相对较短。

如图8所示，当请求并发数为60 个/s时，固定比例因子算法、轮询算法、最小未完成交易数算法和本文算法的吞吐量分别为：36.2个/s、37.5个/s、38.3个/s、38.4个/s；当请求并发数为500个/s时，4种算法的吞吐量分别为：119.0个/s、101.6个/s、117.6个/s、118.1个/s。4种算法的系统吞吐量随着请求并发数量的增多呈上升趋势，本文算法的系统吞吐量和其它算法的系统吞吐量接近，并发量高时略低于其它算法。

图8 4种算法的吞吐量

这是由于当多个用户在一定时间周期内，发送来多个连续请求，并且这些用户请求映射到相同的服务器上去处理，该服务器的处理压力会增大，极端情况时服务器会由于过载而宕机。此时，服务器处理能力会明显降低，集群系统吞吐量相应的会降低。

(3)场景三：集群系统规模扩展，新增加一个服务器，先到服务注册库中注册，此时服务器总数增加至5台，适配器上部署本文算法，用户请求的映射根据2.4节介绍的动态调整策略变化。观察同一类请求的分布情况，分析请求在系统规模扩展情况下，多少用户请求受到了影响，若在一个实验周期内，由于服务器增加，导致某一用户请求需重映射到新的目标服务器，则记变化一次，统计总的变化次数CT，记该周期内所有用户发送请求的总数为num_req，记系统的变化率为CR，则

(5)

(4)场景四：集群系统规模缩减，模拟集群系统中有一台服务器出现故障，从服务器注册库中删除了一个服务器，服务器总数减少至3台，适配器上部署本文算法，用户请求的映射根据2.4节介绍的动态调整策略变化。观察同一类请求分布情况，统计系统变化率。

场景三和场景四，分别模拟了给集群增加一个服务器和减少一个服务器的情况，并统计集群的变化率，实验结果见表1。

表1 变化率统计

两种状态下本文算法的变化率分别为21%和34%，即表明变化节点沿逆时针到距离其最近的服务器节点之间这一段哈希环上的用户请求数占总请求数的21%和34%。这说明分别有21%和34%的用户的连续请求受到影响，并根据动态调整策略重分布到新的服务器处理。实验结果表明，本文算法保证了绝大多数用户的请求处理不受到集群系统规模变化的影响，避免了所有用户重分布的情况发生，保证了绝大多数用户服务的亲和性。同时受影响的一部分用户请求，能根据动态调整策略重映射到新的服务器上处理，由于算法设置的虚拟节点在哈希环上分布较均匀，部分请求重映射不会造成某一服务器严重过载现象，对集群系统的负载均衡冲击较小，保证了系统的稳定性。

不同场景下的实验结果表明，本文提出的亲和性动态负载均衡算法，优先保证服务的亲和性，虽牺牲了一部分负载均衡性能，使得负载均衡效果没有优于其它算法，但是集群系统的负载均衡仍得以保证。根据实际生产需求，而设计的集群规模变化实验结果表明，系统的亲和性和稳定性均能够得到保证。

4 结束语

为了解决民航业大规模分布式集群系统在进行用户请求负载分配过程中，出现服务的亲和性和负载均衡问题，分析了JCF中间件平台上原有的负载均衡算法以及其它常见负载均衡算法的特点，基于带有虚拟节点的一致性哈希算法，提出一种亲和性动态负载均衡算法，通过设计对比实验，验证了该算法能够使得用户请求得到合理的分配，满足服务的亲和性需求，同时具有负载均衡功能，并保证集群系统的稳定性和可伸缩性。

但是，该算法还有许多不足，如何在此基础上，进一步提升算法的负载均衡效果，将是下一步重点研究内容。