張子浪+++葛昂+++鄭家民

【 摘 要 】 文章利用并行計(jì)算框架MapReduce，探索數(shù)據(jù)立方體的計(jì)算問(wèn)題。數(shù)據(jù)立方體的計(jì)算存在兩個(gè)關(guān)鍵問(wèn)題，一個(gè)是計(jì)算時(shí)間的問(wèn)題，另一個(gè)是立方體的體積問(wèn)題。隨著維度的增加，計(jì)算時(shí)間將呈現(xiàn)指數(shù)級(jí)的增長(zhǎng)，立方體的體積也是如此。盡管MapReduce是一個(gè)優(yōu)秀的并行計(jì)算框架，但在處理數(shù)據(jù)傾斜時(shí)，分區(qū)算法不夠完善，導(dǎo)致一些計(jì)算任務(wù)時(shí)間過(guò)長(zhǎng)，影響整個(gè)作業(yè)的完成時(shí)間。本文通過(guò)數(shù)據(jù)采樣的方式，優(yōu)化數(shù)據(jù)分區(qū)，實(shí)驗(yàn)結(jié)果表明，數(shù)據(jù)立方體的計(jì)算的性能明顯提升。為解決數(shù)據(jù)立方體體積過(guò)大的問(wèn)題，在Reduce階段將最終的結(jié)果輸出到基于NoSQL的HBase數(shù)據(jù)庫(kù)進(jìn)行存儲(chǔ)，HBase方便水平擴(kuò)展，同時(shí)也便于日后對(duì)數(shù)據(jù)立方體的查詢。

【 關(guān)鍵詞 】 數(shù)據(jù)立方體；數(shù)據(jù)分區(qū)；數(shù)據(jù)分析

【 文獻(xiàn)標(biāo)識(shí)碼 】 A

1 引言

在互聯(lián)網(wǎng)和電子商務(wù)領(lǐng)域，一些運(yùn)營(yíng)商以及電子商務(wù)平臺(tái)提供商擁有大量的用戶，并以云計(jì)算的方式向用戶提供服務(wù)，這些服務(wù)響應(yīng)用戶的請(qǐng)求，在后端產(chǎn)生相應(yīng)的數(shù)據(jù)，由于數(shù)據(jù)的集中儲(chǔ)存以及用戶的頻繁請(qǐng)求，使得數(shù)據(jù)量呈現(xiàn)快速增長(zhǎng)。在電子政務(wù)領(lǐng)域，一些政府部門根據(jù)自身信息化的發(fā)展水平及業(yè)務(wù)發(fā)展的需要，將信息化系統(tǒng)集中部署到省級(jí)機(jī)構(gòu)，各地、市通過(guò)專網(wǎng)訪問(wèn)。這其中信息化化建設(shè)步伐更快的政府部門，在省級(jí)集中的基礎(chǔ)上，實(shí)行全國(guó)數(shù)據(jù)的集中。在科學(xué)試驗(yàn)領(lǐng)域，科學(xué)家所觀測(cè)的對(duì)象也產(chǎn)生了大量的數(shù)據(jù)，比如天文學(xué)當(dāng)中利用天文望遠(yuǎn)鏡，只需幾天的時(shí)間，并能掃描半個(gè)天空。

就這些領(lǐng)域的數(shù)據(jù)產(chǎn)生速度而言，一些IT系統(tǒng)每天產(chǎn)生TB級(jí)的數(shù)據(jù)量，有的則多達(dá)PB級(jí)。有了大量的數(shù)據(jù)，就會(huì)產(chǎn)生數(shù)據(jù)挖掘的需求，包括對(duì)數(shù)據(jù)進(jìn)行匯總分析。數(shù)據(jù)立方體能夠很好地表達(dá)多維的結(jié)構(gòu)化數(shù)據(jù)的匯總分析，傳統(tǒng)的聯(lián)機(jī)分析（OLAP）技術(shù)對(duì)于立方體的計(jì)算方法也相對(duì)較為成熟。傳統(tǒng)的OLAP根據(jù)數(shù)據(jù)儲(chǔ)存方式的不同，可分為兩類：一類是ROLAP，以關(guān)系表進(jìn)行多維數(shù)據(jù)的表示和存儲(chǔ)；另一類是MOLAP，以多維數(shù)組進(jìn)行多維數(shù)據(jù)的表示和存儲(chǔ)。ROLAP計(jì)算數(shù)據(jù)立方體就是利用SQL中的group by語(yǔ)句對(duì)特定維度屬性集合的所有子集分別集合，后來(lái)引入了Cube操作，一個(gè)Cube等價(jià)于多個(gè)Group by。MOLAP計(jì)算數(shù)據(jù)立方體時(shí)基于數(shù)組對(duì)數(shù)據(jù)進(jìn)行集合，一種比較成熟的算法是多路數(shù)據(jù)聚集算法。

盡管基于傳統(tǒng)的數(shù)據(jù)立方體的并行計(jì)算的算法比較成熟，但其不能直接應(yīng)用于大數(shù)據(jù)的計(jì)算，因?yàn)橛捎谶@些大數(shù)據(jù)基于文件系統(tǒng)存儲(chǔ)，而不是基于關(guān)系型數(shù)據(jù)庫(kù)存儲(chǔ)或者數(shù)組，而且，其數(shù)據(jù)量也大得多。

