（计算机应用技术专业论文）基于复合优化算法的p2p文件共享系统的设计与实现.pdf

摘要 摘要 以g n u t e l l a 为代表的基于无结构型p 2 p 网络的文件共享系统，已经成为互 联网上增长最迅速的应用。但是目前主流的无结构型p 2 p 文件共享系统，基于 用户体验的考虑，在查询时往往采用洪泛机制，造成网络中查询消息数指数级 增长，浪费了有限的网络带宽，也限制了网络的规模。 p o p u l a r i t y a n di n d e x 系统，即p a l 系统是一个实验性质的原型搜索架构。p a i 系统的基本通信协议部分参考g n u t e l l a 协议，其主框架部分实现了一个完整的 无结构型p 2 p 文件共享系统。系统中的节点可以通过将文件放置于共享文件夹， 向p a l 网络中的其他节点提供文件共享服务；通过文件名作为关键字，节点可 在网络中搜索待查文件；此外，p a l 系统还支持动态性网络，允许系统中的每 个节点自由地加入或者离开网络。 p a l 系统提供了完备的算法扩充接口。通过编写功能模块，开发者可以将最 新的搜索优化算法集成到p a l 系统，迅速开发基于高效搜索算法的p 2 p 文件共 享应用。通过流行度预判，转发优化和索引发布三个算法优化模块的共同优化 作用，基于p a l 系统的新系统可在保证用户体验的前提下，大幅降低网络中的 查询消息数，提高稀缺文件的搜索成功率。 关键词：无结构p 2 p ，搜索机制，p a l 系统，文件搜索框架 a b s t r a c t a b s t r a c t u n s t r u c t u r e dp 2 p a p p l i c a t i o n ，l i k eg n u t e l l a , h a sb e c o m et h em o s tp o p u l a rn e t w o r k i n g a p p l i c a t i o n b u tm o s tu n s t r u c t u r e dp 2 pa p p l i c a t i o na p p l i e sf l o o d i n gs e a r c ha l g o r i s m ， w h i c h h a r m st h es c a l a b i l i t y , a n dr e s u l t si nt h ee x p l o s i o no fq u e r ym e s s e g e s p a ls y s t e m ，w h i c hm e a n sp o p u l a r i t ya n di n d e x ，i saf i l es h a r ef r a m e w o r kb a s e do n g n u t e l l a , w h i c hi m p l e m e n t st h eb a s i cf u n c t i o n a l i t yo fg e n e r a lf i l es h a r es y s t e m a n o d ec a ns h a r ef i l e sb ym o v i n gf i l e st ot h es h a r ed i r e c t o r y p a ls y s t e ms u p p o r t sf i l e s e a r c h ，u s i n gi t sn a m ea sq u e r yk e y p a ls y s t e ma l s os u p p o r t sd y n a m i cn e t w o r k ， w h i c hm e a n sa n yn o d ec a n j o i no rl e a v ep a ln e t w o r kf r e e l y p a ls y s t e me x p o r t sas e to fa l g o r i s me x t e n t i o ni n t e r f a c e s d e v e l o p e rc a ni n t e g r a t e t h e r eo w na l g o r i s mo p t i m i z a t i o nm o d u l et ot h ep a lf r a m e w o r k , t oi m p l e m e n tan e w p 2 pf i l es h a r es y s t e m u s i n gp o p u l a r i t yj u d g m e n t ，f o r w a r do p t i m i z a t i o na n di n d e x d i s t r i b u t i o n , t h en e ws y s t e mc a nl i m i tt h eo v e r a l lc o u n to fq u e r ym e s s a g e sa n d i n c r e a s et h es u c c e s s 戌l t eo fr a r ef i l e s k e yw o r d s ：u n s t r u c t u r e dp 2 pn e t w o r k s ，s e a r c hm e c h a n i s m ，p a ls y s t e m ，f i l e s e a r c hf r a m e w o r k i i 南开大学学位论文使用授权书 根据南开大学关于研究生学位论文收藏和利用管理办法，我校的博士、硕士学位获 得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，即：( 1 ) 学位获得者必须按规定提交学位论文( 包 括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位论文， 并编入南开大学博硕士学位论文全文数据库；( 2 ) 为教学和科研目的，学校可以将公开 的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目录检索、文 摘以及论文全文浏览、下载等免费信息服务；( 3 ) 根据教育部有关规定，南开大学向教育部 指定单位提交公开的学位论文；( 4 ) 学位论文作者授权学校向中国科技信息研究所和中国学 术期刊( 光盘) 电子出版社提交规定范围的学位论文及其电子版并收入相应学位论文数据库， 通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论文的权利。 非公开学位论文，保密期限内不向外提交和提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站：h t t p ：2 0 2 1 1 3 2 0 1 6 1 ：8 0 0 1 i n d e x h u n 。 本人承诺：本人的学位论文是在南开大学学习期间创作完成的作品，并已通过论文答辩； 提交的学位论文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。 作者暨授权人签字： 2 0年月日 南开大学研究生学位论文作者信息 论文题目 姓名学号 答辩日期年月 日 论文类别博士口 学历硕士口 硕士专业学位口高校教师口同等学力硕士口 院系所 专业 联系电话 e m a i l 通信地址( 邮编) ： 备注： 是否批准为非公开论文 注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交校图书 馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外；本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 年月日 第一章引言 第一章引言 第一节课题背景 随着p c 处理能力的增强，以及网络带宽的逐步提高，p 2 p 网络已经成为互联 网的主要应用之一。和传统的基于c s 模型的网络相比，它可以更充分地利用节 点的上行带宽和计算资源，而且可以有效地缓解服务器性能造成的网络服务瓶 颈。此外，p 2 p 网络还具有可扩充性强、容错性好、成本低、负载均衡、节约能 源的特点，因此，越来越多的应用服务转向了p 2 p 平台。c a c h e l o g i c t l j 公司的统计 数据表明，p 2 p 已经占据了5 0 以上的网络带宽，超过w e b ，成为占用i n t e m e t 带 宽最多的网络应用。与此同时，搜索效率较高的p 2 p 软件，优势也愈发明显：全 球最流行的p 2 p 文件分发软件e m u l e l 2 1 和b i t t o r r e n t 3 】产生的流量占p 2 p 总流量的 5 0 以上。 事实上，对等网络并非新技术，而是旧有技术的新应用模式。自i n t e m e t 诞 生之日起，对等计算的思想就已经存在。i n t e m e t 上最基本的t c p i p 协议也是对 等的，在最初的t c p i p 协议中，并没有客户端和服务器的概念，在通信过程中， 所有的设备都是平等的。但是限于当时个人计算机的性能，建立在t c p 1 p 之上 的软件大多采用了c s 模式。上个世纪9 0 年代后期，随着网络服务的增长，服 务器端越来越不堪重负，而客户端空闲的链路带宽被白白浪费，再加上个人计 算机的性能在速度和处理能力方面有了突飞猛迸的发展，人们开始意识到可以 把服务器软件放在个人计算机上，而且可以在个人计算机间初始化全双工的信 息流，这就导致了对等网络技术的复兴。 对等网络提供的分布式结构，可以有效均衡负载，充分利用带宽。目前的 基于p 2 p 网络的应用，已经由早期的单纯的文件共享系统向着多元化的方向发 展。到目前为止，p 2 p 技术不断发展，主要有以下几个研究和应用方向： 1 ) 文件共享服务：文件共享服务是p 2 p 目前最为广泛的应用。基本可分为 以n a p s t e r 4 乘lb i t t o r r e n t 为代表的，有中央节点进行文件索引的文件共享模式模 式和以g n u t e l l a ”，k a z a a 6 】为代表的无中央节点索引的文件共享模式。其中， 第一章引言 有中央服务器进行文件索引的模式，由于搜索方面的高效性，目前在应用领域 的份额较大，但是其鲁棒性较差，而且有版权方面的法律问题。n a p s t e r 公司由 于版权案败诉，与2 0 0 2 年6 月破产，对于后续开发者有着警示作用。而g n u t e l l a 类型的无结构p 2 p 文件共享模式，随着p c 处理能力的增强和网络带宽的拓展， 发展越来越迅速。 2 ) 分布式计算：分布式计算也是当今p 2 p 的主要应用方向。当前p c 的计 算能力已经很强，而绝大部分p c 的计算能力并未得到完全发挥。通过运行特定 的客户端，将众多p c 的计算能力集合起来，用比较低的代价，实现类似甚至超 过超级计算机的处理能力。应用实例包括s e t i h o m e t 7 】和x e n o s e r v e r s t 8 】等。 3 ) 网络存储：网络存储最主要的应用还是在于数据中心的构建，通过结构 型p 2 p 网络搭建的网络存储系统，可以在保证成本的前提下，实现海量文件的 快速搜索，存取。当然，随着个人存储设备成本的下降，以及网络带宽的提高， 一些研究项目开始采用p 2 p 技术来组织和存储数据，将传统的局域存储技术向 基于互联网的数据存储系统发展。这些项目的目标是提供面向全球的数据存储 服务。应用实例包括o c e a n s t o r e 9 1 ，p a s t l l o 】和c f s t l l 】等。 4 ) 即时通讯：目前的即时通讯工具，已经不局限与提供单一的文本交互服 务，而更多的集成语音，视频等功能。出于安全性考虑，目前的即时通信工具 虽然在提供文本交互服务的时候基本采用服务器转发模式，但是对于语音，视 频等数据量较大的通讯方式，已经更多的采用p 2 p 的通信方式，仅在建立连接 阶段由服务器进行辅助，之后的数据传输则完全是p 2 p 方式的。其应用实例包 扩i c q t l 2 1 ，m s n 1 3 】和s k y p e 1 4 】等。 5 ) p 2 p 搜索引擎：与传统搜索方式相比，利用p 2 p 可以充分检索网络上的 所有结点，并且可以通过检测网站的变化，提高搜索引擎的可达范围和数据的 刷新率。应用实例包括i i l 丘镪e a r c h 【1 5 】，p a n d a n g o 1 6 1 和g o o g l e 1 7 1 等。 6 ) 发展中的应用方向。这些方向包括：提供从多点持续测试网站性能的诊 断工具；用散布在i n t e r n e t 上的计算机来创建一个精确和实时的网络交通图；用 网络上不同地点的多个结点来检测、监测和鉴别恶意行为；利用p 2 p 技术进行 安全路由等。 当然，以上六种应用绝不是p 2 p 仅有的应用，其巨大的开发空间将成为未 来i t 界关注的焦点。p 2 p 不仅是技术革命，更是技术思想的革命，它将实现互 2 第一章引言 联网的大部分潜力，将互联网从一个基于网页和电子邮箱的网络转变成为一个 动态的、颗粒状网络。 第二节论文的选题及研究现状 p 2 p 文件共享系统具有分散化、自主性强、容错性好、信息量大等优势，因 而得到了快速发展。以g n u t e l l a 、k a z a a 、b i t t o r r e n t 等为代表的一批无结构型 p 2 p 文件共享系统，已经成为当前i n t e m e t 中最重要的应用之一。 但是这些无结构型p 2 p 文件共享系统，出于用户体验的考虑，在搜索算法 方面往往过于注重命中数和响应时间，在对于查询消息数方面的控制手段较少， 甚至从贪婪的角度，设置一个过大的搜索范围，其后果就是：对于流行文件， 系统能在较短的响应时间搜索到大量的结果，但结果可能远远超出需求，造成 网络带宽的浪费，损伤系统的可能的可扩展性；对于稀缺文件，系统在经过较 长的响应时间后，可能仍难以搜索到足够多的结果，甚至搜索不到结果造成查 询的失败。 考虑到实际文件的分布也具有很大的差异性，即整个系统中某个文件的副 本数呈现出幂律分布【l8 】【1 9 j ：约5 0 的文件拥有不到2 0 个副本，而最流行的文件 却拥有上千个副本，现有的无结构p 2 p 文件共享系统这种比较粗糙的文件搜索 方式更加难以适应目前规模越来越大的无结构p 2 p 网络，所以，需要在现有的 无结构p 2 p 文件共享系统架构的基础上，集成最新的搜索算法研究成果，将文 件搜索环节进一步细化，提高整体系统的性能和可扩展性。 目前，对于搜索优化的算法研究，大致可以归为以下三类： 1 ) 流行度预判机制。一般是利用探测、采样或其它策略，获取流经某些结 点的查询消息和返回结果的数据集合，建立相应的数学模型，以判定要查询的 文件在系统中的流行度，并根据判定结果和查询需求调整查询的规模。文章【1 9 】 提出根据q r s ( 查询结果数) 、t f ( 关键字频率) 、t p f ( 关键字对频率) 和 s a m ( 采样结果) 来判定文件的流行度。g a b 2 0 j 则实现了一种基于g o s s i p 协议 的判定方法，每个结点通过r a n d o m i z e dg o s s i p 方式与其它结点交互信息，进而 进行比较科学的判定。 第一苹引言 2 ) 转发优化机制。主要是改进g n u t e l l a 协议的洪泛( f l o o d i n g ) 机制，一般 通过提高搜索效率，增加动态控制，以及采用信息指导等方式，通过在邻居节 点中选择一个子集进行转发来实现。例女 1 r a n d o mw a l k s l 2 1 1 ，e x p a n d i n gr i n g t 2 1 】， r o u t i n gi n d i c e s 2 2 】等等。绝大多数的改进机制能够减少网络流量，提高p 2 p 系统 的可扩展性，但往往又导致结点覆盖率低、响应时间增大等不足。 3 ) 索引和缓存机制。结点索引其它结点的文件信息或者缓存流经的查询结 果。当自身进行查询或其它结点的查询消息流经该结点时，直接将索引或缓存 中的信息反馈给查询发起结点。这样能够缩短查询的响应时间并且获得更多的 结果。文章【1 9 j 就利用g o s s i p 协议，提出了一种基于概率的文件索引和搜索方案。 目前，考虑到针对的领域不同，这三种搜索优化方向的研究是相对独立的， 流行度预判机制可以减少系统的查询消息数浪费，转发优化机制可以提高整体 系统的搜索效率，而索引机制可以用比较小的代价提高文件在整体系统中的副 本数。但是正是由于他们研究的领域不同，可以通过设计一个复合型的无结构 p 2 p 搜索架构，将这三种搜索优化方向进行系统级别的集成，实现一个高效的可 扩展的无结构p 2 p 文件共享系统。 第三节本文研究内容 本文首先介绍了在无结构p 2 p 搜索算法研究的现状。然后，讨论了目前的 三种搜索优化方向的基础上，对三种优化方向的优点和不足进行了分析和总结， 并在理论上提出了将这三种优化方向统一的系统架构- - p a l 系统，并设计开发 了对应的p 2 p 客户端。 p a l 系统结合了流行度预判机制，索引发布机制与转发优化机制，在搜索效 率方面获得了以下三个方面的加强：一方面，系统可以根据流行度的计算值， 根据不同的流行度确定不同的预算，避免了查询消息的浪费；另一方面，通过 文件索引数的扩散，在不改变整体系统中文件副本数量的前提下，提高了稀缺 文件被检索到的可能性；在此基础上，通过转发优化机制，提高整体查询消息 的扩散效率。通过将这三种优化方式有机结合，p a l 系统可以再保证在减少系统 查询消息数的前提下，大幅提高稀缺文件的查询成功率。 4 第一章引言 第四节论文结构 本文共分为六个部分，具体结构如下： 第一章介绍了本文的课题背景，无结构p 2 p 网络下文件查询的研究现状， 以及本文的研究内容和意义。 第二章列述了提高p 2 p 网络搜索效率的三个方向，即流行度预判，索引信 息发布和搜索算法改进，分析了这三种优化方式的优势和不足，并在此基础上 提出了一种新的系统实现方案。 第三章阐述了该系统的整体设计方案以及各模块间的依赖关系。 第四章进一步介绍了该系统的详细设计，具体功能模块实现以及应用的技 术。 第五章介绍了两个算法扩充模块， 体实现。 第六章对论文进行了简要的总结， 即流行度判别模块和索引发布模块的具 并提出了今后的研究方向。 第二章无结构p 2 p 网络搜索算法 第二章无结构p 2 p 网络搜索算法 第一节p 2 p 网络的基本概念 2 1 1p 2 p 网络的概念 在p 2 p 系统中，每个结点都拥有对等的功能与责任，即每个结点既可以充 当服务器向其它的结点提供数据或服务，又可以作为客户机享用其它结点提供 的数据或服务；结点间的交互可以是直接与对等的。 从不同角度，存在几种p 2 p 的定义和诠释。对等计算工作组定义p 2 p 为“通 过直接交换共享计算机资源和服务” 2 3 1 ；a l e xw e y t s e l 将之定义为“以非客户的 能力使用因特网外围设备” 2 4 1 ；c l a ys h i r k y 则给出了下面的定义【2 5 】：“对等网络 是利用因特网边缘设备资源，如存储、c p u 周期、内容等的一类应用。因为访 问这些分散化的资源意味着在一个连通性不稳定和不可预测p 地址的环境中进 行，p 2 p 结点必须能够独立于d n s 系统运行，并且具有独立于集中服务器的大 部分的或完全的自治性。 通常意义上认为，p 2 p 就是一种分布式网络，网络的参与者共享他们所拥有 的一部分硬件资源( 处理能力、存储能力、网络连接能力、打印机等) ，这些共 享资源需要由网络来提供服务和内容，能被其它对等结点直接访问而无需经过 中间实体。在此网络中的参与者既是资源( 服务和内容) 提供者，又是资源( 服 务和内容) 获取者。 2 1 2p 2 p 网络的特点 在p 2 p 模式下，当某结点进行信息资源的传输活动时，会直接发送请求给 存储有源信息的对等结点；接收到请求的结点再将需要的信息直接反馈给对方。 如图2 1 所示，整个过程只需两步，即创建信息一查看信息。这与人们所熟知的 c s 模式大大不同。在c s 模式下，当用户间要进行信息资源的传输活动时，首 6 第二章无结构p 2 p 网络搜索算法 先需要构建一个有一定资源的服务器，然后在其它地方( 大多数为在个人计算 机上) 创建信息并发布到服务器上。这些信息在服务器上等待请求。接收到请 求之后，由服务器将信息传递给请求者。整个过程需要三步，即创建信息一发 布信息一查看信息，见图2 2 。 创建信息 图2 1p 2 p 模式的体系结构及信息传输过程 c l i e n t 图2 2c ，s 模式的体系结构及信息传输过程 对比p 2 p 模式与c s 模式的体系结构口6 1 ，可以得出p 2 p 模式具有以下优点： 7 第二章无结构p 2 p 网络搜索算法 1 ) 资源利用率高。在c s 模式下，集中计算方式、信息和数据都保存在服 务器端，每台服务器所能提供的信息数量受到自身存储空间的限制，导致客户 端有大量的资源被闲置。相反，p 2 p 模式下的结点同时扮演着c s 模式中的服务 器和客户端两个角色，网络上的闲散资源有机会得到利用。所有结点的资源总 和构成了整个网络的资源。整个网络可以被用作具有海量存储能力和巨大计算 处理能力的超级计算机。 2 ) 可扩展性强。p 2 p 网络的规模随着加入结点的数量的增长而增长，新结 点的加入会给系统增加新的资源。从理论上看，p 2 p 网络的可扩展性几乎是无限 的，可以达到现有的i n t e m e t 规模。而c s 模式下，随着结点的增加，服务器的 负载就越来越重，形成了系统的瓶颈，一旦服务器崩溃，整个网络也随之瘫痪。 3 ) 耐攻击，高容错。p 2 p 网络的服务是分散在各个结点之间进行的，部分 结点或网络遭到破坏对其它部分的影响很小。一般情况下，在部分结点失效时 能够自动调整整体拓扑，保持其它结点的连通性。p 2 p 网络通常都是以自组织的 方式建立起来的，并允许结点自由地加入和离开。 4 ) 基于内容的寻址方式处于一个更高的语义层次。p 2 p 模式下，用户在搜 索时只需指定具有实际意义的信息标识而不是物理地址，每个标识对应着包含 这类信息的结点的集合。这将创造一个更加精炼的信息仓库和一个更加统一的 资源标识方法。c s 模式则一般用u r l 来表示信息资源的地址，但是u r l 很少 能直接体现所定位的信息的内容，甚至不能直接链接到具体的内容上。 5 ) 易实现负载均衡。p 2 p 减少了对传统c s 结构服务器计算能力、存储能 力的要求，其资源分布在多个结点，从而更好地实现整个网络的负载均衡。 6 ) 信息在网络设备间直接流动，高速及时，降低了中转服务成本。 当然，p 2 p 模式也有不足之处。首先，p 2 p 每一个结点都可以随意的发布信 息，分散化程度较高，信息的获取比较困难。其次，p 2 p 模式允许更多的用户参 与信息交换，不易管理。随之而来的是，p 2 p 网络中数据的安全性难于保证。因 此，在安全策略、备份策略等方面，p 2 p 的实现要复杂一些。另外，由于对等结 点可以随意地加入或退出网络，会造成网络带宽和信息存在的不稳定。 8 第二章无结构p 2 p 网络搜索算法 第二节p 2 p 网络拓扑结构 按照拓扑结构可以对p 2 p 网络进行分类。目前有很多标准。按照网络结点 集中化程度的不同，可分为：纯分布式拓扑( p u r e 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 yc e n t r a l i z e dt o p o l o g y ) 和混合型分布式拓扑( h y b r i d d e c e n t r a l i z e dt o p o l o g y ) 。按照网络结构化程度的不同，可分为：非结构化拓扑 ( u n s t r u c t u r e dt o p o l o g y ) 、松散式结构化拓扑( l o o s e l ys t m c 眦dt o p o l o g y ) 和 结构化拓扑( s t r u c t u r e dt o p o l o g y ) 。 为了便于分析和论述，国内外部分学者将松散式结构化拓扑归类到非结构 化拓扑中。通常将p 2 p 网络的拓扑结构划分为四类口7 】【2 8 】： 1 ) 集中式拓扑( c e n t r a l i z e dt o p o l o g y ) ； 2 ) 分布式无结构化拓扑( d e c e n t r a l i z e d u n s t r u c t u r e dt o p o l o g y ) ； 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 ) ； 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 ) 。 2 2 1 集中式拓扑结构 图2 3 集中式拓扑结构 集中式拓扑结构的核心在于采用了中心服务器。该服务器上保存和维护着 p 2 p 网络中所有结点发布的共享资源的描述信息。用户通过中心服务器搜索资 9 第二章无结构p 2 p 网络搜索算法 源，服务器将用户需求和已发布的资源信息进行匹配，找到最合适的结点，然 后两个结点之间直接进行通讯。中心服务器仅仅提供资源的描述信息，实质性 的工作是由各个结点来完成的，这是集中式拓扑结构的p 2 p 系统与传统的c s 模式的网络系统的根本区别，如图2 3 【2 8 】所示。集中式拓扑结构的典型应用包括 n a p s t e r 、b i t t o r r e n t 等。 2 2 2 分布式无结构化拓扑结构 分布式无结构化拓扑结构的p 2 p 网络不存在居中的中心服务器，各个结点 自由地与其它结点相连。每个结点存储的资源放置在本地，不需向网络中其它 结点发送资源描述信息。文件是随机地分布在结点上的，且文件分布和网络拓 扑之间没有关联。当用户提出搜索请求时，系统将以洪泛等方式向其它结点发 送查询消息。其它结点收到查询消息后检索本地资源，如果找到符合条件的资 源则将查询结果直接返回给查询发起结点，如图2 4 【2 8 j 所示。分布式无结构化拓 扑结构的典型应用包括g n u t e l l a 、f r e e n e t 3 l j 等。 图2 4 分布式无结构化拓扑结构 2 2 3 半分布式拓扑结构 半分布式拓扑结构结合了集中式拓扑结构和分布式无结构化拓扑结构的特 1 0 第二章无结构p 2 p 网络搜索算法 点，运用了超级结点的概念。在这种拓扑结构下，p 2 p 网络中的一些性能较好的 结点被挑选作为超级结点。每个超级结点与p 2 p 网络中的一部分普通结点以集 中式拓扑的形式建立一个p 2 p 子网，由超级结点保存并维护子网中普通结点的 资源索引信息。而超级结点之间则以分布式无结构化拓扑的形式组网，如图2 5 t 2 8 j 所示。半分布式拓扑结构的典型应用包括k a z a a 、g r o k s t e r f 3 l 】和i m e s h 3 2 】等。这 3 种p 2 p 文件共享软件都是以f a s t t r a c k 协议1 3 3 j 为基础的。f a s t t r a c k 协议引入了 超级结点的概念来提高p 2 p 网络的可靠性。 图2 5 半分布式拓扑结构 2 2 4 分布式结构化拓扑结构 c h o r d 3 4 1 、c a n 0 5 1 、p a s t r y 3 6 1 和t a p e s t r y 3 7 1 是这类拓扑的代表，它们建立在 分布式哈希表( d i s t r i b u t e dh a s ht a b l e ，简称d h t ) 之上。在这些结构中，文件 会根据系统生成的标识排列。这种标识一般是对文件名进行哈希的结果。系统 中每一个结点都和一个特定区段内的标识关联，并保存关联标识对应的文件信 息。当分布式哈希表系统对标识进行查询时，相应的结点便会返回对应的信息。 分布式哈希表系统的核心是路由协议。系统中的分布式哈希表结点构成一 第二章无结构p 2 p 网络搜索算法 个覆盖网，每一个查询操作都是通过该覆盖网找到目标结点的。所以，分布式 哈希表系统的性能就取决于所采用的路由协议的效率。虽然各种分布式哈希表 系统的路由协议都不相同，但它们有一个共同的特点，就是每一个结点在覆盖 网中拥有的邻居数目为o ( 1 0 9 n ) ，完成每一次路由所需步数在o ( 1 0 9 n ) 以内，其 中n 为系统总结点数。 路由协议根据接收到的标识( 一般是一定长度的数字串) ，把信息路由到 相应的结点。每个结点也有一个标识，这个标识通常和它对应的文件的标识相 同。此外，每个结点还维护有一张路由表，记录其它一些结点的信息。当某结 点收到一个查询操作时，如果发现所查询的标识不在自己关联的区间内，就会 把该查询发送给路由表中它认为最靠近目标的邻居。各种算法中，对“最靠近 目标的定义不尽相同，但通常都是根据结点标识和目标标识进行定义的。c h o r d 采用了d h t 技术把p 2 p 结点在逻辑上组成一个环形结构；c a n 则组成了一个 t o r u s 结构；t a p e s t r y 和p a s t r y 的工作原理非常接近，都组成了超立方体结构。 第三节无结构p 2 p 搜索算法的优化 2 3 1 基于流行度预判优化 无结构p 2 p 网络中的文件分布是极度不均衡的，各种文件的流行度截然不 同。如果以整个系统中某个文件的拷贝数作为判断该文件流行度的依据，就会 发现文件的流行度呈现出幂律分布：约5 0 的文件拥有不到2 0 个拷贝，而最流 行的文件却拥有上千个拷贝。对于流行文件的查询，系统能够以较短的响应时 间搜索到大量的结果；对于稀缺文件的查询，系统在经过较长的响应时间后仍 难以搜索到足够多的结果来满足用户的需求。以g n u t e l l a 为例，有4 i 的查询 消息最终得到1 0 个或更少的结果，其中1 8 的查询没有得到任何结果。但是对 于搜索发起端，由于估计该次搜索需要范围多大才可以得到满意的结果，而只 能以平均的搜索范围来完成每次搜索：如果搜索的是流行文件，那么可能会由 于返回结果过多导致系统消息数浪费；如果搜索的是稀缺文件，那么可能会由 于搜索范围过小导致搜索失败。 如果在搜索文件之前能够对文件的流行度有一个预判，并根据文件流行度的 1 2 第二章无结构p 2 p 网络搜索算法 动态调整搜索策略，使得针对流行文件的查询返回满足需要、但不至于过多的 结果，而针对稀缺文件的查询返回尽可能多的结果。这样既能减少查询开销， 又能得到满意的查询结果。 g n u t e l l a 网络是分布式网络，拥有资源的节点分布在世界各地，要想使得所 有节点对网络中文件的流行度做出准确判断是非常困难的。而且g n u t e l l a 网络节 点加入退出频繁，这更增加了文件流行度判定的难度。 d y n a m i cq u e r y i n g t 3 s l 提出了通过探测查询的方法来判断文件流行度：查询节 点在搜索之前，先向部分邻居发起相对较小t t l 的洪泛作为探测，然后根据探 测结果预测文件的流行度，并根据文件流行度调整后续查询的t t l 值和转发的 邻居数目。该方法实现简单，但它需要改变底层网络的拓扑结构，要求每个节 点的度数至少为1 5 ，推荐使用3 0 以上。b t l o o 在论文【3 卅中提出了根据查询结 果数( q r s ) 、关键字频率( t f ) 、关键字对频率( t p f ) 和采样结果( s a m ) 来判定文件的流行度，这些判定方法都只利用了局部信息，因此判定不准确。 m z a h a r i a 在论文g a b 4 0 j 中提出了一种基于闲谈( g o s s i p ) 的文件流行度判 定方法：每个节点通过闲谈的方式与其它节点进行信息交换以获得每个文件的 全局信息，从而判定文件的流行度。与前面的方法不同，该方法能获得对文件 流行度的全局统一认识。该方法综合了用于估计集合中不同元素数量的 p r o b a b i l i s t i cc o u n t i n g 算法和用于信息交换的g o s s i p 算法【4 2 1 。其基本思想是： 当一个节点看见它没有索引的文件时，它就为该文件抛至多k 次硬币，在首次遇 到硬币反面朝上时停止抛硬币，记录下连续出现正面的次数c t 。然后该节点通 过g o s s i p 算法与其它节点交换它保存的c t 值，在每轮交换中，每个节点保存每 个文件最大的c t 值，记为m a x c t 。从概率上讲，越流行的文件所对应的m a x c t 值越大，每个节点可以根据文件所对应的m a x c t 值大小来判断文件的流行度。 基于闲谈的文件流行度判定方法具体实现如下：通过抛硬币实验来模拟 p r o b a b i l i s t i cc o u n t i n g 算法要求的哈希函数，每个节点就自己所拥有的每个文件 抛至多k 次硬币( 扮1 51 0 9 ，为p 2 p 系统中节点数目) ，在首次遇到硬币反面 朝上时停止抛硬币，记录下连续出现正面的次数c t ，将第c t 位为“1 ( 从左 边数起) 、其它位为“0 的k 位二进制数存入该文件对应的c t a r r a y 中。然后每 个节点之间通过闲谈的方法交换所有文件的c t a r r a y 值。在闲谈过程中，每个节 点把收到的c t a r r a y 值与自己的相应文件的c t a r r a y 值进行“或运算，然后保 第二苹无结构p 2 p 网络搜索算法 存“或”运算的结果。经过b g 轮的信息交换，每个节点为每个文件保存了一 个c t a r r a y 值。从左边数起，假设c t a r r a y 值中第一个“0 出现在第f 位，从 概率上讲，某个文件的副本数越多，则它的f 值也越大。该文件的副本数可大致 估计为2 0 7 7 3 5 1 ，理论上，当文件的副本数趋于无穷时，所得结果的标准误 差约为1 1 2 。 2 3 2 基于索引发布的优化 索引的方法是提高p 2 p 搜索性能最常用的策略。其主要思想是每个节点都缓 存或索引少量其他节点或历史查询的相关的信息，以提高搜索的命中率：稀缺 文件本身的特点是系统中文件的复本数较少，并且分布十分不均匀，因此使用 索引机制并采用动态索引发布算法来提高稀缺资源的数量、改善稀缺资源的分 布，是解决稀缺文件搜索问题十分有效可行的方法。 局部索引( l o c a li n d i c e s ) 策略m j 要求每个结点记录给定半径范围内所有结 点存储的文件的索引信息，因此每个结点都可代表这些结点处理查询请求。既 然节点可以代表某些其他节点处理查询请求，那么首先在消息发送之前应该有 一个策略p ，用来规定哪些节点收到消息后处理，哪些节点收到消息后不用处理 直接转发。例如：设查询半径r = 2 ，p = ( 1 ，5 ) ，那么在第一跳和第五跳收到查询消 息的节点都会处理这个查询请求，处于第一跳和第五跳之间的节点只需简单的 转发这条消息即可，算法在第五跳处终止。为了保证索引数据的有效性，这种 方法必须考虑节点加入、退出和更新时的索引维护问题。在这个方法中规定， 节点加人时必须发出t t l = r 的j o i l l 消息，并在消息中包含这个节点上所有共享 文件的索引信息，每一个收到该消息的节点必须给这个节点直接回一个j o i n 消 息，消息中也包含它们的共享文件的索引信息。同时规定一个超时来管理节点 的各种离开情况，如果这个节点有一定的次数没有响应p i n g 消息，那么缓存索 引节点就会清空关于这个已离开节点的信息。当一个节点更新了它的共享内容 时，就会发送一个t t l 为r 的u p d a t e 消息，这个消息中包含了更新的数据，收 到该消息的节点会相应地对其索引进行更新。 路由索引( r o u t i n gi n d i c e s ) 策略假设可将文档分成若干种类型，每个结点 维护一张路由信息表，记录可通过邻接结点获取的各种类型文档的数量。由各 1 4 第二章无结构p 2 p 网络搜索算法 结点根据一定度量标准，结合本地路由表信息选择具有最佳转发因子的结点， 例如选择通过该邻居方向能访问到的文件总数最大的节点。信息索引可以提高 搜索效率，降低延迟，减少消息传递。但是其深度优先的搜索方法会明显增大 响应时间，相应的带来索引维护开销也较大。 2 3 3 基于查询算法的优化 在基于改进转发机制的方法中，按照消息转发的策略，又可以分为两大类： 盲目转发策略和基于信息的转发策略。 1 盲目转发策略 1 ) m b f s ( m o d i f i e d b f s ) 方法 m b f s 方法是在洪泛( f l o o d i n g ) 算法上面作了一定修改。跟洪泛搜索方法 不同，m b f s 搜索过程只是随机的选取一定比例的相邻节点作为查询消息的发送 目标，而不是发送给所有相邻节点。相比于f l o o d i n g 方法来说，由于仅选择了 一部分结点来进行搜索，必然节省了网络流量，但查询成功率也会因此而降低。 2 ) i t e r a t i v ed e e p e n i n g 方法 i t e r a t i v ed e e p e n i n g 的迭代递增策略循环递增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 搜索方法给t t l 赋一个较大的值 不同，这种方法在初始阶段，给t t l 一个很小的值，如果在t t l 减为0 时还没 有搜索到资源，则给t t l 重新赋更大的值。这种策略可以减少搜索的半径，如 果p 2 p 网络内重复资源丰富，这种方法在不影响搜索质量的基础上将减少网络 内的查询流量，但是在最坏的情况下( 如查询稀缺文件时) ，网络流量和延迟将 变的更加严重。在有的文献中该方法亦称为e x p a n d i n g 硒n g ( 扩展环搜索) 。 3 ) r a n d o mw a l k s 方法 查询节点同时生成k 个查询消息给随机挑选的k 个相邻节点，然后每个消 息在节点之间依次随机转发传递，每路消息称为一个w a l k e r 。r a n d o mw a l k s 方 法能够显著减少搜索产生的查询消息数，但是搜索延迟较高，并且其盲目的随 机转发特性使得搜索性能得不到保证。 2 基于信息的转发策略 基于信息的转发是在搜索中采用某些启发式策略和统计信息，如选择最近返 第二章无结构p 2 p 网络搜索算法 回结果最多的邻居，或者最有可能到达目标节点的邻居等等，算法只选择部分 邻居节点进行转发，目的是减少网络中查询消息的流量。 1 ) d b f s ( d i r e c t e d b f s ) 方法 d b f s 方法将查询消息转发给可能提供更多结果或更快结果的一部分邻居， 它假定历史查询好坏能够预示将来查询的好坏。为了能够有方向的选择邻居， 每个节点都维护了其邻居的一些简单统计数据，比如该邻居以前返回的结果数， 或到该邻居的延迟。从这些统计数据中，可以启发式的选择最好的邻居来发送 查询。但如果稀缺资源恰恰存放在过去表现不好的结点上，采用d b f s 方法就 会搜索不到这类文件。 2 ) i s m ( i n t e l l i g e n ts e a r c hm e c h a n i s m ) 方法 i s m 方法是对m b f s 的改进，它将查询发送到最可能得到返回结果的邻居。 每个节点在收到消息后将当前的查询和以前的查询进行比较，按相似度对邻居 节点进行排名，然后把查询转发到最可能获得成功的节点。本质上该方法是基 于相似性的邻居选择策略，根据邻居节点的历史信息来预测未来的查询。它同 样对查询频率低的稀缺文件表现不佳。 3 ) a p s ( a d a p t i v ep r o b a b i l i s t i cs e a r c h ) 方法 a p s 是一种改进的基于信息的r a n d o mw a l k s 算法，它在转发时不是随机选 择邻居，而是根据邻居的历史概率性的选择下一个转发节点。a p s 方法增加或 者减少某个邻居的选中概率是利用反馈机制，根据乐观或悲观策略，对经常返 回结果的邻居结点增大选中的概率，反之减小其概率。a p s 方法在查询成功率 和响应时间方面都要优于r a n d o mw a l k s 方法，在一定程度上保证了查询效果， 但它对于稀缺资源的查询仍不如传统的洪泛或部分洪泛方法，因为a p s 方法搜 索的结点数目依然很少。 4 ) m s f ( m u l t i p l es m a l l s c a l ef l o o d s ) 方法 m s f 方法提出使用代理节点进行多次小规模洪泛的机制，其主要思想是将 查询请求尽量分散到可以返回尽可能多结果的区域中去，并利用小范围洪泛来 控制查询消息的数量。m s f 机制中使用最多返回结果的方法排列代理结点，并 采用同步、顺序和并行三种策略来控制小洪泛的发起顺序，使得用户可以在最 小化响应时间和尽量减少网络流量二者中作出选择。 5 ) p o p u l a r i t y b i a s e dr a n d