（计算机软件与理论专业论文）基于对等计算的数据管理系统的设计与实现.pdf

摘要 摘要 在计算机及网络技术迅猛发展的今天，随着互联网的普及与数据管理技术的 发展，越来越多的互联网用户需要共享数据或者服务。随着数据采集技术的成熟 与硬件成本的降低，传感器网络在各种监控应用中也变得越来越重要。越来越多 的网络应用要求节点既可以作为客户机也可以成为服务器，或者既是客户机又是 服务器；很多应用需要节点可以根据需要在应用层与其它节点建立连接或者进行 通讯。具有上述特性的系统通常被抽象为“对等计算”( p e e r - t o p e e r ，或者p 2 p ) 系统。 对等计算网络中节点具有自主性、对等性；节点可以任意加入或者退出网络， 对等网络是动态的、可扩展的；对等计算网络中节点是大规模分布式的，网络中 没有集中控制；各个节点的共享数据存储模式可能是不同的，而节点共享与处理 数据的能力也存在着差异。本文针对上述对等网络的特点，着力研究对等环境下 数据管理问题。对等计算网络中数据管理主要涉及网络中数据和查询的路由、定 位与查找，数据放置、查询处理等方面。 本文主要贡献有： 1 在对现有对等计算模型共享与数据管理系统分析基础上，提出在非结构 化( u n s t r u c t u r e d ) 对等计算网络中利用“视图协作”机制，以及基于分 布式散列表( d i s t r i b u t e dh a s ht a b l e ，或d h t ) 的资源定位查找机制，构 建视图协作网络，利用大规模分散的网络节点资源，通过d h t 将数据 源、查询、协调节点等信息进行定位，查询节点相互协商、合作，为相 同或相近的查询建立不同粒度的视图( v i e w ) ，共享关系数据。通过节 点间协作维护视图减少网络传输代价、优化查询、提高查询响应速度、 减轻数据源工作负载： 2 利用b e s t p e e r 网络作为底层平台，建立视图协作网络，给出基于视图的 协作网络实验测试结果。网络中节点共享真实数据，发出大量查询。分 别对网络传输率、吞吐量、查询响应时间等数据量进行统计，通过与无 视图协商策略的分布式网络进行比较来证明视图协作网络可以有效地 提高网络带宽利用率、减少查询响应时间； 3 实现了基于非结构化( u n s t r u c t u r e d ) 对等计算模型的查询处理系统 摘要 p e e r v i e w 。该系统具有通用性，可以建立在任意非结构化对等计算网络 平台上。网络中每个节点都会根据自己的实际处理能力提供视图共享空 间，用来与其它节点共同建立及维护共享视图。节点既可以利用后端数 据库处理查询也可以进行跨节点的查询处理；节点通过查询进行聚类， 具有相同相近查询的节点共同建立维护共享视图，以减小网络开销、查 询处理开销；节点间通过协商为收益最大的查询建立视图；节点既可以 直接访问数据源取得数据也可以利用有效的共享视图获得数据。该系统 可应用于数据大规模分散的某一行业体系内，关系数据共享与查询方 面，如医疗管理领域等。 本文建立在对当前已有技术的分析和实验测试基础上。实验和分析表明，与 当前其他对等计算环境下的查询处理方式相比，基于视图的协作网络构建思想在 查询效率和资源利用率上更具优势。而本文中介绍的p e e r v i e w 系统正是对基于 视图的协作网络的实现。 关键词：对等计算，查询处理，视图选择 i i a b s t r a c t a b s t r a c t w i t ht h e p o p u l a r i t yo fi n t e r a c t a n dt h e d e v e l o p m e n to fn e t w o r ka n dd a t a m a n a g e m e n tt e c h n o l o g i e s ，m o r ea n dm o r eu s e r st e n dt os h a r et h e i rd a t ao rs e r v i c e w i t ho t h e r s s e n s o rn e t w o r k sa r ep l a y i n gi m p o r t a n tr o l e si nm o n i t o ra p p l i c a t i o n s i n b o t ha p p l i c a t i o n sm e n t i o n e da b o v e ，an e t w o r kn o d ec a l lp l a yt h er o l eo f ac l i e n to ra s e r v e r , o rb o t h a n dan o d em a ye s t a b l i s hc o n n e c t i o no rc o m m u n i c a t i o nw i ma n y o t h e rn o d eo na p p l i c a t i o nl e v e l s y s t e m sw i mt h e s et w of e a t u r e sa r cg e n e r a l i z e da s s y s t e mw i mp e e r - t o p e e rm o d e l p 2 pn e t w o r kh a sm a n y c h a r a c t e r i s t i c s ，s u c ha ss y m m e t r y , a u t o n o m y , d y n a m i c s ， d e c e n t r a l i z a t i o n ，d i s t r i b u t i o n ，a n ds oo n w i t hav i e wt ot h e s ef e a t u r e s ，t h i st h e s i s f o c u s e so nt h ei s s u e so fd a t am a n a g e m e n ti np 2 p e n v i r o r t r a e n t m a n yp r o b l e m s ，s u c h a sl o g i cn e t w o r k c o n s t r u c t i n g ，b u i l d i n gr o u t i n gt a b l e ，d a t aa n dq u e r yr o u t i n g ，l o c a t i n g a n ds e a r c h ，d a t ap l a c e m e n t ，q u e r ya n s w e r i n g t e c h n i q u e s f o rs u p p o r t i n gc o m p l e x q u e r y p r o c e s s i n g ，a r er e f e r r e dt o i tp r o v i d e sa m o d e la n dar e a ls y s t e mo nu n s t r u c t u r e dp 2 p n e t w o r k u s i n g c o l l a b o r a t i v ev i e w m a j o r c o n t r i b u t i o n so f t h i st h e s i si n c l u d e 1 am o d e lo nc o l l a b o r a t i v en e t w o r ki sp r e s e n t e d i nt h i sm o d e l ，u s e rc a nu s e c o l l a b o r a t i v ev i e wt od e c r e a s ec o s to fn e t w o r kt r a n s p o r ta n di n c r e a s e e f f i c i e n c yo f q u e r yp r o c e s s i n g 2 e x t e n s i v ee x p e r i m e n t a ls t u d i e sa b o u tc o l l a b o r a t i v en e t w o r km o d e lh a v eb e e n d o n ei nt h i s 血e s i s r e s u l t ss h o wt h a to u rm o d e li sm o r ee r i e c t i v et h a l lo t h e r m o d e l u s i n g c a c h em e c h a n i s m ； 3 aq u e r yp r o c e s s i n gs y s t e m ，c a l l e dp e e r v i e wf o ru n s t r u c t u r e dp e e r t o - p e e r e n v i r o n m e n t s ，i sp r o p o s e d q u e r yp r o c e s s i n gc a r t b ee x e c u t e do v e rp e e r s b a s e do nu n s t r u c t u r e d p e e r - t o - p e e rp l a t f o r m a n dt h er e l a t i o n a ld a t a b a s e e n g i n eo fe a c hp e e r p e e r v i e wd i f f e r s i t s e l ff r o me x i s t i n gs y s t e mi ni t s c o l l a b o r a t i v ev i e wa n dd i s t r i b u t e dh a s ht a b l e ( d h t ) b a s e dr e s o u r c el o c a t i o n a n ds e a r c hm e c h a n i s m w i t h m u l t i g r a n u l a r i t y v i e w si nc o l l a b o r a t i v e e n v i r o n m e n t ，q u e r yp r o c e s s i n gc a n b ep e r f o r m e de f f i c i e n t l y t h ew o r ki sb a s e do nt h e a n a l y s i s o fc u r r e n t t e c h n o l o g y a n de x t e n s i v e e x p e r i m e n t a lt e s t i n g t h ee x p e r i m e n ta n da n a l y s i ss h o wt h a t ，c o m p a r e dw i t he x i s t i n g 1 1 1 a b s t r a c t q u e r yp r o c e s s i n gs y s t e m sc o n s t r u c t e di np e e v t o - p e e re n v i r o n m e n t s ，o u rs y s t e mi nt h i s t h e s i sh a sa d v a n t a g e so f e f f i c i e n c y i nb o t h q u e r yp r o c e s s i n ga n d r e s o u r c eu t i l i z a t i o n 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 ，q u e r yp r o c e s s i n g ，v i e ws e l e c t i o n i v 引言 1 引言 随着网络及计算机硬件的发展，对等计算( p e e r t o p e e r c o m p u t i n g ，或p 2 p ) 研究成为工业界和学术界共同关注的新开发研究领域。对等计算是种不同于传 统客户机n 务器( c l i e n t s e r v e r ，或c s ) 模型的网络计算模型。与传统网络相比， 对等计算具有两个明显的特征。第一，对等计算中的节点既可以单独得做客户机 或服务器，也可以同时具有客户机和服务器双重身份；第二，在某些必要的情况 下，对等计算网络中的节点可以在应用层与任意节点建立连接或者通讯。 从2 0 0 1 年丌始，出现了大量基于对等计算的软件系统。其中较为著名的包 括早期的n a p s t e r n a p s t e r ，2 0 0 3 、g n u t e l l a g n u t e l l a ，2 0 0 3 、i c q 【i c q ，2 0 0 3 ，以 及当前流行的k a z a a 【k a z a a ，2 0 0 3 、m o r p h e u s m o r p h e u s ，2 0 0 3 、m s n m e s s e n g e r m s n m e s s e n g e r ，2 0 0 3 1 等。这些系统的用户群从最早的学生群体发展 到广大因特网用户。据统计，到2 0 0 3 年9 月，当前最流行的基于对等计算的多 媒体文件共享平台k a z a a 的下载次数已经达到2 3 0 ，3 0 9 ，6 1 6 次【k a z a a ，2 0 0 3 。 学术研究总是与工业界应用开发相呼应的。在学术界，从2 0 0 1 年开始，a c m s i g c o m m 【s i g c o m m ，2 0 0 3 1 、v l d b 【v l d b ，2 0 0 3 1 、i e e e i n f o c o m 【i n f o c o m ，2 0 0 3 】等计算机领域的重要学术会议上先后出现关于对等计算的学 术论文；而自2 0 0 2 年开始，以对等计算为主题的学术会议也相继出现。对等计 算正在学术界掀起研究热潮。 本文主要探讨对等计算环境下的数据查询处理的问题。其目的是探索如何高 效地在基于对等计算模型的系统中提供复杂查询功能。对该问题的解决涉及到数 据和查询在对等计算系统中的路由( r o u t i n g ) 、查询的定义、分布环境下索引的 构造、利用与维护、数据的缓存( c a c h i n g ) 、放置( p l a c e m e n t ) 与复制( r e p l i c a t i o n ) 等很多问题。 1 1 对等计算研究背景 早期的网络构建雏形是对等模式的。但是由于存在安全、信任、公平性以及 计算机硬件水平等方面的限制，使得网络最终采用了客户机服务器( c s ， c 1 i e n t s e r v e r ) 架构模式。防火墙将统一的网络割裂开来，使网络用户安全得 引言 到有效的保障、保护用户的隐私。但是因特网中绝大部分资源并未得到充分的利 用，用户之间的共享合作几乎是不可能的。 随着计算机硬件设备的发展，人们开始将目光转向对等计算模式网络上来。 由于网络安全、用户信任度等方面的限制仍然存在，对等讨算的研究从简单的共 享与即时通讯方面展开。对等计算最先在这两类应用中取得成功：文件共享( f i l e s h a r i n g ) 和即时消息传递( i n s t a n tm e s s a g e ，或i m ) 。 基于对等计算的文件共享就是本地文件不经过第三方文件服务器直接共享、 传递给文件请求方。基于对等计算的文件共享系统，主要用来共享多媒体文件， 例如，音频文件、视频文件等。n a p s t e r 是最早出现的文件共享系统之一。n a p s t e r 曾经创造了在十六个月由用户创建了两千三百万个“n a p s t e r 地址”的纪录 s h i r k y ，2 0 0 1 。虽然由于法律原因，n a p s t e r 网站被暂时关闭 n a p s t e r ，2 0 0 3 ， 但是继之而起的g n u t e tl a 6 n u t e l l a ，2 0 0 3 、p r e e n e r f r e e n e t ，2 0 0 3 3 、k a z a a k a z a a ，2 0 0 3 、m o r p h e u s m o r p h e u s ，2 0 0 3 等文件共享软件仍然在被广泛使用。 而且k a z a a 已经成为下载量最高的共享软件( s h a r e w a r e ) k a z a a ，2 0 0 3 。 基于对等计算的即时消息传递是为不同计算机用户提供可以互相递送消息， 进行即时网络对话的应用。这不同于同一台主机不同终端用户之间的消息传递， 因为消息的传递是在两台不同的计算机之间进行的，这两台计算机可以拥有不同 的体系结构、运行不同的操作系统。著名的即时消息传递软件i c q i c q ，2 0 0 3 曾经是下载量最大的共享软件。其它著名的即时消息传递软件包括a o li n s t a n t m e s s a g e ( a i m ) a i m ，2 0 0 3 、y a h o o ! m e s s e n g e r ( y a h o o ! p a g e r ) y a h o o 卜p a g e r ，2 0 0 3 、m s nm e s s e n g e r m s n m e s s e n g e r ，2 0 0 3 等。这些即时消 息传递软件除了提供简单的文字消息传递功能以外，还提供包括文字会议、文件 共享、即时音频对话甚至即时图像传输等功能。 在实际应用领域中，对等计算技术主要考虑日常生活和娱乐等方面问题；而 对于工业界、政府和学术界来说，它们更重视p 2 p 在工业、商业、科研等领域的 实际作用。在工业界，著名的s e t i h o m e s e t i h o m e ，2 0 0 3 项目致力于i n t e r n e t 上大量零用分散的闲置c p u 资源进行探索外太空的科学计算。而重要的软件生产 商，例如，m i r c r o s o f t 、s u nm i c r s y s t e m 公司，则推出了基于类p 2 p 结构的分 布式平台，即m i c r o s o f t 的n e t 构架 m i c r o s o f t n e t ，2 0 0 3 ，s u nm i c r s y s t e m 的。1 x t a 平台 j x t a ，2 0 0 3 。这些构架和平台的目的在于提供一种通用的机制， 在不需要知道具体的服务提供者的来源、位置的情况下，使网络中每一台计算机 能够互相提供和享受服务，其本质就是实现对等计算。在推出软件平台的同时， 引言 这些软件生产商还致力于制定协议和标准以规范服务的提供、使用与查找。这些 协议、标准和软件平台一起被置于w e b 服务( w e bs e r v i c e ) 的体系结构下。 另一方面，政府和一些大型的研究机构所推行网格计划( g r i d ) ，其目的是提 供存储与计算等公共信息服务。在网格计划中，由于各个网格节点往往是分布的， 所以需要整合这些节点，以向外( 即向网格用户) 提供统一的信息服务。在整合 过程中，涉及到节点之阃的信息交换、服务共享、负载平德等多方面的问题。这 些问题本身都是对等计算的问题。从这个角度来看，网格的目标是利用p 2 p 技术 提供操作系统一级的服务：而对等计算研究一方面考虑的是通用的对等计算模 型，另一方面则更多地考虑应用一级的服务 u 1 i m a n ，2 0 0 3 。此外，一些网格项 目旨在利用已经存在的边缘( e d g e e n d ) 计算机资源，即大量的个人电脑( p c ) ，来 提供统一的存储或者计算服务。因此，前面提到的s e t i h o m e 项目也常常被归入 网格项目。 除公司和政府以外，一些民间组织也在参与对等计算系统开发、应用拓广。 例如，自n a p s t e r 以后。出现了一大批具有类似功能的开源软件( o p e n s o u r c e s o f t w a r e ) 或自由软件( f r e e w a r e ) ，例如g n u t e l l a g n u t e l l a ，2 0 0 3 、f r e e n e t f r e e n e t ，2 0 0 3 、o p e n n a p o p e n n a p ，2 0 0 3 等。除了这些针对特定应用的软件 以外，还有一些开源软件或者自由软件致力于提供通用的基于对等计算模型的服 务。例如，j a b b e r j a b b e r ，2 0 0 3 主要被开发用来提供基于可扩展标注语言 ( e x t e n s i b l em a r k u pl a n g u a g e ，或x m l b r a ye ta 1 ，2 0 0 0 ) 的消息传递。与 i c 0 等即时消息传递软件不同，j a b b e r 系统希望通过传递带标注的x m l 消息来达 到应用程序与应用程序之问的“对话”功能。所以j a b b e r 其实是一个通用的基 于p 2 p 的消息传递平台，它既可以被一些程序用来执行即时消息传递任务，也可 以被用来开发其它应用程序。 在应用的推动下学术界开展了大量针对对等计算模型、系统、核心技术的 研究。目前，已经启动了很多研究项目，并有很多原型系统相继问世。这些研究 工作的目的都是利用对等计算模型，在分布的环境下，提供各种更好的服务。一 般的讲，这些研究工作中存在着两类不同的指导思想：一种是利用现有的网络环 境、机制，在这些环境和机制上研究并开发新技术，以提供更好的应用层服务。 这些研究包括很多对于非结构化p 2 p 系统的研究；另一种是通过“构造”新的网 络结构，以使这些网络能够具有一些良好的查找、路由和定位的性质。利用这些 性质，研究者可以更方便地开发上层应用。很多对结构化p 2 p 系统的研究属于这 一类。这两类研究工作的目的都是为了提供更好的信息服务，而且它们都取得了 引言 一 丰收的研究成果。就研究的取向来说，前者偏向于研究提高质量的应用层服务， 而后者注重底层平台支持，以及下一代“i n t e r n e t ，构建。 下面，首先从i n t e r n e t 发展角度来分析对等计算模型，主要分析对等计算 产生的原因以及它和其它网络计算模型之问的关系；然后从数据管理角度分析对 等计算与传统集中式或者分布式环境下数据管理的异同。 i i 。1 从i n t e r n e t 发展看对等计算 从讨算模型角度来看，i n t e r n e t 的发展历史大致分为三个阶段： i n t e r n e t 发展早期，原始的p 2 p 时期( 1 9 6 5 年一1 9 9 5 年) 尽管上面提到成功 的p 2 p 应用或者系统大多数是从2 0 0 0 年前后开始出现的，但是作为计算模 型，对等计算在i n t e m e t 发展初期就已经存在。当i n t e r n e t 前身a r p a n e t 诞生时，其成员u c l a 、s r i 、u c s b 和u u t a l l 都是对等的计算中心。随后 出现的很多重要的网络应用都沿袭了这种p 2 p 模型。例如，域名服务系统的 各个域名服务器之间是纯粹的p 2 p 关系。另一个著名的基于p 2 p 模型是 u s e n e t ，u s e n e t 服务器是对等的，并且是完全自治的，整个u s e n e t 系统在各 个自治的服务器的协作下运作良好 m i n a r a n d h e d l u n d ，2 0 0 1 】。可见，p 2 p 模 型是伴随着i n t e m e t 而产生的。特别是在大规模分布式信息共享时，p 2 p 模 型在实践中证明了其有效性。尽管如此，p 2 p 模型主要还是应用在服务器层 次上，对于终端用户来说，它们采用的仍然是c s 模型。 i n t e r n e t “爆炸”时期，c s 模型取得成功( 1 9 9 5 年一1 9 9 9 年) 随着计算机和 网络的普及，大量企业和个人用户开始使用网络，包括i n t e m e t ，在这其间 诞生了很多应用，这些应用大多使用c s 模型。c s 模型取得成功有三方面 原因：首先，从硬件发展角度来看，由于终端用户计算机一般不具有很强的 存储和计算能力，需要借助服务器才能完成一些重要任务；并且，终端用户 的网络带宽通常是不对称的，即下传的带宽一般大于上传的带宽 m i n a ra n d h e d l u n d 。2 0 0 1 1 ，这使得用户提供服务既不可能也不方便。其次，从软件丌 发方面来看，随着c s 模型诞生一些非常有效的软件开发方法和协议，这些 方法和协议大大提高了软件开发豹效率，减小了开发成本。最后，从人为因 素来看，由于病毒、垃圾邮件、供给的泛滥以及协议的滥用，致使网络管理 加强，特别是防火墙的广泛设立和拥塞控制的加强。管理的加强虽然保障了 网络的f 常运行却抑制了对等计算的发展节点之间的协作不再存在。 i n t e r n e t 新时期( 2 0 0 0 年至今) 个人电脑处理能力的提高以及网络条件的改善 引言 促使对等计算在硬件方面的限制首先被打破。同时，很多可以绕过或者“欺 骗”防火墙的应用程序的出现使节点之间协作与共享成为可能。即时消息传 递和文件共享成为最先成功的新对等计算应用。这些应用与早期p 2 p 应用模 型不同：这些应用中，参与节点本身是终端用户，即所谓的边缘用户 ( e d g e - e n du s e r ) 。虽然每个终端用户的处理能力有限，但是它们提供的服务 的规模巨大。同样，大型公司与政府对w e b 服务和网络等框架与系统的推 行同时推进了对等计算的发展。 虽然对等计算技术在迅猛发展，但是仍然缺少在大型应用或者关键应用中的 成功实行。原因主要在于两个方面：首先，大型应用和关键应用对于企业或者机 构的发展作用重大，在具有成功把握之前企业与机构不会轻易采用新技术。其次， 对等计算技术本身不成熟。在效率、可靠性、技术实施成本等方面，对等计算仍 然不能证明其竞争力。但是，边缘用户的大量闲置资源吸引了很多企业及软件商 的研究机构、著名高校和研究所投入大量精力研究。本文所要探讨的数据查询处 理问题是对等计算应用的一个重要问题之一。 1 1 2 从数据管理看对等计算 数据管理 g a r c i a m o l i n ae ta 1 ，2 0 0 2 包括数据的定义与包u 建、查询、存储， 以及相关的控制等问题。数据管理问题本身是和应用的环境以及数据的特点紧密 相关的。本小节将从应用的体系结构和数据特点两方面阐述对等计算模式下的数 据管理问题。 p 2 p 环境下数据库应用的体系结构p 2 p 环境下的数据管理环境与传统的数据库 体系结构不同。首先，数据源是分布的，即每个节点都可能提供数据。这不 同于集中式或客户机服务器体系机构的数据库系统。其次，在p 2 p 环境下， 一般不存在集中控制，即每个节点都是“对等的”。而且节点都是自主的， 节点可以具有不同模式。这些问题都是传统的分布式数据库技术所不考虑 的。第三，p 2 p 环境下节点数目巨大，采用传统的信息集成技术代价昂贵。 最后，每个节点所要求的服务是不同的。单一的信息集成过程不能满足所有 节点的需要。这些问题都要求针对p 2 p 环境的特性探索和开发新的数据库应 用体系结构。 数据特点在p 2 p 环境下，节点是独立、自治的，每个节点部可以按照其自身的 方式发布数据，即按照自身的模式发布数据。虽然数据的发布者可能可以管 理某个节点上数据的内模式和概念模式，但是其它节点可见的仅仅是外模 引言 式，各个节点采用的模式可能不同。相同数据在不同节点中可能存在不同的 表示；不同节点中具有相同表示的数据可能表示不同的意义。 共享数据量可能是巨大的。一方面，某些节点上可能共享大量数据；另 一方面，虽然单个节点共享的数据可能并不多，但在整个p 2 p 系统中共享的 数据仍然可能是巨大的。所以，共享的数据量可能超过任何一个节点的处理 能力。 综上所述，p 2 p 数据管理系统首先要能够提供一种跨越不同语法和语义造成 的鸿沟的查询方式；其次在处理查询时，系统必须考虑到不同节点的处理能力的 差异，在此前提下充分利用每个节点的资源；最后，系统希望能够在大量节点参 与的动态环境下，有效并且高效的处理海量数据。 1 2 对等计算的特点 从i n t e r n e t 和数据管理两方面的分析以及对潜在应用情况的介绍中可见， 基于对等计算的系统主要具有节点间对等( s y m m e t r y ) 、节点自治( a u t o n o m y ) 、网 络动态( d y n a m i c s ) 以及无集中控制( d e c e n t r a l i z a t i o n ) 和大规模分布 ( d i s t r i b u t i o n ) 的特点。下面分别就每一个特点说明其和传统分布式系统的异 同： 对等传统分布式计算中，节点的客户机或服务器角色区分明确。而在p 2 p 系统 中，节点问是对等的。它们既可以是客户机也可以是服务器。同时，节点还 可以在应用层和任意一个节点进行通讯，发出请求或者接收应答。所以，对 等计算系统构造了节点间应用层联系与底层物理网络不同的“对等网络( p 2 p n e t w o r k ) ”。于是在一些文献中，对等网络又被称呼为“重叠网络( o v e r l a y n e t w o r k ) ”。 自治传统分布式计算中，节点是受控的。在对等计算应用中，节点是自治的。 这意味着节点可以在任何时候动态加入或者退出系统，节点可以以其自身的 语法和语义发布数据，节点可能具有差异相当大的处理能力。节点的自治并 不意味着节点间不能协作或者相互提供服务。相反，一些系统要求节点必须 提供服务才能享受服务，以遵守所谓的“公平( f a i r n e s s ) ”原则。此外， 些系统通过把具有相同或者相似服务请求的节点进行聚类并让它们相互服 务的手段来实现节点间的协作。 动态由于节点的自治以及网络和系统稳定性的影响，整个p 2 p 网络是动态的。 在p 2 p 系统中考虑的动念性不同于传统的分布式计算中的动态性。在一般分 引言 布式系统中，对动态性的考虑主要包括系统的纠错与恢复等问题 c o 谢。嘣s e ta 1 ，2 0 0 0 ，t a n e n b a u ma n d v a i ls t e e n ，2 0 0 2 1 ，而在p 2 p 环境下，对于动态性 的考虑主要围绕如何利用当前可用的资源提供最好的服务开展。此外，p 2 p 系统的动态性还体现在数据的动态性上。这与传统的分布式数据库中考虑的 数据动态性相似，数据可以被插入、删除和更新。 无集中控制和大规模分布传统的分布式计算系统中一般存在集中式的控制，而 在p 2 p 系统中，这样的控制不存在。所以，节点间的合作必须通过协商解决。 此外，缺乏集中控制还造成系统整体情况信息的缺失每个节点都通过有 限的局部信息做出决定。这样造成的后果可能是系统不能以全局最优的策略 完成某一个特定任务。另一方面，p 2 p 系统中参与的节点个数一般远远大于 传统的分布式系统中的节点个数。在没有集中控制的前提下协调大量节点是 p 2 p 系统和传统分布式系统的主要区别之一。 1 3 对等计算对查询处理的要求 对等计算具有与传统分布式计算不同的特点，对等计算环境对于查询处理技 术提出了新的要求与挑战。主要包括以下几个方面： 分布( d i s t r i b u t i o n ) 分布式查询处理是对等计算系统中查询处理的核心。尽管， 对于用户来说查询可能是位置透明的，但是系统必须知道为了处理一个查询 请求，应该在哪个节点上获取哪些数据。也就是说，系统必须提供一种在用 户没有提供数据位置、系统无法预知数据位置情况下，数据的定位和查找机 制。同时，系统必须考虑寻找最优或者较优的查询计划。由于对等计算系统 一般都处于动态环境中，系统需要具有动态判断查询计划优劣的能力。另外， 由于缺少集中控制。分布式查询和优化需要各个节点相互协作。 可伸缩性( s c a l a b i l i t y ) 可伸缩性包括两个方面：数据量可伸缩和节点个数可伸 缩。数据量可伸缩式查询处理技术一直关注的问题，是传统数据管理技术所 要达到的首要目标。但是，在具有成千上万的节点，甚至更多节点的系统中， 如何有效利用资源进行查询处理是对等计算环境提出的新挑战。可伸缩性问 题不但和查询处理本身有关，还与数据的查找、路由等问题紧密相关。 鲁棒性( r o b u s t n e s s ) 对等计算的环境是动态的，节点的加入和退出、网络故障、 数据的增删都可能经常出现。这就要求系统可以在部分节点或者数据不可以 用的情况下。仍然能够正确或者接近正确的执行查询。鲁棒性要求系统不能 够出现所谓的“单点故障”，即系统在某个节点出问题时陷入瘫痪状态。所 引言 以，查找、定位、计算等操作不能够只依赖于某个或者某几个特殊的节点。 高效性( e f f i c i e n c y ) 对等计算环境下的查询处理与传统的查询处理一样，要求 查询被高效地处理。但是，对等计算环境下的节点可能散布在网络的不同位 置，物理上距离比较远，节点的处理能力和网络条件都可能存在很大差异。 所以在处理查询时要充分考虑到节点的异质性、节点操作问的并行性以及节 点间的负载平衡。同时，查询处理时还要考虑索引的利用以及节点空闲时间 的利用，以充分利用边缘资源。 安全性( s e c u r i t y ) 对等计算环境下每个节点都是自治的。数据可靠性和请求服 务者的可靠性都需要系统加以保证。本文不考虑对等计算环境下查询处理中 的安全性问题。 1 4 本文贡献 本文从非结构化p 2 p 应用角度分析探讨了对等网络数据管理涉及的数据和 查询的路由、定位与查找，数据放置、查询处理等问题。本文提出利用p 2 p 网络 中节点的相互合作，共同维护物化视图，并给出网络节点选择建立物化视图的协 商方法。同时本文通过在真实数据集上的实验，验证基于视图的协作网络可以减 少网络开销、提高查询效率理论的正确性。在大量分析与实验基础上，本文构建 了基于视图的协作网络框架系统p e e r e w 。 1 5 本文组织 本文第二章介绍当前p 2 p 网络与数据管理的研究发展，主要分析现有p 2 p 数据管理系统或原型的体系结构、查询技术。第三章提出基于视图的协作网络， 给出协作视图的选择与协商方法；第四章通过实验说明基于视图的协作网络比一 般的p 2 p 网络在网络传输利用率、查询响应时间等方面具有优势；第五章介绍通 用的查询处理系统p e e r v i e w 。第六章总结本文所介绍的对等计算环境下的查 询处理技术，并对今后工作进行展望。 对等计算删络及其应用的研究进展 2 对等计算网络及其应用的研究进展 近年来，很多学者从不同角度开展了关于对等计算的研究。从技术背景看， 具有不同研究背景的学者参与对等计算的研究，包括网络、计算机理论、数据库 等方向；从研究目的看，研究可以分成对于p 2 p 系统底层支持的关键技术的研究 和对于上层应用的研究。在这些研究项目中，以p 2 p 为模型的应用，包括文件共 享、海量存储、信息检索、w e b 缓存、数据管理、数据监控等。 本章将首先对当前关于对等计算的研究和关于p 2 p 环境下的数据管理做简 要的介绍，然后着重从系统结构、查询处理两个方面举例介绍与本文相关的，当 前的p 2 p 环境下数据管理系统的研究情况。 2 1 对等计算研究简介 从系统结构角度来看，p 2 p 系统大体上可以分为两类：结构化p 2 p ( s t r u c t u r e d p 2 p s y s t e m ) 与非结构化p 2 p ( 1 l n s 仇】c n l r e d p 2 p s y s t e m ) 。 结构化的p 2 p 系统的特点是将节点的标识( i d e n t i f i e r ) 统一组织起来，映射 到某个标识空间中。例如，c h o r d 系统【s t o i c a e ta 1 ，2 0 0 1 】的标识空间被组织为 一个环，而c a n 系统f r a t a n a s a m y e ta 1 ，2 0 0 1 】的标识空间是一个多维空间。此 外，一些p 2 p 系统利用p l a x t o n 算法 p l a x t o n e ta 1 ，2 0 0 1 的变型组织构建p 2 p 网 络，例如，p a s t r y 系统 r o w s t r o n a n dd r u s e h e l ，2 0 0 1 】和t a p e s t r y 系统 z h a oe ta 1 ， 2 0 0 2 1 。结构化p 2 p 系统一般具有理论基础。在这些系统中，路由效率、检索正 确性在理论上可被证明的，而且系统的鲁棒性大都具有理论保证。 非结构化p 2 p 系统 y a n ga n dg a r c i a - m o l i n a ，2 0 0 1 】是另一类被广泛研究与 应用的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 具有自配置特性，即每个 节点能够在应用层和任何节点建立联系，这使得非结构化网络更适合于动态的 p 2 p 环境。在非结构化p 2 p 网络中，节点并没有按照某种特殊的“结构”被组织 映射到某个特殊的标识空间中。因此需要通过索引或者广播的方式查找和定位某 对等计算网络及其应用的研究进展 个节点。根据查找时对维护索引的节点( 索引服务器) 的依赖程度，非结构化 p 2 p 系统又可以细分为集中式的( c e n t r a l i z e d ) 、非集中式的( d e c e n t r a l i z e d ) 和混 合式的( h y b r i d ) 。集中式p 2 p 系统，例如n a p s t e r ，采用单个的索引服务器。g n u t e l l a 和f r e e n e t 都是非集中式的p 2 p 系统。混合式的p 2 p 系统一般通过借助多个超级 节点建立多个索引服务器，在超级节点之间往往通过泛滥法相互通讯。而基于超 级节点的p 2 p 系统也成为p 2 p 系统研究中的一个热点。b e s t p e e r 系统附g e ta 1 ， 2 0 0 2 是典型的混合式p 2 p 系统。 对于不同模型p 2 p 系统的研究往往具有不同的侧重点。在结构化p 2 p 系统 的研究中，人们着重于在保证路由效率的前提下提高系统的鲁棒性以及标识空间 的维护效率 s t o i c ae ta 1 ，2 0 0 1 ，r a t n a s a m ye ta 1 ，2 0 0 1 ，m a l k h ie ta 1 ，2 0 0 2 ，d a t a r , 2 0 0 2 ，r o w s t r o na n dd r u s c h e l ，2 0 0 1 ，z h a oe ta 1 ，2 0 0 2 】。而在非结构化p 2 p 系统的 研究中，更着重于利用各种启发式方法提高搜索效率 y a n ga n dg a r c i a m o l i n a , 2 0 0 1 ，z h a n ge ta 1 ，2 0 0 2 ，y a n ga n dg a r c i a - m o l i n a ，2 0 0 2 ，g r e s p oa n dg a r c i a m o l i n a , 2 0 0 2 ，c o o p e ra n dg a r c i a 、m o l i n a ，2 0 0 3 1 。此外，对于各种p 2 p 应用的研究各自侧 重于如何利用p 2 p 底层平台提供的机制建立可靠、商效的应用系统。本文主要从 非结构化方面研究数据管理查询技术。 从数据管理角度来看，p 2 p 研究在数据库领域中的研究项目和系统通常包括 两类。一类目的在于研究通用的数据管理，特别是查询功能。这类项目包括p i e r h a r r e ne ta 1 ，2 0 0 2 ，h u e b s c he ta 1 ，2 0 0 3 、p i a z z a g r i b b l ee ta 1 ，2 0 0 1 ，h a l e v ye t a 1 ，2 0 0 3 c ，h a l e we ta 1 ，2 0 0 3 a ，h a l e v ye ta 1 ，2 0 0 3 b 、h y p e r i o n k e m e n s t s i e t s i d i s e t a 1 ，2 0 0 3 b ，k e m e n s t s i e t s i d i se ta 1 ，2 0 0 3 a 和p e e r d b n g e ta 1 ，2 0 0 3 a