基于因子分析的动态负载均衡算法*

陈练达，曾国荪，2（.同济大学 计算机科学与技术系，上海 200092；2.国家高性能计算机工程技术中心　同济分中心，上海 200092）

基于因子分析的动态负载均衡算法*

陈练达1，曾国荪1，2
（1.同济大学 计算机科学与技术系，上海 200092；2.国家高性能计算机工程技术中心同济分中心，上海 200092）

随着互联网的不断发展、用户数量的急剧增长，互联网中出现了网络拥塞、服务器负载过重、响应时间过长等严重问题，其中负载均衡算法是影响服务器集群整体性能的一个关键因素。运用统计学中的因子分析理论，提出了一种基于因子分析的负载均衡算法。该算法利用因子分析法计算出综合负载，并用这个指标帮助负载均衡器选择合适的服务器，均匀地将用户的请求进行分发，从而达到整体上较好的负载均衡。

内容分发；因子分析；负载均衡

0　引言

随着网络的高速发展和普及，人们对网络服务的依赖和需求也越来越来大。为了保持所提供网络服务的高质量、高效率，负载均衡系统是影响服务器集群性能的核心部分，而负载均衡算法是决定负载均衡模块如何分发用户请求的重要部分，但已有负载均衡算法容易造成用户请求分配不均，有着一定的局限性［1］。

研究者们提出了一些新的评估各个服务器节点负载的方法，以此来改进负载均衡算法。例如，张慧芳［2］选择静态参数（如 CPU主频、内存大小等）和动态参数来计算节点的综合负载（如CPU利用率、内存利用率等）；HWANG S T等人［3］提出了用硬件指标、CPU利用率和在线连接数作为评估指标。Duan Zhaolei等人［4］利用CPU利用率、磁盘利用率、分页错误数、请求数、请求响应时间等指标来计算服务器的实时负载；章文嵩［5］、陈伟［6］等人在研究集群系统的动态负载均衡算法方面利用输入指标、服务器节点指标两类负载信息来计算综合负载，其中综合负载通过线性加权计算得出，各指标的权值按照其重要性大小进行确定。

据以往的研究看来，负载的计算往往是按照一定的加权比例进行的，比较经验主义，且主观性和随意性比较大，没有一个较为科学的方法来确定加权的比例，从而导致实时负载计算式反馈出来的不太不准确。为了解决准确评估实时负载的问题，本文采用了统计学中的因子分析法来评估实时负载，以求达到较准确评估负载。

1　基于因子分析的动态负载均衡方法

1.1算法设计思路

在已有负载均衡算法中，有一些以实时负载情况作为依据的负载均衡算法，已有的加权最小连接（WLC）算法能够较有效地均衡服务器集群的负载、分发用户请求，然而目前的WLC算法仅仅是参考了实时连接数这一负载信息，并没有考虑到不同网络应用的连接对服务器负载的影响程度是不同的，如视频连接对服务器的影响肯定比文本连接对服务器的影响大。因此，本文的思路是通过采集一些其他服务器的性能数据信息，改进实时负载情况的计算方式，并将这些新的负载度量信息与WLC算法结合，以达到改进算法、提高用户请求调度效率的目的。改进的动态负载均衡算法的应用模型如图1所示。

图1　负载均衡算法的模型图

设有n台缓存服务器组成的集群，则可以定义服务器设备集合S=｛S1，S2，…，Sn｝（n＞1）。该算法的核心内容为：服务器设备集群中的各个服务器节点在每间隔一个时间周期T就向负载均衡调度器反馈当前服务器的服务器性能参数，调度器接收到这些负载度量信息后，利用这些负载度量信息评估出实时负载情况，结合实时负载情况，做出缓存服务器的选择，达到合理的负载均衡。因此，本文要做的工作是：（1）选择什么负载度量信息；（2）用什么计算方法组织这些负载度量信息，得出一个综合的负载情况指标；（3）如何与WLC算法进行结合。1.2实时负载情况的量化

首要的工作是如何评价服务器的负载情况。采用数值量化的办法无疑是较为合理的，本文利用多元统计分析学中的因子分析法［7-8］，通过合理的推导和计算，获得能够反映实时负载情况的量化，从而帮助现有负载均衡算法做出更准确的任务分配，达到改进已有负载均衡算法的目的。

定义1负载参数变量：某种可观测的、影响实时负载能力的变量，Xi表示第 i种影响负载能力的变量，这里用 X1表示 CPU利用率，X2表示内存利用率，X3表示磁盘利用率，X4表示网络带宽使用率。

定义 2实时负载指数：Load表示负载实时指数，有Load=g（X1，…，X4），g表示Xi与Load的关系函数。

定义3负载参数向量：由X1，…，X4构成的4维可观测向量，记为X，其各维数据均为可以较准确、直接观测出的数据。

