（计算机应用技术专业论文）基于混合p2p结构的网格存储模型的研究.pdf

摘要 基于混合p 2 p 结构的网格存储模型的研究 摘要 网格是利用高速国际互联网把地理上广泛分布的各种资源，包括 计算资源、存储资源、带宽资源、软件资源、数据资源、信息资源、 知识资源等连成一个逻辑整体，就像一台超级计算机一样为用户提供 一体化信息和应用服务。 随着计算机技术和i n t e r n e t 的发展，网络上出现大量闲散的自治 结点，用何种方法能够有效而可靠的利用这些闲散结点的剩余资源， 成为今年来研究的热点之一。 本文首先讨论和总结了分布式存储的发展历史和现状，并在对 p 2 p 技术的研究现状进行了系统、全面的分析和总结的基础上，设计 了一种基于混合型p 2 p 技术的网格存储模型。该存储模型将大量分散 的结点组织成一个逻辑网络。在系统内部，结点被分为服务器结点， 超级结点和一般结点，并结合热点文件和超级结点的特点，对原有的 方根复制策略进行了改进，提出了一种混合型的副本备份策略，即在 一般结点上存储的数据按照方根复制策略进行备份；在超级结点上， 利用r a i d 技术备份热点文件的副本，经过仿真试验证明，在维持相 同可用性的前提下，超级结点上采用r a i d 技术备份文件副本的策 略，能够比单纯的方根复制策略有效的节省有限的网络空间资源。 关键词：p 2 p ，网格，r a i d ，分布式存储 a b s t r a c t r e s e a r c ho nt h eg i u ds t o r a g em o d e lb a s e d o nh y b i r dp 2 p a b s t r a c t g r i di sak i n do ft h et e c h n o l o g yt h a tu s i n gh i g h s p e e di n t e r n e to na b r o a d g e o g r a p h i c a l - d i s t r i b u t e d o fv a r i o u sr e s o u r c e s ， i n c l u d i n g c o m p u t i n gr e s o u r c e s ， s t o r a g er e s o u r c e s ， b a n d w i d t hr e s o u r c e s ， s o f t w a r er e s o u r c e s ，d a t ar e s o u r c e s ，i n f o r m a t i o nr e s o u r c e s ，k n o w l e d g e r e s o u r c e s ， a sal o g i c a lw h o l et h i n g ，j u s ta sas u p e r c o m p u t e ra st o p r o v i d eu s e r sw i t ht h ei n t e g r a t i o ns e r v i c e so fi n f o r m a t i o na n da p p l i c a t i o n w i t ht h ec o m p u t e rt e c h n o l o g ya n di n t e r n e td e v e l o p m e n t ，t h e r ea r e l a r g en u m b e ro fi d l en o d e sa p p e a r e do nt h en e t i nw h i c he f f e c t i v ea n d r e l i a b l ew a yt ob ea b l et ou s et h er e m a i n i n gr e s o u r c e so ft h ei d l en o d e si s ah o tr e s e a r c ht o p i ci nr e c e n t l yy e a r s f i r s t ，t h i sp a p e rd i s c u s s e sa n ds u m m a r i z e st h ed e v e l o p m e n ta n d a c t u a l i t y o fd i s t r i b u t e d s t o r a g es y s t e m s b a s e d o n s y s t e m a t i c a l l y a n a l y z i n g a n d s u m m a r i z i n g t h er e l e v a n tw o r k so n p e e r - t o - p e e r t e c h n o l o g y ， i td e s i g n sah y b r i dp 2 pb a s e dd i s t r i b u t e ds t o r a g es y s t e m o r g a n i z e sl a r g en u m b e r so fn o d e sd i s t r i b u t e di ni n t e r n e ti n t oau n i t e d o v e r l a yn e t w o r k t h es y s t e md i v i d ei n t ot h r e ek i n d so fn o d e ，t h e r ea r e s e r v e rn o d e ， s u p e rn o d ea n dg e n e r a ln o d e c o m b i n e dw i t ht h e i i i 北京化丁大学硕l 学位论文 h a r a c t e r i s t i c so fh o td o c u m e n t sa n ds u p e r - n o d e ，w em o d i f yt h eo r i g i n a l s q u a r e r o o tr e p l i c a t i o ns t r a t e g y ， a n dt h e np r e s e n tan e wm i x e d t y p e r e p l i c a t i o no fb a c k u ps t r a t e g y t h a ti s ，u s i n gt h es q u a r e - r o o tr e p l i c a t i o n i nt h eg e n e r a ln o d ea st h eb a c k u ps t r a t e g y ；a n du s i n gt h er a i d t e c h n o l o g yb a s e do nt h eh o t s p o td o c u m e n ti nt h es u p e r - n o d e s i m u l a t i o n t e s tp r o v e dt h a tt h ep r e m i s eo fm a i n t a i n i n gt h es a m ea v a i l a b i l i t y ， c o m p a r e dw i t ht h eo r i g i n a ls t r a t e g y ，t h em i x e d - t y p er e p l i c a t i o no f b a c k u ps t r a t e g yc a nb em o r ee f f e c t i v ei ns a v i n gt h el i m i t e dr e s o u r c e si n c y b e r s p a c e k e yw o r d s ：p 2 p ，g r i d ，r a i d ，d i s t r i b u t e ds t o r a g e i v 北京化工大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 作者签名： 磊玖 日期： 冲釉两观 关于论文使用授权的说明 学位论文作者完全了解北京化工大学有关保留和使用学位论文 的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北 京化工大学。学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编 学位论文。 保密论文注释：本学位论文属于保密范围，在上年解密后适用 本授权书。非保密论文注释：本学位论文不属于保密范围，适用本授 权书。 作者捧名： 导师签名： 橛 一型一瓤一一 第一章引苦 1 1研究背景 第一章引言 互联网始于1 9 6 9 年，是在a r p a ( 美国国防部研究计划署) 制定的协定下将 美国西南部的大学u c l a ( 加利福尼亚大学洛杉矶分校) 、s t a n f o r d r e s e a r c h l n s t i t u t e ( 史坦福大学研究学院) 、u c s b ( 加利福尼亚大学) 和 u n i v e r s i t y o f l a t a h ( 犹他州大学) ) 的四台主要的计算机连接起来。这个协定由剑桥 大学的b b n 和m a 执行，在1 9 6 9 年1 2 月开始联机。到1 9 7 0 年6 月，m r r ( 麻省 理卫豹葡、h 刚匮d 畔溯呔鹄、b b n 和s y s t e m sd e v e l o p m e n tc o r p i ns a n t a m o n i c a ( n 少h 圣达莫尼卡系统发展公司) 加入进来。到1 9 7 2 年1 月，s t a n f o r d ( 史坦福大学) 、 m r r s l i n c o l n l a b s ( 麻省理工学院的林肯实验室) 、c a r n e g i e m e l l o n ( 卡内基梅隆大 学) 和c a s e w e s t e r n r e s e r v e u 加入进来。紧接着的几个月内n a s a a m e s ( 国家航 空和宇宙航行局) 、m i t r e 、b u r r o u g h s 、r a n d ( 兰德公司) 和t h e u o f l l l i n o i s ( 伊利诺 利州大学) 也加入进来【1 1 。 最初的网络是给计算机专家、工程师和科学家用的。当时一点也不友好。那 个时候还没有家庭和办公计算机，并且任何一个用它的人，无论是计算机专家、 工程师还是科学家都不得不学习非常复杂的系统。 由于t c p i p 体系结构的发展，互联网在七十年代迅速发展起来，这个体系 结构最初是有b o b k a h n ( 鲍勃卡恩) 在b b n 提出来的，然后由史坦福大学的 k a h n ( 卡恩) 和v m t c e r f ( 温特瑟夫) 和整个七十年代的其他人进一步发展完善。八 十年代，d e f e n s e d e p a r t m e n t ( 美国国防部) 采用了这个结构，到1 9 8 3 年，整个世 界普遍采用了这个体系结构。 当e - m a i l ( 电子邮件) 、f t p ( 文件下载) 和t e l n e t ( 远程登录) 的命令都规定为标准 化时，学习和使用网络对于非工程技术人员变的非常容易。虽然无论如何也没有 今天这么容易，但对于在大学和特殊领域里确实极大地推广了互联网的应用。其 它的部门，包括计算机、物理和工程技术部门，也发现了利用互联网好处的方法， 即与世界各地的大学通讯和共享文件和资源。图书馆，也向前走了一步，使他们 的检索目录面向全世界。 由于最开始互联网是由政府部门投资建设的，所以它最初只是限于研究部 门、学校和政府部门使用。除了以直接服务于研究部门和学校的商业应用之外， 北京化t 人学硕j ：学位论文 其它的商业行为是不允许的。9 0 年代初，当独立的商业网络开始发展起来，这 种局面才被打破。这使得从一个商业站点发送信息到另一个商业站点而不经过政 府资助的网络中枢成为可能。 d e p h i 是最早的为他们的客户提供在线网络服务的国际商业公司。1 9 9 2 年7 月开始电子邮件服务，1 9 9 2 年1 1 月开展了全方位的网络服务。在1 9 9 5 年5 月， 当国际科学基金会失去了互联网中枢的地位，所有关于商业站点的局限性的谣传 都不复存在了，并且所有的信息传播都依赖商业网络。a o l ( 美国在线) 和 c o m p u s e r v e ( 美国在线服务机构) 也开始了网上服务。在这段时间里由于商业应用 的广泛传播和教育机构自力更生，这使得国际科学基金会成本投资的损失是无法 估量的。 今天，国际科学基金会已经放弃了资助网络中枢和高等教育组织，一方面开 始建立当地公共图书馆，另一方面研究提高网络大量高速的连接。 互联网能够发展至今，根本原因在于其布建的任何一根血脉都是为人与人之 间的交流而设置的。而现在能够引起互联网震动的，无非也只有交流方式的变革 本身。如今，在基于网络的各种技术充斥于我们周围之时，恐怕只有很少人不 知道p 2 p 的概念了，即便您没有深入探究，但您每日在互联网间进行的活动几乎 没有不沾p 2 p 技术的。一个简单的例子，在你使用q q 尽情聊天之时，实际上就 享受着p 2 p 技术给你带来的快感与兴奋。p 2 p 技术究竟意味着什么呢? 关于p 2 p 技术的两种解释或许可以说明这个问题。 一种解释是，p 2 p 即p e e rt op e e r 。而p e e r 在英语里是“同等者 、“同事” 和“伙伴的意思。这样一来，p 2 p 也就可以理解为“伙伴对伙伴 的意思，或 称为对等联网。而另一种解释是，p 2 p 就是一种思想，有着改变整个互联网基础 的潜能的思想。客观讲，单从技术角度而言，p 2 p 并未激发出任何重大的创新， 而更多的是改变了人们对因特网的理解与认识。正是由于这个原因，i b m 早就 宣称p 2 p 不是一个技术概念，而是一个社会和经济现象【2 1 。 不管是技术还是思想，p 2 p 是直接将人们联系了起来，让人们通过互联网直 接交流。它使得网络上的沟通变得更容易、更直接，真正地消除中间环节。这听 起来仿佛全新的概念，但其实并不是什么新鲜事。我们每天见面，或者通过电话 直接交流都是p 2 p 最直接的例子。而这个时候你有没有从电话的发展的历史中隐 约感觉到，p 2 p 必将在互联网时代有着突飞猛进的发展，因为他可以改变现在的 i n t e m e t 以大网站为中心的状态、重返“非中心化”，并把权力交还给用户，让我 们的语言影像以最直接的方式传递到对方身边。它最符合互联网络设计者的初 衷，给了人们一个完全自主的超级网络资源库。 网格有着与p 2 p 相似的构建目的和作用，但网格更多的是面向大型的专业设 2 第一章引苦 备，它是构筑在互联网上的一组新兴技术，它将高速互联网、高性能计算机、大 型数据库、传感器、远程设备等融为一体，为用户提供了更多的资源、功能和交 互性。它让人们可以透明地使用计算、存储等其他资源【3 1 。随着网格概念和计算 机技术的不断发展，分布式存储技术取得了长足的进步，然而用户和数据的不断 增加，系统规模的不断扩大，对分布式存储技术提出了更高的要求，另外，随着 网络带宽的大幅增加和计算机能力的迅速增强，在传统的客户机服务器模式中 被忽视的客户机成为一种宝贵的资源。微软公司对4 8 0 1 台个人计算机，1 0 5 6 8 个文件系统，共1 0 5t b 的数据进行了跟踪试验，分析并总结了这些机器的使用 情况【4 】。实验表明，个人计算机平均只有5 0 的存储资源得到了利用，大量的 存储空间处于空闲状态。然而，目前仍然缺少一个有效的网格资源管理平台，使 得用户可以更加方便、有效的使用网格资源。p 2 p 存储系统就是充分利用计算机 的空闲计算资源、存储资源和带宽资源，构建高可扩展、高可靠、高性能的分布 式存储系统。本文结合p 2 p 的优势，提出了一种基于混合p 2 p 结构的网格存储 系统模型。 1 2论文内容及组织结构 本文系统、全面地学习和总结了分布式存储系统的发展现状和未来趋势，并 在此基础上，深入细致地研究了基于p 2 p 网络的分布式存储系统的系统构建、混 合式p 2 p 网络的路由和定位方法、动态副本管理和热点问题等内容。在以上研究 的基础上，设计并实现了一个基于混合p 2 p 技术的网格存储系统。后续章节的主 要内容安排如下： 第二章理论基础与相关技术 主要介绍了分布式存储系统的基础知识和相关技术，并对p 2 p 技术的发展与 应用做了简要阐述，最后对p 2 p 存储技术的研究现状做了简要分析。 第三章系统结构与总体设计 在分析了系统可行性的基础上，给出系统的整体结构和总体框架下的几个大 的组成模块，并在最后对系统的几个典型文件操作给出了算法描述。 第四章基于访问频率的动态副本管理机制 本章主要是对混合型p 2 p 副本备份策略作深入研究，首先我们对整体复制策 略以及r a i d 技术作了介绍，然后在对动态副本管理进行分析的基础上，提出了 一种新的基于访问频率的动态副本管理机制。 第五章系统实现与性能分析 对整个系统的功能和性能做了全面测试，并分析了测试结果。 3 北京化1 二人学硕l ：学位论文 第六章结论与展望 总结了全文，并展望未来技术的发展。 4 第二章理论基础j 相关技术 第二章理论基础与相关技术 在开始之前，我们先来看一组数据。德国互联网调研机构i p o q u e 称，p 2 p 已经彻底统治了当今的互联网，其中5 0 9 0 的总流量都来自p 2 p 程序。在p 2 p 程序里，b i t t o r r e n t 已经超过e d o n k e y ( 含e m u l e ) ，占了p 2 p 流量的5 0 - 7 0 ，而 后者根据地区不同份额为5 - 5 0 ，不过在某些地方，e d o n k e y 仍是p 2 p 首选。 e l l a c o y an e t w o r k s 在6 月份公布的统计数据则显示，北美网络流量中已有3 7 来自p 2 p t 2 1 。 2 1p 2 p 技术简介 p 2 p 是p e e rt op e e r ( 对等网络) 的简称，p 2 p 网络中的结点被称为p e 呱对等 体) ，它们之间可实现点到点的对等通信。目前，业界并未对p 2 p 技术形成统一 的定义，我们可以参照i n t e l 公司对p 2 p 系统的定义，将p 2 p 理解为“通过系统间 直接交换达成计算机资源与服务共享”的系统，这些资源与服务包括信息交换、 处理器时钟、缓存和磁盘空间等1 5 。 p 2 p 技术与应用的出现是i n t e m e t 发展过程中的重要事件。2 0 0 1 年，p 2 p 应 用首先在文件共享领域兴起，发展至今，已成为互联网领域的主流应用。据不完 全统计，在i n t e m e t 上出现的p 2 p 系统超过了2 0 0 个，范围涵盖即时通讯、电子 杂志、s n s 、流媒体等多个领域，相对于其它类型的i n t e m e t 应用，p 2 p 应用在 用户规模和互联网带宽占用方面都占有较大优势。目前，p 2 p 应用主要集中在文 件交换、即时通信和流媒体等几大领域【6 】。 其实简单的说，p 2 p 直接将人们联系起来，让人们通过可以直接连接到其他 用户的计算机、交换文件，而不是像过去那样连接到服务器去浏览与下载。就像 在现实生活中我们每天都按照p 2 p 模式面对面地或者通过电话交流和沟通。但是 伴随着p 2 p 的发展，涉密、版权等法律问题也相继出现【阳】。 2 1 1p 2 p 技术的发展 7 0 年代的终端主机( t e r m i n a l h o s t ) 计算模式使得数据集中存储在主机上， 数据存储的核心是主机上高效率的文件系统。8 0 年代以后，客户机i l l 务器 ( c l i e n t s e r v e r ) 模式得到了广泛普及，客户杌服务器模式的分布式存储技术得 到了长足发展，在这种模式下，数据集中在各种服务器上，用户通过服务器获取 所需的数据。然而，随着i n t e m e t 的兴起，原有的传统模式得到了彻底的改革和 北京化工人学硕 - e 学位论文 颠覆，于是p 2 p 适时的出现了。我们所说的c s ，分布式系统以及p 2 p 网络，都 是指t c p l p 模型的第四层应用层的工作方式，如表2 1 所示， 表2 - 1t c p i p 模型 层次协议 应用层 c s ，p 2 p 传输层tcpudp 网络层 i p 接入层链接协议与物理协议 而下面的三层通常是采用标准、单一的工作方式，本身并没有集中式与分布式之 分，只是为应用层不同的工作方式提供底层的服务支持。p 2 p 网络的核心机制， 是在应用层建立逻辑上的覆盖网络( o v e r l a y - n e t w o r k ) ，封装下面三层，让p 2 p 网络的研究者和开发者不必关心下面三层是如何工作的，而仅仅去考虑应用层覆 盖网络的工作情况【9 1 。 p 2 p 本身的基本技术的存在时间和我们曾经熟悉的u s e n e t 、f i d o n e t 这两 种非常成功的分布式对等网络技术几乎是一同的，甚至更长些。翻翻资料就可以 知道，u s e n e t 产生于1 9 7 9 年，f i d o n e t 创建1 9 8 4 年，它们都是一个分散、 分布的信息交换系统。在最初的p 2 p 应用出现时，许多使用该技术的人们甚至 不会使用计算机。然而正是这种孕育着思想的网络技术为p 2 p 的出现搭建了摇 筷 j 吐o p 2 p 正式步入发展的历史可以追溯到1 9 9 7 年7 月，那几乎就是互联网在中 国起步的阶段。在一段介绍此时p 2 p 技术的时间表中这样写着：“1 9 9 7 年7 月， h o t l i n ec o m m u n i c a t i o n s 公司成立，并且研制了一种可以使其用户从别人电脑中 直接下载东西的软件 【2 j 。 或许有人还记得，早在1 9 9 8 年，美国东北波士顿大学的一年级新生、1 8 岁 的肖恩范宁为了能够解决他的室友的一个闯题一如何在网上找到音乐而编写 的一个简单的程序，这个程序能够搜索音乐文件并提供检索，把所有的音乐文件 地址存放在一个集中的服务器中，这样使用者就能够方便地过滤上百的地址而找 到自己需要的m p 3 文件。到了1 9 9 9 年，令他们没有想到的是，这个叫做n a p s t e r 的程序成为了人们争相转告的“杀手程序l 它令无数散布在互联网上的音乐 爱好者美梦成真，无数人在一夜之内开始使用n a p s t e r 。在最高峰时n a p s t e r 网络 有8 0 0 0 万的注册用户，这是一个让其他所有网络望尘莫及的数字。这大概可以 作为p 2 p 软件成功进入人们生活的一个标志。 之所以我们注重开端，是因为这是一个非同意义上的起始，也正是从这天起， p 2 p 开始了它曲折但极富生命力的发展。 6 第= 章理论基础，相关技术 到了2 0 0 0 年，p 2 p 技术的发展就得使用月甚至同来记载了。直到现在使用 p 2 p 技术的软件比比皆是，人们也在不知不觉中感受到了p 2 p 作为高科技发展载 体的快乐。平常我们使用的q q 、m s n 就不提了，其他软件更是铺天盖地，让 人目不暇接”。 p 2 p 的发展主要经历了三个阶段： 2 111 第一阶段，中心化拓扑p 2 p 网络 1 9 9 9 年，1 8 岁的肖恩范宁开发了世界上第一个应用性的p 2 p 网络软件 n a p s t e r ，在半年的时间里即拥有5 0 0 0 万注册用户，最高超过6 1 0 0 万用户，这在 计算机网络领域是一个从未有过的奇迹。图2 - 1 是以n a p s t e r 为代表的中心化拓 扑p 2 p 网络图。 图2 - 1 中心化拓扑图 n a p s t e r 实质上并非是纯粹的p 2 p 系统，它通过一个中央服务器组保存所有 n a p s t e r 用户上传的音乐文件索引和存放位置的信息【l q 。每个服务器保存一部分 用户的共享文件索引信息，所有的服务器互联、整合起来对网站外面的n a p s t e r 用户提供统一的访问接口，在每个用户看来，他们访问的都是同一个服务器。每 个n a p s t e r 用户联结到其中一台服务器，他将愿意与其他用户共享的文件信息发 送给服务器，服务器记录这些信息以及该用户的位置，并将他们做成一条索引添 加到原有的索引表中。当有另外一个用户需要下载这个文件时，首先，他将查询 消息发送至服务器，服务器返回一个确认消息和索引地址，按照这个索引地址， 用户之间互相建立连接，并下载需要的文件。服务期一方面维护所有用户的共享 文件索引，另一方面监控系统中每个用户的状态，比如跟踪记录用户所报告的连 接带宽、连接时间以及掉线信息。这些信息对系统运行有很重要的意义：首先， 对于那些掉线的用户，必须在服务器中去掉该用户对应的文件索引，以保证文件 北京化丁大学硕一l ：学位论文 索引的实效性。其次，当服务器收到用户的查询消息后，返回给该用户的消息中 包含了其他用户的连接带宽、连接时问等信息，这些信息将有助于该用选择与哪 些用户建立什么样的连接【l l 】。 虽然系统将所有的用户看成平等的成员，但是实际上各用户的连接能力还是 有很大不同的，这也就是p 2 p 网络的异构性。就连结时间而言，超过5 0 的用 户连接时问低于1 小时，不到1 0 的用户连接时间高于6 小时【1 1 】【1 2 】，在理想情 况下，系统希望它的每个用户都能在下载的同时提供一些文件上传，这样网络才 高效、平衡。然而，在实际的网络中，很多用户都是自私的，约2 0 4 0 的用 户几乎从来不提供文件共享而只是下载别人的文件，即使不自私的结点，绝大部 分也只是贡献少量的文件。相反，系统中真正提供文件共享的，是网络中少数约 1 的结点，他们才是系统真正的文件提供剖1 3 】。 中央化拓扑的p 2 p 网络首先实现了文件查询与文件传输的分离，有效地节省 了中央服务器的带宽消耗，减少了系统的文件传输延时。这种方式最大的隐患在 中央服务器上，如果该服务器失效，整个系统都会瘫痪。当用户数量增加到1 0 5 或者更高时，n a p s t e r 的系统性能会大大下降。另一个问题在于安全性上，n a p s t e r 并没有提供有效的安全机制。第三，网络结点中存在很多自私结点，他们只下载 文件，几乎从来不上传。自私结点大对于整个网络来说几乎是没有贡献只有消耗 1 3 1 o 然而n a p s t e r 的陨落却并不是因为技术问题，而是法律问题。它被多家唱片 商以侵犯版权为由推上被告席，使其音乐p 2 p 交换的生涯难以为继，最终n a p s t e r 被转卖给他人，而其作为p 2 p 软件的历史也彻底结束了。现在我们看到 w w w n a p s t e r e o m 网站已经是一个付费的在线音乐网站了，虽然还是那个网址， 还是那个标志，但实际上他已经和p 2 p 没有任何关系了【1 0 1 1 3 】。 2 1 1 2 第二阶段，无结构p 2 p 网络 无结构p 2 p 网络和中央化拓扑p 2 p 网络的最大的区别在于无结构p 2 p 是更 加纯粹的p 2 p 系统，因为它没有中央索引服务器，每台机器在网络中是真正的对 等关系，既是客户机同时又是服务器，所以被称为对等机【1 4 】。它以出现在2 0 0 3 年3 月美国的g n u t e l l a 为代表。图2 - 2 是g n u t e l l a 的工作原理图 第一章理论幕础d 柏关技术 图2 , - 2 g n u t e l l a 工作原理图 g n u t e l l a 是一套开放式、非集中化得个人对个人搜索系统，这意味着该网络 的存在并不依赖于某家中央服务器。每个结点即是服务器又是结点，既能向其它 结点发送查询请求并获得查询结果，又能接收其它p e e r 发来的查询请求、返回 所有的文件信息或者将此请求路由给其它的结点。除此之外，系统中的每个结点 还负责监控网络局部的通信状态，互相协作以保持整个网络的完整性与一致性。 要做到这一点，用户必须能找到其他用户，这可以通过于结点相连、连接到其他 结点的索引表【l 目。 g n u t e l l a 在因特网上构建了一个应用层覆盖网络，覆盖网上每个结点对应实 际的一台网络计算机，而覆盖网上每条连接对应因特网上一条点对点的链路。覆 盖网上的连接是由每个结点所保存的“邻居结点”信息确定的，有一个邻居结点就 对应有一条边。 如果因特网上某台计算机要加入g n u t e l l a 网络，它必须首先连接到一个几乎 总是在线的g n u t e n a 结点上，这些结点被称为入口结点。这些入口结点相当于一 个中介，将网络外的结点介绍进网络来。由于这些入口结点众多，且功能等价， 所以并不破坏网络的纯分布式的特性。 在文件检索方面，它与n a p s t e r 也不相同。在g n u t e l l a 网络的发展初期，它 主要采用基于完全随机图的洪泛搜索算法。当一台计算机要下载个文件，它首 先以文件名或者关键字生成一个查询，并把这个查询发送给与它相连的所有计算 机，这些计算机如果存在这个文件，则与查询的机器建立连接，如果不存在这个 文件，则继续在自己相邻的计算机之间转发这个查询，直到找到文件为止。为了 控制搜索消息不至于永远这样传递下去，一般通过1 t lf n m et ol i v e ) 的减值来 控制查询的深度。初始时给t t l 一个 l o j , 的值，如果在1 t l 减为0 ，还没有擅 索到资源，则给1 t l 重新赋更高的值。这种策略可以减少搜索的半径，由此可 见，洪泛法的路径覆盖范围是一个以t 1 l 为半径的圆，而且网络开销随着跳数 一鋈 譬 瞧“妒。， 北京化丁人学颀：f ：学位论文 限制t t l 的增加而指数增加，如图2 2 所示，因此查询范围不可能很大，这也 就造成了，系统中存在某文件，但却查询不到的情况。这种局限性也是无结构 p 2 p 网络的本质缺陷【1 6 1 1 】。 在后期的无结构p 2 p 网络为了避免这种缺陷，采用了一种新的称谓随即走 ( r a n d o mw a l k ) 的路由方法。它指的是结点收到查询消息时只随即选择一个邻 居结点发送该消息，直到数据被找到或者t t l 到限制。随即走方法比洪泛法最 大的优势在于网络开销随着跳数增加而线形增加，因此t t l 可以设的非常大， 所以也就能达到更大的范围。 除此之外，还有扩展缓，选择转发和超结点路由等后期方法，但都由于没有 确定拓扑结构的支持，非结构化网络无法保证资源发现的效率。即使需要查找的 目的结点存在发现也有可能失败。由于采用t t l ( t i m e t o l i v e ) 、洪泛( f l o o d i n g ) 、 随机漫步或有选择转发算法，因此直径不可控，可扩展性较差【1 7 18 1 。 因此发现的准确性和可扩展性是非结构化网络面临的两个重要问题。目前对 此类结构的研究主要集中于改进发现算法和复制策略以提高发现的准确率和性 能。 2 1 1 3 第三阶段，结构化p 2 p 网络 所有的结构化p 2 p 网络都使用分布是散列表( d h t ) 来将结点、数据对象 影射到覆盖网中。分布式散列表实际上是一个由广域范围大量结点共同维护的巨 大散列表。散列表被分割成不连续的块，每个结点被分配给一个属于自己的散列 块，并成为这个散列块的管理者。d h t 的结点既是动态的结点数量也是巨大的， 因此非中心化和原子自组织成为两个设计的重要目标。通过加密散列函数( 比如 s h a - 1 ) ，一个对象的名字或关键词被映射为1 2 8 位或1 6 0 位的散列值 1 3 l 。 最近的研究集中在采用新的拓扑图构建重叠路由网络，以减少路由表容量和 路由延时。这些新的拓扑关系的基本原理是在d h t 表一维空间的基础上引入更 多的拓扑结构图来反映底层网络的结构。 d h t 类结构能够自适应结点的动态加退出，有着良好的可扩展性、鲁棒 性、结点d 分配的均匀性和自组织能力。由于重叠网络采用了确定性拓扑结构， d h t 可以提供精确的发现。只要目的结点存在于网络中d h t 总能发现它，发现 的准确性得到了保证，最经典的案例是t a p e s t r y ，c h o r d ，c a n ，和p a s t r y ”j 。 ，t a p e s t r y 提供了一个分布式容错查找和路由基础平台，在此平台基础之上， 可以开发各种p 2 p 应用( o c e a n s t o r e 即是此平台上的一个应用【2 0 1 ) 。t a p e s t r y 的思 想来源于p 1 a x t o n 【2 1 1 。在p l a x t o n 中，结点使用自己所知道的邻近结点表，按照目 i o 第二章理论基础j 相关技术 的i d 来逐步传递消息。t a p e s t r y 基于p l a x t o n 的思想，加入了容错机制，从而可 适应p 2 p 的动态变化的特点。o c e a n s t o r e 是以t a p e s t r y 为路由和查找基础设施的 p 2 p 平台。它是一个适合于全球数据存储的p 2 p 应用系统。任何用户均可以加入 o c e a n s t o r e 系统，或者共享自己的存储空间，或者使用该系统中的资源。通过使 用复制和缓存技术，o c e a n s t o r e 可提高查找的效率【2 2 1 。最近，t a p e s t r y 为适应p 2 p 网络的动态特性，作了很多改进【2 3 1 ，增加了额外的机制实现了网络的软状态( s o f t s t a t e ) ，并提供了自组织、鲁棒性、可扩展性和动态适应性，当网络高负载且有 失效结点时候性能有限降低，消除了对全局信息的依赖、根结点易失效和弹性差 的问题。 p a s t r y 是微软研究院提出的可扩展的分布式对象定位和路由协议，可用于构 建大规模的p 2 p 系统。如图3 所示，在p a s t r y 中，每个结点分配一个1 2 8 位的 结点标识符号( n o d e l d ) ，所有的结点标识符形成了一个环形的n o d e l d 空间，范 围从0 到2 1 2 8 1 ，结点加入系统时通过散列结点p 地址在1 2 8 位n o d e l d 空间 中随机分配。如图2 3 图2 - 3 p a s t r y 结构图 c h o r d 项目诞生于美国的麻省理工学院【2 4 】。它的目标是提供一个适合于p 2 p 环境的分布式资源发现服务，它通过使用d h t 技术使得发现指定对象只需要维 护o ( 1 0 9 n ) 长度的路由表。在d h t 技术中，网络结点按照一定的方式分配一个 唯一结点标识符( n o d ei d ) ，资源对象通过散列运算产生一个唯一的资源标识符 ( o b j e c ti d ) ，且该资源将存储在结点d 与之相等或者相近的结点上，如图2 4 。 需要查找该资源时，采用同样的方法可定位到存储该资源的结点。因此，c h o r d 的主要贡献是提出了一个分布式查找协议，该协议可将指定的关键字( k e y ) 映射 到对应的结点( n o d e ) 。从算法来看，c h o r d 是相容散列算法的变体。 北京化工人学硕十学位论文 图2 - 4 c h o r d 结构图 d h t 这类结构最大的问题是d h t 的维护机制较为复杂，尤其是结点频繁加 入退出造成的网络波动( c h u m ) 会极大增加d h t 的维护代价。d h t 所面临的 另外一个问题是d h t 仅支持精确关键词匹配查询，无法支持内容语义等复杂查 询【2 5 】【2 6 1 。 2 1 2p 2 p 研究现状 2 1 2 1 小世界模型 “s m a l lw o r l d 原先是社会学中一个重要概念，描述了任何两个人最少需要通 过几个中间人来取得联系。上世纪6 0 年代，美国的社会学家s t a n l e ym i l g r a m 和 他的同事做了一个试验。在美国任意两个洲中，任意挑选了若干对人，然后让这 些彼此互不认识的人，通过各自的熟人进行物品的传递。试验的目的是为了了解 在这些彼此不认识的人之间需要多少环节才能把他们联系起来。但当时的实验结 果并不让人满意，即便如此，在成功的实验个例中还是基本上可以证实s m a l l w o r l d 现象的存在。经过一段时间的沉寂，直到上世纪9 0 年代，美国哥伦比亚大 学的w a r s 利用i n t e m e t 的e m a i l 系统重新进行实验，这次实验的结果是 令人满意的，每封邮件从发送人到接收入，中间只需要5 6 个人转发就可以了。 这次实验证明了“六度分离”这个结论1 2 列。 这个结论所揭示出的网络特点是这样的。从本质上说，小世界模型网络是具 有一定随机性的一维规则网络。小世界模型中定义了两个特征值：( 1 ) 特征路径 的平均长度l ：它是指能使网络中各个结点相连的最少边长度的平均数，即小世 界网络的平均距离；( 2 ) 聚类系数c ：表示近邻结点联系紧密程度的参数。小世 界网络模型有如下特点：网络结点的连接度比较均匀，每个结点的连接度近似相 等；网络的分离度都很小，任意两个结点之间建立连接的长度都很小。以较小的 1 2 第二章理论基础0 相关技术 概率p 在网络中将少量边“断键重连”，或直接加入少量捷径时网络的基本结构保 持不变，而结点问的特征路径长度下降很快【2 引。该网络同时具有较短的特征路径 长度和较大的聚合系数，因此可以减少网络的平均路径长度和网络的通信开销。 这类网络中大多数结点的连接度都不大，只有少数结点的连接度很高，可以将这 些少数结点看成中心结点。这样的结点一般连接不同的区域，是重要结点( 或称 关键结点) ，起着簇头的作用。它们使网络通信范围更广，可用资源更丰富查询 和搜索效率更赢b a r a b a s i 和a l b e r t 等人研究发现结点的连接具有偏好依附的特 性。因此，网络规模随着新结点的加入而增大，但新加入的结点偏向于连接到已 存在的具有较大连接度的结点上去【2 8 1 。大量研究证明了以n a p s t e r ，g n u t e l l a 为 代表的p 2 p 网络符合s m a l lw o r l d 特征，也就是网络中存在大量高连通结尉1 3 j 。 2 1 2 2 热点问题 热点问题由来已久，比如一家普通的书店最好的一万本书里有半数每季度卖 不出一本。沃尔玛最好的一万张c d 中有半数每季度一张都卖不掉，事实上，沃 尔玛甚至不会存储这么多的c d ，e c a s t e 公司的c e ov a n n - a d i b e 做过统计，实际 上5 0 这个数字都是非常乐观的，真正能保持销量的产品总占所有产品类别的 2 ，换句话说，沃尔玛9 8 的c d 在一个季度内都卖不出一张。热点问题是供 给资源匮乏的产物如果只有那么几个货架、几个波段，唯一明智的做法就是 把这点空间留给那些最热门的东西【2 9 1 。针对这个结果，任意一家沃尔玛里，最好 的位置上永远摆放的是大热门的c d ，而不是品味独特的小资音乐。 放到网络中，热点问题描述了某个网络资源在一段时间内，对它的获取请 求发生了不可预料的、大量的、快速的增长，这种突然爆发的流行性导致网络某 个结点造成难以应付的拥挤。因为在p 2 p 网络中，并不是所有的用户都能够保持 连续的资源共享，所以真正能够为系统服务的结点永远是少数结点。于是，为了 保证资源的可用性，就必须在一定范围之内解决热点问题。 解决热点问题的方法是“复制”或者“缓存”。结构化p 2 p 网络中，保存该数据 对象的结点将它复制到n o d e l d 临近的结点，同时对获取请求做重定向，告诉获 取请求到邻近的结点去拿副本。无结构的p 2 p 网络通常将数据对象复制或缓存到 邻居结点，由于获取请求常常先到达邻居结点，所以在那时就可以发现并直接传 送副本给需要的用户，根本不用再往前走，也就谈不上重定向了。 2 1 3 典型的p 2 p 应用 1 3 北京化- t 人学硕一 ：学位论文 1 b i b t 全称“b i t t o r r e n t ”，是一款开放源代码的下载工到3 0 j 。从字面上看是“比特 流”的意思。b t 之所以流行是因为它体现了p 2 p 文件交换系统的一个重要特征， 就是参与的用户越多那么下载的速度就越快。由于其在下载上的优势导致其用户 群的急剧增加。传统的下载模式如：f t p 、h 1 v r p 都是采用了客户端朋艮务器的模式， 用户从中央服务器上下载所需要的文件。这样所有的服务都要由中央服务器来完 成，无论中央服务器的硬件设备配置多么好，由于服务器端的出口带宽总是有一 定的限制，所以总会有用户人数的限制，就是说只能为少数用户服务。当用户增 多的时候就会出现服务性能下降或者无法登录服务器的现象。人数越多服务性能 就越差是传统模式的特点，而采用p 2 p 模式的b t 下载则恰好相反，人数越多下 载速度越恻3 l j 。首先b t 将文件分割成n 份，并制作相应的文件来标识数据块儿。 假设有l o 个人要下载这个文件，并非所有的结点都到存有文件的结点上去从头 下载。而是分工协作，比如：甲下载文件的1 、2 两个数据块，乙下载3 、4 ，丙下 载5 、6 ，依次类推，然后各个下载结点之间再相互交换已经下载的数据块。采 用这种方式，各个结点在下载文件的同