（计算机科学与技术专业论文）p2p分布式存储系统副本策略研究.pdf

r e p l i c as t r a g e g y r e s e a r c hb a s e do np 2 pd i s t r i b u t e ds t o r a g e s y s t e m b y h uv t m i n g b e ( h e n g y a n gn o r m a lu n i v e r s i t y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g c o m p u t e ra p p l i c a t i o n i n t h e g r a d u a t es c h o o l o f h u n a nu n i v e r s i t y s u p e r v i s o r a s s o c i a t ep r o f e s s o ry a n gl e i ，l ir e n f a ( m a y , 2 0 11 ) 学位论文原创性声明 。 湖南大学 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： 钥巷蛾 学位论文版权使用授权书 日期：) o t l 年岁月孑7 日 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 拥巷胡 拗 日期：) 口1 f 年f 月；日 日期：伽ff 年f 月专je l 硕 学位论文 摘要 数据的爆炸式增长推动存储技术快速发展。相比传统的c s 模式，p 2 p 存储 系统充分利用分散的普通用户资源，以开放、安全、可扩展性强等优点得到广泛 关注。 作为p 2 p 存储系统的一个重要组成部分，副本策略是提高p 2 p 存储系统可扩 展性、容错性、可用性和减少查询响应时间的有效机制。但是副本数量的增加同 样会带来副本管理问题。目前副本管理策略中存在副本创建时存储位置和数量不 合理、网络带宽消耗大以及副本一致性维护算法冗余消息多、更新速度不及时等 问题。本文针对上述问题展开研究。 针对副本创建策略存在的问题，本文提出一种分簇拓扑结构基于访问频率的 副本创建策略。通过预测网络距离将节点进行分簇，同时使用超节点选择方式为 每个簇选取一个簇首，簇内和各簇首之间使用c h o r d 协议进行管理。簇内节点网 络距离较近，可以降低查询时延、提高查询效率和数据传输速率。基于访问频率 的副本创建策略将数据副本放置在访问频率较高的节点上或节点附近，减少远程 访问引起的带宽消耗。实验验证该算法能有效降低网络消耗，减少远程数据访问 量。 针对副本一致性维护算法中的问题，本文提出一种覆盖网络中基于节点异构 度的副本一致性维护算法一一n h d c o m 。该算法采用c h o r d 协议对副本节进行管 理，利用每个节点所维护的指取表信息进行划分，提出一种异构度收集树构建方 法，理论分析表明算法能显著降低分割时消息传播开销。考虑到节点的差异性， 提出节点异构度的概念并构建异构度收集树，然后通过动态规划方法求解最小延 迟更新内容树。理论分析和模拟实验表明基于节点异构度副本一致性维护算法能 有效减少更新冗余消息、快速更新副本。 关键词：p 2 p 网络；网络距离分簇；副本创建；异构度；副本一致性； i i p 2 p 分布式存储副本策略研究 a b s t r a c t t h ee x p l o s i v eg r o w t ho fv a r i o u sd a t ap r o m o t e sc o m p u t e rs t o r a g et e c h n o l o g yt o d e v e l o pr a p i d l y c o m p a r e dw i t ht h et r a d i t i o n a lc sm o d e ，p 2 ps t o r a g es y s t e m sm a k e f u l lu s eo fd e c e n t r a l i z e du s e r s r e s o u r c e s c o n s e q u e n t l y , i tg e t sal o to fa t t e n t i o nf o r i t so p e n ，s a f e t y , f l e x i b l ee x p a n d a b i l i t ya n ds oo n a sa ni m p o r t a n tp a r to fp 2 ps t o r a g es y s t e m ，r e p l i c as t r a t e g yc a ni m p r o v et h e e x t e n s i b i l i t y , u s a b i l i t y ，f a u l tt o l e r a n c ea n d r e d u c eq u e r yr e s p o n s et i m e b u ti n c r e a s i n g t h en u m b e ro fr e p l i c a sm a yb r i n ga b o u tr e p l i c a sm a n a g e m e n tp r o b l e m s a tp r e s e n t ， t h e r ea r es o m eq u e s t i o n sa sf o l l o w s a tf i r s t ，w h e nr e p l i c ai sc r e a t e d ，t h eu n r e a s o n a b l e d e c i s i o no fs t o r a g el o c a t i o n sa n dq u a n t i t yc a nr e s u l t i nc o n s u m p t i o no fs t o r a g e r e s o u r c e sa n dn e t w o r kb a n d w i d t h a tt h es a m et i m e ，r e p l i c ac o n s i s t e n c ya l g o r i t h m s c a nn o tg u a r a n t e et or e d u c er e d u n d a n tu p d a t em e s s a g e sa n du p d a t er e p l i c a s o nt i m e t h i sp a p e rr e s e a r c h e so nt h ea b o v ep r o b l e m s o nr e p l i c a t i o ns t r a t e g i e s ，t h ep a p e rp r o p o s e s a na c c e s sf r e q u e n c yr e p l i c a t i o n a l g o r i t h mb a s e do nc l u s t e rt o p o l o g y a tf i r s t ，i tp a r t i t i o n st h en e t w o r k i n t oc l u s t e r sb y n e t w o r kd i s t a n c e a n dac l u s t e rh e a di sc h o o s e db yt h es a m ew a ya ss u p e rn o d e s e l e c t i o n c l u s t e r m e m b e r sa n dc l u s t e r - h e a d sa r em a n a g e db yc h o r dp r o t o c 0 1 d u et o c l o s en e t w o r kd i s t a n c e ，ac l u s t e ri sl o o k e da sau n i t y ，w h i c hc a nr e d u c ea c c e s st i m e d e l a y ，i m p r o v eq u e r ye f f i c i e n c ya n dd a t at r a n s m i s s i o nr a t e b a s e do na c c e s sf r e q u e n c y r e p l i c a t i o ns t r a t e g y c a nc o p yp o p u l a rd a t aa n dp l a c ei t i nr e a s o n a b l ep o s i t i o n c o n s e q u e n t l y ，i tc a nr e d u c et h eb a n d w i d t hc o n s u m p t i o nc a u s e db yr e m o t ea c c e s s e x p e r i m e n t a lr e s u l t sv e r i f y t h a tt h ea l g o r i t h mc a ne f f e c t i v e l yr e d u c et h en e t w o r k c o s t sa n dr e m o t ed a t aa c c e s s i na d d i t i o n ，t h ep a p e rp r o p o s e san o d eh e t e r o g e n e o u sd e g r e e b a s e dr e p l i c a c o n s i s t e n c ym a i n t a n c ea l g o r i t h m f o r o v e r l a yn e t w o r k b a s e d o nc h o r dg r o u p m a n a g e m e n tp r o t o c o l s ，w ep r e s e n tap a r t i t i o nm e t h o db yt h ef i n g e rt a b l et os o l v et h e p r o b l e mo fn o d ei n f o r m a t i o na c q u i s i t i o n c o n s i d e r i n gt h e n o d eh e t e r o g e n e i t y ，t h e a u t h o r sp u tf o r w a r dt h ec o n c e p to fh e t e r o g e n e o u sd e g r e e sn o d e s a n d c o n s t r u c t h e t e r o g e n e o u sd e g r e e s c o l l e c t i o nt r e e l a s tb u tn o tl e a s t ，i tg e t sm i n i m u md e l a y c o n t e n tu p d a t e st r e ec o n t e n tu p d a t e t r e e b yd y n a m i cp r o g r a m m i n ga l g o r i t h m t h e c i r e t i c a la n a l y s i sa n ds i m u l a t i o nr e s u l t s s h o wt h a tn o d eh e t e r o g e n e o u sr e p l i c a c o n s i s t e n c ym a i n t e n a n c ea l g o r i t h mc a nr e d u c e r e d u n d a n tm e s s a g ee f f e c t i v e l ya n d i i i 硕十学位论文 u p d a t er e p l i c aq u i c k l y k e yw o r d s ：p 2 pn e t w o r k ；n e t w o r kd i s t a n c eg r o u p i n g ；r e p l i c ac r e a t i o n ；n o d e h e t e r o g e n e o u sd e g r e e ；r e p l i c ac o n s i s t e n c ym a i n t e n a n c e i v p 2 p 分布式存储副本策略研究 目录 学位论文原创性声明学位论文版权使用授权书i 摘要i i a b s t r a c t 。i i i 插图索引v i i 附表索引v i i i 第1 章绪论1 1 1 课题研究背景及意义1 1 2 本文主要工作一3 1 3 本文的结构4 第2 章p 2 p 存储系统副本管理技术研究5 2 1p 2 p 网络技术5 2 2p 2 p 存储系统的节点组织方式研究一6 2 2 1 集中式p 2 p 体系6 2 2 2 结构化p 2 p 体系7 2 2 3 无结构化p 2 p 体系10 2 3 副本创建相关技术研究l l 2 3 1 副本创建冗佘方法一1 1 2 3 2 副本创建关键问题1 3 2 。3 3 副本创建相关方法1 4 2 4 副本一致性维护算法研究1 5 2 4 1 集中式拓扑中的一致性研究1 6 2 4 2 结构化拓扑的一致性研究1 6 2 4 3 非结构化拓扑一致性研究1 6 2 5 小结17 第3 章分簇拓扑结构中基于访问频率副本创建策略1 9 3 1 引言19 3 2 基于分簇的双层c h o r d 环1 9 3 2 1 基于分簇的双层c h o r d 环的构建2 0 3 3 基于访问频率副本创建策略一2 l 3 4 模拟实验2 5 v 硕上学位论文 3 5 小结2 8 第4 章基于节点异构度副本一致性维护策略2 9 4 1 引言2 9 4 2 节点异构度2 9 4 2 1 节点异构度计算3 0 4 2 2 异构度收集树的建立3 1 4 2 3 节点异构度收集一3 3 4 3 更新内容树3 5 4 4 副本节点维护3 7 4 4 1 副本节点的加入与离开一3 7 4 4 2 副本节点的失效3 7 4 5 模拟实验3 8 4 6 j 、结4l 结论4 3 参考文献4 5 致 射4 9 附录a ( 攻读学位期间所发表的学术论文) 5 0 附录b ( 攻读硕士期间参与的项目列表) 一5 1 v i p 2 p 分布式存储副本策略研究 插图索引 图1 1c s 模型2 图1 2p 2 p 模型2 图2 1n a p s t e r 网络结构6 图2 2 包含三个节点的c h o r d 环7 图2 3c h o r d 环路由表8 图2 4 节点6 加入后的路由表一8 图2 5 节点1 退出后的路由表9 图2 6g n u t e l l a 工作原理l0 图2 7 纠错码冗余机制1 2 图3 1 基于网络距离分簇的拓扑结构2 1 图3 2o p t o r s i m 体系结构图2 5 图3 3 作业平均处理时间2 7 图3 4 远程文件访问数2 7 图3 5 网络使用率2 7 图4 1 异构度收集树算法的流程图3 2 图4 2 由1 0 个副本节点组成的c h o r d 网络，m = 4 3 3 图4 3 基于图4 2 的异构度收集树3 3 图4 4 异构度收集算法流程图3 4 图4 5 最小延迟更新内容树算法流程图3 6 图4 6 异构度与更新时间的关系( n = 5 0 0 ，s i z e = 5 m ) 3 9 图4 7 异构度与更新时间的关系( n = 5 0 0 ，s i z e = 5 0 m ) 3 9 图4 8 文件大小与更新时间的关系( n = 1 0 0 ，6 = 2 0 ) 4 0 图4 9 文件大小与更新时间的关系( n = 5 0 0 ，6 = 2 0 ) 4 0 图4 1 0 节点规模与更新时间的关系( s i z e = s m ，6 = 1 0 ) 4 1 图4 1 1 节点规模与更新时间关系( s i z e - s m ，6 = 1 0 0 ) 一4 1 v i i 硕十学位论文 附表索引 表3 1o p t r o s i m 模拟实验参数设置2 6 表3 2 三种副本创建算法实验结果2 6 v i i l 硕i ：学位论文 第1 章绪论 1 1 课题研究背景及意义 经济的高速发展促使i n t e r n e t 网络的不断壮大，数据信息迅猛增加推动计算 机存储技术不断发展。在此情形下，传统的c l i e n t s e r v e r 模式及存储技术已不能 满足日益发展的需求。为了充分利用互联网中散布的大量网络资源，基于p 2 p 存 储技术初步显现了强大的威力，得到了广泛关注。 与传统的c l i e n t s e r v e r 的集中式结构不同，p 2 p 存储系统所有的节点在功 能上是平等互联的，如图1 1 、1 2 所示。p 2 p 文件存储系统主要由p c 机组成的 对等网络，将数据资源存储到不同的节点上解决服务器存储能力及访问所带来的 超负荷开销。较传统的存储系统相比，p 2 p 存储系统有如下优点。 ( 1 ) 非集中化- - p 2 p 网络中，存储系统中的所有服务都不依赖于中央服务器，而是在存储系 统的所有节点上进行，从而避免了服务器自身所带来的性能瓶颈及服务器失效导 致系统无法提供服务。非集中化的特点对服务器性能要求降低，极大的减少成本 开销。 ( 2 ) 高扩展性 在p 2 p 网络中，由于每个节点都是自由平等的，节点的加入不但不会影响到 整个系统的性能，反而使得系统的服务能力得到提高。相反，传统的c s 模式由 于需要中央服务器对所有的节点进行集中化管理，节点之间消息的转发也会加重 服务器的负担，所以扩展性受到服务器性能的约束。 ( 3 ) 鲁棒性 传统的集中式服务模式完全依赖于服务器。当服务器系统故障或网络中断等 异常，导致整个系统无法向客户提供服务。p 2 p 系统由对等节点构成，各个节点 功能对等，整个系统缺失任意节点仍能正常工作。系统允许节点自由的加入和离 开，根据自适应性机制自动调整拓扑结构，保持所有节点正常工作，具有很强的 鲁棒性。 ( 4 ) 隐私性 p 2 p 网络中不需要服务器的介入，信息的传输分散在各节点之间进行，大大 减少用户的隐私信息被窃听和泄漏。 ( 5 ) 高性能 计算机的计算和存储能力以及网络带宽快速增长。p 2 p 存储系统有效地利用 p 2 p 分布式存储系统副本策略研究 分布在网络中的资源，将计算任务和存储服务分发给系统中的空闲节点完成，有 效提高了整个存储系统的服务性能，以较小的代价达到或超过集中式控制系统的 规模。 图1 1c s 模型 端 客户端 图1 2p 2 p 模型 客户端 户端 虽然p 2 p 系统具有高扩展性及高容错性，但p 2 p 系统中每个节点自由地加入 和退出，使得任何节点都可能暂时或永久失效。若节点暂时离开，保存在该节点 上的所有数据资源面临暂时无法访问；而节点永久失效直接导致数据丢失，降低 系统的可靠性。为了保证系统数据的可用性和可靠性，副本技术是在有节点失效 情况下保证数据持久性的重要手段。 作为p 2 p 存储系统中的关键技术之一，副本技术是指将系统中的数据资源存 储在不同的节点上，对提高系统的可用性、可靠性、查询负载等改善系统性能方 面，具有重要的意义。 首先，副本可以提高系统的可靠性。当系统的某一个或几个副本节点暂时失 硕十学位论文 效或永久失效时，可以对其它副本进行操作，不会因某个或几个节点失效而造成 用户无法访问存储在系统中的数据，也可避免用户数据丢失，增加系统容错性。 其次，副本可以避免单节点负载过重。当访问p 2 p 某节点上的网络资源发生 不可预料的大量的增长时，容易导致热点问题。如果将数据存储在不同的节点上， 各节点访问传输率最快的数据资源，不仅减少了访问时延，而且避免了由于单节 点负载过重产生的性能瓶颈。 最后数据副本可以减少访问时延，提高存取效率。将数据资源存储在经常访 问的节点上或附近距离，极大的降低了访问时延，提高整个系统的访问效率。 虽然数据副本给p 2 p 文件存储系统带来上述优点，但不可避免地也带来了一 系列的副本管理问题：副本复制需要消耗大量网络带宽，冗余副本的存储占用系 统存储资源，副本位置选取的合理性对系统性能造成较大影响、副本一致性维护 时带来冗余消息的增加等。目前副本管理策略中存在副本创建时存储位置和数量 不合理、网络带宽消耗大以及副本一致性维护算法冗余消息多、更新速度不及时 等问题。 综上所述，提出一种高效、灵活、动态的副本管理策略具有重要意义。 1 2 本文主要工作 本文的工作主要是在前人研究成果的基础上，对基于p 2 p 分布式存储系统副 本管理的策略进行改进创新，主要包括副本的创建与副本一致性维护两个方面。 工作总结如下： 首先，对国内外副本管理的研究现状进行总结分析是开展本文工作的重要前 提。然后将分析国内外系统节点间的组织方式和副本冗余方法，以及研究副本创 建策略和副本一致性维护策略等相关技术和现有方法的优缺点。 其次，在副本创建过程中，为了降低查询时延、提高副本传输效率，本文考 虑根据网络距离预测算法选择网络距离相近的节点划入同一簇中，并使用超节点 选取方法为簇选择簇首及备份节点。簇内和簇间同时采用c h o r d 协议进行管理， 构建双层c h o r d 拓扑结构。本文还将在上述拓扑结构上提出基于分簇的频率访问 副本创建策略，通过簇首记录簇间副本读写访问频率，决定副本创建时机与副本 创建位置。然后通过o p t o r s i m 模拟验证基于访问频率的副本创建策略能否有效的 放置副本，节省网络带宽，提高整个p 2 p 存储系统的性能。 在要求副本数据具有强一致性的环境下，如何利用端特性使更新数据快速传 播、减少冗余消息传播，是本文解决的关键问题。本文将通过引入节点能力度量 参数节点异构度，提出一种基于节点异构度的无结构覆盖网络副本一致性维 护方法n h d c o m 。由于拟考虑n h d c o m 利用c h o r d 组管理协议管理副本节 点，本文将提出基于指取表的分割方法动态获取副本节点的异构信息，并通过理 3 p 2 p 分布式存储系统副本策略研究 论证明该算法性能。为使副本的更新时间最优，权衡节点异构性和节点度关系， 将利用动态规划方法提出一种基于时延的动态节点度约束生成树算法来构建更新 内容树，确保该算法能保证系统强一致性的前提下快速更新副本。仿真实验将按 照o p t o r s i m 中副本更新仿真的基本思想模拟构建一个中小规模的无结构覆盖网 络一致性维护评测环境，并分别实现n h d c o m 算法、p a t c o m 算法和d c m d 算法，并对他们进行性能的比较。 1 3 本文的结构 全文共分为五章。 第1 章为绪论，主要介绍了课题研究的背景及意义，并在此基础上介绍了本 文的工作。 第2 章讨论了当前p 2 p 存储系统节点组织方式、副本冗余方法、副本创建策 略及副本一致性维护相关技术，分析了现有p 2 p 网络存储系统副本管理现状及 不足。 第3 章在当前副本创建方法的基础上，提出一种分簇拓扑结构基于访问频率 的副本创建策略，使用o p t o r s i m 模拟实验验证了算法的性能。 第4 章是在研究分析当前无结构p 2 p 存储系统的前提下，结合p 2 p 系统节点 的异构性，提出副本一致性维护算法n h d c o m 。对提出的n h d c o m 算法进行仿 真模拟实验，并与p a t c o m 及d c m d 进行对比分析，然后给出结论。 文章最后是总结与展望。总结了全文的主要工作，并分析了本文有待改进之 处，为以后继续研究确定方向。 4 硕 学位论文 第2 章p 2 p 存储系统副本管理技术研究 作为p 2 p 存储系统的的基础和前提，本文首先对p 2 p 网络进行了简单的介绍。 考虑到p 2 p 存储系统节点组织方式是副本管理策略所要考虑的条件和依据，本章 研究分析不同系统节点组织方式的优缺点。其次，对副本的创建的冗余方法进行 了介绍和分析比较。为了深入的理解现有的副本一致性维护算法，本章还在前人 研究的基础上，按不同节点组织方式的副本一致性维护算法进行了总结和分析。 2 1p 2 p 网络技术 p 2 p 网络，即对等网络，由分布式系统和计算机网络结合而成，网络中的所 有节点平等、互联。在c s 模型中，每个节点要么是客户端，要么是服务器，其 中，服务器是一个集中控制点。而p 2 p 网络中，所有的计算机自组织成一个整体 网络，享有对等地位，每个节点既能请求资源与服务，又能响应其它计算机的请 求并向其提供服务。 p 2 p 网络能够适应网络环境不断的动态变化。网络的核心部分由中央服务器 转向系统中的每一个节点，用户不但能享受网络服务，而且能为其他的网络用户 提供服务。p 2 p 网络的优点可归纳为以下几点： ( 1 ) 提高网络工作效率 p 2 p 网络没有集中式的控制，任意两个节点之间交换信息不需通过服务器， 从而不会因为服务器性能瓶颈导致网络无法正常工作。同时，p 2 p 网络通过构建 一个覆盖网，并使用h a s h 函数将节点和数据资源均匀的分布在系统中，使得任 意两个节点定位需要经过的网络跳数在l o g n 左右，有效地提高了路由效率。 ( 2 ) 充分利用网络带宽 p 2 p 网络不存在因服务器造成效率瓶颈，也不会出现服务器“单节点失效” 导致整个网络通信中断情形。系统中所有的节点共同分担存储和计算等服务。 p 2 p 的非中心化基本特点，充分利用了网络带宽。 ( 3 ) 开发每个网络节点潜力 p 2 p 技术使网络由以前的服务器中心控制转变成系统中的每一个节点功能平 等。系统中所有的节点既是服务的享有者，又是服务的提供者。它们共同分担存 储和计算等服务，充分利用了节点的空闲资源，大大降低了服务器的成本。 ( 4 ) 高可扩展性 在p 2 p 网络中，用户不断增多虽然会增加消息传播开销，但平均到每一个节 点上影响很小。路由跳数增加，但是增量不大，通信效率仍然保持较高水平。并 5 p 2 p 分布式存储系统副本策略研究 且节点的增多不需要更新服务器硬件设备。理想环境中扩展性趋于无穷。 2 2p 2 p 存储系统的节点组织方式研究 通常p 2 p 存储系统节点组织方式分集中式、结构化和非结构化三种方式。下 面按照节点组织方式分别介绍了典型的存储系统，并分析了三种节点组织方式的 优缺点。 2 2 1 集中式p 2 p 体系 n a p s t e r 2 】作为世界上第一个应用p 2 p 网络，以集中目录式结构组织系统节点， 主要用来共享音乐文件，如图2 1 所示。 n a p s t e r 网站是一个服务器机群，每个服务器保存一部分用户的共享信息，所 有的服务器是互联、整合起来对用户提供统一的访问接口，在每一个用户看来他 们访问的都是同一个服务器。用户注册与文件检索过程类似于传统的 c l i e n t s e r v e r 模式，其区别在于所有共享文件并非存储在服务器上。每个n a p s t e r 用户连接到机群中的一台服务器，将他愿意与系统中其他用户分享的信息发给服 务器。服务器并不将相关的信息复制过来，而是保存相关信息及该用户位置，并 将它们合成一条索引添加到服务器索引表中。当有用户想查询文件时，先将查询 信息发送到服务器，服务器收到信息后，与服务器机群一起处理查询信息，处理 完后返回给用户，其中包括表单及文件索引。用户选取自己所需要文件，直接与 该文件所在用户建立连接。 图2 1n a p s t e r 网络结构 6 硕士学位论文 n a p s t e r 网站服务器不仅需要保存用户共享文件的索引，同时需要监视所有用 户的状态，包括用户已连入n a p s t e r 网络的时间、网络带宽，以及掉线等。比如 用户非正常退出，必须要在服务器中删除掉所有有关该用户的信息，以保证文件 索引的有效性。 集中目录式网络将所有的资源存储在不同的服务器机群中，并且统一向用户 提供接口，使用户感觉到只和一个服务器通信。由于采用服务器进行统一管理， 不存在副本一致性等问题。但是集中目录式p 2 p 存储系统也存在很多缺点：集中 目录式系统功能的实现依赖于中央服务器节点，若其中一个服务器节点失效，与 之相连的节点则无法与系统中的其他节点保持联系，因此可靠性和安全性低；由 于所有的文件目录及节点信息都保存在服务器机群中，随着网络规模的不断扩大， 中央服务器不能承担重负，必须不断更新服务器设备，提高系统性能。这种维护 的成本较高，并且维护起来也比较困难。所以，系统的可扩展性受限于中央服务 器节点。由以上分析可知，集中目录式p 2 p 存储系统系统对于小型网络在系统管 理和控制方面占有一定的优势，但是鉴于种种缺陷，其并不适应于大规模网络。 2 2 2 结构化p 2 p 体系 结构化p 2 p 网络最大的特点在于它们都有一个严格的覆盖网络拓扑结构，作 为该领域最著名的理论模型，c h o r d 具有最简单最精确的优点。它基于带弦环拓 扑结构的分布式散列表，通过安全散列函数( s h a 1 ) 给每个系统节点及数据资源对 象分配唯一的标识符，分别为n o d e l d 和f i l e l d 。s h a 散列函数值的h a s h 值长度 通常大于等于1 6 0 ，从而保证i d 是惟一的，不会重复出现。 田 s u 图2 2 包含三个节点的c h o r d 环 7 p 2 p 分布式存储系统副本策略研究 c h o r d 环是一个虚拟的空间，所有节点按照n o d e l d 号从小到大排列在环上， 路由就在这个虚拟标识空间中进行。当有数据需要保存在环上时，根据数据资源 所拥有的f i l e l d 在环上依次查询与之相等或第一个大于它的n o d e l d ，这个节点被 称之为此对象的后继节点。数据资源k 的后继节点记为：s u c c e s s o r ( k ) 。数据资源 被分配在后继节点。如图2 2 所示，s u c c e s s o r ( 1 ) = 1 ，s u c c e s s o r ( 2 ) = 3 ，s u c c e s s o r ( 6 ) = 0 分别表示数据对象1 放置在节点1 上，数据对象2 放置在节点3 上，数据对象6 放置在节点o 上。 图2 3c h o r d 环路由表 图2 4 节点6 加入后的路由表 8 硕士学位论文 图2 5 节点1 退出后的路由表 为了高效地定位，每个c h o r d 节点维护一个额外的路由表，称之为指取表， 由m 项路由表组成( m 是i d 位数) ，如图2 3 所示。它的设计有两个特点：首先， 每个节点只保存很少其他节点的信息，并且离它越近节点所知越多，反之，离它 越远所知信息就越少。其次，环上的节点不能通过自己的路由查看数据对象的后 继。为了确定数据对象k 的后继，节点需要在自己的指向表中找到一个离k 最 近的节点，然后再让，找离k 最近的节点，依次循环，直到找到k 的前驱。 在动态网络环境中，节点可以在任何时刻加入或者离开，为了达到自适应性 目的，c h o r d 需要保持两个属性：因为c h o r d 中正确的后继关系是一切工作的基 础，所以必须使每个节点的后继关系正确；其次，对于数据对象k ，节点s u c c e s s o r ( k ) 始终负责k 的索引。因此任何一个节点刀的加入必须完成三个任务：初始化节点 ”的前驱和路由表；更新现存节点的前驱和指向表以反映刀的加入；通知节点，l 的后继将该由甩负责的数据对象索引传递过来。如图2 4 中，当节点6 加入后， 各节点需要更新路由表，s u c c e s s o r ( 6 ) = 6 ，存储在节点o 上的数据对象转移到节点 6 上，节点o 的k e y 。 综上所述，个节点组成的c h o r d 环中，节点的指取表需要保存需o ( 1 0 9 n ) 个节点信息。每次查找时覆盖网中的路由跳数只需要o ( 1 0 9 n ) 。当节点加入或者 离开网络时，为了维护网络结构及自适应性，c h o r d 需及时更新指取表， 节点的加入或者离开需传递o ( 1 0 9 2 n ) 条消息。 9 p 2 p 分布式存储系统副本策略研究 结构化p 2 p 网络数据资源通过哈希表存储在其标识相等或相近的节点上，具 有查找可确定性、简单性和分布性等优点。为了使这种映射唯一、均匀、随机， 大多数p 2 p 系统采用安全散列函数是s h a 1 ，它能产生与输入无关的1 6 0 位散列 值，并且冲突的概率极小。将系统中的数据资源和节点均匀地映射在逻辑空间中， 每个节点维护o ( 1 0 9 ) 条邻居信息和路由信息进行查找定位，效率一般为 o ( 1 0 9 ) 。相比如谣言机制，这种消息传递机制有效减少大量冗余消息，减轻了 节点的负担，提高系统的性能。但结构化p 2 p 网络容错性、安全性通常不及无结 构p 2 p 网络，因为拓扑结构越严格、定位越准确，维护起来就越复杂，暴露给攻 击者的弱点也就越多。 2 2 3 无结构化p 2 p 体系 无结构p 2 p 系统中没有服务器，所有的节点完全是对等的。系统中只存在一 类节点一一对等节点，而不存在任何所谓的服务器。节点的加入与离开只需通过 邻居节点反映，彻底去除了服务器集中管理的思想。正因为如此，任意单个节点 的暂时离开或永久失效都不会影响整个系统的正常运行。这种强容错性及自适应 性使得无结构p 2 p 网络得到广泛的使用。其经典案例是g n u t e l l a 。 g n u t e l l a 是第一个无结构p 2 p 网络，于2 0 0 3 年3 月诞生于n u l l s o f i ，其发明 人是著名的m p 3 播放软件w i n a m p 的设计者一一j u s t i nf r a n k e l 和t o mp e p p e r 。 由于n a p s t e r 带来的一系列版权问题，g n u t e l l a 软件公布不久会关闭了下载网站， 并且该公司也没有推出新的版本。g n u t e l l a 体系结构的工作原理图如图2 6 所示。 图2 6g n u t e l l a 工作原理 df i l ed o w n l o a d g n u t e l l a 作为一种纯粹p 2 p 架构的分布式文件共享系统，系统中只有对等节 点，没有服务器的存在。在g n u t e l l a 网中消息可以被广播也可以被回播。为了查 1 0 辩 盯 碍 姗 e 屺 唾 晰 一 一 o q r 硕士学位论文 询系统中数据资源，节点n 给它所有的邻居节点发送请求消息q u e r y 。这种消息 具有一个随机产生的全局唯一标识符，并且设有跳数限制( 丁儿) 。m 是用来 控制消息数量，使得g n u t e l l a 洪泛式的广播不会无度地消耗网络资源，否则网络 无法承载巨大的开销。消息在覆盖网上每走一跳丁儿减1 ，当r 儿等于0 时，消 息不再传递。收到q u e r y 消息的节点首先检查是否有它共享的文件，如果有则沿 着q u e r y 消息传送过来的路径回播；如果没有则向自己的邻居继续广播q u e r y 消息。显然g n u t e l l a 的查询方式有两个缺陷：首先，由于采用洪泛式的方法广播 消息，会消耗大量网络资源；其次，由于r 儿限制了消息的传播跳数，从而使得 即使文件存在也有可能找不到。 当有新的节点n 需要加入g n u t e l l a 网络，n 必须知道一个自举节点，并通过 它连入网络。节点的加入和离开都需要使用g n u t e l l a 协议中的p i n g 和p o n g 来 保持覆盖网的一致性和节点信息的及时更新，其方法类似上面的查询消息，通过 洪泛进行广播，确保整个g n u t e l l a 网络较好的自组织和自适应性。 无结构p 2 p 网络的拓扑结构简单，软件开发和实现难度都比较小。具有高容 错性和良好的自适应性。由于整个网络没有严格的拓扑结构，可以达到非常高的 安全性和匿名性。但是由于无结构网络中大多采用洪泛式的消息传播机制，路由 效率不高，消息传递消耗大量的网络带宽。采用单纯的洪泛法，导致网络可扩展 性不强。由于路由的局部性，无法保证网络中存在的数据一定能被找到，使得数 据无法准确定位。 2 3 副本创建相关技术研究 2 3 1 副本创建冗余方法 在存储系统中，为了保证数据的持久性，需要对存储在系统中的数据做一定 量的冗余，确保系统数据的可靠性和可用性。当节点退出系统时，存储在节点上 的数据将无法被其它节点访问，降低了数据的可用性。若存储数据的节点失效， 则导致存储在节点上数据的丢失，降低系统数据的持久性。基于p 2 p 存储系统中， 一般采用的机制主要是完全复制