金仙力 馬凱旋

(南京郵電大學計算機軟件學院 江蘇 南京 210003)

0 引 言

近年來，計算機應(yīng)用發(fā)展迅速，社交網(wǎng)絡(luò)、電子商務(wù)、數(shù)字城市等許多應(yīng)用領(lǐng)域中產(chǎn)生了規(guī)模巨大的數(shù)據(jù)，這些應(yīng)用數(shù)據(jù)不僅存儲量大，而且增長速度也非常迅猛[1]。為了解決上述問題，Google公司在2006年提出了“云計算”的概念。美國國家標準與技術(shù)研究院(NIST)將云計算定義為借助互聯(lián)網(wǎng)實現(xiàn)按需、隨地、便捷地訪問共享資源池的計算模式。云計算是信息產(chǎn)業(yè)的一大創(chuàng)新模式，一經(jīng)提出就獲得了各個領(lǐng)域的廣泛關(guān)注。

OCL以約束的形式描述類的屬性或方法，可以準確地約束行為，廣泛地應(yīng)用于模型約束中。隨著信息技術(shù)地發(fā)展，OCL約束變得越來越復雜，OCL規(guī)則庫也相應(yīng)地變得越來越大。OCL查詢功能在處理少量的數(shù)據(jù)時是高效的，但是在處理大量的數(shù)據(jù)時，不能在有效的時間內(nèi)得出最終的結(jié)果。所以，如何處理大規(guī)模數(shù)據(jù)下的OCL查詢是迫切需要解決的問題。Google 提出的MapReduce并行編程框架，在處理大規(guī)模數(shù)據(jù)問題上具有顯著的優(yōu)勢，能夠滿足人們對數(shù)據(jù)處理的需要。

因此，為了提高OCL查詢的速度，本文提出來一種基于MapReduce的OCL并行查詢方法OPQM(OCL Parallel Query Method)。主要內(nèi)容：使用MapReduce等并行編程框架來簡化數(shù)據(jù)的處理模型，通過提取OCL對象屬性集合，實現(xiàn)從OCL規(guī)則庫查詢到OCL對象屬性查詢的查詢轉(zhuǎn)化，并利用MapReduce實現(xiàn)對象屬性并行查詢。

1 相關(guān)工作

對象約束語言O(shè)CL是在UML中特別用來對約束和規(guī)則進行說明的語言[2]。盡管OCL語言是一種形式化語言，但是具有易讀、易寫等特點。它主要有兩個作用：一是對模型進行語義約束；二是對模型的查詢。OCL用于查詢時，主要是用于根據(jù)對象屬性查詢滿足約束條件的對象，并且在查詢時可以對圖中的任何元素寫表達式。其中，對象屬性是指與模型中對象有關(guān)的特征。由上述內(nèi)容可得知，對于OCL的約束查詢也就相當于對約束中所包含的OCL對象屬性集合的查詢。

隨著OCL規(guī)則庫的增大，傳統(tǒng)的查詢處理方式需要花費大量的時間匹配所有的對象屬性與查詢條件。因此，為了提高海量OCL約束查詢的效率，需要一種方法來提高OCL約束的查詢速度，減少整個查詢的時間。OCL規(guī)則庫可以遵循XML標準進行描述[3]，參考XML文檔查詢的優(yōu)化，可以對OCL規(guī)則庫進行查詢優(yōu)化。

目前，有很多關(guān)于XML海量數(shù)據(jù)的分布式處理的研究，黃玉龍等[4]借助關(guān)系數(shù)組等設(shè)計了處理的XPath查詢算法GRAXQ。在并行查詢階段,依次執(zhí)行每個定位步且標記返回結(jié)果，極大減少了查詢過程中的消重代價。

閆威等[5]提出了MapReduce編程模型下多謂詞選擇的查詢處理方法。包括海量XML數(shù)據(jù)的存儲方法、MapReduce編程模型下基于多謂詞選擇的Map邏輯算法和Reduce邏輯算法、基于多謂詞選擇的MapReduce查詢優(yōu)化方法，提高了系統(tǒng)的性能。

何志學等[6]提出TwigMRR算法對XML Twig查詢進行分布式處理。先對XML數(shù)據(jù)進行Dewey編碼，水平切分后存儲于分布式文件系統(tǒng)，再進行并行查詢。

