（计算机应用技术专业论文）p2p分布式数据库研究.pdf

摘要 p 2 p 结构具有鲁棒性、分散性、负载平衡和可扩展性等特点，是下一代互联网技术发展 方向之一，在文件共享和分布式计算领域倍受关注。随着i n t e r n e t 的发展，基于局域网的传 统分布式数据库，在管理和共享广域网范围内的数据时显得力不从心，可扩展性较差，而且 这种具有严格体系结构及其a c i d 特性的要求很难适应i n t e m e t 的动态特性。p 2 p 结构的出 现恰恰弥补了这些缺陷，为管理和共享广域网范围内的数据提供了一种高效平台。本文以 d h t - b a s e d 结构化p 2 p 作为分布式平台，设计一种i n t e r n e t 环境下的分布式数据库实现机制。 d h t ( d i s t d b u t e dh a s ht a b l e ) 结构化p 2 p 网络具有鲁棒性、自适应性、可用性、负载均衡 等特点，但是其缺乏表示、管理复杂语义数据的手段，仅支持关键字精确匹配查询。这恰恰 是分布式数据库技术( 数据复制，索引机制，查询处理等等) 优势，p 2 p 技术和分布式数据 库相结合，克服p 2 p 技术的不足，实现广域网范围内数据管理和信息共享。 本文首先对分布式数据库技术进行研究分析，并比较、分析其与p 2 p 技术的不同；其 次对三种p 2 p 结构的作必要的分析，从网络结构、体系结构、数据复制等方面对典型的p 2 p 数据管理系统进行研究；在此基础上，本文探讨一种基于d h t p 2 p 的分布式数据库实现机 制。 在该系统中，利用数据分割和数据复制，把节点负载分散，达到系统负载均衡和提高可 用性；首先，用分割规则把关系表分割成小的数据副本，并对这些小的数据副本进行标识： 然后，把这些数据副本和副本定位元数据放置其它节点上，定位元数据负责副本定位。关系 表标识、副本标识和物理索引组成一个层次索引机制，达到快速资源定位，并有效保持了副 本间的逻辑整体性。 一组联系比较紧密的节点之间存在频繁的数据交换，把这些节点组成一组，并利用协调 规则管理数据的存取，实现l d b s 之间的数据共享和交换。 利用分层索引和p 2 p 路由算法设计一种资源定位方法，当用户进行数据请求时或查询 相关数据时，以关系表名称和查询条件为参数，实现相关副本定位。把数据操作发送给相关 节点，执行局部操作，返回数据集。 关键字：p 2 p 数据库，资源定位，数据复制，分层索 a b s t r a c t p 2 pn e t w o r kh a sr o b u s t n e s s ，a d a p t i v e ，a v a i l a b i l i t ya n dl o a d - b a l a n c e ，i so r eo fn e x tg e n e r a t i o n i n t e m e tt e c h n o l o g i e s w i t ht h ed e v e l o p m e n to fi n t e m e t ，t h ed i s t r i b u t e dd a t a b a s es y s t e m sb a s e d o nl a b h a v ep o o rs c a l a b i l i t y ，r i g i da r c h i t e c t u r ea n dr e q u i r eo fm a i n t a i n i n gd a t aa c i d ，w h i c hc a l l n o ta f f o r dt om a n a g et h ed a t ad i s t r i b u t e da m o n gw o r l d w i d en e t w o r k t h ep 2 pt e c h n o l o g yc a n m a k eu pt h ed i s t r i b u t e dd a t a b a s es y s t e m sl a c k sa n ds u p p l yae f f e c t i v en e t w o r kp l a t f o r mf o r m a n a g i n ga n ds h a r i n gd a t ai ni n t e m e te n v i r o n m e n t t h et h e s i sd e s i g n e da ni m p l e m e n t a t i o n m e c h i s mo fp 2 pd a t a b s eb a s e do nd h t 巾i s t r i b u t e dh a s ht a b l e ) p 2 pn e t w o r k d h t - b a s e dp 2 pn e t w o r kh a sr o b u s t n e s s ，a d a p t i v e ，a v a i l a b i l i t ya n dl o a d - b a l a n c eb u ti tl a c k s m e t h o d so fd e s c r i p t i o na n dm a n a g e m e n to fc o m p l e xs e m a n t i c sd a t a ，a n ds u p p l i e so n l ye x a c t m a c h q u e r yb a s e so nk e y w o r d s a tf i r s t ，t h et h e s i sa n a l y s e dt h ed i s t r i b u t e dd a t a b a s es y s t e mt e c h n o l o g i e s ，a n dc o m p a r ei tw i t h p 2 en e x t ，w ea n a l y s e dt h ep 2 pt h r e ek i n d so fa r c h i t e c t u r e s ，a n dr e s e a r c h e do nt h ec l a s s i cp 2 p d a t am a n a g e m e n ts y s t e mf r o mn e t w o r kt o p l o g y , a r c h i t e c t u r e ，d a t ar e p l i c a ，e t c b a s e do na l la b o v e ， w ep r o p o s e da ni m p l e m e n t a t i o nm e c h i s mo fp 2 pd a t a b s eb a s e do nd h t - b a s e dp 2 pn e t w o r k t h er e p l i c ap l a c e m e n t ，r e s o u r e si n d e xa n dl o c a t i o nm e c h a n i s mo fc o m p l e xs e m a n t i c sd a t ai s t h ec o r eo fp 2 pd a t a b a s e i nt h i sp a p e r ，ar e p l i c ap l a c e m e n ts t r a t e g ya n dam e c h a n i s mo fd a t a i n d e x a n dr e s o u r c e sl o c a t i o ni np 2 pd a t a b a s ew a sp r e s e n t e d ，w h i c hm a i n t a i n e dc o m p l e x s e m a n t i c sd a t a r e p r e s e n t a t i o n d a t ar e p l i c a sp l a c e do i lo t h e r p 2 pn o d e s i m p r o v e d t h e f a u l t t o l e r a n c ea n da v a i l a b i l i t y ad i s t r i b u t e dh i e r a r c h i c a li n d e xm e c h a n i s mw a sp r o p o s e d ，b y w h i c ht h es y s t e mc o u l dl o c a t er e s o u r c e se f f e c t i v e l ya n ds u p p o s e dc o m p l e xq u e r i e s t h e m e c h a n i s mo fr e s o u r c e sl o c a t i o nb a s e do nd h tc o u l db r i d g eag a pb e t w e e nd h tp 2 pa n d c o m p l e xs e m a n t i c sd a t am a n a g e m e n t ag r o u po fp e e r sw h i c hh a v et i g h e rr e l a t i o n s h i pa n de x c h a n g ed a t af r e q u e n t l yw o u l db e c o m p o s e di n t oai n t r e s tg r o u p c o o r d i n a t i o nr u l e sw e r ep r o p o s e d ，b yw h i c hp e e r sc o u l de x c h a n g e a n ds h a r ed a t ad y n a m i c l y b a s e do nh i e r a r c h i c a li n d e xa n dd h t - b a s e dp 2 pr o u t i n ga l g o r i t h m s ，ar e s o u r c e sl o c a t i o n m e t h o dw a sd e s i g n e dt ol o c a t ed a t a ( r e l a t i o nt a b l e ) a n dr e s o u r c e sr e q u e s t e db yu s e r k e y w o r d s ：p 2 pd a t a b a s e ，r e s o u r c e sl o c a t i o n ，d a t ar e p l i c a ，h i e r a r c h i c a li n d e x 第一章引言 1 1 研究背景 自上世纪7 0 年代后期以来，分布式数据库一直是数据库领域研究的熟点，也是发展比 较迅速的领域。早期分布式数据库技术，如半联接( s e m i - j o i n ) 、时间戳( t i m es t a m p ) 、分 布式目录等等对d d b s 领域的研究和开发产生了非常深远的影响。 i n t e r n e t 的出现，使得数据管理和共享不仅仅局限于某个有限的局部地理空间，人们 迫切要求在广域网范围内实现数据管理和信息共享。传统的分布式数据库技术需要和 i n t e r n e t 和分布式计算模型相结合，朝广域网方向发展。 p 2 p 网络是一种分布式网络，网络的参与者共享它们拥有的一部分硬件资源( 处理能力、 存储能力等) 和数据资源，这些共享资源能被其它对等节点直接访问而无需经过中间实体， 每一个节点既是资源( 服务和内容) 提供者，又是资源( 服务和内容) 获取者。p 2 p 覆盖网 络具有非中心化( d e c e n t r a l i z a t i o n ) 可扩展性( s c a l a b i l i t y ) 容错性( f a i l u r e - t o l e r a n c e ) 和负载平衡( l o a d b a l a n c e ) 等优点。主要应用领域有：分布式存储应用、分布式科学计算， 数据管理、文件共享和即时通信等等。 p e e r - t o p e e r ( p 2 p ) 环境下的数据管理和共享是数据库领域的研究热点，焦点问题集中 在如何寻找高效的p 2 p 结构，并使之支持复杂的数据管理功能。t a p e s t r y “，c h o r d 2 i ，c a n d j ，“ 和p a s t r y 4 1 等基于分布式散列表( d h t ：d i s t r i b u t e dh a s h t a b l e ) 的结构化p 2 p 网络能够自 适应结点的动态加入退出，有着良好的可扩展性、鲁棒性、结点i d 分配的均匀性和自组织 能力。但是，d h t 在保证查询的精确性的同时，因为h a s h 函数的特点，使得数据语义完全 丧失。因而现在的基于d h t 的p 2 p 网络多数仅仅支持关键字匹配查询，并且缺少复杂语义数 据的表示手段。 传统的分布式数据库系统研究的主要课题是：事务，分布式查询优化异构数据源的互 操作和节点的可靠性等，系统中节点和数据的位置一般是固定的。由于它具有的复杂性和l 不 灵活性，系统的规模受到限制，在处理大规模应用时力不从心。而在p 2 p 系统中数据模型和 查询语言简单，节点可以自由离开和加入，数据的位置往往是不固定的，它只执行本地修 改。这样的特点使得p 2 p 系统没有复杂的事务概念，没有复杂的查询优化，网络分割对系统 没有影响，容易执行异构数据源的互操作，因此，它具有灵活性和简单性，这正是p 2 p 系统处理大规模应用的魅力所在。 1 2 国内外研究现状 国外，对p 2 p 研究起步较早，并且提出了一些p 2 p 网络模型，如：以n a p s t e r 2 ”， g n u t e l l a 2 “，c a n ，c h o r d ，p a s t r y , t a p e s t r y 等。在这些网络模型的基础上，开发了如，文件 共享、 开展了 我国对p 2 p 研究起步较晚，例如北京大学网络实验室开发了m a z e 系统，主要应用是文 件共享；清华大学开发的g r a n a r y 分布式存储系统。可以看出我国对p 2 p 领域的研究和国外 相比有一定的差距。我们的课题目标是利用p 2 p 网络作为基础网络模型，来研究复杂数据的 在i n t e r n e t 广域网中的管理问题，该领域具有较高的科研价值和应用前景。 1 2 本课题的研究方向 尽管p 2 p 已经成功应用于文件共享领域它们，如g n u t e l l a 、n a p s t e r 、b i t t o r r e 等系统， 这些系统仅仅只要对整个文件进行管理，不需要提供复杂数据类型的语义联系，也缺乏复杂 数据管理能力。如关系结构数据，它们只支持基于关键字的简单查询，几乎不支持基于内容 的复杂查询。尽管有些p 2 p 数据管理系统具有复杂数据的管理功能，但是他们是基于带有 超级节点的混合网络模型，这种拓扑结构过分依赖于超级节点，有悖于p 2 p 的初衷。 本课题的主要目的是研究在p 2 p 分布式网络环境中，如何来管理复杂数据。首先，我 们研究一些典型的p 2 p 数据管理系统，如，p i e r i s , 1 6 ，e d u t e l l a i “】，p e e r d b l 5 , q 等等，主要 这种分析他们的p 2 p 覆盖网络，数据分布策略、查询处理等等方面。 在此基础上，以结构化d h t p 2 p 网络作为i n t e r n e t 分布式平台，讨论广域网环境下的结 构化数据管理问题，同时要保持数据语义间的联系，避免了h a s h 对数据语义的破坏；对数 据使用规则进行分割，并复制到网络中去，提高系统的可靠性和并行性；提出一种分层索引 机制使得数据请求节点可以高效的资源定位；利用协调规则来协调局部数据库之间的自动数 据交换。本文主要从体系结构、p 2 p 结构、数据复制、分层索引机制、查询处理等几个方面 说明我们的系统。 1 3 本文组织结构 本文以p 2 p 分布式数据库实现机制展开论述，本为分五个章节，各部分的内容如下： 第一章引言：讲述本文的研究背景、p 2 p 技术和p 2 p 数据管理国内外研究现状，以及 有待于解决的问题，本文要研究的主要研究方向和创新点。 第二章分布式数据库技术：对分布式数据库技术做简要的介绍；对分布式数据库扩展 形成的多数据库系统、虚拟数据库、信息集成等等做简要的概述。 第三章p 2 p 结构和p 2 p 数据管理系统：介绍p 2 p 的基本概念、p 2 p 特点：分析典型p 2 p 2 数据管理系统的体系结构、查询处理和资源定位方式。 第四章p 2 p 数据库系统：本章是本文的创新点。我们主要从p 2 p 数据库的定义、体系 结构、数据复制和数据放置策略、分层索引机制和查询处理来探讨系统的实现机制。 第五章系统模拟实验。 第六章总结和展望。 3 第二章分布式数据库技术 分布式数据库系统是在应用的驱动下，是网络技术和数据库技术结合的产物。自上世纪 7 0 年代后期以来，分布式数据库一直是数据库领域研究的热点，也是发展比较迅速的领域。 世界上第一个分布式数据库系统s d d l 是由美国计算机公司( c c a ) 于1 9 7 9 年在d e c 计 算机上实现，该项目的研究成果，如半连接( s e m i - j o i n ) 查询优化、时间戳( t i m es t a m p ) 、 分布式目录等等对d d b s 领域的研究和开发产生了非常深远的影响。此外还有一些比较有 影响的d d b s 系统，如d i s t r i b u t e di n g r e s ，s y s t e m 胁p o r e l 和c - p o r e l 等等。 2 1 分布式数据库技术 2 1 1 复制管理 复制是指在分布式数据库中存储一个关系r ，系统维护r 的几个完全相同的副本( 拷贝) ， 各个副本存储在不同的节点上。与复制相对的方式是只存储关系r 的一个拷贝。数据复制是 提高分布式系统可用性和可靠性的一项关键技术，将同一个数据对象复制成多个副本存放在 不同的场地，用户的读写请求可在多个场地得到满足，从而提高了系统的性能；此外，数据 复制增强了系统的容错能力，提高了系统的可靠性。复制带来的主要问题是数据的一致性问 题，为了保证多个副本之间的一致性，需要提供复杂的副本控制机制，因而增加了系统的开 销和复杂性。 复制根据更新传播方式分为两类：同步复制和异步复制。同步复制( 紧密一致性) 是事务 执行的一部分，每个更新操作都要同步传播到包含副本的其它节点上，在事务提交时，所有 副本的更新一起提交。异步复制( 松散一致性) 提供了另外一种机制，首先提交原始节点复本 的修改操作，然后把修改传播到其它复本上，如果某一副本不可用，则该修改将被保存起来 等待下一次传播，可用复本则快速地执行复制操作，只需几秒钟时间。如果原始副本修改己 提交且存在未修改的某副本，即该副本和原始副本不一致，这也会导致数据库操作失败。 同步复制协议主要包括r o w a ( r e a d - o n ew r i t e - a l l ：读一，写全部) 及2 p c 协议。 主副本乐观复制是乐观复制方法的一种，在一个数据项的所有副本中，存在一个主副本， 其它所有副本称为次副本。对主副本可以执行读和写操作，但对次副本只能执行读操作。事 务分为查询事务、修改事务和刷新事务；修改事务是指包含对主副本进行修改的事务；刷新 事务是指对应的修改事务在次副本上进行更新传播的事务，由一组修改组成。 复制服务器也是经常使用的一种异步复制方式，s y b a s e 数据库系统就是使用这种方式支 持分布式服务。这一模型中，修改只能在主复本上进行，然后复制给次复本，也就是，主复 4 本节点上的数据修改操作提交后，才传送到次复本的节点上去。 2 1 2 查询优化 联接操作是数据库的各种操作中代价最大的，特别在分布式数据库中，参加联结的多个 关系可能处在不同的场地上，联接的执行次序不同将导致联结操作的代价有很大的差别。因 此，对联接操作进行查询优化是查询处理所要考虑的首要问题，以便决定合适的操作执行次 序以取得较小的代价。 为了减少执行联接操作时，节点之间的数据传输量，通常使用半联接( s e m i - j o i n ) 查询技 术【1 9 】。所谓半联接程序，是用半联接技术实现联接操作，也就是使用半联接和联接操作序 列来实现等值联接操作，即： 尺禺s 咎( 尺篇丌) 篇s 或r 禺s ( s 篙7 r 算) 器r 半联接操作对操作数r 或s 有缩减作用，且由于其不对称性各自缩减的程度不一样。半联 接操作的缩减性与在联接操作前对操作数关系做选择和投影有相似的效果。特别在分布式环 境中，可用半联接操作减少网上数据的传输量。 a h y 算法f 2 4 】( 由a p e r s ，h e v n e by a o 提出) 也是利用半联接技术来降低响应时间和总体 开销。对于一个全局查询，a h y 算法首先执行查询中的局部操作；然后将其分解为若干简 单查询，并为这些简单查询生成使用半联接操作的查询优化策略，最后，将这些分散的查询 策略综合一个完整的查洵策略。 2 2 多数据库系统 至今数据库没有也不可能形成统一的标准，数据库研究者先后提出了基于各种数据模型 的数据库系统，并在它们之上建立了大量的应用程序。随着网络的发展和信息共享的需求， 一些应用需要访问分布到不同数据库系统之间的、在不同结点上的数据。由于不同的数据库 系统具有不同的体系结构、数据模型、数据模式、用户接口语言和事务处理策略，要实现在 这些系统之间互操作或集成显然不是件容易的事。为了解决这一难题，一些数据库研究人员 提出过多种方案，如数据转移、中介信关、公共数据协议等，联邦数据库系统、全局模式多 数据库系统、互操作系统和多数据库系统等都是在这样的背景下产生的。 多数据库系统( m u l t i d a t a b a s es y s t e m ，m d b s ) 是在已经存在的多个异构数据库的基础 上构造一个相互协调的分布式软件系统，以支持对多个异构数据库的透明访问和互操作。一 个 i d b s 是由一组分散到网络上的、独立的局部数据库组成，并在这些数据库之上为用户建 立一个统一的存取数据的环境，使得用户像使用一个统一的数据库系统一样。 m d b s 除具有传统分布数据库系统的共同特性外，还具有已存性、自治性和异构性。多 5 数据库系统中的各个数据库被称为参与数据库，已存性是指各参与数据库在建立m d b s 之前 就已经存在。自治性是指各参与数据库系统具有控制的自主性、操作的独立性等。异构性包 括环境的异构和数据的异构环境的异构指各参与数据库系统具有不同的计算机硬件、操作 系统、网络平台和数据库管理系统：数据的异构包括数据模式和数据定义的异构。多数据库 系统可以屏蔽底层数据库系统的这些差异。 多数据库系统体系结构( 图表2 1 ) 分为两个层次：多数据库系统层和局部系统层。局 部系统层由参与m d b s 的诸局部数据库系统( l o c a ld a t a b a s es y s t e m ，l d b s ) 组成，其中 l i s ，表示l d b s t 的内部模式，l c s t 表示l i s - 对应的概念模式，l e s t j 是l d b s t 提供给局部系统用 户的外部视图。 多数据库系统层集成参与的诸l d b s 的局部概念模式l c s ，得到全局概念模式或全局视 图g c s 。g c s 是在局部概念模式之上增加的一层，它提供了额外的数据独立性。g c s 与传统 d d b 的分布式全局概念模式是不一样的，它不强迫局部系统去遵守任何类型的标准模式设 计，也不改变局部模式。为了使用方便，多数据库系统层还根据应用和用户的需要在全局视 图上面定义了全局外部视图g e s 。多数据库系统层和局部系统层之间通过通信网络和分布式 计算平台进行交互和通信。 多数据库系统层是整个系统的核心，它负责管理全局数据库系统的控制信息，包括全局 模式、全局事务处理和全局查询等。它负责接收用户的查询请求，根据相应的模式集成信息， 将它分解成多个l d b s 能接受的局部查询请求，然后传给相应的l d b s ，获得查询结果后将所 有这些局部查询结果集成并转换成全局请求要求的表示形式，返回给用户。 图表2 1 多数据库系统体系结构 为了解决多个异构数据库之间的互操作问题，多数据库系统给用户提供一个虚拟的全局 模式，模式集成的目的是将一组不同的l c s 模式转化成一个统一的全局模式g c s 。模式集成 的困难是各模式之间结构和语义上存在很大的区别，这主要是已有的l d b s 是按不同的模式 和方法构建的，或者允许设计者们采用自己喜爱的方式来构建新的l d b s 。 多数据库系统和p 2 p 数据管理最大的不同在于：多数据库系统向用户提供全局概念模 式，供用户透明的访问整个系统中的数据资源；而p 2 p 数据管理系统没有一个全局概念模 式，需要整合p 2 p 模型、协调规则来和资源定位方法来达到数据共享的目的。 2 3 信息集成系统 传统的分布式数据库技术可以满足现在的大多数应用，但是随着i n t e r n e t 的出现，带来 了一些新的应用，并且使得系统中服务器和客户端的数目不断增加。在这种环境中，传统的 分布式查询处理方法变得低效。信息集成技术主要研究在i n t e r n e t 环境中为用户提供透明 的数据服务。 由于多数据库或联邦数据库的解决方案是将所有的局部模式一次集成为一个单一静态 的全局模式，具有难以加入新的数据源、难以满足集成用户的多视角要求等缺陷，从9 0 年 代起，国际上提出了异构数据源集成系统的1 3 解决方案( i n t e l l i g e n ti n f o r m a t i o ni n t e g r a t i o n ) 这种解决方案采取三层软件结构，最上层是应用，中间层称为”协调器”，用以冲突消解和执 行查询，下层称为”包装器”，用以封装和转化局部数据源。从9 0 年代起，国际上的多数据 源集成系统多采取1 3 框架，著名的有s t a n f o r d 大学的t s i m m i s i ”】，i b m 公司的g a r l i c 2 6 1 ， 法国i n r i a 研究所的d i s c o 等。由于异构数据源集成系统还有一些难题尚未完全解决( 如 语义冲突的消解，查询优化等) 。 2 4 虚拟数据库技术【2 7 1 互联网的普及使得数据量迅猛增长。对企业，组织和个人( 为方便计，下面只提及企业) 有用的大量数据散布在互联网或内部网( 为方便计，下面只提及互联网) 上的成千上万的节 点中。这些数据源的数据组织方式、使用的符号集以及数据的存取和查询机制都是不尽相同 的，其中很多甚至不支持传统的询问操作，混入了这些数据源的写操作更是一项复杂的任务， 通常是不可能实现的，这些区别也为数据源的集成带来了困难。如何有效的利用这些巨量分 布的异构的数据源为企业服务，成了计算机工作者关注的课题。传统的d d b 技术不能给出满 意的答案，上个世纪九十年代虚拟数据库v d b ( v i r t u a ld a t a b a s e ) 技术应运而生。 v d b 技术的实质是就是要实现对分布在互联网中的各种数据源的透明访问，v d b 技术 收集、组织并集成来自互联网中的各种不同数据源的数据，将企业需要的互联网上的数据转 化成一个规范的数据库，使之成为企业关系数据库的扩充，为企业提供优质的服务。v d b 技术为应用程序员提供了统一规范的r d b 的数据表示，方便应用程序对散布在备类原始数 据源中的数据进行访问。如果数据库是集合 ，那么虚拟数据库是集台 ，其中m a p p i n g 是虚拟数据库中的s c h e m a 向数据库库中s c h e m a 的 映射，虚拟数据库中不存储数据，仅仅为应用层提供访问多个数据库的单一全局视图。 7 v d b 技术与现在人们常说的对异构数据库的访问既有联系又有区别。一方面，v d b 需 要实现对异构数据库的访问，将访问请求分解到各个不同的数据库中去，再将返回的结果进 行整合，这就要求v d b 技术具有各种异构型数据库的全部知识和相应的处理能力。另方 面，v d b 技术要具各网络资源的访问能力和分布异构数据源的集成和处理能力，这就要求 v d b 与外部数据源进行交互的中间接口拥有较高的工作效率，否则用户将忍耐漫长的等待。 2 5 数据网格 网格是把整个网络整合成一个虚拟的巨大的超级计算环境，实现计算资源、存储资源、 数据资源、信息资源、知识资源和专家资源的全面共享。网格被誉为下一代i n t e r n e t ，数据 库技术和网格技术相结合产生网格数据库，我们认为它是分布式数据库的一种，因为，使用 数据集成技术向用户提供一个虚拟数据库( v i r t u a ld b ：w 3 d ) ，用户感觉不到数据的物理来 源，另外，网格是一种分布式计算系统为之提供了一个良好的分布式环境。网格数据库管理 系统的体系结构可以简单描述如图2 2 ，目标是构造一个中间件，用于网格环境中对数据的 存取和集成，向用户提供一个虚拟数据库。 翌至 图表2 2 网格数据库结构 开放式网格服务体系结构( o p e ng r i d s e r v i c e sa r c h i t e c t u r e ：o g s a ) ：请参阅： h t t p ：w w w g l o b u s o r g o g s l 价是利用w e bs e r v i c e s 技术并且对其进行扩展来提供网格服务。 全球网格论坛( g l o b a lg r i df o r u m ：g g c ) 的d a i s ( d a t a b a s ea c c e s sa n di n m g r a t i o ns e r v i c e s ： d a i s ) i 作组开发的o g s a - d a i 中间件( 请参阅：丝p ；! 型坐q 9 1 4 d 吐q 蜡：! k o 用于网格环境中 对数据的存取和集成，是d a i s 工作组制定的网格数据库服务标准草案的一个参考。基于 o g s a - d a i 的o p e ng r i ds e r v i c e sa r c h i t e c t u r e - d i s t r i b u t e dq u e r yp r o c e s s o r ( i o g s a - d q p ) ( 请 参阅：h t t p ：w w w o g s a d a i o r gu k d q p ) 已经开发出来，利用它可以在网格环境建立进行分布 式查询处理。 8 一b；j ：_ ：| | 一 一= f 肖虱百 7 一5 一 百 2 6 本章小结： 传统分布式数据库系统为用户透明的访问数据提供了底层封装，注重严格的数据的 a c i d 特性实现；信息集成、虚拟数据和数据网格是对分布式数据系统的扩展。i n t e m e t 环境 下，当数据请求节点往往巨大，这要求系统具有良好的可扩张性，这恰恰是传统的分布式数 据库的弱点。尽管，信息集成、虚拟数据和数据网格基于i n t e r n e t 环境，但是这些系统往往 要求系统提供全局视图，这在动态i n t e r n e t 环境下往往是不现实的。 9 第三章p 2 p 结构和p 2 p 数据管理 3 1p 2 p 简介 在广域网应用中，人们希望可充分利用遍布全球的个人闲置资源，来完成单台计算机无 法胜任的任务。p 2 p 计算是一种分布计算模型，充分利用网络边界闲置资源( 包括存储资源、 c p u 、数据等等) ，在这种模型中参与的每个结点没有c 1 i e n t 和s e r v e r 之分，既分享其它结 点的资源，同时也为其它结点提供资源，也就是说每个结点是对等的，如图3 1 。 图表3 1p 2 p 结构 p 2 p 打破了传统的c l i e n t s e r v e r ( c s ) 模式，在网络中的每个结点的地位都是对等的。每 个结点既充当服务器，为其他结点提供服务，同时也享用其他结点提供的服务。 网络中不存在中心控制节点，数据和服务分散到网络中去，信息的传输和服务的实现都 直接在结点之间进行，可以无需中间环节和服务器的介入，避免了集中式服务器资源限制的 瓶颈。随着用户的加入，不仅服务的需求增加了，系统整体的资源和服务能力也在同步地扩 充，理论上其可扩展性几乎可以认为是无限的。由于服务是分散在各个结点之间进行的，部 分结点或网络遭到破坏对其它部分的影响很小。p 2 p 网络一般在部分结点失效时能够自动调 整拓扑结构，保持其它结点的连通性。每个节点既是服务器又是客户机，减少了对传统c s 结构服务器计算能力、存储能力的要求，同时因为资源分布在多个节点，更好的实现了整个 网络的负载均衡。 与传统的分布式系统相比，p 2 p 技术具有无可比拟的优势。同时，p 2 p 技术具有广阔的 应用前景。 3 2p 2 p 网络拓扑结构 拓扑结构是指分布式系统中各个计算单元之问的物理或逻辑的互联关系，结点之间的拓 扑结构一直是确定系统类型的重要依据。目前互联网络中广泛使用集中式、层次式等拓扑结 构，i n t e m e 本身是世界上最大的非集中式的互联网络，但是九十年代所建立的一些网络应 1 0 j1ili，11ij，l11，1 用系统却是完全的集中式的系统、很多w e b 应用都是运行在集中式的服务器系统上。集中 式拓扑结构系统目前面临着过量存储负载、d o s 攻击等一些难以解决的问题。 p 2 p 系统一般要构造一个非集中式的拓扑结构，在构造过程中需要解决系统中所包含的 大量结点如何命名、组织以及确定结点的加入离开方式、出错恢复等问题。 根据拓扑结构的关系可以将p 2 p 研究分为4 种形式：中心化拓扑( c e n t r a l i z e d t o p o l o g y ) ： 全分布式非结构化拓扑( d e c e n t r a l i z e du n s t r u c t u r e dt o p o l o g y ) ：全分布式结构化拓扑 ( d e c e n t r a l i z e ds t r u c t u r e d t o p o l o g y ，也称作d h t 网络) 和半分布式拓扑( p a r t i a l l y d e c e n t r a l i z e dt o p o l o g y ) 。 3 2 1 中心化p 2 p 结构 中心化p 2 p 结构使用一个中心服务器来负责记录各结点要共享的数据索引信息。要注 意的是，数据或文件并不存储在中心服务器上，而是存储在各结点中，每一个结点对它将要 共享的数据或文件以及进行的通信负责，根据需要下载所需要的其他对等实体上的数据。这 种形式具有中心化的特点，但是它不同于传统意义上的c l i e n t s e r v e r 模式。中心化拓扑最大 的优点是维护简单发现效率高。由于资源的发现依赖中心化的目录系统，发现算法灵活高效 并能够实现复杂查询。其确定与传统客户机朋务器结构类似，容易造成单点故障，访问的 “热点”现象和法律等相关问题，这是第一代f 2 p 网络采用的结构模式，经典案例就是著 名的m p 3 共享软件n a p s t e r 。 图表3 。2 带中心索引节点p 2 p 结构 3 2 2 全分布非结构化p 2 p 全分布非结构化网络在重叠网络( o v e r l a y ) 采用了随机图的组织方式，面对网络的动 态变化体现了较好的容错能力，因此具有较好的可用性。同时可以支持复杂查询，如带有规 则表达式的多关键词查询，模糊查询等，最典型的案例是g n u t e l l a 。 图表3 3 非结构化p 2 p 结构 g n u t e l l a 是一个p 2 p 文件共享系统，它和n a p s t e r 最大的区别在于g n u t e l l a 是纯粹的p 2 p 系统，没有索引服务器，它采用了基于完全随机图的洪泛( f l o o d i n g ) 发现和随机转发( r a n d o m w a l k e r ) 机制。为了控制搜索消息的传输，通过t t l ( t i m et ol i v e ) 的减值来实现。 随着联网节点的不断增多，网络规模不断扩大，通过这种洪泛方式定位对等点的方法将造成 网络流量急剧增加，从而导致网络中部分低带宽节点因网络资源过载而失效。所以在初期的 g n u t e l l a 网络中，存在比较严重的分区，断链现象。也就是说，一个查询访问只能在网络 的很小一部分进行，因此网络的可扩展性不好。所以，解决g n u t e l l a 网络的可扩展性对该 网络的进一步发展至关重要。 3 2 3 带有超级结点p e e r - t o p e e r ( 混合式p 2 p ) 带有超级结点的p e e r - t o p e e r 在整体设计时充分考虑各方面的因素，在某些管理域内采 用集中式形式，而在管理域之间采用分布式形式，在设计思想和处理能力上都得到了进一步 的优化。各个结点将要共享的目录和文件信息发送到自己的超级结点。超级结点维护自己所 属的结点的共享文件信息。各结点查询时将请求发送到自己的超级结点，超级结点之间采用 消息机制来发送查询和查询结果。超级结点将查询结果和其他超级结点返回的查询结果返回 给查询结点。带有超级结点的p e e r - t o p e e r 结构是对于前两种结构的一种利弊权衡，结合了 两者的优点。 图表3 4 混合式p 2 p 结构 3 2 4 完全分布式结构化拓扑网络 另外，由于非结构化系统中的随机搜索造成的不可扩展性，大量的研究集中在如何构造 一个高度结构化的系统。目前研究的重点放在了如何有效地查找信息上，最新的成果都是基 于d h t 的分布式发现和路由算法。这些算法都避免了类似n a p s t e r 的中央服务器，也不是像 g n u t e l l a 那样基于广播进行查找，而是通过分布式散列函数，将输入的关键字惟一映射到 某个结点上，然后通过某些路由算法同该结点建立连接。 最新的研究成果体现在采用分布式散列表( d h t ) 的完全分布式结构化拓扑网络。 分布式散列表( d h t ) 实际上是一个由广域范围大量结点共同维护的巨大散列表。散列 表被分割成不连续的块，每个结点被分配给一个属于自己的散列块，并成为这个散列块的管 理者。d h t 的结点既是动态的结点数量也是巨大的，因此非中心化和原子自组织成为两个设 计的重要目标。通过散列函数，一个对象的名字或关键词被映射为1 2 8 位或1 6 0 位的散列值。 一个采用d h t 的系统内所有结点被映射到一个空间上2 0 ，n ，如果散列函数映射一个自位的 名字到一个散列值日，则有月2 3 三。 最近的研究集中在采用新的拓扑图构建重叠路由网络，以减少路由表容量和路由延时。 这些新的拓扑关系的基本原理是在d h t 表一维空间的基础上引入更多的拓扑结构图来反映 底层网络的结构。 d h t 类结构能够自适应结点的动态加入退出，有着良好的可扩展性、鲁棒性、结点i d 分配的均匀性和自组织能力。由于重叠网络采用了确定性拓扑结构，d h t 可以提供精确的发 现。只要目的结点存在于网络中d h t 总能发现它，发现的准确性得到了保证，最经典的案例 是t a p e s t r y ! “，c h o r d t 2 t ，c a n t 3 i ，和p a s t r y t ”。 在d h t 技术中，网络结点按照一定的方式分配一个唯一结点标识符( n o d ei d ) ，资源对 象通过散列运算产生一个唯一的资源标识符( o b j e c ti d ) ，且该资源将存储在结点i d 与之 相等或者相近的结点上。需要查找该资源时，采用同样的方法可定位到存储该资源的结点。 因此，c h o r d 的主要贡献是提出了一个分布式查找协议，该协议可将指定的关键字( k e y ) 映 射到对应的结点( n o d e ) 。 a t & ta c i r i 中心的c a n ( c o n t e n th d d r e s s a b l en e t w o r k s ) 项目独特之处在于采用多维 的标识符空间来实现分布式散列算法。c a n 将所有结点映射到一个n 维的笛卡尔空间中，并 为每个结点尽可能均匀的分配一块区域。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 1 3 个结点，系统维数为d ，则路由路径长度为0 ( n ) ，每结点维护的路由表信息和网络规模 无关为0 ( d ) 。 纯p e e r - t o p e e r 结构的问题是网络中的消息会随着时间的变化而迅速增多，使得网络负 载增加，容易产生洪泛式f f l o o d i n g ) 的广播查询，而且查询结果往往是不完全的。但是这种 结构的优点也是非常明显的，任何一个结点停机或者离开网络后不会对其他结点的查询产生 致命的影响，同时也没有任何结点成为查询的瓶颈。混合式p e e r - t o p e e r 结构和中心化p