仅仅通过 Load=g（X1，…，X4）无法得出各种负载参数变量与Load的合理关系，于是开始因子分析法。首先，建立正交因子分析模型：设 X=（X1，…，X4）T是可观测的随机向量，即按照上面的定义引入了p种负载参数变量，其协方差矩阵∑为：

其中，σij为 Xi和 Xj的协方差。设 F=（F1，F2，F3）T为公共因子，这些因子属于不可直接观测、却又可以影响每个负载参数变量的共同潜在因素，按照本文选取的参数，可以给F1、F2、F3分别命名为计算速度因子、网络传输速度因子、I/O速度因子；且 E（F）=0，D（F）=I3（即 F的各分量方差为1，且互不相关）。设ε=（ε1，ε2，…，ε4）T为特殊因子，它与F互不相关却又可以影响负载参数变量，那么每个负载参数变量都可以表示成公共因子的线性函数与特殊因子之和，则：

该模型用矩阵表示为：

通过以上过程，得到了初步的数学模型，即描述了负载参数Xi与潜在因素F存在一定的关系。然而模型中仍有未知的特殊因子ε和aij，因此可利用观测出的数据X对模型进行求解，以得到 Xi与 Fm的关系。

由于公共因子是不相关的，且均有潜在影响，则有：Load=f（F1，F2，F3）。然而这些公共因子F很难通过实际数据去测量，因此在因子分析法中，首先考虑用X来代替F，用可观测量反映不可测量。接下来将公共因子转换成负载参数的组合，这个过程就是因子得分（factor scoring）。潜在因素向量F=（F1，F2，F3）T可以用最小二乘法估计为：

这样就可以得到潜在因素向量F与最初的可观测向量 X的关系，其中 S=（βij）4×3为因子得分系数矩阵，而X就是前面各种负载因素变量组成的向量，可以看出因子得分系数矩阵的计算主要与因子载荷矩阵A有关。再把F替换为X，得到：

根据因子分析方法中的概念，将潜在因素使用线性相加的办法可以进一步得出一些关于负载指数的具体计算式：

其中，wi为公共因子Fi的权重。由因子分析法可知，wi的值为使用方差贡献率作为权重值，结合式（5）和（6），得到：

经过以上分析过程，从原来常用简单的线性叠加式，通过使用因子分析法的方式，得到了实时负载指数的计算公式，为后文的负载均衡算法的改进和实验分析提供了依据。

1.3DLBFA算法的设计

本文的思路是在已有算法的基础上进行改进，其中加权最小连接（Weighted Least-Connection，WLC）是目前已有算法连接请求调度情况较好的一种算法，它选择服务器设备节点的算法过程主要以考虑服务器节点的连接数为主，但是其缺陷就是算法中每个服务器节点的分配权重为固定值，并不能实时地按照服务的性能调整服务器节点的权重。因此引入前面得出的服务器实时负载指数，提出基于因子分析的动态负载均衡（Dynamic Load-balance Based on Factor Analysis，DLBFA）算法，动态地修正服务器的权值，这样负载均衡系统可以根据动态权重做出服务器的选择。

从前文可知，负载情况的计算需要采集的一些服务器性能信息是以较主流的 CPU、内存、磁盘和网络4个方面来源为主的。其中负载参数向量X记为：X＝（U1，U2，U3，U4）T，其中向量各维分别为 CPU利用率、内存利用率、磁盘利用率和网络带宽使用率。那么可以结合式（8），经过因子分析的过程算出Li。再将Li与WLC算法结合，形成改进算法。可以约定如下：设服务器集合 S=｛S1，S2，…，Sn｝（n＞1），W（Si）表示服务器的权值，C（Si）表示服务器 Si当前连接数，α（Si）表示服务器Si对应的可变因子，则选择服务器的策略为：其中，βi=（β1i，…，β4i）T是前面提到的因子得分系数矩阵的列向量，X为负载因素向量。

由于在因子分析法计算出的综合得分有一些会出现负值，因此做一定修正，即：

式（9）达到了 W（Si）的动态变化的目的，其中 α（Si）的确定与 Li的值有关，这样就可以做到 Li与WLC算法的结合。α（Si）确定的策略以各个服务器的负载平均值L为基准，即：其中，当第i台服务器的负载指数大于平均负载指数时，可认为负载过重，此时将 α（Si）的值调小，达到了降低权值的目的；如果第i台服务器的负载指数小于平均负载指数，则认为负载较轻，此时 α（Si）的值为 1不变，保持权值也不变。这里设置的ε、θ是为了防止 α（Si）调整过于频繁影响任务调度而设置的阈值，保证了服务器的负载情况稳定在一定范围之内。算法的伪代码描述如下：

算法1基于因子分析的动态负载均衡算法

输入：用户请求集 VR，服务器节点集 VS，服务器权重集合W，可变因子集合α，服务器当前连接数集合C。

输出：请求映射到服务器的集合。

2　实验及分析

2.1实验方案与环境

