（计算机软件与理论专业论文）基于蚂蚁算法的网格计算容错机制研究.pdf

独创性声明 i f | f f 川f f f i f l f f f f i f f f f f i f f f f 1 6 y 18 2 4 6 8 9 7 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重废 由g 电太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名：憨砍放 签字日期：呷年，月二弓日 学位论文版权使用授权书 本学位论文作者完全了解一重庆鱼e 电太堂 有关保留、使用学位论 文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权一重麽邮电太堂 可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。 、( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：尹舂、放吹 导师躲 1 昱芝 签字日期：及丑年争月2 弓日 签字日期：2 一j 1 年s 月2 ；日 重庆邮电大学硕士 摘要 网络的广泛运用推动了分布式计算的快速发展。网格作为分布式计算 的重要支撑技术受到广泛的关注，它不仅突破了单个计算机计算能力的限 制，而且将分布的资源组织起来，协同地解决大规模的科学计算和工程问 题；为用户提供了强大的计算能力，极大地推动了科学研究和工程实践的 发展。然而，由于网格系统本身及其资源的动态性和异构性，网格计算平 台相对传统的计算平台来说更容易遇到各种故障。故障的频繁发生已成为 困绕科学家、工程技术人员和网格用户的主要问题之一。如何针对网格系 统的特点，引入恰当的容错机制，切实提高网格计算的可靠性和稳定性， 是网格技术研究的热点和难点。 论文基于容错相关技术的对比研究，总结网格系统中任务调度和容错 的需求及特点。在借鉴已有网格容错框架“m i g o l 思想的基础上，结合蚂 蚁算法在路径选择上的优势，对蚂蚁算法进行一定的改进使之适用于网格 计算。把改进的蚂蚁算法应用到网格任务调度和容错当中，并据此给出自 适应容错调度机制“a d a p t i v e m i g o l ”。首先通过介绍网格的概念及体系 结构引出网格容错流程及容错基本技术。再详细介绍改进蚂蚁算法及其在 网格任务调度和容错过程中的应用，并进行收敛性分析。然后阐述网格系 统中错误检测及错误恢复的相关理论和实现过程，分析整个流程的算法复 杂度。最后用仿真平台“g r i d s i m 对算法进行仿真，分析总结仿真结果。 “a d a p t i v e m i g o l 继承了“m i g o l 灵活的错误检测和恢复机制，改 进了“m i g o l 框架中任务调度算法的效率和错误恢复过程中资源选择的 方式。仿真结果表明： “a d a p t i v e m i g o l 比“m i g o l 在任务数多的情况 下有一定的优势，能够有效地减少任务执行时间和提高任务成功率。 关键词：网格计算，蚂蚁算法，自适应，错误检测，错误恢复 t h er a p i d d e v e l o p m e n t0 fn e t w o r kh a s a r o u s e d s u r g ei n d i s t r i b u t e c o m p u t i n g t h eg r i di s w i d e l yr e g a r d e d a sa n i m p o r t a n tt e c h n o l o g yi n d i s t r i b u t ec o m p u t i n g 1 tn o to n l yb r e a k st h r o u g ht h el i m i to fc o m p u t i n ga b i l i t y o ns i n g l ec o m p u t e r ，b u ta l s oo r g a n i z e sd i s t r i b u t e dr e s o u r c e sf o rs o l v i n gl a r g e s c a i es c i e n c ec o m p u t i n ga n de n g i n e e r i n gp r o b l e m sc o o p e r a t i v e l y t h c g r i d t e c h n o l o g yp r o v i d e sp o w e r f u lc o n l p u t i n ga b i l j t yf o ru s e r s ，a n dp r o m o t e st h e d e v e l o p m e n t0 fs c i e n c er e s e a r c h e sa n de n g i n e e r i n gi m p l e m e n t a t i o n s i n c et h c g r i ds y s t e ma n dr e s o u r c e sa r ed y n a m i ca n di s o m e r i s m ，m o r cp r o b l e m s h a p p e n i n go ng r i dp l a t f b r mt h a nt r a d i t i o n a ic o m p u t i n gp l a t f o r m i ti so n e0 f p r o b l e m st ob es o l v e df o rs c i e n t i s t s ，e n g j n e e r sa n du s e r st h a tt h em a l f u n c t i o n s h a p p e nf t e q u e n t l y a tp r e s e n t ，ah o t s p o ta n dd i f f i c u l tp r o b l e mf b rt h eg r i d r e s e a r c hi s i m p o r t i n gp r o p e rf a u l tt o l e r a n c em e c h a n i s mf o ri m p r o v i n g r e l i a b i l i t ya n ds t a b i l i t yo fg r i dc o m p u t i n gb a s e do nt h ec h a r a c t e r i s t i co fg r i d s y s t e m t h e d e m a n da n dc h a r a c t e r i s t i c a r es u m m a r i z e db yr e s e a r c h i n ga n d o ft h et a s ks c h e d u l i n ga n df a u l tt o l e r a n c e c o m p a r i n gt h ei n t e r r e l a t e df a u l tt o l e r a n c e t e c h n o l o g i e si n t h i sp a p e r c 0 m b i n i n gt h ea d v a n t a g e s0 fa n ta l g o r i t h m0 n r o u t es e l e c t i o n ，t h ea n ta l g o r i t h mi si m p r 0 v e df o ft h ei m p l e m e n t a t i o ni ng r j d c o m p u t i n gb a s e d0 na r c h i t e c t u r eo fg r i ds u p p o r t i n gf a u l tt o l e r a n c c ，i e “m i g o l ”t h ei m p r 0 v e da n ta l g o r i t h mi sa p p l i e di ng r i dt a s ks c h e d u l i n ga n d f a u l tt o l e r a n c e ，a n dt h ec o r r e s p o n d i n ga d a p t i v ef a u l tt o l e r a n c e a d a p t i v e m i g o l ”m e c h a n i s mi sp r o p o s e d f i r s t l y ，t h en o wa n db a s i ct e c h n o l o g i e s0 f g r i df a u l tt o l e r a n c ea r eg i v e nb yi n t r o d u c i n gt h eg r i dc o n c e p ta n da r c h i t e c t u r e t h e nt h ea n t a l g o r i t h ma n di t sa p p l i c a t i o ni n t h e p r o c e s so fg r i dt a s k s c h e d u l i n ga n df a u l tt o l e r a n c ea r ei n t r o d u c e di nd e t a i la n dt h ei m p 南v e d a l g o r i t h mc o n v e r g e n c ei sa n a l y z e d t h et h e o r ya n di m p l e m e n t a t i o no ff a u l t d e t e c t i o na n df a u l tr e c o v e r yi ng r i ds y s t e ma f ee x p a t i a t e da n dt h ec o m p l e x i t y 0 fa l g o r i t h mi sa n a l y z e d f i n a l l y ，t h ea d v a n c ea n ta l g o r i t h mi sv e r i f i e db yt h e g r i ds i m u l a t i o nt o o l s “g r i d s i m ” “a d a p t i v e - m i g o l i n h e r i t st h es m a r tf a u l td e t e c t i o na n d r e c o v e r y0 f n 重庆邮电大学硕士论文 a b s t r a c t “m i g o l ”，a n di m p r o v e st h ee f f i c i e n c yo ft h es c h e d u l i n ga l g o r i t h m sa n dt h e m e a n s0 fc h o o s i n gn e wr e s o u r c ea f t e rd e t e c t e df a u l t t h es i m u l a t e dr e s u l t s h o w sl h a tt o t a lt i m eo np r o c e s s i n gt a s k so n “a d a p t i v e - m i g o l ”i sl e s st h a n “m i 9 0 l i nc a s eo fl a r g en u m b e fo ft a s k s k e yw o r d s ：g r i dc o m p u t i n g ，a n ta 1 9 0 r i t h m s ，a d a p t i v e ，f a u l td e t e c t i o n ， f a u l tr e c 0 v e r y i l l 重庆邮电大学硕士论文 摘要i a b s t r a c t i i 第一章绪论一1 1 1 研究背景1 1 2 国内外研究现状2 1 3 论文研究内容与意义5 1 4 论文结构6 第二章网格计算及容错技术研究7 2 1 网格计算简介j 7 2 1 1 网格的概念及特点7 2 1 2 网格体系结构1 0 2 2 网格容错相关技术1 4 2 2 1 网格容错流程1 4 2 2 2 网格容错基本技术1 5 2 3 本章小结1 6 第三章容错需求及自适应容错模型的设计1 7 3 1 网格系统的容错需求1 7 3 1 1 网格容错的必要性一1 7 3 1 2 网格容错的特点1 8 3 2 自适应容错模型设计与分析2 0 3 2 1 容错策略2 0 3 2 2 自适应容错模型设计2 1 3 2 3 容错模块分析2 2 3 3 本章小结。2 5 第四章基于蚂蚁算法的自适应容错的实现2 6 4 1 蚂蚁算法简介2 6 4 2 蚂蚁算法在网格中的应用2 9 4 2 1 蚂蚁算法的改进2 9 4 2 2 算法收敛性分析3 l 4 3 错误检测一3 3 i v 重庆邮电大学硕士论文目录 4 3 1 错误检测需求3 3 4 3 2 错误检测模型3 4 4 4 错误恢复3 6 4 4 1 检查点机制原理分析3 6 4 4 2 检查点机制关键问题3 7 4 4 3 错误恢复的实现3 9 4 5 复杂度分析4 1 4 6 本章小结一4 3 第五章仿真及结果分析4 4 5 1 仿真平台介绍4 4 5 1 1g r i d s i m 介绍4 4 5 1 2g r i d s i m 平台搭建4 6 5 2 仿真及结果分析4 7 5 3 本章小结5 4 第六章总结及未来工作5 5 6 1 论文总结一5 5 6 2 未来的工作5 5 致谢5 7 攻读硕士学位期间从事的科研工作及发表的论文5 8 参考文献一5 9 v 却经常处于闲置状态。为了有效地提高资源利用率，同时也满足更多用户 的需求，“网格 的概念便应运而生。 、 网格【卜3 】作为下一代并行和分布式计算平台，可以将地理上分布的各 种资源通过高速网络连接起来，这些资源包括计算资源、存储资源、软件 资源、信息资源、贵重仪器和特殊设备等。通过资源整合，网格具备了单 个计算机甚至超级计算机都无法比拟的计算功能和解决问题能力，能够给 用户提供方便、快捷的网络服务。网格提供大规模的、可扩展的、种类繁 多的资源，不仅突破了原有计算能力、存储能力的限制，而且还突破了地 理位置的限制，能够解决对资源要求很高甚至以前都无法解决的问题。另 外，网格系统允许用户访问全球范围内的计算、信息和服务资源以满足本 地用户的需求1 4 l 。对用户而言，网格系统中所有的资源都是透明的，来自 远程的服务就好像是由本地计算机提供的一样，用户不需要关心资源是由 哪里提供，只需要知道系统中哪些资源和服务可用。网格技术的运用大大 提高了资源的利用率，最大限度地满足了网络用户的需求，提供了丰富的 网络资源。将各个领域的服务和资源充分结合起来，协同地提供服务，极 大地节省了时间和费用。 网格是一个大规模的、集成不同地域资源的服务平台，这导致系统在 运行过程中发生故障的概率也相应增加。同时，由于资源在同一时刻可能 被多个用户使用而只被拥有者一人控制，资源此时可用，而下一时刻可能 不可用，具有较大的变动性。系统中的各个环节也可能发生异常，例如： 网络故障； 资源所有者需要独占资源，禁止其他用户共享资源； 节点异常关机； 节点发生( 瞬时间歇永久) 故障； 系统软件升级、节点更换或系统维护等。 为避免任务在执行的过程中遇到故障后直接导致任务失败，也为提高 重庆邮电大学硕士论文第一章绪论 系统的稳定性和可靠性，网格必须具备一定的容错功能，在遇到故障后采 取一定的措施，防止任务执行失败。网格容错技术的发展状况影响网格系 统的稳定性，而网格系统的稳定性也直接关系到网格技术的应用和推广。 鉴于网格系统中容错技术的重要性，网格研究人员对容错进行了大量的讨 论和研究，也取得了很大的进展。对网格计算的长期演进和发展来说，容 错技术是网格研究的重点与难点。 1 2 国内外研究现状 网格应用现状 最近几年网格技术在全球范围内得到广泛的发展，网格项目在很多科 技领域中起着重要的作用。2 0 0 8 年1 0 月，全球迄今为止最大规模的分布式 运算网格“全球l h c 计算网格正式启动【5 】，它将为设在欧洲的大型强子 对撞机( l h c ) 提供强大的数据运算支持。这个运算网格共包括分布在全 球3 3 个国家和地区的1 4 0 多个计算中心，参与运算的科研人员将多达7 0 0 0 名，每年可分析和管理大型强子对撞数据超过1 5 0 0 万g 。网格技术起源于 美国对超级计算机使用的研究，所以，在网格技术开发和网格示范方面， 美国已有多年丰富的经验并具有世界领先的技术水平。为了进一步促进网 格技术、网格平台和网格应用的发展，美国也在不遗余力地进行网格技术 的研究与实验。在美国国家科学基金会的“太网格 项目中1 6 j ，以t 字节级 处理大量数据的研究正在进行。4 个国家性计算中心正在建设一个大规模 集成示范系统，拟将处理能力共有1 3 6 t 次浮点运算并有5 7 6 t 字节存储空 间的高性能计算机与4 0 g b p s 高速网络连接。另一个项目是美国国家卫生研 究院的“生物医学信息研究网络 。这一项目由加州大学牵头，全美1 0 家 研究机构参与，开发能使脑活动视觉化和共享数据的网格平台，以便研究 阿尔茨海默氏症和其他疾病。网格技术也得到亚洲很多国家的重视，正在 从事网格研究的主要亚洲国家和地区有中国、日本、韩国、新加坡和中国 厶渣 口i 弓。 我国从上世纪9 0 年代末开始研究网格技术以来，经过几年的发展已经 取得了显著进展。其中，中国国家网格【7j ( c n g r i d ) 是国家8 6 3 重大专项 “高效能计算机及网格服务环境”的课题之一。其目标是开发技术先进、 性能稳定、实用性强的网格软件( c n g r i dg o s ) ，有效支撑中国国家网格 环境与网格应用的开发、部署、运行管理和维护，实现生产性运行并推广 2 重庆邮电大学硕士论文 第一章绪论 应用。通过c n g r i dg o s 支持资源共享、协同工作、应用集成功能。建立在 西藏羊八井的宇宙线观测实验室是我国重要的粒子天体物理实验基地。羊 八井宇宙线观测实验基地每年将采集约2 0 0 t b 以上的原始数据。这些数据 的处理需要约相当于4 0 0 个目前最快的c p u 的处理能力。所以，必须采用网 格技术来分析和处理这些海量数据。2 0 0 8 年1 1 月，中国科学院计算技术研 究所、曙光信息产业有限公司和中国科学院计算机网络信息中心正式签署 合作协议，三方将共同建设中科院网格超级计算平台。这一平台将实行商 业化运作，面向社会提供服务。我国高性能计算机的研发及生产水平已经 处于世界领先的水平，曙光公司的5 0 0 0 a 型高性能计算机在全球排名第十， 一但应用水平有待提高，此次合作建设的网格超级计算平台将进一步促进高 性能计算机的应用。这标志着中国在网格的应用与商业推广方面迈出了坚 实的一步。 容错系统现状 由于容错机制在计算机系统中的重要作用，研发人员十分重视容错技 术的研究与发展。2 0 0 7 年8 月第十二届全国容错计算学术会议【8 】在北京召 开。与会代表分别就容错计算机体系结构、故障诊断与测试理论、容错机 制的可靠性和可用性、容错机制的实现等方面进行了学术交流与讨论并产 生很多共识。2 0 0 9 年1 月，我国科技部正式与浪潮集团签订“浪潮天梭高 端容错计算机 项目，该项目将投资近1 0 亿，用于自主开发承担关键商业 应用的高端容错计算机系统。高端容错计算机是“十一五 期间“8 6 3 计 划在信息技术领域的重大技术项目，是国家信息技术布局的战略举措， 对于打破国外对高端容错计算机及其核心关键技术的垄断，摆脱对国外高 端容错计算机的依赖，消除信息安全隐患，保障国家信息战略安全具有深 远意义。 目前，对网格系统容错技术的研究尚处起步阶段，常用的几种容错技 术是：重试，复制，检查点技术。重试是最简单的容错技术，系统检测到 错误后，不论任务执行到什么状态都把该任务在源节点上重新执行。重试 技术的优点就是算法简单、灵活、容易实现；缺点是浪费以前的执行结果， 对需要长时间运行的任务来说，浪费时间。重试技术适用于短时间任务。 复制技术l9 1 0 l 的思路是：一旦检测到哪个资源节点失效，复制该节点上的 所有任务到其他节点上，在新节点上重新运行。在这种情况下，只要不是 全部的节点失效，任务就能处理完成。复制技术的缺点也和重试技术一样， 对长时间运行的任务来说，浪费时间。检查点技术l 1 1 ，l2 j 就是在系统运行的 适当时刻设置检查点( c h e c k p o i n t ) ，保存系统当时的规范运行状态，并对 3 重庆邮电大学硕士论文第一章绪论 各进程进行相关的跟踪和记录，建立检查点文件。系统发生故障后，将相 关进程回卷【”，1 4 】( r o l l b a c k ) 到故障前系统一致性状态( 检查点) ，经过状 态恢复后从检查点处执行，而不是从开始处执行。检查点技术的优势是能 够节省大量重复计算的时间，缺点是算法复杂，需要占用额外的存储空间。 检查点技术适用于需要长时间执行的任务。网格系统中经常运行大规模科 学计算任务，如高能物理、生物计算、战场模拟等应用。这些任务的执行 时间都很长，一旦系统发生异常将导致任务运行失败。如果将这些程序都 重新执行的话，会引起计算资源的巨大浪费，也浪费很多时间。所以，在 网格环境下利用检查点作为容错技术已成为网格研究人员的共识。 文献【1 5 】提出一种基于运行时刻的容错管理软件体系结构，支持开发 者和管理员针对不同中间件服务失效定制合适的故障检测和修复机制。文 献f 1 6 1 在开发网格服务体系结构的基础上提出一种自适应错误检测框架， 该框架可以根据用户的需求制定不同程度的错误检测服务。文献【1 7 】在综 合研究目前网格作业调度环境的基础上提出一种容错计算网格作业调度 的随机p e t r i 网模型，并给出了网格作业分配策略和计算站点内的作业选择 策略，以及网格容错计算的性能评价指标。文献【1 8 】提出一种灵活的网格 容错中间件，把不同的容错技术集合到一个大的框架中，用户可以对一些 参数的大小进行设置，从而选择不同的容错技术。文献【1 9 】同样也介绍了 多容错技术相结合的容错模型，该模型结合了重试、复制、检查点三种容 错技术，这三种容错技术在时间、空间上存在一定的折衷，不同是任务可 以根据对时间或空间要求的不同选择不同的容错技术。文献【2 0 】提出一套 通用网格计算容错框架，该框架通过提供一种层次式错误检测方式以及基 于策略的通用错误处理方式来保证网格计算的可靠性。文献【2 1 】提出一个 专门为工业管理及财务管理而设计的支持动态负载平衡的软件容错体系 结构，该文提供了一个考虑到时间要求、c p u 消耗、并行计算要求的仿真 实例。文献【2 2 1 阐述了针对代理服务器失效的容错管理策略，提出了一种 多代理服务器并支持应用控制的技术框架。文献【2 3 】从工作流的角度阐述 了网格容错机制，该文重要考虑了网络带宽，网络时延等因素。在选择任 务调度方式和容错技术的时候主要采用了总体规划分配任务和任务迁移 方式。 德国学者a n d r el u c k o w 和b e t t i n as c h n o r 在文献【2 4 】中提出一种新的 网格容错模型“m i g o l 。“m i g o l ”【“2 6 l 是一种基于检查点技术的，面向服 务的、可靠的、支持容错的网格中间件。“m i g o l 框架的重点集中于研究 网格系统错误的检测和恢复机制。所以“m i g o l ”的优势在于灵活的错误 4 重庆邮电大学硕士论文第一章绪论 检测和恢复，而在选取任务调度算法的时候只选择了最小期望时延算法， 而且在检测到错误后把检查点文件回卷在原来的资源节点上，在原来的资 源节点上重新启动新进程。这就存在一个缺陷，一旦节点失效或拥有者独 占资源时，任务就无法继续执行。针对“m i g o l 的这些不足，论文在“m i g o l 的基础上给出一种自适应容错机制“a d a p t i v e m i g o l 。首先，结合蚂蚁算 法【2 7 】选择路径的优势，对蚂蚁算法进行一定的改进，把这改进的蚂蚁算法 作为“m i g o l 的任务调度算法；然后，在检测到错误后，在恢复的过程 中不再把检查点文件回卷到原来的资源节点上，而是利用先前蚂蚁算法对 资源节点的评估结果选择一个相对最优的节点，在这个新选择的节点上建 立新进程，把检查点文件回卷到该新进程上，重启新进程。这样就能有效 避免原节点失效时导致任务无法继续完成的极端情况。 1 3 论文研究内容与意义 论文在根据重庆市教委科学技术研究项目( 1 ( j 0 5 0 5 0 7 ) 网格资源管 理及任务调度的关键技术与应用的基础上深入分析网格容错相关理论和 技术，针对网格计算的容错需求和已有容错技术的优缺点，旨在探索一种 面向网格计算的自适应容错策略，介绍相应的任务调度算法和错误恢复过 程中的资源选择方式，以进一步提高网格系统的可靠性和稳定性。 本文的主要内容包括： ( 1 ) 分析当前网格容错的相关技术，总结已有容错技术的优缺点以 及适用情况； ( 2 ) 根据网格环境下任务调度的特点，结合蚂蚁算法在路径选择方 面的优势，给出一种改进的蚂蚁算法，进行相关的算法分析； ( 3 ) 分析和总结网格环境下错误检测和错误恢复的相关理论和技术， 详细描述改进的蚂蚁算法在网格任务调度和错误恢复中的应用； ( 4 ) 利用网格仿真平台g r i d s i m 对算法进行仿真，并对仿真结果进行 分析、对比。 目前，网格环境下的容错研究还处在发展阶段，研究人员对容错技术 和容错框架提出了很多假设和创新，论文也是为提高网格容错效率而进行 的一种探索，其研究意义在于：针对已有网格容错框架“m i g o l 给出了一 种改进的容错策略一一“a d a p t i v e m i g o l ”，它在继承原有灵活容错功能的 同时缩短任务执行时间，改善容错过程中新节点的选择方式，进一步提高 5 重庆邮电大学硕士论文 ， 第一章绪论 网格容错的稳定性。对网格容错的研究提出一种新的想法和新的探索，为 网格环境下容错技术的后续研究做铺垫。 1 4 论文结构 论文共由六章组成，详细的组织结构如下： 第一章阐述论文的研究背景，结合当今最新的相关资料和文档分析国 内外相关工作的研究现状，指明论文的研究目的及贡献，给出论文的组织 结构。 第二章介绍网格的基本概念、网格的特点以及现有的网格体系结构。 简要介绍网格的容错流程及现有容错基本技术。 第三章首先通过一个实例分析网格容错的必要性，然后分析网格系统 中容错的特殊性以及容错需求，介绍网格容错的特点。通过对网格容错的 分析给出自适应容错模型的设计框架，对该框架下几个重要的模块进行分 析和介绍，为论文后续章节的研究打下基础。 第四章针对网格计算中的任务一一资源匹配方式给出改进的蚂蚁算 法，并把算法应用在网格的任务调度及错误恢复中。然后分析该算法的收 敛性。结合网格系统处理任务的整个过程，在介绍任务调度算法后分析网 格系统的容错策略。阐述错误检测与错误恢复的详细模型和过程。最后， 对整个任务调度和容错的过程进行复杂度分析。 第五章简要介绍仿真工具“g r i d s i m 和“g r i d s i m 的搭建过程。然 后对算法进行仿真，分析对比仿真结果。 第六章对全文作出总结，指出文章中的一些缺点，并指明下一步的研 究方向。 6 重庆邮电大学硕士论文 第二章网格计 网格作为一种大型的服务平台，连接了分布在各地的计算机、数据库、 服务器等资源。网格系统在管理这些异构资源的同时也必须遵循网络中已 有的各种协议，因此，必须建立一套完成的网格体系结构，协调各组件之 间的交互。五层沙漏结构和开放网格服务体系结构是两种比较成熟的网格 体系结构。容错作为网格系统一个重要的功能也是网格研究的热点，研究 人员针对网格容错提出了很多具有建设性的理论框架，其中一些也受到广 泛的关注并应用到实际当中。本章就将对网格概念、体系结构以及容错的 相关理论进行分析介绍。 2 1 网格计算简介 2 1 1 网格的概念及特点 网格的概念最早产生于二十世纪九十年代中期，它的产生是大规模科 学计算对计算资源和计算能力需求不断增长的结果。当现有计算机系统不 能满足大规模科学计算的需求时，就需要使用其它的计算资源。通常的方 法是购买新的计算设备，如超级计算机、大型硬件设施等，但这样也存在 很多缺点。第一：由于这些超级计算机系统价格非常昂贵，导致添置新设 备的成本过高；第二：现实的科学研究以及对计算机的使用发展非常快， 对计算机系统更新的要求也非常快，导致计算机硬件更新的速度跟不上对 计算机系统要求的速度。而此时，有许多计算资源却处于闲置状态，这样 一方面计算资源不足，另一方面又有很多计算资源浪费，造成资源利用不 合理。急需一种新技术将现有的资源进行统一的整合和管理，以此来解决 复杂的科学计算任务同时也最大限度地利用现有的资源，网格的概念便是 在这种情况下应运而生。 一 网格是借鉴电力网的概念提出来的。在使用电力时，用户不需要知道 电是从哪个电站输送出来的，也不需要知道该电力是通过什么样的发电机 产生的，而只需将插头插入电力网，就可以得到所需要的电力。 网格的最终目标也是希望消费者在使用网格的资源时，就如同现在使 用电力一样方便，用户只要把任务提交到网格中就能通过网格系统处理任 7 重庆邮电大学硕 务而不用关心是谁处理任务。网格希望通过系统对资源的整合和管理最终 给用户提供的是与地理位置无关，与具体计算设施无关的通用计算能力和 各种网络资源。 广义的网格概念一一全球网格g g g ( g r e a tg l o b a lg r i d ) ，不仅包括计 算网格、数据网格、知识网格、商业网格等，还包括一些已有的网络计算 模式，如对等计算p 2 p 等。可以说，网格试图实现的是网络上所有计算的 连通和资源的共享。这样网格就形成一个集成的计算与资源环境。它能够 充分利用各种计算资源，把整个互联网集成为一台巨大的超级计算机，从 而提供一种随处可得的、可靠的、高效而且廉价的计算能力，实现全球范 围内各种资源的全面共享。广义的网格包括以下三点含义： ( 1 ) 从理论上讲，网格的目标是实现资源共享和协同工作。这种理 论可以清晰地指导行业和企业中各个部门的资源进行整体上的统一规划、 部署、整合和共享，而不仅仅各个部分独立的规划、调配、占有和使用资 源。 ( 2 ) 网格是一种技术。为了达到不同类型的、分布各地的资源实现 共享和协作的目的，网格计算必须解决多个层次的资源共享和合作问题， 制定一定的网格标准，把i n t e r n e t 作为通讯和信息交互的平台提升到资源 共享的平台。但是目前的并行计算、分布计算、中间件等技术远远没有解 决多个组织之间的资源共享问题，以及广域范围的多系统之间联合处理和 、 计算等网格计算面临的关键问题。因此，网格计算技术的研究具有独特性、 紧迫性和挑战性。 ( 3 ) 网格是一种公共基础设施，是连接网格环境中各种计算机、数 据、设备和服务等资源的基本设施。这种设施的建立，可以使得用户随时 随地方便地利用网络上的各种资源，无需在用户端配备大量的硬件设施和 复杂的软件系统就可以简便地使用网格提供的各种服务。这样，用户对设 备和软件的投资以及维护开销将大大减少。 网格的概念提出以后，研究人员又进一步对网格进行一定的规范，为 网格制定一系列的标准。首先，对网格的功能和使用进行一定的规范，经 过学者和研究人员不断地讨论和研究，最终认定网格系统必须满足以下三 个条件： ( 1 ) 在非集中控制的环境中协同使用各种资源。网格整合各种资源， 协调不同的任务，这些资源和用户在可能处在不同地域，比如，个人电脑 或超级计算机；相同或不同公司的不同单元：网格还必须解决分布式环境 中出现的安全策略、费用、成员权限等问题。否则，系统只能算本地管理 8 重庆邮电大学硕士论文 第二章网格计算及容错技术研究 系统，而不是网格。 ( 2 ) 网格系统必须使用标准、开放、通用的协议和界面。网格的使 用建立在多功能的协议和界面之上，这些协议和界面解决认证、授权、资 源发现和资源存取以及任务的调度等基本问题。应该着眼于一个大的网格 环境来解决各种应用，而不仅仅是本地资源。 ( 3 ) 用户可以得到本地资源所不能提供的服务。网格允许它的资源 被协调使用，以得到多种服务质量，满足不同使用者的需求，如系统响应 时间、流通量、有效性、安全性、资源重定位以及资源的共享，使得网格 整体系统的功效比各部分的功效总和要大得多。 网格作为一种新出现的重要基础设施，和传统计算机系统或大型计算 机系统相比，它有很大的不同，并具有自己重要的特征。主要体现在以下 几方面：， 分布性j 分布性是网格最主要的特点之一。网格的分布性，首先是指网格的资 源是分布的。组成网格的是计算能力不同的计算机，各种类型的数据库甚 至电子图书馆，或者其他的设备与资源，这些资源都是分布在地理位置互 不相同的多个地方，而不是集中在一起的。分布的网格一般涉及的资源类 型复杂，规模较大，跨越的地理范围较广。 基于网格的计算是分布式计算而不是集中式计算，网格是在分布式环 境下解决资源与任务的分配与调度、安全传输与通信、实时性保障、人与 系统以及人与人之间的交互等问题。网格的分布性也给网格系统的稳定提 出了巨大的挑战，突出了网格环境下容错的必要性。 共享性 网格资源是分布的，但是可以充分共享，即网格上的任何资源都可以 提供给网格使用者。共享是网格的目的，没有共享便不是网格，解决分布 资源的共享问题，是网格的核心内容。共享的含义非常广泛，不仅指一个 地方的计算机可以用来完成其他地方的任务，还可以指中间结果、数据库、 专业模型库以及人才资源等各方面的共享。 自相似性 网格具有自相似性特征。网格的局部与整体之间存在着一定的相似 性，局部往往在许多地方具有全局的某些特征，而全局的特征在局部也有 一定的体现。网格的自相似性在网格的建造和研究过程中具有重要意义。 动态性 网格的动态性包括动态增加和动态减少两方面。原来可用的资源或者 9 重庆邮电大学硕士论文第二章网格计算及容错技术研究 功能，在下一时刻可能会出现故障或者不可用；而原来没有的资源，可能 随着时间的推移会不断地加入进来。 网格资源的动态变化特点要求网格管理必须充分考虑并解决好这一 问题，对于网格资源的动态减少或者资源出现故障的情况，要求网格能够 及时采取措施，实现任务的自动迁移，做到对高层用户透明或者尽可能减 少用户的损失。 网格资源的动态增加需要提高网格的可扩展性，也就是在网格的设计 与实现时，必须考虑到新的资源能否很自然地加入到网格中来，并且可以 和原来的资源融合在一起，共同发挥作用。网格的可扩展性要求体现在规 模、能力、兼容性等方面。一开始网格的规模往往不是特别大，不需要也 不可能一步到位，但是网格应该能够允许对它自身进行多种形式的扩展， 网格规模扩展后网格相应的管理软件也应该能够满足可扩展性要求，最大 限度地利用资源。 网格动态性大大增加了任务不能持续运行的可能，一旦资源离开就会 导致任务的中断，所以网格系统必须具备容错功能。 多样性 网格资源是异构和多样的。在网格环境中可以有不同体系结构的计算 机系统和类别不同的资源，因此网格系统必须能够解决这些不同结构、不 同类别资源之间的通信和互操作问题。正是因为异构性和资源多样性的存 在，对网格软件的设计以及网格资源的管理提出了更大的挑战。 自治性与管理的多重性 网格上的资源，首先是属于某一组织或者个人的，因此网格资源的拥 有者对该资源具有最高级别的管理权限，网格应该允许资源拥有者对他的 资源有自主的管理能力，这就是网格的自治性。但是网格资源也必须接受 网格的统一管理，否则不同的资源就无法建立相互之间的联系，无法实现 共享和操作，无法成为一个整体为更多的用户提供方便的服务。 因此，网格的管理具有多重性，一方面它允许网格资源的拥有者对网 格资源具有自主性的管理，另一方面又要求网格资源必须接受网格的统一 管理。 2 1 2 网格体系结构 网格体系结构就是关于如何建造网格的技术。它给出了网格的基本组 成与功能，描述了网格各组成部分的关系以及它们集成的方式或方法，刻 1 0 重庆邮电大学硕士论文 第二章网格计算及容错技术研究 画了网格有效运转的机制。到目前为止，比较重要的网格体系结构主要有 两个，一个是f o s t e r 在2 0 0 1 年提出的五层沙漏结构；另一个是以i b m 为 代表的科技企业提出的开放网格服务体系结构( o p e ng r i d s e r v i c e e s a r c h i t e c t u r e ，o g s a ) 。 五层沙漏结构 五层沙漏结构【2 8 】是一种影响十分广泛的结构，它的主要特点就是简 单，主要侧重于定性的描述而不是具体的协议定义。它的一个很重要的思 想就是以“协议”为中心，也十分强调服务与程序设计接口和软件开发工 具的重要性。 五层沙漏结构根据其中各组成部分与共享资源的距离，将对共享资源 进行操作、管理、使用的功能分散在五个不同的层次，越向下层就越接近 于物理的共享资源，因此该层与特定资源相关的成分就比较多；越向上层 就越感觉不到共享资源的细节特征，也就是说上层是更加抽象共享资源的 表示，因此就不需要关心与底层资源相关的具体实现细节。 峭应用 应用层 、燃 汇聚层 资源与服务 资源层 的安全访问 与连接层 j i 夕嚆攀兹源 构造层 图2 1 五层沙漏体系结构 如图2 1 所示，在五层沙漏结构中，底层的部分是构造层，构造层面 对的是具体的物理资源，通过对这些局部资源的管理，向上层提供对这些 资源管理的控制界面。构造层的上面是连接层，主要是为下层的物理资源 提供安全的数据通信能力，这是资源之间进行互操作的前提，连接层使得 孤立的单个资源之间建立了联系。连接层上面是资源层，它反映的是抽象 的局部资源的特征，汇聚层的功能是如何将下面以单个资源形式表现出来 的资源集中起来，解决多个资源的汇聚问题。应用层和资源的距离最远， 重庆邮电大学硕士论文 第二章网格计算及容错技术研究 它关心的是有什么样的资源可以由其他层提供给虚拟组织，解决不同虚拟 组织的具体问题。 五层沙漏结构的另外一个重要特点就是沙漏形状。其内在的含义就是 因为各部分协议的数量是不同的，对于其中核心的部分，要能够实现上层 各种协议向核心协议的映射，同时实现核心协议向下层各种协议的映射。 核心协议在所有支持网格计算的节点都应该得到支持，因此核心协议的数 量会少于上层和下层协议的数量，这样核心协议就形成协议层次结构中的 一个瓶颈。 开放网格服务体系结构 开放网格服务体系结构【2 9 l ( o p e ng r i ds e r v i e c e sa r c h i t e c t u r e ，o g s a ) 是继五层沙漏结