（计算机软件与理论专业论文）基于p2p的视频下载系统的设计与实现.pdf

浙江大学硕士学位论文摘要 摘要 近年来，随着中国宽带互联网络发展迅速，基于口的各种互联网应用层出不 穷，其中对视频节目的下载需求也逐渐增大，但是传统的视频下载服务主要是采 用c s ( 客户端服务器) 模式，服务器以单播的方式和每个客户建立连接。随着 客户数目的快速增加，服务器的带宽等资源很快被消耗完，成为系统瓶颈所在， p 2 p 技术作为解决集中式服务方式的诸多技术弊端，充分利用网络资源的一种解 决方案，应用日益广泛。 本文对p 2 p 技术进行了研究，提出了一种基于k a d e m l i a 协议的p 2 p 视频下 载模型，然后对该模型提出了设计方案并设计实现。 本文的主要工作包括以下几方面： 第一、围绕p 2 p 技术，介绍了p 2 p 的基本概念，并从内容发布技术发展的角 度，研究了p 2 p 技术的当前进展，总结了研究现状。 第二、针对p 2 p 网络模型和p 2 p 信息检索技术进行了研究，分析对比现存主 要的p 2 p 网络拓扑结构，指出各种结构的优缺点，并介绍各种网络结构的代表性 产品的实现原理。 第三、研究了k a d e m l i a 协议，为模型的提出进行理论上的铺垫。 第四、提出了基于k a d e m l i a 协议的p 2 p 视频下载模型，同时详细的分析这 种模型的特点以及服务器、客户端的设计。 第五、p 2 p 视频下载模型实现技术研究。结合实际应用需求，从系统层面进 行设计并实现了该系统。 关键词p 2 p ，k a d e m l i a ，信息检索 浙江大学硕士学位论文 a b s t r a c t n o w a d a y s , w i t ht h ef a s td e v e l o p m e n to fb r o a d b a n dn e t w o r ka n da l s od u et ot h e a p p e a r a n c eo fv a r i o u si n t e r n e ta p p l i c a t i o n sb a s e do nm t h ed e m a n df o rv i d e o d o w n l o a ds e r v i c eb e c o m e sm o r ec r i t i c a l ，b u tt h et r a d i t i o n a ls t r e a m i n gm e d i as e r v i c e s a r em a i n l yb a s e do nc s ( c l i e n t s e r v e r ) m o d u l e s i n c es t r e a m i n gm e d i as e r v i c eh a s t h ef e a t u r eo fh i g hb a n d w i d t ho c c u p a t i o na n dl o n gd u r a t i o n , t h er e s o u r c e so fs e r v e r s s n c ha sb a n d w i d t hw i l lb ec o n s u m e dq u i c k l yi nt e r n lo fr a p i di n c r e a s e0 fu s e r s t h i s w i l lb e c o m et h eb o t t l e - n e c ko ft h es y s t e m p 2 pt e c h n o l o g y , a sas o l u t i o no fl a c ko f c e n t e rs e r v i c e s ，h a s a l r e a d yb e e nw i d e l yu s e dt o d a y t h i sp a p e rp r o p o s e san e wp 2 1 v i d e od o w n l o a dm o d e lw i t hk a d e m l i aa n da l s o p r o v i d e sat h e o r yf o rt h ed e s i g na n dr e a l i z a t i o n0 fs y s t e m t h i sp a p e rf o c u s e so nt h ef o l l o w i n ga s p e c t s ： 1 i n t r o d u c e st h ee o n c e p to ft h ep 2 pt e c h n o l o g ya n ds u m m a r i z e sc o r r e n ts i t u a t i o n f r o mt h ep o i n to fi n f o r m a t i o nt e c h n o l o g yd e v e l o p m e n t 2 a n a l y z e st h em a i np 2 pt o p o l o g yf r a m e w o r k s p o i n t so u tt h e i ra d v a n t a g e sa n d d i s a d v a n t a g e s ，a n di n t r o d u c e st h er e p r e s e n t a t i v ep r o d u c to fe v e r yf r a m e w o r k 3 r e s e a r c h e sk a d e m l i ap r o t o e o lf o rp 2 pv i d e od o w n l o a dm o d e l 4 p r o p o s e san e w p 2 pv i d e od o w n l o a dm o d e lw i t hk a d e m l i a , a n da n a l y z e st h e c h a r a c t e r i s t i c so ft h i sm o d e la n dt h ed e s i g no fs y s t e m 5 n er e s e a r c ho fr e a l i z a t i o nt e c h n o l o g yo fi 2 pv i d e od o w n l o a dm o d e l c o m b i n e dp r a c t i c a la p p l i c a t i o nd e m a n d s ，t h i sm o d e lw a sd e s i g n e da n dd e v e l o p e df r o m s y s t e ml e v e l k e y w o r d ap 2 p , k a d e m l i a , i n f o r m a t i o nr e t r i e v a l 浙江大学硕士学位论文圈目录 图目录 图1 - 1c ，s 架构下的服务器拥塞。 图1 - 2 代理服务器示意图4 图1 - 3 c d n 网络 图1 4 c d n 网络 图2 - 1 中心化拓扑结构图。 图2 - 2n a p s t e r 结构图 图2 - 3 全分布式非结构化拓扑 图2 - 4c m u t c l l a 的拓扑结构和文件检索方法 1 1 1 2 1 3 1 4 图2 - 5 半分布式拓扑1 5 图2 - 6 全分布式结构化拓扑图 图2 - 7c h o r d 查询过程 图3 - 1 节点0 0 1 1 的子树划分 图3 2 通过i d 值定位目标节点 图3 3k 桶结构 1 8 2 1 图3 - 4a = 1 时的查询过程 图3 - 5 缓存原则 图3 - 6 节点0 0 0 的路由表生成演化 图3 - 7 节点0 1 0 0 的k 桶分裂过程。2 9 图4 1 系统拓扑结构图3 1 图4 - 2 包封装格式 图4 - 3 引导服务器和发布服务器功能模块图。3 3 图“k a d 网络模块 图4 5 k a d 持久化 图4 6 k a d 数据结构 图4 _ 7 推送服务器模块3 5 图4 8 客户端结构图 图5 1 类图 图5 2 节点分裂( o 代表叶子节点，团代表非叶子节点) 3 9 图5 3 路由表的维护 图5 - 4 节点查找 图5 - 5 节点查找函数调用 4 0 4 2 4 3 图5 - 6c s e a r c h ：p r o c e s s r e s p o n s e 流程。4 5 图5 7 资源发布。4 5 图5 8 关键字查找和文件查找 图5 9 实际效果图。 浙江大学硕士学位论文第1 章绪论 第1 章绪论 1 1 引言 对等计算( p e e r - t o - p e e r ，简称p 2 p ) 打破了传统c s 模式服务器对网络资源的 集中化管理和提供，解放了服务器响应的压力和降低了带宽负载，最近几年，p 2 p 迅速成为计算机界关注的热门话题之一。作为一种分布式网络，p 2 p 网络的参与 者共享他们所拥有的部分硬件资源( 处理能力、存储能力、网络连接能力、打 印机等) ，这些共享资源需要由网络提供服务和内容，能被其它对等节点( p c c r ) 直 接访问而无需经过中间实体。在此网络中的参与者既是资源( 服务和内容) 提供 者( s e r v e r ) ，又是资源( 服务和内容) 获取者( c l i e n t ) 。p 2 p 打破了传统的 c l i e n t s e r v e r ( c s ) 模式，在网络中的每个结点的地位都是对等的。每个结点既充 当服务器，为其他结点提供服务，同时也享用其他结点提供的服务。 p 2 p 技术的特点体现在以下几个方面。 1 非中心化：网络中的资源和服务分散在所有结点上，信息的传输和服务 的实现都直接在结点之间进行，可以无需中间环节和服务器的介入，避免了可能 的瓶颈。p 2 p 的非中心化基本特点，带来了其在可扩展性、健壮性等方面的优势。 2 可扩展性：在p 2 p 网络中，随着用户的加入，不仅服务的需求增加了， 系统整体的资源和服务能力也在同步地扩充，始终能较容易地满足用户的需要。 整个体系是全分布的，不存在瓶颈。理论上其可扩展性几乎可以认为是无限的。 3 健壮性：p 2 p 架构天生具有耐攻击、高容错的优点。由于服务是分散在各 个结点之间进行的，部分结点或网络遭到破坏对其它部分的影响很小。p 2 p 网络 一般在部分结点失效时能够自动调整整体拓扑，保持其它结点的连通性。p 2 p 网 络通常都是以自组织的方式建立起来的，并允许结点自由地加入和离开。p 2 p 网 络还能够根据网络带宽、结点数、负载等变化不断地做自适应式的调整。 4 高性价比：性能优势是p 2 p 被广泛关注的一个重要原因。随着硬件技术 的发展，个人计算机的计算和存储能力以及网络带宽等性能依照摩尔定理高速增 长。采用p 2 p 架构可以有效地利用互联网中散布的大量普通结点，将计算任务或 存储资料分布到所有结点上。利用其中闲置的计算能力或存储空间，达到高性能 计算和海量存储的目的。通过利用网络中的大量空闲资源，可以用更低的成本提 供更高的计算和存储能力。 5 隐私保护：在p 2 p 网络中，由于信息的传输分散在各节点之间进行而无 浙江大学硕士学位论文第1 章绪论 需经过某个集中环节，用户的隐私信息被窃听和泄漏的可能性大大缩小。此外， 目前解决i n t e m e t 隐私问题主要采用中继转发的技术方法，从而将通信的参与者 隐藏在众多的网络实体之中。在传统的一些匿名通信系统中，实现这一机制依赖 于某些中继服务器节点。而在p 2 p 中，所有参与者都可以提供中继转发的功能， 因而大大提高了匿名通讯的灵活性和可靠性，能够为用户提供更好的隐私保护。 6 负载均衡：p 2 p 网络环境下由于每个节点既是服务器又是客户机，减少 了对传统c s 结构服务器计算能力、存储能力的要求，同时因为资源分布在多个 节点，更好的实现了整个网络的负载均衡。 与传统的分布式系统相比，p 2 p 技术具有无可比拟的优势。同时，p 2 p 技术 具有广阔的应用前景。i n t e m t 上各种p 2 p 应用软件层出不穷，用户数量急剧增加， 大量p 2 p 软件的用户使用数量分布从几十万、几百万到上千万并且急剧增加，并 给i n t e m e t 带宽带来巨大冲击。p 2 p 计算技术正不断应用到军事领域，商业领域， 政府信息，通讯等领域。 1 2 研究背景 1 2 1 传统的c 1 i e n t s e r v e r 架构 图1 - 1c s 架构下的服务器拥塞 c s ( c l i e n t s e r v e r ) 架构，即客户机和服务器结构。它是软件系统体系结构， 通过它可以充分利用两端硬件环境的优势，将任务合理分配到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 ) 架构的优点是应用服务器运行数据负荷较轻和数据的储 存管理功能较为透明。其缺点是高昂的维护成本且投资大。并且传统的c s 体系 2 浙江大学硕士学位论文第1 章绪论 结构虽然采用的是开放模式，但这只是系统开发一级的开放性，在特定的应用中 不论是c l i e n t 端，还是s e r v e r 端都还需要特定的软件支持。由于没能提供用户真 正期望的开放环境，c s 结构的软件需要针对不同的操作系统系统开发不同版本 的软件，加之产品的更新换代十分快，已经很难适应百台电脑以上局域网用户同 时使用。而且代价高，效率低。 服务器必须通过网络给每个用户发送多份相同的数据，因为多媒体的数据量 大，随着客户端数目的增加，很容易造成s e r v e r ：端的网络拥塞。同时也增加了对 服务器性能和服务器出口带宽的需求，为了降低服务器的负载，代理服务器，p 2 p 技术开始得到研究和发展。 1 2 2b s ( b r o w s e r s e r v e r ) 架构 即浏览器朋艮务器结构。它是随着i n t e r n e t 技术的兴起，对c s 结构的一种变 化或者改进的结构。在这种结构下，用户工作界面是通过w w w 浏览器来实现， 极少部分事务逻辑在前端( b r o w s e r ) 实现，但是主要事务逻辑在服务器端( s e r v e r ) 实现，形成所谓三层结构。这样就大大简化了客户端电脑载荷，减轻了系统维护 与升级的成本和工作量，降低了用户的总体成本( t c o ) 。 b ，s 架构的优点是维护和升级方式简单，以及成本降低，选择更多，不局限 于w i n d o w s 平台。其劣势是应用服务器运行数据负荷较重。应用服务器运行数据 负荷较重，一旦发生服务器“崩溃”等问题，后果不堪设想。因此，需要大量的 备份数据库存储服务器，以防万一。 3 浙江大学硕士学位论文 第1 章绪论 1 2 3 代理服务器 图1 - 2 代理服务器示意图 代理服务器( p r o x y ) 【1 l 是一种特殊类型的i n t e m e t 服务器。在传统的w e b 应用 中，代理服务器用于扩展用户对i n t e r n e t 的数据访问能力。为提高代理服务器的 系统效率，缓存( c a c h e ) 技术被引入到代理服务器中，代理服务器将一些频繁访问 的数据存贮在内存或硬盘中，当用户通过代理服务器用户访问时，如果数据在代 理服务器的缓存中，代理服务器就无需访问远程的服务器，而只需通过本地缓存 为用户服务。流媒体代理服务器的重要作用表现在： 代理服务器承担了一部分用户访问，有效的降低了主服务器的访问负载，可 以提高用户访问的响应速度，降低启动延迟。 代理服务器离用户较近，网络状况较好，可以提供更好的流媒体服务，可以 提高服务器的鲁棒性及节省网络资源。 然而代理服务器的主要问题在于如何保证主服务器的内容于代理缓存中的 内容的一致性。即当服务器的内容更新后，如果保证代理服务器中缓存的数据即 时更新，对这些问题的研究就产生了更智能的c d n 技术。 4 浙江大学硕士学位论文第1 章绪论 1 2 4c d n 概述 图1 - 3 c d n 网络 c d n 【1 】的英文全称是c o n t e n td e l i v e r yn e t w o r k ，即互联网内容发布网络，它 是一个建立并覆盖在互联n ( i n t c r n c t ) 之上、由分布在不同区域的节点服务器群组 成的虚拟网络，如图1 3 所示。c d n 可以实现把服务器的内容高效、稳定地发布 到离客户端最近的地方。其基本思路就是尽可能避开互联网上有可能影响数据传 输速度和稳定性的瓶颈和环节，使内容传输的更快、更稳。通过在网络各处放置 节点服务器所构成的在现有的互联网基础之上的一层智能虚拟网络，c d n 系统能 够实时地根据网络流量和各节点的连接、负载状况以及到用户的距离和响应时间 等综合信息将用户的请求重新导向离用户最近的服务节点上。对用户来说，通过 c d n 系统，得到响应的时间被大大缩短，连接质量也大大提高，从而大大提高了 上网访问的总体性能。然而，c d n 高昂的部署成本始终是一个问题。 5 浙江大学硕士学位论文第1 章绪论 1 2 5p 2 p 网络概述 每傩务誓i i 掏簪印o 务，i 鞭 图1 - 4 c d n 网络 p 2 p 技术主要指由硬件形成网络连接后的信息控制技术，主要代表形式是在 应用层上基于p 2 p 网络协议的客户端软件。m m 为p 2 p 下了如下定义： p 2 p 系统由若干互联协作的计算机构成，且至少具有如下特征之一： 系统依存于边缘化( 非中央式服务器) 设备的主动协作，每个成员直接从其他 成员而不是从服务器的参与中受益。 系统中成员同时扮演服务器与客户端的角色。 系统应用的用户能够意识到彼此的存在，构成一个虚拟或实际的群体 事实上p 2 p 网络是互联网整体架构的基础，互联网最基本的t c p i p 协议并 没有客户端和服务器的概念，在通讯过程中，所有的设备都是平等的一端。 目前流行的p 2 p 软件的架构手段主要有三种；中心目录服务器、无中心结构 化模型和无中心非结构化模型。详细的内容将在第二章进行介绍。 1 3 文章的研究内容及组织 本文介绍的是一种基于全分布式结构化拓扑网状结构的视频下载模型，分析 了模型的工作原理以及优点，并结合应用实际，完成了p 2 p 视频下载系统的实用 性设计。 论文内容安排如下： 第一章：主要介绍了p 2 p 的概念和研究背景，介绍了内容发布技术的比较， 并总体概括文章的组织结构。 第二章：分析对比现存主要的p 2 p 网络拓扑结构，指出各种结构的优缺点， 6 一多鼍缝 审，断避 浙江大学硕士学位论文第1 章绪论 并介绍各种网络结构的代表性产品的实现原理。 第三章：主要研究了k a d 网络的技术框架。为视频下载模型的提出进行理 论上的铺垫。 第四章：提出一种基于k a d 网络的视频下载模型，同时详细的分析这种模 型的优点和客户端、服务器的设计。 第五章：介绍了视频下载模型的实现以及其核心模块的工作原理和实现方 法。这是对理论的实践过程。 第六章：总结全文，并且提出了目前视频下载模型的不足和未来需要优化增 加的工作。 1 4 本章小结 p 2 p 技术打破了传统c s 模式服务器对网络资源的集中化管理和提供，解放 了服务器响应的压力和降低了带宽负载，p 2 p 逐渐成为计算机界关注的热门话题 之一。p 2 p 技术具有非中心化、可扩展性、健壮性、高性价比、隐私保护、负载 均衡等特点，具有广阔的应用前景。本章为绪论，主要介绍了p 2 p 的概念、特点 和研究背景，介绍了内容发布技术的比较，并总体概括文章的研究内容和组织结 构。 7 浙江大学硕士学位论文第2 章p 2 p 应用的技术框架 第2 章p 2 p 应用的技术框架 2 1p 2 p 信息检索技术 f 2 p 系统本质上也是一个分布式系统，同时它也具备着一些区别于传统分布 式系统的特色：更强调自组织、对等、动态的特性。因此在研究p 2 p 信息检索技 术的同时，可以借鉴传统分布式信息检索( d i s t r i b u t e di n f o r m a t i o nr e t r i e v a l ，d 取) 的研究，并结合p 2 p 自身的特点进行设计。这部分将在回顾已有的分布式信息检 索的研究的基础上，进一步总结分析目前已有的p 2 p 搜索方面主要的研究。 2 1 1 分布式信息检索 分布式信息检索是信息检索领域的一个分支。传统意义上的d i r 一般研究 如下的几个问题： 1 如何取得一个文本数据库的内容描述符( s 沁d e s c r i p t i o n ) 。描述符一般是文 本数据库中的词列表及它们的词频信息。 2 如何根据数据库内容描述符和查询的比较，对数据库进行排名( r e u r c e r a n k i n g ) ，决定最可能包含所需信息的数据库。对每一个查询都要执行这个操作。 3 如何选择进行检索的目标数据库( r e s o u r c es e l e c t i o n ) 。 4 如何对目标数据库进行检索( s e a r c h i n g ) 。 5 如何把来自不同数据库的文档列表合并。 在这种框架下的检索方法有：c o r i 2 1 、c v v 、l a n g u a g em o d e l i n g 、q u e r y c l u s t e r i n g 、q u e r yp r o b i n g 、q u e r y - b a s e ds a m p l i n g 3 等，其中c o r i 与q u e r y - b 鹊e d s a m p l i n g 是两种效果较好的方法。这些方法的主要优点是所需要的信息量较少， 只要有各个数据库中的词频统计信息，就可以进行检索，在一定程度上满足用户 的信息需求。如果满足以下条件，检索效果可以相当不错： 1 每个文本数据库都可以提供精确的描述符； 2 每个文本数据库的检索结果都是可比较的； 3 用户不要求很高的查全率。 并行检索 4 1 ( p a r a l l e li n f o r m a t i o nr e t r i e v a l f i r ) 是另一种形式的非集中式信 息检索方法。这种方法主要是出于性能考虑而不是应用的需求。例如，我们可以 按照关键词把倒排索引分块，分配到多处理机的不同结点上，然后在检索时同时 进行处理，这样可以大大加快总的检索速度。 8 浙江大学硕士学位论文第2 章p 2 p 应用的技术框架 2 1 2 非结构化p 2 p 网络中的搜索技术 在非结构化的p 2 p 网络中，节点采用随机的方法或采用启发策略加入网络， 网络拓扑随着节点的变迁和网络通信的进行而发生演变。在非结构化p 2 p 网络内 进行搜索的技术分为两类： 2 1 2 1 不利用任何文档分布信息的盲搜索( b l i n ds e a r c h ) 这类研究都可以抽象为如何从一个随机图中的任一个点出发定位目标点，使 得整个过程遍历的点的个数最少。其中最具有典型代表意义的是g n u t e l l a 的宽度 优先遍历搜索( b f s ) t 5 】；参考文献【6 】中给出了对b f s 改进的搜索方法，每次只搜 索一定比例的邻居；参考文献【7 l 对b f s 的改进是动态地调整搜索的宽度，随搜索 深度而增加扩大搜索宽度；参考文献【8 l 采用了一种随机发起1 1 个同样的查询的方 法，每个收到查询的节点从自己的邻居中随机挑选一个作为下一跳，这样就保障 了整个搜索过程中始终有n 个并行的搜索痕迹；参考文献【9 l 中引入超级节点的混 合结构来降低整个网络的通信量。 2 1 2 2 利用网络中文档分布信息的搜索( i n f o r m e ds e a r c h ) 对b f s 的改进的共同特点是各个节点记录以前接受过的请求和应答，并根据 这种对应的关系作为对后来的路由过程的启发，或者通过记录邻居的文档信息来 尽量将查询路由到相关的节点，而减少不必要的通信量。以及给出一种定期交换 路由表的方法使得每个节点都获知网络内部的一个子集的文档分布状况，从而达 到迅速定位目标资源的目的。 上述方法都是对原有的在非结构化网络上检索的改进，对g n u t e l l a 等基于文件 名检索的p 2 p 文件共享网络比较适用，但无法胜任全文信息检索，为了保证较高 的文本的召回率( r e c a l l r a t e ) ，需要覆盖较多的节点，牺牲较大的通信代价和主 机计算代价，对于稀疏资源的定位更是如此。 2 1 3 基于兴趣局部性优化的p 2 p 搜索 这类方法基于这样的原则：每个节点都表现出某些可以捕捉到的兴趣，相近 兴趣的节点保存的内容和提交的查询也相近。通过挖掘每个节点的兴趣，把节点 按照兴趣关系组成网络，使得兴趣相近的节点在网络中比较近。 目前主要的研究是按照用户提交的检索的行为来划分用户的兴趣的。文献 1 0 】 中揭露了这种按兴趣组成的网络表现出和社会网络相近的所谓小世界特性。这些 特性用于提高检索效率证明是有效的。但这类研究没有充分地挖掘节点共享的内 9 浙江大学硕士学位论文第2 章p 2 p 应用的技术框架 容所体现的节点的兴趣，用户提交的查询只是反映用户共享兴趣的一个部分，尤 其对于提供大量信息的节点，所产生的查询只是反映其存储内容的一个很小的子 集，因此需要去挖掘其共享内容所反映的兴趣，从而使得网络中其他节点在需要 时能够高效地检索这些内容。在p 2 p 全文信息检索中这个问题更加突出，因为用 户提出的查询词的尺度远远小于共享的信息的尺度，查询所反映的共享兴趣就更 有限了。 文献【1 l 】提出通过节点共享的内容来挖掘节点的兴趣。它使用类似于分布式 检索的方法，由代理节点定期采集各个共享节点共享的内容索引，然后通过聚类 的方法把这些索引分成若干话题区域( t o p i cs e g m e n t a t i o n ) ，每个节点属于一个 或两个区域。对每次查询，也通过计算查询和各个话题区域中心的距离来判断该 查询所属的区域，路由查询时先路由到该查询所属的目标区域，然后再在目标区 域中进行广播。这种方法的不足之处在于代理节点负担沉重，而且共享的内容很 难确定地划分为独立的区域，往往每个节点属于多个t o p i c s 。 此外文献【1 2 】、【1 3 是按照预先指定的分类标准对用户进行分类，并使用这些 分类来启发路由，把查询传递到相同类别的节点中去，从而减少传输代价。但这 种分类的标准需要预先定义，不够灵活，同时也无法动态地反映p 2 p 共享网络中 的内容更替。 2 1 4 结构化p 2 p 网络中的搜索技术 在这类网络中，每个节点都有固定的编址，整个网络具有相对稳定而规则的 拓扑结构。依赖拓扑结构，可以给网络的每个节点指定一个逻辑的地址，并把地 一 、 址和节点的位置对应起来。给定某个地址，拓扑结构保证只需要通过o i l o g 川j 跳 就能路由到具有相应地址的节点上去( n 是网络中的节点数) 。结构化网络可以 用来有效地存储分布的信息，网络中存储的信息可以用 这个二元组来唯 一定位，其中k e y 是信息的索引，u d 是存储该信息的节点。 分布地存储 在结构化网络中，每个节点存储那些k e y 和自己的地址相近的二元组。这样，要 查找某个索引为k e y 的信息，只需要路由到地址和k e y 相近的节点就可以获得 的二元组，从而定位目标信息，就像我们平常在哈希表中查找数据一样， 所以称为分布式的哈希表( d i s t r i b u t e dh a s ht a b l e ，d h t ) 。 给定存储信息的索引k e y ，d h t 能高效率定位到对应该索引的信息。但要作 全文信息检索，必须要像搜索引擎一样能按内容中包含的字段来进行检索。因此， 这些内容字段必须能够转化成为相应的索引k e y 。这就要求k e y 必须体现内容信 浙江大学硕士学位论文第2 章p 2 p 应用的技术框架 息，同时d h t 类的方法面临本身固有的问题一负载均衡不易、网络拓扑维护代 价大、k e y 的同步维护困难等( 参见文献【1 7 】) 。这些问题在设计d h t 文件共享系 统的时候都是需要重视的。 2 2p 2 p 网络模型研究 拓扑结构是指分布式系统中各个计算单元之间物理或逻辑的互联关系，结点 之间的拓扑结构一直是确定系统类型的重要依据。目前互联网络中广泛使用集中 式、层次式等拓扑结构。 i n t e r n e t 本身是世界上最大的非集中式互联网络，但是上世纪9 0 年代所建立 的一些网络应用系统却是完全的集中式系统，许多w e b 应用都是运行在集中式的 服务器系统上。集中式拓扑结构系统目前面临着过量存储负载、d o s ( d e n i a lo f s e r v i c e ，拒绝服务) 攻击、网络带宽限制等一些难以解决的问题。p 2 p 系统主要 采用非集中式的拓扑结构，很大程度上解决了以上问题。根据结构关系可以将p 2 p 系统细分为四种拓扑结构： 2 2 1 中心化拓扑( c e n t r a l i z e dt o p o - l o g y ) 图2 - 1 中心化拓扑结构图 在这种模型中，所有的节点都和中心目录服务器建立连接，中心目录服务器 负责索引所有节点中的内容。当节点发出请求时，中心目录服务器会根据节点的 请求找出符合该节点要求的节点，然后文件交换就直接在这两个节点之间进行。 因为这种模型仍然需要一个中心目录服务器，所以当节点的数量增多时，服务器 端的存贮和带宽仍然会有一些限制。n a p s t e r 3 的实现是这种模型代表。 中心化拓扑优点： 1 1 浙江大学硕士学位论文第2 章p 2 p 应用的技术框架 1 网络结构简单、易于简单，资源发现效率高。 2 由于资源的发现依赖中心化的目录系统，发现算法灵活高效并能够实现复 杂查询。 3 管理维护整个网络消耗的网络带宽比较小。 其主要缺点： 1 查询计算全部由中心服务器完成，对服务器的性能和带宽要求过高。 2 服务器的索引不能及时更新，查询结果不能保证精确。 3 与传统客户机，服务器结构类似，容易造成单点故障。 4 易引起访问的“热点”现象和版权纠纷。 5 穿透防火墙能力比较弱。 中心化拓扑模型n a p s t e r 是最早出现的p 2 p 系统之一，采用的就是中心化拓 扑结构。通过一个中央索引服务器保存所有n a p s t e g 用户上传的音乐文件索引和 存放位置的信息。当某个用户需要某个音乐文件时，首先连接到n a p s t e r 中央索 引服务器，在服务器上进行检索，服务器返回存有该文件的用户信息，再由请求 者直接连到文件的所有者传输文件。n a p s t e r 首先实现了文件查询与文件传输的分 离，有效地节省了中央服务器的带宽消耗，减少了系统的文件传输延时。 图2 - 2n a p s t e r 结构图 然而，这种对等网络模型存在以下这些问题： 1 中央索引服务器的瘫痪容易导致整个网络崩溃，可靠性和安全性较低。 2 随着网络规模的扩大，中央索引服务器维护和更新的费用将急剧增大。 3 中央索引服务器的存在常引起版权问题上的纠纷。 综合上述优缺点，对小型网络而言，中心化拓扑模型在管理和控制方面占一 1 2 浙江大学硕士学位论文第2 章p 2 p 应用的技术框架 定优势。但鉴于其存在的上述缺陷，该模型并不适合大型网络应用。 2 2 2 全分布式非结构化拓扑( d e c e n t r a - l i z e du n s t r u c t u r e d t o p o l o g y ) 图2 - 3 全分布式非结构化拓扑 在这种模型中，每个节点的请求都会广播( f l o o d e db r o a d c a s t ) 给所有和它 直接相连的节点，如果这些节点中都没有所请求的文件，这些节点会把这个请求 继续广播给所有和他们直接相连的节点，直到找到所请求的文件或者广播的次数 超过了某个值( 一般是5 - 9 ) 。模型中的广播的方法会消耗很大的带宽并，因此不 具有扩展性，然后这种模型在局域网内却非常有效。通过设置请求中的参数1 1 凡 并缓存搜索过的路径可以改善性能。g n u t e l l a 7 的实现是这种模型的代表。 由于非结构化网络将重叠网络认为是一个完全随机图，结点之间的链路没有 遵循某些已定义的拓扑来构建。这些系统一般不提供性能保证，但容错性好，支 持复杂的查询，并受结点频繁加入和退出系统的影响小。 全分布式非结构化拓扑的优点： 1 全分布式非结构化拓扑的p 2 p 网络是在重叠网络( o v e r l a yn e t w o r k ) 中采 用了随机图的组织方式，结点度数服从p o w e r - l a w 规律( 幂次法则) ，从而能够较 快发现目的结点。 2 面对网络的动态变化体现了较好的容错能力，因此具有较好的可用性。 3 可以支持复杂查询，如带有规则表达式的多关键词查询和模糊查询等。 缺点为： 1 查询的结果可能不完全。 浙江大学硕士学位论文 第2 章i 2 1 应用的技术框架 2 查询速度较慢。 3 采用查询的系统对网络带宽的消耗非常大 4 可扩展性差。 全分布式非结构化拓扑模型g n u t e l l a 和n a p s t e r 最大的区别在于g n u t e l l a 是 更加纯粹的p 2 p 系统，因为它没有中央索引服务器，每台机器在g n u t e l l a 网络中 是真正的对等关系，既是客户机同时又是服务器，所以被称为对等机( s e r v e n t ， s e r v e r + c l i e n t 的组合) 。 在文件检索方面，它与n a p s t e r 也不相同。在g n u t e l l a 网络的发展初期，它 主要采用基于完全随机图的f l o o d i n g 搜索算法。下图显示了f l o o d i n g 的工作流程： 当一台计算机要下载一个文件，它首先以文件名或者关键字生成一个查询，并把 这个查询发送给与它相连的所有计算机，这些计算机如果存在这个文件，则与查 询的机器建立连接，如果不存在这个文件，则继续在自己相邻的计算机之闻转发 这个查询，直到找到文件为止。为了控制搜索消息不至于永远这样传递下去，一 般通过t r l ( t r i n e t ol i v e ) 簸j 减值来控制查询的深度。 图2 - 4g n u t e l l a 的拓扑结构和文件检索方法 但是，随着联网节点的不断增多，网络规模不断扩大，通过这种f l o o d i n g 方 式定位对等点的方法存在如下缺点：将造成网络流量急剧增加，从而导致网络中 部分低带宽节点因网络资源过载而失效。所以在初期的g n u t e l l a 网络中，存在比 较严重的分区和断链现象。也就是说，一个查询访问只能在网络的很小一部分进 行，因此网络的可扩展性不好。 1 4 浙江大学硕士学位论文第2 章p 2 p 应用的技术框架 2 2 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 ) r q 口嘲糟e p e e r 龇s o u r c ep e e r 图2 - 5 半分布式拓扑 半分布式拓扑结构( 有的文献亦称作混杂模式，英文表达为h y b r i ds t r u c t u r e ) 吸取了中心化结构和全分布式非结构化拓扑的优点，选择性能较高( 处理、存储、 带宽等方面性能) 的结点作为超级结点( 英文表达为s u p e r n o d e s 或者h u b s ) ，在 各个超级结点上存储了系统中其他部分结点的信息，发现算法仅在超级结点之间 转发，超级结点再将查询请求转发给适当的叶子结点。半分布式结构也是一种层 次式结构，超级结点之问构成一个高速转发层，超级结点和所负责的普通结点构 成若干层次。 由于半分布式拓扑对结构化对等网络模型进行了进一步的扩展，在其中引入 分层的概念并融入多种的网络模型。新型网络模型中的关键值查询算法通过结合 杂凑函数散列表查询算法和文字模糊匹配算法在提高查询效率的基础上为用户 提供了更好的服务。 半分布式拓扑优点： 1 新型的网络体系结构融合了现存主流p 2 p 网络，增强了全分布式拓扑的可 扩展性。 2 改进了全分布结构化拓扑所存在的绕路( d e t o u r i n g ) 问题和i n t c r n e t 主干 网超荷负载的问题 3 网络体系结构中加入相应的管理机制，增强了网络的可管理性，解决了 p 2 p 网络一直存在的管理混乱和商业价值不高的缺点。 4 在网络体系结构中加入的新型关键值匹配方案保证了网络的透明性，为用 浙江大学硕士学位论文 第2 章p 2 p 应用的技术框架 户提供了更好的服务。 缺点为： 对超级节点依赖较大，易受到攻击，容错性也受到影响。 2 2 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 - 6 全分布式结构化拓扑图 全分布式结构化拓扑的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 ) 技术来组织网络中的结点。在这种模型中，网络中的每个节 点都会被赋予一个随机产生的d ，并且每个节点知道网络中的部分其他的节点， 当一份文件在网络中发布( 共享) 时，会根据该文件的内容和名字，用某种h a s h 算 法生成一个文件d ，然后文件发布的节点会把该文件路由( r o u t e ) 给它所知道 的节点中节点d 最接近该文件m 的节点，直到当前节点就是最接近文件d 的 节点。所有参与r o u t e 的节点都会保存一份该文件的拷贝。同样，当某个节点发 出需要某个文件的请求时，请求会转发给节点i d 最接近所请求的文件l d 的节点， 直到找到真正具有该文件的节点，然后该文件会传给最原始的请求者，所有参与 这次r o u t e 的节点同样会保存一份该文件的拷贝。 相比于上一种中心目录模型，这种模型实际上是把索引的功能分散到了各个 节点，没有了服务器的概念，是一种更纯的p 2 p 系统。 f r e e n e t 4 ，c h o r d 5 ， p a s t r y 6 的实现是这种模型的代表。 浙江大学硕士学位论文第2 章p 2 p 应用的技术框架 全分布式结构化拓扑优点： 1 用户基本上都可以在一次跳转之内得到查找结果，所以非常方便。 2 每个用户要储存的数据= 平均文件数平均每文件关键字数，与系统规 模无关，所以采取这种方案的系统可以支撑起非常多的用户。 d h t ( 分布式哈希表) 使用分布式哈希算法来解决结构化的分布式存储问题。 分布式哈希算法的核心思想是通过将存储对象的特征( 关键字) 经过哈希运算，得 到键值( h a s hk e y ) ，对象的分布存储依据键值来进行。具体来讲，大致有以下步 骤：对存储对象的关键字进行哈希运算，得到键值。这样就将所有的对象映射 到了一个具体的数值范围中。重叠网中的每个节点负责数值范围中的特定段落。 例如，节点a 负责存储键值从8 0 0 0 到8 9 9 9 的对象；而节点b 负责7 0 0 0 - 7 9 9 9 的对象。这样就将对象集合分布地存储在所有的节点中。节点可以直接存储对象 本身，如文件中的一个片段；也可以存储对象的索引，如该对象所在节点的m 地址。 由于实际的p 2 p 网络动态变化较大，一致性哈希是实用的d h t 协议，c h o r d 、 p a s t r y 等都是在一致性哈希的基础上对路由算法进行了改进。 在一致性哈希算法( c o n s i s t e n th a s h ) 的路由算法中，每个节点( 对应p 2 p 系 统中的p e e r ) 都有随机分配的i d 。在将内容映射到节点时，使用内容的关键字和 节点的d 进行一致性哈希运算并获得键值。一致性哈希要求键值和节点m 处于 同一值域。最简单的键值和d 可以是一维的，比如从0 0 0 0 到9 9 9 9 的整数集合。 根据键值存储内容时，内容将被存储到具有与其键值最接近的i d 的节点上。例 如键值为1 0 0 1 的内容，系统中有i d 为1 0 0 0 ，1 0 1 0 ，1 1 0 0 的节点，该内容将被 映射到1 0 0 0 节点。 为了构建查询所需的路由，一致性哈希要求每个节点存储其上行节点( m 值 大于自身的节点中最小的) 和下行节点( 值小于自身的节点中最大的) 的位置 信息( 口地址) 。当节点需要查找内容时，就可以根据内容的键值决定向上行或 下行节点发起查询请求。收到查询请求的节点如果发现自己拥有被请求的目标， 可以直接向发起查询请求的节点返回确认；如果发现不属于自身的范围，可以转 发请求到自己的上行下行节点。 为了维护上述路由信