（计算机软件与理论专业论文）基于chord的p2p网络负载平衡研究.pdf

基十c h o r d 的p 2 p 嘲络负载f 衡研究 摘要 负载平衡是影响系统有效运行的重要因素之一，对于p 2 p 网络系统尤为如 此。但由于p 2 p 网络中各节点相互平等且没有中心存在，传统基于中心服务器 调度的负载平衡算法不适用，需根据p 2 p 特性研究负载平衡算法。 本文针对结构化p 2 p 网络c h o r d 中由于绕路、热点等引起的负载平衡问题， 利用i p v 6 分层地址结构和无状态自动配置地址配置方式，选取i p v 6 为网络层 协议，拆分i p 地址，提取可表征节点物理位置的部分；并将节点按物理位置分 域组构成c h o r d 环；而后在分组结构上设置多副本资源发布方式。给出了基于 c h o r d 的静态负载平衡策略。此策略尽可能地将查询本地化，以缩短查询路径， 使查询路径中的中间节点减少，释放部分节点承担的查询转发负载；并分摊热 点资源负载。经分析验证，以上设计确实缓解了c h o r d 运行中出现热点、拥塞 的问题，提高了系统的负载平衡性。 然而，结构化p 2 p 网络中，节点和资源在同一个标识空间随机分配本身就 有0 ( 1 0 9 n ) 的不平衡性，系统在运行过程中不可避免地会出现负载失衡，因而 引入动态负载平衡机制很有必要。但动态平衡额外开销较大，故本文对虚拟服 务器动态负载平衡算法进行改进：提取节点i p v 6 地址中的物理位置信息为节点 问相关性信息，进行轻、重载节点问的匹配。所做改进降低了相关性信息的计 算开销。 关键词：结构化p 2 p ；c h o r d ；域组；i p v 6 ；负载平衡 基fc h o r d 的p 2 p 啊络负载f 衡研究 a b s t r a c t l o a db a l a n c i n gi so n eo ft h ei m p o r t a n tf a c t o r st h a ta f f e c tt h e e f f i c i e n c yo fs y s t e m ，p a r t i c u l a r l yf o rp 2 pn e t w o r ks y s t e m b u tb e c a u s e o fe q u a l i t ya n dn oc e n t e r ，t h o s et r a d i t i o n a ll o a db a l a n c i n ga l g o r i t h m s ， b a s e dt h ec e n t e r ，a r en o ta p p li c a b l e t h es t u d i e so f1 0 a db a l a n c i n g s h o u l dc o n s i d e rt h e c h a r a c t e r is ti co fp 2 p a i ma tl o a db a l a n c i n gp r o b l e mo w i n gt od e t o u ra n dh o t p o i n t ，i nt h i s p a p e r ，w ep r e s e n ta n yi m p r o v e dd e s i g ni nc h o r d ：e x p l o i tt h ei p v 6a d d r e s s h i e r a r c h i c a lf e a t u r e ，i p v 6i sc h o s e nt ob et h ep r o t o c o lo fn e t w o r kl a y e r ， p i c ku pt h ep h y s i c a lp o s i t i o ni n f o r m a t i o n ：g r o u pt h en o d e sa c c o r d i n gt o t h ep h y s i c a lp o s i t i o ni n f o r m a t i o n ：t h ei s s u a n c eo fr e s o u r c e sw i t hm o r e c o p i e s t h e s es t r a t e g i e sl o c a l i z e dq u e r y ，s h o r t e nq u e r yp a t h ，r e l e a s e l o a do ft h en o d ei nm i d w a y b ya n a l y z ea n dv a l i d a t e ，i ti m p r o v et h e1 0 a d b a l a n c i n go fs y s t e m h o w e v e r ，i ns t r u c t u r e dp 2 p ，t h e r ea r eo ( 1 0 9 n ) i m b a l a n c ef a c t o r ，s o d y n a m i cl o a db a l a n c i n gs t r a t e g yi sn e c e s s a r y b u ti tb r i n g si nb i g g i s h i n c i d e n t a le x p e n s e s t h e r e f o r ew ei m p r o v et h ev i r t u a ls e r v e ra l g o r i t h m ： p i c ku pt h ep h y s i c a lp o s i t i o n i n f o r m a t i o nf r o mi p v 6a d d r e s st ob e p r o x i m i t yi n f o r 眦t i o n ，a n du s ei tt og u i d el o a dr e a s s i g n m e n t sb e t w e e n l i g h t l yl o a d e dn o d e sa n dh e a v i l yl o a d e dn o d e s o u rc h a n g ed i m i n i s h e st h e i n c i d e n t a lc o m p u t a t i o ne x p e n s e s k e yw o r d s ：s t r u c t u r e dp 2 p ；c h o r d ：d o m a i mi p v 6 ：l o a db a l a n c i n g h 堆fc h o r d 的p 2 p 网络鲍载i - 衡研究 1 1 研究的意义 第一章绪论 p 2 p 技术在近年来得到了广泛的发展，已成为i n t e r n e t 中重要的应用技术 之一，显示出了强大的发展潜力，吸引了越来越多的研究机构和团体加入到这个 研究领域。 p 2 p 不仅是一项技术，更是一种思想。i b m 称p 2 p 是一个社会和经济现象。 它改变了网络中信息、服务的交换和共享方式，允许网络边缘的终端设备平等直 接地交换彼此共享的资源。不同于c s 、b s 等模式，它弱化甚至取消了服务器 的作用，使网络中的节点以一种点对点对等的方式实现存储空间、计算能力、网 络带宽等资源的共享。从而使我们通过网络的交流不再需要服务器作为媒介进行 中转，变得更为直接，效率更高，更符合我们在现实社会中的交流方式。同时， 避免了系统因服务器处理能力不足引发服务器性能瓶颈和单点失效的问题，增强 了系统的可扩展性和可靠性。 p 2 p 设计之初用于音乐文件的共享“1 ，而后由于它在交互方式、效率、可扩 展性、自组织性等方面的优势，其应用逐渐扩展到文件共享、对等计算、协同工 作、实时通信、信息检索、广域网存储、智能代理、网络游戏等等许多领域。 p 2 p 网络出现的目的就是希望能够更直接、更充分、更高效地利用互联网中 所蕴含的潜在资源。但在实际研究中各种各样的问题使得在p 2 p 网络中的潜在资 源并没像希望地那样被充分、高效地利用。网络中某时期，部分节点承担的交互 量过重，则向其请求服务的节点将无法在可接受的时间内得到服务，导致内容资 源没有被高效利用，严重时导致系统无法提供服务；另外某些节点由于访问量较 小其处理能力被闲置，导致处理能力资源没有被充分利用。负载平衡是实现资源 有效共享，提高系统资源有效使用率的必然要求，是影响网络系统服务质量的重 要因素之一。改善网络系统的负载平衡性对于提升网络性能，保证稳定的服务质 量具有积极的意义。 筚rc h o r d 的p 2 p 阿络负载r 衡研究 1 2 研究现状 为了改善系统的性能、提高系统健壮性、保证服务质量，通过在多台计算机 之间合理地分配负载，使各台计算机的负载基本均衡，这种计算能力共享的形式， 通常被称为负载平衡或负载共享。 负载平衡的研究主要分为静态负载平衡和动态负载平衡。静态策略预先分配 网络负载，额外开销小；动态策略则根据网络中负载的不断变化动态的分配负载， 效率高但额外开销也大。 传统的负载平衡算法由于系统中存在中央服务器一般为基于各种调度策略 的方法，实现效率高。但p 2 p 网络中各节点相互平等，没有中心存在，传统负载 平衡算法不能直接使用。需根据p 2 p 本身的特点设计负载平衡策略。 各种p 2 p 结构的负载平衡性不尽相同，导致负载平衡问题的原因也不同。例 如，在结构化p 2 p 网络中查询消息量少，但存在绕路及热点引起的负载平衡问题， 但在g n u t e l a “1 网络中不存在绕路问题而主要是消息冗余量大及热点问题。所以 改善p 2 p 系统负载平衡性的方法针对各种不同p 2 p 结构的特点需采取不同的方 法。 1 3 本文研究内容 本文对p 2 p 网络进行分析研究，特别是几种常见典型的结构化p 2 p 网络的覆 盖网络结构及路由机制。通过分析研究发现网络间节点的连接方式对网络的负载 平衡性具有不可忽视的影响。连接方式不同，系统将具有不同的负载平衡性。因 此在构建体系结构时就需要充分考虑负载平衡因素。一个合适的连接方式本身就 能在很大程度上减少出现负载失衡的可能。 针对c h o r d 中路由路径的逻辑距离与物理距离不相符及资源流行度高产生 的热点，导致资源不能有效利用，负载失衡的问题。本文首先，利用i p v 6 支持 分层地址及无状态自动地址配置方式选取i p v 6 为网络层协议，拆分i p 地址，提 取可表征节点物理位置信息的部分。其次，以物理位置信息为标识，将属于同一 物理位置区域的节点分在一个逻辑域组内构成c h o r d 环，再以域组为单位构成外 c h o r d 环。然后，设置多副本资源发布机制，在本地域组内及其它域组内存放资 肇fc h o r d 的1 2 1 州络负载f 衡研究 源副本。尽可能地将查询本地化，缩短查询路径，使查询路径中的中间节点减少， 释放部分节点承担的查询转发负载，且多副本在出现热点前预先分散负载。经分 析验证，确实缓解了c h o r d 运行中出现热点、拥塞的问题，提高了系统的负载平 衡性。 此外，上述方法虽然降低了系统运行时出现负载失衡的可能，但由于结构化 p 2 p 系统本身的负载不均衡性及热点问题的不可完全避免，系统中仍会出现负载 失衡，所以动态负载平衡不可缺少。但动态负载平衡策略一般引入较大的额外开 销。为了降低负载在轻、重载节点之自j 转移的丌销，本文对虚拟服务器负载平衡 算法进行改进：提取节点i p v 6 地址中的物理位黄信息作为负载转移时轻、重载 节点的相关性信息，选择物理位置邻近的轻、重载节点相匹配进行负载转移，以 减少负载匹配和转移时的开销，增强负载平衡的快速和有效性。 1 4 论文组织 本文共分为五章，按如下方式组织。 第一章对论文的研究意义、现状及研究内容作简要介绍，同时给出本文的 组织结构。 第二章介绍了p 2 p 的概念、特点、应用领域和发展，重点描述了四种结构 化p 2 p 网络的覆盖网络结构和路由机制，并介绍了负载平衡技术及其重要性。 第三章对结构化p 2 p 网络中的负载平衡问题进行分析。选取i p v 6 位网络层 协议，从i p v 6 地址中提取了物理位置信息，据此对c h o r d 作了提高系统负载平 衡性的改进，包括：组织结构、资源发布方式、查询机制等。 第四章对虚拟服务器负载平衡算法的负载转移过程进行改进，减少负载匹 配和转移时的计算丌销。 第五章给出本文总结，进一步的工作及对p 2 p 技术的展望。 肇rc h o r d 的p 2 p 叫络负载1 7 律f 究 第二章p 2 p 网络概述 随着计算机处理能力的不断增强及对资源充分利用的要求，网络逐渐从客户 端服务器( c s ) 模式向对等( p 2 p ) 模式演变。所i w p 2 p 为“p e e r - t o - p e e r ”的 缩写，可直译为“伙伴对伙伴”( 即相互对等，直接联系) 。故我们可将p 2 p 网络 直观理解为网络中各端点相互平等，通过直接交换来共享相互的资源和服务。 2 1p 2 p 网络的概念 对于p 2 p 到目前为止还没有统一的定义，有公司将其定义为：使个人与个人 之间直接通信成为可能且更便捷的网络结构；i n t e l 将p 2 p 定义为：通过系统间 的直接交换所达成的计算机资源与信息( 包括信息交换、处理器时钟、缓存和磁 盘空间等) 的共享；i b m 将p 2 p 定义为：p 2 p 系统由若干互联协作的计算器构成， 系统依存于边缘化设备的主动协作，每个成员直接从其它成员而不是服务器的参 与中受益，系统中的成员同时扮演服务器与客户机角色，能相互意识到彼此的存 在，构成一个群体。 然而p 2 p 并不是一个全新的技术，早期的网络( 如局域网中的文件共享， f i d o n e t 等) 本就是对等网络。且当下i n t e r n e t 也是以此为基础的，其中最本 的t c p i p 协议里所有的设备在通信过程中都是平等的一端。但早期机器的性能 制约了网络规模的扩大，为了满足规模的扩大人们设计出了客户端服务器( c s ) 模式。但随着机器性能的不断提升及对交流更直接的需求，对网络能更贴近我们 的真实生活的希望，促进了p 2 p 的新发展。p 2 p 网络出现的目的就是希望能够更 直接、更充分地利用互联网中所蕴含的潜在资源。 2 2p 2 p 网络的特点、发展 p 2 p 技术充分利用分布在终端电脑上的边缘性资源( 包括计算、带宽、内容 等资源) ，弱化甚至取消服务器的作用。 p 2 p 网络最重要的特点就是“无中心性”和“边缘化”：网络中没有所谓的 中心存在，每个节点的地位都是对等的( 此处为逻辑上的对等，而不是节点处理 幕fc h o r d 的p 2 pi 川络负载卜衡研究 能力的对等) ，兼有客户端和服务器的功能；网络中的资源不再存于主要的服务 器上，而是存于处在网络边缘所有用户的终端机上，资源分布分散。 大量文献表明p 2 p 网络还具有以下特点： 1 交互共享资源和服务的直接性( 请求者节点和拥有者节点建立直接连接， 交互共享的资源和服务，脱离服务器) 2 可扩展性强( 加入节点的数量理论上无限制) 3 高度动态性( 节点频繁加入退出) 4 高度异构性( 允许节点在带宽、延迟、有效性等方面存在3 5 个数量级 的差异，p 2 p 中的对等是指节点在逻辑上地位的对等，而并非处理能力 的对等) 5 自组织性( 节点自主的加入、退出，网络可自主的根据变化进行调整， 维护其正确可用) 6 节点的可信度较低( 节点的自主性导致节点的随意性，很难对节点统一 的认证保证节点的可信) 另外，p 2 p 与传统c s 相比还具有：双向性( 即可以提供服务，也可以被服 务) 、及时性、廉价性( 不需要配置处理能力很强，但昂贵的服务器组件) 和健 壮性( 不存在影响面较大的服务器单点失效的危险) 等优势。 基于以上特点和优势，p 2 p 目前主要应用于 4 ： 1 文件共享( 直接交换信息这种方式更符合人们信息交流的方式。如 n a p s t e r 嘲、g n u t e l l a 嘲、k a z a a 、f r e e n e t 嘲等) 2 对等计算( 对等计算的目的就是利用闲散计算资源完成大规模计算，实 际即为实现网络上c p u 资源共享。而p 2 p 的目标也正是充分利用网络中 的边缘资源。如s e t i h o m e ”1 ) 3 协同工作( 构建共享虚拟空间，共享工作中所需的各种资源( 中自j 数据) ， 直接共享的方式保证系统中每个参与者获得的信息总是最新的，使不同 地点的参与者可协同完成某项工作。如g r o o v e “”、k d t ) 4 信息检索( 目前的检索实际是在海量数据库内部进行搜索，虽然很快， 但不能保证搜索的深度和节果的时效性，如g o o g l e 也只能搜索到2 0 摹于c h o r d 的p 2 p 嘲络负载r 衡研究 一3 0 9 6 的网络资源。p 2 p 节点间动态、对等的互联关系可以有效地跟踪 数据的更新速度，保证搜索的实时性及更深的搜索深度。如g n u t e l l a ， 搜索范围在几秒钟内以几何级数增长，应用软件有i n f r as e a r c h ) 5 广域网存储系统( 为了充分利用网络中闲散的存储空间，使用p 2 p 技术 来组织和存储文件，如o c e a n s t o r e “、f a r s i t e 、p a s t “”等，其目标都 是提供面向全球规模的存储服务) 6 实时通信( 为了更直接地快捷地进行交流，我们交流环境本身就是p 2 p 模式的。如i c o 、o i c o 、s k y p e 。j a b b e r “”是一个开放源码的实时通信 平台，提出了一个采用x m l 表示的在不兼容的各种实时通信平台之间进 行消息交换的协议) 7 网络游戏( 点对点通信将大大提高目前多人在线交互游戏的性能) p 2 p 的发展大致经历了以下三个阶段： 集中式目录结构阶段( 以n a p s t e r ”1 为代表) ：系统中有一个中央服务器， 但不是像c s 模式中用来存放资源，而是用来存放索引的。节点加入要向其注册 并动态更新地传送自己所共享资源的索引。当网络中节点搜索资源时，将带有所 需资源标识的请求发送到中央服务器，中央服务器检索资源索引，将拥有该资源 节点的标识发送给请求者，请求者按标识直接访问资源拥有者节点，获取资源。 搜索所需信息量小，速度快，搜索全面。但中央服务器的处理能力限制了网络规 模成为系统瓶颈，且易发生单点( 中央服务器) 失效。 纯分布式结构阶段( 以g n u t e l l a “1 为代表) ：网络中没有中央服务器，节点 随机加入或退出网络，与自己相邻的邻居节点通过点对点连接构成逻辑网络。采 用洪泛请求的模式进行资源搜索。每个节点维护一张邻居节点路由表，在限定的 t t l 值内向所有邻居节点发送资源搜索请求，拥有该资源的节点在收到请求后发 出回应，建立连接，获取资源。获得了较好的可扩展性和容错性( 不会发生单点 失效) 。但洪泛机制导致控制信息量过大，占用大量带宽；节点无需任何注册， 可信度不高，易受到恶意攻击，安全性不高。这一阶段中出现了基于分布式哈希 表构建覆盖网络的结构化对等网络。本文的研究基于此，在下一小节中做重点介 绍。 混合式结构阶段( 以k a z a a ”1 为代表) ：在纯分布式结构的基础上根据节点 幕十c h o r d 的p 2 p 嘲络负载f 衡研究 能力引入了超级节点的概念。超级节点和其邻近的普通节点构成一个自治簇，簇 内采用集中式目录结构，普通节点向本簇的超级节点发送资源索引和搜索请求。 各簇之问可以超级节点为标识按照某种结构组织( 例如按纯分布式组织) 。这种 结构有效地减少了洪泛机制产生的大量控制信息，并由于超级节点对节点行为的 控制提高了安全性。但超级节点的存在引入了单点失效的发生( 虽好于集中式目 录结构) 。 2 3 结构化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 2 p 网络是一种资源位置和网络拓扑结构松散相关的对等网络。这 类网络的主要思想是在网络中进行洪泛( 或受限洪泛) ，资源位置不需要按照网 络结构进行精确的定位，每个节点维护局部相邻节点路由表即可，最典型的就是 g n u t e l l a ”1 。其自组织性和扩展性较好，但网络中重复消息量过大，占用带宽， 网络负载过大，且安全性较低。 结构化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 ) 之间建立一 个确定的一对一映射关系。分布式哈希表，顾名思义就是把哈希表分散至u 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 ) “” 来实现映射，将资源和节点均匀地映射到一个标识空间( i d e n t i f i e rs p a c e ) 中， 每个节点维护有限的邻居信息和路由信息完成资源的定位。分布式哈希表在节点 失效、遭受攻击和突发性高负载面前都能表现出很好的健壮性；具有良好的可扩 展性，能以较低系统开销获得较大的系统规模；可以自我配置，不需要手工干预 就可以自动把新节点加入到系统中；能提供简单灵活的接口，可以为多个p 2 p 应 堆十c h o r d 的p 2 ph 络负载1 7 衡研究 用同时使用。 结构化p 2 p 网络通过每个节点维护较少的路由信息即可有效地实现查找，取 消了洪泛机制，大大减少了网络中的信息量。但由于覆盖网络结构维护、节点异 构性及逻辑网络与物理网络匹配等问题使得系统更为复杂，故还有很多方面需进 一步研究，使其更有利于实际应用。当前以加州大学伯克利分校的c a n 和 t a p e s t r y 、麻省理工学院的c h o r d 、及微软研究院的p a s t r y 为代表性研究项目。 2 3 1d 蝌 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 3 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 将执行合并操作。如果不能，则该区域 将交给其邻居节点中所负责区域最小的节点，它将临时负责两个区域。详细过程 可参见文献 1 6 。 摹fc h o r d 的p 2 p | 卅络负载卜衡研究 图2 1 二维c a n 坐标空间的划分 图2 1 所示，为d = 2 时二维笛卡儿坐标空间中的一个划分，其中7 个节点分 别负责一块儿互不相交的坐标区域：a ( 0 - 0 4 ，0 7 - 1 ) ，b ( 0 ，4 - l ，0 7 - 1 ) ，c ( 0 - 0 3 ，0 - 0 7 ) ，d ( 0 3 - 0 7 ，0 3 - 0 7 ) ，e ( 0 7 - l ，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 ) 存放在这个虚 拟的坐标空间中。例如，存放( k l ，v 1 ) ：使用一个统一哈希函数把关键字k 1 映 射为坐标空间中的一个点p ，则该键值对( k l ，v 1 ) 就被存放在所负责区域包含 点p 的节点中。c a n 中的节点自主地加入虚拟坐标空间描述的覆盖网络，每个节 点获取并保存一部分节点的i p 地址，这部分节点为所负责的坐标区域与该节点 所负责的坐标区域相邻接的节点。节点区域相邻接是指，在d 维坐标空问中，当 两个区域在d - 1 维上都覆盖相同的跨度在另一维上相互邻接，那么这两个区域相 邻接。例如图2 1 中d 和e 的区域相邻接，因为它们在纵坐标上的区域跨度相同 都是( o 3 - 0 7 ) ，而在横坐标上相邻，故是邻接节点；而a 和c 的区域不相邻 接，因为它们的纵横坐标区域跨度都不相同，所以不是邻接节点。 2 3 1 2c a n 的路由机制 c a n 中的路由是在坐标空间中寻找一条从源坐标到目标坐标的直接路径。每 个c a n 节点保存一张包括其邻接节点的i p 地址和虚拟坐标区域的坐标路由表。 这些简单的本地邻居状态足够在这个坐标空间中任意两点问路由。每个c a n 消息 都包括目标坐标。使用其邻居坐标集，每个节点只需将消息路由到坐标区域更接 近于目标坐标的邻居节点。当需要查询资源1 时，任何节点都可以使用同样的哈 希函数对资源1 的关键字k 1 进行映射，找到点p ，然后从该点对应的节点取出 摹fc h o r d 的p 2 pl q 络负载r 衡研究 相应的值。如果此节点不是发起查询请求的节点，c a n 将负责将此查询请求转发 到对应的节点。图2 2 所示为一个简单的例子。 下_ 一 乜y 暑 e 木一 、 | c 图2 2c a n 路由举例 如果一个d 维空间划分成n 个相等的区域，那么平均路由长度是( d 4 ) ( n “d ) ， 每个节点只需要维护2 d 的邻接节点信息。这个节果表明在d 维空间中，节点数增 加时每个节点维护的信息不变，且路由长度以0 ( n “。) 增长。并且在坐标空间中， 两点之间可以有许多条不同的路径。当节点的一个或几个邻居节点失效时，节点 会自动沿着其他的路径进行路由。当节点丢失了所有的邻居节点且恢复机制还没 建立时，节点可使用一个扩展查询：使用在c a n 网络中有限制的洪泛来查找离目 标坐标更近的节点。 2 3 2t a p e s t r y t a p e s t r y “”的路由机制完全是基于软状态的。t a p e s t r y 具有自我管理、容错 和灵活平衡负载等特点。 2 3 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 基于c h o r d 的p 2 p 州络负载、r 衡研究 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 中的每个节点都保存了邻居映射表。每张邻居映射表都按照路由层 次组织，每个层次都保存匹配该层次对应的后缀并离该结点最近的一组节点，节 点数等于标识符表示法的基数。邻居映射表可以用于把消息按照目的地址一位一 位地向前传递，匹配从右到左进行，例如料丰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 + l 级，并选择其中 和目的节点标识符的下一位对应的项。转发过程将在每个节点中依次迸行直到到 达目的节点。图2 3 所示为。个t a p e s t r y 节点的数据结构：邻居映射表、热区 ( h o t s p o t ) 监视器、对象定位指针和对象存储。修正了需要全局信息的问题。 确堍抽m 唪纽m 目m 可 2 * l 蝌_ 蟮她 i i 0 6 4 2x 0 4 2x x 0 2 ：x 蒯 i ：。支 1 6 毒2x 1 4 2 x x l 2 ：m l 。：， 2 6 4 2x 2 4 2 ! m 2 z ： 置置x 2 3 6 4 2x 3 4 2 3 ：x 置x 3 ：；- - ? - 一， 4 6 4 2x 4 4 2 x x 4 2 ：x x d ，k s 科2x s 4 2 m r 5 2 ： r a m 5，一气 6 6 毒2x 6 4 2 懿：x 6! ” 7 6 朝x 7 4 2【花：m a t 7 ：；：善 图2 3t a p e s t r y 节点的数据结构 结点p 在加入t a p e s t r y 网络之前，需知到一个已经在网络中的结点q 。然 后p 请求q 发出路由自己标识符的请求，根据所经过节点的邻居映射表构造自己 的邻居映射表。构造过程中还需要进行一些优化工作。构造完自己的数据结构后， 节点p 将通知网络中的其他节点自己已经加入网络。 国圜 幕十c h o r d 的p 2 p 啊络负载1 衡研究 t a p e s t r y 采用两种机制处理节点的退出。1 、节点从网络中自行消失( 节点 失效) 。在这种情况下，它的邻居可以检测到它已经退出网络并可以进行相应的 调整来保证路由表的正确性。2 、节点在退出系统之前通过后向指针通知所有把 它作为邻居的节点，这些节点对路由表进行相应调整，并通知对象服务器该节点 已经退出网络。 2 3 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 ，在这 条路径上的每个节点都保存了一条关于对象0 的位置信息 。这里的位嚣信息只是一个指向p 的指针，并不是真正保存有对象0 的副本。当有多个副本位置信息时，t a p e s t r y 保存了所有副本的位置信息，允 许应用来决定如何在这多份数据副本中进行选择，以增加灵活性。修正了根节点 实效的问题。 当请求定位一个对象时，节点通过使用邻居映射表对比所请求对象的标识 符，选择邻居节点发出消息，消息转发过程中如果碰到包括所请求对象位置信息 的节点，从中取出请求对象的保存节点信息，与之建立连接，获取对象。如果网 络中n 个节点两两之间的延迟( 或者按照某种度量测量的距离) 是已知的，那么 可以选择延迟最小的路径。 图2 4p l a x t o n 路由举例 基于c h o r d 的p 2 p 网络负载、1 7 衡研究 检测诈常操作过程中的链路和服务器失效，除可以使用t c p 连接超时机制 外，每个t a p e s t r y 节点都使用后向指针周期性的发送心跳u d p 包给那些把自己 加入其邻居映射表的节点。每个节点都可根据自己收到的心跳包来决定自己的邻 居映射表中是否有节点失效。在邻居映射表中除了主邻居节点( 最近的) 外，每 个邻居表项还保存了两个备用的邻居节点。当检测到主邻居节点失效后，邻居映 射表将顺序选择备用邻居结点，以适应动态查询。 2 3 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 位的标识符。节点 的标识符可以通过哈希节点的i p 地址产生得到，而资源的标识符可以直接哈希 此资源关键字得到。标识符长度m 必须足够长，保证两个节点或者资源关键字哈 希到同一个标识符上的概率小到可以忽略不计。这些资源和节点的标识符排列成 一个圆环( 0 2 。_ 1 ) ，如图2 5 所示。这个环是一个虚拟的一次空间，c h o r d 中的 路由就在这个虚拟标识空间中进行。 s u c c e s s o r ( 6 图2 5 一个m = 3 ，包含三个节点的c h o r d 环 在这个虚拟标识环中节点直接对应标识符在环中依次排列，而资源则保存在 它的后继节点s u c c e s s o r 中。所谓后继节点，就是节点的标识符大于等于该资源 标识符的第一个节点。如果哈希该资源的关键字得到的标识符用k 表示，则后继 毕十c h o r d 的p 2 p 州络掘载r 铂研究 节点记为：s u c c e s s o r ( k ) 。也就是，s u c c e s s o r ( k ) 为从k 开始沿环顺时针方向的 第一个节点。如图2 5 ，资源1 ，2 ，6 所存放的位址依次为：节点l ，节点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 个节点组成的网络中，每个节点只需要维护其他0 ( 1 0 9 n ) 个节点的 信息，同样，每次查找只需要0 ( 1 0 9 n ) 条消息。当节点加入或者离开网络时， c h o r d 需要更新路由信息，每次加入或者离开需要传递0 ( 1 0 9 2 y ) 条消息。 ( a )( b ) 图2 6c 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 网络中。 2 、更新现存节点的路由表和前驱以便反映n 的追加。 节点n 将需要被加入到一些已存在节点的路由表中。节点n 将成为节点p 的 苎! 型竺丝! 塑塑丝堑= ! ：塑型窒 第i 个f i n g e r ，当且仅当：( 1 ) 、节点p 先于n 至少2 l 1 ；( 2 ) ，节点p 的第i 个f i n g e r 后继于n 。 3 、通知更高层软件以便它能够传送与节点n 当前负责的资源相联系的状态 ( 例如值) 。 算法描述“”为： # d e f i n es 毡c c e s s o ff m g e r 1 n o d e # n o d e n j o i n st h eh 8 r k “娃 sa l la r b i t r a r yn o d 6 钒t h em a w o r 量 n j o l n ( n i ) j f ( ) i a i t f i n g e r t a b l e ( n ) ； l 驴妇招_ d 捕o ； # m o v e 姆i 捕( p r e d e c e s s o r ，碉夕研删l $ t o l e e l s e n 虹t h ew 妒n o d # i nt wm a w o r k 如r i = 1 协m 融g 圆。h 鲥t ；n ； p r d e c # s s o r = ，l ： # i n i t i a l i z e f i n g o rt a b l eo f l a v a ln o d m ； 一虹佣a r b j w a r y 舶如d 瑚方i 摊跏m a w o r k n 。i n l t f l n g e r _ t a b l e ( n i ) 乒鸭川l 】础= 订7 $ 妇c a s s o r ( m g e r 1 1 s t a r * ) ； p 瑚函配茁工d r = s 氍睇懿o r p 嘲函比整r ： 捌c c 稻r 尹措瘟晒暖繇口，= 抖； 如r i = l | 。m 一1 i f 渤g 哦i - kl 】豫时。励蒯1 o d e ) ) 触静十l 】n o d e = 励酬i 】，l 砌口； e l s e 胁i r l , i 糍燃i 细瞄- k1 l 删； 抽d ：硪“憾5 口d 彝嘎g 帮隧1 j 衄撑) ； u 卿a n , 翘，l d 西盱w h o s # f i n g h r t a b g s h a u d 咖船n 罪u p d a t m _ o t i m r a ( 】 如r t = 1 t o m 删l a s t n o d epw h o s 口i 协f i n g e rm i g h t6 i 辟 p 。净斑孚伟凼删跖o n 一一1 ) - p 。哪知h 招和毋田i 一舳( n ，i ) ； 矿5 虹矿 f m g m - 帆岫纽n t 参r 鬯f 纽谳 霸。u p d a t e d t n g m t m b l e ( s ，订 西( 。h , 廊g e r 踊糟“哟) 算# 喀】。t t o d o = $ ； p 。f 孳d 舔s 钟；痧琶孽耋囟礤a o d e 矽豳h g n 尹。l i p 凼招乒曙配缸6 l 雪扣，t ) ； 1 5 - 坫fc h o r d 的p 2 p 嘲络负载1 衡研究 图2 7 ( a ) 为上图中网络节点6 加入后的路由表 ( b ) 为节点1 离开后的路由表 当节点n 失效时，在指针表中包括n 的节点都必须把n 替换成n 的后继节点。 在失效处理中最关键的步骤是维护正确的后继指针。为了保证这一点，每个c h o r d 节点都维护一张包括r 个最近后继的后继列表。如果节点n 注意到它的后继节点 失效了，它就用后继列表中第一个正常节点替换失效节点。引入稳定机制周期性 的维护路由表。 2 3 3 1c h o r d 的路由机制 c h o r d 的路由可以被认为是一个一次g r i d 定位系统的模拟。g r i d 依赖真实 世界的地理位蜀信息来定位查询：c h o r d 则将节点映射到一个虚拟的一次空问， 在其中路由通过一个类似于g r i d 中的算法实现。如果m 是标识符的位数( 采用 二迸制表示) ，那么每个节点只需要维护一张最多m 个表项的路由表( f i n g e r t a b l e ) ，参看上图2 6 ( a ) 。节点n 的路由表的第i 个表项包括的是 s = s t l c c e s s ( n + 2 l 1 ) ，( 1 = i 的节点。2 、如果不存在这样的节点，则将消息传递给共 同前缀长度相同，但在节点号数值上更接近消息的关键字的节点。在正常操作条 件下，路由的步数小于l 0 9 2 b n 的上取整，b 是一个配置参数，典型的b = 4 。 为了支持这样的路由过程，每个节点必须维护一定的路由状态。图3 9 列出 了节点号为1 0 2 3 3 1 0 2 的节点的数据结构，包括：叶子集、路由表、邻居集三部分。 其中b = 2 ，1 = 8 ( 叶子集中节点数，通常取1 6 或3 2 ) 。 摹fc h o r d 的p 2 pn i 络负载r 衡研究 n o d e l d10 2 3 3 10 2 r o u h n gl 翻3 1 e 4 2 2 1 2 c 2 爨溆黔懋灞- 2 - 2 3 0 1 2 0 3 - 3 - 1 2 0 3 瑚 隧强弱i 自l 1 1 + 3 0 2 翳1 - 2 - 2 1 - 3 - 0 2 1 0 2 2 1 0 - 0 - 3 1 2 0 3t 1 0 - 1 - 3 2 1 0 e 麓黧鬣澄濯! 堡3 2 3 3 8 2 1 0 2 - 0 0 2 3 0 ；1 0 2 - 1 1 3 ( 1 2 1 0 2 ，2 - 2 3 0 2 熬黧霪翻 1 0 2 3 _ d - 2 2 21 0 - - 一1 0 0 0 t 鼢2 - 1 2 1 譬溢翟糊 迸猫攀翼，i 0 2 船- ，2 瑚- 3 2 一。_ _ ： 圈2 9p a s