（计算机软件与理论专业论文）计算机集群中负载均衡机制的形式化分析.pdf

摘要 本文主要应用p e m 网工具形式化分析了计算机集群中负载均衡机制，在建 立了负载均衡机制模型的基础上，做出了模型的形式化验证和性能分析。作者的 工作主要体现在以下三个方面：一研究了计算机集群中负载均衡机制；二对p e t r i 网的分析方法作了综合性的阐述；三建立了负载均衡的p e 仃i 网模型，并应用p e t r i 网理论分析了这个模型。使用形式化方法分析计算机集群中的负载均衡机制是系 统的、科学的方法。 在第一章中，介绍了研究背景、现状和领域内常用的研究方法。第二章阐述 了计算机集群中负载均衡机制的工作原理、基本的负载均衡算法，并且通过例子 来直观的了解负载均衡具体的运作方式。第三章综合阐述了p e 试网模型的建立 方法，形式化验证方法和性能分析方法，并且简单的介绍了相应的数学理论工具 马尔可夫链。第四章建立了计算机集群中负载均衡机制的p e t r i 网模型，并作了 形式化的分析。第五章对研究的存在问题和将来需要做的工作做了简要阐述和展 望。性能分析中，非马尔可夫模型，辅助分析软件的应用都是值得进一步研究的 问题。同时，使用本文的分析方法有助于开发出更加有效的负载均衡算法。 关键词：负载均衡；p e t r i 网；建模；形式化验证：性能分析 a b s t r a c t t h i sw o r km a k e sag e n e r a li n t r o d u c t i o nf o rt h a t ，t h ef 0 衄a 1 1 ya n a l y s i so nt h e l o a db a _ i a n c i n gi nc o m p u t e rc l u s t e rw i t ht h et o o lo fp e t r in e t o n 也eb a s eo fp s e n t i n g ag e n e m l l o a db a l 卸c i l l gm o d e l ，v e r i f i c a t i o na i l dp e r f o m a n c ea i l a l y s i so ns e v e m l l o a d b a l a l l c i n gs 仃锄e g ya r ed o n eb ya n 撕y s i n gt h j sm o d e l t h e r ea r e3p o i m si nt l l i sp a p e r ， o n ei st 1 1 es t u d i e so fl o a db a l a l l c i n gi nc o m p u t e rc l u s t e r ；廿l eo t h e ri sm a 虹n gag e n e r a l i m o d u c t i o nf o rt 1 1 ef b m l a l l ya 1 1 a l y s i s 、v i t l lp e 嘶n e t ；t h et h 矾i ss e t t i n gu pam o d e lo f l o a db a i a n c i n ga 1 1 dm a k j n gf o n n a l l ya 1 1 l y s i so ni t t h em o d e l i sp r e s e n t e di nc o i n m o n s e n c e a n d c o m d b eu s e d t os t u d y 胁h e r m o r e i nt h e 矗埘c h a p t e ro ft h i sp a p e r 西y e st h eb a c k 野o u n do f 妊s t i 】d j e s ，a n d i m r o d u c e st 1 1 em o s tg e n e r a lm e 血o d sw h i c ha r eu s i n gi nt h ef i e l da tp r e s e l l t i i lt l l e s e c o n dc h a p t e r ，血e o r y ，s t f a t e 科a n d 撕t 1 i i l e t i co fl o a d a 1 1 c 协gi nc o m p u t e rc l u s t e ri s c o n c e m e db yu s ，a i l dw h a ta n dh o wt 1 1 el o a db a i a n c i n gw o r kc a i lb es e e n 恤吣u 曲t w o e x 锄p l e s h lt h em i r dc h a p t e r ，b a s i cc o n c e p t i o na n dc h a r a c t e ro fp e t r in e ta r ei n t m d u c e d ，a l s om 砒o do fa n a l y s i l l gi ss t i l d i e d 讪ec h 印t e rg i v e sa c o n c i s es 诅t e m e n to f t l l ef o n n a l l ya n a l y s i so fp e t r ii l e t 趾di n t m d u c e st 1 1 em o s tg e n e m lm e t h o d s ，、：h i c ha r e u s i n gi nt h ef i e l da tp r e s e m h 血ef b u hc h a p t e r ，a1 0 a db a l a n c i n gm o d e l l ss e t l l p ，a 1 1 d v e r i n c a t i o na i l dp e r f o 工m a n c ea i l a l y s i so nb a s i cl o a db a l a n c i n gs t r a t e g ya r ed o n eb y u s i n gm em e t h o di n 仃o d u c e di na b o v ec h a p t e lf i n a l l y ，t 1 1 ep r o m i s e sa i l dp m b l e m so f t h ea p p m a c ha r ei 1 1 u s t m t e d b yp e r f b n n 柚c ea i l a l y s i s ，n o n m a r k o vp r o c e s sa f l d a s i s t a 1 1 ta n a l v s i cs o f t w a r en e e da 1 1a d v a l l c e dr e s e a r c h a n dam o r ee 行i c i e n tl o a d b a l a n c i n ga r i 岫e t i cc o u l db ed e v e l o p e db yu s i n gm e t h o dm e n t i o n e di nt h ep a p e l k e y w o r d s ：1 0 a db a l a l l c i n g ；p e 啊n e t ；m o d e l ：v e f i c a t i o n ；p e r f o r m a n c ea n a l y s i s 学位论文独创性声明 本人所呈交的学位论文是我个人在导师的指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果。与我一同工作的同事对本研究所做的任何贡 献均已在论文中作了明确的说明并表示了谢意。如不实，本人负全部责任。 一一名罐碡年( 聊 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期刊电子杂志 社有权保留本人所送交的学位论文复印件或电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密 期内的保密论文外，允许论文被查阅或借阅。论文全部或部分内容的公布( 包括 刊登) 授权河海大学研究生院办理。 论文作者( 签名 l 柙占年乡月d 怠 河海大学硕士论文计算机集群中负载均衡机制的形式化分析 1 1 1 研究背景 第一章绪论 第一节引言 首先，集群技术的研究可以追溯到2 0 世纪8 0 年代，只不过因为当时网络技 术及并行研究还不是很成熟，没有大规模的应用。到2 0 世纪9 0 年代，集群技术 已经被广泛用于i t 等各个行业。在2 0 0 3 年世界高性能计算的t o p l o 中，集群结 构占了7 个，说明在构建超大规模计算系统的时候，集群是主要的系统构成方式。 在计算机技术中集群负载均衡是自成体系的，目前它是一个热门技术也是一个高 端应用。 其次，形式化方法是基于严密的、数学上的形式机制的系统研究方法。客观 的讲，有了数学的应用，就有了形式化方法。但是，一般认为形式化方法是始于 2 0 世纪6 0 年代末的f l o y d ， i o a r e 和m a n n a 等在程序规格和验证方面的研究， 当时由于“软件危机”，人们试图用数学方法证明程序的正确性而发展成为各种 程序验证方法，但是受程序规模限制，这些方法并未达到预期的应用效果。从 2 0 世纪8 0 年代末开始，形式化方法在工业中的广泛应用，掀起了形式化方法和 技术的学术研究和工业应用的热潮。 本文采用的形式化建模分析工具是p e t r i 网。p e 仃i 网的概念最早在1 9 6 2 年由 c a r l a d 锄p e 砸的博士论文自动机通信中提出来。p e 缸的工作引起了欧美学 术界与工业界的注意。1 9 7 0 至1 9 7 5 年，m i t 的计算研究小组积极参与p e 仃i 网 的相关的研究。从1 9 8 0 年召开第一次p e 砸网理论和应用的国际研讨会以来，每 年一次的国际研讨会连续不断，p e t r i 网理论和应用的研究成果主要集中在会议 论文集中。近年来p e m 网的论文己大量出现在各种学术年会和期刊上。 本章参考了互联网和文献 1 6 】的内容。 1 1 2 研究现状 将多台计算机组织起来进行协同工作来模拟一台功能更强大的计算机来解 决问题，这种技术称为集群技术。目前应用最为广泛的集群计算技术可以分为三 大类：高可用性集群技术、高性能计算集群技术和负载均衡集群技术。在群集的 这三种基本技术类型之间，高可用性群集也可以在其节点之间均衡用户负载，同 时仍试图维持高可用性程度。同样，可以从要编入应用程序的群集中找到一个并 行群集，它可以在节点之间执行负载均衡。在计算机集群中，负载均衡技术在多 节点之间按照一定的策略( 算法) 分发网络或计算处理负载。它能让多台服务器 或多条链路共同承担一些繁重的计算或i 0 任务，从而以较低成本消除网络瓶颈 河海大学硕士论文计算机集群中负载均衡机制的形式化分析 和提升系统总体性能，提高计算机集群的灵活性和可靠性。可见负载均衡技术是 计算机集群技术中的一个关键点，负载均衡算法对集群服务器的整体性能起决定 作用。影响负载均衡的因素有三个，分别是算法、网络拓扑以及负载均衡的粒度。 如何开发出高效的负载均衡算法成为了个值得研究的问题。章文嵩开发的 i s ( l i n “s u a ls e “e r ) 1 2 3 j 给出了基于i p 层和基于内容请求分发的负载均衡 调度解决方法，并在l i n u x 内核中实现了这些方法。l v s 在l i n u x 操作系统的内 核中实现了l a y e r - 7 交换，称之为k t c p v s ( k _ e m e lt c pv i r t i l a is e r v e r ) 。目前， k t c p v s 已经能对h t t p 请求进行基于内容的调度，但它还不很成熟，在其调度 算法和各种协议的功能支持等方面，有大量的工作需要做。李文中等人提出了服 务组合中自适应的动态负载均衡算法1 7 j 。可是，最优的负载均衡策略很难实现， 即使在简化的情况下，也是一个n p 完全问题【8 】。 基于系统的工程方法是保证计算机集群中负载均衡算法开发质量的首选方 法。类似于常规系统的开发，负载均衡策略的开发过程必须经过系统的设计、分 析、测试、维护等阶段。为了保证系统能够逻辑一致、完整、高效的运行，要注 意以下两个方面的问题：1 对于给定的问题，设计者如何设计出一套满足需求的 负载均衡算法。2 对于一个设计好的负载均衡算法，分析者如何进行严格验证和 性能分析，证明其是可用的和正确的。为了更好的从这两个方面来解决负载均衡 机制的设计问题，我们需要采用有效的方法和技术一“形式化”的方法和技术。 “形式化方法”主要指使用形式描述语言( f d l ，f o m l a ld e s c r i 砸o nl a n g l l a g e ) 来对系统进行描述，并贯穿于系统开发的各个阶段。每一种f d l 都有一种或多 种形式模型作为基础，有严格的语法和语义定义，它抽象于具体实现。 目前，开发分布式、并行系统常用的形式化方法有：通信顺序过程c s p l 9 1 、 通信演算系统c c s i l 0 】以及p e 仃i 网【2 r 4 】。c s p 和c c s 都是为处理分布式系统而设 计的演算工具，其目标是给出在不同描述程度上构造和比较不同模型的框架，它 们都是以表达式的基本语法为起点的。c s p 和c c s 具有很强的描述能力，也有 一定的分析演算能力，但是仍然存在一定的不足l l o j ： 其处理是针对系统运行机制的，没有反映系统物理结构信息，不便于系 统结构设计和处理。 其表达形式较自动机语言更为复杂，不便于控制操作。 尽管对并行有一定的刻画，但是仍不能很好的反映真并发行为。 在p e t r i 网研究与应用的发展历史中，它的应用范围已经远远超出了计算机 科学的领域，成为研究离散事件动态系统的一种有力的工具。两个成功的应用领 域是系统性能评价和通信协议，其他很有前途的应用领域包括分布式软件系统、 分布式数据库系统、并发和并行计算、柔性制造与工业制造系统、离散事件系统、 多处理机系统、数据流计算、容错与故障诊断系统、逻辑推理、办公自动化系统、 形式语言、人一机系统、神经元网络与决策模型等。与传统的并行建模方法相比， 河海犬学硕士论文 计算机集群中负载均衡机制的形式化分析 p e t r i 网具有以下优点： 具有极强的描述能力。已经证明：对于加限制弧的p e t r i 网，其描述能 力与图灵机等价。 对并行、并发、异步、同步等现象可以进行很好的描述。 是一种图形表示的模型，能以直观的方法表达系统的特性。 具有一套成熟的数学理论，有众多的分析技术。 应用领域广泛。 p e 砸网可以使用层次建模的方法，实现模块化和逐步求精的建模。 系统工程的方法：系统的形式描述、系统的形式化验证、系统性能的评价、 系统的目标实现和测试。这些都可以在一个p e 伍网系统模型的框架上完成，其 它图形或数学工具都不具备如此功能。 在应用p e 缸网作为并行程序的验证方面，t m l l r a t a 教授使用p e 砸网的不变 量对a d a 程序进行验证【l l j ；蒋昌俊教授等利用p e m 网的死锁、陷阱等结构性质 来对a d a 程序进行验证【”】；k b a r k a o u i 和j f p r a d a t p e v r e 提出利用p e t r i 网的可 达树、可达图进行p v m ( p a r a l l e lv i n i l a lm a c h i n e ) 程序验证【1 2 】；丁志军博士使 用时序p e t r i 网对a d a 程序进行验证【1 4 】。 在应用p e t r i 网做性能分析方面，m a d i s o 【1 5 】提出了时间p e 砸网的性能分析 模型；k y o t o 和m e l b o u r n e l l 7 1 分别提出了p e 廿i 网的的性能模型；林闯博士提出 了随机p c t i i 网的性能分析方法l l8 】和进行了w e b 服务器集群请求分配和选择的性 能分析【”。 目前使用p e t r i 网对负载均衡进行描述的模型【1 8 11 9 3 1 4 4 1 ，多是建立在w e b 上的服务器系统，侧重点是描述w e bq o s 控制机制的基于优先级的h t l p 进程 调度策略，研究主要解决的问题是w 曲服务器系统的q o s 保证问题。同时，使 用p e m 网对系统建立的模型，主要是用在性能分析方面，在使用模型对负载均 衡的算法进行形式化验证的研究很少。 计算机集群中负载均衡机制的研究需要解决的问题是如何在多节点之间按 照一定的策略( 算法) 分发网络或计算处理负载，这里算法调度的负载指用户提 交给集群的计算任务或网络流量。如果在负载均衡算法的设计开发过程中使用形 式化验证技术，就可以在算法的设计阶段最大限度的检测和纠正系统错误和缺 陷。 1 1 3 相关技术简介 首先介绍负载均衡机制作用的相关技术。 由此可以看出负载均衡建立在某种网络结构之上，它在多节点之间按照一定 的策略( 算法) 分发网络或计算处理负载。特别指出，在尖端科学计算领域中， 河海大学硕士论文计算机集群中负载均衡机制的形式化分析 有许多为集群专门设计的网络，在这样的网络上通常可以绕开网络协议，减少不 必要的开销，以此实现高带宽、低延迟的网络，以满足高性能计算的要求。 负载均衡的研究是使重负载的处理机转移一部分任务到某些轻负载处理机 中，使系统负载均衡的分布于计算机集群的计算节点上的策略和算法，充分发挥 集群中所有节点的计算能力，不出现忙闲不均的情况，从而改进计算机系统整体 性能。负载均衡在计算机集群中即使没有空闲的节点时，也尽量使负载均衡的在 节点中分配。负载均衡主要研究三大策略问题：传输策略、定位策略和选择策略。 下面介绍用p e t r i 网作为工具进行形式化分析的相关技术。 p e 订i 网以研究模型系统的组织结构和动态行为为目标，它着眼于系统中可 能发生的各种状态的变化以及变化之间的关系。p e t r i 网主要特性包括：并行、不 确定性、异步和分布描述能力和分析能力。作为图形工具除具有可视描述功能， 可通过标记( t o k e n ) 的流动模拟系统的动态和活动行为，它是一种动态图形工具； 作为数学工具，p e 晡网可以建立状态方程、代数方程和其它数学方法来描述系 统的行为。 p e m 网研究的系统模型行为特性包括：状态的可达( r e a c h a b i l i t y ) 、位置的 有界性( b o l l i l d e d n e s s ) 、变迁的活性( 1 i v c n e s s ) 、初始状态的可逆达( r e v e r s i b i l 畸) 、 标识之间的坚挺( p e r s i s t e n c e ) 、事件之间的同步距离( s y c h r o i l i cd i s t 锄c e ) 和公 平性( 场r n e s s ) 等。 p e 岫网模型的主要分析方法依赖于：可达树、关联矩阵和状态方程、不变 量和分析化简规则等。 p e 蜘网易于表示系统变化发生的条件及变化发生各种状态变化以及变化发 生后系统的状态，但不易表示系统中数据值或属性的具体变化或运算。在大型、 复杂系统的模型中，p e m 网应用的主要困难是模型状态空间的复杂性问题，对 p e t r i 网模型的化简技术始终是p e t r i 网研究的主题之一。 随机p e m 网( s t o c h a s t i cp e t r in e t 简称s p n ) 是把变迁与指数分布实施联系 起来，这个思想是由m 0 1 l o v ，f 1 0 血和n a t k i i l 等人独立提出的。给p 厂r 网的每个 变迁相关联一个实施速率( 矗一n gr a t e ) ，得到的模型就是s p n 。s p n 与相对应的 p 厂r 网拥有完全相同的可达图，所以它可以做p ，r 网上所能完成的系统模型分析， 如真确性证明、并行性分析等。同时，已经证明，一个s p n 同构于一个连续时 间马尔可夫链( m a r k o vc h a i n 简称m c ) ，s p n 的每个标识映射成m c 的一个状 态，s p n 的可达图同构于一个m c 的状态空间。在s p n 的可达图上很容易获得 m c 转移速率矩阵的参数，因此能够计算出m c 的每个状态( 标识) 的稳定状态 下的稳定概率。有了稳定概率，也就打开了系统性能分析的大门，在此基础上可 分析一些系统的性能指标。 随机高级p e 埘网( s t o c h a s t i cl l i g i 一1 e v e rp e 砸n e t 简称s h l p n ) 是由林闯和 m a r i n e s c u 于1 9 8 6 年提出，而后逐步完善形成的一种新型随机p e t r i 网。它的基 河海大学硕士论文 计算机集群中负载均衡机制的形式化分析 本思想是把指数分布的变迁实簏时间变量引入到h l p n 的变迁集，使之既继承保 留h l p n 在描述和分析系统方面原有的特点和性质，又具s p n 的状态空间与m c 同构的特性。更重要的是在s h l p n 中，不但保持了h l p n 将多个相同结构子系 统压缩成一个子系统的特点，而且进一步将多个同行为标记成的多个标识压缩成 一个标识( 复合标识) ，显著的减小了系统的状态空间。 把具有m a r k o v 性的随机过程称为m a r k o v 过程。离散空间的m a r k o v 过程， 就是熟知的马尔可夫链( m a r k o vc h a i nm c ) 。m c 既可以是连续时间的，也可以 是离散时间的，它取决于索引参数的设定。随机p e t r i 网中变迁实施速率的指数 分布所导致的无记忆性和标识的可数性是构造随机p e 仃i 网可达图和m c 之间同 构的关键因素。 第二节本文主要工作 本文把形式化开发方法引入到计算机集群中负载均衡策略的开发过程中，从 形式化描述、形式化验证、到基于形式化模型的性能分析等一系列方法的应用可 以确保系统开发的质量。 本文使用p e m 网为工具，形式化分析了计算机集群中负载均衡机制。首先 研究了计算机集群中的负载均衡机制，归纳出了负载均衡一般的算法。然后，总 结出利用p 洲网研究问题的一般方法。最后在上述工作的基础上使用随机高级 p e t r i 网描述了一个一般的计算机集群中服务器负载均衡的模型，这个模型概括 了计算任务负载和网络负载两种形式，具有普遍的特性；随后基于这个形式化的 模型采用相关的方法进行分析：主要包括形式化验证和系统性能分析等工作。从 而为系统的设计开发工作提供参考和指针。鉴于论文完成时间的限制，本文不涉 及编程与实现的环节。 第三节本文组织结构 本文主要分为以下部分： 第一章阐述了相关研究的背景、现状和相关技术简介。 第二章阐述了计算机集群中负载均衡机制的相关研究，总结出了常见的负载 均衡的算法。 第三章对使用的形式化分析工具p e t r i 网的概念和技术作出阐述。 第四章使用随机高级p e t r i 网建立了一个计算机集群负载均衡机制的一般性 模型，并进行了形式化验证和性能分析，给出了性能分析的指标。 第五章对全文进行总结，说明有待进一步研究的问题，并对未来的技术发展 趋势进行展望。 河海大学硕士论文计算机集群中负载均衡机制的形式化分析 第二章计算机集群中负载均衡机制的研究 对于提高服务器性能而言，单纯地靠提高单个处理器的运算能力和处理能力 正在变得越来越难，而采用新技术、新体系构建高性能服务器，才是真正提高现 代服务器处理能力的有效途径。根据资源被共享和复制的级别不同，通常的高性 能服务器系统可以分为：大型主机( m a i n 行a m e ) 、大规模并行处理机( m p p ) 、 对称多处理机( s m p ) 以及基于集群体系结构的服务器系统( c l u s 缸) 。 集群( c l u s t e r ) 就是一组计算机，它们作为一个整体向用户提供一组网络资 源。这些单个的计算机系统就是集群的节点( n o d e ) 。一个理想的集群是，用户 从来不会意识到集群系统底层的节点，在他她们看来，集群是一个系统，而非 多个计算机系统。并且集群系统的管理员可以随意增加和删改集群系统的节点。 将多台计算机组织起来进行协同工作来模拟一台功能更强大的计算机来解 决问题，这种技术称为集群技术。目前应用最为广泛的集群计算技术可以分为三 大类：高可用性集群技术、高性能计算集群技术和负载均衡集群技术。 科学计算集群：它涉及为群集开发并行编程应用程序，以解决复杂的科学问 题。这是并行计算的基础，尽管它不使用专门的并行超级计算机，这种超级计算 机内部由十至上万个独立处理器组成。但它却使用商业系统，如通过高速连接来 链接的一组单处理器或多处理器p c ，并且在公共消息传递层上进行通信以运行 并行应用程序。 高可用性集群：高可用性群集的出现是为了使群集的整体服务尽可能可用， 以便考虑计算硬件和软件的易错性。如果高可用性群集中的主节点发生了故障， 那么这段时间内将由次节点代替它。次节点通常是主节点的镜像，所以当它代替 主节点时，它可以完全接管其身份，并且因此使系统环境对于用户是一致的。 负载均衡集群：如名称所暗示的，该系统使负载可以在计算机群集中尽可能 平均地分摊处理。该负载可能是需要均衡的应用程序处理负载或网络流量负载。 这样的系统非常适合于运行同一组应用程序的大量用户。每个节点都可以处理一 部分负载，并且可以在节点之间动态分配负载，以实现均衡。对于网络流量也是 如此。 在群集的这三种基本类型之问，高可用性群集也可以在其节点之间均衡用户 负载，同时仍试图维持高可用性程度。同样，可以从要编入应用程序的群集中找 到一个并行群集，它可以在节点之间执行负载均衡。由此可以看出负载均衡建立 在现有网络结构之上，它在多节点之间按照一定的策略( 算法) 分发网络或计算 处理负载。 负载均衡技术提供了一种廉价有效的方法来扩展服务器带宽，增加吞吐量， 提高数据处理能力，同时又可以避免单点故障。本章探讨了计算机集群中负载均 衡工作原理与实现算法方面的问题。 河海大学硕士论文计算机集群中负载均衡机制的形式化分析 本章首先介绍了负载均衡机制的工作原理：然后列出了常用的一些负载均衡 的算法；最后通过两个例子来进一步说明负载均衡机制作用的具体情形。本章内 容参考了文献【2 0 】。 第一节负载均衡的工作原理 本质上讲，网络负载均衡是分布式作业调度系统的一种实现。均衡器作为网 络请求分配的控制者，要根据集群节点的当前处理能力，采用集中或分布策略对 网络服务请求进行调配，并且在每个服务请求的生命周期里监控各个节点的有效 状态。负载均衡器在集群的各个服务节点中分配工作负载或网络流量。 2 1 1 实现的原理 负载均衡的作用就像轮流值日制度，把任务分给大家来完成，以免让一个人 过度劳累。但是与轮流值日制度不同的是，它是一种动态均衡，通过一些工具实 时地分析数据包，掌握网络中的数据流量状况，把任务理分配出去。对于不同的 应用环境( 如电子商务网站，它的计算负荷大；再如网络数据库应用，读写频繁， 服务器的存储子系统系统面临很大压力；再如视频服务应用，数据传输量大，网 络接口负担重压。) ，使用的均衡策略( 算法) 是不同的。所以均衡策略( 算法) 也就有了多种多样的形式，广义上的负载均衡既可以设置专门的网关、负载均衡 器，也可以通过一些专用软件与协议来实现。在o s i 七层协议模型中都有相应的 负载均衡策略( 算法) ，在数据链路层上实现负载均衡的原理是根据数据包的目 的m a c 地址选择不同的路径；在网络层上可利用基于i p 地址的分配方式将数 据流疏通到多个节点；而传输层和应用层的交换( s 、v i t c h ) ，本身便是一种基于 访问流量的控制方式，能够实现负载均衡。 在高性能计算领域，某些并行群集系统可以达到如此高的带宽和低延迟， 其原因是它们通常绕过使用网络协议，如t c p ，i p 。虽然网际协议对于广域网很 重要，但它包含了太多的开销，而这些开销在节点相互己知的封闭网络群集中是 不必要的。其实，那些系统中有一部分可以在节点之间使用直接内存访问( d m a ) ， 它类似于图形卡和其它外围设备在一台机器中的工作方式。因此横跨群集，可以 通过任何节点上的任何处理器直接访问一种形式的分布式共享内存。它们也可以 使用低开销的消息传递系统，在节点之问进行通信。消息传递接口( m p i ) 是并 行群集系统间消息传递层的最常见实现。m p i 存在几种衍生版本，但在所有情 况下，它为开发者访问并行应用程序提供了一个公共a p i ，这样开发者就不必手 工解决如何在群集的节点之间分发代码段。其中一个，b e o w u l f 系统首先将m p i 用作公共编程接口。 河海大学硕士论文计算机集群中负载均衡机制的形式化分析 2 1 2 实现的层次 1 基于客户端的负载均衡 这种模式指的是在网络的客户端运行特定的程序，该程序通过定期或不定期 的收集服务器群的运行参数：c p u 占用情况、磁盘1 0 、内存等动态信息，再根 据某种选择策略，找到可以提供服务的最佳服务器，将本地的应用请求发向它。 如果负载信息采集程序发现服务器失效，则找到其他可替代的服务器作为服务选 择。 这种技术存在通用性的问题，所以这种技术仅在特殊的应用场合才使用到。 另外，在采用j a 、，a 构架模型中，常常使用这种模式实现分布式的负载均衡，因 为i a v a 应用都基于虚拟机进行，可以在应用层和虚拟机之间设计一个中间层， 处理负载均衡的工作。 2 基于服务器端的负载均衡 如果将客户端的负载均衡层移植到某一个中间平台，形成三层结构，则客户 端应用可以不需要做特殊的修改，透明的通过中间层应用服务器将请求均衡到相 应的服务节点。比较常见的实现手段就是反向代理技术。使用反向代理服务器， 可以将请求均匀转发给多台服务器，或者直接将缓存的数据返回客户端，这样的 加速模式在一定程度上可以提升静态网页的访问速度，从而达到负载均衡的目 的。 3 高层协议内容交换 除了上述的负载均衡方式之外，还有在协议内部支持负载均衡能力的技术， 即u r l 交换或七层交换，提供了一种对访问流量的高层控制方式。w 曲内容交 换技术检查所有的h t t p 报头，根据报头内的信息来执行负载均衡的决策。 4 网络接入协议交换 当前负载均衡主要用于解决服务器的处理能力不足的问题，因此并不能充分 发挥交换机带来的高网络带宽的优点，使用基于操作系统的第四层交换技术因此 孕育而生。通过开放源码的l i n u x ，将第四层交换的核心功能做在系统的核心层， 能够在相对高效稳定的核心空间进行i p 包的数据处理工作。同时又可以在核心 层或者用户层增加基于交换核心的负载均衡策略支持，因此在灵活性上远远高于 硬件系统，而且造价方面有更好的优势。 2 】3 负载均衡的基本问题 在计算机集群中，计算任务或网络流量被分配到各个处理节点上并行执行， 称之为负载。更加准确的讲，负载的定义应是绝对的负载量与节点处理能力的比 值。当整个系统的任务较多时，分配给各个节点的负载可能并不均衡，整个系统 河海大学硕士论文计算机集群中负载均衡机制的形式化分析 的利用率就会降低。有效的将各个并行计算任务或网络流量均匀的分布到不同的 计算节点并行计算，使各个节点的利用率达到最大，这就是研究负载均衡机制的 目的。 负载均衡主要研究三大策略问题： 1 传输策略( w h e n ) ：决定何时进行负载的执行或迁移。 2 定位策略( w h e r e ) ：定位什么样的目的计算节点作为负载分派的目的对 象。 3 选择策略( w l l i c h ) ：选择哪一个负载执行或迁移。 衡量负载均衡策略的好坏有两个常用标准，即完成性能和策略本身的执行效 率。 与大多数分布式系统一样，负载均衡的研究也分为两个方向，即静态负载均 衡和动态负载均衡。 静态负载均衡是采用某种分配算法在任务执行前即确定分配到各个节点的 方案，其分配基于系统平均情况，不考虑系统瞬时状态变化，基于对负载的计算 量、通信关系和依赖关系，以及计算机集群本身的状况等先验知识或预测形成远 程执行进程表。任务投入后就不可再转移。这种方式的特点是开销小，简单实用， 不需要收集存储当前的计算节点状态信息，但先验知识难以确定或可能确定错 误，另外只能在进程运行前作出分配决定。 动态负载均衡可根据当前运行状态自适应决定负载均衡策略，动态方法是通 过集群系统的实施负载信息，动态的将负载在各个计算节点进行分配和调整。以 消除系统中负载分布的不均匀性。动态方式可分为两种：( 1 ) 动态非抢先式：仅 允许任务未运行前进行迁移。( 2 ) 动态抢先式：允许中止正在运行的进程，迁移 到另外的计算节点上继续运行。 第二节负载均衡的基本算法 目前，基于均衡算法主要有三种：轮循( r o l l i l d r o b 岫、最小连接数( l e a s t c o i l i 】e c t i o n sf i r s t ) ，和快速响应优先( f a s t e rr e s p o n s ep r e c e d e n c e ) 。 1 轮叫调度( r o u n dr o b i ns c h e d u l i n g ) 该算法就是以轮叫的方式依次将请求调度不同的服务器，即每次调度执行i = ( i + 1 ) m o dn ，并选出第i 台服务器。算法的优点是其简洁性，它无需记录 当前所有连接的状态，所以它是一种无状态调度。 2 加权轮叫调度( w e i g h t e dr o u l l d r o b i ns c h e d u l i n g ) 该算法可以解决服务器间性能不一的情况，它用相应的权值表示服务器的处 理性能，按权值的高低和轮叫方式分配请求到各服务器。权值高的服务器比权值 河海大学硕士论文计算机集群中负载均衡机制的形式化分析 低的服务器处理更多的连接，相同权值的服务器处理相同数目的连接数。它也是 一种无状态调度。 3 最小连接调度( l e a s t - c o i u l e c t i o ns c h e d u l i n g ) 该算法是把新的连接请求分配到当前连接数最小的服务器。最小连接调度是 一种动态调度算法，它通过服务器当前所活跃的连接数来估计服务器的负载情 况。调度器需要记录各个服务器己建立连接的数目，当一个请求被调度到某台服 务器，其连接数加l ：当连接中止或超时，其连接数减一。 4 加权最小连接调度( w j i g h t e dl e a s 卜c 咖e c t i o ns c h e d u l i n g ) 该算法是最小连接调度的超集，各个服务器用相应的权值表示其处理性能。 服务器的缺省权值为1 ，系统管理员可以动态地设置服务器的权值，在调度新连 接时尽可能使服务器的己建立连接数和其权值成比例。 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 s s c h e d u l i n g ) 该算法是针对请求报文的目标i p 地址的负载均衡调度，目前主要用于c a c h e 集群系统，因为在c a c h e 集群中客户请求报文的目标i p 地址是变化的。这里假 设任何后端服务器都可以处理任一请求，算法的设计目标是在服务器的负载基本 均衡情况下，将相同目标i p 地址的请求调度到同一台服务器，来提高各台服务 器的访问局部性和主存c a c h e 命中率，从而整个集群系统的处理能力。 6 带复制的基于局部性最小连接调度( l o c a l 畸一b a s e dl e a s tc o n n e c t i o n s 谢血 r 印l i c a t i o ns c h e d u l 啦) 该算法先根据请求的目标i p 地址找出该目标i p 地址对应的服务器组；按 “最小连接”原则从该服务器组中选出一台服务器，若服务器没有超载，将请求 发送到该服务器；若服务器超载；则按“最小连接”原则从整个集群中选出一台 服务器，将该服务器加入到服务器组中，将请求发送到该服务器。 7 目标地址散列调度( d e s t i n a t i o nh a s l l i n gs c h e d l l l i t l g ) 该算法先根据请求的目标i p 地址，作为散列键( h a s hk e y ) 从静态分配的 散列表找出对应的服务器，若该服务器是可用的且未超载，将请求发送到该服务 器，否则返回空 8 源地址散列调度( s o u r c eh a s h i n gs c h e d u l i l l g ) 该算法根据请求的源i p 地址，作为散列键( h a s hk e y ) 从静态分配的散列 表找出对应的服务器，若该服务器是可用的且未超载，将请求发送到该服务器， 否则返回空。 第三节计算机集群中负载均衡机制作用的例子 2 3 1 一个科学计算集群的例子 河海大学硕士论文 计算机集群中负载均衡机制的形式化分析 在1 9 9 4 年夏季，t h o m a ss t e r li 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 ，。b e o w u l f 集群这 种方法很快从n a s a 传遍了整个科研机构和社团。实际上，b e o w u l f 集群现在己 被人们看作高性能计算中的一个分支或流派。 b e o w u | f 集群具有的特征： b e o w u l f 是一种系统结构，它使得多个计算机组成的系统能够用于并行 计算。 b e o w u i f 系统通常有一个管理节点和多个计算节点构成。它们通过以太 网( 或其他网络) 连接。管理节点监控计算节点，通常也是计算节点的网关和 控制终端。当然它通常也是集群系统文件服务器。在大型的集群系统中，由 于特殊的需求，这些管理节点的功能也可能由多个节点分摊。 b e o w u | f 系统通常由最常见的硬件设备组成，例如，p c 、以太网卡和以 太网交换机。b e a w u i f 系统很少包含用户定制的特殊设备。 b e o 、) m l f 系统通常采用那些廉价且广为传播的软件，例如，l i n u x 操作系统、 并行虚拟机( p v m ) 和消息传递接口( m p d 。 如图2 1 所示，是i b m 的集群c 1 1 l s t e r1 3 0 0 上b e o w l l l f 集群的组件视图。 弓尹7 r 鞭警l ，、 w 一li m 叫l m m il c n | x 彳7 一 l 。l 糍嚣，粼 一t ：猡鬈z r “”弋一一 l t | | | | 。嚣引e ti = 。4 。8 1 “j ”一“ s e ，e ，h a ，d 。k f 图2 1c l u s t e 3 0 0 上b e o w m f 集群的组件视图 通常b e o w u | f 集群由四个层次构成： 硬件：主要是指i n t e l | a 架构的p c 服务器。 网络：指用于节点间通信的局域网( 普通的以太网) 和并行进程问通信的 高速网( m y r i n e t 等高速网) 。 软件：主要指l i n u x 操作系统和用于并行通信的并行编程库( 如m p i 和 p v m l 。 河海大学硕士论文 计算机集群中负载均衡机制的形式化分析 并行应用 从硬件组织的角度说，b e o w u l f 集群中的节点都是非共享内存的计算机，它 们通过消息传递进行通信完成并行程序问通信。 b e a w u | f 集群在软件层次面临的问题是如何在硬件层次上获得最大的性能。 通常，b e o w u | f 集群采用l i n u x + m p l 的方式支持并行计算。m p l 是采用消息传递 的方式实现并行程序间通信。虽然也可以采用其他的通信方法，但是消息传递模 式是最适合于集群系统的。 消息传递需要在c p u 问拷贝数据。消息传递也可以在线程上实现，并且消 息传递既可以用于集群系统，也可以用于s m p 系统。和线程相比，在s m p 系 统上使用消息传递的优点在于可以很方便的把s m p 上的应用移植到集群系统 上。 i b m 的集群c l u s t e r1 3 0 0 中有一个接入服务器为控制节点( c o n t r o in o d e ) ， 用户提交的任务通过这个节点接入集群系统，其提供管理作业功能p b s ( p o r t a b l e b a t c hs y s t e m ) ，主要是用来在各个计算节点上分配计算任务，控制节点通过搜集 后端计算节点的负载和可用情况来实施它的负载均衡策略。 2 3 2 在l v s 种负载均衡的应用 l m u x n l 】硝s e r v e r 项目是国内最早出现的自由软件项目之一【2 2 2 引。中国为 l m l l ) 【核心贡献代码的人寥寥无几，