（计算机应用技术专业论文）p2p文件存储系统负载均衡技术研究.pdf

c l a s s i f i e di n d e x ： u d c ： ad i s s e r t a t i o nf o r t h ed e g r e eo f m e n g r e s e a r c ho nt e c h n i q u e so fl o a d b a l a n c i n g i np 2 pf i l es t o r a g es y s t e m c a n d i d a t e ：z h a oj i n g h u a n s u p e r v i s o r ：a s s o c i a t ep r o f q i a nz h e n a c a d e m i cd e g r e ea p p l i e df o r ：m a s t e ro fe n g i n e e r i n g s p e c i a l i t y ：c o m p u t e ra p p l i e dt e c h n o l o g y d a t eo fs u b m i s s i o n ： m a r c h , 2 010 d a t eo fo r a le x a m i n a t i o n ：m a r c h 2 010 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y k。i 1 - 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均己在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：莲舷 日期： 加，d 年弓月步日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 叼在授予学位后即可口在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、 作者( 签字) ：起拣嚷 日期： 犀弓月修日 导师( 签字) ： 2 0 ，9 年弓月 ，“一 r 0 。j i 哈尔滨t 程大学硕+ 学位论文 摘要 随着互联网应用的发展和社会信息化的深入，需要处理的数据的规模和 越来越大，传统的存储系统已经适应不了新的存储需求。由于基于d h t 的p 2 p 网络具有去中心化的资源利用和去中心化的自组织结构特性，使得在其上构 建的文件存储系统具有良好的扩展性和动态性，并成为了国内外研究的热点。 p 2 p 文件存储系统较传统的存储系统在扩展性和冗余方面有着先天的优势， 但p 2 p 的引入也带来了相应的负载均衡方面的问题。， 本文在已有研究工作的基础上，针对p 2 p 文件存储系统的负载均衡问题 进行研究。本文所取得的成果如下： 针对每个节点负责的i d 区域大小不同和节点能力差异很大的问题，提出 基于虚节点划分的负载均衡技术。该方法首先建立适用于p 2 p 存储系统的节 点性能模型，并提出基于虚节点划分的p 2 p 负载均衡机制，将物理网络中临 近的性能弱的节点划分成一个d h t 网络中的虚拟节点以平衡系统的负载。 针对文件的访问频度差异很大的问题，提出单指数平滑法的热点预测和 处理技术。通过分析过去查询数据的时间序列，运用单指数平滑法预测未来 的热点。根据访问热点的用户查询行为的差异，采取端到端复制和轻负载邻 居节点复制策略，有效地避免和消除了热点造成的负载不均衡问题。 最后，本文在研究和总结已有负载均衡技术的基础上，针对p 2 p 存储系 统中的数据分布和数据访问不均衡问题，提出相应的解决方案。经过实验验 证，提出的方案可以有效得平衡网络存储系统的负载。 关键词：p 2 p 存储；负载均衡；虚节点划分：热点预测 曩 一 i i ， t l ， 哈尔滨t 稗大学硕十学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e m e ta p p l i c a t i o n sa n di n f o r m a t i o nt e c h n o l o g y , t h es c a l eo ft h ed a t ai sg r o w i n g t r a d i t i o n a ls t o r a g es y s t e m sh a v en o tb e e na d a p t e d t ot h en e ws t o r a g er e q u i r e m e n t s t h ef e a t u r et h a td h t - b a s e dp 2 pn e t w o r k sh a v e d e c e n t r a l i z e dr e s o u r c eu s ea n dt h ed e c e n t r a l i z e ds e l f - o r g a n i z i n gs t m c t u r em a k e s t h ef i l e s t o r a g es y s t e mw h i c hb a s e so nd h tn e t w o r kg o o ds c a l a b i l i t ya n d d y n a m i c a n di th a sb e e nar e s e a r c hh o t s p o ta th o m ea n da b r o a d p 2 pf i l es t o r a g e s y s t e m i sm o r es c a l a b l ea n dr e d u n d a n tt h a nt h et r a d i t i o n a l s t o r a g es y s t e m i n h e r e n t l y b u ti ta l s ob r o u g h tt h el o a d - b a l a n c i n gi s s u e s i nt h i sp a p e r , l o a db a l a n c i n gi s s u e so fp 2 pf i l es t o r a g es y s t e mh a v eb e e n r e s e a r c h e do nt h eb a s i so ft h ep r e d e c e s s o r s w o r k s t h er e s u l t so ft h i sp a p e ra r ea s f o l l o w s ： f i r s to fa l l ，t h ei dr e g i o nw h i c he a c hn o d ei sr e s p o n s i b l ef o ri sd i f f e r e n t ，a n d n o d ec a p a b i l i t i e sv a r yw i d e l yi nd h t t or e m e d yt h i si s s u e ，am e t h o db a s e do i l v i r t u a ln o d e sd i v i s i o ni sp r o p o s e d an o d ep e r f o r m a n c em o d e li se s t a b l i s h e di n p 2 ps t o r a g es y s t e m ，a n dt h e nal o a db a l a n c i n gm e c h a n i s mi sp r o p o s e d t h ew e a k p e r f o r m a n c en o d e sn e a r l yi nt h ep h y s i c sn e t w o r ka r ed i v i d e di n t oav i r t u a ln o d et o b a l a n c et h es y s t e ml o a di nt h em e c h a n i s m s e c o n d l y , t h ef r e q u e n c yo ff i l e a c c e s s e si sd i f f e r e n t ah o tf o r e c a s ta n d p r o c e s s i n gt e c h n o l o g yi sp r o p o s e db a s e do ns i n g l ee x p o n e n t i a ls m o o t h i n gm o d e l u s ep a s tq u e r yd a t aa n ds i n g l ee x p o n e n t i a ls m o o t h i n gm o d e lt op r e d i c tt h ef u t u r e h o ts p o t s t h ep r o c e s s i n gm e t h o di sb a s e do nt h eu s e rq u e r yb e h a v i o r t h e e n d - t o e n d r e p l i c a t i o ns t r a t e g y a n d l i g h t - l o a dn e i g h b o rr e p l i c a t i o ns t r a t e g y e f f e c t i v e l yp r e v e n ta n de l i m i n a t el o a di m b a l a n c ec a u s e db yt h eh o ts p o t s f i n a l l y , l o a db a l a n c i n gt e c h n i q u e s f o rp 2 ps t o r a g es y s t e m sh a sb e e n r e s e a r c h e da n dc o n c l u d e di nt h i sp a p e r a n dm e t h o d sa r ep r o p o s e dt ob a l a n c et h e l o a do fi nd a t ad i s t r i b u t i o na n dd a t aa c c e s s t h ee x p e r i m e n t sv e r i f yt h a tt h e 一 一 一 一 一 哈尔滨t 稃大学硕十学位论文 p r o p o s e ds c h e m ec a l le f f e c t i v e l yb a l a n c et h el o a do i ln e t w o r ks t o r a g es y s t e m s k e yw o r d s ：p 2 ps t o r a g e ；l o a db a l a n c i n g ；v i r t u a ln o d ep a r t i t i o n ；h o tf o r e c a s t 第1 章绪论l 1 1 课题背景l 1 2 课题研究内容2 1 3 论文组织结构2 第2 章国内外研究概况4 2 1d h t 概述4 2 2 存储系统负载问题的产生9 2 3 负载均衡技术研究现状1 0 2 3 1 虚服务方法1 0 2 3 2 调整d 区域方法13 2 3 3 节点分组方法1 4 2 3 4 复制方法15 2 4 负载均衡技术发展趋势1 6 2 5 本章小结1 7 第3 章基于虚节点划分的负载均衡技术1 8 3 1 引言一1 8 3 2 节点模型2 0 3 2 1 节点性能模型2 0 3 2 2 节点网络坐标2 3 3 3 虚节点划分方法2 4 3 3 1 节点加入算法2 5 3 3 2 节点合并算法2 7 3 3 3 节点查询算法2 8 3 3 4 节点退出算法2 8 哈尔滨t 稗大学硕七学位论文 3 4 仿真试验与算法分析2 9 3 4 1 仿真器简介2 9 3 4 2 实验验证2 9 3 4 3 理论分析31 3 5 本章小结3 1 第4 章基于访问热点的负载均衡技术3 2 4 1 引言。3 2 4 2 基于单指数平滑法模型的热点预测方法3 3 4 2 1 时间序列分析方法3 3 4 2 2 单指数平滑模型3 4 4 2 3 热点预测方法3 5 4 3 基于访问行为的热点复制策略4 0 4 3 1 基于访问行为的副本位置选择4 1 4 3 2 基于文件热度的副本数量选择4 2 4 3 3 副本的访问规则4 4 4 4 实验仿真及性能分析。4 5 4 4 1 实验一4 5 4 4 2 实验二4 5 4 4 3 性能分析4 6 4 5 本章小结4 7 结论4 8 参考文献4 9 攻读硕士学位期间发表的论文和取得的科研成果5 3 致 射5 4 哈尔滨t 程大学硕士学位论文 第1 章绪论 1 1 课题背景 随着信息化的深入和发展，数据的规模越来越大，数据的重要性也越来 也高。例如g o o g l e ，b a i d u ，a m a z o n 等互联网公司，每天都要对海量的数据 进行存储；而对于银行等金融机构或公司，任意微小数据的丢失都意味着巨 大的损失。数据的存储越来越重要，对容量和安全方面的要求也越来越高。 而传统的服务器从容量和安全方面已经适应不了数据的存储的要求，网络存 储技术逐渐成为了存储市场上的主流技术。 与传统的存储系统相比，网络存储系统在可用性、扩展性、安全性和成 本方面都要较大的优势。网络存储系统部署的地域更加广大，可以使数据接 近使用者，提高数据的可用性；网络存储系统的规模可以随着应用的变化而 变化，进而提供海量数据的存储功能；网络存储系统在保障数据安全性有着 先天的优势，数据冗余和备份在分布式存储系统中占有相当重要的地位；网 络存储系统可以由大量廉价的p c 机构成，成本也很低。 网络存储技术由最开始的直接相连存储d a s 发展到集群存储和p 2 p 存储， 体系结构由集中式向分布式发展。具体的存储技术有直接连接存储d a s 、网 络附属存储n a s 、存储区域网s a n 、i p 存储、集群存储和p 2 p 存储掣1 1 。 直接连接存储d a s 是对s c s i 总线的进一步发展，网络附属存储n a s 、存 储区域网s a n 和i p 存储也都是对s c s i 总线的扩展，上述协议使得s c s i 命令 可以在存储设备之间传输，这样系统的存储任务就会由多个存储设备共同完 成。 集群存储技术充分利用了廉价的p c ，提升了存储系统的可扩展性和稳定 性，最典型就是g o o g l e 的集群存储体系【2 1 。p 2 p 存储系统是利用p 2 p 网络构 建底层网络的存储系统，与其他存储技术相比，p 2 p 存储系统在可用性、扩 展性和可靠性方面就有明显的优势，也是目前存储技术研究的热点。 p 2 p 是“p e e rt op e e r 的英文缩写，与传统的客户机服务器模式不同， 哈尔滨丁程大学硕十学位论文 在纯的p 2 p 网络中，机器与机器的角色是平等的，每个机器既是客户机接受 其他机器的服务，又是服务器向其他机器提供服务。在互联网的早期，机器 与机器是对等的，机器与机器通信也没有客户端与服务器之分。在互联网数 十年的发展过程中，网络上资源越来越集中，使得在构建在对等网络层上的 软件逐渐采用客户机服务器模式。尽管服务器的性能都很强大，在它面对海 量的客户端服务请求时，还是会遇到性能上的瓶颈。通过p 2 p 技术可以充分 利用海量的处于网络边缘的机器性能，使得网络资源分散在网络中，消除传 统服务器遇到的性能上的瓶颈。 1 2 课题研究内容 结构化p 2 p 网络存储系统成为存储系统研究中的热点，而结构化p 2 p 网 络的引入也给网络存储系统的负载均衡方面带来了新的问题。本文的研究内 容是基于d h t 的p 2 p 存储系统的负载均衡技术，分析了基于d h t 的p 2 p 网 络存储系统负载差异的原因，并提出相应的负载均衡方法。研究工作的具体 内容如下： 1 分析总结基于d h t 的p 2 p 文件存储系统的负载分布不均的原因。主 要有两方面的原因：1 ) 主机i d 区域不均衡和存储系统中节点的性能差异；2 ) 文件访问的不均衡。 2 分析总结前人在基于d h t 的p 2 p 网络中负载不均衡方面的工作。研 究基于虚服务、调整i d 区域、节点分组和复制等均衡p 2 p 网络中负载的方 法。 3 针对主机i d 区域不均衡问题，建立适用于p 2 p 网络文件存储系统的 节点性能模型，将物理上临近的主机划分成d h t 网络中的一个节点，通过将 弱节点合并的方式使节点负责的区域与它的能力成正比。 4 针对文件访问的不均衡，利用单指数模型预测文件的访问趋势，对于 热点文件，结合热点文件的查询特征采用端对端或邻近节点复制的方法处理。 1 3 论文组织结构 数据的规模和安全性的要求使得网络存储技术从众多存储技术中脱颖而 出，但负载均衡方面的问题也同样困扰着网络存储技术，本文详述了p 2 p 网 哈尔滨t 程大学硕士学何论文 络存储系统中负载均衡工作的研究现状，重点针对节点i d 区域不均衡和热点 文件问题进行了深入的研究和分析，结合已有的研究成果，提出了虚节点划 分技术和基于单指数模型的热点文件处理技术，并通过实验对上述技术和理 论进行验证。本文具体组织结构安排如下： 第二章是p 2 p 存储负载均衡技术研究，重点介绍了已有负载均衡技术的 研究现状，并分析总结了基于d h t 的p 2 p 存储系统负载均衡技术的发展方 向。 第三章提出了虚节点划分的负载均衡技术，提出了适用于结构化p 2 p 存 储系统的节点性能模型，并研究了网络定位算法，在p 2 p 网络上建立实际的 网络坐标，通过合并物理相邻的弱节点平衡系统负载。最后通过实验验证该 方案的效果。 第四章是基于单指数模型的热点文件处理方法，首先利用单指数模型预 测p 2 p 存储文件系统的热点文件，并根据用户访问行为的特征，然后提出端 对端复制和邻居节点复制的机制对热点文件进行处理，平衡系统的负载。最 - 后通过实验验证方案的效果。 结论部分总结了本文研究的主要内容和创新点，分析了当前研究工作的 不足，最后提出本领域未来的发展趋势。 2 1d h t 概述 近几年来随着网络的发展，出现了众多的大规模p 2 p 系统，如n a p s t e r t 3 1 、 g n u t e l l a t 4 】等。这些系统中的用户的数量都非常庞大，达到了百万以上的数量 级。这些系统中，有的采用非结构化的p 2 p 系统，有的采用结构化的p 2 p 系 统。在非结构的p 2 p 系统中，数据的查找或依赖于中心服务器或通过洪泛查 找的方式，这两种查找方式的可扩展性都不好。依赖于中心服务器的查找方 法，所有数据的查询都要通过中心服务器来完成，系统存在中心服务器这个 单点故障，中心服务器容易成为系统性能的瓶颈。在洪泛查找的方法中，节 点向系统中的所有节点都发送查询消息，并由相应的节点返回查找结果。这 样的查询方法会消耗大量的系统带宽，严重影响系统的性能。 为了解决非结构化的p 2 p 查询方法中的问题，研究人员将研究的焦点放 在分布式的、内容可寻址的数据存储方法上并开发了基于分布式哈希表 ( d h t ) 的结构化的p 2 p 系统。 在使用中心服务器方法的查找方式中，中心服务器存储系统中的索引信 息，这种方法查询的效率很高，但可扩展性不好；而在基于洪泛的查找方式 中，每个节点都只保存自身的索引信息，节点可以动态加入或退出网络，但 查询需要通过广度搜索来完成，系统的查询效率不高。在d h t 中，通过文件 内容的哈希值来得到文件存储的位置，这样d h t 就完成了分布式的、内容寻 址的功能。在d h t 的文件查找过程中，通过每个节点只保存到其他节点的少 量指针，使得查询消息经过少量的节点就能到达目的节点。这样既保持了系 统的可扩展性，查询的效率也较高。 分布式哈希表的核心思想是用哈希函数建立文件与文件存储位置的一一 映射。首先对文件的内容或关键字进行哈希，得到一个哈希值。而文件的存 储位置即网络中的主机相当于哈希函数中的桶，负责哈希值范围的一部分， 哈希值在这段范围内的文件就由这个主机来存储。例如网络中有4 个主机a 、 4 哈尔滨_ t 程大学硕七学位论文 一i i 置i | i 宣i i 置宣嗣嗣i 萱i i i i i i i i i i i i 萱置i i i i i i i i i i i i i i i i i i i i i i i i i i b 、c 和d ，哈希值范围是区间 1 ，1 6 】。a 负责1 q ，b 负责5 8 ，c 负责9 - - , 1 2 ， d 负责1 3 。1 6 。对文件内容哈希后得到一个在哈希值范围内的数值，根据每 个节点负责的范围就可以找到该文件应该存储的位置。 通过分布式哈希表可以建立分布式的内容可寻址数据存储网络，但简单 的分配网络中主机负责的哈希范围带来了较大的问题。网络中的主机的数量 是动态变化的，当网络中有新的主机加入或退出网络后，网络中的每台主机 负责的哈希值范围都要重新分配，进而每台主机存储的文件也要重新进行分 配。除了上述问题外，如何才能通过文件的哈希值定位文件存储的具体位置 即d h t 的路由问题也是分布式哈希表需要解决的问题。 针对上面的问题，一致性哈希算法【5 】在1 9 9 7 年由麻省理工学院提出的。 在一致性哈希算法中，存储的文件通过哈希函数生成一个文件i d ，网络中的 主机也通过哈希函数生成一个主机i d 。在对主机进行哈希是可以根据主机的 i p 地址进行哈希。在一致性哈希算法中存储文件的哈希值范围和网络主机的 哈希值范围是相同的，是一段一维的数值区域。 在网络主机哈希范围分配时，没有简单的根据线性映射的方式分配主机 的哈希范围。每个主机没有固定的数值范围。在定位文件的存储位置时根据 文件的文件i d 找到与该值最接近的主机i d ，该主机就是文件要存储的位置。 这样当网络中主机动态加入或退出时，只有与新加入主机相邻的节点才需要 进行调整。 通过文件d 和主机i d 的临近性来定位文件的存储位置不仅解决了主机 动态性带来的存储问题，也对d h t 的路由问题的解决奠定了基础。文件的 i d 和主机的i d 都在相同的数值空间内，只要网络中的每个主机只要存储相 邻的两个主机就可通过递归查询找到文件的存储位置。假设网络中的主机数 量大于3 个，网络中的每个主机的路由表中都会存储两个相邻的主机，一个 主机是所有大于主机自身i d 值中主机i d 最小的主机，另一个主机是所有小 于主机自身值中主机d 最大的主机。在主机根据文件的i d 值查询文件的存 储位置时，根据文件的文件i d 向路由表中i d 值最接进的主机发起查询请求， 收到查询请求的主机根据主机i d 的临近性来决定是否是文件存储的位置。具 体的判断方法就是与路由表中主机的主机i d 相比较，如果发现比路由表中的 主机i d 更接近文件i d ，该主机就是文件存储的位置，此时向查询请求的源 哈尔滨丁程大学硕十学位论文 节点发送确认信息。若路由表中的主机i d 更接近文件i d ，则继续递归查询。 为了维护主机路由表中的信息，在主机新加入网络或退出网络时，主机的相 邻主机要及时更新路由表中的信息。若每个主机仅存储两个最邻近的主机信 息，当其中i d 较大的主机退出网络后，主机就无法获得比该主机d 大的主 机的信息。所以主机不仅存储最邻近的两个节点的信息，还要存储多个比较 邻近的主机信息，通过多个节点的信息来维护节点的路由表。 一致性哈希算法完成了动态网络中文件的分布存储和文件路由的要求， 每个节点仅存储少量的节点信息，节点加入和退出网络时也仅有少量的节点 需要调整，这些特征使得一致性哈希算法成为第一个使用的d h t 算法。但一 致性哈希中的路由算法存在一定的不足，查询消息要通过o ( n ) 跳在能定位文 件的存储位置。为了提高路由的效率，人们又提出了c h o r d 6 、内容寻址网络 ( c a n ) 【7 】和p a s t n 引，它们都是基于一致性哈希算法的，但具体的标识符空 间和路由算法方面存在不同，下面对c h o r d 、内容寻址网络( c a n ) 和p a s t r y 分别进行介绍。 1 ) c h o r d 、 c h o r d 对一致性哈希算法的路由过程进行了优化，在一致性哈希算法中， 每个主机存储多个直接相邻的主机的信息。在c h o r d 中，每个主机同样需要 存储多个其他主机的信息，这些主机的信息存储在被称为路由表( f i n g e r t a b l e ) 的主机集合中。虽然一致性哈希算法中的主机同样具有存储主机信息 的集合，但在c h o r d 中，路由表中存储的信息不再是i d 值邻近的多个主机的 信息，路由表存储的多个d 值与主机自身d 存在特定的关系。路由表中的 i d 与主机自身的i d 将成2 1 ( i 为路由表中各个表项的值) 的关系。每个i d 值对应着存储该i d 值的主机。这样的路由表使得路由查询时按照折半查找的 方法进行查询。 在进行路由查询的过程中，查询发起的主机发起查询请求，查询请求的 目的地址是与文件i d 值最接近的主机上，该主机的查找利用主机的路由表或 得。当主机收到查询请求节点后发现在自身负责的范围内时，主机直接向查 询请求的源节点发送回应，具体的判断方法与一致性哈希算法中的相同；如 果被查询请求中文件的i d 不在主机负责的范围内，就根据路由表将查询请求 转发到与文件i d 最接近的主机上，直到到达目标主机。文件定位的过程是一 6 哈尔滨丁程大学硕十学传论文 个折半查找的过程。 c h o r d 的路由算法中，如果文件i d 与主机的i d 距离较远，文件查找的 就可以一跳内跳过很大的距离，更快到达目的主机。如果文件i d 与主机的 d 距离较近，主机路由表上的相关路由信息就很详细。由于路由表中存储的 文件i d 与主机i d 距离大小为2 的指数，路由过程中的每一跳中的目的节点 i d 与文件i d 至少减少一半距离，对于具有n 个主机的c h o r d 网络查询路由 的平均要经过o ( 1 0 9 2 n ) 次路由转发。 2 ) 内容寻址网络 c a n 的思想与一致性哈希相同，文件被映射到d 值相临近的节点上， 定位文件和路由消息也很简单，每个主机仅存储节点直接临近的节点的信息。 与一致性哈希算法不同的是标示符的空间，在一致性哈希算法中利用哈希函 数得到的标识符空间是一维的，而在c a n 中，标识符空间是多维的。与单 维空间的线性遍历相比，多维空间的比较使得文件查询和定位的效率得到了 极大的提高。 c a n 的标识符空间可以看成为一个d 维的笛卡尔空间，每一维相当于一 个c h o r d 的标示符空间，d 是可以定义的常量。文件定位就在这个d 维的空 间中来完成。在c a n 中，每个主机利用哈希函数生成一个d 维的i d ，每个 文件利用哈希函数也生成一个d 维的i d 。当d 为2 时，d 的形式就为 ， 一个长度为1 6 位的标示符将前8 位看成第一维，后8 位看成第二维，就可完 成二维d 的生成。在d 维空间中与主机相邻进的主机的定义与一维空间中临 近主机的定义不同。在d 维空间中，当两个主机的i d 有d 1 维是相同，另一 维相临近，这两个主机在d 维空间中就是临近的。c a n 中主机的路由表紧存 储直接临近的主机，每个主机在一个维度上临近的主机由两个，主机一共要 存储2 d 个临近主机信息。 c a n 的路由查询过程与一致性哈希算法中的相似。每个文件根据哈希函 数生成一个文件i d ，这个d 是一个d 维的向量；每个主机也会利用哈希函 数生成一个主机i d ，主机i d 也是一个d 维的向量。文件定位的过程中，主 机在路由表中查找与文件i d 相临近的主机，此时临近性的判断跟主机临近性 判断相同。找到与文件i d 向邻近的主机后，向该主机发送文件定位请求。收 到文件定位请求的主机如果发现文件定位到主机自身上，直接相发送请求的 哈尔滨t 稗大学硕+ 学位论文 源节点回应自身的位置信息；如果文件i d 不在主机自身的负责范围内，就在 路由表查找与文件i d 最接近的主机，并转发到这个主机上，直到定位到文件 的存储位置上为止。文件i d 与接受查询的主机的i d 的空间距离不断地减少， 直到到达文件的目的地点。 在一致性哈希算法中，文件定位消息的平均需要经过o ( n ) 次转发才能达 到目的节点。在c a n 的路由算法中，文件定位消息的需要的转发的次数由 o ( n ) 减少到o ( ( 叭) ( n 1 付) ) ，由于d 是常数，路由消息的转发的平均次数为 o ( n 1 埘) 或o ( c t n l 埘) 。 3 ) p a s t r y p a s t r y 是有r o w s t r o n 等在2 0 0 1 年提出的。p a s t r y 也与一致性哈希算法类 似，但路由的效率要比一致性哈希算法要高。p a s t r y 的标识符空间没有像 c h o r d 将标识符空间组成一个环，在p a s t r y 中，每个主机都拥有一个l 位的 标识符，每个文件也通过哈希函数生成一个l 位的标识符。标识符空间为 o 2 l 1 之间的区间。p a s t r y 将标识符看成以2 6 为基的数字串，并将文件存储 在其i d 在数值上最接近的节点上。 一 p a s t r 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 ) 和一个叶子节点集合( l e a f s e t ) 。 路由表类似c h o r d 中的f i n g e r t a b l e ，存储网络中其他主机的信息。路由 表的行数位l b ，每行包含2 6 1 个表项，每个表项表示一个主机的信息。对 于一个主机，该主机的路由表中第i 行的表项中的主机d 信息的前i 位和当 前主机的前i 位相同，第i + l 位与当前主机不同。若没有满足条件的主机， 该表项就为空。 路由表中的主机信息是通过i d 前缀的相等来找到的，而叶子节点集合中 存放的是在标识符空间中与当前主机i d 距离最近的主机的信息，其中叶子节 点集合中一半主机的标识符大于当前主机，另一半主机的标识符小于当前主 机。 邻居节点集合中存放的是在真实网络中与当前主机距离最近的主机的信 息。但p a s t r y 并未提供主机邻居节点集合的初始化方法，一般假设通过其他 方法获得。 8 哈尔滨t 程大学硕十学佗论文 在p a s t r y 的文件查询过程中，首先，利用哈希函数生成文件的文件i d ， 并在查询消息中发送出去，当主机收到查询消息时，主机首先检查文件i d 是 否落在主机的叶子节点集合的范围内。如果落在叶子节点集合范围内，则直 接把查询消息转发给叶子节点集合中相应的主机；若没落在叶子节点集合范 围内就在路由表中选择一个主机作为查询消息的下一跳地址，这里主机的选 择是根据最长前缀优先的原则来完成的。如果不存在这样的主机，当前主机 就会从其所知道的主机信息中选择一个距离文件i d 最近的主机作为查询消 息的转发地址。 从文件查询过程中可以看出，每一跳路由与上一跳相比都将更靠近目标 主机。如果路由表不为空，每次路由前缀匹配的位数至少增加一位。查询消 息的平均转发次数为l o g 2 b n ，n 为网络中主机的数量。 2 2 存储系统负载问题的产生 基于d h t 的p 2 p 网络文件系统的主要功能是保存用户提交的文件，并 在用户的请求访问文件时，将用户所需要的文件提供给用户。 p 2 p 文件存储系统的功能是由构成整个系统的各个主机共同完成的，系 统的资源就是组成系统的各个主机资源之和。用户在上传文件时，主机要提 供存储空间以容纳用户提交的文件，在用户访问时，主机要通过网络将文件 传输给用户。由于p 2 p 网络文件系统中主机数量十分巨大，主机性能上的差 异也很大。理想负载均衡的情况下，每个主机承担的负载要与它的能力相适 应，每个主机存储的文件与它的能力相适应，每个文件的访问次数也大致相 同。但由于d h t 算法每个主机承担的存储负载并不相同，文件的访问差异也 使得每个主机由访问引起的负载差异很大。从总体上看，系统的负载分布很 不均衡。 基于d h t 的p 2 p 文件存储系统中，用户上传文件时并不知道文件最终 的存储的地址，文件的定位是由d h t 算法来完成的。在d h t 算法中，文件 或主机都依据哈希函数生成一个数值，对应着文件的d 或主机的i d ，文件 i d 和主机i d 都在相同的数值空间内。在定位文件时，查找与该文件的i d 最 近的主机i d ，此时的最近被定义为数值上的接近，该主机就是文件要存放的 位置。这样每个主机都会拥有一段i d 区域，凡是i d 落在该区域的文件都将 9 哈尔滨t 稃大学硕七学位论文 存放在这个主机上。 利用哈希函数可以使主机的i d 近似均匀的分布在整个数值空间上，但每 个主机所负责的区域的大小并不是均匀的，根据文献【9 】可知，网络上主机负 责的最大i d 区域与最小d 区域的比值可达l o g ( n ) ，n 为网络中的主机的 数量。再考虑到p 2 p 网络中，每台主机的性能是不同的，主机的存储容量和 带宽差异很大，这样更加剧了文件存储的不均衡分布，如果一个存储容量很 小的主机刚好承担了很大的i d 区域，这台主机存储不下应该存储的文件，从 而造成文件的丢失，影响用户的使用。 在基于d h t 的p 2 p 文件存储系统中，每个文件的访问次数是不一样的。 每个文件都要经历建立、完善并销毁的过程，每个文件在不同时间的访问次 数是不相同的，不同文件的访问次数的差异更大。像社会的其他随机事件一 样，文件的访问次数服从z i p f 分布，就是通常所说的极少数的文件被访问的 次数占据了总的文件访问次数的很大一部分。存储这些文件的主机就要承担 大量的下载请求，进而降低系统的整体性能。 根据上文所述，将存储系统的负载不均衡现象分为两个方面：、由于存储 文件而产生的存储不均衡现象；由于文件访问而产生的访问不均衡现象。 将基于d h t 的p 2 p 存储系统的负载均衡问题归结为两个原因t 1 ，节点性能的差异性和节点负责i d 区域的不均衡。 2 ，文件系统中的文件的访问频度不同。 2 3 负载均衡技术研究现状 随着用户上传文件和下载文件，系统中各个节点的存储容量在不断变化， 针对这种状况，产生了两种思路t 第一种着重考虑产生负载分布不均的原因， 以预防的观点，避免产生负载不均衡的角度出发，在数据的存放和节点的i d 区域差异等方面做了深入的研究。另一种从调整负载为手段，实时监控系统 的负载信息，发现负载分布不均衡时，通过将负载用重负载节点上转移到轻 负载节点上，使得系统中的节点负载大致均衡。两种方法并不是相互独立的， 有时相互统一在一个方法中。下文将对具体的方法进行介绍。 2 3 1 虚服务方法 l o 哈尔滨t 稃大学硕十学何论文 d h t 网络是一种覆盖| ) c ) 9 络，实际物理嘲络中的主机通过哈希函数映射到 d h t 网络中的一个节点，根据上文所述，每个节点所负责的最大i d 区域与 最小i d 区域的大小比可达到o ( 1 0 9 n ) 【9 】，为了使每个节点分配的i d 区域 的大小相等，是将每个主机映射到d h t 网络中的l o g n 节点上，这样就使得 每个节点的i d 区域大小相掣6 】。虚服务的方法指的就是使每个物理节点对应 多个d h t 网络上的节点。r a oa 【1 0 1 首先提出了虚服务的概念，并在此基础上 提供了三种简单的负载均衡算法：一对一、一对多、多对多。三种算法的基 本思想是转移负载，不过负载转移的单位不是传统的文件，而是重负载主机 上的虚服务，一个虚服务就是d h t 网络中的一个节点，通过转移虚服务将一 段i d 区域由重负载节点转移到轻负载节点上以达到平衡系统负载的目的。由 于转移虚服务的方法比较简单，通过虚服务的加入和退出d h t 网络算法就可 以完成，并不需要更改网络的结构，所以虚服务的机制得到了广泛的应用。 三种方法的区别在于发现系统中轻负载节点和重负载节点的手段，在一对一 方法中，每个轻负载节点会随机选择一个节点，向该节点发出请求希望获得 对方的负载情况，当发现被请求的节点是重负载节点时将重负载节点的虚拟 服务器转移到本节点上。在一对多和多对多方法中，系统中的节点计算自身 的负载情况，如果发现自身的负载情况超过一定阈值而成为轻负载节点或重 负载节点时，节点将自身的信息发给系统指定的节点，这些指定的节点被成 为目录节点。目录节点会获得系统中的轻负载和重负载节点的信息，通过与 一对一相同的方式转移虚服务，平衡系统的负载。与一对一方法中负载仅能 在两个节点间转移相比，一对多与多对多的方法在调度负载时可以考虑多台 主机，生成的调度策略能更快使系统负载达到平衡的效果。c f s t 】系统就采 用了虚服务的方法，利用一对一、一对多和多对多的策略平衡系统的存储负 载。c f s 系统采用的d h t 算法是c h o r d 算法，文件在上传时，被分割成大 小相同的数据块，进行负载均衡处理时以文件块为单位。 但一对多和多对多方法也有明显的缺点，系统中会存在特定的目录节点 来接受系统中节点的负载信息并生成策略，这样对目录节点的性能要求很高， 如果目录节点的负载很高就无法完成系统的负载调度工作。然而，此算法在 过载与非过载节点间转移虚服务器，并没有考虑它们之间的位置关系，负载 转移需要消耗过多的带宽和延迟。 哈尔滨t 稃大学硕十学何论文 李振宇【1 2 j 也提出了一种虚服务的方法来完成系统的负载平衡，为了避免 一对多和多对多方法中由于目录节点的过载使得系统负载不均的状况出现， 文中改进了d h t 网络中的负载信息收集策略。文中采用了一种与路由选择信 息协议r i p 相似的策略，每个节点向d h t 网络中的邻居节点发出最大跳数 为k 负载查询请求，收到请求的节点返回自身的负载信息和时间戳。通过这 种方法节点收集到局部网络中节点的负载信息和链路延迟，算法在生成转移 策略不仅考虑了各节点的负载情况，还考虑了节点间的链路延迟，使得虚服 务的转移更加快速。王刊1 3 】提出了一种改进了一对一的方法。在“一对一 的方法中，每个节点都会发出负载探测请求，这样系统中会产生大量的负载 查询消息，降低了系统的性能。文中提出移动代理的概念，每个移动代理就 是一条负载查询消息并由系统生成。它按照d h t 网路访问系统中的节点，并 保存所