（计算机软件与理论专业论文）基于p2p的分布式存储研究.pdf

_ ! ! 竺! 塑型! 坐堕坐! ! ! ! 塑型业! 型堡 摘要 对等网( p e e r - t o p e e r ，简称p 2 p ) 技术是2 1 世纪的技术热点之一。p 2 p 的出王见 将互联网的存储模式由以前的“内容位于中心”模式转变为“内容位于边缘”模式， 正适应了宽带互联网和更稳定、更高性能的个人电脑的现状，使得个人电脑重新焕 发活力，大大提高了网络资源的利用率。目前p 2 p 在文件共享、协同工作、对等计 算、搜索引擎、电了商务、在线游戏，即时通信等方面的应用越来越广泛，并显示 了良好的应用前景。 分布式存储以其低成本、容错性强、易于管理、安全性等特性一直受到业界的 青睐。由于p 2 p 网络的发展，基于p 2 p 的分布式存储系统也应运而生并以极大的速 度发展。n i 在快速发展的同时也出现了一些问题，如文件在网络上的分布问题、节 点的负载平衡问题、路由热区问题等。本文在研究了当前已有的基于p 2 p 的分布式 存储系统的基础上提出一种基于完全哈希定址思想和多重选择思想的文件分布式存 储策略。通过文件分布式存储策略的改进提高了网络各节点的负载平衡性能，减少 了路由的热点现象，实现了文件的高效查找性能。 本工作得到了上海市科委发展基金项目“基于对等计算( p 2 p ) 技术的虚拟研 究平台”的支持。本文主要对对等网中的分布式存储进行了有益的探索和实践，做 了以下工作： 1 分析了现有的基于p 2 p 的分布式存储系统。 2 提出了一种基于完全哈希定址和多重选择的文件存储策略。 3 提出两种不同的文件搜索策略。 4 实现一个基于j x t a 的p 2 p 分布式存储系统h i b e r 。 关键词：对等网，分布式存储，完全哈希，多重选择，概率预测，h i b e r 上海大学硕十学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y a b s t r a c t p 2 pi so n eo ft h eh o t t e s tt e c h n o l o g i e si n21s tc e n t u r y i tm a k e st h es t o r a g e - m o d eo f i n t e r n e tc h a n g ef r o m “c o n t e n ta sc e n t e r t o “c o n t e n ta se d g e ”，a n dm e e t st h eb r o a d b a n d i n t e m e ta n di t l o r es t e a d y ，m o r eh i g h p e r f o r m a n c ep c b e c a u s eo fp 2 p , p cr a d i a t e sv i g o r a g a i n ，a n dn e t w o r kr e s o u r c ei s u s e df u l l y ，p r e s e n t l yp 2 ph a sb e e na l r e a d yr e s e a r c h e di n t h ef i e l do ff i l e s h a r i n g ，c o o r d i n a t i o nw o r k i n g ，r e c i p r o c i t yc a l c u l a t i n g ，s e a r c he n g i n e ， e c o m m e r c e ，g a m eo nl i n e ，i n s t a n tm e s s a g i n g ，e t c ，a n dh a so b t a i n e dc e r t a i na c h i e v e m e n t p 2 ph a ss h o w ng o o dp r o s p e c t t h ed i s t r i b u t e ds t o r a g es y s t e mh a sa l w a y sp o p u l a rb yt h et r a d ec i r c l ef o ri t sl o wc o s t p r i c e ，p e r m i s s i o no fm i s t a k e s ，e a s ym a n a g e m e n t ，a n ds e c u r i t ya n ds o o ns i n c ep 2 p s e l e c t r i cn e t w o r kd e v e l o p m e n t ，t h ed i s t r i b u t e ds t o r a g es y s t e mb a s e do nt h ep 2 pe m e r g e s a st h et i m e sr e q u i r ea n dd e v e l o p sa sah i g hs p e e d y e ts o m ep r o b l e m sa r i s ea si td e v e l o p s ， s u c ha st h ed o c u m e n td i s t r i b u t i o np r o b l e m so nt h en e t w o r k ，n o d el o a db a l a n c ep r o b l e m s ， a n dt h ep a t hh o t s p o tp r o b l e m se t c g r o u n d i n go nt h er e s e a r c ho nt h eo r i g i n a ld i s t r i b u t e d s t o r a g es y s t e mb a s e do nt h ep 2 p , t h i sp a p e rp r o p o s e sad o c u m e n td i s t r i b u t e ds t o r a g ep l a n w h i c hb a s e so nt h e c o m p l e t e h a s ha d d r e s s i n gi d e aa n d m u l t i p l e s e l e c t i o ni d e a t h r o u g h o u tt h ea m e l i q r a t i o no ft h ed o c u m e n td i s t r i b u t e ds t o r a g ep l a n ，i td e v e l o p st h e n o d el o a db a l a n c ep e r f o r m a n c ea n dr e d u c e st h ep a t hh o t s p o tp r o b l e m s ，a n da c t u a l i z e st h e e f f e c t i v ed o c u m e n tl o o k u pp e r f o r m a n c e t h i sw o r ki ss u p p o r t e db y “v i r t u a lr e s e a r c hp l a t f o r mb a s e do np 2 p ”，t h ep r o j e c to f s h a n g h a is c i e n c ec o m m i t t e e t h i sp a p e rm a k e sab e n e f i c i a lr e s e a r c ha n dp r a c t i c ei nt h e d i s t r i b u t e ds t o r a g ei np 2 pn e t w o r k ，i n c l u d e s ： 1 a n a l y s ee x i s t i n gp 2 pd i s t r i b u t e ds t o r a g es y s t e m 2 p u tf o r w a r dad i s t r i b u t e ds t o r a g es t r a t e g yb a s e do nc o m p l e t eb a s ha d d r e s s i n gi d e aa n d m u l t i p l es e l e c t i o ni d e a 3p u tf o r w a r dt w od i f f e r e n td o c u m e n tr e s e a r c hs t r a t e g i e s 4 i m p l e m e n tap 2 pd i s t r i b u t e ds t o r a g es y s t e mb a s e d o nj x t a ， k e y w o r d s ：p 2 p , d i s t r i b u t e ds t o r a g e ，c o m p l e t eh a s h ，m u l t i p l es e l e c t i o n ，p r o b a b i l i t yb u d g e t ， h i b e r 上海大学硕士学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名铆签逸日期：塑引4 上海大学硕十学位沦文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 1 1 课题背景 第一章绪论 随着近几年网络技术的发展，由于网络信息量的爆炸增长，已经没有任何一 种服务器或者服务器集群能够存放如此之多的信息或者检索。虽然新的处理器和 存储器的出现不断打破运算速度和存储能力的记录，使得网络上终端的处理能力 大大增强。可是还是有海量的数据积累在少数的计算中心，使得网络服务器超负 荷的工作，大量终端的处理能力却被闲置，这无疑是一种巨大的浪费。 在这种网络背景下，p 2 p 开始显现优势并且崭露头角。p 2 p 把互联网的架构由 集中到分散，再从分散到集中，然后形成了现在这种蜘蛛网式的网络格局。p 2 p 的出现正在深刻而快速的影响瓦联网从今而后的架构：一种由服务享受者的单一 角色向既是服务享受者又是服务提供者的双重角色的转化过程。 随着p 2 p 技术的发展，基于p 2 p 的分布式存储系统也相应地快速发展。e j 前 已经有很多比较成熟的p 2 p 分布式文件存储系统。其中最具典型的有： o c e a n s t o r e 1 1 、p a s t z 1 、f r e e h a v e n 3 j 等文件存储系统。o c e a n s t o r e 和p a s t 都提 供了一种有效的广域网存储模型。o c e a n s t o r e 面向一个更加广义的存储概念，支 持对大量复制的移动数据的串行化更新策略，但更倾向于一个专门的服务模型。 p a s t 是面向一个相对简单而紧凑的概念，试图利用网络中闲置的存储节点建立一 个更加完善的存储语义。f r e e h a v e n 在匿名机制方面做得更为出色，建立了一个 详细的匿名体系用来防止潜在的恶意攻击。 1 2 问题的提出及研究内容 分布式存储系统是p 2 p 系统研究的重要问题之一。对于p 2 p 分布式存储系统有很 多问题需要研究。来自于不同节点的不同文件、数据库信息需要存储在地理上分布 的计算机中，系统必须为这些文件和数据提供统一的数据读写访问接口；数据的访 问需要通过局域网、广域网或者i n t e r n e t ：数据的存储和访问需要保证可靠性；系 统还需要维护副本的一致性，并充分考虑效率和网络的稳定性来选择副本的存放位 置。除存储问题之外，数据或文件的定位、查淘路由等问题也是分布式存储系统要 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 考虑的重要问题。 现有的一些分布式存储系统能很好地实现在p 2 p 网络中的文件分布存储，f u 也存 在些缺陷。 1 、文件副本在网络上存储分布问题 现存的很多基于d h t 的文件存储系统在文件副本的存储上都存在一个主存储节 点，其它文件副本则分布在主存储节点逻辑上邻近的节点上。文件查寻时都要通过 主存储节点，这样容易导致网络中部分节点的负载不均衡。 2 、搜索效率问题 不同的应用产品采用不同的搜索策略，这些搜索策略各有优劣。但没能将多种 资源的搜索应用、可扩展性、高效性和全面性很好的结合起来。 3 、路由热区( r o u t i n gh o ts p o t s ) 问题 在文件查寻上，很多p 2 p 文件存储系统都存在路由热区的问题，即存在部分节 点查寻的时候负载过重。 针对以上的这些问题，本文在现有的p 2 p 网络平台基础上，提出了一种基于完 全哈希定址思想和多重选择思想的文件分布式存储策略及相应的文件查找算法。 1 3 论文安排 第一章，即本章，介绍p 2 p 网络的发展、意义和存在的问题以及论文的研究方向 和主要工作；第二章介绍了p 2 p 网络的特点及相对传统的c s 网络模式的优势。第 三章介绍了分布式存储及基于p 2 p 的分布式存储；分析了当前基于p 2 p 分布式存储 存在的问题。第四章提出了基于完全哈希定址思想及多重选择思想的文件存储策略 及相应的文件查找算法；第五章实现了基于p 2 p 的分布式存储实验系统h i b e r ； 第六章提出了今后需迸一步研究的方向。 r 海大学硕_ _ = 学位沦文 ! 生! ! ! ! g ! 塑! 坐! ! 型! ! ! ! ! ! ! ! 壁! ! 坐型： 第二章p 2 p 网络概述 2 1 对等体到对等体计算模式 p 2 p 模式和c 1 i e n t s e r v e r 模式不同，对等体没有明显的c l je n t 和s e r v e r 之 分，在不同的任务中充当不同的角色。一个对等体往往实现了服务器和客户端的双 重功能。现在，列等计算的规模已经发展到i n t e r n e t ，形成独具特包的对等互联网， 2 1 1p 2 p 的定义 简单的说，对等互联网就是由许多权力平等、自治且相互协作的节点组成，网 络资源分布于各个节点( 所谓节点是指包括了所有具有一定运算功能的设备，如：p c 机，p d a 、甚至是手机等) 川”。 2 1 2p 2 p 发展历程 p 2 p 并不是一种全新的技术。从网络发展史看，p 2 p 是瓦联网整体架构的摹础。 在十年之前，所有的五联刚上的系统都同时具有服务器和客户d l 的功能。当然，后 来发展的那些架构在t c p i p 之h 的软件的确采用了客户机服务器的结构：浏览器 和w e b 服务器，邮件客户端和邮件服务器。但是，对于服务器来说，它们之间仍然 是对等联网的。以e m a 订为例，瓦联嘲上并没有一个邑大的、唯的邮件服务器来 处理所有的e m a i l 而是对等联网的邮件服务器相瓦西作把e m a i l 传送到相应的服 务器r 去。其实，i n t e r n e t 最基本的协议t c p i p 并没有客户机丰u 服务器的概念， 所有的设备都是通讯的平等的一端。 u s e n e t 和f id o n e t 6 】被认为是最早的两个对等的无中心的分布式的典型应用。 在那个时候，i n t e r n e t 规模很小，文件和信息通常只能通过电话线，采用最“原始“ 的点到点的方式进行传送。最明显的特点是：参与数据传输的节点少，而且传输的 速度很慢。 现代p 2 p 技术是分布式计算与现有技术相结合的产物。具有强大的计算能力的节 点以及不断增长的网络带宽，是实现p 2 p 的硬件基础。此外，非技术的原因也加快了 p 2 p 技术的发展：参与p 2 p 的用户既是信息的分享者，也是信息的提供者，这样会更 加激发用户的参与热情。 加激发用户的参与热情。 上海大学硕二 学位论文 2 1 3p 2 p 的三种计算模型 从对等网节点的作用出发，可以把对等网分为三种类型口j ： 1 纯对等结构 这种拓扑的特点是：整个网络没有一台服务器，所有节点完全平等，节点间通 过邻居进行路由和资源访问。这种结构强调网络的容错性和可扩展性。好的路由算 法是保证该系统能够正常运行的前提。典型产品有：f r e e n e t ，g n u t e l l a 等。 2 存在索引服务器( 包含资源列表和用户信息) ，内容分布于边缘。 加入索引服务器的目的是为了快速地寻找节点，在大型网络中，这是一种迅速 定位节点的行之有效的方法。与纯对等结构相比，系统的容错性比较差，索引服务 器一旦出现故障，整个系统将崩溃。典型产品如：n a p s t e r 等。 3 组间纯对等，组内存在索引服务器，内容分布于边缘。 这是种介于l ，2 之间的结构。系统对节点分组( 节点有权随意加入任何一个 组) ，每组都有一个索引服务器记录该组节点的位置信息，组服务器之间采用纯对 等方式访问。这种结构既保证在组内能快速查找信息，又具有一定的容错性。但由 于组内和组间采用了不同的路由方法，因此，系统功能比较复杂。典型产品如：s u n 公司的j x t a 1 等。 2 2p 2 p 模式与c s 模式 2 2 1 c l i e n t s e r v e r 模式概述 c s 模式一般采用面向应用的设计方法( 首先设计一个在单机上运行的通常的 应用程序，再分剖此程序成为两个或多个部分，添加各部分之间的通讯西议，实现 各个部分在不同的计算机上的并行运行，并协作完成应用服务) ，将一个完成特定服 务功能的应用程序分成两类运行于不同主机上的不同部分：客户机部分和服务器部 分。 典型的两层结构的c s 模式常见于数据库应用系统。客户端发送s q l 或h t t p 等命令，并通过网络传送给中央服务器，由d b m s 等资源管理器接收这些请求，取得 相应的数据或进行相应的处理后，再将查询结果或处理结果返回客户端。然而这种 结构存在一些缺陷，例如，如果连接的客户端数目激增，服务的性能将会因为无法 进行负载均衡而大大下降；每一次应用需求的变化，都需要对客户端和服务器的应 上海大学硕十学位沦文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 用程序进行修改，给应用的维护和升级造成极大的不便；此外，大量数据在网络上 传输，将使系统的运行费用增高。 近年来，随若c s 技术的成熟和发展，二层c s 模型己逐渐代替早期的两层c s 模型，成为构筑企业级c s 应用的首选方案，例如b r o w s e r w e b d a t a b a s e 体系机构 就是三层c s 模型的一种特例。 图2 3 经典c s 模式( 在i n t e t n e t 环境中) 在三层结构中，客户端与数据库或其它资源管理器之间加进了一个中间层，即 应用服务进程( a p p l i c a t i o ns e r v i c e ) 。 企业网络 图2 4c s 模式中的三层结构模型 相对于以数据库为中心的两层客户数据库服务器模型，三层结构模型( 客户 应用服务器数据库) 将应用的业务逻辑和用户界面隔离，从而使应用开发人员能专 注于应用核心业务逻辑的分析、规划和设计，快速建立应用系统的核心业务功能原 型。此外，界面表示利业务逻辑的明确划分，也使用户能够有效地管理应用系统。 三层模型将用户交互的表示部分与内部的业务逻辑分开，这样，对业务逻辑的一些 上海大学硕士学位论文 ! 些! ! ! 堡! ! ! 型! ! ! ! ! ! ! ! ! ! ! ! 坚! ! ! 旦坐型堡 修改甚至数据库模式的改动，通常都不会要求客户端的改动。而且，将核也，业务逻 辑组件利表示逻辑及数据层划分开来，可以在服务器级别上非常有效地管理应用的 运行。这种模式可以动态地符理消息流程和服务请求、快速启动和停止服务器、根 据变化的负荷复制服务器、动态地广播、撤消服务器中的服务以及将服务从个服 务器转移到另一个服务器等等。这些对中间层应用服务级别上的管理大大增加了分 布式应用的伸缩性和灵活性。 2 2 2p 2 p 与c s 的比较 1 、内容分布 p 2 p 与c s 之间的最大区别在于内容的分布位置。c s 模式决定了数据是存放在 服务器上，客户向服务器发出请求，由服务器端的服务程序负责获取数据后向客户 端返回。对等网模式不排除服务器和客户端的概念，但每个节点可以同时具有客户 端和服务器的功能，也就是说内容分布于边缘节点。内容分布于边缘节点有两个明 显的优点，即： ( 1 ) 能够共享的信息数量迅速增加。从理论上，能够共享的资源几乎无限。 ( 2 ) 共享的信息范围更广。基于c s 的i n t e r n e t ，能够共享的信息是由各个网站 的编辑人员提供的，一方面他们的人数有限，另一方面，他们最关心的是热 点信息，因此，共享内容涉及的面比较狭窄。而采用对等网，加入对等网的 每个人既是信息的分享者也是信息的提供者，他们能够提供的信息多而广， 可满足各种人的爱好。 2 、共享的范围和能力 采用c $ 结构，网上能够共享的基本上就是数据信息，如：文件，e m a i l 等等。 而采用对等网，能够共享的资源包括：数据信息、c p u 、硬盘空间、存储器等。s e t i h o m e 公司已经开发了利用对等网节点的空闲c p u 时间进行特大型科学计算的产品。 3 、可伸缩性 对等网具有更灵活的伸缩性控制。节点可随时加入或退出对等网，基本不会对 网络的性能产生影响。c s 模式中的服务器一般不能随意退出i n t e r n e t ，加入 n t e r n e t 也需要满足一定的条件，如申请i p 和域名等。而且随着自身网络客户群 的增大，服务器性能要求不断地提高，这都会影响系统的可伸缩性。 4 、容错性 上海大学硕十学位沦文 相比而言，对等网有更强的容错性。由于对等网在数据共享时采用了k 次分布技术， 理论上，只有当所有的k 个节点同时失效时，数据才可能丢失：而基于c s 结构， 如果服务器出现问题，那么存在于服务器的数据将会全部丢失。为增加系统的容错 能力，许多网站，特别是大的门户网站，不得不采用镜像、磁盘阵列等技术，从而 在这方面做出大量的投资。 2 3 小结 本章阐述了p 2 p 的概念以及p 2 p 的历史，分析了目前的p 2 p 的体系结构：并对p 2 p 和c s 计算模型进行了比较。 上海大学硕士学位论文 第三章基于p 2 p 的分布式存储系统 3 1 分布式存储概述 与目前大量应用的集中式存储方式不同，分布式存储并不将数据存储某个或多 个节点上，而是通过网络使用每台机器上的存储空间，并将这些分布的存储资源构 成一个虚拟的存储设备，数据分散地存储于各个角落。 分布式存储的优势主要体现在：( 1 ) 低成本由于使用的是几乎所有系统的空 闲磁盘空间不再需要购买新的硬件设备，从而充分利用存储资源的同时也降低了存 储成本。( 2 ) 容错性强由于数据存储于多台机器，从而可以很轻易地设置存储策 略，使得一个文件中可以在多台机器上存在副本。这样即使某台机器崩溃，其中的 分布式存储数据也可保证不会丢失。( 3 ) 易于管理相对于集中式存储的设备相关 管理方式，由于分布式存储将存储虚拟为一个设备，从而可以方便地设置存储策略， 查看存储资源的使用情况和状态。( 4 ) 安全性高分布式存储能够很方便地实现数 据加密技术，提高数据安全性。 分布式存储主要的实现方法有：( 1 ) 由服务器支持的客户服务器( c s ) 结构： 服务器负责整个分布式存储的管理，客户端在读取分布式存储内容时向服务器发出 文件浏览或定位请求同时也提供本地磁盘空间以供分布式存储系统使用，而服务器 负责文件的检索和存储策略的实现。( 2 ) 基于网络广播的对等方式的分布式存储结 构：通过网络广播来查找文件的宿主机器，而每台机器会定期更新分布式存储系统 的文件列表。( 3 ) 基于p 2 p 的分布式存储结构：每台加入分布式存储系统的机器同 时承担服务器和客户端的责任。在某一时刻总有一台或多台机器担任服务器角色， 而网络会在当前服务器角色不存在时进行服务器选举以确定哪台机器承担服务器角 色。 3 2 基于p 2 p 的分布式存储 由于p 2 p 网络和以往的c s 结构的网络有着本质的区别，基于p 2 p 的分布式存 储系统和传统的基于c s 结构的分布式存储有着很大的区别。由于p 2 p 网络的高动 态性和节点的不可信任性，基于p 2 p 的分布式存储具有其自身特点和要求，丰要体 上海大学硕十学位论文 t h ep o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y 现在以下几方面： ( 1 ) 要求具有良好的扩展性：对于p 2 p 分布式存储系统要求能够透明地增加对等 主机，透明进行扩容：能够安全地删除对等主机，透明地进行缩小容量。 ( 2 ) 要求具有良好的容错性：容错性是指在出现设备故障( 网络故障、机器故障、 刑等中机退出系统) 时整个系统还能正常工作。 ( 3 ) 数据的存储和访问需要保证可靠性，还需要维护副本的一致性，并充分考虑 效率和网络稳定性来选择副本的存放位置。 ( 4 ) 数据或文件定位、查询路由等问题也是要考虑的重要问题。 3 2 1 现有的p 2 p 分布式存储系统 i 、 办作文件系统c f s p l ( c o o p e r a t i v ef i l es y s t e m ) c f s 是一个用于对等网络的只读的存储系统，它可以提供高效率的、鲁棒的和 负载平衡的文件存取功能。c f s 采用了完全的分布式体系结构可以很容易地扩展到 大规模网络。c f s 服务器为存储文件块提供了分布式哈希表d h a s h 。c f s 客户端则 把d h a s h 块看作文件系统。d h a s h 采用文件块粒度进行文件分布和缓存以实现负载 平衡。使用复制技术实现鲁棒性，- 通过服务器选择减少延迟。d h a s h 使用c h o r d 仂 议进行文件块查找。 c f s 文件系统通过把文件块在可用的c f s 服务器之间进行分布实现文件系统的 功能。c f s 客户端软件将把文件块看作文件系统的数据并为应用程序提供通常的只 读文件系统接口。c f s 的软件核心分成两个层次：d h a s h 和c h o r d 。d h a s h 层为客户 端取文件块数据、在服务器之间分发文件块并维护文件块的缓存和复制拷贝。d h a s h 使用c h o r d 分布式查找系统来定位相应文件块对应的服务器。 d h a s h 基于c h o r d 进行文件块的管理。d h a s h 通过把大文件的文件块分布在不同 的服务器上来实现负载平衡。d h a s h 支持预取以减小下载时的延迟。d h a s h 对每个 文件块都进行复制并保存在其他服务器上来提高可靠性。d h a s h 允许对每个服务器 支持的虚拟服务器数量进行配置，这样可以对服务器存储的数据量进行控制。 c f s 实现了分布式的只读的文件存储功能。客户端只能对文件执行读取操作， 而文件的更新操作由少量的文件发行者完成。系统的结构如图3 1 所示。 c f s 客户端软件分为三层：文件系统客户端、d h a s h 存储和c h o r d 查找。每个 c f s 服务器分为两层：d h a s h 存储利c h o r d 查找。c f s 服务器方并不关心文件系统 上海大学硕士学位论文 的语义，它只是提供分布式的块存储操作。 c f sc1ie n t c f ss e r v e 口一c f ss e r v e r ( 图3 - 1c f s 系统结构图) c f s 客户端采用类似于s f s r o 的文件系统格式解释d h a s h 块。如图3 - 2 所示， 每个块或者是文件数据或者文件系统数据，比如目录信息。文件发行者将文件块存 入c f s 系统时，使用每个块内容的哈希值作为块的标识符。然后发行者用他的私钥 对根块进行签名，并用公钥作为根块的标识符将根块存入c f s 系统。客户端使用相 应的公钥来命名文件系统，他们可以使用公钥检查根块的完整性，也可以用内容哈 希值检查文件系统树中其他子结点的完整性：这一策略可以保证客户端看到经过认 证的完整的文件系统。 d a t ab i o c k ( 图3 - 2c f s 客户端数据组织) 对客户端来说，c f s 是只读文件系统，但是发行者可以对c f s 进行更新。发行 者可以更新文件系统的根块，或者使它指向新的数据。实际上，每个发行者对应了 一个文件系统。c f s 通过发行者的公钥对更新操作进行认证。时间戳机制用来防止 多次出现旧的更新。c f s 可以允许在不改变根块标识符的情况下对文件系统数据进 行更新。 c f s 对文件系统的保存是有时间限制的。如果发行者想对数据进行持久存储， 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 则需要定期向c f s 提出存储周期扩展请求。 2 、p a s t i 2 】 p a s t 是基于i n t e r n e t 的，p 2 p 的全球存储应用，它可以提供持久存储、高可用 性、可扩展性和安全性。p a s t 系统由连接到i n t e m e t 的结点组成，每个结点都可以 发出创建或者检索文件的请求，当然也可以路由这些请求消息。另外，结点也可以 参与文件存储。p a s t 结点形成了自组织的重叠网络。创建文件时，文件将被保存 在多个结点上以提供高可用性。p a s t 系统使用p a s t r y 路由机制把客户方发出的请 求可靠地传送到目标结点。客户方发出的检索文件的请求将以很大的可能性发送到 离客户方最近的( 这种远近是基于某种度量的，比如i p 路由的跳数、链路带宽或者 物理距离) 的存放该文件的目标结点。p a s t 中存放的每个文件都对应一个唯一的 标识符。在检索文件之前，客户方必须预先知道文件的标识符( 某些情况下，可能 还需要解密密钥) 。p a s t 并不提供目录查找、密钥分发等服务。 连接到i n t e r n e t 的任何一台主机安装了p a s t 软件后都可以作为一个p a s t 结点。 p a s t 结点可以作为用户的访问点，当然，p a s t 结点还可以参与文件存储和消息路 由等工作。 每个p a s t 结点和每个用户都持有一张智能卡( 当然，只进行只读操作的用户 不需要智能i ) 。每张卡都保存着一对公钥和私钥。卡的公钥由膏的发行者用私钥进 行数字签名。智能 用于牛成和验证各类证书并记录用户的存储配额。当然，不采 用智能 也可以使p a s t 正常运行，但是要想达到和使用智能 相同的安全功能会 使系统更加复杂。作者假定：( 1 ) p a s t 中使用的公钥加密算法和密码哈希算法是 不可破解的。( 2 ) 虽然客户方、结点操作员和结点软件都是不可信任的而且攻击者 可以控制单个p a s t 结点的行为，仍然假定p a s t 电的大多数结点是行为良好的。( 3 ) 攻击者不能控制智能 。 3 、o c e a n s t o r e f 3 o c e a n s t o r e 是一种全球范围内的数据存储基础架构，它可以自动从服务器和网 络的失效中恢复，并可以混合使用新的资源和适应不同的使用范式。 o c e a n s t o r e 由数百万个不同的服务器组成，它们协同工作提供服务。一组这样 的服务器称为一个p o o l 。数据可以自由地在这些p o o l 之间流动，一个数据对象的复 制数据对象可以在任何时间出现在任何地方。由于o c e a n s t o r e 由不可信任的服务器 组成，它利用了冗余和客户方的加密技术提供数据安全保证。在某个时刻，驯使同 时有多个服务器不能正常工作，整个系统仍然可以保证为用户提供稳定的存储服务。 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 另外，由于客户方数据是加密的，服务器不可能知道客户数据的内容。使用 o c e a n s t o r e 的用户需要从某个o c e a n s t o r e 服务提供者( o s p s ) 处购买服务，每个 o s p 都拥有自己的o c e a n s t o r es e r v e r 。o c e a n s t o r e 采用t a p e s t r y 作为底层的路由机 制。 4 、几种系统的比较 p a s t 系统和c f s 系统在负载平衡策略上不同。p a s t 服务器存储的是整个文件， 如果需要保存的是一个大文件，那么整个系统有足够的空间是不够的，服务器必须 有足够的空间。p a s t 通过在查找路径上缓存文件来进行负载平衡。和p a s t 不同， c f s 保存的是文件块。这样可以防止出现大文件造成的存储负载的不平衡。c f s 提 供了虚拟服务器机制来对具有不同的存储容量的服务器进行管理。 o c e a n s t o r e 的目标是提供全球的持久存储系统。它提供了数据保护，允许客户 端更新数据并可以保证持久存储。但是o c e a n s t o r e 为实现这些目标付出了复杂性的 代价。例如，o c e a n s t o r e 采用了b y z a n t i n e 同步协议解决冲突等。o c e a n s t o r e 假定核 心系统是由商业化的服务提供者维护的。 3 2 2 基于p 2 p 分布式存储的冗余策略及负载平衡策略 为了提高查询性能和系统的容错性能，对等网络系统往往需要进行数据的复制。 那么，如何通过数据复制降低延迟并更好地分担负载是需要进一步研究的问题。 建立在大范围网络上的p 2 p 系统对于加入的节点一般没有严格的控制，节点提 供给系统的信息也很少。这样，节点不能证明自己的可靠性，系统也无法加以区分。 p 2 p 分布式存储系统一般通过冗余策略来保证系统的可靠性。冗余是通过牺牲空间来 换取可靠性，对于有着广阔空间潜力的p 2 p 系统是台理的选择。如何组织，管理和搜 索，定位副本是实现p 2 p 分布式存储系统的关键。下面介绍一下分布式存储系统的冗 余策略以及负载平衡策略。 1 、冗余策略 p 2 p 系统通常通过数据的冗余策略来增强系统的可靠性，这对于有着广阔的潜 力的p 2 p 系统是合理的选择。p 2 p 系统的可靠性通常由以下几方面决定：冗余数据 的增加数量；节点的数量及单个结点的可靠度；冗余数据在网络拓扑结构上是如何 组织的。将数据分布存储在不可信任的节点就像通过r a i d 存储方法将数据存储在硬 盘阵列上一样。诞生于1 9 8 7 年的r a i d 其全称为r e d u n d a n t a r r a yo f d i s k s ，磁盘冗 上海大学硕士学位论文 ! 堕! ! 韭! 塑! 坐! ! 竺! ! 堕! ! ! ! ! 堕望坐! ! 皇笪 余阵列，是一种使用多磁盘驱动器来存储数据的数据存储系统，可以使用多种不同 的存储技术来实现不同等级的冗余、错误恢复和性能。类似的在p 2 p 系统中也可以 通过多种方法来实现不同的冗余策略。 i d a 方法：i d a 是由m r a b i n 提出来的数据分割算法。其基本思想是将欲存储 文件数据分割成n 个数据块，其中任意的k ( k - 2 ) 个箱子放球在这种情况下，一些研究表明任意一个箱予最多装 有球的个数变为l o g l o g n l o g d + o ( 1 ) 。这个结论的重要性在于即使提供选择 的值极小，对网络各节点负载均衡也有极大的改善拱际上，当d = 2 时，即只有两个选 择的时候，相比只有一个选择时节点的最大负载值将减少很多。因为每增加一个选择 节点的最大负载值都会缩小固定的倍数。基于这种理论，本文提了一种二重选择的 折中方案，即在每次选择节点进行存储的时候都同时选择两个节点进行比较，选择 负载更小的节点来存储副本。 4 3 c h r s 副本存储策略 c h r s 是基于完全哈希定址思想和多重选择思想的d h t 文件存储策略。所有副 本在网络的全局分布上采用完全哈希定址的思想，即所有副本存储的地址都是通过 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y 哈希函数来定址的。而在具体每一份副本发布的时候则采用多重选择的思想，即对 每份副本发布来说，每次都通过不同的两种哈希函数得到备选的两个可能的存储节 点，然后通过这两个节点上负载的比较，选择负载较轻的节点来进行此副本的存储。 4 3 1c h r s 副本存储算法思想 很多文件副本的存储是由单个用户或小的g r o u p 决定的。c h r s 则不同，所有 副本存储都是通过一种全局统一算法进行副本存储宿主机的定位，并且在选择存储 节点的时候应用二重选择的方式进行节点筛选，选择当前系统中网络负载较小的节 点进行副本存储。 每个要存储的文件都具有关键词k ( 关键词通常为文件名及作者名等) 。所有的 副本存储的主机地址通过两种全局统一的算法决定。如h i ( m ，k ) 和h 2 ( m ，k ) ，其中k 为所需存储的文件的关键词，m 为此副本的索引号，而函数h ( ，) 和h 2 ( ，) 为全 局统一的定址函数，为所有节点所共享，通常为两种不同的哈希函数。( 例如文件f 具有关键词k ，其需要两份副本在p 2 p 网络进行存储。那么，对于第一份副本：有 h l ( 1 ，k ) l jh 2 ( 1 ，k ) 得到两个备选节点，比较这两个节点的当前负载，其中负载较轻 的节点即为文件f 的第一份副本的存储节点；对于第二份副本：有机( 2 ，k ) 和h 2 ( 2 ，k ) 得到两个备选节点，比较这两个节点的当前负载，其中负载较轻的节点即为文件f 的第二份副本的存储节点。) 通过这种定址方法，每个节点都能很容易地知道可能的副本的存储主机位置。 但是对于本地节点来说只知道文件副本可能的存储位置是不够的，我们希望知道副 本的数量或者是离本地节点相对近的副本的存储位置才是关键。为了解决这个问题 c h r s 提出了基于全局的几个副本存储规则，所有的副本存储都必须遵循以下几个 副本存储规则。 4 3 2c h r s 副本存储规则 ( 1 ) 所有的文件副本都必须存储在由全局统一定址函数所得到的丰机地址 上。 ( 2 ) 二重选择原则：即任何副本存储时都通过两种不同的哈希函数得到两个 不同的节点来进行选择存储，选择当前负载较轻的节点作为该副本的存 储节点。 上海大学硕十学位沦文 ! ! ! ! ! ! ! g ! ! ! ! 竺! ! 塑! ! ! ! ! 竺g 堕! ! ! ：! 型堡 ( 3 ) 对于任何一个存储文件都必须至少有一个初始副本( 即索引号为m = j 的 副本) 。 ( 4 ) 对于每一个需要发布的文件的所有非初始副本，只有当索引号为m 1 的 副本存在时，索引号为m 的副本才有可能存在。 ( 5 ) 对于所有的需要发布的文件都不得多于r 个副本( r 为系统预先确定的 文件副本存储的最大值) 以上副本存储规则( 1 ) 是基于完全哈希定址思想的，即所有副本存储节点都由 哈希函数定址来决定。规则( 2 ) 则是基于多重选择的思想，具体每一份文件副本存 储的时候需要考虑到节点负载来进行选择存储。规则( 3 ) 保证了系统中至少存有文 件的副本。规则( 4 ) 和规则( 5 ) 则是为了方便文件的查寻，提高文件的搜索效率。 另外规则还表明：当一个具有r 个副本的文件d ，其所有的副本都被存储于h i ( m ，d ) 或h ：( m ，d ) 所定址的节点上( 其中me 1 ，r 的整数，r 为文件的副本存储数量，d 为 该文件的关键词) 也就是说对于文件发布所需存储的r 个副本的所有的索引值m 是 1 ，r 中所有的连续整数集( 其中包括1 和r ) 。在c h r s 中只有哈希函数h 1 ( ，) 和h 2 ( ，) 以及副本可能的最大数量值是预先定义好的。 4 3 3 c h r s 的副本添加和删除算法 基于以上定义的c h r s 五项副本存储规则，我们提出了相应的副本添加及副本 删除算法。对于文件副本的添加以及删除最n ：要i n - - 点就是要严格遵循上面提到的 文件副本存储的五项存储规则。其具体的算法如下： 1 、副本添加算法 a d d r e p l i c a ( ) r - - n u m r e p l i c a s ( d ) ； 4 在 i ，r 】( r 为系统预定的副本可能的最大数量值) 中进行搜索( 可以采用线