（计算机应用技术专业论文）基于tapestry构建p2p资源搜索系统的研究.pdf

摘要 随着存储空间的增大和存储价格的下降，即使是一个较小的p 2 p 用户群 也会共享大量的数据。大量的共享资源使得p 2 p 系统吸引了大量的用户，但 困难的是如何在大量的共享资源中寻找用户想要的资源。 本文在分布式散列表( d h t ) 思想的基础上，设计并初步实现了一个基于 元数据的对等信息系统m p i s ( m e t a d a t a b a s e dp e e r t o p e e ri n f o r m a t i o n s y s t e m ) 。由于网络资源具有多样性和复杂性，为了准确表述用户对资源的 要求，也为了使系统返回给用户的结果能更好的满足用户需求，需要用多个 属性从不同角度描述资源，从而构成这个资源的元数据。利用d h t 可以将单 个键映射到网络中节点的特点，在发布资源时，m p i s 将资源的各个属性对应 的倒排索引发布到特定的节点；在搜索资源时，用户根据实际需要指定一个 或多个资源属性值作为搜索条件，m p i s 根据用户指定的各个属性搜索条件将 搜索请求路由到存放各个属性倒排索引的节点，并将多个属性值对应的倒排 索引求交集以使得结果满足用户的所有条件。我们利用t a p e s t r y 的d h t 模块， 采用j a v a 语言，实现了一类比较典型的带有元数据的资源( m p 3 音乐文件) 的 发布和搜索。对于搜索时经常起使用的属性，我们使用组合属性的方法进 行发布和搜索，从而减少了倒排索引传递时的网络传输和求交集时的c p u 周 期。考虑到属性的同义性和近义性，我们在系统中建立常用的近义词库来扩 展搜索的范围。另外我们使用虚节点的方法模拟大盘节点来检验我们的系 统，并且这种方法在一定程度也可以起到负载平衡的作用。 论文首先介绍了p 2 p 的基本概念，然后从结构角度出发分别介绍了四类 搜索技术并对其各自的优缺点进行了介绍：接着研究了如何基于t a p e s t r y 构 建p 2 p 资源搜索系统；随后详细叙述了m p i s 的设计方案和实现的关键方法； 最后实验性地使用m p i s 发布和搜索一些资源，分析m p i s 的效率以及其他一 些相关问题，展现了m p i s 的实用性。 羡键词：对等网络；s p i d e r ；分布式散列表；m p i s ；元数据；资 源发布；资源搜索 r e s e a r c ho nb u i l d i n gp 2 ps e a r c hs y s t e m b a s e do nt a p e s t r y a b s t r a c t a l o n gw i t ht h ea u g m e n t a t i o no fs t o r i n gs p a c ea n dt h ed r o po fs t o r i n gp r i c e ， e v e ni fas m a l lg r o u po fp 2 pu s e r sc a ns h a r eag r e a td e a lo fr e s o u r c e sa sw e l l a b u n d a n ts h a r e dr e s o u r c e so fp 2 ps y s t e m sa t t r a c tl a r g ea m o u n to fu s e r s ，b u ti t i sd i f f i c u l tt of i n dd e s i r a b l er e s o u r c e sf r o mt h eh u g ea m o u n to fr e s o u r c e s b a s e do nd i s t r i b u t e dh a s ht a b l e ( d h t ) i d e a ，am e t a d a t a b a s e dp e e r t o - p e e r i n f o r m a t i o ns y s t e m ( m p i s ) i sd e s i g n e da n di m p l e m e n t e di nt h i sp a p e r b e c a u s e o ft h ed i v e r s i t ya n dc o m p l e x i t yo fn e t w o r kr e s o u r c e s ，i ti s n e c e s s a r y t o c h a r a c t e r i z ee a c hr e s o u r c ew i t hs e v e r a lp r o p e r t i e sf r o mv a r i o u sp o i n t so fv i e ws o a st oe x p r e s su s e r s r e q u i r e m e n t sm o r ea c c u r a t e l ya n dt om a k et h es e a r c hr e s u l t m e e tt h eu s e r s r e q u i r e m e n t sb e t t e r ，a n dm e t a d a t ai sf o r m e da sar e s u l t u s i n gt h e a b f l i t yo fd h t t h a ti ti sa b l et om a pas i n g l ek e yt oap e e ri nt h en e t w o r k ，a n d m p i sp u b l i s h ；t h ei n v e r t e di n d i c e so fe a c hp r o p e r t yt oc e r t a i np e e r sr e s p e c t i v e l y w h i l el i s t i n gr e s o u r c e s ，a n dr o u t e st h es e a r c hr e q u e s tt ot h e s ep e e r sp o s s e s s i n gt h e i n v e r t e di n d i c e sa c c o r d i n gt og i v e ns e a r c h i n gc o n d i t i o n so f e a c hp r o p e r t yw h i l e s e a r c h i n gr e s o u r c e s i t sr e q u i r e df o rm p i s t oc o l l e c tt h ei n v e r t e di n d i c e so fe a c h p r o p e r t ya n dc o m p u t et h ei n t e r s e c t i o no ft h e ma st h er e s u l to fs e a r c h b a s e do n d h tc o m p o n e n to ft a p e s t r y ，w ei m p l e m e n t e dt h ep u b l i c a t i o na n ds e a r c ho fa c l a s so ft y p i c a lr e s o u r c e st h a t p o s s e s sm e t a d a t a ：m p 3a u d i of i l e , i nt h e e n v i r o n m e n to fl i n u xu s i n gj a v ap r o g r a m m i n gl a n g u a g e a st ot h o s ep r o p e r t i e s t h a ta l w a y sa r eu s e dt o g e t h e rw h i l es e a r c h i n gf o rr e s o u r c e s ，w ea d o p tc o m b i n e d p r o p e r t i e sm e t h o dt op u b l i s ha n ds e a r c hf o rr e s o u r c e s w es t o r eg r o u p s o f s y n o n y m si no u rs y s t e ms oa st oe x p a n dt h es c o p eo fs e a r c h i n g u s i n gv i r t u a l n o d e s ，w es i m u l a t em a n yp e e r st oc h e c ko u rs y s t e m ，a n dt h i sw a ya l s oh a st h e f u n c t i o no fl o a d b a l a n c e m e n t i nt h i sp a p e r , w ei n t r o d u c et h ec o n c e p t i o no fp 2 p ，s u r v e yt h es e a r c h i n g m e t h o d so fv a r i o u sp 2 pm o d e l sa n da n a l y z et h ea d v a n t a g e sa n dd r a w b a c k so f e a c hm e t h o df i r s t l y t h e nw es t u d yh o wt od e v e l o pa p p l i c a t i o n so nt h eb a s i so f t a p e s t r y a f t e rt h i s ，w ed e s c r i b et h ed e s i g ns c h e m ea n di m p l e m e n t a t i o no fm p i s i nd e t a i l a tl a s tw e p u b l i s ha n ds e a r c hs o m er e s o u r c e su s i n gm p i sa se x p e r i m e n t ， s oa st oa n a l y z et h ee f f i c i e n c ya n ds o m eo t h e rp r o b l e ma n ds h o wt h eu s a b i l i t yo f m p i s k e yw o r d s ：p e e r - t o p e e r p 2 p ) ；s p i d e r ；d i s t r i b u t e d k s ht a b l e ( d h t ) ； m e t a d a t a - b a s e dp e e r - t o - p e e ri n f o r m a t i o ns y s t e m ( m p i s ) ； m e t a d a t a ；r e s o u r c ep u b l i c a t i o n ；r e s o u r c es e a r c h 基j 二t a p c s t r ) _ 掏建p 2 p 资源搜索系统的研究 1 1 选题的背景和意义 第1 章绪论 p 2 p 是英文“p e e r - t o p e e r ”的缩写，称为对等网或点对点技术，p 2 p 是一 种分布式技术，不同于c l i e n t s e r v e r , b r o w s e r s e r v e r 等传统模式，它抛开了 应用服务器的束缚，使得网络中的节点以种对等的方式共享这些节点的存 储空间、处理器的计算能力、网络带宽等资源。一方面节点自】可以直接进行 交互，不再需要服务器作为媒介进行中转，从而使交流更直接，效率更高； 另一方面节点不再依赖中央服务器，从而解决了因服务器能力不足而引起的 性能瓶颈问题，增强了系统的可伸缩性，同时也避免了因中央服务器的失败 而导致的整个系统无法工作的可能性，使得系统的可靠性更强。p 2 p 技术最 初用于音乐文件共享，随着技术的发展逐步扩展到普通的数据文件共享、分 布式计算、通信和协作等多个应用领域。 许多数字信息( 如图片、音乐、录像、演示文稿等) 都不在大型服务器上， 用户想要交流的人也不是坐在大型服务器后面。信息和通信的大部分都在个 人计算机上，也就是i n t e r n e t 对等设备上。p 2 p 的目标就是使用户获得信息并 联系到最关心的人。 随着存储空间的增大和存储价格的下降，即使是一个较小的用户群也会 共享大量的数据。例如n a p s t e rm p 3 音乐文件共享系统1 9 9 9 年9 月出现。蛰 2 0 0 0 年中时用户数就已经超过2 0 0 0 力。即便每个用户共事一些文件，整个用户群 所共享的文件数也是千力数量级的。资源共享的前提是资源的搜索和发现， 大量的共享资源使得p 2 p 系统吸引了大量的用户，但困难的是如何在大量的 共享资源中寻找用户想要的资源。 1 2 研究现状 由于p 2 p 蕴含着巨大的技术潜力和商业价值，许多学术机构、大公司 先后投入到对p 2 p 技术的研究之中。要想充分的利用p 2 p 网络上的资源， 首先要有效的发现需要的资源，即在p 2 p 网络中进行搜索。目前，p 2 p 研 犟pt a p v s c r ) 掏建p 2 p 资源搜索系统的研究 究中的一个主要问题就是搜索问题。 在p 2 p 系统中，资源分散在各个节点上。节点频繁的加入或退出，p 2 p 系统处于不断的变化之中。p 2 p 系统的规模一般都很大，而且会不断扩展。 由于p 2 p 系统的可扩展性，节点的不确定性，设计一个好的搜索机制比较困 难。最早的n a p s t e r n 系统采用集中式的结构来进行搜索，中央服务器保留 了所有资源的索引，节点( p e e r ) 通过向中央服务器搜索索引然向别的节点请 求获取资源，n a p s t e r 的组织结构决定了它的可靠性和可伸缩性不太好。 c h o r d g ，c a n n o ，p a s t r y 1 2 等采用分布式敖列表( d h t i i s ，d i s t r i b u t e d h a s ht a b l e ) 的方法来实现资源的搜索，这类系统又称为结构化的p 2 p 系统。 这类系统对各共享资源的标识进行散列，将所有共享资源映射到一个散列空 间，并且对各个节点也进行相同的敫列，将所有节点也映射到同样的散列空 间，从而在资源和节点之问建立一种对应关系。在用户给定一个资源的标识 后，对该标识进行散列就可以快速而准确地定位到负责该资源的节点。但在 这类p 2 p 系统中，如果不知道要访问资源的标识，将无法定位和访问该资源。 因此从本质上说，这样的p 2 p 系统只是在资源标识与资源位置之i 日j 的一种映 射，并不真正具有搜索功能：另一方面，由于网络中资源的多样性和资源本 身的复杂性，仅仅用一个标识很难去标识一个资源。由于不支持复杂查询， 严重制约了这种搜索方法的发展。非结构化p 2 p 网络采用泛洪( f l o o d i n g ) 的 方法进行搜索，例如g n u t e l l a 2 ，一个节点向所有邻居节点广播查询消息， 邻居节点再向自己的所有邻居节点广播，就这样向外洪泛扩张。这种模型本 身因为采用应用层广播的协议，导致消息量过大，网络负担过重，使得性能 较差的节点很快就成为整个系统的瓶颈；但是这种方法具有节点覆盖率高， 健壮性好以及实现简单的优点，更重要的是搜索时理论上可以使用任何的匹 配方法，例如基于关键字的全文搜索，只要各个节点将本节点满足搜索请求 的结果返回给请求的源节点即可。算法方面新近提出的方法有迭代泛洪方法 ( i t e r a t i v ef l o o d i n g ) 、本地索引方法( l o c a li n d e x ) 、随机游走搜索方法 ( r a n d o mw a l k ) 以及基于移动a g e n t 的搜索方法等。 混合式p 2 p 网络主要是提出了超级节点的概念，利用超级节点作为高速 转发层来进行搜索，典型的有k a z a a 。 2 基于t a p e s t r y 句建p 2 p 资源搜索系统的研究 1 3 本文的解决方案 虽然现有的基于d h t 的p 2 p 系统不具有搜索功能，但是它提供了一种机 制，允许将单个的键映射到网络中的节点。 本文在d h t 的基础上，设计并初步实现了一个基于元数据的对等信息系 统m p i s ( m e t a d a t a - b a s e dp e e r - t o p e e ri n f o r m a t i o ns y s t e m ) ，它能够根据资源的 多个属性来定位所需资源。m p i s 对于多个属性描述的资源，预先生成资源各 属性与资源标识相对应的倒排索引。利用d h t 可以将单个的键映射到网络中 的节点的特点，m p i s 将资源的各个属性对应的倒排索引存放到特定的节点， 以及根据用户指定的属性搜索条件将搜索请求路由到存放该属性倒排索引 的节点。对于搜索时经常起使用的属性，m p i s 使用组合属性的方法进行发 布和搜索，从而减少了倒排索引传递时的网络传输和求交集时的c p u 周期。 考虑到属性的同义性和近义性，m p i s 在系统中建立常用的近义词库来扩展搜 索的范围。另外m p i s 可以在一个物理节点启动多个逻辑节点，这种虚拟节点 方法可以用来平衡负载。 在原有的基于d h t 的p 2 p 系统中，每访问一个资源都需要提供该资源的 标识。由于网络中资源的种类和数量同渐庞大，原来的d h t 系统的工作方式 在某些情况下使得用户无法得到想要的资源。例如用户要寻找网络中所有王 菲的歌曲，在用户不知道歌曲名称( 更何况网络中许多歌曲文件并不是以歌 曲名称作为文件名存储) 的情况下，将无法访问到这些文件。即便用户知道 所有歌曲名称，让用户根据歌曲名称逐个搜索也是不合理的。 而m p i s 很好的解决了这类问题，在m p i s 中，只要用户提供一个或者多 个属性的属性值，则不论用户是否知道资源的标识，不论资源以何种形式存 在。都可以搜索到所有符合条件的资源。这使得m p i s 所能发布和搜索的资源 的类型更广泛、更灵活。例如用户不需要知道王菲的“唱游”专辑罩的歌曲 名称，不需要知道这些歌曲文件是m p 3 格式或者r a l n 格式还是别的什么格式， 不需要知道文件名是“红豆m p 3 ”还是“c h a n g y o u 0 7 m p 3 ”，只要提供歌 手和专辑这两个属性值，就可以获得该专辑的所有歌曲。因此m p i s 的搜索能 力是显著的，更能满足用户的各种搜索需求。 m p i s 是基于t a p e s t r y 的d h t 模块开发的，因此m p i s 也具有d h t 系统所具 琏十t a p e s t r y 构建p 2 p 资源搜索系统的研究 有的高搜索效率和强可伸缩性。与集中索引方式相比较，它不具有单点失败 的缺点，并且可伸缩性更强。与泛洪请求模型比较，它的消息路由更有目的 性，相对于所需消息量来说搜索效率更高。相对于原有的d h t 系统来说， m p i s 具有良好的搜索能力。除此之外，m p i s 采用近义词库使得搜索具有一 定的语义性，它还使用组合属性的方法提高搜索的效率，并且它使用的虚拟 节点方法可以作为负载平衡的途径。 1 4 论文的组织结构 第二章首先介绍p 2 p 相关知识，然后研究现有的各种p 2 p 系统的搜索技 术，并分析各自的优缺点。第三章研究了如何基于t a p e s t r y 构建p 2 p 应用系 统。第四章详细叙述了m p i s 的设计以及完善m p i s 系统的方案。第五章实 验性地使用m p i s 发布和搜索一些资源，检验了m p i s 的实用性以及其他一 些相关问题。第六章总结了整篇论文并且指出了m p i s 进一步完善的方向。 4 蟮十t a p e s t r y 勾建p 2 p 资源搜寮系统的研究 第2 章p 2 p 概述及搜索技术 2 1p 2 p 介绍 2 1 1p 2 p 的基本概念 p 2 p 是p e e r - t o - p e e r 的缩写，p e e r 在英语中的解释是“伙伴”的意思， p 2 p 可以理解为“伙伴对伙伴”的意思，或称为对等联网。p 2 p 最仞的起源 是联网通信方式，是一种比较古老的技术，如产生于1 9 7 9 年的u s e n e t 1 9 8 4 年的f i d o n e t 都是基于p 2 p 技术的，但是目前p 2 p 己被赋予了新的含义， 是旧有技术的新的应用模式。 p 2 p 的原意是一种通信模式，在这种通信模式中，每一个部分具有相同 的功能，任意一个部分都可以开始一次通信。现在对p 2 p 概念进行了扩展， 如i b m 公司认为：p 2 p 系统若干互联协作的计算机构成，且至少具有如下 特征之一：系统依存于边缘化( 非中央式服务器) 设备的主动协作，每个成员 直接从其他成员而不是从服务器的参与中受益；系统中成员同时扮演服务器 与客户端的角色；系统应用的用户能够意识到彼此的存在，构成一个虚拟或 实际的群体。 对等网络尚无统一的标准。2 0 0 0 年8 月成立了p 2 pi 作组，成员包括 i n t e l 、i b m 和h p 公司等。发展对等网络的其他主要障碍还有版权问题、网 络带宽问题、管理问题和安全问题等。如何连接电话、手机和家电、工业设 备等，也是对等网络需要解决的问题。当然p 2 p 也有一些缺点。由于大多数 p 2 p 应用程序都缺乏集中性，这使得对p 2 p 应用程序的预测很困难，因而具有 不町预见性。有些p 2 p 应用程序依赖匿名的对等设备，这些对等设备对共享 的内容或者提供的服务不具有任何的验证和认证水平，例如一首杯题为“好 听的歌m p 3 ”的歌不见得就好听，甚至于根本不是一首歌，p 2 p 内容不可思 议的膨胀使得对信息的验证和维护变得极其困难。 2 1 2p 2 p 的分类 p 2 p 模型从结构上可以分为四类：集中式，结构化，非结构化和混合式。 集中式的趣犁代表皋n a p s t e r l l j ，它的名字虽然叫做集中式，但这里集中的只 基十t a r r y 构建p 2 p 资源搜索系统的研究 是索引。结构化的p 2 p 有c h o r d 【9 】，p a s t r y 1 2 ，c a n 1 0 等，它们主要是对 资源和节点采取一定的方式进行处理，使节点和资源变得有序可寻，通过服 务器来进行搜索资源。 非结构化的p 2 p 主要代表是g n u t e l l a 2 l ，它是p 2 p 最能体现p 2 p 特点的 一种结构，网络上没有服务器，网络拓扑是一个分散的状态。通过基于对等 网的客户端软件搜索网络中存在的对等节点( p e e r ) 。 混合式的p 2 p 网络选择了一些性能比较高的节点作为超级节点( s u p e r n o d e ) ，这些超级节点存储了其他一些节点( p e e r ) 的信息。由超级节点作为小 的服务器来处理属于自己那部分节点的信息，同时超级节点之间也协同处理 一部分信息。从应用程序角度来说，主要有三种类型的p 2 p 应用程序。 i ) 并行的。并行的p 2 p 程序把一个大的任务分解成一些可以并行的运行 于许多独立的p e e r 节点上的子任务。大多数使用这类模型的应用程序都是 计算集中的程序。隐藏在这些程序背后的思想是，连接在i n t e r n e t 节点上 的任何一台计算机的空闲周期都可以被利用，用来解决那些需要大量计算的 困难问题。通常束说，相同的任务会在不同的p e e r 上使用不同的参数来运 行。这一类的例子包括搜索外星生命、破解密码、市场和债务的价值计算和 人口统计分析。 2 ) 内容和文件管理。内容和文件管理的p 2 p 程序主要用来向网络中不同 的p e e r 上存储信息，以及从这些p e e r 里搜索信息。这类程序所使用的模型 就是内容交换模型。像n a d s t e r 和g n u t e l l a 这样的程序允许p e e r 搜索和下 载其他p e e r 共享出来的文件( 主要是音乐文件) 。对于它们当中的大多数来 讲，当l ； 的程序还没有对如何提供可靠性做出保证，它们依赖用户来对诸如 应该从哪儿下载以及当下载失败时应该从哪儿开始重新尝试这类问题做出 判断。它们充分利用空闲的存储空间，作为用户的s e r v e r 。这些程序必须用 更传统的数据库技术例如冗余来保证可靠性，很多研究项目都探索了p 2 p 文 件系统的基础。另外，过滤和挖掘的程序例如o p e n c o l a 5 j 和j x t as e a r c h 已经出现，这些程序侧重于用来在p 2 p 网络上建立供查询用的索引条目所采 用的合作过滤技术。像j x t a 搜索这样的技术可以与像g n u t e l l a 这样的程序 结合，在大量的分稚式的信息中查找到更新的东婚。 6 肇ft a p e s t d 构建p 2 p 瓷源搜索系统的研究 3 ) 合作类型。合作p 2 p 程序允许用户实时的合作，不依赖于中央服务器 收集和转发信息。即时消息就属于这类程序。像m s n 、腾迅q q 、迅雷、p p l i v e 等程序如今己经拥有了大量忠实的用户。 2 1 3p 2 p 的应用 由于p 2 p 模式具有的技术特点，很多i t 公司和研究部门都认为该技 术蕴涵着巨大的技术和商业潜在价值，并从不同的角度研究和应用该技术。 目前p 2 p 的应用主要有：文件交换、对等计算、协同工作、搜索引擎、即 时通信、网络游戏软件、基于i n t e m e t 的文件存储系统等。 1 ) 文件交换 传统的w e b 方式中，要实现文件交换需要w e b 服务器的大力参与，通 过将文件上传到某个特定的网站，用户再到该网站搜索需要的文件，然后下 载。这就要求w e b 服务器能够对大量用户的访问提供有效的服务，成为 w e b 应用的瓶颈之一。而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 ，国内的有北大天网m a z e 、迅雷等。 2 ) 对等计算 通过众多计算机来完成超级计算机的功能，是全球的科学家梦寐以求的 事情。采用p 2 p 技术的对等计算，正是把网络中的众多计算机闲鼍的计算 能力进行利用，使用积累的计算能力来执行超级计算机的任务。任何需要大 量数据处理的行业都可从对等计算中获利，如天气预报、动画制作、基因组 的研究、安全加密等，有了对等计算之后，就无需昂贵的超级计算机了。应 用实例有：d i s t r i b u t e n e t 和s e t i h o m e 等。 3 1 协同工作 协同工作是指多个用户之间利用网络中的协同计算平台来共同完成某 项任务，共享信息资源等。协同工作是w e b 更具个性化的特征，使用户可 以按自己的方式来和其他人共享信息。企业机构的闩盏分散，员工和客户游 离不定，人们的工作环境起了很大的变化。当前的以服务器为中心的c s 集 中式互联臃结构不再适合这种环境的变化。p 2 p 技术的出现，使协同工作成 为可能。通过让绝大部分的节点和其它节点直接交互，p 2 p 大大降低了中间 7 肇于t a p e s t r y 构建p 2 p 资源搜索采统的研究 商的作用，使个人电脑再一次成为商务中心的内容的主要存储地。p 2 p 技术 使得人们在互联网上进行实时信息交互交流变得更方便和容易。互联网上任 意两台p c 都可建立实时的联系，建立了一个安全共享的虚拟空b 】，用户在 此基础上进行各种各样的活动。采用p 2 p 技术，可以去掉目前协同工作系 统中的中央服务器，参与协同工作的计算机直接建立连接。应用实例有：i m e l 的n e t b a t c h 等。 2 2p 2 p 搜索技术的分类及特点 p 2 p 领域一个很重要的研究就是搜索研究，p 2 p 网络中的搜索和现在使 用的搜索引擎搜索技术有很大的差别。p 2 p 搜索技术从结构角度出发又可以 分为四类：集中式p 2 p 网络的搜索技术，结构化p 2 p 网络的搜索技术，非 结构化p 2 p 网络的搜索技术，混合式p 2 p 网络的搜索技术。本章首先介绍 了p 2 p 搜索与传统搜索的区别与联系，然后分别具体介绍各种p 2 p 搜索技 术，并分析了它们的优缺点。 2 2 1p 2 p 搜索与传统搜索的比较 传统搜索( 如我们熟悉的b a i d u 、g o o g l e 、y a h o o 等) 并不真正搜索 i n t e r n e t ，它搜索的实际上是预先整理好的网页数据库的索引一徭绵音寸 的 搜索引擎工作过程大致可以分为以下三个步骤。 1 ) 从i n t e r n e t 上抓取网页资料 i n t e r n e = t 有海量的网页资料，利用自动收集网页的s p i d e r ( 又称为网络蜘 蛛或者网络爬虫) 系统程序自动访问网站上的网页，并沿着网页链接爬到本站 或者其它网站，不断的重复这个爬网页的过程，并把爬过的网页收集起来。 一般来说搜索引擎的s p i d e r 程序需要定期的重新访问所有的i n t c m e t 网 页，由于各个搜索引擎的特点，重复访问网页访闯的时间也不同，对于特定 的网页也会有不同的访问更新频率。这样就可以及时地更新网页索引数据 库，反映出网页内容的变化情况，新增新的网页信息，去除死的网页链接， 并根据i n t e r n e t 上网页的内容、连接关系的变化，用户的访问频率对网页重 新进行排序。最终，网页的具体内容的索引就会出现在用户查询的结果集中。 2 ) 建立i n t c m e t 网页索引数据库 8 螭于r a p c s t r , , 掏建p 2 p 资源搜索系统的研究 将网页资料抓取回来以后，就可以用索引分析程序对s p i d e r 搜集回来 回来的网页信息进行分析，提驳网页肇面的相关要素信息( 包括网页的链接地 址、网页内容包含的关键词、关键词所在的位置、页面内容的生成时间、网 页的大小、网页的编码类型、和其他网页的连接关系等等) ，依据一定的相关 性算法进行复杂运算，得到针对每一个网页页面内容及超级链接中每个关键 词的相关度的参数，然后利用这些计算出来的参数信息建立网页索引数据 库。大型搜索引擎的数据库存储了i n t e m e t 上几十亿到几百亿的网页索引， 数据量达到了几万g 。但即使是最大搜索引擎建立起来超过几百亿网页的索 引数据库，也只能占i n t e r n e t 上普通网页的不到3 0 。 3 ) 在索引数据库中进行搜索 当用户在搜索引擎的客户端输入关键词进行搜索后，由搜索引擎的搜索 系统程序从网页索引数据库中找到适合用户的关键词的所有相关网页。针对 特定的关键词，所有网页的相关度参数已经计算好，所以我们只需要按照现 成的相关度参数进行排序，相关度越高排名越靠静，反之则越靠后。最后由 搜索引擎的页面生成系统将搜索结果的链接地址以及页面内容摘要等返回 给用户。p 2 p 搜索和传统的搜索不同，p 2 p 搜索是真疆的去搜索i n t e m e t 。 在p 2 p 网络中，用户将各自拥有的资源共享出来，而共享的资源就存储在 用户的机器上。一台机器上的用户将搜索信息请求同时发给网络上另外的n 台机器，如果搜索信息不能够得到满足，这n 台机器中的每一台都会把搜 索信息的请求转发给另外n 台p c ，不断重复这个过程。这样搜索的范围将 会在几秒钟内以几何级数增长，一定时间内就可以搜遍百万台机器上的资源 信息。 相对于传统的搜索服务而言，p 2 p 技术不仅仅节约了服务器的成本并提 高了信息的搜索效率，更重要的意义在于促进了搜索的多元化和权利、义务 的分解，使每台机器都参与到了搜索过程中去，由普通的接受服务的客户 端向可以提供服务的一方转变。通过合理可行的方法，将p 2 p 技术与搜索 服务结合在一起，在现有的建立统一搜索索引数据库的思路之外，还可以另 外引进二条思路：是在i n t e m e t 上进行全面的分散备份和无机备份、分散 9 摹十t a p e s t d 橱建p 2 p 资源搜索系统的研究 索引和无机索引的思路，而是在互联网上进行至索引而无备份的思路。这样 就可以使搜索技术大步向l l 迈进，走出搜索形式多样化的道路。 2 2 2 集中式p 2 p 网络的搜索技术 集中式p 2 p 网络采取是集中索引结构，对等体( p e e r ) 发送一个查询信息 到唯一的一个索引服务器，索引服务器根据对等体发送来的查询信息，在服 务器保存的索引信息进行本地搜索，然后将搜索结果发送给对等体。对等体 根据服务器发送回来的消息与对应拥有资源的对等体建立连接，并在对等体 之间传输所需内容。 当对等体的资源发生变化时，比如资源的增加，修改，删除等，索引服 务器将收到更新消息，并据此修改服务器缓存的资源索引信息。这种结构查 询信息和更新消息只在服务器和对等体之i 日j 传播。 n a p s t e r h ( 如图2 - 1 所示) 就是最早的据此建立起来的第一代p 2 p 系统。 图2 i 集中目录式网络 中央索引服务器保存所有n a p s t e r 用户上传的音乐文件索引和存放位置的信 息，当某个用户需要某个音乐文件时，首先连接至u n a p s t e r 中央索引服务器， 在服务器上进行检索，服务器返回存有该文件的用户信息，再由请求者直接 连到文件的所有者传输文件( 如图3 1 中曲线所示) 。n a p s t e r 首先实现了文件 查询与文件传输的分离，有效地节省了中央服务器的带宽消耗，减少了系统 的文件传输延时。集中式p 2 p 搜索技术的优点： 1 ) 查询效率高，查询算法灵活多变并能够实现复杂查询。 2 ) 对等体负载低，处理消息量少。 3 ) 系统可维护性好。 1 0 基于t a p e s t r ) 构建p 2 p 瓷勃墓搜索系统的研究 集中式p 2 p 搜索技术的缺点： 1 ) 对索引服务器的处理能力和带宽的要求很高。 2 ) 对索引服务器的安全性要求比较高，易遭受d o s ( 拒绝服务攻击) 等攻 击而瘫痪。 3 ) 随着网络规模的不断扩大，维护成本将会变高。 4 ) 索引服务器容易引起版权问题的纠纷。 综合上述的优缺点，这种网络的搜索形式只适合小型网络，在管理方面 有定优势，但是由于上述的缺点，这种形式不适合大型网络使用。 2 2 3 结构化p 2 p 网络的搜索技术 ， 结构化p 2 p 网络采用分布式哈希表( d i s t r i b u t e dh a s h ，t a b l e 简称d h t i t s ) 结构，使用分布式哈希表索引对资源和节点进行搜索。 d h t 技术简介：首先将整个搜索空间对应到一个散列( h a s h ) 空日j ，并且 对各个节点( 基于节点的i p 地址) 也进行相应散列，每个节点各负责一部分散 列空间。当一个节点发布一个资源( 例如文件) ，需要对该资源的唯一标识( 如 文件名) 进行散列，而根据该敝列值可以确定负责管理该资源的节点。当一个 节点要搜索该资源时，同样对该资源的唯一标识使用相同的散列函数进行散 列得到散列值，通过有效地局部路由，找到负责该资源的节点从而可以找到 要搜索的资源。在这类系统中，赋给每个节点的区域是动态的，依赖于每个 时候加入和离丌网络的节点数量。 下面重点介绍几个典型的使用d h t 搜索技术的p 2 p 网络。 1 ) c h o r d c h o r d 9 1 项目诞生于美国的麻省理工学院。它的目标是提供一个适合于 p 2 p 环境的分布式资源发现服务，它通过使用d h t 技术使得发现指定对象只 需要维护0 0 0 9 n ) 长度的路由表。在d h t 技术中，网络节点按照一定的方式 分配一个唯一节点标识符( n o d ei d ) ，资源对象通过散列运算产生一个唯一的 资源标识符( o b j e c t i d ) ，且该资源将存储在节点i d 与之相等或者相近的节点 上。需要查找该资源时，采用同样的方法可定位到存储该资源的节点。因此， 基于t a p e 泖均琏p 2 p 资源搜索系统的研究 c h o r d 的主要贡献是提出了一个分稚式查找协议，该协议可将指定的关键字 ( k e y ) 映射到对应的节点( n o d e ) 。 2 1 p a s t r y p a s t r y 1 2 l 是微软研究院提出的可扩展的分布式对象定位和路由协议，可 用于构建大规模的p 2 p 系统。在p a s t r y 中，每个节点分配一个1 2 8 位的节点 标识符号( n o d e l d ) ，所有的节点标识符形成了一个环形的n o d e l d 空问，范围 从0 到2 1 2 8 1 ，节点加入系统时通过散列节点r p 地址在1 2 8 位n o d e l d 空 间中随机分配。在搜索过程中，路由查询消息中将携带被查询对象i d ( o b j e e t i d ) ，又称消息键值。当收到路由消息时，节点首先检查消息键值是否落在叶 子节点集合的范围内。如果是，则直接把消息转发给叶子节点集合中节点标 识和消息键值最接近的节点；否则就从路由表中根据最长前缀优先的原则选 择个节点作为路由目标，转发路由消息。如果不存在这样的节点，当i j 节 点将会从其维护的所有邻居节点集合( 包括路由表叶子集合及邻居集合中的 节点) 中选择一个距离消息键值最近的节点作为转发目标。 3 1 c a n c a n l l o l ( c o n t e n ta d d r e s s a b l en e t w o r k s ) 采用多维的标识符空间来实现分 布式敝列算法。c a n 将所有节点映射到一个n 维的笛卡尔空间中，并为每个 节点尽可能均匀的分配一块区域。c a n 采用的散列函数通过对( k e y ，v a l u e ) 对中的k e y 进行散列运算，得到笛卡尔空间中的一个点，并将( k e y ，v a l u e ) 对 存储在拥有该点所在区域的节点内。c a n 采用的路由算法相当直接和简单， 知道目标点的坐标后，就将请求传给当前节点四邻中坐标最接近目标点的节 点。c a n 是一个具有良好可扩展性的系统，给定n 个节点，系统维数为d ，则 路由路径长度为o ( n a ) ，每节点维护的路由表信息和网络规模无关为o ( d ) 。 在搜索的过程中，查询节点( 源节点) 首先计算被查询内容的键值( d 维向 量) ，然后在节点列表中查找在笛卡尔空间中与该键值最为接近的相邻节点， 找到后向该节点发送查询请求( 这策略被称为贪婪策略) 。查询请求中将携 带被查询内容的键值。收到查询请求的节点如果发现自身存储了被查询的信 息，可以直接回应查询节点( 这与致性哈希完全相同) ；如果被查询的信息 不在本地，就根据相邻节点表将请求转发到与键值最接近的节点上。这样的 謦十t a p e s t r y 构建p 2 p 费源搜索系统的蹦f 究 过程一直持续到找到相应的节点为止。在查询过程中，被查询节点到目标节 点的笛卡尔空间距离单调地减少。 现有d h t 算法搜索技术由于采用分布式散列函数，所以只适合于准确的 查找，如果要支持目前w e b 上搜索引擎具有的多关键字查找的功能，还要 引入新的方法，主要的原因在于d h t 的工作方式。基于d h t 的p 2 p 系统 采用相容散列函数根据精确关键词进行对象的定位与发现。散列函数总是试 图保证生成的数列值均匀随机分布，结果两个内容相似度很高但不完全相同 的对象被生成了完全不同的散列值，存放到了完全随机的两个节点上。因此， d h t 可以提供精确匹配查询，但是支持语义是非常困难的。 目前在d h t 基础上开展带有语义的资源管理技术的研究还非常少。由于 d h t 的精确关键词映射的特性决定了无法和信息检索等领域的研究成果结 合，阻碍了基于d h t 技术的p 2 p 系统的大规模应用。 2 2 4 非结构化p 2 p 网络的搜索技术 非结构化p 2 p 网络是在重叠网络( o v e r l a yn e t w o r k ) 上使用了随机图的方 式，搜索技术主要采取的是泛洪( f l o o d i n g ) 。非结构化p 2 p 网络的典型代表就 是g n u t e l l a 2 1 ，g n u t e l l a 采取的是基于随机图的泛洪算法。f l o o d i n g 的工作流 程：当一台计算机要下载一个文件，它首先以文件名或者关键字生成一个查 询，并把这个查询发送给与它相连的所有计算机，这些计算机如果存在这个 文件，则与查询的机器建立连接，如果不存在这个文件，则继续在自己相邻 的计算机之f b j 转发这个查询，直到找到文件为止。为了控制搜索消息不至于 永远这样传递下去，一般通过t t l ( t i m et ol i v e ) 机制柬控制查询的深度。 随着联网节点的不断增多，网络规模不断扩大，通过这种f l o o d i n g 方 式定位对等点的方法将造成网络流量急剧增加，从而导致网络中部分低带宽 节点因网络资源过载而失效。所以，后来许多研究人员在f l o o d i n g 的基础 上作了许多改进，下面将分别介绍各种方法。 1 ) 迭代泛洪( i t e r a t i v ef l o o d i n g ) 迭代泛洪是f l o o d i n g 方