（计算机应用技术专业论文）非结构化纯p2p系统中副本问题的研究.pdf

两华大学硕+ 学位论文非结构化纯p 2 p 系统中副本问题的研究计算机应用技术研究生林j 下国指导教师刘克剑随着互联网技术的不断发展和个人p c 机性能的不断提高，p 2 p 技术在人们生活中扮演着越来越重要的角色，越来越受到人们的重视。各种基于p 2 p技术的应用不断涌现，人们不再满足只利用对等网络完成资源的搜索和下载，支持动态业务的p 2 p 系统成为新的研究目标和方向。副本管理作为p 2 p 系统的一个重要组成部分，副本可以为系统带来可靠性和性能上的提升。但是，随着越来越多业务的发展需要，文件更新频繁以及p 2 p 用户自由出入导致网络的高度动态性，使得如何有效地维护副本一致性变得越来越重要。本文首先全面的了解了p 2 p 系统的特点并且分析了几个经典的模型，然后对副本的生成做了详细的描述，最后对副本一致性维护算法进行了深入的研究。在副本创建策略上，提出了当查询热度或者节点性能大于系统临界值的时候节点就下载文件，否则节点仅存储文件位置信息。利用这种方法来减少副本的创建，减轻系统的负担。但与此同时不降低系统的查询成功率。在维护副本一致性方面本文提出了以中心节点的方法来维护系统副本的一致性。中心节点维护各个副本节点的位置信息，副本节点维护中心节点的位置信息，当副本发生改变的时候先汇报到中心节点处，中心节点再向各个副本节点发送更新信息。此算法旨在更新文件时，减少传递的消息数量，避免了盲目的洪泛广播。最后本文在实验环境下模拟了算法，证明了算法的有效性。关键词：p 2 p ，f r e e n e t ，副本，一致性r e s e a r c ho nr e p l i c a t i o nm a n a g e m e n tr e l a t e dp r o b l e m sb a s e do nu n s t r u c t u r e dp u r ep 2 ps y s t e mc o m p u t e ra p p l i c a t i o nt e c h n o l o g ym d c a n d i d a t e ：l i nz h e n g g u os u p e r v i s o r ：l i uk e j i a na st h ei n t e r a c t sd e v e l o p m e n ta n dt h ec a p a b i l i t yo fp ce n h a n c e m e n t , t h et e c h n o l o g yo fp 2 pn e t w o r kb e c o m em o r ea n dm o r ei m p o r t a n ti np e o p l el i f e v a r i o u sa p p l i c a t i o n sb a s e do np 2 pt e c h n o l o g ya r es p r i n g i n go u t p e o p l ed on o ts a t i s f yw i t ht h ep 2 ps y s t e mw h i c hc a no n l yp r o v i d es o m eb a s i cc a p a b i l i t ys u c ha ss e a r c h i n ga n dd o w n l o a d i n gr e s o u r c e s as y s t e mc a ns u p p o r td y n a m i cb u s i n e s sh a v eb e c o m i n gn e wg o a l sa n df i e l d so fr e s e a r c h r e p l i c a t i o nm a n a g e m e n ti sa l li m p o r t a n tp a r tt ot h ep 2 ps y s t e m d a t ar e p l i c a t i o ni saw e l l k n o w na n dw i d e l ya c c e p t e dt e c h n i q u et or e d u c ed a t ar e s p o n s et i m ea n dn e t w o r kb a n d w i d t hc o n s u m i n g h o w e v e r ，b e c a u s et h en o d em a yj o i na n dl e a v ef r e e l ya n df r e q u e n t l y ，t h ep 2 pn e t w o r kp r e s e n t sak i n do fs i g n i f i c a n td y n a m i cc h a r a c t e r i s t i c ，m a i n t a i n i n gc o n s i s t e n c yo fr e p l i c a t i o n si sm o r ec h a l l e n g i n gi nt h e s ee n v i r o n m e n t s i nt h i st h e s i s ，f i r s t l y ，w ea n a l y z et h e c h a r a c t e r i s t i c so fp 2 ps y s t e m sa n di n t r o d u c cs e v e r a lc l a s s i cm o d e la n dr e p l i c a t i o n sc r e a t i o ns t r a t e g i e s ，f u r t h e r m o r e ,p r e s e n tan e wc o n s i s t e n c ym a i n t a i n i n ga l g o r i t h m w ec h o o s et h en o d e st od o w n l o a df i l e sw h o s eh e a tl e v e lo fs e a r c h i n go rp e r f o r m a n c ei sg r e a t e rt h a nat h r e s h o l d o t h e r w i s e ，i no r d e rt or e d u c et h ec r e a t i o no fr e p l i c a t i o na n dt h eb u r d e no fs v s t e m ，t h en o d e so n l ys t o r et h el o c a t i o ni n f o r m a t i o no fn o d e sw h i c hh a v et h o s ef i l e s w h a td e s e r v e st ob em e n t i o n e d ，i td o e sn o td e c r e a s et h ep r o b a b i l i t yo fs u c c e s so fs e a r c h i n g i ns u c c e s s i o n ，ah o s tn o d ei sa d a p t e dt om a i n t a i n两华大学硕+ 学位论文r e p l i c a t i o n s c o n s i s t e n c y h o s tn o d es t o r e ss o m el o c a t i o ni n f o r m a t i o no fa l lr e p l i c a t i o nn o d e s ，a n dr e p l i c a t i o nn o d es t o r e st h el o c a t i o no fh o s tn o d e w h e nar e p l i c a t i o nh a sb e e nc h a n g e d ，r e p l i c a t i o nn o d es e n di n f o r m a t i o nt ot h eh o s tn o d e ，t h e nh o s tn o d ew i l ln o t i c eo t h e rr e p l i c a t i o nn o d e s i tm a k e ss u r et h a tu p d a t i n gm e s s a g e sw i l lb et r a n s f e r r e dt h r o u g hi tw i t h o u tf l o o d i n gb l i n d l y a tl a s t ，w es i m u l a t et h ea l g o r i t h m sm e n t i o n e da b o v eu n d e rl a b o r a t o r ye n v i r o n m e n t ，a n dp r o v et h ev a l i d i t yo ft h ea l g o r i t h m k e yw o r d s ：p 2 p ，f r e e n e t ，r e p l i c a t i o n ，c o n s i s t e n c ym a i n t e n a n c ei l l两华人学硕士学位论文8 声明本人声明所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得西华大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确地说明并表示谢意。本学位论文成果是本人在西华大学读书期间在导师指导下取得的，论文成果归西华大学所有，特此声明。作者签名：林正固年厂月占日别憷轹害p 年f 月万日5 1两华人学硕十学位论文9 授权书西华大学学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，西华大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位论文。本学位论文属于1 、保密口，在年解密后适用本授权书；2 、不保密瓯适用本授权书。( 请在以上口内划)学位论文作者签名：林孟闰日期：卅f f 誓主教师警：专1 乞镊j日期：口彳、 、2 ，b西华大学硕十学位论文1 概述1 1 课题的背景网络技术的飞速发展与迅速普及使其在现代社会中的重要性越来越突出了。网络规模越来越大。为了充分利用分散在网络上的每个微机的巨大资源，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 技术具有广阔的应用前景。i n t e m e t 上各种p 2 p 应用软件层出不穷，用户数量急剧增加。技术正不断应用到军事领域，商业领域，政府信息，通讯等领域，成为二十一世纪计算机技术的最令人关注的技术之一。数据副本即将一个数据项复制多份分别放在分布式系统的多个结点上，作为分布式系统的一个重要组成部分，副本对于分布式系统有着重要的意义，它可以提高系统的可靠性、存取效率和改善系统的性能。与传统领域中的副本管理技术相比，p 2 p 广域存储系统中的副本管理技术具有以下特点：广域网环境：p 2 p 广域存储中的副本分布于广域网上，广域网的异构性和消息传播的延迟对维护副本的一致性提出了新的要求。海量数据：数据量一般比较大，不仅表现为源数据的规模较大，而且副本的数量也很多。因此要求副本管理机制能够对海量数据进行良好的管理。动态组织结构：由于p 2 p 系统允许节点动态加入和退出系统，因此系统中的副本管理机制必须能够支持节点的动态加入和退出。负载动态性：p 2 p 系统的负载经常发生变化，这就要求系统中的副本能够在运行时刻根据系统负载和客户的需求进行动态创建和删除。p 2 p 广域存储中副本管理所面临的上述特点决定了传统的副本管理技术并不能够很好地应用到p 2 p 广域存储中，因此需要针对其中复制技术的特点，研究满足其要求的副本管理技术。西华大学硕十学位论文1 2 目标本文的目标首先是在于对p 2 p 统进行研究和分析。完整的了解这类系统的各方面特性。在此基础上对p 2 p 系统中副本放置问题进行分析最后得出一个优化结果，并且利用中心节点算法设计一个方案保证系统中副本的一致性。1 3 本文的内容组织第一章概述。本章对p 2 p 系统副本管理做一个简要的介绍，并说明了本文的动机和目标。第二章p 2 p 系统简介。这一章对p 2 p 文件共享系统进行概述，包括这种系统的历史起源及应用现状、系统的主要特性、对几个典型的时间应用系统的介绍、副本一致性原理在p 2 p 系统中的应用。第三章副本管理。这一章对f r e e n e t 系统进行了分析，首先，提出在不影响f r e e n e t 系统性能的前提下，减少系统中的副本。其次提出了中心节点算法来管理系统副本的一致性。第四章系统的测试、分析与评估。对改进过后的系统进行测试和分析工作，对改进过后的系统进行评价。第五章总结与展望。对本文做出总结，并提出以后工作地展望。2两华人学硕士学位论文2p 2 p 系统简介p 2 p 文件共享系统自从诞生以来就深受用户青睐，迅速风靡互联网。随着时间的推移，这一类型的用户数量不断增长，应用系统的数量也越来越多。作为一种新兴事物，它凭借着满足用户需求的功能赢得了用户的支持，拥有了良好的用户基础。用户的需求又反过来推动着p 2 p 文件共享系统的发展，赋予了它强大的生命力。众多的软件公司被其良好的市场前景所吸引，开发了多个应用系统。各种研究机构看它的发展潜力，致力与对它的研究。众多的国际学会议把p 2 pc o m p u t i n g 设为一个研究方向，作为分布式系统研究的一个组成部分。由此可见，p 2 p 文件共享系统有良好的发展空间。研究p 2 p 文件共享系统有必要了解这一系统的历史起源及现状，理解它的兴起原因及发展历程，关注相关的应用问题。进行深入研究的基础是对这一系统从整体上有全面的理解和认识，对各个方面有比较透彻的了解。熟悉一些有代表性的具体的p 2 p 文件共享系统，并进行有针对性的分析也是进行深入研究的必要前提。2 1p 2 p 网络的基本概念与分类2 1 1p 2 p 网络的特点p 2 p 技术主要指由硬件形成网络连接后的信息控制技术，主要代表形式是在应用层上基于p 2 p 网络协议的客户端软件。i b m 为p 2 p 作了如下定义：p 2 p系统由若干互联协作的计算机构成，且至少具有如下特征之一：系统依存于边缘化( 非中央式服务器) 设备的主动协作，每个成员直接从其他成员而不是从服务器的参与中受益：系统中成员同时扮演服务器与客户端的角色；系统应用的用户能够意识到彼此的存在，构成一个虚拟或者实际的群体。p 2 p 技术改变了“内容 所在的位置，使其正在从中心走向边缘，也就是说内容不再存在于主要的服务器上，而是存在所有用户的p c 机上。p 2 p 使得p c 重新焕发活力、不再是被动的客户端、而成为具有服务器和客户端双重特性的设备。p 2 p 网络是一种具有较高扩展性的分布式系统结构，其对等概念是指网络中的物理节点在逻辑上具有相同的地位，而并非处理能力的对等。3两华大学硕士学位论文比较传统的c l i e n t s e r v e r 系统与p 2 p 网络模式拓扑结构的不同，可以看出p 2 p 与c l i e n t s e i v c i 相比具有如下的特征i l l ：( 1 ) 非中心化：网络中的资源和服务分算在所有节点上，信息的传输和服务的实现都直接在节点之间进行，可以无需中间环节和服务器的介入，避免了可能的瓶颈。( 2 ) 可扩展：在传统的c s 模式中，系统能够容纳的用户数量和提供服务的能力主要受服务器的资源限制。而集中式服务器之间的同步、协同等处理又产生大量的开销，限制了系统规模的扩展。p 2 p 网络中，用户的加入在增加服务的需求，同时也使得系统整体的资源和服务能力得到了扩充。( 3 ) 健壮性：传统的集中式服务模式中，集中式服务器作为整个系统的中心，一旦发生网络中断、网络拥塞、节点失效等异常就会影响系统服务。而p 2 p 系统由一组对等节点构成，具有自组织特性，允许节点自由地加入和离开。部分节点失效时，系统能够自动调整整体拓扑，保持其它节点的连通性。某些p 2 p 模型还能够根据网络带宽、节点数、负载等变化不断地做自适应式的调整，具有很强的健壮性。( 4 ) 负载均衡：资源分布在多个节点，更好的实现了整个网络的负载均衡。( 5 ) 高性能价格比：计算机的计算和存储能力以及网络带宽等性能依照摩尔定理高速增长。而在目前互联网上，这些普通用户拥有的节点只是以客户机的方式链接到网络中，仅仅作为信息和服务的消费者，对于这些边际节点的能力来说，存在极大地浪费。采用p 2 p 网络可有效地利用互联网中散布的大量普通节点，将计算任务或存储资料分不到所有节点，以较小的代价达到超过集中式系统的规模。( 6 ) 隐私性：p 2 p 网络中，由于信息的传输分散在各节点之间进行，无需经过某个集中环节，用户的隐私信息被窃听和泄露的可能性大大缩小。虽然如此，但p 2 p 模型在管理容易性、数据覆盖率和数量等表现不如c l i e n t s c r v c r 模型，这是由于p 2 p 模型的特征造成的，是必然的。表2 - 1 列出了p 2 p 与传统c s 模型性能的比较。4西华人学硕+ 学位论文表2 1p 2 p 模型与传统c s 模犁的性能比较t a b l e2 - 1c o m p a r i s o no fp 2 pa n dc sm o d e l性能p 2 p 模型c s数据发布好差数据接收中好数据互动性好差数据即时性( 传输速度)好差数据安全性差好数据更新好差数据成本控制好差数据覆盖率和数量( 价值)差好数据管理方便性差好2 1 2p 2 p 网络的分类p 2 p 系统按照拓扑结构可以分为结构化p 2 p 和非结构化p 2 p 。这两种拓扑类型都是基于种叫做o v e r l a y l 2 l 的覆盖网络技术实现的，结构化和非结构化p 2 p 网络的主要区别在于结构化p 2 p 网络是按照某种规则进行组织和构建的，网络中的节点的加入和离开严格遵守这种规则。而非结构化p 2 p 则不存在这样的限制。2 1 2 1 非结构化p 2 p 网络非结构化p 2 p 网络又可以分为混合式拓扑、纯分布式拓扑以及带超级节点的拓扑【3 1 1 4 l 。1 混合式拓扑结构最开始的p 2 p 软件是一个集中式的p 2 p 网络，其各节点之间可以直接建立连接，但网络的构建需要服务器，通过集中认证，建立索引机制。然而这里的服务器仅用于辅助对等节点之间建立连接，一旦连接成功，服务器不再起作用，对等节点之间直接进行通信。这不同于c s 模式中的服务器，也可以认为是弱化了服务器的作用。这种p 2 p 网络模型和纯分散式p 2 p 网络相比，易于发现5西华人学硕士学位论文网络节点、易于管理且安全性较好，但是也有类似c s 模式的缺陷，如容错性差等。经典案例是n a p s t e r 。( 1 ) n a p s t e rn a p s t e r 5 删是由美国波士顿东北大学的一年级新生s h a w nf a n n i n g 为了共享m p 3 音乐文件而发明的，n a p s t e r 的出现带动了p 2 p 网络的发展。如图2 - 1 所示n a p s t e r 中没有文件存储服务器，只有用户的计算机和一个用来放置索引信息的服务器。用户在服务器上注册自己，提供其享的文件信息及位置信息等。需要文件的用户首先在服务器上进行信息查找，若系统中有节点共享了所请求的文件，则可根据服务器上提供的信息直接去节点下载，连接和下载过程中不需要服务器介入。这个架构的问题是当数据量巨大时，服务器的存储能力和运算能力会难以满足需求，查询响应时自j 会比较长。这一问题虽然可以通过提升服务器的性能来解决，但是代价在所难免。黪f i g u r e2 - 1 n a p s t e r m o d e l图2 - 1n a p s t e r 模型譬西华人学硕士学位论文2 纯分布式拓扑结构相对于集中式p 2 p 结构来说，非结构化纯分布式p 2 p 网络更加彻底地体现了p 2 p 的对等精神。它完全抛弃了基于服务器的思想，网络中不存在任何形式的单独的服务器，所有节点的地位完全对等，如图2 2 所示。这种结构的网络采用了随机图的组织方式，当有新的节点要加入到网络中时，它会自由地连接到其他节点，即随机选择某些节点作为邻居。纯p 2 p 结构非常适合于高度自治的节点组成的环境。纯分布式的非结构化p 2 p 网络相对于集中式p 2 p 的优点是显而易见的。由于网络中不存在中心服务器，单个节点的实效一般不会影响到整个系统的正常运转。因此它非常适合于节点动态变化的应用。由于具备较好的容错能力，较好的可用性，因而在互连网上得到了广泛的配置。其经典案例有g n u t e l l a 和f r e e n e t 。f i g u r e2 - 2u n s t r u c t u r e dp u r ep 2 pm o d e l图2 - 2 纯分布式非结构化p 2 p 模型( 1 ) g n u t e l l ag n u t e l l a l 7 1 1 8 】于2 0 0 0 年3 月在s l a s h d o t 网站j 下式发布。他的作者是j u s t i nf r a n k e l 和t o mp e p p e r ，这两位是n u l l s o f t 公司的创始人，著名的m p 3 传播软曲华大学硕十学位论文件w i n a m p 的创始者。g n u t e l l a 在发布时被称为“一种文件共享的工具，将比n a p s t e r 更强大”。不久之后发布g n u t e l l a 的网站就不再提供服务了，n u l l s o f i后来也没有在继续推出新版本的g n u t e l l a 软件。不过，当时已经有很多人下载了g n u t e l l a 软件，并且有一批程序员致力于继续开发这一工具软件。他们在技术和协议分析的基础上根据g n u t e l l a 协议开发了一些衍生系统。g n u t e u a 作为一种纯粹p 2 p 架构的分布式文件共享系统，其中的节点只知道与自己已经建立了连接的节点的存在，而不知道其它节点的存在，也就是说其它节点是不可见的，除非这些节点对本节点的探测或者请求消息做出了应答。节点发起文件搜索请求时提供了一个用于标志文件的搜索字符串和t i m e t o 1 i v e 参数，并把这个搜索请求发给与自己有链接的所有节点。收到搜索请求的节点在本地进行查找，若找到请求文件则沿着搜索路径方向返回搜索成功的信息，把本节点的相关信息如m 地址、端口等发回。请求者收到这些信息后就可以与目的节点建立连接下载文件。若在当前节点未找到所需文件则把请求进一步转发到与当前节点有链接的所有节点。消息转发的次数受到t i m e t o 1 i v e 参数的限制。新节点加入系统时至少要知道一个老节点的存在，通过发出t i m e t o 1 i v e参数的探索消息向老节点生命自己的存在。收到消息的老节点除了做出回应，把自身的口、端口、共享文件数目等信息传回之外，还把消息转发给与自己有连接的其它节点，转发次数受最初指定的t i m e t o 1 i v e 参数的限制。( 2 ) f r e e n e tf r e e n e t 9 l i l o l 起源于1 9 9 7 年，是由爱丁堡大学的i a nc l a r k e 发起的一个研究项目。该系统是一个完全分布式的，支持匿名的文档存储和检索的p 2 p 应用系统。它允许在发布、复制和检索文件的同时保护发布者和检索者的匿名性，其主要设计目标是：( 1 ) 保护文件的作者与读者的匿名性；( 2 ) 文件存储者的否认本领；( 3 ) 高效的信息路由和分布式的文档存储；( 4 ) 消除所有的单点控制和单点失效。f r e e n e t 是已经实现的点对点技术并以不受场所限制的密钥著称。每个节点维护他们自己在本地的数据存贮，提供网络对其进行读、写的能力，就像包含其他节点及密钥的动态路由表。他有意让系统的许多用户都能建立节点，同时提供措施防止恶意外部节点的攻击及提高整个网络存储的能力。f r e e n e t 系统可8两华大学硕十学位论文以被看成一个具有合作性质的分布式文件系统，具体表现为地域的独立性和透明、方便的复制机制。f r e e n e t 系统的路由机制不同于g n u t e l l a 中的泛洪模式，而是借助本地路由表采用深度优先的原则进行资源查询。f r e e n e t 最基本的模型为：对密钥的请求沿着节点通过一串代理请求向外发送，在这串代理中的每个节点都按照l p 路由的模式，做出一个向何处节点发送下个请求的决定。依靠请求密钥，路由不断变化。这是必须要做的，因为为了保护信息的隐蔽性，每个节点仅拥有在代理链上的与他们相连的上一个或者下一个节点信息。每个请求都受至1 h o p s t o i v e 的限制，与g n u t e l l a 中的t i m e t o 1 i v e ( t t l ) 类似，这是一个在每个节点上都减l 的变量，专门用来防止形成无穷的代理链。每个请求还被设计了一个“伪唯一随机标识符”，便于节点能拒绝他们曾经发出过的请求阻止死循环的发生。如果它们发现有一个请求是他们曾经处理过的请求，他们立即将前一个节点发出的信息转发到另外一个节点上。这个过程一直持续到满足这个请求或者超出它i 拘h o p s t o 1 i v e j 也限制。成功或者失败的结果都返回到发出这个请求的接点上。f r e e n e t 很重要的一个特点是：所有资料都是加密传输、分散存放，而且多次存放，具体一份资料的位置是无人知晓的，而且它们的疋地址和端口号是不断变化着的。自由网中的文件是通过二进制的索引密钥进行标识的，而索引密钥又是通过哈希运算得到的。f r e e n e t 使用1 6 0 位s h a - 1作为进行运算的哈希函数。一共采用了四种不同类型的文件索引密钥，它们的用途和构成方式都有所不同，这四种索引密钥分别是标识关键字索引密钥( k e y w o r d s i g n e dk e y ，简称k s k ) 、标识子空间索引密钥( s u b s p a c e s i g n e dk e y ，简称s s k ) 、内容哈希密钥( c o n t e n t h a s hk e y ，简称c h k ) 、地图空间索引密钥( m a p s p a c ek e y s ，简称m s k ) 。3 带超级节点的非结构化p 2 p在集中式和纯分布式的p 2 p 结构模型中，节点能力的异构性没有得到充分的考虑。而实际上，在某些p 2 p 网络中，各个节点的处理能力和行为方式差别很大l l 。为了适应这种现实需求，研究人员在纯分布式p 2 p 结构模型的基础上提出了超级节点概念。根据节点能力的不同将节点分为普通节点和超级节点。如图2 3 所示，超级节点与其直接相连的若干普通节点之间构成了一个自治的簇。在一个簇内，采用集中式的p 2 p 模式，整个p 2 p 网络中各个不同的9西华大学硕十学位论文簇之间，通过纯p 2 p 的模式将各个超级节点连接起来，形成了超级节点网络。其经典案例是k a 7 _ a a 。( 1 ) k a z a a如图2 3 所示k a z a a 1 2 l i l 3 】综合了n a p s t e r 和g n u t e l l a 模式形成了一种半分布的结构。在k a z a a 的系统下对等方被分为两种：普通对等方和组长。每个普通对等方被指派给一名组长，组长作为一个重要中心跟其它连接的对等方组成了一个类似于n a p s t e r 的系统；而许多组长之间通过t c p 连接形成一个类似于g n u t e l l a 的覆盖网络。一个查询请求先由组长在自己的对等方列表中查询，如果标示符未能匹配，则该组长将向它的邻居组长转发该查询。f i g u r e2 - 3u n s t r u c t u r e dp 2 pm o d e lw i t hs u p p e rn o d e图2 - 3 带超级节点的非结构化p 2 p1 0两华大学硕十学位论文2 1 2 2 结构化p 2 p 网络正如前面提到得那样，结构化p 2 p 模式一般都基于分布式哈希表d h t 进行组织和建立。d h t 类结构能够自适应节点的动态加入和退出，有着良好的可扩展性、鲁棒性、节点l d 分配的均匀性和自组织能力。由于覆盖网络采用了确定性拓扑结构，d h t 可以提供精确地发现。只要目的节点存在于网络中d h t 总能发现它，发现的准确性得到了保证。其经典案例包括c h o r d 、c a n和p a s t r y 。( 1 ) c h o r d如图2 - 4 所示c h o r d 1 4 】【1 5 】系统是一款基于d h t 算法的p 2 p 系统。d h t 的主要思想是：首先，每条文件索引被表示成一个( k ，v ) 对，k 称为关键字，可以是文件名( 或文件的其它描述信息) 的哈希值，v 是实际存储文件的节点的i p 地址( 或节点的其他描述信息) 。所有的文件索引条目( 即所有的( k ，v ) 对) 组成一张大的文件索引哈希表，只要输入目标文件的k 值，就可以从这张表中查出所有存储该文件的节点地址。然后，再将上面的大的文件哈希表分割成很多局部小块，按照特定的规则把这些小块的局部哈希表分布到系统中的所有参与节点上，使得每节点负责维护其中的一块。这样，节点查询文件时，只要把查询报文路由到相应的节点即可( 该节点维护的哈希表分块中含有要查找的( k ，v ) 对) 。这里面有个很重要的问题，就是节点要按照一定的规则来分割整体的哈希表，进而也就决定了节点要维护特定的节点，以便路由能顺利进行。c h o r d s 的实现方式：给定一个关键字k e y ，将其映射到某个节点。为此，采用相容哈希为每个节点和关键字产生一个m 位的l d ，并按照i d 大小构成环行拓扑。图2 4 表示了m = 6 的一个c h o r d 环，它可以容纳2 6 = 6 4 个节点。运行c h o r d 的主机相互连接构成c h o r d 网络，这是一个建立在口网络之上的覆盖网络。每个节点n 有2 个邻居，以顺时针为正方向排列在n 之前的第一个节点称为n 的前继节点，在n 之后的第一个节点称为n 的后继节点，资源放于其关键字l d 的后继节点上。为了路由的需要，节点保存前继节点和后继节点的信息，并维护一张最多m 项的路由表，称之为f i n g e r 表，其中，第k 项保存i d 为伽埘+ 2 k - 1 ) m o d 2 “的后继，图2 4 显示了节点n 8 的f i n g e r 表及其生成方法。两华人学硕士学位论文粥2f i g u r e2 - 4c h o r dr o u t i n gm o d e l图2 4c h o r d 路由模型f i n g e r 爱n s * ix l 二n g 。：n ! n 8 ，- ix 1 0n 8 - 8：x s 1 5n ；：n s - 3 二!( 2 ) c a n如图2 5 所示洲1 6 1 1 1 7 1 类似于一张大哈希表。c a n 由大量自治的节点组成。每个节点保存哈希表的一部分，称为一个区( z o n e ) 。此外，每个节点还保存少量的邻接区的信息。c a n 基于虚拟的d 维笛卡儿坐标空间实现其数据组织和查找功能。整个坐标空间动态地分配给系统中的所有节点，每个节点都拥有独立的互不相交的一块区域。如图2 5 所示给出了一个2 维的【0 1 1 【0 ，1 1的笛卡儿坐标空间划分成五个节点区域的情况，虚拟坐标空间采用下面的方法保存( 关键字，值) 对。当保存( k 1 ，v 1 ) 时，使用统一的哈希函数把关键字k 1 映射成坐标空间中的点p 。那么这个值将被保存在该点所在区域的节点中。当需要查询关键字k 1 对应的值时，任何节点都可以使用同样的哈希函数找到k 1 对应的点p ，然后从该点对应的节点取出相应的值。如果此节点不是发起查询请求的节点，c a n 将负责将此查询请求转发到对应的节点。c a n 中的路由机制非常简单，只需要计算目的点的坐标，然后寻找从发起请求的点到目的点的一条路径就可以。两华人学硕十学位论文( o 5 o 7 5 ，o 5 - 1 o )0 0、节点a 的虚拟坐标区域f i g u r e2 - 5w i t hf i v en o d e st w od i m e n s i o nc a nt o p o l o g y图2 - 5 有5 个节点的2 维c a n 拓扑7 5 1 0 ，o 5 - 1 o )( 3 ) p a s t r yp a s t r y t l 8 l 【1 9 】是微软研究院提出的可扩展的分布式对象定位和路由协议，它是由p a s 仃y 节点组成的自组织的高结构化覆盖网络( o v e r l a yn e t w o r k ) 。p a s t r y 节点需要维护3 种数据结构，如图2 6 所示：( 1 ) 路由表( r o u t i n gt a b l e ) 。假定网络由个节点组成，它有il 0 9 2 6 ni 行。每行有2 6 1 ( b 是一个配置参数，典型取值是1 ，2 ，3 ，4 ) 个入口的表项组成。行以的2 6 1 个入口指向其n o d e l d 和当前节点的n o d e l d 共享前万位但第n + 1 位不同的2 6 1 个表项。值b 的选择考虑了路由表的长度和路由跳数的权衡，b 越大则路由跳数越小，但需要维护的路由信息越多。路由表中每行的阴影项表示当前节点号对应的位。( 2 ) 叶子集( l e a fs e t ) 。存放的是和当前节点的标识符从数值上看最接近的节点，叶子节点集合在消息路由时需要用到。它是i 工i 2 的下取整数( i 三i 是配置参数值为2 6 ) 个其n o d e l d 最接近且大于本地节点n o d e l d 的节点和l i 2的下取整数个其n o d e l d 最接近且小于本地节点的n o d e l d 的节点集合。西华大学硕+ 学位论文( 3 ) 邻居集( n e i g h b o r h o o ds e t ) 。它包含同本地节点最接近的imi ( imi 是配置参数，值为2 x 2 6 ) 个节点，用于保证路由表中每个表项指向的节点都是离当前节点最近的节点，保证的自 提是网络距离度量满足欧氏空间的三角不等式。当前节点周期性地和邻居节点集合总的节点交换信息以验证这个节点是否仍在p a s t r y 系统中，如果某个节点失效，那么当前节点将要求其他邻居节点把自己的邻居节点集合发送过来并从中选择一个新的邻居节点来替换失效节点。n o d e i ( 11 0 2 3 3l ( 2l e a f s e ts 卫压a i i ，e rl a r g e rl10 2 3 3 0 3 31 0 2 3 3 0 2 11 0 2 3 3 1 2 01 0 2 3 3 1 2 21 0 2 3 3 0 0 110 2 3 3 0 0 010 2 3 3 2 3 010 2 3 3 2 3 2r o u t i n gt a b l e2 2 3 0 1 2 0 33 1 2 0 3 2 0 30 2 2 1 2 1 0 2101 1 3 0 1 2 3 31 2 2 3 0 2 0 31 3 0 2 l0 2 21 0 0 3 1 2 0 31 0 1 3 2 1 0 22l0 3 2 3 3 0 2l0 2 0 0 2 3 01 0 2 1 1 3 0 2l0 2 2 2 3 0 2310 2 3 0 3 2 21 0 2 3 1 0 0 01 0 2 3 2 1 2 l31 0 2 3 3 0 0 l110 2 3 3 2 3 201 0 2 3 3 1 2 02n e i 寸l b o r h o o ds e t1 3 0 2 1 0 2 2l0 2 0 0 2 3 01 1 3 0 1 2 3 33 1 3 0 1 2 3 30 2 2 1 2 1 0 22 2 3 0 12 0 33 1 2 0 3 2 0 33 3 2 1 3 3 2 lf i g u r e2 - 6d a t as t r u c t u r eo fp a s t r y sn o d e图2 - 6p a s t r y 节点数据结构示意图1 4西华人学硕十学位论文2 2 副本创建策略副本创刊2 0 l 1 2 2 1 【2 3 1 通常分为静态副本创建和动态副本创建两类。静态副本创建是由系统管理员统一安排好系统布局后，副本布局将固定不变；若用户访问发生较大变化而要求改变这种布局时，必须由管理员重新配置。动态副本创建允许系统在运行时刻，自动选择存储结点进行副本创建、撤消并根据用户的访问特征自动变化副本创建策略。后者为系统提供了更强的灵活性和可扩展性。由于p 2 p 网络环境具有动态性，广域性以及资源数量大等特点，只有动态数据副本创建才能满足p 2 p 网络环境的要求。动态数据副本创建策略1 2 4 1 【冽一个关键问题是副本创建的位置。不同的副本放置策略会直接影响用户请求响应时间和广域网带宽消耗，从而影响数据网格系统的性能。另外，需要解决副本创建的粒度问题。考虑到复制时带宽消耗、用户访问性能和副本占用空间代价等问题，副本创建时可能只需要拷贝初始数据的一部分，而不是全部。副本创建和撤消的时机也是副本创建涉及的一个问题。只有在满足一定的条件后，才触发副本创建服务，例如某个副本在一定时间段内被请求的次数超过特定阈值等。在实际应用中，需要根据具体的于p 2 p 网络环境和用户访问特征等来设计合适的副本创建策略。2 2 1 创建副本的问题在副本创建时必须讨论以下两个问题：( 1 ) 副本应放置在合适的位置，以保证各个服务器的负载均衡。( 2 ) 选择最佳副本数量。也就是说为了维护系统的整体性能，必须在可靠性、访问效率和一致性开销之间找到平衡。1 副本位置提高数据的访问效率是复制技术设计的初衷。如果一个数据的访问需求过高，而网络中又没有该数据集的副本，很容易导致网络的带宽过分消耗和单个节点负载过重。复制技术通过一系列的副本放置策略在数据需求量非常大的节点附近放置该数据的副本，有效地提高了数据的访问效率。同时，由于网络中节点的自由度较高，它可以自由地加入和退出网络，并且网络问题或者节点瘫痪等都可导致节点不可访问，所以系统中任何单个节点1 5两华人学硕+ 学位论文的可靠性都是非常差的。而复制技术使一个数据集在系统中有了多个副本，它们保存在多个单独的节点中，这样从客观上大大提高了获得至少二个数据副本的概率。2 届u 本数量当副本数在一定范围内增加时，访问效率随之明显增加；当副本数超过一定范围时，访问效率并不随副本数的增加而增加，反而会减少。这是因为随着系统中副本数的增多，维护数据一致性的开销急剧增大，影响到整个系统的性能，进而表现为访问延迟并不再随副本的增加而减少。在系统中，增加一个副本的开销包括副本复制开销和目录更新开销。当一个节点中的副本被更新时，系统就要考虑到文件一致性维护的开销，它包含三个部分：( 1 ) 一个副本文件更新后，更新原文件的开销；( 2 ) 原文件更新后，写所有节点中的文件副本带来的开销；( 3 ) 目录更新的开销。一般说来，应该为读操作频繁的文件保持较多的副本，提高数据读取的效率和可靠性；操作较频繁的数据应保持较少的副本，减少其更新时维护副本一致性的费用。2 2 2 几种典型的副本复制策略副本的数目并非越多越好。因为要保持系统中多个副本的一致性，当数据被修改时，必须更改所有的副本，这将带来巨大的带宽消耗和更新开销。总之，在为数据创建副本时，副本过多，则副本节点维护副本的费用会非常昂贵【冽；副本过少，则无法保证数据访问的效率。目前流行的复制策略【2 7 l 是均匀复制( u n i f o r ms t r a t e g y ) 策略，比例复制( p r o p o r t i o n a ls t r a t e g y ) 策略和均方根策略。下面我们面我们是对这三种算法的简单描述：假使网络中有万个节点，m 个数据文件，一个节点的r e p l i c a t i o n 平均数目容量是c ，n c = r 是系统全部的容量。用g 表示不同文件的查询频率，设9 。q l 苫q 2 q 3 苫q 4 q m ，罗一1 ，讲是查询队列中第f 个查询序列。尉代表第f 个数据的拷贝数目( 包括o w n e r ) 。p 一r i r 是占所有容量的比例。了，f r ( r l r ，r 2 r ，r 3 r ，r m r ) 。均匀策略( u n i f o r ms t r a t e g y ) ：简单说来就是遵循每个共享的文件拷贝数目一样的原则对文件进行复制。1 6两华人学硕士学位论文定理2 1 当r m c ，p i = 1 mf 一1 , 2 t t 因为当朋 c 最优化安置的方式就是在每个节点都有每个文件备份，而当 。节点d 和节点e 收到的更新消息标签中已包含了其所有邻居节点不再传输。在整个过程中，对于洪泛算法减少了2 条更新消息。当然这种方法的一个缺点是随着更新消息的传播条数的增加，消息头部中记录以传播节点的地址信息也不断增加，消息变得越来越臃肿。为了应对这种不利状况，文献1 3 7 j 采用b l o o mf i l t e r 编码技术加以解决。需要注意的是，虽然利用节点轨迹算法的思路简单，可以减少传输冗余，但是仍然不可避免的存在消息的冗余，例如图中c 至i j e 和f 到e 两条消息。( 3 ) 基于谣言( g o s s i p ) “推( p u s h