集群文件服务系统中的负载均衡算法的研究

刘恩海，李 伟，张素琪，董永峰，方新春

（1.河北工业大学 计算机科学与软件学院，天津300401；2.天津大学 电子信息工程学院，天津300072；3.河北工业大学 电气工程学院，天津300401）

0 引 言

在这个网络飞速发展的时代，文件管理网络化的趋势越来越明显，以往传统、单一服务器的性能配置早已不能满足对庞大的文件群的管理，此时集群技术应运而生。它是使用两个或两个以上的服务器连接在一起相互协作，共同完成某一任务的技术。应用负载均衡算法来研究如何将任务合理均衡的分配到各服务器上，才能使系统达到最优。目前最常用的是周期性动态反馈负载均衡算法［1］，它周期性的更新各节的负载信息，按某种规则将其进行分组，然后将请求依次分发到负载最轻的一组节点上进行处理。分析了其优缺点后，本文在周期性动态反馈算法的基础之上，加入了对请求文件自身的负载情况的考虑，然后结合服务器的实时负载，更加准确的估计了当前的系统情况，从而更均衡地将文件分配到合适的服务器上进行处理，并在获取负载信息时采用定量更新原则。最后在现有的系统中设计、实现了该均衡策略。实验结果表明，该算法在实际系统应用中，减少了用户等待时间，减轻了系统的网络负担，提高了系统吞吐量，达到了良好的负载均衡。

1 负载均衡算法简介

1.1 常见的负载均衡算法

负载均衡算法按其分配策略可分为静态和动态负载均衡算法。静态负载均衡是在服务触发之前就设定好了分配原则，在请求处理过程中不再考虑任何变化的情况；动态负载均衡是在系统运行过程中根据各个节点的资源利用情况，动态的调整分配给每个节点请求任务。优点是可以根据节点的实时负载调整请求的分配，具有更大的灵活性；缺点则是频繁的与各节点进行交互，增加了网络负担。而在实际应用中，各节点的瞬间负载变化比较大，静态算法的均衡效果会比较差，因此，怎样更好的实现动态负载均衡是当前研究的重点。目前常见的网络负载均衡算法有以下几种［2－4］：

（1）轮转法：属于静态算法，简单快捷。假设有N个节点，所有的请求轮流分配给集群中的各个服务器，从1到N然后重新开始。因此可以提前预知节点的负载分布。由于不考虑各节点之间的差异，所以轮转法适用在集群中所有节点的处理能力和性能大体相同的情况。

（2）权重轮转法：较轮转法有了一定的进步，它给各节点按照其不同的处理能力设定了不同的权值，使其能够接受相应权值数的服务请求。将该算法应用于请求处理的任务长度大致相同的情况时，是比较简单、高效的，但是将其应用于任务长度差别较大的场合时，就会造成节点间负载的不均衡。

（3）最少连接法：是最简单的动态算法，记录了目前各系统所有的活跃连接数，使其代表当前系统的负载情况。然后系统把每一个新的任务分配到当前连接数最少的节点上，充分利用其系统资源，从而更好的实现负载均衡。这种算法比较适用于长时处理的请求服务，如FTP。

（4）最快响应法：记录到每一个节点的网络响应时间，并将下一个到达的连接请求分配给响应时间最短的节点。这种方法能较好的反映出当前节点的负载情况。

（5）处理能力均衡法：它综合考虑节点系统的处理能力及当前的网络情况，得出一个负载值，使其对节点的负载评估更加准确。然后根据此值将请求任务分发到负载最轻的节点上进行处理。比较适用于在应用层实施负载均衡。

1.2 周期性动态反馈负载均衡算法

周期性动态反馈负载均衡算法［5］是一些中小型应用系统目前常用的一种负载均衡算法，它的主要流程是主服务器周期性的收集节点服务器的各项负载信息，据其将各节点进行轻载、适载、重载的队列划分，然后在队列中将各节点按权值进行排序，最后将并发请求依次分配到轻载队列的各个节点上进行处理。它汲取了以上几种算法的优势，但还是存在一些不足［2］：

