基于MapReduce的OCL的并行查询方法

金仙力 马凯旋

(南京邮电大学计算机软件学院 江苏 南京 210003)

0 引 言

近年来，计算机应用发展迅速，社交网络、电子商务、数字城市等许多应用领域中产生了规模巨大的数据，这些应用数据不仅存储量大，而且增长速度也非常迅猛[1]。为了解决上述问题，Google公司在2006年提出了“云计算”的概念。美国国家标准与技术研究院(NIST)将云计算定义为借助互联网实现按需、随地、便捷地访问共享资源池的计算模式。云计算是信息产业的一大创新模式，一经提出就获得了各个领域的广泛关注。

OCL以约束的形式描述类的属性或方法，可以准确地约束行为，广泛地应用于模型约束中。随着信息技术地发展，OCL约束变得越来越复杂，OCL规则库也相应地变得越来越大。OCL查询功能在处理少量的数据时是高效的，但是在处理大量的数据时，不能在有效的时间内得出最终的结果。所以，如何处理大规模数据下的OCL查询是迫切需要解决的问题。Google 提出的MapReduce并行编程框架，在处理大规模数据问题上具有显著的优势，能够满足人们对数据处理的需要。

因此，为了提高OCL查询的速度，本文提出来一种基于MapReduce的OCL并行查询方法OPQM(OCL Parallel Query Method)。主要内容：使用MapReduce等并行编程框架来简化数据的处理模型，通过提取OCL对象属性集合，实现从OCL规则库查询到OCL对象属性查询的查询转化，并利用MapReduce实现对象属性并行查询。

1 相关工作

对象约束语言OCL是在UML中特别用来对约束和规则进行说明的语言[2]。尽管OCL语言是一种形式化语言，但是具有易读、易写等特点。它主要有两个作用：一是对模型进行语义约束；二是对模型的查询。OCL用于查询时，主要是用于根据对象属性查询满足约束条件的对象，并且在查询时可以对图中的任何元素写表达式。其中，对象属性是指与模型中对象有关的特征。由上述内容可得知，对于OCL的约束查询也就相当于对约束中所包含的OCL对象属性集合的查询。

随着OCL规则库的增大，传统的查询处理方式需要花费大量的时间匹配所有的对象属性与查询条件。因此，为了提高海量OCL约束查询的效率，需要一种方法来提高OCL约束的查询速度，减少整个查询的时间。OCL规则库可以遵循XML标准进行描述[3]，参考XML文档查询的优化，可以对OCL规则库进行查询优化。

目前，有很多关于XML海量数据的分布式处理的研究，黄玉龙等[4]借助关系数组等设计了处理的XPath查询算法GRAXQ。在并行查询阶段,依次执行每个定位步且标记返回结果，极大减少了查询过程中的消重代价。

闫威等[5]提出了MapReduce编程模型下多谓词选择的查询处理方法。包括海量XML数据的存储方法、MapReduce编程模型下基于多谓词选择的Map逻辑算法和Reduce逻辑算法、基于多谓词选择的MapReduce查询优化方法，提高了系统的性能。

何志学等[6]提出TwigMRR算法对XML Twig查询进行分布式处理。先对XML数据进行Dewey编码，水平切分后存储于分布式文件系统，再进行并行查询。

李东等[7]为了实现基于MapReduce的XML查询处理,首先实现了区间编码、前缀编码、层次编码3种不同的XML数据编码方式,以此为基础来研究基于MapReduce的XML结构连接处理。同时，建立了代价模型,通过代价估算获得优化的查询计划树。

Fan等[8]提出了一种基于MapReduce的高效的分布式XPath查询处理。他们使用虚拟节点将大规模XML数据文件拆分成文件片段，分配到分布式存储系统。此外，为了有效地处理大型的XML数据，他们构建分区索引并使用随机访问机制来执行查询。

Damigos等[9]提出了一种整合大量XML数据的技术，并使用MapReduce框架来有效地查询集成数据。为了实现这个功能，他们提出了一个单步的MapReduce算法，该算法利用虚拟结构，并以分布的方式有效地计算给定XPath查询的答案。

Choi等[10]为大规模XML数据设计了并行树标签算法。他们提出基于MapReduce框架的两个突出的树标签方案的并行版本。他们利用工作负载平衡和数据重新分区的技术，解决由于运行时数据偏斜和MapReduce的继承限制而导致的性能问题。