李東等[7]為了實現(xiàn)基于MapReduce的XML查詢處理,首先實現(xiàn)了區(qū)間編碼、前綴編碼、層次編碼3種不同的XML數(shù)據(jù)編碼方式,以此為基礎(chǔ)來研究基于MapReduce的XML結(jié)構(gòu)連接處理。同時，建立了代價模型,通過代價估算獲得優(yōu)化的查詢計劃樹。

Fan等[8]提出了一種基于MapReduce的高效的分布式XPath查詢處理。他們使用虛擬節(jié)點將大規(guī)模XML數(shù)據(jù)文件拆分成文件片段，分配到分布式存儲系統(tǒng)。此外，為了有效地處理大型的XML數(shù)據(jù)，他們構(gòu)建分區(qū)索引并使用隨機訪問機制來執(zhí)行查詢。

Damigos等[9]提出了一種整合大量XML數(shù)據(jù)的技術(shù)，并使用MapReduce框架來有效地查詢集成數(shù)據(jù)。為了實現(xiàn)這個功能，他們提出了一個單步的MapReduce算法，該算法利用虛擬結(jié)構(gòu)，并以分布的方式有效地計算給定XPath查詢的答案。

Choi等[10]為大規(guī)模XML數(shù)據(jù)設(shè)計了并行樹標簽算法。他們提出基于MapReduce框架的兩個突出的樹標簽方案的并行版本。他們利用工作負載平衡和數(shù)據(jù)重新分區(qū)的技術(shù)，解決由于運行時數(shù)據(jù)偏斜和MapReduce的繼承限制而導致的性能問題。

Khatchadourian等[11]提出目前ChuQL的實現(xiàn)利用現(xiàn)有的主存儲器XQuery處理器并面臨兩個挑戰(zhàn)：中間XML值增長大于內(nèi)存、大量的輸出文件。為此他們描述了兩個ChuQL構(gòu)造來克服這些限制，分別是使用迭代器來處理XML值序列和分割作業(yè)輸出。

Bi等[12]提出了一種基于大規(guī)模XML文檔的分布式學習解決方案，它基于MapReduce技術(shù)將XML文檔分布式轉(zhuǎn)換為表示模型，并采用基于極限學習機的分布式學習組件進行分類或聚類任務(wù)。

Song等[13]集成了數(shù)據(jù)存儲，標簽，索引和并行查詢，以處理大量的XML數(shù)據(jù)。具體來說，引入了SDN標簽算法和使用DHT的分布式分層索引。

Bidoit等[14]提出一個處理大型XML文檔的查詢和更新的研究原型。該原型基于靜態(tài)和動態(tài)分割輸入文檔的想法，以便在Map / Reduce集群的機器之間分配計算負載?？梢赃\行預定義的查詢和更新符合XMark模式的文檔，以及提交自己的查詢和更新。

Consens等[15]描述了ChuQL，一個MapReduce擴展到XQuery，以及相應(yīng)的Hadoop實現(xiàn)。ChuQL語言結(jié)合了記錄來支持MapReduce的鍵/值數(shù)據(jù)模型，并且利用高階函數(shù)提供語義。

XML已經(jīng)是網(wǎng)絡(luò)信息描述和交換的標準，隨著越來越廣泛的XML應(yīng)用，關(guān)于XML數(shù)據(jù)的查詢方法也越來越多。但是，很多XML數(shù)據(jù)查詢方法都存在相應(yīng)的局限性。

由此可知，OCL規(guī)則庫可以遵循XML標準進行描述，參考XML文檔查詢的優(yōu)化，可以對OCL規(guī)則庫進行查詢優(yōu)化。但是與XML文檔相比，OCL規(guī)則庫中的對象屬性所包含了許多豐富的信息，我們需要對這部分屬性進行相應(yīng)的處理。本文中我們采用預處理的方式，對涉及的所有OCL對象屬性進行提取，并使用并行模型來解析匹配這些屬性。

2 基于對象屬性的OCL并行查詢

2.1 MapReduce并行處理模型

MapReduce是谷歌首先提出的一種在大型計算機集群上處理大數(shù)據(jù)的并行計算模型，在谷歌以及其他公司的許多項目中得到了廣泛應(yīng)用。它是數(shù)據(jù)密集型的并行計算模型，即特別適合于處理大規(guī)模海量數(shù)據(jù)。MapReduce既是一種并行計算模型，又是一種并行計算框架。