为了验证改进算法的基本性能，本实验采用网络仿真软件 OPNETModeler模拟网络环境进行测试，将DLBFA算法与 OPNETModeler自带的最小连接调度（WLC）算法以及其他改进的基于动态反馈的负载均衡算法（MTN）［9］进行对比。本次实验主要观察平均响应时间，即集群系统对连接请求的平均响应时间。

模拟网络的客户端有200个节点，仿真运行30 min，由于客户端的配置数目较大，固定性能数据采集周期T设置为20 s。为了验证算法在性能不同的服务器集群上的效果，本实验使用3种性能不同的服务器组成了实验集群，服务器性能大小次序为：服务器1＜服务器2＜服务器3。客户端与服务器集群系统通过链路与负载均衡器相连。

2.2实验结果与分析

实验结果如图2所示。

图2　实验结果

实验运行约 5 min后进入响应时间稳定期，通过观察此后响应时间数据分析结果。从图2（a）可见，在运行WLC算法的集群中，不同性能的服务器的响应时间差别并不太大，说明性能较好的服务器其处理资源并没有被充分利用，负载均衡算法对任务分配并不理想，并没有达到预期的目的。从图2（b）可以看出，改进的MTN算法由于考虑了服务器的负载和性能情况，各个节点的响应时间随着性能变化而变化，分配效果有了一定的改进，但是响应时间的区分程度还是不够明显。而图2（c）显示，本文的DLBFA算法的负载均衡效果有了进一步提高，能更好区分不同服务器的性能任务的分配，这使得服务器集群的资源得到了充分的利用，达到了实验需要的目标。

3　结论

CDN中的负载均衡算法是提高网站服务质量和性能的关键，与传统的负载均衡算法相比，本文提出的动态负载均衡算法有如下特点：

（1）该算法通过负载均衡器动态地收集各个服务器的实时性能数据，将服务器的实时负载加入到算法中综合考虑，使得连接请求的调度更加合理。

（2）如何通过实时的性能数据合理地评估实时负载情况是本文的主要着力点。本文通过使用统计学中的因子分析法将获得的实时数据组织起来，提出了一个较为有理有据的实时负载情况的计算式。

通过合理地组织实时负载数据，较准确地测算出实时负载情况，可以帮助负载均衡模块在连接请求调度时做出更为合理的选择，而本文的实验结果也证明了这一点，具有一定的应用价值。

［1］胡利军.Web集群服务器的负载均衡和性能优化［D］.北京：北京邮电大学，2010.

［2］张慧芳.基于动态反馈的加权最小连接数服务器负载均衡算法研究［D］.上海：华东理工大学，2013.

［3］HWANG S T，JUNG N S.Dynamic scheduling of web server cluster［C］.Proceedings of the 9thInternational Conference on Parallel and Distributed System，2002：563-568.

［4］Duan Zhaolei，Gu Zhimin.Dynamic load balancing in web cache cluster［C］.7thInternational Conference on Grid and Cooperative Computing，2008：147-150.

［5］章文嵩.Linux服务器集群系统（四）［EB/OL］.（2002-05-20）.［2014-08-30］.http：//www.ibm.com/developerworks/cn/ linux/cluster/lvs/part4/index.html.

［6］陈伟，张玉芳，熊忠阳.动态反馈的异构集群负载均衡算法的实现［J］.重庆大学学报，2010，33（2）：73-78.

［7］谢雯.基于因子分析的中国证券公司竞争力研究［D］.上海：复旦大学，2012.

［8］高惠璇.应用多元统计分析［M］.北京：北京大学出版社，2005.

［9］刘健，徐磊，张维明.基于动态反馈的负载均衡算法［J］.计算机工程与科学，2003，25（5）：65-68.

CDN′s dynamic load-balance algorithm based on factor analysis method

Chen Lianda1，Zeng Guosun1，2
（1.Department of Computer Science and Technology，Tongji University，Shanghai 200092，China；2.Tongji Branch，National Engineering&Technology Center of High Performance Computer，Shanghai 200092，China）

With the development of Internet and the rapid increase of users，there are a lot of serious problems in Internet，such as network congestion，server overload and too long response time.The load balance algorithm is the important factor that impacts the whole performance.In this paper，the factor analysis method is used to improve the algorithm，and an improved algorithm that combined with factor analysis method is propsed.The improved algorithm uses factor analysis method to figure out the servers′load，and the index can help load balancer choose the appropriate server，then the requests will be distributed evenly，and the cluster achieves a better load-balance status.

content delivery；factor analysis；load balance

TP319

A

1674-7720（2015）02-0059-04

863项目（2009AA012201）；国家自然基金项目（61272107，61202173，61103068）；上海市优秀学科带头人计划项目（10XD1404400）；华为创新研究计划项目（IRP-2013-12-03）；高效能服务器和存储技术国家重点实验室开放基金项目（2014HSSA10）

（2014-09-17）

陈练达（1990-），男，硕士研究生，主要研究方向：并行与分布式计算。

曾国荪（1962-），男，博士，教授，博士生导师，主要研究方向：并行计算，可信软件，信息安全。