（1）文件上传策略中没有考虑上传文件的数量和大小，即文件负载量，如果依旧遵循先来先服务的原则，会可能发生将文件负载大的请求分配到负载量较重的服务器上，而文件负载小的分配到负载量较轻的服务器上，从而造成负载失衡。

（2）信息收集策略中收集参数时，以往的算法中只考虑了CPU利用率和内存利用率，但是不同类型的请求对服务器各项指标的要求是不一样的，有的请求需要大量的计算或者繁琐的与数据库交互等操作，此时就要求CPU的性能高一些；而有的请求是读取或写入大量不同类型的文件，这就要求网络带宽和磁盘读写速度性能高一些，所以在参数的选择上应根据实际情况多加考虑。

（3）负载更新策略中采用的周期性更新［5］中，周期的长短不好掌控，周期过长不能及时反映各节点的负载情况，造成负载失衡；周期过短又会因为服务期间频繁的交互，产生大量额外的网络负担。

2 改进的动态反馈负载均衡算法

针对以上问题，提出了一种改进的动态反馈负载均衡算法。下面将从文件上传策略、信息收集策略、负载更新策略三方面进行说明：

（1）文件上传策略 引入了文件负载量这一概念，将上传请求按照指定的公式计算出文件负载量，然后把任务请求队列按负载量进行排序，以此为其分配服务节点。在页面嵌入小的程序，在上传文件时触发，将除文件以外的信息发给web主服务器，然后主服务器通过负载均衡分配算法将节点服务器的IP和端口返回，使用异步调用的方法再将文件传给节点服务器完成上传操作，这样主服务器不用把文件完全读完在进行处理，既减轻了主服务器的压力，又可以缩短用户等待响应的时间。

（2）信息收集策略 结合文件的特点，主要收集节点的cpu利用率、内存利用率、磁盘读写速度、网络速率几项信息来计算节点服务器的负载量。收集的系统参数，采用C＃编程，java调用的方法，如图1所示。

图1 java调用C＃图解

系统中有很多可用的计数器类别，常用的有缓存（cache）、内 存 （memory）、对 象 （objects）、 物 理 磁 盘（physical disk）、进程 （process）、处理器 （processor）、服务器 （server）、系统 （system）和线程 （thread）等类别。

（3）更新策略 将以往的定时更新，改为定量更新。当给服务器分队列后，当某节点负载从轻载、适载、重载队列之间转换时，再向主服务器发出更新请求，减少了与主服务器的交互，降低了定时更新时产生的大量额外的开销，同时也能及时向主服务器反应自己的负载情况。

此外，节点服务器向主服务器发送负载信息时使用对象的序列化和反序列化的方法进行传送 （socket网络通信方式）。可以把对象的字节序列永久地保存到硬盘上，通常存放在一个文件中，并在网络上传送对象的字节序列。

基于改进的动态反馈负载均衡算法进行系统设计，其结构［7］主要包括三部分：Web主服务器、客户端以及节点群 （存储服务器）。Web主服务器主要负责收集各节点的实时负载量并将其分组，根据负载均衡机制分配各请求到适合的节点上；节点群中各节点主要实时收集自己的负载信息，并上传给Web主服务器、负责文件的接收和存储。系统框架如图2所示。

图2 系统框架

2.1 算法中相关参数的确定和计算方法

根据改进的动态反馈负载均衡算法，定义几个变量［8，9］：

（1）计算各节点的实时负载量RL （i）

RL （i）：由节点的当前运行状况计算得出。本文选择CPU使用率和CPU个数的乘积、进程数量占用率、内存使用率、磁盘I／O占用率、网络带宽使用率几个参数来计算实时负载量

其中，Ri（i＝1，2，3…）为各参数权值，ΣRi＝1，参数对性能的影响越大，权值越大。（对于文件上传而言，磁盘读写速度和网络带宽要求较高）

（2）计算各节点的最大负载量 （处理能力）MAXL （i）

MAXL （i）：由节点的硬件配置决定。本文选择CPU主频和CPU个数的乘积、最大进程数、内存大小、最大磁盘容量、最大网络带宽使用率几个参数来计算最大负载量。