針對(duì)大數(shù)據(jù)的分析，Google提出了map-reduce的并行計(jì)算框架，結(jié)合上千臺(tái)的廉價(jià)PC服務(wù)器，使得大數(shù)據(jù)的分析能夠在很短時(shí)間之內(nèi)完成，Hadoop是基于該編程模型的開(kāi)源實(shí)現(xiàn)。 利用Hadoop進(jìn)行數(shù)據(jù)立方體進(jìn)行計(jì)算的研究相對(duì)較少，有的利用Hadoop計(jì)算數(shù)據(jù)立方體，但沒(méi)有考慮數(shù)據(jù)的優(yōu)化分區(qū)，直接采用Hadoop缺省的分區(qū)方式，這種方式存在缺陷，不能讓高度傾斜的數(shù)據(jù)（少數(shù)幾個(gè)鍵值出現(xiàn)的次數(shù)占據(jù)了非常大的比例）均勻分配給各個(gè)并行的計(jì)算任務(wù)，導(dǎo)致某些計(jì)算任務(wù)的輸入數(shù)據(jù)過(guò)多，從而導(dǎo)致其完成時(shí)間滯后于其它計(jì)算任務(wù)，影響整個(gè)作業(yè)的完成時(shí)間。

本文給出了基于Map-Reduce計(jì)算數(shù)據(jù)立方體的算法以及分區(qū)優(yōu)化算法，為讓數(shù)據(jù)均勻分布到各個(gè)Reduce任務(wù)，采用數(shù)據(jù)抽樣的方式?jīng)Q定采用何種分區(qū)方式，為并行計(jì)算立方體提供了一種新方式。

數(shù)據(jù)立方體有多種，完整數(shù)據(jù)立方體，冰山立方體，封閉立方體。冰山立方體和封閉立方體考慮了數(shù)據(jù)立方體的體積，減少不必要的存儲(chǔ)。由于封閉立方體或者冰山立方體中的某一個(gè)子立方體很可能就是一個(gè)完整的立方體，因此，計(jì)算完整立方體的過(guò)程不可避免，而且，完整立方體也是其它立方體的基礎(chǔ)。所以本文研究完整立方體的計(jì)算。

在此先介紹并行計(jì)算、數(shù)據(jù)立方體、Hadoop的相關(guān)概念，給出通用的計(jì)算數(shù)據(jù)立方體的Hadoop實(shí)現(xiàn)，在分析可能由于數(shù)據(jù)分布不平衡而導(dǎo)致的計(jì)算不平衡的基礎(chǔ)上，設(shè)計(jì)基于抽樣的分區(qū)算法。然后結(jié)合實(shí)驗(yàn)對(duì)算法進(jìn)行分析。最后對(duì)當(dāng)前工作進(jìn)行總結(jié)，并提出未來(lái)的可能研究方向。

2 概念

2.1 數(shù)據(jù)立方體

實(shí)體關(guān)系模型主要應(yīng)用于在關(guān)系型數(shù)據(jù)庫(kù)中，這樣的二維數(shù)據(jù)模型比較適合事務(wù)處理，但是不適合數(shù)據(jù)的在線分析。在數(shù)據(jù)倉(cāng)庫(kù)當(dāng)中，往往需要從多個(gè)角度對(duì)數(shù)據(jù)進(jìn)行分析，因此需要多維的數(shù)據(jù)模型，數(shù)據(jù)立方體就是用來(lái)描述多維數(shù)據(jù)模型的。

給定基本關(guān)系R（A1，A2，A3，…，An，M），由R產(chǎn)生的數(shù)據(jù)立方體是R的屬性的所有的可能組合，n個(gè)屬性產(chǎn)生2n個(gè)組合。A1，A2，A3，…，An為立方體的屬性維，M為度量維，M是一個(gè)數(shù)字函數(shù)，描述數(shù)據(jù)以何種方式進(jìn)行聚合或者計(jì)算。

取n=3，即基本關(guān)系R（A1，A2，A3，M）產(chǎn)生的立方體由以下分組構(gòu)成：

{（A1，A2，A3），（A1，A2），（A1，A3），（A2，A3），（A1），（A2），（A3），（）}。

度量維常見(jiàn)的聚合函數(shù)有SUM，MAX，MIN，AVG等。聚合函數(shù)可分為三類，分別是分布式，代數(shù)式，綜合式的?？紤]對(duì)分組P中的元素進(jìn)行聚合。

分布式的聚合函數(shù)：，Pi（i=1，2，3，…n）為P的兩兩不相交的子集，即∪Pni=1=P并且□ij，i≠j，Pi∩Pj=?，如果存在函數(shù)G，使得F（P）=G（F（P1）， F（P2）， …，F(xiàn)（Pn）），那么稱聚合函數(shù)F為分布式式函數(shù)。COUNT（）， MIN（）， MAX（），SUM（）都是分布式函數(shù)。除了COUNT函數(shù)外，其余三個(gè)幾個(gè)函數(shù)F=G。對(duì)于COUNT函數(shù)而言，G=SUM，即COUNT（P）=SUM（COUNT（P1）， COUNT（P2）， COUNT（P3），…， COUNT（Pn））。endprint

代數(shù)式聚合函數(shù)：Pi（i=1，2，3，…n）為P的兩兩不相交的子集，∪Pni=1=P并且□ij，i≠j，Pi∩Pj=?，如果存在函數(shù)G和函數(shù)H（對(duì)于所有的Pi，H函數(shù)返回一個(gè)k元組），使得F（P）=G（H （P1）， H（P2）， …，H （Pn）），那么稱聚合函數(shù)F為分布式式函數(shù)。AVG函數(shù)就是代數(shù)式函數(shù)，對(duì)每個(gè)每個(gè)Pi，H函數(shù)返回一個(gè)二元組（sumi，counti），G函數(shù)對(duì)所有的sumi及counti分別相加，然后相除產(chǎn)生整體的平均值，即 。

