（计算机软件与理论专业论文）两层对等计算系统架构与概率搜索.pdf

中文摘要 对等计算( p e e r t o p e e rc o m p u t i n g ) 技术自近年以来在学术界与产业界引起 广泛的关注，许多基于对等计算技术的文件共享、数据共享、计算资源共享、即 时消息传递等应用被广泛地开发。非结构化对等计算系统具有分布式性、自组织 性、自治性、鲁棒性、维护代价小等优点，同时还有可扩展性差、搜索效率低下 等缺点。本文试图在保留非结构化对等计算系统优点的情况下，尽可能提高其搜 索效率及可扩展性。 本篇论文首先提出了一个两层的对等计算系统架构。然后定义了两种不同的 基于相似度( s i m i l a r i t y ) 的查询，第一类是基于多维向量模型的相似度查询；第 二类相似度查询是基于主题层次( t o p i ch i e r a r c h y ) 的。随后对于两种不同的搜索 问题给出了不同的搜索策略，并进行了实验分析。 本文的主要贡献有如下几点： 1 提出了一个结合结构化与非结构化对等计算系统各自优势，同时摒弃两者劣 势的两层对等计算系统架构。这个架构具有结构化与非结构化两层，在此 基础上，文章提出了节点聚类算法，通过节点聚类，相同主题的节点将被聚 类到一个小簇中，提高了查询的效率及准确性。 2 定义了基于多维向量模型的相似度查询。在两层对等计算架构上，提出了一 个自适应路由策略用以解决这类查询问题。根据查询所属的主题及节点相似 度，该搜索策略能够自动地调整路由状态。文章对这个策略进行了实验分 析，结果表明自适应路由策略在响应时间、查全率、带宽消耗及计算资源 使用率方面都优于宽度优先策略。 3 提出了一个基于主题层次的相似度查询，给出了一个概率模型( p r o b a b i l i s t i c m o d e l ) 。利用概率模型中两类概率信息，提出了基于概率信息的路由算法 及概率信息的维护算法。随后在两层对等计算系统架构上，给出了如何进 行概率路由和维护概率信息的算法，并且利用实验比较了宽度优先，随机行 走搜索策略。结果表明，基于概率信息的搜索策略从查全率、覆盖率与响 应时间都要优于其它策略，而基于概率信息搜索的性能在两层对等计算架 构中比在一般非结构化网络拓扑结构中更好。 本文首先提出了一个两层对等计算系统构架，并定义了两类基于相似度的查 粤，对于这两种查询问题在两层架构上给出了不同的搜索策略。文章所提出的技 术在非结构化对等计算信息检索中有广泛的应用前景。 关键词：对等计算，两层架构，相似度查询，概率信息 l l 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 gh a sb e e np o p u l a r i z e db o t hi na c a d e m i aa n di n d u s t r y r e c e n t l y m a n yp 2 p b a s e da p p l i c a t i o n sh a v eb e e nd e v e l o p e d ，s u c ha sf i l es h a r i n g ， d a t as h a r i n g ，c p uc y c l es h a r i n ga n di n s t a n tm e s s a g e ( i m ) u n s t r u c t u r e dp 2 ps y s - t a m sh a v es e v e r a la d v a n t a g e s ：d e c e n t r a l i z e d ，s e l f - o r g a n i z e d ，a u t o n o m o u s jr o b u s t a n dl o wi n a i n t e u a n c ec o s t 0 nt h ec o n t r a r y t h o s es y s t e m ss u f f e rf l o ml o ws e a r c h e f f i c i e n c ya n dp o o rs c a l a b i s t y t h i st h e s i sa i m sa ti m p r o v i n gt h ed i s a d v a n t a g e so f u n s t r u c t u r e dp 2 ps y s t e m sw h i l ep r e s e r v i n ga d v a n t a g e s m a i nc o n t r i b u t i o n so ft h i st h e s i si n c l u d e 1w eh a v ep r o p o s e dt h ei d e o l o g yo ft w o l a y e ra r c h i t e c t u r ef o rp 2 ps y s t e m ss o t h a tt h em e r i t so fb o t hs t r u c t u r e da n du n s t r u c t u r e da r c h i t e c t u r e sc a nb ee m p l o y e da n 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 sc a l lb ec o m p e n s a t e dw i t ht h eo t h e r 8 a d v a n t a g e sf o l l o w i n gt h a t ，w eh a v ep r o p o s e dat o p i c q u e r yb a s e ds t r a t e g y t oc l u s t e rp e e r sw i t hs a m ef a v o r i t e st h eq u e r ye f f i c i e n c ya n da c c u r a c yi s i m p r o v e ds i n c ep e e r sw i t ht h es a m ef a v o r i t ea r ec l u s t e r e dt o g e t h e r 2 佬h a v ed e f i n e dam u l t i d i m e n s i o n a lv e c t o rm o d e lb a s e ds i m i l a r i t ys e a r c h f 0 1 - l o w i n gt h et w o 1 a y e rp 2 pa r c h i t e c t u r e ，w eh a v ed e v i s e das e l f - a d a p t i v er o u t i n g s t r a t e g yf o rs y s t e m sw i t hp e e rc l u s t e rt o p o l o g yt oh a n d l et h es i m i l a r i t ys e a r c h w eh a v ec o n d u c t e da np r i m a r ye x p e r i m e n t a ls t u d yw h i c hv e r i f yo u rs t r a t e g i e s a r eb e t t e rt h a nb f s ( b r e a d t hf i r s ts e a r c h ) b a s e do nr e s p o n s et i m e ，r e c a l l ， b a n d w i d t hc o n s u m p t i o na n dc o m p u t i n gr e s o u r c eu t i l i z a t i o n 3 w eh a v ep r o p o s e da n o t h e rs i m i l a r i t ys e a r c hp r o b l e mb a s e do nt o p i ch i e r a r c h y a n dt w ot y p e so fp r o b a b i l i s t i ek n o w l e d g ea r ec o n s i d e r e d b a s e do nt h ep r o b - a b i l i s t i ck n o w l e d g e ，a na d a p t i v ep r o b a b i l i s t i cs e a r c ha l g o r i t h ma r ep r o p o s e d a n da nu p d a t ea l g o r i t h mi sd e v i s e dt ok e e pt h ef r e s h n e s so ft h ep r o b a b i l i s t i e k n o w l e d g e s e a r c ha l g o r i t h ma n du p d a t ea l g o r i t h mi nt w o - l a y e rp 2 pa r c h i t e c t u r ea r ea l s op r o p o s e d a ne x p e r i m e n t a ls t u d yi sc o n d u c t e dw h i c hs h o w s o u rs t r a t e g i e sa r eb e t t e rt h a nb f sa n dr a n d o mw a l kb a s e do nr e c a l l ，c o v e r _ a g ea n dr e s p o n s et i m ea n dp r o b a b i l i s t i cs e a r c hi sm o r ee f f i c i e n ti nt w o - l a y e r a r c h i t e c t u r e i nt h i st h e s i s ，at w o l a y e rp 2 pa r c h i t e c t u r ea r ep r o p o s e da n dt w od i f f e r e n ts i r e - i l a r i t ys e a r c hp r o b l e m sa r ed e f i n e dt w os t r a t e g i e sa r ed e v e l o p e dt os o l v et h et w o s e a r c hp r o b l e m si nt h et w o l a y e rp 2 pa r c h i t e c t u r ew h i l ea c h i e v i n gb o t he f f i c i e n c y a n da c c u r a c yt h es t r a t e g i e sp r o p o s e di nt h i sp a p e rc a nb ew i d e l ya p p l i e dt oi n f o r m a t i o nr e t r i e v a li np 2 ps y s t e m s 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 ，t w o l a y e ra r c h i t e c t u r e ，s i m i l a r i t ys e a r c h p r o b a b i l i s t i ck n o w l e d g e 图目录 2 1 混合的p 2 p 系统 22 纯的p 2 p 系统 2 3 包含超级节点的混合的p 2 p 系统 3 1 两层p 2 p 系统架构 4 1 网络传输时间 4 2 查全率 4 3 带宽消耗 44 计算资源使用率 5 1 计算机科学中的一些主题划分 5 2 反映计算机科学领域概率分布的一颗编码树 53 查全率v s 主题数 5 4 覆盖率v s 主题数 5 5 查全率v s t t l 5 6 覆盖率v s t t l 5 7 响应时间v s t t l 5 8 查全率v s 网络动态 5 9 覆盖率v s 网络动态 5 1 0 响应时间v s 网络动态 l l n u 他 丝 驰骺 驵骑蚯们蛳盯盯盯 表目录 21 一些流行的p 2 p 软件及它们的网络结构 4 1 模拟实验参数缺省值 1 x 1 1 8 1 第1 章 已i 考 ji 口 对等计算技术( p e e r t o p e e rc o m p u t i n g ，简称p 2 p ) 是一种在工业界被认为 具有广泛前景，同时在学术界又被广泛研究的分布式计算技术。这种技术可 以看作是对传统客户机服务器( c l i e n t s e r v e s ，简称c s ) 或者三层模型( t h r e e t i e r sm o d e l ) 的颠覆，与传统分布式系统相比，它具有以下这些优点：分布式性 ( d e c e n t r a l i z e d ) 、白组织性( s e r f - o r g a n i z e d ) 、可扩展性( s c a l a b l e ) 、自治性 ( a u t o n o m o u s ) 、鲁棒性( r o b u s t ) 、可用性( a v a i l a b l e ) 、匿名性( a n o n y m o - u s ) 。 由于上述这些特点，对等计算技术在学术界受到了广泛的关注，自2 0 0 1 年开 始，s i g c o m m 、i n f o c o m 等网络领域重要学术会议，s i g m o d 、v l d b 、i c - d e 等计算机领域重要学术会议先后出现了关于对等计算技术的学术论文，一些会 议还出现了对等计算技术的分会( s e s s i o n ) 。同时在工业界，自2 0 0 1 年开始，产 生了大量的基于对等计算技术的软件或者使用对等计算技术的软件系统。包括早 期的n a p s t e r 4 i 、g n u t c l l a 1 5 1 、f r e e n e t 2 5 1 以及较近一些的k a z a a 6 1 、e d o n k e y 2 一 o o o 1 4 、b i t t o r r e n t 1 3 1 ，还有更近一些的p 2 p t v 等，这些系统都有着惊人的用 户数量；同样，很多流行软件包括m s nm e s s e n g e r 1 1 1 、w o r i do fw a r e r a f t 1 6 等 都或多或少包含着对等计算技术。 一般来说，基于对等计算技术的系统从网络架构上可以分成两类：结构 化( s t r u c t u r e d ) 、非结构化( u n s t r u c t u r e d ) 。这两类覆盖网络( o v e r l a yn e t w o r k ) 在某些方面有着对立的优势与劣势。例如，非结构化对等计算系统有较好 的自组织性、鲁棒性和自治性等特点；而结构化对等计算系统具有更好的可扩展 性与查询效率等特点。虽然，现在已经有一些工作试图提高非结构化系统的查询 效率和扩展性，但是对于如何提高结构化系统的自组织性、自治性及降低维护代 价的问题相关工作不是很多，一些文献f 44 1 也指出结构化对等计算系统需要一个 更宽松的设计。本文试图在详细分析结构化与非结化系统的基础上，给出一个折 1 言 衷的两层架构，主要解决如何在提高路由效率、扩展性的同时保持系统的自组织 性、自治性及较低的维护代价。 查询处理也是对等计算的一个主要问题，其目的是探索如何高效地在对等计 算系统中提供所需的资源。结构化与非结构化对等计算系统在查询处理问题研究 上侧重点各有不同。非结构化对等计算系统查询问题主要在于如何提高查全率 ( r e c a l l ) 、查准率( p r e c i s i o n ) 及如何降低路由的消息数从而提高系统的可扩展 性。结构化对等计算系统提供了非常高的扩展性及完美的查全率与查准率，所以 查询处理问题主要在于如何提供更复杂的查询处理能力，例如，范围查询( r a n g e q u e r y ) 。本文的另一个研究目标是如何有效的在所提出的两层架构网络上解决基 于相似度的查询。 在p 2 p 系统中，许多用户都有自己特定的兴趣，针对于这些兴趣，系统可以 将资源进行分类，从而使用户更方便快捷地查找及维护资源。从另外一方面看， 用户从具有相同兴趣的节点处获得所需要信息的可能性要比从兴趣不同的节点处 获得所需信息的可能性大得多。 本章的第一节将概述对等计算目前的应用与研究。第二节介绍了结构 化p 2 p 系统与非结构化p 2 p 系统的优缺点。第三节给出了基于用户兴趣的一 些p 2 p 系统实例并简述兴趣分类方法。第四节阐述了本文的研究动机以及所面i 临 的挑战。第五节介绍了本文的组织结构。 作为简写，在本文的剩余部分，在不造成歧义的情况下，对等计算将被简写 为p 2 p 。 1 - 1p 2 p 系统应用与研究 2 0 0 0 年以来，由于个人计算机硬件条件的增强与网络带宽的提升，同时随着 网络技术的飞速发展，许多网络应用程序可以绕过防火墙进行通讯，使得节点之 间的协作、信息或服务共享成为了可能。在这种情况之下，即时信息传输和文件 共享成为最先成功的“新兴”p 2 p 应用。虽然每个节点提供的存储、计算和网络 带宽资源是有限的，但是由所有节点提供的资源和服务总和却是海量的。 目前，由于版权的问题( 例如，m p 3 的版权问题) ，一些p 2 p 网站( 例 如，n a p s t e r ) 被迫关闭。同时也由于流行的p 2 p 软件的广泛应用， 以及技术的不 断成熟，纯脆的基于文件共享的p 2 p 软件几乎没有新的推出。但是p 2 p 技术却在 许多流行软件中被广泛采用，这些软件本身并非以p 2 p 作为卖点，或者技术上的 亮点，但是却包含了部分p 2 p 技术的元素。例如，w a ro fw a r c r a f t ( w o w ) f 1 6 1 是一个当前十分流行的网络游戏，整个软件大小约1 0 g b 左右。如果从官方网站 下载，对于网络游戏广大的用户而言，几乎是不可能完成的任务，对于这个问 2 i 引言 题，w o w 提供了一个几m b 种子( s e e d ) 文件，通过该文件和已经下载完部分软 件的节点相连，通过这些节点进行游戏的下载。可以预见的是，p 2 p 技术将更广 泛的应用到各个领域的软件之中，纯粹基于文件共享的p 2 p 软件发展会受到版权 问题的制约，而在学术界被广泛研究的p 2 p 数据管理技术势必会在产业界得到应 用。 e t 前p 2 p 系统从应用来看大致分为四类：数据共享、协作或即时消息传输、 计算共享与p 2 p 平台。下面从这四种应用对p 2 p 的现状进行介绍。 在p 2 p 数据共享系统中，每个节点都向系统的其他节点共享本地的一些 数据，例如，m p 3 音乐文件。通过p 2 p 数据共享系统提供的文件查找与传输 协议，每个节点都可以从其他的节点上获取自己所需的数据。与传统的数 据共享系统不同，在p 2 p 数据共享系统中，数据本身不存放在中央服务器 上，或者本身就不存在中央服务器，而是由系统中的用户提供且存放在用户 本地。需要注意的是，虽然一些p 2 p 数据共享系统，如n a p s t e r 4 1 ，使用了集 中式目录服务器，但是服务器仅仅提供资源定位功能，而并不存储任何著 享数据。这类系统是迄今应用最广泛的p 2 p 系统，如g n u t e l l a 1 5 1 、k a z a a 6 1 、 f r e e n e t 2 5 、e d o n k e y 2 0 0 0 1 1 4 及b i t t o r r e n t 1 3 1 。 在p 2 p 协作系统中，一类应用是即时消息传输。在这种p 2 p 系统中，位于不 同地方的用户通过i n t e m e t $ 日互传递消息进行对话( 包括音频、视频或文字对 话) ，从而举行多方会议，或者互相提供文件共享。这些信息的传递是在不同 的计算机之间进行的，而这些计算机可能拥有不同的体系结构、运行不同的操 作系统。流行的即时消息传输软件有i c q g l 、m s nm e s s e n g e r 1 1 1 、a o li n s t a n t m e s s a g e 8 等。另一类p 2 p 协作系统，如j a b b e r 1 0 j 提供了基于可扩展标记语言 ( e x t e n s i b l em a r k u pl a _ i l g u a g e ，或x m l ) 的信息传输机制，希望通过传输“机 器可读( m a c h i n er e a d a b l e ) “的x m l 数据，实现应用程序之间的”对话与协作 f 除了上述两类应用，学术界更注重对等计算模型在科学计算方面的应用。这 是因为，一方面在这些领域存在着许多海量的科学计算任务，另一方面为这些科 学计算任务配备专用大型机的代价非常昂贵。计算共享p 2 p 系统为这些科学计算 任务提供了一种价格低廉的解决方案：充分利用分散在i n t e r n e t 上大量闲置的处 理器资源( c p u 资源) 来实现海量的科学计算任务。例如，用于探索外星生命 的s e t i q h o m e 5 1 、用于生物计算的f o l d i n g h o m e 1 1 。 此外，一些大型软件生产商推出了基于类p 2 p 结构的分布式平台，如微软 的n e t 3 架构与s u n 壬- n 的j x t a 2 平台。这些构架或平台的目标在于提供一种通 用的机制，使得网络中的计算机之间能够互相提供和享受服务，而不需要知道服 务提供者的来源与位置。 3 1j 言 在上述应用需求的推动下，学术界开展了大量的研究工作。这些工作大致可 分为两类：一类研究工作对于数据或者索引的放置没有限制，所以被称为非结构 化p 2 p 系统。另一类p 2 p 系统则对如何放置数据或者索引有着严格的限制，并且 具有可扩展性、查全率与查准率非常高的特点，被称为结构化p 2 p 系统。 1 2p 2 p 系统特点概述 1 2 1p 2 p 系统的一般特点 一般而言，p 2 p 系统主要具有：分布式性( d e c e n t r a l i z e d ) 、自组织性( s e l 5 o r g a n i z e d ) 、可扩展性( s c a l a b l e ) 、自治性( a u t o n o m o u s ) 、鲁棒性( r o b u s t ) 、 可用性( a _ v a , i l a b l e ) 、匿名性( a n o n y m o u s ) 的特点。并非每个p 2 p 系统都包含 所有这些特性，一些特性属于结构化p 2 p 系统，一些则属于非结构化p 2 p 系统， 接下来将阐述这些特性的意义。 分布式性传统的分布式计算系统一般存在集中式的控制，而在p 2 p 系统中，不存 在这种控制。节点通过两两之间的信息交互进行协作。缺乏集中控制造成 了系统整体信息的缺失，导致每个节点只能通过一些局部信息做出决定。这 使得p 2 p 系统永远无法得到一个全局最优的策略。另外，在p 2 p 系统中参与 的节点个数一般远大于传统的分布式系统，在没有集中控制的前提f 协调大 量节点是p 2 p 系统带来的新的挑战。 自组织性部分p 2 p 系统提供由用户或者基于某种策略自由选择网络中邻居 ( n e i g h b o r ) 节点的能力，这种能力使得节点可以选择其信赖的，或者 带宽较高的，或者与其内容较为接近的，或者具有某些其他特性的节点作为 邻居，从而提高系统的性能。这种特性给用户带来方便，也使得网络结构 变得非常动态。 可扩展性可扩展性指的是系统的性能不随着系统中的节点数增加或者减少发生大 的变化，一些非结构p 2 p 系统在可扩展性上存在着瓶颈，而结构化p 2 p 系统 则提供了非常好的可扩展性。 自治性在p 2 p 系统中，节点可以任何时间动态加入或者退出节点、节点可以以 其自身的语法( 模式) 和语义发布数据、节点可能有差异相当大的处理能 力。 鲁棒性与传统分布式系统不同，p 2 p 系统往往具有较高的鲁棒性，在一部分节点 因为某些原因退出系统时，系统仍然能够具有较高的性能。 4 j 引言 可用性可用性包括数据、计算能力、网络带宽等资源的可用性。与传统分布式系 统相比，p 2 p 系统具有高得多的可用性，因为它集合了大量的处于网络边缘 的计算机节点。 匿名性一些p 2 p 系统能够提供隐藏内容的提供者，或者内容的下载者，或者路由 中间节点的能力。部分原因是由于p 2 p 文件共享的版权问题，内容提供者不 希望自己被获知。一方面匿名也提供了更高的安全性。 1 2 2 非结构化p 2 p 系统特点概述 简单的说，非结构化p 2 p 系统就是那些对数据或者索引放置无限制的p 2 p 系 统。这类系统一般是应用最广泛的文件共享系统。有些非结构化p 2 p 系统也提供 关键字( k e yw o r d ) 查询用以定位文件。与传统c s 架构相比，非结构化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 系统中节点的退出和加入仅仅影响直接的 邻居节点。 鲁棒| 生非结构化p 2 p 系统与结构化p 2 p 系统相比，具有更强的鲁棒性，节点的加 入退出及信息的更新只影响本地节点，或者邻居节点。 维护代价小对于非结构化p 2 p 系统的客户端而言，它只需要维护本地元数据及邻 居节点信息。对于包含服务器的非结构化p 2 p 系统而言，服务器将要承担所 有元数据的维护及节点是否可用的信息更新。 可扩展。陛差非结构化p 2 p 系统具有可扩展性差的缺点，这是由于这类系统对于数 据放置及邻居选择没有任何限制，可以说这是其自组织性的优点所导致的 5 l 引言 缺点。对于不含超级节点或者服务器的非结构化p 2 p 系统，搜索效率由于缺 少足够的数据放置信息而受到影响，所以许多系统采用广播的方式来寻找 数据，这导致网络中节点数量不可能很多；而对于包含服务器或者超级节点 的非结构化p 2 p 系统，这些超级节点或者服务器本身就会成为系统可扩展性 的瓶径。 搜索效率低非结构化p 2 p 系统存在着搜索效率低的缺点，在不存在一个集中式服 务器的非结构化p 2 p 系统中，搜索在节点间或者超级节点间通过广播或者其 它形式进行传播，由于对数据的存放缺乏一个准确的了解，搜索效率无法得 到保证。使用一个集中式的服务器可以解决这一问题，但导致的结果是系 统的可扩展性受到很大影响。 1 2 3 结构化p 2 p 系统特点概述 结构化p 2 p 系统大多数是分布式散列表( d i s t r i b u t e dh a 8 ht a b l e 。简称d h t ) 的形式，当前也有许多结构化p 2 p 系统不使用分布式散列表，而用基于一种跳跃 表( s k i p l i s t ) 的结构，或者基于树( t r e e ) 的结构。结构化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 系统中是不支持副本的，这一特点与p 2 p 系统的 初衷相违背，在许多p 2 p 文件共享系统中，用户所查询及共享的往往是一些 、 最热门的文件，用户只需要找到所有副本中的一个。 6 1 引言 1 3 基于用户兴趣的p 2 p 系统及兴趣分类方法 用户兴趣在p 2 p 系统中起到两种作用：首先，对于用户而言，使用兴趣对数 据进行分类可以使用户在管理本地数据时更方便快捷；其次，从系统角度来看， 具有相同兴趣的节点可以为彼此提供更多的信息，这一特性能够提高系统的搜索 效率。 现有的p 2 p 系统对于用户兴趣给予了较少的支持，这是由于大多数p 2 p 系统采 用一个集中式的服务器或超级节点来处理用户的查询。而这些查询一般是基于关 键字的。在这种模式下，系统很难去了解一个节点的兴趣，或者给出一个明确的 兴趣定义及分类。在现有的系统中，大多数使用了文件类型的兴趣分类方式，或 者基于目录的兴趣分类方式。 b i t t o r r e n t 1 3 1 是一个提供简单兴趣分类的p 2 p 系统，通过一些网站上手动对 文件的类型、类别进行简单的归类来达到兴趣分类的目的。用户通过浏览网页来 选择正确的分类，从而寻找到目标t o r r e n t 文件。这种兴趣的分类方法由如下几个 问题：首先，类别是事先设定的；其次，t o r r e n t 文件是人为发布的，这导致类别 的选择是完全人为的：最后，这种分类方法对于节点本身没有任何描述能力。 m a z e 1 8 1 是一个基于目录兴趣分类的系统，这种划分方式使得用户能更方便地 管理本地信息，同时使搜索更具有针对性。但同样具有划分是人为的问题。 对于文件的分类在各个领域都有许多的研究，些最基本的分类方法包括如 下几种： 基于文件类型的分类最简单的分类方法既是按文件类型对文件进行划分，这种方 法的优势是划分非常简单，但问题同样突出，除了文件的类型，这类划分 方法无法提供更多的描述资源的信息。 文本分类对于文本文件，文本分类技术能够对其进行语意上的划分。通过计算每 个文本文件中单词的词频，文本分类技术能够将文本文件划分成不同的类 别，这种技术能够实现对单个节点内容的描述。这类技术较难应用在p 2 p 系 统之上，这是由于其分类结果是动态的，对于不同的数据集合所给出的分 类结果往往是不同的。 主题层次分类d b l p 1 7 是基t j 题层次的分类方法，这类分类方法特点是划分 是事先固定的，并且具有层次的结构。这类划分方法比较容易应用于p 2 p 系 统之上，但是由于其分类过程中存在重叠，所以如何处理重叠部分的信息是 这类划分方法所要面临的问题。 7 1 引言 空间划分方法这类分类方法是将数据映射到一个多维空间，然后对这个多维空间 进行划分，节点所存储的信息通过多维空间的代表点或者所属的空间来表 示其类别。这类划分的方法存在的问题是当数据分布比较倾斜时，这种方法 将使得分类的结果不均匀。 1 4 本文的研究动机与面i 艋的挑战 正如前几节所叙述的，非结构化p 2 p 系统具有很多方面的限制，主要包括下 面几个方面： 搜索效率低纯的非结构化p 2 p 系统搜索效率非常低，这是由于所采用的搜索策略 大都是启发式的，它面临这样几个矛盾：当路由表中包含大量关于数据放 置的信息时，维护代价及路由表的存储代价就会很大；当路由表中包含较少 的关于数据放置信息时，路由效率又会受到很大的影响；而且当网络中节 点增多时，任何纯的非结构化p 2 p 网络的查准率或者查全率都会受到很大的 影响。 服务器超级节点瓶颈为了提高查询效率和提高系统的扩展性，一些非结构 化p 2 p 系统采用了一个服务器或者一些超级节点来维护所有文件或者数 据的索引，但是这同样会带来两个问题，首先，使用单一的服务器或超级 节点会有单个节点失败( s i n g l ep o i n tf a i l u r e ) 的问题，其次服务器或超级节 点所维护的文件索引及处理的查询将会使服务器或超级节点的负载过重，对 于索引的更新，如果更新过快，势必增加服务器或超级节点的负载，若更 新过慢又会倒置查询准确率下降。 隐私问题使用服务器或者超级节点来维护其它节点的文件索引对于一般普通用户 而言有时是不能接受的，许多用户系统自己维护文件索引，或者由所信赖 的节点帮助其维护这些索引，而不是交由某个特定的服务器或者超级节点完 成。 同样对于结构化p 2 p 系统也具有许多方面的限制，主要包括下面几个方面 节点动态问题p 2 p 的节点是异常动态的，许多节点频繁的加入退出网络，或者在 退出网络时常常不通知网络中其他节点，这导致结构化p 2 p 系统需要定时的 发现已经退出网络的节点。并且，一旦一个节点退出网络，维护在这个节点 上的数据或者索引就不在存在了，或者索引数据在其它节点存有副本，或 者系统需要很大的维护代价。 8 1 引言 副本问题大多数结构 t - k , p 2 p n - q e 仅仅支持准确查找，在网络中不存在副本，而 在非结构化p 2 p 系统中，一个流行的文件往往存在较多的副本，在非结构 化p 2 p 系统中查找流行文件往往要更有效的多，结构化p 2 p 系统中维护流行 文件的节点则往往负载过重。 隐私问题在结构化p 2 p 系统中，每个节点所保存的文件的索引由分布式散列表指 定特定的节点，而不是保存在本地或者由节点自己选择，这会使节点的隐 私受到损害。 数据动态性问题在结构化p 2 p 中，如果数据动态性较高，索引的维护代价就会很 大，这又会引起一对矛盾，如果索引的更新比较慢，则查询的效率会下降， 如果索引更新较快，则系统的整个负载又会增加。 根据上面的叙述，可以总结出本文的研究目标，本文试图给出一种具有较高 搜索效率、本地维护索引且能够适应节点动态性的查询处理策略。索引由本地维 护能够避免上述结构化p 2 p 系统除节点动态性之外的问题，同时也能避免非结构 化p 2 p 系统除路由效率以外的问题，文本的挑战在于如何设计一种策略，在不维 护任何其他节点的文件索引的条件下，给出一种高效的路由策略，并且能适应节 点的动态性。 1 5 本文组织 本文第二章介绍了文章的相关工作，首先介绍了非结构化p 2 p 系统底层网络 及搜索策略，随后介绍了结构化p 2 p 系统覆盖网络及查询处理技术。第三章介绍 了一个结合结构化与非结构化p 2 p 系统两者优势的两层p 2 p 架构，并且详细介绍 了网络拓扑结构、节点聚类算法。第四章介绍了一个基于两层架构的自适应路由 策略及实验结果。第五章将介绍一个基于概率模型的查询处理技术，并且将阐述 如何将该技术应用于两层p 2 p 架构之下，最后给出实验结果。第六章将对本文进 行总结，并且对将来可能的研究进行展望。 9 第2 章 相关工作 学术界! 自2 0 0 0 年开始，开展了大量对于p 2 p 的研究工作，吸引了包括计算机网 络、计算机理论、数据管理等各个不同领域的众多研究人员。本章将讨论本文的 相关工作，分别从非结构化p 2 p 系统与结构化p 2 p 系统的底层网络及查询处理技 术进行阐述。 2 。1 非结构化p 2 p 系统 非结构化p 2 p 系统是最早出现的p 2 p 系统，也是晟被广泛应用的p 2 p 系统。本 节将从底层网络、搜索策略两个方面对非结构化p 2 p 系统进行介绍。 2 1 1 底层网络 图2 1 、图2 2 、图2 3 分别是混合的p 2 p 系统、纯的p 2 p 系统与包含超级节点的 混合的p 2 p 系统。表2 1 中列出了一些比较流行的非结构化p 2 p 系统。下面将从底 层网络的角度介绍这些p 2 p 系统。 n a p s t e r 从网络结构来看，n a p s t e r l 4 1 是混合型结构的p 2 p 系统，拥有一个包含1 6 0 个 节点的聚簇( c l u s t e r ) 作为其服务器。n a p s t e r 的服务器维护着如下的元数 据作为索引：1 节点所报告的每个节点的代宽；2 节点当前所贡献的文 件数；3 节点当前上传和下载的文件；4 节点所共享的文件名与文件大 小；5 节点的i p 地址。当节点每次连接入n a p 8 t e r 网络中时，将向服务器更 新这些信息。 n a p s t e r 提供了基于关键字的查询，用户通过输入关键字提交给服务器，由 服务器提供查询的结果，以文件列表的形式返回。 1 0 2 相关i 作 p 2 p 系统网络结构 n a p s t e r混合的p 2 p 系统有一个包含1 6 0 个节点的聚簇( c l u s t e r ) 作为其服务罟 g n u t e l l a纯的p 2 p 系统 f r e e n e t 纯的p 2 p 系统 f a s t t r a c k k a z a a混合的p 2 p 系统具有超级节点 e d o i l k e y 2 0 0 0混合的p 2 p 系统 b i t t 0 r r e n t 混合的p 2 p 系统 图2 l ：混合的p 2 p 系统 图2 2 ：纯的p 2 p 系统 2 相关i 作 岛一画画 轧舻i n 。d 8芦一弋 凰 图23 ：包含超级节点的混合的p 2 p 系统 在n a p s t e r 中，一个节点必须一次性的从另一个节点下载整个文件。系统不 支持从多个节点下i 载同一文件。如果下载失败，节点必须选择从另一节点 下载该文件。 对于邻居选择的问题，n a p s t e r 采用的是全手动化的方法，节点客户端程序 显示一个含有文件名，文件大小，比特率，用户报告的连接速度，单个 包传输时间( p i n gt i m e ) ，节点i d ，及用户可用性( 用户可用性这里表示 该节点提供一个上传的连接，可以即刻进行文件传输) 。用户根据这些信 息，手动的选择其邻居节点进行文件下载。 g n u t e l l ag n u t e l l a 1 5 从网络结构看是纯酗j p 2 p 系统，没有一个中央的服务器，对于索 引而言，c n u t e l l a 每个节点只保存本地的索引信息，而本地索引根据不同的 客户端程序而不同。关于如何对文件进行索引，如何进行查询与本地文件之 间的匹配在g n u t e l l a 系统中未被定义。 同n a p s t e r - - 样，g n u t e l l a 也支持基于关键字的查询。 在g n u t e l l a 中，文件通过节点i d 与本地索引来共同标识。当一个文件下载失 败时，下载该文件的节点可以通过一个“续传命令”来继续对该文件的传 输，但该命令只在提供该文件的节点重新连入网络后才有效。 对于邻居选择，c n u t e l l a 与n a p s t e r - - 样属于全手动化的方法，用户通过客户 倔 凰号禽r 凰， 葩 户画l 凰 蜃 2 相关i 作 端显示的一些信息，包括文件名，文件大小，还有包括单个包传输时间 节点i p 地址来选择邻居。 f r e e n e tf r e e n e t 2 5 1 从网络结构看是纯的p 2 p 系统，共享文件的索引由每个节点本 地保存。文件可能原来并不属于本地节点，这是由于f r e e n e t 的设计目标 是提供匿名的文件存取功能。每个文件由键值来加以区分。f r e e n e t 中有三 中键值，第一种是关键字签名键( k e y w o r d - s i g n e dk e y ，k s k ) ，是一组 由用户选取的对文件进行描述的字符串。该字符串用来生成一组公开私 人密钥，公开密钥通过散列得到文件标识。私人密钥用以对文件进行签 名及检查文件的完整性。因为不同的用户也许会选择相同的关键字签名 键，个人命名空问( n a m e s p a c e ) 被用来区分相同的关键字签名键( s i g n e d s u b s p a c ek e y ) 。公共的命名空间与描述性字符串被分别散列后进行异或 运算，再次散列后得到文件键值。第三种是内容散列键值( c o n t e n t h a s h k e y ，c h k ) ，它由对文件进行散列而取得。 在f r e e n e t 中，一个用户必须先得到或者计算出文件