（管理科学与工程专业论文）基于随机高级petri网模型的服务器均衡集群研究.pdf

西安建筑科技人学硕上学位论文 基于随机高级p e t r i 网模型的服务器均衡集群研究 专业：管理科学与工程 研究生：刘兆明 指导教师：黄光球教授 摘要 计算机网络应用的1 速发展，对网络卜的服务器提出了越来越高的要求。越来越 多的瓶颈会出现在服务器端。集群技术是实现高性能服务的一种有效途径。服务器集 群负载均衡应用成倍提高了服务器应用的可用性、可伸缩性和可靠性，扩展了服务器 带宽和增加吞吐量，加强网络数据处理能力，提高网络的灵活性和可用性。 本文首先介绍了基 二随机高级p e t r i n j ( s h l p n ) 的服务器集群负载均衡模型，这是 本文研究均衡集群的基础。基于此模型并综合了现有算法的特点提出了基于动态反馈 的集群负载均衡算法和请求任务队列涧度算法。基于动态反馈的负载均衡请求分配算 法考虑各服务器的实时负载和响应情况，通过周期性地获取服务器状态信息，动态地 计算出当前每台服务器具有的权值，不断调整服务器间处理请求的比例，来避免有些 服务器超载时依然收到大量请求，从而提高整个系统的吞吐率和请求响应时间。在对 基于该算法的负载平衡系统进行客错性处理时，本文对关键设备即负载均衡器进行了 冗余备份。这两种算法的组合策略使服务器集群中各个服务器实体根据自身处理能力 不断逼近最优运行状态。运用随机高级p e t r i 阚j 的相关理论基础知识，给出了该均衡集 群模型的性能评价指标( 如：吞吐量、响应时间) ，为了解决模型的规模增大对求解带 来的困难，讨论了对模型的各项指标做近似求解。最后，本文讨了论在网格环境下如 何合理有效的分配、管理和调用资源以实现用户隋求的有效均衡负载。 小论文剥服务器集群负载均衡技术进行了深入的分析，所提出的方法能够较好的 缩短请求响应时问和提高系统资源的利用率，对实际应用具有相当参考价值。 关键词：服务器集群动态负载均衡随即高级p e t r i 网( s 1 1 l p n )网格 论文类型：应川研究 两安建筑科技大学硕士学位论文 s t u d y o ns e r v e rb a l a n c e dc l u s t e rb a s e do ns t o c h a s t i ch i g h - l e v e l p e t r in e tm o d e l s p e c i a l t y ：m a n a g e m e n ts c i e n c e a n de n g i n e e r i n g n a m e ：l i uz h a o m i n g i n s t r u c t o r ：p r o f h u a n gg u a n g q i u a b s t r a c t t h er a p i dd e v e l o p m e n to fn e t w o r ka p p l i c a t i o no ft h ec o m p u t e r , h a sp u tf o r w a r dh i g h e r a n dh i g h e rr e q u i r e m e n tt ot h es e r v e ro nt h en e t w o r k m o r ea n dm o r eb o r l e n e c k sw i l la p p e a r i nt h ee n do ft h es e r v e r c l u s t e rt e c h n o l o g yi sak i n do fe f f e c t i v ew a yo fr e a l i z i n gt h eh i g h p e r f o r m a n c es e r v i c e ，b u tt h ee l a s t i c i t ya n dd e p e n d a b i l i t yt h a tt h ec l u s t e rl o a db a l a n c i n go f t h es e r v e rh a su s e da n di m p r o v e dt h eu s a b i l i t yt h a tt h es e r v e ru s e sa td o u b l e ，e x p a n dt h e b a n d w i d t ho ft h es e r v e ra n di n c r e a s et h et h r o u g h p u t ，s t r e n g t h e nt h ed a t ah a n d l i n gc a p a c i t y o f t h en e t w o r k ，r a i s et h ef l e x i b i l i t ya n du s a b i l i t yo f t h en e t w o r k t h i sp a p e rh a si n t r o d u c e dt h ec l u s t e rl o a db a l a n c i n gm o d e lo fs e r v e rb a s e do n s t o c h a s t i ch i g hl e v e l p e t r in e t ( s h l p n ) ，t h i si st h ef o u n d a t i o nt h a t t h i sp a p e rs t u d i e s b a l a n c e dc l u s t e r t h e np u tf o r w a r do nt h eb a s i so ft h ec l u s t e rl o a db a l a n c i n ga l g o r i t h mt h a t i sf e e d b a c kd y n a m i c a l l ya n da s k e df o rt a s kq u e u ed i s p a t c h e r sa l g o r i t h mi nc h a r a c t e r i s t i c b a s e do nt h i sc o m p r e h e n s i v ee x i s t i n ga l g o r i t h mo fm o d e l a s s i g na l g o r i t h mc o n s i d e re v e r y r e a l t i m e1 0 a do fs e r v e ra n dr e s p o n dt h es i t u a t i o no nt h eb a s i so fl o a db a l a n c i n gr e q u e s tt h a t f e e d b a c kd y n a m i c a l l y ，t h r o u g ho b t a i n i n gt h es t a t u si n f o r m a t i o no ft h es e r v e rp e r i o d i c a l l y ， c a l c u l a t eo u ts o m er i g h tv a l u eo fe a c hs e r v i c eu t e n s i la tp r e s e n td y n a m i c a l l y , a d j u s ta n d d e a l i n gw i t ht h ep r o p o r t i o na s k e da m o n gt h es e r v e r sc o n s t a n t l y , t op r e v e n ts o m es e r v e r s f r o ms t i l lr e c e i v i n gal a r g ea m o u n to fr e q u e s tw h i l eo v e r l o a d i n g ，t h u sr a i s et h eh a n d l i n gu p r a t eo ft h ew h o l es y s t e ma n da s kf o rt h er e s p o n s et i m e w h e nc a r r yo nf a u l t - t o l e r a n t t r e a t m e n tt ot h eb a l a n c e ds y s t e mo fl o a db a s e do nt h i sa l g o r i t h m ，t h i sp a p e rh a sb a c k e du p r e d u n d a n t l yt h ek e ye q u i p m e n tn a m e l yl o a db a l a n c i n gd e v i c e t w oa s s o c i a t i o nt a c t i c so f a l g o r i t h mt h e s em a k es e r v e rc l u s t e re a c hs e r v e re n t i t ya p p r o a c ht h eo p t i m u mo p e r a t i o ns t a t e a c c o r d i n gt oo n e so w nh a n d l i n gc a p a c i t yc o n s t a n t l y u s et h er e l e v a n tt h e o r i e sr u d i m e n t a r y k n o w l e d g eo fa d v a n c e d p e t r in e t w o r ka tr a n d o m ，i t p r o v i d e c l u s t e rn o tb a l a n c e d p e r f o r m a n c ee v a l u a t i o ni n d e xo fm o d e l st h i s ( f o ri n s t a n c e ：t h r o u g h p u t ，r e s p o n s et i m e ) i n c r e a s et o a s k i n g s o l v i n gt h ed i f f i c u l t yb r o u g h t t b rt h es c a l eo fs o l v i n gt h em o d e l ， d i s c u s s i o n se v e r yi n d e xt om o d e lm a k ea p p r o x i m a t et oa s ks o l v i n g f i n a l l y ，h o wu n d e rt h e 两安建筑科技大学硕士学位论文 e n v i r o n m e n to fn e td o e si td i s c u s sb yt h i sp a p e rr e a s o n a b l ev a l i dd i s t r i b u t i o n ，m a n a g ea n d t r a n s f e rr e s o u r c ei no r d e rt or e a l i z ev a l i de q u i l i b r i u ml o a dt h a tu s e ra s k t h i sp a p e rh a sc a r r i e do nd e e pa n a l y s i st ot h ec l u s t e rl o a db a l a n c i n gt e c h n o l o g yo f t h e s e r v e r ，p u tf o r w a r dm e t h o dc a ni si ta s kf o rr e s p o n s et i m ea n dr a i s es y s t e m a t i cu t i l i z a t i o n r a t i oo f r e s o u r c et os h o r t e n i n gb e t t e gw o r t hq u i t ec o n s u l t i n gt op r a c t i c a la p p l i c a t i o n k e y w o r d s ：s e r v e rc l u s t e rd y n a m i cl o a db a l a n c i n g s t o c h a s t i c h i g h l e v e l p e t r i n e t ( s h l p n ) g r i d p a p e rt y p e ：a p p l i c a t i o ns t u d y 声明 本人郑重声明我所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含本人或其他 人在其它单位已申请学位或为其它用途使用过的成果。与我一同工作的同 志对本研究所做的所有贡献均已在论文中作了明确的说明并表示了致谢。 申请学位论文与资料若有不实之处，本人承担切相关责任。 论文作者签名：纠匙明日期：2 朋，i 关于论文使用授权的说明 本人完全了解西安建筑科技大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布 论文的全部或部分内容，可以采用影印、缩印或者其它复制手段保存论文。 ( 保密的论文在论文解密后应遵守此规定) 雠徽州e 啊聊虢谨艺 将此页附在论文首页。 ；ji7 西安建筑科技大学硕二l 学位论文 1 1 论文研究的背景 1 绪论 i n t e m e t 的飞速发展给网络带宽和服务器带来了巨大的挑战。很多网络服务因为访 问次数爆炸式地增长而不堪重负，不能及时处理用户的请求，导致用户进行长时间的 等待，大大降低了服务质量。越来越多的瓶颈会出现在服务器端i i j 。如何建立高可用 性、高可靠性和高可伸缩的网络服务来满足不断增长的负载需求已成为迫在眉睫的问 题。 大部分网站都需要提供每天2 4 z j x 时、每星期7 天的服务，对电子商务等网站尤为突 出，任何服务中断和关键性的数据丢失都会造成直接的商业损失。例如，根据d e l l 的 新闻发布，d e l l 现在每天在网站上的交易收入为一千四百万美元，一个小时的服务中 断都会造成平均五十八万美元的损失。所以，这对网络服务的可靠性提出了越来越高 的要求i 。 单个服务器已无法满足与日俱增的服务，由多个服务器组成的多个节点形成的服 务器集群在硬件上提供了满足需求的可能，但如何将负载较均衡地调度到各台服务器 上对利用和挖掘系统资源的潜力来说非常关键。服务器集群的目的是共享和高效地利 用资源，提供大型运算，提供负载均衡分配请求能力以及出现故障时能够进行切换以 实现高可用性。负载均衡一般用于提高服务器的整体处理能力，并提高可靠性，可用 性，可维护性，最终目的是加快服务器的响应速度，从而提高用户的体验度pj 。服务 器集群负载均衡应用成倍提高了诸如w e b 服务器、f t p j 务器和其他关键任务服务器 上的应用的可用性、可伸缩性和可靠性，扩展了服务器带宽和增加吞吐量，加强网络 数据处理能力，提高网络的灵活性和可用性。 1 2 论文研究意义 人们在服务器集群时，发现了这样一个问题：在一个由网络连接起来的多计算机 环境中，在某一时刻，一些服务器的负载比较重，而另外一些服务器的负载却比较轻。 平衡各服务器之问的负载是任务分配与调度的一个主要目标，它能够提高整个系统的 性能【8 l 。为了改善系统的性能，通过在多台计算机之| i l j 合理地分配负载，使各台计算 机的负载基本均衡。这样既能提高系统的利用效率，又能充分发挥硬件设备的功能。 随着网络应用的急刷增长，对“j 硬件和软件方法实现高可仲缩、高可用网络服务的需 求不断增长，本文研究的目标在于以下几点：当服务的负载增长时，系统能被扩展来 满足需求，且不降低服务质量，即满足系统的可扩展性；当部分硬件和软件会发生故 障，整个系统的服务必须是每天2 4 小时每星期7 天可用的即满足系统的高可靠性； 西安建筑科技大学硕士学位论文 在服务清求雨1 分配中兼顾各服务器实体的硬件配置和实时负载状况动态负载，以实现 各个服务器实体问的动态负载均衡。山此看出，研究服务器集群的负载均衡对发挥集 群性能、提高服务质量具有十分重要的意义。 1 3 国内外研究现状及发展动态 通过高性能网络或局域网互联的服务器集群正成为实现高可伸缩的、高可用网络 服务的有效结构。集群的目的是共享和高效地利用资源，提供大型运算，提供负载均 衡分配请求压力以及出现故障时能够进行切换实现高可用性。负载均衡一般用于提高 服务器的整体处理能力，并提高可靠性，可用性，可维护性，最终目的是加快服务器 的响应速度，从而提高用户的体验度。为了将负载均匀的分配给内部的多个服务器上， 需要应用一定的负载均衡策略。 1 3 1 服务器集群系统 早在二十世纪七八十年代，d i g i t a le q u i p m e n t 公司希i t a n d e m 计算机公司就开始了集 群系统的研究与开发工作。集群( c l u s t e r ) 就是一组计算机，它们作为一个整体向用 户提供一组网络资源。这些单个的计算机系统就是集群的节点( n o d e ) 。一个理想的集 群是，用户从来不会意识到集群系统底层的：仃点，在他她们看来，集群是一个系统， 而非多个计算机系统。并且集群系统的管理员可以随时增加和删改集群系统的节点。 节点之问通过网络实现相互问的通信。应用程序可以通过网络共享内存进行消息传送， 实现分布式计算机。集群中的各个服务器实体可以是同构也可以是异构的。这种松耦 合结构的服务器集群系统有下列优点j ： ( 1 ) 性能：网络服务的工作负载通常是大量相互独立的任务，通过一组服务器分 而治之，可以获得很高的整体性能。 ( 2 ) 性能价格比：组成集群系统的p c 服务器或r i s c 服务器和标准网络设备因 为大规模生产降低成本，价格低，具有最高的性能价格比。若整体性能随着结点数的 增长而接近线性增加，该系统的性能价格比接近于p c 服务器。所以，这种松耦合结 构比紧耦合的多处理器系统具有更好的性f 3 7 , 价格比。 ( 3 ) 可伸缩性：集群系统中的结点数目可以增长到几千个，乃至上万个，其伸缩 性远超过单台超级汁算机。 ( 4 ) 高可用性：在硬件和软件一l - j , i i 有冗余，通过检测软硬件的故障，将故障屏蔽， 由存活结点提供服务，可实现高可用性。 当然，用服务器集群系统实现可f j 缩网络服务也存在很多挑战性的工作： ( 1 ) 透 ! j = | 性( t r a n s p a r e n c y ) ：如何高效地使得| = i = | 多个独立计算机组成的松藕合 的集群系统构成一个虚拟服务器；客户端应用程序与集群系统交互时，就像与一台高 西安建筑科技大学硕士学位论文 性能、高可用的服务器交互一样，客户端无须作任何修改。部分服务器的切入和切出 不会中断服务，这对用户也是透明的。 ( 2 ) 性能( p e r f o r m a n c e ) ：性能要接近线性加速，这需要设计很好的软硬件的 体系结构，消除系统可能存在的瓶颈。将负载较均衡地调度到各台服务器上。 ( 3 ) 高可用性( a v a i l a b i l i t y ) ：需要设计和实现很好的系统资源昶i 故障的监测和 处理系统。当发现一个模块失败时，要这模块上提供的服务迁移到其他模块上。在理 想状况下，这种迁移是即时的、自动的。 ( 4 ) 可管理性( m a n a g e a b i l i t y ) ：要使集群系统变得易管理，就像管理一个单一 映像系统一样。在理想状况下，软硬件模块的插入能做到即插即用( p l u g & p l a y ) 。 可编程性在集群系统上，容易开发应用程序。 最常见的三种集群类型包括高性能科学集群、高可用性集群和负载均衡集群。 高可用性集群( h i g ha v a i l a b l e ) 高可用性集群( h i g ha v a i l a b l e ) 用于不可间断服务的环境下。提供冗余的容错备份， 在主节点失效后，能够立即接管相关资源及继续提供相应服务。 高性能计算机集群h p c ( h i g hp e r f o r m a n c ec o m p u t i n g ) 概念并不完全统一，有一定争论，应该理解为并行系统，主要用于科学计算。 负载均衡集群( l o a db a l a n c i n gc l u s t e r ) 负载均衡集群为企业需求提供了更实用的系统。如名称所暗示的，该系统使负载 可以在计算机集群中尽可能平均地分摊处理。该负载可能是需要均衡的应用程序处理 负载或网络流量负载。这样的系统非常适合于运行同一组应用程序的大量用户。每个 节点都可以处理一部分负载，并且可以在节点之间动态分配负载，以实现平衡。对于 网络流量也是如此。通常，网络服务器应用程序接受了太多入网流量，以致无法迅速 处理，这就需要将流量发送给在其它节点上运行的网络服务器应用。还可以根据每个 节点上不同的可用资源或网络的特殊环境来进行优化。在应用服务的高负载情况下运 用该技术，由多台节点提供高可伸缩的，高负载的服务器组，以保证对外提供良好的 服务响应。本文主要研究基于随机高级p e t r i 网模型的负载均衡集群，将在设计中兼顾 高可用性和高性能。 集群系统采用的操作系统主要有v m s 、u n i x 、w i n d o w s n t 和l i n u x 。美国d e c 公司( d i g i t a le q u i p m e n tc o r p o r a t i o n ) 开发的v m s c l u s t e r 系统开发最早，技术也很成 熟，应用也很广泛，但由于v m s 操作系统只能在d e c 公司的v a x 系歹l j , na l p h a 系 列服务器上运行，v m s c l u s t e r 的应用受到很大限制。u n i x 是服务器或工作站上普遍 使用的操作系统，它运行稳定、安全性也比较好，因此许多大的公司都采用了基于 u n i x 的集群系统解决方案，如d e c 、h p 、s u n 、i b m 、n c r 和d g 等公司，其中在 国内影响比较大的主要是d e c 、h p 、s u n 和i b m 。基于w i n d o w s n t 的集群系统解决 西安建筑科技大学硕士学位论文 方案厂商主要有m i r c r o s o f i 和d e c 。m i c r o s o f t 于19 9 5 年就开始了集群系统的开发工 作。 集群的应用主要有：w e b 服务集群，流媒体服务集群，c a c h e 服务集群，邮件服务 集群。本文主要探讨w e b 服务集群的应旷“。 近几年来，除了原有的以生产商用二号有集群系统为主的厂+ 商仍在发展l - ：h 己的专有 平台集群系统外，l 个主要的硬件厂商都在研制并有计划推出基于l i n u x 的开放源码 的集群产品，i i i i1 b m 、h p 、s g i 等等。开放源码界的迅猛发展为集群的出现提供良 好的技术舞台，而向t u r b o l i n u x 、r e d l l a t l i n u x 、v a l i n u x 等老牌的l i n u x 厂商更是把 l i n u x 集群这一高端应用领域作为自己的战略发展方向，不遗余力的加入激烈的市场 产品竞争中。涌现在我们面前的则是多种多样的可供选择的集群解决方案，有硬件的 也有软件的。 国内也有不少公司进行了集群系统的研究和开发工作。联想公司在1 9 9 9 年9 月推 出了用于分布式高i i i i 计算的n s l 0 0 0 0 高性能集群服务器，该系统是一个四节点的系 统，主要基于联想万全4 5 0 0 r 服务器，以总体成本相对较低的设备组合，足以替代传 统r i s c 小型机和中型机的工作，而价格仅为市场上同等性能小型机的】2 一】4 。朗新 公司也推出了类似于t u r b o c l u s t e r 的高可用性集群系统l o n g s h i n ec l u s t e rs e r v e r 。中国 自主，f 发研制的集群式高性能计算机集群系统”曙光4 0 0 0 a ”于2 0 0 4 年3 月问世。曙光 4 0 0 0 a 采用近2 2 0 0 颗a m do p t e r o n 处理器，超过2 t b 的内存容量和2 g b s 的内部网 络速度，占地面积相当于l 4 个足球场大小，峰值浮点运算速度为1 0 万亿次1 4 j 。 1 3 2 服务器负载均衡系统 如今，服务器必须具备提供大量并发访问服务的能力，其处理能力和i o 能力己 经成为提供服务的瓶颈。显然，单台服务器有限的性能不可能解决这个问题，一台普 通服务器的处理能力只能达到每秒几万个到l 十万个请求，无法在一秒钟内处理上百 万个甚至更多的请求。但若能将多台这样的服务器组成一个系统，并通过软件技术将 所有请求合理分配给所有服务器，那么这个系统就完全拥有每秒钟处理几百万个甚至 更多晴求的能力。这就是利用服务器机群实现负载均衡的基本设汁思想。 负载均衡是种策略，它建立在现有网络结构之上，能让多台服务器或多条链路 共同承担一些繁重的计算或i l o 任务，从而提供了一种廉价有效的方法来扩展服务器 带宽和增加吞吐量，加强网络数据处理能力，提高网络的灵活性和可用性。 负载均衡有两方而的含义：首先，大量的并发访问或数据流量分担到多台节点设备 上分别处理，减少用户等待响应的i i ；i f - - l e 次，单个重负载的运算分担到多台节点设备 一t - 做并行处理，每个= 节点设备处理结束后，将结果汇总，返回给用户，系统处理能力 得到大幅度提高。本文着重讨论研究第一种情况下的集群负载均衡。 西安建筑科技大学硕士学位论文 w e b 集群负载均衡的方法主要可以从客户端、服务器和劂络端进行。基于客户机 的方法如b e r k e l e y 的s m a r t c l i e n t ，把负载分散到客户端，但调度不够灵活有效，n e t s c a p 的n a v i g a t o r 也曾经采用这种方式。y a h o 采用的服务端r r d n s 通过d n s 重新分配负 载，但不能区分集群- p 各服务器的差异，又受到t t l 的限制。e d d i e 、r e v e r s e p r o x y 和s w e b 使用纂于应用层调度的方法来建立一个可扩展的w e b 服务器集群，将到达 的h t t p 请求转发到不同的w e b 服务器，但因其工作在应用层系统开销大。b e r k e l e y 的m a g i c r o u t e r 、c i s c o 的l o c a l d i r e c t o r 使用服务端的i p 层负载平衡调度方法，但还只 是研究原型，没有成为有用的系统存活下来。l v s ( l i n u xv i t u a ls e r v e r ) 负载平衡在 内核实现，调度性能高，速度快，但因工作在网络层，无法灵活运用应用层的特征来 分配请求。 负载均衡是集群服务器中的关键技术，它决定了集群分配器的请求分发策略，并 且直接影响着服务器集群系统的整体性能。这几乎在所有有关服务器集群系统的技术 文献和研究论文中均有论述，见文献瞳。3 “5 1 。 负载均衡可以分为两种：静态的均衡和动态负载均衡。静态算法主要适用于较小规 模的、同构的、提供静态网页信息服务的系统；而动态算法适用于大规模的、异构的、 提供动态网页信息服务的系统，是当前研究的热点问题1 6 1 。 对于负载调度，早期的负载均衡算法有随机( r a n d o m ) 算法和轮询( r o u n d r o b i n ) 算 法，两者都属于静态凋度，不适于工作复杂的现实环境，特别是轮询算法采用传统的 轮转转发分配方式，计算简单、效率高，应用较广。但这两种算法不考虑后端服务器 的差异，不能保e 在不同的服务器间达到负载均衡，因此，不适合于异构的集群系统。 另外还有基于服务器中当前活跃连接数( 正在处理的请求连接) 的最小连接数( l e a s t c o n n e c t i o n sf i r s t ) 算法，选择当前正在处理的请求个数最少的服务器作为转发对象。但 活跃请求连接个数并不能完全反映服务器处理负荷上的差异，如处理能力强的服务器 在单位时问内可以处理更多的请求。此外，还可能在请求量少时将多个请求分配到同 一台服务器。 为了适应异构集群系统的需求，出现了加权轮询( w e i g h t e dr o u n d r o b i n ) 算法和加 权最小连接数( w e i g h t e dl e a s tc o n n e c t i o n sf i r s t ) 算法，通过为不同的服务器配置不同的 权值爿( 平衡服务器问的差异，选取合适的转发对象。但随着动态、多媒体网络信息的 大量应用，静态的权值信息不能表现动态的负载特征，随着系统运行时间增长，将导 致集群负载分和的不平衡。 目前，有研究者提出了选择加权百分k l ( s e l e c t e dw e i g h t e dp e r c e n t a g e ) 算法。算法 中综合考虑了服务器f 门阎有能力、当前负荷、服务速度等参数，通过对c p u 利用率、 内存利用率、刚卡输： 流量等分别加权计算来确定转发对缘。从理论分析和一些试验 来看，在许多情况下要好于上述算法。但存在的问题是算式中的各个权值系数需由系 西安建筑科技大学硕士学位论文 统管理员人为确定，这恰恰是很难办到的。不同速率的c p u 和不同大小的内存究竟各 占多大比例合适，根据不同的情况和所完成的任务不一样而有所不同。负载平衡的调 度方法并不成熟，还有不少工作值得研究。为了克服静态配置权值信息的缺点，本文 将基于s h l p n 模型探讨研究动态反馈计算权值信息的负载分配算法。 现有的一些集群请求分配器产品和软件系统，如c i s c ol o a d d i r e c t o r 、i b m d i s p a t c h e r 、浪潮英信x s 、t u b e rl i n u x 等都提供轮洵、最小连接数优先、最快响应优 先等方式的均衡算法。 1 4 本论文研究内容 本文将基于随即高级p e t r i 网模型，结合服务器均衡集群各部分的组成实现机制， 以提高服务器集群的性能为目标展开工作，具体目标如下：提供最短的作业平均响应 时问，提高系统的资源利用率，系统中每台处理机的负载量与它的处理能力相当， 避免各处理器花费大量的时间来传送任务。论文的主要工作围绕以下几个方面： ( 1 ) 基于随机高级p e t r i 网( s h l p n ) 模型，提出一种基于动态反馈的请求负载 分配算法。在研究了传统的各种请求负载分配算法后，采用随机高级p e t r i 网的建模和 分析技术提出了该分配算法。 ( 2 ) 提出了一种适合服务器均衡集群的请求队列调度算法。结合现有的队列调度 算法，本文联系课题的实际应用需求，设计了更加有效的请求队列调度算法。在拥塞 控制和服务质量q o s 方面都能得到改善； ( 3 ) 结合s h l p n 模型，对提出的请求分配算法和请求调度算法进行了性能分析 与评价； ( 4 ) 结合网格技术，讨论了在网格环境中的负载均衡应用； 西安建筑科技大学硕二e 学位论文 2 基于s h l p n 的服务器均衡集群系统模型 2 1 随机高级p e t r i 网( s h l p n ) p e t r i 网的概念最早在1 9 6 2 年德国人c a r ta d a mp e t r i 的博士论文“c o m m u n i c a t i o n w i t ha u t o m a t a ”中提出“网状结构的信息流模型”得来的【5 “。p e t r i 网是信息处理系统 描述和模型的数学工具之。主要特性包括：并行、不确定性、异步和分布描述能力 和分析能力。它可应用到很多系统和领域，比如：性能评价、通讯协议、并发和并行 计算等。作为图形： 具除具有可视描述功能，可通过标记( t o k e n ) 的流动模拟系统的 动态和活动行为，它是一种动态图形工具。做为数学工具，p e t r i 网可以建立状态方程、 代数方程和其它数学方法来描述系统的行为。p e t r i 网既可为理论工作者也可为工程 人员所使用，便于人们进行交流和理解。系统工程的方法：系统的形式描述、系统的 正确性验证、系统性能的评价、系统的目标实现和测试【5 2 1 。这些都可以在一个p e t r i 网 系统模型的框架上完成，其它图形或数学： 具都不具备如此功能。 p e t r i 网模型范围：研究模型系统的组织结构和动态行为，着眼于系统中可能发生 的各种状态变化和以及变化之问的因果关系；不易表示系统中数据值或属性的具体运 算。其模型特点如下： ( 】) 模拟性：从组织结构的角度，模拟系统的控制和管理，不涉及系统实现所 依赖的物理和化学原理； ( 2 ) 客观性：精确描述事件( 变迁) 问的依赖( j i l 页序) 关系希i 不依赖( 并发) 关系。这 种关系客观存在，与观察无关； ( 3 ) 流特性：适合描述以有规则的流动为行为特征的系统，包括能量流、物质流 和信息流： ( 4 ) 描述性：用统一的语言( 网) 描述系统结构和系统行为； ( 5 ) 分析性：网系统具有与应用环境无关的动态行为，是可以独立研究的对象。 这样，可按特定方式进行系统性质的分析和验证； ( 6 ) 异步并发性：适合描述异步并发系统； p e t r i 网作为系统的一种模型，在一个系统中事件的发生需要一定的时问，而事件 的发生通常用一个变迁的实施来表示，在每个变迁的可实施与实施之问联系一个随机 的延迟时问，这种类型f f j p e t r i 网叫做随机p e l r i 网( s t o c h a s t i cp e t r in e t ，s p n ) ”“。 随机高级p e t r if a l ( s l t 1 p n ) 的基本思想是把指数分布的变迁实施h e f 0 ) ，当地址 映射的有效期未过时，地址映射请求就会被中间域名服务器直接处理并返回给客户 端，而不会最终到达集群d n s 。因此，集群d n s 只能处理很少一部分地址映射请求， 从而只能实现一种粗粒度的负载均衡。 西安建筑科技大学硕：i ：学位论文 图2 1 基- - t 二d n s 的集群体系结构及其请求分配过程 由于集群d n s 对到达请求的控制能力有限，加之来自不同客户域负载的高度不 一致性和真实w e b 工作负载的高可变性，d n s 调度器通常需要使用复杂的负载均衡 算法来实现可接受的性能 1 。 2 2 2 基于请求分配器的集群体系结构 剜兰z i n l e l n e ： 三( 7 ) ：t - 7 岱4 ： i ps ”、i ? ： o o 举；斟穗 - u ：垂耳e p 州e t l ：、饥菇m 一* e 十吁# * h “h 烈 t i - 、r u ；m ! ? 】t - ，。 2 巧l 羊e1 mo i | 、 忑，跑l 量。 i l 熹鲤 睁 藿”鲥1l _ 咿u j 蓦旦! r 吊 t i 一 一 ；l 疑口i 霉警! 宝三j ：耳b h 图2 2 基于请求分配器的集群体系结构及其请求分配过程 与基于d n s f f j 集群棚比，存基于请求分配器的w e b 服务器集群( 如图2 2 所示) 的体系结构中，则能完全控制所有到来的请求且实现精细粒度的负载均衡“1 。在基 于请求分配器的集群系统中，前端的晴求分配器作为到达请求的代理，负责集中接收 所有到达的请求，然后按照特定的负载均衡策略将客，o 的请求均衡、透明地分配给集 群中的后端服务器节点。整个集群具有单一的虚拟i p 地址，即集群地址，使集群中的 服务= ； ： 对用户端具有透明性。实际上，集群地址就是晴求分配器的i p 地址。在这种体 亲一 西安建筑科技大学硕士学位沦文 系结构中，早期的研究与产品采用笫四层交换机( 仅处理到达的请求分组) 或t c p 路 由器( 处理到达的请求分组硐i 返回的应答分组) 作为请求分配器，能根据后端服务器 的私有i p 地址或m a c 地址对之进行独一无二的识别，并在t c p 层执行请求分配( 即笫 四层处理) 。所采用的典型请求分配机制包括分组重写( p a c k e tr e w r i t i n g ) 、分组转 发( p a c k e tf o r w a r d i n g ) 、h t t p 重定向( r e d i r e c t i o n ) 等。其负载均衡策略根据后端 服务器的活动连接数、运行队列中的进程数量、到达的清求速率等情况来选择负载最 轻的服务器。 本文将主要讨论基于请求分配器的服务器均衡集群。基于图2 2 在请求分配器中 兼顾各个服务器实体的实时负载情况，在请求分配器中引入基于动态反馈算法的请求 分配算法，在信息流中增加了服务器实体的实时负载反馈信息。可以抽象成如图2 3 所示的均衡集群清求分配模型。 图2 3 服务器均衡集群请求分配调度系统模型 在此请求分配调度系统模型中，清求分配器可以是一个专门的集成设备也可以是 一台装有相关软件的服务器，它作为整个集群系统的前端负责接受负载清求，并执行 负载分配策略，根据所获得的应用层信息，血 j u r l 请求类型、文件名路径等，将清求 分成多个类别。不同类别的请求根据实际应用需求确定不同的优先级权值。前端清求 分配器和后端服务器节点遵守相同的淆求分类和优先化原则。根据集群中各个服务器 实体的实时负载情况选择当前最适合负载的服务器，将清求分配转发给该服务器。 集群的各个后台服务器节点具有相同的内容，每台服务器都能够响应任何客户的 请求。所有的服务器都采用“进程每请求”的体系结构，因此每个到达的请求均对应 个单独的进程处理。服务器：1 了点收到请求后，执行相应的请求分类和优先化操作。 清求的优先级被映射成处理该请求的进程的优先级。每个服务器中都有一组进程就绪 西安建筑科技大学颂士学位论文 队列，每个就绪队列对应一个优先级别。具有相同优先级别的进程进入相同的就绪队 列进行排队，并且在内核中按! f c f s 的规则接受处理。每个就绪队列都设有一个阀 值来限定其可以容纳的最大进程数。每个服务器根据优先级选择不同就绪队列中的进 程进行执行。硇5 1 i n u x 探作系统下，这种w e b 服务器集群模型可以通过修改a p a c h e 服务 器得以实现。a p a c h e 服务器采用多进程模型并且具有“进程每请求”的体系结构：服 务器启动时生成一定数量的进程( 进程池) ，一个请求到来时就分配一个单独的进程进 行处理。 在该体系结构中，集群中各个服务器实体将实时负载情况如c p u 利用率，内存利 用率，当前等待进程数，响应时间等每问隔一个时间用期定期( 采样周期) 发送给请求 分配器，请求分配器结合各个服务器实体的实时负载情况来分配请求来实现负载均衡 策略。 2 3 服务器均衡集群的s h l p n 模型 为使本文研究的服务器集群系统具有一般性，我们做如下况明 1 , 5 2 1 ： ( 1 ) 集群系统中包含1 1 1 个服务器节点，接受1 1 类请求，并且相应地分配n 个优 先级别。其中第i 类请求记作n ( 1 i n ) ，第j 个服务器资源记作s ，( 】j m ) ： ( 2 ) 每个w e b 服务器具有n 个进程就绪队列，每个队列对应一个优先级别。请 求优先级被映射成处理请求的进程的优先级，因此同一等待队列中的进程负载处理相 同优先级的清求。在同一队列中排队的进程按f i f i o 的方式依次执行，所有1 1 个就绪 队列共享服务器。每个就绪队列设有一个阀值以限制挂起进程的最大数量；每个服务 器包含一个缓冲队列，s j 的队列由标识符q j 表示，其缓冲空间的容量为b j ； ( 3 ) 客户请求的到达为泊松( p o i s s o n ) 过程。任务r ，到达速率为九，r i 可以被分 配到m 个资源队列中的任一队列当所有接纳任务的m 个队列容量都满时任务的到达 过程中断； ( 4 ) 每个服务器服务不同淆求可有不同的服务时间s j 的服务速率为j 服务速率 是独立的指数分布的； c a t l e d g e 和c u n h a 等人通过分析些著名w e b 站点的日志文件发现，w e b 访问中会 话组的到达规律基本上服从负指数分布1 。文献中的理论分析和仿真实验结果均表 叫，在相邻w e b 晴求之问，时训隔的分布基本上符合一种分阶段的负指数分布，故 剥上述说明中泊松到达的假设是成立的”1 。 西安建筑科技大学硕士学位论文 c 1 耿 彤 d _ 口_ m5 _ 图2 4 服务器均衡集群的s h l p n 模型 在此s h l p n 模型中，对应于n 类不同请求，将服务器分成n 个独立的逻辑服务器， 每个逻辑服务器对应一个缓冲队列，在请求服务时，每个服务器的n 个缓冲队列共享 该服务器。长方形代表时问变迁，黑棒代表瞬时变迁。请求的到达和服务均由时间变 迁表示，并且联系指数分稚的实施时问。服务的速率可与系统的状态相关。请求分配 到后端服务器节点和竞