（计算机应用技术专业论文）基于p2p的分布式存储系统的研究与实现.pdf

哈尔滨工程大学硕士学位论文 摘要 随着i n t e r n e t 的飞速发展，互联网上海量的数据和日益增加的用户给传 统存储技术带来了严峻的挑战。而随着终端系统处理能力的迅速增强和网络 带宽的大幅增加，一种基于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 分布式存储系统。 2 综述基于结构化覆盖网的资源搜索技术研究现状，详细分析p a s t r y 路由协议的结点状态、路由查找和拓扑结构维护等内容；分析完全副本和纠 错码两种冗余方式的特点，对比了多种纠错码的性能，把r a p t o rc o d e 引入存 储系统来实现数据冗余；概述了p 2 p 系统中复杂数据查询技术的研究现状， 分析分布式b + 树的基本操作和节点分布策略，实现了基于分布式b + 树的复 杂数据查询。 3 概述了p 2 p 分布式存储系统的主要功能，说明了系统的逻辑实现框 架和数据组织结构，在详细介绍各个功能模块的设计后通过实验分析了系统 的性能。 ， 最后对本文所做工作进行总结并指出后续的研究方向。 关键词：对等系统；分布式存储；结构化覆盖网；纠错码；数据查询 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e r n e t ，ag r e a td e a lo fd a t aa n dt h e i n c r e a s i n gu s e r sa r eb r i n g i n gs e v e r ec h a l l e n g e st ot r a d i t i o n a ls t o r a g et e c h n o l o g y a tt h es a m et i m e ，w i t ht h et e r m i n a ls y s t e mh a n d l i n gc a p a c i t yh a si n c r e a s e d r a p i d l ya n dt h es u b s t a n t i a li n c r e a s ei nn e t w o r kb a n d w i d t h ，ap e e r - t o 。p e e rb a s e d d i s t r i b u t e ds t o r a g es y s t e md e v e l o p e dr a p i d l y t o d a yp e e r - t o p e e rd i s t r i b u t e d s t o r a g es y s t e mh a sb e c o m ea r e s e a r c hh o t s p o tb e c a u s eo fi t sa d v a n t a g e ss u c ha s h i 曲s c a l a b i l i t y , m a s s i v es t o r a g es p a c e ，h i g hr e l i a b i l i t ya n dh i g ha v a i l a b i l i t ya n d s o0 n p 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 ms t r u c t u r e sd u et oah u g en u m b e ro f n o d e s ，n o d e sd y n a m i c ，h e t e r o g e n e o u ss t r o n gm i s t r u s tb e t w e e nn o d e s ，t h en o d e s w i t hs e l f i s h n e s sa n ds oo nh a sb e c o m ev e r yc o m p l e xa n dd i f f i c u l t i td i dn o t m a t u r es y s t e mf o rc o m m e r c i a lu s e r s t h i sp a p e rd o e ss o m ep r e l i m i n a r yr e s e a r c h o nt h eb a s i ca s p e c t so fp 2 pb a s e ds t o r a g et e c h n o l o g yi n c l u d i n gr e s o u r c es e a r c h ， d a t ar e d u n d a n c ya n dd a t aq u e r y 1 s u m m a r i z et h er e l e v a n tr e s e a r c ho np e e r - t o p e e rs y s t e m ，p o i n to u tt h e m a i nr e s e a r c hc o n t e n to fp e e r - t o p e e rs t o r a g es y s t e m ，a n dg i v ec o m p a r a t i v e a n a l y s i so f t h ee x i s t i n gw e l l k n o w np e e r - t o - p e e rd i s t r i b u t e ds t o r a g es y s t e m s 2 p r e s e n tt h er e s e a r c hs t a t u so fr e s o u r c es e a r c ht e c h n o l o g yb a s e do n s t r u c t u r e do v e r l a y , d e t a i l e da n a l y z et h em a i nc o n t e n to fp a s t r yr o u t ea r i t h m e t i c i n c l u d i n gn o d es t a t e ，r o u t i n ga n dt o p o l o g y sm a i n t a i n ；a n a l y z et h ec h a r a c t e r i s t i c s o fc o m p l e t ec o p yr e d u n d a n c ya n de r a s u r ec o d i n gr e d u n d a n c y ,c o m p a r et h e p e r f o r m a n c eo fav a r i e t yo fe r a s u r ec o d e s ，a n db r i n gr a p t o rc o d ei n t os t o r a g e s y s t e m st oa c h i e v ed a t ar e d u n d a n c y ；s u m m a r i z et h er e s e a r c hs t a t u so fc o m p l e x d a t aq u e r yt e c h n o l o g yi np 2 ps y s t e m ，a n a l y z et h eb a s i co p e r a t i o na n dn o d e d i s t r i b u t i o ns t r a t e g yo fd i s t r i b u t i o nb + t r e e ，a n dr e a l i z ec o m p l e xd a t aq u e r yb a s e d o nd i s t r i b u t e db + t r e e 3 s u m m a r i z et h em a i nf u n c t i o n so fp 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 ， 哈尔滨工程大学硕士学位论文 i l l u m i n a t es y s t e m sl o g i cf r a m e w o r ka n dd a t ao r g a n i z a t i o n a ls t r u c t u r e ，a n a l y z et h e p e r f o r m a n c eo ft h es y s t e ma i t e rg i v ea d e t a i l e di n t r o d u c t i o na b o u te v e r yf u c t i o n a l m o d u l e sd e s i g n f i n a l l y , s u m m a r i z et h ew o r ko ft h i sp a p e r , a n dp r e s e n tt h ep r o s p e c to ft h e 1 a t e l w o r k k e y w o r d s ：p e e r - t o p e e rs y s t e m ：d i s t r i b u t e ds t o r a g e ：s t r u c t u r e do v e r l a y ： e r a s u r ec o d e s ：d a t aq u e r y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本论文的研究做出重要贡献的 个人和集体，均已在文中以明确方式标明。本人完全意识 到本声明的法律结果由本人承担。 作者( 签字) ：主j 垒 日期：2 oo g 年；月f 多e l 哈尔滨工程大学硕+ 学位论文 1 1 课题背景及意义 第1 章绪论 随着i n t e r n e t 规模的不断扩大，文本、图像、音频、视频等大量数据充 斥着网络。如何对海量的数据进行快速、高效和安全地存储和访问，是当前 因特网面临的挑战之一。 数据存储的主流技术是客户机服务器模式，但是这种模式已逐渐不能满 足新的需求【- j 。 首先是数据量的急剧增加。现在i n t e m e t 每时每刻都产生大量的数据， 数据的类型越来越多，单个文件的数据量也越来越大，如软件、视频文件动 辄几十兆，几百兆的电影更是随处可见。这不仅要求存储服务器有海量的存 储空间，而且要求数据存储空间具有较高的可扩展性。 其次，用户对服务质量要求越来越高。互联网的用户数量正以爆炸式的 速度增长，接入速度也有了很大的提高。庞大的用户数量给i n t e m e t 带来的 是高密度、海量的数据请求，而客户机连接速度的提高也使得用户期望更快 更好地获取服务，难以忍受以往过长的服务响应延迟。 另外，用户对数据可靠性的要求越来越高。当前电子商务发展迅猛，许 多企业已实现高度电子化。企业运行过程中产生的大量数据非常重要，这些 数据一旦丢失或损坏，企业将遭受沉重的打击，甚至会陷于灭顶之灾。 由于服务器和客户机在数量上的绝对悬殊，靠单纯提高服务器的软硬件 配置和增加网络带宽已不能满足海量客户机密集而苛刻的请求。另外，服务 器因其固有的部署方式也很容易成为攻击者攻击的对象，一旦服务器瘫痪， 整个系统将崩溃，因而难以保证存储服务的可靠性和安全性。 在服务器性能成为系统瓶颈的同时，一般作为客户机的p c 机性能却有 显著的提高，可以完成以前服务器才能完成的工作。在此情况下，基于对等 方式( p e e r - t o p e e r ，简称p 2 p ) 的存储系统出现并迅速发展起来，成为数据 存储新的研究热点。p 2 p 存储系统具有如下优势： 1 、提供的存储空间更大，信息资源更丰富。系统不仅由能力强大的服务 器构成，任何个人用户也可以参与进来，成为系统中的一个结点，共享自己 哈尔滨工程大学硕十学位论文 的信息资源。海量的结点也带来海量的存储空间，同时系统中资源的种类也 更加丰富，用户通过搜索可以更快捷、更方便地获取所需的信息。 2 、数据的可靠性和可用性更高。p 2 p 系统中大量结点的信息复制导致高 度的冗余，冗余使得网络不会出现“单点失效 问题，从而提高了数据的可 靠性。另外数据在广域网范围内分布，用户不论在什么地理位置，都可以就 近获取信息，其结果是提高了信息的可用性。 3 、实现有效的搜索。常规的w e b 搜索引擎在互连网上搜索并存储信息 量巨大的静态索引信息数据库，其搜索到的信息可能是不存在的。但在p 2 p 网络中，任何节点的信息只有当节点在线的时候才被索引，因此索引信息与 网络状态同步1 2 1 。 1 2 国内外研究现状分析 1 2 1p 2 p 系统概述 目前为止，p 2 p 系统尚未形成统一的定义，但以下两点是公认的p 2 p 系 统的核心特点。 1 、从用户的使用方式来看，系统中每个用户既向其他用户提供资源，也 从其他用户那里获取资源。也就是说，每个结点既是服务器也是客户端。这 里的资源可以是一份文件、一块存储空间、一定量的带宽，也可以是一段时 间内保证质量的c p u 使用权限。总之，p 2 p 系统的本质是参与系统的所有结 点地位对等、互相合作。这与传统的一方提供服务一方享受服务的c s 结构 有着本质的不同。 2 、从体系结构来看，系统采用无中心结构，没有中心结点负责一致性控 制、任务调度、决策仲裁等工作，而是通过参与系统的结点之间充分合作以 完成用户提交的任务。事实上，很多p 2 p 系统的规模都非常大，往往有上百 万结点同时参与。在这种情况下，也很难有结点能够有能力进行中心控制和 全局管理。 除了以上两点之外，很多p 2 p 系统还具有结点数量大、动态性高、异构 性强、分布广泛、结点之间不信任等特点，这些都是传统的在集群或者局域 2 哈尔滨丁程大学硕十学位论文 网范围内实现的分布式系统所不曾面临的问题，也很大程度上增加了p 2 p 系 统设计与实现的难度。 当前，主要的p 2 p 应用系统包含： l 、文件共享系统。每个结点既共享自己的文件给他人，也从其他结点下 载自己感兴趣的文件。 2 、广域网分布式存储系统。每个结点既提供自己的存储空间给他人，也 使用他人的存储空间存储数据，以提高数据的可靠性、可用性和访问效率。 3 、大文件分发及视频直播系统。每个结点既从其它结点处下载数据块或 视频流，也提供上行带宽供他人下载数据。 4 、基于覆盖网的i p 电话系统。每个结点既提供多条与其它结点连接的 通路，也利用其它结点之间的通路通过多跳转发的形式进行i p 通话。 其它的p 2 p 应用系统还包括：应用层多播系统、网页合作缓存服务、基 于对等结构的搜索引擎、新一代域名服务系统等等。总之，人们试图使用对 等结构去解决很多传统问题，并在很多领域获得了成珊，1 。 1 2 2p 2 p 存储系统主要研究问题 p 2 p 存储系统非常复杂，需要研究的问题很多，主要有以下几个方面： 1 、覆盖网及路由协议。任何p 2 p 系统都首先需要一个覆盖网，保证结 点之间的通信，通常p 2 p 存储系统使用结构化覆盖网进行结点通信。结构化 覆盖网的设计首先必须保证消息路由的收敛性，即所有消息都可以通过结点 之间的转发到达目标结点。并且，当结点众多且动态性很高时，结构化覆盖 网还必须维持其连通性、路由收敛性和路由效率。另外，异构性、安全性和 自适应性等也是设计中必须考虑的问题。 2 、结点信息收集。结点需要把数据存放在其它结点上，因此必须要知道 系统中有哪些结点，它们的基本信息如何，然后从中选择合适的结点进行数 据存放和空间交换。显然，对于一个结点而言，收集到的其它结点信息越多， 越容易从中找到合适的结点；但是，由于带宽等能力的限制，大多数结点难 以收集到系统中所有结点的信息。于是，如何设计高效的结点信息收集算法， 使得每个结点可以收集到尽量多的信息就直接影响到数据放置的合理性与高 哈尔滨t 程大学硕士学位论文 效性。另外，结点收集算法还必须保证收集到的信息的及时性，因此当一个 结点的信息发生变化时如何将这个消息准确高效地组播给所有需要知道该消 息的结点就成为结点信息收集算法中的核心问题。 3 、数据放置策略及一致性维护。数据放置一直是分布式系统中的关键问 题，数据是随机放置、按照分布式哈希表放置、还是用两者结合的方法，一 方面决定于数据模式，另一方面也决定于用户如何使用该系统。另外，当数 据有多副本时，如何保证副本之间的一致性又是严峻的问题。由于在广域网 中无法严格保证数据的线性一致性，那么在不同的网络环境下如何保证尽量 强的数据一致性就是需要仔细研究的问题。， 4 、数据维护。通常，为了提高数据的可靠性和可用性都会对数据进行复 制，当数据存有多副本时，就需要对这些副本进行动态管理，其中包括：当 副本减少时，再生出足够多的副本以保证数据的可用性达到用户的要求；当 系统负载不平衡或者出现访问热点时，将某些副本的位置迁移或者再生出一 些新的副本；当系统空闲时，进行副本之间的一致性维护等等。 5 、安全性和私密性。p 2 p 节点来自于不同的组织和用户，节点的加入和 退出是高度动态的，恶意节点针对某个用户攻击时能以一定概率推算该用户 数据的存放节点，他就可以通过对这些节点的攻击达到干扰用户使用的目的。 同时系统中每个用户都可以直接发布信息，随着恶意节点的出现，大量的伪 造数据和欺骗行为会影响p 2 p 的应用，因此在p 2 p 存储服务中，安全性显得 尤为重要。另外，用户把数据存放在其它结点上，实际上是希望利用其它结 点的空间，而不希望存储的数据被对方看到。因此，p 2 p 存储系统必须承担 保护用户隐私的任务。 6 、公平性维护。通常假设p 2 p 结点都是理性结点，尤其在p 2 p 交换系 统中，每个结点都希望把自己的利益最大化，那么它就会在系统允许的范围 内选择尽量让自己多获取、少付出的策略。那么如何保证所有使用其它结点 存储空间的结点都相应地贡献出自己的存储空间、维护交换中的公平性就成 为p 2 p 存储系统面临的新问题。 7 、负载均衡。在p 2 p 存储系统中要有一套负载均衡机制，避免少数结 点负载过重，而其他大部分结点几乎没有负载情况发生，从而使系统正常提 供存储服务。 4 哈尔滨t 程大学硕十学位论文 1 2 3p 2 p 存储系统研究现状 对于基于p 2 p 的存储技术，许多国内外著名的研究机构进行了深入的研 究，并取得重要的成果。然而由于p 2 p 存储系统固有的复杂性，目前还没有 成熟的p 2 p 存储系统出现，基本都是原型系统，主要有： 1 、m i t 的c f s c f s t 4 】是一个只读的文件系统。系统主要分为三个层次：c f s 使用c h o r d 做底层覆盖网络：d h a s h 负责块级别的数据存取，并维护数据冗余；客户端 的文件系统层负责提供文件系统接口与数据块之间的转换。 c f s 客户端将整个文件系统按小数据块的方式组织起来，目录信息存成 一个块，数据文件被分为多个小块存储，并用i n o d e 块来记录数据块之间的 关系。每个小块以都其块数据内容的哈希值为i d 。c f s 的文件系统客户端负 责将数据块最终转换为上层应用需要的只读文件系统接口。c f s 将文件分成 大量的数据块使得可以方便地做负载均衡和处理热点文件的问题。 d h a s h 负责每个小块在系统中的存储。d h a s h 首先将一个数据块做k 个 完全副本，然后用d h t 直接分发的方式将k 个副本顺序的放置在数据块i d 对应的负责节点及后继节点上。当c h o r d 网络检测到有一个副本丢失时，数 据块的主节点负责立即再修复出一个副本。 c f s 底层采用c h o r d 算法；利用副本方式冗余；直接d h t 方式分发冗 余数据；通过底层的覆盖网络来检测邻居节点的失效；采用积极修复的策略。 c f s 通过p 来认证节点，以防止恶意节点的攻击。节点的i d 以其i p 的哈 希值为基础，节点要加入网络时，其邻居节点可以向其号称的i p 地址发请求 以确认其身份，这使得节点很难伪造身份，并且实现基于口的分布式存储配 额管理机制。 系统使用信息发布者的公钥来认证信息发布者对其根目录的更新权限， 以保证数据完整性。数据块的d 使用数据块内容的哈希做d ，也保证了数 据块级别的完整性。另外，c f s 系统支持数据块级别的缓存，而数据块的更 新必然导致新块的i d 的变化，这样被缓存的陈旧副本也就自然失效。当不同 节点的存储容量差异悬殊时，通过在容量大的机器上运行多个c f s 节点来均 衡系统负载。c f s 系统不存在删除操作，其中每个数据都有有效期，用户为 5 哈尔滨工程大学硕+ 学位论文 了保持自己数据的持久存储，需要不断的刷新自己数据的有效期。 2 、b e r k e l e y 的o c e a n s t o r e 及其原型p o n d o c e a n s t o r e t s l 是一个在全球范围内搭建的海量存储池，提供安全可靠的存 储服务。p o n d t 6 j 是o c e a n s t o r e 的原型系统，包含高效的路由、容忍拜占庭错 误的更新协议、基于覆盖网上的广播实现缓存副本的更新、持续地用纠错码 方式存储档案文件等。 1 ) 存储组织 o c e a n s t o r e 的基本数据是对象。数据对象包含了按顺序组织的多个只读 版本。用户可以查看文件或目录的以前版本，并可恢复误删的数据。整个数 据对象用a g i , j i d 来标识，数据的每个版本称为v g u i d 。a g u i d 通过对与 特定应用的名字和所有者公钥的组合进行安全h a s h 得到。包含所有者公钥可 以防止用户间的冲突和简化访问控制。 3 ) 数据放置与路由 o c e a n s t o r e 采用的结构化覆盖网为t a p e s t r y 。o c e a n s t o r e 并不直接使用 d h t 存储实际数据，而是仅仅利用d h t 存储数据指针，也就是实际存储数 据的结点的地址列表。与直接使用d h t 存储数据的方法相比，这种方法在 结点进入、退出时由副本迁移所引发的带宽消耗会小很多。 4 ) 复制策略 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 错误的一致协 议，生成一个统一的操作顺序再把这个顺序广播给所有结点( 包括所有一级 结点和二级结点) ，采用g o s s i p 的方式广播，以保证广播的可靠性。 5 ) 档案存储 o c e a n s t o r e 中的数据分为活动( a c t i v e ) 和档案( a r c h i v a l ) 两种状态。 6 哈尔滨工程大学硕十学位论文 活动状态的数据表示数据的当前状态，拥有一个修改入口。档案数据存储数 据的曾经状态，只可读，不可修改。档案数据用e r a s u r ec o d i n g 的方法编码， 并散布到大量的存储结点上。由于只需要找回其中一定量的编码块就可以重 新恢复数据，因此任何地理局部的灾难都无法造成数据的破坏或丢失。 6 ) 数据对象缓存 e r a s u r ec o d i n g 比较费时，为了避免频繁读的对象进行编码，o c e a n s t o r e 也支持整块的缓存。读取一个块数据时，结点首先向t a p e s t r y 请求块数据本 身，如果得不到则通过t a p e s t r y 取得块的碎片并执行编码得到块数据。在两 种情况下，这个结点接着都会公布自己拥有这个块数据，以后别的结点读该 块数据时将会从该节点获得。p o n d 使用l r u 方式缓存对象。 为了取回一份数据的最新版本，需要利用t a p e s t r y 从对象主备份那取回 一个心跳，心跳里有最新版本的信息。o c e a n s t o r e 通过把二级备份数据组织 成应用层广播树的形式实现它们高效的基于推方式的更新。树的根结点为对 象的主备份，这棵树称为分发树。每次更新时主备份创建一个新版本，并在 分发树上往下发送更新和心跳，因此，更新被直接广播到二级备份上。分发 树是自组织的，每个二级备份利用t a p e s t r y 定位一个附近的已经存在的备份 作为自己的父母结点。 3 、m i c r o s o f t 的p a s t p a s t v j 是一个存储服务系统，向用户提供k e y - v a l u e 对形式的数据存储， 其中k e y 是数据的标识，v a l u e 是数据内容，存储语义非常简单。 p a s t 为用户提供以下几种操作原语： f i l e l d = i n s e r t ( n a m e ，o w n e r - c r e d e n t i a l s ，k ，f i l e ) 该原语将文件存储到p a s t 网络中，k 表示保存到k 个不同的结点。f i l e l d 是1 6 0 位的文件标识符，该文件标识符根据文件名、文件所有者的公钥和一 个随机数用s h a 一1 算法计算。这样可以保证文件标识符在很高的概率下是唯 哈尔滨工程大学硕士学位论文 一的。该原语将记录客户方需要的存储空间( 文件大小的k 倍) 然后为文件 加上一份文件证书，该证书包括f i l e l d ，文件内容的s h a 1 哈希，复制参数k ， 随机数，创建日期和其他些可选参数，证书将用所有者的私钥进行数字签 名。然后文件证书和该文件将以f i l e l d 为目的地址交由p a s t r y 进行路由。i n s e r t 操作中的k 是可以根据可用性要求和文件的访问频度来确定的一个参数。对 于需要经常访问的文件，k 应该取大一些。 f i l e = l o o k u p ( f i l e l d ) 该原语将从p a s t 中获取f i l e i d 所指的文件的一份拷贝。只要保存该文 件的k 个结点有一个可以访问，该原语就可以成功返回相应文件。该操作的 执行过程是结点以f i l e l d 为目的结点发出一条请求消息，只要该消息到达存 储文件的结点，该结点就会给客户结点返回文件和文件证书。 r e c l a i m ( f i l e l d ，o w n e r - c r e d e n t i a l s ) 该原语宣布撤销f i l e l d 表示的文件的k 份拷贝。该原语完成后，p a s t 将 不再保证l o o k u p 操作能够找到对应的文件。该操作和删除操作语义不同， r e c l a i m 操作之后仍然有可能能够检索到相应的文件。 p a s t 直接使用基于p a s t r y 的d h t 进行文件存储。单纯使用d h t 进行 数据放置会出现负载不平衡的问题，因此p a s t 又做了一些负载调整的工作 以提高结点的存储利用率：在存放某文件时，如果根据d h t 的原则该文件 应放置于结点a ，而此时a 的负载过重，就在a 的l e a f s e t 中找一个负载不 是很重的结点放置，在a 上留下放置结点的指针，如果a 的l e a f s e t 中的所 有结点的负载都很重，就在a 的l e a fs e t 的边缘的某结点的l e a fs e t 中寻找 负载不重的结点，这样一直顺着l e a fs e t 寻找，直到找到足以放下该文件的 结点为止。p a s t 的另一个简化是只提供用户个人存储，不允许共享，也就 是说，一个文件只有其所有者可以进行访问，不支持并发访问。这大大简化 了系统设计，因为较之多用户访问，单用户访问的一致性控制简单得多，这 哈尔滨工程大学硕士学位论文 实际上也提高了数据的访问性能。 p a s t 用比较简单的办法来解决安全性问题：有一个专门的公信机构向 p a s t 的所有用户和服务结点发放智能卡( s m a r t c a r d ) ，智能卡中有公信机 构签名的认证，证明其所有者的身份。s m a r t c a r d 中还记录了用户和服务器 之间的每笔交易情况和用户的存储余额等信息，而交易的所有参与方都要对 交易形成的决议进行签名，因此服务方和消费方都不能否认已达成的协议或 者谎称曾达成过某协议。另外，由于使用p a s t r y 协议进行覆盖网路由，就必 须保证p a s t r y 的安全性，p a s t r y 的安全路由算法也因此得以仔细研究。 4 、清华的g r a n a r y g r a n a r y _ 【 j 提供基于对象的存储方式。客户端在g r a n a r y 提供的c l i e n t a p i 的基础上编写，具体的操作主要包括创建类、删除类；创建对象、删除对象、 对象读写；基于对象的数据查询；订阅事件响应。 1 ) 基本数据与加密控制 g r a n a r y 以对象为基本数据单元，对象由若干属性组成。属性是 的三元组，n a m e 是属性名，t y p e 是该属性的类型，当前g r a n a r y 的数据属性可以为浮点数、字符串或二进制数据块三种，v i s i b l e 表明该属性 在存储中是否加密，也就是说是否为系统可见。系统可以针对这些数据进行 数据查询，从而增强用户的访问方式。 2 ) 数据存放与数据定位 g r a n a r y 采用清华大学提出的t o u r i s t 路由算法，这种算法可以根据网络 的动态情况自适应地改变自己的路由表大小，使得网络在稳定环境中获得 o ( 1 ) 的路由效率，而在动态环境中至少保证o ( 1 0 9 n ) 的路由效率。g r a n a r y 采 用完全副本的数据冗余方式，冗余后的数据被g r a n a r y 均匀地分发到网络中 的节点上，以防止相关性错误，冗余数据所在节点的列表以及数据对象的 属性被作为元数据，以d h t 的方式存储在p 2 p 网络中。 9 哈尔滨工程大学硕士学位论文 3 ) 数据复制及数据一致性 对于只有读写操作的系统来说，强一致性意味着用户不会读取到过期数 据：如果在时刻t ，某用户的写操作w 得到成功确认，那么所有在t 之后发 出的读请求都不会获得比w 更早的数据版本。获得强一致性的一个充分条件 是所有备份按照同样的顺序执行它们收到的操作。这个全局l 致的操作顺序 称为t o t a lo r d e r 。在广域网这样的异步网络环境中t 0 t a lo r d e r 无法实现，因 此一般通过实现数据的概率一致性来代替。g r a n a r y 使用g o s s i p 算法与 q u o r u m 算法的结合。 q u o r u m 算法的基本思想是：在复制算法中所有命令都需发往所有的备 份，且在所有备份上被执行，这将影响系统的吞吐率，因此q u o r u m 算法中， 所有写操作都只发往一部分备份( 如m 个备份) ，所有读操作也只发往一部 分备份( 如n 个备份) ，比较这些备份的版本，取版本最新的数据备份。如 果系统中不会发生拜占庭错误，那么只要( m + n ) 比总备份数多，就可以 保证数据一致性，同时提高效率。 4 ) 数据查询 数据查询是g r a n a r y 的独有的功能。g r a n a r y 提供的数据查询类似于对 象数据库的查询，是根据用户给出的对各个属性的限制条件在同类对象中找 出符合条件的，查询语义较强。g r a n a r y 借鉴了数据库中的倒排表、b + 树等 技术，并将其应用到分布环境中。 下表显示了这些系统之间的对比。 1 0 哈尔滨工程大学硕士学位论文 表1 1p 2 p 存储系统对比 环境路由访问模式冗余策略数据放置 c f s 低动态 c h o r d 文件系统副本基于d h t o c e a n s t o r e高动态 t a p e s t r y 对象存储副本纠错码 基于目录 p a s t 高动态 p a s t r y 文件系统副本基于d h t g r a n a r y 低高动态 t o u r i s t 对象存储 副本基于目录 错误检测数据修复 数据更新 访问控制复制方法 c f s 基于覆盖网立即修复新文件创建没有有 o c e a n s t o r e 心跳检测 延迟修复块数据和档 有有 案数据更新 p a s t 新文件创 有有 建，旧文件 删除 g r a n a r y应用层广播基于属性更有有 新 缓存机制安全性 c f s 在查询路径上缓存数据，使结点d 由s h a - 1 对口地址和一个索引得 用l r u 算法维护所有缓存到，攻击者难以控制；文件根目录有签名， 块 文件块有摘要，保证数据完整性 o c e a n s t o r e 请求结点缓存数据，使用能容忍拜占庭错误，采用端到端加密保证 l r u 算法维护数据私密性，数据块互相校验保证完整性 p a s t 在查询路径上缓存数据，使所有用户和结点拥有一个专门的公信机构 用g d s 算法维护发放的s m a r t c a r d ，验证所有者身份。 g r a n a r y 1 3 论文研究内容 本文对基于p 2 p 分布式存储技术的几个方面作了初步的研究，主要研究 内容如下： 1 、分析了p 2 p 分布式存储技术的国内外研究现状，对比分析了现有p 2 p 分布式存储系统的优缺点。 2 、研究基于结构化覆盖网的资源搜索技术，分析并实现p a s t r y 资源搜索 算法。 3 、分析了基于纠错码的数据冗余技术，研究并实现使用r a p t o rc o d e 来 实现数据冗余。 哈尔滨工程大学硕士学何论文 _ i i 鼻i i 宣i 葺i i i _ 宣i _ i i i i _ i i i i 11 1i ei ii1 i i 4 、分析p 2 p 存储系统中复杂数据查询问题，设计并实现了基于分布式 b + 树的复杂数据查询。 5 、设计并实现了一个基于p 2 p 的分布式存储原型系统。 1 4 论文组织结构 论文内容组织如下： 第2 章介绍基于结构化覆盖网的资源搜索技术。详细分析了p a s t r y 路由 协议的结点状态、路由查找及拓扑结构维护等内容。 第3 章介绍基于纠错码的数据冗余技术。对比了几种典型纠错码性能的 基础，着重研究了r a p t o rc o d e 中的预编码和l t 编码技术。 第4 章介绍p 2 p 环境下的复杂数据查询技术。说明了分布式b + 树对复杂 数据查询的支持，分析了分布式b + 树的结点分布策略和基本操作，表明了分 布式b + 树实现数据查询的高效性。 第5 章介绍了系统的设计与实现。说明了系统的基本功能、逻辑实现框 架和文件系统组织结构，详细分析了各功能模块的处理流程，并且通过实验 分析了系统的性能。 最后对本文进行总结，并对未来将要开展的研究进行展望。 1 2 哈尔滨工程大学硕十学位论文 第2 章基于结构化覆盖网的资源搜索技术 2 1 引言 资源搜索是p 2 p 系统最基本的功能，研究如何通过结点间的转发把数据 实际传送到特定结点。搜索是否高效直接影响到系统服务的性能。这里主要 讨论基于结构化覆盖网络的资源搜索技术，这也是目前学术界的默认观点。 结构化覆盖网络的基本思想是将每一个结点的地址通过一个哈希函数映 射为某个空间中的一个点，称为该结点的n o d e i d 。在消息通信时，给定地址 空间的一个点作为消息的目标地址，消息在结点之间不断转发，使得收到消 息的结点的n o d c i d 不断向目标地址逼近，最终到达一个当前所有结点中n o d e i d 离目标地址最近的结点。目前提出的结构化覆盖网主要有：c h o r d 、c a n 、 p a s t r y 等。 c h o r d t 9 1 是m i t 提出的结构化覆盖网。它将结点和数据映射到同一空间， 将数据存储在最接近其h a s h 值的结点上，i d 为k 的文件存放在结点i d 为k 或者 紧邻k 的结点上。如在图2 1 中，m = 6 ，c h o r d 环中1 0 个结点存储着5 份数据。 每个结点有一个f i n g e r 表，起着加快查询的作用，f m g e r - 表有m 行，第i 行存着 ，l + 2 卜1 的后继。如图2 2 所示。路由算法采用类似二分查找的方法，路由查找 的复杂度为o ( 1 0 9 n ) 。 1 3 图2 ic i l d r d 数据与存放结点关系图图2 2 c h o r d 环中结点f i n g e r t a b l e 圉 c a n 州由伯克利和a 他r 催出，通过在现有网络之上抽象出一层覆盖层， 将所有的结点映射到一个虚拟的n 维笛卡尔空间，并为每个结点尽可能均匀分 配一块区域。如m 2 3 所示。在【0 ，l 】x 【0 ，1 】的二维空间，5 个结点各占据一个区 域。在c a n 中，信息咀关键字，数据对( k e y ，v a l u c ) 的形式存储，其中k c y 值通 过两个独立的均匀哈希函数映射至c a n 空间中的一点p ( x ，y ) ，如果p 点属于某 一结点所占据的区域，则该结点实际存储这一关键字，数据对。在d 维空间中， 每个结点维护的邻居结点数目只为2 d ，与系统中所有结点数目n 无关。c a n i 使用贪婪策略不断地接近并最终到达目标结点，其路由的复杂度为o ( d n ) 。 n 。“b 。s v 志。自j n a k o 图23 拥有5 个结点的二维空间示意图 哈尔滨工程大学硕士学位论文 p a s l r y _ 【 u 是微软剑桥研究院和美国r i c e 大学的研究人员提出的结构化覆 盖网，p a s 仃y 中每个结点维护一些指向其它结点的指针，这些指针分为三个部 分：路由表( r o u t i n gt a b l e ) 、近邻结点集( n e i g h b o r h o o ds e t ) 和叶子结点集 ( 1 e a f s e t ) 。 r o u t i n gt a b l e 按照前缀匹配的方式组织，存储着地址空间中较远处结点的 指针，l e a f s e t 中存放的是在地址空间中n o d e i d 离自身最近的陋1 个结点的指 针。n e i g h b o r h o o ds e t 包含一些在网络中离当前结点网络距离很近的结点。 p a s t r y 采用前缀匹配不断增长的路由策略，保证路由在- 1 0 9 占 跳之内完成。 大多数结构化覆盖网是将一些其它的有结构图运用到结构化覆盖网中。 c h o r d 使用的是带弦环；p a s t r y 和t a p e s t r y _ 【1 2 】使用的是p l a x t o n 树；v i c e r o y t ”l 使用 的是蝴蝶网；s k i p n e t t - 4 1 使用的是s k i p 图；k o o r d d l 5 】使用的是d eb r u i j n 图； s y m p h o n f l 6 使用的s m a l lw o r l d 图；等等。这些协议都坚持结点维护指针数不 多、路由在o ( 1 0 9 ) 跳内完成的基本思想。 一些研究者认为o ( 1 0 9 ( n ) ) 跳仍然效率不高，现在的终端结点有能力维护 更多的指针，从而取得更高的路由效率。他们提出一些在一跳或两跳之内完 成消息路由的协议，包括：k e l i p s t n 、o n e - h o p t l 8 】等等。这些协议与前述协议 的根本不同在于它们使用组播或者广播的方式进行指针维护。这种方法较之 显式探测的方法带宽开销小很多，因此结点可以维护非常大量的指针，保证 路由在很少的跳数内完成。 下表显示了几种主要结构化覆盖网的一些特征的对比： 哈尔滨工程大学硕士学位论文 表2 1 几种主要的结构化覆盖网对比【1 9 】 结构化覆盖网 c h o r dc a n p a s t r y t a p e s t r y 单向环d 空多维d 坐标空p l a x t o n 类型网 p l a x t o n 类型网 结构 间间 匹配k e y 与结 使用h a s h 函数把 i n i - d k e y 与结点d 的后 在结点i d 中匹 路由方点d 定 缀 配后缀 法位到坐标空间 中的一个点 系统参n 一结点数n 一结点数目 n 一结点数目n 一结点数目 b 一标志符的比特数b 一基于结点 数目d 一空间维数 ( b = 2 6 ) 标志符 路由复 o ( 1 0 9 n ) i 杂度 o ( d n i ) o ( 1 0 9 口)o ( 1 0 9 口n ) 路由表 大小 l o gn 2 d b l 0 9 8 n + b l 0 9 8 n l o g 口n 结点加 ( 1 0 9 n ) 2 2 d l o g 口nl o g b n 入退出 结点失 o ( 1 0 9 )o ( 1