（计算机应用技术专业论文）基于dht的p2p复杂搜索机制的设计与实现.pdf

摘要 摘要 p 2 p 网络是一种所有的网络节点都扮演相同角色的网络。在该网络中，各节点 可以平等和直接地在网络中交换资源与服务，因此p 2 p 网络被广泛应用于文件共 享系统中。p 2 p 网络通常分为结构化网络和非结构化网络两大类：在一个非结构化 网络中，资源的检索通过洪泛查询的方式，该方式低效且网络负荷高；而基于d h t ( d i s t r i b u t e dh a s ht a b l e ) 的结构化网络具有很好的搜索效率和性能。然而，目前 d h t 网络主要针对精确关键字匹配来进行搜索，并不能有效地对多关键字进行搜 索。因此，结构化p 2 p 网络复杂搜索的研究是有必要的。 本文的主要目的是研究基于结构化p 2 p 网络的复杂搜索机制，并且在仿真环境 中进行测试，基于仿真结果分析其性能指标和特点，并对进一步研究的方向进行 了讨论。 本文的创新点在于，从内容索引和物理索引映射的方式来研究结构化p 2 p 的复 杂搜索机制，并用文本分类来作为内容索引的基础，从而使内容相近的资源可以 尽可能的在物理位置上接近，提高了搜索性能和资源发布性能。 本文首先对几种现有的结构化p 2 p 复杂搜索方案进行了深入研究，并将目前对 结构化p 2 p 复杂搜索研究方法分为四大类。研究分析表明，通过内容索引和物理 节点索引相结合的方法是一种较为行之有效的研究方法。本文采用该方法，并结 合d h t 网络k a d e m l i a ，提出了一种支持多关键字搜索的d h t 新机制：k n n k a d 。在 介绍了k n n k a d 的机制的实现细节并分析了其可行性之后，阐述了在p 2 p 的仿真 平台p e e r s i m 上k n n k a d 的具体实现细节。通过分析仿真结果，得出k n n k a d 不 仅相对现有的结构化p 2 p 复杂搜索机制有更好的搜索性能，并且也同样具有更低 的网络通信量、较好的负载均衡能力和低维护代价。 关键词：p 2 p ，结构化p 2 p 网络，多关键字搜索，k 最邻近法，p e e r s i m 仿真 a b s t r a l c t a b s t r a c t ap 2 pn e t w o r ki sak i n do fn e t w o r k st h a ta 1 1o fn o d e ss h a r et h es a m e r o l e s i n c ea 1 1o ft h en o d e sc a ne a s il ya n dd i r e c t l ye x c h a n g er e s o u r c e s a n ds e r v i c e si nt h i sn e t w o r k ，p 2 pn e t w o r k sa r ew i d e l yu s e di nf i l es h a r i n g s y s t e m g e n e r a l l ys p e a k i n g ，p 2 pn e t w o r k sc a nb ed i v i d e di n t ot w oc a t e g o r i e s ： u n s t r u c t u r e dp 2 pn e t w o r k sa n ds t r u c t u r e dp 2 pn e t w o r k s i na nu n s t r u c t u r e d p 2 pn e t w o r k ， s e e k i n gap i e c eo fs p e c i f i cr e s o u r c eo f t e nr e s o r t st o “f l o o d i n g ”h o w e v e r ，t h i sm e t h o dn o to n l yb r i n g sl o we f f i c i e n c y ，b u ta l s o ah e a v yb u r d e nt on e t w o r k s ：c o m p a r a t i v e l y ， as t r u c t u r e dn e t w o r kb a s e do n d h t ( d is t r i b u t e dh a s ht a b l e )iso fah i g h e re f f i c i e n c ya n dp e r f o r m a n c e b u to nt h eo t h e rh a n d ，c u r r e n td h tn e t w o r k sc a no n l ys u p p o r ts i n g l ek e y w o r d s e a r c h ，a n dt h el o we f f i c i e n c yo fm u l t i w o r ds e a r c hr e m a i n s t h e r e f o r e i ti se s s e n t i a lt od e v i s eah i g hp e r f o r m a n c ec o m p l e xs e a r c hm e c h a n i s mf o r s t r u c t u r e dp 2 pn e t w o r k s t h ep r i m a r yg o a lo ft h i st h e s i si st oi n t r o d u c ean e wa n dab e t t e r m a c h a n i s mt os o l v et h em u l t i w o r ds e a r c hp r o b l e mi ns t r u c t u r e dp 2 pn e t w o r k s a n ds i m u l a t et h i sm a c h a n s i mt oa n a l y s ei t sc o m p r e h e n s i v ep e r f o r m a n c ea s w e l la si t sa d v a n t a g e s ， d i s v a n t a g e s ， a n dt h ef u r t h e ri m d r o v e m e n t s t h ei n n o v a t i o no ft h em e c h a n i s mi nt h i st h e s i s1 i e si nt h eu t i l i z a t i o n t h ec o m b i n a t i o no ft h ec o n t e n t i n d e x i n ga n dt h en o d ei n d e x i n g ，a n dt h e c o n t e n c ti n d e x i n gb a s e do nt e x tc a t e g o r i z a t i o n w i t ht h i sm e t h o d t h e r e s o u r c e sw h i c hh a sas i m i l a r l yt h e m ec o u l db eg a t h e r e da sc l o s ea sp o s s i b l e s o a st oi m p r o v et h es e a r c hp e r f o r m a n c et os o m ee x t e n x t i nt h i st h e s i s ， s e v e r a lc u r r e n tc o m p l e xs e a r c hm a c h a n s i mb a s e do n s t r u c t u r e dp 2 pi sd e e p l ys t u d i e da tf i r s ta n dt h e nd i v i d e di n t of o u rc l a s s e s a f t e rt h a t ， a n a l y z a t i o nr e s u l t si n d i c a t et h a tt h ec o m b i n a t i o no fc o n t e n t i n d e x i n gw i t h n o d ei n d e x i n gi sap r o m i s i n gr e s e a r c hm e t h o dt od e v i s ea s t r u c t u r e dp 2 pn e t w o r kc o m p l e xs e a r c gm e c h a n i s m b a s e do nt h ism e h o d a a b s 仃a c t d h tb a s e dm o d e lw h i c hs u p p o r t sm u l t i w o r ds e a r c h ， k n n k a d ， i sp r o p o s e d a f t e rt h em e c h a n i s mo fk n n k a di si n t r o d u c e da n di t sf e a s i b i l i t yi s a n a l y s e d ，t h i sm o d e li ss i m u l a t e di np e e r s i m w i t ht h es i m u l a t i o nr e s u l t s ， i tp r o v e st h a tk n n k a dh a sac o m p a r a t i v e l yh i g h e rp e r f o r m a n c e ，ab e t t e r l o a db a l a n c ea b i l i t y ，l o w e rc o m m u n i c a t i o nb u r d e na n di sm u c he a s i e rt o m a i n t a i n k e y w o r d s ： p 2 p ，d h t ，m u l t i - w o r ds e a r c h ，kn e a r e s tn e i g h b o r ，s i m u l a t i o n i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：煎兰骂匕蜂一一嚣期： 年月墨 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 血业擎 导师签名：盏全汪z导师签名：盘盘zk 日期：年月日 第一章引言 1 1 课题背景 第一章引言弟一早jl 函 p 2 p 即是p e e r t o p e e r 的缩写，称为对等连接或者点对点网络。p 2 p 是一种分 布式网络，其中的参与者共享他们所拥有的一部分硬件资源或者软件资源( 处理 能力、存储能力、网络连接能力、打印机以及文件资料等) ，这些共享的资源需要 由网络提供服务和内容，能被其他对等方直接访问而无需经过中间服务器。在此 网络中，参与者既是资源( 包括服务和内容) 的提供者，又是资源的获取者。 1 1 1p 2 p 网络的定位方式分类 根据p 2 p 资源定位方式的不同，p 2 p 网络可以分为集中式网络、非结构化网 络和结构化网络。 集中式网络以n a p s t e r 为代表，其资源定位的方法比较简单和直观。在集中式 p 2 p 网络中，所有共享信息的记录以及反馈对这些信息的查询由一个统一的中心服 务器来完成。每一个对等方要对它所需要共享信息进行维护，根据其他对等方的 需要传送到所相应的对等方上。这种资源搜索机制具有中心化的特点，但是它不 同于传统的c l i e n t s e r v c r 模式。因为传统的c l i e n t s e r v e r 模式将所有的资料都存在 中央服务器上，客户机只能从服务器上传和下载资源；而集中式p 2 p 网络则是将 所有网上提供的资料都存放在提供该资料的客户机上，服务器上只保留索引信息， 此外的服务器与对等实体以及对等实体之间都具有交互能力。 以g n u t e l l a 为代表的非结构化p 2 p 网络相对于集中式p 2 p 网络在资源定位方 法上最大的不同是，非结构化p 2 p 没有中央索引服务器，而是采取了洪泛( n o o d i n g ) 和随机转发( r 锄d o mw a l k e r ) 的机制来对网络上的资源进行查询。非结构化p 2 p 网络面对网络的动态变化体现了较好的容错能力，因此具有较好的可用性。同时 支持了多关键字搜索等复杂查询。 为了防止搜索消息的泛滥和产生回路，非结构化p 2 p 网络提供了搜索消息的 1 几( r n m et ou v e ) 的减值的机制来控制其跳数( h o p ) 。在结构化p 2 p 网络中， 电子科技大学硕士学位论文 每个对等方在功能上是相同的，既是客户机又是服务器。 非结构化p 2 p 网络的搜索机制最大的缺点在于：由于没有特定的网络拓扑结 构的支持，非结构化网络无法保证资源的发现效率。由于采用1 r l ，洪泛和随 图1 1 集中式p 2 pi 网络一n a p s t e r 机的机制，这些机制固有的缺点会导致如下几个问题：首先是会导致非结构化p 2 p 网络的搜索消息路由不可控制，随着网络规模的扩大，网络资源的消耗也急居4 增 加；其次，采取这种搜索机制存在比较严重的分区，断链现象。也就是说，一个 资源消息只能在网络的很小一部分进行，这个缺点导致资源搜索的效率随着这个 网络规模的扩大而降低，无法保证资源发现的效率，即使一个需要的资源已在该 p 2 p 网络上存在，搜索也可能失败。 为了解决非结构化p 2 p 的搜索机制的以上限制，出现了以d h t ( d i s t r i b u t e d h a s h t a b l e ) 为基础的结构化p 2 p 网络。其中，主流的d h t 系统有：勋d e m l i a 【， p a s 衄【2 】，t a p e s t r y 【3 1 ，c h o r d 【4 】，以及c a n 【5 】等。 结构化的p 2 p 网络中，每一个节点通过统一的哈希函数计算出节点i d ，将物 理环境中的节点映射为空间中的节点i d 标识。不同的p 2 p 网络中不同的p 2 p 搜索策略采用不同的路由信息组织方式，带来的是不同的侧重性能和特点，同时 不同的搜索策略还会影响到上层应用的组织方式、维护策略和系统性能。 d h t 实际上是一个由广域范围大量节点共同维护的巨大散列表。散列表被分 割成不连续的块，每个节点被分配给一个属于自己的散列块，并成为这个散列块 2 第一章引言 的管理者。d h t 的节点既是动态的，同时节点的数量也是巨大的，因此如何设计 该非中心化的网络拓扑结构成为结构化p 2 p 网络的关键，由于重叠网络采取了确 定性的拓扑结构，d h t 可以提供精确的范围。只要目标节点存在于网络中d h t 总 能发现它，发现的准确性得到了保证。 d h t 资源定位方法最大的问题是d h t 的维护机制较为复杂，尤其是节点频繁 加入和退出( c h u m ) 造成的增加d h t 的维护代价。d h t 所面临的另一个问题是 d h t 仅支持精确关键字匹配查询，无法支持内容语义等复杂查询。 1 1 2 主流的基于d h t 的p 2 p 系统简介 c h o r d 【4 j 是u cb e r k e l e y 和m i t 共同提出的一种分布式查找算法，目的是为了 能在p 2 p 网络中查找数据。给定一个关键字，c h o r d 可以有效地把该关键字映射到 网络中某个节点上。因而在p 2 p 网络中只要给每个数据v 都赋予一个关键字k ， 就可以利用c h o r d 在该关键字映射的节点上存储或提取相应的( k 对。 c h o r d 的突出特点是算法简单，而且可扩展。在c h o r d 中，每个关键字和节点 都分别拥有一个m 比特的标识符。关键字标识符k 通过哈希关键字本身得到，而 节点标识符n 则通过哈希节点的口地址得到。所有节点按照其节点标识符从小到 大沿着顺时针方向排列在一个逻辑的标识圆环上( 称为c h o r d 环，如图1 2 所示) 。 c h o r d 的映射规则是： n _ l 图1 2 c h o r d 环 3 电子科技大学硕士学位论文 关键字标识为k 的( k ，v ) 对存储在这样的节点上，该节点的节点标识等于k 或者 在c h o r d 环上紧跟在k 之后，这个节点被称为k 的后继节点，表示为s l l c c e s s o r ( k ) 。 因为标识符采用m 位二进制数表示，并且从0 到2 m 一1 顺序排列成一个圆圈， s u c c e s s o r ( k ) 就是从k 开始顺时针方向距离k 最近的节点。 如图卜2 所示，当标识为2 6 的节点接入时，原有标识为3 2 的节点负责的标识 为2 4 的关键字将转由新节点存储。显然，为了能在系统中转发查询报文，每个节 点要了解并维护c h o r d 环上相邻节点的标识和i p 地址，并用这些信息构成自身的 路由表。有了这张表，c h o r d 就可以在环上任意两点间进行寻路。 c h o r d 的路由如下：c h o r d 中每个节点只要维护它在环上的后继节点的标识和 i p 地址就可以完成简单的查询过程。对特定关键字的查询报文可以通过后继节点 指针在圆环上传递，直到到达这样一个节点：关键字的标识落在该节点标识和它 的后继节点标识之间，这里的后继节点就是存储目标( k 对的节点。 k a d e m l i a 【1 】协议( 简称k a d ) 是美国纽约大学的p e t a r p m a y m o u n k o v 和d a v i d m a z i e r e s 在2 0 0 2 年发布的一项研究结果。虽然k a d e m l a 和c h o r d ，c a n 或p a s t r y 一样， 都属于基于d h t 的p 2 p 网络，但是k a d e m li a 通过采用独特的异或算法作为距离计算 的基础，建立了一种全新的d h t 拓扑结构。相比于其他算法，k a d e m l i a 的路由搜索 速度有了较大的提高。因此，k a d e m l i a 被广泛地应用于文件共享系统中：例如e 叫l e 署b it t o r r e n t 。 k - b u c k e t l o l k b u 醢馥1 l k 七c k 戤f 2 l k - b u 噍e 嗵1 s 9 l h e 嬲 d i s t 暑f ：1 1 ，2 l e 豁圣- r e n t 够 1 2 15 兮，2 “1 8 0 ta i l 臣了d ) 圳 m d t r e n t v 图1 3l 锄e m l i a 路由表 4 第一章引言 在k a d e m l i a 网络中，每一个节点均维护了1 6 0 个l i s t ，其中的每个l i s t 均 被称之为一个k 一桶( k 咱u c k e t ) ，如下图所示。在第i 个l i s t 中，记录了当前节点 已知的与自身距离为从2 “i 到2 ( i + 1 ) 的一些其他对端节点的网络信息( n o d ei d ， i p 地址，u d p 端口) ，每一个l i s t ( k 一桶) 中最多存放k 个对端节点信息，注意，此 处的k 与上文所提到的复制系数k 含义是一致的；每一个l i s t 中的对端节点信息 均按访问时间排序，最早访问的在l i s t 头部，而最近新访问的则放在l i s t 的尾 部。 k a d e m l i a 的节点查询过程非常直接，其方式类似于d n s 的迭代查询： ( 1 ) 由查询发起者从自己的k 一桶中筛选出若干距离目标i d 最近的节点，并向这 些节点同时发送异步查询请求； ( 2 ) 被查询节点收到请求之后，将从自己的k 一桶中找出自己所知道的距离查询 目标i d 最近的若干个节点，并返回给发起者； ( 3 ) 发起者在收到这些返回信息之后，再次从自己目前所有己知的距离目标较 近的节点中挑选出若干没有请求过的，并重复步骤1 ； ( 4 ) 上述步骤不断重复，直至无法获得比查询者当前已知的k 个节点更接近目标 的活动节点为止j ( 5 ) 在查询过程中，没有及时响应的节点将立即被排除；查询者必须保证最终 获得的k 个最近节点都是活动的。 k a d e m l i a 的每个资源同样通过s h a 一1 得到每个资源所独有的1 6 0b i t s 的关键 字，并且k a d e m l i a 通过该关键字对该资源进行检索，具体步骤如下： ( 1 ) 计算到资源r 的距离：d ( x ，y ) = xoy ；( o 表示异或) ( 2 ) 从x 的路由表中取出最接近关键字y 的q 个节点的信息，同时进行查找关键 字操作； ( 3 ) 对接受到查询操作的每个节点，如果发现自己就是包含关键字y ，则向x 发 送资源r ；否则测量自己和t 的距离，并从自己对应的路由表中选择最接近 关键字y 的q 个节点的信息给x ； ( 4 ) x 对新接受到的每个节点都再次执行查找关键字操作，此过程不断重复执 行，直到资源r 或者路由表上每一个分支都有节点响应自己是最接近t 的。 5 电子科技大学页士学位论文 1 2 复杂搜索问题的课题意义 纯分布式p 2 p 系统已经发展了两代( 非结构化p 2 p 网络和结构化p 2 p 网络) 垆。 从网络流量和路由跳数上，结构化的纯分布式p 2 p 系统已经在很大程度上超越了 其它纯分布式p 2 p 网络系统。对于c h o r d ，t a p e s t r y ，p a s t r y ，c a n 等经典的d h t 算法，x u 【6 】以图论的方法证明了就其的路由表大小而言，它们所获得的路由效率( 即 路由跳数) 已经在数量级上达到最优，即0 ( 1 0 9 n ) h o p s 的路由跳数已经是路由表 容量为o ( 1 0 酬) 时的最优结果，并且不存在路由表容量和路由跳数均为o ( b ) 的纯 分布式网络( 其中b 为常数) 。 然而，完全基于d h t 的结构化纯分布式p 2 p 系统却几乎没有成功的实际运用案 例。这主要在于d h t 算法在提高信息检索和路有效率的同时带来了不能支持多关 键字复杂查询和拓扑结构动态维护等问题【7 1 ，其中特别是多关键字复杂查询问题， 因为经典的d h t 中的h a s h 算法本质上是将一个精确的i d 映射到对应的节点，这 样用户将只能对某种资源进行精确匹配而无法进行如模糊匹配、范围查询和多关 键字查询等复杂查询，这正是阻碍结构化的纯分布式p 2 p 系统得到成功应用的最 主要的障碍瞵】。 综上所述，结构化纯分布式p 2 p 算法已经拥有了比较出色的低网络流量和路由 跳数，其所面临的主要问题已经不是路由效率，而是关键字复杂查询和拓扑结构 动态维护等问题。其中，关键字复杂查询问题是阻碍系统可用性的最主要的问题， 实现基于结构化纯分布式p 2 p 网络的复杂搜索，是促使结构化纯分布式p 2 p 系统 得到成功应用的关键问题之一。结构化纯分布式p 2 p 系统的复杂搜索算法在形式 上可以分为以下两个大类：基于d h t 的复杂搜索算法和基于新拓扑结构的结构化 网络复杂搜索算法。接下来本文将对这两类算法进行深入的分析。 1 2 1 结构化p 2 p 复杂搜索机制国外研究现状 1 2 1 1 基于经典d h t 的复杂搜索扩展 由于经典d h t 算法在路由跳数和网络流量上已取得较大的成功，早期的复杂 搜索的研究大多是围绕d h t 算法展开的，其基本思想是在d h t 的逻辑拓扑结构之 上再构建某种形式的覆盖网络( o v e r l a yn e t w o r k ) ，以反映文档间的相似聚类信 息以便进行复杂搜索。 6 第一章引言 在2 0 0 2 年，a n d r z e j a k ，x u 等人首次提出了如何将资源范围映射到d h t 节点 空间上的方法【9 】。他们的研究基于经典的c a n 算法，通过将一种特殊的空间填充曲 线( 希尔伯特曲线) 映射到c a n 算法的拓扑结构之上，从而在d h t 算法上维护了 两个文档相似聚类特性： ( 1 ) 邻近的资源范围映射到邻近的c a n 区域； ( 2 ) 如果一个资源范围分裂成为两个子范围，那么原来资源范围的c a n 区域也 分裂为两个子范围的区域。 通过将相似的文档映射到临近的c a n 区域，该算法可以支持资源范围查询 ( r a n g eq u e r y ) 等复杂搜索。之后的文献【l o 】同样借助了这一思想，他们的研究基 于经典的c h o r d 算法。不同于文献 9 】的算法，文献【1 伽将d 维空间的希尔伯特空间填 充曲线映射到了c h o r d 一维索引之上，这样一种映射结构赋予了该算法进行多属 性搜索的能力。 文献【l l 】提出了另一种将资源范围映射到d h t 节点空间上的方法，类似于文献【1 0 】 中的算法，他们的研究同样基于经典的c h o r d 算法。不同于空间填充曲线，他们 提出了一组特殊的局部性敏感的h a s h 函数( 1 0 c a li t ys e n s i t i v eh a s hf u n c t i o n s ) 将相似的资源范围映射到c h o r d 算法相邻的节点空间中，从而可以支持范围搜索 等复杂搜索。该算法拥有较好的路由性能，在他们所做的1 0 0 0 个节点的仿真环境 中，其路由跳数分布与精确匹配的c h o r d 算法非常相似，但其负载平衡能力比较 差，负载最小的节点和最大的节点其负载差了两个数量级。 以上两种基于将相似资源范围映射到某种d h t 算法相邻节点空间的方法，虽 然部分地解决了范围搜索或多属性搜索等复杂搜索等缺陷，但也存在另一些问题。 主要的问题在于范围h a s h 所带来的负载平衡和路由跳数之间折衷。文献【1 2 】论述了 基于d h t 的方法本质上就不适合作为范围搜索，d h t 算法的随机h a s h 函数与范围 搜索相抵触，范围h a s h 要求必须预划分，如果预划分过大的范围h a s h 会产生严 重的负载平衡问题；而如果预划分过小，可能会出现过多的路由跳数。 由于基于范围h a s h 的办法自身的局限性，一些研究探索了在d h t 拓扑结构上 建立某种语义索引的方法。 基于d h t 的前缀h a s h 树是在d h t 的逻辑拓扑结构之上创建某种语义覆盖网络 的一种尝试，r a t n a s a m y 等算法【1 3 】【1 4 】按文档间的相似性构建了一棵能够映射到任 意d h t 结构上的前缀h a s h 树，其初步分析表明前缀h a s h 树能较好地支持范围搜 索，并具有双对数复杂度的搜索时间，负载平衡以及容错能力。 p s e a r c h 【1 5 】【1 6 】【1 7 】和e s e a r c h 【1 8 】贝0 是在d h t 的逻辑拓扑结构之上创建某种语义覆 7 电子科技大学硕士学位论文 盖网络的另一类方法。它们首先利用空间向量模型建立文档间的语义索引，然后 将其映射到d h t 逻辑拓扑结构上，e s e a r c h 基于经典的c h o r d 算法，而p s e a r c h 则 基于经典c a n 算法。根据作者的初步分析结果，基于空间向量模型语义索引的 p s e a r c h 和e s e a r c h 较好的实现了范围搜索和部分匹配。 以上几种基于语义索引的方法虽然部分地解决了范围搜索或多属性搜索等复 杂搜索问题，但也存在许多问题。由于它们的基本思想均是首先按文档的相似聚 类信息构建某种基于语义的索引，然后直接映射到了d h t 的拓扑结构上，这样必 须进行两次索引查找，在支持复杂搜索时，其真正能支持范围搜索或多属性搜索 的部分只能在高层的语义索引上进行，当在高层语义索引上通过复杂搜索得到一 组相近的资源时，对每个具体资源的获取通常还必须进行一次d h t 算法的路由查 询，当相似资源较多时，其效率是很低的。表卜1 总结了各种基于d h t 的复杂搜 索算法的特点。 表卜l 基于d h t 的复杂搜索算法及其分析 所基于的 算法基本思想所支持的复杂搜索主要问题 d h t 结构 a n d r z e j a k 空间填充曲线 c a n 范围搜索负载平衡 等 s c l i i l i d t 等空间填充曲线 c h o r d 范围搜索、多属性搜索负载平衡 1 0 c a l i t y g u p t a 等 s e n s i t i v eh a s h c h o r d 范围搜索负载平衡 f u n c ti o n s r a t n a s 锄y基于语义索引的任意d h t 算 每个相似资源 等前缀h a s h 树 法 范围搜索都需要一次d h t 路由查询 p s e a r c h 空间向量模型c h o r d范围搜索和部分匹配同上 e s e a r c h 空间向量模型 e c a n 范围搜索和部分匹配同上 1 - 2 1 2基于新拓扑结构的结构化p 2 p 网络复杂搜索算法分析 所谓新拓扑结构，就是专门为复杂搜索而设计出的拓扑结构。由于经典d h t 算法在本质上就不适合支持范围搜索、多关键字等复杂搜索，很多研究开始探索 其它索引结构以实现复杂搜索。 文献f 1 9 】试图在保持关键字顺序的s k i p l i s t 数据结构基础上建立一个结构化纯 分布式p 2 p 系统，称为s k i pg r a p h 。在s k i pg r a p h 算法中，由于使用关键字有 序的s k i p l i s t 数据结构而不使用散列函数，因而与d h t 相比，s k i pg r a p h 能更有 第一章引言 效地支持范围搜索等复杂搜索。然而s k i pg r a p h 算法也有显著的缺陷，由于s k i p g r a p h 算法具有过多的结点间冗余链接，在带来结点故障容忍能力的同时，当节点 频繁加入和退出时产生了较严重的结构维护问题，并且由于缺乏为节点分配文档 键值的算法；同时，s k i pg r a p h 还存在全局负载平衡以及相邻文档键值间节点距 离较大等问题。一些较新的s k i pg r a p h 改进算法【2 0 1 【2 1 1 部分减轻了这些问题，文献 【2 0 】提出了两个s k i pg r a p h 的结构，一个对数据进行索引而另一个跟踪系统中每一 个节点的负载，这样每一个节点都能测定它的邻居节点的负载以及系统中负载最 重和最轻的节点。文献【2 1 】贝0 在s k i pg r a p h s 结构外新增了一层“桶层 ( b u c k e t l a y e r ) ，每一个节点负责一组b u c k e t s ，每一个b u c k e t 推举一个所代表的键值， 这样节点间能局部的平衡它们的负载。该算法虽然部分的减轻了s k i pg r a p h s 所 存在的问题，但s k i pg r a p h 依然存在以下一些难以克服的困难： ( 1 ) 结点之间冗余链接过多，s k i pg r a p h 算法至少需要0 ( n 1 0 9 n ) 条链接，从 而带来拓扑结构维护困难； ( 2 ) s k i pg r a p h 算法大多要求每个结点只存放一个数据项，这通常不满足实际 需要。 m e r c u r y 【2 l 】【2 2 】是探索以新的结构化拓扑结构支持复杂搜索的另一种尝试。在 m e r c u r y 之中，节点被组织成为不同的逻辑属性中心，每一个逻辑属性中心负责不 同的搜索属性。与s k i pg r a p h 一样，m e r c u r y 也回避了使用d h t 散列的方式，而 是将属于一个逻辑属性中心的节点被组织成一个环，使用k 步距离链接( k 1 0 n g d i s t a n c el i n k s ) 有效地在逻辑属性中心内路由。m e r c u r y 将资源信息复制 到各个属性中心上，当解析多数性搜索时，从待搜索的属性中选择一个属性，使 得对此属性进行区段搜索时需要访问的节点数最少，请求查询被送到此属性对应 的属性中心上，从而有效的支持多属性的范围搜索，并且由于m e r c u r y 利用了随 机样本估计节点间的平均负载以及整个网络中负载较轻的部分，因而m e r c u r y 算 法也具有较好的负载平衡能力。m e r c u r y 算法的主要问题是每个节点必须维护所属 属性中心的k 个节点的指针和其它每个属性中心中任意节点的指针，这在属性较 少的网络环境下可能有较好的结果，但在搜索属性很多的大规模结构化p 2 p 网络 中，每个节点将必须维护过多的指针，当节点频繁加入和退出时可能会产生较严 重的拓扑结构维护问题。 类似于前缀h a s h 树算法，p g r i d 【2 3 】尝试建立一棵基于语义的二进制搜索树以 支持复杂搜索。在p g r i d 系统中，节点间每次相遇就交换双方的信息，从而对搜 索空间不断进行分割，使每个节点负责管理某一区间上数据信息并负责响应针对 9 电子科技大学硕士学位论文 这些数据的查询请求，最终搜索空间的划分状态在逻辑上可以用一棵二进制搜索 树表示。在此基础上，信息的搜索就可描述为二进制搜索树的查找过程，相邻子 树保存了相邻数据的信息，从而较有效的支持范围搜索。然而p 嘶d 算法假设了 每个节点具有固定的性能，这与真实网络环境有较大的差异，并且由于p 嘶d 算 法基于前缀树的数据组织方式，节点间的数据分布差异较大，可能造成突出的负 载平衡问题。 文献【2 4 】提出了一种基于d p m s ( d i s t 曲u t e dp a t t e mm a t c h i i l gs y s t e m ) 的d h t 复 杂搜索解决方案。在d p m s 中，所要发布的资源的关键字在节点中重复存储并且 以层次的方式聚集( 如图1 4 所示) 。重复存储方式方式提高了某些节点离线时资 源的可能性和整个d h t 网络搜索的弹性，而层次聚集方式减少了存储的开销。在 d h t 的拓扑结构维护良好的情况下，d p m s 总体上可以获得一个较高的性能( o ( 1 0 9 n + 1 0 9 ( n ( 1 0 9 n ) ) ) 的搜索时间复杂度) 。然而，该d h t 系统的维护代价是高 昂的，每个节点不仅需要维护三个表，并且在节点不断进出该p 2 p 网络的情况下， 网络的拓扑结构会受到破坏。 irqrr2象 ? | i 袁衾竣磊 7 乃 i 爻圣 7 i、八 l j 上l ljrj1，r1 ，1 r1 r1 - 图1 _ 4d m p s 的结构 其中，表1 2 总结了各种基于新拓扑结构的结构化网络复杂搜索算法。 l o 第一章引言 表1 2 基于新拓扑结构的结构化网络复杂搜索算法及其分析 算法基本思想所支持的复杂搜索主要问题 s k i pg r a p hs k i p l i s t范围搜索拓扑结构维护困难 m e r c u r y多个环状属性中心范围搜索、多属性搜索拓扑结构维护困难 基于语义的二进制搜 p g r i d 范围搜索负载平衡 索树 以树状聚集，重复发 d p m s 多属性搜索 拓扑结构维护困难 布语义 1 2 2 结构化p 2 p 复杂搜索机制国内研究现状 国内在也开始研究结构化p 2 p 复杂搜索机制，2 0 0 7 2 发表的文献【2 5 】提出了 b m p ( b e n e f i tb a s e dm u l t i k e y w o r dp r o c e s s i n gs t r a t e g y ) 算法。该算法不仅对 每个节点和资源进行分组，并且考虑了如何优化一个组内的结构。采用了纳什均 衡来构建一个基于关键字之间的关联和节点覆盖度的优化的对等方节点分组。因 此，b m p 机制可以构建一个搜索结果和带宽使用率上优化之间相互妥协的优化的 p 2 p 复杂搜索机制。一个根据纳什均衡优化的对等方分组的定义为：假设一个包含 s 个对等方的分组p g ，p g = p l ，p s ：b 1 ，b s ) ，如果每个节点f 分配于分 组 暑+ ，e ，彳) ，则满足式( 3 ) ： 6 f ( 彳，e ) 6 z ( 巧，艺) ，v f 公式( 卜1 ) 假设节点己打要查找包含关键字t l 的资源，其资源查找步骤如下： 1 只甜首先计算关键字t 1 的哈希值k e y l ，通过式( 3 ) 找到与关键字k e y l 所在的 最佳对等节点分组p 1 。 2 和其他d h t 的单关键字迭代搜索算法不同的是，b m p 算法是在最优化节点分组 p 1 进行广播查找关键字t 1 。 3 如果该查询中包含多个关键字，则通过布隆过滤器的“与”为运算来进行并行 的查询。 4 如果分组p 1 未能检索到关键字t l ，那么就通过关键字t 2 定位最优化的节点 分组p 2 ，然后执行步骤3 。 在该文献中的实验结果表明，该算法运行过程中，只有很小的概率运行步骤4 ， 因此，该策略可以在一定程度上降低通信量和搜索所需要的时间。 d h t 搜索的节点分组策略可以在一定程度上提高多关键字检索的效率。但是， 该策略最大的一个缺点是随着节点数的增加，在同一个分组内的节点数同样会增 电子科技大学硕士学位论文 多，然而在一个节点分组内的却仍然是使用洪泛查询的搜索策略。因此，节点分 组的资源检索方式只能适合于节点数较少的情况，在节点数较多的情况下和非结 构化网络相比，性能改进不多了。 1 2 3当前复杂搜索机制研究方法的分析与展望 当前各种尝试在结构化纯分布式p 2 p 网络中支持复杂搜索的主要算法在上面 进行了初步的分析，其中主要可以分为基于d h t 的复杂搜索算法和其它新拓扑结 构的复杂搜索算法。然而，如果仔细地分析这些各种看似拓扑结构间有很大差异 的算法，可以发现这些算法按索引方式大致可以分为以下4 类： ( 1 ) 完全物理节点索引：将物理节点空间组织成一个逻辑上具有某种拓扑结构 的网络，其代表就是经典的d h t 算法如c h o r d 【4 】，c a n 【5 1 ，p a s 一2 1 等，这 类只将资源i d 精确映射到某个物理节点上而不考虑任何资源内部的关系即 资源内容索引的算法无法实现复杂搜索。 ( 2 ) 完全的内容索引：使用如层次树、二进制搜索树、层次聚类等办法为资源 内容建立内容索引结构，而查找则直接在二进制搜索树等内容索引上进行。 像p 。g r i d 阻】等算法即是这类算法的代表，其优点是在内容索引上能很好的 支持像范围搜索等复杂搜索，但由于缺乏对物理节点的有效组织，无法将 资源合理地分配到物理节点之上，难于解决负载平衡问题。 ( 3 ) 内容索引向物理节点索引的直接映射：最初的很多试图在d h t 之上直接支 持复杂搜索的算法大多属于这类算法，如使用范围h a s h 的a n d r z e j a k 算法【7 】、 p a m s h a r 【8 1 算法和g u p t a 【9 】算法，以及试图建立语义索引的p s e a r c h 【1 3 】【1 4 】【1 5 】、 e s e a r c h 【1 6 】算法r a t n a s 锄一1 1 】【1 2 】都属于这类算法。这类将内容索引直接向物 理节点索引映射的方式能直接有效的支持复杂搜索，但是上述其物理节点 索引采用的均是d h t 算法，由于范围h a s h 与复杂搜索的固有矛盾，其在负 载平衡和路由跳数上存在折衷的问题。 ( 4 ) 将内容索引同物理节点索引相结合的方式：s k i p 鲫h 【1 7 】和m e r c u 2 0 】【2 l 】算 法有些类似这种思想，其拓扑结构的组织某种意义上既是内容索引又是物 理节点索引。虽然还存在一些问题，但这应该是非常有前途的方法，前面 的分析表明，前3 类算法存在的问题是由于单一索引结构或直接映射所造 成的，如果能将内容索引同物理节点索引结合起来，上述算法的问题则可 以克服。表1 3 给出了当前复杂搜索研究方法基本思路及其评价。 1 2 第章引言 表1 3 当前复杂搜索研究方法基本思路及其评价 基本研究思路所属算法 算法特性 算法分析及评价 完全物理节点c h o r d ，c a n ，p a s t r y 等经典 将资源i d 精确映射到 缺乏内容索引信息，难于 某个物理节点上而不考 索引d h t 算法实现复杂搜索。 虑任何资源内容索引 只为资源内容建立内容 缺乏对物理节点的有效 完全内容索引p g r i d 等 索引结构，查找直接在 组织，难于解决负载平衡 内容索引上进行问题 内容索引向物 范围h a s h 的a n d r z e j a k ， 由于d h t 与范围搜索的固 理节点索引的 p a r a s h a