（计算机科学与技术专业论文）面向海量数据的副本定位与副本放置技术研究.pdf

国防科学技术大学研究生院学位论文 摘要 随着数字化革命和网络技术的飞速发展，i n t e m e t 上的数据量呈现出指数增长 的趋势，大量的数据密集型应用会产生海量的数据，如何有效存储管理i n t e m e t 上 的海量数据，已经成为研究的热点问题之一。在海量数据管理中采用数据复制技 术能够减少访问延迟，提高数据可用性，降低结点失效。在研究海量数据及现有 的海量数据管理系统的基础上，对海量数据的特点和海量数据管理系统进行了总 结和分析。从副本定位和副本放置两个方面对海量数据管理中的数据复制技术进 行了深入研究。 针对结构化p 2 p 系统中常用的d h t 定位技术的重叠网拓扑与底层网络拓扑不 一致以及存在网络热点问题等不足之处，提出了基于几何空间划分的层次式d h t 定位方法( h l s p ) 。h l s p 采用基于坐标的网络距离预测技术g n p ，构建基于地 理邻近性的重叠网拓扑；构造基于地理范围的层次式d h t ，把数据对象的位置信 息存放到网络中具有某种逻辑层次关系的多个结点上；在此基础上对资源进行发 布、撤消和查找，采用一种贪婪算法向前转发消息，并对结点加入和离开时导致 的局部结点邻居列表变化进行动态维护。模拟实验结果表明，h l s p 方法是一种有 效的d h t 定位方法，基于地理邻近性的重叠网拓扑解决了重叠网拓扑与底层网络 拓扑不一致的问题，基于地理范围的层次式d h t 能够消除网络热点并且实现高效 查找。 针对满足延迟限制的副本放置问题，提出了基于延迟估算的动态副本放置算 法( d l d r p ) ，d l d r p 中副本总是被放置在满足副本请求结点延迟限制范围内的 结点上。d l d r p 首先设计了一个抽象的几何模型，通过该模型来确定候选副本结 点所处的区域，从而将副本放置问题转变成在几何空间中求解满足某些条件限制 的区域位置的问题；然后根据新副本结点上的负载来源情况动态调整副本放置： 在某个结点上新增副本或者合并多个旧副本。模拟实验结果表明，d l d r p 能够满 足客户端延迟限制，减少数据访问响应时间，实现副本个数最小化，副本分布均 匀且结点负载平衡。 主题词：海量数据数据复制副本定位副本放置d h t 方法延迟估算 第i 页 国防科学技术大学研究生院学位论文 a b s t r a c t w i t ht h eh i s h - s p c e dd e v e l o p m e n to f d i g i t a lr e v o l u t i o na n dn e t w o r kt e c h n o l o g y ，t h e s c a l eo fd a t as e t si ni n t a m e tp r e s e n t sat r e n do fe x p o n e n t i a lg r o w t h al a r g en u m b e ro f d a t a - i n t e n s i v ea p p l i c a t i o n so f t e np r o d u c em a s s i v ed a t a , w h i c h n a k e si tb e c o m ea r e s e a r c hh o tt h a th o wt os t o r ea n d 瑚a i 擅_ g em a s s i v ed a t ae f f e c t i v e l yi ni n t o m e t d a t a r e p l i c a t i o nc a l lr e d u c ea c c e 8 5l a t e n c y , i m p r o v ed a t aa v a i l a b i l i t ya n dd e p r e s sn o d ef a i l u r e r a t ei nm a s s i v ed a mm a n a g e m e n t i nt h i sp a p e r , b a s e do nt h er e s e a r c ho fm a s s i v ed a t a a n de x i s t i n gm a s s i v ed a t am a n a g e m e n ts y s t e m s ，t h ef e a t u r e sa r es u m m a r i z e da n d a n a l y z e d ，a n dr e p l i c al o c a t i o na n dr e p l i c ap l a c e m e n ta r cs t u d i e d o n eo ft h es h o r t c o m i n g sf o rp o p u l a rd h tl o c a t i o nt e c h n o l o g i e si ns t r u c t l l r e dp 2 p s y s t e m si st o p o l o g i c a ld i s p a r i t yb c t 、 r e no v e r l a ya n du n d e r l y i n gn e t w o r k s ，a n o t h e ri s t h ep r o b l e mo fn e t w o r kh o t s p o t ah i e r a r c h i c a ld h tl o c a t i o nm e t h o db a s e do n g e o m e t r i c a ls p a c ep a r t i t i o nc a l l e dh l s pi sp r o p o s e da c c o r d i n gt ot h a t h l s pu t i l i z e s g l o b a ln e t w o r kp o s i t i o n i n g ( o n p ) t oc o n s t r u c to v e r l a yn e t w o r k so nt h eb a s i so f g e o g r a p h i c a lp r o x i m i t y h l s pd e s i g n sh i e r a r c h i c a ld h t b a s e do ng e o g r a p h i c a ls c o p e s ot h a tl o c a t i o ni n f o r m a t i o no fd a t ao b j e c t sc a nb ed i s t r i b u t e do ns e v e r a ln o d e sw h i c h m e e ts o m e1 0 9 i c a lh i e r a r c h yi nn e t w o r k h l s po f f e r ss e v e r a lo p e r a t i o n st od a t ao b j e c t s ， s u c ha so b j e c tp u b l i s h , w i t h d r a wa n dq u e r yo p e r a t i o m1 1 1 ea c t u a lp a c k e tf o r w a r d i n gi n h l s pi sb a s e do n ag r e e d ya l g o r i t h mg u i d e db yad e s t i n a t i o nc o o r d i n a t es t a m p e di nt h e p a c k e th e a d e r h l s ps u p p o r t sd y n a m i cm a i n t e n a n c eo f l o c a ln o d e - n e i g h b o r l i s t sa l t e r e d w i t hn o d e o i n j n go rl e a v i n g 1 1 ”s i m u l a t i o nr e s u l t ss h o wt h a th l s pi sa ne f f e c t i v e d h tl o c a t i o nm e t h o d , a n do v e r l a yt o p o l o g yb a s e do ng e o g r a p h i c a lp r o x i m i t yc a l l r e s o l v et o p o l o g i c a ld i s p a r i t yb e t w e e no v e r l a ya n du n d e r l y i n gn e t w o r k s ，a n dh i e r 耻c h i c a l d h tb a s e do ng e o g r a p h i c a ls c o p ec 缸a v o i dn e t w o r kh o t s p o t sa n da c h i e v eh i g h e m c i e n ts e a r c h e s w h e ni tc o m e st or e p l i c ap l a c e m e n tp r o b l e mu n d e rl a t e n c yc o n s t r a i n t s ，ad y n a m i c l a t e n c yd r i v e nr e p l i c ap l a c e m e n ta l g o r i t h mc a l l e dd l d r pi sp r o p o s e d , i nw h i c h r e p l i c a sa r ea l w a y sp l a c e do nt h en o d e s t h a ta r eu n d e rl a t e n c yc o n s t r a i n t s i nd l d r p ，i t f i r s tg i v e s 姐a b s t r a c tg e o m e t r i cm o d e lf o l l o w i n gw h i c ht h er e 百o i l so fc a n d i d a t e r e p l i c a sa r ed e t e r m i n e d i nt h i sw a y , t h ep r o b l e mi st r a n s f o r m e di n t oh o wt og e tt h e r e g i o nt h a tm e e t ss o m er e s t r i c t i v ec o n d i t i o n si ng e o m e t r i cs p a c e a f t e r w a r d s , d l d r p a d j u s t st h ep l a c e m e n t so fr e p l i c a sd y n a m i c a l l ya c c o r d i n gt ot h el o a ds o n r e eo fn e w r e p l i c a , t h a ti s , an e wr e p l i c ai sa d d e di nac e r t a l nn o d eo rs e v e r a l 谢s t i n gr e p l i c a sa r e m e r g e d 1 1 1 cs i m u l a t i o nr e s u l t ss h o wt h a td l d r p c a l lm e e tt h ed e l a yh o u n do fc l i e n t e f f e c t i v e l y , r e d u c ea c c e s sl a t e n c y ，m i n i m i z et h en u m b e ro fr e p l i c a sa n da c h i e v ea u n i f o r md i s t r i b u t i o no f r e p l i c a sa n d1 0 a db a l a n c eo f n o d e s 第i i 页 国防科学技术大学研究生院学位论文 k e yw o r d s ：m a s s i v ed a t a ，d a t ar e p l i c a t i o n ，r e p l i c al o c a t i o n ，r e p l i c ap l a c e m e n t ， d i s t r i b u t e dh a s ht a b l e ( d h t ) ，l a t e n c ye s t i m a t i o n 第i i i 页 国防科学技术大学研究生院学位论文 图目录 图2 1 重叠网拓扑与底层网络拓扑之间的差异。9 图2 2 集群和集群树 图2 3 动态模型复制算法流程图1 2 图2 4b m m e t 的几何空间模型1 4 图2 5 确定界标的坐标1 4 图2 6 确定普通主机的坐标 图3 1 指针数据结构。 图3 2 对邻近副本的跳跃查询。 图3 3 对象的发布、撤消及查找操作。 1 5 图3 4 兄弟指示器在对象查找树中的体现 图3 5 点p 到子空间最近的点口+ 图3 6 结点加入时子空间的分裂 图3 7 结点离开时子空间的合并 图3 8c a n 与地理邻近性的重叠网延迟伸展对比 图3 9 对象副本数v s 邻近因子 图3 1 0 不同服务请求数的指针结点所占比例 图4 1 二维空间中的区域及其权值 2 8 2 8 2 9 3 0 3 1 3 2 3 3 3 7 图4 2 结点区域集合q 和副本结点区域集合q 例的区域表示4 1 图4 _ 3 超载的副本结点6 图4 4 新负载为空时副本结点的选取4 3 图4 5 旧负载为空时副本结点的选取4 4 图4 6 新旧负载皆不为空时副本结点的选取4 5 图4 7 副本合并后的位置4 5 图4 8d l d r p 与e m o 任务执行时间对比4 8 图4 9d l d r p 与e m o 产生的平均副本数对比4 8 图4 1 0d l d r p 与e m o 的负载均衡性对比。4 9 第页 国防科学技术大学研究生院学位论文 表目录 表3 1 对象发布算法2 3 表3 2 对象查找算法2 5 表3 3 改进后的对象发布算法 表3 4 改进后的对象查找算法 表3 5c a n 与地理邻近性的重叠网延迟伸展对比 表3 6 对象副本数v s 邻近因子 表3 7 不同请求频率下的指针结点服务数 表4 1 副本放置候选区域选择算法 表4 2o p t o r s i m 任务配置表 2 6 2 7 3 2 3 3 3 4 4 2 4 7 第页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：亘自瀣量熬堂鲍割奎宝焦生型奎兹量篡洼珏窒 学位论文作者签名：秘上峰l 日期： 咖年5 月，罗日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存，汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：亘自连量熬塑鲍割奎塞焦量副奎筮星篡洼纽塞 学位论文作者签名：陛 违 日期：铆舌年6 月，7 日 作者指导教师签名：主：盔墨日期：年乡月日 国防科学技术大学研究生院学位论文 第一章绪论 近年来，由于数字化革命和m e t 的发展，数据集容量呈爆炸式增长趋势， 现有的数据管理系统已不能满足数据密集型应用处理海量数据的需求。海量数据 呈现的新特点带动了海量数据管理系统的研究。数据复制技术作为数据管理技术 中一种提高系统可靠性和系统性能的重要手段，在海量数据管理中的应用尤其重 要【l 。海量数据的诸多特性，如数据量大、广域分布以及异构等，给数据复制技 术带来新的挑战。海量数据的复制技术研究具有重要的理论意义和应用价值。 1 1 海量数据管理 目前，许多的数据密集型应用，如石油勘探、核模拟、气象、地球科学、高 能物理学、医学、化学工业、材料科学、生物科学、环境研究、武器制造、战场 仿真、作战指挥等领域的数据量都已经达到t b 级，很快将达到p b 级。例如欧洲 原子能研究机构c e r n 中在2 0 0 5 年投入使用的大型强子对撞机l h c 【4 1 ，它是人类 历史上最强大的粒子加速器。在l h c 上进行的实验有大约1 5 0 家科研机构的2 0 0 0 多人共同参与，每年产生的数据量达到了1 p b 左右。 1 1 1 海量数据的特点 海量数据的主要特点可归纳为以下几个方面： 数据对象海量且广域分布。在数据密集型应用中，除了数据对象的数目具 有海量的特点外，数据对象的规模也很大，而且这些数据广泛的分布于广 域网络的各个结点上。 数据对象种类繁多且格式复杂。在数据密集型应用中，对于不同的需求， 需处理的数据对象的种类多种多样，而且不同种类的数据对象具有不同的 数据格式，甚至同一类型的数据对象也存在多种格式。 数据对象存储资源多样，管理方法不统一。这些数据密集型应用集成了多 种技术，每种技术涉及不同的行业标准，因此数据对象的格式标准也多种 多样，数据管理技术也很不统一，比如：有文件系统、数据库系统和专用 的管理系统等多种数据管理方法。 1 1 2 海量数据管理系统 针对海量数据的诸多特点，许多著名的公司和研究机构开发了一系列的海量 数据管理系统，以适应数据密集型应用的需求。根据其采用的关键技术不同，大 国防科学技术大学研究生院学位论文 致可以分为下面几种较为典型的系统： 1 、p 2 p 计算环境中的海量数据管理系统 p 2 p 计算( 也称为对等计算或对等网络) 是通过模仿人类社会中人到人 ( p e r s o n - t o - p e r s o n ) 的交流方式而提出的一种新的网络计算模式。当前对p 2 p 计算 并没有严格的定义，多数定义突出了p 2 p 模式与c s 模式的主要区别，即p 2 p 网 络中无专门的服务器，计算结点在功能上是对等的。传统的c s 计算模式在应用 层采取集中控制，由服务器提供服务并对客户端进行控制；而p 2 p 网络中各个结 点( p e e r ) 在应用层是逻辑对等的，各个结点之间可以直接进行数据通信而不需要 通过中间的服务器，每个结点同时充当其它结点的服务器和客户。 基于p 2 p 计算环境的海量数据管理系统主要有o c e a n s t o r e 3 、c f s 【5 】、p a s t 6 j 等。 o c e a n s t o m ：o c e a n s t o r e 是加州大学伯克利分校j o l i nk u b i a t o w i c z 等人开发的 一个项目，它是最早提出的p 2 p 海量数据管理系统。o c e a n s t o r e 的目的是提供 全球范围的持久数据存储，为普适计算环境下的各种终端提供存储服务，也可 用于其它海量数据存储，如科学数据的分布存储等。o c c a n s t o r e 采用t a p e s t r y 重叠网进行数据定位，进而使用了简化的b l o o mf i l t e r 算法提高数据定位的速 度。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 并不直接使用t a p e s t r y 存储实际数据，而是仅仅 利用它存储数据指针，也就是实际存储数据的结点的地址列表( 通常一份数据 会有多个副本) ，数据与其存放结点之间没有任何必然的联系。 c f s ( c o o p e r a t i v ef i l es y s t e m ) ：c f s 是m i t 开发的一个文件系统，是一个只 读分块的存储共享系统。c f s 能够平衡服务器负载，为客户端快速找到数据， 还能够在服务器失效概率很高的情况下保证数据的可用性。c f s 构建在c h o r d 之上，c h o r d 将所有结点组织成一种虚拟环，在环上进行数据定位和复制。c f s 使用静态复制和动态缓存相结合的方法：首先，c f s 将数据复制k 份，放在距 离源结点最接近的k 个后继结点上。其次，在结点间有数据访问请求产生时， 采用沿路缓存技术和l r u 替换策略。 p a s t ：p a s t 是m i c r o s o rr e s e a r c h ( c a m b r i d g e ，u k ) 开发的一个项目。p a s t 是一个大规模的p 2 p 存储系统，可提供高可用性、可扩展性、结点问的负载平 衡以及匿名性保护。文件可永久保存在p a s t 系统中，并可共享给其它用户。 p a s t 的定位算法是p a s t r y ，和t a p e s t r y 一样采用前缀路由。p a s t 将每个文件 复制k 份，放在n o d e i d 与文件的k e y l d 最接近的k 个结点上。在插入新文件 或查询时，需要经过中间结点，如果文件的大小不超过当前中间结点缓存大小 的c 倍( 由算法指定) ，就缓存该文件。p a s t 采用g d s ( c r r e e d y d u a l s i z e ) 第2 页 国防科学技术大学研究生院学位论文 缓存替换策略。 2 、网格计算环境中的海量数据管理系统 网格计算( o r i dc o m p u t i n g ) 技术能够整合网络中的所有资源，为甩户提供一 种虚拟的巨型超级计算机系统。数据网格是得到最广泛研究的网格计算技术，以 数据管理为中心，面向底层屏蔽网络中各种异构存储和数据资源，面向上层应用 提供通用和可靠的数据服务。数据网格可为地理上分布的研究团体对海量数据进 行复杂分析、联合处理提供基本环境，也使得单个研究人员可以充分调动网格上 的计算资源、信息资源，方便地访问和分析庞大的数据。 基于网格计算环境的海量数据管理系统主要有e d g 7 8 】和s r b 9 1 0 l 等。 欧洲数据网格( e u r o p e a nd a t a g r i d ，e d g ) 是欧盟投入巨资建设的一个项目， 它能够对许多研究机构的科学实验室中产生和存放的海量数据进行平等的资 源共享、协作的处理和分析。e d g 是由许多物理资源( 如计算机、磁盘和网 络等) 和“中间件”( m i d d l e w a r e ) 软件组成，其中“中间件”负责保证对这 些资源的访问和平等使用。e d g 采用统一的接口屏蔽不同站点的数据存贮方 式和处理方式之间的差异，使分布的存贮资源能够无缝融合。e d g 在g l o b u s t o o l k i t2 的基础上开发了两种副本管理工具来进行数据复制和副本管理： g d m p ( g r i dd a t am i r r o r i n gp a c k a g e ) 和e d g - r e p l i c a - m a n a g e r 。g d m p 和 e d g r e p l i c a - m a n a g e r 都使用了r e p l i c ac a t a l o g u ei n t e r f a c e 来识别和定位副本，目 前又提出了一种新的定位技术r e p l i c al o c a t i o ns e r v i c e ( r l s ) ，能够消除 r e p l i c ac a t a l o g u ei n t e r f a c e 定位副本时遇到的问题。r l s 将是e d g 2 0 版本的 组成部分之一。 存储资源代理系统( s t o r a g er e s o u r c eb r o k e r ，s r b ) 是由圣地皿哥超级计算中 心开发的软件中间件。s r b 为用户提供了一个访问文件系统、档案系统、数据 库系统等多种异构存储系统的统一接口，屏蔽了存储系统的异构特性，支持广 域网络环境下多种数据源的访问。s r b 被广泛应用于网格技术中，如p a _ r t i c l e p h y s i c sd a t ag r i d t l 】、d o ea s c i 1 2 1 、n a s ai n f o r m a t i o np o w e rg r i d 【1 3 】及n s f g - r p h y n 1 4 】等；s r b 还能够被用来处理大规模的数据集，包括2 m i c r o na l l s k y 数据、n p a c i 数据集和l t e r 超光谱数据集等。 3 、其它种类 在对等计算和网格计算之前，就已经有一些成功的分布式海量数据管理系统， 如高性能存储系统h p s s t ”】和分布式并行存储系统d p s s 1 6 】等。 高性能存储系统( h i g hp e r f o r m a n c es t o r a g es y s t e m ，h p s s ) 是由毋m 与几家 科研机构共同开发的一种海量数据管理系统。h p s s 项目早就在1 9 9 3 年就已经 开始研究，它是一个层次化的存储系统，其目标是让海量数据能够在网络化存 第3 页 国防科学技术大学研究生院学位论文 储、高性能计算机、海量数据库之间快速传递。h p s s 提供高可用的可升级的 层次存储管理，将最近使用的数据保存在磁盘上，而最近很少使用的数据放置 在磁带库上。h p s s 使用了集群和存储局域网( s a n ) 技术来聚集许多计算机、 磁盘和磁带驱动器的存储容量和性能到一个存储容量较大和功能多样的虚拟 文件系统中。i - i p s s 在世界上众多的机构中被使用，例如在大型研究实验室( 美 国的l o s a l a m o s n a t i o n a l l a b o r a t o r y 、b r o o k h a v e n n a t i o n a l l a b o r a t o r y 和欧洲原 子能研究机构c e r n 等) ，超级计算机中心( s a nd i e g os u p e t c o m p u t e rc e n t e r ， s d s c ) 、科学数据文档和大学里的海量存储系统等。h p s s 同样也是许多重大 国家项目的组成之一( 如美国国家航空航天局n a s a ) 。 分布式并行存储系统( d i s t d b u t o dp a r a l l e ls t o r a g es y s t e m ，d p s s ) 由加州大学 伯克利分校的密集数据分布式计算工作组开发。d p s s 建立在数个高速连接的 a t m 广域网上，可以用于不同类型的数据密集型应用。d p s s 是广域网上一组 并行操作的磁盘服务器的集成，提供对大规模数据集的程序块级存取。从结构 上看，d p s s 就像是一个网络磁盘阵列，其独特之处在于允许客户应用完全自 由地决定最佳的数据布局、复制和冗余编码策略、安全方针及对系统信息的重 新配置。d p s s 最初被用在m a g i c 1 7 1 项目中，对大量类似图像的只读数据集 进行实时记录和存取，现在在卫星图片处理和高能物理研究中都得到了广泛应 用。 p 2 p 计算和网格计算都是现今分布式系统研究的热点，数据复制技术是其关键 技术之一。在海量数据管理中采用数据复制技术是减少访问延迟，提高数据可用 性，降低结点失效，增强系统性能的重要手段。 1 2 主要研究内容 本文的研究内容主要有： 研究分析了海量数据的特点及现有的几种典型的海量数据管理系统。 研究分析了数据复制技术中的两个主要问题：副本定位和副本放置。指出 了结构化p 2 p 系统中副本定位技术的主要缺陷是重叠网拓扑与底层网络 拓扑不一致的问题及网络拥塞和网络热点问题；指出了海量数据中的副本 放置主要目的是降低访问延迟和减少副本个数。 针对结构化p 2 p 系统中重叠网拓扑与底层网络拓扑不一致的问题，利用 g n p 的坐标系统构造了基于地理邻近性的重叠网拓扑；针对网络拥塞和 网络热点问题，设计了一种基于地理范围的层次式哈希法，通过增加指针 结点来消除网络热点。 第4 页 国防科学技术大学研究生院学位论文 提出了基于几何空间划分的层次式d h t 定位方法( h l s p ) 。h l s p 给出 了对象命名规则、消息路由策略和对象发布、查找算法。讨论了当结点加 入或离开系统时的动态维护方法。通过模拟测试验证了基于地理邻近性重 叠网拓扑的有效性以及i - i l s p 在定位邻近副本和消除网络热点方面的改 进。 通过研究基于延迟限制的副本放置需求，提出了基于延迟估算的副本放置 算法。首先利用g n p 进行延迟估算，使用区域选择算法确定副本放置的 区域；然后研究网络环境变化时副本的动态调整策略。通过模拟测试验证 了副本放置方案对系统性能的优化。 1 3 论文组织结构 本文的内容组织如下： 第一章：主要分析了海量数据管理的相关内容，确定了本文的研究内容。 第二章：介绍了数据复制技术和延迟估算技术的研究现状。 第三章：研究提出了基于几何空间划分的层次式d h t 定位方法并进行了模拟 测试。 第四章：研究提出了基于延迟估算的副本放置算法并进行了模拟测试。 第五章：结束语。总结了本文研究的主要内容，展望下一步的工作。 第5 页 国防科学技术大学研究生院学位论文 第二章数据复制关键技术研究 分布式系统应用中数据集是相当庞大的，而用户的访问活动又是动态变化和 无法预测的，在如今的网络条件下为每一个用户请求从数据的原始位置获取内容 是相当低效和不现实的。为了提高数据访问的效率，系统会利用数据复制技术在 网络中多个结点上创建数据副本，实现数据的就近访问，给不同访问点提供距离 最近、访问最快、开销最小的数据访问服务，从而提高系统的整体性能。 副本定位解决数据访问过程中的数据定位问题，即通过某种给定的信息( 数 据对象的名字、m 或关键字等) ，在整个广域分布的系统内高效精确查找并返回 数据对象的位置信息。副本放置解决数据复制过程中的副本分布问题。从狭义上 讲，副本放置就是把数据对象的副本放到某个特定的位置，使得用户对该对象的 访问开销最小；从广义上讲，副本放置需要综合考虑结点负载、存储容量和网络 带宽等诸多因素，来决定何时创建副本、创建多少副本以及在哪里创建副本的策 略，从而使系统性能达到最优。 在数据复制过程中，系统会根据当前网络的性能机动地选取最优的通信路径 来定位最近的副本或者将远程副本放置到离数据请求结点最近的位置上。利用延 迟估算技术能够有效估算出分布式系统中任意两个结点之间的网络距离，从而可 以在结点通信时选取最优路径，降低定位副本和放置副本时的通信开销。 2 1 1 副本定位技术 2 1 数据复制技术 副本定位是分布式海量数据访问和管理的基础，对整个系统的性能有着重要 的影响。副本定位的目的就是在分布式系统中根据搜索请求有效地查找到符合搜 索条件的数据对象( 副本) 。 在p 2 p 系统中，由于其结点的对等性，没有结点维护系统全局的信息。因此 p 2 p 系统中的定位技术有其自身的特点。 非确定性的还是受某种机制严格控制的， 化p 2 p 系统。 l 、非结构化p 2 p 系统 根据p 2 p 系统的拓扑构造过程是动态、 p 2 p 系统分为非结构化p 2 p 系统和结构 在非结构化p 2 p 系统中，结点问的拓扑关系通常较为松散，具有较大的随意 性，例如c m u t e l l a 堋、f r e e n e t ( 1 9 1 和f a s t t r a c k l 2 0 等。 g n u t e l l a 采用受限r r l ( t i m et ol i v e ) 的泛洪技术来进行资源搜索，每个结 点都将接收到的搜索请求广播给所有的邻居结点，同时搜索请求的r r l 值减1 ， 第6 页 国防科学技术大学研究生院学位论文 直到t t l 的值为0 。如果某结点发现本地有符合搜索条件的资源对象，该结点会 沿着搜索路径反向传播q u e r y h i t 消息到发起搜索的结点，然后两个结点通过h r t p 协议直接传输文件。泛洪技术的优点是无集中服务器，全分布，可靠性好，查询 的命中率通常较高；缺点是查询比较慢，广播对网络带宽的消耗也过大，并由此 带来可扩展性等问题。 在f r e e n e t 中，文件发布时，首先计算文件的二进制关键字k e y ，并产生一个 h t l ( h o p st ol i v e ) 值。资源搜索时首先获取需搜索文件的k e y ，然后发出搜索消 息。当任一结点接收到搜索消息时，首先进行本地匹配，若匹配成功则返回搜索 结果；否则将搜索消息转发到本地“路由表”中与k e y 最相近的关键字对应的结点 上。搜索消息会一直转发下去，直到搜索成功或者h r l 变为0 。如果搜索成功， 则在搜索路径中的各结点上复制该数据，并在各结点的路由表中建立数据源和k e y 的映射。如果搜索消息转发后出现了路由环或结点失效，则根据路由表中次相近 的关键字进行转发。f r e e n e t 对文件进行了大量复制，资源搜索只需搜索到文件的 任一个副本，但f r e e n e t 不能保证资源搜索的效率和准确性。 2 、结构化p 2 p 系统 在结构化p 2 p 系统中，结点间的逻辑拓扑关系通常由确定性的算法严格控制。 结构化p 2 p 系统通常采用分布哈希表技术( d i s t r i b u t e dh a s ht a b l e ，d h t ) 【2 1 1 1 2 2 1 构建，并利用d h t 将数据对象映射到结点。例如t a p e s t r y l 2 3 1 、p a s 时洲、c h o r d c 2 5 l 和c a n 2 6 1 等。结构化p 2 p 系统采用基于d h t 的定位技术进行副本定位，通常包 括对象命名、消息路由和资源搜索三大部分。在这些系统中，文件根据系统生成 的标识( d ) 排列。这种标识通常是文件名经过哈希计算的结果。系统中的每一 个结点都和一个特定区段内的标识关联，并保存相关联标识对应的文件的信息。 当根据d h t 对标识进行查询时，相应的结点便会返回对应的信息。 基于d h t 的p 2 p 系统的副本定位过程如下：重叠网路由协议根据接收到的数 据对象的标识( 一般是一定长度的数字串) ，把信息路由到相应的结点。每个结 点也具有一个标识符( n o d e i d ) 。而且，这个标识符通常是和它对应的文件的标识 相同。同时，每一个结点都维护一张路由表，记录其它一些结点的信息。当一个 结点收到一个查询操作时，如果它发现所查询的标识不在自己关联的区间内，那 么该结点将会把该查询发送给其路由表中它认为最靠近目标的邻居。各种算法中， 对“最靠近目标”的定义不尽相同，但是通常都是根据结点标识符和目标标识进 行定义。 基于d h t 的p 2 p 系统的核心是路由协议。系统中的d h t 结点构成一个重叠 网，每一个查询操作都是通过这个重叠网找到目标结点。所以，基于d h t 的p 2 p 系统的性能就取决于其所采用的路由协议的效率。下面介绍几种典型的重叠网路 第7 页 国防科学技术大学研究生院学位论文 由协议： p l a x t o n 树：p l a x t o n 树 2 7 1 是第一个能够被d h t 系统大规模使用的路由协议， 虽然该算法的初衷是针对静态网络设计，而不是p 2 p 系统。该算法采用的是标识 “前串匹配”的路由模式。每一步路由都会把信息传送到“前串”更加匹配目标 的结点去。 t a p e s t r y ：t a p e s t r 产3 】是对p l a x t o n 树的改进算法，使之能够部署在动态的网 络之中。t a p e s t r y 的思路来源于p l a x t o n 、r a j a m a r a n 以及r i e h a 提出的路由机制， 但后者是静态结构且需要结点的全局视图，而t a p e s t r y 不需要全局视图且可以处 理结点动态变化。t a p e s t r y 采用的是p l a x t o n 基于后缀的路由：即从标识符的后一 位开始一步步逼近目的d ，例如由8 到+ 9 8 再到* 5 9 8 再到4 5 9 8 ，这里+ 是通配 符。事实上，这种逼近的思路与c d r 口地址分配体系的最长前缀路由类似，只 不过t a p e s t r y 是由右到左的。 p a s t r y ：在p a s t r y i 冽中，每一个结点都被分配了一个1 2 8 位的结点标识 ( n o d e i d ) ；用于确定该结点在环状标识空间中的位置。每一个结点的结点标识是 在结点加入系统时随机分配的。这里假设目d 的分配是均匀的( 实际上，现在的哈 希算法能够保证这一点) 因为这种随机性，在标识空间中位置相邻( n o d e i d 最 接近) 的任意两个结点在权限、所处的网络拓扑、所有权和网络配置等等方面都 可能有很大差异，换句话说，在标识空间相邻的结点，在实际网络中却往往差异 很大。 c h o r d ：c h o r d l 2 5 1 也是一个使用环状标识空间的系统。同样，针对一个标识的 路由目标就是在数值上最接近该标识的n o d e i d 的结点，并称为针对该标识的承接 点。在c h o r d 中，每一个结点都维护着两套邻居。其中一套为在标识空间中紧接 着该结点的k 个结点，另一套为指向在整个标识环中以该结点为基准依次折半的 结点的指针。其中，第一套邻居是确保路由正确的关键。c h o r d 可以确保路由在 标识空间中单向靠近目标结点而且不会越过，并且可以保证路由在o ( l o g n ) 步内 完成。 c a n ：c a n 2 6 1 采用的标识是从一个多维( 假设为d 维) 环状空间中选择的。 每一个结点都与其标识周围的_ 个立方区域相关联，同时，它的邻居就是拥有和 它相邻的立方区域的结点。路由时，消息一直是从一个结点传输到它的拥有与目 标标识最接近的n o d e i d 的邻居。与前面几种算法不同，c a n 中每个结点维护大 小为d 的路由表，同时，每一次路由都在o ( d n l 步内完成，特别当d = o ( l o g n ) 时，c a n 的路由表和路由长度将与其它系统相似。 结构化p 2 p 系统中基于d h t 的定位技术的优点是资源定位准确并且可保证效 第8 页 国防科学技术大学研究生院学位论文 率，通常都能保证只要系统中的资源对象存在，就一定能够在一定的跳步数内定 位到该资源对象。d h t 方法具有良好的可扩展性，并提供了简单有效的抽象接口， 可以作为通用网络架构支持多种应用。但是它仍然面临着若干挑战： 位置邻近性：在传统的d h t 方法中，对所有的请求者来说，查找开销几乎都 是单一的，只和结点的规模有关，忽视了请求者和对象提供者之间可能存在的 位置邻近性，不能够利用在大规模网络中经常存在的局部性原理来提高访问效 率； 爨爨阿拓芥 蕺艟糊貉籀芥 图2 1 重叠网拓扑与底层网络拓扑之间的差异 重叠网拓扑的构造：在已有的d h t 方法中，对象i d 和结点n o d e i d 都是通过 随机的哈希函数得到，d h t 的基本设计没有考虑位置特性，重叠网的结点邻 居属性和底层口网络的结点邻居属性有可能不一致，不能够很好地反映底层 网络拓扑的特征，故其查找延迟往往不是最优的。例如在图2 1 中，重叠网拓 扑中结点a 和b 相隔较近，但实际上在底层网络拓扑中两者相距甚远，假如 结点a 向c 发出一个多跳的搜索请求，结点a 可能需要通过一个拓扑较远的 结点b 来向前转发消息，才能够到达一个在底层网络拓扑中实际上很近的结 点c ，这就会给查询过程带来较长的延迟，同时浪费了网络带宽，增加了网络 拥塞的几率。 网络拥塞和热点问题：在d h t 的基本设计中，一个对象被哈希到d 空间中的 一个点或多个点，拥有该点所