由于各参数单位不一致，某些参数水平相差很大，例如内存为2G，但是网络带宽可能为1000M／bps，如果直接用原始数据值进行分析，就会突出数值较高的参数在整体计算中的作用，相对削弱了数值较低的参数的影响。因此，为了保证结果的可靠性，需要对原始数据进行标准化处理。

数据标准化就是由于各指标的度量单位不同，为了能够将各指标都参与评价计算中，它通过函数变换去除了数据不同单位、不同量级的限制，将其转化成无量纲的纯数值并映射到某个数值区间内。本文选用最常见的标准化处理方法，即Z标准化 （标准差标准化）。公式如下

式中：L——参数标准化前的数值，L′——参数标准化后的数值，μ——所有参数数据的均值，σ——所有参数数据的标准差。对各参数进行标准化后，再计算最大负载量，公式如下

其中，Ri（i＝1，2，3…）为各参数权值，ΣRi＝1，参数对性能的影响越大，权值越大。

（3）计算上传文件的负载量Pi

FSi：上传文件的大小，FNi：上传文件的数量，需要根据以上计算请求的负载量Pi，首先计算

定义首次上传的RL （i）为MRL （i），α为轻载因子，β重载因子。一般论文中α取45%，β取85%。需要在测试中反复求证。

（5）计算各节点的权值WL （i）

2.2 算法描述

算法步骤具体描述如下：

（1）各节点服务器首次收集自身的负载信息并计算实时负载量RL （i）发送到主服务器，主服务器根据相关公式划分为轻载、适载、重载三个队列；

（2）各节点服务器收集自身的硬件配置信息并计算最大负载量MAXL （i）发送至主服务器，主服务器根据权值公式计算相应权值WL （i），在队列中对其进行排序；

（3）各节点周期性更新负载信息，并计算实时负载量RL （i），判断实时负载量是否跨队列，是，转到 （4）；否，则周期性执行本步骤；

（4）将RL （i）发送到主服务器，主服务器重新为其划分队列；

（5）是否有文件请求到来，是，转到 （6）；否，等待；

（6）获取上传文件的负载量发送到主服务器，主服务器将其加入到上传队列中，并按一定规则进行排序，然后依次将队列中的请求循环分配到轻载队列中的各节点上，并向客户端返回服务节点的IP和Port端口号，完成上传操作。

3 算法性能测试与分析

3.1 测试指标

为了考察负载均衡算法的效率，考虑两个测试指标［10］：一是应答响应时间，浏览器向Web服务器提交一个请求到完成响应之间的总时间；二是平均吞吐量，是指单位时间内Web服务器成功处理的HTTP页面或HTTP请求数量。平均吞吐量越高，表示系统在单位时间内能处理的请求越多，系统的并发处理能力越强，系统的性能也就越好。

3.2 测试环境

在实验室搭建一个集群平台［11］，选择三台性能不同的服务器组成负载均衡集群系统进行实验。服务器配置如表1所示。使用Badboy（录制脚本）＋Jmeter测试工具，通过与已有算法的对比来验证新算法的效果。其物理布局如图3所示。

图3 测试环境布局

表1 服务器配置一览表

3.3 测试结果

（1）响应时间

响应时间对比图，如图4所示。

图4 响应时间对比

注：横轴是并发连接数，纵轴是上传完成的时间 （单位：秒），并发上传的是20M的文件。

参数R1＝0.15，R2＝0.1，R3＝0.15，R4＝0.3，R5＝0.3，α＝0.45，β＝0.85。

根据图4所示，在并发连接数较少时 （50、100），三种算法的响应时间相差不多，但是随着并发连接数的继续增加，本算法的优势越来越明显。对客户的请求作出快速的响应，提供了更好的服务。

（2）平均吞吐量

根据图5所示，系统平均吞吐量随着并发连接数的持续增加，本算法的优势才逐渐显现出来。因为负载均衡是解决高并发量带来的压力，所以低并发时，使用负载均衡没有什么明显的效果。

图5 平均吞吐量对比

4 结束语

