（计算机科学与技术专业论文）并行数据库中并行io的研究与实现.pdf

i ：1 4 防科0 技术人学研究乍院学位论史 摘要 r 具有数据规模庞大、查询复杂度高和高实时性等特点的数据库新应用渴望 高性能数据库系统的出现。并行处理技术的同渐成熟和并行计算机系统的实用 化使其成为可能。基于并行计算机系统的并行数据库系统通过多机并行可解决 传统数据库系统的i 0 瓶颈和c p u 瓶颈问题，性价比高。近年来，国内外掀起 理论研究和系统开发热潮：国内研究水平与国际水平相比尚有较大差距。研究 开发具有高性能、高可用性和扩充性强等特点的并行数据库系统还有需要做大 量工作。 无共享结构( s n ) 是公认的支持并行最好的计算机系统结构。p c 工作站机 群系统是其中最经济最广泛的种，扩充机群系统上的多个串行数据库系统组 成并行数据库系统是一个很好的方法。在基于s n 结构的并行数掘库系统中， 大多数的数据库查询都包括磁盘i o 操”：和网络数据传输，而且随着处理机个 数的增加，磁盘i 0 操作和网络数据传输所占用的时问变得十分巨大，将严重 地制约并行数据库系统性能的发挥。因此，需要檄大可能地使c p u 与网兰 传输 和磁盘i o 许行起来，减少嘲络和磁稚i o 瓶颈，抛l i 5 系统榉体性能夕小煤越 在旗j 二p c r 作站机群的s n 结构的并行数掘库系统叶究和实脱了彤m 、拉拟i 0 系统有效地解决了i 0 瓶颈问越，提商了系统性能。 测试舐叫，我们的系统的并行i 0 方案足可行的，与串行数据麒谢i 比性能 夫人抛t ：、i ，所实现的月：行连接算法也呶掰了接近线f t 的加迷比。论文 女肝总结 了谍题和论文的j 。作，结合实际提出了将水i i 作方向。 关键词：并行数据库系统，无共享结构，并行虚拟i o ，并行连接算法 筑l l i 吼 鲤堕型竺丝尘兰塑茎尘坚：! ：竺丝兰 a b s t r a c t t h eu e wd a t a b a s ea p p l i c a t i o n s ，w i t hv e r yl a r g ed a t as c a l e ，v e r yc o m p l i c a t e d q u e r ya n dh i g hr e s p o n s i b i l i t y , a r ee x p e c t i n gd a t a b a s es y s t e m so f h i g l l e rp e r f o r m a n c e n l es u c c e s so ft h ep a r a l l e lp r o c e s s i n gt e c h n o l o g ya n dt h ea p p l i c a t i o no fm a s s i v e p a r a l l e lc o m p u t e rs y s t e m sm a k ei tp o s s i b l et od e v e l o pap a r a l l e ld a t a b a s es y s t e mo f v e r y h i g hp e r f o r m a n c e b yp a r a l l e lp r o c e s s i n go nm u l t i p l ep r o c e s s o r s ，p a r a l l e l d a t a b a s es y s t e m s w h i c hb a s e do np a r a l l e lc o m p u t e rs y s t e m s ，c a nr e m o v et h e l f o b o t t l e n e c ka n dc p ub o t t l e n e c k ，w h i c hr e s t r i c tt r a d i t i o n a jd a t a b a s es y s t e m s ，a n dg e t h i g hp e r f o r m a n c e c o s tr a t i oi nr e c e n ty e a r s 1 0 t so fr e s e a r c hw o r kh a sd o n ei nt h e w o r l d a n dm a n ys y s t e m sw e r em a n u f a c t u r e d t h er e s e a r c hl e v e li no u rc o u n t r yi s m u c hi o w e rt h a nt h ei n t e r n a t i o n a jo n e t od e v e l o pap a r a l l e ls y s t e mo fv e r y h i g h p e r f o r m a n c e a v a i l a b i l l t ya n ds c a l a b i l i t y , m o r ew o r km u s tb ed o n e i ti sw e l lk n o w nt h a tt h es h a r e d n o t h i n ga r c h i t e c t u r ei st h eb e s to n ef o l d e v e l o p i n gp a r a l l e ld a t a b a s es y s t e m s p c w o r k s t a t i o nc l u s t e rs y s t e m sa r et h em o s t e c o n o m i c a la n dt h em o s te x t e n s i v e l ya p p l i e di n s t a r i c eo fs h a r e d n o t h i n ga r c h i t e c t u r e s i t i sag o o dm e t h o dt ou p g r a d es e v e r a lt r a d i t i o n a ld a t a b a s es y s t e m si n t oap a r a l l e l d a t a b a s es y s t e m i np a r a l l e ld a t a b a s es y s t e mb a s e do bs na r c h i t e c t u r e ，m o s tq u e r i e s n e e dt h eo p e r a t i o no fd i s ki n p u t o u t p u ta n dd a t at r a n s m i s s i o nt h r o u g hn e t w o r k t h e t i m es p e n do i ld i s ki n p u t o u t p u ta n dd a t at r a n s m i s s i o nt h r o u g hn e t w o r ki sm u c hb i g w h e ni n c r e a s i n gt h en u m b e ro fp r o c e s s o r ，a n di tw i l l s e r i o u s l yr e s t r i c tt h e p e r f o r m a n c eo fp a r a l l e ld a t a b a s es y s t e m t h e nw es h o u l dp a r a l l e lt h ec p u i n t e r n e l t r a n s m i s s i o na n dd i s ki n p u t o u t p u t ，s ot h a td e c r e a s et h eb o t t l e n e c ko fi n t e m e t t r a n s m i s s i o na n dd i s ki n p u t o u t p u t a n di m p r o v es y s t e mp e r f o r m a n c e j nt h i sp a p e r w es t u d ya n di m p l e m e n tt h ep a r a l l e lv i r t u a li n p u t o u t r u ts y s t e mo nt h ep a r a l l e l d a t a b a s es y s t e mb a s e do np c w o r k s t a t i o nc l u s t e rs y s t e m ss h a r e d - n o t h i n ga r c h i t e c t u r e s o l v et h ep r o b l e mo f i n p u t o u t p u tb o t t l e n e c k ，a n di m p r o v es y s t e mp e r f o r m a n c e i t i sv e r i f i e db yt e s t st h a tt h es c h e m ef o ri m p l e m e n t i n gt h ep a r a l l e li 0s y s t e mi s f e a s i b l e i tg a i n sh i g h e rp e r f o r m a n c ec o m p a r i n gt os e r i a ld a t a b a s es y s t e ma n dt h a tt h e i m p l e m e n t e dp a r a l l e lj o i na l g o r i t h m sg a i nn e a r l yl i n e a rs p e e d u p a tl a s t t h i sp a p e r c o n c l u d e st h ef r u i t so fm yo w l lw o r ka n dp r e s e n t st h ef u t u r ew o r k k e y w o r d ：p a r a l l e ld a t a b a s es y s t e m ，s h a r e d n o t h i n ga r c h i t e c t u r e ，p a r a l l e lv i r t u a l i 0 ，p a r a l l e lj o i na l g o r i t h m s 国防科。；技术人学研究生院学位论文 第1 章引言 随着信息技术的迅猛发展和应用领域的不断扩展，新的数搌库应用呈献出 如下新的特点：数据库规模十分陇大、数据库查询越来越复杂、实时性要求高。 能否为越来越多的用户提供高事务吞吐量和低响应时间已成为衡量数据库性能 的重要指标。 然而，由于传统数据库系统固有的i o 瓶颈和c p u 瓶颈问题，越来越多的 应用表明，基于传统大型计算机的串行数据库系统缺乏支持高性能联机事务分 析处理( o l a p ) 和复杂查询操作的能力，同益加重的负载使其性能达到了极限。 进入9 0 年代以来，迅猛发展的并行处理技术和基于网络的多计算机机群的并行 计算机系统的实用化、商用化为高性能数据库系统的实现带来希望。因此，近 几年柬，基于并行计算机系统的并行数据库系统迅速成为一个觏的数据库研究 领域。 制约串行数据库系统性能主要有以下两个因素： f 1 ) i o 麓颈当静磁盘技术的发展严重滞后于微处删器和内存技术的发 展，阿者与后者相差至少一个数量级，甚至更高，这使得磁盘i o 瓶颈 问题闩益突出。 ( 2 ) c p u 瓶颈由于大量的数据仅出单个c p u 逐个地处理，处王 | ! 上亿字节 数据所需的处理能力显然 理单个c p u 所能提供的处理能力不匹配。比如 复杂查询中的算术运算、连接运算，特别是基于嵌套循环算法的连接运 算等。 计算机多处理器结构以及并行数据库服务器的实现为解决以上问题提供了 很大的可能。通过将数据库分柿存储在多个磁盘上，可以利用多个处理器对磁 盘进行并行处理，从而解决了c p u 瓶颈和磁盘i o 瓶颈问题。同样，潜在的主 存访问瓶颈也可通过并行性而获得解决。并行数据库系统通过丌发事务问的并 行性、查询间的并行性、查询操作i 叫的并行性和查询操作内的并行性可以大大 提高查询效率。为实现不同粒度的并行性，并行数据库研究主要围绕硬件体系 结构、数据划分、并行数据操作算法和并行查询优化四个领域进行。硬件体系 结构将在下一节详细介绍，此节不作叙述。 1 1 1 数据划分 数据划分的核心问题是如何在多处理器或多磁盘之间分析i 每个数据库关 系，以达到蛮询内、操作内的两种低粒度， f 行，使查询处理时最小化。数捌 划分策略刈于能甭充分利用系统的c p u 和带宽资源，减少通信 销，中衡系统 第1 页 因防秆技术人卞究生院。f 口论史 负载和减少计算量，从而能否最佳地发挥并行性和系统性能至关重要。如果数 据分布不合理，系统资源将遭到浪费，系统的并行性不能得到充分的发挥，既 增加了查询处理时间，也降低了系统的处理能力。按划分属性数，数据划分方 法i 州可以分成一维数据划分和多维数据划分，它们都属水平划分。常用的维 数据划分方法有r o u n d r o b i n 划分、h a s h 划分和r a n g e 划分。一维数据划分不能 很好地支持在关系的非划分属性上具有条件谓词的数据查询。这样的查询必须 被送到所有包含操作关系的元组的处理节点上进行。显然，把一个数据操作送 到不包含所需元组的处理节点是完全没有必要的，必然浪费大量系统资源，降 低系统的处理能力。为此，人们提出几种多维数据划分方法f l o l ，如c m d 方法、 b e r d 方法和m a g i c 方法。 许多研究表明，使用并行数据库操作算法实现查询的并行处理能更充分发 掘并行处理机器的并行性，更大地提高系统的查询处理效率。因此，数据库操 作算法的研究已经成为最近几年一个非常活跃的并行数据库系统研究领域。l 于j o i n 操作是数据库操作中最耗时而又最常用的操作，大量并行数据库操作算 法研究都围绕连接操作进行。基于不同体系结构和数据分伽，人们提出了各种 j o i n 算法1 1 r s i i ”】包括并行嵌套循月= 连接算法( p n l j ) ，并行排序归并连接算法 ( p s m j ) 并行哈希连接算法f p h j ) f 1 。其中p h j 算法是研究焦点，人们先后提出 了g r a c e h a s h j o i n 算法( p g h j ) 、h y b r i d h a s h j o i n 算法( p h h i ) 和幕j 二划称位向 , “p ( s y m m e t o3 ，b i tv e c t o r ) 的p h h j 鳃法一。 研究表明，数据分布的不均匀性即数据偏斜对并行j o i n 算法效率影响很大 2 。1 1 ”l 。数据偏斜在实际应用中是不可避免的，因此人们又提出了一些抗数据偏 斜影响的并行j o i n 算法i ”】它们的共同思想是通过数据的动态再划分来保证负 载平衡。 1 1 3 并行查询优化 查询优化在并行数据库系统中占重要地位。并行数据库查询优化的目标是 寻找具有最小响应时间的执行规划，而查询执行工作量不是首要的。并行数据 库查询优化研究包括查询规划模型研究和查询优化算法研究两方面。目| j i ，基 于查询树模型f ”】1 3 0 ，人们先后提出了基于左线性树的查询优化算法2 l 、基于右 线性树的查询优化算法】、基于浓密树的查询优化算法2 和基于操作森林的查 询优化算法1 1 3 1 。 除了以上四个主要研究方向外，人们还对并行数据库的数据装载1 和再组 织4 、处理机调度与系统负载平衡及并行恢复、并行索引与并发控制等进行了 研究并取得了一定成果。 幽防科二j 投术人。学研究生院。f t 沦史 在过去的几年里，并行数掘库系统研究一直以下列三种并行计算结构为基 础：共享主存储器( s h a r e dm e m o r y , 下简称为s m 结构) ，共享磁盘结构( s h a r e d d i s k ，下简称为s d 结构) 和无共j z 结构( s h a r e dn o t h i n g 下简称为s n 结构) 。 s m 并行结构由多个处理机、一个共享主存储器和多个磁盘存储器构成。 多处理机和共享主存储器由高速通信网络连接，每个处理机可直接存取一个或 多个磁盘存储器。s m 并行计算机结构如图1 1 所示。这种实现简单，而且可以 基于实际负荷来给各处理器动念地分配任务，因而可以很好地实现负载平衡。 但是，这种结构的系统出于硬件成员之间的互连很复杂，因而成本高昂。而且， 为了避免由于内存访问冲突增多而导致系统性能下降，节点数目必须限制在几 十个之内。此外，内存的任何错误都将影响到多个处理器，因此系统的可用性 不好 3 “。 s d 并行结构由多个具有独立主存储器的处理机和多个磁盘存储器构成。 每个处理机都可以读写任何磁盘存储器。多处理机和磁盘存储器由高速通信网 络连接。s d 并行计算机结构如图1 2 所示。这利一结构的系统的成本较之s m 要 低：”每，个处理器有足够大的高速缓存，孙l 删，对其享磁盘的访问冲突州衙爷 最低，i 划此i i 丁扩充性相对很好，节l i 数1 1 , j - 达数“个；i - 个处罔! 器m j i 的失败 才i 敛影i 目其它处理器的工作，吲胁系统j 川性i 叠。似是存在潜在的刈lr 磁擞 访问的竞争| 、u j 题和缓冲区数据一致性的问题。 i 联网络 儿享存储器且联网络 幽1 1 s m 缔构并行计算机 幽i 2s d 结构并行计算机 s n 并行结构由多个处理机结点构成。每个处理机结点具有自己的处理机、 主存储器和磁盘存储器。多个处理机由高速通信网络连接。s n 结构并行计算机 如图1 3 所示。与s d 结构一样，s n 结构的成本也较低。数据库权威人士 s t o n e b r a k e r 指出s n 结构是支持并行数据库系统最好的体系结构7 ，这个观点 已被普遍接受。s n 结构有三个主要优点： ( 1 ) s n 结构通过最小化共享资源使得由资源竞争带来的系统干扰最小 化： ( 2 ) s n 结构具有高可扩充性，处理机个数可扩展至数百个甚至，i ：千个而 1 i 增：! j i j 处y 1 1 j j ) l i n j 的f 扰： 凳3 页 国防科学技术人学研究生院学化论文 ( 3 ) s n 结构在复杂数据库查询处理和联机事务处理过程中可获得接近线 性的加速比。 互联网络 豳1 3s n 结构并行计算机 目的，并行数据库系统的实现模型可分成三种：重写、扩充和半重写变换。 重写方案通常在研制并行数据库原型系统时被采用，如著名的g a m m a 系统h j 。 但传统的关系数据库技术已发展了二十年，大量商品化系统得到广泛的应用并 具有良好的可靠性。因此，更为普遍采用的模式是在现有串行数掘库系统中扩 充并行处理能力。，其中典型代表1 2 唷o r a c l e 公司的o r a c l e7 0 上的“并行数掘库 服务器”和o r a c l e8 x 系列、s y b a s e 公司的s y b a s es y s t e m1 l 上的虚拟服务器结 构( v s a ) 和s y b a s em p p 、i n f o r m i x 公司的l n f o r m i x o n l i n e7 x 、i n f o r m i x o n l i n e 8 x 上的动念服务器、i b m 公司的d b 2p e 、d b 2u d be e e 。 “半重写变换”模型是重写模型和扩充模型的结合，它要求以传统的d b m s 核一t l , 为基础，但不要求修改原代码。“半重写变换”模型对影响并行数据库效率 的部分进行重写，重写后的并行数据库仍利用原来基础d b m s 系统的界面与其 交互，用户提交的s q l 查询经编译和并行优化后被变换为并行执行规划。 前面我们已经指出，提供高的事务吞吐量和低的响应时间是衡量数据库系 统性能的重要指标。并行数据库的各项研究也主要是以此为其最终目标。从根 本上来看，它们都是从不同的侧面来解决串行数据库的c p u 瓶颈和i o 瓶颈问 题的。并行体系结构通过增加处理机和磁盘部分地解决了c p u 瓶颈和i o 瓶颈 问题；数据划分通过好的划分策略来减少数据通信丌销，以达到减少总的i o 次数和延迟，解决i o 瓶颈；并行数据操作算法通过充分发掘处理器问的并行 性，使各个处理机分担一部分查询任务，以减少执行时间；并行优化通过丌发 查询的并行性，重迭i o 延迟来解决i o 瓶颈，减少查询执行时间。综上所述， 所有的研究大都是以解决i o 瓶颈为目标的，可见i o 瓶颈是数据库的主要问 第4 页 国防科，技术人学研究生院学位论文 题。如何解决1 1 3 瓶颈，这也就赴我要研究和解决的主要问题之一 从上一节我们可以看出，在支持并行数据库系统的并行计算结构中，无共 享结构( s n 结构) 和共享磁盘( s d ) 结构是支持并行化最好的两种结构。s n 结 构由于各处理机的共享资源少，因而由资源竞争带来的干扰小，具有良好的可 扩展性。但是由于数据分布在不同的处理机上，当数据的划分策略不好时，由 于数据共享而引起的网络通信量较大，网络通信成为影响数据库性能的“瓶颈”； s d 结构由于各处理机共享磁盘，因而具有高的通信带宽和低延迟，但是当处理 机数目达到一定程度时，各处理机之间对共享磁盘的访问竞争使各处理机之间 的干扰变大，对共享磁盘的访问竞争成为“瓶颈”。如果把s d 结构和s n 结构 的优点结合起来，在s n 结构中把网络通信和磁盘d o 重叠起来，使其像s d 结 构中那样，感觉不到网络通信的存在，所有的数据存取好像都在共享磁盘上操 作一样，对于提高系统的整体性能将是一项有意义的工作。如何在s n 结构下 模拟实现s d 结构的优点是我要研究的另一问题。 在设计基于s n 结构的并行数据库系统时，由于各节点的自治性，数据是分 布在各个处理节点上的，因此，查询处理器在执行查询操作时需要知道数据所 在的结点，也需要在执行查询时交换数据，这样影响了查询处理器的独立性， 使查询处理器的实现复杂化。从上面并行数据库的实现模型来看，在保证性能 的前提下我们应使并行数据库的实现尽可能简单，因此，必须使查询处理器的 设计独立化。为增加查询处理器的独立性，使查询处理器的实现简单化和独立 化，我们有必要提供一种方法使对串行数据库的查询处理器不用做太多的修改 就可用于并行数据库，并为查询处理器提供数据分布的位置透明性，使查询处 理器不必关系数据的分布细节。这是我要研究的第三个问题。 由于数据库的查询操作一般涉及的数据量较大，且数掘具有一定的局部特 性，大多数i o 是可以预测的，因此我们可以采用异步i o ，以实现c p u 和i o 的并行执行：如果同时我们知道还有哪个处理器需要数据，就可以在执行i o 操作的同时执行网络数据传输，实现i o 和网络通信的并行。 另外，在多个任务同时执行的情况下，局部处理节点上不同任务的i o 操作 可能出现重复的情况，对同一关系的随机i o 请求在一定范围内也可能是有序 化的，因此可以通过对i o 操作的重组和排序，减少数据读取时间和磁盘寻道 延迟时问，最终缩短查询执行时间。 因此，本课题寻求在操作系统的支持下，设计一个独立完成磁盘i o 操作和 网络通信的并行虚拟i i o 系统，在保证原串行数据库并行操作算法的确定性的 前提下，达到在s n 结构下模拟实现s d 结构的共享磁盘的特性，减小网络和磁 盘i o 瓶颈，提高系统的整体性能的目的。 为此，我采用s n 系统结构，利用现有的串行o a l a x y d b 数据库系统，设计 并实现了一个基于p ：，工作站机群环境的并行数据库系统的并行虚拟i o 系统一 一p v d b 。 1 5 论文组织 论文的讨沦围绕基于s n 结构的并行数据库系统展丌，后续部分安a o n t 箱5 页 堕堕型鲎垫查叁! ! 翌壅尘堕竺生丝兰一 第2 章介绍设计p v d b 所基于的并行数据库模型及相关知识。第3 章首先介绍 p v d b 设计的总体结构，接着讨论了有关的关键技术，最后举例说明了并行数 据库系统中并行查询的执行过程。第4 章详细介绍p v d b 的实现。第3 、4 章 是课题中心工作又是论文论述重点。第5 章给出了应用p v d b 的并行数据库系 统的功能和性能测试结果，最后是课题总结和下一步的工作。 1 6 本文约定 论文标题分三个级别，从高到低分别称为章、节和小节。 1 6 1论文插图每章独立编号，章内按序编排。图号形式为图x y ，其中x 为章号，y 为该图在该章内的序次。 1 6 2流程所采用的编号形式为流程x y ，编号方法同( 2 ) 。 1 6 3定义则是按节独立编号，同一节内按序编号，标示形式为定义m n 鱼 其中m 为章号n 为节号，s 为序次。 1 ，6 4在一句话中出现形如“页面( 或元组) ”的表述是指旬中所有出现“页面” 的地方都可用“元组”代替，叙述仍然成立，只是被缩写了。 第6 页 国防科掌技术人学研究生院学何论文 第2 章系统模型 图2 1 显示了基于s n 结构的具有p v d b 的并行数据库系统结构。用户在任 意一计算机上提出查询请求并传送给控制节点。控制节点负责接收用户的查询 请求，对查询请求进行语法分析形成查询规划，在进行并行优化后将并行子 查询分别发送给相关处理节点上的子查询服务器。各子查询服务器主要负责并 行予查询处理，通过p v d b 实现对各局部处理节点的局部数据库的i o 操作。 处理节点i 由局部查询服务器i 、本节点上的p v d b 和局部数据库d b i 组成。 用户；i 用户：i ；r 用户m l ，jl _ 一 控制节点 童一l 童询 i 删啊瞒f 彝ij 务2i f - ”i p v d b 图2 1并行数据库系统的结构 上图中，控制节点负责接收用户递交的各种数据库查询命令并通过检索在 本机上的并行信息库选择查询参与节点；接着把查询分解成多个子查询；然后 把子查询交给选中的参与节点上的局部查询服务器后台进程执行：最后回收合 并各后台处理结果向用户返回。每个局部查询服务器将子查询看作一个出它自 己独立完成的子任务。系统全局数据按某种数据分布方法分存在参与节点的本 地硬盘中，称每个节点上存放的数据为局部数据。必要的话，子查询所处理的 数据除了包括本地硬盘存贮的局部数据之外还包括其他节点上的数据，此时后 台进程向其他节点上的后台进程请求数据或由其他节点主动把数据传送过束。 控制节点是并行数据库系统的前端，向用户呈现一个逻辑视图，并行机制 对用户是透明的。前端与任一局部查询服务器后台进程闻以c l i e n t s e r v e r 模式 进行通讯。在不产生混淆的情况下，简称局部查询服务器后台进程为后台或后 台( 服务器) 进程。 每个局部查询服务器执行的查询过程基本l 与串行d b m s 相同。所4 i 同的 第7 页 国防科学技术人学研究生院学何论文 是并行查询处理中每个局部查询服务器可能需要对外发送数据，并接收其他节 点发送来的数掘，实现数据共享。各局部查询服务器具有以下自治性： 局部查询服务器是串行d b m s 的扩充，仍具有单独处理串行查询的 能力； 各节点上数据的组织完全等同于串行系统中数据组织模式： 存放在节点k 上的数据只能由本节点上的局部查询服务器存取，不 为其它节点上的局部奁询服务器所见。 在并行查询处理中，每个参与节点的局部查询服务器被指派个子 处理任务并在处理过程中可能实现数据共享： 局部数据的管理和维护须出并行系统进行全局统筹安排以保持一致 性和完整性。 并行数据库系统中有全局查询和子查询两种不同的查询，定义如下： 定义2 1 1 ：对全局逻辑数据实施访问处理的查询命令称为全局查询。 定义2 1 2 ：仅访问处理单个节点上的局部数据的查询命令称为予查询。 全局查询和子查询的根本区别在于所处理的数据的范围不同。用户向胁端 递交的查询命令即为全局查询命令，它访问的是由多个节点| 二的局部数据综合 起柬的全局数据；a u 端向后台递交的命令则是予查询，它访问的是单个f i 点上 的局部数据。 在各节点上，数据的组织完全等同于串行系统中数据组织模式，刁i 必为支 持并行而作特殊处理。这大大减少了扩充工作量。当用户在并行数据库系统内 创建一个数据库时，他创建的是全局数据库。控制节点将在多个节点上分别创 建一个局部数据库。为区分这两类不同层次的数据库，本文定义全局数据库和 局部数掘库如下，简称全局( 局部) 数据库为全局【局部) 库。 定义2 2 1 ：用户在并行数据库系统上创建的，物理上由存储在一个或多个 节点上的局部痒组成数据库称为全局库。 定义2 2 2 ：存储在单个节点上的、必须由并行数据库系统统一管理、存取 的同属于一个全局库的多个物理数据库，称为局部库。 全局库是一个逻辑数据库，用户不必了解数据存储细节。局部库只为本节点 局部查询服务器所存取访问，对用户透明。对局部查询服务器而占，局部库是 自己管理的串行数据库，但存取访问由系统统一调度，单独访问局部库将导致 错误。 同理，用户在使用数据库过程中，执行创建一个关系操作时，控制节点将 在多个节点上分别创建一个物理关系。为区分这两类关系，定义全局关系和局 部关系如下。 定义2 2 3 ：用户在并行数据库系统的某个全局库上建立的，由一个或多个 节点上的物理关系组成的逻辑关系，称为全局关系。 定义2 2 4 ：存储在单个节点上的属于一个全局关系的物理关系，称为局部 第8 页 国防科了技术人。研究生院学何论文 关系。 全局关系是用户所见到的逻辑视图，关系分布细节对用户透明。并行查询 分解器将保证局部关系隶属于全局库的局部库。 任一全局关系r 的元组都按照一种数据划分方法分存在各局部关系r 中 ( i = l ，2 ，n ，i a 为局部关系总数) 。当前普遍采用的划分方法都是水平划分。 每个局部关系是全局关系的一个片段，它们必须是完全的，即下式须成立： r = r i y r 2 y y r l l 控制节点负责实施数据划分。数据划分是把一个全局关系的全部元组分划 成多个局部关系分存在各节点上。局部关系之间可以相互重叠即内含相同的元 组，此为数据冗余。并行数据库系统一般只允许下面两种冗余，不允许出现混 合冗余。 ( 1 ) 完全无冗余：任两个局部关系交集为空： ( 2 ) 完全冗余：每个局部关系等同于全局关系。 完全冗余旨在减少节点问的数据传递和协作，加速查询处理速度。在这种 情形中，后台之间不需要共享数据。本文的后续讨论围绕完全无冗余情形展丌。 该模型中，局部数据库( 关系) 的名字与全局数据库( 关系) 的名字相同。这样 能使大多数全局查询命令不经修改就能用作子查询命令，如元组插入、删除、 修改命令：对少数必须修改的查询命令如建表命令，也保证改动量戤少。 2 3 控制节点 控制节点是并行数据库系统和的台应用程序的接口。它与每个局音| j 查询服 务器建立连接通道，每个局部查询服务器都是它的后台s e r v e r 。控制节点将列 用户递交的命令进行分析，根据数掘分布的情况选择有关后台参与处理：然后 把查询语句原样地或经少许修改后传送给参与节点，并激活工作节点。控制节 点同时管理维护结点配置信息和数掘分布信息：它始终与在其上的并行信息库 相连接，随时检索数据分耜信息；当数据分布发生变动时更改分布信息记录内 容。 并行信息库用来保存系统节点配置信息和数掘分布信息，由控制节点全权 负责管理、访问和维护。节点配置信息用来说明当前系统节点可用性；数据分 相信息则列出用户所使用关系的存放场所等信息。 2 3 1 并行信息库 并行信息库用来保存节点配置信息、全局库和全局关系的分稚信息。目前， 我利用局部查询服务器能够执行串行数据库操作的能力，把并行信息库组织成 一个串行数据库，分布信息用一些固定的关系来描述。节点的配置信息包括节 点在系统内的编号、节点的i p 地址、后台服务器进程监听端口号、节点是否可 用标志四项。结点配置1 二作 | j 系统管理员实旌。 令j 4 库和令局荚系的分和信息也捅： 1 全局侔分伟信息3 项： 第9 页 国防科学技术人警：研究生院学何论文 数据库名、 存储节点数、 节点编号数组： 2 全局关系分布信息5 项： 数据库名、 关系名、 存储节点数、 节点编号数组、 数据划分方法： 3 属性说明信息5 项： 数据库名、 大系名、 属性名、 属性类型、 1 关键字标志： 4 根据数据分稚负载分配存储空i i b j 信息，包括新增局部关系的存放节点 及插入元组存放位置等。 t - 述全局库和全局关系的分布信息在目l ； 的系统中是完备的。随着数据划 分方法和并行数据库操作算法的增加，分椎信息种类将进一= 少扩大，同时应目 的积累将使信息条目不断增多。把并行信息库组织成一个串行数据库是很有效 的手段，充分利用了串行数据库系统的已有能力。 并行信息库存放在控制节点上。并行信息库的管理、检索和维护全7 i j ：；幽控 制节点通过其局部查询服务器实施，对用户透明。 2 3 2 节点配置 收到“节点配置”命令后，控制节点将显示如图2 2 所示用户界面。 图2 2 配誊仃点界面 系统管理员可以在此增加个处理节点；删除不可用的处理节点；标记一个 柏点不可用或恢复不可用节点为可用。控制节点根掘配置操作自动修改并行信 第+ 1 0 页 国防科- 7 技术人学研究生院学何论文 息库中节点配置信息。 目前节点配置管理属于静态配置，系统管理员必须手工配置节点当前是否可 用。系统尚未能支持动态检测节点可用与否并配置节点状态信息的功能。 数据偏斜对并行数据库系统的性能，如线性加速比和规模比影响很大，而 r o u n d r o b i n 方法实现了最大限度的数据均匀性，是并行数据库系统普遍采用的 数据划分方法。因此，我们的并行数据库系统也采用r o u n d r o b i n 数据划分方案。 实施r o u n d r o b i n 数据划分方案较简单。设有全局关系r 分存在k 个节点上， 节点编号依次为0 ，1 ，k 1 。执行往关系r 内插入元组的操作时，第一次 选用节点0 ：以后若上一次选用节点j ，则本次选用节点( i + 1 ) r o o dk 。易知， 此方法保证最大分片和最小分片至多相差一个元组，一个分片等价于一个节点 上的局部关系。系统目前仅在用户插入元组时按轮转顺序选择节点存放新元组， 在删除元组时未加任何考虑。 r o u n d r o b i n 数据划分方法的不足是不能充分利用数据特性很好地支持高效 的并行数据库操作算法。 图2 3 为并行虚拟i d p v d b 的软件结构图( 仅单个节点的情况，其它 节点与此相同) 。各处理节点上的读进程、接收进程和发送进程组成本节点的 p v d b 。其中读进程负责进行任务的重新组合、从磁盘中读取数据放入共享缓 冲区中，执行具体的物理i o 操作，在必要的时候通知发送进程发送数掘。接 收进程负责从网络上接收控制节点的任务、其它处理节点传输过来的数掘、接 图2 3 并行j o p v d b 结构 收本节点各查询处理进程的读请求和各种i p c 消息，将各请求组合排序插入请 求队列。发送进程负责在需要时将凑进程读取的数据发送给其它的处理节点。 本h i 点：的各进程之问通过i p c 消息机制进行通信。所有处理1 2 节点上的p v d b 第1 l 页 里堕型竺垫查查兰婴窒生堕堂堡堡苎 共同组成并行虚拟i o 系统，完成磁盘操作和网络通信。 并行虚拟i o - p v d b 的读操作过程如下： a )各个查询处理器进程将读请求发送给接收进程，接收进程将其登记 在请求队列中。在请求队列中，对于同一关系的读请求按磁盘块顺序 进行排序。 b 1读进程根据本节点的数据在磁盘上物理分布信息调度各读请求。将 读取的数据放入共享缓冲区，或者进行h a s h 分成不同的组。并根据 具体情况决定是否需要发送该数据给其它节点。在需要发送时，给发 送进程送一消息，请求发送进程发送数据。 c )发送进程将数据缓冲区中的数据发送到其它处理节点处。发送时， 发送进程将根据该数据覆盖的处理节点数和网络结构确定是采用点到 点方式还是广播方式发送。当覆盖数超过一阀值时采用广播方式。该 阈值由通讯开销同磁盘开销比确定。覆盖处理节点数超过阈值时，说 明消息的发送开销将大于磁盘开销，磁盘操作将无法掩盖通讯，将采 用广播方式发送减少消息的发送量。当覆盖处理节点数小于该阈值 时，磁盘操作可以掩盖通讯操作，将采用点到点方式将数据分别发送 到相关节点。在广播方式中，发送进程将数据形成一个广播报文发送 网络上，由其它节点自动接收。在点到点方式中，发送进程将属于同 一处理节点的数据打包发送。 第1 2 页 国防科学技术人学研究生院学位论文 第3 章并行虚拟i o 的设计 并行虚拟i 0 的设计思想是利用软件和操作系统来在s n 结构中模拟s d 结 构的共享磁盘存储器特性，对用户和局部查询服务器提供数据的位置透明性， 同时尽可能使各节点的后台服务器的查询处理与磁盘i o 、网络通信三者并行执 行，减少系统响应时间。用户不必关心所需要的数据的存放位置，可以像使用 集中式数据库一样，认为他( 她) 所使用的数据就存放在本地。当局部查询服 务器访问的数据不在共享缓冲区时，便产生缺页信息，由并行虚拟i o 找到相 应的块( 页) 并驳回，然后通知局部查询服务器数据已经取到。 3 2 并行连接算法及相应的i o 信息 在基于无共享结构的并行数据库系统中，数据库中的数据一般根据定的 策略分布在不同的节点上。控制节点对查询进行并行优化和查询分解，形成多 个可以并行执行的子查询，并调度各个处理节点并行执行这些子查询。局部节 点的局部查询服务器在执行分配的子查询时，其所需的数据可能需要从其它节 点上获取。并行g a l a x y d b 的控制节点在分配予查询时将这些i o 信息发送给相 关的节点的p v d b ，出p v d b 完成所需的磁盘i o 操作和网络数据传输，从而 局部查询服务器在执行其子查询时只需要向本节点的p v d b 进程请求数据即 可，不需要了解数据的分布，实现数据分布对子查询的透明性。另外，由于数 据是在多个节点上分布的，p v d b 充分利用数据的分抑性，在多个节点上同时 启动p v d b 相关的1 1 0 进程，这些i o 进程协同操作，并行地完成控制节点交 给的i o 任务，实现了数据i o 的并行化。 控制节点产生两类信息：子查询和i ，0 信息。子查询发送给相关执行节点， i t o 信息发送给p v d b 的相关i o 进程。 不失一般性，设关系a 分布在节点l 、2 上，分别为a ，a ，关系b 分布 在节点2 、3 上，分别为b ，b ，。考察如下查询u ： s e l e c t a x ，b y f r o ma ，b w h e r ea x = b y ； 控制节点接收到该查询后，根据关系的分布信息分别向节点1 、2 、3 发送 以下子查询和i o 信息： 节点1 ：执行予查询u ，i o 信息为读取本节点上的关系a ，从节点2 、3 上 接收关系b 。 节点2 ：执行子查询u ，i o 信息为从本节点上读取关系a ，从本节点读取 并从节点3 接收关系b ，同时将本节点的关系b 发送到节点l 。 节点3 ：不执行查询，i o 信息为读取本节点上的关系b ，然后发送到节点1 第1 3 页 和2 。 即将查询分解为a o 表示将向外面发送数据。 第1 4 页 国防科学技术大学研究生院学位论文 ( 2 ) 设置数据库信息 消息类型( p v d bs e t d b ) 、任务标识、数据库名长度、数据库名 ( 3 ) 计算关系的页面数( 或元组数) 信息 消息类型f p v d b _ p a g e s ) 、任务标识、结点个数、关系名长度、关系名 结点数为0 表示将不从外面接收数据 结点数为n 表示将从n 个外部结点接收数据 ( 4 ) 开始读取页面信息 消息类型( p v d bo e t p a g e ) 、任务标识、结点个数、关系名长度、关系 名 结点数为0 表示将不从外面接收数据； 结点数为n 表示将从r 1 个外部结点接收数据； p v d b 接收到开始读取页顽信息p v d bg e l w 岖e 后，开始读取数据并和 局部查询服务器进行交互：局部查询服务器接收到开始执行查询语句的命令后， 开始执行查询，并和p v d b 进行交互。此后，p v d b 和局部查询服务器互相合 作完成查询任务。 控制节点收鲥局部查询服务器的查询结果后，通知p v 】) b 结束该次查询任 务；发送任务结柬消息给p v d b ，其中包含：消息类型( p v d be n d ) 和任务 标识 定义3 1 ： 设r t ，k 是r 的p 个子集合，s i ，s ，是s 的p 个子集 合，a 是关系r 和s 的连接属性。如果对于所有r r ，所有s es j ( i j ) ，r 【a 】 s a 】，则称子集合对( r ，s i ) 是可独立连接对。 并行排序合并连接算法由两个阶段即排序和连接阶段组成。在排序阶段， 它按