（计算机应用技术专业论文）基于linux集群系统负载均衡的研究和实现.pdf

摘要 摘要 随着高性能计算、科学计算的深入发展，集群系统越来越受到重视。集群系 统具有低成本、高性能的特性，提供了强大的批处理和并行计算能力，代表了高 性能计算机发展的主流方向。如何提高集群系统的运行效率、可用性和易用性是 集群计算领域的一个重要的课题。在该类系统中，通过提高硬件性能并不能完全 满足用户复杂多样的要求，尤其是不能满足大规模科学计算和商业应用的要求， 还需要对计算资源进行高效的管理。 集群管理系统( c l u s t e rm a n a g e m e n ts y s t e m ) 作为集群系统软件中一个重要组 成部分，主要的设计目标就是实现上述的需求。目前比较流行的集群管理系统， 虽然具有较完善的基本管理能力，但还不能根据不同应用对软硬件资源的需求和 偏好程度进行资源的动态调度，管理性能与适应能力还有待进一步提高。本文系 统而深入地研究了集群系统中的负载均衡调度算法和资源管理优化技术，深刻分 析了集群系统的模型结构。对现有的集群系统的负载均衡算法进行了新的改进， 从而使集群的资源调度问题得到了很好的解决。同时设计并实现了基于l i n u x 平 台节点终端动态负载均衡备份的集群管理系统。由于新算法的引入本集群管理系 统不但能在集群内部进行资源动态负载均衡调度，而且在不同集群之间的负载均 衡调度也有很好的表现。实验表明本系统与传统的系统相比在吞吐量和平均响应 延迟等方面均具有很好的优越性。 关键词：集群集群管理系统负载均衡l i n u x 平台 a b s t r a c t w i t h i n d e p t hd e v e l o p m e n to fh i g h - p e r f o r m a n c e c o m p u t i n g a n ds c i e n t i f i c c o m p u t i n g ，c l u s t e rs y s t e mh a sb e e nr e c e i v e da t t e n t i o ni n c r e a s i n g l y c l u s t e rc o m p u t i n g s y s t e mw i t hl o w - c o s t , h i g h p e r f o r m a n c ef e a t u r e s ，i n c l u d i n gp o w e r f u lb a t c hp r o c e s s i n g a n d p a r a l l e lc o m p u t i n gc a p a c i t y , r e p r e s e n t st h em a i n s t r e a m d e v e l o p m e n to ft h e h i g h - p e r f o r m a n c ec o m p u t e r h o wt oi m p r o v et h eo p e r a t i n ge f f i c i e n c y , a v a i l a b i l i t ya n d e a s yt ou s eo ft h ec l u s t e rs y s t e mi sa l li m p o r t a n ti s s u ei nc o m p u t i n gf i e l d i ns u c h s y s t e m s ，i m p r o v i n gh a r d w a r ep e r f o r m a n c ec a nn o tf u l l ym e e td i v e r s er e q u i r e m e n t so f u s e r sa n dp a r t i c u l a r l yc a nn o tm e e tt h er e q u i r e m e n t so fm a s ss c i e n t i f i cc o m p u t i n ga n d c o m m e r c i a l a p p l i c a t i o n s ，s o i ti s n e c e s s a r yt om a n a g et h e c o m p u t e r r e s o u r c e s e f f e c t i v e l y b e i n ga ni m p o r t a n tc o m p o n e n to ft h ec l u s t e rs o f t w a r es y s t e m ，t h em a j o rd e s i g n g o a lo ft h ec l u s t e rm a n a g e m e n ts y s t e mi st oa c h i e v et h ea b o v er e q u i r e m e n t s a l t h o u g h w i t hap e r f e c tc a p a c i t yo fm a n a g e m e n t ，c l u s t e rm a n a g e m e n ts y s t e m p o p u l a r l yc a n t s c h e d u l er e s o u r c e so fh a r d w a r ea n ds o f t w a r ed y n a m i c a l l yb a s e do nd i f f e r e n ta p p l i c a t i o n , a l s oi t sm a n a g e m e n ta n da d a p t i v ec a p a c i t yi sy e tt ob ef u r t h e ri m p r o v e d i nt h i sp a p e r , w e s t u d yt h e l o a d b a l a n c i n gs c h e d u l i n ga l g o r i t h ma n dr e s o u r c em a n a g e m e n t o p t i m i z a t i o nt e c h n i q u es y s t e m a t i c a l l y a f t e ra n a l y z i n gt h em o d e ls t r u c t u r eo ft h ec l u s t e r s y s t e m ，w ei m p r o v et h eo r i g i n a la l g o r i t h ma n ds o l v et h er e s o u r c e s c h e d u l i n gp r o b l e m g r e a t l y a tt h es a m et i m e ，al i n u x b a s e dc l u s t e rs y s t e mt e r m i n a ln o d ed y n a m i cd a t a b a s e b a c k u ps y s t e mi sd e s i g n e da n dr e a l i z e d o t h e rt h a nt h ec a p a c i t yo fl o a db a l a n c i n g s c h e d u l i n go fr e s o u r c e sd y n a m i c a l l yi n s i d et h ec l u s t e rs y s t e m ，o u rc l u s t e rm a n a g e m e n t s y s t e mi sa l s oa b l et op e r f o r mw e l li nl o a db a l a n c i n gs c h e d u l i n ga m o n gd i f f e r e n tc l u s t e r s y s t e ma f t e rt h ei n t r o d u c t i o no fn e wa l g o r i t h m e x p e r i m e n t ss h o wt h a to u rs y s t e m o u t p e r f o r m st r a d i t i o n a ls y s t e mi nt e r m so ft h r o u g h p u ta n da v e r a g er e s p o n dd e l a y k e y w o r d s ：c l u s t e rc l u s t e rm a n a g e m e n ts y s t e ml o a db a l a n c i n gl i nu xo s 独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：日期竺堕三 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密在一年解密后适用本授权书。 本人签名：丝盛 导师签名： i i ， l ，、 日期逊：；：互 日期迦8 ：j ： 第一章绪论 第一章绪论 本章对集群系统现有的技术做出了简要的介绍，分析了当前集群管理系统现 状和集群系统的发展需求。集群技术作为2 0 世纪最重要的技术之一对科学计算和 高性能计算有着至关重要的作用。本文正是针对以上的问题进行了深入的分析和 研究。 1 1 引言 集群是以网络技术连接起来的工作站或p c 机的组合，它在工作中是一个统一 的整合资源，所有节点使用单一界面。但仅仅将工作站或p c 机用网络互联，并不 能形成集群，还需要有管理这些机器的软件系统。集群管理系统就是集群系统软 件的重要组成部分。集群管理系统可以根据用户的需求，统一管理和调度集群的 软硬件资源，保证用户作业公平合理地共享集群资源，提高系统资源利用率和吞 吐率。 、一， 近年来，国内外对集群管理系统的研究工作一直很活跃f 3 l ，并且产生了许多公 用和商业化的集群管理系统，国外公用的免费系统如p b s c o n d o r 等及商业化 的c a n a d ap l a f r o f e l l 公司的l s f 等产品，国内神威、曙光系列集群系统以及上海大 学的自强2 0 0 0 高性能集群也都开发了自己的集群管理系统。但是这些研究都是基 于集群系统内部的，基于集群系统层次之上的研究才刚刚开始，现有比较有名的 产品有p l a t f o r m 公司2 0 0 3 年推出的l s fm u l t i c l u t e r6 0 系统等。这些管理系统实 现方式各不相同，采用的界面多种多样，面对通用的或者专门的集群应用，它们 均缺乏对多集群计算环境的有力支持。 目前国内针对多集群系统的管理研究很少，仅有的几个研究也是刚刚开始。 例如国家“8 6 3 ”计划支持的“中国国家网格 项目开发了“织女星网格操作系统 ( v e g a o s ) ，这个软件可以实现多集群之间作业的管理。 由于工程领域对计算能力需求的增长和分布式技术的发展，越来越多的高校 和科研机构都建立了高性能集群系统用于科学计算，甚至有些单位内部都有一个 以上的集群系统，但是这些集群系统之间往往不能互相使用对方的计算资源，它 们往往分布在不同的地理位置，组成集群的节点机在结构、配置和操作系统方面 可能互不相同，而且出于各自处理的日常业务不同，使得各集群的可用性有很大 差异。这就需要计算任务既要能在不同的平台上运行，又要动态分配计算任务， 从而获得多个集群计算资源的最大可用率。 一个完善的集群系统主要应该由两大部分组成：组成集群的硬件系统和使集 基于l i n u x 集群系统负载均衡的研究和实现 群硬件设备协同工作的软件系统。正是由于这两个部分的紧密结合才使得集群能 够综合各个节点的计算能力，从而满足高性能计算的需要。 1 、集群系统的硬件组成 对于集群系统来说，高性能的处理器和高速网络是构建系统所不可或缺的硬 件条件，同时为了满足不同用户在存储方面的要求，还应该选择合适的网络存储 设备。 ( 1 ) 技术的发展已经产生了主频高达几个g h z 的处理器，加上与最新的主板 芯片组技术的结合，为l i n u x 集群的构建提供了高性能的计算节点。例如， s u p e r m i c r o 公司生产的主板系列，可以提供对双i n t e l x e o n r 处理器高达3 0 6 g h z 的支持，并且提供的最高6 4 位1 3 3 m h z 的p c 工总线支持，为高速网络设备 的使用提供了必要的条件。 ( 2 ) 集群系统中，分布在各个节点上的进程之间通常有大量的信息要交换，这 都要通过互联网络来实现。因此，互联网络性能的优劣会直接影响信息交换的速 率和效率，进而影响整个集群系统的整体性能。 理想状态下集群系统应该具有以下特征： 较短的通信延时( l a t e n c y ) 较高的通信带宽( b a n d w i d t h ) 极小的错误率( e r r o rr a t e ) 较好的可扩展性( s c a l a b i l i t y ) ( 3 ) 集群计算任务的不断增加，对待处理的数据和处理结果数据的存储要求越 来越高，而且，用户还希望能够不去访问集群内部的节点就获得处理的结果，这 样，采用一个专门的存储设备就成为一种非常好的选择方案。目前，n a s ( n e t w o r k a t t a c h e ds t o r a g e ，网络附加存储) 、s a n ( s t o r a g ea r e an e t w o r k ，存储区域网络) 和 d a s ( d i r e c ta t t a c h e ds t o r a g e ，直接附加存储) 是目前比较流行的集中存储模式，并 且都有成熟的商业产品可供选择。 2 、集群系统的软件组成 对于本文所涉及的高性能计算集群来说，集群系统的软件主要由两部分所组 成：并行程序开发运行环境和集群管理系统。 ( 1 ) 并行程序开发运行环境 目前广泛使用的并行程序开发及运行系统是p v m 和m p i 。 p v m ( p a r a l l e lv i r t u a lm a c h i n e ) 是由美国田纳西大学、奥克里季国家实验室等研 制的并行程序开发环境【5 1 。它可以把多个异构的计算机组织起来成为一个易于管理 的、可扩展的、易编程使用的并行计算资源。它的各个计算节点可以是共享存储、 第一章绪论 分布式存储的多处理机、向量超级计算机或者是专用的图形、标量工作站。这些 异构的计算节点可以通过多种网络( 比如e t h e m e t ，f d d i 等等) 互联，成为一个网络 计算虚拟机。用户的计算任务被分配到各个计算节点上，多个节点并行运算，从 而实现粗粒度的并行。p v m 的免费、开放以及易用使其成为一个被广泛接受的并 行程序开发环境，有很多并行机公司都宣布支持p v m ，p v m 可以安装到各种u n i x ， l i n u x ，w i n d o w s 操作系统上运行。所有这些又有力地促进了p v m 的推广。现在所 有的并行机都支持p v m 。 m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 是并行计算机的消息传递接口标准。指定该标 准的主要目的是为了提高并行程序的可移植性和使用的方便性。有了统一的标准， 并行计算环境下的应用软件库以及软件工具就都可以透明的移植。各个厂商可以 依据标准提供独具特色和优势的软件实现和硬件支持，从而提高并行处理的能力。 ( 2 ) 集群管理系统c m s ( c l u s t e rm a n a g e m e n ts y s t e m ) 集群管理系统是集群软件的另外的一个重要组成部分。用户正是通过集群管 理系统实现对集群的管理和监控。 本文所做的主要工作就是基于集群管理系统的研究，我们将在后面的章节中 对这部分内容进行详细的介绍。 1 2 集群技术的研究现状 一、集群的概念和特点 我们把多台同构或异构的计算机通过网络连接起来用于完成特定的任务的系 统称为集群系统。集群中的计算机称为“节点终端。因此可以说，集群系统是 通过高性能网络所组成的节点终端的集合。 蜒 $ 蜒 $ 性能 性能 集群系统性价比曲线超级计算机系统性价比曲线 图1 1 超级计算机系统和集群系统的性能价格比曲线图 4 基于l i n u x 集群系统负载均衡的研究和实现 一个集群系统应该具有以下的几个特点【4 】： 1 ) 是将普通p c 工作站、工作站或服务器通过某种方式连接起来构成的多机 系统。连接方式可以采取通过网络适配器和网络集线器，或通过将各个机 器的r s - 2 3 2 串口直接连接起来，还可以通过内存通道卡和内存通道集线 器的方式连接各台机器。 2 ) 具有良好的可用性。即它们都能够在集群的某部分系统资源出现故障的情 况下继续向用户提供持续的服务。几乎所有的典型集群都拥有灾难恢复功 能。 3 ) 具有良好的可扩展性。只需很少的配置工作就可以方便地向集群中加入或 删除工作节点。 4 ) 提供良好的可管理性。管理人员通过简单的操作就可以对集群中的工作节 点或控制节点进行配置工作。 5 ) 提供负载均衡功能。负载均衡包括静态负载平衡和动态负载平衡，为了最 大程度地利用集群中的一切资源，集群需要具有动态负载均衡功能，它能 够通过监视集群中的实际节点终端负载情况并动态地进行调度的改变。 6 ) 一般都有一个主控机，它能够对集群中的机器的运行状态进行监视，而且 能够根据各机器的负载轻重进行任务的调度。 二、目前成熟的集群系统产品 t u r b ol i n u x 公司推出了能够显著地提高基于t c p i p 协议的多种网络服务的 服务质量的高可用性集群系统t u r b oc l u s t e r 。r e dh a t 也提供了基于l i n u xv i r t u a l s e r v e r 思想构建的高可用性集群系统p i r a n h a 。由e r i c s s o n 软件工程研究中心开发 的高可用性集群系统e d d i e 的主要目的是提供一个商业级的，具有较好服务质量的 集群系统的解决方案。 c a n a d ap l a t f o r m 公司开发的高可用性集群系统l s f 提供了分布式集群系统的 解决方案【6 】，通过将物理上分离的多个集群系统连接在一起，使多个同构或异构的 计算机能够通过局域网或广域网共享计算资源，并能够为用户提供对资源的透明 访问。 高性能集群系统m o s i x 为l i n u x 核心增添了集群计算的功能。在m o s i x 集 群环境中，用户无需对应用程序进行修改，或将应用程序与库连接起来，或将应 用程序分配到不同的节点上运行。m o s i x 会自动将这些工作透明地交给别的节点 来执行。 i b mm i c r o s o f t 和i n t e l 于2 0 0 0 年7 月联合发布了一种高可用性服务器集群软 件包及硬件【7 1 ，这种服务器集群的配置包括3 2 台i b mn e t f i n i t y8 5 0 0 r 及i n t e l p e n t i u mi i ix e o n 处理器，运行i b m 的d b 2u n i v e r s a ld a t a b a g e 和m i c r o s o f tw i n d o w s 第一章绪论 5 2 0 0 0a d v a n c e ds e r v e r 操作系统，每分钟可以执行4 4 0 8 7 9 次交易。这套系统面向数 据密集的应用，特别是b 2 b 、电子商务和企业资源规划领域。 在科学计算领域中，比较成功的例子是高性能集群系统b e o w u l f ，它最初是由 n a s a 的g o d d a r df l i g h tc e n t e r 进行开发的，主要目的是支持大规模的科学计算问 题，如地球和太空科学面临的一些计算问题。 1 3 本文主要研究工作及组织结构 本文在系统并深入地分析集群管理系统及集群资源负载均衡技术的基础上， 结合新的动态负载均衡算法设计并实现了集群管理系统软件，通过实验研究表明， 该系统对改善资源利用率和负载均衡均问题均具有良好的效果。 本论文所作的工作主要包括以下几个方面： 1 、系统地阐述了集群系统环境下资源管理系统的特点 对高性能集群系统及其资源管理技术进行了描述，比较分析了集群环境中资 源管理的典型实现，指出集群系统资源管理的特点，这在理论上和技术上对集群 管理系统的设计与实现具有现实的指导意义。 2 、设计并实现了集群管理系统 根据集群系统的环境特点，提出了集群管理系统的体系结构，具体描述了各 模块的功能，并对各个模块进行了详细的分析和设计，最后基于该框架结构以及 c a n a d ap l a t f o 衄公司提供的集群环境，实现了一个多集群管理系统。 3 、对负载均衡算法的分析和研究 对传统的资源调度算法和负载均衡策略进行了深入分析，根据负载均衡相关 技术以及一些影响和制约系统并行效能的关键因素，指出了静态负载均衡策略对 多集群系统支持的不足，在多集群环境下提出并实现了集中式动态负载均衡算法。 4 、实现多集群之间的动态负载均衡。不仅仅在同一个集群内部的共享资源能 够做到相互调度，而且在跨越不同集群之间也能很好的完成资源动态负载均衡工 作，使得整个集群里的可用资源利用率得到极大的提高。 本文的组织结构如下： 第一章：概括了现有的集群技术发展现状，阐述了本文的主要研究工作及组织 结构。 第二章：依据现有的负载均衡技术，深刻的分析了负载均衡的发展状况。针对 目前存在的问题提出了新的集群管理系统模型，同时详细描述了本文所采用新的 动态负载均衡算法设计过程。 第三章：详细描述了本文提出的集群管理系统的设计原理和体系结构，深入分 析了各个功能模块的设计和实现方法。 6 基于l i n u x 集群系统负载均衡的研究和实现 第四章：从单一集群内部资源调度和多集群之间资源调度两个方面验证所实 现的集群管理系统，对本文所采用地新的结构体系和负载均衡算法的优越性进行 了详细的分析。 第五章：总结了全文的主要研究工作，简述了此研究方向的发展重点以 及对文中有待继续改进工作的展望。 第二章基于动态负载均衡新算法的研究 第二章基于动态负载均衡新算法的研究 负载均衡技术基于现有网络结构，提供了一种扩展系统带宽和增加系统吞吐 量的廉价有效的方法，加强了集群系统的处理能力，提高了集群系统的灵活性和可 用性。本章所采用的集中式动态负载均衡算法，能够有效地解决集群系统拥塞问题， 能够就近提供服务，实现地理位置无关性。同时，还能提高节点终端的响应速度，提 高节点终端及其它资源的利用效率，避免集群系统关键部位出现单点失效，从而为 用户提供更好的访问质量。 2 1 负载均衡技术概述 目前海量数据、分布式计算等问题越来越普遍，对计算机性能要求越来越高。 另一方面计算机硬件迅速发展，硬件淘汰周期越来越短，计算机硬件成本越来越 高。为此集群系统的开发迫在眉睫，集群系统的资源调度问题就更加突出了。在 此情况下，如果扔掉现有设备去做大量的硬件升级，这样将造成现有资源的浪费， 而且如果再面临下一次业务量的提升，这又将导致再一次硬件升级的高额成本投 入，甚至性能再卓越的设备也不能满足当前业务量的需求。于是，基于集群系统 的负载均衡机制应运而生。 负载均衡有两方面的含义：首先，大量的并发访问或数据流量分担到多台节 点终端上分别处理，减少用户等待响应的时间；其次，单个重负载的运算分担到 多台节点设备上做并行处理，每个节点设备处理结束后，将结果汇总，返回给用 户，系统处理能力得到大幅度提高。 2 1 1 负载均衡技术分类 目前有许多不同的负载均衡技术用以满足不同的应用需求，下面从负载均衡 技术所采用的设备对象、应用的网络层次及应用的地理结构等方面来分类【l 们。 1 、软件硬件负载均衡 软件负载均衡解决方案是指在一台或多台服务器相应的操作系统上安装一个 或多个附加软件来实现负载均衡。硬件负载均衡解决方案是直接在服务器和外部 网络间安装负载均衡设备，这种设备我们通常称之为负载均衡器。 2 、集中式分布式负载均衡 在集中式算法中，设置了一台主机专门负责系统的负载状况收集和迁移决策， 在分散式算法中，这些工作被分配给不同的处理器【l 。 3 、静态动态负载均衡 8 基于l i n u x 集群系统负载均衡的研究和实现 静态负载均衡中，任务对节点资源的分配是在任务执行前完成的，均衡策略 与系统状态无关，而动态负载均衡要到任务在系统中执行时才能进行。静态方法 又称为确定性调度，而动态方法又叫动态负载均衡。 4 、本地全局负载均衡 本地负载均衡是指对本地的集群做负载均衡，全局负载均衡是指对分别放置 在不同的地理位置、有不同网络结构的集群间作负载均衡。 5 、近似式启发式 近似式负载均衡算法仅仅搜索一个解空间的子集，当寻找到一个好的解就终 止执行。启发式则使用某些特殊参数，能够近似地对整个系统建模。 根据以上的分类，本文所设计的集群管理系统属于全局地、集中式、动态软 件负载均衡。所以它兼有以上技术的优点。 2 1 2 静态和动态的负载均衡技术 负载均衡建立在集群系统的结构之上，它提供了一种廉价有效的方法扩展服 务器带宽和增加吞吐量，加强集群系统的数据处理能力，提高集群系统的灵活性 和可用性。负载均衡并非传统意义上的“均衡”，一般来说，负载均衡只是把有可能 拥塞于一个地方的负载交给多个地方分担。如果将其改称为“负载分担”，也许更好 懂一些。说得通俗一点，负载均衡在集群系统中的作用就像轮流值日制度，把任 务分给大家来完成，以免让一个人累死累活。不过，这种意义上的均衡一般是静 态的，也就是事先确定的“轮流值日 策略。 与轮流值日制度不同的是，动态负载均衡通过一些监控模块实时动态地分析 数据包，掌握网络中的数据流量状况，把任务合理分配出去。 静态负载均衡技术 所谓静态负载均衡算法，即根据系统的先验知识做出决策，运行时负载不能 够重新分配【1 2 】。目标在于调度一个任务集合，使得他们在各个目标节点上有最小 的执行时间。因此，静态负载均衡又被称为调度问题。 总体上，设计调度策略有三个主要因素： 结合互联 任务划分( 粒度策略) 任务分配 通常一个资源调度问题即使在简单地对计算开销和通信开销某种假设后，仍 然是一个n p 完全问题【1 3 】。因此，许多方法均利用数学工具、启发式规则来得到最 优的解。 1 、任务互联 第二章基于动态负载均衡新算法的研究 9 _ 般来说用图模型来表示任务和各个节点终端之间的关系，可以运用任务优 先图，其每个连接定义了任务之间的优先关系；或者运用任务交互作用图，用来 对任务集合建模。 通信 任务一 图2 1 任务优先图图2 2 任务交互作用图 2 、任务划分 一个给定任务划分的粒度( 数据单元) 定义是任务分解中影响通信开销的所 有单元的平均尺度，可分成细粒度、中粒度和粗粒度。顾名思义，粒度小的即是 细粒度，粒度大的即是粗粒度，而中粒度介于细粒度和粗粒度之间。当粒度过大， 并行度会降低，因此潜在并行任务可能被划分进同一个任务而分配给一个处理器； 当粒度过小，进程切换和通信的开销则会增加。而尽可能地消除处理器问通信引 起的开销作为任务划分的一个重要目标，有三种方法比较可行： ( 1 ) 水平或者垂直划分；在给定的任务优先图中垂直或者水平划分。垂直划分 中使用关键路径这个概念来表示，而水平划分将给定的任务分成若干层， 任务的优先级由其所在的层次来决定。 ( 2 ) 通信延迟最小划分：把通信频繁的节点归成一类。然而，这些需要通信的 任务分配在一个处理器上会丧失任务间的并发性。当减少通信延迟的方面 抵消了并行认为串行化的损失时，优选通信延迟最小划分。 ( 3 ) 任务复制：是任务划分中的一个可选方法。使得通过在各个处理器节点上 复制认为来降低通信开销。保留了任务原来的并行性，但在存储空间要求 和同步方面的开销有所增加。 3 、任务分配 在给定的网络系统中分配颗粒，即分配任务划分的结果。如果任务图和处理 器图的节点数目都是m ，则有所! 种不同的分配方法把任务图g i 里的节点分配到处 理器图g n 的节点上。这种方法称作g 到g n 的一个映射。 r 。 二、动态负载均衡技术 集群系统中运行的并行程序，要在程序运行之前就完全确定运行顺序和运行 l o 基于l i n u x 集群系统负载均衡的研究和实现 过程中所产生的负载情况，是很难实现的。因此，动态负载均衡适应了应用程序 可变化，可伸缩特点的需求，在程序动态运行过程中实现实时任务调度和负载均 衡，省去了静态调度分析、形成存储有向任务图等许多负担。 动态负载均衡技术又称为状态相关均衡【l4 1 ，取决于系统的当前状态，也就是 说，系统可以根据当前的负载分布情况，对各个节点上的负载进行动态的调整， 使得已经分配给超载节点上的任务，通过算法调度迁移到轻载的节点上去执行， 从而达到提高系统的资源利用率，减少任务的平均响应时间的目的。 动态负载均衡技术的组成要素t 1 、启动策略：决定谁应该激活负载均衡活动。在发送者启动算法中，超载节 点启动负载转移过程。在接受者启动算法中，轻载节点启动负载转移过程。 2 、转移策略：用于确定一个节点终端是否处于参与任务转移的状态，是作为 发送者，还是作为接收者。 3 、收益性策略：不均衡因子量化了系统中负载不均衡程度，并作为系统负载 均衡其在收益的估计，评估系统均衡负载是否是有收益的。负载均衡的决策给予 关于均衡费用的函数c p ( t ) 的值和均衡代价函数w ( t ) 的值。c p ( t ) 是估计时刻t 通过负 载均衡能够取得的潜在收益的不均衡因子。可定义为均衡前最大处理器负载l m a x 和均衡后最大处理器负载l b a l 的差值。 ，( f ) = f ( lm a x l b a l )( 3 1 ) 通常，如果节约大于付出，负载均衡就是有收益的，即：妒( t ) w ( t ) 负载均衡的代价主要来自以下三个方面： 处理器间传播的负载信息； 任务转移前的任务选择的决策过程； 任务移植的通信延迟。 4 、位置策略：寻找合适的节点位置均衡负载。即当转移策略确定了某节点为 、发送者时，它负责寻找一个接收者。定位策略可以是集中式的或非集中式的，可 分为手动策略、顺序查找策略、门限策略、最短c p u 对列策略、匹配策略等。通 常作为开始负载均衡的节点询问其他节点，以决定是否它适于均衡负载。局部范 围方法中，只有相邻节点才是询问的候选节点；相反，全局范围方法中，系统的 任一节点都是询问的对象。从所有候选节点中选取一个节点，可以随机选取，也 可以基于上一次轮询收集的信息。轮询的替代方法是广播要求，适用于所有节点 都能负载均衡的情况。 5 、信息策略：决定收集系统中其它节点状态信息的时机、收集的方位和收集 的信息。在每个节点终端收集的信息越多，负载均衡的过程则会越有效。然而， 信息收集过程中也会产生新的代价，因为需要有所折中。 第二章基于动态负载均衡新算法的研究 2 2 本系统采用新的集中式动态负载均衡算法 通过以上对现有负载均衡技术的分析研究，本文结合现在有集群系统现状采 用了集中式的动态负载均衡算法来实现提出的集群管理系统。使实现的系统即具 有集中式的易管理性有具有了动态式的灵活性。 负载均衡的主要任务在于： 解决网络拥塞问题，服务就近提供，实现地理位置无关性； 为用户提供更好的访问质量； 提高服务器响应速度； 提高服务器及其他资源的利用效率； 避免了网络关键部位出现单点失效。 基于以上几点，本文采用了集中式动态负载均衡的技术，创新性的实现了不 同集群之间的动态负载均衡，最大化的利用了系统资源，实现更深层次的资源共 - 一 旱。 大型集群负载均衡主要完成来自客户端的服务请求的调度的功能【1 们，是服务 器集群系统中的核心模块。设计良好的负载均衡算法来支持集群系统的动态负载 均衡调度对于整个系统性能的提高是至关重要的。在集群系统中的任务分配算法 的性能问题是一个考虑通讯代价、负载均衡、任务平均等待时间等因素的优化问 题。 通过对负载均衡系统结构和常规的负载均衡算法进行了总结，建立分析了集 群系统的集中式动态负载均衡调度模型，确定了反映系统性能的目标函数。根据 该目标函数提出了一种新的集群系统的动态负载分配算法。该算法在充分考虑服 务器节点的负载状况的基础上，合理的分配任务请求，避免了常用动态负载均衡 算法所存在的任务迁移的“抖动”问题，减少了服务器节点的通信开销和系统负 担，提高了整个集群系统的效率。 2 2 1 现有负载均衡算法存在的问题 集群系统的任务分配是一个需要考虑通信代价、负载均衡、等待时间以及系 统总效率等多目标优化问题。有关它的策略、方法以及算法的研究已经取得了许 多成果。 目前，静态负载均衡算法根据系统的先验知识做出决策，算法不考虑当前节 点状态，决策的准确率低，带有一定的盲目性。常用的方法有图论法、枚举法和 排队法等。这种方法易于实现，但效率不高。现实中各个节点终端以及系统的状 态是不断变化的，只有充分考虑这些状态变化才能实现真正的负载均衡。 1 2 基于l i n u x 集群系统负载均衡的研究和实现 现有的动态负载均衡算法原理是，集群系统中节点终端根据当前的负载情况， 对各个节点终端的负载进行动态的调整，使得已经分配给重载节点终端上的任务， 转移到轻载节点终端，从而提高系统的资源利用率，减少任务的平均响应时间。 动态负载均衡算法应该包含以下三个基本步骤： 山各个节点终端间负载信息的收集； t 根据所收集的负载信息进行决策； 实现系统任务在各个节点间的迁移。 这样的处理往往给系统增加了一定的任务开销。实践的运用中，由于集群系 统中节点终端负载信息的获取、任务有可能无法从负载较重的节点终端转移到负 载较轻的节点终端上，如果强行执行任务迁移，可能会导致该节点终端的崩溃。 另外，如果转移策略的阈值选择不当，还可能会出现负载从一个节点终端转移到 另外一个节点终端又被这个点转移回来的情况，这也大大增加了任务执行的时间， 进而影响了整个集群系统的运行效率。 关于静态均衡算法，它对应用程序中的任务大小、前趋关系、任务通信量等 各种信息，以及网络拓扑结构、各个节点的计算能力等网络情况，在程序运行前 就需要得到，并做好任务分配，继而开始运行程序。这种算法忽略了系统的当时 状态，任务分配是基于对某些计算量和通信量的先验知识。由于网络环境中，各 个节点的负载总是不断地存在变化，因而不可能做出准确的预测，这势必影响到 系统的效率。此类算法适用于较大型的应用程序。 关于动态均衡算法，它通过分析系统的实时负载信息，动态地将任务在各个 节点之间进行分配和调整。重载的处理器及时地将任务再分配到轻载的节点上， 或轻载的节点及时向重载的节点来申请任务。显而易见，后者算法的优点，尽管 这样的调度会增加系统的开销，但是此算法适应应用程序的变化，对于解决动态 到来的任务引起的负载问题做出了及时并有效的响应。 通过上面的分析我们可以发现，现有的均衡算法包括静态负载均衡算法和动 态负载均衡算法。一般的静态负载均衡算法不能感知节点终端的负载情况，从而 无法满足实时负载均衡集群系统设计，为此，我们设计实现了一种高性能的集中 式动态负载均衡算法。 2 2 2 新的系统模型和性能指标 基于以上对现有集群系统的分析，以及现有集群系统存在的问题，本文提出 了新的负载均衡调度模型和算法。在此模型和算法的指导下设计并实现了新的集 群管理系统。 1 、本文提出的集群系统模型 第二章基于动态负载均衡新算法的研究 依据以上分析，本文提出了新的集中式动态负载均衡调度模型，它有多个客 户机、多个服务器及相关的通讯设备组成，客户机产生任务通过网络到达前端调 度器，前端调度器根据任务请求的内容和各个服务器节点的负载情况，将任务分 配到相应的服务器节点终端上。 由于调度均衡问题是一个n p 完全问题，我们对系统通信代价和各个服务器的 处理能力简化处理，做以下假设( 显而易见所列假设条件都很容易满足) ： 服务器集群系统是一个局域同构网络但是各个服务器处理能力是不相同 的。即一个任务在不同的服务器上执行，所需的运行时间是不一样的。 前端分配器和节点终端之间具有相同的通信连接，因此通信费用一致，即 任务通信时间是与服务器节点终端无关的。 m 个客户机独立地、随机地提出任务请求，且每个客户提出请求的时间间 隔t 服从负指数分布。 n 个服务器节点终端独立工作，一个服务器节点终端失败并不影响其它服 务器节点运行的效率。 、 每个任务只需要通过一个服务器即能完成。一个服务器对每项请求的服务 时间是相同的，也就是说我们这里不考虑不同的服务的完成所需要的计算 量的不同。 不考虑任务之间的通信，只在服务器节点与客户端之间有信息发送。 巴 雪 客户机 国 _ 秽 客户机 | 荔 已 詈 客户机 叼固每习啄刁 图2 3 集中式动态负载均衡调度模型 1 4 基于l i n u x 集群系统负载均衡的研究和实现 2 、性能指标 在集中式动态负载均衡调度模型中，m 个来自客户机的任务与个服务器构 成集群系统。由于服务器集群系统对于客户端来说是透明的，因此在系统的服务 的接受者客户端来说，整个系统性能的好坏最关键的一项指标就是任务能不能以 最快的速度完成。相应的，对于提供服务的服务器来说最重要就是要能够快速的 处理来自客户端的请求。因此，图2 3 所描述服务器集群负载调度模型就可以描述 成：有m 个来自客户端的新到的任务，个提供服务服务器节点，各个服务器节 点终端的处理能力和负载状况各不相同，目标是要为负载均衡器找到一个最优的 调度方案，使得所有m 个新到的任务处理的时间最短。 集群系统节点终端处理任务速度的快慢，主要与该节点终端的性能以及当前 的负载状况有关。在集群系统中，能够反映节点终端性能和负载状况的参数主要 有：c p u 的相对速度s 、c p u 任务就绪队列的长度l 、内存占用率z 、网络带宽占 用率w 等等【2 0 】。一般来说c p u 的相对速度越快、c p u 的就绪队列越短、内存占 用率越小、网络带宽占用率越小，那么，它处理任务的速度就越快。为了简化处 理，我们取c p u 的相对速度s 和c p u 就绪队列的长度l 来反映服务器节点终端 的负载情况。 因此，假设f 台服务节点的任务队列长度为p l , ，c p u 相对速度s ，在该服务 器上所分配额的新任务数量珐。 则有： ， 0 m( 3 - 2 ) m = n t ( 3 3 ) i - - i 不同的负载参数对任务负载均衡分配的影响是不同的，根据t h o m a sk u n z 的 研究，对负载均衡分配影响最大的是c p u 的任务就绪队列长度以，随着以的增 大任务的处理时间呈现近似指数增长。即任务的处理时间与，2 的正比，而与c p u 的相对速度成反比增加，即任务的处理时间与s 成反比。针对图2 3 所描述的服务 器集群系统，我们做了这样的预测： 第i 台服务器节点中原有的以个任务，其处理时间为： ， 五= - - 。p l , 2 ( 3 - 4 ) 其中c 为常数。 向第i 台服务器节点分配个新任务，那么所有的任务的处理时间就是： 第二章基于动态负载均衡新算法的研究 1 5 互。詈( 以+ ( 3 - 5 ) 那么，对于第f 台服务器节点来说，它完成所要完成的任务的时间是： g ( n , , s t , p l 户t 2 一互。量+ 哆) 2 一以2 ) ( 3 - 6 ) 对于所有的新到任务来说，它们要完成的时间总和就是每个服务器节点完成 所分配任务时间的总和。所以如果我们取x = ( ，z l ，n 2 ，) 为一个分配方案，那么 所有任务完成所需要的时间就可以表达为： = g ( x ) = g ( 啊，t ，以) ( 3 - 7 ) 2 3 新算法的设计 目前，在集中式负载均衡系统中最常用的负载均衡算法是静态负载均衡算法。 然而由于静态负载均衡算法不考虑节点终端的负载情况，只是按照固定的策略向 节点终端分发任务请求，常用的动态负载均衡算法又不适应集中式负载均衡集群 结构。为了解决以上问题，我们提出了一种新的高可用负载均衡算法。臻矗。 本算法将负载任务调度策略分为两个步骤，如图2 4 所示。 1 ) 任务的初始调度：负载均衡器分析当前接收到的来自客户端的任务请求的 内容，参考负载均衡器中任务节点映射表中的内容。如果该任务仍然存在 与某个节点终端的缓存中，并且该节点终端负载情况为“轻载”则将该任 务发送到这个节点终端上去。采用这种方式可以大大提高节点终端的缓存 命中率，从而实现更快的任务相应。 2 ) 任务的动态负载均衡调度：对于没有任务的初始调度策略中分发出去的客 户端请求，我们采用一种基于遗传算法的高性能动态负载均衡调度算法。 该算法在考虑节点终端负载状况的基础上，充分利用遗传算法在随机搜索 方面的优良性能，将客户端的任务请求合理的分担到各个服务器节点上 去，使得各个服