（计算机系统结构专业论文）基于对等网络的搜索引擎关键技术研究.pdf

基于对等网络的搜索引擎关键技术毒 j y 攀帆1 帆8 帆2 眦7 8 眦4 心5 ( 受国家自然科学基金课题支持基金编号：6 0 7 0 3 0 8 2 ) 学位论文完成日期： 指导教师签字： 答辩委员会成员签字： 如lo i 专、谚 考捌址 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含未获得 ( 洼；如递查墓丝益要挂别直明笪：奎拦互窒2 或其他教育机构的学位或证书 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示谢意。 学位论文作者签名：占槲 签字日期：勿，口年厂月谚日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，并同意以 下事项： l 、学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。 2 、学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可以 采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权清华大学 “中国学术期刊( 光盘版) 电子杂志社”用于出版和编入c n k i 中国知识资源总 库，授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数 据库。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 冰啸 签字日期：) o l o 年歹月谚日 导师签字钟专耋 签字日期：别。年厂月凹日 基于对等网络的搜索引擎关键技术研究 摘要 随着互联网络的高速发展，w e b 上的信息量越来越大，而且这些信息本身 是高度分布式的。而传统的搜索引擎大都采用集中式的搜索机制，因此很难满 足用户对于搜索效率和搜索结果的要求。与此同时，对等网络( p e e r - t o p e e r , p 2 p ) 由于其本身的分布式体系结构以及其对于网络中硬件资源的利用能力，为 解决以上问题提供了一个新的研究方向构建基于对等网络的搜索引擎。 基于对等网络的搜索引擎的优势主要体现在以下几个方面：( 1 ) 网络中的信 息本身就是高度分布式的，这与对等网络的体系结构相符合；( 2 ) 由于对等网 络中的节点都能够向网络提供自己的资源，包括带宽、存储和计算能力等，因 此对等网络能够利用到网络中更多的硬件资源。然而，基于对等网络的搜索引 擎作为一种新兴的网络应用，还有很多问题有待解决，例如现有的搜索算法效 率较低，难以支持复杂查询等等。 本文在分析基于对等网络的搜索技术存在的问题基础上，提出了一种基于 非结构化对等网络的信息检索路由算法基于搜索历史的多关键字搜索 ( h i s t o r y - b a s e dm u l t i k e y w o r d ss e a r c h ，h m s ) 算法。h m s 算法只需要每个节点 为各个邻居节点保存部分历史查询信息，当节点收到一个新的查询消息时，便 根据对这些历史信息的分析自动发现有几个以及具体是哪几个邻居节点有可能 回复当前的查询消息。在转发查询消息时，节点只把查询消息发给那些比较有 可能回复该查询消息的邻居节点。 最后，本文设计并实现了一个基于非结构化对等网络的信息检索仿真系 统，并利用该系统对h m s 算法的搜索效率作了验证。试验结果表明h m s 算法 能够有效地降低网络通信开销，同时还能够保证较高水平的查询结果。 关键词：搜索引擎；对等网络技术；信息检索；多关键字搜索算法； i l r e s e a r c ho nt e c h n oio gie so fs e a r c he n gir eb a s e do n p e e r t o p e e rn e t w o r k s a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e m e tr a p i d l y ，m o r ea n dm o r ei n f o r m a t i o na r e p u b l i s h e do nt h ew o r l dw i d ew e b t h ei n f o r m a t i o na r eh i g h l yd i s t r i b u t e dr e s i d i n go n m i l l i o n so fs i t e s t h i st r e n dc h a l l e n g e st h et r a d i t i o n a li n f o r m a t i o nr e t r i e v a lt e c h n i q u e s l i k es e ( s e a r c he n g i n e ) ，f o rs ea r eo ft h ec e n t r a l i z e da r c h i t e c t u r e s h o w e v e r , c e n t r a l i z e ds e r v e rc a nn o tm e tt h ed e m a n d so fu s e r so nt h eq u a n t i t ya n d s p e e do f i n f o r m a t i o np r o c e s s i n gb e c a u s et h er e s t r i c t i o no ft h ec a p a c i t yo fs t o r a g eb a n d w i d t h a n dt h ec a p a c i t yo fc o m p u t a t i o n m e a n w h i l e ，t h ed e v e l o p m e n to fp 2 p ( p e e r - t o - p e e r ) o f f e r san e wr e s e a r c ha r e a - e s t a b l i s h i n gas eb a s e do np 2 p t h em a i na d v a n t a g e so fp 2 ps e a r c he n g i n ea sf o l l o w s ：f i r s t ，i n f o r m a t i o ni sh i g h d i s t r i b u t e di nn e t w o r ka n di ti si na c c o r dw i t ht h ea r c h i t e c t u r eo fp 2 p s e c o n d ，p e e r s i np 2 pn e t w o r ka r ea b l et op r o v i d es e l fr e s o u r c ei n c l u d i n gt h ec a p a c i t yo fs t o r a g e b a n d w i d t ha n dt h ec a p a c i t yo fc o m p u t a t i o n a c c o r d i n g l y ，p 2 pn e t w o r ka r ec a p a b l eo f m o r eh a r d w a r er e s o u r c e h o w e v e r ，嬲an e wt h ea p p l i c a t i o no fn e t w o r k ，s e 。b a s e do n p 2 pn e t w o r kh a sm a n yp r o b l e m s f o ri n s t a n c e ，l o we f f i c i e n c ya l g o r i t h mi sd i f f i c u l tt o s u p p o r tc o m p l e xq u e r i e s t h i sp a p e ra n a l y s i st h et e c h n o l o g yp r o b l e m so fs eb a s e do np 2 pa n dp r o p o s e h i s t o r yb a s e dm u l t i - k e y w o r d ss e a r c h ( h m s ) i nu n s t r u c t u r e dp e e r - t o p e e rs y s t e m s ， w h i c ho n l yr e q u i r e se a c hp e e rt om a i n t a i np a r t i a lq u e r yi n f o r m a t i o no fi t sn e i g h b o r s ， a n de x p l o i tt h e s ei n f o r m a t i o nt oa u t o n o m o u s l yf i n dh o wm a n yn e i g h b o r sa n dw h i c h n e i g h b o r sa r el i k e l yt oa n s w e r t h ep e e r sw i l lo n l yf o r w a r dq u e r ym e s s a g e st o n e i g h b o r sw h i c ha r em o r el i k e l yt or e p l y a tl a s t ，w ed e s i g na n di m p l e m e n ta ni n f o r m a t i o nr e t r i e v a ls i m u l a t i o ns y s t e m b a s e do nu n s t r u c t u r e dp 2 pa n du s i n gi tt ot e s tt h ee f f i c i e n c yo fr i m s t h er e s u l t i i i s h o w sh m si sa b l et or e d u c en e t w o r kc o m m u n i c a t i o nc o s ta n de n s u r eh i g hq u a l i t y s e a r c h i n gr e s u l t s k e y w o r d s ：s e ( s e a r c he n g i n e ) ，p e e r - t o p e e rn e t w o r k , i n f o r m a t i o nr e t r i e v a l ， m u l t i - k e y w o r d ss e a r c ha l g o r i t h m i v 目录 1 弓l 言 1 1 研究背景1 1 1 1 对等网络应用背景及现状一2 1 1 2 网络信息检索技术应用背景及现状2 1 2 本文的主要研究意义3 1 3 本文主要贡献5 1 4 本文组织结构j5 2 基于对等网络的搜索引擎关键技术分析。7 2 1 相关对等网络技术7 2 1 1 对等网络拓扑分类j 7 2 1 1 1 中心化拓扑( c e n t r a l i z e dt o p o l o g y ) 。一9 2 1 1 2 全分布式非结构化拓扑( d e c e n t r a l i z e du n s t r u c t u r e dt o p o l o g y ) 1 0 2 1 1 3 半分布式拓扑( p a r t i a l l yd e c e n t r a l i z e dt o p o l o g y ) 1l 2 1 1 4 全分布式结构化拓扑( d e c e n t r a l i z e ds t r u c t u r e dt o p o l o g y ) 1 2 2 1 1 5 四种对等网络拓扑结构对比1 3 2 1 2 典型的非结构化对等网络路由算法1 4 2 1 2 1f l o o d i n g 算法1 5 2 1 2 2m o d i f i e d b f s 算法1 7 2 1 2 3i t e r a t i v ed e e p e n i n g 算法18 2 1 2 4r a n d o m w a l k 算法18 2 1 2 5i n t e l l i g e n ts e a r c hm e c h a n i s m 算法1 9 2 2 相关搜索引擎技术2 0 2 2 1 搜索引擎的工作原理2 0 2 2 1 搜索引擎分类21 2 2 3l u c e n e _ 基于j a v a 的全文索引工具包2 2 2 3 本章小结2 6 3 基于搜索历史的多关键字搜索算法设计2 7 v 3 1 算法设计背景2 7 3 2 算法核心设计2 8 3 2 1 查询消息传递机制2 9 3 2 2 邻居节点排序机制31 3 2 3 邻居节点选择优化机制3 3 3 2 使用h m s 算法的信息检索示例3 6 3 3 本章小结3 8 4 非结构化对等网信息检索仿真系统的设计与实现3 9 4 1 仿真系统设计3 9 4 2 仿真系统实现4 5 4 3 仿真试验设置4 6 4 4 仿真结果分析：4 9 4 5 本章小结：5 3 5 总结与展望5 4 参考文献5 5 致谢5 8 个人简历。 发表的学术论文5 9 v l 基于对等网络的搜索r j i 擎关键技术研究 l 引言 1 1 研究背景 在网络技术飞速发展的今天，网络信息检索已经成为广大网络用户获取各 种信息资源的主要手段。与传统的信息获取渠道相比，网络中的信息资源具有 多样性和全面性的特点，可以为用户提供更多的选择。另外，由于网络信息的 更新速度相对于传统的信息传播更快，可以为用户及时提供更新更准确的信 息。特别是随着网络应用的迅速发展，个人用户通过网络发布的信息日渐增 多，成为网络信息资源中非常重要的一部分。这种趋势是与网络其本身的分布 性、动态性及信息的迅速增长性相符合的。然而，这种信息的迅速增长也恰恰 对传统的网络信息检索技术，如搜索引擎等，提出了挑战。面对网络中庞大的 信息资源，传统的搜索引擎由于受到硬件及体系结构的限制，在搜索效率上很 难满足用户的要求。这是由于传统的搜索引擎大都采用集中式体系结构，这种 结构直接违反了网络资源的分布式特性，而且集中式服务器的存储能力、带宽 和计算能力等都有上限，导致搜索引擎的数据库很难能够随着网络中信息资源 的快速增长而及时更新，另外，搜索引擎也很难及时探测到网络中原有信息资 源的修改、删除和转移等【l 】。因此，如何给用户提供更高效的信息检索服务成 为网络搜索引擎技术的一大挑战。 与此同时，对等( p e e r t o p e e r ，p 2 p ) 网络的迅速发展给大范围内的信息共 享提供了新的机遇【2 1 。对等网络应用也为网络信息检索提供了一个非常可行的 方案，主要有以下几点原因：( 1 ) 网络中的信息本身就是高度分布式的，它们 存在于数以百万计的网络站点中，特别是随着网络中个人用户的增多，他们通 过各种方式( 例如通过个人博客发布消息等) 向网络中发布的信息成为网络信 息资源的重要组成部分；( 2 ) 由于对等网络中的节点都会向网络提供自己的资 源，包括带宽、存储和计算能力等，因此对等网络能够利用到网络中的更多的 硬件资源，一个对等网络在处理能力方面绝对可以超过任何一个大型的集中式 服务器，这使得它能够采用更加先进有效的语言数据分析算法、统计算法或其 他的语义分析算法等；( 3 ) 一个对等网络中的节点可以利用自己的计算机资源 基于对等网络的搜索引擎关键技术研究 对自身的信息内容加以分析，从而了解这个节点用户的兴趣所在，这有助于进 行基于用户兴趣的信息检索。 正是出于以上几点原因，在解决网络搜索引擎所面临的难题时出现了一个 新的研究方向基于对等网络的信息检索技术。 1 1 1 对等网络应用背景及现状 对等网络( 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 ，c s ) 结构来说，对等网络中的彼此连接的计 算机均处于对等的地位。对等节点之间可以直接交换信息、共享资源( 包括信 息资源、处理器资源、存储资源甚至高速缓存资源等) 和服务，无需依赖集中式 服务器支持【3 1 。 对等网络的一个重要特性就是网络中的节点既作为客户端又作为服务器 端，即对等网中的用户在享受网络服务的同时也需要为网络提供自己的资源， 包括带宽、存储空间和计算能力等。因此，当有节点加入网络时，不只是对网 络系统的使用请求增多，整个系统的容量也在同时增大。这与传统的c s 结构 相比，后者由于受限于服务器的容量和计算能力等，当系统中用户增多时，提 供给每个用户的服务资源将相应减少，也就说越多的用户意味着越慢的服务。 另一方面，传统的c s 结构中，由于所有用户依赖于一个中心索引服务器来发 现数据，一旦该服务器发生故障，系统将出现单点崩溃。而在对等网络环境 下，用户可以通过多个节点获取服务，单个节点的故障并不影响用户的使用， 这无疑增加了网络系统的健壮性。 虽然目前互联网中大多数的应用仍然采用c s 架构，但在互联网设计之 初，实际上并没有客户端和服务器端的概念，互联网在本质上是分布式的，因 此可以说对等网络技术是对互联网本质的回归。基于对等网络的各种优势，对 等网络技术目前已经受到来自各个领域的关注，并被财富杂志誉为将改变 互联网未来的四大新技术之一。 1 1 2 网络信息检索技术应用背景及现状 网络信息检索是指以计算机及互联网技术为手段，根据用户的需要从互联 网的信息集合中找到相关信息的过程。目前，网络信息检索技术的核心主要集 2 基于对等网络的搜索引擎关键技术研究 中在搜索引擎技术的发展上。搜索引擎的主要业务就是以信息检索的方式为用 户提供信息存取、信息管理和信息检索的服务。 目前，搜索引擎已经成为网民在互联网中获取所需信息的重要工具。据相 关统计报告显示，截至2 0 0 8 年底，中国搜索引擎的用户规模己达到2 0 3 亿 人，与2 0 0 7 年底相比，搜索引擎的用户增长了5 1 0 0 万人，年增长率达到 3 3 6 。目前，搜索引擎在全国网民中的使用率为6 8 ，在各种互联网应用中 位列第四。面对如此庞大且仍在迅速增长的用户群体，搜索引擎如何应对日益 增加的服务请求，为用户提供迅速有效的信息检索服务成为一大难题。 传统的搜索引擎的服务仍然需要依赖于中心服务器，随着用户的进一步增 长和网络中信息资源的不断增加，搜索引擎对检索请求和信息资源的处理能力 会受到越来越大的挑战。传统的搜索引擎大多数只能检索到互联网中的静态网 页，而对于那些处于边缘网络内的实时性和动态性很强的信息却很难全部搜索 到。据统计，互联网上共享的文档总量超过5 5 0 0 亿，目前g o o g l e 所能检索到 的8 0 亿只是其中很小的一部分【4 】。同时，由于网络中信息的更新具有不确定 性，传统的搜索引擎的数据库更新很难与信息的更新保持一致，这有可能会导 致搜索结果中出现信息过时、网页缺失等问题。另一方面，由于目前搜索引擎 的商业化需求，搜索结果中常常出现一些与用户搜索意愿并不相关的内容。在 搜索引擎对检索结果进行商业排序之后，用户真正需要的检索结果可能会被排 在较后的位置。 1 2 本文的主要研究意义 对等网络抛弃了传统的中心服务器结构，网络中各个节点在使用网络资源 的同时需要提供自己的资源给网络，共同组成一个庞大的分布式网络数据库， 因此基于对等网络的信息检索理论上可以检索到网络中每台主机上存储的内 容。同时，由于对等网络信息检索的信息直接来自于各个节点，因此可以保证 每次检索到的都是最新的信息。另一方面，由于对等网络技术可以有效地利用 网络中更多的存储、计算等资源，基于对等网络的搜索引擎可以适应网络中不 断增多的服务请求，具有良好的可扩展性。此外，对等网络中的节点均处于对 等的地位，这就决定了用户在信息检索时可以避开商业因素的影响，真正掌握 3 基于对等网络的搜索引擎关键技术研究 对网络资源的使用权。综上所述，构建基于对等网络的搜索引擎可以弥补传统 搜索引擎的许多不足，为网络信息检索技术的发展提供一条可行之径。 然而，基于对等网络的搜索引擎作为一种新兴的网络应用，与传统搜索引 擎技术相比，在技术方面还有许多有待完善的方面，其面临的问题主要有以下 几个方面【5 1 ： 搜索效率：由于对等网络系统通常都是由处于边缘网络中的节点组成，这 些节点的计算能力、存储资源和网络带宽往往比较有限，因此如何设计高效的 搜索算法是一个很大的难题。 自治性：对等网络中各节点都有很强的自治性，但自治与效率往往是矛盾 的1 6 ，如何权衡两者之间的关系是研究者需要考虑的问题。 性能保证：主要是指查询响应时间、查询结果质量( l l 女u 查全率、查准率) 等 搜索性能。在对等网络的动态分布环境中，如何保证搜索性能是必须解决的问 题，而且在搜索效率与查询结果质量两方面也存在着权衡关系。 可用性：在对等网络这样高度动态的环境中，要保证系统可用性，必须有 相应的容错机制和优化方法，例如副本、压缩、缓存技术等。 可扩展性：虽然对等网络系统被普遍认为具有较强的可扩展性，但在面对 w e b 搜索时，由于w e b 的巨大规模和海量数据，系统的可扩展性仍然是需要重 点考虑的问题。 负载均衡：w e b 搜索中固有的“热点”问题在对等网络环境中同样存在，而 且相比于传统集中式搜索引擎，对等网络中的负载均衡显得更为重要，同时难 度也更大。 复杂查询：所谓复杂查询，是相对于键值查询这样的简单查询来说的，人 们希望w e b 搜索能够支持关键词查询、聚合查询，甚至s q l ( s t r u c t u r e dq u e r y l a n g u a g e ) 查询、语义查询这样的复杂查询，从而满足人们更高的查询需求。目 前，无论是集中式搜索引擎还是对等网络搜索引擎庄要的研究都还是针对关键 词查询。在对等网络中如何支持高效的复杂查询也是一个难点。例如，p i e r l 7 1 能够支持s q l 查询，不过实验结果显示存在严重的“热点”问题。 4 基于对等网络的搜索引擎关键技术研究 安全性：对等网络系统中虽然没有易受攻击的中心服务器，但也存在其他 的安全问题，比如其节点容易遭受d o s 攻击、如何对文件进行认证以保证数据 的真实性、如何保证匿名性、如何进行访问控制以保护某些内容的版权等。 解决以上问题所需要的技术涉及到对等网络技术的方方面面，包括拓扑结 构、路由算法、数据存放策略、激励机制等。本文主要关注于网络拓扑结构和 路由算法方面，通过对路由算法的改进提高对等网络中信息检索的搜索效率。 1 3 本文主要贡献 本文通过分析基于对等网络搜索引擎的关键技术的现状，主要是分析对等 网络的拓扑结构和路由算法的相关技术，提出一种新的基于非结构化对等网络 的信息检索路由算法，本文称之为基于历史学习的多关键字查询( h i s t o r y b a s e d m u l t i k e y w o r d ss e a r c h ，h m s ) 算法。本文假设网络中的每个节点都有一个包含信 馕， 息文档的数据库且这个数据库对于对等网中的其他节点也是可用的。一个节点 可以通过其它节点发送查询消息来检索自己需要的信息。h m s 算法利用网络中 各个节点的历史查询记录引导当前查询消息的转发，尽可能地避免将查询消息 转发给过多的无关结点。然后，通过构建一个基于非结构化对等网络的信息检 索仿真系统，验证本文提出的检索算法的效率，并将该算法的效率与现有的几 j 爨， 种相关典型算法的效率作对比分析。最后通过对仿真实验结果的分析得出有关 h m s 算法效率的结论。 1 4 本文组织结构 本文共分为五章，各章内容简介如下： 第1 章：首先分别介绍了对等网络技术和网络信息检索技术的应用背景及 发展现状，然后对本文的研究意义、主要贡献和章节组织作了介绍。 第2 章：对本文研究内容所涉及到的几项关键技术进行介绍，主要包括相 关的对等网络技术和网络搜索引擎技术。 第3 章：设计一种新的对等网络检索算法( h m s 算法) ，并对该算法的核 心思想和主要机制设计作了详细介绍。最后举例说明h m s 算法在对等网络信 息检索中的应用。 基于对等网络的搜索引擎关键技术研究 第4 章：介绍了基于非结构化对等网络的信息检索仿真系统的设计与实 现。然后，对利用仿真系统进行几种路由算法的仿真试验过程作简要介绍。最 后对仿真试验的结果数据作出分析。 第5 章：对本文进行了总结，并对未来工作进行了展望。 6 基于对等网络的搜索引擎关键技术研究 2 基于对等网络的搜索引擎关键技术分析 基于对等网络的搜索引擎，是指将对等网络技术与网络信息检索技术相结 合，构建分布式的搜索引擎系统。本章的主要内容可以分为两个部分，分别介 绍相关的对等网路技术和相关的搜索引擎技术。 2 1 相关对等网络技术 一个对等网络( p e e r - t o p e e rs y s t e m ，p 2 p ) 从定义上来说，是指由多个以分 布式资源共享为目标的节点( 一个节点称为一个p e e r ) 共同组成的自组织的网 络，这个网络中不需要中心服务器的参与，网络中的所有节点都是对等且自治 的。其对等概念是指网络中的物理节点在逻辑上具有相同的地位，而并非处理 能力的对等。 对等网络系统主要具有以下特性： ( 1 ) 分布式的资源共享： 网络中的资源( 包括带宽、存储空间、计算能力等资源) 分布在网 络中各个节点上。 。 网路中的每个节点都可以利用其他节点提供的资源，但同行也必须 把自己的资源提供给网络中的其他节点使用。 ( 2 ) 无中心服务器的自治结构： 通常情况下，对等网络中的节点之间的互联不会通过任何的中心控 制机构，而是彼此直接互联。 各个节点对于自己的资源是完全自治的。 在完全的分布式对等网络中，节点之间可以脱离中心服务器的控制 而直接进行资源的访问和交换。但是，在某些情况下出于效率的考 虑，例如为了更加快速的定位资源的位置，可能会需要中心控制结 构参与对等网络的组成，这种情况就是半分布式的对等网络拓扑。 2 1 1 对等网络拓扑分类 对等网络的拓扑是指对等网络中节点之间进行连接的方式及共同组成的网 络结构形式。对等网络的拓扑结构又可以分为以下四类：中心化拓扑、全分布 式非结构化拓扑、半分布式拓扑、全分布式结构化拓扑。拓扑结构的不同直接 7 基于对等网络的搜索引擎关键技术研究 决定了对等网络在应用中的各方面特性的不同。由于对等网络是相对于传统的 c s 网络来说的，因此在介绍对等网路的拓扑之前先简要介绍一下传统的c s 结构的网络及其特点。 图2 1 客户端服务器( c l i e n t s e r v e r ，c s ) 网络模型 如图2 1 所示，在传统的客户端服务器( c l i e n t s e r v e r ，c s ) 结构的网络 下，网络中的用户终端( c l i e n t 端) 需要通过向服务器端( s e r v e r 端) 发送请求 来获得网络资源。可以看出，这种结构对中心服务器的依赖程度非常高，中心 服务器的瘫痪将直接导致整个系统的崩溃，也就是所谓的单点崩溃问题。同时 由于中心服务器的存储容量、计算能力和带宽等方面的限制，系统的可扩展性 较差。 8 基于对等网络的搜索引擎关键技术研究 2 1 1 1 中心化拓扑( c e n t r a l i z e dt o p o l o g y ) 图2 2 中心化拓扑( c e n t r a l i z e dt o p o l o g y ) 中心化拓扑( c e n t r a l i z e dt o p o l o g y ) 也称为集中目录式拓扑，这种拓扑结 构是最早出现的对等网络应用模型。如图2 2 所示，这种拓扑结构需要依赖于 一个中心的目录服务器，因此并不算是纯粹的对等拓扑结构。 中心化拓扑结构应用中最具有代表性的是n a p s t e r 8 。n a p s t e r 是一款应用 于m p 3 音乐文件共享的软件，其用户的注册以及网络中文件的搜索过程都与传 统c s 模式类似，主要区别在于n a p s t e r 的服务器并非用来存储网络中的文件资 源，而是存储网络中资源的目录，真正的文件资源存储在网络中的各个节点 上。当一个节点需要进行文件检索时，通过查找服务器上的文件目录，找到存 有匹配资源的节点，然后根据网络的流量和延迟等信息选择合适的节点直接建 立连接并进行文件传输。类似的中心化拓扑结构的对等网络应用还有 a u d i o g a l a x yt g l ，w i n m x 1 0 1 ，b i t t o r r e n tf l l ，1 2 】等。 中心化拓扑结构结合了c s 系统检索高效和p 2 p 系统信息量大的优点，但 是由于这种拓扑结构并没有完全脱离对中心服务器的依赖，因此虽然具有较高 的路由效率且支持复杂查询，但是在可扩展性和可靠性方面表现较差。服务器 的单点崩溃问题仍然存在，同时由于缺乏有效的资源共享激励机制，资源可用 9 基于对等网络的搜索引擎关键技术研究 性较差。另外，中心服务器的存在容易引起共享资源在版权上的纠纷，这也是 最终导致n a p s t e r 破产的原因。 2 1 1 2 全分布式非结构化拓扑( d e c e n t r a l i z e du n s t r u c t u r e dt o p o l o g y ) 图2 3全分布式非结构化拓扑( d e c e n t r a l i z e du n s t r u c t u r e dt o p o l o g y ) 全分布式非结构化拓扑( d e c e n t r a l i z e du n s t r u c t u r e dt o p o l o g y ) 也称为纯对 等网络模型或广播式对等网络模型。如图2 3 所示，全分布式非结构化拓扑彻 底摆脱了中心服务器结构，网络中的节点之间都是随机互连，相连的节点互相 称为邻居节点。 全分布式非结构化拓扑应用最广泛的模型是g n u t e l l a t n 】。g n u t e l l a 中的每个 结点都有一个节点标识符。节点标识符是在节点加入系统时，通过对其地址 ( i p 及端口) 进行哈希运算得到的。网络中的每个节点都会保存一个邻居节点 列表，表中存有指向各个邻居节点的指针，每个指针都是一个邻居节点的节点 标示符、i p 地址和端口等信息。g n u t e l l a 中采用洪泛方式进行路由，具体方式 为：节点每收到一个查询信息，首先检查一下这个信息是否是第一次收到，若 是，则向它的邻居节点表中的全部邻居节点广播此信息；若否，则丢弃该消 息。g n u t e l l a 中节点通过定时运行拓扑维护算法，处理对等网的扰动问题。节 点会定时向邻居结点发p i n g 消息，若有限时间内收到邻居节点回复的p o n g 1 0 基于对等网络的搜索引擎关键技术研究 消息，则证明该邻居节点运行正常；若超时没有收到回复，则重发；若连续3 次都收不到p o n g 消息，则更新自己的邻居节点表。全分布式拓扑结构的其他 应用模型还包括f r e e n e t t l 4 】等。 全分布式非结构化拓扑解决了网络结构中心化的问题，扩展性和容错性较 好，但是g n u t e l l a 网络中的搜索算法以泛洪的方式进行，通信消息的泛滥消耗 了大量带宽并很快造成网络拥塞甚至网络的不稳定。同时，局部性能较差的节 点可能会导致g n u t e l l a 网络被分片，从而导致整个网络的可用性较差，另外这 类系统更容易受到垃圾信息，甚至是病毒的恶意攻击。另外，由于这种拓扑结 构缺少对网络上的用户节点数以及对他们提供的资源的一个总体把握，因此这 种拓扑结构很难进行商业化的应用。 2 1 1 3 半分布式拓扑( p a r t i a l l yd e c e n t r a l i z e dt o p o l o g y ) 图2 4 半分布式拓扑( p a r t i a l l yd e c e n t r a l i z e dt o p o l o g y ) 半分布式拓扑( p a r t i a l l yd e c e n t r a l i z e dt o p o l o g y ) 结构也可以称为混合对等 网络结构。为了避免洪泛路由方式造成的网络拥塞，半分布式拓扑结构中引入 了超级节点( s u p e r - n o d e ) 的概念。根据各个节点的计算能力、存储能力、带 基于对等网络的搜索引擎关键技术研究 宽以及网络延迟时间等性能的不同，将网络中的节点分为超级节点和普通节点 两类。 如图2 4 所示，一个超级节点与临近的多个普通节点之间采用中心化拓扑 的方式相连，共同组成一个自治的簇，个簇内的普通节点之间可以进行直接 通信。一个簇通常选择会性能最优的节点作为超级节点，当有新节点加入或节 点性能发生改变时，也有可能会重新选择性能最优的节点或引入另外的节点作 为超级节点。各个超级节点之间则采用全分布式拓扑的模式相连。超级节点用 于存储簇内的普通节点上的可用资源目录以及它们的i p 地址信息，同时还要负 责维护整个网络的结构。 在半分布式拓扑的对等网络中，当普通节点需要进行资源检索时，它首先 到它连接的超级节点的目录中进行查找，如果找到了相应的资源，则根据资源 所在节点的i p 地址建立直接连接；如果没有找到，则超级节点会把这个查询消 息以洪泛的方式发给网络中的其他超级节点，直到得到想要的资源。s k y p e t ”】， k a z a a 16 1 ，e m u l e l l 7 】以及m l d m o n k e y t l 8 1 等都是基于半分式拓扑结构的对等网络应 用系统。 半分布式拓扑，由于综合了中心化拓扑快速查找和非结构化拓扑脱离中心 化的优势，因此有效的消除了非结构化拓扑中使用泛洪算法带来的网络拥塞、 搜索迟缓等不利影响。同时，由于超级节点可以监控一个簇内所有普通节点的 行为，因此其网络的安全性可以得到较好的保证，而且超级节点的存在还可以 提高网络的负载平衡能力。但是，由于超级节点本身的脆弱性也可能导致其簇 内的节点处于孤立状态，因此这种拓扑结构仍然存在一定的局限性。 2 1 1 4 全分布式结构化拓扑( d e c e n t r a l i z e ds t r u c t u r e dt o p o l o g y ) 结构化拓扑与非结构化拓扑的根本区别在于每个节点所维护的邻居是否能 够按照某种全局方式组织起来以利于快速查找。结构化拓扑是一种采用纯分布 式的消息传递机制和根据关键字进行查找的定位服务，目前的主流方法是采用 分布式哈希表( d h t ) 技术。由于d h t 各节点并不需要维护整个网络的信息， 只在节点中存储其临近的后继节点信息，因此较少的路由信息就可以有效地实 现到达目标节点，同时又取消了洪泛算法。这种拓扑结构有效地减少了节点信 基于对等网络的搜索引擎关键技术研究 息的发送数量，从而增强了对等网络的可扩展性。同时，出于冗余度以及延时 的考虑，大部分d h t 总是在节点的虚拟标识与关键字最接近的节点上复制备份 冗余信息，这样也避免了单一节点失效的问题。 c a n t l 9 1 ，t a p e s t r y 2 0 1 ，c h o r d 2 1 】，p a s t r y 2 羽，s k i p n e t t 2 3 】和b u t t e r f l y 2 4 1 等是目前 几个比较典型的结构化拓扑的应用系统。这些系统一般都假定节点具有相同的 能力，这对于规模较小的系统较为有效。但这种假设并不适合大规模的i n t e m e t 部署。 与非结构化拓扑相比，结构化拓扑虽然具有很好的可扩展性和较高的路由 效率，但是却不支持复杂查询。同时基于d h t 的拓扑维护和修复算法也比非结 构化拓扑和半分部式拓扑等要复杂得多。事实上，目前大量实际应用还大都是 基于无结构的拓扑和洪泛路由机制，现在大多采用d h t 方式的p 2 p 系统缺乏 在i n t e m e t 中大规模真实部署的实例，成功应用还比较少见。 2 1 1 5 四种对等网络拓扑结构对比 在实际应用中，对等网络的各种拓扑结构各有优缺点，下面通过表格对这 四种拓扑结构在扩展性、路由算法效率等几个方面进行对比： 表2 1 对等网络拓扑结构对比表 瀑 中心化拓扑全分布式非结全分布式结构半分布式拓扑 构化拓扑化拓扑 比较标准 可扩展性 差 差好中 可靠性 差 好好 中 可维护性 最好最好好中 路由算法效率 最高中商中 复杂查询支持支持不支持支持 目前基于对等网络的信息检索方面的研究主要采用非结构化和结构化的拓 扑结构 2 5 - 3 1 】。本文研究的重点是全分布式非结构化对等网络的搜索技术。 全分布式非结构化拓扑具有较好的容错性，网络受节点的频繁a n * 或退出 的影响较小，且支持复杂查询，这有利于其在搜索方面的应用，但是由于这种 基于对等网络的搜索引擎关键技术研究 拓扑结构的网络节点之间的连接是随机的，且其典型的路由算法洪泛路由 算法的效率较低，因此如果构建的对等网搜索引擎采用非结构化的拓扑结构， 则其技术重点在于研究如何提高路由算法的效率，这也正是本文研究的主要内 容。 2 1 2 典型的非结构化对等网络路由算法 对等网络在应用中的一个关键问题是路由效率问题，尤其是在对等网络搜 索引擎技术中，一个路由算法的效率将直接影响到整个搜索引擎的性能。对等 网络搜索中的路由算法是指当网络中的某个节点发起一个信息检索的请求后， 该请求消息在网络中如何进行转发，最终找到查询结果的过程。本文研究的重 点也正是对等网络中的路由算法。 对等网络中的路由算法主要是由网络本身的拓扑结构决定的，目前对等网 络中的路由主要分为三种： 第一种是中心目录式的路由，主要是集中目录式对等网络采用的路由算 法。系统中用一个中心目录保存所有数据的位置，节点需要进行查询时，首先 连接到中心目录进行信息查找，确定相关信息所在的目标节点后再直接与目标 节点进行通信。这种路由方式非常简单高效，且能够支持复杂查询，但是由于 需要中心目录服务器的参与，使得系统存在与c s 类似的单点崩溃及不易扩展 等方面的问题。 第二种是结构化路由，如c h o r d 等，主要采用哈希表技术( d i s t r i b u t e d h a s ht a b l e ，d h t ) 【3 2 】技术，查找时只需将关键词进行h a s h ，得到的结果就是 放置文件指针的结点i d ，因此该方式的查找具有确定性，它具有可扩展性能 好、容错性能高等优点。 第三种是非结构化的路由。非结构化对等网地路由按照搜索策略又可以分 为两种：盲目搜索( b l i n ds e a r c h ) 和启发式搜索【3 3 】。盲目搜索也称为随机搜 索，其主要方式是通过洪泛方式在网络中检索需要的信息，如g n u t e l l a 就是采 用这种洪泛方式进行路由。洪泛路由方式中，一个节点发起信息检索请求后， 该查询消息被转发给所有邻居节点，收到查询消息的节点同样将其转发自己的 全部邻居节点。这种路由算法的实现非常简单，不要额外的系统状态信息作为 1 4 基于对等网络的搜索引擎关键技术研究 支持，也不需要中心服务器或中心目录的控制。但是这种方式会使得网络中产 生巨大的通信量，占用大量的网络带宽资源，因此导致搜索效率低下且不可扩 展。而启发式搜索的主要方式是利用一些已有的信息来辅助查找过程。启发式 搜索需要系统中保存一些资源存储的信