（教育技术学专业论文）基于chord协议的xml文档查询机制研究与实现.pdf

天津师范大学硕士学位论文 摘要 在如今的p 2 p 对等网络环境中。快速并且准确地确定资源的位置是一个至 关重要的问题，其中基于d h t ( d i s t r i b u t e dh a s ht a b l e ) 资源定位及查找算法是 目前比较流行的算法之一。与此同时x m l 数据库技术迅速的成为i n t e r n e t 上用 于数据表示和数据交换的标准。由于x m l 文档的大量出现，对于x m l 文档的 有效管理和查询受到了广泛研究人员的关注。 为此本文对基于c h o r d 协议的x m l 文档查询机制进行研究。文中介绍了对 等网络中具有代表性的c h o r d 路由算法，提出了基于此模型的x m l 文档查询机 制，并对其进行了具体的分析阐述与系统实现。 本文主要研究在p 2 p 网络中对x m l 数据文档的查询问题。现今在d h t 网 络环境中数据查询定位算法基本都是通过文件的文件名进行准确匹配查询的。本 文讨论的问题是在p 2 p 网络中实现处理x m l 数据和进行x p a t h 查询。每个单 独的p e e r 节点包含有一个完整的x m l 文档或者一个后继p e e r 节点的x m l 部 分，完全片段。这其中每个x m l 片段或者x m l 文档都是使用唯一的路径表达式 所标识，路径表达式是编码在分布式哈希表( d h t ) 5 b 。本文的框架结构不同于以 往基于内容的路由机制，而是通过查询来找到最为相关数据的p e e r 节点集。实 现了x m l 片段的存储，同时通过利用少量的保存在每个p e e r 节点上的路径表 达式信息来查询到相关的x m l 片段。 整个系统实现是以c h o r d 路由协议为p 2 p 网络结构的，主要设计分为三个 组成部分，分别是x m l 存储模块，查询处理模块和网络结构模块。在实现上采 取分层的策略，分为用户界面层，应用接口层，服务层，c h o r d 层，网络层。利 用j d o m 作为x m l 文档解析器使用j a v a 语言进行实现。最后本文对提出的方 法进行了相应的实验分析和评价。 关键词：p 2 p 网络c h o r d 协议x m l 查询x p a t h 天津师范大学硕士学位论文 a b s t r a c t a ni m p o r t a n tp r o b l e mt h a tc o n f r o n t sp e e r - t o - p e e rn e t w o r ki st h ee f f i c i e n t l o c a t i o no ft h en o d et h a ts t o r e sad e s i r e dd a t ai t e m t h er e s e a r c hf o c u s e so nt h ed h t ( d i s t r i b u t e dh a s ht a b l e ) ，b e c a u s ed h tl o o k u pa l g o r i t h m so f f e ras c a l a b l ea n d e f f i c i e n tr o u t i n ga n do b j e c tl o c a t i o np l a t f o r mf o rp e e r t o - p e e rn e t w o r k s a tt h e s a m et i m ex m ld a t a b a s et e c h n o l o g yi sa l s or a p i d l yb e c o m i n gt h ei n t e r n e tf o rd a t ao n e x p r e s sa n dd a t ae x c h a n g es t a n d a r d s x l v i ld o c u m e n t s a n df r a g m e n t sa p p e a r s u b s t a n t i a l ，x m ld o c u m e n t sa n dq u e r yt h ee f f e c t i v em a n a g e m e n to fs a i l l eh a v ea l s o b e e nw i d e s p r e a dc o n c e r n t ot h i se n dt h i sp a p e ro ft h ep r o t o c o lb a s e do nx m ld o c u m e n t sc h o r dq u e r y m e c h a n i s mf o rr e s e a r c h i n t r o d u c eo n eo ft h em a i nr e p r e s e n t a t i v e so ft h ec h o r d a l g o r i t h m ，b a s e do nt h i sm o d e lt h ex m l d o c u m e n tq u e r ym e c h a n i s m ，a n di t sa n a l y s i s o ft h es p e c i f i ci m p l e m e n t a t i o na n ds y s t e m w et a k eu pw i t ht h ep r o b l e mo fq u e r y i n gx m ld a t ao v e rap 2 pn e t w o r k i np 2 p n e t w o r k s ，t h ea l l o w e dk i n d so fq u e r i e sa r eu s u a l l ye x a c t - m a t c hq u e r i e so v e rf i l e n a n l e s w ed i s c u s st h ee x t e n s i o n sn e e d e dt od e a lw i t hx m ld a t aa n dx p a t hq u e r i e s a s i n g l ep e e rc a nh o l daw h o l ed o c u m e n to rap a r t i a l c o m p l e t ef r a g m e n to ft h el a t t e r e a c hx m l f r a g m e n t d o c u m e n ti si d e n t i f i e db yad i s t i n c tp a t he x p r e s s i o n , w h i c hi s e n c o d e di nad i s t r i b u t e dh a s ht a b l e o u rf r a m e w o r kd i f f e r s f r o mc o n t e n t - b a s e dr o u t i n g m e c h a n i s m s ，b i a s e dt o w a r d sf i n d i n gt h em o s tr e l e v a n tp e e r sh o l d i n gt h ed a t a w e p e r f o r mf r a g m e n t sp l a c e m e n ta n de n a b l ef r a g m e n t sl o o k u pb ys o l e l ye x p l o i t i n gf e w p a t he x p r e s s i o n ss t o r e do ne a c hp e e r r e a l i z et h ew h o l es y s t e mi sb a s e do nc h o r dr o u t i n gp r o t o c o lf o rt h ep 2 pn e t w o r k s t r u c t u r e ，d e s i g n e dm a i n l yd i v i d e di n t ot h r e ec o m p o n e n t s ，n a m e l ym e m o r ym o d u l e s a r ex m l ，q u e r yp r o c e s s i n gm o d u l ea n dt h en e t w o r ks t r u c t u r em o d u l e t a k e nu pa t t i e r e di m p l e m e n t a t i o ns t r a t e g y , d i v i d e di n t ou s e ri n t e r f a c el a y e r , a p p l i c a t i o ni n t e r f a c e l a y e r , s e r v i c el a y e r , c h o r dl a y e r ，n e t w o r kl a y e r a sx m l d o c u m e n t su s i n gj d o m p a r s e ri m p l e m e n t a t i o nu s i n gj a v al a n g u a g e f i n a l l yt h i sa r t i c l et ot h em e t h o dw h i c h p r o p o s e dh a sc a r r i e do n t h ec o r r e s p o n d i n ge x p e r i m e n ta n a l y s i sa n dt h ea p p r a i s a l k e yw o r d s ：p 2 p n e t w o r k sc h o r dp r o t o c o lx m l q u e r y i n g x p a t h i i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我 所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研 究成果，也不包含为获得苤鲞堑蕉盘堂或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签名： 缎日 学位论文版权使用授权书 本人完全了解天津师范大学有关保留、使用学位论文的规定，即：学校有权将学位论文 的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇 编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的论文在解密后应遵守此规定) 签名：鬟坌趁导师签名： 日期： 天津帅范人学坝i j 学位论义 1 1 背景和意义 第一章绪论 当前如g n u t e l l a 1 1 和k a z a a 2 】这类型的文件共享系统都是非结构化的系统， 主要依赖泛洪机制来进行基于准确关键字的搜索，在这些文件共享系统中不能保 证能够查询到所有用户所需要得到的结果。另一类系统是结构化的系统，是基于 内容路由算法进行寻址搜索的，其中主要是利用索引机制来进行查询。在这些索 引中，d h t 是最为广泛使用的一种路由算法，这是由于d h t 路由算法的优势在 于在降低了查询的时间复杂度同时提高了查询到有效结果的可能性同。在这种 x m l 轻量数据库的实际应用中，d h t 路出算法是在p 2 p 网络中数据管理的最基 础的索引结构。文章【4 】【5 】【6 】详细分析并讨论了在现有已经存在的研究模型中相 应地扩展方法。目前在整个因特网规模的情况下，关键字内容的查询方法都是用 一个包含倒排文件关系的索引来实现的1 4 1 。每个p e e r 节点仅仅包含有关系表的 部分信息而且扩展后d h t 路由协议可对相近的范围查询进行高效准确的定位p j 。 通过增加b + 树来扩充d h t 算法使其可以对范围查询的内容以元组的方式进行 表示嘲。在本文中，要集中解决的问题是在于一个以c h o r d 协议为基础的p 2 p 网络环境中对x p a t h 查询的问题。因为路径查询与以关键字( 或以范围) 为基 础的查询过程是不相同的。目前存在的所有d h t 路由协议的扩展中对于x p a t h 查询没有可完全直接适用的方法。 1 2 发展现状与趋势 在p 2 p 网络结构的系统中处理x m l 数据的关键问题在于如何有效的定位用 户所关心的数据。近年来的研究中已经有相应的机制用以快速的查找定位到用户 感兴趣的p e e r 节点并找出与其对应的x m l 相关数据信息。他们的过程是在每 个p e e r 节点上存放部分摘要或目录信息( 其中包括路径摘要，直方图，光晕滤 波器( b l o o m f i l t e r s ) 嗍和多级光晕滤波器( 。然而这些解决方案对于在p 2 p 网络 中p e e r 节点大量存在时和处理任意共享的x m l 文档时系统的可伸缩性上存在 天津师范大学硕士学位论文 定问题。此外这些数据索引信息( 包括本地的数据和临近p e e r 节点数据信息 的描述) 在网络环境进行经常改变的情况下是难以对他们更新的信息进行维护 的。对这一问题的研究目前有以下三种解决办法： 1 对x m l 文档进行分布式存储处理时严格限制其的最大深度吐 2 限制网络中的节点数量，例如认为存在一个固定的群组，这其中的p e e r 节点提供各自的共享数据同时在整个网络环境中自始至终的有效嘲； 3 选择一个“准零”的复制方法，例如当p e e r 节点仍然保有查询能力的条 件情况下取消复制每个p e e r 节点的完整目录信息。 在本文中将以假定3 作为研究思路进行设计，作用在一个大型的而且是动态 变化的p 2 p 网络环境中，p e e r 节点可以任意的加入和退出网络【1 l 【2 1 。 使用查询处理器来提高p 2 p 网络性能的研究是近几年内数据库领域高度关 注的课题。在网络中使用一个保存有局部信息的哈希函数来映射查询范围：这项 改进也减少了查询响应时间，因为近似的范围是非常容易哈希到相同p e e r 节点 上的。g e h r k e 等人关于在p 2 p 网络环境下相关的范围查询的研究中定义了名为 p - t r e e 的编址方式【6 l ，其采用一个分布式的b + 树进行编址，使得让每个p e e r 节点包含有树的一个子集和一些路由信息。可是当每个p e e r 能包含有至多一个 元组时p - t r e e 不能实现高效地可扩展性。在x p a t h p 2 p 中主要解决的是当每次 p e e r 节点包括多于一个x m l 片段时的般情况。此外复制的索引是由很少的 x p a t h 路径表达式组成的，这样处理的效果使得索引数据一般可小于整个p - t 怕e 的大小。x m l 文档的分布式存储技术在近几年也是对于数据库领域研究者高度 重视的研究方向。g e r t z 在研究中提出一个分段存储x m l 片段的方法，同时对 于一个虚拟x m l 存储库提出了一个分配模型【”】，然而这种方法是适合于一个静 态情况下。在这种情况下有一组固定的p e e r 节点，这些节点从来不离开这个网 络环境，当在如p 2 p 一样的动态环境下它将失去意义。x m l 文档的分布式查询 在s u c i u 研究中得以解决l 仞，但是查询到有效的结果都是数百组的位置。因此 对于在大型的动态p 2 p 环境中这个问题仍然未被解决。此时在【7 】中研究者提出 p 2 p 层次网络的拓扑结构，达到每个p e e r 节点包含有x m l 内容和关于临近节 点的统计信息。在【8 】中研究者在c h o r d 网络环境下使用x m i - 文档中的t a g 名称 作为哈希k e y 值来进行处理。然而这种方法的局限性在于大量x m l 文档可能会 2 天津师范大学硕士学位论文 产生相同的t a g 名称使得查询过程中有额外的开销处理要进行解决。文献吲【8 】 提及的两种方法在大量p e e r 节点存在时和高频繁地更新网络环境时都缺乏良好 的可伸缩性。类似于文献 8 】中的实现方法，x m l p e e r 是一个x m l 数据查询共 享系统。 1 3 本文研究的主要内容 给出定义存在一个描述x m l 文档或者它的一个片段x p a t h 表达式和一个 包含n 个p e e r 节点的集合，本文的目标是：将只分配到网络中的一个p e e r ! - _ ， 使得这个节点包含有与相对应的x m l 片段和这个x m l 片段相关的路径表达 式信息，本文的设计建立于目前p 2 p 技术的支持下。本文所做的贡献在于如下 几个方面： 1 在基于c h o r d 的网络环境中对于处理x m l 数据内容的一个框架结构，通 过每个p e e r 节点上的褶关路径表达式进行有效地存储和查询数据； 2 在不需要存储全部目录信息前提下对x m l 片段的查找； 3x p a t h p 2 p 的可扩展性和查询路由性能的实验评价。 本文所介绍的部分x m l 文件共享系统，是解决数据集成领域的一个新的体 系结构【1 0 1 ，但不只限于这一种方面应用 1 3 1 。本文将设计一个系统称作 x p a t h p 2 p ，它将实现使用x p a t h 来处理x m l 片段，通过各自x p a t h 表达式的 一个集合进行准确定位。本文提出的方法对于一个任意数量p e e r 节点的情况下 都是到目前为止的处理方法中较易于操作的。在此值得注意的地方是为了保证达 到最大的可伸缩性，本文没有对全部的目录信息进行复制操作，这和以往研究的 操作也是有所区别的。对于存储一个x m l 片段的p e e r 节点，它也将存储一个 很小的描述x p a t h 路径表达式的集合，包括自身描述的路径表达式，x m l 的子 片段的路径表达式和x m l 的父片段。如何标识这些关联的路径表达式的介绍在 本文第三章中做详细的阐述。本文使用了一个非常轻量级的索引机制，这样可以 使得在每个节点上保存的额外信息只有很少的字节。通过分析统计在一个包括 1 0 0 0 个x m l 片段( 从d b l p 中随机产生【研) 的网络中，这些x m l 片段的文件大小 在3 k b 2 m b 之间，与其关联的路径表达式的大小范围仅在1 0 0 b 4 k b 之间。 天津师范大学硕士学位论文 此外x p a t h p 2 p 限定了在运行过程中仅有很少的x m l 片段的副本存在。在 先前非结构化的网络环境中大量副本存在的情形是很容易出现的【1 1 1 2 1 ，由此产生 的后果就是使得整个的网络越来越趋向缓慢。目前存在的一个折中解决办法的系 统是带有p i e r d b 的g n u t e l l a ，但是其主要关注的是基于关键字的查询。本文认 为本系统可以解决x m l 文档数据的存储和多关键字搜索查询。 相信x p a t h p 2 p 在协调p e e rs c h e m a 和面对未知的全局s c h e m a 情形下有 着更为广泛的应用。因为当对于需要严格保密的情形下，一个完整的s c h e m a 会 有所缺失和部分保留，那么在每个p e e r 节点上仅有其它p e e r 节点的部分x m l 数据信息，而此时仍计划进行查询操作，那么x p a t h p 2 p 此时就可以满足用户 的要求得到所需的查询结果和对应的x m l 文档【14 】。 1 4 本文的组织结构 第一章详细的论述了相关主题的发展现状和背景；第二章从理论上介绍了在 x p a t h p 2 p 系统中的基础知识；第三章具体阐述了系统模型的设计以及操作方 法的可行性分析，描述了对于x p a t h 表达式查询的算法；第四章对x m l 文档查 询机制的系统设计进行了详实地描述；第五章对x m l 文档查询机制的系统实现 进行了论述并通过c h o r d 仿真模拟器对原型进行了具体的试验分析；第六章即 最后一章对本文进行了完整的总结并对以后的研究方向做了科学地展望。 4 天津师范大学硕士学位论文 第二章x m l 文档查询机制网络结构的研究 2 1p 2 p 技术概述 2 1 1p 2 p 的概念 p 2 p 即p e e r - t o p e e r ，称为对等计算或对等网络，是模仿人类社会 p e r s o n t o p e r s o n 的交流方式，也可以理解为伙伴对伙伴的意思。它是近几年兴 起的网络技术研究领域中的一个热点，改变了人们使用网络的方式。与c s 模 式不同的是，p 2 p 不存在专门的中央服务器，计算节点在功能上是对等的，既 充当客户机，享用其他节点提供的服务：又充当服务器，为其他节点提供服务， 允许计算节点之间的直接交流和协作，所以称为s e r v e n t 模式，s e r v e n t 一词是 由c l i e n t 和s e r v e r 构成的，代表既有客户机的功能，又能充当服务器的角色。 p 2 p 研究领域对p 2 p 没有一个统一的定义，常见的定义有以下几种： i b m 为p 2 p 下了如下定义：p 2 p 系统由若干互联协作的计算机构成，且至 少具有如下特性之一：系统依存于边缘化( 非中央式服务器) 设备的主动协作，每 个成员直接从其他成员而不是从服务器的参与中受益：系统中的成员同时扮演服 务器与客户端的角色：系统应用的用户能够意识到彼此地存在，构成一个虚拟的 或实际的群体。 s h i r k y 等认为，p 2 p 是利用位于i n t e m e t 边缘的存储空间、c p u 周期、数 据内容等有效( a v a i l a b i e ) 资源的类应用程序。由于在连接不稳定和i p 地址不 确定的环境下访问分布资源，p 2 p 节点必须独立于域名系统( d n s ) 并且要有足够 的自治能力。 m i l o j i o i c 等认为，p 2 p 是利用分布资源以分布式的方式执行关键功能的一类 应用程序或者系统。分布资源包括计算能力、数据内容、存储空间和网络带宽等， 关键功能包括分布式计算、数据内容共享、通讯协同和平台服务等。 s t e p h a n o s 等认为，p 2 p 是由节点自组织( s e l f - o r g a n i z a t i o n ) 互连而成的分 布式系统，节点互连的目的是共享资源，比如数据内容、c p u 周期、存储和带 宽等，能够适应节点的动态变化( 加入、离开或失败) ，同时维持可接受的连接性 天津师范大学硕士学位论文 和网络性能，不需要中介或者全局服务器的支持和授权。 2 1 2p 2 p 的特点 1 非中心化 网络中的资源和服务分散在所有结点上，信息的传输和服务的实现都直接在 结点之间进行，可以无需中间环节和服务器的介入，避免了可能的瓶颈。p 2 p 的非中心化基本特点，带来了其在可扩展性、健壮性等方面的优势。 2 可扩展性 在p 2 p 网络中，随着用户的加入，不仅服务的需求增加了，系统整体的资 源和服务能力也在同步地扩充，始终能较容易地满足用户的需要。整个体系是全 分布的，不存在瓶颈。理论上其可扩展性几乎可以认为是无限的。 3 健壮性 p 2 p 架构天生具有耐攻击、高容错的优点。由于服务是分散在各个结点之 间进行的，部分结点或网络遭到破坏对其它部分的影响很小。p 2 p 网络一般在 部分结点失效时能够自动调整整体拓扑，保持其它结点的连通性。p 2 p 网络还 能够根据网络带宽、结点数、负载等变化不断地做自适应式的调整。 4 高性能价格比 性能优势是p 2 p 被广泛关注的一个重要原因。随着硬件技术的发展，个人 计算机的计算和存储能力以及网络带宽等性能依照摩尔定理高速增长。采用p 2 p 架构可以有效地利用互联网中散布的大量普通结点，将计算任务或存储资料分布 到所有结点上。利用其中闲置的计算能力或存储空间，达到高性能计算和海量存 储的目的。通过利用网络中的大量空闲资源，可以用更低的成本提供更高的计算 和存储能力。 5 隐私保护 在p 2 p 网络中，由于信息的传输分散在各节点之间进行而无需经过某个集 中环节，用户的隐私信息被窃听和泄漏的可能性大大缩小。此外，目前解决 i n t e r n e t 隐私问题主要采用中继转发的技术方法，从而将通信的参与者隐藏在众 多的网络实体之中。在传统的一些匿名通信系统中，实现这一机制依赖于某些中 继服务器节点。而在p 2 p 中，所有参与者都可以提供中继转发的功能，因而大 6 天津师范大学硕士学位论文 大提高了匿名通讯的灵活性和可靠性，能够为用户提供更好的隐私保护。 6 负载均衡 p 2 p 网络环境下由于每个节点既是服务器又是客户，减少了对传统 c l i e n t s e r v e r ( 客户，服务器) 结构服务器计算能力、存储能力的要求，同时因为 资源分布在多个节点，更好的实现了整个网络的负载均衡。 2 1 3p 2 p 主要应用 p 2 p 技术具有广泛的发展前景，目前主要有以下几个方面的应用： 1 信息资源共享 信息资源共享是p 2 p 技术产生的主要目的和根本动力，p 2 p 技术的出现改 变了传统共享信息的方式，无需再通过w e b 服务器，用户可以直接从任意一台 计算机上下载信息，实现了资源的全面共享，避免了w e b 服务器的瓶颈问题。 采用p 2 p 的方式共享信息资源，可以充分的利用网络带宽，提高共享效率，目 前流行的p 2 p 文件共享系统有g n u t e l l a 、f a s t t r a c k 、f r e e n e t 、k a z a a 、b i t t o r r e n t 在占 宇o 2 对等计算 对等计算是p 2 p 技术的一个重要应用，目的是共享网络上数目庞大的计算 机暂时不用的c p u 资源，将这些资源积累起来，用以完成以往需要超级计算机 来完成的任务。在对等计算中，任务分割成许多独立的单元，分配给网络中的计 算机进行独立计算，计算结束后返回结果，领取新的任务再开始新的计算。任何 需要处理大量数据的行业都可以通过对等计算大大降低计算成本，如天气预报、 动画制作、基因组的研究等。 3 实时通信 实时通信是目前互联网上最流行、使用最广泛的应用，它为用户之间的实时 交流提供了虚拟平台，目前著名的实时通信系统包括m s n ，i c q ，o i c q 等，尽 管目前的实时通信技术都存在中央服务器，但中央服务器仅用来控制用户的身份 认证用于对等网络的分布式哈希查找系统 除了上面介绍的几种主要应用外，随着研究的深入，p 2 p 技术将快速发展， 在更多的领域具有广泛的应用。 7 天津师范大学硕士学位论文 2 1 4p 2 p 的分类 1 集中式p 2 p 系统 集中式p 2 p 系统以n a p s t e r 、g n u t e l l a 和f r e e n e t 为代表，采取比较直观的 方式实现系统的分布式存储、分布式管理和自组织的文件存储系统。 集中式p 2 p 模式由一个中心服务器来负责记录共享信息以及反馈对这些信 息的查询：每一个对等实体要对它所需共享的信息以及进行的通信负责，根据需 要下载它所需要的其他对等实体上的信息。中心服务器上只保留索引信息，此外 服务器与对等实体以及对等实体之间都具有交互能力。 集中目录式p 2 p 模型还存在很多问题，主要表现在中央服务器的瘫痪容易 导致整个网络的崩溃，可靠性和安全性较低：随着网络规模的扩大，中央目录服 务器维护和更新的费用将急剧增加，所需成本过高：中央服务器的存在引起共享 资源在版权问题上的纠纷。 集中式p 2 p 对小型网络而言在管理和控制方面占有一定的优势，但对大型 网络并不适合。 2 非结构化p 2 p 系统 非结构化的对等网络系统采用完全分布式的拓扑结构，之所以称其为“无结 构 ，是和下一节将要介绍的结构化对等网络相对的。无结构对等网络中每个节 点之间是比较松散的关系，节点的加入和离开仅需遵循一些简单的规则。无结构 对等网络中每个节点保存各自共享的文档，由于不再存在中央目录服务器，每个 节点对本地保存的文档进行索引，并转发或应答其他节点的搜索请求。 在无结构对等网络中，资源查找最基本的方式是泛洪( f l o o d i n g ) 或类似泛洪 的盲目搜索。每个节点都将接到的搜索请求转发给所有的邻居节点，并由邻居节 点进一步转发给更多的邻居节点，直至找到期望的文档或者达到系统允许的最大 搜索跳数后搜索失败。如果成功找到所需的文档，那么搜索请求的发起节点直接 从期望文档的保存节点那里下载所需文档。 由于没有确定拓扑结构的支持，非结构化网络无法保证资源发现的效率。即 使需要查找的目标结点存在，发现也有可能失败。由于采用t t l 、f l o o d i n g 和 随机转发机制，因此路由直径不可控，可扩展性较差。从而发现的准确性和可扩 展性是非结构化网络面临的两个重要问题。目前对此类结构的研究主要集中于改 天津师范大学硕士学位论文 迸发现算法和复制策略以提高发现的准确率和性能。 g n u t e l l a 是一个p 2 p 文件共享系统，它和n a p s t e r 最大的区别在于g n u t e l l a 是纯粹的p 2 p 系统，没有索引服务器，它采用了基于完全随机的泛洪( f l o o d i n g ) 发现和随机转发( r n a d o mw a l k e r ) 机制。为了控制搜索消息的传输，通过 - i - r l ( r i m et ol i v e ) 的减值来实现。随着联网节点的不断增多，网络规模不断扩大， 通过这种泛洪方式定位对等节点的方法将造成网络流量急剧增加，从而导致网络 中部分低带宽节点因网络资源过载而失效。所以在初期的g n u t e l l a 网络中，存 在比较严重的分区，断链现象。也就是说，一个查询访问只能在网络的很小一部 分进行，因此网络的可扩展性不好。 为了提高g n u t e l l a 的可扩展性，人们提出了各种改进的g n u e t l l a 协议。除 了原有的关键字搜索之外，增加了通过文档内容哈希值进行搜索的方式，可以减 少系统中有着不同名字的相同文档对搜索性能的影响；通过在相邻节点之间交换 各自保存文档的关键字的方案来降低搜索的盲目性，提高g n u t e l l a 的可扩展性； 通过利用g n u t e l l a 网络中的异质性，限制发往带宽较小节点的搜索请求数量， 同时增加发往带宽较大节点的搜索请求数量来提高g n u t e l l a 的可扩展性。还提 出了超级节点的改进方案，该方案选择g n u t e l l a 网络中有着较高带宽和计算能 力的节点担当超级节点的角色，具体方案同下面将要介绍的基于f a s t t r a c k 的对 等网络系统类似。 对g n u t e l l a 泛洪的改进是随机步( r n a d o mw a l k ) ，该搜索从本质上和泛洪 搜索机制类似，都属于盲目搜索。和泛洪将搜索请求转发给所有邻居节点的方式 不同，随机步采取的转发方式是将搜索请求随机转发给邻居节点中的一个。一个 随机步定义为一个搜索进程，该搜索进程随机的将用户发出的搜索请求转发给当 前节点的邻居节点中的一个，直至找到期望文档，或者达到最大允许搜索跳数后 搜索失败。和泛洪搜索相比，随机步搜索可以大大降低对网络带宽的消耗，提高 系统的可扩展性，但是随机漫步搜索方式的一个主要缺陷是搜索的延时比较大。 假设一个随机步搜索进程需要经过t 步才能完成搜索请求，那么n 个随机步进 程同时进行搜索需要经过的平均跳数为t ，n ，即搜索延时缩短为原来的i n 。采用 n 个泛洪搜索那样在网络中产生过量的流量，同时也降低了单随机步搜索带来的 时延，因此是在网络带宽的消耗和搜索时延之l 、日j 的一种折衷方案。 9 天津师范大学硕士学位论文 l v 等在文中通过模拟实验验证了无结构对等网络中多随机步搜索方案的有 效性，得出1 6 至6 4 个随机步是比较恰当的选择。实验表明采用多个随机步的 搜索机制可以将泛洪搜索在网络中产生的流量降低两个数量级。 3 结构化p 2 p 系统 结构化对等网络也是完全分布式的对等网络系统，通常采用的是分布式哈希 表( d i s t r i u t e dh a s ht a b l e s ，简称d h t ) 的结构。和无结构对等网络相比，结构化 对等网络对文档在系统中的存放位置有严格的控制并且节点之间的关系比较紧 凑。结构化对等网络的最大优点在于它可以在。o ( 1 0 9 n ) ( 其中n 是系统中节点 的数目) 的跳数之内完成文档的路由和定位。结构化对等网络的主要特点是自组 织、可扩展、负载均衡、以及较好的容错性。和无结构对等网络主要用于文件共 享领域不同，结构化对一等网络的这些优良特性使得它可以应用在对可靠性和扩 展性要求比较高的场合。 4 混合式p 2 p 系统 混合式p 2 p 网络吸取了中心化结构和全分布式非结构化拓扑的优点，选择 性能较高( 处理、存储、带宽等方面性能) 的结点作为超级节点( s u p e r n o d e s n ) ，在各个s n 上存储了系统中其他部分结点的信息，发现算法仅在超级点之 间转发，超级点再将查询请求转发给适当的叶子结点。混合式结构也是一个层次 式结构，超级点之间构成一个高速转发层，超级点和所负责的普通结点构成若干 层次。最典型的案例就是k a z a a 。k z a a a 是现在全世界流行的几款p 2 p 软件之 一。根据c a 公司统计，全球k a z a a 的下载量超过2 5 亿次。使用k a z a a 软件 进行文件传输消耗了互联网4 0 的带宽。之所以它如此的成功，是因为它结合 了n p a s t e r 和g n u t e l l a 共同的优点。从结构上来说，它使用了g n u t e l l a 的全分 布式的结构，这样可以是系统更好的扩展，因为它无需中央索引服务器存储文件 名，它是自动的把性能好的机器成为s n ，它存储着离它最近的叶子节点的文件 信息，这些s n 再连通起来形成一个o v e r l a yn e t w o r k 。由于s n 的索引功能， 使搜索效率大大提高。 l o 天津师范大学硕士学位论文 2 2c h o r d 协议 2 2 1c h o r d 协议及拓扑结构 c h o r d 是麻省理工学院( m i t ) 研究人员提出的一种用于在动态p 2 p 网络中提 供查找服务的可扩展协议。c h o r d 的核心在于关键字映射，即将给定关键字( k e y ) 映射到相应的节点。通过c h o r d 协议，节点自身负责与摸个关键字对应的信息 的存储。c h o r d 采用相容哈希( c o n s i s t e n th a s h i n g ) 的一种变型为节点分配关 键字。相容哈希可以做到负载平衡，所有的节点基本负责相同数量的关键字，并 且节点的加入或离开仅造成很少节点的移动。一般的相容哈希是让每个节点掌握 所有其它节点的路由信息，而c h o r d 在相容哈希的基础上做出了一些改进，即 c h o r d 将节点路由表设计为分布式的，节点只需要知道少量其它节点的路由信息 就可以正确解析哈希函数，从而改善了相容哈希的扩展性。 c h o r d 将整个网络抽象为一个环形的拓扑结构，通常使用哈希函数 s h a 1 f 1 5 1 ，给每一个节点和文档都赋予一个m 位的标识符k e y ，节点的标识符 是通过对节点的i p 地址进行哈希变换得到的，文档的标识符是通过对文档的内 容进行哈希变换得到的。标识符的长度m 应该足够大，使得c h o r d 环能够容纳 最大可能的参与节点数，并且使得任意两个节点或者文档经过哈希变换后得到相 同标识符的概率可以忽略不计。 在c h o r d 中，每个节点维护少量的路由信息，通过这些路由信息，可以提 高查询的效率。如果m 是关键字和节点标识符的位数( 采用二迸制表示) ，那么每 个节点只需要维护一张最多m 个选项的路由表，称之为指针表。节点n 的查找 表的第i 个表项包括的是s = s u c c e s s ( n + 2 i - , l ，这里1 f m 并且所有的计算都要 进行m o d 2 ”，s 称为节点n 的第i 个指针，本文用甩f i n g e r i - ，z o d e 表示，指针表 中的其他项的含义如下表所示。 天津师范大学硕士学位论文 表2 1 节点1 3 的变量定义 符号定义描述 f i n g e r k s t a r t ( n + 2 h ) m o d 2 ”，1 k m i n te r v a l ( f i n g e r k s t a r t ，f i n g e r k + 1 s t a r t ) n o d e 第一个大于等7 = n f i n g e r k s t a r t 的n o d e s u c c e s s o r 标识符环上下一个n o d e 节点f i n g e r 1 n o d e p r e d e c e s s o r 标识符环上前一个n o d e 节点 c h o r d 网络中所有的节点根据标识符从小到大的顺序以顺时针的方向构成 一个逻辑环形的拓扑结构，文档保存在后继节点上。后继节点( s u c c e s s o r ) 是节 点标识符大于或者等于当前节点标识符的最小的一个节点，形象说后继节点就是 逻辑环中顺时针方向第一个跟着当前节点的实际存在的节点：前置节点 ( p r e d e c e s s o r ) 与后继节点正相反，是逻辑环中逆时针方向第一个跟着当前节点 的实际存在的节点，方便节点逆时针方向的查找，节点m 的后继节点和前置节 点分别记为s u c c e s s o r ( m ) 和p r e d e c e s s o r ( m ) 。例如在图2 1 中， s u e e e s s o r ( 18 ) = 3 1 ，p r e d e c e s s o r ( 18 ) = 10 ，k e y 6 映射到节点10 ，k e y 2 8 映射 到节点3 1 ，k e y 7 7 映射到节点8 2 。 其中c h o r d 协议定义了关键字查找、新节点加入流程以及节点失效处理等 方面的内容。 2 2 2 关键字查找 在c h o r d 网络中，简单的资源搜索机制是每个节点只需要保存其后继节点 的信息，这样查询消息就可以沿着c h o r d 环以顺时针的方向一步一跳的传递， 直到找到匹配的节点。例如在图2 1 中，节点1 计划查找k e y 值为2 8 的文档， 那么节点1 首先查找其后继节点5 ，节点5 再查找其后继节点1 0 ，依此类推， 直到查找到节点3 1 才找到k 2 5 。这种通过节点的邻接关系进行消息顺序传递的 方法虽然简单可行，但是效率非常低，网络中的两个节点为了找到对方很可能将 消息绕环传递一周。为了提高奄询效率，减少定位丌销，网络中的每个节点保存 一个具有m 个表项的f i n g e r 表( f i n g e rt a b l e ，邻居表) ，用以记录距离该节点 1 2 天津师范大学硕士学位论文 2 ( 0 i 朋) 的节点，节点n 的f i n g e r 表中的第i 项是刀+ 2 卜1 ，的后继节点， 在c h o r d 环空间上是跟在咒+ 2 卜1 之后的第一个节点s ，即 s = s u c c e s s o r ( n + 2 卜1 ) = ( n + 2 i - 1 ) m o d 2 “，其中1 f 所，表2 2 列出了图2 1 中 节点5 的f i n g e r 表。这样网络中的每个节点只需要维护自身f i n g e r 表中的小部 分节点，无需掌握网络中其他节点的信息，就可以通过节点之间的通信，找到任 一节点。具体查询步骤如下： 1 节点n 预搜索一文档，首先对文档内容做哈希变换得到一k e y 值。 2 节点n 查找k e y 所在的位置，若k e y 在n 和s u c c e s s o r ( n ) 之间，则文档 存放在节点n 的后继节点上，于是节点n 便可以直接向其后继节点发送查询请 求。 3 否则若k e y 不在n 和s u c c e s s o r ( n ) 之间，则节点n 需要查询其f i n g e r 表，找到标识符最接近k e y 并且小于k e y 的节点，直接向此节点发送查询请求， 节点接到查询请求后重复此查询步骤，直到搜索到目标节点。 图2 1c h o r d 的资源搜索过稃示意图 天津师范大学硕士学位论文 图2 1 显示了节点5 查找k 7 7 的过程，节点5 首先查看其f i n g e r 表，发现 节点3 1 最接近7 7 并且小于7 7 ，便发送查询请求至节点3 1 ，节点3 1 根据同样 策略找到节点5 8 ，最后节点5 8 找到k 7 7 存放在其后继节点8 2 处，节点5 8 将 节点8 2 返回给查询发起节点5 ，查询过程结束。 表2 2 节点5 的f i n g e r 表结构 f i n g e r 表 n 5 + ln 1 0 n 5 + 2 n 1 0 n 5 + 4n 1 0 n 5 + 8n 1 8 n 5 + 1 6n 3 1 从上述搜索过程可以看出，利用f i n g e r 表使查询距离至少减少一半。因为 根据f i n g e r 表的结构，任何一个节点到第i + 1 个f i n g e r 节点的距离是到其第i 个f i n g e r 节点距离的两倍，查询请求每经过一次转发离目标节点的距离就近了 一半，所以每个节点发出的查询请求最多经过o ( i o g n