（计算机应用技术专业论文）结构化p2p中的数据副本研究.pdf

天津师范大学硕士学位论文 摘要 p 2 p 处在一个动态的环境中，网络结构不断地发生变化，使得建立和维护一 个p 2 p 网络拓扑结构并有效的搜索网络中的资源变得异常复杂。目前，p 2 p 分布 式模式中有非结构化和结构化两种基本拓扑类型。非结构化p 2 p 网络大部分利 用泛洪机制进行搜索，但是可扩展性和查询效率比较低，控制信息的泛滥消耗了 大量带宽并很快造成网络拥塞甚至网络的不稳定。结构化p 2 p 网络的主流方法 是采用分布式哈希表( d h t ) 技术，有效地减少了控制信息的发送数量，从而增强 了p 2 p 网络的扩展性。 本文对结构化p 2 p 中的副本技术进行了探讨和研究，在结构化p 2 p 中，副 本技术是一种最为常用的分布式数据管理机制。通过为系统中的文件增加副本， 保存冗余的文件数据，可以十分有效的提高文件的可用性和可靠性，避免在地理 上广泛分布的系统节点由于网络的断开或机器故障等动态不可测因素引起的数 据丢失。然而这也带来了副本维护的问题，当数据进行升级时，容易造成副本内 容的不一致。特别是当升级进行时，存储副本的节点离线或者更新内容不可达， 当离线节点再次加入网络，导致副本内容不一致，使得结构化p 2 p 中的查询难 以返回最新的数据版本。 针对数据副本内容一致性问题，本文提出了一个基于网络时间协议的版本号 生成服务。通过此服务，可以为网络中副本生成单调递增的版本号，借助版本号 就可以检索到最新版本，提高了生成数据版本号的可靠性。最后，对基于网络时 间协议的版本号生成服务进行仿真测试，并分析节点数目和失效率对该模型查找 效率的影响。 关键词：对等网络，哈希表，副本 2 天津师范人学硕士学位论文 a b s t r a c t p 2 pi si nad y n a m i ce n v i r o n m e n t ，t h en e t w o r kt o p o l o g yc h a n g e sc o n s t a n t l y , m a k e s t h ee s t a b l i s h m e n ta n dm a i n t e n a n c eo fap 2 pn e t w o r ka n ds e a r c h i n gn e t w o r kr e s o u r c e s e f f i c i e n t l yb e c o m ee x c e p t i o n a l l yc o m p l e x a tp r e s e n t ，t h ep 2 pd i s t r i b u t e dm o d e lh a s t w ob a s i ct y p e s ：u n s t r u c t u r e da n ds t r u c t u r e dt o p o l o g y m o s tu n s t r u c t u r e dp 2 pn e t w o r k u s e saf l o o d i n gm e c h a n i s mf o rs e a r c h i n g i th a saf a i r l yh i g hs t a b i l i t y , b u ts c a l a b i l i t y a n dq u e r ye f f i c i e n c yi sr e l a t i v e l yl o w t h es p r e a do fc o n t r o li n f o r m a t i o nc o n s u m e sa g r e a td e a lo fb a n d w i d t ha n dv e r yq u i c k l yc a u s en e t w o r kc o n g e s t i o na n de v e nn e t w o r k i n s t a b i l i t y t h es t r u c t u r ep 2 pn e t w o r k sm a i n l ya d o p td i s t r i b u t e dh a s ht a b l e ( d h t ) t e c h n o l o g yt oe f f e c t i v e l yr e d u c et h en u m b e ro fc o n t r o li n f o r m a t i o n i ti n c r e a s e sp 2 p n e t w o r ks c a l a b i l i t y , b u ti th a sp o o rs t a b i l i t y a tt h es a m et i m e ，t h et o p o l o g yb a s e do n d h ti su s u a l l ym u c hm o r ec o m p l e xt h a nu n s t r u c t u r e dn e t w o r ki nm a i n t e n a n c ea n d a l g o r i t h mo fr e p a i r i nt h i sp a p e r , w es t u d yt h ep l a c e m e n tt e c h n o l o g yo fr e p l i c ai ns t r u c t u r e dp 2 p ，t h e p l a c e m e n tt e c h n o l o g yo fr e p l i c ai st h em o s tc o m m o nt e c h n o l o g yi nad i s t r i b u t e dd a t a m a n a g e m e n ts y s t e m t h r o u g hi n c r e a s i n gt h er e p l i c a ，c a nb ev e r ye f f e c t i v et oi m p r o v e t h ea v a i l a b i l i t ya n dr e l i a b i l i t yo ft h ed a t a a v o i dp e e rw h i c hi sw i d e l yd i s t r i b u t e dl o s e s d a t a , b e c a u s eo fn e t w o r ko rm a c h i n ef a i l u r e s a n do t h e ru n p r e d i c t a b l ef a c t o r s h o w e v e r ，w h e nt h ed a t au p g r a d e s ，i ti se a s yt o c a u s er e p l i c ai n c o n s i s t e n c i e s e s p e c i a l l yw h e nt h eu p g r a d ei np r o g r e s s ，a n dr e s p o n s i b l ep e e ru n r e a c h a b l e w h e n t h ep e e rr e - j o i nt h en e t w o r k ，w i l lc a u s er e p l i c ai n c o n s i s t e n c y s oaq u e r yi ns t r u c t e d p 2 p i sd i f f i c u l tt or e t u r nl a t e s tr e p l i c a i no r d e rt os o l v et h ep r o b l e mo fr e p l i c ai n c o n s i s t e n c y ，w ep r e s e n t san t p - b a s e d v e r s i o ng e n e r a t o rs e r v i c e i tc a ng e n e r a t em o n o t o n i c a l l yi n c r e a s i n gv e r s i o nn u m b e r u s i n gv e r s i o nn u m b e r , w ec a l lg e tt h el a t e s td a t a c o m p a r e dw i t ht h ep a p e r 1 ，i m p r o v e t h er e l i a b i l i t yo fs y s t e m i na d d i t i o n ，w em a k eas i m u l a t i o na n dt e s t ，a n da n a l y s i s e f f e c t i o no nr e s p o n s et i m e ，w h e nt h en u m b e ro fn o d e sa n dt h ef a i l u r er a t ec h a n g e k e yw o r d s ：p e e r - t o - p e e r ，d h t ，r e p l i c a 3 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得天盗逝范大鲎或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示 了谢意。 签名：王丝 日 期：塑啦z 学位论文版权使用授权书 本人完全了解天津师范大学有关保留、使用学位论文的规定，即：学校有权将学位论 文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、 汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的论文在解密后应遵守此规定) 签名：至逸 导师签名：日期：21 1 乞么：z 天津师范大学硕士学位论文 第一章绪论帚一早珀下匕 1 1 论文的研究背景 对等网络( p e e r - t o p e e rn e t w o r k ，简称p 2 p ) 技术是目前流行于国际计算机 网络技术研究领域的一个热点，在一年多时间里，技术先后出现在国际各大主流 杂志和学术期刊上，并被财富杂志誉为将改变因特网未来的四大新技术之一， 甚至被认为是无线宽带互联网的未来技术。网络不仅为个人用户提供了前所未有 的自由和便利，同时也试图有效地整合互联网的潜在资源，如计算资源、带宽资 源、存储资源等，将基于网页的互联网转变成动态存取、自由交互的海量信息网 络。技术的发展将影响整个计算机网络的概念和人们的信息获取模式，真正实现 “网络就是计算机，计算机就是网络”的梦想。 p 2 p 网络是一种具有较高扩展性的分布式系统结构，其对等概念是指网络中 的物理结点在逻辑上具有相同的地位，而并非处理能力的对等。技术的实质在于 将互联网的集中管理模式引向分散管理模式，将内容从中央单一结点引向网络边 缘，从而充分利用互联网中众多终端结点所蕴含的处理能力和潜在资源。跟传统 的集中式客户服务器模型相比较，模型弱化了服务器的概念，系统中的各个结点 不再区分服务器和客户端的角色关系，每个结点既可请求服务，也可以提供服务， 结点之间可以直接交换资源和服务而不必通过服务器。 客户端客户端客户端客户端 图1 1 传统网络模式和对等网络模式对比 事实上，并不是新概念，自从世纪年代因特网出现以来，它就存在了。从某 种意义上说，它是向着互联网本质的回归，但是人们却一直没有意识到它的存在， 直到n a p t e r t l j 的出现才使人们看到了它的魅力所在。 天津师范大学硕十学位论文 p 2 p 改变了人们对于互联网的理解和认识，激发了人们用新的方式来组织网 络中的各种资源，使人们在网络上的交流变得更加简单、自由和直接。正因为这 些特点，p 2 p 网络作为计算机网络的一个新兴的研究领域，在短短的几年时间里 就经历了一系列的快速发展。 1 2 本文的主要研究内容 本文着重研究结构化p 2 p 中的数据副本问题，讨论了如何利用结构化p 2 p 的网络特性来解决副本不一致。本文的主要研究内容如下： 研究了数据副本关键技术，包括在数据复制过程中，p 2 p 系统如何根据当前 网络的性能机动地选取最优的通信路径来定位最近的副本或者将远程副本放置 到离数据请求结点最近的位置上，以及如何利用延迟估算技术能够有效估算出分 布式系统中任意两个结点之间的网络距离，从而可以在结点通信时选取最优路 径，降低定位副本和放置副本时的通信开销。 研究了在结构化p 2 p 中副本一致性管理所存在的问题，提出了基于网络时 间协议的版本号生成器和副本管理服务，基于网络时间协议的版本号生成器可以 对每一个关键字生成单调递增的版本号，副本管理服务通过版本号，可以检索到 最新的数据副本。结合结构化p 2 p 的特性，设计了一个基于关键字的数据副本 一致性管理模型，并对该模型的主要性能指标进行了仿真实验，最后对实验数据 进行分析。 1 3 论文的组织结构 本论文可以分为六章，论文的结构安排如下： 第二章：主要介绍与论文研究相关的一些基础知识，对p 2 p 网络的研究现 状进行了阐述与总结，包括p 2 p 网络技术的发展概况，典型的p 2 p 网络应用及 其分类，支撑p 2 p 应用的p 2 p 网络技术及其分类，重点描述了四种结构化p 2 p 网络的覆盖网络结构和路由机制，形成本论文的研究基础。 第三章：研究了数据复制技术和延迟估算技术的现状。p 2 p 系统如何根据当 前网络的性能机动地选取最优的通信路径来定位最近的副本或者将远程副本放 置到离数据请求结点最近的位置上。 第四章：结合结构化p 2 p 的特性，分析结构化p 2 p 中数据副本管理存在的 问题，并提出了基于网络时间协议的版本号生成器和副本管理服务，基于网络时 2 天津师范人学硕士学位论文 间协议的版本号生成器可以对每一个关键字生成单调递增的版本号，副本管理服 务通过版本号，可以检索到最新的数据副本。 第五章：以结构化p 2 pc h o r d 为例，搭建实验平台，给出了设计过程，并设 置了相关参数，最后对该模型进行了仿真实验，分析了节点数目和失效率对该模 型查找效率的影响。 第六章：对本文进行了总结。 3 天津师范人学硕士学位论文 第二章结构化p 2 p 当前网络研究的重点正在从传统的网络层研究转移到应用层，通过在应用层 部署一层o v e r l a y 网络的方式来增强网络的功能及性能，并以服务的形式、开放 的接口提供给用户。 目前，以p 2 p 网络技术为基础的o v e r l a y 网络的研究已取得了许多成果，这 一章主要对p 2 p 网络的研究成果进行阐述，以此形成论文的研究基础。主要内 容包括：p 2 p 网络技术发展概况和几种典型结构化p 2 p 网络的自组织管理模式。 2 1p 2 p 网络技术发展概况 网络研究领域，术语对等( p e e r - t o p e e r ) 最早来源于a r p a 网络体系结构中 的对等层的概念【2 1 ，分层原则是网络协议设计中的重要设计思想，在对等层上传 送当前层的协议数据单元p d u ，按照协议进行对等层之问的通信，进而实现通 信实体间网络通信过程。 集群( c l u s t e r ) 技术【3 】的研究设计中，也涉及到对等的概念，不过强调的是 多个节点( 一个多任务系统代表一个物理节点) 间的物理对等。通过高速网络将 节点连接成规则的物理拓扑，以便基于消息传递机制的并行应用调度的顺利实 施，节点间消息传递的路径与网络拓扑相关，即路由算法的设计与特定的网络拓 扑形状密切相关。部分并行机计算技术中则是考虑c p u 级的对等互联关系。而 对等网络( p 2 p 网络) 的研究中，则强调节点间逻辑对等的设计理念。i n t e r n e t 中隶属于不同物理网络中的异构节点，通过o v e r l a y 的联网方式，自组织建立起 一个环型拓扑结构的p 2 p 网络，网络拓扑中的节点呈现逻辑对等的互联关系。 2 1 1p 2 p 网络应用分类 p 2 p 网络应用主要包括：文件共享、普适计算、协同工作、网络存储、应用 层多播、网络计算环境的构建、网页缓存等等。 文件共享是p 2 p 网络中最为典型的应用。目前人们所采用的基于c s 模式 的文件共享方式，主要包括：w e b 、f t p 等文件下载服务，其中w e b 、f t p 服务器 经常成为系统的性能瓶颈。目前采用p 2 p 网络技术的文件共享应用项目包括： n a p s t e r 、f r e e n e t 、g n u t e l l a 4 1 、c f s 、f r e eh a v e n 、l i m e w i r e 、o h a h a 等，p 2 p 文 4 天津师范大学硕士学位论文 件共享服务充分整合了散布于整个广域网范围内的各类文件资源，该类文件服务 系统区别于传统的c s 模式文件服务器最大的优点在于单点瓶颈的消除，网络中 的端用户节点不单是文件的需求者，亦作为存放部分文件资源的服务器端向其他 端用户提供服务。 s e t i h o m e 、c o n d o r 等p 2 p 研究项目致力于计算力资源的整合，通过将不 同地点的计算机连接起来，以形成强大的、可以超过世界上任何一台超级计算机 的计算能力，该类研究可归为普适计算的范畴。虽然，超级计算机运算能力有了 很大的提高，但是，还是不能满足许多强计算要求的科学研究的需要，如生物医 学、航空航天、地质气象等，计算力资源整合项目的研究可应用于此类科学计算 环境的构建。另一方面，可以帮助企业完成大规模的数据处理，通过整合企业内 部的闲散计算能力和资源，在不增加企业成本的前提下，可以大幅提升企业的计 算能力。 g r o o v e 5 】是p 2 p 协同应用软件的典型代表，其用户可以直接进行实时的协同 工作。协同工作是指多个用户之间利用网络中的协同计算平台互相协同来共同完 成某项任务，一般的协同应用包括：实时通信、白板系统、语音通讯、视频会议 等基本的功能。由于协同应用中的用户规模数较大，数据通信量较多，采用传统 的中心节点服务方式很难满足这种应用，如果采用p 2 p 网络的对等联网方式可 以不再需要目前协同工作中的中心服务器，参与协同工作的计算机之间可以建立 直接联系以进行协同工作。 网络存储一直是人们所关注的一项网络应用技术。p a s t 6 】是美国r i c e 大学 联同微软研究院开展的提供面向整个互联网的存储服务的项目，其路由算法是 p a s t r y 。u cb e r k e l e y 开展的o c e a n s t o r e 【7 】项目也是提供面向整个互联网的存储 服务，该项目中的路由算法采用的是t a p e s t r y 【1 6 。该类应用通过整合数目庞大 的零散存储资源，不仅可以提供海量数据的存储以及文件共享服务，而且具有很 强的鲁棒性，对于当前对网络造成较大危害的d o s ( 服务失效攻击) 、d d o s ( 分 布式服务失效攻击) 几乎难以构成威胁。 网络计算环境建设的目标是将地理上位置分散的计算设施、存储设备、仪器 仪表等集成在一起，建立一个通用的面向服务的基础支撑环境，从而实现i n t e m e t 上计算资源、数据资源和服务资源的有效聚合和广泛共享，进而建立一个能够实 5 天津师范人学硕士学位论文 现区域或全球合作或协作的虚拟科研和实验环境，支持以大规模计算和数据处理 为特征的科学活动。鉴于结构化p 2 p 网络在资源管理过程中特有的自组织特性、 强大的可缩放性、以及资源语义路由等功能特性，可以利用p 2 p 网络技术实现 网络计算环境中的资源管理，以向上层提供一个分布的、自组织的统一资源池。 网络科学计算环境可以解决超级计算机解决不了的问题，虽然面前的超级计算机 运算能力有了很大的提高，但还是不能满足许多强计算要求的科学研究的需要， 利用p 2 p 网络技术所构建的网络科学计算环境，通过将不同地点的计算机连接 起来，形成强大的计算能力，可以超过世界上任何一台超级计算机。 s q u i r r e l 8 】项目所研究的是一个基于结构化p 2 p 网络的分散式网页缓存系统， 其基本路由算法为p a s t r y ，节点所属的本地缓存形成一个广域网范围内的网页缓 存，其一致性问题尚需进一步研究。 p 2 p 网络技术确切的定位应该是一种新型的网络中间件技术，以上所述的各 种不同类型的p 2 p 网络应用则是基于p 2 p 网络技术构建的具体的分布式应用。 2 1 2p 2 p 网络基本性质 p 2 p 网络技术作为一种典型的o v e r l a y 网络实现技术，具备如下三个方面的 基本性质： ( 1 ) 对等性 节点间对等的逻辑互连关系是p 2 p 网络重要的基本性质之一，其实质是将 基于c s 架构的集中管理模式替代成分散管理模式。将共享资源的位置从单一服 务器节点引向网络的边缘，从而充分利用互联网中规模庞大的端节点所蕴涵的处 理能力和各类资源。节点不再区分客户端、服务器端等角色关系，每个节点既是 客户端、也是服务器端；所有资源和服务的交换都是在节点间完成的，而不必通 过专门的应用服务器。 ( 2 ) 易部署性 p 2 p 网络的构建是通过在应用层进行部署，有效地屏蔽了不同网络、操作系 统、计算机硬件、以及编程语言等所带来的异构性。并以服务的形式、开放的接 口提供给用户，保证了整个p 2 p 网络及其应用的功能实现是易于扩展的。 ( 3 ) 自组织特性 6 天津师范大学硕十学位论文 以g n u t e l l a 、f r e e n e t 等为代表的无规则拓扑p 2 p 网络以及以c a n 、c h o r d 、 t a p e s t r y 、p a s t r y 等为代表的结构化拓扑p 2 p 网络所采用的都是具备自组织特征 的管理模式。自组织管理模式下的p 2 p 网络中不存在体系结构上的单点失效问 题，因此具备先天的容错性及鲁棒性。 2 2 结构化p 2 p 网络 p 2 p 网络按照资源组织与定位方法可以将其简单地分为非结构化p 2 p 网络 ( u n s t r u c t u r e dp 2 pn e t w o r k ) 和结构化p 2 p 网络( s t r u c t u r e dp 2 pn e t w o r k ) p 】。 非结构化p 2 p 网络是一种资源位置和网络拓扑结构松散相关的对等网络。 这类网络的主要思想是在网络中进行洪泛( 或受限洪泛) ，资源位置不需要按照网 络结构进行精确的定位，每个节点维护局部相邻节点路由表即可，最典型的就是 g n u t e l l a l 。其白组织性和扩展性较好，但网络中重复消息量过大，占用带宽，网 络负载过大，且安全性较低。 结构化p 2 p 网络是一种资源位置与网络拓扑结构紧密相关的对等网络。这 类网络的主要思想是在i p 网络的基础上建立一个覆盖( o v e r l a y ) 网络。资源的定位 指针位于指定位置( 与覆盖网络的结构紧密相关，可准确描述) ，资源i d 与资源存 储位置通过分布式路由表进行映射。目前的结构化p 2 p 大都基于分布式哈希表 ( d h t ) 。基于d h t 的分布式检索和路由算法因为具有查找可确定性、简单性和 分布性等优点，正成为国际上结构化p 2 p 网络研究和应用的热点。哈希表作为 一种数据结构，可以在资源的存储位置( v a l u e s ) 和它的关键字( k e y s ) 之间建立一 个确定的一对一映射关系。分布式哈希表，顾名思义就是把哈希表分散到p 2 p 网络的各个节点上。即使用一致性哈希函数( c o n s i s t e n th a s h i n gf u n c t i o n ) 1 0 】，来实 现映射，将资源和节点均匀地映射到一个标识空间( i d e n t i f i e rs p a c e ) 中，每个节点 维护有限的邻居信息和路由信息完成资源的定位。分布式哈希表在节点失效、遭 受攻击和突发性高负载面前都能表现出很好的健壮性；具有良好的可扩展性，能 以较低系统丌销获得较大的系统规模；可以自我配置，不需要手工干预就可以自 动把新节点加入到系统中：能提供简单灵活的接口，可以为多个p 2 p 应用同时使 用。 结构化p 2p 网络通过每个节点维护较少的路由信息即可有效地实现查找， 取消了洪泛机制，大大减少了网络中的信息量。但由于覆盖网络结构维护、节点 7 天津师范大学硕十学位论文 异构性及逻辑网络与物理网络匹配等问题使得系统更为复杂，故还有很多方面需 进一步研究，使其更有利于实际应用。当前以加州大学伯克利分校的c a n 和 t a p e s t r y 、麻省理工学院的c h o r d 、及微软研究院的p a s t r y 为代表性研究项目。 2 2 1c a n c a n 一内容访问网络( c o n t e n t a d d r e s s a b l en e t w o r k ) ，采用基于网格的分 布式哈希表( d h t ) 。其设计完全是分布式的，没有任何形式的中央控制点。具有 可扩展性、容错性和完全自组织的优点。 2 2 1 1c a n 的覆盖网络结构 c a n 基于虚拟的d 维笛卡儿坐标空间，动态地将整个坐标空间分配给系统 中所有节点，每个节点负责互不相交的一块儿区域。这个虚拟的坐标空间完全是 逻辑上的，与物理网络不相关。 当一个新的节点加入网络时： ( 1 ) 新节点必须首先找到一个已经在c a n 中的节点。 ( 2 ) 新节点使用c a n 的路由机制找到一个区域将要被分裂的节点。 ( 3 ) 然后原有区域的邻接区域必须被告知发生了分裂，以便新节点能被别的 节点路由到。 当节点离开c a n 时，它的区域被c a n 系统收回，分配给其他仍然在系统 中的节点。由某个节点来接管这个区域和所有的键值对数据库：如果这个区域可 以和相邻区域合并形成一个大的区域，那么c a n 将执行合并操作。如果不能， 则该区域将交给其邻居节点中所负责区域最小的节点，它将临时负责两个区域 详细过可参见文献3 。 天津师范大学硕士学位论文 图2 1 二维c a n 坐标空间的划分 如上图所示，为d 绍时二维笛卡儿坐标空间中的一个划分，其中7 个节点分 别负责一块儿互不相交的坐标区域：a ( o 0 4 ，0 7 1 ) ，b ( o ，4 1 ，0 7 1 ) ，c ( o 0 3 ， 0 - 0 7 ) ，d ( 0 3 - 0 7 ，o 3 - 0 7 ) ，e ( o 7 1 ，0 3 0 7 ) ，f ( 0 3 - 0 7 ，0 0 3 ) ，g ( o 7 1 ，0 - 0 3 ) 。 资源的关键字、值对( k e y ，v a l u e ) 存放在这个虚拟的坐标空间中。例如，存放( 1 ( 1 ， v 1 ) ：使用一个统一哈希函数把关键字k l 映射为坐标空间中的一个点p ，则该键值 对( k 1 ，v 1 ) 就被存放在所负责区域包含点p 的节点中。c a n 中的节点自主地加入 虚拟坐标空间描述的覆盖网络，每个节点获取并保存一部分节点的i p 地址，这 部分节点为所负责的坐标区域与该节点所负责的坐标区域相邻接的节点。节点区 域相邻接是指，在d 维坐标空间中，当两个区域在d 1 维上都覆盖相同的跨度在 另一维上相互邻接，那么这两个区域相邻接例如图2 1 中d 和e 的区域相邻接， 因为它们在纵坐标上的区域跨度相同都是( o 3 0 7 ) ，而在横坐标上相邻，故是邻 接节点：而a 和c 的区域不相邻接，因为它们的纵横坐标区域跨度都不相同，所 以不是邻接节点。 2 2 1 2c a n 的路由机制 c a n 中的路由是在坐标空间中寻找一条从源坐标到目标坐标的直接路径。 每个以n 节点保存一张包括其邻接节点的i p 地址和虚拟坐标区域的坐标路由 表。这些简单的本地邻居状态足够在这个坐标空间中任意两点问路由。每个以n 消息都包括目标坐标。使用其邻居坐标集，每个节点只需将消息路由到坐标区域 更接近于目标坐标的邻居节点。当需要查询资源1 时，任何节点都可以使用同样 9 天津师范大学硕士学位论文 的哈希函数对资源1 的关键字l 【l 进行映射，找到点p ，然后从该点对应的节点 取出相应的值。如果此节点不是发起查询请求的节点，c a n 将负责将此查询请 求转发到对应的节点。图2 2 所示为一个简单的例子。 h( x y ) f - j b 一 e a c 图2 2 c a n 路由举例 如果一个d 维空间划分成n 个相等的区域，那么平均路由长度是( 舭) ( n 1 d ) ， 每个节点只需要维护2 d 的邻接节点信息。这个节果表明在d 维空间中，节点数 增加时每个节点维护的信息不变，且路由长度以o ( n 4 ) 增长并且在坐标空间中， 两点之间可以有许多条不同的路径。当节点的一个或几个邻居节点失效时，节点 会自动沿着其他的路径进行路由。当节点丢失了所有的邻居节点且恢复机制还没 建立时，节点可使用一个扩展查询：使用在c a n 网络中有限制的洪泛来查找离目 标坐标更近的节点。 2 2 2t a p e s t r y t a p e s t r y t l l 】的路由机制完全是基于软状态的。t a p e s t r y 具有自我管理、容错 和灵活平衡负载等特点。 2 2 2 1t a p e s t r y 的覆盖网络结构 p l a x t o n 等人提出了一种分布式数据结构用于在网络范围内定位命名对象并 可以将消息路由到这些对象。p l a x t o n 中使用的数据结构，称之为p l a x t o nm e s h 。 在p l a x t o n 中，每个节点都可以承担服务器( 保存对象) 、路由器( 转发消息) 和客户 1 0 天津师范人学硕士学位论文 端( 请求发起者) 的功能。另外，资源和节点的标识符和他们的位置以及具体内容 无关，用某种固定长度的位串采用随机方式确定( 哈希函数) 。 t a p e s t r y 是对p l a x t o n 的改进，继承了基本的定位和路由机制，修正了其中 存在的问题：构造p l a x t o nm e s h 时需要知道全局信息，导致节点的加入和离开操 作很复杂：如果每个资源的根结点失效，则该节点拥有的资源将可能无法被访问 到：缺乏适应动态查询的能力。 t a p e s t r y 中的每个节点都保存了邻居映射表。每张邻居映射表都按照路由层 次组织，每个层次都保存匹配该层次对应的后缀并离该结点最近的一组节点，节 点数等于标识符表示法的基数。邻居映射表可以用于把消息按照目的地址一位一 位地向前传递，匹配从右到左进行，例如，i c 木木8 一半木9 8 一宰5 9 8 4 5 9 8 。即层次j 的 第i 项是以“i + s u f f i x ( n ，j 1 ) 结尾的离当前节点最近的节点的标识符。当一条 消息到达传递过程中的第n 个节点时，该节点和目的节点的共同后缀长度至少大 于n 。为了进行转发，该节点将查找邻居映射表的第n + 1 级，并选择其中和目的 节点标识符的下一位对应的项。转发过程将在每个节点中依次进行直到到达目的 节点。图2 3 所示为一个t a p e s t r y 节点的数据结构：邻居映射表、热区( h o t s p o t ) 监视器、对象定位指针和对象存储。修正了需要全局信息的问题。 n 鞋鼬m i , 纽m 酗哆 2 e c 嘲曩秽n e t 垂l 铀黯 0 6 4 2 ： x 0 4 2 ：x x 0 2 ： x x x g ： 1 6 4 2 ：x 1 4 2 ：x x l 2 ：x x x l ： 2 6 4 ：=垃| 二：x x 2 2 ：x x x 2 ： 3 6 4 ：, t 3 4 2 ：x x 3 2 ：x x x 3 ： 4 6 4 2 ：x 4 4 2 ：x x 4 2 =x ：髓- x 4 ： 5 6 4 ：x 5 4 2 ：x x _ 5 2 =x x x 3 ： 6 融：x 6 4 2 ：x x 6 2 ：x x x - 6 ： 7 6 | ：x 7 4 3 ：x x 7 2 二蕊，： ：oqo 移 图2 3t a p e s t r y 节点的数据结构 结点p 在加入t a p e s t r y 网络之前，需知到一个己经在网络中的结点q 。然 后p 请求q 发出路由自己标识符的请求，根据所经过节点的邻居映射表构造自 天津师范大学硕十学位论文 己的邻居映射表。构造过程中还需要进行一些优化工作。构造完自己的数据结构 后，节点p 将通知网络中的其他节点自己己经加入网络。 t a p e s t r y 采用两种机制处理节点的退出。 1 、节点从网络中自行消失( 节点失效) 。在这种情况下，它的邻居可以检测 到它已经退出网络并可以进行相应的调整来保证路由表的正确性。 2 、节点在退出系统之前通过后向指针通知所有把它作为邻居的节点，这些 节点对路由表进行相应调整，并通知对象服务器该节点已经退出网络。 2 2 2 1t a p e s t r y 的路由机制 图2 4 所示为p l a x t o n 中的路由过程举例。t a p e s t r y 的路由机制与p l a x t o n 中的路由机制类似。节点p 通过发送消息来通知其它节点它保存有对象0 ，在这 条路径上的每个节点都保存了一条关于对象o 的位置信息 这里的位置信息只是一个指向p 的指针，并不是真正保存有对象0 的 副本。当有多个副本位置信息时，t a p e s t r y 保存了所有副本的位置信息，允许应 用来决定如何在这多份数据副本中进行选择，以增加灵活性。修正了根节点实效 的问题。 当请求定位一个对象时，节点通过使用邻居映射表对比所请求对象的标识 符，选择邻居节点发出消息，消息转发过程中如果碰到包括所请求对象位置信息 的节点，从中取出请求对象的保存节点信息，与之建立连接，获取对象。如果网 络中n 个节点两两之间的延迟( 或者按照某种度量测量的距离) 是己知的，那么可 以选择延迟最小的路径 图2 4p l a x t o n 路由举例 1 2 天津师范大学硕士学位论文 检测正常操作过程中的链路和服务器失效，除可以使用t c p 连接超时机制 外，每个t a p e s t r y 节点都使用后向指针周期性的发送心跳u d p 包给那些把自己 加入其邻居映射表的节点。每个节点都可根据自己收到的心跳包来决定自己的邻 居映射表中是否有节点失效。在邻居映射表中除了主邻居节点( 最近的) 外，每个 邻居表项还保存了两个备用的邻居节点。当检测到主邻居节点失效后，邻居映射 表将顺序选择备用邻居结点， 以适应动态查询。 2 2 3c h o r d c h o r d 一个可扩展的p 2 p 因特网应用的搜索服务。c h o r d 协议仅支持一个活 动：给出一个键值，它将这个键值分给一个节点。 2 3 3 1c h o r d 的覆盖网络结构 c h o r d 使用一致性哈希函数( s h a 1 ) 为资源和节点分配m 位的标识符。节点 的标识符可以通过哈希节点的p 地址产生得到，而资源的标识符可以直接哈希 此资源关键字得到。标识符长度m 必须足够长，保证两个节点或者资源关键字 哈希到同一个标识符上的概率小到可以忽略不计。这些资源和节点的标识符排列 成一个圆环( 0 _ _ 2 m - 1 ) ，如图2 5 所示。这个环是一个虚拟的一次空间，c h o r d 中 的路由就在这个虚拟标识空间中进行。 图2 5 包含三个节点的c h o r d 环 = 3 天津师范人学硕士学位论文 在这个虚拟标识环中节点直接对应标识符在环中依次排列，而资源则保存在 它的后继节点s u c c e s s o r 中。所谓后继节点，就是节点的标识符大于等于该资源 标识符的第一个节点。如果哈希该资源的关键字得到的标识符用k 表示，则后继 节点记为：s u c c e s s o r ( k ) 。也就是，s u c c e s s o r ( k ) 为从k 开始沿环顺时针方向的第一 个节点。如图2 5 ，资源l ，2 ，6 所存放的位址依次为：节点1 ，节点3 ，节点0 。 这个s u c c e s s o r ( k ) 值同另外一些项构成节点的路由表，图2 6 ( a ) 。在c h o r d 中， 节点并不需要知道所有其他节点的信息。每个c h o r d 节点只需要知道关于其他节 点的少量的“路由 信息。 c h o r d 中每个节点维护一个前驱指针。一个节点的前驱指针包括该节点的最 直接前驱的c h o r d 标识和i p 地址，且可以被用来沿着标识环逆时针转动。用于 简化加入和离开机制。 在由n 个节点组成的网络中，每个节点只需要维护其他o ( 1 0 9 ：n ) 个节点的 信息，同样，每次查找只需要o ( 1 0 9 ：n ) 条消息。当节点加入或者离开网络时， c h o r d 需要更新路由信息，每次加入或者离开需要传递o ( 1 0 9 ：n ) 条消息。 图2 6 c h o r d 的路由表 当一个节点n 加入该网络时c h o r d 必须完成三个任务： ( 1 ) 初始化节点n 的前驱和路由表 我们假设新节点通过某种机制知道了一个己存在c h o r d 节点n 的标识。随后 节点n 利用n 的路由表和其前驱的拷贝，初始化它的状态并将它自己加入到现存 的c h o r d 网络中。 1 4 天津师范大学硕士学位论文 ( 2 ) 更新现存节点的路由表和前驱以便反映n 的追加 节点n 将需要被加入到一些己存在节点的路由表中。节点n 将成为节点p 的第1 个f i n g e r ，当且仅当：( 1 ) 、节点p 先于n 至少2 1 1 ；( 2 ) 、节点p 的第i 个 f i n g e r 后继于n 。 ( 3 ) 通知更高层软件以便它能够传送与节点n 当前负责的资源相联系的状态 ( 例如值) 。 天津师范大学硕十学位论文 ( 袅) 图2 7 ( a ) 节点6 加入后的路由表( b ) 节点1 离开后的路由表 当节点n 失效时，在指针表中包括n 的节点都必须把n 替换成n 的后继节点。 在失效处理中最关键的步骤是维护正确的后继指针。为了保证这一点，每个 c h o r d 节点都维护一张包括r 个最近后继的后继列表。如果节点n 注意到它的后 继节点失效了，它就用后继列表中第一个正常节点替换失效节点。引入稳定机制 周期性的维护路由表。 2 2 3 1c h o r d 的路由机制 c h o r d 的路由可以被认为是一个一次g i r d 定位系统的模拟。g i r d 依赖真实 世界的地理位置信息来定位查询；c h o r d 则将节点映射到一个虚拟的一次空间，在 1 6 天津师范大学硕士学位论文 其中路由通过一个类似于g r i d 中的算法实现。如果m 是标识符的位数( 采用二进 制表示) ，那么每个节点只需要维护一张最多m 个表项的路由表( f i n g e rt a b l e ) ，参 看上图2 6 ( a ) 。节点1 1 的路由表的第1 个表项包括的是s = s u c c e s s ( n + 2 - 1 ) ， ( 1 = l - - m 并且所有的计算都要进行m o d 2 n ) 。s 称为节点n 的第i 个指针，我们 用n f i n g e r 1 n o d e 表示。一个f i n g e r 表项包括c h o r d 标识和相应节点的i p 地址( 和 端口号) 。注意到n 的第一个f i n g e r 是其在环上最接近的后继。在图2 6 ( b ) 所示的 例子中，节点l 的f i n g e rt a b l e 分别指出了标识( 1 + 2 0 ) m o d2 3 ，( 1 + 2 1 ) m o d2 3 = 3 ， 和( 1 + 2 2 ) m o d2 3 = 5 的后继节点。标识2 的后继节点是节点3 ，因为这是2 后的第 一个节点，标识3 的后继节点是节点3 ，且5 的后继节点是节点0 。 查询时，节点通过资源k 的后继节点得到资源的存储位置获得资源，当节点 n 不知道资源k 的后继节点时，如果n 能够找到一个节点，这个节点的标识符更 接近k ，那么这个节点将会知道该资源的更多信息。所以，n 将查找它的路由表， 找到节点标识符大于k 的第一个节点j ，并询问节点j ，看j 是否知道哪个节点 更靠近k 。通过重复这个过程，n 最终将会知道k 的后继节点。 当节点n 执行f i n dp r e d e c e s s o r 时，它在c h o r d 环上向着资源标识符i d 的方 向顺时针接触到一系列节点。如果节点n 联系到一个节点n ，则资源标识符i d 落在n 和n 的后继节点之间，f i n dp r e d e c e s s o r 返回1 1 。否则，节点n 向节点 n 询问其知道的最接近并先于资源标识符i d 的节点因此，这个算法是向着资源 标识符i d 的前驱进行的。 1 7 天津师范大学硕士学位论文 图2 8c h o r d 中的查询算法 我们通过一个例子来熟悉这个过程。例：节点3 需要查找关键字1 的后继节 点。由于1 属于循环区 7 ，3 】，它属于3 f i n g e r 3 i n t e r v a l ，为此节点3 查找其指针 表的第3 项，返回0 。由于o 先于1 ，因此节点3 将要求o 去寻找关键字1 的后 继节点。依此类推，节点o 将查找它的指针表并发现l 的后继节点是节点1 本身， 于是节点0 返回节点1 给节点3 。 2