（计算机科学与技术专业论文）结构化p2p系统容错机制研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 p 2 p ( p e e r t o 。p e e r ) 已经成为新一代互联网应用的重要形式，它为网络应用带来 了更好的扩展性、自组织性和高效性。结构化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 系统结点可靠性评估模型。论文提出了p 2 p 系统结点的可 靠性度量框架，对评价p 2 p 系统结点的可靠性以及多种情况下拓扑中超结点的选 取有一定的指导意义。 在此基础上，论文设计了基于簇备份的结构化p 2 p 系统容错机制r s f e 。 该机制设计了与f i s s i o n e 相对应的r s f e 路由、结点加入和结点退出算法，采用硬 件冗余的方式备份结点信息达到容错的目的，并通过实验验证了该机制可有效提 高p 2 p 系统的容错能力。 最后，论文总结了全文的工作，指出了存在的优缺点，并对未来工作进行了 展望。 主题词：结构化p 2 p ，扰动，容错技术，动态性，可靠性评估，网络分割，冗 余备份机制 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t p e e r t o p e e r ( p 2 p ) h a sb e c o m eo n eo ft h em o s ti m p o r t a n ta r c h i t e c t u r e sf o ri n t e m e t a p p l i c a t i o n sf o ri t si n h e r e n ts c a l a b i l i t y ，f a u l tt o l e r a n c e ，a n dh i g hp e r f o r m a n c e t h e r e s e a r c ho fd h t s y s t e m si so n eo ft h eh o t t e s ti s s u e si np 2 p ，m o r ea n d m o r ea p p l i c a t i o n s o nd h tc o m ei n t ou s e ，a n di tp l a y sa ni m p o r t a n tr o l ei ni n t e r n e t n e v e r t h e l e s s ，e v e r y p e e ri sm e a n tt oi o i na n dl e a v et h es y s t e ma r b i t r a r i l y ，w h i c hm a k e sf a i l u r em o r e c o m m o nt h a no t h e rs y s t e m sa n dm a k e st h es y s t e mr u ns l o w l y ，e v e nb r e a kd o w n t o h a n d l et h ec h u m ，an u m b e ro fa p p r o a c h e sh a v eb e e np r o p o s e dt od a t e i i lt h i s p a p e r w es u m m a r i z e dt h e c o n t e n ta n dr e l a t i v ep r o b l e mo fp 2 p f a u l t t o l e r a n tf i r s t l y ，a n dt h e ni n t r o d u c e das e r i e so ft e c h n i q u e sf o rs t r u c t u r e dp 2 p f a u l t t o l e r a n tu n d e rc h a m w ea n a l y z e df i v ei m p o r t a n ta s p e c t so ns t r u c t u r e dp 2 p f a u l t t o l e r a n tr e s e a r c h ：s y s t e md y n a m i c , f a i l u r ed e t e c t i o n ，o v e r l a yp a r t i t i o n ，d a t a r e d u n d a n c ya n dn e wt o p o l o g yf o rf a u l t t o l e r a n t ，a n do u t l i n e dt h es h o r t c o m i n g sa n d p r o b l e m so fe x i s t i n gm e t h o d s e c o n d l y t h i sp a p e rd i s c u s s e dt h en o d er e l i a b i l i t ye v a l u a t i o np r o b l e mi np 2 p f i l e s h a r i n gs y s t e mf r o mt h eq u a l i t yo fs e r v i c ep e r s p e c t i v e b a s e do na r t i f i c i a ln e u r a l n e t w o r km e t h o d i td e s i g n e dan o d er e l i a b i l i t ye v a l u a t i o nm o d e li np 2 ps y s t e m ，a n d p r e s e n t e dan o d er e l i a b i l i t ym e a s u r e m e n tf r a m e w o r ki np 2 pf i l e s h a r i n gs y s t e m ，w h i c h h a ds o m es i g n i f i c a n c ei nr e l i a b i l i t ye v a l u a t i o no fp 2 pf i l e s h a r i n gs y s t e mn o d e ，a sw e l l a st h es u p e rn o d es e l e c t i o ni nt o p o l o g i e s o nt h i sb a s i s ，t h i sp a p e rd e s i g n e dar e d u n d a n c ys t r a t e g yb a s e do nc l u s t e ri n s t r u c t u r e dp 2 ps y s t e m - r s f e t h i ss t r a t e g yi n c l u d e dr s f er o u t i n ga l g o r i t h m ，n o d ej o i n a n dd e p a r ta l g o r i t h mo nf i s s i o n e ，a n da c h i e v e dt h ep u r p o s eo ff a u l t t o l e r a n tb yu s i n go f b a c ku pn o d ei n f o r m a t i o nw i t hr e d u n d a n th a r d w a r e t h ee x p e r i m e n ts h o w e dt h a tt h i s s t r a t e g yc a ni m p r o v e t h ef a u l t t o l e r a n tc a p a b i l i t ye f f e c t i v e l yi nt h ep 2 pn e t w o r k i nt h ee n d t h ef u t u r et r e n do ft h ep 2 pf a u l t t o l e r a n tt e c h n o l o g yi sd i s c u s s e d k e yw o r d s ：s t r u c t u r e dp e e r - t o p e e rt o p o l o g y ，c h u r n ，f a u l t t o l e r a n t ， d y n a m i c ，r e l i a b i l i t ye v a l u a t i o n ，o v e r l a yp a r t i t i o n ，r e d u n d a n c ys t r a t e g y 第i i 页 国防科学技术大学研究生院硕十学位论文 表目录 表1 1p 2 p 文件共享系统分类5 表2 1 五种d h t 网络崩溃点实验结果1 8 表3 1 模型评价指标2 6 表4 1 模型训练样本( 部分) 3 4 表4 2 模型参数设置3 6 表4 3 模型测试样本( 部分) 3 7 表5 1n o d e 类中r s f e 参数配置表5 3 第1 v 页 国防科学技术大学研究生院硕士学傍论文 图 目录 图1 - 1c s 模式与p 2 p 模式拓扑对比副4 7 1 ，1 图2 - 1p 2 p 共享文件系统发展1 4 2 1 3 图3 1 人工神经网络基本模型2 2 图3 2 人工神经网络b p 算法学习阶段流程图2 4 图3 3 结点可靠性评估模型流程图2 5 图3 4 结点可靠性评估模型示意图2 7 图3 。5 人工神经网络结点可靠性模型2 8 图3 6 结点可靠性模型b p 学习算法实现( 1 ) 2 9 图3 7 结点可靠性模型b p 学习算法实现( 2 ) 3 0 图4 1 评估模型模块设计图( 1 ) 3 2 图4 2 评估模型模块设计图( 2 ) 3 3 图4 3 训练样本输入模块3 3 图4 4 训练样本数据处理模块。3 5 图4 5 测试样本数据处理模块3 7 图4 6 模型测试模块3 8 图4 7 训练后的样本最小均方差一3 9 图4 8 测试样本误差3 9 图5 1k a u t z 图k ( 2 ，3 ) 【4 6 j 4 3 图5 2f i s s i o n e 拓扑示例【矧4 3 图5 3r s f e 容错示意图4 5 图5 4r s f e 三结点基本拓扑4 6 图5 5r s f e 路由机制4 6 图5 - 6r s f e 资源发布机制4 7 图5 7 结点加入处理算法4 8 图5 8 结点退出处理算法5 0 图5 - 9p 2 p s i m 编译过程5 2 图5 1 0p 2 p s i m 模拟器类图框架【6 到5 2 图5 1 l 实验过程顺序图5 3 图5 1 2r s f e 机制容错特性图5 4 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目： 缱圭堑丝里2 里丞统空堡狃剑盟窥 学位论文作者签名：主：l 圣s日期：如。3 年j 2 月艿日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阕和借阕；可以将学位论文的全部或部分内容编入有关数据库进行检索 可以采用影印，缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书) 学位论文作者签名：墨：! 鳖 作者指导教师签名： 点蚌 日期：炒弓年f 2 月巧日 日期：计年i ，月巧日 国防科学技术大学研究生院硕士学位论文 第一章绪论 1 ，1 课题背景 近年来p e e r t o p e e r ( p 2 p ) 计算技术受到广泛关注，成为计算机业界的重要热 点，在很多领域都有着大量的研究与应用。p 2 p 技术【舐4 7 】是相对于客户机朋艮务器 ( c s ) 模式的另一种网络计算模式。在c s 模式中，数据的分发通常采用专门的服 务器，多个客户端都从此服务器获取数据。这种模式的优点是：数据的一致性容 易控制，系统也容易管理。但是此种模式的两个主要缺点是：因为服务器的个数 非常有限，系统容易出现单点失效；单一服务器面对众多的客户端，由于c p u 能 力、内存大小、网络带宽的限制，可同时服务的客户端数量有限，而且可扩展性 差。 p 2 p 技术正是为解决这些问题而提出的一种对等网络结构。在p 2 p 系统中， 每个结点既可以从其他结点得到服务，也可以向其他结点提供服务。这样，网络 上众多的终端资源被利用起来，同时避免了c s 模式中的两个弊端。i n t e l 、h i 和 s o n y 等著名公司联合成立了p 2 p 工作组【4 2 1 ，s u n 开发了开放源码的p 2 p 计算平台 j x t a t 4 3 ，m i t 、u c b e r k e l e y 和s t a n f o r d 等众多著名大学以及m i c r o s o f t 研究院 和h p 研究院等著名研究机构都纷纷开展了大量的相关研究工作。 取者 p e e r t op e e r 模式 图1 - 1c s 模式与p 2 p 模式拓扑对比图【4 7 】 逻辑上来说，p 2 p 系统中的各结点是地位平等且相互独立的对等体，通过直接 交换来利用计算、存储、信息和带宽等资源。相比c s 系统，p 2 p 系统通常具有更 好的可靠性和可扩展性，拥有巨大的潜力。图1 - 1 给出了c s 模式与p 2 p 模式拓 扑对比图。 第1 页 供 燃p 国防科学技术大学研究生院硕十学位论文 1 。1 ，1p 2 p 技术的兴起 最初p 2 p 的概念源于两个对等体之间的通信，在电话交谈中，电话两端的通 话者( p e e r ) 处于平等的地位，通信方式是点对点的。早期的互联网应用方式中， 有很多技术都体现了p 2 p 的思想，例如a r p a n e t 、t e l n e t 和u s e n e t 等。a r p a n e t 网络早期的几个结点分布于美国的一些大学和研究机构中，它们的地位都是平等 的，a r p a n e t 通过对等的方式( 而不是m a s t e r s l a v e 或c s 的方式) 将这些结点连 接起来。 随着w e b 技术的广泛应用，越来越多的用户连接到i n t e m e t 上，造成i p 地址 缺乏。终端结点可以自由地加入退出，没有固定的i p 地址，所以客户端很难为网 络提供服务。这种环境下，c s 计算模式广泛流行并被大量部署，取得了巨大的成 功。 p 2 p 计算技术兴起的一个标志性事件是文件共享系统n a p s t e r l 4 5 j 的出现。1 9 9 9 年5 月s h a w nf a n n i n g 等发布了n a p s t e r 系统，为i n t e r n e t 上的用户提供m p 3 音乐 文件共享和交换服务。n a p s t e r 迅速取得了巨大的成功，是成长最快的i n t e r n e t 应 用之一，创立一年半后用户就达到了5 千万。2 0 0 1 年2 月，因为音乐版权的问题 被起诉，n a p s t e r 被法院判决停止进行有版权的音乐文件交换。 另一个采用p 2 p 方式实现计算资源共享的例子是s e t i h o m e 5 1 j 。该项目由美 国加州大学伯克利分校的空间科学实验室主办。这是一个寻找外星球文明的大型 科研工程。它通过互联网利用家用个人计算机处理天文数据的分布式计算项目， 其目标是充分利用互联网上闲散资源的计算能力。它利用的是空闲的处理器资源， 不影响用户正常使用计算机。目前，该项目在世界各地拥有近5 0 0 万参与者。 s e t i h o m e 是迄今为止最成功的分布式计算试验项目之一。很多公司也在从事 p 2 p 相关工作。例如，p o p u l a r p o w e r 、u n i t e d d e v i c e s 和e n t r o p i a 等公司都在开发相 关产品，以共享使用处于工作间隙的电脑的闲置计算能力。 随后i n t e m e t 上出现了更多流行的p 2 p 应用，如g n u t e l l a 5 3 1 、k a z z a 5 5 1 、 b i t t o r r e n t l 5 6 1 、t h u n d e r 、e d o n k e y 、e m u l e 、b i t s p i r i t 、t o m s k y p e 等。图2 1 给出 了p 2 p 文件共享系统的发展过程。 2 0 0 2 年3 月，h p 、i n t e l 等r r 业界巨头与p r i n c e t o n 、m i t 等著名院校联合启 动“p l a n e t 1 a b 计划( 4 9 1 。p l a n e t 1 a b ，官方定义为a mo p e np l a t f o r mf o rd e v e l o p i n g ， d e p l o y i n g 。a n da c c e s s i n gp l a n e t a r y s c a l es e r v i c e s ，中文含义：星球实验室，一个用于 开发、部署和使用的“星系级别 的网络服务的开放平台。p l a n e t 1 a b 是一个全球 性的研究网络，用于新型网络服务的开发。从2 0 0 3 年起，超过1 , 0 0 0 个来自顶级 学术机构和业界实验室的研究人员在p l a n e t i a b 上开发了新技术并进行部署实验， 其中包括：分布式存储、网络映射、d h t ( 分布式哈希表) 和查询处理等。到2 0 0 8 第2 页 国防科学技术大学研究生院硕士学位论文 年1 1 月，p l a n e t 1 a b 实验床已经包括了全球6 0 多家高等院校的4 7 3 个分布站点， 9 2 1 个结点，已有7 0 多个研究项目在p l a n e t 1 a b 实验床上运行与测试。 1 9 9 92 0 0 02 0 0 12 0 0 2 现在 兰! ! ! 习日兰! 竺i f 困圆f c ： e d o n k e y 2 0 0 0 1 习l里! 兰i 圆日园 图2 - 1p 2 p 共享文件系统发展【4 2 1 p 2 p 系统的优势如下： ( 1 ) p 2 p 系统促进网络资源共享。p 2 p 系统充分共享i n t e r n e t 上大量分布的计 算、存储、通信等资源，可降低系统的成本，而且突破了s e r v e r 的瓶颈，实现少 量s e r v e r 难以完成的工作。 ( 2 ) p 2 p 系统具有灵活、方便协作的特点。p 2 p 系统促进了i n t e r n e t 用户以及 设备间的直接协作和交流，提高了网络和资源效率，给网络用户带来新的有益的 交流和协作方式。 ( 3 ) p 2 p 系统创造了新的应用模式。p 2 p 技术可以使得应用可扩展行更好， 能够处理动态和不可预测的i n t e m e t 环境和新的移动环境。目前p 2 p 模式已经成为 构建新型大规模分布式应用的重要技术。 目前p 2 p 计算技术已在广域分布计算、文件共享、即时消息、分布式存储、 协同工作、应用层组播、数据管理和大规模联机游戏等多个领域有着广泛的研究 与应用。p 2 p 既代表一种新技术，也映射着种新文化。从技术角度来说，它通过 p e e r 与p e e r 的对等沟通，打破了传统的c s 的主从模式，是对互联网应用技术的 创新，也是互联网本质的回归。p 2 p 计算技术受到了广大网络用户的欢迎，在 i n t e r n e t 上得到广泛的应用。例如，目前主要的网络电视p 2 p 软件p p s t r e a m 、沸点 网络电视、t v k o o 、猫眼网络电视、q q 直播等；影视歌曲文件下载类的p 2 p 软件 b t 、百宝、酷狗( k u g o o ) 、电骡( e m u l e ) 等；通信类的p 2 p 软件t o m s k y p e 等【铝1 。 第3 页 詈酗囤 国防科学技术人学研究生院硕士学位论文 1 1 2p 2 p 系统的分类 目前存在着多种不同特性的p 2 p 网络，不存在唯一的分类标准，这里考虑2 种 分类方法【4 6 , 5 2 , 6 3 l 。 分散度是指p 2 p 系统的拓扑结构对中央服务器的依赖程度。根据分散度，p 2 p 系统可以分为三类： ( 1 ) 集中式拓扑 在集中式拓扑的p 2 p 系统中，存在着一个少数中央服务器。中心服务器保存 着所有节点的地址和目标文件信息，这样节点只需要向服务器请求它所需要信息 所在的节点地址，但结点之间的交互与资源共享等行为仍是直接以p 2 p 模式进行。 典型系统如n a p s t e r 和b i t t o r r e n t 等。 ( 2 ) 部分分布式拓扑 在部分分布式拓扑的p 2 p 系统中，存在一些“超级结点 ( s u p e r ，p e e r ) 。超级 结点具有比普通结点更强的能力和更高的地位，通常充当其它部分结点的目录服 务器的角色。但这些超级结点都是由p 2 p 系统动态选择和组织的，一般不会给p 2 p 系统带来单点失效等问题。部分分布式结构的优点是性能、可扩展性较好，较容 易管理，但对超级点依赖性大，易于受到攻击，容错性也受到影响。典型系统如 f a s t t r a c k 和b r o c a d e 等。 ( 3 ) 全分布式拓扑 在全分布式拓扑的p 2 p 系统中，所有结点都是完全平等的，每个结点既是服 务器也是客户端，系统中没有任何目录服务器。这种p 2 p 网络中信息也是分布式 存储的，通常采用d h t 技术构建拓扑结构。典型系统如g n u t e l l a 【5 3 1 、f r e e n e t 5 4 1 和 c h o r d 8 1 、f i s s i o n e 【1 5 】等。 耦合度是用来衡量p 2 p 系统的拓扑构造过程是受某种机制严格控制还是动态、 非确定性的。根据耦合度，p 2 p 系统可分为三类： ( 1 ) 非结构化拓扑( u n s t r u c t u r e d ) 在非结构化拓扑的p 2 p 系统中，结点间的逻辑拓扑关系通常较为松散，具有 较大的随意性。这类系统的特点是文件的发布和网络拓扑松散，相关资源( 或资 源元信息) 的放置通常与p 2 p 系统的拓扑结构无关，一般只放置在本地。非结构 化拓扑的实现和维护相对简单，可支持灵活的资源搜索条件，但高效的资源搜索 通常较为困难，适用于由大量自治性强的结点组成、对服务质量没有严格要求的 应用，如p 2 p 文件共享应用等。非结构化拓扑可进一步按照分散度进行分类：如 n a p s t e r 和b i t t o r r e n t 是集中式非结构化拓扑，g n u t e l l a 和f r e e n e t 是全分布式非结 构化拓扑，f a s t t r a c k 是部分分布式非结构化拓扑。 ( 2 ) 结构化拓扑( s t r u c t u r e d ) 第4 页 国防科学技术大学研究生院硕士学位论文 这类系统的特点是文件的发布和网络拓扑紧密相关。文件按照p 2 p 拓扑中的 逻辑地址精确的分布在网络中。在结构化拓扑的p 2 p 系统中，结点间的逻辑拓扑 关系通常由确定性的算法严格控制，资源( 或资源的元信息) 的放置也是由确定 性的算法精确发布到特定的结点上。在此拓扑上构造个存储文件的分布式哈希 表d h t ，文件根据自身的索引存储到哈希表中。每次检索也是根据文件的索引在 d h t 中搜索相应的文件。生成文件的索引的方法有三种：根据文件的信息生成的 哈希值( h a s h ) ，如c f s ，o c e a n s t o r e ，p a s t ，m n e m o s y n e 等；根据文件 包含的关键字生成关键字索引；还有根据文件的内容向量索引，如p s e a r c h 。结构 化拓扑的优点是资源定位准确并且可保证一定的效率，有着良好的可扩展性和性 能，因而适用于对可用性要求高的系统。结构化拓扑的应用领域广泛，包括分布 式存储、应用层组播和名字服务等。但结构化拓扑的维护相对复杂，通常只支持 精确匹配资源搜索，对复杂搜索条件的支持较差。结构化拓扑的p 2 p 系统大都是 全分布式的，如c h o r d l 8 1 、t a p e s t r y 1 2 】和c a n 1 0 】等：也有少部分是部分分布式的， 如b r o c a d e 。 表1 - 1p 2 p 文件共享系统分类 覆盖网络 结构化非结构化 n a p s t e r , 集中式拓扑 m a z e k a 2 a a 混合型拓扑 f a s t t r a c k 集中 e d o n k e y 程度 b i t t o r e n t k a d e m l i a ( o v e r n e t ) c h o r d g n u t e u a 全分布式拓扑 p a s t r y ( p a s t ) l i m e w i r e t a p e s t r y ( o c e a n s t o r e ) m o r p h u s n a p s t r y ( 3 ) 松散结构化拓扑 此类系统介乎结构化和非结构化之间。系统中的每个结点都有分配有虚拟的 逻辑地址，但整个系统仍然是松散的网络结构。文件的分布根据文件的索引分配 到相近地址的结点上。随着系统的使用，文件被多个检索路径上的结点加以缓存。 类似的系统包括f r e e n e t ，f r e e h a v e n 等。相关系统非常强调共享服务的健壮性和安 全性。非结构化拓扑、结构化拓扑和松散结构化拓扑具有不同特点，可分别适用 于不同需求的p 2 p 系统。表2 1 给出了p 2 p 文件共享系统的分类。 很多结构化p 2 p 系统都采用了d h t ( 分布式哈希表) 技术。分布式哈希技术 的核心思想是通过将存储对象的特征( 关键字) 经过哈希运算，得到键值( h a s hk e y ) ， 第5 页 国防科学技术大学研究生院硕士学位论文 对象的分布存储依据键值来进行。在不需要服务器的情况下，每个p e e r 结点负责 一个小范围的路由，并负责存储小部分关键字，从而实现整个d h t 网络的寻址 和存储。从2 0 0 1 年开始，d h t 方法成为p 2 p 资源定位技术研究的重点内容，著名 的d h t 方法包括c h o r d 8 1 、c a n 1 0 1 、p a s t r y 1 1 1 、t a p e s t r y l l 2 1 、k a d e m l i a 13 1 、f i s s i o n e 1 5 】 等。 d h t 方法中同时实现了p 2 p 系统的拓扑构造、消息路由和资源搜索三大功能。 d h t 能够容纳数量巨大的结点数目，并且能不断处理新加入的结点，同时能够妥 善地处理结点离开，具有很好的容错性。将d h t 作为应用层拓扑，可以构建更加 复杂的应用。目前d h t 方法己发展成为一种通用p 2 p 系统架构，基于d h t 方法 的p 2 p 系统在分布式存储、应用层组播、名字服务和数据管理等多个领域都有着 广泛的应用。例如分布式文件系统，点对点文件共享，内容分发系统，协同w e b 缓存，应用层组播，分布式域名解析以及即时消息服务。 1 。1 。3p 2 p 技术面临的挑战 与传统的分布式系统不同，p 2 p 系统可充分利用大量端用户资源，改变了已有 模式中端用户资源闲置的弊端，这是p 2 p 分布式系统能够如此迅速发展的重要原 因。p 2 p 系统资源众多，但是由于p 2 p 系统中通常缺少中央控制系统，结点自由 度较高，给p 2 p 系统的稳定性和可靠性带来了很多新的挑战： ( 1 ) p 2 p 系统通常具有较大的规模。1 9 9 9 年，p 2 p 文件共享系统n a p s t e r 4 s 】 创建，这是p 2 p 时代标志性的事件。此时p 2 p 还不被人熟知，在之后的一年多内， n a p s t e r 用户就增长到5 千万。此后的k a z a a 系统的注册用户曾达到1 5 亿，参与 s e t i h o m e 的计算机数量达到4 8 0 万【删。大量的用户使得p 2 p 系统中共享了海 量的计算、数据、存储和带宽等各类资源，但是也给p 2 p 系统的稳定性带来了很 大挑战。 ( 2 ) p 2 p 系统具有很强的分布性。p 2 p 系统中参与的用户和资源众多，并且 各个结点和各类资源在地理上广泛分布。一般来说，p 2 p 分布式系统在全球广泛分 布。很多p 2 p 系统是完全分布的( 如g n u t e l l a 和c h o r d 等) ，所有结点地位完全 平等，既是客户端也是服务器，系统中没有任何传统意义上的服务器来提供服务； 有些p 2 p 系统中，存在着某种形式的服务器( 如n a p s t e r 等) ，但其中服务器的作 用通常只是用来协调结点间的通信和协作，具体的任务仍然由分布的各结点来完 成。由于p 2 p 系统中通常没有集中控制管理部件对结点的信誉机制、可靠性策略 等工作进行统一部署和规划，资源的可靠性难以保证，给系统的可靠性、稳定性 带来困难。 ( 3 ) p 2 p 系统具有很强的动态性。在p 2 p 系统中，结点可能会由于各种原因 第6 页 国防科学技术大学研究生院硕士学位论文 ( 结点自主意愿或网络连接不稳定等) 随时加入或退出，结点的动态加入与退出 是系统的一种常态。但由于p 2 p 系统中结点可以随意地加入和离开，使得p 2 p 系 统的计算环境难以预知，结点离开或失效等行为较为频繁。即使是在相对稳定的 p l a n e t l a b 实验床中，也有很多明显的由于结点失效造成的扰动( c h u m ) 。据统计【1 5 】， i n t e m e t 上计算机的平均无故障时间约为1 3 小时，即在1 0 0 0 0 个结点的p 2 p 系统 中，平均每2 分钟有一个结点失效。对典型p 2 p 文件共享系统n a p s t e r 和g n u t e l l a 的研究表明，结点加入和退出系统的频率相当高，结点每次平均在线时间只有1 小时。因此p 2 p 应用系统( 如p 2 p 存储系统) 的设计者必须充分考虑结点的动态 性，采用相应的策略来应对结点的短暂或永久的失效。 ( 4 ) 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 技术应能充分考虑结点间的异构性，以提高p 2 p 系统的整体 效能。 由于结点动态性的存在，导致p 2 p 系统失效增加，稳定性下降，影响了p 2 p 系统的服务质量。因此，p 2 p 系统普遍需要解决的闯题是扰动【1 7 1 。 p 2 p 系统的扰动是指结点频繁的加入、离开或者失效的现象。由于结构化p 2 p 系统没有集中的控制，结点由各个用户自主地控制开启或者关闭，用户的随意性 致使结点以很高的频率加入和离开系统。用户的主观随意性和结点被动失效是导 致系统不稳定的两个最主要的因素1 1 7 , 1 9 】。面对这样一个动态的网络环境，p 2 p 系统 需要采用一套有效的方法来处理这些情况。引起p 2 p 系统不稳定的因素有很多， 客观因素源于结点失效、结点负担过重的“热点”问题，主观因素包括恶意攻击、 用户信誉或者p 2 p 系统设计者的疏忽等。对这些错误的避免以及补救，称为“容 错性”。 与非结构化p 2 p 系统相比，结构化p 2 p 系统具有比较严格的拓扑。为适应结 构化拓扑维护的需要，其容错技术在非结构化p 2 p 容错的基础上又需要有新的特 点。因此，结构化p 2 p 技术在带来高效的同时，也给容错技术的研究带来了新的 难题。 1 2 本文的主要工作 本文的主要工作分以下四个方面： ( 1 ) 对结构化p 2 p 系统容错技术进行了总结归纳。 第7 页 国防科学技术大学研究生院硕十学位论文 本文首先概述了结构化p 2 p 系统容错技术的概念和相关问题，并对p 2 p 容错 技术的分类进行了探讨，从系统动态性测量和分析、冗余备份、周期性检测和失 效恢复、结点大量失效与网络分割、容错p 2 p 拓扑结构等五个主要方面，对结构 化p 2 p 系统容错技术的研究现状及成果进行了深入的分析归纳，指出了其中存在 的问题和缺陷，并指出了结构化p 2 p 系统容错技术未来的发展趋势。 ( 2 ) p 2 p 系统结点可靠性评估模型 论文基于人工神经网络算法建立了p 2 p 系统结点可靠性评估模型，从成功服 务次数、网络带宽、在线时间、断线次数、恶意服务五个方面提出p 2 p 系统结点 可靠性的度量框架，对评价p 2 p 系统中结点的可靠性以及多种情况下拓扑中超结 点的选取具有一定的指导意义。 ( 3 ) p 2 p 结点可靠性评估模型实现与测试 本章对基于人工神经网络的p 2 p 系统结点可靠性评估模型进行了实现和测试。 文中模型采用模型化设计，经验证，模型可以迅速收敛，评价精度较高。模型建 立在人工神经网络基础上，具有自组织、自学习、精度高、结果可靠等特点。 ( 4 ) 基于簇备份的结构化p 2 p 系统容错机制 本章介绍基于簇的结构化p 2 p 系统容错机制r s f e 方法。该机制采用硬件 冗余的方式备份p 2 p 系统的结点信息，以实现容错目的。r s f e 在f i s s i o n e 上设计 了相对应的r s f e 路由、结点加入和结点退出算法，可有效的降低p 2 p 系统中结 点的动态性对网络造成的影响，增强了f i s s i o n e 的容错特性，以促进整个p 2 p 系 统更加稳定的运行，降低结点失效对全系统的影响。 1 3 本文的创新点 ( 1 ) 基于人工神经网络的p 2 p 系统结点可靠性评估模型 p 2 p 文件共享系统结点的可靠性评价是p 2 p 系统容错机制中不可缺少的一部 分。论文系统地考虑p 2 p 系统结点可靠性评估的问题，基于人工神经网络算法建 立了p 2 p 系统结点可靠性评价模型。该模型将成功服务次数、网络带宽、在线时 间、断线次数、恶意服务五个方面作为评价指标建立b p 反馈网络，通过自组织学 习可以有效的对p 2 p 系统结点的服务质量及其可靠性进行评价。并且，该模型可 根据需求进行指标及样本的提取，将原来定性的描述和等级划分进行了定量的计 算，模型灵活移植性强；用经典算法b p 对标准样本进行学习，自组织、自学习、 精度高、结果可靠，使模型有很好的数学基础。模型提出的p 2 p 系统结点可靠性 度量框架，对评价p 2 p 文件共享系统中结点的可靠性以以及多种情况下拓扑中超 结点的选取有一定的指导意义。 ( 2 ) 基于簇备份的结构化p 2 p 系统容错机制。 第8 页 国防科学技术大学研究生院硕十学位论文 在结构化p 2 p 拓扑上增加容错机制是p 2 p 系统可靠性的必然要求。本文设计 了基于簇备份的结构化p 2 p 系统容错机制r s f e 方法。r s f e 方法采用硬件冗 余的方式备份f i s s i o n e 的结点信息达到容错的目的。该方法在f i s s i o n e 上设计了 相对应的r s f e 路由、结点加入和结点退出算法，可有效的降低p 2 p 系统中结点 的动态性对网络造成的影响，增强了f i s s i o n e 的容错特性，为整个拓扑更加稳定 的运行、减少失效开销提供了保障。 1 4 本文的结构 本文共分六章。 第一章为绪论，简述了问题的背景，分析p 2 p 系统容错机制面临的挑战和当 前的发展，简述本文的研究内容和组织结构。 第二章概述了结构化p 2 p 容错技术，从结构化p 2 p 技术的兴起、问题的产生 和相关定义、容错技术分类和相关研究等方面进行了论述。 第三章介绍p 2 p 系统结点可靠性评估模型，模型基于人工神经网络的方法， 系统地考虑p 2 p 系统结点可靠性评估的问题。 第四章对p 2 p 结点可靠性评估模型进行实现与测试。 第五章介绍基于簇备份的结构化p 2 p 系统容错机带i - - r s f e 方法。分别介绍在 f i s s i o n e 上设计的r s f e 路由、结点加入和结点退出算法。 第六章总结本文工作，并对未来工作进行展望。 第9 页 国防科学技术大学研究生院硕十学位论文 第二章结构化p 2 p 系统容错技术概述 自上个世纪末开始，p 2 p 系统作为一项新的计算技术成为计算机领域研究和应 用的重要热点。p 2 p 系统在应用层构建了一个具有特定拓扑结构的覆盖网络 ( o v e r l a y ) ，该拓扑网络是整个p 2 p 系统的基础。p 2 p 系统的其他机制如结点命 名、分布散列表、路由定位、负载均衡等，大都是基于其拓扑结构的。很多p 2 p 系统中结点( p e e r ) 之间共享数据，对数据进行管理，这些以前由服务器完成的工 作由分布的各结点来完成。但是由于结点动态性的存在，导致p 2 p 系统失效增加， 稳定性下降，影响了p 2 p 系统的可靠性和服务质量。 2 1 结构化p 2 p 容错问题的产生和相关定义 2 1 1 结构化p 2 p 容错问题产生 在结构化p 2 p 系统设计的初期，高效是最主要的目标。设计者通过研究新的 拓扑加快资源定位的速度，一般以短的网络直径、较少的结点度数和较小的网络 拥塞等为优化目标【1 5 】。在系统稳定的前提下，快速定位与容错这两个目标存在一 定矛盾，因此，在p 2 p 拓扑设计的初期，为了在定位的准确与速度上得到改进， 容错技术很少在设计中加以考虑。但与传统的分布式系统不同，p 2 p 系统具有规模 巨大、分布广泛和动态性强等诸多特点1 8 ，1 2 ，1 5 】，使得p 2 p 系统的稳定性难以保证， 给p 2 p 系统中的资源定位和查找带来了困难。 由于结构化p 2 p 系统没有集中的控制，结点由各个用户自主地控制开启或者 关闭，用户的随意性致使结点以很高的频率加入和离开系统。用户的主观随意性 和结点被动失效是导致系统不稳定的两个最主要的因素1 17 1 9 】。面对这样一个动态 的网络环境，p 2 p 系统需要采用一套有效的方法来处理这些情况。引起p 2 p 系统 不稳定的因素有很多，客观因素源于结点失效、结点负担过重的“热点 问题， 主观因素包括恶意攻击、用户信誉或者p 2 p 系统设计者的疏忽