（计算机应用技术专业论文）dmfarch：分布式高维数据管理技术研究.pdf

东北大学硕士学位论文 摘要 d m f a r c h ：分布式高维数据管理技术研究 摘要 随着i n t e r n e t 技术的飞速发展，分布式存储技术取得了长足的进步。同时，目 益增加的用户和数据，也给分布式存储技术带来了新的挑战。另一方面，随着p 2 p 计算模式的兴起、网络带宽的大幅增加和i n t e r n e t 端系统计算能力的迅速增强，原 先被忽视的端用户设备成为一种宝贵的资源。如何充分利用这些端用户设备，在动 态的p 2 p 网络环境中构建大规模、高可扩展、高可靠、高性能的分布式存储系统， 是近年来研究的热点之一。 网络技术的飞速发展与迅速普及使其在现代社会中的重要性越来越突出，对 数据共享的要求也越来越高。目前的分布式p 2 p 系统为我们在数据共享与发布等 方面提供了便捷、高效的方法，因此为了能够提高查询效率，需要找到一种更适 合分布式系统的分布式空间索引结构。另外高维对象的逻辑结构等自身特性使得 对多维数据对象的查询变得更加复杂化，导致了目前现存的空间索引结构大多不 适于分布式数据共享系统。 因此为了提高分布式系统的查询效率，本文提出了一种基于高维的更适用于 分布式p 2 p 环境的高维数据管理技术一一d m f a r c h 。这种新型的高维数据管理技 术首先将整个待查询的数据空间进行层次划分。各个节点通过一个分布式索引结 构( i p ) 对自己周围邻近的信息进行管理，并且采用分布式b l o o m f i l t e r ( d b f ) 技术对待查区域进行有效的过滤。当某一节点查询请求时，首先进行本地搜索， 如果未返回查询结果则根据d b f 所提供的信息将该查询向上发送到其父亲节点。 实验表明本文提出的通过层次划分对高维数据进行过滤来解决高维问题的思 想在查询效率等方面都优于其他的索引形式。从实验结论中可以看出这种过滤代 价几乎可以忽略不计，能够有效地提高索引的查询性能，对于解决高维问题是非 常有效的，通过与m r t r e e 的实验对比也可以看出d m f a r c h 无论在查询效率还 是在查询返回点个数等方面都优于其他的集中式索引形式。 关键词对等计算；分布式存储；p 2 p ；高维索引；路由算法：范围查询 i i 东北大学硕士学位论文 a b s t r a c t t h ed m f a r c h ：ad i s t r i b u t e d m u l t i d i m e t i o n a ld a t am a n a g e m e n t f r a m e w o r k 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 m e tt e c h n o l o g y , t h ei n c r e a s i n gu s e ra n d m a s s i v ed a t ab r i n gt h en e wc h a l l e n g ef o rt h ed i s t r i b u t e ds t o r a g et e c h n o l o g y o nt h e o t h e rh a n d ，w i t ht h ed e v e l o p m e n to fp e e r - t o p e e r ( p 2 p ) c o m p u t i n gp a r a d i g m ，n e t w o r k b a n d w i d t ha n dt h ec a p a c i t yo fi n t e r n e t b a s e de n d s y s t e m s ，t h ee n d - s y s t e m si g n o r e di n t h e p a s tb e c o m ev a l u a b l ec o m p u t i n gr e s o u r c e s h o wt o u t i l i z et h ee n d s y s t e m s r e s o u r c e st ob u i l dad i s t r i b u t e ds t o r a g es y s t e mw i t h l a r g e - s c a l e ，h i g hs c a l a b i l i t y , r e l i a b i l i t ya n dp e r f o r m a n c eb e c o m e s o n eo fi m p o r t a n tt h i n g s n e t w o r kh a sb e c o m em o r ea n dm o r ei m p o r t a n ti nm o d e ms o c i e t yw i t hi t sr a p i d d e v e l o p m e n ta n dp o p u l a r i z a t i o n ，a n di s s t i l lg e t t i n gl a r g e ra n dl a r g e r w i t hl o t so f w i d e l yd i f f e r e n ta p p l i c a t i o n s ，w en e e dh i g h e rd e m a n d sf o rt h es h a r eo f d a t a i no r d e rt o i m p r o v et h ee f f i c i e n c yo fs e a r c h ，w ea r eu r g e dt of i n da na p p r o p r i a t ei n d e x ，w h i c h m a k e st h es e a r e ho nd a t ao b j e c t so fm u l t i d i m e n s i o n a is p a c em o r ec o m p l i c a t e d t h i s r e s u l t si nt h a tt h ep r e s e n ts p a t i a li n d e xs t m c m r e sa r en o tm a t c hw i t ht h es y s t e mo fp 2 p d a t as h a r i n g h e n c e ，i no r d e rt oi m p r o v et h ee f f c i e n c yo fs e a r c hi np 2 ps y s t e m s ，i nt h ep a p e r w ed e s i g na na p p r o p r i a t ed i s t r i b u t e dd a t am a n a g e m e n tf r a m e w o r km a k e st h es e a r c ho n d a t ao b j e c t so fm u l t i d i m e n s i o n a ls p a c em o r ec o m p l i c a t e d ，c a l l e da st h ed m f - a r c h i ti s h i e r a r c h i c a lp a r t i t i o n so nd a t as p a c ew h i c hw i l lb es e a r c h e d p e e r sc o u l ds e n dm e s s a g e t oe a c ho t h e ra c c o r d i n gt oi n d e xp a r t i t i o na n dw h e nan o d ew a n t st ok n o wi ft h e r ea r e a n yr e s u l t si ni t sr e g i o n ，t h ed i s t r i b u t e db l o o m f i l t e r ( d b f ) w i l lb eu s e di nt h e d m f a r c h an o d es e n d saq u e r yr e q u e s tt oi t sd i r e c tp a r e n ta n dt h e nr e t u r n st h er e s u l t s o rf o r w a r d st h er e q u e s tt ot h eu p p e rl e v e l o u rr e s u l t ss h o wt h ee f f i c a c yo fo u ra p p r o a c h t h i st h e s i sp u t sf o r w a r dat h o u g h t o fr e d u c i n gd a t ab yh i e r a r c h i c a lp a r t i t i o n so nd a t as p a c et os o l v et h eh i g hd i m e n s i o n a l r e t r i e v a lp r o b l e m ，w h i c hi sb a s e do nc o m p a r i s i o na n da n a l y s i so ft h ee x i s t i n gm e t h o d s i i i 查些查兰翌主兰竺笙圭一型塑翌坠竖二 e x p e r i m e n t a r e s u l t si n d i c a t et h a tt h ef i l t e r i n g c o s tc a na l m o s tb ei g x a o r e d i tc a n i m p r o v et h er e t r i e v a lp e r f o r m a n c eg r e a t l y s oi ti sa ne f f i c i e n ta p p r o a c h t os o l v i n gt h e h i g hd i m e n s i o t t a lr e t r i e v a lp r o b l e m u s i n ge x p e r i m e n t a lc o m p a r i s o n ，w ei l l u s t r a t et h a t t h ed m f a r c hi sn e a r l y o p t i m a la n ds i g n i f i c a n t l yo u t p e r f o r m so t h e ri n d e xs t r u c t u r ea s m c r t r e e k e y w o r d s ：p e e r t o p e e rc o m p u t i n g ；d i s t r i b u t e ds t o r a g e ；p 2 p ；h i g hd i m e n s i o n a li n d e x ； r o u t i n ga l g o r i t h m ；r a n g eq u e r y i v 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取 得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或 撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确 的说明并表示谢意。 学位论文作者签名：毫铲舨岛 日期：l 坤、2 弓 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学 位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅。本人授权东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： 东北大学硕士学位论文第一章引言 第一章引言 网络技术的飞速发展与迅速普及使其成为数据通信的重要手段，出现了越来 越多的基于i t 的应用，它们在社会经济、科学研究、工业领域中扮演着关键的角 色。其中电子商务、网络游戏、消息传递、远程 办作等等分布式应用既要求分布 式计算模式，同时又要保证各参与节点的自治性。另外些应用【1 1 ，如基因分析、 天气预报与气候预测、太空探索等需要超强的计算能力来处理海量的数据。网络 规模越来越大，连入网络中的设备阻及计算单元的数量和种类也越来越多，连入 网络中的设备以及计算单元的数量和种类也越来越多，然而这些设备以及计算单 元并没有得到充分的利用，如果能够将这些设备以及计算单元的处理器的计算能 力、磁盘存储能力以及网络带宽资源等进行充分利用将会有效缓解目前互联网所 面临得一些问题。所以现在人们越来越关注网络资源共享的方式和在不同共享方 式下查找资源的方法。 1 1 背景 p e e r - t o p e e r 网络系统( 以下简称p 2 p 系统或者是p 2 p 网络) 的出现为分布式 计算技术甚至为整个互联网的发展提供了新的契机，是目前比较流行的网络资源 共享网络。通过p 2 p 系统，使p c 拥有者可以直接通过互联网进行通信而脱离任 何服务器的控制。p 2 p 系统将带来一个资源共享、按需分配、完全互动的新的互 联网。但是现有的系统不能达到这些目标，大多数的p 2 p 系统要求有中心服务器， 如n a p s t e r ，这使得中心服务器有可能成为网络的瓶颈，并且一旦中心服务器瘫痪， 整个系统就无法运作了。而另一些无中心服务器需求的p 2 p 系统对网络带宽要求 很高，如g n u t e l l a ，在拨号上网的网络中根本无法工作。这种p 2 p 系统的查询代 价高，响应速度慢。造成这种现象的原因就是它没有一个内在的索引结构，查询 请求是在网络中进行广播。 国外开展p 2 p 技术研究的组织和机构主要包括大学、国际学术团体和i t 公 司。大学的研究工作侧重于p 2 p 理论研究，高新技术公司侧重于p 2 p 技术的应 用开发和产品化，而国际学术团体则主要涉及p 2 p 的标准化阀题。 国外开展p 2 p 研究较为著名的大学和科研机构主要包括u cb e r k e l e v 、m i t 东北大学硕士学位论文 第一章引言 和a t t 互联网研究中心( a c i r i ) 。在u c b e r k e l e y 大学，t a p e s t r y 2 1 项目和 o c e a n s t o r e 项目1 3 与p 2 p 技术直接相关。 l h p e s t r y 提供了一个分布式容错查找和 路由基础平台，在此平台基础之上，可以开发各神p 2 p 应用( o c e a n s t o r e 即是此平 台上的一个应用) 。t a p e s t r y 基于p l a x t i o n 的思想，加入了容错机制，从而可适 应p 2 p 的动态变化的特点。o c e a n s t o r e 是以x a p e s t r y 为路由和查找基础设施的 p 2 p 平台。它是一个适合于全球数据存储的p 2 p 应用系统。任何用户均可以加入 o c e a n s t o r e 系统，或者共享自己的存储空间，或者使用该系统中的资源。通过使 用复制和缓存技术，o c e a n s t o r e 可提高查找的效率。 1 2 计算模式的演变 人们通常将计算机俗称为“电脑”，这蕴涵了人们的一种期望，那就是希望有 一天，计算机也能够像人一样自己独立的进行工作。在现实生活中，正常的成年 入应当能够独立地承担某项工作，为社会提供服务，同时获得收入，享受他人的 服务。在这个过程中，他要同其他个体进行协调、合作。在未来的计算机世界里， 各个计算机也应当同时是服务提供者和消费者，在完成各自任务的时候，需要同 其他计算机进行协调、合作。我们知道，人不是生来就具备这种能力。在人的婴 幼) l d i t 期，几乎不能独自完成有意义的工作，这时，他们是完全依赖于家长的； 在青少年时期，他们具备了一定工作能力，但是还不能独当一面，主要还是在家 长的指导下工作、学习，真正意义上的工作还是由家长完成；等到成年后，他们 就具备完全的工作能力，享有完全的行为权利和义务。在计算机网络世界里，计 算模式的演变也经历了类似的三个阶段。 1 2 1 主从式计算模式 系统构成以大型主机和哑终端为特征i 从计算机网络的诞生到上个世纪8 0 年代，计算机是一种昂贵的奢侈品，但他们的功能相对较弱，这是采用主从式模 型的客观条件。这时的哑终端是完全依赖于大型主机的，就像婴幼儿完全依赖于 父母一样。但是随着网络技术的发展，网络的传输速度的目益加快，网络用户的 急剧增长，这种集中式服务器模式对文件交换的不便之处，以及过分依赖中央服 务器，造成对高性能计算机的要求越来越大，网络的更大规模的应用收到了极大 的限制。 2 东北走擘项士学位论文 第一章； 言 1 2 2 客户机，月务器模式 存这种模式中，系统分成两大部分- _ 一服务器和客户机，其基本工作方式是 客户机发出请求，服务器接受请求后，进行分析处理，然后将处理结果返回给客 户机。从上世纪9 0 年代开始，客户机，月日务器模式开始流行，目前这种计算模式 已经是市场上的主流。谚模式包括客户机，文件服务器、两层c s 、多层c s 以及 浏览器服务器( b i g ) 等几种类别。在该模式中，客户机具备一定的计算能力， 但主要工作还是依赖于服务器柬完成。 在客户机月r 务器模式下，进行资源查找很简单，只要客户端知道存放共享资 源的服务器的i p 地址或者是域名，就可以在i n t e r a c t 上实现资源共享。不同的客 户可以使用不同服务器上的资源。在客户机朋务器模式中进行资源查找一般都是 由客户端进行初始化，发送建立连接请求，根据应用特点建立t c p 或者u d p 的 连接，连接建立之后，客户选择应用层提供不同的应用服务，发出请求信息然 后进行数据的传送和处理。 要构建客户机，月r 务器模式需要性能较好的服务器，服务器的性能越好，其价 格越贵，使得构建网络的代价昂贵。整个网络上由于有单个服务器容易出现单点 失效，而且随着客户的不断增加，服务器性能也需要不断的扩展，扩展代价是很 高的。另外服务器的i p 地址或者域名对客户而言都是已知的，这样给服务器带来 了很多不安金的因索，为了保证安全需要对服务器进行专用的维护。对于不同衲 应用还需要服务器和客户端运行不同的软件。 在9 0 年代，客户朋务器计算体系流行到了极点，因为它打破了世界上一些 数据提供者的垄断。同时，它也鼓励资源共享并为它的用户提供不同的防火墙。 但是1 9 9 9 年n a p s t e r 对c s 体系提出了挑战。 “资源在哪里创建，就在哪里访问”的愿望促进了因特网进入第- - 4 、发展阶 段一一分布式网络计算。删络计算正处于发展阶段，人们对它的定义还没有形成 共识，但一个相对可以接受的理解是：“网络计算”是把网络连接起来的各种自治 资源和系统组合起来，以实现资源共享、协同工作和联台计算，为各种用户通过 基于网络的各类综合性服务。基于此，人们把企业计算、网络计算、对等计算和 普及计算均归类到网络计算。它们各自的重点又各不相同，目前有人认为企业计 算是以中间件为核心：网络计算强调让计算能力“公用化”；对等计算则倡导平等 共享：普及计算要求计算无所不在。 j 上享；普及计算要求计算无所不在。 - 3 东北大学硕士学位论更第一章引言 正因为因特网的这神转变导致了对等计算的流行。 1 2 3 对等计算模式 在上述的经典的客户机服务器计算模式中，客户机作为服务消费者，是不提 供任何服务的；而服务器则只是被动的响应客户机的请求，从不要求客户机进行 协助。这种模式存在许多不足： ( 1 ) 性能：服务器是性能瓶颈，客户机的性能不能得到利用； ( 2 ) 可伸缩性差：服务器的资源水平决定了系统的最大工作负载，而服务器 的资源水平很难有效伸缩； ( 3 ) 容错性差：服务器是单点故障点； ( 4 ) 缺乏灵活性：用于客户机和服务器通信的协议是硬编码的。客户和服务 器之间的角色分配在设计时就已经决定系统的功能很难扩展和升级； 要知道，随着技术的飞速发展，现在充当客户机的计算机的性能已经达到甚 至超过了早期的大型主机。也就是说，它们不再是“小孩”了，像正常的成年人 一样，它们可以也应当独当一面，不但可以请求其他机器的服务，也必须提侠自 己的服务。这就是最新的对等计算模式。 所谓对等计算我们可以将它简单的看成是个将计算机串联的行为，将网络 上c p u 资源的共享。通过对等计算我们可以将存在于网络之中很多的计算机间接 的联系在一起，使它们发挥出只有超级计算机才具有的巨大能量。这样我们在任 何需要大量数据处理的行业都可从对等计算中获利，如天气预报、动画制作、基 因组的研究等，有了对等计算之后，就不再需要昂贵的超级计算机了。 对等计算是网络计算的一种，具有如下几个特征： ( 1 ) 作为分布式计算模型的一种，他的每个节点与其他节点一样都拥有相同 的能力。 ( 2 ) 每个对等点既是客户端又是服务器端。 ( 3 ) 网络上每个节点是其他任一节点的对等节点，并且能够与它的对等节点 建立通信会话喝共享信息。 ( 4 ) 网路拓扑是动态可变的。 1 3 对等网络概述 对等网络( p e e r t o p e e rn e t w o r k ，p 2 pn e t w o r k ) 为大家所熟悉，得益于一个 4 东北大学硕士学位论文 第一章引言 叫n a p s t e r 【4 】的文件共享系统的成功运行，该系统主要用于m p 3 音乐文件的交换。 然而，对等网络不仅仅用于文件共享，它还可以用于协同合作、边界服务、分布 式计算嘶】、分布式代理【7 】和主动网络 8 1 等等领域。许多重要的研究领域，比如聚 集计算蚰( c l u s t e rc o m p u t i n g ) 、网格计算( g r i dc o m p u t i n g ) 也可以借鉴对等 网络中的思想。 那么，什么是对等网络，它的核心主题是什么? 对等网络并不是新概念，早在上个世纪七十年代中期，很流行的l a n 文件 共享以及多媒体游戏就建立在p 2 p 的模型之上。上个世纪9 0 年代，s s i m o n “l ”，k y o u n g f l 2 1 就提出和研究了对等网络这种体系结构。s w r a y 等将对等网络定义为 由网络连接起来的异质分布式资源的集成。也有人将其简单地定义为客户机服务 器体系的对立面。 从前面介绍的计算机网络计算模式的演变过程，我们可以发现，对等网络是 与对等计算模式紧密相关的。在本课题中，我们将对等网络定义为；对等网络是 一种分布式网络体系结构，网络中的参与者应当共享它们的部分资源( 处理器、 存储资源、网络带宽、外设、软件资源、服务等等) ，并且这些资源不需通过中介 就能被其他参与者直接访问；从而，网络的参与者既是资源( 服务和内容) 的提 供者，又是资源的消费者。 对等网络又可以细分为两种类型：“纯粹”的对等网络和“混合”的对等网络。 所谓“纯粹”的对等网络是指在对等网络中，任意一个参与者的加入和退出都不 会导致网络整体服务的损失。所谓“混合”的对等网络是指对等网络中需要一个 中心实体来保证网络服务的提供。本课题主要研究对象是“纯粹”的对等网络。 和传统客户机朋匣务器网络相比，对等网络有如下吸引人之处： ( 1 ) 整体性能高 对等网络中，没有服务器、客户机之分，可以充分利用各参与者提供的共享 资源，实现网络整体性能的最大化。 ( 2 ) 可扩展性好 在对等网络中，系统自动适应参与者的加入和退出。随着参与者的增加，网 络规模越来越大，网络中可共享的资源越来越丰富。 ( 3 ) 容错性好 当网络中参与者较多时，资源冗余成为必然，从而保证了资源的可得性和抗 5 东北大学硕士学位论文第一章引言 毁性；冗余还可以避免“单点失效”问题。对等网络中参与者具有分散性等特性， 这进一步提高了系统资源的可靠性。 ( 4 ) 信息内容更丰富 各个网络参与者都可能是信息提供者，随着网络规模扩大，信息必将越来越 丰富。当网络增长的时候，共享信息的数量和范围都将随之增长。在一个开放网 络环境下，p 2 p 网络能够很快积累相当丰富的信息。 ( 5 ) 负载均衡 对等网络环境下可以根据策略灵活分布信息。负载均衡模块可以监控各种信 息的流量和请求率，然后重新分布这些信息以减轻单个节点的负载。通过这种负 载平衡策略可以提供分布式c a c h e 可以实现的功能，但是更简单而且代价小。 6 东北大学硕士学位论文 第二章p 2 p 技术在信息共享系统中的应用 第二章p 2 p 技术在信息共享系统中的应用 在客户机朋务器结构的应用中，资源主要集中在一小部分节点上，这些节点 必须采用非常复杂的负载平衡和容错算法来提供持续可靠的服务。人们采用缓存 和复制机制来弥补这种体系结构所存在的问题，然而随着w w w 服务成为最成功 的互联网服务，网络带宽也日益成为这种服务模式的瓶颈所在。此时，n a p s t e r 、 g n u t e l l a 等p 2 p 信息共享应用程序的流行，使p 2 p 技术重新受到人们的广泛关注。 2 1p 2 p 的概念及其发展 p 2 p 的定义有很多种： ( 1 1p 2 p 是一种通信模型，其中每个参与者都具有相同的能力，任何一方都可 以发起一次通信会话。与之相对应的模型有c l i e n t s e r v e r 模型和m a s t e r s l a v e 模 型。在一些应用中，开发者使各个通信节点同时具有服务器和客户端两者的功能， 以此实现对等通信，n a p s t e r 和g n u t e l l a 都是此类的p 2 p 软件”】。 ( 2 ) c l a ys h i r k e y 给p 2 p 下了如下的定义：“p 2 p 是一种利用位于i n t e r n e t 边缘 的各种可用资源( 如存储空间、计算能力、媒体内容) 的应用。访问这些分散的 资源，就意味这要在连接不稳定和i p 地址不可预见的环境里工作，网络上大量的 节点工作在d n s 系统之外，这些分散的资源具有不稳定的连通性和未知的i p 地 址，因此p 2 p 节点不能再使用d n s 来进行访问，并且节点从中央服务器中获得 极大的自主权1 1 5 。” ( 3 ) p 2 p 是种对等网络计算技术，就是利用客户端的处理能力，实现客户端 之间的点到点通信，实现通信与服务端的无关性( 或者说客户端就是服务端) 。它 使得网络上的每个用户直接连接到其他用户的计算机上，而不是连接到服务器上。 因为消除了中间环节，p 2 p 技术似的网络上的沟通变得更容易、更直接。p 2 p 改 变了i n t e r n e t 现在以大网站为中心的状态、重返“非中心化”，并把权利交还给用 户【1 6 1 。 p 2 p 作为一项技术已应用于很多方面： ( 1 ) 共享计算能力 采用p 2 p 技术的对等计算能把网络中众多计算机暂时不用的计算能力连接起 7 东北大学硕士学位论文 第二章p 2 p 技术在信息共享系统中的应用 来，使用累积的能力执行超级计算机才能完成的任务。任何需要大量数据处理的 行业都可从对等计算中获利，如天气预报、动画制作、基因组、蛋白质合成过程 的研究等，有了对等计算之后，就无需昂贵的超级计算机了。 ( 2 1 搜索功能 无论是现在的目录式搜索引擎还是l y c o s 和国内百度的智能搜索引擎。器搜 索都要依赖服务器来完成，而利用p 2 p 技术的搜索引擎，则完全不用受服务器的 限制。当输入搜索关键字时，搜索指令便同时向多台计算机发出，然后这些计算 机再分别向另外的一些计算机发出搜索指令，如此在短时间内，搜索范围以几何 级数迅速增长。它的搜索深度和广度式现存的搜索引擎难以比拟的。 ( 3 ) 共享信息功能 n a p s t e r 就是共享信息功能的范例。此外，p 2 p 技术还可以应用于小说、图片 以及任何媒体对象的共享系统中去。传统的共享式种交换，网络时代的信息共 享使我们的财富爆炸性地增加。而p 2 p 恰恰起到了推波助澜的作用，极大地加快 了这个进程。 ( 4 ) 随时沟通、及时互动功能1 许多人一直在使用的各种即时通信系统如i c q 、q q 、a o l i n s t a n tm e s s e n g e r 、 y a h o op a g e r 、微软的m s nm e s s e n g e r 等都使最流行的p 2 p 应用。p 2 p 似的人们的 沟通得到突破性的发展。 目i j i i n t e r n e t 的存储模式是“内容位于中心”，而p 2 p 技术的运用将使i n t e r n e t 上的内容向边缘移动。这将带来以下改变：首先，客户不再需要将文件上传到服 务器，而只需要使用p 2 p 软件与其他计算机进行共享；其次，使用p 2 p 技术的计 算机不需要固定的i p 地址和永久的i n t e r n e t 连接，这使得占有极大比例的拨号上 网用户也可以从p 2 p 带来的变革中获利。从性能方面来看，在c s 模型中当过多 的用户登录来下载文件时，服务器就成了瓶颈。p 2 p 模型的优势就在于降低了对 服务器的依赖，理想中的p 2 p 模型甚至不需要服务器，因此也就不存在单点崩溃 的隐患。 2 2 基于d h t 算法的p 2 p 应用 自从n a p s t e r ，f a s t t r a c k ，g n u t c l “1 7 1 和f r e e n e t 1 8 , 1 9 1 等初级的对等网络应用 系统地成功推出，对等网络就引起了人们的广泛关注，虽然大多数人关心的是由 8 东北大学硕士学位论文 第二章p 2 p 技术在信息共享系统中的应用 此引发的版权问题。由于对等网络具有非集中控制、自组织、自适应和良好的可 扩展性等优点，使得越来越多的企事业单位关注对等网络技术本身，包括微软、 i n t e l 、s u n 和h p 等在内的大公司也纷纷加入p 2 p 的研究行列中，并由i n t e l 发起， 成立了包括上述公司的p 2 p 工作组，以推动p 2 p 进一步发展，财富( f o r t u n e ) 杂 志更将p 2 p 列为影响i n t e r n e t 未来的四项科技之一。 由于本文的侧重点在于p 2 p 技术在数据共享应用中的快速查找算法的优化， 因此本章将分析并讨论该应用领域几个众所周知的p 2 p 案例：n s p s t e r 、f a s t t r a c k 、 c h o r d 和c a n 。 2 2 1n a p s t e r 和f a s t t r a c k n a p s t e r 是第一个取得大范围商业成功的p 2 p 应用，它是基于带有发现和查找 服务器的p 2 p 模型构建而成的。n a p s t e r 的设计重点在于共享扩展名为m p 3 w m a 的文件用户第一次使用该文件时必须先注册一个帐号。之后，用户通过i n t e r n e t 连接登录到n a p s t e r 中央服务器上，中央服务器保存所有的在线注册用户的索引， 也维护了这些用户机器共享的m p 3 w m a 音乐文件的列表，这些目录随着用户每 次登录或退出n a p s t e r 服务器都被更新。当用户为了查找某首歌曲而发送请求 时，中央服务器会在当前在线用户索引中查找，然后返回拥有这首歌曲的所有在 线用户列表，单击列表上的用户名字就能与该用户直接建立连接。中央服务器在 连接建立后即退出通信过程，文件从一个用户传送到另一个用户的机器上，服务 器并不存储实际的文件。n a p s t e r 的通信模型可以用图2 1 表示： 固 i 服务暑葺 发出蕊勤 圈 下载文件 峰 囝 圈2 1n a p s t e r 通信模型 f i g2 1t h em o d e lo f n a p s t e rs y s t e m 从严格意义上来说，n a p s t e r 是c s 模型与p 2 p 模型的混合体。其资源发现和 查找过程采用c s 模式，节点问的文件传输则采用p 2 p 模式。n a p s t e r 的优势在于： 9 东北大学硕士学位论文 第二章p 2 p 技术在信总共享系统中的应用 ( 1 ) 查询速度快，可以推算查询所需的最长时间；( 2 ) 使用服务器保存用户的注册 信息，只有注册用户的信息才能在n a p s t e r 网络上传输，用户比较有安全感。n a p s t e r 的不足在于：( 1 ) 它仍是带有集中式特征的系统，单点故障使系统的容错性很差， 一旦出现技术问题，服务器会减速甚至停止服务；( 2 ) 服务器很容易成为系统的瓶 颈，服务器可承受的负载限制了系统扩展；( 3 ) 只能提供m p 3 w m a 音乐文件， 任何其它文件都不能共享。 与n a p s t e r 相类似的f a s t t r a c k 的p 2 p 技术也被许多著名的p 2 p 应用( 如 k a z a a ) 采用来建立文件共享服务网络。f a s t t r a c k 的协议是不公开的，所有基于 该技术的应用都必须获得f a s t t r a c k 的授权。f a s t t r a e k 支持各种媒体文件( 如视 频、音频、高维数据、文本、软件) 的元数据( m e t a d a t a ) 搜索，元数据信息可 以自动从文件提取或由用户通过应用程序提供的向导功能来添加。尽管f a s t t r a e k 是一个非常庞大的分布式系统，它的搜索速度可以与诸如n a p s t e r 的集中式系统 相匹配。f a s t t r a c k 仍然采用了中央服务器维护节点注册信息，负责节点登录( 为 了维护在线用户的统计数据) 。当服务器验证节点身份后，就将一个或多个“超级 节点”( s u p e r n o d e ) 的i p 地址和端口( 通常是1 2 1 4 ) 发送给用户。超级节点类 似于局部范围内的搜索中心，它们是从普通节点中自动产生的，前提是它们具有 足够的带宽和处理能力。超级节点为所有连接到它的节点建立共享文件的索引， 并代表这些节点执行搜索操作。超级节点间相互连接，并转发搜索请求，搜索结 果将包含目标节点的i p 地址，节点间通过h t t p 协议以p 2 p 方式进行文件传输。 与g u n t e l l a 采用的广播式搜索算法相比，这种模式大大减少了搜索时间。 节点 图2 2f a s t t r a c k 的通信模型 f i g2 2t h em o d e lo f f a s t t r a e ks y s t e m 1 0 东北大学硕士学位论文 第二章p 2 p 技术在信息共享系统中的应用 f a s t t r a c k 的另一个特点是采用了s m a r t s t r e a m 技术和f a s t s t r e a m 技术。当文 件下载过程尚未完成却无法再连接到目标节点时，s m a r t s t r e a m 技术能尝试找到菇 享该文件的令一节点，自动进行断点续传。f a s t s t r e a m 技术则解决了p 2 p 文件兆 享系统下载速度慢的问题，当搜索引擎发现有多个在线节点能提供某文件的下载 服务时，下载任务将由这些节点共同完成，以提高下载速度1 2 0 1 。图2 2 给出了详 细的f a s t s t r e a m 的通信过程模型 2 2 2c h o r d 和c a n c h o r d 算法【2 l 】是由m i t 提出的一种分布式查找协议，该协议中，每个机器被赋 予一个m 比特的节点标识号( 对机器的1 p 地址进行晗希运算求得) 。每个数据纪录 ( k v ) 有一个唯一的关键字k ，在c h o r d 中，对k 进行哈希运算可得n - 个唯一 的数据标识号，从而使得数据和机器都可以用唯一的标识号表示。所有可能的 n = 2 m 个节点号构成一个一维环，机器映射到( 根据其节点号) 相应的虚拟节点 中。对每个节点标识号，环中顺时针方向的第一个物理机器就叫做它的后继节点。 每个数据纪录( k ，v ) 有一个标识号p = h a s h ( k ) ，确定该数据的存储节点位置，即 p 的后继节点。为了实现高效路由，每个节点的本地仅仅维护环中其后第l ，2 ，4 ， 8 ，n 2 个虚拟点的后继节焦的位置信息。这样，每个节点需要o ( 1 0 9 n ) 大小 的存储空间来保存拓扑信息( f i n g e r t a b l e ) 。 查找信息k 时，先求得p = h a s h ( k ) ，然后从任意一个物理节点开始进行查找， 节点在“f i n g e r t a b l e ”中查找匹配p 的表项，如找到则直接把请求发送到对应节点， 查询结束。如没有匹配表项，则搜索“f i n g e rt a b l e ”中节点标识符小于且最接近p 的节点，并把查询请求转发到该节点。通过递归使用以上步骤，请求以类似于二 分查找的速度接近p 的后继，最终查找成功。因此，算法的时间复杂度为o ( 1 0 9 n ) 。 在c h o r d 中，节点可以随时加入或退出。对于正常的节点加入或退出，在绝 大多数情况下，时间开销为o ( 1 0 9 2 n ) ；在最差的情况下，时间开销为o ( n ) 。如果 c h o r d 环中各个节点维护r 个最近后继节点表，那么系统能够自动检测节点失效， 并从失效中自动恢复。 c a n ( c o n t e n t a d d r e s s a b l e n e t w o r k ) 1 2 2 l 是由b e r k e l e y 提出的一种非集中式查 找算法，它的基本工作原理如下：在c a n 中，每个机器或数据根据其i pt l g t t l ：或 关键字k ，由哈希函数p = h a s h ( k ) 映射到d 维空间中的点，c a n 维护一个基于 东北大学硕士学位论文第二章p 2 p 技术在信息共享系统中的应用 “d t o r u s ”的d 维虚拟空间。虚拟空间被划分为许多小的d 维区域，每个物理机 器对应一个区域，并维护由哈希函数映射到该区域的数据，在d 维空问中，如果 两点有d 1 维坐标相同，并且剩下的一维坐标相邻，这他们互为邻居。每个机器 都要维护它的邻居位置信息( 每维有2 个，共2 d 个) 。查找时，需要先计算给定 关键字在d 维空间中的位置，从任意个物理机器出发，沿着它的邻居点进行查 询，直到找到目的节点。在d 维空间中，每个节点维护2 d 个邻居位置信息，即， 空间复杂度为：2 d 。平均查找长度为：( d 4 ) ( n l d ) ， c a n 通过在现有的网络之上抽象出一层叠加网，将其中所有节点映射到个1 1 维的笛卡尔空间中，并为每个节点尽可能均匀的分配一块区域。c a n 采用的哈希 函数通过对( k e y ，v a l u e ) 对中的k e y 进行哈希运算，得到笛卡尔空间中的一个点，并 将( k e y ，v a l u e ) 对存储在拥有该点所在区域的节点内。c a n 采用的路由算法相当直 接和简单，知道目标点的坐标后，就将请求传给当前节点四邻中坐标最接近目标点 的节点。c a n 是一个具有良好可扩展性的系统，给定n 个节点，系统维数为d ，则 路由路径长度为o ( n ) ，每节点状态信息和网络规模无关为0 ( d ) 。 2 3 基于d h t 的算法存在的问题 诸如以上所介绍的d h t 算法虽然在很大程度上解决了系统查找的可扩展性， 问题，但同时也带来了新的问题。 n a p s t e r 的文件搜索速度比较快，因为所有节点的文件列表都存放在中央服务 器，搜索一个文件只需搜索服务器数据库里的相应记录就可以了。然而从严格意 义上来说，n a p s t e r 不属于真正的p 2 p 应用，系统中仍然有中央服务器协调整个文 件搜索过程，因此同样存在c ，s 结构的缺陷。 f a s t t r a c k 定程度缓解了中央服务器的负载压力，尽管节点提供搜索服务， 并将搜索请求转发到其它超级节点，下载同样采用p 2 p 方式进行。不尉的是 f a s t t r a c k 采用分层体系结构，利用客户端来实现n a p s t e r 中央服务器的文件列表 存储和文件搜索功能。 因为现有的d h t 算法由于采用分布式哈希函数，所以只适合于准确的查找， 如聚簧支持目前w 叠b 上授索引擎再有的多关键字查拽的功能，还舞引入靳的方 法。一个思路是利用现有的基于d h t 的分布式查询协议( 如c a n ，c h o r d 等) ， 针对不同关键字建立k e y w o r d 服务器，多个k e y w o r d 服务器组成一“叠加”网 1 2 东北大学硕士学位论文第二章p 2 p 技术在信息共享系统中的应用 络。用户输入待查关键字，并通过哈希运算映射到对应的k e y w o r d 服务器，通过 多个关键字对应的不同的k e y w o r d 服务器之间的协同完成查询。当文件插入系统 时按照一定的规则抽取关键字，每个关键字都发送到负责该关键字的服务器。当 客户需要对多个关键字k 1 、k 2 、k 3 进行查询时，系统首先向负责k i 的关键字服务 器s l 发出请求，s 1 响应查询请求把查询结果发给负责k 2 的服务器s 2 ，s 2 进行本