構(gòu)建高維度數(shù)據(jù)立方體的有向圖方法

張 巖, 呂夢儒(沈陽師范大學 計算機與數(shù)學基礎(chǔ)教學部, 沈陽 110034)

0 引 言

大規(guī)模數(shù)據(jù)的實時分析處理是Hadoop平臺生態(tài)圈進行不斷改進和擴展的根本要求。數(shù)據(jù)倉庫的OLAP(On-Line Analytical Processing,聯(lián)機數(shù)據(jù)分析)提升響應性能主要方法是立方體數(shù)據(jù)的預聚集,也就是在數(shù)據(jù)的在線分析之前,對立方體中的細粒度數(shù)據(jù)進行預先的聚合計算,并進行預存儲,在發(fā)生OLAP時直接調(diào)用預計算的結(jié)果,節(jié)省數(shù)據(jù)掃描和計算的時間,降低時間代價[1]。很多關(guān)于預聚集的計算和存儲的研究都是針對度量的選擇、投影和連接等算法的改進以及存儲效率的提高等方面。采用的主要技術(shù)是利用Hadoop框架,從Hive中讀取源數(shù)據(jù),使用 MapReduce作為Cube構(gòu)建的引擎,并把預計算的結(jié)果保存在HBase中,對外開放Rest API/JDBC/ODBC的查詢接口[2]。隨著Spark等框架技術(shù)的發(fā)展,在內(nèi)存中完成預計算和利用基于內(nèi)存的RDD(Resilient Distributed Datasets,彈性分布式數(shù)據(jù)集)存儲和計算數(shù)據(jù)可以實現(xiàn)OLAP的實時分析或者準實時分析[3]。為了實現(xiàn)這個目標,就要對數(shù)據(jù)立方體構(gòu)建進行優(yōu)化。維度是數(shù)據(jù)立方體規(guī)模的決定因素,所以數(shù)據(jù)立方體的高維度優(yōu)化是數(shù)據(jù)立方體優(yōu)化的關(guān)鍵。

1 大規(guī)模數(shù)據(jù)的高維度數(shù)據(jù)立方體

1.1 有向圖描述的高維度數(shù)據(jù)立方體

數(shù)據(jù)立方體是多維數(shù)據(jù)的模型抽象。在大規(guī)模數(shù)據(jù)環(huán)境中,數(shù)據(jù)立方體呈現(xiàn)出高維度所導致的數(shù)據(jù)膨脹的特點[4]。由于超過四維的模型是人腦很難想象和描繪的,所以高維度的數(shù)據(jù)立方體可以用多維分析的維度組合的集合來進行描述。構(gòu)建高維度數(shù)據(jù)立方體可以抽象為有向圖的建立,其中的每個結(jié)點對應多維分析的一個維度或者維度組合,每個結(jié)點的度表示多維分析的維度數(shù)量。構(gòu)建包含地區(qū)(Region)、時間(Time)、產(chǎn)品(Goods)和供應商(Supplier)4個維度的數(shù)據(jù)立方體如圖1所示。為了數(shù)據(jù)立方體的簡潔化,將地區(qū)、時間、產(chǎn)品和供應商表示為R、T、G和S。

圖1 四維度數(shù)據(jù)立方體cube的構(gòu)建Fig.1 Construction of four dimension data cube

有向圖可以清楚地描述數(shù)據(jù)立方體cube的構(gòu)建過程。從圖1中可以看出,構(gòu)建數(shù)據(jù)立方體cube的過程包括確定數(shù)據(jù)維、構(gòu)建數(shù)據(jù)切片、構(gòu)建數(shù)據(jù)切塊等3個環(huán)節(jié)。圖1中一維的結(jié)點是數(shù)據(jù)維,二維的結(jié)點是數(shù)據(jù)切片,三維的結(jié)點和四維的結(jié)點是數(shù)據(jù)切塊。

1.2 高維度對數(shù)據(jù)立方體規(guī)模的影響

圖1中數(shù)據(jù)切片和數(shù)據(jù)切塊有多個,每一個數(shù)據(jù)片或數(shù)據(jù)塊都是維度表和事實表的連接計算[5]。可以推斷,如果維度數(shù)每增加一個,則數(shù)據(jù)切片量和數(shù)據(jù)切塊量會增加至n2量級。從圖1中也可以看出,構(gòu)建數(shù)據(jù)切塊的路徑存在多條。對于規(guī)模比較小的數(shù)據(jù),增加的存儲空間和計算代價可以應對,但是大規(guī)模數(shù)據(jù)情況下,特別是對于準實時響應有要求的數(shù)據(jù)分析等,這些代價將嚴重影響系統(tǒng)的性能,甚至是造成整個系統(tǒng)的崩潰。所以對數(shù)據(jù)立方體cube構(gòu)建的各個數(shù)據(jù)切片和數(shù)據(jù)快要進行合理性的檢驗處理,對構(gòu)建cube的Hadoop平臺進行I/O性能測試和統(tǒng)計排序等基準測試[6],從而提高構(gòu)建數(shù)據(jù)立方體cube的效率。

