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

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

0 引 言

大規(guī)模數(shù)據(jù)的實(shí)時分析處理是Hadoop平臺生態(tài)圈進(jìn)行不斷改進(jìn)和擴(kuò)展的根本要求。數(shù)據(jù)倉庫的OLAP(On-Line Analytical Processing,聯(lián)機(jī)數(shù)據(jù)分析)提升響應(yīng)性能主要方法是立方體數(shù)據(jù)的預(yù)聚集,也就是在數(shù)據(jù)的在線分析之前,對立方體中的細(xì)粒度數(shù)據(jù)進(jìn)行預(yù)先的聚合計算,并進(jìn)行預(yù)存儲,在發(fā)生OLAP時直接調(diào)用預(yù)計算的結(jié)果,節(jié)省數(shù)據(jù)掃描和計算的時間,降低時間代價[1]。很多關(guān)于預(yù)聚集的計算和存儲的研究都是針對度量的選擇、投影和連接等算法的改進(jìn)以及存儲效率的提高等方面。采用的主要技術(shù)是利用Hadoop框架,從Hive中讀取源數(shù)據(jù),使用 MapReduce作為Cube構(gòu)建的引擎,并把預(yù)計算的結(jié)果保存在HBase中,對外開放Rest API/JDBC/ODBC的查詢接口[2]。隨著Spark等框架技術(shù)的發(fā)展,在內(nèi)存中完成預(yù)計算和利用基于內(nèi)存的RDD(Resilient Distributed Datasets,彈性分布式數(shù)據(jù)集)存儲和計算數(shù)據(jù)可以實(shí)現(xiàn)OLAP的實(shí)時分析或者準(zhǔn)實(shí)時分析[3]。為了實(shí)現(xiàn)這個目標(biāo),就要對數(shù)據(jù)立方體構(gòu)建進(jìn)行優(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)出高維度所導(dǎo)致的數(shù)據(jù)膨脹的特點(diǎn)[4]。由于超過四維的模型是人腦很難想象和描繪的,所以高維度的數(shù)據(jù)立方體可以用多維分析的維度組合的集合來進(jìn)行描述。構(gòu)建高維度數(shù)據(jù)立方體可以抽象為有向圖的建立,其中的每個結(jié)點(diǎn)對應(yīng)多維分析的一個維度或者維度組合,每個結(jié)點(diǎn)的度表示多維分析的維度數(shù)量。構(gòu)建包含地區(qū)(Region)、時間(Time)、產(chǎn)品(Goods)和供應(yīng)商(Supplier)4個維度的數(shù)據(jù)立方體如圖1所示。為了數(shù)據(jù)立方體的簡潔化,將地區(qū)、時間、產(chǎn)品和供應(yīng)商表示為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é)點(diǎn)是數(shù)據(jù)維,二維的結(jié)點(diǎn)是數(shù)據(jù)切片,三維的結(jié)點(diǎn)和四維的結(jié)點(diǎn)是數(shù)據(jù)切塊。

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

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

圖1中描述的構(gòu)建數(shù)據(jù)立方體的有向圖方法是個漸進(jìn)式的動態(tài)過程。在這個漸進(jìn)式過程中,二維數(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ù)立方體的操作可以通過集合運(yùn)算來完成。集合操作的線性化特點(diǎn)便于數(shù)據(jù)的收縮和擴(kuò)展,分散數(shù)據(jù)的各個元素,數(shù)據(jù)可以隨時以一個元素的形式進(jìn)行訪問和更新[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í)際問題的數(shù)據(jù)分析過程中,有的維度在所有維度的組合中都是必須的,有些維度是在維度組合中必須同時出現(xiàn)的,而有的維度在所有維度的組合中都不是必須的[2]。所以,根據(jù)維度的利用頻度和利用方式,提出以下相關(guān)維度的概念。

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

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

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

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

聯(lián)合維度表示的是在實(shí)際數(shù)據(jù)分析時,在任何數(shù)據(jù)塊維度組合中都同時出現(xiàn)的若干個維度。如圖2中的(R,G)結(jié)點(diǎn)和(G,S)結(jié)點(diǎn)。地區(qū)R和商品G、商品G和供應(yīng)商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é)點(diǎn),如果某個一維結(jié)點(diǎn)的出度為0,則可判斷該結(jié)點(diǎn)為可無維度。如圖3所示,假定在數(shù)據(jù)立方體集合中,數(shù)據(jù)片(R,S)、(T,S)和(G,S)都不存在或被刪除,此時S結(jié)點(diǎn)的出度為0,則S結(jié)點(diǎn)就是可無維度。

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

1) 在數(shù)據(jù)立方體的有向圖中,遍歷搜索維度為2的結(jié)點(diǎn)(Di,Dj);如果某個(Di,Dj)不是數(shù)據(jù)分析需要的結(jié)點(diǎn),則將(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é)點(diǎn)(D1,D2,…,Dn);如果某個(D1,D2,…,Dn)的入度

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

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

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

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

2) 在數(shù)據(jù)立方體的有向圖中,遍歷搜索維度為n(n≥3)的結(jié)點(diǎn)(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é)點(diǎn)(D1,D2,…,Dn),如果某個n維結(jié)點(diǎn)中出度為n(n≥2),并且該結(jié)點(diǎn)的維度同時出現(xiàn)在其子結(jié)點(diǎn)中,則可判斷該結(jié)點(diǎn)所包含的維度組合為聯(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é)點(diǎn)(R,T,G)和(R,T,S),(R,T)均同時出現(xiàn);繼續(xù)遍歷(G,S)的子結(jié)點(diǎn)(R,T,G)和(R,T,S),(G,S)不同時出現(xiàn)。所以判斷結(jié)點(diǎn)(R,T)中的R和T為聯(lián)合維度。

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

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

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

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

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

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

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

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

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

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

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

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

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

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