Khatchadourian等[11]提出目前ChuQL的实现利用现有的主存储器XQuery处理器并面临两个挑战：中间XML值增长大于内存、大量的输出文件。为此他们描述了两个ChuQL构造来克服这些限制，分别是使用迭代器来处理XML值序列和分割作业输出。

Bi等[12]提出了一种基于大规模XML文档的分布式学习解决方案，它基于MapReduce技术将XML文档分布式转换为表示模型，并采用基于极限学习机的分布式学习组件进行分类或聚类任务。

Song等[13]集成了数据存储，标签，索引和并行查询，以处理大量的XML数据。具体来说，引入了SDN标签算法和使用DHT的分布式分层索引。

Bidoit等[14]提出一个处理大型XML文档的查询和更新的研究原型。该原型基于静态和动态分割输入文档的想法，以便在Map / Reduce集群的机器之间分配计算负载。可以运行预定义的查询和更新符合XMark模式的文档，以及提交自己的查询和更新。

Consens等[15]描述了ChuQL，一个MapReduce扩展到XQuery，以及相应的Hadoop实现。ChuQL语言结合了记录来支持MapReduce的键/值数据模型，并且利用高阶函数提供语义。

XML已经是网络信息描述和交换的标准，随着越来越广泛的XML应用，关于XML数据的查询方法也越来越多。但是，很多XML数据查询方法都存在相应的局限性。

由此可知，OCL规则库可以遵循XML标准进行描述，参考XML文档查询的优化，可以对OCL规则库进行查询优化。但是与XML文档相比，OCL规则库中的对象属性所包含了许多丰富的信息，我们需要对这部分属性进行相应的处理。本文中我们采用预处理的方式，对涉及的所有OCL对象属性进行提取，并使用并行模型来解析匹配这些属性。

2 基于对象属性的OCL并行查询

2.1 MapReduce并行处理模型

MapReduce是谷歌首先提出的一种在大型计算机集群上处理大数据的并行计算模型，在谷歌以及其他公司的许多项目中得到了广泛应用。它是数据密集型的并行计算模型，即特别适合于处理大规模海量数据。MapReduce既是一种并行计算模型，又是一种并行计算框架。

MapReduce计算模式是云计算的核心计算模式，解决大规模数据的处理问题。它在设计之初，就将局部性原理纳入考虑的范畴，通过利用局部性原理实现问题的分而治之。Map 调用能够被分布到多个节点执行，是通过将输入数据分割为若干个数据片段的集合实现的，不同的节点能够同时并行处理输入的数据片段，同时Reduce 调用也会被分布到多个节点上并行执行。Map 调用产生的中间 key 值会被分区函数分成N个分区，其中的分区函数、分区个数(N)由用户决定。MapReduce流程的三个阶段如图1所示。

图1 MapReduce的操作流程图

(1) Map阶段 由于 Map 是并行操作数据集，所以用户程序首先会调用的MapReduce库，对输入的数据集进行操作，将数据集分割成一些数据片段如上图的数据块。在数据分割完以后，会形成多个分割体，为了保证处理的效率，分割体会被分配到不同的Map处理器上进行并行处理。Hadoop 中的类 Input Format，从输入数据中解析出键值 (key/value)对。接下来，Map函数接收传入的键值(key/value)，并对其进行处理，产生中间的键值 (key/value)对，并将这些中间数据缓存到内存中。同时，为了提高Reduce的处理效率以及增加集群内部数据的传输速度，在Map函数之后设置了一个洗牌(shuffle)过程。

(2) 中间阶段 中间阶段的实现主要是由Hadoop 框架提供的一个合成器(Combine)来完成。中心控制作业 Job Tracker 会选取节点来进行 Map 运算，产生键值(key/value)对。同时，综合考虑性能和效率因素，这些键值(key/value)将被收集到一些 List 数据集中，而不会立即写入输出文件。

(3) Reduce 阶段 这个过程由复制、排序、 reduce 任务这3个步骤组成。在集群模式下，首先，服务器上的中间阶段数据会周期性地复制到本地文件系统上。复制完数据之后，Reduce 任务会对这些中间阶段的数据进行排序，将具有相同的数据进行整理并合并到一个文件中。最后一步由 Reduce 函数完成，将键(key)所对应的值(values)传给 Reduce 函数产生最后的结果。

将MapReduce并行模型和OCL规则库的存储结构综合起来，MapReduce中的最小处理单元即是OCL规则库中的一个对象属性。在处理过程中，节点根据实际的查询，匹配并筛选OCL对象属性，得到满足条件的对象属性集合，并对其进行构造得到最终的查询结果。