圖1中描述的構(gòu)建數(shù)據(jù)立方體的有向圖方法是個漸進式的動態(tài)過程。在這個漸進式過程中,二維數(shù)據(jù)切片、三維數(shù)據(jù)切塊和四維數(shù)據(jù)切塊是依各個層次建立的。與傳統(tǒng)的數(shù)據(jù)立方體的構(gòu)建方法和過程是有本質(zhì)區(qū)別的,可以控制高維數(shù)據(jù)立方體的膨脹。

2 高維度數(shù)據(jù)立方體的維度

2.1 數(shù)據(jù)立方體的概念

數(shù)據(jù)立方體是一個多維或者高維的數(shù)據(jù)模型的抽象。在大數(shù)據(jù)規(guī)模下,數(shù)據(jù)立方體更多地表現(xiàn)出隨時性、分散性和動態(tài)性。以集合的理論,數(shù)據(jù)立方體是數(shù)據(jù)維、數(shù)據(jù)片和數(shù)據(jù)塊所構(gòu)成的集合。數(shù)據(jù)立方體的操作可以通過集合運算來完成。集合操作的線性化特點便于數(shù)據(jù)的收縮和擴展,分散數(shù)據(jù)的各個元素,數(shù)據(jù)可以隨時以一個元素的形式進行訪問和更新[7]。

數(shù)據(jù)維是構(gòu)成數(shù)據(jù)片和數(shù)據(jù)塊的基本元素,包括維度和度量數(shù)據(jù),表示為Di,數(shù)據(jù)維的集合表示為D(Di)。

數(shù)據(jù)片是由2個數(shù)據(jù)維直接構(gòu)成的,包括2個維度和所包含的度量數(shù)據(jù),表示為(Di,Dj),數(shù)據(jù)片的集合表示為P((Di,Dj))。

數(shù)據(jù)塊是由n個數(shù)據(jù)維(n≥3)構(gòu)成的,包括n個維度和所包含的度量數(shù)據(jù),表示為(D1,D2,…,Dn),數(shù)據(jù)塊的集合表示為B((D1,D2,…,Dn))。

基于以上描述,則數(shù)據(jù)立方體表示為C(D,P,B)。

2.2 數(shù)據(jù)立方體的規(guī)模及相關(guān)維度概念

從數(shù)據(jù)立方體的有向圖描述和數(shù)據(jù)立方體的集合概念來看,數(shù)據(jù)立方體的規(guī)模是由維度的規(guī)模決定,大數(shù)據(jù)的高維度將使數(shù)據(jù)立方體的規(guī)模增大甚至是膨脹,這樣將降低數(shù)據(jù)分析的效率。但是,在實際問題的數(shù)據(jù)分析過程中,有的維度在所有維度的組合中都是必須的,有些維度是在維度組合中必須同時出現(xiàn)的,而有的維度在所有維度的組合中都不是必須的[2]。所以,根據(jù)維度的利用頻度和利用方式,提出以下相關(guān)維度的概念。

圖2 降維簡化后的cubeFig.2 Cube after dimension predigested

假設(shè)一個包含地區(qū)(Region)、時間(Time)、產(chǎn)品(Goods)、供應商(Supplier)和制造商(Made)等5個維度的數(shù)據(jù)立方體,結(jié)合實際數(shù)據(jù)分析,對數(shù)據(jù)立方體的全描述有向圖進行了維度的預降維處理,如圖2所示。

可無維度表示的是在實際數(shù)據(jù)分析時,不出現(xiàn)在任何數(shù)據(jù)片維度組合中的維度。如圖2中的M結(jié)點。制造商M和地區(qū)R、時間T、產(chǎn)品G、供應商S不同,它沒有在數(shù)據(jù)分析中被使用。

必須維度表示的是在實際數(shù)據(jù)分析時,在所有的數(shù)據(jù)片維度組合中都出現(xiàn)的維度。如圖2中的地區(qū)R結(jié)點和供應商S結(jié)點。

聯(lián)合維度表示的是在實際數(shù)據(jù)分析時,在任何數(shù)據(jù)塊維度組合中都同時出現(xiàn)的若干個維度。如圖2中的(R,G)結(jié)點和(G,S)結(jié)點。地區(qū)R和商品G、商品G和供應商S這2對維度組合是同時出現(xiàn)在數(shù)據(jù)分析中的[8]。

