（计算机软件与理论专业论文）对等计算系统中基于xml的查询路由和数据路由.pdf

图目录 l j l d b l p 中的x m l 文档示例 2 1 c h o r d 系统 2 2 基于x m l 的内容路由网络拓扑 3 1 查询消息发送和反馈过程 ， 3 , 2 不同的索引主题数的对比实验结果 3 3 r g 与b f s 、r w 的对比实验结果 4 1 发布订阅系统 42 x m l 文档及文档树 4 3x c h o r d 环 ， 4 4 分发路径树( d t 树) 4 ，5 改进后的x c h o r d 环+ 46 不同的查询路径映射长度三的对比 4 7 环上节点分布比较 4 8 全部节点路由信息占用空间的比较 49 数据包路由效率的比较 4l o 节点工作负载的比较 7 珀埔 恐乳 娼；蝣盯船弱黔硒耵 表目录 3 1 节点b 上的路由向导 3 2r g 模拟系统的相关参数 41 匹配订阅标识集 4 2x c h o r d 模拟系统的相关参数 2 3 2 8 4 0 5 3 摘要 随着互联网( i n t e r n e t ) 上越来越多的信息采用流行的x m l ( e x t e n s i b l e m a r k u pl a n g u a g e ) 格式来表示，x m l 日益成为网络数据表示和数据交换的 标准，并对传统的关系数据库领域带来了强有力的冲击。受其推动，基于x m l 数 据的应用技术，例如x m l 文档的检索、x m l 与关系数据库之间的数据移植，以 及x m l 文档数据流处理等技术也蓬勃发展起来。另一方面，近年来新兴的对等计 算系统( p e e r - t o - p e e rs y s t e m s ，简称p 2 p ) 为x m l 的网络应用开拓了一片新的研 究天地。尤其是关于对等计算环境下x m l 数据交换中的查询路由和数据路由技 术n 相继成为了研究热点，而对等计算系统不同于传统网络和分布式计算系统的 特点对这些技术的研究也提出了新的要求和挑战。 本文研究对等计算系统中基于x m l 的查询路由和数据路由的问题，作者提出 了在非结构化对等计算系统中的x m l 查询路由索引技术，以及结构化对等计算系 统中x m l 数据包的分发技术，旨在改进已有工作的不足之处，并为相关技术探索 新的解决方案。本文的主要贡献包括： 1 针对非对等计算系统中的x m l 文档检索的问题，在分析当前查询路由策略 的基础上，提出了建立路由向导( r o u t i n gg u i d e r ) 的查询索引方案，描述 了该方案的相关协议和算法。该方案的核心在于利用建立的路由向导，也 就是查询索引信息，有效地选择查询消息的发送目的地， 以避免大量无用 的信息发送。 2 以高效的x m l 数据分发为目的，介绍了一个应用于结构化对等计算环境的 发布订阅( p u b l i s h s u b s c r i b e ) 系统原型。简称为x c h o r d 。x c h o r d 系统通 过映射x m l 的路径查询语句和数据包的内容得到逻辑标识， 以此确定各个 中文摘要 节点的网络拓扑位置和数据包发送目的地，并且利用为每个数据包建立的分 发路径树( d i s s e m i n a t i o nt r e e ) 来提高数据包的路由效率。与传统发布订 阅系统相比，在该系统采用的数据路由方案中，不再需要接收包的节点在 本地解析数据文档以确定数据包和查询条件的匹配情况，从而节省了大量 的计算资源。 3 在x c h o r d 基本协议的基础上，提出了网络拓扑结构的改进方法，旨在进一 步降低数据包的路由代价。其中具体介绍了改进后的x c h o r d 系统的动态维 护策略和相关算法，并为后续相关的研究工作指明了改进方向。 本文的研究工作都是建立在对当前已有技术的大量分析和比较的基础上，并 通过详尽的模拟实验来验证所设计的方案的合理性和高效性。实验和分析表明， 作者提出的采用路由向导的查询路由策略相比传统的广度优先路由策略和随机路 由策略，都具有较高的路由效率；而x c h o r d 系统作为一种全新的数据分发系统框 架，能完全满足x m l 数据格式的要求，保证较高的数据匹配和发送效率。 关键词：x m l ，对等计算，查询路由，数据路由 分类号：t p 3 1 1 2 a b s t r a c t a sb e c o m i n gt h ed ef a c t os t a n d a r do fd a t af o r m a ta n dd a t ae x c h a n g e ，x m l ( e x t e n s i b l e m a r k u pl a n g u a g e ) h a sp r e s e n t e di t si n c r e a s i n gd o m i n a t i o no ni n t e r n e t ，c h a l l e n g i n g t h ed o m a i n s p o s s e s s e db yr e l a t i o n a ld a t a b a s e f o l l o w i n gt h i sn e wt i d eo fw e b 1 0 t so f x m l - b a s e dt e c h n i q u e sa r ed e v e l o p e db r o a d l ya n dq u i c k l y , s u c ha sx m ld o c u m e n t s r e t r i e v a l ，m i g r a t i o nt e c h n i q u e sb e t w e e nx m lf a m i l ya n dr e l a t i o n a ld a t a b a s e ，a n d p r o c e s s i n go fx m ld a t as t r e a m s ，e t c i nt h em e a nt i m e ，a n o t h e rn e we m e r g e dw 曲 c o m m u n i t y , p e e r t o - p e e rs y s t e m s ( p 2 pi ns h o r t ) ，b r i n ga sn e wp e r s p e c t i v eo fw e b a p p l i c a t i o n sw h i c hd i f f e r sf r o mt r a d i t i o n a lw e ba n dd i s t r i b u t e ds y s t e m s ，a sw e l la s m a k e su sc o n f r o n t e dw i t hb r a n d n e wc h a l l e n g e s s i n c et h er e s e a r c hf o rx m l b a s e dq u e r yr o u t i n ga n dd a t ar o u t i n gh a sa l r e a d y b e c o m et h eh o t s p o t w ep r e s e n to u rw o r ki nt h i st h e s i 8i nf a c eo fx m la n dp 2 p c o m m u n i t y , i n c l u d i n gd i s t r i b u t e di n d e xt e c h n i q u ef o rx m lq u e r i e si nu n s t r u c t u r e d p 2 ps y s t e m s ，i na d d i t i o nt ox m ld a t ad i s s e m i n a t i o ns o l u t i o ni ns t r u c t u r e dp 2 p s y s t e m s t h ec o n t r i b u t i o n so ft h i st h e s i sa r es u m m a r i z e da sf o l l o w s 1 aq u e r yi n d e xt e c h n i q u e ，c a l l e dr o u t i n gg u i d e 5i si n t r o d u c e d d u r i n gt h e p r o c e d u r eo fx m ld o c u m e n t sr e t r i e v a l ，r o u t i n gg u i d e r sd i r e c tq u e r ym e s s a g e s f o r w a r d e dt ot h en o d e sw i t hm a t c h e dd o c u m e n t s ，b yt h ea i do fh e u r i s t i ci n - f o r m a t i o nc o l l e c t e df r o mf e e d b a c ka b o u tp r e v i o u sq u e r yh i t s ，t h ed e t a i l e d p r o c e d u r ed e s c r i p t i o na n dr e l a t e da l g o r i t h m sa r ep r e s e n t e d r o u t i n gg u i d e r i sp r o v e dt oo u t p e r f o r mb f sa n dr a n d o mw a l ki nt h ep r e s e n to fs i m u l a t i n g c o m p a r i s o n s 3 英文摘要 2 a nx m ld a t ad i s s e m i n a t i o ns y s t e mf r a m e w o r k ，c a l l e dx c h o r di s p r o p o s e d ， t h a ti sa l s oap u b l i s h s u b s c r i b es y s t e m sa p p l i e df o rs t r u c t u r e dp e e r t o - p e e r e n v i r o n m e n t s t h es u b s c r i b ep e e r si nt h i ss y s t e ma r ee n d u r e dw i t hs u b s c r i b e i d e n t i f e r sg e n e r a t e db ym a p p i n gt h e i rs u b m i t t e dx m lq u e r yp a t h s ，a n dp u b l i s h e dd a t ap a c k e t sa r ea l s ol a b e l l e dw i t hs p e c i f i ci d e n t i f e r su s i n gt h es a m e f a s h i o n ，t oe n s u r et h em a t c h e dd i s s e m i n a t i o nd e s t i n a t i o n si nt h es y s t e m w i t h t h ea d d i t i o no fan o v e ld i s s e m i n a t i o np o l i c y ，t h ep a c k e t sc a nb es e n tt ot h e i n t e r e s t e ds u b s c r i b e r sw i t h o u tl o c a le v a l u a t i o na g a i n s tt h eq u e r i e si nt h en o d e s r e c e i v i n gt h e m ，t h u sm o r ec o m p u t i n gr e s o u r c e s & r es a v e d 3 t of u r t h e rr e d u c et h el e n g t ho fd a t ar o u t i n gp a t h ，a ni m p r o v e dp r o t o c o lo f x c h o r di sp r e s e n t e db a s e do nb a s i cm e c h a n i s m i na d d i t i o n ，m a i n t a i n i n g p r o c e s si nf a c eo fv a r i a t i o no fn e t w o r k ，a n do p e r a t i o na l g o r i t h m sa r ed e s c r i b e d i ns u m m a r y , o u rw o r ki sb u i l du p o ne x t e n s i b l ea n a l y s i sa n dc o m p a r i s o n so f c u r r e n tt e c h n i q u e s ，a n dt h es i m u l a t i o n ss h o wt h a t ，b o t hr o u t i n gg u i d e ra n dx c h o r d a r er a t i o n a ls o l u t i o n sr e s p e c t i v e l yt oq u e r yr o u t i n gi nu n s t r u c t u r e dp 2 ps y s t e m sa n d d a t ar o u t i n gi ns t r u c t u r e dp 2 p s y s t e m s ，a sw e l la so w nb e t t e rr o u t i n ge f f i c i e n c yt h a n o t h e rr e l a t e dp o l i c i e s k e y w o r d s ：x m l ，p e e r - t o - p e e rc o m p u t i n g ，q u e r yr o u t i n g ，d a t ar o u t i n g 4 第一章 引言 1 - 1 研究背景 近年来，可扩展标记语言x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) 已经逐渐成 为互联网( i n t e r n e t ) 上信息表示和交换的主要标准，在电子商务、数字图书 馆、w 如服务和信息检索等领域有着广泛的应用，并逐步取代了传统关系型数据 在这些领域中的统治地位。早在传统关系型数据盛行的时代，网络中各节点之间 交换数据一般都遵从提交查询、查询匹配、数据发送的流程模式，而查询路由和 数据路由分别研究如何高效地将查询消息从查询请求节点转发至数据源，以及怎 样将匹配的数据从数据源节点发送给请求客户端，因此，这两类问题一直都是网 络数据交换和数据共享研究领域中的重点和热点。在互联刚m p 3 文件检索、订票 系统中的信息订阅和分发，还有股票市场中流数据处理等技术中，和这些问题相 关的研究成果都得到了实际应用。如今，x m l 的兴起同样使得研究者们开始关注 以x m l 格式数据为研究对象的查询路由和数据路由问题。 不仅是网络中的数据表示形式，在网络的组织结构方面也掀起了一场对等计 算( p e e r t o - p e e rc o m p u t i n g ，简称p 2 p ) 的革命。对等计算系统从分布式计算系 统发展而来，最早应用于文件共享和即时消息传递。凭借对等计算系统领先于传 统客户机服务器( c l i e n t s e r v e r ) 网络模型的优点，再结合x m l 格式在数据表 示方面的强大功能，对等计算环境下的数据交换和数据共享研究体现出广阔的应 用前景。因此，对等计算环境下基于x m l 数据的查询路由和数据路由技术也成为 网络数据研究领域新一轮的研究热点，本文作者也以此作为研究对象，展开了一 系列探索和研究。 5 1 引言 作为本文研究背景的组成部分，我们先对x m l 和p 2 p 系统的概念以及具体应 用做一简单介绍。 1 1 1x m l x m l 文档与d t d x m l ( e x t e n s i b l em a r k u pl a n g u a g e ，可扩展的标记语言) f x m l ，2 0 0 4 1 ， 同h t m l ( h y p e r t e x tm a r k u pl a n g u a g e ，超文本标记语言) 一样都是由s g m l ( s t a n d a r dg e n e r a l i z e dm a r k u pl a n g u a g e ，标准通用标记语言) 发展而来， 是w 3 c 组织为了弥补h t m l 在数据表示的灵活性和描述性等功能上的缺陷， 于1 9 9 6 年底提出的标准。它是一套定义语义标记的规则，这些标记将文档内容分 成许多部分( e l e m e n t ，也称为元素1 并对它们加以标识。同时，x m l 也是一种元标 记语言( m e t a - l a n g u a g e ) ，定义了用于定义其它与特定领域有关的、语义的、结 构化的标记语言的句法。在x m l 文档中，用户可以根据通用的原理来创建自己需 要的标记( t a g ) ，标记的意义具有相当的灵活性，令用户在网络上能够方便地 传输、处理各类复杂的文件。例如，图1 1 是d b l p 【d b l p ，1 9 9 8 数据的x m l 格式文 档中的一段内容，其中的 、 、 等标记都是用户 预先定义的，它不像h t m l 那样必须严格地使用诸f i b 、 、 等 规定好的标记。另外，x m l 文档的定义信息都存储在对应的d t d 文件中。 d t d ( d o c u m e n tt y p ed e f i n i t i o n ，文档类型定义) 可以看作是x m l 文档的 词汇表和句法，其使用意图在于定义x m l 文档的合法构建模块，通过一系列 合法元素来格式化x m l 文档的内部结构。一个x m l 文档当中出现的标记名称 和格式，元素数据包含哪些格式，都在对应的d t d 当中预先定义好了。而且， 一个d t d 不光只应用在一个x m l 文档上，还可以为一类相关的文档创建通用 的d t d ，使得用户可以通过查看d t d 来了解其约束的x m l 文档的内部结构，制 定要交换的数据标准。 鉴于其灵活又不失规范的特点，x m l 被归类为半结构化语言( s e m i s t r u c t u r e d l a n g u a g e ) ，并且自出现以来就对传统关系数据库领域造成强有力的冲击，逐 渐成为w e b 数据信息的表示和存储规范。受其推动，为了有效地分析、处 理x m l 数据，大量相关的技术研究也逐渐兴起，如针对x m l 流数据的过滤 技术 c h a ne ta 1 ，2 0 0 2 ，d i a oe ta 1 ，2 0 0 2 1 、视图处理技术 g u p t ae ta 1 ，2 0 0 2 ，以 及x m l 与传统关系数据库之间的数据移植技术( 如a l l o r a a l l o r a ，2 0 0 4 ) 等等。 6 i 引言 图1 1 ：d b l p 中的x m l 文档示例 7 1 引言 基于x m l 的查询语言 就像针对关系数据库的查询而产生的s q l ( s t r u c t u r e dq u e r yl a n g u a g e ，结 构化查询语言) 一样，x m l 的出现也带动了为其量身订做的半结构化查询语言的 发展。诸如x q l x q l ，1 9 9 9 、x q u e r y x q u e r y ，2 0 0 3 】、x p a t h x p a t h ，1 9 9 9 等 都是业内著名的基于x m l 的查询语言。因为本文所研究的问题场景中都使用类似 于x p a t h 表达式的查询语句，所以在此对x p a t h 这种查询语言做一简单介绍。 x p a t h i p 为x m l 路径语言，它通过表示一段路径来对要查询的x m l 文档中某 个部分( 元素) 进行定位。因为在文档内容定位方面的高效性，x p a t h 经常被其 它x m l 处理语言用来完成特定的功能，如x s l t x s l t ，1 9 9 9 1 、x p o i n t e r x p o i n t e r ，2 0 0 1 i s n x 等。下面是2 个x p a t h 表达式( 简写为x p e ) 的示例： x p e1 ： d b l p m a s t e r s t h e s i s k e y = ”m s b r o w n 9 2 ” a u t h o r x p e2 ： d b l p * 这里，x p e i 定位到了名为a u t h o r 的元素，它是根元素4 b l p 下的m a s t e r s t h e s i s ：元 素的子元素，同时要求它的上层元素m a s t e r s t h e s i s 的k e y 属性为m s b r o w n 9 2 ，条 件 k e y = ”m s b r o w n 9 2 ”】通常被成为谓词( p r e d i c a t e ) 。而x p e 2 贝j j 对应了根元 素d b l p 下的所有子元素，因为+ 是通配符，它代表了任意元素。 1 1 2 对等计算系统 对等计算系统和传统的客户机服务器( c s ) 类型网络，或是传统的分布式 系统相比，至少具有以下特点： 网络中每个节点( p e e r ) 既可以是客户机也可以是服务器，或者兼备两种角 色； 一个节点可以根据自己的需要在应用层与任意一个节点建立连接或通讯a 既然对于对等计算系统中的任何一个结点来说，它都可以承担服务器的角色，这 样相比客户机服务器网络，对等计算系统更容易实现海量数据的存储a 而且， 结点拥有高度的自治性，尤其对于非集中式的p 2 p 系统( 见第二章的详细介绍) ，很多功能的实现不再依靠一个或少数的服务器，因此对网络攻击具有更强的鲁 愀( r o b u s t n e s s ) ，可以避免单点故障( s i n g l e - p o i n tf a i l u r e ) 。 8 1 引言 从其应用角度看，自2 0 0 1 年开始，大量的基于对等计算模型的软件 系统已经应运而生。其中较为著名的包括，早期为t m p 3 音乐文件共享 而产生的f r e e n e t f r e e n e t ，2 0 0 3 ，还有n a p s t e r n a p s t e r ，2 0 0 3 署d 即时消息传递 系统i c q i c q ，2 0 0 3 ，到现今流行的k a z a a k a z a a ，2 0 0 3 】、m s nm e s s e n g e r m s n m e s s e n g e r ，2 0 0 3 等等。 在学术研究领域，因为对等计算系统的特点和优势，很多从事网络、数据 库和分布式计算系统研究的学者也把注意力转移到对等计算领域上来，并已获 得大量研究成果，包括与对等计算系统底层平台和系统原型相关的，女n c h o r d s t o i c ae ta 1 ，2 0 0 1 、c a n r a t n a s a m ye ta 1 ，2 0 0 1 】、t a p e s t r y z h a oe ta 1 ，2 0 0 1 、 b e 8 t p e e r 【b e s t p e e r ，2 0 0 3 和o c e a ns t o r e o c e a n s t o r e ，2 0 0 3 】，以及其上的相关技术 与应用如d h t 【m a n k u ，2 0 0 3 1 ，r i 【c r e s p oa n dc a r c i a - m o l i n a ，2 0 0 2 1 ， p i a z z a p i a z z a ，2 0 0 3 等等。 1 2 研究动机和内容 虽然x m l 和对等计算系统的兴起带动了各自领域中相关工作的研究开展，并 且结合x m l 技术和对等计算平台的应用前景也非常广阔，但是，完全针对对等计 算环境中基于x m l 的查询路由和数据路由技术的研究成果还不多见。要在对等计 算系统中实现x m l 数据的共享和交换，必须考虑而如何提高x m l 查询消息和数据 包的路由效率，而x m l 数据格式和对等计算系统自身的特点对这些问题的研究提 出了更高的要求和全新的挑战。和传统关系型数据相比，x m l 文档和查询之间基 于内容( c o n t e n t b a s e d ) 的匹配机制要比关键字( k e y w o r d ) 的匹配复杂；此外， 对等计算系统中的节点完全自治，没有全局的服务器提供路由的指导信息，如何 让每个节点既自主又能互相合作，来达到高效地发送查询和数据消息的目的；对 等计算系统中各节点卜线、下线变化频繁，随意性强，如何保证网络拓扑的稳定 性，保证查询结果返回的时效性、正确性等等，以上都是本文工作的研究动力所 在，也是我们首要考虑的问题。 基于以上问题，我们展开相关研究工作，并取得了如下进展，也是本文论述 的主要内容。 关于查询路由问题的研究，我们主要针对非结构化的对等计算系统中 的x m l 文档检索的问题，提出了路由向导( r o u t i n gg u i d e r ) 的查询索引技 9 1 引言 术。路由向导是一种分布式的查询索引技术，是通过初始的查询和反馈机 制建立主题索引，索引里面记录的是周围节点匹配某个查询主题的x m l 文 档数。然后，后续的查询以命中查询主题的索引作为启发式信息来引导查 询消息的转发方向。此外，路由向导还能够自适应地调整索引的查询主 题，保持路由指导信息的即时性、正确性。 为了应用所提出的数据路由技术，我们设计了一个以结构化对等计算系统 为平台的x m l 数据发布订阅系统，简称为x c h o r d 。x c h o r d 采纳著名对等 计算系统c h o r d s t o i c ae ta 1 ，2 0 0 1 1 中的环状网络拓扑结构和d h t 映射机制， 并在其基础上针对x m l 查询和数据的特点，运用一套独特的x m l 查询和数 据内容的映射方法来获得逻辑标识地址，通过将每个发布的数据包分发 到具有匹配映射标识的节点，使得订阅节点能够接收到匹配的数据文档。 x c h o r d 中采用的此种数据分发机制避免了数据包在节点本地的过滤处理， 节省了大量的计算资源，同时也减少了多余的在无关节点上的数据转发， 提高了数据路由效率。 1 。3 本文组织 本文的结构如下，第二章简要介绍对等计算系统的主要类别，以及关于查询 路由和数据路由技术的研究工作进展。接下来，第三章和第四章分别介绍路由向 导的查询索引技术与x c h o r d 数据分发系统。在这两章里，我们不仅详细描述了这 两类技术方案完整的机制协议、相关算法，还包括大量的模拟实验结果分析，以 证明这些方案的合理性和高效性。最后的笫5 章里是对当前工作的总结和将来工作 的展望。 1 0 第二章 相关工作的研究进展 2 1 对等计算技术的研究简介 关于对等计算技术的研究，最早兴起于1 9 9 9 年。根据系统中各结点在应 用层上的组织结构，对等计算系统又可以大致分为非结构化对等计算系统 ( u n s t r u c t u r e dp 2 ps y s t e m s ) 和结构化对等计算系统( s t r u c t u r e dp 2 ps y s t e m s ) 两大类。下面分别对这两大类对等计算系统做相关的介绍。 2 1 1 非结构化对等计算系统 非结构化p 2 p 系统( u n s t r u c t u r e dp 2 ps y s t e m ) l y i n ga n dg a r c i a - m o l i n a ，2 0 0 1 是较早被广泛研究并占主要地位的一类p 2 p 系统。这类系统中的节点组织结构 松散，在应用层上可以和任意节点连接，所以相对结构化的p 2 p 系统也比较容 易实现，具有此种特性的网络也常常被称为即兴网络( a dh o cn e t w o r k ) ， 更适合于动态的p 2 p 环境。也正是因为节点组织无规律可寻，所以查找和定 位某个节点往往通过广播( b r o a d c a s t ) 、多播( m u l t i - c a s t ) 或者索引的方式进 行。根据各节点对索引服务器的依赖程度，非结构化p 2 p 系统又可以细分为 集中式的( c e n t r a l i z e d ) 、非集中式的( d e c e n t r a l i z e d ) 和混合( h y b r i d ) 式的。 n a p s t e r n a p s t e r ，2 0 0 3 1 就属于集中式的p 2 p 系统，整个系统采用单个的索引服务 器。因此容易造成单点故障( s i n g l e - p o i n tf a i l u r e ) 问题。而在非集中式的p 2 p 系 统中，如g n u t e l l a g n u t e l l a ，2 0 0 2 1 和f r e e n e t f r e e n e t ，2 0 0 3 ，不存在任何索引服 务器，节点查找和定位通过广播或者多播方式进行。虽然避免了单点故障，但是 1 1 2 相关工作的研究进展 广播和多播可以说是一种泛滥搜索( f l o o d i n gs e a r c h ) ，通常要消耗大量的网络资 源。混合式的p 2 p 系统一般借助于多个超级节点( s u p e rp e e r ) 作为索引服务器， 超级节点之间才是通过泛滥方式相互通讯，它结合了集中式和非集中式系统的优 点，像b e s t p e e r b e s t p e e r ，2 0 0 3 1 就是这类系统。 本文第三章介绍的查询路由技术就是应用于非结构化p 2 p 系统，无论对于哪 种细分的非结构化系统，其中提出的解决方案都具有较强的适用性。 2 1 2 结构化对等计算系统 不同于非结构化p 2 p 系统，结构化p 2 p 系统中的节点组织遵守严格的特 定规则。如c h o r d s t o i c ae ta 1 ，2 0 0 1 1 和c a n r a t n a s a m ye ta 1 ，2 0 0 1 系统都是根 据d h t m a n k u ，2 0 0 3 确定每个节点的标识( i d e n t i f i e r ) ，并按照特定的规则将各 个节点组织在逻辑标识空间中。另外，还有一些p 2 p 系统，如p a s t r y 【r o w s t r o na n dd r u s c h e l ，2 0 0 1 1 和t a p e s t r y z h a oe t “，2 0 0 1 1 ，利用p l a x t o n 算法 p l a x t o ne ta 1 ，1 9 9 7 的变型组织p 2 p 嘲络。由于结构化p 2 p 系统的设计一般具有理 论基础。因此遵循特定规则的节点查找和定位会比非结构化p 2 p 系统中的泛滥方 式效率高而且系统的鲁棒性大都具有理论保证。 因为本文第四章谈到的x c h o r d 系统也是以结构化p 2 p 系统做为底层平台，实 际上是c h o r d 系统的一种改进结构。为了方便读者理解其中的细节，所以在这里 先对c h o r d 系统傲简单的介绍。 c h o r d c h o r d 是一种典型的基- = d h t m a n k u ，2 0 0 3 1 的姑构化对等计算系统，系统的 网络拓扑结构可以看成是一个包含有2 m ( m 一般取1 2 8 ) 个逻辑标识( i d e n t i f i e r ， 简称i d ) 的环，系统中每个节点按照下述规则加到环上：假定一个新加入的 节点p 利用哈西( h a s h ) 函数，例女i s h a i s h a l ，1 9 9 8 】，将自己的i p 地址映射 为一个特定的i d ，记为厶( 2 m ) 。然后p 和那些i d 值最接近但又不小于( + 2 i ) m o d 2 m 0 i m ，的节点建立连接，这些节点被称作f i n g e r ，其地址信息都会 存储在本地一个叫做f i n g e r 表的路由信息表上。对于系统中的每个数据对象，也 是通过哈西其名字或属性映射出一个键值( k e y ) 。当p 确定了在环中的位置后， 凡是键值落在它和它前趋节点( p r e d e c e s s o r ) i d 值范围内的数据对象都由p 来管 1 2 2 相关工作的研究进展 f i n g e r 表m = 4 图2 1 ：c h o r d 系统 理。因此，当一个节点要寻找键值为七的数据对象时，只要利用自己的f i n g e r 表将 查询消息发送到i d 值最靠近但是又不超过k 的后继节点上去。图2 1 标示了一个标 准的c h o r d 环，列出了其中一个节点p 的i d 值和它的f i n g e r 表的内容，它所管理的 范围是7 9 。图中黑色圆圈代表一个节点，括号中是节点的i d 值，而虚线圆圈只 代表一个标识位嚣。 为了保持整个c h o r d 环链路的稳定正常，每次节点的加入和退出，受到影 响的节点都要更新自己的f i n g e r 表以及所管辖的数据对象，如果牵涉的节点 多，改动工程会相当大，在文献 s t o i c a e ta 1 ，2 0 0 1 1 中提到了利用定期稳定维护 ( s t a b i l i z a t i o n ) 的方法以减小更新代价，包括面对节点连接没有及时更新，甚 至节点突然断线的非正常情况下，系统中其它节点如何操作以保证查询的准确执 行，感兴趣的读者可以参看这篇文献的详细内容。 2 2 路由技术的研究工作进展 当前网络中各结点之问的数据共享和交换技术可以分为p u l l b a s e d $ 1 p u s h - b a s e d 两类。前者是指客户端通过向数据源提交自己的查询请求，由数据源对查 询条件进行解析，然后把匹配的数据返还给查询客户端，这种方式里，数据的传 送是由查询请求来触发的：后者是指数据源将自己的数据主动地向网络其它结点 发送，而不考虑客户端当前是否提交查询请求，各客户端接收到数据后会检查是 否符合自己的查询条件，是则接受，否则再转发给其它节点。对应这两种方式， 1 3 2 相关工作的研究进展 分别产生了对查询路由和数据路由两类问题的研究，下面我们分别介绍这两方面 相关的工作。 2 2 1 查询路由技术 本节主要介绍对等计算环境中的查询路由技术的研究工作。由于x m l 属于网 络数据库领域的全新的数据格式，所以在查询路由方面很多已有的研究工作还是 面向传统的关系型数据，使用的查询语句大都是基于关键字( k e y w o r d - b a s e d ) 或 者基于类型的( t y p e - b a s e d ) ，返回的数据对象是关系数据表的元组( t u p l e ) 或 者记录( r e c o r d ) 。 广度优先的路由策略 这种查询路由方式实际上就是一种泛滥式的路由方式。如上节提到的， 像g n u t e l l a 这_ 类非集中式的非结构化p 2 p 系统，由于没有全局的服务器提供路由 信息，系统中的节点只了解自己和周围少数几个节点数据存储情况，所以在查询 时为了保证获得想要的结果，往往将查询消息转发给所有的邻居节点。如果邻居 节点还是不能提供匹配的结果，就继续发送查询给其它的节点，直到超出查询的 跳转限制范围( h o p s - t o - l i v e ) 。就像洪水泛滥一样，如果查询消息没有满足中止 条件，就会遍历网络中所有的节点，于是造成庞大的通信代价。 在基本的广度优先的查询路由策略基础上，为了进一步降低泛滥方式的路由 代价，2 0 0 2 年b y a n g 等人提出了改进的路由策略 y a n ga n dg a r c i a - m o l i n a ，2 0 0 2 。 首先是迭代加深的广度优先搜索策略( i t e r a t i v ed e e p e n i n gb f s ) ，将查询消息散 发的过程分成几个阶段，每个阶段内都设置一个小于查询实际跳转限制的范围， 如果在这个小的范围内查询能够获得足够的结果就不必再继续转发，没有的话则 扩大消息广播的范围进入下一个查询散发的阶段。第二种改进方式是方向性选择 的广度优先搜索策略( d i r e c t e db f s ) ，即每次查询消息的转发不是发给所有的 邻居，而是根据以后前的启发信息发给少数几个能够提供匹配结果的邻居节点。 这两种方式相比基本的广度优先策略都大大降低了系统中消息转发的数量。 深度优先的路由策略 对应广度优先的路由策略，深度优先是非集中式的非结构化p 2 p 系统采用的 另一种主要的查询路由方式。如f r e e n e t 系统，当一个节点接收到查询的时候，它 1 4 2 相关工作的研究进展 不像g n u t e l l a 里面那样同时转发给所有的邻居，而是根据本地存有的相关信息选 择一个邻居发送查询请求。只有当前一个发送去的查询请求返回结果后( 无论有 没有匹配的数据) 。或者超出了查询跳转范围，节点才会尝试将查询请求发给下 一个邻居。这和深度优先的搜索策略( d e p t hf i r s ts e a r c h ) 的原理是一致的。 基于索引的路由策略 对于拥有索引服务器的p 2 p 系统( 如n a p s t e r ，b e s t p e e r ) 来说，节点间的查 询路由可以借鉴索引提供的信息来决定查询消息路由的后继节点。当然，如果没 有集中式的索引服务器，同样可以通过在每个节点上建立分布式的索引来指导查 询路由， 【y a n ga n dg a r d a - m o l i n a ，2 0 0 2 】和【c r e s p oa n dc a r c i a - m o l i n a ，2 0 0 2 两篇 文献中提到的索引策略都是指建立这种分布式索引的路由机制。在后一篇文献中 提出的路由索引( r o u t i n gi n d e x ，简称r i ) 策略更具体化了分布式路由索引的建 立和使用过程，系统中每个节点通过预先统计周围节点能提供的满足某个查询主 题的文档数目，再以此作为路由索引的启发式信息，指导相应主题的查询发送至 能提高匹配文档的邻居节点上。 基于x m l 内容的路由策略 相比传统的关系型数据，针对x m l 文档的查询，牵涉到了文档内容( 文档 中满足条件的元素) 的匹配，要比传统的关键字查找复杂，但表达上的意义更 加丰富，它是一种基于内容( c o n t e n t b a s e d ) 的查询方式。g k o l o n i a r i 等人在文 献i k o l o n i a r ia n dp i t o u r a , 2 0 0 4 l 中提出的方案就是一种基于x m l 内容的查询路由 技术，所描述的问题场景以x m l 查询路径( p a t hq u e r i e s ，类倒( x p a t h ) 作为查询 语言，并以图2 2 所表示的结构作为网络拓扑。图中黑色圆圈代表根节点，根节点 间通过主通道通信，并且每个根节点拥有自己的节点群体( c l u s t e r ) 。一个群体 中最底层的节点把自己的查询条件用广度优先的b l o o m 过滤器( b b f ) 或者深度 优先的b 1 0 0 1 1 1 过滤器( d b f ) 表示，并上传给上层节点。上层节点如果不能满足 过滤器中表示的查询条件，则结合自己的查询要求生成新的综合的过滤器继续发 给更上层的节点，直到上传至根节点。如果根节点也不能提供匹配的x m l 文档， 即表明本节点群内没有符合的查询结果，那么就通过主通道把综合的过滤器( 查 询消息) 发给其它的根节点，继续在其它的节点群内寻找。 文献 k a r n s t e d te ta 1 ，2 0 0 4 6 e 提到的查询路由和处理策略也是针对x m l 数 据，作者所说的查询装载( q u e r ys h i p p i n g ) 和数据装载( d a t as h i p p i n g ) 实际上 1 5 2 相关工作的研究进展 图2 2 ：基于x m l 的内容路由网络拓扑 主通道 就分别对应了查询路由和数据路由技术。该文中提到的路由技术也是借助了节点 上存有的混合路由索引( c o m p o u n dr o u t i n gi n d i c