基于机群架构的并行数据库实现技术研究

第２９卷　第３期　计算机工程与设计　２００８年２月　ＶＯ１．２９　ＮＯ．３　Ｃｏｍｐｍｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ｄｅｓｉｇｎ　Ｆｅｂ．２００８　基于机群架构的并行数据库实现技术研究　柳锴１，２，３　唐雨新１，２，３　张云泉　，　李玉成‘　（１．中国科学院软件研究所并行计算实验室，北京１０００８０；２，中国科学院计算机科学国家重点实验室，　北京１０００８０；３．中国科学院研究生院，北京１０００８０）　摘　要：在总结了现有并行数据库实现模型的基础上，基于“半重写变换”模型…实现了一个并行数据库系统的原型。通过对　数据划分／重划分、并行选择、并行排序、并行连接等关键操作的实验分析，指出了“半重写变换”模型存在的缺陷，并提出了　一种混合式的改进模型。从理论上说，在机群架构下实现并行数据库系统，这种混合模型较单一模型更有优势。　关键词：并行数据库；实现模型；ＳＭＰ机群；数据划分；并行算法　中图法分类号：ＴＰ３１１．１３３，２　文献标识码：Ａ　文章编号：１０００—７０２４（２００８）０３．０５２６．０４　Ｒｅｓｅａｒｃｈ　ｏｎ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｔｅｃｈｎｏｌｏｇｙ　ｏｆ　ｃｌｕｓｔｅｒ　ｐａｒａｌｌｅｌ　ｄａｔａｂａｓｅ　ｓｙｓｔｅｍ　ＬＩＵ　Ｋａｉ　ＴＡＮＧ　Ｙｕ—ｘｉｎ‘ｌ２１３’ＺＨＡＮＧ　Ｙｕｎ—ｑｕａｎ　。。，ＬＩ　Ｙｕ—ｃｈｅｎｇ　（１．Ｐａｒａｌｌｅｌ　Ｃｏｍｐｕｔｉｎｇ　Ｌａｂ，Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｓｏｆｔｗａｒｅ，Ｃｈｉｎｅｓｅ　Ａｃａｄｅｍｙ　ｏｆ　Ｓｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ　１０００８０，Ｃｈｉｎａ；　２．Ｓｔａｔｅ　Ｋｅｙ　Ｌａｂ　ｏｆＣｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｃｈｉｎｅｓｅ　Ａｃａｄｅｍｙ　ｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ　１０００８０，Ｃｈｉｎａ；　３．Ｇｒａｄｕａｔｅ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｉｎｅｓｅ　Ａｃａｄｅｍｙ　ｏｆ　Ｓｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ　１０００８０，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｂａｓｅｄ　ｏｎ　ｔｈｅ　ａｎａｌｙｓｉｓ　ｏｆ　ｅｘｉｓｔｉｎｇ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｍｏｄｅｌｓ　ｏｆ　ｐａｒａｌｌｅｌ　ｄａｔａｂａｓｅ　ｓｙｓｔｅｍ，ａ　ｐｒｏｔｏｔｙｐｅｄ　ｐａｒａｌｌｅｌ　ｄａｔａｂａｓｅ　ｓｙｓｔｅｍ　ｉｍｐｌｅｍｅｎｔｅｄ　ｏｎ　ｈｔｅ　ｂａｓｉｓ　ｏｆ”Ｓｅｍｉ．ｒｅｗｒｉｔｅ　ａｎｄ　Ｔｒａｎｓｆｅｒ”（ＳＲＴ）ｍｏｄｅｌ…ｉＳ　ｄｅｓｃｉｒｂｅｄ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔｓ　ｏｆｃｕｓｅｄ　ｏｎ　ｓｏｍｅ　ｋｅｙ　ｏｐｅｒａｔｉｏｎｓ　ｓｕｃｈ　ａｓ　ｄａｔａ　ｐａｒｔｉｔｉｏｎｉｎｇ／ｒｅ—ｐａｒｔｉｔｉｏｎｉｎｇ，ｐａｒａｌｌｅｌ　ｓｅｌｅｃｔｉｏｎ，ｐａｒａｌｌｅｌ　ｓｏｒｔｉｎｇ，ｐａｒａｌｌｅｌｊｏｉｎ　ｒｅｖｅａｌｅｄ　ｔｈａｔ　ｈｔｅ　ＳＲＴ　ｍｏｄｅｌ　ｈａｄ　ｓｏｍｅ　ｌｉｍｉｔａｔｉｏｎｓ．　Ａ　ｈｙｂｒｉｄ　ｍｏｄｅｌ　ｉｓ　ｐｒｏｐｏｓｅｄ，ｗｈｉｃｈ　ｉｓ　ｃｏｎｓｉｄｅｒｅｄ　ａｓ　ａ　ｂｅｔｔｅｒ　ｍｅｔｈｏｄ　ｆｏｒ　ｉｍｐｌｅｍｅｎｔｉｎｇ　ｐａｒａｌｌｅｌ　ｄａｔａｂａｓｅ　ｓｙｓｔｅｍｓ　ｏｎ　ｃｌｕｓｔｅｒ　ｒａｃｈｉｔｅｃｔｕｒｅ　ｔｈａｎ　ｓｉｎｇｌｅ　ｍｏｄｅｌｓ．　Ｋｅｙ　ｗｏｒｄｓ：ｐａｒａｌｌｅｌ　ｄａｔａｂａｓｅ　ｓｙｓｔｅｍ；ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｍｏｄｅｌｓ；ＳＭＰ　ｃｌｕｓｔｅｒ；ｄａｔａ　ｐａｒｔｉｔｉｏｎｉｎｇ；ｐａｒａｌｌｅｌ　ａｌｇｏｒｉｔｈｍｓ　０　引　言　成为并行数据库设计者们纷纷采用的硬件平台。　在实现方式方面，目前存在３种实现模型，我们分别称之　数据库是计算机领域发展最快和应用最广的学科之一。　为重写、扩充和半重写变换“　。重写模型是以并行体系结构为　随着计算机应用领域的不断扩人，大型应用的强劲需求不断　背景重新设计并行数据库系统的实现方法；扩充模型则是在　促使数据库的规模迅速膨胀，对查询响应时间的要求更是有　现有的数据库管理系统中扩充并行处理功能；而半重写变换　增无减；同时机群技术日趋完善并成为后台超级服务的主流　模型是重写模型和扩充模型的结合。　平台，为高性能数据库的发展提供了强大的支撑。在硬件技　术和应用需求的双重推动下，运用先进的并行处理架构、以满　ｌ现有的并行数据库系统实现模型　足高性能应用需求为目标的并行数据库系统逐渐被人们所重　重写是从零开始重新设计一个并行数据库管理系统，这　视，成为当前数据库领域的研究热点之一。　样可以借鉴以往系统实现的经验教训Ｉ，采用最新的研究成果　根据处理机之间共享资源的方式的不同，可以将并行数　和最优的设计方案，甚至还可以对操作系统进行改进，因为采　据库的体系结构分为３种：共享主存的多处理机、共享磁盘的　用定制的操作系统可为数据库开发并行性提供更好的支持，　多处理机、无共享的多处理机。由于无共享结构具有高扩展　重写模型的代码修改率为１００％，图１（ａ）通常被并行数据库原　性、高可靠性和低成本的优势，它被认为是最适合实现并行数　型系统的研制者所采用，如著名的Ｇａｍｍａ系统。　据库的体系结构。而机群作为一种典型的无共享架构，自然　扩充是对已有的串行数据库系统进行模块改进和功能增　收稿日期：２００７．０３．１２　Ｅ—ｍａｉｌ：ｉｏｓｃａｓ＠ｇｍａｉｌ．ｔｏｍ　基金项目：国家自然科学基金项目（６０３０３０２０、６Ｏ５３３Ｏ２０）：国家９７３重点基础研究发展计划基金项目（２００５ＣＢ３２１７０２）；国家８６３高技术研究发　展计划基金项目（２００６ＡＡ０１Ａ１０２、２００６ＡＡ０１Ａ１２５）。　作者简介：柳锴（１９８２一），男，湖北武汉人，硕士研究生，研究方向为并行算法、并行数据库技术：　唐雨新，男，硕士研究生，研究方向为并　行算法、并行数据库技术；　张云泉，男，博士，副研究员，研究方向为高性能计算及并行数值软件、并行计算模型、并行数据挖掘、并行数据　库：　李玉成，男，研究员，研究方向为大规模科学与工程计算的方法与软件、高性能并行数学软件库。　维普资讯 http://www.cqvip.com 加，使系统能充分发挥多处理机的优势。扩充模型保持串行　数据库系统的应用界面不变，但是对底层ＤＢＭＳ的核心代码　ＤＢＭＳ　Ｉｎｓａｔｎｃｅ：负责各局部数据库的存取和查询。　２．２实验环境　我们借助ＯＳＣＡＲ　搭建了一个４节点的Ｂｅｏｗｕｌｆ机群，　其中１个是起集中控制作用的主节点，另外３个是计算节点，　各节点的配置如下：ＣＰＵ：ＩｎｔｅｌＰｅｎｔｉｕｍ（ｔｍ）ＩＩＩ　１．０Ｇ（ｘ２）。内存：　２ＧＢ　ＤＤＲ。硬盘：３６ＧＢ　ＳＣＳＩ。网卡０：ＩＢＭ　ｐｒｏ１Ｏ０。网卡１：　做了改写，图１（ｂ）这种模型的典型代表有Ｏｒａｃｌｅ公司的ＯＰＳ，　ＩＢＭ公司的ＤＢ２ＰＥ。　半重写变换“　也要求以传统的ＤＢＭＳ核心为基础，但重要　一点是该模型不要求修改ＤＢＭＳ源代码（这大大降低了实现　并行数据库系统的条件），它不改动底层ＤＢＭＳ，只对查询服务　的前端系统做了重写，图１（Ｃ）中国防科技大学的银河３系统　ＩＢＭｐｒｏ１００。节点间采用百兆交换机互联。　２＿３全局字典的设计　全局字典也称为数据字典。在传统定义中，数据字典是　数据库中的一块用来保存数据库自身信息的预留空间。由　即是基于该模型的一个实例。　莒（ａ）重写　甘（ｂ）扩充　营（ｃ）半重写变换　　于并行数据库硬件环境的特殊性，原型系统的全局字典除了　要保存数据库自身的信息外，还需要保存机群节点的配置信　息。通过加入全局字典，可以将那些相对稳定的信息提前保　存起来，这样可以避免查询时的重复操作，从而提高并行查　询的性能。　以下分别是全局字典中节点信息的表结构（ｎｏｄｅｓ　ｉｎｆｏ）和　关系表信息的表结构（ｔａｂｌｅｓ　ｉｎｆｏ）：　ｎｆｏ　（１）ｎｏｄｅｓｉ～图１并行数据库的实现模型　２原型系统的设计与实验　２．１系统架构　首先，我们基于“半重写变换”模型设计并实现了一个机　群环境下的并行数据库原型系统。它主要由查询引擎、并行　算法库、全局字典、执行进程以及多个ＤＢＭＳ　Ｉｎｓｔａｎｃｅｓ组成，　如图２所示。　用户　其中：ＩＤ是节点的编号，Ｈｏｓｔｎａｍｅ是该节点的主机名，Ｎａｍｅ　是该节点在机群系统中的别名，ＩＰ是该节点在机群系统中的　内部ＩＰ。　（２）ｔａｂｌｅｓ　ｉｎｆｏ　查询引擎　分析器　Ｉ全局字典Ｉ　二］［二　并行算法库　±　优化器　。。。。。。。●＿＿●＿。●。。一　——孺　数据重划分　并行选择　并行投影　并行排序　并行连接　、其中：ＩＤ是关系表的编号，Ｔａｂｌｅｎａｍｅ是该表的表名，ＰｒｉｍａｒｙＬ　调度器　ｋｅｙ是该表的主关键字名（如果没有，则为空），Ｔｕｐｌｅｓ　ｎｕｍ是该　表的元组的个数，Ａｔｔｒｉｂｕｔｅｓ　ｎｕｍ是该表的属性的个数，Ｖｅｃｔｏｒｓ　是区间划分的划分向量。　执行进程ｉ　ｆ执行进程ｆ　…　ｆ执行进程　划分向量Ｖｅｃｔｏｒｓ的格式是原型系统自定义的，我们将不　同属性的划分向量集中在一起，以字符串的形式存放在数据字　ＤＢＭＳＩ　Ｉ　ＤＢＭＳｌ　Ｉｎｓｔａｎｃｅｌ　１Ｉｎｓｔａｎｃｅｌ　…　　ｌＤＢＭＳ　Ｉｌｎｓｔａｎｃ，　典中，然后利用专门设计的提取算法来获取所需的划分向量。　２．４并行算法库的设计　在开发并行算法库时，选择实现了３个具有代表性的操　作——选择、排序、连接。它们的性能表现可以直接反映出实　现模型的优劣。为了便于代码重用，我们将并行算法中的公　图２基于“半重写变换”实现模型的并行数据库原型系统架构　查询引擎：该模块为原型系统的前端，它的功能是从用户　处接收ＳＱＬ命令并交给分析器进行语法分析，然后优化器对　其进行优化，生成并行执行规划，最后调度器调用并行算法库　中的相应算法完成该规划。　全局字典：它用来管理全局数据库的表信息以及机群的　节点信息，用来指导查询优化、数据划分和并行算法的执行。　并行算法库：这是原型系统的核心部分，它由数据划分／　重划分、并行操作两类模块组成。数据划分模块用来实现全　共部分提取出来，单独用一个模块来实现，于是形成了并行算　法库中各子模块之间的依赖关系树，如图３所示。　局数据库的分布式存储；数据重划分模块被并行排序和并行　连接模块调用，用来实现复杂并行操作所需的数据重分布功　能；并行选择、并行投影、并行排序、并行连接是若干基本关系　操作的并行实现。　执行进程：负责并行查询规划中算子的执行，包括多处理　机节点之间为执行并行算法而必需的同步与通信。　图３并行算法库中各模块之间的依赖树　２．４．１数据划分（Ｐａｒｔｉｔｉｏｎｉｎｇ）　并行数据库的数据划分是指将数据库中的各种物理数据　——５２７・——　维普资讯 http://www.cqvip.com

