（计算机软件与理论专业论文）基于对等计算的信息检索技术.pdf

论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名： 论文使用授权声明 日期：2 望生! ! 土 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全都或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 名：狲骊堕嘲幽句 摘要 摘要 对等计算( p e e r - t o p e e rc o m p u t i n g ，简称p 2 p ) ，自2 0 0 0 年中期以来迅速成 为计算机研究界和工业界关注的热点。在对等计算系统( 简称p 2 p 系统) 中，每个 节点都拥有对等的功能与责任，即每个节点既可以充当服务器向其他节点提供数 据或服务，又可以作为客户机享用其他节点提的供数据或服务：节点之间的交互 可以是直接对等的：任何节点可以随时自由地加入或离开该系统，形成一个真正 动态的网络环境。这类系统具有许多潜在优势，如系统的可扩展性、鲁棒性、信 息可用性、系统资源利用率高以及能够满足某些特殊应用需求，因而p 2 p 被认 为是未来重构基于i n t e r n e t 应用的关键技术之一。 虽然当前基于对等计算的研发几乎集中于文件共享应用，但是现有的p 2 p 文 件共享系统大都存在仅支持粗粒度( 文件水平) 、弱语义( 甚至缺乏语义) 的共 享以及系统的效率低等局限性。为了应对这些挑战，我们提出了基于对等计算的 信息检索，深入研究了这类系统的关键技术所面临的挑战，并取得了以下成果： ( 1 ) 提出了三层构架的体系结构，由下至上分别为：结构化层、非结构化 层和应用层。这种新型的体系结构集成了当前流行的结构化和非结构化 两种不同的体系结构，既充分发挥了它们的优点，又消除了它们的不足， 能够更充分地发掘对等计算的潜在优势，因而有效地支持在动态的对等 计算环境中进行信息检索。 ( 2 ) 在综合评析当前对等计算系统所采用的资源定位和查询路由策略的基 础上，提出了基于节点聚类的资源定位机制和自适应查询路由策略，使 基于对等计算的信息检索系统不但能够高效地利用系统资源，而且能够 有效地满足用户需求。 ( 3 ) 系统地研究了当前基于对等计算的信息检索系统在检索结果排序和合 并方面所面临的挑战，提出了一种全新的分布式检索结果排序和合并策 略，并解决了与之相关的问题。 ( 4 ) 进行了检索优化和节点动态分析。提出了一种与对等计算系统特性相 适应的代价分析模型和获得模型中各个代价因子系数的办法；把节点动 态性置于该模型之中，应用模糊集理论来刻画和捕捉节点的行为模式， 进行了节点模糊可靠性分析，以确定节点的可靠性。把检索优化的目标 扩展为：保证检索处理执行时间最短和系统资源消耗最少；同时保证执 行节点在整个检索处理过程中具有最高的可靠性。 ( 5 ) 基于上述关键技术，研发了基于对等计算的信息检索原型系统：p e e r l s 。 摘要 总之，本文详细论述了实现基于对等计算的信息检索系统的关键技术和测试 结果。本文的工作是建立在对相关理论和已有技术的详尽分析以及大量的实验测 试结果之上的a 实验结果表明，我们提出的基于对等计算的信息检索技术不但能 够支持语义丰富的信息检索与共享，而且能高效地利用系统资源并有效地满足用 户需求。 关键词：对等计算，信息检索，资源定位。查询路由，查询结果排序 检索优化，节点模糊可靠性分析 分类号：t p 3 1 1 a b s t r a c a b s t r a c t p e e r - t o - p e e rc o m p u t i n g 似b b rp 2 p ) h a sb e c o m eah o ts p o t i nt h e c o m p u t e r r e s e a r c ha n di n d u s t r i a lf i e l d s i nap 2 p - b a s e ds y s t e m ，e a c hp e e r ( n o d e ) h a se q u a l f u n c t i o n a l i t i e sa n dr e s p o n s i b i l i t i e s ，i 。eap e e rc a nb o t ha c ta sas e r v e ro fo t h e r s p r o v i d i n gt h e mw i m d a t a s e r v i c e s a n ds e r v ea sac l i e n to fo t h e r sc o n s u m i n gt h e i r d a t a s e r v i c e s ；f u r t h e r m o r e ，t h ei n t e r a c t i o na m o n gp e e r sc a l lb ed i r e c ta n ds y m m e t r i c ； i na d d i t i o n ，p e e r sc a nj o i ni no rl e a v ef r o mt h es y s t e ma ta n yt i m et of o r md y n a m i c n e t w o r ke n v i r o n m e n t t h i ss o r to fs y s t e m se n j o ym a n yp o t e n t i a lm e r i t s ，i n c l u d i n g s c a l a b i l i t y , r e l i a b i l i t y , h i g l li n f o r m a t i o na v a i l a b i l i t y , a n de f f i c i e n t l yu t i l i z i n gs y s t e m s r e s o u r c e s s ot h a tp 2 pi sr e g a r d e da sap r o m i s i n gt e c h n o l o g yt or e - a r c h i t e c t u r et h e f u t u r ei n t e r n e t - b a s e da p p l i c a t i o n s w h i l ef i l es h a r i n gh a sb e c o m et h em o s tp o p u l a rr e s e a r c ha n d d e v e l o p m e n tt o p i c i nt h ep 2 p c o m p u t i n gf i e l d ，e x i s t i n gs y s t e m sc a nj u s ts u p p o r ts e m a n t i c s - f r e es h a r i n g o fl a r g eg r a n u l a r i t ya n di n e f f i c i e n t l yu t i l i z et h e i ro w nr e s o u r c e s t oa d d r e s st h e s e c h a l l e n g e s ，w et a k et h e t e x tf i l e sa s s h a r i n go b j e c t s a n dp r o p o s et h e c o n c e p to f p e e r - t o p e e rb a s e di n f o r m a t i o nr e t r i e v a ls y s t e m f u r t h e r m o r e ，w ch a v ec o n d u c t e d a l l e x t e n s i v es t u d yt ot h i sn e w t y p eo fs y s t e m st oa d d r e s st h ec h a l l e n g e sr e l a t e dt oi t sk e y t e c h n i q u e sa n d a c h i e v e df o l l o w i n gc o n t r i b u t i o n s ： ( i ) w e h a v ep r o p o s e da t h r e e - l a y e rb a s e da r c h i t e c t u r e ，w h i c hi sm a d eu po f s t r u c t u r e dl a y e r , u n s t r u c t u r e dl a y e ra n da p p l i c a t i o nl a y e r t h i sn e w t y p eo f a r c h i t e c t u r eh a si n h e r i t e dt h e a d v a n t a g e so f b o t hs t r u c t u r e da n d u n s t r u c t u r e d a r c h i t e c t u r e sw h i l ee l i m i n a t e dt h e i rr e s p e c t i v ed i s a d v a n t a g e sa sw e l l ，s ot h a t t h e p o t e n t i a l m e r i t so f p e e r - t o p e e rc o m p u t i n g c a nb e e x p l o i t e d t o e f f i c i e n t l ys u p p o r ti n f o r m a t i o nr e t r i e v a li nt h ed y n a m i cp 2 p e n v i r o n m e n t ， ( i i ) b a s e do nt h ec o m p r e h e n s i v ea n a l y s i so nt h ee x i s t i n gr e s o u r c el o c a t i o na n d q u e r yr o u t i n gs c h e m e s ，w e h a v ep r o p o s e dap e e r - c l u s t e r i n gb a s e dr e s o u r c e l o c a t i o nm e c h a n i s ma n da s e l f - a d a p t i v er o u t i n gs t r a t e g y , w h i c hc a n e f f i c i e n t l yu t i l i z es y s t e m s l 屯s o u r e e sa n de f f e c t i v e l ys a t i s f yu s e r s d e m a n d s ( i i i ) w eh a v es y s t e m a t i c a l l ys t u d i e dt h ec h a l l e n g e sr e l a t e dt or a n k i n ga n d m e r g i n g t h ea n s w e r sr e t r i e v e df r o md i f f e r e n t p e e r s i nap 2 p b a s e d i n f o r m a t i o ns y s t e m ( e g p e e r l s ) ，a n dh a v eo b t a i n e dad e e pi n s i g h tt oi t s u n d e r l y i n gd i a t h e s i s f u r t h e r m o r e ，w eh a v ep r o p o s e daf u l l yd i s t r i b u t e d r a n k i n ga n dm e r g i n gs t r a t e g yf o rp 2 p b a s e di n f o r m a t i o nr e t r i e v a ls y s t e m s 6 a b s t r a c l a n da d c i r e s s e dr e l e v a n ti s s u e s ( i v ) w ch a v e c o n d u c t e da n a n a l y s i s o n r e t r i e v i n go p t i m i z a t i o na n dp e e r d y n a m i c sf o rt h ep 2 p b a s e di n f o r m a t i o nr e t r i e v a ls y s t e m s s p e c i f i c a l l y ，w e h a v e p r o p o s e d ah i g l ll e v e lc o s tm o d e lf o rt h i ss o r to f s y s t e m sa n dd i v i s e da n a g e n t b a s e ds t r a t e g yt oo b t a i nt h ec o e f f i c i e n t so ft h em o d e l f u r t h e r m o r e ， w i t ht a k i n gt h ed y n a m i c so f p e e r sa saf a c t o ro f p 2 ps y s t e m s c o s t w eh a v e p r o p o s e daf u z z yc o s ta n a l y s i so np e e r s d y n a m i c s ，i e ，w eh a v ee m p l o y e d t h ef u z z yt h e o r yt od e p i c ta n dc a p t u r et h ep e e r s b e h a v i o ra n di d e n t i f yt h e i r r e l i a b i l i t y c o n s e q u e n t l y ，t h eg o a l o fr e t r i e v i n g o p t i m i z a t i o n h a sb e e n d e f i n e da st h ec o n d u c t i n g p e e r sm u s ts a t i s f yt h ed e m a n do fr e l i a b i l i t yd u r i n g t h er e t r i e v i n gp r o c e s s i n g ，w h i l et h er e s p o n s et i m em u s tb es h o r t e s ta n dt h e s y s t e m s r e s o u r c e sm u s t h ee f f i c i e n t l yc o n s u m e d ( v ) b a s e d o nt h ek e y t e c h n i q u e sd e s c r i b e da b o v e ，w eh a v ei m p l e m e n t e dp e e r l s ： a p r o t o t y p eo f p 2 p b a s e di n f o r m a t i o nr e t r i e v a ls y s t e m i naw o r d ，t h i st h e s i sh a sd e t a i l e dt h ed e s i g n ，k e yt e c h n i q u e sa n d e x p e r i m e n t a l r e s u l t so fap 2 p b a s e di n f o r m a t i o nr e t r i e v a l s y s t e m ，w h i c hh a v eb e e nr e a l i z e di n p e e r l s a l lt h e s ec o n t r i b u t i o n sa r ea c h i e v e dt h r o u g hac o m p r e h e n s i v es t u d yo nt h e r e l a t e d t h e o r i e s ，e x i s t i n gt e c h n o l o g i e s a n d e x p e r i m e n t a lr e s u l t s m o r e o v e r ，t h e e x p e r i m e n t a lr e s u l t sh a v ev e r i f i e ds u c hap 2 p b a s e di n f o r m a t i o nr e t r i e v a ls y s t e mc a n r e a l i z e f u l l ys e m a n t i ci n f o r m a t i o nr e t r i e v a la n ds h a r i n go ff i n e g r a n u l a r i t y ，a n d e f f i c i e n t l yu t i l i z et h es y s t e m sr e s o u r c e 粥w e l l k e y w o r d s ：p e e r - t o p e e rc o m p u t i n g ，i n f o r m a t i o nr e t r i e v a l ，r e s o u r c el o c a t i o n ，q u e r y r o u t i n g ，q u e r i e d r e s u l t r a n k i n g ，r e t r i v i n g o p t i m i z a t i o n ，f u z z yp e e r r e l i a b i l i t ya n a l y s i s 7 第一章绪论 第一章绪论 在本章，我们论述选题背景、研究目标和主要贡献，并指出本研究的理论意 义和实际意义。 1 1 选题背景 本节首先阐述对等计算出现的社会经济和技术背景；接着描述对等计算的特 征和潜在优势：最后论述了对等计算的研究进展。 1 1 1 社会经济和技术背景 最近十几年，计算机理论与技术日新月异。计算机系统的体系结构迅速演化： 首先从传统的集中式演变为客户机服务器模式1 ；随着i n t e m e t 的发展，这种模 式进而发展为浏览器应用服务器数据库服务器模式。与此同时，计算机、网络 传输设施和其他数字设备的性能保持类似于摩尔定律式的增长，计算网络系统的 信息、带宽和计算资源已经相当丰富，系统的能力也得到很大的提高，能够支持 多种新型的基于i t 的应用，使得网络计算在社会经济、科学研究、工业生产等 领域中扮演着关键的角色，成为经济发展乃至社会进步的强大推动力。并且，随 着社会经济和科学技术的发展，出现了许多新型的基于i t 的应用需求。如电子 商务、远程协作等动态的分布式应用，它们内在地要求采用分布式计算模式并保 持各参与节点的自治性；还有一些应用，如基因分析、天气预报与气候预测等要 求超强的计算能力以处理海量的数据。简而言之，社会经济和技术的发展使得计 算机网络系统的信息、带宽和计算资源能够支持许多新型的基于i t 应用的研发， 同时提出了许多新型的基于i t 应用的需求。然而，当前流行的客户机朋务器计 算模式远远未能充分利用计算机网络系统的信息、带宽和计算资源【g 0 2 。因此， 亟待研究和开发出新型的计算模式，以高效地利用系统资源、有效地满足各种应 用。对等计算正是在这样的社会经济与技术背景下受到关注并成为研究热点的。 1 1 2 对等计算及其潜在优点 对等计算( p e e r - t o p e e rc o m p u t i n g ，简称p 2 p ) ，自2 0 0 0 年中期以来迅速成 为计算机研究界和工业界关注的热点。在对等计算系统( 简称为p 2 p 系统) 中， 每个节点( p e e r ，如用i n t e r a c t 连接起来的p c ) 都拥有对等的功能与责任，即每 1 客户机，服务器模式简称为c s ( c l i e n t s e r v e r ) 模式系统有一个中心服器务负责整个系统的文件维 护和计算，所有客户机向服务器发出请求并得到服务嚣的响应。 g 第一章纬论 个节点既可以充当服务器向其他的节点提供数据或服务，又可以作为客户机享用 其他节点提供的数据或服务：节点间的交互可以是直接与对等的；每个节点可以 随时自由地加入和离开系统，形成一个真正动态的网络环境。虽然对等计算至今 还没有公认的定义，但以下5 个特征使它明显区别于其他计算模式： ( 1 ) 节点对等性。系统中的任意一个节点都可以充当其他节点的服务器， 向其他节点提供数据或服务；也可以作为其他节点的客户机，享用其他 节点提供的数据或服务，节点功能和职责对等。 ( 2 ) 节点自治性。系统中的任意一个节点主要关注本地的事务；可以独立 自主地决定本地文件的共享范围( 哪些文件可共享) 以及共享权限等； 并且当节点离开p 2 p 系统时仍然是一个功能完备的计算机系统。 ( 3 ) 节点动态性。系统中的任意一个节点可以随时加入网络，也可以随时 离开网络。相对而言，在采用c s 体系结构的系统中，服务器( s e r v e r ) 通常以7 2 4 的方式工作，客户机( c l i e n t ) 的扩展和退出以及它们的 行为模式都有规律可循。由于节点的自治性和系统稳定性的影响，在 p 2 p 系统中考虑的动态性不同于传统的分布式计算中考虑的动态性。在 一般分布式系统中，对动态性的考虑主要包括系统的纠错与恢复等问题 c d k 0 1 】，而在p 2 p 环境下，对于动态性的考虑主要围绕如何利用当前 所有可用的资源提供最好的服务而展开。此外，系统的动态性还体现在 数据的动态性上。 ( 4 ) 无集中控制和大规模分布性。p 2 p 系统是彻底的分布式系统，在系统 层面上可以没有任何集中式机制。传统的分布式计算系统中一般存在集 中式的控制，而在对p 2 p 系统中，这样的控制不存在。所以，在保持 节点自治性的同时，节点间必须有一定程度的协作。此外，缺乏集中控 制还造成系统整体情况信息的缺失每个节点都通过有限的局部信 息做出决定。这样造成的后果可能是系统不能以全局最优的策略完成某 个特定任务。另一方面，p 2 p 系统中参与的节点个数一般远远大于传统 的分布式系统中的节点个数。在没有集中控制的前提下协调大量节点是 p 2 p 系统和传统分布式系统的主要区别之一。 ( 5 ) 系统自组织性。p 2 p 系统中的节点可以根据某种规则( 如“利润最大 化”原贝t j p r 9 5 】，以最少的代价( 消耗的带宽和计算资源最少) ，获得 最大的利润( 查询时间最短、最多的合格答案) ) 来决定自己的邻居节 点，整个网络将形成许多基于不同兴趣的虚拟社区。 随着研究的广泛开展，对p 2 p 系统的认识也越来越深入，已经取得的研究 成果表明，这类系统至少具备以下5 个潜在优势： 9 第一章绪论 系统的可扩展性好。对于p 2 p 系统而言，每个新节点的加入都会给系统带 来新的信息资源、带宽和计算资源，因而。系统的资源会随着节点的加入 而丰富，系统的能力会随着节点的增加而增强。 系统的鲁棒性好，因为在系统层面可以没有任何集中式机制，p 2 p 系统不 会出现c s 模式存在的单点出错。此外，在一般情况下，系统中的每个节 点同时有多个邻居节点( 直接相互联接的两个节点定义为邻居) ，某个或 某些节点的失败或离线不会严重影响系统中的其他节点，所以，p 2 p 系统 内在具有鲁棒性。 信息可用性好。在p 2 p 系统中，尤其是在以信息共享和信息各份为主要应 用目标的系统中，一个节点在维护本地用户信息的同时，还可以备份其他 节点的信息。因而，当某个或某些节点失败或离线时，仍然可以从其他节 点获得备份的信息。 系统的资源利用效率高。在p 2 p 系统中，当节点的本地用户没有提交事务 或处理本地用户事务的工作负荷不高时，它可以响应远程节点发来的请 求，向其他节点提供服务。如s e t i h o m e 【s e t i 就是利用对等节点的空闲 时间的计算资源，以屏幕保护程序的形式来完成巨额的计算工作。因而， 系统在几乎不增加软硬件成本、管理和维护费用的情况下，就能完成额外 ( 甚至巨额) 的处理任务，使得系统的性价比高。 能满足各种应用需求甚至特殊应用需求。由于p 2 p 是- t o e 具有上述四种特 性的通用计算模式，因而能够有效地支持各种应用的开发。并且，正如前 面所述，p 2 p 在系统层面可以完全消除集中式控制机制，系统可以在几乎 没有集中管理的情况下运行，因而这类系统可以满足许多特殊的应用需 求，如匿名电子邮件服务等。 正因为对等计算具有许多潜在的优点，并能支持许多新型应用的研发，因而 被认为是重构未来基于i n t e r a c t 应用的关键技术 g h l 0 1 1 。 1 1 3 研究现状 对等计算研究热的兴起首先是从应用开始的，并迅速受到工业界和研究界的 关注。目前越来越多的政府和国际组织也成为对等计算研究的主体。 在应用方面，自2 0 0 1 年以来，已经研发出大量的基于对等计算的软件系统， 主要有文件共享和即时消息传递两类。其中较为著名的包括早期的n a p s t e r 【n a p s t e r 、g n u t e l l a 【g n u t e l l a 和i c q i c q ，以及当前流行的k a z a a 【k a z a a i 、 m o r p h e u s 【m o r p h e u s 、m s nm e s s e n g e r 【m s n 和o i c q o i c q 等。它们的用户群 从早期高校学生扩展到当今的大多数i n t e m e t 用户，并且用户总数量始终保持着 第一章绪论 上升的趋势。据统计，到2 0 0 3 年9 月，当前最流行的基于p 2 p 的多媒体文件共 享平台k a z a a 的下载次数已经达到2 3 0 ，3 0 9 ，6 1 6 次【k a z a a 】。基于p 2 p 的即时 消息传递( i n s t a n tm e s s a g e ) 就是不同的用户通过网络( 般是i n t e r n e t ) 相互递 送消息进行对话。这与同一台主机不同终端用户之间的消息传递是不同的，因为 消息的传递是在两台不同的计算机之间进行的，这两台计算机甚至可能拥有不同 的体系结构、运行不同的操作系统。除了简单的文字消息传递以外，这些即时消 息传递软件一般还提供多方文字会议、文件共享、即时音频对话甚至即时图象传 输功能。在著名的即时消息传递软件中，t c q i c q 曾经是下载量最大的共享软 件。除此之外，还包括a o li n s t a n tm e s s a g e ( a i m ) a i m 、y a h o o ! m e s s e n g e r 【y a h o o 】、m s nm e s s e n g e r m s n 等。当前，国内最流行的即时消息传递软件是腾 讯公司的o i c q 【o i c q l ( 简称q q ) 。自1 9 9 9 年第一个q q 测试版推出之后，q q 用户迅猛增长，最高在线人数以每年超过1 0 0 万人数的速度增长，并于2 0 0 1 年 2 月首次突破最高同时在线人数1 0 0 万大关。2 0 0 4 年3 月初腾讯发布q q 2 0 0 3 i i i 正式版后，最高同时在线人数在不到1 个月的时间内再创新高，突破6 0 0 万。腾 讯q q 最高同时在线人数发展历程如下图所示： r 增 ：普 一 摄 - ，l 阿三d ，d 是节点注册的l i g l o 的i p 地址，n o d e l d 是l i g l o 为节点分配的。因此，节点名字只需对于本服务器唯一。 在不同的l i g l o 注册的节点名字可以相同。因此，命名资源不会受到限 制。 可扩展性。系统l i g l o 可以随意增加，不会影响已有的网络环境。 支持临时网络地址。l i g l o 定义了自己的协议，用b p i d 代替了动态i p 地址。 3 3 5 实验分析 在本节，我们对具有上述四个特性的b e s t p e e r 平台进行了性能测试。在的实 验中，网络中的每个节点都安装b e s t p e e r 软件。我们设置了若干个l i g l o 服务 器，所有节点都在l i g l o 服务器上登记。我们在不同的网络拓扑结构下进行实 第三章体系结构j ，r 靠 验，来比较b e s t p e e r 系统和单线程c l i e n t s e r v e r 体系结构( s c s ) 、多线程 c l i e n t s e r v e r 体系结构( m s c ) 的性能。 c s 与p 2 p 晟根本的区别是，在p 2 p 结构中任意一个节点可以是客户也可 以是服务器：而在c s 结构中只能有一个进程称为服务的提供者，其它进程必须 是服务的接受者。在实验中，我们还比较了b e s t p e e r 协议和g n u t e l l a 的协议。比 较中，我们设计了两个版本的b e s t p e e r 系统不可以重新配置的静态b e s t p e e r ( s t a t i cb e s t p e e r ) ，用b p s 表示；具有重新配置特性的动态b e s t p e e r ( r e c o n f i g u r a b l eb e s t p e e r ) ，用b p r 表示。这可阻使我们观测到动态配置策略的 优越性。实验表明具有重新配置特性的动态b e s t p e e r 系统具有更好的性能。在我 们讨论实验结果以前，我们将先提出一种评估p 2 p 系统的方案。 评估方法 任何系统都必须考虑两方面的因素：有效性( e f f e c t i v e n e s s ) 和效率 ( e f f i c i e n c y ) 。前者是考虑系统返回结果的质量：而后者则是考虑性能方面的表 现。不像现有的分布式系统，目前还没有一个清晰的评估p 2 p 系统的标准。类 似于i n t e m e t 搜索，p 2 p 系统的查询结果依赖于所搜索的节点，很可能不包括网 络中的所有节点。而且，由于节点的动态性，同样的查询在不同时期可能会涉及 不同的节点。为了能有效的评估，建立个可控的网络环境是必要的。我们提出 了三种评估的方案：首先，基于固定数目的节点来评估不同的方案。这对于研究 利用p 2 p 技术实现一组节点间的协作是有用的。例如，考虑在传统的分布式环 境中，所有的节点都会响应一个查询，这里我们可以研究p 2 p 协议或自配置策 略的性能和传统的技术有多大的不同。 其次，在p 2 p 环境中，结果返回的速率是非常重要的一个评估指标。这是 因为用户对于那些p e e r 将返回查询结果以及有多少p e e r 将会被搜索是一无所知 的。所以过长时间的等待将不会被用户所接受。 第三，结果返回的质量和数量也是重要的评估指标。一个节点可能会很快的 返回查询的结果，但是查询结果可能很少或是很查询不是太相关。尽管质量是基 于查询语意的，但是查询结果的数量更容易获得并作为评估的标准。 实验环境 实验是在3 2 台装有p e n t i u m 2 0 0 m h z 处理器，6 4 m 内存的p c 机上进行的。 机器的系统配置如下：9 台机器安装w i n n t 4 0 ，2 2 台机器上安装w i n d o w s 9 8 ，l 台机器上安装w i n d o w sm i l l e n n i u m 。网络的物理结构如图3 4 所示。实验展现的 结果对应于至少三次操作的平均。 3 7 第三章体系结构t j - , f 弁 凰昌凰昌昌凰 宣瓤酹辆 9 喇衄肾l 广百昌幢 p e 甘l p r 盲：彳= 吉；盖司p e 吖 p e e r h 值直幢79 毽色盲 圈3 4 实验环境 实验中为每一台机器安装了一个叫做s t o r m 的完全基于j a v a 的永久存储管 理程序 b g 0 9 9 ，c k p 9 8 1 。节点中可以共享的数据存储在s t o r m 中。在实验里， 每个节点的s t o r m 中存储了1 0 0 0 个共享对象，a g e n t 可以通过s t o r m 的接口访 问这些对象。评估试验实现了与s t o r m 对应的s t o r m a g e n t 。可以使用s t o r m a g e n t 输入用户请求，搜索整个b e s t p e e r 网络。这么做的目的是用s t o r m 中的对象完成 用户查询的匹配。 s t o r m a g e n t 的搜索过程是这样的： 发送s t o r m a g e n t 。查询提交节点将a g e n t 发送给与自己直接相连的邻居。 执行s t o r ma g e n t 。接收到a g e n t 的节点产生一个线程执行a g e n t 。 - 与s t o r m 对象交互。a g e n t 将请求与共享s t o r m 数据库中的每一个对象 相比较，所有匹配的结果被保存在一个临时数组里。 - 返回结果。结果返回给发出请求的节点。 实验还在当前版本的b e s t p e e r 系统中结合了g z i p 数据压缩算法。所有用于 节点问通讯的a g e n t 和消息都被表示成压缩格式。压缩和解压缩由b e s t p e e r 平台 自动完成，对平台上的软件开发人员是透明的。 拓扑结构 我们首先在不同的网络拓扑结构下评估b e s t p e e r 系统，即在星型、树型、线 型网络结构下进行实验( 如图3 5 ) 。在星型结构下( 图3 5 a ) 中心节点是查询的 发起节点，其他节点和中心节点直接相连。在树型结构( 图3 5 b ) 中，根节点是 查询的发起节点，除叶子节点外的所有节点均有k 个直接相连的节点。在线型结 构( 图3 5 e ) 中，除了两端的节点。每个节点均有两个直接相连的节点。这里我 们用最左边的节点发起查询。 第三章体系结构与、f 台 p o e t 绀s t 0 9 0 d g y( b ) 1 加p 出o o ： 凰凰再器鬻县 p 日p 窿 p e er 5 ( 0i m e t o p 幽斟 图3 5 实验中使用的不同拓扑结构 实验中我们变换节点的数目从l 到3 2 ，每一种策略运行多次，使用完成时 间( c o m p l e t i o nt i m e ) 作为性能标准。完成时间是指网络所有节点的查询结果都被 收到的时间。图3 6 显示了不同拓扑结构下的实验结果。 d 一 t ( ) 星型结构树型结构 图3 6 不同拓扑结构下的实验结果 第三章体系结构一j r 台 ( 1 ) 星型结构。图3 6 ( a ) 显示星型结构的实验结果。首先，我们注意到静 态b e s t p e e r ( b p s ) 和自配置b e s t p e e r ( b p r ) 具有相似的表现。这是因为在星 型结构中，这两种方案没有差别。正如结果显示的，随着我们增加网络的规模， 单线程c s ( s c s ) 比别的模型表现要差，这是因为s c s 在任何时候仅处理一个 连接，它必须在处理完成对一个节点的操作才能转向另一个节点的操作。我们还 注意到m c s 和基于b e s t p e e r 方案的性能均显著好于s c s 。这是因为这两个方案 都试图并行处理多个连接并将查询同时传输给所有邻居节点。我们还观察到 m c s 要轻微的优于b p s b p r 。我们会在讨论树型和线型结构时对此做进一步的 解释。由于s c s 的性能很差，我们将不再对其做进一步讨论。在下面的实验里， 我们仅考虑m c s 。为简便起见，我们把m c s 用c s 表示。 ( 2 ) 树型结构。图3 6 ( b ) 显示树型结构的实验结果。在该实验中，我们在 第5 级用4 8 个节点而不是6 3 个节点。我们得到了一些有趣的结果。首先，我们 注意到c s 比b p s b p r 要性能优越。这是可以预料的，因为b p s b p r 本质上是 代码传输策略：不仅要传输a g e n t 到p e e r ，同时还有额外的在p e e r 端a g e n t 的构 造开销。而在c s 模型下，只需要简单地将查询提交到s e r v e r ，然后由s e r v e r 端 的算法处理查询。因此，当树型结构仅有一级时，c s 的性能要优于b p s b p r ( 即 星型结构) ，但是当树型结构的级数增加时，c s 的性能开始下降。这是因为c s 需要数据按照查询的原路径返回。而b p s b p r ，查询结果直接被返回到查询节 点。 尤其重要的是，b p r 明显优于b p s 。这是由于b p r 能够通过自配制策略使 网络结构变的更优。b p s 却不得不总是传递查询给同样的节点，而不管它们是否 提供了查询的结果。 ( 3 ) 线型结构。线型结构的实验结果( 图3 6 ( c ) ) 显示了和星型结构类似 的行为。本质上，不同的方案在线型结构上表现出和树型结构同样的相对性能。 例如，在大多数情况下，b p r 要优于b p s ，而b p s 要优于c s ( 除了在网络节点 数量很少时) 。 请求的响应时问 实验分别考察了静态b e s t p e e r 、动态b e s t p e e r 、c s 模型上查询结果的返回时 间。实验中，节点的数量是3 2 ，实验使用树型结构。一个查询被发出4 次，实 验结果取4 次的平均值。实验结果如图3 7 。 第三章体系结构o 、f 台 囝3 7 查诲结果返回军 在图中，点( k ，t ) 表示在t 时间后得到k 个节点的响应。注意到在不同 的模型下，不同的节点会以不同的速度返回不同的查询结果。关于这点的讨论将 留到下一个实验中。整个实验中动态b e s t p e e r ( b p r ) 的性能一直是比较好的， 在进行若干次查询以后，动态b e s t p e e r 会进行重新配置，所以在以后的查询中节 点可以直接访问有益的p e e r 。实验中注意到，c s 结构返回结果比b e s t p e e r 要慢 ( 除了在最开始的几个节点的时候) 。这是由于查询结果在c s 中要按原查询路 径返回。 结果的质量 只有高的响应速度是不够的，所以要对返回结果的质量进行比较。因为有可 能那些响应迅速的节点仅提供了为数很少的查询结果。在这里考虑的质量就是返 回结果的数量。在早先的实验中记录了每个节点返回查询结果的数量。 n 山a f憎n j b l f ( i ) 第一个投蒙壹询彻t 后一个搜幂童询 图3 8 查询返回结果数 图3 8 显示了该实验的结果。显然，c s 最先返回的结果要比b p s b p r 都快。 第三童体系结构与平台 这是由于在c s 下，最先直接相连的收到查询后立刻将结果返回。而对于 b p s b p r ，代码传输的开销使得最初的响应会有所滞后。但是当更多的结果返回 时，b p s b p r 要优于c s 模型。这显示了p 2 p 模型要优于传统的c s 模型。还 注意到b p r 的性能要总体优于b p s 。 b e s t p e e r 与g n u t e l l a 的比较 f u r lf f u r i 是一个基于g n u t e l l a 协议的j a v a 程序，通过该程序节点可以加 入到的g n u t e l l a 网络。它是一个具有用户界面的完整程序，提供了绝大多数 g n u t e l l a 系统的功能。在该实验中将比较g n u t e l l a 和b p r ( 下面用b p 来表示 b p r ) 。实际上g n u t e l l a 系统与静态b e s l p e e r 类似( 例如个节点有固定数目的 p e e r ，没有动态的配置策略) ，所以只对g n u t e l l a 和动态b e s t p e e r 进行比较。该 实验中，每个节点有1 0 0 0 个可共享的文本文件( 由于从【f w 获得的代码仅能评 估在文本文件中的关键词检索) 。实验还预先设定查询结果仅从固定的若干个节 点中返回。这样，完成时间就由所有查询结果返回的时间决定。实验重复单的 查询4 次。通过若干次实验获得平均的结果。实验结果如图3 , 9 所示。 ( a ) p e e r 数目= 8 n 口r o f m t _ p _ h ( b