2.2 对象属性集提取Extraction算法

并行处理模型面对的处理对象必须可以拆分，也就是说这些处理对象能够被分成若干个子对象，这样才能被不同的处理器并行处理。MapReduce模型和上述的工作原理一致，它是把一个大的数据分割成多个独立的片断(Splits)。

为了让OCL规则库可以有效地在云计算的环境下进行并行查询，就需要对OCL规则库进行预处理，即对OCL规则库提取对象属性，并由此组成OCL对象属性集合，用集合来替代原来的OCL规则库作为云计算并行模型中的输入数据。

在MapReduce并行模型中，这些对象属性集合就会被分割成多个独立的Splits，然后若干个Splits将被分配到不同的Map处理器上进行处理，每个Splits经过Map函数处理之后，还会有一个洗牌(shuffle)过程,之后才进行相应的Reduce任务。

我们使用的预处理方法是基于Hadoop的InputFormat，根据查询条件，筛选出OCL规则库中满足条件的对象属性片段并构造OCL对象属性集合。

使用算法Extraction(fileName，nodeName)提取对象属性，其中fileName是OCL原始规则库名(该规则库是预先存储在HDFS 中的)，nodeName是提取节点名，也就是OCL对象属性名。图2就是OCL查询对象的转换过程。

图2 OCL查询对象的转换

OCL规则库存储于HDFS(Hadoop Distribute FileSystem)，我们需要对规则库所在的所有块进行并行遍历，筛选出满足条件的OCL对象属性，用其构造成OCL对象属性集合，具体的过程如算法1所描述。

算法1对象属性提取Extraction算法

输入: HDFS file path: ocl; OCL Attribute List : attributeList.

输出: OCL Attribute Set: attributeSet

1. blockList = procedure Locate(ocl)

2. /*定位ocl对应的所有block*/

3. for each block in blockList do:

4. /*对存储在本节点上的block进行处理*/

5. for each attribute in block do:

6. if attribute in attributeList then:

7. /*验证当前属性是否属于指定OCL属性*/

8. attributeSet = attributeSet ∪ {attribute}

9. /*将当前属性插入返回集合中*/

10. end if

11. end for

12. end for

上述Extraction算法中的时间复杂度为O(m×n)，其中m为blockList中的block的数量，n为block中attribute数量，Extraction算法的流程图如图3所示。

图3 Extraction算法流程图

一个车辆管理系统和其对象属性的XML描述如下所示：

……

This owner is registered

Lily

female

35

2016-12-12

C00005,C00001

……

……

其中第一个中间的部分是一个对象属性，在该片段中表示一个Owner(车主对象)。多个OCL对象属性组成了一个OCL约束规则库的整体，一个OCL规则库可以包括多类对象属性，具体情况根据实际需要所定。当然，实际上涉及的OCL规则库都比以上内容复杂得多。

利用图3的算法，可以从以上案例中提取Owner所有属性，如Owner=Extraction(″system.xml″，{″Owner″})，得到用于并行查询的OCL对象属性集合Owner，该数据集合Owner如下所示：

1.

2. This is redheaded/registered

3. Lily

4.

5. female

6. 35

7.

8.

9. C00001,C00005

10.

11.

12. 2016-12-12

13.

14.

15. This owner is yellowheaded/registered

16. hobby

17.

18. male

19. 20

20.

21.

22. C11111

23.

24.

25. 2016-12-18

26.

27. ……

2.3 OCL并行查询处理

OCL并行查询输入的数据实际上是OCL对象属性集合。由上一小节可知，Extraction算法根据标签对从OCL规则库中获得符合条件的OCL片段，并组合成了OCL对象属性集合。在完成预处理后，OCL并行查询剩下的工作就是对对象属性进行筛选并获取结果，需要依据实际的查询情况建立对应的MapReduce任务。在MapReduce任务中，Mapper或Reducer处理器处理的对象属性，是以流的形式传递进来的。在Map函数之后，还会有一个洗牌(shuffle)过程，之后才会进行相应的Reduce任务进行最终结果的构建。

整个OCL并行查询包括对象属性筛选和构造查询结果两部分。OCL查询会被处理器翻译成若干个MapReduce任务，每个MapReduce任务可以处理一个或多个查询条件，以此来筛选对象属性。最后，将筛选出来符合查询条件的对象属性进行结果构造，得到最终的结果。以查询年龄不小于25的Owner为例，该查询可以理解为这样一个简单MapReduce任务：Mapper处理器将传入进来的Owner进行筛选，如果当前处理的Owner对象年龄小于25就将其忽略掉，如果Owner年龄大于25就会被传递给Reducer处理器进行结果构造。图4所示的就是上述查询过程。