（关系元组、索引节点）有效的分配到各个处理节点上，通过发　掘Ｉ／０并行来提高并行数据库系统的性能。原型系统的数据　划分模块采用了以下两种划分算法：　（１）基于Ｒｏｕｎｄ—Ｒｏｂｉｎ的数据划分：假设ＲＥＣ，是Ｒ的第ｆ个　元组，系统的处理单元数为Ⅳ，则经过划分后，ＲＥＣ，所在的处理　并行选择算法是基于Ｒａｎｇｅ数据划分设计的，在做并行　选择时，我们假设待查询关系已经按特定的划分向量均匀的　分布到Ｎ个计算节点中了，其执行过程如下：　首先，主节点从用户处获得选择操作的关系名和选择条　件，并根据划分向量得到需要启动的处理机序号，然后，被激　活的计算节点并行的执行本地选择操作，并将查询结果发向　主节点，最后，主节点将查询结果汇总。　单元号可以由下式计算得到：ＰＵＮｕｍ（兄　Ｇ）＝ｉＭＯＤＮ。　（２）基于Ｒａｎｇｅ的数据划分：先将关系Ｒ的元组按划分属　性Ａｔｔｒ进行排序，然后将所排值域序列划分成Ｎ个子区间，假　２．４．４并行排序（ＰＳｏｒｔ）　设为Ｉ。＝【Ｖ。，Ｖ。］，Ｉ　＝【Ｖ。，Ｖ　－Ｉ　＝【Ｖ　，Ｖ　］，其中Ｎ为系统处理　单元总数，我们把这一组区间称为“划分向量”。再按照下式　对数据元组进行分类：＆＝（ＲＥＣ，Ｉ肛ＧＥＲ，Ａｔｔｒ（ＲＥＣ，）∈　），　七∈［１，ｊｖ］。最后把元组集合＆放置到如下处理单元上：ＰＵＮｕｍ　，／ｌＲＥＣ　：Ｋ　ＲＥＣ　∈ｓＩ　２．４．２　数据重戈ｄ分（Ｒｅ．Ｐａｒｔｉｔｉｏｎｉｎｇ）　为了模拟任意时刻并行数据库中数据的分布情况，我们　先调用Ｒｏｕｎｄ—Ｒｏｂｉｎ数据划分算法对计算结点上的数据做了　初始化，然后在此基础上做数据重划分。　（１）基于Ｒａｎｇｅ的数据重划分：首先，丰节点从全局字典　中获取各机群节点的ＩＰ信息，并提取出关系在划分属性上的　划分向量。然后，各计算节点按照划分向量将本地元组划分　成Ｎ块（Ｎ为处理节点数），再将“块数据”按“块号”发送到对应　的计算节点上去，最后各计算结点将接收到的“块数据”汇总。　下面以Ｎ＝３为例，展示该算法的数据流程，如图４所示。　Ｒ　图４基于Ｒａｎｇｅ的数据重划分的数据流程　（２）基于Ｈａｓｈ—Ｒｏｕｎｄ—Ｒｏｂｉｎ的数据重划分：这种重划分算　法与Ｒａｎｇｅ重划分的原理基本相同，只有两点区别：在本地分　块阶段，Ｒａｎｇｅ算法是基于数据字典中的划分向量的，而Ｈａｓｈ．　Ｒｏｕｎｄ—Ｒｏｂｉｎ是基于一个逻辑桶划分函数ｈ的，而且后者分的　块数更多．我们称之为“桶”：另外，由于Ｈａｓｈ—Ｒｏｕｎｄ—Ｒｏｂｉｎ重　划分的块数大于处理节点数，所以不能像Ｒａｎｇｅ算法那样简　单处理，而是需要采取轮转策略进行节点间数据交换。下面　以Ｎ＝３为例．展示该算法的数据流干旱，如图５所示。　２．４－３　并行选择（ＰＳｅｌｅｃｔ）　Ｒ１　Ｒ２　Ｒ３　Ｉ　』　ＢＩＩＩＢＩ２］ＢＩ３　ＢＩ４］ＢＩ５］ＢＩ６　Ｂ２１１．２２　Ｆ．２３１．２４１．２５１．２６　Ｂ３１１．３２１．３３１．３４１．３￣１．３，　ＢＩｌ　匿　ＩＩＢ２１ＩＢ３１　Ｂｉ４１Ｂ２４［Ｂ３４　Ｂｌ２ＩＢ２２ｌＢ３２ｌＢ１蓦　５ｌＢ２５ＩＢ３５　Ｂｌ３ＩＢ２３ＩＢ３３ｌ　ｌ６ＩＢ２６ｌＢ３ｌｆ　　ｌ　』　』　』　』　Ｉ　Ｂｌ　Ｂ４　Ｂ２　ｌ　Ｂ５　Ｂ３　ｌ　Ｂ６　图５基于Ｈａｓｈ．Ｒｏｕｎｄ—Ｒｏｂｉｎ的数据重划分的数据流程　——５２８——　并行排序算法是基于Ｒａｎｇｅ数据重划分设计的，在做并　行排序前，我们假设待查询关系以一种随机的状态均匀分布　于Ｎ个计算节点中，其执行过程如下：首先，主节点从用户处　获得排序操作的关系名和排序属性，然后将排序属性作为划　分属性调用Ｒａｎｇｅ重划分算法，待元组重分布完毕后，所有计　算节点并行的执行本地排序操作。　２．４．５并行连接（ＰＪｏｉｎ）　并行连接算法是基于Ｈａｓｈ．Ｒｏｕｎｄ—Ｒｏｂｉｎ数据重划分设计　的，在做并行连接前，我们假设待查询关系以一种随机的状态　均匀分布于Ｎ个计算节点中，其执行过程如下：首先，主节点　从用户处获得连接操作的关系名Ｒ、ｓ以及连接属性Ｒ．ａ、Ｓ．ｂ，　然后将连接属性分别作为对应关系表的划分属性调用Ｈａｓｈ—　Ｒｏｕｎｄ－Ｒｏｂｉｎ重划分算法，待元组重分布完毕后，所有计算节　点并行的执行本地连接操作，最后主节点将查询结果汇总。　２．５实验和分析　２．５．１　并行选择（ＰＳｅｌｅｃｔ）　“选择”是数据库查询中最简单和最常用的操作，为了对　并行选择的性能进行全面考察，我们针对以下几种典型的选　择操作对系统的并行选择模块进行了测试：　（１）全选择　ｓｅｌｅｃｔ　ｆｒｏｍ　ｔａｂｌｅ；　（２）点选择　ｓｅｌｅｃｔ　ｆｒｏｍ　ｔａｂｌｅ　ｗｈｅｒｅ　ｉｎｔｎ＝５０００；　（３）区间选择　ｓｅｌｅｃｔ　ｆｒｏｍ　ｔｂａｌｅ　ｗｈｅｒｅ　ｉｎｔ　ｎ＞１０００（命中１个计算节点）：　ｓｅｌｅｃｔ　ｆｒｏｍ　ｔａｂｌｅ　ｗｈｅｒｅ　ｉｎｔ　ｎ＞５０００（命中２个计算节点）：　ｓｅｌｅｃｔ｝ｆｒｏｍ　ｔａｂｌｅ　ｗｈｅｒｅ　ｉｎｔ　ｎ＞５００（命中３个计算节点）；　在３个计算节点的情况下，串行选择与并行选择的运行　时间对比如图６（ａ）～６（ｅ）所示。　加速比统计如表ｌ所示。由表ｌ可以看到，并行选择在　各种操作上都有明显的优势。全选择的平均加速比稳定在２．５　左右，区间选择ｌ（命中１个处理机）的平均加速比为１．２９，区间　选择２（命中２个处理机）的平均加速比为１．６９，区间选择３（命　中３个处理机）的平均加速比为２．５５，点选择的平均加速比高　达２．８０，在某些数据集上甚至出现了超线性加速比。　对于区间选择１只有ｌ－３左右的加速，我们的解释是：当　只命中一个处理机时，我们的并行选择实际上己退化为串行　选择。虽然查询范围缩小为原来的ｌ／３，但是由于受启动并行　进程和进程间通信开销的影响，没有获得更高的加速比。　２．５．２并行排序（ＰＳｏｒｔ）　“排序”虽然不是数据库领域的独有问题，但却是数据库　应用中非常普遍且特别耗时的操作之一。我们通过下面的查　维普资讯 http://www.cqvip.com

