（计算机软件与理论专业论文）异构环境下基于dht的p2p应用的研究与设计.pdf

摘要 利用快速发展的刚络技术实现信息资源的高效利用，其可行性及迫切性已经 被广泛认同。p 2 p 技术作为一个新的研究领域，具有广阔的应用前景。现有的p 2 p 应用系统并没有充分发挥其眭能。d h t 结构( 分布式哈西表，d j s t r i b u t e dh a s h t a b l e ) 具有较高的可靠性利可扩展性，可以为大量的应用提供支持。但是同前 d h t 的实际应用并没有如预期般广泛。将大规模、高度动态、高度异构的各种汁 算节点组织到一起，提供高可扩展性、高有效性、高性能的互助服务是p 2 p 技术 研究的基础课题，而如何在实际的网络环境下构建出高效的应用系统是一个具有 挑战性的问题。本文对上述问题进行了深入的研究，主要内容及创新点如下： 1 ) 奉文对现有p 2 p 系统的测量数据归纳总结，论述了极端异构性是p 2 p 网络的 根本特征，并指出异构性对系统性能潜在的影响，充分利用异构性可提高系 统的性能。 2 ) 充分考虑了p 2 p 网络异构性的存在本文设计了一个基于d h t 的通用p 2 p 应 用程序基础框架，尽可能简化上层戍用的开发难度，以期推进d h t 的应用开 发。由于采用分层次设计，该基础框架具有良好扩展性和通用性，可兼容各 种d h t 算法。 3 ) 结合传统的数据复制技术，在充分考虑p 2 p 网络的异构性前提下，本文还设 汁了一种自组织的文档存储策略和一种结合节点综合性能的自适应的最多请 求者与最近最少访问相结合的复制策略。这两种策略结合使用，能够保证文 档存储的可靠性、共享信息的高效可用性并可自动调整网络的负载平衡状 况，保证网络的可扩展性和稳定性。 相信这些研究工作将对p 2 p 技术的大规模实际应用产生积极的影响。 关键词：d h t ，异构性，应用程序基础框架，存储复制策略 a b s t r a c t i th a sb e e nb r o a d l ya c c e p t e dt h a ti ti sp o s s i b l ea n du r g e n tt ou t i l i z et h ei n f o r m a t i o n e f f i c i e n t l yb y f a s t d e v e l o p e dn e t w o r kt e c h n i q u e ，a sah o v e lr e s e a r c hf i e l d 。p 2 p t e c h n o l o g yh a sw i d ep r o s p e c tf o ra p p l i c a t i o nh o w e v e r , t h ec u r r e n tp 2 pa p p l i c a t i o n s y s t e m sh a v en o tf u l l yd e m o n s t r a t e dt h e i rc a p a b i l i t i e s d h t ( d i s t r i b u t e dh a s ht a b l e ) w h i c hh a sh i g hr e l i a b i l i t ya n de x p a n s i b i l i t y , c a ns u p p o r ta b u n d a n ta p p l i c a t i o n w h e r e a s ， p r e s e n ta p p l i c a t i o no fd h t i sn o ta sb r o a da se x p e c t e d t h ef u n d a m e n t a li s s u eo fp 2 p t e c h n o l o g yi s t oc o m b i n ev a r i o u sm a s s i v e ，h i g h l yd y n a m i ca n dh i g h l yh e t e r o g e n e o u s c o m p u t a t i o nn o d e s ，a n dt op r o v i d eh i g h l ys c a l a b l e ，m o r ee f f i c i e n ta n dh i g h l yc a p a b l e s e l f - h e l ps e r v i c e a n di t i sam o r ec h a l l e n g i n gp r o b l e mh o wt oc o n s t r u c te 币c i e n t a p p l i c a t i o ns y s t e mu n d e rc u r r e n tn e t w o r k 1 nt h i st h e s i s ，q u e s t i o n sm e n t i o n e da b o v e a r ed e e p l ys t u d i e d ，a n dm a i nc o n t e n t sa n dc r e a t i r ew o r k sa r ea sf o l l o w s ： w ec o n c l u d e da n ds u m m a r i z e dm e a s u r ed a t u mo fc u r r e n tp 2 ps y s t e m s ，a n de x p a t i a t e d t h a tt h eb a s i cp r o p e r t yo fp 2 pn e t w o r ki se x t r e m eh e t e r o g e n e i t y m e a n w h i l e ，w e p o i n t e do u tt h a th e t e r o g e n e i t y , w h i c hc o u l di m p r o v et h ep e r f o r m a n c eo fs y s t e m ，h a s p o t e n t i a li n f l u e n c eo n t h ec a p a b i l i t yo f s y s t e m c o n s i d e r i n gt h ee x i s t e n c eo f h e t e r o g e n e i t yo f p 2 pn e t w o r k ，w ed e s i g n e daf u n d a m e n t a l f r a m e w o r ko f g e n e r a lp 2 pa p p l i c a t i o nt os i m p l i f yt h ed i f f i c u l t i e so f d e v e l o p m e n ti nt o p a p p l i c a t i o nw i t he x p e c tt op r o m o t et h ed e v e l o p m e n to fd h t b e c a u s eo f t h ed e s i g no f d e l a m i n a t i o n ，t h i sf t l n d a m e n t a lf r a m e w o r ki ss c a l a b l ea n dg e n e r a l ，w h i c hi sc o m p a t i b l e w i t ha l lk i n d so fd h t a l g o r i t h m s w i t hc o n s i d e r a t i o no fh e t e r o g e n e i t yo fp 2 pn e t w o r k ，w ed e s i g n e das e l f - o r g a n i z e dd a t a s t o r a g es t r a t e g y a n da n a d a p t i v er e p l i c a t es t r a t e g y w h i c hc o m b i n e s i n t e g r a t e d p e r f o r m a n c eo fn o d e sa n di nw h i c ht h em a x i m u ma p p l i c a n t sa r ec o m b i n e dw i t ht h e l a t e s tm i n i m u ma c c e s s ，c o m b i n gt h et w os t r a t e g i e s ，w ec a ng u a r a n t e er e l i a b i l i t yo f d a t as t o r a g ea n dh i g h l ) ，u s a b i l i t yo fs h a r e dd a t a m e a n w h i l e ，w ec a na u t o r e g u l a t et h e 1 0 a db a l a n c eo fn e t w o r ka n de n s u r ei t se x p a n s i b i l i t ya n ds t a b i l i t y i ti sb e l i e v e dt h a tr e s e a r c ho np 2 pt e c h n o l o g yh a sap o s i t i v ei m p a c to ni t sl a r g e s c a l e p r a c t i c a la p p l i c a t i o n k e yw o r d s ：d h t , h e t e r o g e n e i t y , a p p l i c a t i o nf u n d a m e n t a lf r a m e w o r k ，s t o r a g e r e p l i c a t es t r a t e g y i i 1 1p 2 p 技术背景 第一鼋绪，q 第一章绪论 1 1 1计算模式的演变 计算机处理能力的增强和价格的降低使得计算机得以广泛普及。然而，汁算 机的使用效率极低，如何有效利用这些计算资源成为一个热点问题。与此同时， 计算速度每f 1 八个月翻一番，网络速度每九个月翻一番，差不多每五年差一个数 量级”1 。利用快速发展的网络技术将各种计算资源整合到一起，从而实现高性能 的分布计算和资源的高效利用，其可行性及迫切性已经被广泛认同。伴随着计算 机性能及网络速度的快速增长，计算模式的演变了经历了三个阶段： 1 ) 主从式训算模式 从计算机网络的诞生到上个世纪八| 年代，计算机的价格昂贵且功能相对较 弱。这种客观条件决定了主从模式的产生。在主从模式下，终端没有处理能力， 只能用于输入数据和显示信息。用户为了对数据进行处理，必须和主机相互交 互。为了尽可能地使用这种昂贵的计算机，一般采用多个作业集中到一台计算机 上的集中处理方式，从而使主机系统资源得到最大的利用。该模式的缺点是： 主机负载过重，系统的可靠性与可用性主要依赖于主机的能力： 主机价格过于昂贵，不利于；1 1 算机技术的普及； 系统的扩展性差，功能扩展困难： 系统安全性差，存在潜在的单点故障威胁。 2 )客，1 机服务器计算模式 大中型计算机价格昂贵，而微型汁算机的性能在逐步提高同时其价格在不 断降低，冈此人们越来越希望用廉价的微型汁算机代替大中型计算机系统，让用 户的任务在不同的计算机上分布进行并统一管理。上世纪七八十年代，客户机 服务器模式“1 ( c i l e n t s e r v e r ，c s ) 开始发展。在这种模式中，系统分成两大 部分客户机和服务器。c s 的基本工作方式是客户机发出请求，服务器接受 请求并进行分析处理，然后将处理结果返回给客户机。从上世纪九十年代开始， 第一章绪论 客j 1 机服务器模式开始流行日前该汁算模式已经是市场上的主流。该模式包 括客户机文件服务器、双层c s 、多层c s 、以及浏览器服务器 ( b r o w s e s e r v e r ，b s ) 等几种类别。在客户机服务器模中，客户机_ ；再像 主从模式里的客户终端那样没有处理能力，客户机已具备一定的计算能力，但主 要的1 二作还是依赖于服务器来完成。由于客户机服务器模式将任务分布在多台 机器上并行执行，冈此使用该模式的系统具有更好的性能。 虽然客广机服务器模式克服了主从模式的设备成本高等缺点，但仍存在以 下缺点： 由于在c s 模c 下，客户机提交请求，服务器同时为多台客户机提供服务并 处理客广机的清求，因此服务器仍然是系统的性能瓶颈： 可扩展性差：服务器的处理能力决定了系统的最大工作负载，而服务器的处 理能力很难有效扩展： 容错性差：服务器容易成为单点故障； 缺乏灵活性：用于客户机和服务器通信的协议是硬编码的：客广机和服务器 之间的角色分配在设计时就已经决定，不能灵活更改；系统的功能很难扩展 和升级。 3 )对等( p e e r t o - p e e r ，p 2 p ) 计算模式 随着汁算机处理能力的进一步增强，当前市场上任一台新生产的计算机都可 做为服务器。在这样的背景下。计算模式从客户机服务器模式逐步演变到对等 计算模式“。p 2 p 网络目前还没有一个明确的定义，其中的每个节点不是严格的 划分为客户机或服务器。p 2 p 剐络中的每个节点既是客户机，又是服务器，还是 路由器。这些节点因为互为服务而共存。而不是依赖于特定的集中式机制。并 且，各个节点可以直接交互并可能随时离开p 2 p 剐络。 d m o o r e 和j h e b e l e r 中对p 2 p 的定性描述“1 充分说明了p 2 p 技术的特 点。其描述如下： p 2 p 彳i 是静态的，而是动态的交换实时信息和能力( c a p a b i l i t y ) ； p 2 p 是双汹的交换； p 2 p 再现了最终的信息定甸和存储： p 2 p 可以提供计算资源作为服务； p 2 p 是直接的信息和服务的交换： 2 p 2 p 中生产者和消费者的角色是小同定的； p 2 p 是结果而4 ；是刚络。 p 2 p 州络中的节点也具有鲜明的特点，可慨括为以下几点： 节点的平等性：实际上由于节点的高度异构性，完全的节点平等性是做不到的， 但是如果抹杀了节点的平等性也就抹杀了p 2 p 州络的存在基础： 节点数量极大：理想的p 2 p 嘲络是数百万甚至数t 万个节点的规模： 节点的高度动态性：节点频繁地加入退出： 节点的高度异构性：容许p 2 p 中的节点在带宽、延迟、有效性等方面存在3 5 个数量级的差异； 节点自治和不可信任。 事实上，除了节点角色的互换性，p 2 p 模型和c s 模型之问并不存在非常明 显的界限。 1 1 2p 2 p 网络的分类及比较 现有的对等嘲络可如下图所示进行分类 1 ) 集中索引服务器结构 集中索引服务器结构中，客户荫先将所要发布内容的元数据提交到服务器上， 由服务器来维护一个用户 数据的索引数据库。用户查找数据时，首先f 艮服务器 连接，找到感兴趣的内容所在的客户机器，再跟这个客户机直接连接交换数据。 事实上，集中索引服务器的模式并不是完全的p 2 p 应用，它是一种混合模式 的产物。它的优点是数据的定位准确、快速，管理简单：缺点是索引服务器的存 在使之成为系统瓶颈和攻击目标( 单点故障) ，可扩展性差，容易引起法律问题( 版 ，珥北j 业入学帧十学f 旺 c 史 第一誊绪论 权问题) ，且数据存放在个人机器上，不适用于刚络存储的应用。曾经风靡全球的 n a p s _ c e r 采用的就是集中索引服务嚣结构。 2 ) 松散的全分布式结构 该结构摈弃了集中索引服务器，节点本身既是客，l l 也是服务器( 被称为 s e r v e n t ) ，节点间的逻辑拓扑关系和数锯的放置方式都没有严格而精确的控制， 因而只能采用泛洪式广播方式来定位数据。 这类系统由于使用了纯分布式的结构避免了传统的c s 结构的弊端，具有容 错性好，支持模糊查询，查询命中率也较高等优点。但是，随着系统规模的增大 泛洪式查找的弊端就会凸现出来：带宽消耗将会导致低带宽的节点无法加入到系 统中，也就意味着系统可扩展性变差。另外，这种查询方式的查询结果可能是不 完全的，每次查询的结果也都不尽相同，甚至可能在数据存在的情况下查询失败， 并且查询速度较慢。g n u t e l l a ”j 系统采用的就是松散的全分布式结构。 3 ) 层次结构 层次结构是介于集中式和纯分布式之间的一种拓扑结构，以f a s t t r a c k 为代 表，是目前较为流行的一类结构。系统自动选择性能较高的节点作为s u p e r - p e e r ， 其他的节点寻找离自身较近的s u p e r p e e r ，将自己的资源发布到这个s u p e r p e e r 上，查询只在s u p e r - p e e r 之间进行，并且采用泛洪式的广播方式。层次结构的优 点是性能及可扩展性都较好，带宽消耗也比g n u t e l l a 一类的纯分布式系统要小的 多。但是该结构对s u p e r - p e e r 的依赖性较大，易于引起攻击，容错性也受限制。 4 ) 结构化的纯分布式结构 结构化的纯分布式结构是第二代p 2 p 网络普遍使用的结构，主要是基于分布 式哈西表( d h t ) 的拓扑结构。结构化p 2 p 刚络的数据放置与刚络拓扑结构相关， 结构化p 2 p 刚络能保证路由的有效进行。 d h t 对p 2 p 技术的影响是深远的。从2 0 0 1 年到r 前，已经出现了若干种分布 式哈西表的结构，如c a n ”3 、t a p e s t r y 、p a s t r y ”1 、c h o r d ”、v i c e r o y “、g l y e s s 、 k a d e m l i a l 及北京大学的燕星系统“等。分布式哈西表使得p 2 p 技术的应用范围大 大扩展，彳i 再局限于文件共享系统，可以成为一个基础构架( i n f r a s t r u c t u r e ) ， 用于构建分布式文件系统、分布式数据库以及其他多种更为有用的应用。 d h t 方法的核心内容是将数据文件通过哈西算法生成一个k e y 值，而每个节点 都被赋予一个与位n n 关自勺- - 个唯一标示n o d e l d ，将文件的k e y 值通过特定的算 4 埘，tj ：业，莩硕 1 学位论上 第章绪论 法与n o d e l d 建立关联也就是数据的插入和查找算法。 尽管d h t 方法的拓扑结构决定r 它难以支持模糊查询，但由于其查找具有确 定性、简单性、高效率等特点，再加上d h t 本身的分布性、鲁棒性、良好的可扩 展性、可靠性利自组织性等优点，d h t 正越来越成为研究和应用的焦点。 1 1 3p 2 p 网络的现有应用 p 2 p 计算技术引导网络应用模式从集中式向分布式偏移，即嗍络应用的核心从 中央服务器向网络边缘的终端设备扩散。目前p 2 p 被广泛应用于各个领域，如信 息资源共享、普及计算、协同工作、实时通信、信息检索、广域网存储系统等。 1 ) 信息资源共享 信息资源共享一直是网络技术发展的重要推动力，也是p 2 p 技术最i l 型的应 用。目前信息资源共享主要通过w e b 技术实现。在以w e b 的方j = l = 共事信息资源时， w e b 服务器需要对大量用户的访问提供有效的服务，因此w e b 服务器常成为这类 系统的性能瓶颈。n a p s t e r 是提供给用户在鱼联网上共享m p 3 音乐文件的p 2 p 应 用。与传统的音乐共享技术不同的是，n a p s t e r 把音乐文件存储在客户节点上而 不是存储在中央服务器上。服务器存储的仅仅是文件的索引信息，用户之间可以 直接共享和传输音乐文件而不需要通过中央服务器。采用这种方式共享信息资源 可以充分地利用网络的带宽资源。目前基于p 2 p 文件共享的研究项目主要有 f r e e n e t 1 、g n u t e l l a ，f r e eh a v e n ”、o h a h a ”等。目前流行的下载工具 b i t t o r r e n t 、e d o n k e y 等也都采用了p 2 p 技术。 2 ) 普及计算 普及训算技术研究的是如何充分利用网络中的计算单元来共同完成大规模的 计算任务。由于单一计算单元的计算能力有限，因此采用并行技术、分布式技术 将多个计算单元联合起来共同完成大规模计算任务。同时，刚络中汁算机的使用 效率极低，人们期单能够充分利用网络中的闲散计算能力来完成大规模的计算任 务。p 2 p 计算技术则为普及计算的发展提供了新的机遇。普及计算研究的典型代 表有s e i t o h o m e i 、g r i d 1 和i b m 的自组织计算计划“。 3 ) 协同工作 协同工作是指多个用户之间利用网络中的协同计算平台互相协同来共同完成 汁算任务。训算机辅助协同t 作c s c w ”“是协同t 作的典型研究方向之一。传统的 5 第一蕈绪论 c s c w 技术存在单点故障和胜能瓶颈问题。由于1 i 依赖于中央服务器基于p 2 p 的 协同 _ 作技术有更好的鲁棒性和可扩展性。g r o o v e ”是基于i n t e r n e t 的p 2 p 协同 应用软件的典型代表，其用户可以直接进行实时的协同工作。 4 ) 实时通信 实时通信技术是p 2 p 网络的重要应用之。目前的实时通信技术大多采用中 ，c , 月1 4 务器认证用户的基本信息，节点之间直接进行数据通信的方式，例如i c q 、 0 c o 、a i m 等。j a b b e r ”是一个开放源码的实时通信平台，它提出了个在不兼 容的箨种实时通信平台之间通过x m l 投术进行信息交换的协议。而目前流行的 s k y p e 也是一个基于上述技术的实时通信软件。 j ) 信息检索 搜索引擎是目前人们在刚络中搜索信息资源的主要 t 具。目前的搜索引擎如 g o o g t e 、y a h o o 等都是集中式的。这种信息搜索方式是一种被动的搜索方式，用 户z i 能主动将自己的信息发布到搜索引擎上，也不能够保持搜索引擎所采集数据 的实h 寸性。j x t as e a r c h “1 通过p 2 p 的搜索技术提高数据访问的有效性以及检索的 效率。 6 ) 广域网络存储系统 分布式文件系统是广泛使用的分布式文件存储技术。典型的分布式文件系统 包括n f s ”“、a f s ”“、c o d a ”等。随着网络规模的扩大，面向i n t e r n e t 的广域网 络存储系统日益受到重视。典型的系统包括o c e a n s t o r e “和c f s 等。这些项日 的目标都是提供面向全球的文件存储服务。 1 1 4p 2 p 网络的研究方向 目前，p 2 p 技术的研究热点主要集中在以下几个方面： 1 ) p 2 p 覆盖网络：主要研究拓扑结构、路由效率等问题，目前主要集中于d h t 的 相关研究。 2 ) p 2 p 资源及数据管理：在p 2 p 的世界，资源是由_ i 同的主体所拥有，这就涉及 到资源交换的相关问题。怎样让这种交换安全、用广透明且用户可定制，是这 个方面的主要研究课题。 3 ) p 2 p 网络的安全性：主要研究课题为系统对抗恶意攻击的能力，系统对抗授权 侵入的能力，以及p 2 p 刚络中的信任关系问题。 6 ，! ! 些垒兰塑兰! ! ! 兰苎； 第一苹绪沦 4 ) p 2 pl 嘲络中的匿名性：为了避免法律上的麻烦和保护隐私等原冈，匿名性也成 为一个研究热点，f r e eh a v e n 和f r e e n e t 便是这个方i 柚上的代表成果。 5 ) p 2 pl 蹦络中的负载均衡：在大规模的系统中节点的极端异构性是其自然的特性， 负载均衡也是关系到p 2 p 能否运用到实际中的一项重要技术。 1 2 本文的研究工作 1 2 1 研究的意义 随着 l 算机嘲络技术的发展，以及人们对计。算能力需求的4 i 断增强，分布式 技术得到长足的发展。分布式技术的优点是可扩展性好、容错性好、易于构造高 性价比的系统，并且克服了集中式技术的单点故障、扩展性差的缺点。但为此需 付出系统的复杂性和可管理性的代价。 但是，相对于单点故障和简单的可管理性而言，人们更看重系统的可用性和 抗攻击性。同时，及时准确地查询网络信息、平衡网络流量、客户系统资源的有 效利用、永久存储等需求被提出，并迫切需要被解决。传统的集中式技术无法很 好的满足，甚至f i 能满足上述需求。随着n a p s t e r 的兴起，p 2 p 技术成为研究的 热点。 在p 2 p 模型中，没有专门的服务器，冈此d d o s 攻击失去了日标；高效新颖的 查询方式，为及时准确地查询提供了可能：精心设计的覆盖网络结构将有助于解 决嘲络负载失衡的问题；大量地理分散的资源通过p 2 p 系统聚集起来，为永久存 储提供了存储容量，通过一定的机制可保证一定的可靠性，同时也提供了一种利 用闲散资源的新途径。更重要的是p 2 p 系统中每个节点都可以是服务器，人们 可以方便地把自己的信息发布到网上，供更多的人共享。 正是由于以上各种优点，p 2 p 技术具有强大的生命力。而d h t 由于具有查找 可确定性、简单性、高效率，网络的分布性、鲁棒性、良好的可扩展性、可靠性 币u 自组织性等优点，正越来越成为研究和应用的焦点。 1 2 2 研究的内容和成果 本文的研究t 作主要围绕以下三个方面展开： 1 ) 大规模p 2 p 系统中异构性的存在及其对系统的影响 7 【，q 北i 业人学硕f 学n 论上 第一蕈绪论 奉文通过列实际p 2 p 刚络进行测量得到的数据进行分析归纳，得出如下结论： 异构性是大规模p 2 p 系统中小可忽视的晕要冈素。在应用p 2 p 技术时，若忽略这 种异构性，会对p 2 p 系统的性能产生严重的影响。并据此提出本文的研究前提。 2 ) 设计了个基于分布式哈西表( n i t ) 的对象存储麻用框架 p 2 p 技术作为一个热门的研究领域，具有广阔的应用前景。d h t 结构具有较高 的可靠性和可扩展性，可以为大量的麻用提供支持。但是目前基于d h t 的应用系 统都是基于单一的d h t ，没有通用的应用基础框架，在一定程度上影响了d h t 的 大规模应用。本文结合对象存储技术，构建了一个基于d h t 的通用应用程序基础 框架，并对各层的功能和主要接口进行了详细的分析设汁。 3 ) 设计了种充分考虑异构性的数据存储复制策略 从i = t 前的应用来看，p 2 p 的威力还主要体现在大范围的信息共享、检索的优 势上。而这些应用与数据存储复制技术是息息相关的。但是目前现有的数据存储 复制技术并没有充分考虑结构化嘲络的特性，冈而并1 i 能很好的适用于d h t 刚络。 本文充分考虑p 2 p 网络的异构性，提出了一套新的数据存储复制策略，并对比传 统的复制存储策略，对该策略的性能进行了简单评价。 1 3 本文的结构 本文共分为六章。章节的组织结构如下： 第一章介绍了课题的研究背景，从而引出了本文的研究意义、内容及成果。 第二章详细介绍了相关研究的前期工作情况，提出有待改进的研究环节，以 更明确本文的研究课题。 第三章通过对实际p 2 p 应用的测量数据进行分析、归纳，论述了大规模p 2 p 系统中异构性是的确存在，并会对系统的性能产生很大的影响。并由此提出奉文 的研究前提。 第四章构建了一个基于对象存储的通用分布式哈西表应用框架。 第五章论述了利用异构性所设计的数据存储复制策略，并对该策略进行了简 单评价。 第六章总结全文并指明未来的研究方向。 8 # + 章绪论 1 4 小结 本章首先从计算模式的演变、p 2 p 网络的分类、现有应用、研究方向四个方 面介绍了p 2 p 技术的背景，而后从奉文的研究意义、研究内容和成果两个方面阐 明了本文的1 二作。最后简要说明了本文的组织结构。 9 第- 二章莉朝研宄| 怍隋况简介 第二章前期研究工作情况简介 日前计算机界在p 2 p 领域的研究处于繁盛阶段，但基于p 2 p 技术的应用系统 却仍处于探索阶段。虽然有部分产品问世，但其陛能都不足够好，仍不能满足用 户对p 2 p 应用系统的需要。p 2 p 技术在研究中的关键问题是如何能够设汁和实现 一种在p 2 p 的极端环境下( 规模巨大、高度动态、高度异构、节点自制和1 i 可信 任) 的健壮的可靠的分布式系统。奉文的研究就旨在为d h t 的实际应用做出贡献， 设计出一种在上述极端环境下通用的分布式应用程序框架。 事实上，奉文的研究t 作是在p 2 p 原型系统的研究成果上进行的。本章将简 单介绍p 2 p 原型系统的相关情况，并据此提出本文的研究课题点。 2 1p 2 p 原型系统的设计 p 2 p 原型系统是以满足嘲络存储的需求为日的而设汁的全分布式结构的p 2 p 应用系统框架。 2 1 1p 2 p 原型系统的功能分析 无论是对等计算还 是文件交换，它们都必须 首先实现文件、信息的存 储。p 2 p 技术可以充分利 用各种空闲的存储资源 和网络资源，在满足信息 分布式存储的条件下，提 供信息服务所需要的容 错、负载平衡、匿名服务、 安全服务等功能，实现网 络环境下的“普及存储系 统”。图二一l 是基于p 2 p 甲甲甲 攀簿避鬯骚 l 安全il 操作模式ii 可靠l 应用层 信息基础设施 一信息管理层 通信服务层 通信设施层 图一一l 暴：p 2 p 的信息的存储系统体系结构 1 0 # 一；，响期研究i 作情，简t - 技术的信息存储系统的体系结构。 通信设施层是通信平台。在p 2 p 通信设施中，设计人员所向- 临的最大挑战是 系统实体的动态性，即用户可能故意或者非故意突然离开p 2 p 系统，或者改变通 信群体。这种用户的不稳定性，使得p 2 p 通信设施的管理异常复杂。这种通信连 接的不稳定性，在基于p 2 p 的信息存储系统中，可通过路由和查找功能来补偿。 在分布式信息存储系统中，最核一1 5 的技术是信息的定位和用户请求消息的传 递。通信服务层要实现的功能包括通信对象发现以及这些对象之间的定位和路由。 对象发现可以是集中式也可以是分布式，甚全二者的综合。在p 2 p 系统中，发现 算法的设计受许多冈素的影响。定位算法和路由算法则主要考虑优化通信对象之 间的消息传递路径，使通信系统延迟最小，从而保证系统的服务质量。 信息管理层实际上是对文件的操作管理，包括读取和修改等常见操作。该层 向上层提供传统的文件系统应用程序编程接口( a p i ) ，因而容易开发满足各种需 求的信息资源基础设旃。 信启、基础设施层是奉系统非常重要的组成之一，它主要包括三个组件：安全 组建、操作模式组件利可靠性保证组件。在p 2 p 系统中，节点既是客户又是服务 器。但将标准的客户设备变为服务器设备将给系统带来很大的风险，因此，p 2 p 系统依赖安全管理机制来保证系统不被恶意用户访问和使用。从资源的角度来看， p 2 p 是资源集聚的平台：它允许各类资源( 文件、数据、音乐等) 分布的集聚在 p 2 p 系统的节点上，并允许其它节点荚享这些资源，同时，对这些资源的操作( 读 取和修改) ，则通过操作模型来决定。而可靠性则是p 2 p 中难以处理的问题。这 主要也是因为p 2 p 具有动态行为，解决该问题的常用方法之一是采用动态路由等 容错技术。本层将向应用层提供服务接口，因而可以在此基础上构建各种具体应 用程序。 应用层包括信息存储系统相关的工具、应用和服务等。对于不同的应用需求， 信息存储系统提供4 i 同的服务，并有相应的工具和应用来支持这些应用需求。常 见的应用包括读取、查找、修改、备份、恢复和消息服务等。 2 1 2p 2 p 原型系统的总体设计 该p 2 p 原型系统要实现一种全分布式结构的p 2 p 分布式存储系统的设计。结 构化全分布结构的p 2 p 分布存储系统中，节点间的逻辑拓扑关系是由算法严格控 1 1 第一童 i 期研究k 作隋况简介 制的，每个数据文件的放置也是由特定算法精确放鼍在特定节点上的。这种结构 通常都能保证系统中的数据一定能够被找到，节点间拓扑关系和数据位置的精确 控制可以使得数据查询较为容易并有较高的效率。结构化全分布式结构的典型例 子是分布式h a s h 表( d h t ) 类结构。该原型系统就设计采用了这种d h t 结构。 该原型系统被期望能够方便的实现多种网络组织结构及路由算法，并能进行 各种组织结构或路由算法之间的对比验征 块性，这样才能在实现不同的阻络组织结 构或路由算法时，小必对系统进行大的改 动，只需对相应的模块进行修改即可。根 据以上需求，该p 2 p 原型系统被设汁为 四层结构，如图二一2 所示。 n e t w o r ks t a g e 是四层结构中的最底 层，它对应于图二一1 中的通信设施层。 这一层与i p 刚络紧密结合，实现侦听网 络连接、数据通信功能。 p e e rs t a g e 被设计为通信服务层与信 故要求该原型系统必须具有很强的模 a p p d h t p e e rs t a g e n e t w o r ks t a g e 图二一2p 2 p 原型系统的总体设计框架 息管理层的结合。p e e rs t a g e 应该能够实现o v e r l a yn e t w o r k 的构建，并实现信息 的存储、查找等功能。这其中最重要的是实现路由算法，这关系到整个原型系统 的效率。 d h t 层对廊于图二一l 中的网络管理层，主要是为应用层提供两个接口： i n s e r t ( k e y ，d a t a ) $ hl o o k u p ( k e y ) 。 至于a p p 层，即为廊用层。在这一层用户可以实现分布式存储、分布式h 算 等多种应用功能。这一层的关键技术在于应用程序对信息的操作进行之前，用户 必须知道所需信息的k e y 值，依据此值才能让下面三层工作，否则系统无法实现 所要实现的功能。这一层的具体设计与实现要根据实际需要而进行。 在这种设计构架中，对于应用层而言，n e t w o r ks t a g e 与p e e rs t a g e 是不可见、 完全屏蔽的。当需要实现多种不同的网络组织结构或路由算法时，设计人员只需 要修改p e e rs t a g e 层即可。这就满足了“模块化”的要求，同时也保障了网络的 匿名性。 1 2 蛹北i 。业凡学矾十：! ! 论z 第一章6 口期刊宄【怍 奇h 简 2 1 3p 2 p 原型系统中有待研究的问题点 上述p 2 p 原型系统的总体设计中主要存在以下三方面问题有待进一步研究改 进。 1 没有充分考虑、利用p 2 p 系统的高度异构性。 p 2 p 技术研究中的关键问题是如何能够设计和实现一种在p 2 p 的极端环境下 的健壮的可靠的分布式系统，这种极端环境就是指节点规模巨大、高度动态、高 度异构、节点自制和0 i 可信任。但是本章所介绍的原型系统中并没有充分考虑高 度异构性这一特点，自然也没有在实际应用时充分利用这一特点来提高系统性能。 但是，高度异构性是p 2 p 系统中不可忽视的重要特性。因此，本文的工作将着重 于如何利用高度异构性这一特征来提高p 2 p 应用系统的性能。 2 总体设计层次过于笼统，通用性及扩展性不够好。 虽然该原型系统具有一定的模块性，但是总体的层次设计还是过于笼统，无 法直接应用于实际应用系统的开发。另外，该原型的扩展性也不够好，需要加以 改进，以适用于开发易扩展的应用系统。奉文在该原型系统的基础上，详细地设 计了一个基于d h t 的通用p 2 p 应用程序基础框架，并给出了层次间详细的外部接 口。 3 原型系统中缺乏对存储策略的研究。 该原型系统的设汁是以满足网络存储的需求为目的，但是在具体的研究过程 中并没有对存储策略的设计加以研究，这是个很大的缺憾。本文弥补了这一缺憾， 并充分考虑了p 2 p 系统的极端异构性，设计了一种自适应的存储策略。 2 2 简析b i t t o r r e n t 在这一节中，我们将分析一下日前非常流行的一个p 2 p 文件共享软件 b i t t o r r e n t ，以进一步说明本文中的研究t 作的必要性。 n a p s t e r 羊ug n u t e l l a 都各自实现了一个完整的文件共享系统，b i t t o r r e n t 与上述两者不同，其中最重要的一个区别是只针对某个文件提供共享机制。b t 的 索引机制很简单将索引文件在网上发布，而查询则需要第三方来支持，所以b t 的共享是非常松散的，动态性远远大于n a p s t e r 和g n u t e l l a 。另一个区别是由于 只是某个文件的共享，所队b t 很容易支持从多个其它结点同时下载文件，提高了 1 3 第二蕈时期研宄怍肯况简介 传输效率，这在n a p s t e r 和g n u t e l l a 是很难实现的。 b t 的最大问题在于稳定性，结点的行为的异构性大大影响了它的可用程度。 b t 在解决结点行为异构方面作了努力，即每个客户下载的同时也必须提供上传 ( 给别人做服务器) 。不管怎样，盯用广群越来越庞大。也许严格来说b t 就技术 来说难髓p 2 p 系统的大雅之堂，但是b t 的热闹程度却反映了p 2 p 系统的追求 资源共享。 从上述分析中我们可以史明确地看出，p 2 p 系统中节点的异构性对系统的性 能具有非常大的影响，在设汁实际的廊用系统时必须考虑节点的异构性。资源共 事是计算机研究领域不变的追求，而资源的安全存储是资源共享的保证，因此高 效的数据存储策略对于p 2 p 系统而言也是很重要的。 2 3 小结 本章对以网络存储的需求为基础对所要设计的原型系统的功能进行了简要的 介绍，也简要分析了h 前流行的p 2 p 文件共享软件b i t t o r r e n t 。本文此后的研究 工作是在此原型系统的基础上进行了改进。 1 4 ! ，；j 些丛兰j _ ! ! 兰堂坚：! 三兰 銎三至苎坐燮坚! 墨丝! 堕堂塑壁塑些 第三章大规模p 2 p 系统中的极端异构性 同前大规模的p 2 p 应用系统已有很多从曾经风靡一时的n a p s t e r 到 g n u t e l l a 、k a z a a 系统，到如今人尽皆知的b it t o r r e n t 系统都采用了p 2 p 技术， 它们都是非结构化的p 2 p 系统。已有很多研究者针对这些实际的p 2 p 应用系统进 行了大量的测量和分析t 作。本章通过对月前已有的这些非结构化系统测量数据 的分析、归纳，论述了大规模p 2 p 系统中，无沦是非结构化还是结构化的，极端 异构性是必然存在的。并同时指出这种异构性对系统所可能产生的影响。 3 1p 2 p 系统中的异构性 现在流行的p 2 p 文件共享系统有e d o n k e y e m u l e 、k a z a a 、b i t t o r r e n t 、 g n u t e ll a 、n a p s t e r ( 己于2 0 0 3 年正式关闭) 等。研究者针对这些系统进行了大 量的测量和分析，从中得到这样的结论：极端异构性是p 2 p 网络的霞要特征。这 种异构性存在于p 2 p 系统的各个方面，主要可归纳为以下两个方面：节点的异构 性、共享资源被请求频度的异构性。 3 1 1 节点性能的高度异构性 节点是p 2 p 网络的基础，节点的性能对p 2 p 系统的性能会产生至关熏要的影 响。通过对现有p 2 p 应用系统的测量发现，p 2 p 系统中的节点在汁算能力、网络 带宽、时间延迟、活动时间、s e s s i o n 时间、所提供的共享资源数目等性能方面 具有极端异构性。 3 1 1 1 节点运算能力异构性 就节点自身而言，运算能力是其重要的衡量因素之一。图三一l 和图三一2 是从 项目s e t i h o m e 的统汁数据“中得到的统讨结果。可以看到，运算能力超低的节 点的数日不多，随着运算能力的增加，节点数日呈上升趋势，到达一定的峰值后 开始下降，这个分布与z i p f 分布相吻合。 j 酉，l h 业凡学厢学似沦殳 慕一章、规模p 2 p 系统朐极端片构性 图二一l 节点的浮点运算能力分布 图三一2 节点的整数运算能力分布 l l u n b e ro pu s e r s h oh a + or e l u r n e jhr e m u l l 二s hr c o u c s 图三一3 返回了n 个运算结果的用户数量分布 事实上，在p 2 p 系统中节点所表现出的运算能力并不一定与其自身所具有的 运算能力相一致。节点所愿意贡献的运算能力事实上取决于用户所愿意共享的程 度。因此，节点返回的运算结果的分布图可以更准确的反映p 2 p 系统中节点的运 算性能。图三一3 是s e t i h o m e 对用户返回结果的数目分布1 0 9 l o g 曲线，它近似 于一条直线，符合z i p f 分布。并且，节点所返回的运算结果存在5 个数量级的差 异。因此节点的运算能力具有异构性。 3 1 1 2 网络带宽异构性 s a t o i u 等对n a p s t e r 进行了为期4 天的测量，同时对g n u t e l l a 进行了为期8 天的测量t 作，并在论文 2 8 中报告了所得到的相关测量数据。 图三一4 即为所得到的g n u t e ll a 节点的上传带宽和下载带宽的分布图。实际 上这里的带宽并不