一种基于Chord的网格资源定位方法

 胡志刚, 谭树斐, 桂卫华, 陈建二, 陈松乔

(中南大学 信息科学与工程学院, 湖南 长沙, 410083)

摘要: 在Chord定位方法的基础上, 针对网格资源的特点, 提出数字型属性范围查询以及多维查询的思想, 并基于这些思想提出在网格环境下的资源定位方法—单属性支配的多维查询方法。 模拟实验结果表明,该方法具有良好的可扩展性。
关键词: 网格; 资源定位; Chord; 多维查询; 范围查询
中图分类号: TP302.1 文献标识码: A 文章编号: 1672-7207(2005)03-0465-05

A resource-location method of grid based on chord

HU Zhi-gang, TAN Shu-fei, GUI Wei-hua, CHEN Jian-er, CHEN Song-qiao

(School of Information Science and Engineering, Central South University, Changsha 410083, China)

Abstract: Aimed at the characteristics of grid resources, the ideas of range queries of numerical attributes and multidimensional queries based on the location method of Chord. Furthermore, a single attribute dominated query method was also provided on the basis of these ideas. And simulative experimental results indicate that this method has a good scalability.
Key words: grid; resource location; Chord; multidimensional queries; range queries 

网格技术近年来已成为分布式系统领域中的一个研究热点^[1-4], 其中,资源定位是网格计算中最重要的问题之一, 它的性能直接影响到计算环境中资源协同工作的效率。 当前, 关于资源定位方法有许多, 如Globus计算网格中的MDS实现了基于LDAP的树状元数据目录服务^[5]; Condor的 MatchMaker^[6]实现了不依赖全局资源而依靠属性匹配的集中式资源共享系统命名; Web服务中的UDDI实现了集中式服务实体的统一描述、 注册和查找^{[7, 8]}。 这些资源定位的方法都基于集中式或层次式, 而在网格环境下需要的是一种不依赖于集中控制的、 而是分布式的资源定位方法。 一些基于DHTs的P2P系统(如Chord, CAN, Pastry等^[9-13])的资源定位策略具有分布式、 可扩展等特点。 这些策略对于研究在网格环境下的资源定位方法具有借鉴意义, 但是,由于网格资源的类型以及属性的多样性, 不能将P2P系统中基于关键字的资源定位方法简单地应用于网格。 为此, 本文作者在P2P系统——Chord的基础上提出了一种适合网格计算环境的资源定位方法。

1 Chord资源定位机制

1.1 基于位置无关的标识符分配与关键字存储

Chord采用相容散列函数(如SHA-1)为每个节点和关键字分配m位字节的标识(identifi-er)^{[8, 9]}, 节点的标识符可以通过散列节点的IP地址产生, 而关键字的标识符可以直接散列此关键字。 例如IP 地址为192.168.0.49 的节点经过SHA-1 散列之后得到的标识符为30, 而关键字“Windows”散列之后的关键字为95。 标识符长度m必须足够长, 以保证2个节点或者2个关键字散列到同一个标识符上的概率小到可以忽略不计。

在相容散列中, 每个关键字都保存在它的后继节点中, 后继节点是节点标识符大于或等于关键字k标识符的第1个节点, 可表示为successor(k)。 如果标识采用m位二进制数表示, 并且将从0 到2m- 1的数排列成一个圆圈, 那么,successor(k) 就是从k开始沿顺时针方向距离最近的节点。

相容散列具有几个特点, 散列函数可以使负载平衡, 即所有的节点都可以接收到基本相同数量的关键字; 当节点加入或者离开系统时,对网络带来的影响可以达到最小。
1.2 Chord 查找方式

在Chord中, 每个Chord节点维护着其他节点的少量路由信息, 节点并不需要知道所有其他节点的信息。 假设m为关键字和节点标识符的位数, 每个节点只需维护一张由m个表项组成的路由表, 也称为指针表。 指针表中各表项含义如表1所示。

表 1   Chord 指针表
Table 1   Chord finger table

Finger[i]为节点n的第i个指针, S[i]为指向标识符环中的下一节点的指针, 其中S[i]=successor(Finger[i])。

Chord 查找算法如下:

a. 节点n接收到关键字为k的查询请求;

b. 搜索指针表, 寻找等于k的Finger[i]。 如果有, 将S[j](Finger[j]=k)返回给节点n。 如果没有, 在Finger[i]中选出最接近k的Finger[r], 并将查询请求路由转发给S[r];

c. 重复上一步。

2 基于Chord的网格资源定位方法

