（计算机应用技术专业论文）基于区间查询的结构化p2p覆盖网设计与分析.pdf

基于区间查嘲的结构化p 2 p 覆盖网设计与分析 摘要 p 2 p 系统的广泛应用推动了当前p 2 p 相关技术的发展，随着应用的不断增加，数据查 询已经不再仅限于最初的单一关键字查询或关键字精确匹配。目前，结构化p 2 p 系统中对 于复杂查询的支持，例如区间查询、前缀查询和聚合查询等，已成为一项具有积极意义的 课题。p 2 p 系统所特有的易变性和规模大等特点，使这一技术变得更为复杂。 传统的结构化p 2 p 覆盖网络大都基于分布式哈希表( 以下简称d h t ) 技术构建，这一 技术可以实现高效的资源查找，并使系统实现负载平衡，但也存在破坏数据顺序的缺点， 从而使得区间查询在这类系统中难以实现。为了解决这一问题，一类非基于d h t 技术构 建的系统被相应提出，用以解决结构化覆盖网络中的区间查询问题。此外，对于已有的覆 盖网络进行修改，使其能够支持区间查询也是解决这一问题的一种方法。 d eb r u i j n 图是一种特殊的图结构，它具有常数度和最优网络直径的特点。我们通过使 用多层后缀树和d eb r u i j n 图相结合的拓扑结构，设计了d b s t 覆盖网络，该网络既有树 形结构对数据顺序保留的特点，使系统能够支持区间查询，同时也具备d eb r u i j n 图在静态 网络中节点常数度的优点，为基于d eb r u i j n 图和d h t 技术构建的结构化p 2 p 覆盖网络提 供了一种解决区间查询问题的方法。 跳图( s k i pg r a p h ) 是一种本身支持区间查询的图结构，它是树形结构的一种变形，可 以保留数据顺序，同时，一个节点在网络中还存在多个复本，这使得使用该结构的网络具 有较高的容错性。通过使用该结构我们设计了一种非基于d h t 技术的p 2 p 覆盖网络，称 为s g p o 覆盖网，它是一种基于跳图的并可实现拓扑意识路由的p 2 p 覆盖网络。通过设计 该系统，我们在解决区间查询问题的同时，还解决了物理网络与逻辑网络不一致的问题。 本文主要对支持区间查询功能的结构化p 2 p 覆盖网络进行设计与分析，全文共分为五 章。 第一章绪论说明了研究的背景和问题的提出，以及论文所做的工作和组织结构；第二 章是对现有的解决区间查询问题的方法的概述；第三章是构造基于d eb r u i j n 有向图的多层 后缀树覆盖网络( d b s t ) ；第四章是设计基于跳图的具有拓扑意识路由的区间查询系统 ( s g p o ) ；第五章是本文的总结以及对下一步工作的展望。 关键词：对等网络；结构化覆盖网络；区间查询；d eb r u i j n 图；常量度；跳 图；拓扑意识路由 基于区间盘询的结构化p 2 p 覆盖l 】c 习设计与分析 a b s t r a c t t h ee x t e n s i v eu s eo fp 2 ps y s t e m si na p p l i c a t i o n sm o t i v a t e st h ee v o l u t i o no fc u r r e n tp 2 p t e c h n o l o g i e s w i t ht h ec o n t i n u o u si n c r e a s ei na p p l i c a t i o n s ，d a t aq u e r yi sn o to n l yl i m i t e di nt h e p r i m a r ys i n g l ek e y w o r do rt h ee x a c tm a t c h e s t h es u p p o r tf o rc o m p l e xq u e r i e s ，s u c ha sr a n g e q u e r i e s ，p r e f i xq u e r i e sa n da g g r e g a t i o nq u e r i e s ，o v e rs t r u c t u r e dp e e r - t o p e e rs y s t e m si sc u r r e n t l y a na c t i v ea n ds i g n i f i c a n tt o p i co fr e s e a r c h c o m p l e xq u e r yi sm o r ec o m p l i c a t e di np 2 ps y s t e m s d u et ot h ev o l a t i l i t ya n ds c a l eo ft h e s es y s t e m s m o s tt r a d i t i o n a ls t r u c t u r e dp 2 po v e r l a yn e t w o r ka r ec o n s t r u c t e db a s e do nt h ed i s t r i b u t e d h a s ht a b l et e c h n o l o g y ，w h i c ha l s oc a l l e dd h t t h i st e c h n o l o g yc a r lh e l pt h es y s t e mt os e a r c h r e s o u r c ee f f i c i e n t l ya n ds o l v et h el o a db a l a n c i n gp r o b l e m h o w e v e r ，i t sd a t ao r d e rm i g h tb e d e s t r o y e da n dm a k ei td i f f i c u l tt or e a l i z et h er a n g eq u e r i e si nt h e s es y s t e m s i no r d e rt os o l v et h i s p r o b l e m ，an o n d h tb a s e ds y s t e mh a sb e e np r o p o s e d i na d d i t i o n , r e f o r ma n dm o d i f i c a t i o no f t h o s et r a d i t i o n a lp 2 pn e t w o r k si sa l s oad e s i r a b l ew a y d eb r u i j nd i g r a p hi sas p e c i a lg r a p hs t r u c t u r e ，i th a sc h a r a c t e r i s t i c sl i k ec o n s t a n td e g r e ea n d o p t i m a ln e t w o r kd i a m e t e r w ed e s i g nad b s to v e r l a yn e t w o r kb yu s i n gm u l t i p l el a y e rs u f f i x t r e ea n dd eb r u i j nd i g r a p h t h i sn e t w o r kn o to n l yh a st h eg o o dp o i n t so ft r e es t r u c t u r e si n r e s e r v i n gd a t ao r d e rp r o p e r t y ，w h i c ha l l o w sr a n g eq u e r i e s i nt h es y s t e m ，b u ta l s oh a st h e a d v a n t a g e so fc o n s t a n td e g r e eo fd eb r u i j ng r a p hi nt h es t a t i cn e t w o r k i tp r o v i d e sar a n g eq u e r y m e t h o dt ot h a td eb r u i j ng r a p h b a s e ds t r u c t u r e dp 2 po v e r l a yn e t w o r k s s k i pg r a p hi s as t r u c t u r et h a ts u p p o r t sr a n g eq u e r yi t s e l f i ti sad e f o r m a t i o no ft r e e s t r u c t u r e s ，a n dd a t ao r d e rc a nb ep r e s e r v e di nt h i ss t r u c t u r e w h a t sm o r e ，n o d e si nt h i sn e t w o r k a r ea l lh a v ed u p l i c a t i o n sw h i c hc o u l de f f i c i e n t l ye n h a n c et h ef a u l tt o l e r a n c ep e r f o r m a n c eo ft h e n e t w o r k b yu s i n gt h i sg r a p h ，w es t r u c t u r ea n o n d h tb a s e do v e r l a yn e t w o r k ，w h i c hw ec a l l e d s g p o ，i ti sas k i pg r a p hb a s e dp 2 pn e t w o r kw h i c ha l s os u p p o r t st o p o l o g y - a w a r er o u t i n g o v e r t h ed e s i g no ft h i ss y s t e m ，w er e s o l v e dt h er a n g eq u e r yp r o b l e m ，a sw e l la st h ei n c o n s i s t e n c y b e t w e e np h y s i c a ln e t w o r ka n dl o g i c a lt o p o l o g yi nt h ep 2 ps y s t e m s i nt h i sp a p e r ，w em a i n l yd e s i g na n da n a l y z es o m es t r u c t u r e dp 2 po v e r l a y sn e t w o r k sw h i c h s u p p o r tr a n g eq u e r i e s t h ec o n t e n ti sd i v i d e di n t of i v ec h a p t e r s i nt h ef i r s tc h a p t e r , w eg i v ea ni l l u s t r a t i o no ft h es t u d yb a c k g r o u n d ，t h ep r o b l e mw ep u t f o r w a r d ，t h ew o r kw ed o ，a n da l s ot h es t r u c t u r eo ft h i sp a p e r ；t h es e c o n dc h a p t e ri sa l lo v e r v i e w o fe x i s t i n gm e t h o d st h a ta r eu s e di nt h es o l u t i o no fr a n g eq u e r yp r o b l e m ；i nt h et 1 1 i r dc h a p t e rw e d e s i g nad eb r u i j nb a s e dm u l t i p l el a y e rs u f f i xt r e ep 2 po v e r l a yn e t w o r k ( d b s t ) ；i nt h ef o u r t h c h a p t e rw es t r u c t u r eas k i pg r a p h b a s e dg e o g r a p h i c a lp r o x i m i t yo v e r l a yf o rp 2 ps y s t e m sw h i c h i i 基于区间金询的结构化p 2 p 覆盖网设计与分析 s u p p o r tr a n g eq u e r y ( s g p o ) ；t h el a s tc h a p t e ri sac o n c l u s i o na n dp r e s e n t st h ef u t u r es t u d y 仃e n d s k e yw o r d s ：p e e r - t o p e e rn e t w o r k s ；s t r u c t u r e do v e r l a yn e t w o r k ；r a n g eq u e r y ；d e b r u i j nd i g r a p h ；c o n s t a n td e g r e e ；s k i pg r a p h ；t o p o l o g y a w a r er o u t i n g i i i 曲阜师范大学博士硕士学位论文原创性说明 ( 在口划“4 ) 本人郑重声明：此处所提交的博士口硕士酣论文基于区间查询的 结构化p 2 p 覆盖网设计与分析，是本人在导师指导下，在曲阜师范大学攻 读博士口硕士匦学位期间独立进行研究工作所取得的成果。论文中除注明 部分外不包含他人已经发表或撰写的研究成果。对本文的研究工作做出重要 贡献的个人和集体，均己在文中以明确的方式注明。本声明的法律结果将完 全由本人承担。 作者签名：参铂 日期：溯b 易 曲阜师范大学博士硕士学位论文使用授权书 ( 在口划“) 基于区间查询的结构化p 2 p 覆盖网设计与分析系本人在曲阜师范大 学攻读博士口硕士留学位期间，在导师指导下完成的博士口硕士留学位 论文。本论文的研究成果归曲阜师范大学所有，本论文的研究内容不得以其 他单位的名义发表。本人完全了解曲阜师范大学关于保存、使用学位论文的 规定，同意学校保留并向有关部门送交论文的复印件和电子版本，允许论文 被查阅和借阅。本人授权曲阜师范大学，可以采用影印或其他复制手段保存 论文，可以公开发表论文的全部或部分内容。 作者签名：去锡 刷程锄捌 r uv 7 ”， 日期：力勿9 b 多 日期：圳厶、； 基于区问金洵的结构化p 2 p 覆盖网设计与分析 1 1 研究背景和问题的提出 第一章绪论 对等网络( p e e r - t o p e e rn e t w o r k ，以下简称p 2 p ) 1 】，即p 2 p 网络，是目前计算机网 络技术领域研究的一个热点。这一技术所指的网络是所有参与网络的节点( p e e r ) 处于完 全对等的地位，每个节点都同时具备客户端( c l i e n t ) 和服务器( s e r v e r ) 的双重特性，可 以同时作为服务使用者和提供者，整个网络可在无中心管理控制的状态下运行，具有高度 自治性，节点之间可以直接交换信息和共享资源。它具有无中心性、高动态性、强异构性、 分布广泛等特点，这些基本特征使得它可以组建大规模、动态的自组织计算机系统，并无 需成本高昂的超级计算基础设施。该技术有着广阔的应用领域，目前主要应用于文件交换、 分布式计算、协同工作、分布式搜索等。 这一网络的出现打破了传统网络的“c l i e n t s e r v e r ”( c s ) 模式，从某种意义上说，这 是一种向传统互联网技术的回归，因为互联网最初的设计目标就是让网络上的计算机相互 之间可以直接通信而不需要中介。随着p 2 p 技术的飞速发展，互联网的存储模式将由目前 的“内容位于中心”模式转变为“内容位于边缘 模式，改变i n t e m e t 现在的以大网站为 中心的状态，重返“非中心化”，将权力交还给用户。 p 2 p 系统可分为集中式系统、分布式非结构化系统和分布式结构化系统三类。其中， 分布式结构化系统是根据覆盖网络，通过路由机制实现资源定位，其代表系统有c h o r d 2 ， 3 】、p a s t r y 4 、t a p e s t r y 5 和c a n 6 ，7 】等，这类系统多基于分布式哈希表( d i s t r i b u t e dh a s h t a b l e ，以下简称d h t ) 8 ，9 】方法构建。d h t 方法，是将数据项通过哈希运算得到键值 ( k e y ) ，根据键值将该数据项分配到系统中一个唯一的节点上，由该节点负责存储这个数 据项。这一技术主要用来映射网络中的关键字到每个节点，使用该方法可以解决分布式结 构化系统的存储问题，并能保证系统具有较高的可扩展性以及负载平衡。 在一个基于d h t 方法构建的系统中查找资源，发出查询请求的节点使用相同的哈希 函数对该资源进行计算从而得到它在该网络中相对应的关键字，再使用该关键字对资源进 行搜索，这是最初的单一关键字查询，或称精确匹配( e x a c t m a t c h i n g ) 。因为哈希运算破 坏了关键字的顺序，对于一些复杂查询，例如基于顺序的区间查询( r a n g eq u e r y ) ，这类系 统是不支持的。此外，由于数据项经过哈希运算后，所存储的位置大都不是提供该数据的 节点，因此，其数据的本地可控性也较差。这样一来，传统的基于d h t 技术构建的系统 就无法有效的保证数据存储的本地性以及区间查询等功能。系统的可扩展性和负载平衡能 力也被其弱本地意识性和仅支持单一匹配查询的缺陷所掩盖，这是该类系统的一个明显缺 点。 基于区间金询的结构化p 2 p 覆盖刚设计与分析 高效的数据查找方法是p 2 p 计算的核心所在，在第一代仅支持单一关键字查询的p 2 p 系统之后，人们开始对p 2 p 覆盖网的复杂查询问题产生兴趣，复杂查询的概念也被提出， 这其中就包括区间查询。在一个p 2 p 覆盖网络中，区间查询的定义是找到一个特定区域中 的所有关键字，这在大范围的数据管理系统中是一个强有力的工具，并且对于多数应用来 说都十分重要，例如数据管理等。能够支持这一功能的系统也越来越成为人们感兴趣的焦 点，设计一个支持区间查询的系统也被列为一个开放性问题【1 0 】。目前在结构化p 2 p 覆盖 网络中解决区间查询问题的研究方向主要有两个，一个是对已有的基于d h t 技术构建的 系统进行修改，使其能够支持区间查询；另一个则是放弃d h t 技术，设计非基于d h t 的 覆盖网络，使其以某种方式保留关键字顺序，从而支持区间查询。 非基于d h t 的p 2 p 覆盖网络大都采用避免哈希计算的方法解决基于d h t 技术构建的 p 2 p 系统的缺陷。在这些系统中，就包含了基于多种树形结构的网络，这些网络都提供一 种分布式搜索树( d i s t r i b u t e ds e a r c ht r e e ，以下简称d s t ) 的功能，允许基于顺序的数据 查询。基于d s t 的p 2 p 系统都是采用保留顺序( o r d e r - p r e s e r v i n g ) 的结构来构造，因此， 它支持与键值顺序相关的查询。并且，资源不经过哈希运算，都保存于提供该资源的节点 上，具有较高的本地可控性。这些系统的例子有p g r i d 1 1 】、跳图( s k i pg r a p h ) 【1 2 、 h y p e r r i n g 1 3 和b a t o n 1 4 等。其中，p - g r i d 是基于t r i e 结构的，跳图【1 2 】是基于跳表( s k i p l i s t ) 【1 5 概念提出的，h y p e r r i n g 基于确定的2 3 树构造的，b a t o n 基于平衡二叉树( a v l ) 设计的。根据这些系统中相应的树结构所采用的局部规则集合，我们将他们分为两类： ( 1 ) 使用分裂和合并操作的b 树( b - t r e e ) 【1 6 及它的衍生物； ( 2 ) 使用旋转操作的平衡二叉树( a v l t r e e ) 和红黑树( r e d b l a c kt r e e ) 等。 在对基于d h t 技术的系统设计上，我们将d eb r u i j n 图 1 7 ，1 8 】和树形结构相结合， 开发出了一种新型的p 2 p 覆盖网，称为d b s t ，它是一种基于d eb r u i j n 图和多层后缀树的 p 2 p 网络，具有节点常数度和最优网络直径的特点。此外，由于它属于一种保留顺序的树 形结构，因此，能够实现区间查询功能。 在非基于d h t 的系统研究上，我们提出了一种s g p o 覆盖网，它是一种基于跳图的 节点地理位置邻近的p 2 p 覆盖网络。该系统使用跳图作为逻辑拓扑，并在设计时加入了一 种n t l m 机制，使系统既能支持区间查询，同时又可以实现拓扑意识路由。此外，它还具 有其它基于d h t 技术构建的系统的大部分性质，例如对数级网络直径等。通过对这一系 统的理论分析，我们还提出了一个有限负载平衡的概念，它可以有效地提高s g p o 的容错 性，并且这一结果可通过仿真数据得以证实。 1 2 论文组织结构 第一章的绪论简要介绍了p 2 p 网络的发展状况、问题的提出和相关工作，给出本论文 的相关组织结构。 2 摹于区间查询的结构化p 2 p 覆盖嘲设计- 1 - j 5 ) 析 第二章对目f j 结构化p 2 p 覆盖网中现有的一些区间查询的方法作了一个简单概述，并 分为基于d h t 技术构建的系统和非基于d h t 的系统两部分进行了讨论。 第三章提出了一个d b s t 系统，它是一种基于d eb r u i j n 图和多层后缀树的p 2 p 覆盖 网，可以实现网络节点的常量度和最优网络直径等特点，并支持区间查询。 第四章设计了一个s g p o 系统，它是一种基于跳图的节点地理位置邻近的p 2 p 覆盖网 络。它使用跳图作为其底层拓扑结构，结合一种n t l m 机制，该系统可以使那些地理邻近 的节点在逻辑覆盖网中连接在一起，这就使得s g p o 既支持区间查询，同时又能通过地理 规划方法实现拓扑意识路由。 第五章对全文进行了总结，并对下一步的研究提出了设想。 基于区间查洵的结构化p 2 p 覆盖网设计与分析 第二章几种区间查询方法的概述 2 1 基于d h t 的系统 p 2 p 网络对于区间查询的支持，已经被视为一项重要的开放性的研究课题。研究者们 所作的一部分努力集中于尝试改善已存的基于d h t 技术的结构，以使其支持区间查询。 这些努力所要面临的最主要问题是随机的哈希函数，这是d h t 类结构用来使不同节点间 达到分布式负载平衡的方法，但不利于区间查询的实现，这是因为在对数值使用哈希函数 计算后，将会使得同一区域内的数值间不再有任何的关系。下面，我们会提供几个支持区 间查询的基于d h t 技术构造的p 2 p 覆盖网，以这几个系统为例来讨论这类覆盖网在解决 区间查询问题时所使用的方法。 2 1 1 扩展的c a n 一种可行的解决方法是对区间进行哈希而非单个数值，这就需要事先将总的区域进行 划分并分配给不同的节点。使用这一方法，划分的规模会成为一个问题，如果划分的区域 过大，容易造成节点超载；另一方面，如果划分的太小，那么定位一个数据就需要更多的 路由跳数。c a n 覆盖网的逻辑拓扑结构就是基于对空间进行分割而构造的，它将d 维迪卡 尔空间分割成若干小区域，每个区域都分配一个节点作为该区域拥有者，在c a n 覆盖网 的基础上，可以有效地解决区域划分大小的问题，因此很多基于d h t 构建的结构化p 2 p 系统都采用扩展c a n 的方法来实现区间查询功能。我们选取其中两个系统做相关讨论。 在文献 1 9 】中，研究者们通过在c a n 覆盖网中使用希尔伯特空间填充曲线( h i l b e r t s p a c ef i l l i n gc u r v e s ) 2 0 实现了区间邻近数值到c a n 邻近区域的映射关联，希尔伯特空 间填充曲线是一条无交叉的穿过多维空间中所有子空间的曲线，沿着曲线的方向，每个子 空间的编码都是紧邻的。它可以用递归的方法定义：对于一个近似层值的数值，来说，当，= l 时，它表示一个点，当，= 2 时，它表示一个划分为四个子区域的区域，依次类推，对于每 一个更高的近似层值，我们都是通过将原有的每个区域再划分为四个子区域得到。每一 个这样创建出来的区域，都与区间【0 0 ，1 0 】中一个特定的子区间相对应。我们在图2 1 中分 别给出了近似层值，= 2 和，= 3 的希尔伯特曲线。 在该方法中，服务器的一个子集合，被称为区间管理员，它们主要负责子区间的属性 值域，每个节点都要向适当的区间管理员报告自己当前的属性值。当系统发出一个区间查 询请求，消息将通过两个方向传播，并传递给相应的区间管理员，一个方向是发送至比请 求区间的数值高端更高的邻居节点，另一个方向是发送至比请求区间的数值低端更低的邻 居节点。这是第一个用于解决c a n 覆盖网中区间查询的方法。该方法能够有效的保证系 4 基于区问金询的结构化p 2 p 覆盖网设计与分析 统的扩展性、可用性和通信有效性等目标。因此，这也使得基于希尔伯特曲线的方法越来 越多的用于解决p 2 p 系统中的区间查询问题，并延展至在其他经典p 2 p 覆盖网络中使用， 例如c h o r d 覆盖网 2 1 】。 1 0 2 5 os i 1 0 s ，0 7 9 厂 l i 1 0 o 2 1 c lm 7 s 1 1 l li - - - 一 l li i = 2l = 3 图2 1 当l = 2 和l = 3 时的希尔伯特曲线 另外一种扩展c a n 的方法是s a h i n 等人在文献【2 2 】中提出的，他们将c a n 系统扩展 为d = 2 。构建一个虚拟的哈希空间，将每个属性值表示成一个二维正方形，并用其属性域 中的最低值和最高值进行界定。例如，给定一个域为【口，b 】的一维属性，与其相对应的虚拟 哈希空间就是一个在直角坐标系中由坐标( 口，口) ，( 6 ，口) ，( 6 ，6 ) 和( 口，6 ) 界定的二维正方形。 这个正方形会被进一步划分成多个矩形区域，且任意两个区域都不重叠。每个区域都被分 配一个节点，这个节点储存那些经哈希计算后属于该区域的区间值，以作为可用的区间查 询结果，并存储邻近区域的相关路由信息。图2 2 给出了一个区间属性值域为【3 0 ，7 0 】的虚 拟空间区域划分图示。查询消息会通过虚拟空间在各矩形区域内进行路由，一旦消息到达 那个区域，该区域所存储的结果就会被查看，如果查询结果在该区域被找到，它们就会返 回。否则，查询消息将会向位于其左边和上面的那些可能含有所需结果的邻居区域继续进 行路由。 基于区间查询的结构化p 2 p 覆盖闷设计与分析 这一方法延展了p 2 p 系统，使其能够在更复杂和更加结构化的数据库上支持更普遍的 数据查询。设计这一方法的主要灵感来源于关系数据库中的s e l e c t i o n 操作，它通常都 会参与数据库查询，并且是从数据库中检索数据的最基本操作。这一方法的最基本目标， 是通过使用d b m s ( d a t a b a s em a n a g e m e n ts y s t e m ，数据库管理系统的缩写) 以实现p 2 p 系统对多种类型的复杂查询的支持，从而使得基本的点对点数据支持成为可能。 2 1 2 在关系数据库中共享资源 g u p m 等人在文献【2 3 】中提出了一个p 2 p 系统，它是一种在c h o r d 覆盖网中进行关系数 据共享的结构，使用一种基于哈希的方法对区间查询提供近似答案。给定一个区间，考虑 该区间中的一个数值的集合，通过使用一种特殊的哈希函数将集合中的每一个数值计算为 一个整数，并最终选取最小的那个整数成为该区间的标识符。使用这一方法，查找操作会 在d ( 1 0 9 ) 跳内完成，其中是系统中节点的数量。然而，从仿真结果中我们也能看到， 对于较大规模的网络来说，存在负载平衡问题。 基于d h t 技术构建的p 2 p 网络，其主要优点就是使用哈希函数使系统实现负载平衡， 然而，当对d h t 技术进行改善以适用区间查询时，又会破坏掉这一性质。因此，多数能 使d h t 支持区间查询的方法，都会引起负载不能平衡的问题。 2 2 其他非基于d h t 结构的系统 因为d h t 技术更适用于单一匹配查询，且改变d h t 技术以支持区间查询通常又会制 造负载平衡的问题，所以，许多研究者也开始关注于使用其他结构来实现区间查询。为与 前面的讨论相区分，我们将这些不使用d h t 技术构造的系统归于非基于d h t 结构一类。 并且，这类系统中的某一些也能实现负载平衡，下面，我们就介绍几种常见的结构。 2 2 1 跳图 跳图( s k i pg r a p h ) 【1 2 是我们在此处讨论的第一个系统，它是跳表( s k i pl i s t ) 1 5 的 一般化形式，它支持区间查询。我们在本文第四章中设计的s g p o 覆盖网就是一个基于跳 图的支持区间查询的p 2 p 覆盖网，关于跳图的详细介绍我们也会在第四章给出，这里仅做 简单介绍。 跳图的最底层，也就是第0 层，是一个由所有参与网络的节点构成的双向链表，且该 链表以节点关键字的升序排列。当一个区间查询请求发出，例如寻找关键字k z 的节点， 寻找关键字k x 的节点，寻找关键字k x 中最小的节点， 寻找区间【x ，y 】中的某些节点，以及寻找区间k y 】中的所有节点等，这类查询操作都将首 6 皋于区间查询的结构化p 2 p 覆盖网设计与分析 先找到位于搜索区间中的一个节点，然后通过查询该节点的邻居节点，找到处于该查询区 间中的其他所有节点。然而，跳图自来具有不能实现负载平衡的问题，这是因其特有的插 入、删除操作或查询负载造成的。 由于跳图对于区间查询的支持，一些非基于d h t 结构的系统都使用它的一些衍生物 设计以支持区间查询功能。它们当中的一些系统可以对抗其自有的负载平衡问题，例如 s k i p n e t 2 4 】。s k i p n e t 系统使用跳图作为其逻辑拓扑，研究者们还在该系统中提出了一个限 制负载平衡c l b 的概念( c o n s t r a i n e dl o a db a l a n c i n g 的缩写) ，c l b 的意思是说系统中处 于同一个c l b 域内的所有节点可以实现负载平衡。另一种使用跳图构建的系统是g a n s e n 等人在文献 2 5 1 中提出的，该系统使用两个跳图构建，其中一个跳图用来做数据索引，另 一个跳图用来追踪节点上的负载。系统中的每个节点能够确定系统的最小负载、最大负载 及其邻居节点上的负载，同时，研究者们还设计了一个算法用来平衡邻居节点间的负载， 以使得空节点能够接管高负载节点的信息。 我们的研究也关注于p 2 p 系统的区间查询问题以及相关的负载平衡问题。在第四章中， 我们提出了一种基于跳图的节点地理位置邻近的p 2 p 覆盖网络，称为s g p o 系统。它基于 跳图构建，并使用一种n t l m 机制，可以使那些地理邻近的节点在逻辑覆盖网中彼此连接。 我们已知使用跳图可以将节点的关键字按升序进行排列，跳图也因此能够支持区间查询。 我们所设计的s g p o 系统是基于跳图设计的，因此也就同样支持区间查询功能。同时我们 也在该系统中提出了一个有限的负载平衡概念( 1 i m i t e dl o a db a l a n c i n g ) ，它的意思是系统在 逻辑层面上能够达到负载平衡，但在底层物理网络上无法实现这一属性。这是因为我们在 设计系统时，安排系统中的一个节点表示一个资源，这一重大贡献同时也可有效提高系统 的容错性能。 除以上几个系统以外，仍有很多网络致力于解决系统负载平衡的问题，由于此处篇幅 有限，不再赘述。 2 2 2 多种树形结构 树形结构是p 2 p 系统中另外一种有名的能够支持区间查询的结构。它包含了许多不同 的形势，像平衡二叉树，b 树，t r i e 树等。这类基于树形结构构造的系统，都是由于树的 物理结构，所以能够解决区间查询问题。一些基于树结构的p 2 p 覆盖网使用d h t 结构， 另外一些不用，这旱我们将所有这类覆盖网划分为非基于d h t 一类，下面我们将选择其 中几种树结构展开讨论。 b a t o n 1 4 系统是基于平衡二叉树构造的p 2 p 覆盖网。这一覆盖网，既能有效的支持精 确查询，又能有效的支持区间查询。同时，每个节点的负载也基本相等，当网络中有大量 节点失效时依然能够保持连通。在文献 2 6 】中，研究者们还提出了另一种树结构，他们称 为分布式分段树。它是一种传统树结构的变形，来源于计算几何学，实质上就是一个完全 7 基卡区间盘询的结构化p 2 p 覆盖网设计与分析 - - y 树。我们在图2 3 中给出了一个区间为【0 ，7 】的分段树的例子。从图中我们可以看出， 区间【0 ，7 】被划分成了不同的区域，这些区域被表示成了一棵二叉树的形式。给定一个区间 p ，t 】，区间查询可以返回属于这一区间中的全部关键字。现在这一结构也被用于了p 2 p 覆 盖网中。 图2 3 区间为【0 ，7 】的分段树 如我们所知，b + 树 2 7 】已被广泛用于集中式数据库的区间查询，但是分布式b + 树并没 有直接应用于p 2 p 环境中。因此，研究者们在p 2 p 覆盖网中提出了一个p 树 2 8 1 的概念。 在一个p 树中，每个节点仅储存并维护其相应b + 树中最左边的那条根到叶路径，节点依靠 一个由其他节点中选择出来的子集来完善自己的树，这一结构也能支持区间查询。 t r i e 树，又被称为前缀树，是一种标准的数据库索引结构。它是一种有序的树形数据 结构，通常用来存储关键字是字符串类型的数组。与二叉搜索树不同的是，t r i e 树中的节 点都不存储与其相关联的关键字，而是通过该节点在树中的位置来表示它与哪个关键字相 关联。图2 4 是一棵包含关键字“t ”，“t o ，“t e ”，“t e a ”，“t e n ，“i ”，“i n 和“i n n 的t r i e 树。文献 2 9 1 是一篇关于如何在一个基于t i l e 树结构的p 2 p 覆盖网上实现区间查询功能的 论文。 图2 4 一个t r i e 树结构的例子 8 基于区间查询的结构化p 2 p 覆盖 。g 设计与分析 g o n z , q l e z b e l t r h n 等人在文献【3 0 】中开发了一种系统，称为跳图树( s k i pt r e eg r a p h ) 。从 它的名字中我们也能看出该系统将树结构与我们在前面讨论过的跳图进行了关联，因为后 者能够实现区间查询的功能，所以跳图树也支持这一功能。同时，通过这两种结构的组合， 系统延展了它们各自的功能，并且一些重要的性能也有所提高。 2 2 3 其他方法 以上我们所介绍的方法大都是基于单一属性区间的查询，文献【3 1 】中提出的m e r c u r y 系统是一个支持基于多属性区间搜索的可扩展的网络协议。 m e r c u r y 与前面所提到的系统的区别在于，它既支持多属性查询，同时又能实现负载 平衡。为了保证高效的路由和负载平衡，m e r c u r y 系统在高动态覆盖网络中对随机节点使 用一种新颖的轻量抽样机制进行均匀抽样。在这一体系中，节点被分组到一些虚拟h u b 中， 每个h u b 都负责一些查询属性，处于h u b 中的节点被组织为类似于c h o r d 的环结构。随机 抽样是用来估量节点上的平均负载，并同时找到负载最轻的那一部分。m e r c u r y 覆盖网能 够实现对数级路由和接近统一的负载平衡的目标。 2 3 总结 结构化p 2 p 系统中对于区间查询功能的支持当前已经是一项积极并有重要意义的研究 课题。在这一章中，我们也介绍了一些解决这一问题的方法。然而，这些方法或者系统在 能够保证区间查询的同时，却不能保证系统的负载平衡问题。此外，这些系统中有一些也 是基于其使用的逻辑拓扑图来实现区间查询的目的。 在下面的两章中，我们将详细介绍d b s t 覆盖网和s g p o 覆盖网，它们都是可实现区 间查询功能的p 2 p 覆盖网。其中，前者是对现有基于d h t 技术构建的网络的改进，后者 是利用跳图设计的非基于d h t 的系统。 9 基于区间查询的结构化p 2 p 覆盖网设计与分析 第三章d b s t - 一种基于d eb r u i j n 图的常数度后缀树p 2 p 覆盖网 网络设计都存在一个度一直径的问题，这个问题可以定义为如何设计一个动态分散的 自组织系统，使得对于一个系统，给定节点数和度数，使网络直径最小。只要达到了这个 最小的直径，资源的查找操作就可以利用这个直径在最短路上实现。设计一个具有常量度 和最优网络直径的p 2 p 覆盖网，也是许多研究者关注的问题之一，许多研究 3 2 ，3 3 ，3 4 】 都在寻求常量度数且具有较小网络直径的覆盖网。我们都知道p 2 p 覆盖网络具有大规模和 高动态性的特征，节点频繁的加入、离开操作会引起系统的不稳定，因此设计这样的一个 覆盖网络具有很大的挑战性。一些特殊的图结构在静态网络中可以实现常量度以及最优网 络直径，例如k a u t z 图【3 5 ，3 6 】、d eb r u i j n 图【1 7 ，1 8 】、蝶形图等，但是在p 2 p 覆盖网络 中，随着动态性的加入，这些性质就无法保证。 这一章，我们来详细介绍d b s t 系统，它是一种基于d eb r u i j n 图和树形结构的p 2 p 覆盖网络。我们使用后缀树的形式对d eb r u i j n 图进行多层构建，使得系统既能保留d e b r u i j n 图在静态网络中的性质，同时又可以基于树形结构保留关键字的顺序性，以实现区 间查询功能。因为我们在使用d h t 技术时，同时设计了一种全新的资源分配方法，可以 实现资源存放的本地化以及多点存放，从而在保留d h t 技术的同时，改善了该技术在资 源本地化和区间查询功能上的缺陷。 3 1d eb r u i j n 图 我们首先给出d eb r u i j n 有向图 2 4 ，2 5 的定义及相关性质。 给定两个整数d ( 2 ) 和d ( 1 ) ，d eb r u i j n 有向图记为b ( d ，d ) ，其中d 为节点度，d 是 网络直径，b ( d ，d ) 的顶点集v = x d l x d 一2 x i x o ： 0 ，l ，d - l ，f - l ，2 ，d ) ，它的边集e 是由从顶点一。而一2 而到d 个一：x l x 的所有边组成的，其中口 o ，l ，d - 1 ) 。一 个记为b ( d ，d ) 的d eb r u i j n 有向图所构成的网络规模为n = d d ，图3 1 是由8 个节点构成 的b ( 2 ，3 ) 静态d eb r u i j n 网络。 在一个d eb m i j n 图中从节点彳到节点b 作路由操作，是通过使用r 对节点彳作连续左 移位操作，直到到达节点b 的方法实现的。这一过程可以通过下面的公式表达出来： b = ( d 掌a + i ) m o dn ，i = t o p l e t t e r ( r ，k ) 其中，t o p l e t t e r ( r ，k ) 是一个函数，它返回足中从左边开始第k 个字母，k 则是从源节点a 开 始的覆盖距离长度。对于任意节点a ，路由操作中对下一跳节点a 的选择，是通过对节点 彳作左移位操作，使得节点a 是节点a 的一个邻居。例如，在一个d = 2 的d eb r u i j n 图中， 从节点0 1 l 路由消息至节点0 0 0 ，所经过的路径为0 1 l 寸1 1 0 1 0 0 寸0 0 0 。因此，以这种 i o 基于区间盘询的结构化p 2 p 覆盖网设计与分析 方式在d eb r u i j n 图的任意两个节点问路由，其至多在d = l o g dn 路由跳之内完成。 lo l l i 图3 1b ( 2 ，3 ) 静态d eb r u i j n 网络 通过上面的定义，我们可以看出d eb r u i j n 图有以下优点： ( 1 ) 节点常数度。网络中每个节点的出度和入度都是常数d 个，这代表节点的路由表 规模是常数级的，与网络规模无关。 ( 2 ) 最优的网路直径。在有个节点构成的网络中，任意两个节点间的路由都至多 在d = l o g j n 跳内完成。 ( 3 ) 强连通性。对d eb r u i j n 图的网络连通性作进一步研究之后，可以证明在不断开 任何节点或节点集合的情况下，至多有d 1 个节点会失效，这是因为任意两点间都存在 d 一1 条内点不相交的路径。由此可见，d 也是网络设计中的一个重要参数。 除以上优点外，d eb m i j n 图也有相应的缺点，其最大的缺陷就是不能很好的应用于动 态网络，因为当网络中有d 1 个节点离开时，d eb r u i j n 图就不再有上述优点存在。而p 2 p 覆盖网络正是一种大规模动态性的网络