MapReduce計算模式是云計算的核心計算模式，解決大規(guī)模數(shù)據(jù)的處理問題。它在設(shè)計之初，就將局部性原理納入考慮的范疇，通過利用局部性原理實現(xiàn)問題的分而治之。Map 調(diào)用能夠被分布到多個節(jié)點執(zhí)行，是通過將輸入數(shù)據(jù)分割為若干個數(shù)據(jù)片段的集合實現(xiàn)的，不同的節(jié)點能夠同時并行處理輸入的數(shù)據(jù)片段，同時Reduce 調(diào)用也會被分布到多個節(jié)點上并行執(zhí)行。Map 調(diào)用產(chǎn)生的中間 key 值會被分區(qū)函數(shù)分成N個分區(qū)，其中的分區(qū)函數(shù)、分區(qū)個數(shù)(N)由用戶決定。MapReduce流程的三個階段如圖1所示。

圖1 MapReduce的操作流程圖

(1) Map階段 由于 Map 是并行操作數(shù)據(jù)集，所以用戶程序首先會調(diào)用的MapReduce庫，對輸入的數(shù)據(jù)集進行操作，將數(shù)據(jù)集分割成一些數(shù)據(jù)片段如上圖的數(shù)據(jù)塊。在數(shù)據(jù)分割完以后，會形成多個分割體，為了保證處理的效率，分割體會被分配到不同的Map處理器上進行并行處理。Hadoop 中的類 Input Format，從輸入數(shù)據(jù)中解析出鍵值 (key/value)對。接下來，Map函數(shù)接收傳入的鍵值(key/value)，并對其進行處理，產(chǎn)生中間的鍵值 (key/value)對，并將這些中間數(shù)據(jù)緩存到內(nèi)存中。同時，為了提高Reduce的處理效率以及增加集群內(nèi)部數(shù)據(jù)的傳輸速度，在Map函數(shù)之后設(shè)置了一個洗牌(shuffle)過程。

(2) 中間階段 中間階段的實現(xiàn)主要是由Hadoop 框架提供的一個合成器(Combine)來完成。中心控制作業(yè) Job Tracker 會選取節(jié)點來進行 Map 運算，產(chǎn)生鍵值(key/value)對。同時，綜合考慮性能和效率因素，這些鍵值(key/value)將被收集到一些 List 數(shù)據(jù)集中，而不會立即寫入輸出文件。

(3) Reduce 階段 這個過程由復制、排序、 reduce 任務(wù)這3個步驟組成。在集群模式下，首先，服務(wù)器上的中間階段數(shù)據(jù)會周期性地復制到本地文件系統(tǒng)上。復制完數(shù)據(jù)之后，Reduce 任務(wù)會對這些中間階段的數(shù)據(jù)進行排序，將具有相同的數(shù)據(jù)進行整理并合并到一個文件中。最后一步由 Reduce 函數(shù)完成，將鍵(key)所對應(yīng)的值(values)傳給 Reduce 函數(shù)產(chǎn)生最后的結(jié)果。

將MapReduce并行模型和OCL規(guī)則庫的存儲結(jié)構(gòu)綜合起來，MapReduce中的最小處理單元即是OCL規(guī)則庫中的一個對象屬性。在處理過程中，節(jié)點根據(jù)實際的查詢，匹配并篩選OCL對象屬性，得到滿足條件的對象屬性集合，并對其進行構(gòu)造得到最終的查詢結(jié)果。

2.2 對象屬性集提取Extraction算法

并行處理模型面對的處理對象必須可以拆分，也就是說這些處理對象能夠被分成若干個子對象，這樣才能被不同的處理器并行處理。MapReduce模型和上述的工作原理一致，它是把一個大的數(shù)據(jù)分割成多個獨立的片斷(Splits)。

為了讓OCL規(guī)則庫可以有效地在云計算的環(huán)境下進行并行查詢，就需要對OCL規(guī)則庫進行預處理，即對OCL規(guī)則庫提取對象屬性，并由此組成OCL對象屬性集合，用集合來替代原來的OCL規(guī)則庫作為云計算并行模型中的輸入數(shù)據(jù)。

在MapReduce并行模型中，這些對象屬性集合就會被分割成多個獨立的Splits，然后若干個Splits將被分配到不同的Map處理器上進行處理，每個Splits經(jīng)過Map函數(shù)處理之后，還會有一個洗牌(shuffle)過程,之后才進行相應(yīng)的Reduce任務(wù)。

我們使用的預處理方法是基于Hadoop的InputFormat，根據(jù)查詢條件，篩選出OCL規(guī)則庫中滿足條件的對象屬性片段并構(gòu)造OCL對象屬性集合。