图4 查询流程

在上述的查询流程中，3个Mapper处理的Owner1-Owner6这6个对象，其中只有Owner1、Owner4、Owner5满足要求，所以只有它们将被传送到Reduce处理器进行构造最终结果。实际的OCL查询中涉及的查询要比图4所示内容复杂很多，OCL查询会被查询处理器转换成一组MapReduce任务，以此来筛选规则库，并将OCL规则库中符合查询要求的片段进行最终结果构造。

3 实验结果及分析

3.1 实验环境和数据

为验证本文方法，设计了一个实验平台。实验平台是由6台普通的PC机(Intel P4 2.8 GHz，双核处理器，内存2 GB，Ubuntu10.04)组成。该实验平台利用Hadoop开源框架对集群进行管理：1个节点当作Name-Node/JobTracker对整个集群进行管理，剩下的5个节点为DataNode/TaskTracker，对数据进行存储和处理。

实验数据使用的是车辆管理系统的OCL规则库(包含：用户数据、车辆数据、登录数据、加入用户的数据)转换成实验使用的XML描述文档。表1所示为数据集的具体信息。

表1 实验数据集

3.2 实验与分析

对于OCL 的查询，可以将其分成下面几类：1) 对象属性查询，如：查询年龄大于25的Owner；2) 对象属性操作查询，如查找Owner登录时需要满足哪些约束；3) 对象属性关系查询，这种类型的查询需要对两个对象属性之间的关系进行匹配，如：查询 1号Owner拥有的所有车，就需要多次进行多个OCL片段集间的比较才能完成。

下面，我们从三个方面来研究查询的效果。

3.2.1 查询时间随文档大小的变化情况

如图5所示，文档大小对查询时间的影响。

图5 查询时间与文件大小关系

根据图5显示，随着文档大小的增加，查询时间逐渐增长，但二者并不是成正比。这是由于选取OCL片段集时，只选取与查询条件相关的OCL片段，而不是选取原始规则库的全部内容。同时，OCL对象属性关系查询需要对两个对象属性之间的关系进行匹配，需要多次进行多个OCL片段集之间的比较才能完成，所以此类查询与对象属性查询、对象属性操作查询相比，需要更多的时间。基于MapReduce的OCL并行查询，同时利用了OCL片段集的方法，可以有效地减轻查询的负荷，与单机的OCL查询相比，查询效率显著提高。

3.2.2 查询时间随集群规模的变化情况

如图6所示，研究OCL规则库的对象属性查询、对象属性操作查询，分析集群规模对查询时间的影响。

图6 查询时间与集群规模的关系

如图所示，查询时间与集群规模成负相关，但是随着集群规模的增大，查询时间的减少幅度逐渐降低。这就需要我们在实际的查询中，将效率提高收益和硬件成本综合起来考虑，选择最佳的集群规模。数据集的大小为3.9 GB，同时将集群文件系统的Block设为64 MB，将处理节点的最大Mapper和Reducer数设为2。因为本实验所涉及的处理器为双核，所以设置为常数2可以充分地利用处理器的能力。

3.2.3 查询时间随集群配置的变化情况

图7表示查询时间与集群配置变化的关系，数据集的大小为5.1 GB。

图7 查询时间与集群配置的关系

如图7所示，查询时间随着HDFS中块(Block)的增大而逐渐减小。因为，当HDFS的块设置增大时，Hadoop集群需要用来处理OCL对象属性集合的Map和Reduce任务减少，进而使任务配置和中间结果的传输的时间缩短，所以整个查询时间会相应缩短。但是HDFS的块设置过大，OCL规则库相对过小，会造成集群内各节点负载不均衡，进而影响查询总效率。根据图7实验结果，将Block大小设置为64 MB或者128 MB时，处理器可以被充分利用，能够有效地减小查询时间，提高查询效率。

4 结 语

本实验将针对OCL规则库的查询转换成对象属性集合的查询，使用MapReduce模型处理集合中的每个对象属性，提高了对OCL查询的效率，缩短了查询时间。本文的OPQM方法充分利用了MapReduce框架，与传统的单机查询相比，无论是查询时间还是查询效率，都有很大的优势。后续将在本文的工作基础上，学习和研究云计算海量数据存储，针对更大规模的OCL规则库，更好地提高查询效率。