3 數(shù)據(jù)立方體有向圖的降維和簡化方法

3.1 可無維度的判定及數(shù)據(jù)立方體有向圖的簡化調(diào)整

圖3 可無維度S的判定Fig.3 Determination of non dimension S

在數(shù)據(jù)立方體有向圖中,遍歷維度為1的節(jié)點,如果某個一維結(jié)點的出度為0,則可判斷該結(jié)點為可無維度。如圖3所示,假定在數(shù)據(jù)立方體集合中,數(shù)據(jù)片(R,S)、(T,S)和(G,S)都不存在或被刪除,此時S結(jié)點的出度為0,則S結(jié)點就是可無維度。

當有向圖中包含可無維度,如圖3中的S結(jié)點,對數(shù)據(jù)立方體要進行簡化調(diào)整。具體方法是:

1) 在數(shù)據(jù)立方體的有向圖中,遍歷搜索維度為2的結(jié)點(Di,Dj);如果某個(Di,Dj)不是數(shù)據(jù)分析需要的結(jié)點,則將(Di,Dj)刪除;將所有與(Di,Dj)的連接邊刪除;重新計算Di和Dj的出度;如果出度為0,則設(shè)置其為可無維度。

圖4 可無維度S刪除后的cubeFig.4 Cube after deleting the non dimension S

2) 在數(shù)據(jù)立方體的有向圖中,遍歷搜索維度為n(n≥3)的結(jié)點(D1,D2,…,Dn);如果某個(D1,D2,…,Dn)的入度

3.2 必須維度的判定及其數(shù)據(jù)立方體有向圖的簡化調(diào)整

在數(shù)據(jù)立方體有向圖中,假定維度規(guī)模為n,遍歷維度為1的節(jié)點,如果某個一維結(jié)點的出度為n-1,則可判斷該結(jié)點為必須維度。必須維度是指在數(shù)據(jù)立方體有向圖的一維結(jié)點中出度達到最大值的結(jié)點。如圖5所示,假定在數(shù)據(jù)立方體集合中,數(shù)據(jù)片(R,T)、(R,G)和(R,S)同時存在,并且(T,G)、(T,S)和(G,S)都不存在或被刪除,此時R結(jié)點的出度為3,達到比維度規(guī)模4少1的出度值,則R結(jié)點就是必須維度[9]。

當有向圖中包含必須維度,如圖5中的R結(jié)點,對數(shù)據(jù)立方體要進行簡化調(diào)整。具體方法是:

1) 在數(shù)據(jù)立方體的有向圖中,遍歷搜索維度為2的結(jié)點(Di,Dj);將所有不包含必須維度的數(shù)據(jù)片結(jié)點刪除;將所有與不包含必須維度結(jié)點的邊刪除。

2) 在數(shù)據(jù)立方體的有向圖中,遍歷搜索維度為n(n≥3)的結(jié)點(D1,D2,…,Dn);如果某個(D1,D2,…,Dn)的入度

圖5 必須維度R的判定Fig.5 Determination of required dimension R

圖6 根據(jù)必須維度R調(diào)整后的cubeFig.6 Cube adjusted on the required dimension R

3.3 聯(lián)合維度的判定及其數(shù)據(jù)立方體有向圖的簡化調(diào)整

在數(shù)據(jù)立方體有向圖中,假定維度規(guī)模為n,遍歷維度為n(n≥3)的數(shù)據(jù)片或數(shù)據(jù)塊結(jié)點(D1,D2,…,Dn),如果某個n維結(jié)點中出度為n(n≥2),并且該結(jié)點的維度同時出現(xiàn)在其子結(jié)點中,則可判斷該結(jié)點所包含的維度組合為聯(lián)合維度。如圖7所示,假定在數(shù)據(jù)立方體集合中,數(shù)據(jù)片(R,T)和(G,S)存在,并且(R,G)、(R,S)、(T,G)和(T,S)都不存在或被刪除,計算(R,T)和(G,S)的出度都為2;繼續(xù)遍歷(R,T)的子結(jié)點(R,T,G)和(R,T,S),(R,T)均同時出現(xiàn);繼續(xù)遍歷(G,S)的子結(jié)點(R,T,G)和(R,T,S),(G,S)不同時出現(xiàn)。所以判斷結(jié)點(R,T)中的R和T為聯(lián)合維度。

當有向圖中包含必須維度,如圖7中的(R,T)結(jié)點,對數(shù)據(jù)立方體要進行簡化調(diào)整。具體方法是:

1) 假設(shè)(Dk,Dh)是聯(lián)合維度,在數(shù)據(jù)立方體的有向圖中,遍歷搜索維度為2的結(jié)點(Di,Dj);將所有不同時含(Dk,Dh)的數(shù)據(jù)片結(jié)點刪除;將所有與不包含必須維度結(jié)點的邊刪除;

2) 在數(shù)據(jù)立方體的有向圖中,遍歷搜索維度為n(n≥3)的結(jié)點(D1,D2,…,Dn);如果某個(D1,D2,…,Dn)的入度

圖7 聯(lián)合維度(R,T)的判定Fig.7 Determination of Joint dimension(R,T)

圖8 根據(jù)聯(lián)合維度(R,T)調(diào)整后的cubeFig.8 Cube adjusted on the Joint dimension(R,T)

4 結(jié) 論

傳統(tǒng)的數(shù)據(jù)立方體的構(gòu)建一般采用星型模型,包括位于中心的事實表和位于各個維的維度表。各個維度表和事實表通過包含的相同關(guān)鍵字段形成連接。也就是數(shù)據(jù)立方體是在數(shù)據(jù)分析之前就預先建立存儲的,在進行數(shù)據(jù)分析時,從存儲的立方體中查詢到事實數(shù)據(jù),完成數(shù)據(jù)的分析處理。但是大規(guī)模數(shù)據(jù)的特點是數(shù)據(jù)量大、數(shù)據(jù)維度寬、數(shù)據(jù)更新快,并且數(shù)據(jù)分析要求達到準實時的響應程度。所以,數(shù)據(jù)立方體的構(gòu)建和使用方法要適應大規(guī)模數(shù)據(jù)的特點,數(shù)據(jù)立方體能進行快速分割或者生成數(shù)據(jù)塊和數(shù)據(jù)片是重要的解決辦法。利用有向圖的構(gòu)建方法,可以從低維的數(shù)據(jù)切片動態(tài)地構(gòu)建低維的數(shù)據(jù)快,進而構(gòu)建高維的數(shù)據(jù)快。經(jīng)測試Hadoop平臺參數(shù)調(diào)優(yōu)后,可以提高系統(tǒng)運算效率6%[11]。對于利用率高的數(shù)據(jù)切片或者數(shù)據(jù)快,可能需要常駐內(nèi)存,以降低I/O代價,或者通過代價比較,選擇在內(nèi)存中生成數(shù)據(jù)切片或者數(shù)據(jù)快,以提高構(gòu)建相應立方體的效率和數(shù)據(jù)查詢分析的效率。

[ 1 ]冷芳玲,鮑玉斌,高偉. 基于MapReduce的數(shù)據(jù)聚集運算算法[J]. 中國科技論文在線, 2011,6(7):469-481.

[ 2 ]連城. 大數(shù)據(jù)預聚合OLAP技術(shù)及應用場景探究[J]. 無線互聯(lián)技術(shù), 2017(19):143-144.

[ 3 ]薩初日拉. 基于Spark平臺的數(shù)據(jù)立方體快速計算方法研究[D]. 保定:華北電力大學, 2016:3-9.

[ 4 ]覃雄派,王會舉,杜小勇. 大數(shù)據(jù)分析----RDBMS與MapReduce的競爭與共生[J]. 軟件學報, 2012,23(1):32-45.

[ 5 ]宋愛波,張若儒,趙經(jīng)華. OLAP 聚集計算中的維存儲技術(shù)[J]. 東南大學學報(自然科學版), 2012,9(45):797-802.

[ 6 ]李棟. 基于MapReduce的數(shù)據(jù)立方體物化算法的設(shè)計與實現(xiàn)[D]. 北京:北京郵電大學, 2015:18-21.

[ 7 ]連城. 大數(shù)據(jù)預聚合OLAP技術(shù)及應用場景探究[J]. 無線互聯(lián)科技, 2017(19):143.

[ 8 ]陳慧,龔婷雨. 大數(shù)據(jù)分析與Apache kylin應用[J]. 江西通信科技, 2016(4):26-29.

[ 9 ]Apache Kylin核心團隊. Apache kylin權(quán)威指南[M]. 北京:機械工業(yè)出版社, 2017:89-118.

[10]蔣守壯. 基于Apache kylin構(gòu)建大數(shù)據(jù)分析平臺[M]. 北京:清華大學出版社, 2017:42-57.

[11]張巖,王研. 基于Hadoop的云平臺參數(shù)優(yōu)化的研究[J]. 沈陽師范大學學報(自然科學版), 2017,35(2):234-239.