Chord系统可以准确地定位关键字所在位置, 然而,这种分布式查找能力对于网格环境下的资源定位还不够。 因为在网格环境下的资源通常是多属性描述的, 因此,需要基于多属性来注册与查询。

例如, 一个资源提供者用以下语句来注册资源:

Register

Name=Tsf&&URL=Gram://tsf.csu.edu.cn:8000&&OS-type=Windows&&CPU-speed=833 MHz&&memory-size=512 MB

一个资源的使用者用以下语句来查询所需要的资源:

Search

OS-type=Windows && 800 MHz〈=CPU-speed〈=1000 MHz && memory-size >=512 MB

从资源注册和用户查询语句中可以发现在网格环境下资源定位的主要特点:

a. 由于资源的多属性, 资源的查找必定也是多属性支配, 而不是由单属性甚至只是单关键字决定。 这一点与Chord系统中基于关键字的查找有很大差异, 在网格环境下资源定位需要多维查询方法。

b. 观察单个属性的查询条件, 可以发现按资源属性值的类型可将资源属性大致分为字符型属性与数字型属性2种。 如‘OS-type’, ‘URL’, ‘Name’ 都是字符型属性, 而且属性值是离散的; 而‘CPU-speed’和‘memory-size’属于数字型属性, 它们的属性值是连续的, 且在给出查询条件时, 通常给出的是一个数值范围, 而不是单个查询关键字。 因此, 对于数字型属性不能再采用基于关键字的查询方法, 而需要一个范围查询的方法。

因此, 需要研究适用于网格环境、 能够满足范围查询和多维查询要求的资源定位方法。
2.1 基于Chord的范围查询方法

在网格系统中, 依照属性值的类型可将资源的属性分为字符型属性和数字型属性2种。 对于字符型属性, 可以沿用Chord的基于关键字查询方法, 即仍采用Chord中的散列函数(SHA-1)为属性值分配m位的标识符; 对于数字型属性, 则通过重新定义散列函数来分配标识符。

假设数字型属性a的数值范围为 [u_max, u_min], 可构造如下的散列函数:

H(u)=(u-u_min) × (2m-1)/(u_max-u_min),
u∈[u_max, u_min]。

对于每个属性值u, 散列函数都分配一个m位的标识符H(u), 并且当u_i〈u_j时则H(u_i)〈H(u_j),即属性值越小,分配到的标识符也越小; 反之, 属性值越大,分配的标识符也越大。 由于u∈[u_max, u_min], 由以上结论可以得到H(u_max)≤H(u)≤H(u_min)。 类似Chord, 为属性值u分配标识符后, 将属性值u存储到successor(H(u))中, 即标识符大于或等于H(u)的第一个节点中。 已知H(u_max)≤H(u)≤H(u_min), 而successor(H(u))≥H(u), 可推出successor(H(u_max))≤successor(H(u))≤successor(H(u_min))。 假设N为资源请求的发起节点, N_x为资源请求路由转发途经节点, W是符合范围查询条件的网格资源表,基于以上结论, 可得到数字型属性范围查询算法, 见如下的算法1。

算法1—— 数字型属性范围查询算法如下:

a. 将节点N接到属性值为u∈[x, y]的范围查询请求, 初始化资源集合W。

b. 将查询请求路由转发到节点N_x上。 其中N_x=Successor(H(x)), 搜索N_x中的资源注册信息, 将属性a满足范围条件的资源添加到W中。

c. 将查询请求转发给下一个后继节点N_i, 同样将满足范围条件的资源添加到W中。 判断N_i是否为N_y, 若是, 将查询结果的资源表W返回给请求端节点N; 若不是, 则执行下一步。

d. 重复步骤c.。

[举例] 如图1所示, N₁₅接到范围查询请求, 查询关键字范围为1~110的资源。 首先, 依照Chord单关键字的查找方法找到关键字K₁所在的节点N₁, 然后, 以N₁为范围查询的起始节点, 将查询请求依次转发给后继节点, 在各节点中搜索资源注册信息, 将满足关键字范围1~110的资源添加到资源集合W中, 直到查询请求到达关键字K₁₁₀所在的节点N₁₂₁, 此时, 停止查询并将查询结果(资源集合W)返回给请求节点N₁₅。

图 1   范围查询算法实例
Fig. 1   Example of range queries algorithm  

该查找算法的时间复杂度为O(lgN+K), 其中O(lgN)为查询请求路由转发到节点N_x上所需时间, 而O(K)是查询请求从查询起始节点N_x到查询终止节点N_y中途所花费的时间, 其中K为N_x到N_y之间的节点数, 在图2中K为途径N₁与N₁₂₁之间的节点个数。
2.2 单属性支配的多维查询方法

在网格中的资源是多属性注册和查询, 所以网格资源定位需要多维查询方法。 假设网格资源的属性集为{a₁,a₂,a₃,…,a_M}, 对应的属性值集合为{u₁,u₂,u₃,…,u_M}, M为固定值。 在网格中资源信息用数对〈u_i, r_x〉描述, r_x为资源的入口地址信息。 在资源注册时将资源信息提交给信息节点, 由于资源的各个属性值在散列时都对应一个信息节点N_i, 所以资源的注册信息分布存储在M个信息节点位置, 即网格中有M个节点位置存储该注册资源的信息。 信息节点根据资源属性集对注册的资源信息进行分类, 根据a_i将〈u_i, r_x〉组织在一起, 采用这种分类索引方法可以提高查询效率。

假设用户提交的查询请求如下:

Search

OS-type=Windows && 800 MHz〈=CPU-speed〈=1000 MHz && memory-size >=512 MB

这是一个3维查询条件, 由3个子条件组合而成。 要满足查询, 首先要满足子查询。 假设W为满足3维查询条件的资源集合, W_i是满足各子条件的资源集合, 可得W_i的交集: W=∩W_i(1≤i≤3)。 最直观的方法是分别进行3次子查询, 求得W₁, W₂和W₃, 然后求交集得到满足3维查询条件的资源集合W。 但是这种方法在子查询的过程中没有充分利用资源中除指定属性(如CPU-speed)外的其他属性信息, 并且子查询需要进行M次迭代才能完成, 大大增加了网格的通信量。 基于以上问题, 作者提出了单属性支配的多维查询方法。

单属性支配的多维查询方法的主要思路是: 在资源的查询请求中选取属性a_i作为查询的支配属性, 在a_i的单属性查询过程中, 达到多维属性查询。 该方法充分利用在信息节点中资源的注册信息, 不需要对查询条件的各维进行单独的迭代查询, 显著简化了查询过程。

假设算法选取属性a_i作为查询过程中的支配属性, S是除属性a_i外其他子查询条件的集合, W是符合多维查询条件的网格资源表。

算法2——单属性支配的多维查询算法如下:

a. 网格节点N接到支配属性a_i的查询范围是[x, y]的多维查询请求, 初始化W。

b. 将查询请求路由转发到节点N_x, 其中N_x=Successor(H(x)), 搜索N_x的资源注册信息, 将符合多维查询条件的资源添加到W。

c. 将查询请求转发给下一个后继节点N_i, 同样将满足多维查询条件的资源添加到W中。 判断N_i是否为N_y, 若是, 将查询结果(资源表W)返回给请求端节点N; 若不是, 则执行下一步。

d. 重复步骤c.。

该算法实例如图2所示, 图中a₁为多维查询的支配属性, R是a₁的查询范围, R=[30,80], S是除属性a₁外其他子查询条件的集合, W用于记录满足多维查询条件的网格资源。 当N₁₅接到多维查询请求时, 首先将请求路由转发到节点N₃₂, 并搜索该节点中满足S的网格资源, 将结果记录到W中; 然后,将请求依次转发给后继节点, 重复相同操作, 直到请求到达关键字K₈₀的存储位置N₈₉, 结束查询, 将结果返回。

图 2   多维查询算法实例
Fig. 2   Example of multidimensional queries
algorithm  

该算法的时间复杂度与在查询中选取的支配属性a_i有关。 这里,定义参数。 其中: S_i表示属性a_i的标识符区间[H(u_ix),H(u_iy)]占整个系统命名空间的比例, 称为属性的查询范围选择度; K_i=S_i×N, K_i表示属性a_i在范围查询过程中路由转发的次数。 因此, 以属性a_i作为支配属性的多维查询算法的时间复杂度为O(lgN+K_i)。 假设S_min为选择度S_i的最小值, 则其最小的时间复杂度为O(lgN+N×S_min)。

3 模拟实验与分析

借助仿真工具SimGrid^{[14, 15]} 对算法2进行计算机仿真实验, 网络拓扑结构为随机产生的网络拓扑, 通过实验对单属性支配的多维查询方法给出性能进行分析。 由于难以估计在查询过程中的网络延迟, 可将在查询路径上经过的节点数(跳转数)作为资源定位性能的量化标准, 当最小查询范围选择度S_min=1%时, 性能曲线如图3所示。 从图3可以看出,随着网格规模的扩大, 查询的平均跳转数与节点数之间的关系大致呈对数关系, 表明该方法具有较好的可扩展性。

图 3   S_min为1%时节点数变化对平均跳转数的影响
Fig. 3   Influence of changes in node numbers on
average hops with S_min of 1%  

