（计算机应用技术专业论文）并行数据库系统负载平衡技术的研究.pdf

中文摘要鼍誓i i i 薯ii i i i 一一i i i i i i 葺中文摘要基于s h a r e d n o t h i n g 结构的并行数据库系统具有良好的可扩展性，既能满足海量数据的存储要求，也能提供高效的查询处理性能。因而得到了广泛的应用。在并行数据库的研究中，负载平衡对于查询处理的性能有着很大影响，本文致力于并行数据库负载平衡技术的研究。并行数据库负载平衡技术分为静念负载平衡和动态负载平衡两种。数据划分和数据重组技术都是有效的静态负载平衡方法。本文的研究内容主要包括并行数据库的数据划分策略、数据重组策略和动念负载平衡技术。目前已有的并行数据序数据划分选择算法均是根搬预知的查询负载给出优化的数据划分方案，不能适应系统查询负载的变化。本文提出的数据划分选择算法，能够随着数掘库查谢负载的变化动态选择j ：行数据库的数据划分策略，使得数掘库的整体查i f l 性z h 。e 保持最优。本文还提出了种r c m d 数据划分策略，j q 以有效地支持多种类型查询。并行数据库数据划分的调整会导敛代价昂贵的数掂重细。目前的数据重组方法在数拟重组j n j 叫，小能保证刈赶咖请求的快速响心。本文挺出的数据迁移和数据氯组算法以及在线重组期间的查询处i 咀方法，能够有效地支持在线重组期间对川户森询的快速响应。在动态负载平衡研究方商，本文提出了动念负载平衡的j o i n 和a g g r e g a t i o n 算法。这两种算法根掘各结点当前的负载状况调度任务的执行，平衡各结点的负载，提高了操作执行的效率。耻论分析和实验结果证明，本文提出的方法能够有效地解决并行数据库的负载平衡问题。关键词：并行数据库数据划分策略数据重组数据迁移动态负载平衡外文摘要a b s t r a c tp a r a l l e ld a t a b a s es y s t e m sb a s e do ns h a r e dn o t h i n gs t r u c t u r ei sae f f e c t i v es o l u t i o nf o rm a s s i v ed a t am a n a g e m e n ts i n c ei tc a np r o v i d es u f f i c i e n tc o m p u t i n ga n ds t o r a g er e s o u r c e s l o a db a l a n c i n gi sak e yi s s u ef o rq u e r yp r o c e s s i n gp e r f o r m a n c ei np a r a l l e ld a t a b a s es y s t e m s ，w ec o n d u c tt h el o a db a l a n c i n gp r o b l e mi nt h i sp a p e r t h el o a db a l a n c i n gt e c h n i q u e si np a r a l l e ld a t a b a s es y s t e m si n c l u d es t a t i cl o a db a l a n c i n ga n dd y n a m i cl o a db a l a n c i n g t h ed e c l u s t e rs t r a t e g i e sa n dd a t ar e o r g a n i z a t i o no fd a t a b a s ei st h ee f f e c t i v es t a t i cl o a db a l a n c i n gt e c h n i q u e si np a r a l l e ld a t a b a s es y s t e m s t h i sp a p e rm a i n l ys t u d y st h et e c h n o l o g i e so fd e c l u s t e rs t r a t e g i e s ，d a t ar e o r g a n i z a t i o nt e c h n i q u e sa n dd y n a m i cl o a db a l a n c i n gm e t h o d s t h ed e c l u s t e rs t r a t e g i e sh a v eg r e a ti m p a c t so nt h eq u e r yp r o c e s s i n gp e r f o r m a n c ei np a r a l l e ld a t a b a s e t h ee x i s t e dd e c l u s t e rs t r a t e g i e ss e l e c t i o na l g o r i t h m so u t p u ta no p t i m a ld a t a b a s ed e c l u s t e rp l a nw i t hag i v e ns t a t i cq u e r yw o r k l o a d ，h o w e v e r ，i ti s n ts u i t a b l ef o ro l t pd a t a b a s ei nw h i c ht h eq u e r yw o r k l o a d sv a r yw i t ht i m e t h i sp a p e rp r o p o s e sa na d a p t i v et e c h n i q u et ot u n et h ed a t a b a s ed e c l u s t e rp l a nw i t ht h ev a r y i n gw o r k l o a d s ，w h i c hc a nk e e pt h eo p t i m a ld a t a b a s ed e c l u s t e rd u r i n gt h el i f e t i m eo fd a t a b a s e an o v e ld e c l u s t e rs t r a t e g yr c m di sa l s op r e s e n t e di nt h i sp a p e r c h a n g i n gp a r a l l e ld a t a b a s ed e c l u s t e rc a l lc a u s et h ee x p e n s i v ed a t ar e o r g a n i z a t i o n t h ee x i s t e dm e t h o d sd e c r e a s et h eq u e r yp r o c e s s i n gp e r f o r m a n c es h a r p l yd u r i n gt h ed a t ar e o r g a n i z a t i o np e r i o d w ep r o p o s es e v e r a ln o v e ld a t am i g r a t i o na n dd a t ar e o r g a n i z a t i o na l g o r i t h m sa n dq u e r yp r o c e s s i n gm e t h o d si nt h er e o r g a n i z a t i o np e r i o d ，w h i c hc a ng e tt h eo p t i m a lp e r f o r m a n c e d y n a m i cl o a db a l a n c i n gs t r a t e g yi sa ne f f e c t i v em e t h o df o rt h es k e wi i 外文摘要w o r k l o a dd u r i n gq u e r yp r o c e s s i n g w ep r o p o s ej o i na n da g g r e g a t i o na l g o r i t h m sb a s e do nt h ed y n a m i cl o a db a l a n c i n gs t r a t e g y ，w h i c hc a nr e b a l a n c et h ew o r k l o a da m o n gt h ep r o c e s s o r sd u r i n gt h er u n n i n gt i m eo ft h ea l g o r i t h m t h e o r e t i c a la n a l y s i sa n de x p e r i m e n tr e s u l t ss h o wt h a tt h ea l g o r i t h m sp r o p o s e di nt h i sp a p e ra r ee f f e c t i v e k e y w o r d s ：p a r a l l e ld a t a b a s e ，d e c l u s t e rs t r a t e g y ，d a t ar e o r g a n i z a t i o n ，d a t am i g r a t i o n ，d y n a m i cl o a db a l a n c i n g 第1 章引言1 1 研究背景第1 章引言数掘库技术是一项十分重要的计算机技术，它在很多应用领域发挥着关键作用。同时，随着应用的积累和i n t e r n e t 技术的闩益普及，以及大量海量信息数据的出现，众多一直在发挥作用的数据库的数据量和工作负荷日益加重，并呈现出数据库规模十分庞大、数据库查询越来越复杂、实时性要求高的特点。传统数据库系统已很难适应迅速增长的性能要求。近十几年来，在上述应用需求和并行处理技术发展的双重驱动下，并行数据库技术一直是研究界和工业界的瞩目焦点。大部分主要的数据库厂商，如i b m ，m i c r o s o f t ，n c r ，o r a c l e ，s y s b a s e 等都推出了并行数据库产品。并行数掘库技术正在各种大肌模应4 j j 发挥作：i ，并将不断面对新的挑战，成为未来高性能数据库系统的必d j 之蹄。并行数据库系统研究直以兰种并行汁算结构为# 础：共享存储器。结构( s m ) 、) e 享磁盘结构( s d ) 、无共享资源结构( s n ) l “，盘图1 l所示。1 9 8 6 年，s t o n e b r a k e r 提出，s n 结构足支持并行数抓库系统的蛾f 【： = 并行结构。这个观点已经得到了普遍的接受。s n 并行结构1 1 通过高速网络互相连接的多个独立的处理结点组成，每个处理结点在本地磁盘上存储数据库的一部分数掘。s n 结构具有高可扩展性，其处理机个数可以扩展到数千甚至上万个。高吞吐量和响应时间不仅可以通过事务问的并行性得到，还可以从复杂查询的事务内并行性获得。本文的研究工作基于s n 结构的并行数据库。高性能数据库是指处理速度快和容量特别大的数据库。而“处理速度”通常是指查询速度，因为“查询”是出现最频繁的操作，其反应速黑龙江大学硕士学位论文：对业务工作影响很大，也关系到数据库在用户心目r f 】的形象。所以提f 并行数据库的性能是众多研究人员的追求。并行数据库系统的性能，：键在于其中的并行数据库算法技术、_ j f ：行查询优化技术以及先进的数：存储技术和负载平衡技术的支持。c ) s l n m , ( 1d i s ki s i ) )图1 1 并行数据库系统结构图帮1 罩引言在s n 结构的并行数据库中，查询处理由多个处理结点其同完成，不论在查询处理的哪个阶段出现各处理结点的负载不均衡，都会导致等待最慢处理结点完成操作的状况，导致系统性能的下降。负载平衡技术就是平衡各处理结点的负载，使得各处理结点尽可能同时完成操作任务，以提高系统的性能。负载平衡的定义为了改善系统的性能，通过在处理结点之间重新分配负载，把当前重载处理结点的任务传送到轻载处理结点执行，这种计算能力共享的形式，通常被称为负载平衡。负载平衡要达到的目标是使各处理结点之问的负载基本均衡。只是利用系统的负载平均信息，而忽视系统当前的负载状况的方法被称为静态负载平衡。根掘系统当前的负载状况来调整任务划分的方法被称为动态负载平衡】。在s n 结构的并行数据库中，数据被划分到各个处理结点上。e j l 讨，在数据划分方法方面已丌展了大量的研究工作，提f ：i _ 了很多有效的并行数据分布方法，如r o u n d r o b i n 、h a s h 、r a n g e p a r t i t i o n 、c m d 等。但是数掘库整体的数据划分策略的研究还很少。数据划分策略是为数抵库的所有关系选择合适的划分方法使得数据均匀分枷到各处理结点，并且适应查询负载的特点，使得总体的查询负载执行代价最小。数据划分策略是并行数据库静态负载平衡的基本方法。山于查询负载和数据库本身都是在不断变化的，所以我们选择的数据划分策略不可能一直都是最优的。数掘重组和数据迁移可以调整关系的划分，使得数据库的划分策略一直适应查询负载，从而提高系统的性能。我们把数据重组和数据迁移统称为数据重组，数据重组是根掘数据库的历史统计的负载平均信息来调整关系的划分，也是并行数据库静念黑龙江大学硕士学位论文负载平衡的一个有效方法。虽然我们可以通过静态负载平衡的方法平衡各处理结点的负载，但足静态负载平衡都是根据系统的历史平均负载信息来平衡负载，某一次的查询还是会出现负载倾斜的问题，而导致查询的性能下降。动态的负载平衡策略应用在查询处理过程中，能很好地解决这个问题。1 1 i 数据划分策略在s n 结构的并行数据库中，数据被划分到各个处理结点上，并且各个结点之间的通讯代价是昂贵的。不理想的数据划分会导致数据倾斜，增加通讯丌销，使性能严重下降。为数据库中的各个关系选择晟佳的存储方式是很复杂的，因为每个关系的不同划分方式只针对某类查询有很好的执行效率。所以要根掘系统的查询类型和频率来选择关系的划分方式。为数据库的所有关系选择划分方法、划分属性和分钿结点集足数据划分策略的主要工作。很多查询彳；仪涉及一个关系，所以在为关系选择划分策略时，也必须考虑备个关系之问的内在联系。关系n 勺划分属性的选择刈于硷咖的执行代价有直接的影响，优化的划分属性选择方法可以减少处理结点之问的通m 外销。关系分币i 的结点集的选择关系到查询处埋的并行度和各处理结点的负载，在选择每个关系的分和结点集时也要考虑使得每个处理结点的数据量基本均衡。i 1 2 数据重组数据重组可以调整关系的划分，使之适应数据库查询负载的变化，得到更好的查询执行效率。重组周期和重组的代价都是数据重组需要研究的问题。优化的重组周期和重组代价分析能有效地提高系统的性能并防止数据重组颠簸。数据重组根据执行时数据库的状态还可以分为在线第1 章引言重组和非在线重组两类。非在线的数据重组比较容易实现，但是会影响数据库的正常运行，那么存线重组是解决这个问题的最佳方式。但是由于数据重组是耗时的操作，并且要锁定重组的关系，所以在线数据重组是比较有难度的。在线重组必须考虑重组期瑚用户提交的查询的处理方法，使得重组不影响用户正常使用数据库。根掘数据重组的目的不同。可将其分为数据迁移和数据重组两类。数据迁移主要解决关系在各处理结点上的负载不均衡的问题，根据系统统计的负载信息来计算各处理结点的负载并给出迁移策略，使得各结点的负载在迁移后基本均衡，提高系统性能。数据重组则是根据当前数据库中关系的状态和统计的历史查询负载信息计算新的优化的数据划分策略，然后通过重组来使整个数据库以新的数据划分策略存储。1 1 3 动态负载平衡在机群环境中，每个处理结点都以不同的速度运行，每个处理结点都有自己的执行任务。凼此就会广：q - + 个问题，在某一时刻，些处理结点的负载极重，而另外一些处理结点的负载极轻。针对负载情况动态地均衡负载，是获得高性能的一个有效途径。并行数据库的动态负载平衡主要是研究动念负载平衡的操作算法。连接算法是数据库中频繁和费时的算法，所以动态负载平衡的连接算法能有效地提高数据库的性能。根据系统当河的负载动态地分配和调度任务，可以平衡各处理结点之间的负载。负载的收集工作列+ 于负载平衡是非常重要的，只有准确的获取当前各处理结点的负载状况，才能有效的均衡负载。负载阀值、负载移动的粒度和负载平衡的频率都关系到负载平衡算法的效率，如果这几个参数值的取值不合理，会造成负载颠簸而影响负载平衡算法的性能。黑龙江大学硕士学位论文1 2 国内外的研究现状近l 年来，并行数据库技术一直是研究界和工业界的瞩目焦点。不仅出现了像g a m m a l 4 弓】、b u b b a l 6 1 、v 0 l c a n o 【7 1 、d b s 3 t8 】等并行数据库原型系统，更有商品化的并行数据库系统问世，如o r a c l e l 9 1 并行数据库服务器、i n f o r m i x 并行查询服务器、i b md b 2u d be e e l l l l 等。国内以哈尔滨工业大学李建中教授为首的研究队伍在并行数据库方面取得了很多研究成果【1 2 1 ，在国际上有一定影响。中国人民大学的p b a s e 原型系统、华中理工大学研制的p a r o 原型系统。总体上，国内的并行数据库系统实现技术水平与国外先进水平相比尚有一定差距。随蓿近年来研究的积累，并行数据库的基本技术已经成熟，并在实际应用中得到验证。近几年研究人员的工作更倾向于提高并行数据库的性能以适应当前的应用需求。关于数据划分的方法的研究结果已有很多，如r o u n d r o b i n 、h a s h 、r a n g e 、h y b i r d r a n g e 、c m d 等等。为数抓库的每个关系选择合适的划分方法的研究并不多。加拿大多伦多人学的d a n i e lcz i l i o 在1 9 9 4 年提出了根挪：给定的查洵负载为每个关系选择划分属性的方法l ”】；文献【1 6 】介绍了b u b b a 系统的数 拭_ j ：分和；文献【1 7 】介缁了为关系选择划分度和分和的结点集：文献t 1 8 】介绍了j i j f , p 分和策略及其性能比较；文献 1 9 1 介绍了自适应并行计算系统的数据分布。i b m 的j u nr a o 等人在2 0 0 2 年提出了根据给定查询负载自动的设计数据库的物理存储方法【2 0 】；文献【2 1 】提出了一个基于连接代价图的关系存储方式选择算法。目前已有的算法主要是在给定的查询负载上自动给出优化的数据划分的算法，不能动态的适应查询负载的变化。单结点数据库的动态数据重组算法在过去已有研究，文献第1 章5 l 言1 2 2 ，2 3 ，2 4 ，2 5 ，2 6 1 阐述了这些问题。文献 2 7 1 介绍了并行数据库系统数据重组的一些问题，提出了利用增量算法的并发数据重组策略，使数据重组期间只有小部分数据不町用；文献 2 8 】介绍了i b m 产品的一些在线数掘重组方法。文献【2 9 】分析了各种数据划分策略的重组代价：文献1 3 0 提出了根据系统状态和当前负载，以及重组的性能受益决定是否重组的策略。d a n i e lc z i l i o 的博士论文也有关于数据重组的研究【3 “，文献【3 2 】是国内的关于数据重组的研究。文献【3 3 】介绍了通过数据划分调节数据分布倾斜的方法。最近几年日本和新加坡有很多关于在线数据迁移的研究 3 4 , 3 5 , 3 6 , 3 7 ，利用两级索引的在线调整r a n g e 分稚区域的方法来解决负载倾斜问题。目前的数据重组方法对重组期间的查询处理没有提出很好的解决方法，考虑的划分方法也不全面，而且不能保证重组期间查询请求的快速响应。在线数据重组方面还有很多问题需要解决。数据划分策略和数据重组是解决并行数据库负载倾斜的静态负载平衡技术，一i - f l j 阐述并行数据库的动态负载平衡技术的研究现状。文献 3 8 ，3 9 ，4 0 ，4 1 1 介绍了s n 结构的并行数拼库的动态负载、r 衡的问题和基本的解决方法。文献 4 2 ，4 3 介绍了s m 结构的并行数据库的动态负载j f 衡问题和动念负载平衡的j o i n 算法。目丽已有柏并行数据库动态负载平衡的研究大部分都是考虑并行连接操作的负载平衡问题，文献【4 4 5 9 1 都足关于解决负载倾斜的并行连接算法的研究，列其它操作和整个事务( 或查询) 没有进一步研究。造成负载不平衡的数据倾斜分四类，对于这四类倾斜的全面具体的研究很少。多用户模式下的负载平衡还有待进一步研究。1 3 本文的贡献本文主要研究并行数据库的负载平衡技术，负载平衡的目标是提高黑龙江大学硕士学位论文i数抓库系统的性能。负载j e 衡分静态负载平衡和动态负载平衡，并行数据库的静念负载平衡的方法有数据划分策略和数据重组策略。本文的研究内容主要分三部分：数掘划分策略、数据重组和动念负载平衡。并行数据库的数据分佰的好坏直接影响查询的性能，因为不合理的数掘分前i 会造成负载倾斜、增加通讯开销和降低并行度+ 导致数掘库性能严重下降。目前已有的算法主要是在给定的查询负载上自动给出优化的数据划分方案。但是这些方法获得较好的查询性能的前提是能准确地预测出数据库将要接收的查询的类型和频度。而实际上在大部分应用中，这种预测是很难的。一方面预测的结果不够准确，另一方面数据库在不同时期的查询负载变化也很大。如采预测与实际查询的情况差距太大，或是应用发生很大的变化，那么最初优化的数据库物理设计也会导致极低的查询执行效率。既然在最初设计关系的划分方式时，很难预知这组关系之上的查询操作类型以及操作发生的频率及其变化，那么静态的数掘划分方式就很难适应不断变化的查询需求。通过统计系统的查询负载，动态地产生数据划分策略，调整数据划分以适应查询需求，将使数据库具柯更好的搀体森询执行效率。本文提出了基于查询负载的数据划分策略，根据系统的查询负载选择合适的划分属性、划分方法和分巾结点集，使得数据划分策略的选择一直适应数据库的查询负载变化，而保持数据库的良好性能。本文还针对一维划分策略和c m d 划分策略的缺点提出了新的划分方法r c m d 和r c m d 数据划分策略。r c m d 数据划分策略既节省磁盘i o ，又节省网络通讯代价，能有效地提高查询的性能。动态的调整数掘的划分策略会导致代价昂贵的数据重组，也会影响数据库的正常运行。目前已有的数据重组算法很少有支持在线重组的，并且很少考虑重组期间的查询处理问题，很难保证正常响应用户的查询请求。本文提出的数据迁移和数据重组算法以及在线重组期间的查询处第1 罩引言理方法，能够很好地支持n 戡重组而1 i 影响用户的查询l f 常执行。本文提出的在线和非在线的数据迁移算法能够有效地、f 衡各个处理结点的负载，将重载结点的负载迁移到轻载结点。利用本文提出的数据重组算法可以根据查询负载的变化动态地调整关系的数据划分方式，使数据库一直都能保持良好的性能。动态负载平衡是解决查询处理过程中负载倾斜的有效方法，本文提出的动态负载平衡的j o i n 和a g g r e g a t i o n 算法，能够根据各个处理结点当前的负载状况调度任务的执行，平衡各处理结点的负载，增加并行度，提高操作执行的效率。作者还提出了针对不同的数据分布而改进的j o i n算法，能够减少不必要的负载颠簸。i | 于本文提出的动态负载平衡算法是针对r c m d 划分策略的，所以在移动负载之前不用划分数据也不会有多余的网络通讯，所以比其它的动念负载平衡算法效率更高。本文提出的静奄负载平衡方法根据系统的平均负载信息调整数据划分使得各处理结点的负载均衡，数据重组还能够有效地调整数据划分减少网络通讯代价。本文提t 的动念负载平衡调度的操作算法能够有效地解决查询处理过程t 内负载倾斜问题。本文作者利用静态和动念负载i r衡技术解决并行数掘库t l 】f f j 负载倾斜问题，有效地提高了并行数据库的整体性能。1 4 论文结构本文主要分为五个部分。第一章引言。介绍了本文的研究背景、国内外的研究现状、本文的贡献，阐明了本文的研究意义和学术价值。第二章基于查询负载的数据划分策略。介绍了各种数据划分方法对数据库性能的影响，基于查询负载的数据划分代价模型。主要介绍了黑龙江大学硕士学位论文基于金询负载的数据划分策略，包括选择划分属性、划分方法和关系的划分度以及分布的结点集。墩后提出了基于r c m df 内数据划分策略并给出了实验结果及性能分析。第三章数据重组策略。介绍了数据迁移和数据重组的基本概念。阐述了在线和非在线的数据迁移算法及数据重组算法，以及支持在线重组的查询处理方法。并给出各个算法的实验结果及性能分析。第四章动态负载平衡。详细叙述了动态负载平衡的j o i n 算法以及改进的j o i n 算法。介绍了动念负载平衡的a g g r e g a t i o n 算法。最后给出实验结果及性能分析。最后给出了本文的结论，不足之处和未来的工作。第2 章基于查询负载的数据划分策略第2 章基于查询负载的数据划分策略在基于s n 结构的并行数据库系统的研究中，并行数据库物理存储方法是一个重要的研究内容。在查询处理过程中，如果数据分斫】不合理，系统的并行性就得不到充分的发挥，降低了并行数据库的性能2 l 。并行数据库的数据存储技术是指研究如何把j t ：t 亍数据库的数据有效地分置到系统中各处理结点上，从而能提高并行数据库系统的性能。数据存储技术的好坏极大地影响整个并行数据库的性能。如果物理数据不能有效地分置到各处理结点上，系统负载不j 卜衡，达不到高并发度的目的，将会导致系统资源的浪费，加大操作响应的延时，降低并行数据库系统的性能。f 因为如此，数据存储技术自数据库诞生以来，已经成为数掘阼研究的重要方向。日前，在并行数抛库数据分布策略方面l l j i ：展了大量的研究工作，捉 ：_ 了很多有效的7 t ：行数掘分布方法，如r o u n d r o b i n 、h a s h 、r a n g e p a r t i t i o n 、c m d 等数掘分硝】方法，这j l q 数据分币j 方法都有各自的优缺点。不同的分斫j 方式只e r ：i 刘某类查咖有很好的效率，在实际应j 1 j qr ，个并行数t ij 4 l ，的所有关系= = _ f ；i 叮能只简单地采i i t 0 1 5 4 i i 策略。为了提高j t - i 7 数据库的查询效率，在进行数据库应用设计过程- | 需要根据每个关系上的查询操作类型以及操作发生的频率来为每个关系确定相应的分布存储策略。本章提出了基于查询负载的优化的数据划分策略。为数据库中的所有关系选择划分属性、划分方法和分布的结点集，使并行数据库的并行性得到充分的发挥，提高整体性能。黑龙江大学硕士学位论文2 1 数据划分方法对数据库性能的影响并行数据库物理设训核心问题是：如何把一个关系划分为多个子集合并分布到多个处理结点上( 以下简称数据划分) ，使得在查询处理中系统的并行性得到充分发挥。数据划分是查询处理并行化的重要基础。很多研究表明，数据划分对于并行数据库系统的性能具有非常大的影响。数据划分是并行数据库系统的一个重要领域，已经出现了很多数据划分方法。这些方法分为三类：一维数据划分、多维数据划分和传统物理存储结构的并行化。2 1 1 一维数据划分一维数掘划分是简单的数据划分方法，已经被a r b r e 、b u b b a 、g a m m a 、 f e r a d a t a 等系统采用6 6 0 】。一维数据划分方法的特点楚根据关系的一个属性的值来划分整个关系。这个属性被称为划分属性。h 前已经提出了四利n 一维数据划分方法。以下设i ：行数据库系统具有n 个处理结正i0 、n 一1 ，r ( a 1 ，a k ) 是具有属性a l ，a k 的关系r 。r o u n d r o b i n 划分方法r o u n d r o b i n 办法，i ：小足维数搦划分方法。因为它和。维数抓拢0分方法样简单，所以我们也把它归并到这一类。设r 足关系r 的第i个元组。使用r o u n d r o b i n 划分方法，r 将被存储到第( im o dn ) 个处理结点上。对于大数掘量查询，r o u n d r o b i n 方法是很理想的。但是，它不能有效地支持具有低选择性谓词的查询。这是因为这种查询仅存取很少的元组，可r o u n d r o b i n 方法却要求启动所有的处理结点，增加了系统丌销。h a s h 划分方法第2 章基于查询负载的数据划分策略设a 是关系r 的划分属性，v 足a 的值域。使用h a s h 划分方法，需要定义一个以v 为定义域的函数h ：v _ + 0 ，n l 。设r 是r 的任意元组。h a s h 划分方法把r 存储到处理结点h “一d 上，其中，阻】表示元组r 在属性a 上的值，t l a s h 方法既能有效地支持大数据量存耿操作，也能有效地支持在划分属性上具有低选择性谓词的数据操作。然而，h a s h方法不能有效地支持具有小区域存取要求的查询操作，也容易引起数据在处理结点问分布不均匀。r a n g e 划分方法【1 1r a n g e 划分方法把划分属性a 的值域划分为n 个空间，。= k ，一l ，1 。= k 。，x 。) 。然后，将r 划分为n 个子集合s ，s 。，其中，s = p ir r ，d 爿】，) 。s i 存储在第i 个处理结点上。r a n g e 划分方法既可以有效地支持大数据量存取操作和在划分属性上具有低选择性谓词的数掘操作，也完全支持毖于划分属性的区域查询操作。但是，r a n g e划分方法可能引起数据在处理结点| 1 = i j 分以瑚q 升i 均匀，在最坏情况卜i ，关系中的所有数掘可能皆分布在吲一个处理结点。j ：。h y b r i d r a n g e 划分方法( 简称h r 方法) c 、f 需要消耗大量系统资源( c p u 时间、i 0 时i e i j 、通l i u l , j l h j ) 的查询来说，所涉及的关系划分越细，分布处理结点数越多，参与处理该查询的处理结点就越多，查询处理的效率也就越高。但是，对于消耗较少系统资源的查询来说，加细关系划分粒度可能会增加查询的响应时浏。这是因为多处理结点的启动、通讯和终止的额外丌销可能会大于并行处理所带来的时间节省量。总之，关系划分策略的选择对于系统的整体性能有重要的影响。上述三种划分方法没有考虑这些影响。h r 划分方法试图在考虑这些影响的条件下给出关系的优化划分策略。它首先确定子集i3 黑龙江大学硕士学位论文合的大小f c ；然后，按划分属性恤对r 进行排序：次之，把r 划分为i r i f c个子集合；最 j ，按r o u n d r o b i n 方式在处理结点间分稚各个子集合。h r 方法的关键是f c 的确定。f c 是在最小化关系r 上平均查询响应时问的条件f 被确定的。h r 方法试图使要求较少系统资源的查询由较少处理结点处理，而使要求较多系统资源的查询由较多处理结点处理，提高了系统的查询效率和处理能力。虽然h r 方法克服了其它一维数据划分方法的缺点，由于它根据数据操作资源需求量的均值确定f c ，当数据操作资源需求量的方差很大时，它将失效。h r 方法是基于选择操作建立的，它是否能有效地支持其它操作尚需研究。r e p l i c a t e 划分方法r e p l i c a t e 其实并不是一种数据划分方法，因为它只是把数据冗余地复制到多个结0 i 存储。i l l f 刈1 ：j j = 行数据库一i | 涉及多个关系的查询巾数据量小的关系采用r e p l i c a t e 方法分巾，叫以减少结点m 通讯丌销，有效地提高查渤的效率，所以这u i 我们也把r e p l i c a t e 视为一种数据划分力法。r e p l i c a t e 力法刈_ 丁具有低选择性嘲渊的查湖和小i 爱域查询支持得很好，丛l 为它只f f , jj f i 动一个结点完成套咖。但是只有小关系才适合采刖这种分析i 方式，如果火夫系采刚tr e p l i c a t e 分伽，j j | 5 么既浪费了整个系统的存储资源，也降低了查询性能。2 1 2 多维数据划分一维数据划分方法具有一个共同的问题：不能有效地支持在非划分属性上具有选择性谓词的查询。这样的查询必须被送到包含给定关系元组的所有处理结点进行处理。显然，把查询送到不包含所涉及元组的处理结点运行将浪费大量的c p u 时间、i 0 时间和通讯时间，降低系统的处理能力。为了解决这个问题，几个多维数据划分方法已经被提出。其中c m d 方法是对于所有的部分匹配查询都是最优的数据放置算法。c m d 多维数据划分方法我们简单介绍一r 下c m d 数据分斫i 方法( 详见文献 6 2 ，6 3 ) 。给定一个具有d 个属性的关系r ( 4 ，a 。) d 仍，其中p 是属性a 。的定义域，c m d 方法把r 视为d 维空间s = d ，d u 的子集合。c m d 方法把空间s 的各维划分为多个不相交区问，把空问s 划分为多个子空间，使得r 在每个子空i j j 中具有近似相同的元组数。于是，关系r 被划分成大小近似相等的子集合。然后，c m d 方法使用坐标和求模函数把s 的每个子空间分配到一个处理机。为了叙述简单，令s = 【o ，1 ) 。设p 是处理机个数，p 个处理机的内存容量( 元组数) 分别为m ，m ：，m 。为了划分空问s ，c m d 方法把空间s 的第i 维的值域划分成长度为二= 的一p 个予区f , j ：r l1 峙怙， 等，其一i - n 是调整因予n ，必须充分大，使得卜列两个条件成立：( 1 ) 划分i 舌的每个超办体所也含的r 的冗组l 州城入。个磁黜负；圆r 的任蛳的任一区问 古，等卜足：ll ter , t 骺，钏缸其中i x i 是关系x 的元组数，阻】是元组f 的爿属性，a 是月的第i 维对应的属性。条件( 2 ) 保证了关系r 与每维的每个划分i x f 1 对应的子集合( 即一属黑龙江大学硕士掌位论文性值聪于该划分区州的元组集合) 可以存储在p 个处理机的内存中，有效地支持并行数据操作算法的设计与实现。设，= l 。寿，专j 是第f 维上v , j 第j 个子区问，是这个子区间的坐标。c m d 方法把s 划分为( il p x n a p ) 个超长方体，每个超长方体都是d 个子区间的笛卡尔积“，虬，b i ，一，h ) 定义为浚超跃方体的坐标。超长方体g - ，x d ) 被分配到处理机c 彻0 一，x 。，) ，其中c m d函数为：c m d ( x l ，h ) = x l + + h ) m o dp 。图2 1 给出了一个s = 【o ，1 ) 2 在4 个处理机问分布的实例，其中n = 珂：= 2 ，p = 4 ，最左列和最底行们标记是各维上的子区间的坐标，方框内的数字表示相应的超方体被分配到的处理机弓。例如，超方体( 6 , 6 ) 被分配到处理机0 。3ol23o12230123ol1230l23o012301233o123ol223o12301l230l23o01230l23ol234567图2 1s = 【0 ，1 ) 2 在4 个处理机间划分的实例7654321o第2 章基于查询负载的数据划分策略定义2 1 关系r 的c m d 存储结构是一个二元组r = ( p k ，p k 忸1 ) ，r 。 ) ，其中p 蚱是关系r 的第i 个属性定义域的划分向量，按划分点递增顺序排列，r ，是r 留驻在第，个处理机的数据子集合用c m d 方法存储的关系称为c m d 关系。c m d 关系具有很多好性质，除整个关系均匀地分布在多个处理机上以外，下面几个性质对于并行数据操作算法的设计十分重要：( 1 ) 在任一维k 上都部分有序：设和是第k 维( 对应属性为a )上的两个划分区间，如果i j ，则对于任意“e f i ，尺，f 【一】l k i ，v t i f 月，【4 】，。i 近一】( v 【彳】；( 2 ) 对于任意维t 上的任意一个划分区削，pl ，足d 彳】j 的数据量不超过全部处理机的内存空问总容量，并且均匀地分布在p个处理机上；( 3 ) 如果， ，和， ，是笫i 维( 列应属性为a ) 上两个不同的划分区f 日j ，则0 i f r ，- 】，。 和i i ，尺，f 爿】l a ：j 具有近似相等数量的元组。s 在各处理结点上的子空问是极不规则的，使得r 在各结点上的子集合难以使用各种现存的物理存储结构组织。为了解决这个问题，c m d方法通过坐标变换，把每个处理结点上的子空问压缩成为一个超方体，使得r 在浚子空间上的子集合在变换后的子空问上近似均匀分稚。c m d方法使用g r i d 文件结构在各处理结点上组织r 的子集合。理论和实验结果都表明，c m d 方法在多数情况下都是优化的，即能够充分发挥系统的并行性。由于数据划分对称地在所有属性上进行，c m d 方法可以有效地支持具有各种选择谓词的查询。经过c m d 方法划分的关系是部分排序的。该性质使基于c m d 的s o r t 和j o i n 等数据操作的实现算法远比黑龙江大学硕士学位论文现有的算法有效1 6 4 , 6 5 l 。c m d 方法把由数据维护操作引起的超方体的分裂与合并局部于单个处理结点，减少了处理结点问的数据传输，提高了数据维护操作的效率。对于所有可预知其数据分布的关系，c m d 方法都是均衡的，即每个处理结点上的数据子集合的大小都近似相等，避免了为保持数掘均衡而进行的耗时的数据再划分操作。2 1 3 数据划分方式对数据库性能的影晌数掘划分方式的选择对数据库的性能有显著的影响，某种划分方式可能只针对某j l 类查询有利，而对其它的查询就不是很理想。f 面i 羊细分析各种划分方式对查询性能的影响。表2 1 划分方法对比大数据量区域划分属性上低数据划分方式查哟查谢选择性谓词查询倾斜r o u n d r o b i n盘f筹筹4 i 会r a n g e姆1 1 1婚a“h a s h好差好可能r e p l i c a t e好好c m d好好好不会r o u n d r o b i n 、r a n g e 和h a s h 方法都能有效地支持大数据量的查询。h a s h 和r a n g e 对于划分属性上的低选择性谓词查询也能有效支持。r a n g e第2 覃基于查询负载的数据划分策略方法能有效地支持划分属性上的区域查询，但是r a n g e 方法可能引起严重的数据倾斜，而h a s h 方法也容易造成数掘倾斜。r e p l i c a t e 方法对于关系要求比较严格，在很多系统中要求更新不频繁的小关系才能采用这种方式。r e p l i c a t e 方法可以只启动华个结点来l 响应该关系上的查询。多维划分方法c m d 具有以上所有优点。表2 1 总结了各个划分方式的特性。下面我们通过数据库中比较费时而且频繁出现的连接操作，比较各个划分方法。例如蝗鼍s ，表示关系r 和s 做等值连接，连接属性分nu 一【，别为r a 和s b 。如果关系r 和s 都采用r a n g e 分布，且划分属性是连接属性，划分区间和分布结点集完全一致，那么r 和s 的等值连接可以直接在数据分布的结点集的各个结点本地执行，没有通讯代价，这种连接叫做本地连接【1 】。如果r 和s 都采用h a s h 分前i ，且划分属性是连接属性，h a s h 函数相同，分价的结点集完全一致，则同样是本地连接，没有通讯代价。但是如粜r 和s 不采用上面两种情况，而采用其它的一维划分( 不包括r e p l i c a t e ) ，则r 和s 的等值连接，就会有至少个关系需要重新分撕j 数据，带来很大的通讯玎销。但是如果r 和s 小较小的个采_ 1 1 _ | r e p l i c a t e 而另一个采用r o u n d - r o b i n 、r a n g e 或者h a s h 中的一种方，则同样足小地连接，没= f _ 迎讯j 闱j 。嘶讨论的足采川吲i 划分方式的情况。如果关系r 和s 都采用c m d 划分则r 和s 的等值连接一定会有通讯丌销，但是如果有选择性谓词的话，磁盘i o 代价要小很多，所以性能介于以上两种情况之问。我们可以看出各个划分方式都有其优点和劣势，没有一个划分方法能使各类查询都获得较高的执行效率。所以并行数据库的存储设计不能只简单地采用一种划分方法，只有根据查询的负载选择合适的划分方法、划分属性和分布结点集才能使并行数据库总体的查询效率提高。黑龙江大学硕士学位论文2 2 基于查询负载的数据划分代价模型基于s n 结构的并行数据库执行查询时，经常需要重分抑数据，这会带柬结点机之i b j 的通讯开销。这种通讯开销极大地影响了查询的执行效率。并行数据库的关系存储方式设计目标就是尽量减少这种通讯丌销1 2 1 1 。因此对于基于s n 结构的并行数据库，咀通讯开销来定义查询的执行代价是一种直观而又准确的方法。连接和聚集操作是西类常用而且费时的查询操作，关系的分布属性的选择对于这两种操作执行效率的影响最大。例如当连接算法采用h a s h j o i n 算法时，如果连接的两个关系都在连接属性上h a s h 分布，那么连接操作在各个节点上本地执行，没有额外的通讯开销，这是最理想的情况；如果有一个关系不是在连接属性上划分的，那么算法就需要在各个节点机上重新分前j 数据，查询执行的性能就会下降。查询中其它操作的执行一般不会带来额外的通汛丌销，因此，本文只对连接和聚集操作的执行代价进行分析和定义。定义2 2 ：设数据库模式d 为组关系模式的集合，表示为d 尺，ir i 为关系模式 。征数据库d上有操f 1 二集台q q i q 砸接，聚集”，则q 在d u 内a 询代价为：c o s l ( ( 2 ，d ) = c o s l ( o , ，d )( e a这燃c o s t ( o j , 纠表示每个操作的代价，同文献【2 1 】一样，该代价 = | j 为执行该操作需要的通讯开销。在基于s n 结构的并