整體式聚合函數(shù)：既不是分布式的函數(shù)以及代數(shù)式的函數(shù)稱之為整體式聚合函數(shù)。

在對(duì)一個(gè)大的數(shù)據(jù)集進(jìn)行聚合時(shí)，如果聚合函數(shù)是分布式函數(shù)或者代數(shù)式函數(shù)，那么可以采用分而治之的思想，可以將大的數(shù)據(jù)集為眾多小的數(shù)據(jù)集，然后對(duì)每個(gè)小的數(shù)據(jù)集進(jìn)行計(jì)算，最后對(duì)中間的計(jì)算結(jié)果進(jìn)行匯總，從而得到整體的計(jì)算結(jié)果。

2.2 MapReduce

MapReduce是基于非共享的并行計(jì)算模型，該模型能夠充分利用由多臺(tái)機(jī)器組成的計(jì)算、存儲(chǔ)、網(wǎng)絡(luò)資源并行地處理計(jì)算任務(wù)， 適合處理與大數(shù)據(jù)相關(guān)的統(tǒng)計(jì)分析。

MapReduce并行計(jì)算模型與其它并行計(jì)算相比，主要有兩個(gè)特點(diǎn)：一是其對(duì)串行任務(wù)與并行任務(wù)的隔離，以及計(jì)算任務(wù)能夠在各個(gè)計(jì)算節(jié)點(diǎn)上獨(dú)立地進(jìn)行；二是編程模型簡(jiǎn)潔，學(xué)習(xí)成本低。MapReduce將計(jì)算分為兩個(gè)階段：Map階段和Reduce階段。首先，一個(gè)大的輸入文件被分割成M塊，分別由m個(gè)并行運(yùn)行的Map任務(wù)進(jìn)行處理，每個(gè)map任務(wù)以鍵值對(duì)的形式接收輸入，對(duì)于每一個(gè)記錄，將其轉(zhuǎn)為的形式，然后由reduce任務(wù)進(jìn)行處理，輸出鍵值對(duì)。

2.3 NoSQL

關(guān)系型數(shù)據(jù)庫(kù)自20世紀(jì)70年代誕生以來(lái)，在企業(yè)和政府的信息化建設(shè)中得到了廣泛的應(yīng)用，今天關(guān)系型數(shù)據(jù)依然發(fā)揮著重要的作用。然而，對(duì)于以PB衡量的大數(shù)據(jù)，關(guān)系型數(shù)據(jù)庫(kù)不能很好地應(yīng)對(duì)。這些數(shù)據(jù)的特點(diǎn)的是數(shù)據(jù)類型多樣，包括結(jié)構(gòu)化、半結(jié)構(gòu)化，非結(jié)構(gòu)化的數(shù)據(jù)，另一個(gè)特點(diǎn)是數(shù)據(jù)量大。非關(guān)系型的NoSQL數(shù)據(jù)庫(kù)適合這類數(shù)據(jù)的存儲(chǔ)。NoSQL具有三個(gè)特點(diǎn)：一是以Key-Value作為存儲(chǔ)模型；二是保證數(shù)據(jù)的最終一致性；三是在保證應(yīng)用不間斷的情況下方便實(shí)現(xiàn)水平擴(kuò)展。NoSQL數(shù)據(jù)庫(kù)主要包括Cassandra、HBase、mongoDB等。這三種作為NoSQL數(shù)據(jù)庫(kù)中的主流代表，在很多生產(chǎn)系統(tǒng)中得到了應(yīng)用，在處理大數(shù)據(jù)時(shí)，能保持很好的性能，都是較為成熟的產(chǎn)品。當(dāng)然，這幾種NoSQL數(shù)據(jù)庫(kù)的系統(tǒng)架構(gòu)不一樣，側(cè)重點(diǎn)也不一樣。HBase的文件系統(tǒng)基于HDFS，能與Hadoop的MapReduce并行計(jì)算框架無(wú)縫集成。由于本文選用的是Hadoop的MapReduce并行計(jì)算框架，因此NoSQL數(shù)據(jù)庫(kù)采用HBase。

3 算法

算法除了實(shí)現(xiàn)MapReduce中的map接口和reduce接口之外，還實(shí)現(xiàn)了getPartition分區(qū)接口。Map函數(shù)根據(jù)關(guān)系模式R的n個(gè)屬性（A1，A1，A3，...，An），形成2n個(gè)所有屬性的可能組合，再取得相應(yīng)屬性的值作為鍵值，這樣，在map階段，每條輸入記錄將產(chǎn)生2n個(gè)中間的鍵值對(duì)。為保證每個(gè)Reduce任務(wù)的負(fù)載大致相同，分區(qū)算法通過(guò)抽樣的方式，統(tǒng)計(jì)每個(gè)鍵出現(xiàn)的頻率，以每個(gè)鍵的頻率之和度量分區(qū)的負(fù)載，盡可能讓每個(gè)分區(qū)的負(fù)載大致相等。Combine函數(shù)根據(jù)具有分布式或者代數(shù)式性質(zhì)的函數(shù)M對(duì)數(shù)據(jù)進(jìn)行聚合，把中間結(jié)果中具有相同key進(jìn)行合并，形成一個(gè)鍵值對(duì)。Reduce的實(shí)現(xiàn)相與Combine相似，只是在輸出的時(shí)候有差異，Reduce將最終結(jié)果保存至HBase數(shù)據(jù)庫(kù)。

