（计算机应用技术专业论文）p2p网络中分类数据查找算法的研究与实现.pdf

二vj 飞 _1 f at h e s i sf o rt h ed e g r e eo fm a s t e ri nc o m p u t e r a p p l i c a t i o nt e c h n o l o g y s t u d ya n di m p l e m e n t a t i o no na l g o r i t h m so f s e a r c h i n gt a x i m o m i c a ld a t ai np 2 p n e t w o r k s l a x 0 n o | c a ld a t a b yx i e k e x i n s u p e r v i s o r ：p r o f e s s o rw a n g g u o r e n n o r t h e a s t e r nu n i v e r s i t y d e c e m b e r2 0 0 7 ， 独创性：声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 ；茧 恧。 学位论文作者签名：谢呵l 山 e t 期：钞口口i 弓1 7 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： 1 东北大学硕士学位论文 摘要 p 2 p 网络中分类数据查找算法的研究与实现 摘要 近年来随着计算机技术、网络技术和数据库技术迅速发展，p 2 p 技术的研究受到密 切关注并得到广泛应用。由于p 2 p 技术具有非中心化、可扩展性、健壮性、高性能价 格比、隐私保护和负载均衡等特点，适合应用于文件共享、对等计算、即时通信、协同 工作和搜索技术等。当前p 2 p 的研究主要集中在网络模型、查找问题和资源管理等方面。 我们先提出了分类数据的语义模型，接着提出了存储遵循某种分类数据语义模型的 数据的分类数据环( t d r n ) 模型。在t d r n 模型中，我们提供了简单路由机制和复杂 路由机制。t d r n 模型主要提供了p e e r 的加入、离开操作和数据项的查找、插入、修改 和删除的操作，这些操作可以满足一般的p 2 p 网络中文件共享的需求。 我们在实现中用模拟t d r n 模型来代替真实t d r n 模型，并在单机环境进行了实 验。我们主要设计并实现了p e e r 加入、离开的算法，数据项的查找、插入、修改和删除 算法，其中数据项的查找算法是插入、修改和删除算法的基础，查找分为概念域查找和 精确查找。我们还对这些算法在两种路由机制下的时间复杂度进行了理论分析。 在实验中，我们生成了一棵三层分类树和一棵四层分类树作为分类数据语义模型， 接着随机为分类树的节点生成数据项，用来进行数据项的操作。我们以p e e r 的数量和数 据项的数量来衡量网络的规模，测试了以上算法的响应时间、转发消息数和转发消息的 跳数。其中模拟网络中这些算法的响应时间变化情况与真实网络中的不尽相同，而转发 消息数和转发消息的跳数与真实网络中是一致的。结果表明t d r n 模型能够对分类数据 进行有效的处理。 冬 矽 关键词：p 2 p ；网络模型；查找；分类数据 、一，kr 、1 n 一1 _ 一1 1 一 s t u d ya n di m p l e m e n t a t i o no na l g o r i t h m s o f s e a r c h i n gt a m i c a ld a t a 。p 2 pn e t w o r k l l a x o n o m i c a ld a t ai n1 2e t w o r k s a b s t r a c t i nr e c e n ty e a r s ，、i t l lr a p i dd e v e l o p m e n to fc o m p u t e rt e c h n o l o g y , n e t w o r kt e c h n o l o g ya n d d a t a b a s et e c h n o l o g y , p 2 pt e c h n o l o g yo n c ea g a i nr e c e i v e sc l o s ea t t e n t i o na n di sw i d e l ya p p l i e d s i n c ep 2 pt e c h n o l o g yh a ss u c hf e a t h e r sa s n o n - c e n t e r , s c a l a b i l i t y , r o b u s t n e s s ，h i g h p e r f o r m a n c e p r i c er a t i o ，p r i v a c yp r o t e c t i o n a n dl o a db a l a n c e ，i tf i t si nf i l es h a r e ，p e e r c o m p u t a t i o n ，c o o p e r a t i o na n d s e a r c hf i e l d s a tp r e s e n t ，p 2 pr e s e a r c hw o r km a j o r l yf o c u s e so n n e t w o r km o d e l s ，s e a r c hp r o b l e m sa n dr e s o u r c em a n a g e m e n t w ef i r s t l y p r o p o s e t h es e m a n t i cm o d e lo ft a x o n o m i c a ld a t a , a n dt h e np r o p o s e t a x o n o m i c a ld a t ar i n gn e t w o r k ( t d r n ) ，d a t ai nw h i c hf o l l o was e m a n t i cm o d e l i nt d r n m o d e l ，w ep r o v i d es i m p l er o u t i n gm e c h a n i s ma n dc o m p l e xr o u t i n gm e c h a n i s m i nt d r n m o d e l ，w ep r o v i d ep e e rj o i na n dl e a v eo p e r a t i o n sa n di t e ms e a r c h ，i n s e r t , u p d a t ea n dd e l e t e o p e r a t i o n s ，a n dt h e s eo p e r a t i o n ss a t i s f yc o n l m o nn e e d sf o rf i l es h a r ei np 2 p n e t w o r k s i no u ri m p l e m e n t a t i o nw es u b s t i t u t e t h es i m u l a t i n gt d r nm o d e lf o rr e a lo n ei n e n v i r o n m e n to fas i n g l ec o m p u t e r w cm a j o r l yd e s i g na n di m p l e m e n ta l g o r i t h m so fp e e rj o i n a n dl e a v e ，a n di t e ms e a r c h ，i n s e r t , u p d a t ea n dd e l e t e a l g o r i t h m so fi t e mi n s e r t ，u p d a t ea n d d e l e t ea r eb a s e do ni t e ms e a r c h ，w h i c hi n c l u d e sd o m a i ns e a r c ha n de x a c ts e a r c h l a t e rw e c a r r yo u tt h e o r e t i c a la n a l y s i so nt i m ec o m p l e x i t i e so ft h e s ea l g o r i t h m su n d e rt h et w or o u t i n g m e c h a n i s m s i ne x p e r i m e n t s ，w eg e n e r a t eat h r e e - l a y e r e dt r e ea n daf o u r - l a y e r e dt r e ea ss e m a n t i c m o d e l so ft a x o n o m i c a ld a t a , a n dt h e nw eg e n e r a t ei t e m sr a n d o m l y , w h i c ha r eu s e df o ri t e m o p e r a t i o n s w cm e a s u r et h en e t w o r k s i z ew i t ht h ep e e ra m o u n ta n dt h ei t e ma m o u n t w i t ht h e n e t w o r ks i z ei n c r e a s i n g ，w et e s tr e s p o n s et i m e ，m e s s a g ea m o u n t sa n dh o p so ft h ea b o v e a i g o f i t h m s a l t h o u g hc h a n g i n go fr e s p o n s et i m ei ns i m u l a t i n gt d r ni sn o tt h es a l t t ea st h a t i nt h er e a lo n e ，m e s s a g ea m o u n t sa n dh o p si ns i m u l a t i n gt d r na r ei nc o n s i s t e n c y 、i t l lt h o s e i nt h er e a lo n e r e s u l t ss h o wt h a tt d r nm o d e lc a ne f f e c t i v e l yd e a lw i t ht a x o n o m i c a ld a t a k e y w o r d s ：p 2 p ；n e t w o r km o d e l ；s e a r c h ；t a x o n o m i c a ld a t a i l l - 、，_r 、 、l j 1 0j 、 r ； j 王 东北大学硕士学位论文目录 目录 独创性声明i 摘要。i i a b s t r a c t i i i 第一章绪论1 1 1 研究背景1 1 2p 2 p 网络模型4 1 2 1 集中目录式模型。4 1 2 2 非结构化网络模型5 1 2 3 结构化网络模型6 1 2 3 混合型网络模型1 2 1 3 本文的贡献1 3 1 4 本文的组织结构。1 3 第二章分类数据环网络模型1 5 2 1 模型的提出1 5 2 2 分类数据语义模型l7 2 3 语义模型的转换18 2 4 分类数据环网络模型1 9 2 4 1t d r n 真实网络模型。1 9 2 4 2t d r n 模拟网络模型2 0 第三章分类数据环网络的构建2 1 3 1 分类树节点的实现2 1 3 2 数据项的实现2 5 3 3p e e r 的实现2 6 3 4 数据库层的实现2 8 3 5p e e r 的加入与离开2 9 第四章路由机制与数据查找3 7 4 1p e e r i d 的分配与路由机制3 7 4 1 1p e e r i d 的分配3 7 4 1 2 路由机制3 8 4 2i t e m 的查找4 2 一i v 东北大学硕士学位论文 目录 4 3i t e m 的插入、修改和删除5 0 第五章实验及结果分析5 3 5 1 实验设置5 3 5 1 1 实验环境一5 3 5 1 2 数据的产生5 3 5 1 3 参数的说明一j 5 4 5 2 实验结果及分析5 5 5 2 1p e e r 操作的测试一5 6 5 2 2i t e m 操作的测试5 9 第六章结束语6 3 参考文献6 5 致 射一6 9 攻读硕士期间发表的论文7 1 一v 一 醅l l ， ： l ， 东北大学硕士学位论文 第一章绪论 第一章绪论帚一早珀。y 匕 p 2 p ( p e e r t o p e e r ) 是近几十年来兴起并不断壮大的一种日益重要的网络模 型，它是传统的c s ( c l i e n t s e r v e r ) 模型的有益补充，二者在互联网的发展和应 用上相得益彰，都起着举足轻重的作用。与传统的c s 网络模型相比，p 2 p 网络 模型中客户端和服务器不再泾渭分明，它们被视为p e e r ( 本有对等的人或物之意) 。 每个p e e r 既可以给别的p e e r 提供数据( 作为服务器) ，又可以从别的p e e r 获得数 据( 作为客户端) 。这样数据不必集中在相对少数的几个服务器上，增加了数据的 冗余，减轻了提供服务器的负担。p 2 p 查找技术是构建p 2 p 系统的基础性关键技 术，对p 2 p 系统的可扩展性、性能和健壮性等各方面都有着十分重要的影响。p 2 p 应用环境所具有大规模、分布式、不稳定性等诸多特点以及数据源的差异性都给 p 2 p 查找技术带来了诸多挑战。p 2 p 有许多应用方向，其中数据共享是一个重要 的方面，而在海量的数据中如何有效地查找到需要的数据，则需要深入的研究和 探讨，本文就是在这样的背景下展开的。 1 1 研究背景 从某种意义上说p 2 p 技术并不是新技术。最初互联网是结构和功能相似的计 算机连接组成，这些相似的计算机是最初的p e e r ，那时的网络是p 2 p 网络的雏形。 由于受早期计算机性能、资源等因素的限制，随着互联网规模的迅速扩大，大多 数连接到互联网上的普通用户并没有能力提供网络服务，从而逐步形成了以少数 服务器为中心的c s ( c l i e n t s e r v e r ) 模型。在c s 模型下，对客户机的资源要求非 常少，因而可以使用户以非常低廉的成本方便地连接互联网，推动了互联网的快 速普及。随着计算机硬件和网络技术的发展，以及用户对进一步交流信息和共享 资源的需求增大，p 2 p 技术再次受到关注。以共享m p 3 音乐软件的n a p s t e r t i 】为代 表的p 2 p 软件的兴起和风靡，标志着p 2 p 技术重新回到了人们的视野当中，重新 出现在互联网应用的舞台中央，从而使p 2 p 技术在互联网中占有举足轻重的地位。 p 2 p 技术【2 , 3 , 4 , 5 1 有其本身的特点和优势，主要体现在以下几个方面。 ( 1 ) 非中心化：网络中的资源和服务分散在所有结点上，信息的传输和服务 的实现都直接在结点之间进行，可以无需中间环节和服务器的介入，避免了可能 的瓶颈。p 2 p 的非中心化基本特点，带来了其在可扩展性、健壮性等方面的优势。 ( 2 ) 可扩展性：在p 2 p 网络中，随着用户的加入，不仅服务的需求增加了， 系统整体的资源和服务能力也在同步地扩充，始终能较容易地满足用户的需要。 论文第一章绪论 整个体系是全分布的，不存在瓶颈。理论上其可扩展性几乎可以认为是无限的。 ( 3 ) 健壮性：p 2 p 架构天生具有耐攻击、高容错的优点。由于服务是分散在 各个结点之间进行的，部分结点或网络遭到破坏对其它部分的影响很小。p 2 p 网 络一般在部分结点失效时能够自动调整整体拓扑，保持其它结点的连通性。p 2 p 网络通常都是以自组织的方式建立起来的，并允许结点自由地加入和离开。p 2 p 网络还能够根据网络带宽、结点数、负载等变化不断地做自适应式的调整。 ( 4 ) 高性能价格比：性能优势是p 2 p 被广泛关注的一个重要原因。随着硬 件技术的发展，个人计算机的计算和存储能力以及网络带宽等性能依照摩尔定理 高速增长。采用p 2 p 架构可以有效地利用互联网中散布的大量普通结点，将计算 任务或存储资料分布到所有结点上。利用其中闲置的计算能力或存储空间，达到 高性能计算和海量存储的目的。通过利用网络中的大量空闲资源，可以用更低的 成本提供更高的计算和存储能力。 ( 5 ) 隐私保护：在p 2 p 网络中，由于信息的传输分散在各节点之间进行而无 需经过某个集中环节，用户的隐私信息被窃听和泄漏的可能性大大缩小。此外， 目前解决i n t e r n e t 隐私问题主要采用中继转发的技术方法，从而将通信的参与者 隐藏在众多的网络实体之中。在传统的一些匿名通信系统中，实现这一机制依赖 于某些中继服务器节点。而在p 2 p 中，所有参与者都可以提供中继转发的功能， 因而大大提高了匿名通讯的灵活性和可靠性，能够为用户提供更好的隐私保护。 ( 6 ) 负载均衡：p 2 p 网络环境下由于每个节点既是服务器又是客户机，减少 了对传统c s 结构服务器计算能力、存储能力的要求，同时因为资源分布在多个 节点，更好的实现了整个网络的负载均衡。 当前的p 2 p 应用可以分为以下几个方面： ( 1 ) 文件共享。 与基于c s 模式的文件共享相比，p 2 p 文件共享不需要中央服务器的控制和 管理，因此有更好的可扩展性，更高的灵活性，更大的冗余。n a p s t e r l l j ，g n u t e l l a l 6 j ， e d o n k e y 7 】和b i t t o r r e n t 8 】是其中著名的代表。 ( 2 ) 对等计算 基于p 2 p 对等计算技术，可以把网络中数以万计的计算机连接起来，使他们 一起承担计算任务，就像一台超级计算机一样。其中著名的例子s e t i h o m e 【9 1 是一项利用全球互联网计算机共同搜寻地外文明的科学实验计划。用户可以通过 运行一个免费程序下载并分析从射电望远镜传来的数据来加入这个项目。该项目 是1 9 9 5 年被提出，并从19 9 9 年5 月开始运行。 ( 3 ) 即时通信 这个之所以单列出来是因为这个领域太普遍地为互联网用户熟悉并应用。其 一2 一 l _ r t l ， 东北大学硕士学位论文第一章绪论 中著名的例子有i c q ，q q ，m s nm a s s a g e r 和雅虎通等。这些应用软件使全球的 互联网用户更方便地沟通和交流。 ( 4 ) 协同工作 协同工作是指多用户之间利用网络中的协同计算平台互相协同来共同完成计 算任务，共享信息资源等。通过采用p 2 p 技术，个人和组织可以随时采用多种方 式建立在线、非在线的协同应用环境。协同应用一般包括：即时通信、聊天室、 文件共享、语音通讯等基本功能，除了这些基本功能，用户之间还可以共享白板、 协同写作、视频会议等。另外，协同有时候还包括工程人员的协作开发软件。例 如，j b u i l d e r 2 0 0 6j a v a 集成开发环境就增加了p 2 p 协同开发的属性。采用p 2 p 技 术使协同工作不再需要中心服务器，参与协同工作的计算机可以点对点建立连接。 g r o o v e 就是基于p 2 p 的协同软件平台，已经被微软公司收购。 ( 5 ) 搜索技术 p 2 p 搜索技术使用户能够深度搜索文档。而且这种搜索无需通过w e b 服务器， 也可以不受信息文档格式和宿主设备的限制，可达到传统目录式搜索引擎无可比 拟的深度。目前，集中式搜索引擎g o o g l e 、y a h o o 、b a i d u 是人们在网络中检索信 息资源的主要工具，但这种集中式的搜索引擎远远无法涵盖所有互联网内的共享 内容，而p 2 p 搜索技术正好是这种集中式检索的一种良性互补。 简单描述这个过程：每个节点在加入网络的时候，会对存储在本节点上的内 容进行索引，以满足本地内容检索的目的。然后按某种预定的规则选择一些节点 作为自己的邻居，加入到p 2 p 网络当中去。发起者p 提出检索请求q ，并将q 发送 给自己的邻居，p 的邻居收到q 后，检查本身是否存在查询的信息，如果不存在， 转发查询，直到返回结果。 由于p 2 p 网络中节点可以动态地加入和离开，而且没有全局管理机制，这样 带来的灵活性导致了p 2 p 系统的复杂性和不稳定性。因此现有的大多用于分布式 系统的技术无法适用于p 2 p 网络系统，从而为p 2 p 的研究带来诸多问题和挑战。 针对有关挑战，当前关于p 2 p 技术的研究主要集中在p 2 p 网络模型，查找问题， 资源管理等方面。 ( 1 ) 网络模型 p 2 p 网络模型的选择和确立是p 2 p 系统构建的核心。当前p 2 p 网络模型可分 为集中式目录模型，非结构化网络模型，结构化网络模型和混合型网络模型。这 些模型有各自的优点和缺点，因而有不同的使用条件和范围。对p 2 p 网络模型的 研究是明确当时的条件和特点，选择或建立合适的网络模型，并在此基础上设计 相应的p e e r 和数据操作的方法。 ( 2 ) 查找问题 一3 一 东北大学硕士学位论文 第一章绪论 查找是p 2 p 系统的首要任务和基本功能，是每个p 2 p 系统都要面临和解决的 问题，因而查找技术的优劣在某种意义上决定了p 2 p 网络的性能。查找的目的是 为了提供用户所需要的资源；在查找的过程中，需要考虑并解决以下问题：网络 的拓扑结构，资源的定位，数据的放置以及消息的路由等问题。 ( 3 ) 资源管理 由于p 2 p 网络结构的动态性和复杂性，即p e e r 可以自由地加入和离开，对 p e e r 以及p e e r 上数据的知识的获得是具有挑战的。不同的p 2 p 网络中有不同的解 决方案，它们的目的都是对这些动态变化的p e e r 节点进行有效的管理。 1 2p 2 p 网络模型 p 2 p 的查找技术，路由机制等都是基于某个特定的p 2 p 网络模型中，只有确 定一个p 2 p 网络模型，才能展开相应的技术研究与探讨。可以说p 2 p 的网络模型 是构建p 2 p 网络的核心和基础。当前诸多的p 2 p 网络模型可以分为四类：集中式 目录模型，非结构化网络模型，结构化网络模型和混合型网络模型。 1 2 1 集中目录式模型 这类模型中的著名的例子是n a p s t e r 。它是一款共享网络中音乐r a p 3 的软 件，它使当时互联网上数以百万计的计算机之间可以共享和交流音乐，在给人们 带来极大震撼和愉悦的同时，把人们的视线吸引到了p 2 p 技术上来。 我们以图1 1 所示的n a p s t e r 为例说明集中式目录模型。它由客户端和服务器 端组成( 这个服务器不同于c s 中的服务器，后者提供资源的下载) ，注册用户在 客户端登陆，而服务器主要存放： ( 1 ) 所有网络上文件的元数据( 文件名，产生的时间等) 的索引； ( 2 ) 注册用户的连接信息表( i p 地址，连接速度等) ； ( 3 ) 文件列表包含每个用户拥有和在网络上共享的文件。 当客户端启动并连接到服务器时，客户端共享的文件列表传送到服务器。当 客户端发出查询请求时，服务器在索引目录中查询匹配的文件，返回拥有该文件 的用户列表，然后用户和拥有这个文件的实体建立直接的连接，从而下载文件。 集中目录模型的优点和缺点都很明显，都是源于目录索引在服务器上的集中 存放。优点是文件查找方便快捷，不需要通过路由，索引维护简单，资源发现效 率高，并支持多关键字查询。缺点是中央服务器容易崩溃，从而造成整个网络的 失效，可靠性和安全性较低；另外，网络的可扩展性受到中央服务器性能的限制。 由以上分析可知，对于相对规模不大的p 2 p 网络，这种集中目录式模型在管理和 一4 一 、 r ； ， 东北大学硕士学位论文第一章绪论 维护上有优势，但是对于规模不可控制的大型网络则不适用。 客户端 图1 1n a p s t e r 网络模型 f i g 1 1n a p s t e rn e t w o r km o d e l 1 2 2 非结构化网络模型 。 非结构化网络模型把资源定位信息分布到各个p e e r 上，而不像集中目录网络 模型那样用一台中央服务器存储用户共享文件索引信息的中央服务器。非结构化 网络模型是种纯粹的p 2 p 组织方式，它从根本上取消了中央服务器，采用随机图 的组织方式，即网络中p e e r 之间的连接是随机的，网络中共享资源的存储位置和 整个网络的拓扑结构之间没有任何关系。每个用户动态地加入网络，并与自己相 邻的一组邻居构成一个逻辑覆盖网络。p e e r 间的查询通过相邻p e e r 广播传递；为 了防止产生搜索环路，每个p e e r 记录自己的搜索路径。 图1 2 所示的g n u t e l l a l 6 , i o j 是这类网络模型的代表。在g n u t e l l a 网络模型中， 所有文件存放的信息分布在网络中的各个p e e r 上，当前p e e r 查询文件时，通过 在网络中有限泛洪，和拥有该文件的p e e r 建立连接并下载文件。 g n u t e l l a 网络用t t l 限制p i n g 和q u e r y 的消息广播：当消息的t t l 为0 时，该消息被放弃。每个消息在g n u t e l l a 网络中有唯一的i d ，从而避免了重复消 息的产生。这样在某种程度上提高了网络的查询效率，降低了对网络带宽的消耗。 与集中目录式模型相比，非结构化网络模型很好地解决了在网络规模增大，资源 增多时的扩展性不强的问题；但是泛洪的方式在网络中产生大量的冗余流量，从 而消耗了大量的网络资源。 一5 一 第一章绪论 1 2 3 结构化网络模型 图1 2g n u t e l l a 网络模型 f i g 1 2g n u t e l l an e t w o r k m o d e l 结构化p 2 p 网络模型有固定的网络拓扑结构和严格的数据存放规则，能够实 现高效的查找和路由。由于结构化网络中数据是按照严格的规则存放的，在p e e r 动态地加入和离开网络时，网络拓扑结构的维护需要较大的代价，其健壮性和可 用性受到一定影响。根据索引的建立基础可以把结构化p 2 p 网络模型分成三类： 基于分布式哈希表的网络，基于跳数列表的网络和基于树的网络。 1 2 3 1 基于分布式哈希表的网络 基于分布式哈希表( d h t ) 1 l 】的系统用分布式哈希表索引数据，其优点是很 好地支持精确匹配查询，而且分布式哈希表可以给每个p e e r 等值地分配负载。在 这类系统中，著名的例子有c h o r d d 2 】( 环结构) ，c a n t l 3 】( 多维网格结构) ， t a p e s t r y t l 4 】和p a s t r y t 5 】( 二者都使用p l a x t o nm e s h t l 6 】) 。因为分布式哈希表的本质 破坏了数据的在某一维度的内在顺序，所以它们在某种意义上说是不支持范围查 询的，或者说范围查询的性能很差。需要补充的是，有些基于分布式哈希表的系 统的变种可以支持范围查询：采用本地敏感哈希，把相似的范围尽可能地哈希到 相同的p e e r ，这种方法提供只能提供近似解；通过缓存1 7 , 1 5 , 1 9 1 范围( 把范围加入 到哈希函数中) ，它虽然支持精确匹配查询，但是效率不高；文献【2 0 】在既能支持 范围查询的又能支持精确匹配查询( 通过本地保存哈希) ，它的缺点是在数据倾斜 时，负载也发生倾斜。 现以c h o r d 为例说明基于d h t 的网络。c h o r d 中每个节点都维护了与其后 一6 一 一 、 ， ， 东北大学硕士学位论文第一章绪论 继节点的邻居关系，在环上沿后继节点总可以正确地到达任何目标节点，但这种 方法效率很低。因此c h o r d 中每个节点都维护一个f i n g e r 表( 即路由表) ，f i n g e r 表 至多有m 项，节点n 的f i n g e r 表第i 项是值为n + 2 卜1 的节点在c h o r d 环上的后继 节点。资源查找时，每个节点都通过查询f i n g e r 表，将查找请求转发到离k e y 最 近的节点上。 c h o r d 方法的节点度数为o ( 1 0 9 2 n ) ，路由延迟和路由消息开销是o ( 1 0 9 2 n ) ， 平均路由延迟为1 2l 0 9 2 n ，动态维护开销为o ( 1 0 9 2 2 n ) ，具有良好的特性。 1 2 - 3 2 基于跳数列表的网络 这类系统是基于跳数列表( s k i p 1 i s t ) 结构的，它们把数据划分到某个维度上 的值确定的范围中，可以很好地支持精确匹配查询和范围查询。著名的例子有s k i p g r a p h i 2 1j 和s k i pn e t z z l 。 s k i pg r a p h 和s k i pn e t 是两个基于s k i p 1 i s t 的结构化p 2 p 系统。它们将节点 和资源对象按照其标识的字典序组织成类似s k i p 1 i s t 的多层双向链表，每个节点 在各层都选择双向链表中相邻位置的两个节点作为邻居。与c h o r d 类似，它们的 节点度数均为o ( 1 0 9 n ) ，区间搜索延迟为o ( 1 0 9 n + n ) 。s k i pg r a p h 和s k i pn e t 没有 采用一般d h t 方法常用的随机哈希算法，而是使用节点或资源对象相关的字符 串或数值来命名，可以通过双链表中的顺序搜索来支持单属性区间搜索，但都不 支持多属性区间搜索。b r u s h w o o d 2 3 j 基于s k i pg r a p h 提供了多属性区间搜索能力。 但b r u s h w o o d 中节点的命名以及动态维护机制与具体的搜索空间和应用紧密相 关，不是通用架构的d h t 区间搜索技术。s c r a p 2 4 】是基于s k i pg r a p h 的通用架 构d h t 区间搜索技术，通过s f c 技术提供了多属性区间搜索能力，但其区间搜 索延迟也是o ( 1 0 9 n + n ) 。 1 2 3 3 基于树的网络 在基于树的p 2 p 网络中，p e e r 上存储的数据用树来索引。这种思路和做法源 于集中式数据库中用b + 树建立索引，用类似这样的索引可以支持精确查询和高效 的范围查询。在集中式环境中，索引的维护代价相对低，只是到了分布式环境中 情形有所不同：在p 2 p 网络中随着p e e r 的加入和离开，维护索引要付出额外的通 信代价，这样人们在把b + 树索引的方法移植到p 2 p 环境中就得反复思量。 ( 1 ) p g r i d p - g r i d l 2 5 】是基于虚拟二叉树拓扑的d h t 方法。p g r i d 中节点标识由节点在虚 拟二叉树中的位置确定，每个节点的路由表中维护了二叉树同一层中的部分节点， 它们的标识中的某一位值正好与本节点互补。p g r i d 的各节点度数分布不均匀， 节点度数介于常量和o ( 1 0 9 n ) 之间。p g r i d 采用基于前缀的路由，平均路由延迟 一7 一 学位论文 第一章绪论 开销为o ( 1 0 9 n ) ，但在某些情况下可达o f n ) 。p - g r i d 中二叉树高层节 低层节点要高得多，负载不平衡现象较突出。 树 p 树【2 6 】是一种分布式，容错性的p 2 p 结构。它既能支持精确查询，又能支持 范围查询。它是一种高度分布的，容错性的，并可扩展的索引结构。其本质是在 每个节点上存储一个半独立的b + 树。最大的值包在最低的值的外面。在基于这种 索引结构的网络中，每个节点( 或者说p e e r ) 把待查询的键的值视为一个有组织 的环。p 树是在c h o r d 覆盖网络上采用b + 树结构，而维护b + 树需要较大的开销。 ( 3 ) b a t o n 及其改进 b a t o n 2 7 】是一个在p 2 p 网络中的平衡二叉树结构覆盖( 如图1 3 ) ，它能有 效地支持精确查询和范围查询。b a t o n 中的平衡二叉树如图所示，它由节点组 成，每个节点有自身的连接和属性。从节点a 开始，l e v e l = 0 ，下面的依次是 l e v e l - - 1 ，l e v e l = 2 ，l e v e l = 3 ，l e v e l = 4 。表1 1 以节点m 为例，说明节点的属性、连接和 左右路由表。对m 来说，l e v e l = 3 ，在这层上，从左至右m 是第六个节点，所以 n u m b e r = 6 。其父亲和左右孩子显而易见。左紧邻( 1 e f ta d j a c e n t ) 和右紧邻( r i g h t a d j a c e n t ) 是先序遍历中节点m 的前驱节点和后继节点。左( 右) 路由表存放与 m 同一层，并且比m 的n u m b e r 少( 多) 2 k 的节点的i d ( k 是整数) ，图中虚线表 示路由连接。u p p e rb o u n d 和l o w e rb o u n d 是节点存放数据值的上界和下界。 图1 3b a t o n 的平衡二叉树 f i g 1 3b a l a n c e db i n a r yt r e eo fb a t o n 一8 一 ， ， 东北大学硕士学位论文第一章绪论 表1 1 节点m 的属性、连接和路由表 t a b l e1 1a t t r i b u t e s 。l i n k sa n dr o u t i n gt a b l e so fn o d em ( a ) 节点m 的属性和连接 m 的属性或连接值 l e v e l3 n u m b e r6 p a r e n t f l e f tc h i l dn u l l r i g h tc h i l d r l e f ta d ja c e n t f r i g h ta d j a c e n t r ( b ) m 的左路由表 n o d el e f tc h i l d r i g h tc h i l d l o w e rb o u n d u p p e rb o u n d 0ln u l ln u l l 1 1 0 w e r l u p p 盯 1k pqk l o w e f k u p p e r 2 3 in u l ln u l l l l o w e r l u p p e r ( c ) m 的右路由表 n o d el e f tc h i l d r i g h tc h i l d l o w e rb o u n d u p p e rb o u n d 0nn u l ln u l l n l o w c r n u p p = r lost o l o w e r o u p p e r b a t o n 能够自适应数据倾斜情况，并且其平衡二叉树的本质决定其高度上 是平衡的，并可以支持精确查询和范围查询。b a t o n 中p e e r 的加入和离开，以 及更新路由表都是以o ( 1 0 9 2 n ) 为代价。由于b a t o n 维护了垂直和水平路由信 息，查询效率较高，且容错性也很好( 即使大量节点失效时也可以保持网络连接) 。 v b i 树【2 8 】是b a t o n 的改进，其结构如图1 4 所示。它可以支持多维索引， 点查询和范围查询都以o ( 1 0 9 2 n ) 跳数为代价。它采用了负载平衡机制，可以适应 数据和负载分布。v b i 树上的节点分为数据节点( 叶节点) 和路由节点( 内节点) 。 前者在图中用灰色标记，用斜体( h ) 代表h ；后者用白色标记。与b a t o n 情形 相同，每个路由节点维护父亲，孩子和紧邻节点的连接，以及两侧路由表。不同 的是，对每个路由节点：( 1 ) 两侧路由表不需要维护邻居节点的上界和下届；( 2 ) 存储一个上行表，该表存储它的所有祖先；( 3 ) 存储以它的孩子为根的子树的高 一9 一 东北大学硕士学位论文第一章绪论 度。表1 2 和表1 3 分别是路由节点m 和数据节点m 的属性、连接和左右路由表。 图1 4v b i 树结构 f i g 1 4s t r u c t u r eo f v b i - t r e e 由于v b i 树采用虚拟树，就是保持相应的接口，可以适用多种实现，如v b i m 树，v b i r 树，v b i s s 树。在多维空间中的r 树和m 树可以映射到v b i 树上。 其中的点查询和范围查询( 也可以k n n 查询) 也在多维空间中进行。它的负载平 衡中用到网络重构( 也是树的重构) ，也就是树的l l ，l r ，r l ，r r 旋转( 类似 a v l 树的旋转) 。 表1 2 路由节点m 的属性、连接和路由表 t a b l e1 2a t t r i b u t e s ，l i n k sa n dr o u t i n gt a b l e so fr o u t i n gn o d em ( a ) 节点m 的属性和连接 m 的属性或连接值 l e v e l3 n u m b e r 6 p a r e n t f l e f tc h i l dn u l l r i g h tc h i l d r l e f ta d j a c e n tm r i g h ta d j a c e n t r u p s i d ep a t hc r c c f a c r l e f tc h i l dh e i g h tl r i g h tc h i l dh e i g h t 2 一l o 、 ， ， 东北大学硕士学位论文 ( b ) m 的左路由表 第一章绪论 n o d el e f tc h i l d r i g h tc h i l d 0ll f 1k pq 2 3 li b