基于网格的海量数据并行JOIN算法研究与实现

VIP免费
3.0 陈辉 2024-11-19 4 4 1.31MB 80 页 15积分
侵权投诉
摘 要
随着信息技术的飞速发展和日益普及，海量信息的处理和高性能计算的需求
越来越迫切。并行计算机和并行环境一直是高性能计算研究热点之一，现已出现
许多高性能的专用并行计算机如 IBM SB2、
SGI Power Challenge、
Cray T3d 以及国
内的曙光系列并行机等，但它们都具备难以接受的高昂的价格。网格和数据网格
以其良好的自治性、自相似性、异构性、管理多样性、强大的并行 I/O 能力、非常
高的性能价格比等特性成为高性能计算的最佳解决方案之一。由于网格并行计算
具有复杂性、动态性，而现在基于网格的数据并行型计算的研究才刚刚起步，存
在着动态管理、扩展性和可靠性问题。
本课题研究的是以网格和数据网格并行计算为基本理论依据，由于网格环境
下各个节点的异构性和通信速率的差异性，再加上海量数据的查询给数据库的查
询操作带来了新的问题。针对这种新的结构特点，本文提出一种基于海量数据并
行JOIN 算法，使其充分利用各种并行性和减少传输量来缩短响应时间。并对算法
进行了实现，对主要影响因素和系统的效率进行了验证。其研究内容有以下几个
方面：网格计算系统（DGCS）、网格监控系统（DGMS）、JOIN 算法实现及优化、
容错机制和资源动态管理策略(RDMM)、海量数据的划分与传输。最后利用 Java
语言和 Eclipse 开发工具实现了这一计算模型，并进行了一系列的实验，获得可靠
的和实用的实验数据，为网格并行计算的研究提供技术和实验数据支持。
关键词：网格计算 并行计算 并行连接 海量数据
ABSTRACT
With the development of information technology, the demand of large scale
information settling and high performance computing become urgent, Parallel computer
and parallel environment is one of the fields of high performance computing. Now some
appropriative parallel computers such as IBM SB2、SGI Power Challenge、Cray T3d
appears, but they have high price. Grid and data grid, with well autonomy,
comparability, isomerism, diversity of management, and powerful parallel I/O capability,
is the best solution of high performance computation.
For data grid parallel computation has complexity and dynamic and the research of
data parallel computation based on data grid starts just now, data grid parallel
computation has the problem of dynamic management, expansibility and dependability.
Based on grid and data grid parallel computation idea and theories , Because of the
high heterogeneity of the nodes and the widely different communication rates under the
Grid environment , in addition the massive data , the database query operation
encounters new challenges. This paper presents an algorithm to make it fully to use each
kind of parallelism and relations reduces algorithm to reduce the response time. And has
carried on the realization to the algorithm, has carried on the confirmation to the major
effect factor and the system efficiency .The content include the following：Date Grid
Computing System (DGCS), Date Grid Monitoring System (DGMS), JOIN algorithm
and optimization, fault-tolerant mechanisms and dynamic resource management
strategy (RDMM), and the delineation of massive data transmission . the programm is
implemented by using Java language and Eclipse development tool. A series of
experience is done and dependable and usable experience data is obtained. The chapter
provides the support of technology and experience data to the research of data grid
parallel computing.
Key Words：Grid Computing, parallel Computing, massive data, parallel
JOIN
目 录
摘 要
ABSTRACT
第一章 绪论 .....................................................................................................................1
§1.1 课题背景与研究意义 .........................................................................................1
§1.2 国内外研究现状及发展 .....................................................................................2
§1.3 本文的研究内容及实施方案 .............................................................................3
第二章 网格计算理论概述 .............................................................................................4
§2.1 网格概述 ............................................................................................................ 5
§2.2 网格计算体系结构 ............................................................................................ 5
§2.3 网格计算系统的关键技术 ................................................................................ 7
§2.4 网格计算系统的应用 ........................................................................................ 8
第三章 海量数据存储方式与并行计算理论 .................................................................8
§3.1 海量数据的划分原则 ........................................................................................ 8
§3.2 数据划分方法 .................................................................................................... 9
§3.3 并行计算概述 .................................................................................................. 11
§3.4 并行计算模型 .................................................................................................. 12
§3.4.1 理想计算模型的特征 .............................................................................13
§3.4.2 典型的同构并行计算模型 .....................................................................14
§3.4.3 异构并行计算模型 .................................................................................17
§3.5 并行算法简介 .................................................................................................. 17
§3.6 并行算法的研究内容 ...................................................................................... 18
§3.7 并行程序设计语言 .......................................................................................... 18
§3.8 并行程序设计目前面临的困难和发展 .......................................................... 19
第四章 并行 JOIN 算法的研究 ....................................................................................21
§4.1 并行 JOIN 的相关算法 ................................................................................... 21
§4.2 基于数据划分的并行连接算法 ...................................................................... 21
§4.2.1 并行嵌套循环连接算法 .........................................................................21
§4.2.2 改进的并行嵌套循环连接算法 .............................................................22
§4.2.3 并行排序合并连接算法 .........................................................................23
§4.2.4 使用索引的并行连接算法 .....................................................................24
§4.2.5 并行哈希连接算法 .................................................................................25
§4.2.6 简单并行 hash 连接算法 ....................................................................... 26
§4.2.7 多趟简单并行哈希连接算法 .................................................................27
§4.2.8 并行 Grace 哈希连接算法 ..................................................................... 27
§4.2.9 并行 Hybrid 哈希连接算法 ................................................................... 28
§4.3 基本并行连接算法比较 ................................................................................ 31
第五章 网格环境管理 ...................................................................................................32
§5.1 基本定义 ........................................................................................................ 32
§5.2 网格监控系统 ................................................................................................ 35
§5.3 任务管理 ........................................................................................................ 38
§5.3.1 任务分解原则 .........................................................................................38
§5.3.2 任务分解策略 .........................................................................................38
§5.3.3 任务协同 .................................................................................................39
§5.3.4 任务冗余分配策略 .................................................................................39
§5.3.5 任务和数据分配 .....................................................................................40
§5.3.6 任务调度策略 .........................................................................................41
§5.3.7 任务和数据访问策略 .............................................................................43
§5.4 资源管理 ........................................................................................................ 44
第六章 网格环境下的 JOIN 算法 ................................................................................47
§6.1 研究的问题及算法描述 ................................................................................ 47
§6.1.1 初始条件及问题描述 .............................................................................47
§6.1.2 参数定义 .................................................................................................47
§6.1.3 查询处理过程 .........................................................................................48
§6.1.4 查询任务 .................................................................................................48
§6.1.5 优化策略 .................................................................................................49
§6.1.6 数据传输策略 .........................................................................................50
§6.1.7 算法处理模型 .........................................................................................50
§6.1.8 算法描述 .................................................................................................52
§6.2 算法时空复杂度分析 .................................................................................... 54
§6.2.1 算法时空复杂度理论分析 .....................................................................54
§6.2.2 本算法连接代价估算 .............................................................................56
第七章 实验模拟与性能分析 .......................................................................................58
§7.1 实验模拟 ........................................................................................................ 58
§7.1.1 环境搭建 .................................................................................................58
§7.1.2 海量数据的产生 .....................................................................................58
§7.1.3 程序核心代码实现 .................................................................................58
§7.1.4 数据划分与存储方式 .............................................................................70
§7.2 实验性能分析 ................................................................................................ 70
§7.2.1 加速比 .....................................................................................................70
§7.2.2 主要影响因素 .........................................................................................71
第八章 结论和展望 .......................................................................................................72
参考文献 .........................................................................................................................73
在读期间公开发表的论文和承担科研项目及取得成果 .............................................76
致谢 .................................................................................................................................77
错误！未定义样式。
1
第一章 绪论
§1.1 课题背景与研究意义
科学技术的发展和金融、电信、交通、信息安全等众多行业信息化需求的不
断增加，在系统业务功能逐步增强的同时,系统的数据量也不断增大,数据量高达
几百 GB 甚至于 TB 级的海量数据库应用已经出现。与此同时,人们对高性能联机
事务处理和复杂查询操作能力的需求也在不断提高，特别针对一些跨国大公司和
国家的公共服务行业，这些地理上分布的海量数据，而用户希望能够访问，使用
这些庞大的分布数据。这种结合海量数据集合，地理上分布的用户和资源，以及
计算密集型的分析处理应用促使了处理海量数据能力的数据库系统的出现，为此,
人们提出了各种不同的并行处理方法： 由 SMP 到集群技术[1-3],再到现在的网格技
术,要求参与并行处理的处理机在地域上的分布越来越分散,从一个计算机内到基
本分布在同一建筑之内的集群,最终到现在遍布全球的网格。网格计算[4-7]的目标是
支持在分布式的异构环境中动态地形成虚拟计算机,方便用户合作完成大型任务。
因为这个虚拟计算机是由分布在各地的计算机形成的,它们之间的协作必定要涉及
到数据的传输问题,尤其是涉及到数据库操作时。数据库在网格环境下的应用,必定
带来数据的大量传输和某些数据操作只能在特定节点执行的问题,还有网格环境本
身固有的高度异构性都给数据库查询任务的并行化带来了新的问题，在海量并行
数据库应用系统中,由于系统具有海量性、高速性、连续性等特点[8-11]，从而对 JOIN
查询的执行效率以及查询性能提出了更高的要求。随着数据源的数量和查询条件
的数量的增加, JOIN 查询所要做的数据传输量也将迅速的增加,系统需要大量的
网络和磁盘 I/O 开销,以至于在海量并行数据库环境下,即使是很简单的查询统计
也变得很难实现,全球各大主流数据库厂商在新产品中无一例外地宣称提供了对海
量数据库 VLDB(Very Large Database) 的支持,众多数据库支持的数据量已达到
TB 级。事实上,对VLDB 的支持并不仅仅指的是数据库系统的数据量,而是更多
地体现在对数据库系统的管理能力,包括日常管理、数据加载、数据查询、索引建
立、运行性能等,同时还需要支持大量的用户连接和大的工作负荷。 只有在此基
础上保持良好运行性能的数据库系统才能构成超大型数据库应用系统。目前商业
并行数据库系统的扩展能力、接入能力和查询效率都不是太理想,尤其随着系统的
扩展,数据规模增大,系统性能急剧下降[12-16]。为此,我们设计并实现了一个网格
环境下海量数据的 JOIN 算法，以使其适应新的环境的要求，并在该环境下进行了
基于网格的海量数据并行 JOIN 算法研究与实现
2
大量的实验，从实验的数据表明，该算法在新的结构下是高效的，这主要得益于
算法充分利用了环境结构的特点提高了查询性能。
§1.2 国内外研究现状及发展
目前国内外已有一些项目开始研究在网格环境下如何实现跨多关系数据库的
分 布 式 查 询 。 在 美 国 国 家 科 学 基 金 的 资 助 下 ,俄 亥 俄 州 立 大 学 正 在 进 行
GRIDDB2Lite 项目的研究，该项目的目标是开发一种网格中间件系统,支持网格
中数据库系统的数据存储、索引和查询,保证在分布式环境下对海量数据进行高效
的存储和查询,为数据密集型的网格科学应用提供数据库访问和集成的支持,研
究重点集中在数据的快速检索和传输领域。
OGSA2DAI 项目是 GGF 的Database Access and Integrat ion ServicesWork ing
Group 发起的,项目的主要目的是在 OGSA 体系结构中促进网格数据库服务标准
的制订,首要目标是为现存的、自治的数据库系统提供一致的访问途径。目前
OGSA2DAI 提出采用若干个 OGSA 服务来实现网格内数据库的一致访问,这些服
务包括 GDS (GridDatabase Services, 执行各种数据库操作)、GDSF (GridDatabase
Service Factories, 创建 GDS )、DSR (DatabaseService Regist ries, 发现数据库、相
应的 GDS 和GDSF)、GDTS(Grid Data T ransfer Services, 实现灵活的数据传输功
能)。 但是这些服务只提供了基本的功能和接口,要实现数据分布、管理、访问和
处理的透明性,用户必须基于这些服务开发新的服务,如分布式查询、事务处理
等。
英国的 MyGrid 项目组 OGSA2DAI 的基础上开发了分布式查询处理系统
(Distributed Query Processing,DQP)。DQ P 支持异构数据源的集成,并利用并行数
据库技术实现复杂查询的隐性并行化。DQ P 的查询优化是基于 Polar 并行数据库
的查询处理引擎实现的,没有充分考虑网格环境与并行数据库运行环境的不同。
SkyQuery 项目利用 Web Service 技术实现多个数据库的集成,它采用经典的
中介子包裹子结构,在每个数据库节点上部署需要的 Web Service, 负责处理元数
据,执行查询等任务。 SkyQuery 支持分布式查询服务,但查询语言是专门为天文应
用设计的,数据分布仅仅支持单一的水平分片策略,不支持查询内的并行,而且没
有充分利用网格特有的资源(或服务)的动态发现、分配和访问机制。在商用领
域,ORACLE IBM 都声称其新一代数据库产品支持网格应用。 然而,无论是刚推
出的 Oracle10g 还是 DB2,它们都仅仅提供了一套网格应用与数据库系统的接口,
通过这套接口,网格应用可以访问和操纵存储在这些数据库系统中的数据,还不
能支持数据的广域分布和访问。
第一章 绪论
3
在国内,中国人民大学、国防科技大学和浙江大学都开展了这方面的研究工
作。 中国人民大学的王珊教授在 2003 中国计算机大会(CNCC203) 做了分组特邀
报告“网格环境下的数据管理”
,详细探讨了传统的分布环境下数据管理系统和网
格环境中数据管理系统的区别,指出网格化的数据库系统需要重点研究数据划分
与调度、高速数据传输、缓存与副本、安全、服务质量和体系结构等问题。 同时,
中国人民大学对于 P2P 系统中的数据管理进行了深入的研究。国防科技大学开发
了Griddaen 数据网格系统,能够集成广域网环境下异构的各种存储资源,例如 L
inux、Windows 等单机文件系统、N FS 等网络文件系统以及数据库系统等,并将
它们统一组织起来,通过系统提供的数据访问和管理服务屏蔽底层存储资源异构
性和多个管理域,为用户提供直观、一体化的文件视图和方便、规范的访问和操作
方法。 数据使用者采用类似于 N FS 文件系统的访问接口对各种异构存储系统进
行访问。 浙江大学正在开展中国中医药网格的研究,采用数据库网格来实现多个
异质数据库的细粒度的数据共享,为用户提供统一的数据视图和访问接口。 系统
的具体实现没有采用 OGSA 体系结构,而是专门开发的中间件和相关协议。“基于
数据网格环境的连接操作算法”考虑了异构通信网络对连接操作算法的影响,并进
行了相应的仿真和实验,证实了该算法在数据网格环境下的有效性,但未论及具
体的实现。综上所述,目前国内外的研究主要集中在网格环境下数据库的访问和集
成领域,即如何设计和实现网格应用与数据库系统的统一接口,用户能够以数据
库无关的方式统一访问和管理存储在不同数据库中的数据。
§1.3 本文的研究内容及实施方案
本课题研究的内容：网格计算系统（DGCS）、网格监控系统（DGMS）、JOIN
算法实现及优化、容错机制和资源动态管理策略(RDMM)、海量数据的划分与传输。
网格计算系统（Data Grid Computing System）主要包括初始化网格系统、分解
任务、分配任务、计算任务、整合中间结果和输出结果。
网格监控系统（Data Grid Monitor System）主要包括监控网格上节点的状态、
性能以及资源的利用率。
JOIN 算法实现及优化，主要包括使用采取关系缩减算法、行分块传输技术和
流水线并行机制，缓存技术等等。
容错机制主要保证系统运行的可靠性。
资源动态管理策略（Resource Dynamic Management Method），网格上节点的
资源是动态变化的，系统根据节点的资源情况来动态的分配任务，优化系统，使
系统的通信比、计算比到达最优。
摘要：

摘要随着信息技术的飞速发展和日益普及，海量信息的处理和高性能计算的需求越来越迫切。并行计算机和并行环境一直是高性能计算研究热点之一，现已出现许多高性能的专用并行计算机如IBMSB2、SGIPowerChallenge、CrayT3d以及国内的曙光系列并行机等，但它们都具备难以接受的高昂的价格。网格和数据网格以其良好的自治性、自相似性、异构性、管理多样性、强大的并行I/O能力、非常高的性能价格比等特性成为高性能计算的最佳解决方案之一。由于网格并行计算具有复杂性、动态性，而现在基于网格的数据并行型计算的研究才刚刚起步，存在着动态管理、扩展性和可靠性问题。本课题研究的是以网格和数据网格并行计算为基本...

展开>> 收起<<
基于网格的海量数据并行JOIN算法研究与实现.pdf

共80页,预览8页

还剩页未读， 继续阅读

相关推荐

更多
立即下载
作者：陈辉 分类：高等教育资料 价格：15积分 属性：80 页 大小：1.31MB 格式：PDF 时间：2024-11-19

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

推荐作者

热门标签

/ 80
评分 收藏
分享
立即下载 VIP免费下载
客服
关注