3.1 Map/Reduce實(shí)現(xiàn)

算法形式化描述：

//R由n個(gè)屬性組成的關(guān)系模式

R={A1，A2，A3…，An}

//e為輸入文件中一條記錄

Map（e）

{

//根據(jù)關(guān)系模式R和e產(chǎn)生中間的key

//每個(gè)輸入元素e產(chǎn)生2n-1個(gè)key

emitKeyBySubSetOfR（0，n，R，e）

}

emitKeyBySubSetOfR（begin，end，R）

{

//計(jì)算包含R[i]的子集

for（i=begin；i

{

stack.push（R[i]）；

}

//i自增，計(jì)算不包含R[i]的子集

emitKeyBySubSetOfR（i+1，end）；

//I為R的一個(gè)子集

I={}

for（each o in stack）

{

I=I∪o

}

//元素e取I中的屬性形成鍵值k

k=I（e）

emit（k，e）

stack.pop（）；

}

//中間結(jié)果保存到文件

Combine（k， iterator values））

{

total=0；

while（e=（values.nextvalue（））

{

total=M（total，M（e））

}

emit2file（k，total）；

}

計(jì)算最終結(jié)果并保存至hbase數(shù)據(jù)庫(kù)

Reduce （k， iterator values））

{

total=0；

while（e=（values.nextvalue（））

{

total=M（total，M（e））

}

emit2hbase（k，total）；

}

3.2 Partition實(shí)現(xiàn)

每個(gè)Map任務(wù)會(huì)輸出一系列的以鍵值對(duì)（）形式的記錄，然后由Reduce任務(wù)進(jìn)行處理。由于存在多個(gè)Reduce任務(wù)，具體的一條記錄由哪個(gè)Reduce任務(wù)處理，是由分區(qū)函數(shù)決定的。Hadoop中缺省采用hash函數(shù)對(duì)Map任務(wù)輸出記錄的鍵值進(jìn)行分區(qū)，由于每個(gè)分區(qū)只由一個(gè)Reduce任務(wù)處理，因此分區(qū)的數(shù)量等于Reduce任務(wù)的數(shù)量，每個(gè)Reduce任務(wù)處理一個(gè)分區(qū)。分區(qū)函數(shù)的形式描述為：

hash （Hash code （Intermediate-key） % numReduceTasks）

Hadoop中的Java實(shí)現(xiàn)如下：

public class HashPartitioner extends Partitioner {

public int getPartition（K key， V value，

int numReduceTasks） {

return （key.hashCode（） & Integer.MAX_VALUE） % numReduceTasks；

}

Hash函數(shù)能夠保證每個(gè)分區(qū)中鍵（Key）的數(shù)量大致相同。假設(shè)有k個(gè)不同的鍵，由r個(gè)reduce任務(wù)處理，分區(qū)函數(shù)能夠保證每個(gè)reduce任務(wù)處理鍵的數(shù)量為k/r。然而由于有的鍵（Key）頻繁出現(xiàn)，即很多記錄具有相同的鍵值，顯然，分區(qū)中包含這樣的鍵其數(shù)據(jù)量要大的多，所需的計(jì)算時(shí)間也更長(zhǎng)。

建設(shè)有6個(gè)鍵，分別是K1，K2，K3，K4，K5，K6，每個(gè)鍵包含的記錄數(shù)分別為1，2，3，4，5，6，這6個(gè)鍵由3個(gè)Reduce任務(wù)處理。采用hash分區(qū)策略，會(huì)形成3個(gè)分區(qū)，Partition1包含K1和K4，Partition2包含K2和K5，Partiton3包含K3和K6。盡管每個(gè)分區(qū)包含鍵的數(shù)量都為2，但是每個(gè)分區(qū)的數(shù)據(jù)量不一致。Partition1包含5條記錄，Partition2包含7條記錄，Partiton3包含9條記錄。理想的情況應(yīng)該是每個(gè)分區(qū)包含7條記錄。

為了達(dá)到圖2中均勻分區(qū)的效果，需要自定義分區(qū)函數(shù)。分區(qū)函數(shù)需要事先知道鍵的分布頻率，如果數(shù)據(jù)集比較大，掃描整個(gè)數(shù)據(jù)集并求出各個(gè)鍵的分布頻率，所需的時(shí)間比較長(zhǎng)?？蓪?duì)數(shù)據(jù)集進(jìn)行抽樣，只針對(duì)一小部分?jǐn)?shù)據(jù)進(jìn)行統(tǒng)計(jì)，數(shù)據(jù)抽樣的時(shí)間與整個(gè)計(jì)算任務(wù)的時(shí)間相比，可忽略不計(jì)。

假設(shè)一個(gè)數(shù)據(jù)集中包含k個(gè)不同Key，鍵值分別為K1，K2，K3，…，Kk，其出現(xiàn)的頻率為f（ki），共有r個(gè)Reduce任務(wù)。每個(gè)Reduce任務(wù)的負(fù)載定義為其相應(yīng)的分區(qū)的大小，分區(qū)大小可用該分區(qū)內(nèi)記錄數(shù)量大數(shù)目衡量，即分區(qū)內(nèi)各個(gè)Key的頻率之和。

分區(qū)算法的目標(biāo)是讓各個(gè)LRi的值盡可能接近。