４００　３５０　３００　厘２５０　苔２００　霜１５０　１００　５０　０　数据规模　（ａ）“全选择”　８　／　／　垂　／　／　／—，——一　ｒ———一　６　／．——－一　—　＝．—●ｒ　。　．　．　　．０　５　１０　１５　２０　２５　３０　数据规模　（ｂ）“点选择”　器　４　／　／　／　／　／／／　／，／　／　；　—－－　，一　８　　．　．　．．　　．０　５　１０　１５　２０　２５　３０　数据规模　（ｃ）命中１个节点的“区间选择”　２８　／　／　／　／—／　盖嚣　／—，一　一，　——／．／　—　：．一—－　２８　ｊ　．　．　．　．　０　５　１０　１５　２０　２５　３０　数据规模　（ｄ）命中２个节点的“区间选择”　３００　２５０　垂２００　鲁１５０　蒿１００　５０　０　数据规模　（ｅ）命中３个节点的“区间选择”　＋并行选择；　＋串行选择　图６　串行选择与并行选择的运行时间对比　表１并行选择操作的加速比（３个计算节点）　选数据规模（×１０　）　择类型　０．１５　１．２　３．０　６．０　９　０　ｌ２．０　３０．０　全选择　２．０９　２．５５　２．４３　２．４５　２　５７　２．５６　２．５４　点选择　３．１５　２．６２　２．８８　２．７５　２．７０　３．Ｏ０　２　５２　区间选择１　１．０６　１．８１　１．２７　１．Ｏ８　１　２２　１．２６　１．３３　区间选择２　１．７６　１．７２　１　７１　１．６７　１．６９　１．６５　１．６３　区间选择３　２．４０　２．６７　２．５６　２．７７　２．６５　２．６５　２．１４　询操作对原型系统的并行排序模块进行了性能测试：　ｓｅｌｅｃｔ　ｆｒｏｍ　ｔａｂｌｅ　ｏｒｄｅｒ　ｂｙ　ｉｎｔｎ；　在３个计算节点的情况下，串行选择与并行选择的运行　时间对比如图７所示。加速比统计如表２所示。　６００５。。　／　／　垦４００　黜　，／　／／　Ｐ　ｒ　：　．　０　５　１０　１５　２０　２５　３０　数据规模　－－－ｉｔ－－并行选择；　＋串行选择　图７“排序”的串并行时间对比　表２并行排序操作的加速比（３个计算节点）　数据规模（×１０　）１　０．１５　Ｉ　１．２　ｌ　３．０　ｌ　６．　９．０　１２．０　３０．０　平均加速比　ｆ　０．５９　ｆ　１．Ｏ０　ｆ　０．９６　ｆ　１　Ｏ１　１．０４　１．１４　１．１４　可以看到，并行排序并没有像并行选择那样获得令人满　意的加速比，在数据集较小时甚至会导致性能劣于串行排序。　造成这种现象的客观原因是：机群的节点数太少，无法充分发　挥并行化后的优势；另一方面，由于时间的关系，没有选取更　大的测试集进行测试，从时间曲线来看，当继续增大数据集　时，并行排序的加速比可能会继续增大。　２．５－３　并行连接（ＰＪｏｉｎ）　“连接”是数据库查询中最耗时和最重要的操作，也是构　成多元连接查询的基本运算。我们通过最简单的等值连接查　询来对原型系统的并行连接模块进行测试：　ｓｅｌｅｃｔ　ｆｒｏｍ　ｔｌ，ｔ２　ｗｈｅｒｅ　ｔ１．ａ＝ｔ２．ｂ；　在３个计算节点的情况下，串行选择与并行选择的运行　时间对比如图８所示。加速比统计如表３所示。　／　弱　∥　／　，，　蔷　／／　一，　．　．　．．－　｝，一一　．　　．．　０　５　１０　１５　２０　２５　３０　数据规模　－－－ｉｔ－－并行选择；　＋串行选择　图８“连接”的串并行时间对比　表３并行连接操作的加速比（３个计算节点）　与并行排序一样，并行连接也存在着同样的性能问题，具　体原因会在后面详细说明。　３改进模型的提出　通过上述测试结果我们可以看到：基于“半重写变换”模　型实现的原型系统对数据交换量很小的操作（如并行选择）具　有显著的加速效果，但是对于并行排序、并行连接这种数据交　换量大的操作就显得力不从心了。　为了改进这种模型，我们有必要分析一下“半重写变换”　的本质。这种模型的主要优点是：结构简单、易于实现、可扩　（下转第６４６页）　－——５２９－——　维普资讯 http://www.cqvip.com

