一种基于内容的web集群服务器负载均衡算法


近年来,服务所提供的信息的种类和数量都有了 Web 很大的变化,所以对于高性能低价格的服务器的需求很大, 而集群服务器正可以符合这种要求。对于集群服务器的应 用,各个节点需要协同工作来处理一个请求,请求的合理分 配将决定对请求响应的质量,这就是集群服务器中一个关键 性的问题——负载均衡问题。 集群服务器的负载均衡算法主要分为静态算法和动Web 态算法。静态算法以章文嵩博士的为代表,不考虑真实LVS 节点的实际负载情况[1, 2],而动态的负载均衡算法则要考虑 当前实际负载。近几年的研究工作也主要是对动态负载均衡 的研究,基于的负载均衡算法是研究的热点之一,文献DNS 中由得到服务器节点的相关负载信息,进行负载均[3]DNS 衡。但这种方式要求不断地和服务器通信,增加了DNSWeb 网络的通信量,而文献引入了一种新的负载描述方法,[4] 这种方法可以在必要的时候才进行负载状态的通信,为了提 高服务的质量[5]则引入了属性,在考虑的前提下选QoSQoS 择负载最小的节点来处理任务。文献主要是考虑任务大[6] 小的情况下采用遗传算法来分配任务,但计算量比较大, 等则通过修改协议的方法提供负载均衡;文献Kostin A.E 则在对任务进行了更详细描述的基础上进行负载均衡。[8, 9] 本文在集群服务器特点的基础上提出了一种基于内Web 容的负载均衡算法,该算法引入了一个反馈环节以实现动态 的负载均衡,从而避免了一般动态均衡方法的不断读取后台 负载的缺陷,最后讨论了算法的测试结果。 本文中的数学符号1 t :请求的当量处理时间; fl :被请求文件的长度; T :被请求文件的类型; n :集群中节点的个数; i ni ££1:,为节点号; iw i:给集群中节点分配负载时的权重; i dl i:真实节点的当量负载; jr j:节点中资源的利用率; ja j:资源的利用率的权值; iR i:节点上当前的请求个数; i cpur i:节点的利用率; CPU i memr i:节点的内存利用率; i netr i:节点的网络利用率; i reall i:节点的真实负载; i reall i:节点归一划处理后的负载; )( realW lE :集群的加权负载均值; )( reallD :归一划处理后的负载的均方差。 基于内容的负载均衡算法2 在本文的研究集群服务器中,包含一个负载均衡节Web 点,主要负责请求的转发,集群中其它节点为真实服务器, 负责处理具体的请求,这些节点可以是单个的,也可以PC 是一个服务器。在本文中,为了描述这种处理能力的区别, iw为每一个节点赋予一个分配任务时的权值,这样每个真 { }iwi , iS实节点就可以看作是一个矢量,用来表示。因 LB此,本文的研究环境可以看作是由一个负载均衡节点和 基金项目:国家自然科学基金资助项目();西安交大博60175015 通股份有限公司基金资助项目 作者简介:任彦琦(1978-,) 男,硕士生, 主研方向:集群服务器 的负载均衡算法和优化;彭勤科、胡保生,教授 定稿日期:2003-12-16 : E-mail renyanqi@cpc.xjtu.edu.cn 一种基于内容的集群服务器负载均衡算法Web 任彦琦,彭勤科,胡保生 西安交通大学系统工程研究所,西安( 710049) 摘要 :提出了一种基于内容的集群服务器负载均衡算法,该算法通过引入一个衡量不同内容任务量并利用当前真实节点上的连接数和Web 请求内容的任务量以及真实节点的处理能力来调整服务器负载。同时,算法引入了一个反馈环节,将真实节点的负载信息反馈到负载均衡 器,让负载均衡器调整自己的负载均衡策略,提高它的自适应能力。 关键词:服务器;集群服务器;负载均衡算法;反馈系统WebLinux A Content-based Load-balancing Algorithm of Web Cluster REN Yanqi, PENG Qinke, HU Baosheng (System Engineering Institute, Xi'an Jiaotong University, Xi'an 710049) 【】Abstract This paper presents a content-based load-balancing algorithm, and studies on the following two questions. First, the nodes load by three variables, the node weight, connection numbers and the requested contents length are measured. Second, a feedback is brought in, to balance the load more optimization . The weight of each node interval is adjusted according to the real load of each node. 【】Key words Web server; Linux cluster server; Load-balancing algorithm; Feedback system 第31卷 第2期 Vol.31 № 2 计 算 机 工 程 Computer Engineering 2005年1月 January 2005 ·网络与通信 · 中图分类号: TP312 文章编号:1000— 3428(2005)02 — 0122— 03 文献标识码:A — 122— { }nSSS L21 ,一个节点集合组成。本文中,将一个客户请 求也同时定义为一个任务,下面的描述中将不作区分。 基本负载均衡算法2.1 为了衡量请求的大小,文献引入了当量处理时间[8, 9] t t参数,并对的含义进行了如下修改: t 为用一个标准节点处理对应请求时的处理时间,这样 t 主要与请求的以下两个方面有关,而与其它参数无关: 与文件的长度有关,如果文件较大的话,处理的时间比较(1) 长,并且造成网络的负载增大;I/O 与文件类型有关,如果是动态请求,则要考虑请求所触发的(2) 操作。 t T通过以上分析可以看出参数主要和文件的类型、静 fl态文件的长度有关,即 ),(1 flTft = (1) t根据这个参数,可以将服务中所有请求按照的大 Web t t小分类,将值相近的请求归为一类,用一个统一的来表 t示,首先是通过经验来给定,然后在算法运行过程中,通 t过统计自学习值。 t通过对的定义,一个真实节点的负载可以表示为当前 真实节点上所有请求的当量处理时间之和与这个节点的权值 的比值,即 i R k k i d w t l i å == 1 i dl定义为真实节点的当量负载。 i 当新的请求到达时,根据请求的内容所请求网页的内( 容、类型决定请求的当量处理时间,然后根据以下算法挑)t 选真实节点来处理请求:i )min( i dli = (2) 这种分配方法,权值越高的得到新的请求的几率越大, 且请求的大小越大,分配到权值高的节点上的几率也越大。 真实负载评估2.2 真实负载评估主要是在真实节点上计算真实节点上的负 载。真实节点的真实负载是一个多维数据,也就是节点中各 个资源的利用率的总体标识了这个节点的真实负载,为了得 到一个负载的评估参数,可以根据各个参量对于节点负载的 影响程度进行加权平均: å = = 1j i jj i real ral (3) 其中, 1 1 =å =j ja 。 实际情况下,集群的服务不同,影响大的参数也不同。 对于服务主要是文件的传输,网络负载的影响最大,Web, 其次由于动态请求和读取文件的原因,使得负载和内存CPU 负载的影响也比较大,因此,本文的真实负载用下式计算: i net i mem i cpu i real rrrl *** γβα ++= 5.0,2.0,3.0 === γβα根据文献取。[10], i reall下面来讨论和那些变量有关。首先,真实节点的负 载是由于处理请求而产生的,因此,请求的转发规则是影响 真实负载的直接原因。而转发规则主要是根据当时各个节点 的权重、当量负载以及新到请求的当量处理时间来决定的, 所以节点的负载主要是由这些量决定: ),,(1 tlwgr i di i net = ),,(2 tlwgr i di i cpu = (4) ),,(3 tlwgr i di i mem = i reall最终,节点的真实负载也就和真实节点的权值、当前 当量负载以及新到请求的当量处理时间相关: ),,( )),,(),,,(),,,(( ),,( 3212 2 tlwe tlwgtlwgtlwgf rrrfl i di i di i di i di i mem i net i cpu i real = = = (5) 参数调节2.3 这一部分用来处理反馈,主要调整基本负载均衡算法的 参数和集群的规模,以达到优化负载均衡算法,提高集群利 用率的目的。 首先来讨论关于集群规模的调整。为了衡量集群的利用 率,引入了一个判断标准,加权负载均值 å å = == n i i n i i reali realW w lw lE 1 1)( (6) 它可以用来标识集群的利用率,此均值的范围应该为 %580 ± ,当负载均值超过最大阈值%时,集群的规模需 85 要增加;当负载均值低于最小阈值%时,集群的规模可以75 减小。 然后来讨论集群负载均衡性的调整。集群中各个节点负 载的均衡性可以通过负载的均方差来衡量,测量出来的负载 均方差没有一个可比的标准,为了使得负载均方差具有可比 性,首先将测量到的负载的评估值作几何归一化处理,这样 就得到一个可比的负载均方差,有利于同自身以及和其他解 决方案进行比较。归一化处理方法如下: å = = n k i i real i i reali real wl wll 1 2)/( / (7) 处理后,计算具有可比性的负载均方差: 1 ))(( )( 1 2 - - = å = n lEl lD n i real i real real (8) n l lE n i i real real å == 1)(其中, 这个负载均方差就可以标识集群的负载均衡程度,当负 载的均方差超过阈值时,集群内的负载没有得到很好的均 衡,需要调整基本负载均衡算法的参数;当负载的均方差小 于阈值时,则说明集群的负载均衡状况比较好,而这个阈值 需要通过大量的试验来测得。 ),,( tlwel i di i real =由式,,即真实负载和节点上分(5) i dl配的所有请求的当量处理时间、系统中各真实节点的权 — 123— iW t重以及刚刚到达的请求的当量处理时间有关,根据公 式、式,可知真实节点负载的均方差也和这几个量相(7) (8) 关,即 2 1 (()) () 1 (,,) n i realreal i real i id lEl Dl n hwlt = - = - = å 所以,当均方差较大时可调整两个量,一个是请求的当量处 理时间的估计值,另一个是节点的权重,由于请求的当量处 理时间的调整是由统计来完成的,因此,最终调整量确定为 iw真实节点的权重,由于当权重大时,分配的请求量也大, 因此,权值的调整应该是对负载较重的权值调小。 真实节点的权重用来描述真实节点的处理能力,定义这 10 << iw个值是一个百分数,即,所以,调整权值的算法 i iw如下:如果真实节点当前的权值为,当前的真实负载 i reall i ' iw为,节点的新的权值为 )( )(/ realw realwi i real lE lEwlA -= λ Aww ii -='设 (10) λ 10 << λ其中,是一个调整的步长,,用来控制每次调 整的大小,以减小系统的振荡。 这个调整的过程可以用图来表示。2 f(t,W)节点权重 (W) 节点负载 (RLoad) 请 求 大 小 ( t ) g1(RLoad) - + E(RLoad) 负载均方差 E(Rload) g2(RLoad) - 图反馈图2 测试结果及分析3 对本文提出算法,我们完成了一个基于的实现,并Java 对其进行了测试,测试环境为一个的集群服务器,其8CPU 中选取个节点为负载均衡节点,而其它个节点则作为服务17 结点,当需要内容的分类处理时,选择个服务结点来处理5 以下的请求,而另外两个节点处理以上的请100kB100kB 求,测试结果及分析如下: 每秒连接数和吞吐量随节点数的增加的变化。从图(1) 、图可以看出,当节点数增加时,吞吐量的变化首先增34 加,而后大概在后台有个节点时达到了峰值,这表明当后4 台达到个节点时,主节点饱和,成为整个系统的瓶颈。而4 每秒连接数基本上也是当后台为个节点时,主节点饱和。4 任务大小不同的请求分开转发到不同的节点上和不(2) 区分任务时的比较 12.3 12.4 12.5 12.6 12.7 1 3 5 7 节点数 每秒连接数 图每秒连接数的变化3 123 124 125 126 127 128 1 3 5 7 节点数 吞吐量(kbps) 图吞吐量的变化4 从图和图可以看出,首先当客户端不断增加时,每56 秒的请求数也在不断增加,当区分处理时,每秒的请求数也 比不区分处理时多;吞吐量也有类似的结果。 同时,应该注意到在这几个图中,第个测试点之后会7 有一个趋势上的反弹,这是由于程序的设置是在到达调整周 期本例为分钟后进行一次权值的调整。(30) 区分和不区分文件大小时的比较 (每秒连接数) 0 10 20 30 40 50 60 1 6 12 18 24 30 客户端数 每秒连接数 (request/second) 区分 不区分 图每秒连接数的比较5 区分和不区分文件大小时的比较(吞吐 量) 0 100 200 300 400 500 1 6 12 18 24 30 客户端数 吞吐量(kbps) 区分 不区分 图吞吐量的比较6 以上两组数据是没有进行程序的优化以及算法参数的优 化的结果,图提供了一个优化后的测试结果,可以看出性7 能有很大的提高。 连接数 0 50 100 150 200 250 20 30 40 50 60 70 80 90 100 客户端 每秒连接数 优化以后的情况 图优化后的结果7 — 124— (9) (下转第181页) 实验结果3.3 采用语音检测器传统方法的系统3.3.1 这个系统采用一种基于能量的语音检测器,去除输入信 号的以获得可用的语音。实验结果如表所示。20%~30%2 表采用传统方法系统的辨识结果2 训练/识别段长 去除比例 EER (%) 集内辨识正确率 (%) 2min/20s 20% 23.2 88.3 2min/40s 20% 17.6 91.7 4min/40s 25% 13.6 96.6 4min/1min 30% 13.2 96.4 采用高斯语音滤波器的系统3.3.2 采用高斯语音滤波器系统的辨识结果如表所示。3 表采用高斯语音滤波器系统的辨识结果3 训练/识别段长 EER (%) 集内辨识正确率 (%) 2min/20s 21.5 86.9 2min/40s 17.1 89.5 4min/40s 11.8 95.3 4min/1min 10.4 96.1 等错误率是集外虚警错误概率和(Equal Error Rate, EER) 集内漏报错误概率相等时的系统错误率。集内辨识正确率指 判决为集内说话人,并且正确辨识其身份的段占所有正确接 受为集内说话人的段的比例。 从上面的实验结果可以看到,高斯语音滤波的方法要优 于仅基于固定比例的传统语音检测器方法。在训练和识别段 长充分的情况下,系统的等错误率最多下降了。可能21.2% 的解释是,在更好地保留与说话人身份有关的信息的同时, 高斯语音滤波器趋向于去除更多一些录音,因此在段长充分 的情况下性能改善更明显。 结论4 本文提出了一种去除实际电话录音中噪音、静音等非语 音信号的新方法,在不同信道条件下都可以自动进行,并且 更好地保留了与说话人身份有关的信息。实验结果表明,采 用这种方法的系统的等错误率比传统方法最多下降了 。21.2% 参考文献 1 Doddington G R, Przybocki M A, Martin A V,et al.The NIST Speaker ——Recognition EvaluationOverview, Methodology,Systems,Results, Perspective. Speech Communication, 2000, 31(2): 225-254 2 Reynolds D A, Rose R C. Robust Text-independent Speaker Identification Using Gaussian Mixture Models.IEEE Trans.SAP,1995, 3(1): 72-83 3 Reynolds D A, Quatieri T F, Dunn R B. Speaker Verification Using Adapted Gaussian Mixture Models. Digital Signal Processing, 2000, 10(1): 19-41 4 Petrovska-Delacretaz D, Cernocky J, Hennebert J,et al.Segmental Approaches for Automatic Speaker Verification. Digital Signal Processing, 2000, 10(1): 198-212 5 Martin A, Przybocki M. The NIST 1999 Speaker Recognition ——EvaluationAn overview.Digital Signal Processing,2000,10(1): 1- 18 上接第页(124) 后台真实节点的负载状况截取一部分见表。在测(3)(),1 试这一组数据时,主要访问的文件是静态文件,主要的负载 变化是网络负载的变化,而对于网络负载,可以看出利用本 文实现的方法负载均衡的比较好,基本没有出现负载很不均 衡的情况,出现的差异基本上最大为单个请求引起的负载。 表本文实现的后台负载数据1 小结4 测试表明本文提出的算法是可行的,但是,算法中有的 参数如权值调整时间、内容分类方法等需要优化才能得到() 更好的结果,本文今后的工作是对算法的相关参数进行优 化,得到一个优化的参数配置,并且希望今后将使用遗传算 法的方式来进行控制,希望得到更好的性能。 参考文献 1 Colajanni M, Yu P S. A Performance Study of Robust Load Sharing Strategies for Distributed Heterogeneous Web Server Systems. IEEE Transactions on Knowledge and Data Engineering,2002-03/04,14:398 2 Cardellini V, Colajanni M, Yu P S. Dynamic Load Balancing on Web- server Systems. Internet Computing, IEEE, 1999-05/06, 3: 28-39 3 Colajanni M, Yu P S, Dias D M. Analysis of Task Assignment Policies in Scalable Distributed Web-server Systems. IEEE Transactions on Parallel and Distributed Systems, 1998-06, 9: 585-600 4 Rumsewicz M, Dwyer M. Preferential Load Balancing for Distributed Internet Servers. First IEEE/ACM International Symposium on Cluster Computing and the Grid, 2001 Proceedings , Brisbane, Qld. , Australia, 2001: 363-370 5 Zhang Jian, Hamalainen T, Joutsensalo J. QoS-aware Load Balancing Algorithm for Globally Distributed Web Systems. 2001 International Conferences on Info-tech and Info-net, 2001 Proceedings, ICII 2001 - Beijing ,2001, 2: 60-65, 6 Zomaya A Y, Yee-Hwei Teh. Observations on Using Genetic Algori - thms for Dynamic Load-balancing. IEEE Transactions on Parallel and Distributed Systems,2001-09, 12:899-911 7 Kostin A E, Aybay I, Oz G. A Rrandomized Contention-based Load- balancing Protocol for a Distributed Multiserver Queuing System. IEEE Transactions on Parallel and Distributed Systems, 2000-12, 11: 1252 8 Tan Ling, Zahir Tari. Dynamic Task Assignment in Server Farms: Better Performance by Task grouping. 2002 Proceedings ISCC 2002 Seventh International Symposium on Computers and Communications, 2002: 175-180 9 Buttazzo G C, Lipari G, Caccamo,et al. Elastic Scheduling for Flexible workload Management. IEEE Transactions on Computers, 2002-03, 51: 289-302 章文嵩服务器集群系统四10 . Linux(). http://www-900.ibm.com/ developerWorks/cn/linux/cluster/lvs/part4/index.shtml — 181— eth (kbps) bt1 158.33 164.67 0.00 225.00 bt2 144.00 190.33 128.33 187.67 bt3 140.00 0.00 169.00 134.67 bt4 146.00 0.00 158.00 137.00 Bt5 172.67 0.67 152.67 179.67 Bt6 0.33 170.00 129.00 130.67 Bt7 127.00 179.00 204.67 126.33 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
还剩3页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 2 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

adamchen

贡献于2013-09-05

下载需要 2 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf