《对等网络中基于dht的web服务发现》由会员分享，可在线阅读，更多相关《对等网络中基于dht的web服务发现（3页珍藏版）》请在金锄头文库上搜索。
1、计算机科学2 0 0 4 V o I 3 1 1 0 ( 增刊) 对等网络中基于D H T 的w e b 服务发现 W e bS e r v 证e sD k c o v e r yi I lP 2 PN e t w o r kB a s e do nD H T 辛颖于守健乐嘉锦 ( 东华大学信息科学与技术学院上海2 0 0 0 5 1 ) A b s t r a c tW e bS e r V i c e sa r et h en e wp a r a d i g mf o rd i s t r i b u t e dc o m p u t i “g ，a n de n a b l em o
2、r ed e v e l o p m e n to le - b u s l n e s s T h e r ee x 扭tl I l a n ys i m 丑a rc h a r a c t e s t i c sb e t W e e nW e bS e r 啸c e sa n dP 2 P I nP 2 P 曲v i r o n f n e n t ，i tc a nt a k ef u l i a d V a n t 3 弘o fW e bS e r v i c e s B u t 垴P 2 Pe n v i r o n r 耻n tt h e r ei sn op e e rw h
3、i c hp l a y st h er 0 1 eo fr e g i 8 t r y T h i 3m a k e 5 i td i m c u l tt od 诂c o v e rW e bS e r v l c e 5i nP 2 Pe n v i r o n m e n t S ow er n a k eu s eo fD H T w h I c hc a nl o c a t ed a t aw e l li n l a g ed 培t r i b u t e d8 y s t e mt oc o m p l e t et h ed i s c o v e r yo fW e bS
4、 e r v 记e sT l l i sm e c h a n i s mo fW “S e r v i c e sd 诗c o v e r yc a n s c a I ew e I Ia n db ea p p l i e di nl a g e ，d y n a m i cd i 8 t r I b u t e d8 y s t e m K e y 咖r d sW e bS e r “c e s ，P Z P ，D H T ，C h o r d 1 引言 w e b 服务是一种崭新的分布式计算，它的出现 大大推进了电子商务应用的发展。w e b 服务是一种 面向服务的体系结构，而面向服务
5、的体系结构中有 三个角色和三个操作。三个角色分别是服务的提供 者、服务的请求者和注册中心；三个操作分别为发 布、绑定和发现。服务提供者将服务发布到注册中心 上，服务请求者通过在注册中心的查我来获得w e b 服务的调用信息，最终服务请求者与服务提供者绑 定，实现w e b 服务的调用。由面向服务的体系架构 可以看出注册中心起了极其重要的作用，良好的发 现机制直接影响到了w e b 服务的利用率。 P 2 P 是一种网络环境下的分布式架构，资源分 布于网络中的各个节点之上节点既是资源提供者 也是资源请求者，节点之间的交互实现了资源的共 享。P 2 P 和面向服务的体系结构的不同之处在于它 没有定
6、义明确的角色关系。每一个节点或对等体都 可以充当服务的请求者、提供者或服务发现的代理。 P 2 P 环境下可以充分利用每个节点上的资源，它比 传统的面向服务的体系结构更能适合w e b 服务的 发展。 综上，P 2 P 与w e b 服务的结合将是一种理想的 解决方案。但在P 2 P 环境下，不再存在服务注册中 心这个角色，因而需要一种w e b 服务发现机制，该 发现机制必须能和分布式环境很好地结合。对此，我 们想到了D H T ( D i s t r i b u t e dH a s hT a b l e ) 。D H T 有 诸多良好的特性，在大型动态的分布式系统中提供 高效的数据定位功
7、能。我们提出建立基于D H T 的 分布式目录系统，来实现P z P 环境中的w e b 服务 发现。该目录系统避免了集中式设计的安全隐患问 3 8 题，并且可扩展性强，在大型的分布式环境下仍保持 了较小的查询代价和维护开销。 2C h o r d 协议 c h o r d 协议是D H T 的一种实现。D H T 利用分 布式的哈希表来定位数据在P 2 P 中的位置。D H T 没有集中式的不足，也不像广播式系统那样可扩展 性差，它可以在大型的、动态的分布式系统中提供有 效的数据定位功能。对于包含”个节点的系统， D H T 用于数据定位的消息传递复杂度为O ( 1 0 9 ) 1 。 2
8、1c h o r d 标识环 c h 。r d 有环形拓扑结构，环上的所有节点和关 键字有m 位的标识符，标识符是通过哈希关键字字 符串和节点的I P 地址而得到的。节点和关键字的标 识符按照太小和一定的方向安排于标识环上，那么 环上有。到2 ”一1 个不同的标识符。关键字被分配 到它的后继节点( s u c c e s s o r ) ，后继节点是在环上按 一定方向紧跟着关键字或与关键字位置相等的节 点。如图1 。按顺时针方向，m 一3 ，标识环上有。到7 个标识符，标识符为6 的关键宇，节点7 是它的后继 节点。 2 2c h o r d 查找方式 C h o r d 是一个分布式查找协议
9、，仅支持一个查 询操作；定位某个关键字的后继节点。 在环上的每个节点只知道自己的后继节点，就 可以查询出任意关键字的后继节点，但可能效率不 高。因而每个C h o r d 节点维护一张路由表，该路由 表包含m 个标识符的后继节点信息，c h o r d 通过这 种方式加快查询。 节点n 的路由表的第i ( 1 摧：m ) 项内容记录 图lc h o r d 的标识环 了”后第2 i 一1 个标识符的后继节点，该标识符的 计算式为( ( ”+ 2 i 1 ) m o d2 m ) 取2 m 的模是为了保 证计算得到的标识符的值在。到2 “一1 的范围内。 可以看出，路由表的第一项内容记录了标识符
10、( ”+ 1 ) 的后继节点，( n + 1 ) 的后继节点等于节点n 的后 继节点。因此节点的路由表包含自己的后继节点信 息，可以确保查询得到正确结果，且路由表的附加信 息可以减少焘询传递的次数。如图1 ，节点5 的路由 表中，第三项标识符( 5 + 2 2 ) m o d2 3 = 1 ，l 的后继节 点指向N 1 。 下面介绍c h o r d 根据路由表查询关键字后继 节点的具体算法。定义标识符的前继节点( p r e d e c e s s o r ) 是在标识环上反方向离标识符最近的节点。那 么在标识环上关键字前继节点的后继节点，等于该 关键字的后继节点。利用这个特点c h o r
11、 d 的查找算 法是先找关键字的前继节点，然后知关键字的后继 节点具体算法如下： ( 1 ) 如果k e y ( n ，n s u c c e s s o r ) 那么n 是k e y 的前继节点，n s u c c e s s o r 是要找的后继节点，跳至 ( 3 ) ； ( 2 ) 否则在n 的路由表中查找在k e y 之前且离 k e y 最近的节点n ，n = n ；跳至( 1 ) ； ( 3 ) 返回n s u c c e s s o r 。 例如，节点1 上开始找关键字6 的后继节点，6 不属于( 1 ，5 ) ，节点1 的路由表中N 5 在关键字6 之 前且与之最近，查询转至N
12、 5 ，在节点5 上根据路由 表知6 ( 5 ，7 ) ，于是返回节点5 的后继节点7 ，7 是 6 的后继节点。 5w e b 服务的发现 5 1 基于D H T 的目录系统 在P 2 P 环境下，目录系统可以是集中式存放于 网络中的某一个节点。或者是把完整的目录信息复 制到所有的节点上。这两种目录比较简单，但当网络 迅速增长时，各自的弊端较明显。 针对以上两种目录系统设计的不足，我们利用 c h o r d 技术建立完全分布式的目录机制。设计的主 要思路是：每个节点都有c h o r d 标识符，节点为发 布的w e b 服务建立目录信息，目录信息再根据关键 字被分配到后继节点上。这样一个
13、w e b 服务的发现 过程分为两个阶段：首先根据c h o r d 定位相应目录 信息存放的后继节点，然后到该节点上根据目录查 询w e b 服务。 基于D H T 目录系统的优势：( 1 ) 目录存放的后 继节点的确定意味着相关w e b 服务信息的确定。 c h 。r d 查找后继节点的复杂度为O ( 1 0 9n ) ，因而 w e b 服务查询的复杂度也为O ( 1 。gn ) ；( 2 ) 目录中 关键宇选定有很大的灵活性，c h o r d 关键字可以是 任意字符串，根据具体应用确定目录关键宇，满足不 同关键字的查询这使我们的目录系统有较好的可 扩展性和实用性。( 3 ) 目录的
14、分配依赖于c h o r d 协 议，C h o r d 一定程度上解决了网络中负载均衡的问 题。 定义目录c 有这样的结构C 一 ( K ，S ，N ) ) 。K 是从w e b 服务原来的描述中抽取出的关键字，每个 w e b 服务有一个关键字l s 是对关键字K 的摘要信 息；N 是关键字为K 的w e b 服务的发布节点。比 如，对于某个买书的w e b 服务B u y B 0 0 k ，我们可以 从w s D L 中提取w e b 服务的名称B u y B 。o k 作为关 键宇K ，提取B u y B o o k 提供的操作B u y ( I s B N ) 作为 摘要信息s ，B
15、 u y B o o k 发布的节点为N 。目录提供的 查询功能是查找是否有名字为B u y B o o k 且含操作 B u y ( I s B N ) 的w e b 服务，如果有这样的w e b 服务 则返回其发布的节点N 。 5 2w 曲服务韵查找过程 根据3 1 节的目录系统的结构，某个节点需要 请求w e b 服务时，其查找过程描述如下： ( 1 ) 对等网络中某个节点请求w e b 服务，该 w e b 服务包含关键字K ； ( 2 ) 查询c h o r d 的路由表是否能得到关键字K 的后继节点能定位K 的后继节点则转( 3 ) ；如果不 能，则根据路由表找到离K 最近的节点，
16、将查询转 至该节点，重复( 2 ) 的过程； ( 3 ) 查询提交至关键字K 的后继节点，后继节 点存储了相关的目录信息，根据目录的查询功能，找 出符合请求的w e b 服务以及该w e b 服务提供者的 位置； ( 4 ) 获取w e b 服务的技术文档，服务的请求者 与提供者绑定，进行w e b 服务的调用。 5 3 目录信息的维护 在系统变更的情况下C h o r d 有自动调整路由 3 9 表的能力，可以保证负责关键字的节点被找到。因而 我们不讨论路由信息的调整，主要讨论节点加入或 离开时，目录信息的维护。当网络中有节点加入、离 开时，不需要对所有节点上的目录信息进行更改，仅 对部分节点上的目录进行移动操作，整个目录系统 有较小的维护开销。 新节点的加入，目录本身的信息不需要修改但 一些目录需要从原来的节点移动到新的节点之上， 因为部分关键宇的后继节点变化了。另外，新节点创 建的目录也需要根据c h o r d 协议注入系统之中。假 设节点N m 要加入系统，首先针对本