R=new ArrayList（）；//初始時(shí)，每個(gè)Reduce的負(fù)載為0

K = {K1， . . . ， Kk}；//K為待分區(qū)的key的集合

While（K.length>0）//如果還有Key沒(méi)有分配到某個(gè)Reduce中

{ //選取頻率數(shù)最大的分配給某個(gè)Ri

kmax = argmaxk∈Kf（k）

//從待分區(qū)的key集合中移除

K.remove（kmax）

//如果存在某個(gè)Ri沒(méi)有負(fù)載

if（R.length < r）

{ keylistofRi={}；

keylistofRi.add（kmax）；

//直接將該key分配給Ri

R.add（keylistofRi）；

}

//如果所有的Ri都有負(fù)載，那么將該key分配給目//前負(fù)載最小的Ri

else

{

keyListOfminLRi = argminiRi∈RLRi

R.remove（keyListOfminLRi）

keyListOfminLRi.add（kmax）

R.add（keyListOfminLRi）

}

}

return R；

這樣，分區(qū)函數(shù)P能夠?qū)i分配給Rj處理，記為P（Ki， Rj）。通過(guò)抽樣形成的分區(qū)方案存入分布式緩存當(dāng)中，每個(gè)map任務(wù)按照分布時(shí)緩存中的分區(qū)方案P（Ki， Rj）對(duì)數(shù)據(jù)進(jìn)行分區(qū)。

4 實(shí)驗(yàn)

為測(cè)試數(shù)據(jù)立方體計(jì)算的空間需求和性能，采用8個(gè)節(jié)點(diǎn)組成的Hadoop集群，每個(gè)節(jié)點(diǎn)的CPU為4核3.1GZ，內(nèi)存為4GB，本地存儲(chǔ)為500G，操作系統(tǒng)環(huán)境為Windows Server 2003。每個(gè)節(jié)點(diǎn)分別運(yùn)行一個(gè)Map任務(wù)和Reduce任務(wù)，輸入數(shù)據(jù)為根據(jù)Zipf分布人工合成，數(shù)據(jù)的傾斜程度通過(guò)參數(shù)z值控制，z的取值范圍是[0，1]，較大的z值表明更高的傾斜程度。

每個(gè)輸入Map接收500萬(wàn)條記錄，輸入數(shù)據(jù)共4000萬(wàn)條記錄。每個(gè)記錄包含4個(gè)屬性，其中一個(gè)屬性的類型為數(shù)字，作為度量維度，另三個(gè)為字符類型，作為屬性維。聚合函數(shù)采用具有分布式函數(shù)特性的sum函數(shù)。

為在數(shù)據(jù)抽樣的比例和精確性之間進(jìn)行平衡，通過(guò)多次試驗(yàn)，發(fā)現(xiàn)以5%的比例進(jìn)行抽樣時(shí)，誤差較小。按這個(gè)比例進(jìn)行數(shù)據(jù)抽樣時(shí)，數(shù)據(jù)抽樣的完成時(shí)間為[5-8]s，這個(gè)時(shí)間與幾百秒的計(jì)算任務(wù)而言，可忽略不計(jì)，以下有關(guān)完成時(shí)間的描述，均未將抽樣時(shí)間計(jì)算在內(nèi)。

當(dāng)取z=0，即數(shù)據(jù)均勻分布，分區(qū)算法采用Hadoop中的缺省分區(qū)函數(shù)時(shí)，最快的Reduce任務(wù)用時(shí)130s，最慢的用時(shí)131s；當(dāng)采用自定義分區(qū)函數(shù)時(shí)，最快的用時(shí)132s，最慢的用時(shí)132.5s。

當(dāng)取z=0.6，即數(shù)據(jù)出現(xiàn)較高程度的傾斜，分區(qū)算法采用Hadoop中缺省分區(qū)函數(shù)時(shí)，最快的Reduce任務(wù)用時(shí)90s，最慢的用時(shí)331s；當(dāng)采用自定義分區(qū)算法時(shí)，最快133s，最慢的用時(shí)138s。

隨著z取更高的值，兩個(gè)分區(qū)算法性能差異明顯，一度出現(xiàn)缺省分區(qū)函數(shù)比自定義分區(qū)函數(shù)慢6倍的情況。

顯然，自定義分區(qū)算法在輸入數(shù)據(jù)無(wú)重復(fù)的情況下，性能與默認(rèn)的分區(qū)函數(shù)相當(dāng)，然而當(dāng)輸入大量重復(fù)，發(fā)生傾斜時(shí)，自定義分區(qū)函數(shù)獲得的性能提升非常明顯。

當(dāng)屬性維度分別從3增加為6和8時(shí)，不管采用何種分區(qū)算法，計(jì)算時(shí)間呈現(xiàn)指數(shù)級(jí)增長(zhǎng)的趨勢(shì)，這主要和每個(gè)輸入記錄產(chǎn)生2n個(gè)中間記錄有關(guān)。

5 結(jié)束語(yǔ)

本文基于開(kāi)源的Hadoop框架對(duì)完整數(shù)據(jù)立方體的計(jì)算進(jìn)行了初步探索。Hadoop并行計(jì)算框架非常優(yōu)秀，簡(jiǎn)化了并行計(jì)算的編程模型，使得并行數(shù)據(jù)立方體的計(jì)算很容易實(shí)現(xiàn)。然而，數(shù)據(jù)立方體的計(jì)算性能非常重要，數(shù)據(jù)分區(qū)是影響性能的一個(gè)重要因素，因?yàn)椴⑿杏?jì)算的前提是各個(gè)計(jì)算任務(wù)的負(fù)載大致相同。Hadoop的缺省分區(qū)機(jī)制在多數(shù)場(chǎng)合能夠讓每個(gè)Reduce任務(wù)的負(fù)載大致相同，然而在數(shù)據(jù)高度傾斜的情況容易導(dǎo)致計(jì)算偏斜。

