（计算机应用技术专业论文）并行数据处理中间件存储分配策略研究.pdf

哈尔滨1 ：程大学硕十学位论文 摘要 并行数据处理是一种十分重要的计算机技术，该技术目前在很多领域发 挥着重要作用。通过开发一个支持并行数据处理的中间件，将集群并行计算 机各节点上分布的数据库连接起来，构成数据并行处理中间件系统，系统中 各节点并行工作，可以以较小的代价获得接近并行数据库的性能。在s n 结 构的并行数据库中，数据被划分到多个处理节点上，查询由多个节点共同完 成。在此应用环境中，划分方法的优劣对提高系统并行性，减少数据倾斜， 提高系统性能具有重要作用。 数据存储分配是查询处理并行化的基础，是并行数据处理技术研究的重 要方向之一。本文通过对存储分配策略的研究，研究并提出最大程度适合本 系统的数据存储分配策略，以提高系统性能。 本文首先描述了数据并行处理中间件的系统结构和工作原理，以此为应 用和研究环境，研究如何对关系进行分片，提出一种基于连结代价的划分属 性选择算法，对r a n g e 和h a s h 划分方法进行改进，提出适合本系统的r h 划分算法，该算法比原有的r a n g e 和h a s h 方法更有利于实现数据均衡，避 免秒j 始数据倾斜的产生。针对系统长期运行后可能发生的数据倾斜，本义研 究了中间件系统中数据重分布策略。研究在发生数据倾斜时，如何确定过载 节点、过热关系以及热点数据块，并给出了热点数据块迁移的方法。经过实 验测试，重分布方法可有效解决数据倾斜的问题。 根据对实际应用环境中数据表特征的研究和分析，本文还对中i 、日j 件系统 中小表的放置、建立索引以及连结操作的问题进行了研究，提出了本系统中 的解决办法，使得本文的研究具有较强的可应用性。 关键词：并行数据处理；中问件；数据划分；存储分配 哈尔滨一i j 程人学硕十学何论文 a b s t r a c t p a r a l l e ld a t ap r o c e s s i n gi sav e r yi m p o r t a n tc o m p u t e rt e c h n o l o g ya n dp l a y sa s i g n i f i c a n tr o l ei nm a n yf i e l d s am i d d l e w a r es u p p o r t i n gp a r a l l e ld a t ap r o c e s s i n g i sd e v e l o p e dt oc o n n e c td a t a b a s e sw h i c hl o c a t eo nt h en o d e so f p a r a l le lc o m p u t e r s y s t e mb a s e do nc l u s t e r s t h en o d e so ft h es y s t e mw o r kp a r a l l e la n dc o u l d a c h i e v ep e r f o r m a n c ec l o s et op d b m s i np d b m sb a s e do ns ns t r u c t u r e ，q u e r y i s c o m p l e t e db ym o r et h a no n en o d e i nt h i sa p p l i c a t i o nc i r c u m s t a n c e ，d a t a d e c l u s t e r i n gi ss i g n i f i c a n t t o i m p r o v es y s t e mp a r a l l e l i s m ，r e d u c ed a t as k e w ， e n h a n c es y s t e mp e r f o r m a n c e d a t as t o r a g ea l l o c a t i o ni st h ef o u n d a t i o no f p a r a l l e l i s mt h a tq u e r yp r o c e s s i n g c o u l dh a v ea sw e l la st h e i m p o r t a n td i r e c t i o no fr e s e a r c ho fp a r a l l e l d a t a p r o c e s s i n g b ys t u d y i n gt h es t r a t e g i e so fd a t as t o r a g ea l l o c a t i o n ，t h es t r a t e g y w h i c ha d a p tt om i d d l e w a r es y s t e mm o s t l yw a sp r o p o s e dt oe n h a n c et h es y s t e m p e r f o r m a n c e t h es t r u c t u r ea n dw o r kp r i n c i p l eo fp a r a l l e ld a t ap r o c e s s i n gm i d d l e w a r ea r e i n t r o d u c e df i r s t l y ，u n d e rt h i s a p p l i c a t i o na n dr e s e a r c hc i r c u m s t a n c e ，h o wt o p a r t i t i o nar e l a t i o ni sw o r k e do v e ra n daa l g o r i t h mi sp r e s e n tt os e l e c tp a r t i t i o n k e yb a s e do nj o i nc o s t t h er a n g ea n dh a s ha l g o r i t h m sa r er e f o r m e da n dt h er h a l g o r i t h mi sp u tf o r w a r dw h i c ha d a p tt oo u rs y s t e mm o r et h a no t h e r s ，f u r t h e r m o r e ， t h er ha l g o r i t h mi si nf a v o ro fa c h i e v i n gl o a db a l a n c i n ga sw e l la sa v o i d i n gt o p r o d u c ee a r l yd a t as k e w c o n c e r n i n gt h ed a t as k e wa f t e rs y s t e mr u nal o n gt i m e ， t h ed a t ar e d i s t r i b u t i o ns t r a t e g yw a sp r e s e n ti nm i d d l e w a r es y s t e m t h et h e s i s s t u d yh o wt of i n do v e r l o a d i n gn o d e s ，r e l a t i o n sa n dd a t ab l o c k sw h e nd a t as k e w o c c u r s ，t h ea l g o r i t h mt ot r a n s p l a n tt h eh o td a t ab l o c k sw a sp r e s e n t t h et e s t c o n f i r m st h a tr e d i s t r i b u t i o n a l g o r i t h m c o u l dr e s o l v ed a t as k e w p r o b l e m e f f i c i e n t l y t h et h e s i sa l s oi n t r o d u c e sm e t h o d st or e s o l v et h ep r o b l e m so f p l a c e m e n to f 哈尔滨 r ：程大学硕十学何论文 s m a l lt a b l e ，c r e a t i o no fi n d e xa n dj o i no p e r a t o r t h a ta l lm a k et h er e s e a r c ho ft h i s t h e s i sh a v eh i g h a v a i l a b i l i t y k e y w ords ：p a r a l l e ld a t ap r o c e s s i n g ：m i d d l e w a r e ：d a t ad e c l u s t e r i n g ：s t o r a g e a l l o c a t i o n 哈尔滨工程大学 学位论文原创性l 声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ： 日期：7 沪舻年弓月争日 哈尔滨t 程大学硕十学何论文 第1 章绪论 1 1 课题研究背景及意义 数据库技术是一项十分重要的计算机技术，由于数据库具有数据结构化、 最低冗余度、较高的程序与数据独立性、易于扩展、易于编制应用程序等优 点，在很多应用领域发挥着关键作用。建立以数据库为核心的信息系统和应 用系统，对于提高企业的效益、改进部门的管理、改善人们的生活具有实实 在在的意义。j 下因为数据库技术与经济、社会的发展和信息化建设有着密切 关系，这门学科才获得巨大的源动力和深厚的应用基础。现在，数据库管理 系统已从专用的应用程序包发展成为通用的系统软件。 2 0 世纪8 0 年代以来，计算机应用领域迅速扩大，随着历史数据的不断 积累和i n t e m e t 技术的同益普及，生产和生活中出现了大量海量信息数据， 有的海量数据系统容黾已达t b 级甚至p b 级。同时，用户查洵越来越复杂， 对数据库管理系统性能( 处理能力和速度) 的要求越米越高，传统的数据库 系统已经很难满足人们对于查询复杂性和实时性的要求。并行数据库系统 ( p d b m s ) 通过充分利用多处理机和多磁盘的并行性提供海量的数据存储空 问和商效的查询处理能力，作为提高系统性能的强有力工具越来越受到人们 的重视。在并行数据库系统中，高吞吐量和向应时间不仅可以通过事务间的 并行性得到，还可以从复杂事务处理的事务内并行性荻得。 并行数据库系统研究一直以三种并行结构为基础：共享内存结构 ( s h a r e d m e m o r y ，简称为s m ) 、共享磁盘结构( s h a r e d d i s k ，简称为s d ) 、 无共享资源结构( s h a r e d n o t h i n g ，简称为s n ) n 1 。1 9 8 6 年，s t o n e b r a k e2 提 出，s n 结构是支持并行数据库系统最好的并行结构，这个观点已经得到普 遍的接受。s n 并行结构通过高速网络把多个独立处理节点连接起来，每个 处理节点在本地磁擞上存储数据库的部分数据。 并行数据库价格昂贵，而且操作和维护都很复杂，需要专业人员来管理， 因此研究低成本并且具有并行数据库高性能的系统就成为迫切需要。针对计 哈尔滨t 程大学硕十学何论文 算机集群上独立的数据库系统( 每个计算机上运行相同的操作系统利同样的 数据库系统软件) ，开发一个支持数掘并行处理的中间件，把计算机集群 ( c l u s t e ro fc o m p u t e r s ) 系统中各个节点上运行的独立数据库管理起来，伎它 1 f j 并行工作，从而以较低的成本( 单机版数据库的成本) 获得较高的性能( 接 近并行数据库系统的性能) ，这样不但可以节省资金，而且操作和维护都相 对简单，针对性强。在中间件系统中，用户通过中间件访问底层的多个单机 数据库，操作对用户是透明的，使用户感觉自己在使用一个真正的并行数据 库4 。 并行数据库的数据存储技术是指研究如何把并行数据库的数据有效地放 置剑系统中各处理节点上，从而提高并行数据库系统的性能。在数据并行处 理中问件系统中，关系( r e l a t i o n s ) 被划分成子集合分布到多个处理节点上， 查询操作时，可以充分发挥系统的并行性，提高查询效率。数据划分是查询 处理并行化的重要基础，很多研究表明，数据划分对于并行数据库系统的性 能具有非常大的影响。如果数据分布不合理，在查询处理过程中系统的并行 性就得不到充分的发挥，达不到高并发度的目的，将会导致系统资源的浪费， 加大查询操作的响应时间，降低并行数据库的性能。正因为如此，数据存储 技术自数据库诞生以来，己经成为并行数据库研究的重要方向1 。 在中问件系统中，数据的划分策略按照初始的查询负载或者预测的杏洵 负载米设计，随着数据库长期运行，查询负载和关系的某些特性可能会发生 一些变化。例如数据库中加入了新的关系，原有的关系加入了新的属性列， 某个关系进行了大量的增、删、改操作，或者某两个很少做连接操作的关系 最近频繁的做连接操作，这时，初始的数据库划分策略不再适应当前的数据 库关系和金询负载特点，造成用户查询的响应时间增加，系统的性能逐渐下 降。如果不及时调整划分策略，初始优化的数据存储策略就会成为阻碍数据 库整体性能的主要因素。 为了改善数据库的性能，需要对数制库中某些关系的数据进行调整，把 过载节点上对系统性能影响较大的数据分散到多个节点上，也就是数据的重 分布( r e 。d i s t r i b u t i o n ) 。通过数据重分布，数据库关系可以较好的适应查询 负载变化，得到更好的查询执行效率。数据重分布不改变关系的划分属性和 划分方法，只是把一部分数据从负载较重的节点迁移到负载较轻的节点，使 2 哈尔滨+ 1 i 程大学硕+ 学何论文 各节点负载史均衡。 本课题针对目前面临的具体情况，继续进行这方面的研究，争取在并行 数据库中间件系统上取得更大的发展，使之得到更广泛的应用。 1 2 国内外研究现状 1 2 1 并行数据处理技术 数据库技术经历了几十年的发展演变，已经取得了巨大的成就，发展成 了一门内容丰富的学科，形成了总量达数百亿美元的一个软件产业。目前， 市场上具有代表性的数据库产品包括o r a c l e 公司的o r a c l e ，i b m 公司的d b 2 以及s y b a s e 公司的s y b a s e 数据库等等。从一定程度上看，这些产品反映了 当前数据库技术的最高水平和发展趋势。 幽外的并行数据库技术发展的比较早，也比较成熟。典型研究成果有： i b m 公司的d b 2 、o r a c l e 、t e r a d a t e 、t a n d e m 、g u m m a 、b u b b a 等“，其特 点是完全按照并行数据库的经典理论丌发而成，功能全面，技术含量高，但 价格昂贵，对系统和机器的要求高。 目前，国内的一些高校、科研院所等研究机构也在积极地进行并行数据 库以及支持数据库并行操作的中间件的研究丌发工作，并已经陆续推出了相 应的产品和解决方案，比如中国人民大学研制的p b a s e 原型系统“，华中理 工大学研制的p a r o 原型系统，但从应用角度来看，其采用的技术路线， 性能和健壮性方面还达不到并行数据库系统的全部要求，与国外先进水平相 比尚有一定差距，还不是真l f 产晶化的通用并行数据库系统，在j i ：程应用方 面尚未形成规模。 随着计算机网络技术的发展，产生了一种新的并行计算系统，即基于网 络的计算机集群并行计算系统。它的特点是通过高速通信网络将多个独立的 计算机系统连接起来以支持并行计算。集群并行计算系统中的每个计算机被 称为节点，这些节点可以是高档微机、小型机、大型机或巨型机。如果系统 中所有的节点都是工作站的话，则被称为工作站集群，这也是目前主要的集 群并行计算系统，有许多针对并行数据库的研究都是基于这样的硬件环境完 成的。 哈尔滨i ：程人学硕十学化论文 mi i i 与大规模并行处理机( m p p ) 相比，集群并行计算系统具有易于实现、灵 活性高的特点，能够方便的将不同体系结构的各种计算机连接起来，有机地 形成异构并行计算环境，但也只有使用高档计算机的集群系统d 能在性能l 二 接近m p p 。m p p 是真正的大规模系统，可以是由数千个处理机组成的并行 系统，这对集群系统来说是不现实的。 实现集群系统最简单的方法就是通过高速网络或局域网将多个计算机连 接起来，节点可以是同构的，也可以是异构的。集群中的计算机数目一般为 几台至几十台，支持控制并行或数据并行的计算。每个节点上都有完整的操 作系统、蚓络和用户界面，都可作为控制节点或处理节点，即节点之间是平 等的。集群系统最近几年的表现引人注月，由于具有出色的性价比、灵活性 和良好的并行处理能力，除了广泛作为研究课题外，在各个行业的应用发展 也很快。目前来说，国内的国防科大、中科院计算所、黑龙江大学、曙光、 联想都在并行集群及并行数据库方面做出了一些成就”“3 。 哈工火首创公司推出的支持数据并行处理的中间件系统，通过中问件把 计算机集群各个节点上独立运行的数据库管理起来，以全局模式向用户提供 透明的信息杏询服务，采用并行处理技术对用户进行查询，减少了系统通讯 开销，使总体的查询负载代价最小，进而提高中问件系统响应能力。这种中 问件系统产品虽然在性能和健壮性方面还达不到并行数据库系统的全部要 求，但是能够以较小的代价实现对数据库的并行操作，结构灵活，部署简单， 目前在黑龙江省地税信息系统和贵州省地税信息系统中已被采用，相比而言 有着更为广阔的发展空间和更强的市场竞争能力。 1 2 。2 数据划分方法 在并jj 二数据库系统中，把一个关系划分成片断并分配到各处理节点上被 称为数据划分。数据分配的结果对于s n 并行结构系统整体性能有重要影响。 数据划分是查i 自j 并行处理的基础，目前已经提出了多种数据划分算法， 这些划分方法主要分为四类：维数据划分方法、多维数据划分方法、文件 并行化方法、索引并行化方法。一维数据划分方法包括r o u n d r o b i n 方法、 h a s h 方法和r a n g e 方法蚓，h y b r i d r a n g e 综合了上述方法并进行了改进+ 。 4 哈尔滨i ：科人。硕十学何论文 g a m m a 数据采用了r o u n d r o b i n 、r a n g e 、h a s h 几种数据划分方法”j ，在对 关系进行划分时，用常规方法为每个关系片段建立主、次索引，一维数据划 分方法只根据单个属性进行划分，而多维划分方法则对多个属性值进行处理。 文献 1 9 】提出了c m d 多维数据划分方法，b u b b a 查询并行处理原型系统中提 出的b e r d 方法伽，利用主从属性对数据进行划分，文献【2 1 1 对多种多维数据 划分方法进行了分析，把h y b r i d 。r a n g e 方法在多维上进行扩展，得到了 m a g i c 划分方法。 m a n i s hm e h t a 和d a v i dj d e w i t t 研究了如何为关系选择划分度和节点集 ”，j u nr a o 、c h u nz h o n g 和g u yl o h m a n 设计了一种数据自动划分工具”。 c o p e l a n d 等人把关系的片断按照热度或者访问频率在节点上分配，这利，方法 把一个关系最热的数据片断分配到当前最空闲的节点上，一直重复这个过程， 直到所有的关系被处理完n “。 关系索引是查询处理中重要的查询手段，因此人们提出了许多基于b 树 的并行化方法。b 树并行化方法土要有三种：记录划分法、大页b 树方法和 页划分方法“。 文献 2 6 2 7 提出了g r i d 文件并行化的方法，这种方法需要解决的关键 问题是g r i d 文件在多处理机间的初始分布和由数据插入与删除所引起的数 据负载不平衡的处理，人们还对其他数据分布方法进行了研究。”圳。 至今，尚未产生一种通用的、有效的支持并行查询处理的数据划分方法， 关于数据划分方法的相关研究仍在继续深入地进行。 1 ，2 3 数据倾斜和重分布 并伯：数据库系统经过长时问运行之后，各节点的奋询负载和关系的某些 特性可能会发生一些变化，特别是经过大量的插人和删除操作，数据的分布 将不再均衡，各处理机的负载会严重失衡，即发生了数据倾斜，目前，关于 数据倾斜的研究己经取得了许多成果。文献1 3 2 3 3 】对数据倾斜的特点以及抗 倾斜技术进行了较为详细的描述。文献【3 4 】j 每传统的并行数据库系统出现的 数据倾斜划分为两大类：固有的数据倾斜( i n t r i n s i cs k e w ) 、划分倾斜( p a r t i t i o n 哈尔滨。1 ：科人。字：硕十。7 ：何论文 s k e w ) ，前一种倾斜是数据空i 白j 的固有特性，无法避免，后一种倾斜可以通 过数据重分布获得较好的解决。 为了改善数据库的性能，对数据库中某些关系的数据进行重新组织，把 过载节点上对系统性能影响较大的数据分散到多个节点上，也就是数据的重 分布，数据重分布又称为数据重组。 数据重分布可以调整关系的划分，使之适应数据库查询负载的变化，得 到更好的查询执行效率。关于数据重分布的算法过去已有很多研究， c h a i t a n y ab a r u 和d a n i e lc z i l i o 介绍了并行数据库系统数据重分布的一些问 题3 ”，提出了利用增量算法的并发数据重分布策略，使数据重分布期问只有 小部分数据不可用。d a n i e lc z i l i o 的博士论文也有关于数据重分布的研究”“， 文献【3 6 】介绍了通过数据划分调节数据分布倾斜的方法，文献 3 7 】关于r a n g e 划分方法提出了在线数据调整方法，文献 3 8 3 9 也有关于在线数据迁移的研 究，利用两级索引的在线调整r a n g e 分布区域的方法来解决负载倾斜问题。 1 3 本文研究主要内容 本课题来源于哈工大首创公司研发的数据并行处理中间件系统。该中间 件系统是首创公司以海量数据库在决策支持领域内的应用为主要应用背景， 运用成熟的并行数据库理论，研发出的数据并行处理中间件产品。在中间件 系统中，数据的存储分配具有重要意义，数据的存储分配不仅影响着系统对 查询操作的响应性能，同时也与系统扩充时数据的重新划分和数掘的动态维 护有着密切的联系。 本文研究的中间件静态数据存储分配策略包括以下几个方面： ( 1 ) 确定关系中的数据分片大小。分片大小决定数据表文件将被划分为 几段，这些片断在分布阶段将被分配到并行系统中不同的节点上。 ( 2 ) 确定关系划分的属性以及关系集合。本文提出一种基于连接代价的 划分属性选择方法。选择哪个属性作为划分属性决定着并行数据库系统执行 查询的效率和成本。除建立数据表时的初始数据划分外，在为查询优化而进 ，重划分、发生数据倾斜而进行数据蕈组时，都需要确定关系的划分属性。 ( 3 ) 对关系划分方法进行比较，并设计种适合本系统的划分方法。不 6 哈尔滨t 稃火导硕十导：何论文 同的划分方法只针对某一类查询有很好的效率，在实际应用中，数据库中的 所有关系不可能只采用一种划分方法进行分配。为了提高数据库的查询效率， 在对中间件系统进行实际开发时，应该根据实际需要为每个关系采用合适的 数据划分方法。 ( 4 ) 为数据库中的关系建立b 树索引。索引的合理与否对大型数据库的 性能起着至关重要的作用，因为数据库中最多的操作是对关系的检索，对记 录的定位，课题中实现了索引的并行放置。 ( 5 ) 实现数据重分布算法。一旦发生数据倾斜，就会造成系统性能下降。 通过对数据倾斜及重分布的研究，统计系统的负载，在发生数据倾斜时，确 定过载节点和需要重分布的数据，对数据倾斜进行精确描述，并在发生数据 倾斜、负载失去平衡和整个系统性能下降时对数据重新分布以恢复系统的高 性能。 1 4 论文的组织 本论文共分5 章。第l 章为绪论，介绍了课题的主要内容、目的、意义 以及国内外发展情况，并对数据存储分配的概念、包含方面、重要意义、研 究目标等进行了阐述：第2 章对并行数据库中| 1 ；l j 件系统从整体上进行了介绍， 阐述了数据存储分配在系统开发中的作用；第3 章对数据存储分配进行了深 入研究和分析，并在此基础上实现了一种改进的数掘划分方法：第4 章对系 统的负载进行分析，对数据倾斜给出定义，并实现了负载倾斜时的数据重分 布算法：第5 章对前几章的内容在系统中进行实现，并对相关实验数据进行 分析。最后总结了本文所做工作，并对下一步的工作进行了展望。 哈尔滨i i 程人学硕十学何论文 第2 章中间件体系结构和系统模型 本章首先介绍中间件的定义及分类，然后说明中间件系统所采用的硬件 结构，最后对整个中间件系统的结构和工作原理进行阐述。在此基础上，分 析存储分配在中间件系统中的作用和研究方法。 2 1 中间件的定义 随着计算机技术的飞速发展，各种各样的应用软件需要在各种平台之间 进行集成，实现互操作，一个平台需要支持多种应用软件和管理多种应用系 统。因此，软、硬件平台和应用系统之间需要可靠和高效的数据传递或转换， 使系统的协同能力得以保证。研究表明，应用及数据系统的异构性和分布性 是系统集成和交互的主要障碍“。 为解决分布异构| u j 题，人们提出了中间件( m i d d l e w a r e ) 的概念“。中 问件这一技术名词在国外出现在2 0 世纪9 0 年代初，一般是指种位于系统 软件( 操作系统和网络软件) 与应用软件之间的软件，利用这层处于中间的 软件，可以使远距离相隔的应用软件协同工作，即实现互操作。 中间件相当于一个过滤层，所有的数据输入输出都要通过这个过滤层， 因此，中间件是否可靠关系到所有数据是否安全，而把住中间件这一关，也 可能将来自后门的攻击拒之门外。在国外中f n j f 牛- i 一商在这一领域目前还未形 成焦断局面之前，开发自主知识产权的中问件产品，将为信息应用提供安全 保障。 中间件包括的范围十分广泛，针对不同的应用需求目前已经产生了多种 各具特色的中间件产品。许多组织和专家都对中问件下过定义，但至今中间 件还没有一个比较精确的定义，所以经常会有“什么是中间件”这样的问题， 这也正说明中问件j 下处于迅速发展之中。以下根据文献 4 2 4 4 对中间件定义 进行归纳。 中问件是在分布式计算环境中，实现应用互连、互操作、资源共享的一 类独立的系统软件或服务程序，是建立在操作系统、网络操作系统和数据库 r 哈尔滨+ r j 鼙大学硕十学f 节论文 系统以及应用软件之i 到的可复用结构或构建群，它町以屏蔽异构和分布所导 致的各种复杂技术细节。随着技术与需求的不断发展，中间件还将整合企业 集团乃至社会计算机应用软件的资源。从该意义上讲，可以用一个等式来表 示中间件：中间件= 平台+ 通信，这表明中问件系统一般用于分布并行式系 统中，同时也把它与支撑软件和实用软件区分开来。 一般来说，中间件具有以下的一些特点： ( 1 ) 满足特定领域各种应用的需要。 ( 2 ) 平台无关性，可运行于多种硬件和操作系统平台。 ( 3 ) 支持分布式计算，提供跨网络、硬件和操作系统平台的透明性的应 用或服务的交互功能。 ( 4 ) 支持标准的协议、标准的接口。 程序员通过调用中间件提供的大量a p i ，实现异构环境的通讯，从而屏 蔽异构系统中复杂的操作系统和网络协议的差异。 中间件大致可以分为消息中间件、事务处理中间件、应用服务器、企业 级应用集成、安全中间件等。本项目研究的中i 、日j 件系统以实现数据并行处理 为主要目标，将无共享并行结构的集群计算机系统各个节点上独立的数据库 系统管理起来，构成数据并行处理中间件系统，以很少的投入获得了较高的 性能，是比较典型的事务处理中间件系统。事务处理中间件是同前主要的中 i 日j 件之一，它是一种复杂的中间件产品，是针对复杂环境下分布式应用的速 度和可靠性要求而实现的。它给程序员提供了一个事务处理的a p i ，程序员 可以使用这个程序接口编写高速而且可靠的分布式应用程序一基于事务处理 的应用程序。 2 2 中间件系统采用的系统结构 目前，并行中间件系统所依赖的并行计算机结构主要包括三种：共享磁 盘结构( s h a r e d d i s k ) 、共享存储器结构( s h a r e d m e m o r y ) 、无共享资源结构 ( s h a r e d n o t h i n g ) 。 1 s d 并行结构 s d 并行结构由多个具有独立主存储器的处理机和多个磁盘存储器构成， 9 哈尔滨t 程大学硕卜学位论文 每个处理机都可以读写任何磁盘存储器，多个处理机和磁盘存储器山高速通 信网络连接，i b m 的s y s p l e x 系统就是一个基于s d 结构的并行计算机系 统”。s d 结构并行计算机如图2 1 所示： 互联网络 图2 1s d 并行结构 s d 结构具有以下特点； ( 1 ) s d 结构可以使用标准总线互连，因而成本要比s m 结构低。 ( 2 ) 每个处理机有足够大的高速缓存空间，对共享磁盘的访问冲突可降 低，因而可扩充性较好，节点数目可达数百个。 ( 3 ) 各处理机节点的失败不致影响其他处理机的工作，因而系统可用性 高。 ( 4 ) 磁盘数据不需重新组织，从一个单处理机的集中系统向一个s d 系统 迁移简便而直接。 该结构的不足在于实现复杂以及存在潜在的性能问题，这是由于s d 方 案中每一处理机可以访问共享磁盘上的数据库页，但它们无共享内存，因此 数据被拷贝到各自的高速缓冲区中。为避免对同一磁盘页的访问冲突，该结 构需要一个分布式缓存管理器来对各处理机并发访问进行全局控制与管理， 并保持数据的一致性。维护数据一致性会带米额外的通信开销，此外对共享 磁盘的访问是现在的瓶颈。 2 s m 并行结构 s m 并行结构由多个处理机、一个共享主存储器和多个磁盘存储器构成， 多处理机的共享主存储器由高速通信网络连接，每个处理机可直接存取一个 或多个磁盘存储器，i b m l 3 7 0 多处理机系统、v a x 多处理机系统和s e q u e n t 1 0 哈尔滨l ：程火学硕十学何论文 系统都是具有s m 结构的典型并行计算机系统n 。s m 并行计算机结构如图 2 2 所示： 处军机 处辈机f 也机 l ii 互联网络 共享存储 器 图2 2s m 并行结构 s m 结构的优势在于实现简单和负载均衡。在该结构中，共同执行一条 s q l 语句的多个数据库构件通过共享内存来交换消息与数据。数据库中的据 划分在多个局部磁擞上，并可以为所有处理机访问。而且，查询问并行性的 实现不需额外开销，查询内并行性的实现也不太困难。这种系统可以基于实 际负载来给各处理机动态地分配任务，因而可以很好地实现负载均衡。 但是这种结构的系统由于硬件成员之i n j 的互连很复杂( 每个处理机要与 每个内存模块和每个磁盘相连) ，因而成本高。为了避免访问冲突增多而导 致系统性能下降，节点数目必须限制在几十个以内，可扩充性较差。此外， 内存的任何错误都将影n 向到多个处理机，因此系统可用性不是很好。 3 s n 并行结构 s n 并行结构由多个处理节点构成，每个处理节点具有自己独立的处理 机、主存储器和磁微存储器，多个处理机节点由高速通信网络连接，n u c b 系统、t e r a d a l a 系统、t a n d e m 系统和v a xc l u s t e r 等系统都是具有s n 结构 的并行计算机系统，。s n 结构并行计算机如图2 3 所示。 1 9 8 6 年，s t o n e b r a k e r 提出s n 结构是支持并行数据库系统的最好并行结 构，这个观点已经被普遍的接受。s n 结构的优点主要有四个”。： ( 1 ) 通过最小化共享资源来最小化由资源竞争带来的系统干扰。 ( 2 ) 具有高可扩展性，其处理机个数町以扩展到数千个甚至上力个，而 不增加处理机间的干扰。 l l n 合尔滨i ：程人学硕十学何论文 图2 3s n 并行结构 ( 3 ) 在数据库查询处理过程中需要在通讯网络一l 进行的数据传输量较 小。 ( 4 ) 在复杂数据席查询处理和联机事务处理过程中可达到按近线性的加 速比和伸缩比。 所谓加速比是指一定规模的任务在小规模系统和大规模系统上运行的时 问之比，即： 加速比= 鬟麓端 如果系统规模扩大了n 倍，例如节点数增加了n 倍后，加速比等于n ， 则称作线性加速比。伸缩比是任务在小规模系统上运行时m 与扩大n 倍的任 务在扩大n 倍的系统上运行时l 、日j 之比，即： 伸缩比= 纂篝鬟蒜 通过上述分析，本文研究的中间件系统采用s n 结构，在后续的研究工 作中，本文称s n 结构中每个由单处理机、主存储器和磁楹构成的单处理机 系统为处理节点。 2 3 中间件体系结构 并行中i 日j 件系统支持并行数据处理，提供并行数据库系统的基本功能和 一些蕈要的管理功能，为应用提供统一的编程模型。中间件系统采用并行处 1 2 哈尔滨t 稗大7 ：硕十学何论文 理技术，以全局模式向用户提供透明的数据企询服务。用户奄询住中间件中 分解为多个子查询，转发到相关的数据源实体完成并行查询。中间件向用户 提供透明的数据处理服务以实现对海量数据的访问，对数据节点进行有效地 管理以实现高性能并行处理，充分利用网格内数量可观的服务器资源，为用 户提供方便、快捷的数据服务是中间件系统结构设计的主要考虑。 目前，支持并行事务处理的数据库管理系统的实现方案可分为两种：重 写和扩充。重写是从零丌始设计一个并行数据库管理系统，这样可以借鉴以 往系统实现的经验教训和采用最新的研究成果和设计方案，甚至也可以对操 作系统进行改进，因为采用特制的操作系统可为数据库系统丌发并行性提供 更好的支持。扩充则是对已有的串行数据库系统进行功能增加和模块改进， 使系统能够在多个处理节点上运行，由于传统的关系数据库技术已发展了近 3 0 年，大量商品化系统已得到广泛的应用并具有良好的可靠性，因此，在现 有的数据库系统中扩充并行处理能力的模式得到了更为普遍的使用，本课题 所丌发的并行事务处理系统也正是基于这样一种实现方案。 整个系统的实现分为客户端、扩充的巾间层以及数据库服务节点三大部 分。系统绝人部分工作由中间层完成，并通过c l i e n t s e r v e r 模式分别与客户 端与数据库服务节点进行通信。这种层次结构不但使整个系统的成本降低， 而且更具灵活性，随着业务的增长，系统还可以轻松扩展，其系统结构如图 2 4 所示。 1 用户接口模块 用户接l j 模块负责监听客户端通过t c p i p 协议发送的连接请求。一旦 监听至0 客户端的连接请求，用户接口模块在向客户端发送同意建立连接命令 的同时，完成以下操作： ( 1 ) 建立w i n d o w ss e r v i c e s 。 ( 2 ) 建立其它服务线程。 ( 3 ) 建立系统缓冲区以及必要的磁盘初始。 ( 4 ) 将截获的s q l 语句( 或者是语句集合) 放入s q l 任务队列中( 内存 缓冲区的队列) 。 哈尔滨t 程大学硕十学位论文 匈1盈1圆圆 翊聊r w 艘1 蝴麓1 霸t 州 1 1 ，、t 、，t n 夕 代理模块l = i 用户接口 丫 止lu ，。悃 f r t 田、 请求分崭 7 毅铤仔储分配首埋 、 数据字典 1 字典管理器 数据存 候选存 查询分解 ， r r l 啊j 弭j j ；ch ，t - i 储分配贮分配 1 i 思力采 并行查询优化 l 数据重分布管理1 一圭 j 数据库基本模式信 i 查询计划 jl息 了l 一h l f j 垧蚀田由o 矾“1 “”。 7 【8 ”8 1 4 。“， t 、 ， il il 士 执行进程执行进程执行进程执行进程 是是建 i i 本地 本地本地本地 i 数据库 数据库数据库数据库 l一一、， 图2 4 中间件系统结构图 2 请求代理模块 对于每个用户请求建立一个服务进程，负责此用，- 的请求的处理与结果 的返回。 3 请求分析模块 请求分析模块负责以下工作： ( 1 ) 语法正确性检查，检查用户请求是否存在语法错误。 ( 2 ) 语句有效性检查，检查用户请求的对象是否存在。 ( 3 ) 语句安全性检查，检查用户是否拥有相应操作的权限。 ( 4 ) 分析完成用户操作，需要启动的节点情况。 1 4 哈尔滨i ：程人学硕 ：学位论文 4 查询分解模块 根据请求分析模块分析到的节点情况，将用户的请求分解成多个等价的 可以在底层数据库上执行的子请求。 5 存储管理模块 并行数据库与顺序数据库查询的不同之处在于查洵处理是在单个节点上 还是多个节点上进行。在并行事务处理系统中，由于数据可能存在f 一个或 多个节点上，如果对于任何一种杏询，都启动所有的节点进行查询，将增加 大量不必要的系统丌销( 包括c p u 、磁盘和网络带宽等) 。因此需要设计存 储管理模块来管理整个系统中的数据存储分配方式，同时通过查询系统中保 存的用户关系分布的数据字典，只启动相应的节点进行查询，降低了系统丌 销。 6 执行控制模块 此模块负责与底层数据库建立连接，将予操作发往底层数据库，并收集 底层数据库返回的结果存入结果缓冲区；另外，执行控制模块还负责对负载 进行均衡。 7 查询结果整理模块 当底层数据库返回的结果需要进行整理时，结果整理模块调用相应的算 法，对结果进行整理。比如用户在客户端执行排序操作，各底层数据库只是 返回在本地结果集中有序的结果，结果整理模块还需要对所有返回的结果按 照某种算法进行整理排序。 以。上足数钳库中间件各模块的功能。而并彳j ：数据库数据分存储分配的工 作主要集中在数据库的建立阶段、数据库的迁移、数据倾斜以及进行连接操 作时的数据重分布，以及查询优化为实现本地连接而进行的重分布操作时。 s n 结构并行数据库系统成本较低，节点间干扰小，具有极佳的可伸缩性和 可用性，它的唯一不足之处就是节点负载难以均衡。数据分布作为重要的负 载平衡机制，在s n 结构并行数据库系统中非常关键，它直接决定着系统的 性能好坏。由于它的静态本质，重分布代价巨大，所以一开始就选择一个合 适的数据分布策略尤为重要。 在图2 4 中可以看到，数据字典处于一个重要地位，当数据库建立或数 据重新分布时，关系的分布信息，如划分方式、划分属性、节点组等将记录 l5 n 合尔滨r 程大学硕 ：学位论文 在数据字典中，系统查询时也要访问数据字典来获圾数据在节点上的分布信 息，以决定把s q l 予查询分发到哪些节点。数据字典记录着每个节点的数据 分布情况，数据重分布工具中数据倾斜的判断也要根据数据字典中的内容来 判断。建立部分和执行部分就是通过数据字典来建立联系的。 2 4 中间件系统中存储分配研究 2 4 1 中间件存储分配介绍 本文所设计丌发的数据库中间件系统依托集群式并行计算机，通过中间 件系统将各个节点上独立运行的数据库联系起来，充分利用多处理机和多磁 盘的并行性来获得较高的处理能力和速度。为了充分利用系统的i 0 并行性， 一个关系中的元纽通常会分布在多个磁盘上，数据存储分配技术就是研究如 何对数据进行划分并把划分的数据分布到不同的节点上。数据分布不仪仪决 定着数据的分布，还决定着直接访问数据的操作( 如s e l e c t ) 的分布。 研究表明，数据存储分配策略对于并行数据库系统的性z 日- 匕e 和伸缩性具有 很大的影响。在中间件系统中，查询处理由多个处理节点共同完成，如果数 据存储分配策略不合理导致各节点负载不均，系统会等待最慢处理节点完成 操作，于是系统并行性不能得到充分发挥，造成系统资源极大浪费，既增加 了查询处理时问，也降低了系统的处理能力。本文设计研究并行数据处理中 间件系统的目的是实现数据库查询语句的并行执行，平衡各处理节点的负载， 使得各处理节点尽可能同时完成操作任务，从而提高查询执行的速度，以便 提高系统的性能。 2 4 2 中间件存储分配技术 开发中间件系统的第一步就是要对数据进行划分和分布，也就是确定如 何对数据进行划分和确定，采用何种方式将划分后的数据分布到各个节点上。 数据分布策略的好坏将直接影响中问件系统的性能，不良的数据分布策略将 导致严蕈的负载失衡，并且在进行事务处理时，需要很高的系统丌销，冈此， 采用什么数据分布策略就成为影响系统性能的关键，数据存储分配技术就成 为并行数据处理中间件中的重要技术之一。 哈尔滨t 样人学硕十学何论文 已出现的数据划分策略包括r o u n d 。r o b i n 、r a n g e 、h a s h 、h y b r i d r a n g e 等一维数掘划分方法，一维数据划分方法有一个共同的缺点，即不能支持在 非划分属性上具有选择谓词的查询；另外还有b e r d 、c m d 和m a g i c 等多 维数据划分方法，这些方法都是基于数据量平衡，还解决了划分属性与查询 属性不一致的问题。一维数据划分方法简单，容易实现，多维数据划分方法 复杂，不易实现，且多维数据划分方法的维护代价基本上已经抵消了其划分 方法所带来的好处，因此在许多实验和商用系统中不采取多维数据划分方法。 到目前为止，还没有一种通用的数据分布策略，本文通过研究，找到一 个适合本系统应用特点的数据分布策略，并实现相关的工具。 为数据