■．　录数的持据体元具系标统数有本系不准据文的管同。广提重理元极泛出复数如大适了建据何动地用设标对态减性问准不元题少，加以数同。了快及据的重我工了标目复们作政录准将建流府系下设继程信统的工续息元配研作目化数置究，录工建据从动系作设管根态统理流的本元，策的速扩上数略工大度提据，作适。升　解标，用了决准以性下支目。　参考文献：　［１］　何志兰．网络信息资源组织～Ｄｕｂｌｉｎ　Ｃｏｒｅ［Ｊ］．现代情报，２００５　（１）：８３．８４．　［２］　赵志荣，张小林．ＧＩＬＳ：结构、元数据、应用［Ｊ］．．隋报科学，２０００，１８：　８ｌ６＿８１９．　［３］　何小箐．论电子政务档案元数据标准【Ｊ］．现代图书情报技术，　２００３，６：８０－８　１．　【４］　政务信息资源目录体系工作组．政务信息资源目录体系第３　部分：核　Ｉｉ，元数据编制说明和征求意见稿［ｓ］．２００５．　【５］ＸＭＬＳｃｈｅｍａＰａｒｔ１：Ｓｔｒｕｃｔｕｒｅｓ　Ｓｅｃｏｎｄ　Ｅｄｉｔｉｏｎ［Ｓ／ＯＬ］．ｈｔｔｒｌ：／／　ｗｗｗ．ｗ３．ｏｒｇ／ＴＲ／ｘｍｌｓｃｈｅｍａ－２／＃ｄａｔａｔｙｐｅ．２００７—０１－０３．　［６］ＸＭＬ　Ｓｃｈｅｍａ　Ｐａｎ１：Ｓｔｒｕｃｔｕｒｅｓ　Ｓｅｃｏｎｄ　Ｅｄｉｔｉｏｎ［Ｓ／ＯＬ］．ｈｔｔｐ：／／　ｗｗｗ．ｗ３．ｏｒｇ／ＴＲ／ｘｍｌｓｃｈｅｍａ一１／，２００７—０１—０３．　［７］　高云君，张学杰，章方铭．ＸＭＬ技术在电子政务信息交换中的　应用研究［Ｊ］．计算机工程．２００３（２３）：１７０—１７９．　［８］　周红波，孙宇达，王继霞，等．基于ＸＭＬ的数据交换及其参照完　整性研究［Ｊ］．计算机工程与设计，２００７，２８（１１）：２６１１－２６１３．　（上接第５２９页）　展性好，但是它的缺点也很明显，由于这种模型不要求改动底　考虑通信问题带来的影响。　层ＤＢＭＳ，所以它的改进措施都位于ＤＢＭＳ核心之外，并行性　的获取主要是通过数据分块来榨取Ｉ／０并行实现的。也就是　参考文献：　说，在执行实际查询操作之前，所有的数据必须通过数据划分　［１］　杨利，昌月楼．并行数据库技术［Ｍ］．长沙：国防科技大学出版　或重划分放到正确的“位置”后，才能开始并行的执行相关操　社。２０００．　作。在这种模型下，计算和通信是分离的，对于通信量小的操　［２］　ＳｃｈｉｋｕｔａＥ．ＫｉｒｋｏｖｉｔｓＰＣｌｕｓｔｅｒｂａｓｅｄｈｙｂｒｉｄｈａｓｈｊｏｉｎ：Ａｎａｌｙｓｉｓ　ａｎｄ　作，计算开销占据主导地位（如并行选择），于是并行化的好处　ｅｖａｌｕａｔｉｏｎ［Ｃ］．ＰｒｏｃⅢＥＥｌｒ／ｔｅｍａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＣｌｕｓｔｅｒＣｏｍ．　得以凸现出来；但是对于通信量很大的操作（如并行排序、并　ｐｕｔｉｎｇ，Ｃｈｉｃａｇｏ：ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　Ｓｏｃｉｅｔｙ　Ｐｒｅｓｓ，２００２：４６１—４６６．　行连接），无论怎么改进并行算法也无法弥补高昂的通信开销。　［３］　１￣ｊｋｕｒｎａｒ　Ｂ．Ｈｉｇｈ　ｐｅｒｆｏｒｍａｎｃｅ　ｃｌｕｓｔｅｒ　ｃｏｍｐｕｔｉｎｇ　ａｒｃｈｉｔｅｃｔｕｒｅｓ　基于以上分析，我们提出了一种新的实现模型。它是综　ａｎｄ　ｓｙｓｔｅｍｓ［Ｍ］．Ｐｒｅｎｔｉｃｅ—Ｈａｌｌ　Ｉｎｃ，１９９９．　合了“半重写变换”模型和“扩充”模型各自的优势的混合模　【４］　Ｇｏｅｔｚ　Ｇｒａｅｆｅ．Ｉｍｐｌｅｍｅｎｔｉｎｇ　ｓｏｒｔｉｎｇ　ｉｎ　ｄａｔａｂａｓｅ　ｓｙｓｔｅｍｓ【Ｊ】．　型。我们不妨将基于机群的数据库查询操作分为两大类：通　ＡＣＭ　Ｃｏｍｐｕｔｉｎｇ　Ｓｕｒｖｅｙｓ，３８（３）：１０　ｅｓ，２００６．　信密集型操作和通信稀疏型操作。对于通信稀疏型操作，我　［５］　Ｊｏｈｎ　Ｃｉｅｓｌｅｗｉｃｚ，Ｊｏｎａｔｈａｎ　Ｂｅｒｒｙ，Ｂｒｕｃｅ　Ｈｅｎｄｒｉｃｋｓｏｎ，ｅｔ　ａ１．Ｒｅａ－　们依然采用“半重写变换”来实现；而对于通信密集型操作，我　ｌｉｚｉｎｇ　ｐａｒａｌｌｅｌｉｓｍ　ｉｎ　ｄａｔａｂａｓｅ　ｏｐｅｒａｔｉｏｎｓ：Ｉｎｓｉｇｈｔｓ　ｆｒｏｍ　ａ　ｍａｓｓｉｖ－　们则改用“扩充”模型来实现。“扩充”模型是一种需要改动底　ｅｌｙ　ｍｕｌｔｉｔｈｒｅａｄｅｄ　ａｒｃｈｉｔｅｃｔｕｒｅ［Ｃ］．Ｃｈｉｃａｇｏ，Ｉｌｌｉｎｏｉｓ：Ｐｒｏｃｅｅｄ－　层串行ＤＢＭＳ的模型，它通过在ＤＢＭＳ核心内部实现并行操　ｉｎｇｓ　ｏｆｔｈｅ　２ｎｄ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｄａｔａ　Ｍａｎａｇｅｍｅｎｔ　ｏｎ　作算法，来达到计算和通信的重叠，从而削弱通信开销对总查　Ｎｅｗ　Ｈａｒｄｗａｒｅ，２００６．　询时间的影响。从理论上说，这种模型比单一的“半重写变　［６］　Ｔｈｅ　Ｏｐｅｎ　Ｃｌｕｓｔｅｒ　Ｇｒｏｕｐ．Ｏｓｃａｒ　ｃｌｕｓｔｅｒ　ｕｓｅＰｓ　ｇｕｉｄｅ　ｓｏｆｔｗａｒｅ　换”和“扩充”模型更适合于在机群系统上实现并行数据库。　ｖｅｒｓｉｏｎ　４．２　ｄｏｃｕｍｅｎｔａｔｉｏｎ　ｖｅｒｓｉｏｎ　４．２．［ＥＢ／ＤＫ］．ｈａｐ：／／ＯＳＣａｒ．　４结束语　ｓｏｕｒｃｅｆｏｒｇｅ．ｎｅｔ，２００５－１０－２８．　［７］　ＭｉｃｈａｅｌＪ　Ｑ．Ｐａｒａｌｌｅｌ　ｐｒｏｇｒａｍｍｉｎｇ　ｉｎ　Ｃ　ｗｉｔｈ　ＭＰＩ　ａｎｄ　ＯｐｅｎＭＰ　虽然基于机群架构的并行数据库系统具有可扩展性好、　［ＭＩ．Ｔｈｅ　ＭｃＧｒａｗ－Ｈｉｌｌ　Ｃｏｍｐａｎｉｅｓ　Ｉｎｃ，２００４．　易于开发等优势，但是同机群上的其它应用一样，机群数据库　［８］　Ｖｉｋｒａｍ　Ｖ　ＭｙＳＱＬ：Ｔｈｅ　ｃｏｍｐｌｅｔｅ　ｒｅｆｅｒｅｎｃｅ［Ｍ］．ＭｃｒＧａｗ－Ｈｉｌｌ　也会遇到通信瓶颈的问题，在选择一种实现模型时，必须充分　Ｏｓｂｏｍｅ　Ｍｅｄｉａ，２００４．　・——６４６・——