（计算机应用技术专业论文）p2p数据库系统的协同查询策略.pdf

华中科技大学硕士学位论文 i 摘 要 p2p 数据库系统有着较高的可靠性，适于地域分散的集团、机关、银行等机构和 部门，有着广泛的用途和应用前景。p2p 数据库系统没有中心服务器，各数据库节点 具有对等性，相应的，其上数据查询也与传统数据库系统有很大区别。 p2p 数据库系统中既存在内容不同的异质异构数据库，也存在内容相同的同构镜 像数据库，论文将重点研究同构镜像数据库之间的协同查询问题。 与传统数据库系统相比，p2p数据库节点具有较高的对等性和动态性，可随时加 入和退出系统，进行协同查询，需重点考虑网络资源路由、节点实时性能、网络传输 延迟等问题。协同查询充分利用p2p网络并行处理的效率，通过将复杂的查询转化为 相对简单的多条查询子句，分发到同构镜像数据库节点执行并行查询，并在发起查询 的节点接收和合并子查询数据，可以提高查询的可靠性和效率。 论文重点探讨了协同查询关键技术，基于ms .net开发环境进行了各模块的设计 与实现：使用第三方编译工具antlr，生成编译器，解析sql查询语句；参考分布式数 据库的查询分解，利用真值表法将sql查询语句分解成为多个粒度相当且相互独立的 子查询语句的主析取范式形式；参考合同网协议的思想，建立实时、稳定的协作查询 网络，并以此为基础上，给出了子查询任务的按动态优先级分配策略；最后讨论结果 回收和合并策略，将最终查询结果提交给用户。 关键词：p2p 数据库，协同查询，查询分解，查询分配 华中科技大学硕士学位论文 ii abstract p2p database system，which has high reliability and a wide range of applications. it s suitable for groups, agencies, banks that are geographically dispersed. p2p database system has no central server, each node is uniform. so, there are considerable differences between p2p database system and traditional database system in query processing. there are lots of isomerous and isomorphic databases in the network. the paper focus on the collaboration query basing on isomorphic database system. comparing with the traditional database, p2p database nodes are much more uniform and dynamic，they can enter and exit system at any time. for doing collaboration query on isomorphic database system, we should pay more attention to issues such as resource routing in networks, node s real- time performance, and transmission delay. collaboration query takes full advantage of parallel processing efficiency, turns complex query into simple sub- queries, and then executes those sub- queries in parallel. finally, the node which requests the query combines the results of sub- queries. collaboration query can significantly improve the reliability and efficiency of query processing. the paper devotes ourselves to do research on the collaboration query, designs and realizes each part using ms.net: parsing the sql using antlr which is a tool for generating compiler; decomposing query into sub- queries which are analogous and unattached; reference to the contract net protocol, establishing a reel- time and steady collaboration networks, and then discussing dynamic priority distribution strategy of sub- queries; researching the results combination, and finally submitting the result to users. key words: p2p datebase, collaboration query, query decomposition, task distribution 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中 以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密 ，在_年解密后适用本授权书。 本论文属于 不保密。 （请在以上方框内打“”） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 华中科技大学硕士学位论文 1 1 绪论 1.1 课题研究背景与意义 p 2 p即对等网络或对等计算，在 p 2 p网络环境中，所有节点在功能上是对等的， 每个节点即能请求获得网络服务，也能响应其他节点的请求，提供资源与服务12。 p 2 p系统没有服务器瓶颈，系统更加稳定可靠，可扩展性强，资源利用更充分，有利 于解决分布式问题。目前 p 2 p 技术应用绝大部分是基于文件系统的，基于数据库的应 用研究才刚刚起步。将分布式数据库的每个单独的数据库称为数据节点，则可以将分 布式数据库看成一个由多个数据节点组成的大型软件系统。按照 p 2 p 的思想来构建这 些数据节点的关系，即使节点间的数据服务是对等的，这样就构成一种全新的体系结 构p 2 p 数据库系统。 p 2 p数据库系统在信息共享、信息加工、信息搜索等方面有着广泛的用途，符合 当今信息系统应用的需求，符合当今企业组织的管理思想和管理方式。尤其适合那些 地域上分散的大集团、大机关、大企业、银行、连锁店、保险业、各类交通运输业、 以及全国性管理机构和军事国防部门等等。在这些组织中往往即要有各部门的局部控 制和分散管理，也需要有整个组织的全局控制和协同工作，这就要求各部门的信息即 能够灵活的交流和共享，又能全局控制和使用3。 查询是数据库系统的关键问题，目前国内外对分布式数据库查询处理技术研究比 较多，提出了很多经典的查询分解和优化策略，但是p 2 p 环境下的查询研究相对较少， p 2 p 数据库系统是一个分散、动态的系统，不存在中心控制节点，节点可以随意加入 和退出网络，因此原来分布式数据库的一些查询处理技术已不再适应p 2 p 数据库系统， 需要新的技术来适应p 2 p 的挑战。 本课题来自湖北省自然科学基金项目： 数据库知识发现基于p 2 p 的查询分解研究。 课题主要研究怎样将 p 2 p 技术的优势更有效的应用到分布式数据库结构中，建立一种 新的体系结构，如何有效的组织网络中的数据库节点，建立协作网络，将一个 p 2 p 数 据库上的全局查询分解为多个数据库节点上的有效的局部查询，多点协同完成用户的 查询请求，希望能有新的发现。 华中科技大学硕士学位论文 2 1.2 课题国内外研究现状 与传统的分布式系统相比，p 2 p具有无可比拟的技术优势和更广阔的应用前景。 i n t e r n e t上各种 p 2 p应用软件层出不穷，用户数量急剧增加。2 0 0 4年 3月来自 w w w . s l y c k . c o m的数据显示，大量 p 2 p软件的用户使用数量从几十万、几百万到上千 万，并且急剧增加，并给 i n t e r n e t 带宽带来巨大冲击。目前，p 2 p 计算技术正不断应 用到军事、商业、政府信息、通讯等领域4。p 2 p 技术主要应用有： (1) 信息资源共享 信息资源共享一直是网络技术发展的重要推动力，也是p2p技术中最典型的应用。 目前人们主要采用web技术来实现信息资源共享，在基于web方式进行信息资源共享 时，web server需要能够对大量用户的访问提供有效的服务，web server经常成为这 类系统的性能瓶颈5。p2p实现信息共享的主要目的是全面实现数据共享，使用者可 以直接从任意一台pc上检索、共享资源，而不是从服务器；用户自动发现最新的文件 列表，而不需担心发布的问题。采用这种方式来共享信息资源可以更充分地利用网络 中的带宽资源，提高系统数据通信的效率。如：freenet、 napster、gnutella、edonkey、 emule、maze、bt等等，这些研究均从不同的角度尝试解决目前网络中的信息资源共 享所存在的一些问题。 这些都是基于文件系统的， 本课题研究基于数据库的资源共享。 (2) 对等计算 人们一直在尝试通过并行技术、分布式技术将多个网络节点联合起来，利用闲散 计算资源来完成大规模的计算任务6。p2p计算技术研究的目标之一就是充分利用网 络中各种各样的计算单元来共同完成大规模的计算任务。单一计算单元的计算能力总 是有限的，而网络中计算机的计算能力一直未充分利用，人们期望能够充分利用网络 中的闲散计算能力来完成大规模的计算任务，这样将会使得网络中所蕴含的海量计算 能力得到更加充分的利用78。 在p2p系统中，每个对等点不再只是单纯地接收计算任务，它还可以根据自己的 情况（比如分到的任务太多）再搜索其他空闲节点把收到的任务分发下去。计算的中 间结果层层上传，最后到达任务分发节点，对等点之间可以直接交换中间结果，协作 计算9。就本质而言，对等计算即是实现网络上cpu资源共享。如berkeley大学启动的 对等计算的研究项目setihome10，有一百万台计算机参与分析在外星系文明研究。 (3) 协同工作 协同工作是指多个用户之间利用网络中的协同计算平台互相协同来共同完成计 算任务，共享信息资源等9。协同应用包括：实时通信、文件共享、聊天室、好友列 华中科技大学硕士学位论文 3 表等基本功能，用户可共享白板、协同设计、进行视频会议等7。groove11是基于 internet的p2p协同应用软件的典型代表。 企业通过运用p2p计算技术， 在没有中心服务器的环境下建造一个包含项目管理、 协同设计和制造等功能的协同应用平台7， 使个人和动态联盟组织可以随时建立在线、 非在线的协同应用环境。协同系统使得在不同地点的参与者可以在一起工作，文件直 接共享的方式可以保证系统中的每个人所获得的信息总是最新的，降低了对服务器存 储及性能的要求，网络的吞吐量和快速反应得到大幅度提高，节约了成本，提高了效 率，使低成本的协同工作成为可能。因此基于p2p技术的协同工作已受到大型企业的 极大重视。本课题将运用对等计算和协同工作技术来实现sql查询语句的高效执行。 (4) 实时通信技术 实时通信技术是网络中重要的通信技术，如典型的icq、oicq、msn messenger 等。从某种意义上说，实时通讯应用将超过文件共享应用，成为p2p网络技术的第一 大应用。p2p的实时通讯软件不仅可以随时知晓对方是否在线，而且交流双方的通讯 完全是点对点进行，不依赖服务器的性能和网络带宽，节点之间直接进行数据通信。 尽管目前的即时通讯技术一般都具有中心服务器，但中心服务器仅是用来控制用户的 认证信息，帮助完成节点之间的初始连接。 (5) 信息检索技术 搜索引擎是目前人们在网络中检索信息资源的主要工具12，目前的搜索引擎如 g o o g l e 、b a i d u 等都是集中式的搜索引擎，搜索模式是由一个机群在互联网上盲目读 取信息，然后按照某种算法根据关键字将信息保存在一个海量数据库内。用户提交的 搜索请求， 实际上是在海量数据库内部进行搜索。 这种机制虽然能尽快获得搜索结果， 但不能保证搜索范围的深度和结果的时效性。即使是g o o g l e 这个目前最出色的全中文 搜索引擎也只能搜索到2 0 % - 3 0 % 的网络资源14。在j x t a s e a r c h 13中认为采用p 2 p 的搜 索技术可以有效地跟踪数据的更新速度、提高访问的有效性以及检索的效率。 p 2 p 网络模式中节点之间的动态而又对等的互联关系使得搜索可以在对等点之间 直接、实时地进行，既可以保证搜索的实时性，又可以达到传统目录式搜索引擎无可 比拟的深度，理论上将包括网络上所有开放的信息资源。 从 p 2 p 的应用领域介绍可以看出，目前的 p 2 p 系统大部分只提供文件级的共享， 这类 p 2 p 系统共享粒度较大，缺乏数据管理能力，为了获取更小粒度的资源共享，p 2 p 技术和数据库技术相结合将是大势所趋。 在数据库技术和应用方面，国内国防科技大学的李海龙15进行了基于 x m l 的网格 环境下数据共享发布技术的研究，重点研究数据库共享与集成中的需求描述模式和交 华中科技大学硕士学位论文 4 互协议，提出了语义化 e - r 模式需求描述思想，采用 x m l 来描述共享和集成方案中的 交互协议。华南理工大学的莫长青16进行了可扩展的关系数据库存取标记语言研究， 填补了x m l 应用在s q l 方面的空白。 中国矿业大学的鲍宇等提出了基于树型结构的p 2 p 分布式数据库模型17。 华南理工大学提出的 p o w e r g a t e 模型系统是以数据库应用为基 础的网格软件，但在处理复杂 s q l 查询时存在一定问题18。 国外研究方面，较国内研究更进一步，其中新加坡国立大学和复旦大学联合开发 的p e e r d b 系统、r o c h e s t e r 大学与h p 实验室合作的p s e a r c h 系统比较具有代表性。 p e e r d b 和p s e a r c h 非别是基于非结构化p 2 p 网络研究和基于p 2 p 网络研究的代表。 p e e r d b 19是构建在b e s t p e e r20上的p 2 p 环境下的查询处理引擎。p e e r d b 假设节点 不知道统一的、全局的模式信息。每个p e e r d b 的节点包含一个本地的对象管理系统 ( o b j e c t m a n a g e m e n t s y s t e m ) 用以管理本地数据。关系的模式、关键词等元数据放在 本地字典( l o c a l d i c t i o n a r y ) 中，而其中的可共享部分被放在导出字典( e x p o r t d i c t i o n a r y ) 中。系统的查询功能是利用d b 代理( d b a g e n t ) 实现的。此外每个节点还有 一个缓存管理器( c a c h e m a n a g e r ) 实现缓存的存放和替换。 p e e r d b 使用了利用代理的查询处理方法( a g e n t - a s s i s t a n t q u e r y p r o c e s s i n g ) ， 在p e e r d b 中，每个节点有一个主代理( m a s t e r a g e n t ) 。该代理监控网络和系统的各种 统计信息，并管理用户查询，包括: 负责复制查询、向邻居节点发送工作代理( w o r k i n g a g e n t ) 、接收查询结果。当用户发出一个查询，查询在本地被解析，系统首先在本地 字典里查找相关的关系，并报告给用户，同时，系统( 主代理) 复制一个关系匹配代理 ( r e l a t i o n m a t c h i n g a g e n t ) ，将它发送到邻居节点，并等待结果。关系匹配代理将 在远程节点的导出字典中寻找相关的关系，并将这些关系的模式信息送回给发出查询 的节点。用户可以选择那些在本地或者远程找到的确与查询相关的关系。以上过程组 成了查询处理的第一阶段。在查询处理的第二阶段，对于每个用户选择的关系，系统 ( 主代理) 复制一个数据抽取代理( d a t a r e t r i e v a l a g e n t ) 。如果该关系在远程节点上， 那么代理将被发送到那个节点。在代理的生存期( t i m e - t o - l i v e ，或者t t l ) 到达以前， 代理将被继续复制并发送到其他邻居节点。数据抽取代理在到达的节点上利用本地的 查询引擎( 即对象管理系统) 执行s q l 查询。并将结果送回发出查询请求的节点。发出 查询的节点收到的所有结果将被主代理返回给用户。这样，整个查询处理过程就结束 了。 可以看出，p e e r d b 在一定程度上解决了 p 2 p 环境下的数据库共享。但p e e r d b 采 用的是一种不精确的搜索方法，而且仍然需要用户的干预。 p s e a r c h 系统21虽然没有使用分布式散列表，但是从网络构架上看p s e a r c h 属于 华中科技大学硕士学位论文 5 结构化p 2 p 网络。它是一种p 2 p 环境下基于c a n 路由策略的信息检索系统。p s e a r c h 利用 向量空间模型( v e c t o r s p a c e m o d e l ，v s m ) 和潜在语义索引( l a t e n t s e m a n t i c i n d e x i n g ，l s d ) ，将文档索引和查询不经过任何映射直接组织在迪卡尔空间中，表示 为向量形式；然后通过计算查询向量与文档索引向量之间的夹角作为查询与文档之间 的相似度；一个查询处理就是寻找与查询相似度大的文档。 在一般的p 2 p 网络中，文档分布是随机的，在进行相似查找时查询处理变得很复 杂。p s e a r c h 通过在网络中发布文档的潜在语义索引的方式，在整个网络中建立分布 式文档语义索引。索引的发布方式与c a n 网络数据放置类似。在p s e a r c h 系统中，将索 引向量作为虚拟迪卡尔空间中的坐标，按照坐标对应的空间位置将索引存放在相应的 节点上。p s e a r c h 也是一种不精确的搜索。 1.3 课题研究主要内容 p e e r d b 被设计为在非结构化p 2 p 环境下的数据共享与查询系统，而p s e a r c h 是建立 在结构化p 2 p 网络上的信息检索系统。p e e r d b 侧重于利用信息检索技术的近似查询处 理以及利用非结构化p 2 p 网络提供的节点的自组织和自配置功能增强查询处理效率的 研究；p s e a r c h 侧重于通过信息检索技术建立索引，然后在结构化p 2 p 网络中通过路由 表以及滚动索引提高查询效率及准确率22。 在系统网络结构方面，p e e r d b 和p s e a r c h 分别是基于非结构化和结构化p 2 p 的数据 库查询系统，它们不可避免的带有其网络结构的先天缺陷，p e e r d b 基于泛洪查找，路 由效率低，p s e a r c h 基于动态哈希d h t 技术，需要过多节点信息的维护；在查询策略方 面，两者都采用近似查询策略，是不精确的查询，且需要人为干预查询。 p e e r d b 和 p s e a r c h 都是基于异构数据库系统的，它们类似于文件系统，查询粒度 大，不考虑各数据库节点间的并行协同查询处理，查询的效率和可靠性得不到保证。 本课题在前人优秀理论和研究成果的基础上，将重点研究 p 2 p 同构镜像数据库环境下 的协同查询技术，依据 s q l 查询条件和数据库镜像资源性能，合理分解查询条件，分 配子查询任务，并行执行子查询，提高查询的效率，主要研究内容包括： ( 1 ) 探讨 s q l 查询语句的解析，确保用户提交的 s q l 语句的正确性和有效性； ( 2 ) 探讨 s q l查询语句的分解分配策略，将 s q l查询分解成多个子查询，让多个 节点并行执行，提高查询效率； ( 3 ) 探讨协同查询网络的建立，保证协作节点的实时有效性； ( 4 ) 探讨子查询结果的回收、合并策略，保证查询的正确性。 华中科技大学硕士学位论文 6 1.4 论文结构安排 本文从 p2p 数据库的研究现状和实际需求出发，对 p2p 技术、p2p 数据库模型、 sql 语句解析和分解、子查询分配、结果合并等方面进行分析和研究，给出了关键部 分的算法模拟，内容编排如下： 第一章绪论概括说明了课题研究背景、国内外研究现状、课题研究主要内容和论 文结构安排。 第二章探讨 p2p 技术与分布式数据库查询融合的可行性，并提出协同查询系统整 体设计思路。 第三章研究 p2p 数据库系统协同查询的设计，给出各模块的设计思想。 第四章研究 p2p 数据库系统协同查询的具体实现。 第五章总结本课题的研究成果，并对进一步的研究进行了展望。 最后是致谢和参考文献。 华中科技大学硕士学位论文 7 2 p2p 数据库系统协同查询相关理论与技术 2.1 p2p 数据库系统 2.1.1 p2p系统特点 最近几年，对等计算( p e e r - t o - p e e r ，简称 p 2 p ) 迅速成为计算机界关注的热门话 题之一，财富杂志更将 p 2 p 列为影响 i n t e r n e t 未来的四项科技之一。 目前，在学术界、工业界对于 p 2 p 没有一个统一的定义23，i n t e l 将 p 2 p 技术定 义为“通过系统间的直接交换达成计算机资源与信息的共享”，这些资源与服务包括 信息交换、处理器时钟、缓存和磁盘空间等。i b m则对 p 2 p赋予了更广阔的定义，把 它看成是由若干互联协作的计算机构成的系统并具备如下若干特性之一：系统依存于 边缘化（非中央式服务器）设备的主动协作，每个成员直接从其他成员而不是从服务 器的参与中受益；系统中成员同时扮演服务器与客户端的角色；系统应用的用户能够 意识到彼此的存在而构成一个虚拟或实际的群体。 与传统的 c / s 模式相比，p 2 p 模式具有如下优点6： ( 1 ) 资源的利用率高 在 p 2 p 网络上，闲散资源有机会得到利用，所有节点的资源总和构成了整个网络 的资源，整个网络可以被用作具有海量存储能力和巨大计算处理能力的超级计算机。 c / s 模式下，纵然客户端有大量的闲置资源，也无法被利用。 ( 2 ) 系统稳定性好 随着节点的增加，c / s 模式下，服务器的负载就越来越重，形成了系统的瓶颈， 一旦服务器崩溃，整个网络也随之瘫痪。而在 p 2 p 网络中，每一个对等点具有相同的 地位，既可以请求服务也可以提供服务（存储空间，c p u周期等） ，同时扮演着 c / s 模式中的服务器和客户端两个角色，因此对等点越多，网络的性能越好，网络随着规 模的增大而越发稳固。 p 2 p 的技术方式将导致信息数据成本资源向所有用户的 p c 均匀 分布，即“边缘化”趋势。 ( 3 ) 资源搜索方便 p 2 p 是基于内容的寻址方式24，基于内容的寻址方式处于一个更高的语义层次， 因为用户在搜索时只需指定具有实际意义的信息标识而不是物理地址，p 2 p软件将会 把用户的请求翻译成包含此信息标识的节点的实际地址，这个地址对用户来说是透明 的，每个标识对应包含这类信息的节点的集合。这将创造一个更加精炼的信息仓库和 华中科技大学硕士学位论文 8 一个更加统一的资源标识方法。 ( 4 ) 服务成本低 资源信息在网络各节点间直接流动，高速及时，不需要专用的昂贵的服务器，降 低了中转服务成本。 但是，p 2 p也有不足之处。首先，p 2 p不易于管理，而对 c / s 网络，只需在中心 点进行管理。随之而来的是 p 2 p 网络中数据的安全性难于保证。因此，在安全策略、 备份策略等方面，p 2 p的实现要复杂一些。另外，由于对等点可以随意地加入或退出 网络，会造成网络带宽和信息存在的不稳定。p 2 p技术与 c / s技术性能比较如表 2 . 1 所示25。 表 2.1 p 2 p 技术与 c / s 技术性能比较 p 2 p c / s 数据发布 好 差 数据接收 中 好 数据互动性 好 差 数据即时性（传输速度） 好 差 数据安全性 差 好 数据更新 好 差 数据质量（价值） 中 好 数据覆盖率和数量（价值） 差 好 数据成本控制 好 差 数据管理方便性 差 好 2.1.2 p2p数据库与分布式数据库系统 p 2 p数据库系统与原有的分布式数据库系统有很大的差异，主要表现在以下几个 方面： ( 1 ) 在 p 2 p 数据库系统中，节点可以动态的加入和离开系统，可扩展性好，而分 布式数据库系统的节点相对固定，且被全局数据库严格管理，不能随意加入 和离开。 ( 2 ) 在 p 2 p 数据库系统中，没有统一的全局模式，能很好的反映节点数据变化情 况，动态性好，而分布式数据库需要一个全局数据库来控制和管理各节点数 华中科技大学硕士学位论文 9 据，每个节点数据变化需通知全局数据库, 全局数据库负担过重且存在单点 失效的问题。 ( 3 ) 在 p 2 p 数据库系统中，数据存放的位置是不固定、不可预知的，当有查询任 务时，需要实时的在网络上路由搜索，而在分布式数据库中数据的位置一般 是固定的，全局数据库事先知道各数据存放的具体位置。 2.1.3 p2p数据库系统网络拓扑模型 p 2 p数据库系统的可用性依赖于对数据的高效查找和提取方法，如何高效快速的 定位 p 2 p 网络上的资源是 p 2 p 系统实现最关键的问题。按照资源组织和定位方法，传 统 p 2 p 网络可分为非结构 p 2 p 网络和有结构 p 2 p 网络26，非结构p 2 p 网络是基于泛洪 搜索, 搜索较慢而且消耗大量的资源，扩展性较差27。结构化 p 2 p网络是基于分布式 哈希表（d i s t r i b u t e d h a s h t a b l e s , d h t ）的，搜索速度快，产生的查询消息少，资 源消耗少28- 31，但有结构网络中的节点在加入和离开网络时需要进行修复操作，由此 产生大量的消息，因此有结构的网络不适合高度动态的网络环境。这些结构各有不同 的特点，下文将分别介绍这些结构，并分析各自优缺点，进而引出改进的适合协同查 询的网络结构。 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 结构连接起来。混合式结构在控制层面引入了两层：一层是普通 华中科技大学硕士学位论文 10 对等体通过客户机/ 服务器模式连接到超级对等体； 另一层是这些超级节点通过纯 p 2 p 无结构网络连接到一起。 2 结构化 p 2 p 网络 结构化 p 2 p 网络使用文档路由模型，这是 p 2 p 网络最新的搜索方法。文件路由模 型需要用分布式哈希表（d i s t r i b u t e d h a s h t a b l e s ， d h t ） ，这是有结构 p 2 p 网络采 用的搜索方法，这也是有结构和无结构 p 2 p 网络的根本区别。在这种模型下，每个对 等体都有一个 i d 号，每个文件有一个关键字 k e y ，当发布一个关键字为 k 1 的文件时， 先通过哈希映射得到对应的 k 1 - i d 1 ，然后将该文件信息( 可以是文件本身的内容，或 者是文件的位置) 存到 i d 号为 i d 1 的节点，文件信息的存放过程需要将文件信息从当 前节点路由到目标节点 i d 1 。反过来，当查找一个关键字为 k 1 的文件信息时，先进行 哈希映射得到 k 1 - i d 1 ，然后将查找消息路由到 i d 1 节点，再将该文件信息从 i d 号为 i d 1 的节点上取到。 c a n 28，c h o r d29，p a s t r y30以及 t a p e s t r y31都属于这种结构化系统。结构化 p 2 p系统的一个优点就是在进行资源定位时，消息所经过的路径具有较少的跳数。无 结构 p 2 p网络在定位资源时需要泛洪查询消息，产生很多查询通信量。对于有结构 p 2 p ，如果系统的结点数为 n ，对于c h o r d ，p a s t r y 和 t a p e s t r y ，路由跳数为()no log， 而 c a n 的路由跳数为 d ndo 1 ，其中 d 是覆盖网络构成的虚拟坐标空间的维数。 3 p 2 p 数据库网络拓扑模型 本课题主要研究 p 2 p 数据库系统上的协同查询，相应的网络体系结构也与传统结 构的不一样。本文综合无结构和有结构网络的优点，采用适合协同查询的一种新 p 2 p 网络模型32- 35基于主题索引的双层 p 2 p模型( t o p i c - b a s e d s t r u c t u r e d p 2 p ， t s - p 2 p ) 。t s - p 2 p上层是基于主题的有结构网络，下层是无结构网络，既保证查询的 搜索效率，又兼顾网络的高动态性；通过多哈希函数改进资源发布策略，将资源映射 到多个上层节点，有效地解决了索引负载瓶颈和单点失效问题。 模型的上层是有结构主题索引节点（t o p i c p e e r ）t p ，下层是无结构的普通节点 （c o m m o n p e e r ）c p ，如图 2.1 所示。 上层主题索引节点 t p 构成有结构 c h o r d 网络，为下层 c p 节点提供索引服务，其 性能稳定且在线时间长，离开系统时要执行相应的修复程序。主题索引网络用 k e y 表 示节点提供的资源，k e y值表示数据库的特征即数据库名，l o c a t i o n ( k e y ，c p ) 表示 k e y 在 c p 上的位置信息。 普通纯对等节点 c p ，不负责节点的索引维护，可以自由加入和离开系统。c p提 华中科技大学硕士学位论文 11 供本地资源 k e y ，利用哈希函数将 k e y 映射到 t p 上，并将 k e y 和 l o c a t i o n ( k e y ，c p ) 存放到其索引表。 图 2.1 基于主题索引的双层 p 2 p 网络模型图 当新节点 cpi加入系统，或 cpi变更数据库资源时， cpi需向主题索引节点发布资 源。首先，cpi联系相邻的索引节点 tpm，计算 cpi提供的资源 key 的哈希值 hash(key)=id， 若网络上存在 node id等于 id 的主题索引节点 tpn， 则 tpm按上层 can 网 络 规 则 路 由 到tpn， 将key 及 位 置 存 放 到tpn的 索 引 表 中 ： topic- index(tpn)=topic- index(tpn)( key, location (key,cpi)|hash(key)=nodeid(tpn)；若网 络上没有 node id等于 id 的主题索引节点，则按 chord 规则将普通节点 cpi加入到上 层 索 引 网 络 中 ， 并 将 其 作 为 一 个 主 题 索 引 节 点 ， 建 立 自 己 的 索 引 表 topic- index(cpi)=(key，location(key，cpi) | hash(key)= nodeid(cpi)。 当有查询请求时，类似于资源发布过程，cpi联系与之相邻的主题索引节点 tpm， tpm通过查询请求的 key 得到 id=hash(key)，按 chord 规则路由到节点号等于 id 的 节点 tpn。找到主题索引节点 tpn之后，搜索本地索引表，找到符合查询条件的节点 集合 a=cpj| cpjtopic- index(tp)。将集合 a 返回给发起查询节点 cp，此后，cp 和目的节点直接通讯并交换数据。 资源节点 cp3 索引网络 资源节点 cp1资源节点 cp2 索引节点 tp1 下层普通节点 上层索引节点 chord tp4 tp3 tp2 cp5 cp4 华中科技大学硕士学位论文 12 与传统的混合模型相比，双层模型的主题索引节点不直接索引普通节点，只索引 通过哈希函数映射到其上的节点，混合模型的索引节点直接索引与之相邻的普通节 点。双层模型中，普通节点可运用多哈希函数映射到多个索引节点，而混合模型的普 通节点只映射到一个索引节点。 2.2 p2p 与分布式查询的融合 2.2.1 分布式数据库查询处理 分布式查询是用户与分布式数据库系统的接口，也是分布式数据库主要研究的问 题之一。分布式数据库基本上都采用关系数据模型，以非过程化语言( 如 s q l或其兼 容语言) 为主要用户接口语言，用户发出查询请求，只需表达自己想要的结果，系统 的查询处理模块负责以最低的代价得到正确的结果，并提交给用户。 在分布式环境下，查询可分为三种类型：局部查询，远程查询和全局查询。局部 查询是指在本机上执行查询，不涉及到网络交互；远程查询是查询网络上另一个节点 上存放的数据； 全局查询是涉及网络上的多个节点的查询。 所以在分布式查询处理中， 主要讨论远程查询和全局查询的处理，在这两类查询中，由于涉及远程节点和多个节 点的数据，必须进行节点间的数据传递，需要一定的通信费用。相应的三种查询的处 理策略也有所不同3。 1局部查询 局部查询只是涉及本地、单个节点上的数据，没有网络通信开销，所以查询处理 类似于单个节点上集中式的处理方式，不需特别处理。 2远程查询 远程查询也只涉及到单个节点上的数据，其查询处理跟局部查询相同，但是远程 查询还涉及到远程节点的选择，为了减少远程查询的通讯代价，因尽可能选择距离发 出查询节点最近的节点。 3全局查询 全局查询涉及多个节点的数据，其查询处理技术要复杂得多，是分布式数据库查 询的难点。为了执行全局查询并确定一个好的查询策略，需要很多判断和计算工作， 其查询处理模块的功能可以分六个层次: ( 1 ) 语句检查 首先要对用户输入的s q l 语句进行语法分析、完整性检查、授权检查等，保证输 入的s q l 语句的正确性和合理性； ( 2 ) 查询分解 华中科技大学硕士学位论文 13 将用户输入的s q l 查询语句翻译为一个定义在全局关系上的关系代数式或s q l 语 句，分解出多个子查询任务。该部分包括对关系代数表达式进行必要的优化； (3) 数据本地化 将全局关系上的查询进行具体化，为该查询所要访问的每一个关系和片段，认定 其一个或多个副本，让子查询落实到合适的站点上执行( 尽可能使查询本地化或最近 化) 。如果一个查询的每一个关系或片段，都只有一个副本，则称为非冗余具体化， 否则称为冗余具体化。对冗余具体化还需研究如何为每一个关系或片段选择他们的副 本，才能使查询代价最小，而结果正确。冗余具体化的目标是：通过冗余数据提高处 理的并行性和减少通讯费用； ( 4 ) 全局优化 全局优化目的是找出分处查询的最佳操作次序，使查询代价最小。主要是确定连 接和并操作的次序，其他操作的次序是不难确定的。例如选择和投影操作总是应尽可 能地提前执行。这个原则与集中式数据库所考虑的策略相同。但在分布式数据库系统 中涉及到的是在不同站点上关系的连接和并操作的次序，更必须认真考虑； ( 5 ) 局部优化 局部优化由参与共同查询的数据库本地执行，提高本机的查询执行速度； ( 6 ) 返回结果 当一个全局查询的各子查询执行完并得到结果，需要将结果返回给发起查询节 点，合并查询结果并提交给用户。 在分布式数据库系统中，常以两种不同的目标来考虑查询优化。一种目标是以完 成任务的总代价最小为标准，除了像集中式数据库系统一样考虑c p u 代价和i o 代价外， 总代价还包括数据通过网络传输的代价。另一种目标是以每个查询的响应时间最短为 标准，这一点在分布式数据库系统中具有重要的意义。因为分布式数据库系统由多台 计算机级成，数据的分布和冗余也增加了查询的并行处理的可能性，从而可以缩减查 询处理的响应时间，加快查询处理速度。查询优化要找到最佳方案是很难的，一般是 寻找相对较优的操作，一般采用多级优化，逐步求精的方案。通常分布式查询优化方 法包括关系代数操作的优化、分解定位的优化、存取路径的优化、连接操作的优化22： ( 1 ) 关系代数优化 关系代数操作的优化目标，是压缩不同的操作之间的信息转换量，它根据关系代 数的事先定好的一些等价变换规则对全局查询处理第一阶段产生的段查询树进行变 换。通过变换公式、剪枝操作、分组操作减少数据在节点间的流动，以达到优化的目 的。 华中科技大学硕士学位论文 14 ( 2 ) 分解定位优化 分解定位的优化方法又分为静态方法和动态方法。 静态方法是根据原有的信息量和对分布在系统中各站点的信息量进行统计， 预先 确定各操作执行的站点，而对于中间结果的信息量，则进行估计，这种方法的优点是 实现起来比较方便，它的不足之处是反映不出信息量的实际变化，更为严重的是，估 计可能会发生错误，最糟糕的情况是一开始估计就发生错误，这样，错误就涉及到全 部操作，其结果就不能以最优的方式确定执行站点，当然获取结果也将变得缓慢了。 动态方法不是预先确定操作执行的站点，而是随着请求执行的变化动态地确定， 确定的主要原则是考虑信息的传输量，动态方法的优点是避免了对信息量的估计，而 是根据上一个操作的真实的执行结果，对下一个操作的执行站点进行决策，当然，这 种方法的算法比静态方法复杂一些，实现起来也比较困难。 ( 3 ) 存取路径优化 在基于网络路径的优化方面， 可以根据站点表中的处理能力指数和网络能力指数 来完成的，处理能力指数放映在本地执行查询的性能它受c p u 能力、内存、高速缓存、 操作系统、本地数据库管理系统等多方面因素的影响，在数据量相同的情况下，由于 网络的能力不同，传输的代价将相差很多，同理计算机本身的硬件条件不同，同样的 查询在不同的机器上本地执行所需的时间也不同，同样的查询在不同的机器上本地执 行所需的时间也不同，因此，系统应优先使用高性能的硬件和快速的网络。 采用这种策略可能带来这样的后果，大家都去争用高性能的硬件和快速的网络造 成这些设备很繁忙，而其它设备被闲置，为解决这个问题，系统中的处理能力指数和 网络能力指数并不是恒定的，每当在一个站点上开始一个查询时，就将在该站点的处 理能力指数减去一个定值， 执行完成后再加上这个定值， 这样即使是高性能的计算机， 在同时执行几个任务后，处理能力指数就将低于性能略差的计算机，从而使设备得到 均衡使用。 ( 4 ) 连接操作优化 连接操作是常用而且代价较高的一种操作， 当连接操作数据在同一站点可以用集 中式数据库技术加以解决。当连接操作的数据跨站点时情况就复杂了。对连接查询的 优化主要分为半连接算法和直接连接算法。一般，如果认为传输费用是主要的，那么 采用半连接方案处理策略比较有利。如果认为局部处理费用是主要的，则采用直接连 接方案处理策略比较有利。 尽管在过去的时间里，分布式数据库已经取得了很显著的研究成果，但是，成功 地进入商品化运行的软件却仍为数不多。 华中科技大学硕士学位论文 15 集中系统的数据库设