本文從優(yōu)化數(shù)據(jù)分區(qū)著手，采用抽樣方式對(duì)分區(qū)算法進(jìn)行了一定優(yōu)化，當(dāng)目標(biāo)問(wèn)題為分布式或者代數(shù)式的集合函數(shù)時(shí)，能夠在一定程度上解決因?yàn)閿?shù)據(jù)傾斜而導(dǎo)致的數(shù)據(jù)立方體的計(jì)算性能問(wèn)題。

在系統(tǒng)架構(gòu)方面，選用HBase存儲(chǔ)數(shù)據(jù)立方體，以便水平擴(kuò)展，應(yīng)對(duì)數(shù)據(jù)立方體積快速增加的問(wèn)題。實(shí)驗(yàn)結(jié)果表明，性能提升明顯。此外，影響Hadoop的性能的因素有很多，比如集群的數(shù)量和集群中計(jì)算節(jié)點(diǎn)的數(shù)量，每個(gè)計(jì)算節(jié)點(diǎn)中運(yùn)行的map任務(wù)和reduce任務(wù)的數(shù)量，以及網(wǎng)絡(luò)帶寬的情況，還有數(shù)據(jù)復(fù)制因子的影響，這些在未來(lái)的研究中也會(huì)涉及到。

參考文獻(xiàn)

[1] Lammel， R.： Googles MapReduce Programming Model - Revisited[J]. Science of Computer Programming 70，2008， 1-30.

[2] Dean， J. and Ghemawat， S. Mapreduce： simplified data processing on large clusters[J]. COMMUNICATIONS OF THE ACM 51，2008.

[3] B. Gufler， N. Augsten， A. Reiser， and A. Kemper. Handling.

data skew in mapreduce. In The First International Conference on Cloud Computing and Services Science，2011，574-583.

[4] J. Gray， S. Chaudhuri， A. Bosworth， A. Layman， D. Reichart， M.Venkatrao，F(xiàn). Pellow， and H. Pirahesh. Data Cube： A Relational Operator Generalizing Group-By， Cross-Tab and Sub-Totals[J].

Data Mining and Knowledge Discovery， 1996， 29-53.

[5] S. Ibrahim， H. Jin， L. Lu， S. Wu， B. He， and L. Qi. LEEN：Locality/Fairness-Aware Key Partitioning for MapReduce in the Cloud. In Cloud Computing Technology and Science （CloudCom）， 2010 IEEE Second International Conference on，2010，17-24.

作者簡(jiǎn)介：

張子浪 （1978-），男，中國(guó)社會(huì)科學(xué)院研究生院，MBA，工程師；主要研究方向和關(guān)注領(lǐng)域：多維數(shù)據(jù)聚合。

葛昂，男，北京大學(xué)，MBA，高級(jí)工程師；主要研究方向和關(guān)注領(lǐng)域：數(shù)據(jù)挖掘、企業(yè)架構(gòu)。

鄭家民，男，北京航空航天大學(xué)，軟件工程，高級(jí)工程師；主要研究方向和關(guān)注領(lǐng)域：數(shù)據(jù)挖掘、企業(yè)架構(gòu)。endprint

為在數(shù)據(jù)抽樣的比例和精確性之間進(jìn)行平衡，通過(guò)多次試驗(yàn)，發(fā)現(xiàn)以5%的比例進(jìn)行抽樣時(shí)，誤差較小。按這個(gè)比例進(jìn)行數(shù)據(jù)抽樣時(shí)，數(shù)據(jù)抽樣的完成時(shí)間為[5-8]s，這個(gè)時(shí)間與幾百秒的計(jì)算任務(wù)而言，可忽略不計(jì)，以下有關(guān)完成時(shí)間的描述，均未將抽樣時(shí)間計(jì)算在內(nèi)。

當(dāng)取z=0，即數(shù)據(jù)均勻分布，分區(qū)算法采用Hadoop中的缺省分區(qū)函數(shù)時(shí)，最快的Reduce任務(wù)用時(shí)130s，最慢的用時(shí)131s；當(dāng)采用自定義分區(qū)函數(shù)時(shí)，最快的用時(shí)132s，最慢的用時(shí)132.5s。

當(dāng)取z=0.6，即數(shù)據(jù)出現(xiàn)較高程度的傾斜，分區(qū)算法采用Hadoop中缺省分區(qū)函數(shù)時(shí)，最快的Reduce任務(wù)用時(shí)90s，最慢的用時(shí)331s；當(dāng)采用自定義分區(qū)算法時(shí)，最快133s，最慢的用時(shí)138s。

隨著z取更高的值，兩個(gè)分區(qū)算法性能差異明顯，一度出現(xiàn)缺省分區(qū)函數(shù)比自定義分區(qū)函數(shù)慢6倍的情況。

顯然，自定義分區(qū)算法在輸入數(shù)據(jù)無(wú)重復(fù)的情況下，性能與默認(rèn)的分區(qū)函數(shù)相當(dāng)，然而當(dāng)輸入大量重復(fù)，發(fā)生傾斜時(shí)，自定義分區(qū)函數(shù)獲得的性能提升非常明顯。