S_min直接影响资源的多维查询性能, 为此, 研究不同的S_min对网格的资源定位性能的影响。 假设固定网格节点数为64, 资源属性集大小为1, 实验结果如图4所示。 结果表明, 在固定网格规模的条件下, S_min的增大时,其对资源定位性能的影响是趋于线性的。

图 4   S_min的变化对平均跳转数的影响
Fig. 4   Influence of changes in S_min on
average hops

4 结 语

资源定位是网格计算中需要解决的核心问题之一, 通过分析网格环境下资源多属性注册与查询的特点, 提出了范围查询以及多维查询的网格的资源定位方法。 模拟实验结果表明, 该方法可有效地解决网格计算中的资源定位和资源发现问题, 且具有良好的可扩展性。

参考文献:

[1]Foster I, Kesselman C. The grid: Blueprint for a future computing infrastructure [M]. San Francisco: Morgan Kaufmann Publishers, 1999.
[2]Foster I, Kesselman C. The physiology of the grid: An open grid services architecture for distributed systems integration[EB/OL]. http://www.globus.org/research/papers/ogsa.pdf, 2002.
[3]Tuecke S, Foster I. Open grid services infrastructure (OGSI), Version 1.0[EB/OL].http://www-unix. globus.org/toolkit, 2003.
[4]Foster I, Kesselman C, Tucke S. The anatomy of the grid: Enabling scalable virtual organizations [J]. International Journal of Supercomputer Applications, 2001, 15(3): 200-222.
[5]Czajkowski K, Fitzgerald S, Foster I. Grid information services for distributed resource sharing[A]. Thomas D. Proceeding of the 10th IEEE HPDC[C]. Washington, DC: IEEE Computer Society Press, 2001. 181-194.
[6]Raman R, Livny M, Solomon M. Matchmaking: distrbuted resource management for high throughput computing [A]. Schaeffer J. Proceeding of the 7th IEEE HPDC[C]. Washington, DC: IEEE Computer Society Press, 1998. 140-146.
[7]Rompothong P, Senivongse T. A query federation of UDDI registries[A]. Aleksy M, Coffey T. Proceedings of the 1st international symposium on information and communication technologies[C].Dublin: Trinity College Dublin Press, 2003. 561-566.
[8]Stoica I, Morris R, Karger D. Chord: a scalable peer-to-peer lookup service for internet applications[A]. Proceeding of ACM SIGCOMM 2001[C]. New York: ACM Press, 2001. 149-160.
[9]Stoica I, Morris R, Liben-nowell D. Chord: a scalable peer-to-peer lookup protocol for internet applications[A]. Ellen W Z. IEEE/ACM Transactions on Networking[C]. New York: ACM Press, 2003. 17-32.
[10]Singh M G. Routing networks for distributed hash tables[A]. Anon. Proceedings of the Twenty-Second Annual Symposium on Principles of Distributed Computing[C].New York: ACM Press,2003. 133-142.
[11]Loguinov D, Kumar A, Rai V. Graph-theoretic analysis of structured peer-to-peer systems: routing distances and fault resilience[A]. Anon. Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications[C].New York: ACM Press, 2003. 395-406.
[12]Ratnasamy S, Francis P, Handley M. A scalable content-addressable network[A]. Anon. Proceedings of ACM SIGCOMM2001[C].New York: ACM Press, 2001. 161-172.
[13]Rowstron A , Druschel P. Pastry: scalable, decentralized object location and routing for large-scale peer-to-peer systems[A]. IFIP/ ACM International Conference on Distributed Systems Platforms[C]. Heidelberg, 2001.
[14]Legrand A, Marchal L, Casanova H. Scheduling distributed applications: the Simgrid simulation framework[A]. Lee S, Sekiguchi M S. Proceedings of the 3th International Symposium on Cluster Computing and the Grid[C]. Washington, DC: IEEE Computer Society Press, 2003. 138.
[15]Casanova H. Simgrid: A toolkit for the simulation of application scheduling[A]. Craig A L, Paul P. Proceedings of the 1st IEEE/ACM International Symposium on Cluster Computing and the Grid[C]. Brisbane: IEEE Computer Society Press, 2001. 430-437.

收稿日期:2004 -09 -20

基金项目:国家自然科学基金重点项目(60433020); 博士后基金资助项目(2004)

作者简介:胡志刚(1963-), 男, 山西孝义人, 教授, 从事操作系统和并行计算研究

论文联系人: 胡志刚, 男, 教授; 电话: 0731-8836300; E-mail: zghu@mail.csu.edu.cn