（计算机应用技术专业论文）web服务器集群负载均衡技术研究.pdf

w e b 服务器集群负载均衡技术研究摘要随着计算机技术和i n t e r n e t 的飞速发展，人们对w e b 服务器的性能的要求也越来越高，负载均衡集群以其较高的性价比和良好的扩展性在w e b 服务器中得到了广泛的应用。因此如何更好的提高集群服务器的综合处理能力便受到了更多的关注。集群的负载均衡策略是提高集群整体性能的关键，其目的是根据处理机的性能来将任务合理的分配到后面的真实服务节点上，使各节点均衡的分担任务来最小化应用程序的执行时间，从而达到提高性能和服务质量。集群设计中的负载均衡算法的优劣将直接影响集群的性能。动态反馈是基于服务器的实时负载和响应情况，不断调整服务器间请求的比例，来避免有些服务器在过载时仍接收大量的请求，以此来达到提高整个集群系统的处理能力。本文详细讨论了集群的主要概念和特点，并分析了目前常用的集群技术。重点研究了负载均衡集群的原理和特点，详细研究了主要的负载均衡技术和常用的负载均衡算法，并着重分析了几种常用的负载均衡算法的优缺点，并结合动态反馈技术提出了一种新的改进算法，其中重点研究了负载状态的评估和权值动态调整的方法，最后通过构造仿真集群测试环境，并和其他方法对比分析验证该方法的有效性。仿真实验表明，该方法能有效的提高集群的性能，降低系统的延迟时间，提高系统的吞吐量，提高集群的利用率。关键词：集群，负载均衡，动态反馈t h er e s e a r c ho fio a db aia n cin go fw e b0iu s t e rs e v e r sm aidin g jin gf a ny o n g s h e n ga b s t r a c tw i t ht h ed e v e l o p m e n to ft h ec o m p u t e ra n di n t e m e t ，t h ed e m a n do fs e r v i c eo fw e bs e v e l 3b e c o m em o r ea n dm o r e ，t h el o a db a l a n c i n gd u s t e ri sw i d e l yu s e di nw e bs e r v e r sf o ri t sl o wp r i c ea n dh i g h e ra b i l i t ya n ds c a l a b i l i t y s op e o p l ea r em o 佗a n dm o r ei n t e r e s t e di nh o wt or a i s et h ei n t e g r a t e dp r o c e s s i n ga b i l i t yo ft h ec l u s t e rs e v e r t h es t r a t e g yo ft h el o a db a l a n c i n gi st h ec r i t i c a lo fr a i s i n gt h ef u n c t i o n , t h ep u r p o s eo fi ti st od i s t r i b u t et h ea s s i g n m e n tt ot h er e a ln o d eo ft h ed u s t e rd e p e n do nt h ea b i l i t yo ft h ep r o c e s s o r s ，f o rt h a tt h i sc a nr a i s et h ea b i l i t ya n dq u a l i t yo fs e r v i c e t h ed e s i g no ft h el o a db a l a n c i n gs t r a t e g yw i l la f f e c tt h ec l u s t e rf u n c t i o nd i r e c t l y d y n a m i cf e e d b a c kc a na d j u s tt h ep r o p o r t i o no ft h e $ e v e rb a s e do nn o d e sl o a ds t a t u s , i no r d e rt oa v o i da c c e p t i n gm o r er e q u e s tw h e no v e r l o a d i n g ，5 0t h a t t h i sc a l lr a i s et h ep r o c e s s i n ga b i l i t yo ft h ed u s t e r t h i sp a p e rd i s c u s s e st h ec o n c e p t i o na n dc h a r a c t e r i s t i co fc l u s t e r , a n da n a l y z e st h et e c h n o l o g yo fd u s t e rw h i c hi nc o m m o nu s e a n df o c u so fr e s e a r c h i n gt h ep r i n c i p l ea n dc h a r a c t e r i s t i co fd u s t e r , a n dr e s e a r c ht h et e c h n o l o g ya n da l g o r i t h mi nd e t a i l a n dt h e na n a l y z et h ea d v a n t a g ea n dd i s a d v a n t a g eo ft h ea l g o r i t h m t h e nd e s i g nan e ws t r a t e g yw i t ht h ed y n a m i cf e e d b a c kp r i n c i p l e a n ds e t u pt h es i m u l a t ee n v i r o n m e n ta n dt e s tt h em e t h o d i nt h ee n d ，t h ee x p e r i m e n ts h o w st h a tt h i sa l g o r i t h mc a nr a i s et h eq u a l i t yo fs e r v i c ea n dd e c r e a s et h ed e l a yt i m eo fc l u s t e re f f e c t i v e l y k e y w o r d ：c l u s t e r ，l o a db a l a n c i n g ，d y n a m i cf e e d b a c k原创性声明本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下，独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人承担。论文作者签名星耋刍二e ii t t l ：理乡：，关于学位论文使用权的说明本人完全了解中北大学有关保管、使用学位论文的规定，其中包括：学校有权保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文；学校可允许学位论文被查阅或借阅：学校可以学术交流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内容( 保密学位论文在解密后遵守此规定) 。签名：炙囊二裔日期：印二p导师签名：茑彦迈。，中北大学学位论文1 1 课题研究背景1 绪论随着计算机技术和网络的飞速发展，人们对计算机性能的要求也越来越高，尤其是i n t e r n c t 的深入发展，对人类的学习、工作和生活正产生日益深远的影响。随着服务内容和表现形式的不断丰富以及交互作用的不断增强，万维网不仅仅是一种内容发布平台，更是一种服务平台。而且随着技术和应用环境的不断发展，已有的服务和应用正逐步延伸到因特网上并以w e b 的方式提供。广阔的应用领域及日益增长的用户需求对作为服务的提供者与因特网的交汇点和基石网络服务器的性能提出了更高的要求。单台服务器性能的提高并不能彻底地解决这个问题，为此，提出了用多台服务器组成一个虚拟服务器系统的技术方案，以解决大用户量并发访问和大容量数据存储的问题，这种技术被称为服务器集群。它为飞速发展的因特网提供了一种易于扩展处理能力，且具有较高性价比的网络服务器解决方案。为了提高服务器的性能，人们提出了多种解决方案。从目前的研究情况来看，主要是从以下两个方面着手【l2 1 。一是从分析客户的访问行为入手，研究可以缩小响应时间的方法，如缓存和预取技术等。这些技术在现有服务器硬件设备的基础之上尽可能地提高系统的性能，但性能提高的程度有限。二是从服务器的硬件性能角度进行考虑，这又可分为单服务器策略和多服务器策略。单服务器策略是通过不断升级网络服务器的软、硬件资源，使其具有更高的性能以满足需求。然而这种方法随着负载的不断增长，会导致服务器不断地升级。经分析总结，单服务器策略存在如下不足：( 1 ) 升级过程繁琐，服务器的切换会使服务暂时中断，并造成原有资源的浪费；( 2 ) 越往高端的服务器，所花费的代价就越大；( 3 ) 服务器是单一故障点；( 4 ) 受到服务器硬件性能极限的限制。多服务器策略是从体系结构入手，将过去单一的服务器结构扩充为集群式多机服务1中北大学学位论文器结构。集群式多机系统是指将多台服务器连接起来协同完成共同的任务。这种改造可以显著提高服务器的总体性能。相对于单机系统而言，集群式多机系统具有很多单机系统无法比拟的优点。1 2w e b 服务器的现状当今计算机技术己进入以网络为中心的计算时期。由于客户服务器模型的简单性、易管理性和易维护性，客户服务器计算模式在网上被大量采用。在九十年代中期，万维网( w o r l dw i d ew e b ) 的出现以其简单操作方式将图文并茂的网上信息带给普通大众，w e b 也正在从一种内容发送机制成为一种服务平台，大量的服务和应用( 如新闻服务、网上银行、电子商务等) 都是围绕着w e b 进行。这促进i n t e r a c t 用户剧烈增长和i n t e r a c t流量爆炸式地增长，i n t e r n e t 连接主机数从1 9 9 5 年的5 , 0 0 0 ，0 0 0 增至2 0 0 0 年的7 0 ，0 0 0 ，0 0 0 ，可见增长趋势较以往更迅猛。i n t e m e t 的飞速发展给网络带宽和服务器带来巨大的挑战。从网络技术的发展来看，网络带宽的增长远高于处理器速度和内存访问速度的增长，如1 0 0 me t h e m e t ，a t m ，g i g a b i te t h e r n e t 等不断地涌现，1 0g i g a b i te t h e r n e t 即将就绪，在主干网上密集波分复用( d w d m ) 将成为宽带i p 的主流技术，l u c e n t 已经推出在一根光纤跑8 0 0 g i g a b i t的w a v e s t a r0 l s8 0 0 6 产品。所以，我们深信越来越多的瓶颈会出现在服务器端。很多研究标明g i g a b i te t h e m e t 在服务器上很难使得其吞吐率达到1 g b s 的原因是协议栈( t c p 口) 和操作系统的低效，以及处理器的低效，这需要对协议的处理方法、操作系统的调度和i 0 的处理作更深入的研究。在高速网络上，重新设计单台服务器上的网络服务程序也是个重要课题。比较热门的站点会吸引前所未有的访问流量，例如根据y a h o o 的新闻发布，y a h o o已经每天发送6 2 5 亿页面。一些网络服务也收到巨额的流量，如a m e r i c a no n l i n e 的w e bc a c h e 系统每天处理5 0 2 亿个用户访问w e b 的请求，每个请求的平均响应长度为5 5 k b y t e s 。与此同时，很多网络服务因为访问次数爆炸式地增长而不堪重负，不能及时处理用户的请求，导致用户进行长时间的等待，大大降低了服务质量。如何建立可伸缩的网络服务来满足不断增长的负载需求已成为迫在眉睫的问题。大部分网站都需要提供每天2 4 小时、每星期7 天的服务，对电子商务等网站尤为2中北大学学位论文突出，任何服务中断和关键性的数据丢失都会造成直接的商业损失。例如，根据d e l l的新闻发布，d e l l 现在每天在网站上的交易收入为一千四百万美元，一个小时的服务中断都会造成平均五十八万美元的损失。所以，这对网络服务的可靠性提出了越来越高的要求。现在w e b 服务中越来越多地使用c g i 、动态主页等c p u 密集型应用，这对服务器的性能有较高要求。未来的网络服务会提供更丰富的内容、更好的交互性、更高的安全性等，需要服务器具有更强的c p u 和i o 处理能力。例如，通过h t i v s ( s e c u r eh 1 曙)取一个静态页面需要的处理性能比通过哪的高一个数量级，h t r p s 正在被电子商务站点广为使用。所以，网络流量并不能说明全部问题，要考虑到应用本身的发展也需要越来越强的处理性能。研究表明，影响网络服务质量的关键因素是网络通信能力和服务器的性能。随着网络技术的发展，网络通信瓶颈效应日益减轻，服务器的性能正在成为制约网络服务质量进一步提高的关键所在。通过对上述发展情况进行分析可知，建立高性能、高可用和可伸缩的服务器系统来满足不断增长的负载需求己成为迫在眉睫的问题。1 3 集群的发展与研究现状服务器集群的概念最早起源于美国u i u c 大学n c s a 提出并实现的一个原型系统“n c s a s c a l a b l ew e bs e r v e rc l u s t e r ，【3 - 4 l 后来r i c e 大学、波士顿大学、c i s c o 公司及i b m公司等也加入了这个行列，提出了许多新方法，使服务器集群的研究得到了进一步的发展。当前有很多基于前端调度器的服务器集群产品，其中基于应用层的典型代表有r e v e r s e p r o x y 5 1 ，s w e b 6 l 和r i c e 大学的l a r d 7 1 ( l o c a l i t y a w a r er e q u e s td i s t r i b u t i o ni nc l u s t e r - b a s e dn e t w o r ks e r v e r ) 等。基于第四层的典型代表有b e r k e l e y 的m a g i c r o u t e r s l ，c i s c o 的l o c a ld i r e c t o r 9 ，1 0 1 、贝尔实验室开发的o n e i p 1 1 1 ，i b m 的t c pr o u t e r l l 2 1 和n c ：t w o r kd i s p a t c h e r 1 3 1 4 1 ，以及l i n u x 开源项目l v s ( l i n u xv i r t u a ls e r v e r ，l i n u x 虚拟服务器) 【1 5 】等。波士顿大学计算机系提出的d p r 1 6 】( d i s t r i b u t e dp a c k e tr e w r i t i n g ，分布式分组重写) 与m a g i c r o u t e r ，l o c a ld i r e c t o r 等在结构上有很大的不同，d p r 是一种无前端调度3中北大学学位论文器的服务器集群方案。国外i b m ，c i s c o 等公司和b e r k e l e y 、r i c e 、波士顿等大学在服务器集群方面做了大量的研究工作，并已形成商品化产品。近年来，国内的一些高校及科研院所也在服务器集群领域进行了相关的研究和产品化工作。清华大学、国防科技大学和中国科学院是较早开展此项研究的机构，红旗l i n u x 也相继推出了通用服务器集群系统软件，这些都说明服务器集群的优势和潜在的市场前景已引起了国内研究机构和厂商的极大兴趣。1 4 本文主要内容本文对计算机集群的关键技术进行深入研究，首先分析研究了计算机集群技术的基本概念和主要特点，并讨论了集群的主要分类和目前典型的集群；接着重点分析了负载均衡集群的结构和原理，总结了负载均衡的特点和优点，并研究了几种重要的负载均衡技术与方法，重点对比分析研究了目前常用的负载均衡算法的特点；然后分析研究了工业上常用的负反馈原理，并在此基础上设计了一种可以用于集群的负载均衡方法；最后构建仿真集群环境，通过实验对比分析该方法的性能。1 5 论文组织第一章绪论。介绍论文的研究背景及主要内容并简述论文的组织结构。第二章集群服务器概述。介绍计算机集群的主要基本概念，重点讨论了高可用性集群，高性能计算集群和高扩展集群及其中的关键技术和特点，并对目前存在的典型集群系统进行分析比较。第三章负载均衡技术。对负载均衡集群系统进行重点分析，讨论了负载均衡的基本原理和特点，以及重要的技术方法，最后研究了常用的负载均衡算法，并对算法特点进行详细对比分析。第四章动态反馈调度算法与实现。分析了动态反馈的基本原理和负载状态评估的方法，并在此基础上设计一个新的负载均衡调度算法。第五章仿真试验评测。对提出的动态反馈调动方法进行仿真实验环境构建与配置，并结合仿真结果进行对比分析。4中北大学学位论文望。第六章总结与展望。总结了本文主要的工作并对未来所要进行的研究工作进行展5中北大学学位论文2 1 集群的概念2 集群服务器概述集群并没有一个严格的定义。一般来说，可以这么理解集群的概念：集群系统是通过高性能网络( l a n 或删) 进行物理连接的计算机集合；这些计算机协同工作以完成共同的任务，同时为用户和应用程序提供单一的系统映像，即用户和应用程序与集群系统进行交互时，集群系统就像一台高性能的服务器。一般称集群中的计算机为节点( n o d e ) ，集群的节点可以是任意类型的计算机，包括p c 、工作站、对称多处理机s m p( s y m m e t r i c a lm u l t i p r o c e s s i n g ) ，甚至是大型机。简单的说，集群( c l u s t e r ) 就是一组计算机，它们作为一个整体向用户提供一组网络资源。这些单个的计算机系统就是集群的节点( n o d e ) 。一个理想的集群是，用户从来不会意识到集群系统底层的节点，在他们看来，集群是一个系统，而非多个计算机系统，该系统为客户工作站提供高可靠性的服务，并且集群系统的管理员可以随意增加和删改集群系统的节点。集群系统的结构如图2 1 所示。i可用性与单一系统映像基础设施操作系统节点操作系统节点操作系统节点l商用或专用互联图2 1 集群系统的典型结构6中北大学学位论文一个c l u s t e r 包含多台( 至少二台) 拥有共享数据存储空间的服务器。任何一台服务器运行一个应用时，应用数据被存储在共享的数据空间内。每台服务器的操作系统和应用程序文件存储在其各自的本地储存空间上。c l u s t e r 内各节点服务器通过一个内部局域网相互通讯。当一台节点服务器发生故障时，这台服务器上所运行的应用程序将在另一节点服务器上被自动接管。当一个应用服务发生故障时，应用服务将被重新启动或被另一台服务器接管。当以上任一故障发生时，客户将能很快连接到新的应用服务上。从上述集群概念的描述可知，集群的概念包含了两个方面的含义：一是从硬件方面考虑，强调独立、自治的计算机；二是从软件方面考虑，强调集群系统的整体性。2 2 集群的特点集群可看作是一组通过网络连接的工作站、p c 或服务器所组成的集合，它们以统一的方式对外提供透明的服务，从而发挥整体优势以提高服务质量。典型的集群系统具有如下特征：n 刀( 1 ) 可易用性：因为集群系统的单个节点仍旧是传统的平台，所以用户可以在他们平时就很熟悉的环境下面开发和运行应用程序。同时，这也可以让许多现有的程序可以不加以修改地运行在处理能力更强大的集群系统平台上，非常有利于保护用户已有的软件投资。( 2 ) 高可用性：高可用性包括可靠性和好的可用性等。在传统的系统中，如大型机和容错系统中，通常是以高费用为代价来提供高可用性。相反，在集群系统中，却是用低费用的组件来提供较高的可用性。集群系统可用性的实现，其关键技术是开发共享组件可用的软件。( 3 ) 可伸缩性：一个集群系统的处理能力可以简单地通过增加节点来加强。同时，集群的可伸缩性是多面的。包括资源的可伸缩性、应用的可伸缩性和技术的可伸缩性等。s m p 提供了处理器的可伸缩性，在集群系统中的可伸缩性可以是计算机的各个组件，如处理器、硬盘、内存或者i o 设备以及软件组件等。对集群的研究起源于集群系统的良好的性能可扩展性( s c a l a b i l i t y ) 。提高c p u 主频和总线带宽是最初提高计算机性能的主要手段。但是这一手段对系统性能的提高是有7中北大学学位论文限的。接着人们通过增加c p u 个数和内存容量来提高性能，于是出现了向量机，对称多处理机( s m p ) 等。但是当c p u 的个数超过某一阈值，像s m p 这些多处理机系统的可扩展性就变的极差。主要瓶颈在于c p u 访问内存的带宽并不能随着c p u 个数的增加而有效增长。与s m p 相反，集群系统的性能随着c p u 个数的增加几乎是线性变化的。图2 2 显示了这种情况。jc p u + 数图2 2 集群系统与对称多处理系统的可扩展性比较( 4 ) 透明性强：服务器集群系统对外表现为一台高性能的服务器，服务器节点的增删不会中断服务。( 5 ) 管理方便：集群系统的图形管理界面能监视和管理整个集群系统中的资源和服务。管理人员通过简单的操作就可以对集群中的工作节点或控制节点进行配置管理工作。( 6 ) 良好的性能价格比：这是因为组成集群系统的服务器和标准网络设备采用的一般都是成熟的商用产品；集群系统良好的性能价格比是它受到人们青睐的重要因素，它可以把一些廉价系统组合在一起协同工作，在总体上的性能却可以超过大型机甚至巨型机。美国亚特兰大的e m o r y 大学，c e s d i s 歌德航天飞行中心和加利福尼亚技术学院的科学技术人员、研究人员和实验室工作人员一起在1 9 9 7 年建立了1 6 个节点的p 2 0 0 微机集群的b e o w u l f 系统，只用5 万美元而使系统达到每秒1 0 亿次浮点运算8中北大学学位论文的能力。使用大众化的p c 通过l a n 互联而达到超级计算机的功能和能力。2 3 集群的分类目前应用最为广泛的计算机集群可以分为三大类：高可用性集群、高性能计算集群和负载均衡集群。下面对这三种集群做一简单的介绍。2 3 1 高可用性集群高可用( h i g h a v a i l a b i l i t y ) 集群，简称h a 集群。目的是在系统出现故障时，仍能继续对外提供服务。高可用性集群的设计思想就是要最大限度地减少服务中断时间，这类集群致力于提供高度可靠的服务，是指以减少服务中断( 当机) 时间为目的的服务器集群技术。计算机系统的可用性( a v a i l a b i l i t y ) 是通过系统的可靠性( r e l i a b i l i t y ) 和可维护性( m a i n t a i n a b i l i t y ) 来度量的。工程上通常用平均无故障时间( m t i t ) 来度量系统的可靠性，用平均维修时间( m t n t ) 来度量系统的可维护性。于是可用性被定义为：m 硎( m t r f + m r n 己) * 1 0 0 。高可用性的目标就是使当机时间以及故障恢复时间最小化。随着全球经济的增长，世界各地各种各样的组织对计算机系统的依赖都在不断增加，电子贸易使得商务活动一周七天2 4 小时不间断的进行成为了可能。新的强大的应用程序使得商业和社会机构对日常操作的计算机化要求达到了空前的程度，趋势非常明显，这需要不问断的、稳定的计算机系统。这种需求的快速增长，使得对系统可用性的要求变得非常重要。现在许多公司和组织的业务几乎完全依赖于计算机系统，任何的当机都会造成严重的损失，关键r r 系统的故障可能会导致整个商业运作系统的瘫痪，因此每一分钟的当机都意味着收入、生产和利润的损失，甚至是市场份额的减少。高可用集群就是采用集群技术来实现计算机系统的高可用性。高可用集群通常有两种工作方式：( 1 ) 容错系统：通常是主从服务器方式。从服务器检测主服务器的状态，当主服务工作正常时，从服务器并不提供服务。但是一旦主服务器失效，从服务器就歼始代替9中北大学学位论文主服务器向客户提供服务。( 2 ) 负载均衡系统：集群中所有的节点都处于活动状态，它们分摊系统的工作负载。一般w e b 服务器集群、数据库集群和应用服务器集群都属于这种类型。2 3 2 高性能计算集群高性能计算集群( h i g hp e r f o r m a n c ec o m p u t i n gc l u s t e r ，简称h p cc l u s t e r ) ，是指以提高科学计算能力为目的计算机集群技术。高性能计算( h i g h p e r f o r m a n c ec o m p u t i n g )是计算机科学的一个分支，它致力于开发超级计算机，研究并行算法和开发相关软件，即是采用集群技术来研究高性能计算。h p cc l u s t e r 是一种并行计算集群的实现方法。并行计算是指将一个应用程序分割成多块可以并行执行的部分并指定到多个处理器上执行的方法。目前的很多计算机系统可以支持s m p ( 对称多处理器) 架构并通过进程调度机制进行并行处理，但是s m p 技术的可扩展性是十分有限的，比如在目前的i n t e l架构上最多只可以扩展到8 个c p u 。为了满足某些“计算能力饥渴 的科学计算任务，并行计算集群的方法被引入到计算机界。著名的“深蓝计算机就是并行计算集群的一种具体实现。2 3 3 负载均衡集群负载均衡集群技术就是带均衡算法的服务器集群。目的是提供和节点个数成正比的负载能力。负载均衡集群通过在系统节点间合理分配工作负载来提高系统的整体性能，如减少系统的平均响应时间等。这类集群很适合提供大访问量的网络服务。负载均衡集群在多节点之间按照一定的策略( 算法) 分发网络或计算处理负载。负载均衡建立在现有网络结构之上，它提供了一种廉价有效的方法来扩展服务器带宽，增加吞吐量，提高数据处理能力，同时又可以避免单节点故障。以w e b 访问为例，后台的多个w e b 服务器上面有相同的w e b 内容，i n t e m e t 客户端的访问请求首先进入一台服务器，由它根据负载均衡算法合理地分配给某个w e b 服务器。每个w e b 服务器有相同的内容做起来不难，所以负载均衡算法选择是关键问题。1 0中北大学学位论文2 4 典型集群系统简介近年来，随着w e b 服务器集群的应用日益广泛，国内外公司纷纷推出商业化的集群产品，同时，一些学术机构也推出了集群实现方案。下面讨论具有典型代表意义的几种集群系统。2 4 18 e o w u i f 弧町1 9 9 4 年夏季，t h o m a ss t e r l i n g ，和d o nb e c k e r 在c e s d i s ( t h ec e n t e ro f e x c e l l e n c ei ns p a c ed a t aa n di n f o r m a t i o ns c i e n c e s ) 用1 6 个节点和以太网组成了一个计算机集群系统，并将这个系统命名为b e o w u l f 。b e o w u l f 集群提供了一种使用c o t s ( c o m m o d i t yo f ft h es h e l f ) 硬件构造集群系统以满足特殊计算需求的方法。这里的c o t s 是指p c 等这种广为应用的标准设备，它们通常可以由多家厂商提供并且大规模生产，所以具有很高的性价比。l并了应用用于并行通信的并行编程库m p i 或p v m 等t c p l p杉幽l i n u x 0 。j = i ；d 0j = ( j + 1 ) r o o dn ；i f ( w ( s j ) 0 )i - j ；2 7中北大学学位论文r e t u r ns i ；) w h i l e ( j ! = i ) ；r e t u mn u l l ；3 5 2 加权轮转算法加权轮转算法的思想是首先按照各服务器实际的性能分别指定不同权值，然后按权值来分配给后台服务器相应的请求数量。负载均衡器保存一张后台服务器链表以记录权值参数。假如各服务器实际的能力是相同的，该算法同退化为轮转算法。如果用相应的权值表示服务器的处理能力。假设服务器b 的权值为服务器a 的权值的两倍，即表示服务器b 的处理能力是a 的两倍。加权轮转算法是按权值的高低和轮转方式分配请求到各服务器。权值高的服务器先收到连接，权值高的服务器比权值低的服务器处理更多的连接，相同权值的服务器处理相同数目的连接。例如，有三个服务器a ，b ，c ，其权值依次为4 ，3 ，2 。则在一个调度周期内调度序列为a a b a b c a b c 。加权轮转算法还是比较简单，高效的。但当各个请求的服务时间交化很大时，单纯的加权轮转调度算法依然会导致服务器间的负载不平衡。当服务器的权值为零时，该服务器是不会被调度的。当所有服务器的权值为零，则没有任何服务器可用，算法返回n u l l ，所有新的请求连接都会被丢掉。加权轮转调度也无需记录当前所有各后台服务器的状态。所以它也是一种无状态调度算法。假设有一组服务器s = s o ，s 1 ，eee js n - 1 ) ，w ( s i ) 表示服务器s i 的权值，一个指示变量i 表示上一次选择的服务器，指示变量c w 表示当前调度的权值，腿x ( s ) 表示集合s 中所有服务器的最大权值，g o d ( s ) 表示集合s 中所有服务器权值的最大公约数。变量i 初始化为- 1 ，c w 初始化为零。w h i l e ( t r u e )i - ( i + 1 ) n ；i f ( i = = 0 )2 8中北大学学位论文c w = c w g c d ( s ) ；i f ( c w - - c w ) r e t u r ns i ；3 5 3 最小连接数算法最小连接数( l e a s tc o n n e c t i o n s ) 算法是一种根据各服务器的负载状况来分配请求的动态调整算法。负载分配程序维持着一张各后台服务器各种活动服务请求的连接个数表，分配程序把每一新到的服务请求分配给当前活动服务请求数量最少的服务器，如同在火车站售票大厅中买票，新来的购票者总会选择去队列最短的窗口。最小连接数算法通过服务器当前所获得的服务请求连接数来估计服务器的负载情况。负载均衡器需要记录下各个服务器当前服务请求连接的数目。当一个请求被调度到某台服务器时，其连接数加1 ，当连接终止或超时，其连接数减1 。在系统实现中，可以设置使得当服务器的权值为零时该服务器不被调度。最小连接数算法的优点是，当所有服务器具有相同的处理能力时，算法把负载变化大的请求平滑到多个服务器器上，所有处理时间比较长的请求不可能被发送到同一台服务器上。但是，当各服务器处理能力不同时，该算法并不理想。因为，t c p 连接在处理请求后会进入t i m ew a i t 状态，此时，连接还没有被释放掉。所以会出现这样情形，性能高的服务器己处理完所有已收到的请求连接，连接处于t i m ew a i t 状态，而性能低的服务器则忙于处理所收到的请求连接，同时，仍然不断接受新的请求。假设有一组服务器s = s o ，s 1 ，s n 一1 ) ，w ( s i ) 表示服务器s i 的权值，c ( s i )表示服务器s i 的当前连接数。f o r ( m = o ；m 0 )f o r ( i = m + 1 ；i n ；i + + )i f ( w ( s i ) - - o ) c o n t i n u e ；i f ( c ( s i ) c ( s i ) w ( s i ) 可以进一步优化为c ( s m ) 木w ( s i ) c ( s i ) 宰w ( s m ) 。同时保证服务器的权值为零时，服务器不被调度。所以，算法只要执行以下流程。3 0中北大学学位论文f o r ( m = o ；i n 0 )f o r ( i = m + 1 ；i c ( s i ) 毒w ( s m ) ) i n = i ；)r e t u r ns i n ；)r e t u r nn u l l ；3 5 5 基于局部性的最少链接调度基于局部性的最少链接调度( l o c a l i t y b a s e dl e a s tc o n n e c t i o n ss c h e d u l i n g ，以下简称为l b l c ) 算法是针对请求报文的目标i p 地址的负载均衡调度，目前主要用于c a c h e 集群系统，因为在c a c h e 集群中客户请求报文的目标口地址是变化的。这里假设任何后端服务器都可以处理任一请求，算法的设计目标是在服务器的负载基本平衡情况下，将相同目标i p 地址的请求调度到同一台服务器，来提高各台服务器的访问局部性和主存c a c h e 命中率，从而整个集群系统的处理能力。l b l c 调度算法先根据请求的目标m 地址找出该目标口地址最近使用的服务器，若该服务器是可用的且没有超载，将请求发送到该服务器；若服务器不存在，或者该服务器超载且有服务器处于其一半的工作负载，则用“最少链接的原则选出一个可用的服务器，将请求发送到该服务器。假设有一组服务器s = s o ，s 1 ，s n - 1 ，w ( s i ) 表示服务器s i 的权值，c ( s i )表示服务器s i 的当前连接数。s e r v e r n o d e d e s t i p 是一个关联变量，表示目标i p 地址所对应的服务器结点，一般来说它是通过h a s h 表实现的。w l c ( s ) 表示在集合s 中的加权最小连接服务器，即前面的加权最小连接调度。n o w 为当前系统时间。3 1中北大学学位论文i f ( s e r v e r n o d e d e s t _ i p 】i sn u l l )n = w l c ( s ) ；i f ( ni sn u l l ) r e t u r nn u l l ；s e r v e r n o d e d e s t _ i p s e r v e r = n ；)e l s en = s e r v e r n o d e d e s t _ i p s e r v e r ；i f ( ( ni sd e a d ) 0( c ( n ) w ( n ) & & t h e r ei san o d emw i t hc 4 m ) w ( n ) & t h e r ei san o d emw i t hc ( m ) 1 & n o w s e r v e r s e t d e s t i p 1 a s t m o d dm = w o c ( s e r v e r s e t d e s t i p ) ；r e m o v emf r o ms e r v e r s e t d e s t _ i p ；)s e r v e r s e t d e s t _ i p 1 a s t u s e = n o w ；i f ( s e r v e r s e t d e s l i p 】c h a n g e d )s e r v e r s e t d e s t i p 1 a s t m o d = n o w ；r e t u r nn ：3 5 7 目标地址哈希散列算法目标地址哈希散列( d e s t i n a t i o nh a s h i n gs c h e d u l i n g ) 算法是针对目标i p 地址的负载均衡技术。但它是一种静态映射算法，通过一个散列( h a s h ) 函数将一个目的i p地址映射到一台服务器，这种算法对后端以c a c h e 服务为主的集群系统有很好的适用性。目标地址哈希散列调度算法先以请求的目的i p 地址作为散列键( h a s hk e y ) ，从静态分配的散列表找出对应的服务器，若该服务器是可用的且未超载，就将请求发送到该服务器，否则，返回空。在实现时，通常采用素数乘法h a s h 函数，通过乘以素数使得散列值尽可能到达较均匀的分布。假设有一组服务器s = s o ，s 1 ，s n l ，w ( s i ) 表示服务器s i 的权值，c ( s i )表示服务器s i 的当前连接数。s e r v e r n o d e 是一个有2 5 6 个桶( b u c k e t ) 的h a s h 表，一般来说服务器的数目会运小于2 5 6 ，当然表的大小也是可以调整的。算法的初始化是中北大学学位论文将所有服务器顺序、循环地放置到s e r v e r n o d e 表中。若服务器的连接数目大于2 倍的权值，则表示服务器已超载。n = s e r v e r n o d e h a s h k e y ( d e s t _ i p ) ；i f ( ( ni sd e a d ) j l ( w ( n ) = = 0 ) j i( c ( n ) 2 宰w ( n ) ) )r e t u r nn ：在实现时，我们采用素数乘法h a s h 函数，通过乘以素数使得散列键值尽可能地达到较均匀的分布。所采用的素数乘法h a s h 函数如下：s t a t i ci n l i n eu n s i g n e dh a s h k e y ( u n s i g n e di n td e s t _ i p )r e t u m ( d e s t _ i p 幸2 6 5 4 4 3 5 7 6 1 u l ) & h a s h _ t a b _ m a s k ；)其中，2 6 5 4 4 3 5 7 6 1 u l 是2 到2 3 2 ( 4 2 9 4 9 6 7 2 9 6 ) f 司接近于黄金分割的素数，( s q r t ( 5 ) 1 ) 2 = 0 6 1 8 0 3 3 9 8 92 6 5 4 4 3 5 7 6 1 | 4 2 9 4 9 6 7 2 9 6 = 0 6 1 8 0 3 3 9 8 73 5 8 源地址哈希散列算法源地址哈希散列算法正好与目的地址地址哈希调度算法相似。只不过它以请求的源i p 地址作为散列键( h a s hk e y ) ，从静态分配的散列表找出对应的服务器，若该服务器是可用的且未超载，则将请求发送给该服务器，否则，返回空。它采用的散列函数与目标地址哈希散列调度算法的相同。3 5中北大学学位论文4 动态反馈调度算法与实现集群系统的负载均衡方法有动态和静态的两种。静态负载均衡s l b ( s t a t i cl o a db a l a n c i n g ) 是根据服务器和网络的负载特性、预先制定一个调度策略或分配算法，在集群运行的整个阶段都按照这个不变的策略或算法给各个服务器分配任务工作站。而动态负载均衡( d y n a m i cl o a db a l a n c i n g ) 需要在集群系统运行时实时检测系统的负载信息，动态地将任务在各个结点之间进行分配和调整以达到系统负载的均匀分配。由于静态负载均衡的调度策略是固定的，因而均衡的效果不如动态负载均衡。研究表明，大多数情况下，动态负载均衡要比静态负载均衡性能提高大约3 0 。4 1 动态反馈研究4 1 1 动态反馈机制动态负载均衡主要包括负载监控、负载分析和负载分配。负载监控负责周期性地监视和收集集群内各个节点的负载信息；负载分析根据负载监控收集的负载信息，对各节点的负载情况作状态进行分析；而负载分配根据负载分析结果来进行同步操作，即对要分配的负载按照权值的比例重新进行分布，并对无响应的节点进行隔离。动态负载均衡算法能根据系统运行状态信息进行负载分配的决策，对系统负载的变化具有动态的调整能力。当客户访问集群资源时，提交的任务所需的时间和所要消耗的计算资源是千差万别的，它依赖于很多因素，例如，任务请求的服务类型、当前网络带宽的情况以及当前服务器资源的利用情况等等。一些负载比较重的任务需要进行计算密集的查询、数据库访问、很长响应数据流；而负载比较轻的任务请求往往只需要读一个小文件或者进行很简单的计算。对任务请求处理时间的不同可能会导致处理节点利用率的倾斜( s k e w ) 即处理节点的负载不均衡。有可能存在这种情况，有些节点己经超负荷运行，而其他节点基本是闲置着；同时，有些节点己经忙不过来，有很长的请求队列，还不断地收到新的请求。反3 5中北大学学位论文过来说，这会导致客户长时间的等待，而集群整体的服务质量下降。因此，有必要采用某种机制，使得均衡器能够实时地了解各个节点的负载状况，并能根据负载的变化及时做出调整。基于负反馈机制的负载均衡算法正是为解决上述问题而提出来的，该算法考查每一个节点的实时负载和响应能力，不断调整任务分布的比例，来避免有些节点超载时依然收到大量请求，从而提高单一集群的整体吞吐率。在集群内，负载均衡器上运行服务端监控进程，监控进程负责监视和收集集群内各个节点的负载信息；而每个节点上运行客户端进程，负责定时向均衡器报告自身的负载状况。监控进程根据收到的全部节点的负载信息来进行同步操作，对将要分配的任务按照权值比例重新进行分布。权值的计算主要是根据各个节点的c p u 使用率、内存使用率、网络使用率以及磁盘i o 状况计算出新的权值，若新权值和当前权值的差值大于设定的阈值，监控器采用新的权值对集群范围内的任务重新进行分布，直到下一次的负载信息同步到来之前。均衡器配合动态权值，采用轮询调度算法来对接受的网络服务请求进行调度【4 5 】。4 1 2 动态反馈原理经典的反馈控制理论已经在工业控制等领域得到了广泛的应用。实践证明，反馈控制理论能在系统受到过载影响的情况下保持系统趋