（计算机应用技术专业论文）基于分布式哈希表的网格资源发现机制研究.pdf

山东师范大学硕+ 学位论义 基于分布式哈希表的网格资源发现机制研究 摘要 随着当今科学技术的发展以及互联网技术的普及，各种特殊应用对广域分布 的资源之间共享和协同提出更高的需求，网格技术成为近年来分布式系统领域中 一个研究热点。网格目标是将地理上分布、异构的高性能计算机、数据服务器和 大型检索存储系统等资源，通过高速互连网络连接并集成起来，共同解决问题， 最终消除信息孤岛和资源孤岛；在动态的网格环境中分布着大量不同类型的服务 和资源，快速、准确地进行资源与服务发现，是影响网格计算性能的关键因素。 在网格从基础理论研究阶段逐步走向应用阶段的今天，网格系统对网格资源 发现提出了新的要求，例如可扩展性、基于属性查找、范围查找、多属性查找等。 资源发现策略归根到底取决于系统中资源的组织模式。结构化拓扑资源发现机制， 将杂乱的信息有序化，然后将信息按照一定的规律组织，进而抽象出高效的查询 算法完成准确查询定位。分布式哈希表技术具有的结构化特性优势，为资源发现 机制提供可扩展的巨大潜力和新性能。 本文围绕分布式哈希表在网格资源发现机制中的应用展开研究，主要内容概 括如下。 ( 1 ) 通过对网格基本概念、网格资源特性的系统分析，得出网格环境下资源 发现机制的功能需求，并对目前较为成熟的共享环境中的资源发现机制进行 了分析。 ( 2 ) 重点分析了结构化方式中基于分布式哈希表( d h t ) 的资源发现机制。d h t 技术可以准确地定位关键字所在位置，具有的结构化特性优势，为资源发现 提供可扩展的巨大潜力和新性能。然而，这种分布式查找能力对于网格环境 下的资源定位还不够。网格资源发现机制不仅应考虑资源的位置信息，而且 应考虑资源的属性信息，分别从多属性查询技术和范围查询技术两个方面对 现有的部分基于分布式哈希表的网格资源发现机制进行分析、比较，讨论了 分布式哈希表技术在网格资源发现机制中的应用。 ( 3 ) 针对分布式哈希表在处理多属性查询和范围查询时的不足，提出一种基 于c h o r d 的网格资源发现机制v c h o r d 。使用d h t 技术的c h o r d 系统，命名 空间是一维的，需要为系统中节点和资源对象提供一个唯一的i d ，即c h o r d 系统只能处理单关键字。v c h o r d 在基本不改变c h o r d 原有特性的基础上， 通过定义网格资源向量空间，资源属性的表示方法，从修改关键字k e y 的内 容着手，将由资源的多属性产生的多关键字转换成由单关键字表示的单一属 山东师范人学硕l ：学位论文 性，实现增强查找发现能力的目标，可以满足多属性查询和范围查询的要求， 并对相关问题进行了讨论。通过模拟实验验证v c h o r d 的有效性与可用性， 并对实验结果进行了分析。 ( 4 ) 研究提出了资源发现机制中资源的主动声明问题。处于可用状态的资源， 可以通过向潜在用户发送声明信息，声明其可用状态，主动供用户选择。资 源的主动声明可以使资源参与到资源发现过程中，变被动等待为主动参与， 用以提高资源被发现和被使用的概率。 关键词：网格；资源发现；分布式哈希表；c h o r d 分类号：t p 3 9 3 山东师范大学硕t 学位论文 r e s e a r c ho nr e s o u r c ed i s c 0 v e r ym e c h a n i s m si ng r i d sb a s e do n d i s t r i b u t e dh a s ht a b i e a b s t r a c t w i t ht h ed e v e l o p m e n to fm o d e mt e c l i i l o l o g y 锄dt h ew i d cu s e0 fi m e m e t ，m 孤y s p e c i a l 印p l i c a t i o n sr c q u i r em o r cs h a r c 柚dc 0 0 p e r a t i o no fw i d e - 缸e ad i s t r i b u t e d e n v i r 0 姗e n tr e s o u r c c s g f i dt e c h n o l o g yi sb e c o m i n gam a i l l l yi s s u ei nt h ed i s t r i b u t e d s y s t e m 1 t sa i mi st oc o n n e c tt h r o u g l lh i g l ls p c e di n t e m e t 柚di n t e g r a t er c s o u r c e s ，s u c h 懿g e o g r a p h i c a l l yd i s t 曲u t e d 孤dh e t e r o g e n e o u s ，h i g l lp e 0 册柚c ec o m p u t e r d a t a s e r v c r 柚di n d e xd a t a b a s es y s t e m ，a n dt h e r e f o r er c s o l v ep r o b l e m st o g e t h e r 卸df i n a l l y e l i m i n a t ei n f b 册a t i o ni s l a n d s 觚dr e s o u - c ci s l 锄d s 。al a 唱en u m b e r0 fs e n ，i c e s 柚d r e s 0 u r c e sa r cd i s t r i b u t e di nt h ed y n 锄i cg r i de n v i r o 姗e n t ，觚dt l l ek e yp o i n ti st 0 d i s c o v e rt h e mp r o m p t l y 锄da c c u n t e l y b u tw h e n 鲥dt e n d st o w a r d sa p p l i c a t i o nf 如mr e s e a r c ho fb a s i ct h e o 巧，t h e 鲥d s y s t e m sp u tf 0 聊盯da d v 柚c e dr c q u e s t so n 舒d r c s o u r c ed i s c 0 v e r y f o re x a m p l e ，t h e a b i l i t y0 fe x t e n s i v e ，r e q u e s tb 弱e d0 na t t 抽u t e s ，珊g eq u e r y ，m u l t i - a t t m u t e sa i l ds 0 0 n t 1 l ee s s e n c e0 fr e s o u r c cd i s c o v e r yi st of i n di l l f 0 姗a t i o no fr e q u i r e dr e s o u r c ei n a g 伊e g a t e 锄dt h ek e yo fr c s o u r c ed i s c 0 v e r ym e c h a l l i s ml i e si nh o wt 0o r g 锄i z e 卸d m 柚a g er e s o u r c ei n f b 加a t i o ni no r d e r t 0s u p p o nr e s o u r c ed i s c 0 v e r y n i sp a p e rs t u d i e so nt h ea p p l i c a t i o no fd i s t r i b u t e dh a s ht i a b l e ( d i 1 ) i ng r i d r e s o u r c ed i s c o v e r ym e c h 锄i s m ，t h em a j o rr c s e a r c hw o f k sa sf o l l o w s f i f s t l y ，t h i st h e s i sa n a l y s i st h eb a s i ct h e o r ) r 觚dr e s o u r c cc h a r a c t e r i s t i co fg r i d ， 趴dr c s o u r c ed i s c o v e r ym e c h a n i s m si i ls h a r c dr c i s o u i c ce n v i r o 姗e n ts y s t e m a t i c a l l y d i s c u s s e st h ef i l n c t i o n a lr e q u i f e m e n to fr e s o u r c cd i s c o v e r ym e c h 觚i s m si ng r i d s s e c o n d l y ，f c u r c ed i s c 0 v e r ym e c h a i l i s m sb 弱e do nd h t i ss t u d i e dm a i n l y 缸 0 n e0 fs t n l c t u r a lm e t h o d ，d h tc 觚d i s c 0 v e rr e s o u r c cp o s i t i o nw i t hak e y 砌r a t e l y ， h o w e v e r i ti sn o te n o u g l lf o fg r i dr e s o u r c ed i s c 0 v e 巧g r i dr c s o u r o ed i s c o v e r y m e c h a n i s m sh a v et ot a k eb o t hr e s o u r c e p o s i t i o n i n f b 加a t i o n觚da t t 曲u t e s i n f b 姗a t i o ni n t oa c c o u n t 。s 0 m ed i s c 0 v e r ym e c h a n i s m si ng r i d sb a s e d 伽d i s t 曲u t e d h a s ht a b l ea r ea j l a l y z e da n dc 0 m p a r e d 舶m 俩0h a n d si nr a n g eq u e r yt e c l l i l i q u e s 卸d m u l t i a t t r i b u t e sq u e r yt e c h n j q u e s t h i r d l y ，i no r d e rt 0m a k eu pt h i sd e f i c i e n c y0 fd h t ，v c h o r d i sp u t sf i 叫n a r d ， a c c o r d i n gt ot h ei n a p p l i c a b i l i t yi nm u l t i a t t r i b u t e sa n d 砌g eq u e r y v c h o f di sag r i d 山东师范人学硕1 ：学位论文 r e s o u r c ed i s c o v e r yb a s e do nc h o r d ，c o m p l y i n gw i t ht h el a wo fc h o r d 。o nt h i sb a s i s ， d e f i n eg r i dr e s o u r c ev e c t o rs p a c em o d e la n dr e s o u r c ea t t r i b u t e se x p r e s s i o nt 0e x t e n d r e s o u r c ed i s c 0 v e r ya b i l i t y r e s o u f c e 柚dn o d e si nc h o r di sm 雒k e db yau n i q u e i d e n t i f i e r v c h o r dc h a n g et h ec o n t e n t0 ft h ek e y ， 0 n ek e yc 舳s t 柚df o r m u l t i - a t t r i b u t e s w ed e v i s e sat e s tp l a nt 0i n s p e c tt h ei d e aw ep r o p o s e dw i t hd h t s i m u l a t o rp e e r s i m ，锄dd os o m ea n a l y s i sw i t ht h es i m u l a t e dr e s u l t f i n a l l y ，w ep r o p o s eam e t h o do fr e s o u r c ea c t i v e d e c l a m t i o n 。t i l l ea v a i l a b l e r e s o u r c e s 伽s e n dd e d a r a t i o nt 0t h e i fp o t e n t i a lc o n s u m e r s ，t 0d e c l a r et h e i rs t a t e s r e s o u r c c 拟i v ed e d 盯a t i o nm a k e sr e s o u r c et a k ep a ni nr e s o u r c cd i s c o v e r y ， t 0 i m p r o v i n gu t i l i z a t i o no ff c s o u r c e s k e y w o r d s ：g r i d ；r e s o u r o ed i s c o v e r y ；d h t ； c h o r d c l a s s i n c a 廿o n ：t p 3 9 3 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 它人已经发表或撰写过的研究成果，也不包含为获得( 注：如没 有其它需要特别声明的，本栏可空) 或其它教育机构的学位或证书使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示谢意。 学位论文版权使用授权书 上忑 了依 本学位论文作者完全了解堂蕉有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人 授权兰堕可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后 适用本授权书) 学位论文作者签名：社 聊签字： 签字日期：2 0 0 9 年7 月弓9 日 签字日期：2 0 0 年月 同 山东师范大学硕十学位论文 第一章绪论 网格技术是分布式计算领域中的一个新的研究方向，网格( g r i d ) 是继i n t e r n e t 和 w e b 之后出现的一种新型的网络应用平台。如果说互联网实现了计算机硬件的连通，w e b 实现了计算机软件的连通，而网格技术则可以实现互联网环境下所有资源的全面连通。 1 。1 研究背景 在信息化的浪潮下，人类的应用需求正朝着高性能、多样化、多功能方向发展，相应 地需要计算能力更强大的计算机。在科学研究领域，许多大规模科学计算需要由多种机器 组成、多个系统合作、多个科学仪器设备相连的网络虚拟超级计算机，这些需求鼓励人们 在互联网技术的基础上把现有的利用率不高的分散在不同地理位置的、异构的、动态的 各种资源通过高速网络连接在一起，整合成一台虚拟的超级计算机，其中每一台参与计算 的计算机就是一个“节点 ，而整个计算是由成千上万个“节点 组成的“一张网格 ， 这种计算方式叫网格计算。这样组织起来的“虚拟的超级计算机 有两个优势：一个是 数据处理能力超强，另一个是能充分利用网上的闲置处理能力。 1 。1 1 网格 简单地讲，网格可以看成一台巨大的具有无限处理能力的超级计算机，一种能够实现 区域或全球合作或协作的虚拟科研和实验环境，支持以大规模计算和数据处理为特征的 科学活动，可以为最终实现网络虚拟环境下的资源共享和协同工作提供了有效的解决思 路。 网格的描述性定义：“网格是构筑在i n t e r n e t 上的一组新兴技术，它将高速互联网、 高性能计算机、大型数据库、传感器、远程设备等融为一体，为科技人员和普通老百姓 提供更多的资源、功能和交互性。i n t e r n e t 主要为用户提供电子邮件、网页浏览等通信 功能，而网格功能更多更强，能让用户透明地使用计算、存储等其他资源。网格就是在 缺少中央控制、没有全知者( o 肌i s c i e n c e ) 以及强的信任关系的情况下能够协同使用地 理分布的各种资源。刀网格所关心的共享不仅仅是简单的文件交换，更强调直接对计 算机、软件、数据以及其它资源的直接访问，而且这种共享是高度可控的，需要在资源 提供者和消费者之间详细的定义什么可以被共享、哪些人可以共享、在什么条件下可以 共享。川2 1 因此，可以认为网格就是把整个i n t e r n e t 整合成一台巨大的超级计算机，充 分吸收各种计算资源，并将它们转化成一种有效的、可靠的、标准的、经济的计算能力， 实现计算资源、数据资源、信息资源、知识资源、专家资源的全面共享和协同。 网格特性 网格作为一种新出现的重要基础性设施，和其他的系统相比，具有以下几个重要特 性。 山东师范大学硕l 学位论殳 ( 1 ) 多样性。网格系统不仅资源种类繁多，而且每类资源有不同的属性。 ( 2 ) 动态性。网格环境下的一些资源本身具有动态性，例如，在处理任务的时候，负载时刻 在变化；网络链路带宽流量的变化；内存的占有量随着进程状态的变化而变化；网格系 统下的局部环境也在动态的改变着。 ( 3 ) 分布与共享性。网格系统的目标是把位于不同地理位置的异构计算机、异构数据库、 贵重仪器、海量存储器等用高速网络连接起来，并用网格中间件、网格资源管理系统等把 它们整合成一个虚拟系统。 ( 4 ) 扩展性。网格系统初期的计算规模较小，随着超级计算机系统的不断加入，系统的 计算规模也随之扩大。要在网格资源规模不断扩大、应用不断增长的情况下，不降低网 格计算的性能： ( 5 ) 自相似性。网格的局部和整体之间存在着一定的相似性，局部往往在许多地方具有全 局的某些特征，而全局的特征在局部中也有一定的体现； ( 6 ) 多级管理性。网格环境下的局部资源既属于个人或机构，由个人对其资源作相应的管 理和维护，又要在网格系统作整体部署的时候，由网格管理员根据系统里任务的情况统一 调度。 ( 7 ) 异构性。高速网络连接起来的各种资源是异构的，类型各不相同。网格分布在广域网 上不同管理域的各种计算资源中，异构机器之间的协作和转换是网格计算的重要问题。 ( 8 ) 自适应性。在网格系统中，资源故障是定律，而不是意外。在众多的资源中，任一 资源都会出现故障，资源管理必须能动态监视和管理网格资源，从可用资源中获取最大 性能。 ( 9 ) 安全性。与仅限于单一组织范围的分布计算环境不同，网格计算环境的安全系统必 须支持高度灵活的共享关系定义和对共享资源的复杂高级控制。在帮助客户和服务相互 确定对方是否可信赖等方面，网格计算环境必须扮演一个关键角色。 网格概念的核心 网格概念的核心在于它突破了以往强加在资源之上的种种限制，使人们可以以一种 全新的更自由、更方便的方式使用资源，解决更复杂的问题。 首先是计算能力大小的限制，以前大部分的用户无法得到足够的计算能力，因此许 多问题的解决是不能够通过计算或者是不能完全靠计算来实现的。而网格所提供的计算 能力要远远超过以前我们所能够想象的程度，对于大多数用户来说网格提供给他们的计 算能力足以满足其计算需求，在这种计算能力的支持下，人们可以做许多以前无法想象 和无法完成的工作。 其次是地理位置的限制，计算资源是分布在各处的，有些资源是稀缺或不可复制的， 有些资源甚至是无法和特定的地理位置分开的因此要使用这些资源，在以前许多情况下 必须到相应的地方去，这在很大程度上限制了这些资源的使用。而网格把“到资源所在 的位置”对资源进行使用的限制打破了，对资源的使用和使用者所在地位置以及资源所 在地位置无关。突破了在使用资源时对位置的限制，是网格的具有突出意义的功能。 山东师范人学坝，i ：学位论文 第三是网格打破了传统的共享或协作方面的限制，以前对资源的共享往往停留在数 据文件传输的层次，而网格资源的共享允许对其它的资源进行直接的控制，而且共享资 源的各方在协作时可以以多种方式更广泛地交流信息，充分利用网格提供的各种功能。 网格使得共享与协作的方式和方法更广泛了，而且为这种合作提供了各种控制策略与手 段，可以根据需要，动态地与不同的组织与个人建立各种级别的工作关系。 这些观念和使用方式上的改变，是由网格技术支持的，不是凭空产生的。网格的意 义，就如同互联网改变了人们传统的通信方式和通信手段一样，它将改变人们传统的计 算方式和计算手段，网格技术将为人们提供更强大、更方便、更高级的问题求解手段。 1 1 2 网格资源 网格中包含有多种形式、功能各异的资源，除了万维网上传统意义的资源之外，还 包括天文望远镜、电子显微镜、环境监测探测器、无线通信设备等。 网格资源定义 网格资源指所有能够通过网格远程使用的实体，它是网格中所有可以被主体请求使 用的实体的总称d 1 。网格资源包括计算机软件和硬件、仪器和设备、人力资源等( 人力资 源包括人的知识、能力等多种因素，是网格上最具有伸缩性的资源) 。资源所有者可向其 他使用资源的人收费，资源可共享或独占，可被清晰地定义，或用参数描述h 1 。 资源参数即资源的属性信息。网格内所有可用资源，包括系统类、网络类、应用类 等，由于资源的动态性，这些资源的属性信息不能全部预先知道，需要资源管理系统实 时发现。例如：系统类资源属性包括，当前节点名、主机名、主机地址、操作系统名、 操作系统版本、硬盘类型、硬盘容量、内存容量、c p u 个数等静态信息和网格节点的内 存利用率、c p u 利用率、硬盘利用率等动态信息；网络类资源，如主机间通信延迟，数 据传输的带宽，路由情况等。 网格资源特点 网格系统中的资源无论在种类的多样性还是功能的多样性方面，都远远超过以往的 系统，同时也具有了一些以往系统中的资源所不具备的特点。下面是网格资源的几大特 占 5 】= ( 1 ) 自治性 网格资源有自己的本地管理机构或处在本地管理机构的管理之下，网格资源具有或 强或弱的本地自治能力。网格管理系统必须尊重本地管理者，迁就本地管理策略，不能 把网格的意愿强加到资源上，更不能替换本地管理系统。网格只能根据资源加入网格时 与网格系统签署的协议合理地使用资源，在协议的基础上，网格系统可以把某个资源强 制给用户使用。 ( 2 ) 异构性 网格上的资源分布在地理位置互不相同的各个地方，可以跨越广阔的地理范围。网 格中的资源不仅数目巨大，而且常常是高度异构的。资源种类繁多，功能各异，访问接 山东师范人学硕i ：学位论文 口也不尽相同，本地管理系统不同，共享规则不同。网格资源异构性主要表现在资源类 型的异构性、体系结构的异构性、软硬件环境的异构性和网络连接的异构性等方面。 ( 3 ) 动态性 网格资源是在不断变化的，其动态性主要表现在以下几个方面。首先，网格资源的 可获取性是处于不断变化之中的，资源所有者在服从网格规则的前提下，可以自由决定 资源加入或退出网格。其次是资源能力处于不断变化之中，资源拥有者在服从网格规则 的前提下，可以在任何时候改变其资源投入网格的能力。第三，对于同一个应用而言， 适合它的资源集合是随应用提交时刻而动态变化的。网格资源变化的细节要对用户和应 用程序透明，应该由网格管理软件对网格的变化进行处理，这就增加了网格资源管理系 统的难度，使得网格资源管理比以往的任何系统更困难。 ( 4 ) 二分特性 网格资源最终都是由具体的资源拥有者提供的，除了一部分专用的网格资源是专门 提供给网格用户使用的之外，大部分资源都同时作为网格用户可以使用的网格资源和资 源拥有者自己使用的本地资源。网格用户远程使用资源不能损害资源拥有者和本地用户 的利益，即使那些百分之百贡献给网格使用的专用网格资源，也要有时间来运行本地管 理系统。尤其是那些可以在其上运行网格用户提交的作业的资源，其能够运行的作业的 种类和可以进行的操作与本地作业拥有的特权是有区别的。网格作业所能进行的操作和 拥有的权限要保证资源本身的安全工作和拥有者的合法权益，以及使用该资源的其他网 格用户的安全。 ( 5 ) 管理策略的多重性 网格应用所使用的资源通常都不可能只被一个管理者拥有和管理，而是由多个管理 者管理各自拥有的各种资源。不同管理者可能采用不同的管理策略，不同的验证机制、 授权机制和访问机制。并且，不同的管理者势必对资源的重要性有着不同的认识，从而 也就会采用不同的局部资源管理策略。需要建立一种机制，该机制能使各个资源管理者 的局部管理策略和系统的整体目标相互协调。 1 1 3v o 虚拟组织 虚拟组织1 ( v i r t u a lo r g a n i z a t i o n ，v o ) 不仅跨地域，而且延伸到不同的组织、 异构的软硬件平台。 v o 划分的原则是将网格系统中属性类别相近的资源节点组织在一起，按照一定的协 议或规则，构成一个v o 。在这个组织中，所有资源节点形成一个团体，相互合作，相互 获取资源，共同完成某些任务。一个v o 类似于一个小的网格，而一个庞大的网格系统可 以看作是由若干个v o 组成，用网络把各种虚拟组织连接起来，形成一个没有边际的动态 网。这样划分v o 可以发挥资源自治性的特点，因为资源共享关系随时问的变化而变化。 v o 将所占用的资源作为自己的“软边界 ，为了动态适应作业处理不同时期对资源需求 4 山东师范人学硕上学位论文 的变化，v o 会适时更新自己的“边界”以增加或释放资源量。各个v o 通过定义自身的 “软边界 来获取所用的资源。 在网格应用中，网格中每个v o 的建立都有其需求和目的，在很多情况下，v o 管理 的资源可以以理解为地理位置分布、逻辑位置相邻、属性相似的资源服务集合。而v o 的属性就体现了这种相似性。当网格加入新的参与者，也建议它根据提供的资源和服务 的属性加入有相似属性的v o ，这样可以为相似服务提供相似的管理策略，实现服务类型 划分。 1 2 问题提出 在网格中存在着数以百万计的共享资源，我们如何才能充分地利用。网格系统首先 要能够为用户找到符合用户标准的资源。当用户要求使用某种资源时，用户提出请求， 相关的资源请求被提交给资源发现机制，资源发现机制通过某些发现策略在系统中找到 符合请求的资源集合，即满足请求条件的目标资源。 实现资源共享和协同工作的关键在于有效地发现资源，资源发现机制是网格系统中 最基础最底层的组成部分。所谓的资源发现就是根据用户或应用的资源发现请求，采用 一定的方法和手段获取所需资源描述信息的过程。而资源发现机制就是在对多样的、异 构的、动态、自治的、分布广泛的资源合理组织的基础上，为用户查找和访问所需资源 提供有效的资源发现服务，最终根据用户的资源发现请求返回一系列符合需求的信息服 务机制。它是网格设计的核心之一。资源发现机制的关键在于如何组织和管理资源信息 以支持资源发现。 因此，在网格环境里如何有效的发现资源就成为影响网格计算是否成功的一种重要 因素，它为网格环境下的其它服务中间件的正常运作奠定了基础，如资源监控、资源匹 配和资源调度等。 由于网格环境下存在着大量资源和用户，再加上资源在地理位置的广域分布性以及 资源类型和用户请求的异构性，使得网格资源发现与其他系统环境下的资源发现有着一 定的区别，最大的问题是网格资源状态的动态变化( 如更新、加入和退出) 很难预测， 这些问题都增加了资源发现的难度和复杂性，使得网格环境下的资源发现面临着一定程 度的挑战。为了更好适应这些方面，网格环境下的资源发现应该满足以下功能需求： ( 1 ) 能有效的注册、注销和更新资源信息：网格中存在大量的不同类型的资源，资源提 供者必须将资源信息有效的注册到网格系统中，资源才能被网格资源使用者利用；当资 源提供者停止提供某项资源服务时，相应的网格资源信息要从网格系统中及时删除；同 样，为确保资源信息的准确性，系统应定期更新资源信息。所有这些面向用户的操作都 要求较少的反应时间和较低的系统歼销。 ( 2 ) 能有效的查询资源信息：有效的资源信息查询是资源发现机制的最基本功能，同样 也是网格资源使用者使用资源的前提，如何快速、有效的查询到与资源使用者提交的资 源查询请求相匹配的资源信息是资源发现服务需要解决的首要问题。并且通过合理的资 源信息组织和资源请求处理方式，尽量降低请求响应的延迟。 5 山东师范人学倾 = 学位论文 ( 3 ) 实现分布式控制：如果采用集中式的资源发现方法，将资源信息都存储在中心服务 器中，随着网格规模的扩大，网格资源数目和资源信息量的增加，中心服务器将会成为 整个系统的瓶颈，极大的影响了发现服务的效率。而采用分布式架构，将资源信息分布 存储在地理位置不同的多个网格节点上，就可以避免中心服务器工作负荷过大、负载不 均衡等问题，并且具有良好的可扩展性。单个服务器的故障不能影响到整个资源发现系 统的正常运行以及发现服务的工作效率，这就要求整个系统具有很高的健壮性。 ( 4 ) 良好的可扩展性：由于网格环境的动态性，随着大量网格资源的动态加入，网格规 模可能随时扩大，因此，如何在系统规模扩大的情况下，使得资源发现的一系列操作( 如 信息发布、删除、查找) 的效率仍然保持不变是需要研究的重要问题之一，也就是说资 源发现机制需要具有良好的可扩展性。 ( 5 ) 支持基于属性的查找：因为网格中共享的资源种类很多，用户需要通过指定一系列 期望的属性( 例如，一个可用内存大于2 5 6 m 的l i n u x 机器。) 来描述所需资源，而不是 指定一个全局唯一的标识符( 例如，v e g a 2 i c t a c c n ) 。 1 3 研究内容 资源发现是网格计算需要解决的首要问题，许多网格项目已经做了不少有益的研究 工作，但是目前的资源发现机制仍存在不少问题。因此，对网格环境下资源发现机制的 研究具有重要意义。本文在以下几个方面开展研究工作。 ( 1 ) 对网格的基本概念和网格资源的特性进行系统的分析，得出网格环境下的资源发现 机制的功能需求。 ( 2 ) 重点分析了结构化方式中基于分布式哈希表( d h t ) 的资源发现机制。d h t 技术可以 准确地定位关键字所在位置，具有的结构化特性优势，为资源发现提供可扩展的巨大潜力 和新性能。然而，这种分布式查找能力对于网格环境下的资源定位还不够。网格资源发现 机制不仅应考虑资源的位置信息，而且应考虑资源的属性信息，分别从多属性查询技术 和范围查询技术两个方面对现有的部分基于分布式哈希表的网格资源发现机制进行分 析、比较，讨论了分布式哈希表技术在网格资源发现机制中的应用。 ( 3 ) 针对分布式哈希表在处理多属性查询和范围查询时的不足，提出一种基于c h o r d 的网格资源发现机制v c h o r d 。使用d h t 技术的c h o r d 系统，命名空间是一维的，需要为 系统中节点和资源对象提供一个唯一的i d ，即c h o r d 系统只能处理单关键字。h o r d 在基本不改变c h o r d 原有特性的基础上，通过定义网格资源向量空问，资源属性的表示方 法，从修改关键字k e y 的内容着手，将由资源的多属性产生的多关键字转换成由单关键 字表示的单一属性，实现增强查找发现能力的目标，可以满足多属性查询和范围查询的 要求，并对相关问题进行了讨论。通过模拟实验验证v c h o r d 的有效性与可用性，并对实 验结果进行了分析。 ( 4 ) 研究提出了资源发现机制中资源的主动声明问题。处于可用状态的资源，可以通过 向潜在用户发送声明信息，声明其可用状态，主动供用户选择。资源的主动声明可以使 6 山东帅范大学帧上学位论文 资源参与到资源发现过程中，变被动等待为主动参与，以提高资源被发现和被利用的概 率。 1 4 论文结构 本文共分为六章。 第一章绪论。介绍网格资源发现机制的研究背景，明确网格、网格资源、虚拟组织 的基本概念，给出了本文的主要研究内容及文章的整体组织结构。 第二章共享资源环境中的资源发现机制研究。介绍共享资源环境中的资源发现机 制，对目前较为成熟的网格项目中的资源发现机制做了详细说明，引出了结构化资源发 现机制。 第三章基于分布式哈希表的资源发现机制。介绍了分布式哈希表，总结和比较了几 种代表性的路由协议，从多属性查询技术和范围查询技术两方面重点分析了分布式哈希 表技术在网格资源发现机制中的应用。 第四章基于c h o r d 的网格资源发现机制。提出一种基于c h o r d 的网格资源发现机制 v c h o r d ，并对相关问题研究讨论。通过模拟实验验证v c h o r d 的有效性，并对实验结果进 行分析。 第五章资源发现机制中的资源主动声明。讨论了资源的主动声明问题，用以提高资 源被发现和被使用的概率。 第六章总结与展望。总结本文的研究工作，提出未来的研究方向。 山东师范人学硕一l j 学位论文 第二章共享资源环境中的资源发现机制研究 资源发现机制是关系到广域分布式环境中资源共享和协同工作效率的关键问题。依 赖于特定的资源共享环境，资源发现问题在含义和需求上有些差别，其目标和约束也不 同。在w e b 服务、计算网格、和p 2 p 技术中，都对这个问题进行了广泛的研究。 2 1w e bs e r v i c e s 中的服务发现 w e bs e r v i c e s 致力于通过使用w e b 的标准协议实现服务的互操作和集成，与网格研 究针对的目标有相似性，而面向服务的网格体系结构0 g s a ( o p e ng r i ds e r v i c e s a r c h i t e c t u r e ) 的出现使两者有了很强的融合趋势。随着网格技术的发展，网格环境中的 所有实体都可以用w e bs e r v i c e ( 简称w s ) 进行表示。广义上讲，w s 定位的定义为：“定 位( 1 0 c a t i n g ) 先前未知的、满足特定功能要求的机器能够处理的w s 描述信息的行为 阳1 。 w e bs e r v i c e s 具有如下的体系结构，基于服务提供者( s e r v i c ep r o v i d e r ) 、服务 注册中心( s e r v i c er e g i s t r y ) 、服务请求者( s e r v i c er e q u e s t o r ) 三个角色之间的交互， 具体涉及到发布( p u b lis h ) 、查找( f i n d ) 和绑定( b i n d i n g ) 三种操作。在w e bs e r v i c e s 体系结构中最重要的角色是服务注册中心u d d i ，( u d d iu n i v e r s a ld e s c r i p t i o n ， d i s c o v e r y ，a n di n t e g r a t i o n 统一描述、发现、集成协议) 是一套基于w e b 的、分布式 的、为w e b 服务提供了信息注册中心的实现标准规范，定义了w e b 服务的发布与发现的 方法，实现了集中式的统一描述、注册和查找。 绑定 图2 一l w e bs e r v i c e s 体系结构 2 。2 网格项目中的资源发现 与传统的分布式系统相比，网格中集成的资源规模更大，种类更多，分属于不同的 组织，而且参与网格的各节点往往拥有不同的利益和资源管理策略。 8 山东师范人学硕 ：学位论文 2 2 1g l o b u s 项目中的资源发现机制 g l o b u s 是一种用于构建计算网格开放体系结构、标准的项目，是当前最流行的网格 开发工具，已成为一种事实上的行业标准。g 1 0 b u s 中的监控和发现服务组件 m d s ( m o n i t o r i n ga n dd i s c o v e r ys e r v i c e ) 删，将网格内的资源及服务组织分为诸多v o ， 利用基于l d a p ( 轻量目录访问协议l i g h tw e i g h td i r e c t o r ya c c e s sp r o t o c o l ，l d a p ) 的层次目录服务机制来组织管理信息。主要功能是资源发现、提供资源状态信息以及提 供资源调度与监控信息。 这里的资源发现是指查找那些满足执行作业所要求条件的资源，这些条件一般包括 操作系统类型、版本、处理器类型、内存大小、网络带宽、负载程度等。资源发现负责 提供资源状态信息，确认网格资源属性信息，完成网格环境中资源信息的发现、描述、 监控和更新，提供对网格计算环境的一个真实、实时的动态反映。 m d s 具有由网格索引信息服务( g r i di n d e xi n f o r m a t i o ns e r v i c e s ，g i i s ) 、网格 资源信息服务( g r i dr e s o u r c ei n f o r 髓t i o ns e r v i c e s ，g r i s ) 和信息提供者 ( i n f o r m a t i o np r o v i d e r ，i p ) 三种组件构成的层次结构。g r i s 提供了查询网格中某个特 定节点的功能，既能提供如主机标识( i d ) 的静态信息又能提供如c p u 和可用内存的动 态信息。 i p 可与任何资源数据搜集服务连接并向g r i s 报告，i p 提供的数据包括负载、c p u 、 操作系统、文件系统、内存及网络连接等方面的信息。g r i s 作为资源的代理运行在资源 上层，g r i s 向g i i s 注册。一个g i i s 包含了被一个特定虚拟组织所管理的所有g r i s 的 信息，提供了单一的系统映像。一个g i i s 可以是几个g i i s 的集合，因而g i i s 可以是一 个层次结构。顶层的g i i s 可以回答所有关于位于其下的虚拟组织中资源的查询。 g r i s 与i p 都运行在资源节点上，其中i p 负责收集资源信息，并将资源信息提交给 驻留在该资源节点上的g r i s ，i p 与g r i s 直接通信。g r i s 将本地资源信息提交给上一级 的g i i s ，由g i i s 生成这些资源信息的索引目录。资源信息注册和查询的过程如图2 2 。 资源消费用户可以通过g i i s 查询到资源的索引信息，也可将查询请求直接递交给本地的 g r i s 。本地g r i s 如果在本地资源信息中查询不到用户需要的资源，就将查询请求提交给 上一级的g i i s ，若上一级的g i i s 也没有可以匹配的资源信息，继续向上一级提交，直 到查询到可匹配的资源信息为止。 9 山东帅范大学坝i 。学位论文 息 图2 2g 1 0 b u s 中的资源发现 m d s 的这种两级资源管理模式，使其对分布式异构资源的发现有了很高的效率和质 量，能够将全局和本地资源管理协调起来。但是，尽管采用了两层的资源发现结构，但是 m d s 并没有提出适应于整个网格范围的资源发现机制。m d s 中的聚合目录只适用于提供某 个特定v o 内的资源信息，各个聚合目录之间尽管可以通过标准的协议进行交互，进行信 息复制等操作，但m d s 并没有对这些信息结点之间的交互定义通用的协议和规范。m d s 通过构建层次状目录服务器来完成资源的组织，但是目录服务器层次的搭建是通过配置 文件来完成的，仍然缺乏有效、易扩展的分布式目录服务器的构建、维护方法。m d s 的 问题在于： m d s 实现的是基于l d a p 的树状元数据目录服务，只能管理相对静态对象的描述信 息，不能处理对象的频繁更新。 m d s 不能处理复杂的查询，层次化的查询语言缺乏对数据进行复杂处理的能力。 l d a p 风格的查询语言需要用户指定查询的起始结点和查询范围，需要指定了查 询的执行顺序 m d s 不提供负载平衡机制 2 。2 。2c o n d o r 项目中的资源发现机制 c o n d o r n 们将大量地理分布、属于不同所有者的空闲计算资源聚合起来支持高吞吐率 的计算。c o n d o r 中的计算资源由于只是在空闲时才对c o n d o r 可用，参与具有不稳定性， 因此被称为机会资源( o p p o r t u n i t yr e s o u r c e s ) 。c o n d o r 允许对任务设置检查点( c h e e k p o i n t ) ，并允许资源拥有者在需要自己的资源时对任务进行抢占。被抢占的任务不会因 此失败，因为检查点保存了任务的状态，可以继续在c o n d o r 中寻找其它的资源完成运行。 c o n d o r 中与资源和调度有关的一个重要部件是匹配器( m a t c h m a k e r ) ，它负责将任务 请求和周期性提交上来的资源状况作匹配，并通知匹配的双方进行谈判和协作。匹配器 做的匹配只是为相互匹配的任务和资源做一种“介绍”，而不管任务的执行。m a t c h m a k e r 实现了不依赖全局资源命名，周期性重新匹配任务，若发现更好的资源，则正在进行的 1 0 山东帅范大学硕l 学位论文 任务会被迁移到新的机器上执行。c o n d o r 中使用c l a s sa d 语言描述任务的需求和资源 的属性，其