當(dāng)屬性維度分別從3增加為6和8時(shí)，不管采用何種分區(qū)算法，計(jì)算時(shí)間呈現(xiàn)指數(shù)級(jí)增長(zhǎng)的趨勢(shì)，這主要和每個(gè)輸入記錄產(chǎn)生2n個(gè)中間記錄有關(guān)。

5 結(jié)束語(yǔ)

本文基于開(kāi)源的Hadoop框架對(duì)完整數(shù)據(jù)立方體的計(jì)算進(jìn)行了初步探索。Hadoop并行計(jì)算框架非常優(yōu)秀，簡(jiǎn)化了并行計(jì)算的編程模型，使得并行數(shù)據(jù)立方體的計(jì)算很容易實(shí)現(xiàn)。然而，數(shù)據(jù)立方體的計(jì)算性能非常重要，數(shù)據(jù)分區(qū)是影響性能的一個(gè)重要因素，因?yàn)椴⑿杏?jì)算的前提是各個(gè)計(jì)算任務(wù)的負(fù)載大致相同。Hadoop的缺省分區(qū)機(jī)制在多數(shù)場(chǎng)合能夠讓每個(gè)Reduce任務(wù)的負(fù)載大致相同，然而在數(shù)據(jù)高度傾斜的情況容易導(dǎo)致計(jì)算偏斜。

本文從優(yōu)化數(shù)據(jù)分區(qū)著手，采用抽樣方式對(duì)分區(qū)算法進(jìn)行了一定優(yōu)化，當(dāng)目標(biāo)問(wèn)題為分布式或者代數(shù)式的集合函數(shù)時(shí)，能夠在一定程度上解決因?yàn)閿?shù)據(jù)傾斜而導(dǎo)致的數(shù)據(jù)立方體的計(jì)算性能問(wèn)題。

在系統(tǒng)架構(gòu)方面，選用HBase存儲(chǔ)數(shù)據(jù)立方體，以便水平擴(kuò)展，應(yīng)對(duì)數(shù)據(jù)立方體積快速增加的問(wèn)題。實(shí)驗(yàn)結(jié)果表明，性能提升明顯。此外，影響Hadoop的性能的因素有很多，比如集群的數(shù)量和集群中計(jì)算節(jié)點(diǎn)的數(shù)量，每個(gè)計(jì)算節(jié)點(diǎn)中運(yùn)行的map任務(wù)和reduce任務(wù)的數(shù)量，以及網(wǎng)絡(luò)帶寬的情況，還有數(shù)據(jù)復(fù)制因子的影響，這些在未來(lái)的研究中也會(huì)涉及到。

參考文獻(xiàn)

[1] Lammel， R.： Googles MapReduce Programming Model - Revisited[J]. Science of Computer Programming 70，2008， 1-30.

[2] Dean， J. and Ghemawat， S. Mapreduce： simplified data processing on large clusters[J]. COMMUNICATIONS OF THE ACM 51，2008.

[3] B. Gufler， N. Augsten， A. Reiser， and A. Kemper. Handling.

data skew in mapreduce. In The First International Conference on Cloud Computing and Services Science，2011，574-583.

[4] J. Gray， S. Chaudhuri， A. Bosworth， A. Layman， D. Reichart， M.Venkatrao，F(xiàn). Pellow， and H. Pirahesh. Data Cube： A Relational Operator Generalizing Group-By， Cross-Tab and Sub-Totals[J].

Data Mining and Knowledge Discovery， 1996， 29-53.

[5] S. Ibrahim， H. Jin， L. Lu， S. Wu， B. He， and L. Qi. LEEN：Locality/Fairness-Aware Key Partitioning for MapReduce in the Cloud. In Cloud Computing Technology and Science （CloudCom）， 2010 IEEE Second International Conference on，2010，17-24.

作者簡(jiǎn)介：

張子浪 （1978-），男，中國(guó)社會(huì)科學(xué)院研究生院，MBA，工程師；主要研究方向和關(guān)注領(lǐng)域：多維數(shù)據(jù)聚合。

葛昂，男，北京大學(xué)，MBA，高級(jí)工程師；主要研究方向和關(guān)注領(lǐng)域：數(shù)據(jù)挖掘、企業(yè)架構(gòu)。

鄭家民，男，北京航空航天大學(xué)，軟件工程，高級(jí)工程師；主要研究方向和關(guān)注領(lǐng)域：數(shù)據(jù)挖掘、企業(yè)架構(gòu)。endprint

為在數(shù)據(jù)抽樣的比例和精確性之間進(jìn)行平衡，通過(guò)多次試驗(yàn)，發(fā)現(xiàn)以5%的比例進(jìn)行抽樣時(shí)，誤差較小。按這個(gè)比例進(jìn)行數(shù)據(jù)抽樣時(shí)，數(shù)據(jù)抽樣的完成時(shí)間為[5-8]s，這個(gè)時(shí)間與幾百秒的計(jì)算任務(wù)而言，可忽略不計(jì)，以下有關(guān)完成時(shí)間的描述，均未將抽樣時(shí)間計(jì)算在內(nèi)。

當(dāng)取z=0，即數(shù)據(jù)均勻分布，分區(qū)算法采用Hadoop中的缺省分區(qū)函數(shù)時(shí)，最快的Reduce任務(wù)用時(shí)130s，最慢的用時(shí)131s；當(dāng)采用自定義分區(qū)函數(shù)時(shí)，最快的用時(shí)132s，最慢的用時(shí)132.5s。