使用算法Extraction(fileName，nodeName)提取對象屬性，其中fileName是OCL原始規(guī)則庫名(該規(guī)則庫是預先存儲在HDFS 中的)，nodeName是提取節(jié)點名，也就是OCL對象屬性名。圖2就是OCL查詢對象的轉(zhuǎn)換過程。

圖2 OCL查詢對象的轉(zhuǎn)換

OCL規(guī)則庫存儲于HDFS(Hadoop Distribute FileSystem)，我們需要對規(guī)則庫所在的所有塊進行并行遍歷，篩選出滿足條件的OCL對象屬性，用其構(gòu)造成OCL對象屬性集合，具體的過程如算法1所描述。

算法1對象屬性提取Extraction算法

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

輸出: OCL Attribute Set: attributeSet

1. blockList = procedure Locate(ocl)

2. /*定位ocl對應(yīng)的所有block*/

3. for each block in blockList do:

4. /*對存儲在本節(jié)點上的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的數(shù)量，n為block中attribute數(shù)量，Extraction算法的流程圖如圖3所示。

圖3 Extraction算法流程圖

一個車輛管理系統(tǒng)和其對象屬性的XML描述如下所示：

……

This owner is registered

Lily

female

35

2016-12-12

C00005,C00001

……

……

其中第一個中間的部分是一個對象屬性，在該片段中表示一個Owner(車主對象)。多個OCL對象屬性組成了一個OCL約束規(guī)則庫的整體，一個OCL規(guī)則庫可以包括多類對象屬性，具體情況根據(jù)實際需要所定。當然，實際上涉及的OCL規(guī)則庫都比以上內(nèi)容復雜得多。

利用圖3的算法，可以從以上案例中提取Owner所有屬性，如Owner=Extraction(″system.xml″，{″Owner″})，得到用于并行查詢的OCL對象屬性集合Owner，該數(shù)據(jù)集合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并行查詢輸入的數(shù)據(jù)實際上是OCL對象屬性集合。由上一小節(jié)可知，Extraction算法根據(jù)標簽對從OCL規(guī)則庫中獲得符合條件的OCL片段，并組合成了OCL對象屬性集合。在完成預處理后，OCL并行查詢剩下的工作就是對對象屬性進行篩選并獲取結(jié)果，需要依據(jù)實際的查詢情況建立對應(yīng)的MapReduce任務(wù)。在MapReduce任務(wù)中，Mapper或Reducer處理器處理的對象屬性，是以流的形式傳遞進來的。在Map函數(shù)之后，還會有一個洗牌(shuffle)過程，之后才會進行相應(yīng)的Reduce任務(wù)進行最終結(jié)果的構(gòu)建。

整個OCL并行查詢包括對象屬性篩選和構(gòu)造查詢結(jié)果兩部分。OCL查詢會被處理器翻譯成若干個MapReduce任務(wù)，每個MapReduce任務(wù)可以處理一個或多個查詢條件，以此來篩選對象屬性。最后，將篩選出來符合查詢條件的對象屬性進行結(jié)果構(gòu)造，得到最終的結(jié)果。以查詢年齡不小于25的Owner為例，該查詢可以理解為這樣一個簡單MapReduce任務(wù)：Mapper處理器將傳入進來的Owner進行篩選，如果當前處理的Owner對象年齡小于25就將其忽略掉，如果Owner年齡大于25就會被傳遞給Reducer處理器進行結(jié)果構(gòu)造。圖4所示的就是上述查詢過程。

圖4 查詢流程

在上述的查詢流程中，3個Mapper處理的Owner1-Owner6這6個對象，其中只有Owner1、Owner4、Owner5滿足要求，所以只有它們將被傳送到Reduce處理器進行構(gòu)造最終結(jié)果。實際的OCL查詢中涉及的查詢要比圖4所示內(nèi)容復雜很多，OCL查詢會被查詢處理器轉(zhuǎn)換成一組MapReduce任務(wù)，以此來篩選規(guī)則庫，并將OCL規(guī)則庫中符合查詢要求的片段進行最終結(jié)果構(gòu)造。

3 實驗結(jié)果及分析

3.1 實驗環(huán)境和數(shù)據(jù)

為驗證本文方法，設(shè)計了一個實驗平臺。實驗平臺是由6臺普通的PC機(Intel P4 2.8 GHz，雙核處理器，內(nèi)存2 GB，Ubuntu10.04)組成。該實驗平臺利用Hadoop開源框架對集群進行管理：1個節(jié)點當作Name-Node/JobTracker對整個集群進行管理，剩下的5個節(jié)點為DataNode/TaskTracker，對數(shù)據(jù)進行存儲和處理。

實驗數(shù)據(jù)使用的是車輛管理系統(tǒng)的OCL規(guī)則庫(包含：用戶數(shù)據(jù)、車輛數(shù)據(jù)、登錄數(shù)據(jù)、加入用戶的數(shù)據(jù))轉(zhuǎn)換成實驗使用的XML描述文檔。表1所示為數(shù)據(jù)集的具體信息。

表1 實驗數(shù)據(jù)集

3.2 實驗與分析

對于OCL 的查詢，可以將其分成下面幾類：1) 對象屬性查詢，如：查詢年齡大于25的Owner；2) 對象屬性操作查詢，如查找Owner登錄時需要滿足哪些約束；3) 對象屬性關(guān)系查詢，這種類型的查詢需要對兩個對象屬性之間的關(guān)系進行匹配，如：查詢 1號Owner擁有的所有車，就需要多次進行多個OCL片段集間的比較才能完成。

下面，我們從三個方面來研究查詢的效果。

3.2.1 查詢時間隨文檔大小的變化情況

如圖5所示，文檔大小對查詢時間的影響。

圖5 查詢時間與文件大小關(guān)系

根據(jù)圖5顯示，隨著文檔大小的增加，查詢時間逐漸增長，但二者并不是成正比。這是由于選取OCL片段集時，只選取與查詢條件相關(guān)的OCL片段，而不是選取原始規(guī)則庫的全部內(nèi)容。同時，OCL對象屬性關(guān)系查詢需要對兩個對象屬性之間的關(guān)系進行匹配，需要多次進行多個OCL片段集之間的比較才能完成，所以此類查詢與對象屬性查詢、對象屬性操作查詢相比，需要更多的時間。基于MapReduce的OCL并行查詢，同時利用了OCL片段集的方法，可以有效地減輕查詢的負荷，與單機的OCL查詢相比，查詢效率顯著提高。

3.2.2 查詢時間隨集群規(guī)模的變化情況

如圖6所示，研究OCL規(guī)則庫的對象屬性查詢、對象屬性操作查詢，分析集群規(guī)模對查詢時間的影響。

圖6 查詢時間與集群規(guī)模的關(guān)系

如圖所示，查詢時間與集群規(guī)模成負相關(guān)，但是隨著集群規(guī)模的增大，查詢時間的減少幅度逐漸降低。這就需要我們在實際的查詢中，將效率提高收益和硬件成本綜合起來考慮，選擇最佳的集群規(guī)模。數(shù)據(jù)集的大小為3.9 GB，同時將集群文件系統(tǒng)的Block設(shè)為64 MB，將處理節(jié)點的最大Mapper和Reducer數(shù)設(shè)為2。因為本實驗所涉及的處理器為雙核，所以設(shè)置為常數(shù)2可以充分地利用處理器的能力。

3.2.3 查詢時間隨集群配置的變化情況

圖7表示查詢時間與集群配置變化的關(guān)系，數(shù)據(jù)集的大小為5.1 GB。

圖7 查詢時間與集群配置的關(guān)系

如圖7所示，查詢時間隨著HDFS中塊(Block)的增大而逐漸減小。因為，當HDFS的塊設(shè)置增大時，Hadoop集群需要用來處理OCL對象屬性集合的Map和Reduce任務(wù)減少，進而使任務(wù)配置和中間結(jié)果的傳輸?shù)臅r間縮短，所以整個查詢時間會相應(yīng)縮短。但是HDFS的塊設(shè)置過大，OCL規(guī)則庫相對過小，會造成集群內(nèi)各節(jié)點負載不均衡，進而影響查詢總效率。根據(jù)圖7實驗結(jié)果，將Block大小設(shè)置為64 MB或者128 MB時，處理器可以被充分利用，能夠有效地減小查詢時間，提高查詢效率。

4 結(jié) 語

本實驗將針對OCL規(guī)則庫的查詢轉(zhuǎn)換成對象屬性集合的查詢，使用MapReduce模型處理集合中的每個對象屬性，提高了對OCL查詢的效率，縮短了查詢時間。本文的OPQM方法充分利用了MapReduce框架，與傳統(tǒng)的單機查詢相比，無論是查詢時間還是查詢效率，都有很大的優(yōu)勢。后續(xù)將在本文的工作基礎(chǔ)上，學習和研究云計算海量數(shù)據(jù)存儲，針對更大規(guī)模的OCL規(guī)則庫，更好地提高查詢效率。