通过分析总结现有的静态负载均衡算法和动态负载均衡算法所存在的不足，本文综合两者的优点提出了一种改进的集中式综合负载动态反馈的负载均衡算法。首先把节点服务器分成轻载、适载、重载三组队列，队列内采用权重轮转算法；其次，加入对上传请求负载量的考虑，能更好的将负载量重的请求分配到负载较轻的服务器上；并且改变定时更新为定量更新，减少了节点服务器与主服务器进行频繁的交互而带来的网络带宽的消耗，同时也能及时反映当时的负载情况。实验结果表明，最终达到了较好的负载均衡效果。

［1］ZHOU Songquan.An improved dynamic load－balancing algorithm for cluster［J］.Computer and Modernization，2012 （1）：135－139 （in Chinese）.［周松泉.一种改进的集群动态负载均衡算法 ［J］.计算机与现代化，2012 （1）：135－139.］

［2］TONG Ruixia.Research on cluster load balancing algorithm based on dynamic feedback mechanism ［D］.Wuhan：Wuhan University of Technology，2011 （5）：8－24 （in Chinese）.［童瑞霞.基于动态反馈机制的集群负载均衡算法研究 ［D］.武汉：武汉理工大学，2011 （5）：8－24.］

［3］LIU Hanbang.Feedback mechanism based on load balancing improve algorithm research ［D］.Qingdao：Qingdao Technological University，2010 （6）：8－26 （in Chinese）. ［刘汉邦.一种基于反馈机制的负载均衡改进算法研究 ［D］.青岛：青岛理工大学，2010 （6）：8－26.］

［4］SHI Hongyan.An improved strategy for load balancing in cluster nodes ［D］.Beijing：Beijing Technology and Business University，2010：13－21 （in Chinese）.［史鸿雁.一种改进集群节点负载均衡的策略 ［D］.北京：北京工商大学，2010：13－21.］

［5］LI Kun，WANG Baijie.Research on load balancing of web－server system and comparison of algorithms ［J］.Computer and Moderni－zation，2009 （8）：7－10 （in Chinese）.［李坤，王百杰.服务器集群负载均衡技术研究及算法比较 ［J］.计算机与现代化，2009 （8）：7－10.］

［6］DENG Chengyu，ZHANG Jiantao，LIU Yongshan.Research on dynamic load balancing strategy and corresponding model［J］.Computer Engineering and Applications，2011，47 （8）：131－134 （in Chinese）.［邓成玉，章剑涛，刘永山.动态负载均衡策略及相关模型研究 ［J］.计算机工程与应用，2011，47（8）：131－134.］

［7］ZHANG Congping，YIN Jianwei.Dynamic load balancing algorithm of distributed file system ［J］.Journal of Chinese Computer Systems，2011，32 （7）：1424－1426 （in Chinese）.［张聪萍，尹建伟.分布式文件系统的动态负载均衡算法 ［J］.小型微型计算机系统，2011，32 （7）：1424－1426.］

［8］WANG Chunjuan，DONG Lili，JIA Li.Load balance algorithm for web cluster system ［J］.Computer Engineering，2010，36（2）：102－104 （in Chinese）.［王春娟，董丽丽，贾丽.Web集群系统的负载均衡算法 ［J］.计算机工程，2010，36 （2）：102－104.］

［9］CHEN Chao，ZHAO Yuelong，WANG Wenfeng，et al.Improved dynamic load balancing strategy based on feedback［J］.Computer Engineering，2010，36 （14）：34－36 （in Chinese）.［陈超，赵跃龙，王文丰，等.基于反馈的改进动态的集群负载 均 衡 策 略 ［J］.计算机工程，2010，36 （14）：34－36.］

［10］HU Lijun.Web cluster server load balancing and performance ptimization ［D］.Beijing：Beijing University of Posts and Telecommunications，2010：33－50 （in Chinese）.［胡 利 军.Web集群服务器的负载均衡和性能优化 ［D］.北京：北京邮电大学，2010：33－50.］

［11］SHEN Wei.Research and realization of an improved load balancing algorithm based on LVS cluster ［D］.Beijing：China University of Geosciences，2010：36－46 （in Chinese）.［申伟.基于LVS集群的一种负载均衡改进算法的研究与实现 ［D］.北京：中国地质大学，2010：36－46.］