（计算机软件与理论专业论文）基于mpi的并行数据库中间件的设计与实现.pdf

摘要 摘要 随着全球信息化浪潮和计算机应用领域的不断拓展，各行各业需要处理的信息量越 来越大，尤其在航空航天、通信、海洋开发、天气预报、军事等诸多领域，数据规模已 达到t b 级甚至p b 级，传统的串行数据库系统面对如此庞大的数据处理己显得力不从 心。因此，设计并行数据库系统用来存储和管理大规模数据，提供比传统数据库系统更 好的性能已经成为数据库领域的共识。并行数据库系统是以高性能、高可用性和高扩充 性为目标，充分利用多处理器平台的工作能力，多个处理机协同处理，以达到更快的数 据库响应速度和分析能力。目前已经有了一些相对成熟的并行数据库技术，同时也存在 一些商业化的并行数据库产品。 本文结合前人的研究成果，在无共享( s n ) 结构的集群( c l u s t e r ) 系统上，提出了基于 m p ! 结合已有关系型d b m s 进行并行数据库系统中间件软件的开发，该中间件的设计目 的就是为了屏蔽并行程序和数据库的操作，直接向上层用户提供并行数据库操作。在 这个思路的指导下设计研究出了一个并行数据库原型系统p d b s 0 。本文的主要研究成 果如下： 1 、在集群的基础上建立了一整套软件硬件的研究平台。 2 、提出了基于m p i 和a c c e s s 的并行数据库系统中间件软件p d b s 0 的理论框架。 3 、实现了很多并行数据库查询操作模块。如并行排序、并行选择、并行连接。 4 、对整个系统在平台下进行全面的测试并进行了详细的测试结果分析，总结出了 提高整个系统性能的关键点。 关键词：集群，并行数据库，s n ，m p i a b s t t a c t a b s t r a c t w i t ht h ei m p a c to fg l o b a lw a v eo fi n f o r m a t i o na n dt h ec o n s t a n te x p a n s i o no fc o m p u t e r a p p l i c a t i o n s ，a l lw a l k so fl i f ed e a l 诵t 1 1g r e a t e ra m o u n to fi n f o r m a t i o n ，p a r t i c u l a r l yi nt h en e r o s p a c e ，c o m m u n i c a t i o n s ，m a r i n ed e v e l o p m e n t , w e a t h e rf o r e c a s t i n g ，m i l i t a r ya n do t h e rf i e l d s t - h es c a l eo fd a t ah a sr e a c h e dt bc l a s so re v e np bc l a s s t h et r a d i t i o n a ls e r i a ld a t a b a s es y s t e m e n c o u n t e r i n gs u c hl a r g e - s c a l ed a t ah a sb e c o m eu n a b l et od e a lw i t h t h e r e f o r e ，i th a sb e c o m e t h ec o n s e n s u so ft h ed a t a b a s ef i e l d st od e s i g nt h ep a r a l l e ld a t a b a s es y s t e mu s e dt os t o r ea n d m a n a g el a r g e - s c a l ed a t aa n dt op r o v i d eb e t t e rp e r f o r m a n c e p a r a l l e ld a t a b a s es y s t e ma l m sa t h i g hp e r f o r m a n c e ，h i g ha v a i l a b i l i t ya n dh i g hs c a l a b i l i t yt of u l l yu t i l i z em u l t i p r o c e s s o rp l a t f o r - i l l s w o r k i n g 、析t 1 1an m n b e ro fs y n e r g i s t i cp r o c e s s o r si no r d e rt oa c h i e v eaf a s t e rr e s p o n s ea n d a n a l y s i sc a p a b i l i t i e s a tp r e s e n t ，t h e r eh a v eb e e ns o m er e l a t i v e l ys o p h i s t i c a t e dp a r a l l e ld a t a b a s et e c h n o l o g y ，b u ta l s ot h e r ea r es o m ec o m m e r c i a lp a r a l l e ld a t a b a s ep r o d u c t s w i t ht h ep r e v i o u sr e s e a r c hr e s u l t s ，b a s e do nc l u s t e rs y s t e mo f s h a r e d - n o t h i n g ( s n ) s t r u c t u r e ，t h ea u t h o rp r o p o s e dt od e v e l o pt h em i d d l e w a r es o f t w a r eo nt h eb a s i so fm p ia n d r d b m s t h er o l eo fm i d d l e w a r ei st os h i e l dp a r a l l e lp r o g r a m m i n ga n dd a t a b a s eo p e r a t i o n st o t h eu p p e r p a r a l l e ld a t a b a s eo p e r a t i o n s u n d e rt h eg u i d a n c eo ft h i st h o u g h t , ap a r a l l e ld a t a b a s e p r o t o t y p es y s t e mp d b s - 0i sf o r m e d t h em a i nr e s e a r c hr e s u l t sa r ea sf o l l o w s ： 1 、as e to fs o f t w a r ea n dh a r d w a r er e s e a r c hp l a t f o r mh a sb e e ns e tu po nt h eb a s i so ft h e c l u s t e r s 2 、t h et h e o r e t i c a lf r a m e w o r ko ft h ep a r a l l e ld a t a b a s es y s t e mm i d d l e w a r es o f t w a r ep d b s 一0 h a sb e e np u tf o r w a r do nt h eb a s i so fm p ia n da c c e s s 3 、al o to f p a r a l l e ld a t a b a s eq u e r yo p e r a t i o nm o d u l e s h a v eb e e na c h i e v e d s u c ha sp a r a l l e l s o r t ，p a r a l l e ls e l e c t i o na n dp a r a l l e lj o i n 4 、a c o m p r e h e n s i v e t e s th a sb e e nc o n d u c t e da n dad e t a i l e da n a l y s i so ft e s tr e s u l t sh a v e b e e nc a r d e do u t ；t h ek e yp o i n t so fi m p r o v i n gt h ep e r f o r m a n c eo ft h ew h o l es y s t e mh a v e b e e ns u m m e f i z e d k e y w o r d s ：c l u s t e r ，p a r a l l e ld a t a b a s e ，s n ，m p i 西北大学学位论文知识产权声明书 本入完全了解西北大学关于收集、保存、使用学位论文的规定。学 校有权保留并向国家有关部门或机构送交论文的复印件和电子版。本人 允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的全部或 部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存和汇编本学位论文。同时授权中国科学技术信息研究所等机构 将本学位论文收录到中国学位论文全文数据库或其它相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：耋：塑已指导教师签名：学位论文作者签名：竺塑匕指导教师签名： 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢 的地方外，本论文不包含其他人已经发表或撰写过的研究成果，也 不包含为获得西北大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示谢意。 学位论文作者签名： 奄掭 力口。夕年乡月日 西北大学硕士学位论文 1 1 背景 第一章绪论 在现代信息化社会中，随着计算机应用领域的不断扩大，数据库的规模也随之日益 增长，需要处理的信息量越来越大，人们对于计算机的要求也越来越高，各种性能更高 的计算机不断的被研制并应用，如s m p ( 对称多处理器) 计算机、m p p ( 大规模并行处 理) 计算机等。这些计算机大都具有很高的配置( 如大内存、海量存储、可多达上千个 的c p u 等) ，具有很强的处理能力。但这些计算机的价格却与其高性能是成正比的。 并行数据库技术起源于2 0 世纪7 0 年代的数据库机( d a t a b a s em a c h i n e ) 研究，研 究的内容主要集中在关系代数操作的并行化和实现关系操作的专用硬件设计上，希望通 过硬件实现关系数据库操作的某些功能，该研究以失败而告终【l 】。8 0 年代后期，并行数 据库技术的研究方向逐步转到了通用并行机方面，研究的重点是并行数据库的物理组 织、操作算法、优化和调度策略。从9 0 年代至今，随着计算机集群技术( c l u s t e r - t e c h n o l o g y ) 的发展和处理器速度的不断提高，相对廉价的机器通过网络互联组成的集群( c l u s t e r ) 能够替代昂贵的并行机器，从而实现了以较低的代价获得与并行机器相当的高性能。这 一技术在数据库领域得到了越来越多的应用，使得并行数据库技术的研究上升到一个新 的水平，研究的重点也转移到数据操作的时间并行性和空间并行性上。 因此，可以设想开发一种支持数据并行处理的中间件，把计算机集群系统中各个节 点上运行的独立的单机版数据库管理起来，使它们能够并行工作。这就实现了以较低的 成本( 单机版数据库的成本) 获得较高的性能( 接近并行数据库系统的性能) ，从而极大限 度地保护了用户的现有投资。基于这种想法，我们研究设计了一个支持数据并行处理的 中间件，该中间件与并行机各节点上运行的单机版d b m s ，采用多层架构模式一起构成了 并行数据库中间件系统。 1 2 并行数据库研究的必要性 1 2 1 数据库应用的新特点 随着社会各个领域数据的不断集中以及网络技术的快速发展，导致数据库应用需要 存储和使用的数据对象变得越来越庞大和复杂，例如，多媒体信息系统的图象、正文、 第一牵绪论 声音等；科学与统计数据库应用系统的大型矩阵、数组和向量等；软件工程数据库应用 系统的程序版本和文档等；化学数据库应用系统的蛋白质结构等。如此纷繁复杂的数据 对象，对d b m s 就提出了一系列新的要求，比如：能够直接支持图象、声音、矩阵、时间 序列等复杂的数据对象；支持新一代数据库查询语言；适应于复杂数据对象的存储结构、 索引技术、存取方法；数据类型的管理能力，为程序员提供构造复杂数据类型的机制等。 而从数据库管理系统本身的应用来讲，随着数据量达到t b 甚至p b 级( 如g 1 s 地理信息系 统、天气预报、地质勘探、飞行器模拟、基因工程等等) ，即使运行在性能极高的大型 主机上，在处理大量并发用户和大规模数据量时，也极易造成应用中计算机i o 和处理 器的瓶颈问题。在这种情况下，数据库管理系统采用并行技术就成为一种强烈的需要。 基于以上的几点情况，一个d b m s 的性能应该由该d b m s 能否为越来越多的用户维 持高事务吞吐量和低响应时间来作为衡量的重要指标，因此将传统的数据库管理技术与 并行处理技术结合的并行数据库技术已越来越为人们所瞩目。 1 2 2 关系数据库系统的固有并行性 由于关系代数的封闭性和数据操作的相对独立性，使得传统的关系数据库模型本身 就具有极大的并行可能性：而且关系数据库系统的非过程性的查询语言为其并行化提供 了有力的支持。关系查询具有以下三种固有并行性【2 】： 1 、数据操作间的流水线并行性( p i p e l i n ep a r a l l e l i s m ) ：两个数据操作可以按流水线 方式并行执行，意味着一个操作( p r o d u c e r ) 的输出是另一个操作( c o n s u m e r ) 的 输入。如果一个查询包含两个可按流水线方式执行的操作，我们可以为每个操 作分配一个处理机，使这两个操作在p r o d u c e r 产生第一个输出后( 不用输出全 部p r o d u c e r 的结果) 即可并行执行，以此加速查询处理速度。 2 、数据操作问的独立并行性( i n t e r o p e r a t o rp a r a l l e l i s m ) ：如果两个数据操作完全独 立，可以同时执行而不受影响，我们可以使用多个处理机同时执行这些可独立 并行执行的操作，加速查询的处理，减少查询的响应时间。 3 、单数据操作内的并行性( i n t r a - o p e r a t o rp a r a l l e l i s m ) ：如果一个操作可以分解成几 个可独立并行执行或者按照流水线方式并行执行的子操作，则这个操作可以由 多个处理机并行执行，加快处理速度。 关系查询特别适合于并行处理。关系系统中的这三种固有并行性为建立高性能的并 行数据库系统提供了非常有利的条件。 2 西北大学硕士学位论文 1 3 国内外研究状况 数据库技术经历了几十年的发展演变，已经取得了巨大的成就，发展成了一门内容 丰富的学科，形成了总量达数百亿美元的一个软件产业。国外的并行数据库技术发展的 比较早，也比较成熟。典型研究成果有：t e r a d a t a ，t a n d e m n o n s t o ps q l ，g a m m a 等【3 ，4 ，5 1 。 目前，市场上具有代表性的数据库产品包括o r a c l e 公司的o r a c l e ，ib m 公司的d b 2 以 及s y b a s e 公司的s y b a s e 数据库等等。从一定程度上看，这些产品反映了当前数据 库技术的最高水平和发展趋势。 t e r a d a t a 自1 9 7 8 年t e r a d a t a 就在普通的处理器、磁盘、存储器上建立s h a r e d - n o t h i n g 结构 的高度并行s q l 查询系统，t e r a d a t a 系统主要是作为运行在传统计算机客户程序的s q l 服务器。t e r a d a t a 系统可以同时处理一千个处理器和几千个硬盘。t e r a d a t a 系统中的处 理器按功能分为两组：接口处理器r ( i f p s ) 和存取模块处理器( 6 山伸s ) ， i f p s 负责主机间 的通讯、查询分析与优化，在查询执行过程中协调枷s ：a m p s 负责查询的执行，每 个a m p 通常拥有几个磁盘和一个大的内存缓冲区。i f p s 和a m p s 通过双倍冗余的树形 互联网络y n e t 互相连接。数据分布采用哈希算法将每个关系数据库文件分配到每个 a m p s 的子集磁盘中。查询结果的合并采用一种并行的s o r t m e r g e 算法，而不是流水线 算法。t e r a d a t a 系统已经应用在许多具有超过一百个处理器和几百个磁盘的大型系统中， 这些系统在关系查询中显示了接近线性的s p e e d u p 和s c a l e u p ，远远超过了传统主机在 处理大数据量数据库时的性能。 t a n d e mn o n s t o ps q l t a n d e mn o n s t o ps q l 系统f l - 1 4 丛光线环互相连接的处理器机群组成。不像大多数其 他的并行数据库系统，t a n d e mn o n s t o ps q l 在同一个处理器集群和操作系统下运行应用 程序作为数据库服务器。在程序和机器之间没有前端和后端之分。每个磁盘被共享存储 器的一组处理器管理，通过预取大的数据单元来优化查询，通过s q l l 田n 词来过滤和操纵 查询字段，使共享的互联网络上的数据通讯量降至最低。关系数据库的数据按r a n g e 划 分方法分布到多个磁盘上，支持b 树二级索引，提供多种并行连接算法。t a n d e m 最初是 为在线事务处理设计的，目的是在大的共享数据库系统上运行大量的简单交易。由于大 量独立事务处理的固有并行性，t a n d e m 系统具有并行索引更新的特征，这使它具有很高 的读速度，但插人、更新、删除比较慢。t a n d e m 系统在在线数据查询中获得了接近线性 第一章绪论 的s c a l e u p ，在大规模并行关系数据查询中获得了接近线性的s p e e d u p 和s c a l e u p 。 g a m m a 当前版本的g a m m a j 垂行在一个3 2 节点的i n t e l i ps c 2 超级立方结构计算机上，每个节 点连接着一个自己的磁盘。除 r o u n d r o b i n , r a n g e 和h a s h 数据划分方法，g a m m a 还提 供t h y b r i d - r a n g e 方法，它结合t r a n g e 和h a s h 分区策略的最好的特征。其索引由b 树或 哈希表建立。查询的分割和合并采用的是并行和流水线并用的方法，支持s o r t m e r g e 和 其他三种不同的h a s h 合并算法，在这种体系结构上的关系查询经测定获得了接近线性的 s p e e d u p 和s c a l e u p 。 o r a c l e 1 o r a c l e 公司在自己o r a c l e8 i 产品的o p s ( o r a c l ep a r a l l e ls e r v e r 并行服务器) 中使用 了并行数据库处理的概念。o p s 可以让位于不同系统的多个实例同时访问同一个数据 库，可以有效地提高系统的可用性和对多系统的访问性能。o p s 主要用于u n i x l i n u x 集群环境中，具有以下优点： 1 ) 高可用性； 2 ) 加快事物响应时间可用于决策支持系统； 3 ) 增大交易连接数可用于连机事物处理系统。 o p s 可以将用户的大量数据请求分为多个相对较小的处理单元，它们可以被不同进 程协调并发执行，这样可以极大地提高处理速度。o p s 采用内存集中的并行处理，要求 服务器之间互连并共享磁盘子系统，共享磁盘技术能够对使用模式做出动态的响应，并 进行非常有效的调整，不需要人工干涉来重新分配资源。o p s 从实际意义上来讲是一种 建立在共享磁盘系统上的并行处理服务器，它的各个进程协同操作，可以同时读取和写 入文件，但是当同时读取和写入相同的文件时，会引发冲突。所有可以做成集群的系统 都可以运行o p s ，常用的有u n i x l i n u x 和n t 等。在o p s 中，如下的操作可以被 并行执行：s e l e c t 、g r o u pb y 、o r d e rb y 、i n s e r t 、u p d a t e 、d e l e t e 。 2 0 r a c l e 9 i 是o r a c l e 公司推出的并行数据库的重量级产品，o r a c l e 9 ir e a la p p l i c a t i o n c l u s t e r s ( r a c ) 是o r a c l e 的新一代并行服务器系列产品。o r a c l e 9 ir a c 针对访问相同数据 而设计了快捷高效的共享集群高速缓冲寄存器，从而提供了透明的应用程序可扩展性。 o r a c l e 9 ir a c 是o r a c l e 五年多研发工作的结晶，其中包含9 项独家专利和1 8 项已申报 的专利请求。o r a c l e 9 ir a c 利用高速缓存熔接( c a c h ef u s i o n ) 技术共享聚合高速缓存来满 4 西北大学硕士学位论文 足数据库的请求，这个技术可以使得集群中的节点通过一个高速的内部连接去同步高速 缓存，从而使得磁盘的v o 操作达到最小，o r a c l e 9 i 中高速缓存熔接的完成使客户可以 轻松地利用r a c 所提供的可伸缩性，实现随着应用和需求的继续增长自由扩大数据库 层。利用这样的技术，o r a c l e 数据库可以在增加或者删除节点的时候不必重新划分数据， 从而极大地提高了系统的可扩展性。 o r a c l e 9 ir a c 还提供了超强的系统可用性，即当一个节点失效的时候，这个节点的 工作负载就会立即安全地转移到别的节点中去。 3 o r a c l e1 0 9 ，在这个版本中，o r a c l e 延续了9 i 的r a c 技术进行并行数据库服务器 的推广，同时还引进了网格的概念。在1 0 9 中，r a c 提供了单一系统映象的管理功能， 使得用户在管理数据库系统的时候更加方便和有效。 4 o r a c l e1 1 9 ，这个最新的版本向用户提供了高性能、伸展性、可用性、安全性，1 1 9 中的r a c 节点通信协议得到更进一步的改进，可以根据节点的负荷作出动态的调整， 大大减少节点之间的消息传递量。o r a c l e1 1 9 能更方便地部署在任何服务器上，能够在 从小刀片服务器到最大型的s m p 服务器以及其他低成本服务器和存储设备组成的网格 上运行。并对许多操作执行块一范围的并行化，如备份与恢复等。 i b m 公司 1 d b 2p e ( d b 2p a r a l l e le d i t i o n ) 运行于r s 6 0 0 0 s p 系列大型并行处理( m p p ) 服务器 中，可将复杂的查询分解成许多部分，从而可以在数十，甚至数百个处理器上同时运行。 它具有如下几个特点【6 】： 1 ) 完全并行性。在d b 2p e 中，可以使用标准s q l 自动创建并行的存取计划一无需 编程。d b 2p e 的并行功能可用于r e a d 、i n s e r t 、u p d a t e 和d e l e t e 函数。数 据扫描、合并、排序、负载平衡、表重组、数据加载、索引生成、索引访问备份及 恢复等都可以在所有节点上同时执行。 2 1 ) 极高的可伸缩性。其“无共享 体系结构在执行查询时将节点之间的数据传输量降 至最低。因为分区数目对分区内的通讯量几乎没有影响，当您添加s p 节点或s m p 处理器时，系统性能可近似按线性模式提高。 3 ) 智能数据分发。d b 2p e 通过智能数据库分区功能支持并行查询。d b 2p e 可在数据 库的多个分区或子集中分数据，这些数据库可以位于多个s p 节点或对称多处理器 ( s m p ) 服务器中。独特的分区图允许d b 2p e 管理分发过程并在必要时重新分发。 第一章绪论 4 ) d b 2 基于成本的s q l 优化器，利用分区信息估计s q l 查询不同执行计划的成本， 在需要进行分布数据和重新分布数据时作有效的管理，从中选择成本最低的执行计 划。 5 ) 采用了完全的s h a r e n o t h i n g 体系结构，这个被业界认为是最有希望成为并行数据库 系统标准的体系结构己经被i b md b 2 完全采用。 2 d b 2 通用数据库企业版( u d be e ) ：是一种可网络操作的全功能关系型数据库管 理系统，适用于从i n t e l 服务器到大型的u n i xs m p 服务器，主要是针对中到大型商业 用户和部门，特别是要求具有i n t e m e t 和企业连通能力的用户。整套数据库包括a i x 、 h p u x 、s o l a r i s 、o s 2 、l i n u x 和w i n d o w sn t 版。d b 2 通用数据库企业扩展版( u d be e e ) 这是一种用于集群或m p p 服务器的全功能、全网络化及全并行关系型数据库管理系统， 是d b 2 并行版( p a r a l l e le d i t i o n ) 的升级产品，适用于要求并行处理，特别是运行数据仓 库和数据挖掘但还需要具有o l t p 能力的应用。可支持a i x 、s u ns o l a r i s 和w i n d o w n t 。 国产并行数据库 由于数据库软件的开发需要巨大的资金和研发力量的投入，自己做数据库系统软件 的难度较大，因此长期以来，国内数据库软件的绝大部分市场份额一直由o r a c l e 、s q l s e r v e r 、d b 2 、s y b a s e 等国外产品所占据。但无论是从国家信息安全，还是从国家软 件产业发展的角度考虑，数据库软件的国产化都有其重要的意义。我国的数据库研发经 过“八五和“九五”期间的努力，己经形成了具有一定规模的数据库研究和开发力量。 但是尽管如此，国产数据库产品的成熟度和稳定性还有待于进一步提高，在支持互联网 应用、海量数据管理、安全性支持、系统可扩展性等方面仍显薄弱。基于国产核心d b m s 产品的应用套件还不够丰富，缺乏大规模的应用磨合，这也影响了国产d b m s 核心的 产品化，下面介绍一下一些有突出特色的国产并行数据库系统： 1 并行数据库管理系统h p d b 该系统由黑龙江大学国内并行数据库权威专家李建中教授主持开发，是一个建立在 微型计算机集群并行计算系统h c l u s t e r 之上的并行关系数据库管理系统。h p d b 完全采 用了并行物理存储结构、并行存取方法、并行数据操作算法和并行查询优化技术，支持 数据操作内的并行性、数据操作间的独立并行性、数据操作间的流水线并行性、事务间 并行性等四种并行性。 。 h p d b 具有如下特点： 1 ) h p d b 建立在李建中教授研究并提出的并行数据库系统的理论、技术和方法的基础 6 西北大学硕士学位论文 之上。h p d b 采用的主要并行物理存储结构、并行存取方法、并行数据操作算法、 并行查询优化技术都是他们的有关并行数据库的基本研究成果。 2 ) h p d b 系统不仅支持标准的s q l 语言，而且有所扩充。h p d b 系统的数据定义和与 物理存储结构有关的语句由s q l 语言的相应语句扩充而成，使得一些必要的与并行 数据库物理存储结构有关的表达和处理能力有所增加。这个扩充的s q l 语言称为 p s q l 语言。 3 ) h p d b 系统支持并行b + 树等并行存储结构，支持r o u n d r o b i n 、r a n g e 等物理数据 划分和分布方法。 4 ) h p d b 支持查询间、查询内、数据操作间、数据操作内和流水线并行性。h p d b 的 所有数据操作都由并行算法实现。 5 ) h p d b 系统具有一个性能很高的并行查询优化处理程序。这个查询优化处理程序具 有自适应性。它可以根据查询的实际情况自动选择能够产生最优查询计划的枚举算 法或启发式近似算法，对给定的用户查询进行优化处理，产生最优的或近似优化的 查询计划。 6 ) h p d b 系统是一个适用于计算机集群并行计算环境的数据库管理系统。 7 ) 在h p d b 的设计中，采用了严格层次结构，系统分为五层六个子系统，每个子系统 由独立的软件系统和调用界面构成。消息传递机制是一个独立子系统，具有自己的 使用界面m p i 。h p d b 是建立在m p i 之上的系统，每个子系统的调用界面由一组标 准c 语言函数组成。适当地修改m p i 的实现程序，h p d b 就可以在任何一个计算机 集群并行环境下运行。所以，h p d b 系统具有相当高的可移植性。 2 华中科技大学并行数据库系统p a r o 该成果于2 0 0 0 年1 1 月3 0 日由教育部委托华中科技大学召开“并行数据库管理系 统p a r o ”鉴定会。鉴定委员一致认为【7 , g , 9 , 1 0 】： 1 ) 在多台p c 机组成的无共享系统上实现了并行数据库系统原型。 2 ) 系统符合s q l 标准，具备关系数据库的基本功能，支撑数据模式的定义、数据操纵、 完整性维护和多事务应用等。 3 ) 系统具备并行数据划分、数据装载、数据重组的能力。 4 ) 系统采用并行b + 树索引技术及基于成本估算的查询优化技术，能够有效地存取数据 库，性能优良，加速比高。 5 ) 系统采用前映像文件( b i ) 实现向前恢复以及基于副本的节点故障恢复技术，提供了有 第一章绪论 力的故障恢复保证。 6 ) 系统提供了分布式数据库、并行数据库所构成的客户一服务器的工作方式，具有服 务器多级扩展能力。 3 中国人民大学数据与知识工程研究所，p b a s e 并行数据库系统【l l 】 1 ) 主要技术指标：p b a s e 采用单进程多线程体系结构，除具有普通d b m s 引擎的所有 功能，如数据管理、数据独立性、安全性、完整性、并发控制，恢复等外，还提供 了数据分片、数据分布的透明性、全局数据字典和全局资源信息管理、多级查询优 化、查询调度等功能。目前p b a s e 能够实现事务间、事务内、操作间、操作内各种 粒度的并行性，能够充分利用一切可用的处理节点，并行执行查询、更新、建表、 建索引、恢复等操作。 2 ) 技术成熟程度：原型系统，已通过部级鉴定，鉴定意见认为p b a s e “在实现技术的 先进性和实用性相结合方面达到国际先进水平，在基于流的查询模型、优化方案和 执行机制等方面的研究与实现上进入国际领先行列 。目前该系统正在商品化和实 用化，正在寻求应用。 3 ) 应用范围：运行于各种并行计算机平台，作为高性能数据库服务器，为大型数据库 应用、数据仓库应用和w e b 数据库应用提供支持。具体地说包括： 大规模o l t p 应用行业，如银行、税务、民航等； i s p 以及其它需要w e b s e r v e r 和w e b 应用的大型企业等； 决策支持部门。目前国产数据库大多处于原型系统阶段，还没有出现真正商业化运 作的并行数据库系统。所以，开发针对应用性更强的并行数据库构件将很有可能弥 补中国目前在并行数据库系统上的匾乏问题，针对一定的问题进行专门的数据库优 化也将有利于将来整合成一个较为统一的系统。 1 4 并行数据库研究的问题 伴随着m p p 的发展，新的并行机分布式计算技术、计算机集群( c l u s t e r - t e c h n o l o g y ) 等引起了人们的极大关注，成为十分活跃的研究领域。并行数据库特别是并行关系数据 库已经成为数据库研究的热点。目前在并行数据库领域主要有下列问题需要解决f 1 2 】。 1 、并行体系结构：目前的并行计算机其各个处理机都具有自己独立的主存和磁盘， 不共享硬件资源，处理机之间的通信由高速网络实现。因此需要研究的是与这 些并行计算机结构相一致的并行数据库的体系结构及有关实现技术。 8 西北夫学硕士学位论文 2 、并行数据操作算法：为提高并行查询的效率，需要研究联接、句集合统计等数 据操作的并行算法。 3 、并行查询优化：对并行操作的步骤进行优化组合，以迸一步提高系统执行效率。 4 、并行数据库的物理设计：包括数据分布算法的研究和数据库设计工具的研究等。 5 、并行数据库的数据加载和再组织技术。 1 5 课题提出依据及目标 随着对并行数据库技术的进一步研究，它必将在各行各业中得到广泛的应用。不只 是大的行业、企业，很多地方的小企业，小单位也有很强的数据处理的需求，它们的数 据处理量也越来越大，传统的单机数据库系统也越来越难以满足应用的要求，他们也需 要高性能的并行数据库系统来为他们工作。虽然目前有好几种大型的并行数据库系统产 品可供选择( 如o r a c l e11 9 ) ，但是这些产品都是通用的大型数据库系统，价格也太过于 昂贵，在功能上也远远超出了这些中小单位机关的需求水平。他们需要一种既能满足功 能和性能需要，价格又不是特别昂贵的数据库系统。考虑到很多企业的数据库是架构在 w i n d o w s 平台上，他们并不需要那种跨越操作系统平台的通用并行数据库系统，而且一 般一个单位内部都会统一使用一个公司的数据库系统产品( 一般不会一个部门使用d b 2 ， 另一个部门使用其它公司的产品如o r a c l e ) ，这样，如果只针对一种系统数据平台开发数 据库系统软件，相对来说会比较容易，成本也就相应的下降了许多。这就有可能制作出 一种满足市场需要的低端高性能数据库产品，这就是我们课题提出的依据。 本文设计的p d b s 0 并行数据库中间件系统定位于一个初级的阶段。因为要实现一 个完整的数据库系统，不仅需要考虑到效率、安全、可恢复等诸多因素，同时也希望该 系统具有安全的管理机制和非常高的容错技术。但是本文的目的只是希望研究设计出数 据库系统核心的算法，其他外围应该考虑的设计不在本论文范围内。况且，追求高效率 的数据库大多数都是需要实现诸如查找、排序、连接等基本操作，所以该中间件应该着 重于核心基本功能的研究，主要实现一些数据分布、快速查询等模块。 1 6 本章小结 本章主要介绍了论文的背景和国内外研究的现状，并提出了本课题研究的依据及目 标。在后续章节中，主要从实验研究平台的搭建，系统软件的设计和实验结果分析几个 方面来进行安排。 9 第二章研究实验平台的搭建 第二章研究实验平台的搭建 并行数据库系统是数据库技术与并行计算技术相结合的产物，它是在并行机上运行 的具有并行处理能力的数据库系统。并行计算技术是利用多处理机并行处理所产生的规 模效益来提高系统的整体性能的，它为并行数据库系统提供了一个良好的硬件平台。这 一章重点介绍基于集群的并行数据库系统实验硬件平台的搭建以及软件的选择。 在并行数据库系统的研究过程中，首先需要做的就是要搭建一个实验研究的平台， 只有在这个平台上，研究者才可以尝试各种实现办法和策略。因此，实验平台的搭建在 一个并行数据库系统研究的整个过程中占据了十分重要的地位。由于当一个平台确立 后，系统的所有研究环境就已经确立，所以必需对所需要的工作进行全局的考虑，并进 行软硬件平台的选择。 2 1 并行数据库系统简介 到底什么是并行数据库? 它和我们以往理解的数据库系统有哪些不同? 2 1 1 并行数据库的实现目标 一般来说，一个并行数据库系统( p a r a l l e ld a ta b a s es y s t e m ) 应该实现以下三个目标， 以此来提供比同等的大型机要高得多的性能价格比【1 3 , 1 4 】。 1 、高性能并行数据库系统可通过面向数据库的操作系统支持、并行性、优化以 及负载均衡等相互补充的方案来获得高性能。让操作系统面向数据库操作可以简化底层 数据库功能的实现，从而降低成本；并行性可以增加吞吐量( 通过查询间并行性) 和减少 事务响应时间( 通过查询内和操作内的并行性) ；为了使并行性所带来的通信开销降至最 低，对查询进行优化和并行化是至关重要的；负载均衡是指系统将一定量的工作负荷在 多个处理器之间均匀分配。这可通过适当设计物理数据库的静态方式或在运行时调整负 荷的动态方式来实现。 2 、高可用性并行数据库系统可通过数据复制来增强数据库的可用性。这样，当 某一磁盘损坏时，该盘上数据在其它磁盘上的副本仍可供使用，且无需额外开销( 与基 于日志的恢复不同) 。当然，对于数据复制的支持需要有控制协议来保证系统数据的一 致性。例如最常用的r o w a ( r e a do n ew r i t ea l l ) 协议。此外，如果磁盘失败频繁发生， 则系统负载会严重失衡，因此数据复制应与数据划分技术相结合以保证当磁盘失败时系 l o 两北大学硕上学位论文 统仍能并行访问数据。 3 、可扩充性 并行数据库系统环境可以更容易地满足增大数据库规模或提高系统 性能的需要。这里，数据库系统的可扩充性指系统通过增加处理和存储能力而平滑地扩 展性能的能力。充分利用多处理器平台的工作能力，多个处理机协同处理，以达到更快 的数据库响应速度和分析能力。理想情况下，并行数据库系统应具有两个方面的可扩充 性优势：线性伸缩和线性加速。其中，线性伸缩指当数据库规模与处理和存储能力都呈 线性增加时，系统性能将保持不变；线性加速指当数据库规模不变而处理和存储能力呈 线性增加时，系统性能也线性增长。 在很多情况下，并行数据库的数据分布在多个处理机中并共同组成一个完整的数据 库系统。 2 1 2 并行数据库的系统结构 并行数据库系统的发展始终与体系结构密切相关。由于存在许多构成并行硬件系统 的方法，选择什么样的并行硬件结构最适合并行数据库系统的并行处理，是数据库研究 领域一直在争论的问题。理想的并行硬件应该有一台无限快的计算机，并有一个宽带无 限宽和容量无限大的内存，这在技术上是不可能的。现在的问题是如何用若干处理速度 有限的处理机及存储容量有限的内存构成一台速度和容量尽可能快和高的计算机。1 9 8 6 年，美国人m s t o n e b r a k e r 提出了三种用于构造并行数据库系统的硬件结构模型，它们分 别是：全共享结构( s h a r e d e v e r y t h i n g ) 、共享磁盘结构( s h a r e d - d i s k ) 和无共享结构 ( s h a r e d - n o t h i n g ) 【l 】。1 9 9 3 年美国学者g r a e f e 提出了第四种并行结构，称为分层并行结构 ( h i e r a r c h ys y s t e m ) 。这四种结构的示意图如图1 4 9 f i 示p , i s 。 1 、全共享结构( s h a r e d e v e r y t h i n g ) 结构 如图1 所示的s h a r e d e v e r y t h i n g 方案中，该结构包括多个处理器、一个全局共享的内 存( 主存储器) 和多个磁盘存储，各个处理器通过高速通讯网络( i n t e r c o n n e c t i o n n e t w o r k ) 与共享内存连接，并均可直接访问系统中的一个、多个或全部的磁盘存储，在系统中， 所有的内存和磁盘存储均由多个c p u 共享。i b m 3 0 9 0 、b u l l 的d p s 8 等大型机以及s e q u e n t 、 e n c o r e 等对称多处理器都采用了这一设计方案。这种结构又叫共享内存结构 ( s h a r e d - m e m o r y ) 或者对称多处理机s m p ( s y m m e t r i cm u l t i p l ep r o c e s s o r s ) 结构。 第二章研究实验平台的搭建 l 高速互联网 lll 共享内存 图1s e 结构 s h a r e d - e v e r y t h i n g 方案的优势在于实现简单和负载均衡，体现在以下几个方面： 1 ) 提供多个数据库服务的处理器，通过全局共享内存来交换消息和数据，通 讯效率很高，查询内部和查询问的并行性的实现也均不需要额外的开销； 2 ) 数据库中的数据存储在多个磁盘存储介质上，并可以被所有处理器访问； 3 ) 由于元信息( 目录表) 和控制信息( 锁表等) 可被所有处理器共享，在数据库软 件的编制方面与单处理机的情形区别也不大。 4 ) 这种结构由于采用了共享的内存，所以可以基于系统的实际负荷来动态地 给系统中的各个处理器分配任务，从而可以很好地实现负荷均衡。 然而这种结构也存在着一些不足之处，反映在以下几点： 1 ) 这种结构硬件资源之间的互连比较复杂( 每个处理器要与每个内存模块和每 个磁盘相连) ，因而硬件成本较高； 一 2 ) 由于多个处理器共享内存，所以系统中的处理器数量的增加会导致严重的 内存争用，从而导致系统性能的下降，因此系统中处理器的数量受到限制， 节点数目必须限制在几十个以内，因此系统的可扩充性较差； 3 ) 由于共享内存的机制，会导致共享内存的任何错误将影响到系统中的全部 处理器，使得系统的可用性表