红领巾的系法-石家庄科技信息职业学院

　
2009
年第
8
期
文章编号
:1006< br>2
2475
(
2009
)
08
2
0007< br>2
04
计算机与现代化
JISUANJIYUXIANDAIHUA
总 第
168
期
服务器集群负载均衡技术研究及算法比较
李　坤
,
王百杰
(
西安电子科技大学计算机学院
,
陕西西安
710071< br>)
摘要
:
简要介绍了负载均衡技术的分类及其发展
,
重点介绍 了服务器集群负载均衡技术及应用。并对评价负载均衡优劣
的重要标准之一———负载均衡算法的种类做 了详细介绍及优缺点比较。对近年来一些新的负载均衡算法做了介绍。最
后
,
对服务器 集群负载均衡技术的发展前景做出了展望和预测。
关键词
:
服务器集群
;负载均衡
;
负载均衡算法
中图分类号
:TP301.6
　　　文 献标识码
:A
　　　
doi:.1006
2
2475.2009.0 8.003
ResearchonLoadBalancingofWeb
2
serv erSystemandComparisonofAlgorithms
LIKun,WANGBai
2
jie
(
SchoolofComputerScience,Xidia nUniversity,Xi
’
an710071,China
)
Abst ract:Thispapersimplyintroducesthetypesofloadbalanc ingstrategy,andmainlydescribestheconceptofloadbala ncingof
Web
2
includesadetailedpresentati onofthealgorithmsofloadbalancing,whichisakeypointo fjudging
loadbalancingstrategy,s,anintroduction ofsomenewloadbalancingalgorithmsis
ndofthispape r,theprospectofloadbalancingonWeb
2
serversy stemisshowed.
Keywords:Web
2
serversystem ;loadbalancing;loadbalancingalgorithms
0
　引　 言
随着
Internet
不断发展的应用需求
,
网络信息资
源的日益丰富
,
用户数量及对网络访问量呈爆炸式增
长
,
网络核心设 备的处理能力和计算强度也相应增
大
,
给传统的单一网络设备带来沉重的压力。而仅依
靠硬件升级会造成大量的资源浪费、随着业务量的不
断提升使设备陷入不断循环的硬件升级,
最重要的是
性能再卓越的设备也并不一定能满足当前业务量的
需求
,< br>于是多设备的集群系统由于其高性能、低价格、
可扩展性强等特点
,
正被得到广 泛使用。如何在处理
能力相当的多台网络设备之间进行合理的业务量分
配
,
使 得集群系统不至于出现一部分设备过忙而另一
部分设备却未充分发挥处理能力的情况
,
就成为一个
急需解决的问题
,
这样
,
负载均衡机制应运而生。
本文主要对服务器集群的负载均衡机制进行研
究
,
并对负载均衡的重要因素———均 衡算法进行详细
介绍和比较。
1
　负载均衡的分类
负载均衡建立在现有网络结 构上
,
提供一种廉
价、有效、透明的方法扩展网络设备和服务器带宽、增
加吞 吐量、加强网络数据处理能力、提高网络的灵活
性和可靠性。服务器集群负载均衡指服务器群中所
有服务器和应用程序之间流量负载的应用。负载均
衡技术除了可根据使用设备分为软件负载均衡和硬< br>件负载均衡以外还有其它分法
,
下面分别从不同的应
用需求对现有集群负载均衡 技术进行分类。
1.1
根据应用的地理结构分类
(
1
)
本地 负载均衡。
本地负载均衡是指对本地的服务器群做负载均
衡
,
充分利用现有设 备
,
避免服务器单点故障造成数
据流量的损失。其有灵活多样的均衡策略把数据流量合理地分配给服务器群内的服务器共同负担。即
收稿日期
:2008
2
08
2
13
作者简介
:
李坤
(
1985
2
)
,
女
,
陕西西安人
,
西安电子科技大学计算机学 院硕士研究生
,
研究方向
:
计算机网络与信息处理
;
王百杰
(
1984
2
)
,
男
,
山东菏泽 人
,
硕士研究生
,
研究方向
:
盲源分离
,
统计信号处理
,
计算机网络。

　
8
计　算　机　与　 现　代　化
2009
年第
8
期
使是再给现有服务器扩充升级
,
也只是简单地增加一
个新的服务器到服务群中
,
而不需改变现有网络结构、停止现有的服务。
(
2
)
全局负载均衡。
全局负载均衡是指 对分别放置在不同的地理位
置、有不同网络结构的服务器群间作负载均衡。全局
负载均衡主要用 于在一个多区域拥有自己服务器的
站点
,
为了使全球用户只以一个
IP
地址或域名就能
访问到离自己最近的服务器
,
从而获得最快的访问速
度,
也可用于子公司分散站点分布广的大公司通过
Intranet
(
企业 内部互联网
)
来达到资源统一合理分配
的目的。
1.2
根据应用的网 络层次
(
OSI
参考模型
)
(
1
)
链路聚 合技术
(
第二层负载均衡
)
。
图
1
　轮循算法链路聚合技术将多条物理链路当作一条单一的
聚合逻辑链路使用
,
网络数据流量由 聚合逻辑链路中
所有物理链路共同承担
,
由此在逻辑上增大了链路的
容量,
使其能满足带宽增加的需求。
(
2
)
现代负载均衡技术。现代负载均衡技术通常操作于网络的第四层或
第七层。第四层负载均衡将一个
Intern et
上合法注册
的
IP
地址映射为多个内部服务器的
IP
地 址
,
对每次
TCP
连接请求动态使用其中一个内部
IP
地址 。在第
四层交换机中
,
根据源端和目的
IP
地址、
TCP< br>或
UDP
端口号和一定的负载均衡策略
,
在服务器
IP
和
VIP
间进行映射。
第七层负载均衡控制应用层服务的内容
,
提 供了
一种对访问流量的高层控制方式
,
通过检查流经的
HTTP
报头
,
根据报头内的信息来执行负载均衡任
务。第七层负载均衡受到其所支持的协议限制< br>(
一
般只有
HTTP
)
,
并且检查
HTTP
报头会占用大量的系
统资源
,
在大量连接请求的情况下
,
负 载均衡设备自
身容易成为网络整体性能的瓶颈。
从图
1
中可以看出轮循算法的 明显优点是简单
易实现。但其缺点也是显而易见的
,
由于集群中服务
器的处理 能力各不相同
,
这种绝对公平的算法会使处
理能力强的服务器得不到充分利用
,
而处理能力较弱
的服务器任务堆积
,
严重的可能造成个别服务器瘫
痪。所以轮循算法适合在各个服务器处理能力相当
且网络中请求相对均衡的情况下使用。
(2
)
带有权重的轮循算法
(
WeightedRoundRobin)
。
带有权重的轮循算法是在轮循算法的基础上为
每台服务器增加了一个权值,
这个权值表示的是服务
器的处理能力。分配任务的时候就可以依照权值的
不同轮 循为每台服务器分配不同数量的任务。如图
2
所示
,
服务器
1
、
2
、
3
、
4
的权值为
2:1:1:1,
所以在轮
循时服务器
1
的任务分配量即为另外
3
台服务器的
两倍。
2
　常用的负载均衡算法
影响负载均衡有
3
个关键因素,
分别是负载均衡
算法、网络拓扑和负载均衡的粒度
,
本文中主要讨论< br>算法。负载均衡算法从大体上可分为无状态调度和
有状态调度两种
,
无状态调度 是指不考虑当前所有连
接状态及各节点之间当前的负载情况。
2.1
无状态调度
(
1
)
轮循算法
(
RoundRobin
)
。< br>图
2
　带权重的轮循算法
将来自网络中的请求按顺序依次分配给集群中
的每台服务器
,
如图
1
所示。
从图
2
中易得
,
该算法改进了轮循算法的弱点
,
保证了处理能力强的服务器可以得到更多的连接任

　
2009
年第
8
期李坤等
:
服务 器集群负载均衡技术研究及算法比较　
9
务
,
从一定程度上避免了出现处理能 力低的服务器由
于任务堆积而瘫痪的情况。但该算法没有考虑处理
请求的时间变化
,< br>可能导致服务器间负载的不均衡。
2.2
有状态调度
上述无状态调度可能造成集 群间负载不均衡甚
至单台故障。为了克服这个缺陷
,
有状态调度算法使
用一张 表记录当前所有连接情况
,
按照一定规则分配
任务。
(
1
)
最小连接数
(
LeastConnection
)
。
最小连 接数算法使用一张表记录当前每台服务
器的连接数
,
新的服务请求将被分配到当前连接 数最
少的服务器上。如图
3
所示
,
当新请求到达时
,
根据
表中记录的连接数分配至
3
号服务器。
图
4
　带权重 的最小连接数算法
　　
(
3
)
最快响应速度
(
Fa stest
)
。
最快响应速度算法记录每台服务器的请求连接
响应时间
,
当新请求到来时
,
分配至响应时间最短的
服务器上
,
使 其能最快获得处理
,
如图
5
所示。
图
3
　最小连接 数算法
由于充分考虑当前每台服务器的连接情况
,
最小
连接数算法能把请求平 滑分配到各个服务器上
,
实现
连接数量的负载均衡。但是要考虑
TCP
连接的响应
时间
,
当服务器处理能力不相同时
,
可能出现处理能< br>力不等的服务器的负载不均衡现象。
(
2
)
带权重的最小连接数
(
WeightedLeastCon
2
nection
)
。该算法是对最小连接数算法的改进
,
每台服务器
用一个权值来表示其处理能力,
在调度请求时应尽可
能地使服务器的连接数与其权值成比例。服务器群
1
、
2
、
3
、
4
的权值比例为
2:1:1:1,< br>当前连接数如下所
示
,
请求调度如图
4
所示。
与带权 重的轮循算法相同
,
服务器的权值代表了
服务器的处理能力
,
但是在 实际应用中
,
权值的设置
与很多因素相关
,
仅仅靠经验确定会带来很 大误差。
图
5
　最快响应速度算法
最快响应速度算法确保了最短的服务器响应 时
间
,
使任务能很快得到分配处理
,
而不会因为响应时
间过 长使任务延时。此种均衡算法能较好地反映服
务器的当前运行状态
,
但最快响应时间仅 仅指的是负
载均衡设备与服务器间的最快响应时间
,
而不是客户
端与服务器间 的最快响应时间。
3
　新的负载均衡算法
从文中研究可得
,
动态调度 由于考虑到服务器的
负载和自身处理能力
,
比静态调度优越
,
可是仍 存在
一定问题
,
比如
:
由于各个连接请求不同
,
当 前连接数
并不能真实反映服务节点的负载情况
;
由于响应时间
的不同
,
负载均衡器对各节点连接数的记录与节点真
实的连接数量之前可能会存在误差
;随着并发连接数

　
10
计　算　机　与　现　代　化
20 09
年第
8
期
量的增加
,
负载均衡器本身可能成为服务的瓶 颈。
近年来
,
新的、更有效的负载均衡算法已成为国
内外研究机构的研究热点 之一
,
本文对其中一些研究
成形并证明有效的算法加以概要介绍。
3.1基于多参数的负载均衡算法
种细粒度的算法
,
能有效提高集群的性能。经过测试
,
文献
[9]
得出
LARD
在
CPU
及磁盘速度方面都比
带权值的轮循算法
(
WRR
)
优越。
3.3
基于遗传算法的负载均衡策略
文献
[8]
提出了一种基于多参数的负载 均衡算
法
,
与传统算法只考虑
CPU
排队情况不同
,
该算法基
于分布式服务器集群
,
其中每个节点使用了一些不同
的参数
,
如
CPU
负载、网络负载以及内存使用。根据
当前负载情况把节点分为< br>4
个等级
:
空置
(
idle
)
、闲
(
low
)
、中等
(
normal
)
和忙
(
high
)
。对每个节点来说
,
CPU
利用率
(
cpu-u
)
,CPU
队列长度
(
nr
)
,
内存利用
率
(
mem-u
)
和网络负载
(
net-u
)
都要被考虑到
,
用
来决定该节点是处于
4< br>个等级中的哪一个。
当有新请求到来时
,
如果当前节点空置
,
则由当
前节点接收并处理请求。下一个选择是其它任何一
个空置的节点。如果当前节点处于忙的 状态
,
下一个
选择是一个低负载的节点。如果上述条件没有选择
出来一个节点
,
这个请求将由当前节点接收。
文献
[8]
经过测试得到
,
文中算法的总体性能比
单纯基于
CPU
队列长度的算法优越
43.5 %
。仅仅在
三个参数
,CPU
利用率、网络负载和内存利用率都很
低 的情况下基于
CPU
队列长度的算法才优于文中提
出的算法。当网络中有较大负载和< br>
或者内存使用较
大时
,
文中提出的算法有较好的性能。
3.2
基于内容请求的负载均衡算法
遗传算法是一种基于遗传和基因的搜索算法
,
通
过对问题的求解对象过去和现在的变化
,
最终求得问
题的最优解。文献
[11]
提出的遗传算法用于动态负
载均衡策略中时
,Web
服务器负载均 衡可以描述为
:
有
N
个新到的任务分到
M
个服务器节点,
各服务器
负载状况不同
,
目标是要找到一个最优的调度方法
,
使得整个任务处理的时间最短。
设服务器节点
i
所分配的任务数为
k
i
,
则整个分
配方案的基因编码为
:k
1
,k2
,k
3
,
…
,k
M
。按照随机的
方 式产生初始种群。文献
[11]
中以节点处理请求的
时间的倒数作为适应度
,
选取个体进行复制。即对以
概率被选中的分配方案中的两个服务器上分配的任
务数进行 交叉操作
,
从而产生新的分配方案。在选中
的个体内
,
任意选取个体 的两个各不相同字符
,
对其
有效位进行交换操作
,
产生新的个体。由 于遗传算法
本身是一种反复迭代的搜索算法
,
必须确立一个收敛
条件保证算法 及时终止。文献
[11]
预先设定一个最
大的繁殖代数
N
max。
经过测试可得
,
文献
[11]
提出的基于遗传算法
的 负载均衡策略使得各个服务器节点的
CPU
利用率
相对均衡
,
在客户 机任务请求数量大的情况下
,
这个
优势会明显地表现出来。
3.4
基 于动态反馈的负载均衡算法
文献
[9]
提出的
LARD
(
L ocality
2
AwareRequest
Distribution
)< br>是一种基于内容请求的负载均衡算法
,
该算法中
,
所有的服务器被认为 配置及处理能力相
当
,
唯一不同的是各个节点的当前负载状况。
图
6
　
LARD
算法
如图
6
所示
,
前端分配器 根据用户请求的
URL
解析出具体的服务类型
,
按照规则选择最近的服务节< br>点接收请求。算法定义了两个阈值作为衡量节点空
闲与否的标准
,T
low(
当前活跃的连接数
)
和
T
high
,
当节点负载低于
T
low
时
,
认为节点空闲可以接收新的请
求
;
当节点负载高于
T
high
时
,
则认为当前 节点忙并可
能引起延时及拥塞
,
于是该节点在当前时刻不接收新
的连接请求。
由分析可得
,
基于内容识别的负载均衡算法是一
文献
[12]
提出了一种透明动态反馈负载均衡技
术
,
该算法引入一个负载冗余
,
既考虑服务器节点的剩
余节点处理能力
,
又考虑各个后台服务器的当前实际
负载
,
还考虑了在某个时间段之间负载均衡。系统采
用一个主
Linux服务器
(
LinuxVirtualServer,LVS
)
与
每一个服务器节点建立长期稳定的
TCP
连接
,
并维护
着一张记录各 节点负载信息表。
LVS
除了具有客户请
求队列外
,
还有负载信息和 冗余信息两个队列
,
前者按
各服务器节点的负载轻重
,
降序存放各服 务器节点号
(
ID
)
和权值
W
i
;
后者用 来存放两个时间片之间的某个
时刻来了新任务请求后
,
按各个服务器节点负载冗余量
D
i
降序排列服务器节点号和对应的负载冗余量
,
便
于算法动态调整在两个时间片之间新来任务请求的分
配和各个服务器节点的负载均衡性。该算法综合CPU
负载、内存负载及
IO
使用率得到节点的真实负载
i
B< br>real
。反馈调节根据节点的负载情况及反馈进行负载
(
下转第
15
页
)
调节
,
提高集群利用率。

　
2 009
年第
8
期秦亮等
:
软件可靠性
J
2
M
模型的特性分析　
15
了数值实验证明了模型方程解的有效性与正确性。
但 是
,
上述方法还存在一些不足
,
模型应用的通用性
还不是很强
,
解的精度仍有待提高
,
这都是在以后工
作中要继续努力解决的地方。参考文献
:
[1]
　徐仁佐
,
郑人杰
.
软件可 靠性模型与应用
[M].
北京
:
清
[7]
　方木云
,
李锐
.
软件可靠性评估研究
[J].
微机发展
,
2002,12
(
1
)
:11
2
13.
[8]　
LittlewoodB,ianreliabilitygrowth
modelfo rcomputersoftware[J].ware
Engineering,1973,22:3 32
2
346.
[9]
　徐仁佐
,
等
.
软 件可靠性专家系统
(
SRES
)
中经验模型的
奇异性问题与参数估计 方法
[J].
计算机学报
,1998,21
(
2
)
:145
2
153.
[10]
宋晓秋
.
软件可靠性
J
2
M
增长模型的特性分析
[J].
系统
华大学出版社,1994:8
2
9.
[2]
　
okofSoftwareRe liabilityEngineering
[M].McGraw
2
Hill,19 96.
[3]
　蔡开元
.
软件可靠性工程基础
[M].
北京
:
清华大学出版
工程与电子技术
,1997
(
9
)
:44
2
46,70.
[11]
丛珉
,
陆民燕,
等
.
软件可靠性预计方法研究及实现
[J].
北京航空航天大 学学报
,2002,28
(
1
)
:34
2
38.< br>[12]
韩成宇
,
侯朝桢
,
徐勇
.
带失效因 子的
J
2
M
软件可靠性预
社
,1995:53
2< br>54.
[4]
　黄锡滋
.
软件可靠性、安全性与质量保证
[M ].
北京
:
电
计模型
[J].
火力与指挥控制
,2 006,31
(
3
)
:18
2
20.
[13]em entandcontinuousimprovementofsoft
2
warereli abilitythroughoutsoftwarelife
2
cycle[J].Jou rnalof
SystemsandSoftware,1999,47
(
2
2
3
)
:189
2
195.
[14]
方木云
,
屈玉贵
,
赵宝华
.
软件可靠性
JM
模型完全排 错假
子工业出版社
,2002:36.
[5]
　陆民燕
.
软 件可靠性参数研究
[J].
北京航空航天大学
学报
,2001,27
(
2
)
:241
2
244.
[6]
　
Je linskiZ,rereliabilityresearch[J].Sta
2
tisti calComputerPerformanceEvaluation,1972
(
2
)
:10
2
12.
设的修改
[J].
小型微型计算机系统
,2001,22
(
2
)
:199
2
200.(
上接第
10
页
)
Honolulu,HI,USA,1996 :850
2
856.
[3]
　
ficationofdynamic loadbalan
2
cingstrategiesinanetworkofworkst ations[C]FifthInterna
2
gton,
USA,2008:12 63
2
1265.
[4]
　刘高峰
.
负载均衡技术全攻略< br>[EBOL].http:www.
,2001
2
06
2
26 .
[5]
　王霜
,
修保新
,
肖卫东
.Web
服务器集群的负载均衡算法
经过测试可得
,
文献
[12]
提出的基 于动态反馈的
负载均衡算法使各个节点的负载趋于稳定
,
能有效地
减少平均应 答时延
,
提高了系统资源利用率和服务器
的性能。
4
　结束语
近年来
,
负载均衡的研究取得了很大的成就
,
但
是随着应用和体系 结构的发展
,
研究需继续进行。负
载均衡算法仍然是国内外研究者的研究热点
,
现有的
负载均衡算法须被改进以适应更加复杂的应用。在
设计负载均衡算法的时候< br>,
要考虑到应用的不同
,
如
一些负载均衡算法适用于大的并行处理,
一些算法在
处理短小的任务时较有优势。另外
,
在集中式的服务
器集群中
,
即负责处理负载均衡的是一台服务器
,
还
需解决的是负 责处理负载均衡的服务器成为瓶颈
(
bottleneck
)
和单点故障(
one
2
nodefailure
)
的问题。
参考文 献
:
[1]
　
ValeriaCardellini,MicheleCol ajanni,
2
icloadbalancingonWeb
2
serve rsystem[J].IEEEInternet
Computing,1999,3
(3
)
:28
2
39.
[2]
　
Andrese nD,TaoYang,:Towardsascala
2
bleWorldWideWebs erveronmulticomputers[C]Proceed
2
ingofthe10 thInternationalParallelProcessingSymposium.
研究< br>[J].
计算机工程与应用
,2004,40
(
25
)
:78
2
80,99.
[6]
　李红瑞
,
胡子飞
,
潘清
.
基于集群的
Web
服务器关键技
术研究
[ J].
计算机科学
,2002,29
(
9
)
:209
2
212.
[7]
　
KerdlapananD,t
2
b asedloadbalancing
withmulticastandTCP
2
h andoff[J].
(
25
2
28
)
:348
2
351.
[8]
　
PaulWerstein,HailingSitu,l ancingina
clustercomputer[C]SeventhInternationa lConferenceon
ParallelandDistributedComputing,A pplicationsandTechnol
2
,Taiwan,2006:569
2
577.
[9]
　魏臻
,
王雪辉
,
周霞
.
基于内容识别的
Web
集群负载均衡算法
IEEEXplore,2003 ,2
的研究
[J].
计算机工程与设计
,2006,27
(
18
)
:3410
2
3412.
[10]
孙林
,< br>罗大庸
,
张航
.
基于遗传算法的
Web
服务器集群负 载
均衡研究
[J].
计算机测量与控制
,2006,14
(
10
)
:1364
2
1365.
[11]
龚梅
,< br>王鹏
,
吴跃
.
一种集群系统的透明动态反馈负载均
衡算法[J].
计算机应用
,2007,27
(
11
)
:26 62
2
2665.
[12]
田绍亮
,
左明
,
吴绍伟
.
一种改进的基于动态反馈的负载均
衡算法
[J].
计算机 工程与设计
,2007,28
(
3
)
:572
2
5 73,728.