（计算机软件与理论专业论文）基于dht技术的数据副本散布与模拟研究.pdf

摘要 摘要 近年来i n t e m e t 的飞速发展和网格技术的出现和发展，对存储系统在容量、 性能、可靠性、分布性以及可扩展性等方面提出了更高的要求，存储领域的研 究也相应出现了新的趋势和发展方向。 在对分布式哈希表( d i s t i l b u t e dh a s ht a b l e ，d h t ) 技术研究的基础上，本 文研究的目标主要是针对广域对等环境下，研究数据副本散布策略，以及引入 副本散布之后系统的数据定位路由的算法模拟，并且给出了模拟结果分析。这 对于构建分布式大规模数据存储系统来讲是重要的基础支持。 本文首先综合当前d h t 技术分析了其中涉及的主要问题，包括该环境下数 据存储的特点和要求。在此基础上，本文讨论了利用完全的冗余方案数据 副本进行研究d h t 环境下的数据可用性和相关性能要求。 c h o r d 作为一种典型的分布式哈希表d h t ，至今一直对其进行了不断的优 化的研究；并且c h o r d 对于其它d h t 来讲具有一定的相通之处。因此，本论文 的研究方法是，通过结合c h o r d 对所提出的副本散布策略实现模拟。这样保证 了策略对于其它的结构化d h t 能够具有一定的通用性。 本文的主要贡献体现在以下几个方面：提出了两种副本散布的策略，分析 实现了散布的自维护算法；并且，结合c h o r d 模拟器加以实现分析。通过分析 实验模拟的结果，这两种策略具有良好的可用性。 夺数据副本的散布策略 本文给出了两种数据散布策略：直接连续副本散布和全局再哈希副本散布 策略。前者将每个节点的所有的数据对象，利用后继列表直接散布在其后继列 表的前若干个节点上散布数据副本。副本定位简单，数据分布均匀，较好的达 到了系统的负载均衡。而后者对于每个主数据对象的各个副本进行再次哈希， 以此确定各个副本的位置。由于副本再次哈希的名称空间和主数据相一致，这 样副本分布于整个d h t 空间，查找定位的代价和c h o r d 一致。 夺数据副本散布的模拟实现和分析 通过各种实验参数下实验模拟，得到这两种策略的实验结果。这两种策略 相比较，在副本查找定位的性能上有一定的相似性。但是在节点的数据散布均 摘要 衡等方面存在较大差异，有待进一步的优化。 最后在进一步的工作中，需要综合考虑性能和可用性等具体量化的要求， 进而优化副本散布的策略。在满足数据可用性的基础上，进一步将提高数据对 象访问的性能。 关键词：分布式哈希表；d h t ；c h o r d ；副本散布：性能 i i a b s l x a e t 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 a c ta n dg r i dt e c h n o l o g yi nr e c e n ty e a r s ，t h e r e q u i r e m e n t so fc a p a c i t y , p e r f o r m a n c e ，r e l i a b i l i t y , d i s t r i b u t i o na n ds c a l a b i l i t yo f t h e s t o r a g es y s t e ms h o u l db em o r ee n h a n c e d t h e r e f o r e ，t h en e wr e s e a r c ht r e n d sa n d d i r e c t i o n si ns t o r a g ef i e l da l ea p p e a r e d o nt h eb a s i so fr e s e a r c ho fd i s t r i b u t e dh a s ht a b l et e c h n o l o g y , t h er e s e a r c hg o a l o ft h i st h e s i sm a i n l ya i m st od e s i g no fd a t ar e p l i c a sp l a c e m e n ts t r a t e g i e s ，a n dr e l a t i v e a l g o r i t h ms i m u l a t i o na n da n a l y s i sf o rr e p l i c a sr o u t i n ga n dl o c a t i o ni nw i d ea r e a p e e r - t o p e e re n v i r o n m e n t m o r e o v e r , t h ee v a l u a t i o na n da n a l y s i so f s i m u l a t i o nr e s u l t a r ed e s c r i b e d t h ew o r ki sa ni m p o 他n ta n df o u n d a t i o n a li s s u ef o rl a r g es c a l eo f d i s t r i b u t e ds t o r a g es y s t e m t h et h e s i sf w s t l ya n a l y s e st h ep r i m a la s p e c t so fd h t s y s t e mr e s e a r c h ，i n c l u d i n g t h ec h a r a c t e r i s t i c sm a dr e q u i r e m e n t so fd a t as t o r a g ei nd h t a n dt h e ni td i s c u s s e s t h ea v a i l a b i l i t ya n dr e l a t i v ep e r f o r m a n c er e q u i r e m e n t so fu s i n gf u l ld a t ar e d u n d a n c y s c h e m e ，d a t ar e p l i c a si nd h t a sat y p i c a lk i n do fd i s t r i b u t e dh a s ht a b l e ，c h o r dh a sb e e nf o c u s i n go n o p t i m i z a t i o ns t u d ya n di th a ss o m ec o m m o np l a c e sw i t hs o m eo t h e rd h t s t os o m e e x t e n t s s o ，t h er e s e a r c hw a y sa n dm e a n so f t h et h e s i sa r et h a td e s i g na n ds i m u l a t i o n o fr e p l i c a sp l a c e m e n ts t r a t e g i e sa r ec o m b i n e dw i t hc h o r d t h e r e f o r e ，i tc a na s s a r e t h a tt h e yw o u l db eg e n e r a l i z e dt os o m eo t h e rs t r u c t u r e dd h t s h i g h l i g h t so fo u rc o n t r i b u t i o n si nt h i st h e s i si n c l u d et h ef o l l o w i n ga s p e c t s t w o r e p l i c a sp l a c e m e n ts t r a t e g i e s a r ep r o p o s e d , a n dt h er e l a t i v ea d a p t i v ep l a c e m e n t a l g o r i t h m sa r ei m p l e m e n t e da n da n a l y z e d f u r t h e r m o r e ，t h es t r a t e g i e sa r ei n t e g r a t e d w i t hc h o r d t h r o u g ha n a l y s i ss i m u l a t i o nr e s u l t s ，i ts h o w st h a tt h es t r a t e g i e sa r e f a v o r a b l ea v a i l a b i l i t y 夺d a t a r e p l i c a sp l a c e m e n ts t r a t e g i e s t w or e p l i c a sp l a c e m e n ts t r a t e g i e sp r o p o s e di nt h et h e s i sa r ed i r e c ts e q u e n c e p l a c e m e n ts t r a t e g ya n dg l o b a l r e h a s h p l a c e m e n ts t r a t e g y t h ef o r m e rd i r e c t l y d i s t f i b u t e sd a t ao b j e c t si ne a c hn o d et os o m ef r o n tn o d e so fi t ss u c c e s s o rl i s t t h e i i a b s t r a c t a d v a n t a g e so ft h i ss t r a t e g ya r er o u t i n ga n dl o c a t i n gr e p l i c a sa r es i m p l e ，d a t ao b j e c t s a r eu n i f o r m e dw h i c hc o u l dl e a dt ol o a db a l a n c e t h el a t t e rr e - h a s h e se a c ho r i g i n a l d a t ao b j e c t ，a n dl o c a t e sc o r r e s p o n d i n gp l a c e sf o ra l lr e p l i c a s t h er e p l i c a sa r el o c a t e d t oe n t i r ed h t s p a c eb e c a u s et h er e p l i c a sr e - h a s h e dn a m es p a c ei se q u a lt oo r i g i n a l d a t ao b j e c t s 夺i m p l e m e n t a t i o na n da n a l y s i so f r e p l i c a ss i m u l a t i o n t h ee x p e r i m e n t a lr e s u l t sa r ea t t a i n e db ye x p e r i m e n ts i m u l a t i o nu n d e rs o m e p a r a m e t e r s t h e ya r ec o m p a r a b l et os o m ee x t e n t si nr e p l i c a sl o c a t i n gp e r f o r m a n c e b yc o m p a r i n gt h et w oe x p e r i m e n t a lr e s u l t s b u tt h ea m o u n to fd i s t r i b u t e dd a t a r e s i d i n gi ne a c hn o d ep r e s e n t sd i f f e r e n ts t a t u s e s a sf o rf u t u r ew o r k s ，i ts h o u l dc o n s i d e rt h es p e c i f i cq u a l i t yr e q u i r e m e n t so ft h e p e r f o r m a n c ea n da v a i l a b i l i t yi no r d e rt oo p t i m i z er e p l i c a sp l a c e m e n ts t r a t e g i e s o n t h eb a s i so fs a t i s f y i n gd a t aa v a i l a b i l i t y , t h er e p l i c a sa c c e s sp e r f o r m a n c ei st oi m p r o v e m o r e k e y w o r d s ：d i s t r i b u t e dh a s ht a b l e ；d h t ；c h o r d ；r e p l i c a sp l a c e m e n t ；p e r f o r m a n c e 1 v ￥8 0 4 9 1 6 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务：学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位敝作者签名= 孝7 乡，舞fp 。3 b 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： i 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： 一：一i j i 一i _ ! ? ：2 0 一 内部5 年【最长手，苟少于5 年) 秘密l o 年( 最长1 0 年，可手1 0 年) 机密2 0 年( 最长2 0 年，可少于2 0 年) 束淼帮蠢 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 0 ! 年r 具刁3 日 第1 章绪论 第一章绪论 针对广域网络环境下的数据存储的需求背景下，本章首先将简要分析研究 问题的提出背景，给出了课题的研究动机。然后，分析了本文研究问题的主要 工作和所要达到的目标；同时，列举了研究课题应用的价值和前景。最后给出 本论文的内容组织。 第一节问题的提出 存储技术一直是人们所关注的一项技术，是计算机科学非常重要的研究领 域之一。8 0 年代末，p a t t e r s o n 等人提出的r a i d 技术【1 ，2 ，3 1 ，将存储领域的研究 推向了一个新的阶段。相关研究成果不断涌现，具有大容量、高性能、高可靠 性等特点的单机存储技术逐渐成熟。9 0 年代中后期，网络技术发展迅速，研究 人员发现，借助于高速网络设备，可构建更大规模、更高性能的存储系统。相 关研究工作迅速开展起来，n a s 、s a n 就是这一时期出现的具有代表性的网络 存储技术，已经得到了较为广泛的应用 4 , 5 1 。 而今，由于网络规模的扩大，人们对网络的使用变得越来越普遍、灵活多 样。特别是近年来i n t e r n e t 的飞速发展和网格技术的出现和发展，对存储系统在 容量、性能、可靠性、分布性以及可扩展性等方面提出了更高的要求，存储领 域的研究也相应出现了很多新的趋势和发展方向。 因此，快速增长着的数据信息以独立、动态的形式存在于广域范围内，同 时数据节点也具有独立和动态性，这形成了广域环境下数据环境。该领域研究 的重心开始将传统的局域存储技术4 ，5 ，6 】转向基于i n t e r n e t 的存储系统发展 7 ，8 ， 9 1 。基于i n t e m e t 的存储系统，与传统单机存储系统和局域存储网络相比，出现 了诸如规模特别巨大、系统变化频繁、故障率更高、更强的数据共享需求等等 新的特性。在这样的环境背景下，非常有必要进行研究广域环境下分布式大规 模存储技术。 针对上述的主要的内容，如何组织和管理这样庞大动态的网络和数据? 在 过去十几年，研究一直围绕着非结构化和结构化的系统组织方式进行的。 第1 章绪论 对于非结构化系统，例如g n u t e l l a 1 0 , 1 1 ，搜索原理是将查询向所有邻居结点 广而告之，并在搜索的过程中计算时间延迟。从本质上说，它在网络中的路由 定位方式采用广度优先( b f s ) 方式，直至找到需要的数据对象。也称为“泛 洪”( f l o o d i n g ) u ”算法。但是，由于非结构化系统具有较大的网络通信量，易 于造成网络拥塞；同时，系统的扩展性成为最大的障碍之一。 为了适应网络和数据规模扩大，近几年来国内外正在逐步转向结构化的系 统研究工作，通过结构化的系统组织方式达到系统高扩展性。目前新一代的数 据定位和路由算法大多采用分布式哈希技术( d i s t r i b u t e dh a s ht a b l e ，d h t ) ， 通过哈希技术实现海量数据到其存储位置的高效映射，通过分布式结构维护超 大规模的哈希表，比较适合于大规模分布式存储系统。这方面已经产生了一些 成果c a n 12 1 、c h o r d 13 1 、p a s t r y 1 4 】和t a p e s t r y 1 5 , 1 6 。此外，还有其它一些d h t 结构组织方式【1 7 1 8 l 。在此基础上，国外正在进行积极有效的研究和探讨广域环 境下存储系统的相关应用研究。例如o l o b u s 联盟【1 9 的数据网格项目d a t a g r i d 2 川 和u c b 的o c e a n s t o r e 8 1 项目等。表1 1 给出了基于d h t 系统和其它组织方式的 比较，不难看出d h t 在各个方面具有明显的优势。 表1 1 基于d h t 系统和其它组织方式的比较 ，抽象性 扩屡鹰曩、负载均衡 i 容错性，可编程性茸组织性 ，结构化d h t高高支持席易于编程支持 集中查找 手符否席手等不支祷 泛洪算法0 乒掰否 击 乒筝支持 值得注意的是，分布式存储中数据对象存储的关键技术并不成熟，有待进 一步发展和完善。例如d h t 方法将节点组织为逻辑拓扑结构，与物理网络拓扑 完全脱节，这显然限制了系统性能的优化。相关的研究对此进行了一些折衷处 理，取得了一些成果。 值得注意的是，这些系统在可用性上做得不够。这些系统大都是依靠节点 的自治性来完成系统构造。节点可以随时加入、离开系统，当系统的存储节点 存在失效时，系统的数据可用性很小。为此，可用性有待进一步提高和加强。 本文侧重于利用数据冗余的副本分布研究，使之能够支持高可用性的分布式大 规模存储系统。 第1 章绪论 第二节研究的主要工作和目标 为了保证数据的高可用性，具有许多数据冗余理论和技术支持。但是，由 于副本适合于广域环境下数据的特点，本文主要讨论利用完全的冗余方案 数据副本进行保证数据可用性。 c h o r d l l 3 是由m i t 于2 0 0 1 年提出并实现的一种分布式哈希表d h t 。鉴于 数据可用性在算法设计中占重要的地位，而目前针对该算法的数据可用性有待 进一步的研究。因此，我们所设计的副本散布策略在c h o r d 的基础上给予实现 模拟。当然，副本散布策略也可应用其它的d h t 实现形式，例如c a n l l 2 】等。 通过提出数据副本散布算法策略，分析实现了散布的自维护算法；并且，结合 c h o r d 模拟器加以实现分析。通过分析实验模拟的结果，这两种策略具有良好 的可用性。本文解决的关键问题主要包括以下两点： 夺数据副本的散布策略 为了保证数据可用性和用户透明访问的性能，要保证数据对象副本的一定 数量和散布策略。数据副本散布策略决定数据副本的散布规律形式，副本的创 建和迁移时机等。在本文中，我们给出了两种数据散布策略：直接连续副本散 布和全局再哈希副本散布策略。同时，也对进一步的副本散布研究工作进行了 简要分析。 夺数据副本散布的模拟实现和分析 在分析c h o r d 算法的基础上，进行了副本散布算法的模拟。引入副本散布 后，分析了相应的c h o r d 算法的改变和优化实现。这两种策略通过实验模拟比 较，在副本查找定位的性能上有一定的相似性。 但是在节点的数据散布均衡等方面表现有较大差异，有待进一步的优化， 使之尽可能地满足用户对数据对象尽可能的访问本地化，从而提高数据对象访 问的效率。 总之，本文基于分布式哈希表d h t 技术，对广域分布式环境下数据对象副 本散布关键技术进行了研究分析。在对研究分布式哈希表技术分析基础上，本 文研究的目标主要是针对数据副本冗余的合理散布，以及引入副本散布之后系 统的数据定位路由的算法模拟，并且给出了模拟结果分析。这对于构建分布式 大规模数据存储系统来讲是重要的基础支持。 第1 章绪论 第三节应用的前景 基于d h t 的存储系统的各种应用，可以有效地利用互联网中散布的大量普 通节点，将存储数据分布到各个节点上。大量的普通节点除了包括各种服务器、 工作站和个人计算机外，还包括各种数字移动设备、数字家电等。利用其中闲 置的存储资源，达到大规模存储的目的。通过利用网络中的大量空闲资源，可 以用更低的成本提供更有效的存储能力。因此，各种应用具有广泛的发展前景 和应用趋势。 夺信息资源共享和搜索。这一直是网络技术发展的重要推动力，也是最典 型的应用。采用结构化的d h t 资源路由定位技术可以有效的管理数据， 提高访问的有效性。副本的研究使得信息共享变得更为便捷。 夺移动广域存储。移动广域存储是指在广域环境下人们能够使用任意移动 设备、通过任意网络、在任意时间都可以获得一定质量的网络数据访问 服务的技术。 夺存储网格。新数据中心的一种表现形式是网格存储模型。虚拟化能够以 全新的模型重新组织数据中心内的各个组件，并将其视作共享资源。其 最终结果是，所有的存储资源、服务器和网络资源都将被虚拟为一个资 源池。这个资源池就是存储网格。网格存储作为一种理想的存储方式， 既可应用于s a n 环境，又可应用于n a s 环境，是网格计算的理想补充。 它提供快速简单的对于容量、性能、服务质量和或连接协议的可升级 性，可对企业所有数据进行统一查看和管理，远远超出当前有限的虚拟 化实现途径，还可优化分布式企业远程数据访问的性能。 利用d h t 支持的数据存储，可为上述的各种应用提供统一的数据存储底层 支持。 第四节论文内容组织 本文的内容组织如下：本章概要的分析了所要研究问题的提出，介绍了研 究的角度、所作的主要工作和目标。同时，给出了应用的前景。 第二章介绍了与此相关的工作，主要涉及各种d h t 的研究现状，介绍了 4 第l 章绪论 d h t 的理论基础。侧重分析了d h t 的核心问题拓扑结构与路由定位和查 找，这是d h t 设计的关键。同时，结合c h o r d 分析了主要的算法。第三章分析 了数据冗余是如何保证数据可用性，数据复制相关研究和分布式大规模存储系 统的研究。 这前面几章的基础上，第四章从数据副本散布的引入，定性地给出副本散 布的评价标准，进而提出了两种数据散布的策略：直接邻接副本散布策略和全 局再哈希副本散布策略。在第六章中对这两种策略在c h o r d 中的进行了模拟实 现，并且分析了由于副本布局的引入影响c h o r d 算法的，并且给出了模拟实验 结果分析。根据数据副本的相关参数改变，权衡分析对路由定位延迟和数据是 否可用进行了分析。 最后一章，对将来进一步的工作进行了展望，期望利用更为动态有效的策 略进行副本散布的研究工作，例如小世界( s m a l lw o r l d ) 模型；以及容错编码 的数据分布研究都是在今后的工作中需要考虑的。最后，对本文的研究工作进 了总结。 第2 章分布式哈希表d h t 基础 第二章分布式哈希表d h t 基础 本章介绍了分布式哈希表d h t 的基础知识。这对于认识和设计d h t 系统， 进而研究数据副本的散布策略起到基础作用。d h t 一直以来作为一种简化的大 规模分布式应用的方法而被提出的。d h t 将数据分散于i n t e m e t 各个节点上。 网络中每个对象都被分配一个难一的标识符，依靠分布的路由表查找定位相应 的分布的数据。典型的d h t 包括c a n 、c h o r d 和p a s t r y 等。 第一节通常的哈希处理 在整个哈希空间内s ，对应的通常操作主要包括：插入、查找和删除等。 下面描述了通常的哈希处理，采用链接地址的方法解决冲突。如图2 1 所示。 查找s e a r c h ( a ，s ) 操作：从集合s 中查找对象a 。对s 【h ( a ) 】指向的链表进行 查找，若a 存在则返回其位置，否则返回空。插入i n s e r t ( a ，s ) 操作：将对象a 插入到集合s 中。利用哈希函数h 计算h ( a ) ；调用s e a r c h ( a , s ) 查询由s h ( a ) 】 指向的链表，如果a 不在该链表中，将其插入到其中。删除d e l e t e ( a ，s ) 操作： 从集合s 中删除对象a 。对s 口a ) 】指向的链表进行查询，若查找到，则将其从 链表中删除。 h ( a ) = i 图2 1 链接地址的哈希处理 m 假设有n 个对象通过某一个哈希函数，存放到哈希表中的1 1 1 个桶中。那 么每个链表的平均长度为负载因子1 3 m 。这样，不成功搜索和插入的平均长度 第2 章分布式哈希表d h t 基础 为代价为n ，m ，而成功搜索的代价约为负载因子的一半。这样数据的搜索等操 作具有较好的效率。 第二节分布式哈希表( d h d 类似于上述的链接地址哈希表处理，分布式哈希表d h t 定义了一个全局的 哈希空间，利用相应的哈希函数将数据对象映射到相应的位置。不同于通常的 哈希表集合s 只是在单个节点进行操作，d h t 将集合s 中数据分布存储于各个 节点之上，需要形成各个数据子集和路由信息。这样，所有的数据都分布于各 个节点上，相应的操作由各个节点根据路由信息分布完成。图2 2 展示的是在 分布式哈希处理时，数据对象k i 的插入和查找的情形。 rv 图2 2 分布式哈希表的分布情形 通过上图，引入“分布”式数据，d h t 产生的关键问题主要表现在以下两 个方面： 夺如何将整个哈希表划分为多个分布式的哈希表? 夺若不能够在本地哈希表中找到所要的对象，如何能够找到拥有该对象 对应的键值所在的哈希表呢? 为了解决以上两点问题，其一，所有的数据对象的应当以唯一的数字键值 来描述，例如可使用s h a 1 1 2 3 j 哈希函数；其二，节点之间能够实现分布韵哈希 表在节点之间的路由信息，从而形成逻辑上的整个对象集合s 。 这就规定了系统中的所有对象都具有全局统一的命名空间。值得注意的是， 节点之间必须能够实现分布的哈希子集在节点之间的转接，由此引入了路由表 第2 章分布式哈希表d h t 基础 ( r o u t i n gt a b l e ) 的概念，这些路由表的转接关系构成了一种逻辑拓扑结构的网 络。该逻辑结构的网络称为覆盖网络( o v e r l a yn e t w o r k ) ，这是建立在现有的网 络之上的网络，对应的数据传输处理实际上仍然在现有的物理网络上进行的。 可以将其认为是现有网络之上的逻辑网络。并且具有相应的拓扑结构。这对于 分析研究数据定位搜索等各种机制提供了底层逻辑支持。覆盖网络具有规模庞 大、不确定性等典型的特征。 这样，在全局统一的命名空间下，组织成何种拓扑、如何实现是问题的关 键。从这个意义上讲，d h t 是构成覆盖网络的数据结构的形式。覆盖网络中节 点的协作提供了哈希表的功能。应用d h t 系统设计时，需要全面地考虑涉及到 的问题。下面是其中涉及几个主要的要求： 夺扩展性：系统必需能够扩展，各个节点可能不知道其它的所有节点。 这样能够构建大规模的覆盖网络。 夺适应性：系统具有动态性，允许节点加入和退出覆盖网络。当若干个 节点加入和退出时，系统必须能够进行重新调整和分布哈希键值对。 夺可靠性：当节点发生失效时，系统必须能够恢复。此外，还要能够解 决网络分割和失效的问题。通常，一种解决方案利用副本完成；这样 一来，副本管理成为一个问题。这是本文主要考虑的问题。 夺性能：性能和有效性是任何系统考虑的主要问题。在覆盖网络系统中， 通常以访问的延迟和信息的交换的带宽来测量性能。 以上的几个问题，几乎涵盖了系统设计的主要方面。当然，在开放的网络 环境下，安全性也是必不可少的方面。 第三节结构化d h t 根据节点间的转接是否有规则的拓扑结构，d h t 系统可以分为结构化的和 无结构化的两种类型。在无结构化的系统中，k e y v a l u e 对的布局完全和重叠拓 扑无关。路由定位算法是按照扩展的方式进行，或者称为“泛洪”算法( f l o o d i n g ) 。 这样，对数据对象的搜索按照宽度优先搜索的方式进行，因此，随着系统规模 增大和动态性增强，可扩展性成为其最大的问题。由此，对于无结构化的d h t 研究，也出现了不少的相关优化研究。 结构化的d h t 系统中节点之间具有规则的拓扑结构。这样，通过对象的哈 第2 章分布式哈希表d h t 基础 希键值根据拓结构路由定位相应的目标节点。除了早期的几个d h t 系统外，现 今大都是结构化的d h t 系统。 2 3 1 设计思路 通常的设计思路是给各个节点赋予特定的i d ( 例如，随机选择的方法) ， 按照某种规则为节点赋予数据对象i d 。这样，数据对象x 存储于与其较近的该 节点。“近”的概念是这样定义的：数据对象x i d 和节点的i d 较为“接近”。 若查找对象兄如何查找定位相应节点呢? 这就需要知道一些节点信息。 但一个节点不可能了解所有的节点的状态。这样，一个节点只需跟踪一小部分 其它的节点。也许当前节点不知道那个节点拥有正但是知道哪个节点比自身 更了解情况。所以，可以通过一定的中间节点进行搜索兄但是，经过的节点 数量不能过多；否则，时间延迟过大，从而造成系统不可用。例如，通过o ( 1 0 9 n ) 个其它的节点查找定位是个不错的选择。 综合上述的要求，一个完整的d h t 算法应该包括以下几个方面： 夺定义节点和数据对象i d 的名称空问； 夺数据对象i d 向节点i d 的指派，形成拓扑结构； 夺定义每个节点的路由表内容； 夺说明节点加入、离开和故障算法； 夺说明利用路由表的查找算法： 拓扑结构是指分布式系统中各个计算单元之间的物理或逻辑的互联关系， 节点之间的拓扑结构是确定系统类型的重要依据。 确立了d h t 的拓扑结构，数据资源分布在各个独立的节点上，如何高效地 索引、查找、定位以及访问这些数据信息资源是另一个需要关注的重要问题。 这个核心的问题就是数据对象的路由定位问题。将数据对象的哈希值映射到网 络中特定的节点，这需要实现协作路由定位算法。同时，哈希表分布于各个节 点上的数据对象子集尽可能的均匀，以便保持各个节点的负载均衡。由此，不 可避免地引入副本机制来解决。 这涉及的研究内容体现在以下几个主要的方面： 夺数据对象的命名空间和拓扑结构。广域范围内各个节点的松耦合性， 决定了数据对象具有独立性和动态性特征。如何组织和优化数据对象， 第2 章分布式哈希表d h t 基础 这是研究首要解决的问题。 夺数据对象的选择与路由定位。这并不是传统的网络路由机制，是建立 其上的对数据对象的路由定位。选择较短访问延迟的数据，这不仅仅 与数据对象的存储位置相关，而且需要综合考虑网络的多方面性能因 素。 夺数据对象的副本复制与迁移。根据分布式网络的动态变而化的特征， 将数据对象进行实时地有效地复制和迁移，达到数据对象副本存储优 化的目的，决定了数据对象及其副本散布存储合理的位置和数据对象 的各个副本数量两个主要的方面。 总之，在构造过程中需要解决系统中所包含的大量节点如何命名、组织以 及确定节点的加入、离开方式和出错恢复等问题。 针对上述的问题，近几年来，不断提出了各种结构化的d h t 网络。例如 c a n 1 2 1 ，c h o r d i l 3 1 ，p a s t r y 14 1 ，t a p e s t r y l l 5 ，1 6 1 p - g r i d 1 7 1 和s k i p n e t t 吲等。下面几 个小节分别描述了它们的构造主要方面，最后小节对它们进行了关键的性能指 标比较。 2 3 2c a n c a n ( c o n t e n ta d d r e s s a b l en e t w o r k s ) 是由s y l v i ae ta 1 珥提出一种分布式 网络结构。c a n 将标识符映射到d 维的笛卡儿坐标空间。该坐标空间内n 个节 点将空间划分为n 个区。每个节点将标识符的映射到对应的区。因此，c a n 把 节点模型化在一个超环空间中的区域。每个节点都和这个超环空间的超立方体 区域相联系，它的路由信息保存了那些与它相邻的超立方体区域相应的节点。 图2 3 二维c a n 数据的插入和查找 l o 第2 章分布式哈希表d h t 基础 c a n 的基本操作包括插入、查找和删除( 关键字，值) 对。此外，每个节 点还保存适量的邻接区的信息。对每个特定关键字的插入( 或者查找、删除) 请求由中间的c a n 节点进行路由直到到达包括该关键字的c a n 节点所在的 区。图2 3 显示了一个二维c a n 的笛卡儿坐标空间划分和相应的数据的插入和 查找的操作。 当加入( 关键字，值) 时，例如( k 1 ，v i ) ，使用统一的哈希函数把关键字 k l 映射成坐标空间中的点p 。那么这个值将被保存在该点所在的区域的节点中。 当需要查询关键字k l 对应的值时，任何节点都可以使用同样的哈希函数找到k l 对应的点p ，然后从该点对应的节点取出相应的值。 在c a n 中，路由是逐步转发消息到与此消息在超环空间内最近的节点。 c a n 性能由其维数决定。对于一个被划分为n 个相等区的d 维空间，平均路径 长度是d n 删h o p s 且单个节点维护2 d 个邻居。这个结果意味着对一个d 维的空 间，可以在不增加每个节点状态的情况下增加节点数，同时平均路径跳是 o ( d n l 。 通过对c a n 的简单描述，可以看出c a n 具有如下几个特性： 夺c a n 的设计完全是分布式的，它不需要任何形式的中央控制节点。节 点只需维护少量的控制状态而且状态数量独立于系统中的节点数量。 夺节点状态自组织。节点动态加入和离开，c a n 系统进行自动维护。 夺c a n 支持容错冗余路由。在c a n 系统中，空间中的两个端点存在多 条路由路径，因此即使节点的一个或多个邻居崩溃了，这个节点能够 自动路由到另一条合适的路径。 2 3 3c h o r d c h o r d 【l3 】系统是由i s t o i c ae ta 1 提出的，建立在相容哈希( c o n s i s t e n t h a s h i n g ) 1 23 j 之上。假定环的名称空问是s = f 乳2 ”一，。一般m 取为1 2 8 。所有 的节点被映射到相容哈希环上，通过哈希每个节点的i p 地址来指定唯一i d s 。 在相容哈希中，每个数据对象都保存在它的后继( s u c c e s s o r ) 节点中，后继节 点是节点标识符大于等于数据对象k 标识符的第一个节点。 这样，i d 是逻辑的被安排在一个环形指针空间上的。一个k e y 的i d 是通 过对这个k e y 进行哈希得到的。c h o r d 用s h a 一1 ( k e y ) 来获取i d 的。在i d 空 第2 章分布式哈希表d h t 基础 间中，一个值为k 的k e y 就会被分配到第一个i d 值大于或等于k 的结点上，即 后继节点上。如图2 4 所示。 图2 4c h o r d 的拓扑构造 当结点n 不知道数据对象k 的后继结点时怎么办? 在c h o r d 中，每个结点 使用连续哈希来维护一个后继指针。通过该后继指针可以依次顺序查找到数据 对象k 所对应的节点。但是，如果只使用后继指针的话，要定位一个对应于某 一k e y 值的结点是相当慢的，它所消耗的时间将与系统中的结点总数成比例关 系。为了使查找变的更加的快速，c h o r d 使用了一个叫做查找表( f i n g e r t a b l e ) 的结构。 这样每个节点必须维护主要是由查找表构成的路由表。节点n 查找表的第 i 项是大于等于n + 2 1 的第一个节点，其中i 0 ，1 ，m 1 ) 。由i d 标识的数 据项保存在节点i d 的后继节点中。同时，为了维护拓扑结构，每个节点还保留 了前驱节点( p r e d e c e s s o r ) 信息。 如果在节点n 查找数据对象k ，通过节点n 能够找到一个结点的标识符更 接近k ，那么这个结点将会更大可能知道该信息所驻的节点。根据这一特性，n 将查找它的f i n g e r t a b l e ，找到第一个结点标识符大于k 的结点j ，并询问结点j ， 看j 是否知道哪个结点更靠近k 。通过重复这个过程，n 最终将会知道k 的后继 结点。 如图2 5 所示，每个结点都拥有一个查找表。对于结点n 来说，它的查找 表中的第i 条包含了在i d 环上后继于n 结点2 l - 1 跳数的i d 。f i n g e r 表中结点 n 8 的后继不是n 8 ，而是所有与n 8 相差2 1 _ 1 个跳数的结点。如i - 6 ，即n 8 的 一个后继应是n 4 0 ，但这个位置若还没有结点加入，则指向该位置的下一个有 1 2 第2 章分布式哈希表d h t 基础 效结点n 4 2 。 为了找到负责k e y 为k 的结点，我们必须找到k 的后继；要找到k 的后继， 我们的查询要用f i n g e r 表路由，一步步的接近那个后继结点，一旦发现k 落在 一个结点和它的后继之间，那么当前结点的后继结点就是k 的后继。这种迭代 的查找方法至少降低了到达k 后继的路程的一半，因此，在一个这样的c h o r d 系统中的每次查找的平均消息传递数目是o p o g n ) 。 f i a 壮t t a b l e 图2 5 查找表和查找示例 当一个新的结点加入这个环时，其中的少数的几个k e y 将要从它的后继结 点移动到新的结点上。当由结点离开时，那么被分配在这个结点上的所有的k e y 将重新分配到这个结点的后继结点上，其余结点上的k e y 保持其原状态。所以， 这种连续哈希的一个最大优点就在于，当结点加入或离开时只影响到小部分的 k e y 值映射。 p a s t r y 和下一小节描述的t a p e s t r y 所采用的路由定位算法都是基于 p l a x t o n c l l 】提出的算法思想。该算法思想是通过找到与查找消息中所查找的标识 符共享最长的前缀的节点，重复进行同样的操作，直到查找到对应的目标。每 个节点具有和其自身相匹配各种前缀但下一数位不同的标识符的邻接节点。对 于具有n 个节点的系统，每个节点具有o ( 1 0 9 n ) 个邻居，并且一个路由路径至 多经过o ( 1 0 9 n ) 跳。 第2 章分布式哈希表d h t 基础 p a s t r y 的名称空间的构造同c h o r d 一样，都是m 位的i d 空间。i d 的表示 每个数位以2 6 为基数，共m b 个数位。而和c h o r d 不同之处是，数据对象依据 i d 分配于在数值上接近的节点上。如图2 6 所示。 图2 6 p a s t r y 的名称空间 p a s t r y 采用基于前缀的查找算法。基于前缀的路由，假设从节点a 路由到 节点b ，在每一跳，例如第i 跳时，中间经过的节点至少要和b 具有1 位前缀。 每个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 ) 和叶集( 1 e a f s e t ) 等三方面的路由信息。每个节点的路由表保存了具有各种前缀的节点信息。 同时，p a s t r y 通过邻居集的局部性信息达到路由消息到达距离其最近的节点。 叶集保存了在数值上和当前节点最为接近的一些节点信息。图2 7 给出了系统 中某个节点的路由信息的实例。 p a s t r y 的路由过程依据上面的路由信息进行。当收到一条消息时，结点首 先检查消息的关键字是否落在叶集中。如果是，则直接把消息转发给对应的结 点，也就是叶子结点集合中结点号和关键字最接近的结点。 如果关键字没有落在叶集中，那么就将使用路由表进行路由。当前结点将 会把消息