張正凡,都儀敏
(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院,云南 昆明 650500)
在過去的幾十年里,數(shù)據(jù)處理主要集中在傳統(tǒng)單機(jī)數(shù)據(jù)庫上。隨著大數(shù)據(jù)時(shí)代的到來,市場瞬息萬變,企業(yè)需要快速、有效地從歷史數(shù)據(jù)中獲得對(duì)市場變化的預(yù)測,或從歷史數(shù)據(jù)中獲得經(jīng)驗(yàn)進(jìn)行決策分析[1-2]。數(shù)據(jù)倉庫的出現(xiàn),為數(shù)據(jù)立方體的聯(lián)機(jī)分析處理(Online Analytical Processing,OLAP)提供了平臺(tái)[3-4]。但隨著歷史數(shù)據(jù)的積累,對(duì)數(shù)據(jù)立方體操作在時(shí)間、空間上存在巨大挑戰(zhàn)。因此,許多學(xué)者針對(duì)數(shù)據(jù)立方體壓縮技術(shù)相繼提出了不同的壓縮模型[5]。例如冰山立方體、封閉立方體、商立方體、濃縮立方體等,其中冰山立方體需要預(yù)先設(shè)定一個(gè)最小閾值,按照預(yù)先定義的約束條件對(duì)原始數(shù)據(jù)立方體進(jìn)行剪枝操作,只保留符合約束條件的方體;封閉立方體通過計(jì)算等價(jià)類,將由等價(jià)類上界構(gòu)成的集合進(jìn)行物化,舍棄其它所有單元,通過具有代表性的封閉單元響應(yīng)對(duì)原始數(shù)據(jù)立方體的查詢[6];濃縮立方體是相應(yīng)原始數(shù)據(jù)立方體的一個(gè)子集,對(duì)于原立方體中基于同一條基本單元組聚集而得、且具有相同聚集值的多個(gè)格,在濃縮立方體中僅存儲(chǔ)其中無*值的一個(gè)格,通過該剪枝方式減小數(shù)據(jù)文件體積[7];而商立方體在封閉立方體的基礎(chǔ)上保留了等價(jià)類的上下界,更好地保持了類似區(qū)間的模型[8]。同時(shí),由于商立方體保存了整個(gè)等價(jià)區(qū)間,可以保證區(qū)間內(nèi)所有數(shù)據(jù)單元都具有相同聚集值,因此商立方體對(duì)非單調(diào)聚集函數(shù)具有很強(qiáng)的支持性。在此基礎(chǔ)上,文獻(xiàn)[9]提出了一種分層封閉立方體查詢算法,通過增加層號(hào)限制查詢的中間結(jié)果從而提高效率。與此同時(shí),大數(shù)據(jù)技術(shù)的發(fā)展帶來了Hadoop、Spark等分布式系統(tǒng)[10-11],MapReduce編程模型也逐漸應(yīng)用廣泛[12],一些傳統(tǒng)算法可以通過MapReduce模型改造后在分布式系統(tǒng)上運(yùn)行。文獻(xiàn)[13]提出了一種基于QC-Tree的商立方體查詢算法,并在Hadoop集群中加以實(shí)現(xiàn),但在MapReduce模型中,尤其在shuffle過程中需要經(jīng)常對(duì)磁盤進(jìn)行I/O操作[14],因Spark具有基于內(nèi)存的特性,所以非常適用于需要迭代計(jì)算的大數(shù)據(jù)運(yùn)算[15],甚至有些程序在Spark中運(yùn)行速度比在Hadoop中快上百倍[16]。
目前針對(duì)在Spark集群上的商立方體研究較少,因此本文從商立方體基本概念出發(fā),提出一種基于Spark平臺(tái)的商立方體分布式查詢算法,該算法首先將商立方體進(jìn)行分片,然后將待查詢單元通過廣播形式發(fā)送到各Worker節(jié)點(diǎn),最后通過查詢函數(shù)對(duì)查詢單元進(jìn)行查詢操作。
設(shè)C是基本表r上計(jì)算得到的數(shù)據(jù)立方體,其數(shù)據(jù)單元c=(a1,a2, …,an:ma),其中,ai是維屬性值(可能為ALL),1≤I≤n,ma是度量值。當(dāng)維屬性值中存在k(0≤k≤n)個(gè)非ALL的值時(shí),則c是k維數(shù)據(jù)單元。給定數(shù)據(jù)單元u∈C,v∈C,u和v間具有如下關(guān)系:
定義1(元組覆蓋):u∈C,v∈C,對(duì)于?ai,1≤I≤n,如果滿足以下條件,則稱v覆蓋u或u被v覆蓋:①如果v(ai) ≠All,則u(ai)=v(ai);②如果v(ai)=All,則u(ai) =any。
例如:u(S1, *,R1: 18)覆蓋v(S1,T2,R1: 12),w(S1,T1,R1: 6)。
定義2(基本元組集):給定數(shù)據(jù)單元c∈C,c的基本元組集BTS(c)={t|t∈r且t≤c},即所有上卷到數(shù)據(jù)單元c的基本表元組集合,或單元c覆蓋的基本表元組集合。例如:BTS((S1,T1,R1∶6)) = {(S1,T1,R1∶6)},BTS((S1,*,R1∶18))={(S1,T2,R1∶12), (S1,T1,R1∶6)}。
定義3(等價(jià)關(guān)系≡):當(dāng)u,v滿足BTS(u) =BTS(v),則u和v等價(jià),記為u≡v。例如:現(xiàn)有元組(S1,*,R1∶18)和元組(S1, *, *∶18),并且BTS((S1,*,R1∶18))=BTS((S1,*,*∶18))={(S1,T2,R1∶12),(S1,T1,R1∶6)},則兩個(gè)元組等價(jià),標(biāo)記為(S1,*,*:18)((S1,*,*:18)。
定義4(等價(jià)類):基本元組集相等的元組集合。如給定數(shù)據(jù)單元u、v,若u≡v,則u、v屬于同一等價(jià)類。
定義5(等價(jià)類的上界):在等價(jià)類C中,對(duì)所有c∈C,B為c中的屬性值集合構(gòu)成的元組。若UP=(a1,a2,a3,...,an)是等價(jià)類C的上界,對(duì)于第i維屬性值ai必須滿足如下條件:①若{ai|ai(UP}=*,則{ai|ai∈B}可以為任意值;②若{ai|ai(UP}=s,則{ai|ai∈B}=s。
定義6(等價(jià)類下界):等價(jià)類中非ALL的維度值最多的數(shù)據(jù)單元集合。
定義7(等價(jià)區(qū)間):C為數(shù)據(jù)立方體所有等價(jià)類的集合,對(duì)于所有c∈C,q為c的上界,p為c的下界,則p與q組成一個(gè)等價(jià)區(qū)間,記作[q,p]。
定理1:落在等價(jià)區(qū)間內(nèi)的單元,其基本元組集相等。
證明:給定數(shù)據(jù)單元u,v,w∈C,設(shè)u≤w≤v,u≡v。首先由u≡w≡v,可以得到BTS(u)?BTS(w)?BTS(v),又u≡v,則BTS(u)=BTS(v),因此BTS(w)=BTS(u)=BTS(v),w≡u(píng)≡v,得證。
定理2:若u≡v,則對(duì)于任何聚集函數(shù),u和v的度量值必然相等。
證明:由u(v,得BTS(u)=BTS(v),既然兩者基本元組集相同,通過相同的聚集函數(shù)計(jì)算,聚集值即度量值,必然相等。
需要注意的是,若C存在兩個(gè)數(shù)據(jù)單元c1和c2,且兩者基本元組集相等,則度量值相等;但若度量值相等,基本元組集卻不一定相等。
例如:對(duì)于求平均的聚集函數(shù)avg,設(shè)u=(*,1,*),v=(*,1,1),且BTS(u)={(1,1,1:5),(2,1,2:5)},BTS(v)={(1,1,1:5)},在這種情況下,u>v,且u、v的度量值都是5,但基本元組集不相等。
通過上文對(duì)商立方體定義的描述,等價(jià)區(qū)間查詢匹配過程如圖1所示。
圖1 等價(jià)區(qū)間查詢匹配
設(shè)一個(gè)商立方等價(jià)區(qū)間,其中a1=(apple,KM,2016,S1:6)為下界,a2=(*,*,2016,*:6)為上界,若此時(shí)待查詢?cè)M為a3=(apple,*,2016,*),a2覆蓋a3覆蓋a1,且a1與a2的聚集值均為6。因此,根據(jù)定理1,可以得到待查詢單元a3的聚集值也為6,響應(yīng)查詢即可。
但是在實(shí)際查詢過程中,由于基本表數(shù)據(jù)巨大,生成的商立方體也會(huì)很大。為了省去不必要的覆蓋判斷,對(duì)商立方體進(jìn)行分層,將層數(shù)作為掃描操作的依據(jù),若待查詢單元落在某一商立方體上下界之間,則其層數(shù)也必在上下界層數(shù)之間。
基于以上原理,提出商立方體的分布式查詢算法(Distributed Quotient Cube Query Algorithm):
輸入:quotientCube (等價(jià)區(qū)間的集合)
queryArray (帶查詢?cè)M集)
輸出:equivalentRegion (匹配到的等價(jià)區(qū)間)
load base table from hdfs
loading mapping data
DFS processing to generate quotient_cube
generate queryArray randomly
broadcast(queryArray);
sc.parallelize(3).mapPartitions(partRDD => {
for i = 0 to test_query_cells.size
for j = 0 to quotientCube.size
if( quotientCube[j] includes queryArray[i])
Cache hit; break;
end if
end for
end for})
在程序執(zhí)行前,預(yù)先將基本表存儲(chǔ)在HDFS文件系統(tǒng)中。在本例中采用HDFS的默認(rèn)分區(qū)策略。數(shù)據(jù)在文件系統(tǒng)中以block形式存放,大小默認(rèn)為128M,每個(gè)block對(duì)應(yīng)一個(gè)RDD分區(qū)。Spark執(zhí)行時(shí),創(chuàng)建SparkContext對(duì)象,對(duì)象為程序入口,同時(shí)讀取配置文件信息,并以該配置運(yùn)行整個(gè)Spark程序。
首先從HDFS中加載基本表,以及映射關(guān)系表,通過一系列轉(zhuǎn)化操作,將基本表中字符串根據(jù)映射關(guān)系轉(zhuǎn)化成數(shù)字類型的RDD,然后通過DFS算法生成商立方體quotientCube,并生成用以測試的待查詢單元queryArray。然后對(duì)待查詢單元賦值給一個(gè)廣播變量,廣播變量通過廣播的形式將本地RDD復(fù)制到遠(yuǎn)程節(jié)點(diǎn)上以待查詢。最后根據(jù)覆蓋關(guān)系,若帶查詢?cè)M能被某一等價(jià)區(qū)間覆蓋,則直接響應(yīng)查詢,并開始下一元組的查詢,若不能覆蓋,則直接開始下一輪查詢。
本實(shí)驗(yàn)以Scala語言編寫,Scala版本號(hào)為2.10.4,操作系統(tǒng)為Ubuntu 16.04(X86_64),Hadoop 版本為Hadoop-2.6.0,Spark 版本為Spark-1.6.1 -bin- hadoop- 2.6,JDK 版本為jdk 1.8.0_151。
Spark集群環(huán)境的計(jì)算機(jī)有3臺(tái),主要配置見表1。
表1 實(shí)驗(yàn)環(huán)境配置
本實(shí)驗(yàn)將Spark環(huán)境下商立方體分布式查詢與單機(jī)環(huán)境下的商立方體查詢進(jìn)行對(duì)比,測試本文提出的分布式商立方體查詢算法(DQCQ算法)性能。測試數(shù)據(jù)采用Food Mart數(shù)據(jù)集。實(shí)驗(yàn)結(jié)果如圖2所示。
圖2 Spark環(huán)境與單機(jī)環(huán)境對(duì)比
在實(shí)驗(yàn)中,每隔2萬次輸出程序運(yùn)行時(shí)間。由圖2可以看出,在查詢次數(shù)相同的情況下,并行情況下的查詢性能幾乎是單機(jī)條件下的兩倍。因?yàn)檫\(yùn)行分布式系統(tǒng)占用一定性能,且存在分區(qū)、廣播等同步操作,雖然集群有3個(gè)節(jié)點(diǎn),但是查詢速度無法達(dá)到單機(jī)的3倍。
在第二次實(shí)驗(yàn)中,將集群節(jié)點(diǎn)數(shù)作為參數(shù),通過改變集群節(jié)點(diǎn)數(shù)量測試算法性能。實(shí)驗(yàn)結(jié)果如圖3所示。
圖3 節(jié)點(diǎn)數(shù)對(duì)查詢速度的影響
在本實(shí)驗(yàn)中,將查詢次數(shù)限定在10萬次,從1個(gè)節(jié)點(diǎn)增加到5個(gè)節(jié)點(diǎn)。通過實(shí)驗(yàn)結(jié)果可以得出,隨著集群節(jié)點(diǎn)增加,查詢時(shí)間越來越少,因?yàn)楣?jié)點(diǎn)變多,進(jìn)行查詢的單元隨之增加,所以在總數(shù)不變的情況下,查詢時(shí)間變少。
綜上所述,在實(shí)際應(yīng)用場景中,本文提出的DQCQ算法查詢性能較好,且隨著集群規(guī)模的擴(kuò)大,算法性能隨之?dāng)U大。實(shí)驗(yàn)結(jié)果與理論預(yù)期一致。
本文基于商立方體的基本結(jié)構(gòu),提出了一種商立方體分布式查詢的優(yōu)化算法,并在Spark環(huán)境下實(shí)現(xiàn)。通過對(duì)比實(shí)驗(yàn)可以看出,在Spark環(huán)境下商立方體的分布式查詢具有一定的可行性和較高的效率。
本文對(duì)數(shù)據(jù)集進(jìn)行隨機(jī)劃分,但考慮到節(jié)點(diǎn)間的負(fù)載均衡,建設(shè)采用邊劃分或點(diǎn)劃分進(jìn)行數(shù)據(jù)集劃分,確保集群中某些節(jié)點(diǎn)不會(huì)過度負(fù)載而降低算法性能;本文提出的算法需要等待商立方體全部物化后才能開始查詢,由于初始化需要等待,可以考慮動(dòng)態(tài)查詢商立方體,通過邊查詢邊物化完善商立方體。