當(dāng)取z=0.6，即數(shù)據(jù)出現(xiàn)較高程度的傾斜，分區(qū)算法采用Hadoop中缺省分區(qū)函數(shù)時(shí)，最快的Reduce任務(wù)用時(shí)90s，最慢的用時(shí)331s；當(dāng)采用自定義分區(qū)算法時(shí)，最快133s，最慢的用時(shí)138s。

隨著z取更高的值，兩個(gè)分區(qū)算法性能差異明顯，一度出現(xiàn)缺省分區(qū)函數(shù)比自定義分區(qū)函數(shù)慢6倍的情況。

顯然，自定義分區(qū)算法在輸入數(shù)據(jù)無(wú)重復(fù)的情況下，性能與默認(rèn)的分區(qū)函數(shù)相當(dāng)，然而當(dāng)輸入大量重復(fù)，發(fā)生傾斜時(shí)，自定義分區(qū)函數(shù)獲得的性能提升非常明顯。

當(dāng)屬性維度分別從3增加為6和8時(shí)，不管采用何種分區(qū)算法，計(jì)算時(shí)間呈現(xiàn)指數(shù)級(jí)增長(zhǎng)的趨勢(shì)，這主要和每個(gè)輸入記錄產(chǎn)生2n個(gè)中間記錄有關(guān)。

5 結(jié)束語(yǔ)

本文基于開(kāi)源的Hadoop框架對(duì)完整數(shù)據(jù)立方體的計(jì)算進(jìn)行了初步探索。Hadoop并行計(jì)算框架非常優(yōu)秀，簡(jiǎn)化了并行計(jì)算的編程模型，使得并行數(shù)據(jù)立方體的計(jì)算很容易實(shí)現(xiàn)。然而，數(shù)據(jù)立方體的計(jì)算性能非常重要，數(shù)據(jù)分區(qū)是影響性能的一個(gè)重要因素，因?yàn)椴⑿杏?jì)算的前提是各個(gè)計(jì)算任務(wù)的負(fù)載大致相同。Hadoop的缺省分區(qū)機(jī)制在多數(shù)場(chǎng)合能夠讓每個(gè)Reduce任務(wù)的負(fù)載大致相同，然而在數(shù)據(jù)高度傾斜的情況容易導(dǎo)致計(jì)算偏斜。

本文從優(yōu)化數(shù)據(jù)分區(qū)著手，采用抽樣方式對(duì)分區(qū)算法進(jìn)行了一定優(yōu)化，當(dāng)目標(biāo)問(wèn)題為分布式或者代數(shù)式的集合函數(shù)時(shí)，能夠在一定程度上解決因?yàn)閿?shù)據(jù)傾斜而導(dǎo)致的數(shù)據(jù)立方體的計(jì)算性能問(wèn)題。

在系統(tǒng)架構(gòu)方面，選用HBase存儲(chǔ)數(shù)據(jù)立方體，以便水平擴(kuò)展，應(yīng)對(duì)數(shù)據(jù)立方體積快速增加的問(wèn)題。實(shí)驗(yàn)結(jié)果表明，性能提升明顯。此外，影響Hadoop的性能的因素有很多，比如集群的數(shù)量和集群中計(jì)算節(jié)點(diǎn)的數(shù)量，每個(gè)計(jì)算節(jié)點(diǎn)中運(yùn)行的map任務(wù)和reduce任務(wù)的數(shù)量，以及網(wǎng)絡(luò)帶寬的情況，還有數(shù)據(jù)復(fù)制因子的影響，這些在未來(lái)的研究中也會(huì)涉及到。

參考文獻(xiàn)

[1] Lammel， R.： Googles MapReduce Programming Model - Revisited[J]. Science of Computer Programming 70，2008， 1-30.

[2] Dean， J. and Ghemawat， S. Mapreduce： simplified data processing on large clusters[J]. COMMUNICATIONS OF THE ACM 51，2008.

[3] B. Gufler， N. Augsten， A. Reiser， and A. Kemper. Handling.

data skew in mapreduce. In The First International Conference on Cloud Computing and Services Science，2011，574-583.

[4] J. Gray， S. Chaudhuri， A. Bosworth， A. Layman， D. Reichart， M.Venkatrao，F(xiàn). Pellow， and H. Pirahesh. Data Cube： A Relational Operator Generalizing Group-By， Cross-Tab and Sub-Totals[J].

Data Mining and Knowledge Discovery， 1996， 29-53.

[5] S. Ibrahim， H. Jin， L. Lu， S. Wu， B. He， and L. Qi. LEEN：Locality/Fairness-Aware Key Partitioning for MapReduce in the Cloud. In Cloud Computing Technology and Science （CloudCom）， 2010 IEEE Second International Conference on，2010，17-24.

作者簡(jiǎn)介：

張子浪 （1978-），男，中國(guó)社會(huì)科學(xué)院研究生院，MBA，工程師；主要研究方向和關(guān)注領(lǐng)域：多維數(shù)據(jù)聚合。

葛昂，男，北京大學(xué)，MBA，高級(jí)工程師；主要研究方向和關(guān)注領(lǐng)域：數(shù)據(jù)挖掘、企業(yè)架構(gòu)。

鄭家民，男，北京航空航天大學(xué)，軟件工程，高級(jí)工程師；主要研究方向和關(guān)注領(lǐng)域：數(shù)據(jù)挖掘、企業(yè)架構(gòu)。endprint