（计算机应用技术专业论文）基于chord的高性能文件存储技术的研究与设计.pdf

浙江大学硕士学位论文 摘要 摘要 网络的迅猛发展、信息化建设的快速推进，电子商务、电子政务、网上银行 等应用系统对存储的要求越来越高。传统的单个计算机存储系统已不能满足这种 爆炸式数据的存储要求，数据的网络化存储已成为近年来存储系统发展的新趋 势。 由于p 2 p 技术具有非中心化、可扩展性强等特点，近年来，基于p 2 p 技术的 分布式存储系统成为了存储系统的研究热点，出现了许多商业化产品及许多学术 成果，如n a p s t e r 、o c e a n s t o r e 、k a z a a 、g r a n a r y 、m a z e 等。这些系统与传统的分 布式系统相比在很多方面都具有明显的特色。 论文主要深入分析当前的分布式和p 2 p 技术，以及这些技术在文件存储系统 的方面的应用；分析当前基于d h t 的一个典型实现c h o r d ，以此模型为基础 提出分布式文件存储系统的网络结构模型，同时结合该模型解决文件的路由定位 和文件服务节点的动态维护等问题：针对文件存储系统的传输模块设计了文件的 传输模型和多源下载过程( 客户端下载文件时，可以从服务器的多个复本中取数 据，同时也可以从先前已经下载过该文件的客户端取数据) ，为了提高文件传输 性能，研究了动态缓冲区算法和文件分布缓存策略；论文的另一个重点是针对分 布式存储系统的负载平衡问题，定义了一个负载度量准则，在该准则基础上提出 了一个基于负载统计的动态负载平衡算法，性能测试数据表明采用该负载平衡策 略后，服务器超载时，负载会从重载服务器转移到轻载服务器达到性能的自动优 化；最后给出了文件存储系统的整体结构、传输模块的详细设计以及系统的实现。 关键词p 2 pc h o r d 文件存储动态缓冲区分布式缓存负载平衡 浙江大学硕士学位论文 a b s t r a c t w i t ht h e r a p i dd e v e l o p m e n t o fn e t w o r ka n di n f o r m a t i o nc o n s t r u c t i o n , e c o m n l e t c e ，e - a d m i n i s t r a t i o n ，i n t e m e tb a n k i n ga n do t h e ra p p l i c a t i o ni n c r e a s i n g l y d e m a n do nd a t as t o r a g e t r a d i t i o n a ls i n g l ec o m p u t e rs t o r a g es y s t e mc a nn o tb e s a t i s f i e dw i t l ls u c ha l le x p l o s i o no f d a t as t o r a g er e q u i r e m e n t s i nr e c e n ty e a r s n e t w o r k d a t as t o r a g eh a sb e c o m ean e wl r e n df o rs t o r a g es y s t e m i nr e c e n ty e a r s , d u et ot h ec h a r a c t e r i s t i co fp 2 pt e c h n o l o g yl i k ed e c e n t r a l i z a t i o n , s c a l a b i l i t y , d i s t r i b u t e ds t o r a g es y s t e mo np 2 pt e c h n o l o g yb e c o m eah o tr e s e a r c hi n s t o r a g es y s t e m a sar e s u l t ，m a n yc o m m e r c i a lp r o d u c t sa n da c a d e m i ca c h i e v e m e n t a p p e a r e d ，s u c h 髂n a p s t e r , o c e a n s t o r e ，k a z a a , g r a n a r ya n dm a z e 4 2 0 m p a r et o t r a d i t i o n a ld i s t r i b u t e ds t o r a g es y s t e m , t h e s es y s t e m sh a v em o r ef e a t u r e si nm a n y a s p e c t s t l l i sp a p e ri n - d e p t ha n a l y z e sc u r r e n td i s t r i b u t e da n dp 2 pt e c h n o l o g y , a n dt h e s e t e c h n o l o g i e s a p p l i c a t i o ni nf i l es t o r a g es y s t e m a n a l y z eat y p i c a ld h ti m p l e m e n t - - b o r d d e s i g nan e t w o r ks t r u c t u r em o d e lo f d i s t r i b u t e df i l es t o r a g es y s t e mb a s e do n t h i sm o d e l w i t l lt h i sm o d e l w es o l v ef i l er o u t i n ga n dl o c a t i n g , d y n a m i c a l l y m a i n t a i n i n go ff i l es f f r v e rn o d e s a i m e da tt r a n s p o r tm o d u l eo ff i l es t o r a g es y s t e m ，w e d e s i g n e dt r a n s p o r tm o d e la n dm u l t i s o u r c ed o w n l o a dp r o c e s s ( w h e nc l i e n t sd o w n l o a d ， w ec a r lg e td a t af r o ms e v e r a l 船- t v e r s ，a n da l s oc a nf r o mc l i e n t sw h i c ha l r e a d yf i n i s h e d d o w n l o a d i n g ) i no r d e rt oi m p r o v ef i l et r a n s p o r tp e r f o r m a n c e ，w er e s e a r c h e dd y n a m i c b u f f e ra r i t h m e t i ca n dd i s t r i b u t e dc a c h es t r a t e g y a n o t h e rh i g h l i g h to ft h i sp a p e ri s s o l v i n gt h ep r o b l e mo f l o a d i n gb a l a n c eo f d i s t r i b u t e df i l es t o r a g es y s t e m w jd e f i n e da l o a dm e a s u r e m e n tc r i t e r i a , b a s e do nt h i sc r i t e r i ad e s i g n e dal o a d i n gb a l a n c ea r i t h m e t i c t h ed a t ao fp e r f o r m a n c et e s ti n d i c a t e st h a tu s e st h i s1 0 a db a l a n c i n gs t r a t e g y , w h e n s a l v e ri so v e r l o a d e d ，l o a dt r a n s f e rf r o mh e a v es e r v e rt ol i g h ts e r v e ra n da u t o m a t i c a l l y r e a c ht oab e s tp e r f o r m a n c es t a t e f i n a l l y , w eg i v et h ew h o l ea r c h i t e c t u r eo ft h i sf i l e s t o r a g es y s t e m ，t h ed e t a i lo f d e s i g no f t r a n s p o r tm o d u l ea n di m p l e m e n to f t h i ss y s t e m k e y w o r d sp 2 p 、c h o r d 、f i l es t o r a g e 、d y n a m i cb u f f e r 、d i s t r i b u t e dc a c h e 、l o a d b a l a n c i n g 浙江大学硕士学位论文 图目录 图目录 图2 1m = 3 且系统中只有四个可用节点时数据存储位置的分布1 3 图2 - 2m = 6 且系统中只有8 个可用节点时f i n g e r 表的状态1 5 图2 3 文件存储系统的网络模型1 6 图3 1 文件存储系统传输模型2 2 图3 - 2 多源分块文件下载模型2 4 图3 3 动态缓冲区模型。2 8 图3 - 4 分布式缓存体系结构3 0 图4 1 同一个客户端在不同线程数下传输一个2 m 大小文件的情况4 2 图4 2 同一个客户端在不同线程数下传输一个2 0 m 大小文件的情况4 3 图4 3 四个c l i e n t 同时从单个服务器下载一个1 0 0 m 大小文件的情况。4 4 图4 _ 4 通过负载转移提高文件传输性能情况4 5 图5 1 文件存储系统架构4 6 图5 2 文件传输协议的全过程。4 8 图5 3 文件传输时t a s k l n f o 交互过程4 9 。 图5 4d a t a l - l e a d 交互过程，交互每次传输的文件块位置和大小5 0 图5 5b u f f e r 相关类图5 l 图5 - 6i o s t r e a m 相关类图5 2 图5 7p r o t o c o l 相关类图5 3 图5 8 服务器的启动过程。5 4 图5 9 客户端上传文件过程5 5 图5 1 0 客户端下载文件过程5 6 1 1 1 浙江大学硕士学位论文 表目录 表目录 表2 1 节点n 的变量定义 表2 2 文件元数据表结构 表4 - 1 针对负载平衡的文件元数据表结构 表4 - 2 测试机配置 i v 1 4 1 7 4 0 4 1 浙江大学硕士学位论文第1 章绪论 第l 章绪论 1 1 背景和意义 随着网络的迅猛发展，信息数字化的日益加深，有人预言不久的将来所有的 信息都将数字化，这意味着海量的数据需要存储。显然，传统的单个计算机存储 系统己不能满足这种爆炸式数据的存储要求，数据的网络化存储成了近年来存储 系统发展的新趋势，大量s a n i 、n a s 2 等网络存储设备蜂拥出现，并被市场 广泛接受。网络存储使得存储与计算脱离，对于存储系统的各方面技术的专门研 究开辟了更大的空间；另一方面，高速网络的迅猛发展和普及也为网络存储提供 了底层支持，使大规模远距离的网络存储系统成为可能。然而，当前的文件存储 系统并没有完全满足人们对于存储的需要，在易用性、可靠性、安全和性能等方 面的表现欠佳。 从总体发展方向看，分布式文件存储系统的研究成为当前文件数据存储领域 的焦点。它的目标在于有效地利用网络中众多结点上空闲的存储空间提供超大容 量、高可靠、高性能的数据存储服务。随着p 2 p 技术的发展，对许多领域都产生 了深远的影响，特别是基于p 2 p 的分布式存储领域更是成为当前研究的热点。近 年来，该领域无论是商业化产品还是学术成果都如雨后春笋般地出现，国外以 n a p s t e r 3 、o c e a n s t o r e 4 1 、g a z a a 5 为代表，国内以g r a n a r y 、m a z e 为代表。这 些系统与传统的分布式系统相比在很多方面都具有很大的优势，比如：服务器的 非中心化，节点的可扩展性强，数据的隐蔽性和健壮性好，并且易于达到负载均 衡等特点。 本项目以浙江省重大科技攻关项目为依托，针对浙江省信息数字化的迅速发 展，电子商务、电子政务、网上银行等对存储的要求越来越高，传统的大规模集 中式的存储方式存储设备价格高、维护难，已经无法满足网络应用的迅速发展的 现状而研究与设计。分布式网络存储是下一代存储的发展方向，可以将网络上闲 置的存储空间有效的集中利用起来，通过大量廉价的p c 做集群，降低存储成本。 本项目在已有的关于中间件的研究成果之上，研究分布式的文件存储模型，其目 的在于提供一个文件服务的中间件平台，最终形成一个拥有自主知识产权的文件 服务器，这对提高我省企业的竞争力，促进中间件技术水平有着实际的意义。 浙江大学硕士学位论文 第l 章绪论 1 2 文件存储系统的发展现状与趋势 1 2 1 集中式文件存储系统 n a s 和s a n 是文件存储系统行业主流的两种集中存储的技术。两种技术均 将存储与使用存储的系统分离，利用网络实现连通及共享，从而达到存储设备统 一使用、统一管理，具有良好的可扩充性。通过合理的、动态的空间划分达到空 间的最合理使用，减少扩容的盲目性和降低不必要的扩容成本。通过设备共享和 统一管理，减少存储设备的维护和升级的复杂度，降低运行成本，提高维护效率。 1 n a s n a s ( n e t w o r k a t t a c h e ds t o r a g e ) ，网络附加存储。它被定义为一种特殊的专用 数据存储服务器，内嵌系统软件，可提供跨平台文件共享功能。n a s 设备完全以 数据为中心，将存储设备与服务器彻底分离，集中管理数据，从而有效释放带宽， 大大提高了网络整体性能，也可有效降低总成本，保护用户投资。 2 s a n s a n ( s t o r a g e a r e a n e t w o r k ) ，存储区域网络。通过特定的互连方式连接的若干 台存储服务器组成一个单独的数据网络，提供企业级的数据存储服务。s a n 是一 种特殊的高速网络，连接网络服务器和诸如大磁盘阵列或备份磁带库的存储设 备，s a n 置于l a n 之下，而不涉及l a n 。利用s a n ，不仅可以提供大容量的存 储数据，而且地域上可以分散，并缓解了大量数据传输对于局域网的影响。s a n 的结构允许任何服务器连接到任何存储阵列，不管数据置放在哪里，服务器都可 直接存取所需的数据。 1 2 2 分布式文件存储系统 分布式文件系统已经发展了2 0 余年，并且取得了巨大的成功，典型的系统有： n f s 6 1 ，a f s 、c o d a 、x f s 等。这些系统的主要功能是：支持用户在一定网络范 围内对一定数量的分布文件进行透明访问。随着i n t e r a c t 的出现，人们研制了面 向i n t e r a c t 的分布式文件系统，例如：j a d e ，u f o ，a l e x 和w c b f s 等，支持用户 在i n t e r n e t 范围内对一定数量的分布式文件进行透明访问。 文件系统以n f s 和a f s 最具代表性，它们对以后的文件系统设计也具有十分 重要的影响。 1 n f s n f s 从1 9 8 5 年出现至今，已经被移植到了几乎所有主流的操作系统中，成为 2 浙江大学硕士学位论文 第1 章结论 分布式文件系统事实上的标准。n f s 利用u n i x 系统中的虚拟文件系统机制，将 客户机对文件系统的请求，通过规范的文件访问协议和远程过程调用，转发到服 务器端进行处理；服务器端在v f s 之上，通过本地文件系统完成文件的处理，实 现了全局的分布式文件系统。s u n 公司公开了n f s 的实施规范，互联网工程任务 组将其列为征求意见稿，这很大程度上促使n f s 的很多设计实现方法成为标准， 也促进了n f s 的流行。 2 a f s 1 9 8 3 年由c a r n e g i em e l l o n 大学设计开发的a f s 将分布式文件系统的可扩展 性放在了设计和实现的首要位置，并且着重考虑了在不安全的网络中实现安全访 问的需求。它在位置透明、用户迁移、与已有系统的兼容性等方面进行了特别设 计。a f s 具有很好的扩展性，能够很容易地支持数百个节点，甚至数千个节点的 分布式环境。同时，在大规模的分布式文件系统中，a f s 利用本地存储作为分布 式文件的缓存，在远程文件无法访问时，依然可以部分工作，提高了系统可用性。 后来的c o d af i l es y s t e m 、i n t e r - m e z z of i l es y s t e m 都受到a f s 的影响，更加注重 文件系统的高可用性和安全性，特别是c o d a ，在支持移动计算方面做了很多的研 究工作。 1 2 3 基于p 2 p 的文件存储系统 1 2 3 1p 2 p 简介 对等网络( p e e r - t o - p e e r ，简称p 2 p ) 是一种网络模型，在这种网络中所有的 节点是对等的，各节点具有相同的责任与能力并协同完成任务。对等点之间通过 直接互联共享信息资源、处理器资源、存储资源甚至高速缓存资源等，无须依赖 集中式服务器或资源就可完成。在文件共享、分布计算、协同工作、搜索引擎、 p 2 p 平台等很多方面都有广泛的应用。目前，对于p 2 p 没有一个统一的定义，简 单说来，p 2 p 就是系统之间通过直接互连，来共享计算机资源和服务。这些资源 包括信息资源、内存、c p u 时间、缓存、磁盘存储空间以及硬盘驱动器处理周期 等等。 p 2 p 并不是互联网出现后才被引申出来的一项全新网络技术，早在几年前互 联网出现的时候p 2 p 就已经应运而生，但是由于当时互联网的发展并不是像今天 这样普及，而且在网络建设( 如带宽、处理能力) 和相关的硬件器材上并不能够 满足p 2 p 的需求，因此在几年的互联网发展过程中也衍生出来了许多中间产物。 p 2 p 只不过是不同于c s 和b s 等传统模式的新型通信技术，它最大的特点是抛 浙江大学硕士学位论文 第1 章绪论 开了应用服务器的束缚，使网络非中心化。在p 2 p 模式当中，p e e r 之间可以直接 互连。对于每一个p e e r ，它既可以作为客户机，又可以作为服务器，使得传统意 义“服务器”的概念被削弱了。应用p 2 p 技术把桌面p c 机和网络连接起来，使 用户或企业单独没有能力完成的任务，能够借用网上的共享资源来实现。 p 2 p 是一种分布式网络，网络的参与者共享他们所拥有的一部分硬件资源( 处 理能力、存储能力、网络连接能力、打印机等) ，这些共享资源需要由网络提供 服务和内容，能被其它对等节点直接访问而无需经过中间实体。在此网络中的参 与者既是资源提供者，又是资源获取者。 文献【7 】详细介绍了p 2 p 的拓扑结构，根据拓扑结构的关系可以将p 2 p 研究分 为4 种形式：中心化拓扑( c e n t r a l i z e dt o p o l o g y ) 、全分布式非结构化拓扑 ( d e c e n t r a l i z e du n s t r u c t u r e dt o p o l o g y ) 、全分布式结构化拓扑( d e c e n t r a l i z e d s t r u c t u r e dt o p o l o g y ) 和半分布式拓扑( p a r t i a l l yd e c e n t r a l i z e dt o p o l o g y ) 。 1 2 3 2p 2 p 的特点 本节将讨论运用p 2 p 技术实现的系统将会具有的特点：非中心化、可扩展性、 隐私性、健壮性和高性能等。这些特点是影响p 2 p 系统和应用的主要因素。 1 非中心化 基于c s 结构的传统模型中，数据的存储和处理都在中心服务器上进行，存 取数据也要通过请求应答方式来实现。这样的系统在访问权限控制和安全管理方 面有一定的优势，也必然存在系统性能瓶颈问题，而且整个系统是否正常运行都 建立在该中心服务器是否正常运行的基础之上。采用p 2 p 技术，网络中的资源和 服务分散在所有节点上，信息的传输和服务的实现都直接在节点之间进行，可以 无需中间环节和服务器的介入，避免了可能的瓶颈。即使是在混合p 2 p 中，虽然 在查找资源、定位服务或安全检验等环节需要集中式服务器的参与，但主要的信 息交换最终仍然在节点中间直接完成。这样就大大降低了对集中式服务器的资源 和性能要求。p 2 p 的非中心化基本特点，带来了其在可扩展性、健壮性等方面的 优势。 2 可扩展性 在传统的c s 架构中，系统能够容纳的用户数量和提供服务的能力主要受服 务器的资源限制。为支持互联网上的大量用户，需要在服务器端使用大量高性能 的计算机，铺设大带宽的网络。为此机群、c l u s t e r 等技术纷纷上阵。在此结构下， 集中式服务器之间的同步、协同等处理产生了大量的开销，限制了系统规模的扩 4 浙江大学硕士学位论文第1 章绪论 展。而在p 2 p 网络中，随着用户的加入，不仅服务的需求增加了，系统整体的资 源和服务能力也在同步地扩充，始终能较容易地满足用户的需要。即使在诸如 n a p s t e r 等混合型架构中，由于大部分处理直接在节点之问进行，大大减少了对服 务器的依赖，因而能够方便地扩展到数百万个以上的用户。而对于纯p 2 p 来说， 整个体系是全分布的，不存在瓶颈。理论上其可扩展性几乎可以认为是无限的。 p 2 p 可扩展性好这一优点已经在一些得到应用的实例中得以证明，如n a p s t e r ， g - n u t e l l a ，f r e e n e t 等。 3 隐私性 随着互联网的普及和计算存储能力飞速增长，收集隐私信息正在变得越来越 容易。隐私的保护作为网络安全性的一个方面越来越被大家所关注。目前的 i n t e m e t 通用协议不支持隐藏通信端地址的功能。攻击者可以监控用户的流量特 征，获得m 地址。甚至可以使用一些跟踪软件直接从i p 地址追踪到个人用户。 在p 2 p 网络中，由于信息的传输分散在各节点之间进行而无需经过某个集中环节， 用户的隐私信息被窃听和泄漏的可能性大大缩小。此外，目前解决i n t e m e t 隐私 问题主要采用中继转发的技术方法，从而将通信的参与者隐藏在众多的网络实体 之中。在传统的一些匿名通信系统中，实现这一机制依赖于某些中继服务器节点。 而在p 2 p 中，所有参与者都可以提供中继转发的功能，因而大大提高了匿名通讯 的灵活性和可靠性，能够为用户提供更好的隐私保护。 4 健壮性 在互联网上随时可能出现异常情况，网络中断、网络拥塞、节点失效等各种 异常事件都会给系统的稳定性和服务持续性带来影响。在传统的集中式服务模式 中，集中式服务器成为整个系统的要害所在，一旦发生异常就会影响到所有用户 的使用。而p 2 p 架构则天生具有耐攻击、高容错的优点。由于服务是分散在各个 节点之间进行的，部分节点或网络遭到破坏对其它部分的影响很小。而且p 2 p 模 型一般在部分节点失效时能够自动调整整体拓扑，保持其它节点的连通性。事实 上，p 2 p 网络通常都是以自组织的方式建立起来的，并允许节点自由地加入和离 开。一些p 2 p 模型还能够根据网络带宽、节点数、负载等变化不断地做自适应式 的调整。 5 高性能 性能优势是p 2 p 被广泛关注的一个重要原因。随着硬件技术的发展，个人计 算机的计算和存储能力以及网络带宽等性能依照摩尔定理高速增长。采用p 2 p 架 构可以有效地利用互联网中散布的大量普通节点，将计算任务或存储资料分布到 5 浙江大学硕士学位论文第1 章绪论 所有节点上。利用其中闲置的计算能力或存储空间，达到高性能计算和海量存储 的目的。通过利用网络中的大量空闲资源，可以用更低的成本提供更高的计算和 存储能力。 1 2 3 3 国内外p 2 p 研究现状 随着n a p s t e r 、k a z a a 、b t 、e m u l e 这样的基于p 2 p 技术的文件共享软件在 i n t e m e t 上迅速传播，p 2 p 技术在国际国内都引发了研究的新热潮。国外开展p 2 p 研究的学术团体主要包括p 2 p 工作组( p 2 p w g ) 、全球网格论坛( g g f ) 以及各 高校的研究小组。p 2 p 工作组成立的主要目的是希望加速p 2 p 计算基础设施的建 立和相应的标准化工作。p 2 p w g 成立之后，对p 2 p 计算中的术语进行了统一， 也形成相关的草案，但是在标准化工作方面工作进展缓慢。目前p 2 p w g 已经和 g g f 合并，由该论坛管理p 2 p 计算相关的工作。g g f 负责网格计算和p 2 p 计算 等相关的标准化工作。 从国外公司对p 2 p 计算的支持力度来看，m i c r o s o f t 公司、s u n 公司和i n t e l 公 司投入较大。m i c r o s o f t 公司成立了p a s t r y 项目组，主要负责p 2 p 计算技术的研 究工作，目前开发了基于p a s t r y 的多种应用，包括s c r i b e 、p a s t 、s q u i r r e l 等。在新一代的w i n d o w sv i s t a 操作系统中，也增加了最新的p 2 p 研究成果来支 持协同工作。在2 0 0 0 年8 月，i n t e l 公司宣布成立p 2 ps e 作组，正式开展p 2 p 的 研究。工作组成立以后，积极与应用开发商合作，开发p 2 p 应用平台。2 0 0 2 年i n t e l 发布了n e t 基础架构之上的a c c e l e r a t o rk i t ( p 2 p 加速工具包) 和p 2 p 安全a p i 软件包，从而使得微软n e t 开发人员能够迅速地建立p 2 p 安全w e b 应用程序。 i b m 公司也开展了基于p 2 p 技术的研究，提出了s m a r t n e t w o r k i n g ，另外i b m 公 司大力支持的网格计算( g r i dc o m p u t i n g ) 与p 2 p 计算在许多方面研究类似。 s u n 以j a v a 技术为背景，开展了j x t a 项目。j x t a 是基于j a v a 的开源p 2 p 平台，任何个人和组织均可以加入该项目。因此，该项目不仅吸引了大批p 2 p 研 究人员和开发人员，而且已经发布了基于j x t a 的即时聊天软件包和搜索引擎。 1 a 定义了一组核心业务：认证、资源发现和管理。在安全方面，j x t a 加入了 加密软件包，允许使用该加密包进行数据加密，从而保证消息的隐私、可认证性 和完整性。在j x t a 核心之上，还定义了包括内容管理、信息搜索以及服务管理 在内的各种其它可选j x t a 服务。在核心服务和可选服务基础上，用户可以开发 各种j x t a 平台上的p 2 p 应用。 近年来国内对p 2 p 技术也有相当深入地研究。m a z e 是北京大学网络实验室 6 浙江大学硕士学位论文 第1 章绪论 开发的一个中心控制与对等连接相融合的对等计算文件共享系统，在结构上类似 n a p s t e r ，对等计算搜索方法类似于g n u t e l l a 。网络上的一台计算机，通过安装运 行m a z e 的客户端软件自由加入和退出m a z e 系统。每个节点可以将自己的一个或 多个目录下的文件共享给系统的其他成员，也可以分享其他成员的资源。m a z e 支持基于关键字的资源检索，也可以通过好友关系直接获得。g r a n a r y 是清华大 学自主开发的对等计算存储服务系统。它以对象格式存储数据。另外，g r a n a r y 设计了专门的节点信息收集算法p e e r w i n d o w 的结构化覆盖网络路由协议t o u r i s t 。 p p l i v e 是一款用于互联网上大规模视频直播的共享软件。它使用网状模型，有效 解决了当前网络视频点播服务的带宽和负载有限问题，实现用户越多，播放越流 畅的特性，整体服务质量大大提高。 1 2 3 4 基于p 2 p 的存储系统 基于p 2 p 的文件存储系统按照其假定的系统环境可分为两大类： 1 共享型系统 对于文件共享系统认为系统的运行环境有极多的节点存在，每个节点能力较 弱( 如p c 机) ，节点的稳定性差，可能随时发生意外事故，系统结构变化频繁， 节点的进入和退出每时每刻可能在发生。文献【8 】给出了一个共享型系统的研究， 典型案例如：n a p s t e r ，b t ，k a z a a ，e m u l e 等。 n a p s t e r 是最早的实用化p 2 p 系统之一，主要用来进行文件共享，但它仍然是 一个集中式的系统。n a p s t e r 实质上并非是纯粹的p 2 p 系统，它通过一个中央服 务器保存所有n a p s t e r 用户上传的音乐文件索引和存放位置的信息。这种集中性 质为开放性的共享系统提供了强大的管理能力。当某个用户需要某个音乐文件 时，首先连接到n a p s t e r 服务器，在服务器进行检索，并由服务器返回存有该文 件的用户信息；再由请求者直接连到文件的所有者传输文件。n a p s t e r 首先实现了 文件查询与文件传输的分离，有效地节省了中央服务器的带宽消耗，减少了系统 的文件传输延时。这种方式最大的隐患在中央服务器上，如果该服务器失效，整 个系统都会瘫痪。当用户数量增加时，n a p s t e r 的系统性能会大大下降。另一个问 题在于安全性上，n a p s t e r 并没有提供有效的安全机制。在n a p s t e r 模型中，一群 高性能的中央服务器保存着网络中所有活动对等计算机共享资源的目录信息。当 需要查询某个文件时，对等机会向一台中央服务器发出文件查询请求。中央服务 器进行相应的检索和查询后，会返回符合查询要求的对等机地址信息列表。查询 发起对等机接收到应答后，会根据网络流量和延迟等信息进行选择，和合适的对 浙江大学硕士学位论文第1 章绪论 等机建立连接，并开始文件传输。 2 存储型系统 文件存储系统要求节点能力强，每个节点本身就是一个大的存储服务器，节 点较多，但比文件共享系统要少很多，节点稳定性强，由于节点本身就是专用于 提供服务的服务器，因此在正常情况下保持7 * 2 4 小时的服务，除非发生系统错 误或者网络错误，系统结构变化不频繁，节点不会经常出入系统。文献【9 】给出了 一个存储型系统的设计，这方面比较成功的系统有o c e a n s t o r e ，p a s t 和f r e e h a v e n 。 o c e a n s t o r e 和p a s t 都提供了一种有效的广域网存储模型。它们的底层都建立 了一个代价上限为l o g ( n ) 的路由策略。o c e a n s t o r e 第一次提出了p 2 p 存储系统的 构想，并对其中的一些主要问题提出了解决方案。o c e a n s t o r e 是以t a p e s t r y 为路 由和查找基础设施的p 2 p 平台，它是一个适合于全球数据存储的p 2 p 应用系统。 o c e a n s t o r e 是一个在全球范围内搭建的海量存储池，向用户存储服务，尤其针对 那些移动终端，例如一些嵌入式设备。用户可以在任何时候、任何地点、通过任 何设备接入i n t e r n e t ，并访问存储在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 中占用的存储空间付费，存储的 个人数据保证安全，不会泄漏给其他用户，也不会泄漏给系统管理员。当然，用 户可以赋予其他用户访问其个人数据的权力。通过使用复制和缓存技术， o c e a n s t o r e 可提高查找的效率。p a s t 则是面向一个相对简单而紧凑的概念。它采 用p a s t r y 提供的路由机制，试图利用网络中闲置的存储节点建立一个更为完善的 存储语义。p 2 p 的系统都强调匿名机制，但无疑f r e e h a v e n 在这方面做得更为出 色。它建立了一个详细的匿名体系，用来防止潜在的恶意攻击。 1 3 课题研究的研究背景与内容 本论文研究的大背景是浙江省重大基础软件产品开发专项“基础中间件 平台的研制及其产业化”课题。该项目的整体目标是在应用软件平台化的背景和 趋势下，面向制造业信息化、服务业电子化、电子商务、电子政务等应用领域， 结合浙江省制造业信息化、服务业电子化工程及国家8 6 3 项目，全面采用先进、 成熟的计算机技术及最新研究成果，整合浙江省软件企业资源，开发中间件软件 平台产品，实现浙江省中间件产品的跨越式发展，为浙江省多数软件开发商提供 平台支撑，辐射广大应用软件开发商，提升浙江软件企业的层次和水平，增强浙 8 浙江大学硕士学位论文 第1 章绪论 江软件企业的核心竞争力。 本文的研究的主要内容是是分析当前的分布式和p 2 p 技术，以及这些技术对 文件存储系统的发展产生的影响；同时研究当前基于d h t 模型中的一个典型模 型c h o r d 的数据路由与定位以及节点的动态维护等，并且在c h o r d 的基础之 上研究设计了分布式文件存储系统的系统架构；针对该文件存储系统提出了文件 数据传输模型和传输协议，同时针对传输性能研究设计了动态缓冲区算法和分布 式缓存技术；文章的另一个重点是针对分布式系统的负载平衡问题，提出了一个 基于负载平衡的动态负载平衡算法，并对该算法进行了性能测试。 1 4 文章的章节组织 本文内容共分七章，第一章是“绪论”，第二章至第五章是本文的主要内容， 第六章是“总结与展望”。 第一章绪论 介绍本论文的研究背景、意义和主要内容，对文件存储系统的发展现状与趋 势做了简要的概述，同时对p 2 p 技术作了详细介绍。 第二章文件存储系统的网络结构设计 本章首先对c h o r d 协议作了详细介绍，包括c h o r d 协议的一致性哈希和数据 的路由与定位，接着提出了本文的文件存储系统的网络模型，并讨论了文件的数 据路由和定位问题，最后描述了文件存储系统中节点的动态维护过程。 第三章文件存储的传输性能研究 本章重点研究了如何在分布式件存储系统中提高文件传输性能。包括传输模 型和多源分块下载的设计，动态缓冲区算法的研究以及分布式缓存技术的应用。 第四章基于负载统计的负载平衡策略 本章主要研究如何在基于c h o r d 的文件存储系统中实现负载平衡。首先介绍 了传统的负载平衡算法和p 2 p 负载平衡算法，接着定义了一个负载度量准则，并 在该准则基础上提出了一个基于负载统计的动态负载平衡算法，并对该算法进行 了性能测试。 第五章文件存储系统传输模块的设计与实现 本章给出了文件存储系统的整体系统结构，并针对传输模块设计了传输协议， 最后简要介绍了与传输模块相关的类图以及系统的实现。 第六章总结与展望 9 浙江大学硕士学位论文第1 章绪论 对论文的工作进行了回顾、总结，并对后续工作进行了展望。 1 5 本章小结 本章对论文的研究背景、研究意义和研究内容做了总体介绍。对文件存储系 统的发展历程、现状和趋势作了简要的介绍，同时对p 2 p 技术的概念、特点和发 展现状也做了概要描述。最后给出文章的主要内容及章节安排。 1 0 浙江大学硕士学位论文 第2 章文件存储系统的网络结构设计 第2 章文件存储系统的网络结构设计 随着p 2 p 技术的深入研究及应用，国内外有相当多的文件存储系统采用了p 2 p 技术。这些存储系统都必须依靠一种底层网络协议，这层网络被称为o v e r l a y n e t w o r k ，这层网络都具有定位和路由功能。早期的构建这层网络结构的方法比 较简单，比较成功的典型案例是n a p s t e r ，它通过一个中央服务器保存所有该拓扑 结构上的节点以及n a p s t e r 用户上传的音乐文件索引和存放位置的信息。c m u t e l l a 作为一个p 2 p 共享系统，采用了全分布非结构化的拓扑结构构建了底层网络。 本章在结构化全分布拓扑结构模型c h o r d 【l o 】的基础之上提出了文件存储 系统的网络结构模型，并结合c h o r d 讨论了文件的路由定位和文件服务节点的动 态维护问题。 2 1c h o r d 协议 2 1 - 1c h o r d 协议的发展历程 在结构化p 2 p 系统中，每个节点只存储特定的信息或特定信息的索引。当用 户需要在p 2 p 系统中获取信息时，他们必须知道这些信息( 或索引) 可能存在于 那些节点中。由于用户预先知道应该搜索哪些节点，避免了非结构化p 2 p 系统中 使用的泛洪式查找，因此提高了信息搜索的效率。但是，结构化p 2 p 也引入了新 的问题：既然信息是分布存储的，那么如何将信息( 或索引) 分布存储在重叠网 中的节点上以及由于节点动态的加入和离开重叠网，如何将拓扑的变更信息( 或 索引) 通知其它节点。 d h t 的引入基本解决了上述问题，d h t 全称叫分布式哈希表，是一种分布式 存储方法。在不需要服务器的情况下，每个客户端负责一个小范围的路由，并负 责存储部分数据，从而实现整个d h t 网络的寻址和数据存储。分布式哈希算法 的核心思想是通过将存储对象的特征( 关键字) 经过哈希运算，得到键值( h a s h k e y ) ，对象的分布式存储依据键值来进行。基于这种思想产生了各种不同的d h t 模型，如c h o r d 1 0 、p a s m ： 1 1 、c a n 1 2 、t a p e s t r y 1 3 ，其中c h o r d 是应用比较 广泛的d h t 模型。 c h o r d 协议是在2 0 0 1 年由麻省理工学院提出，其核心思想就是要解决在p 2 p 应用中遇到的基本问题：如何在p 2 p 网络中找到存有特定数据的节点。c h o r d 专 浙江大学硕士学位论文 第2 章文件存储系统的网络结构设计 门为结构化p 2 p 应用设计，考虑了在p 2 p 应用中可能遇到的特殊问题。c h o r d 使 用一致性哈希作为哈希算法。在一致性哈希协议中并没有定义具体的算法，在 c h o r d 协议中将其规定为s h a - i 。c h o r d 的主要贡献是提出了一个分布式查找协 议，该协议可将指定的关键字( k e y ) 映射到对应的节点( n o d e ) 。从算法来看， c h o r d 是相容散列算法的变体，m i t 的g r i d 和r o n 项目则提出了在分布式广域 网中实施查找资源的系统框架。c h o r d 的路由程序被看作为一维的网格定位系统 ( g l s ) ，gl s 是依靠其的真实地理信息来路由其的查询，c h o r d 把节点映射到一个 虚拟的一维空问，其路由算法非常类似g r i d 。 2 1 2 一致性哈希 c h o r d 采用一致性哈希作为数据路由和定位的基础，一致性哈希利用基本的 哈希函数给每个节点和对象一个m 位的标识符。每个节点要维护一些资源信息， 即( k e y ，v a l u e ) 对，k e y 决定存储的目标节点，v a l u e 则是存储在目标节点的信 息，可以是内容的索引( 如该对象所在节点的l p 地址) ，也可能是内容本身( 如 文件中的一个片段) 。节点标识符( n o d ei d ) 可以通过对节点的m 地址进行散列 得到，类似地，对象的标识符( o b j e c ti d ) 可以是对象某个属性的散列。节点进行 信息的插入和查找时，同样也是对关键字哈希，