張 濱，樂(lè)嘉錦

(1.東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 201620;2.浙江財(cái)經(jīng)大學(xué)，杭州 310018)

1 概述

隨著計(jì)算機(jī)技術(shù)和互聯(lián)網(wǎng)的急速發(fā)展，特別是隨著Web2.0 的發(fā)展，互聯(lián)網(wǎng)上的數(shù)據(jù)量高速增長(zhǎng)，現(xiàn)有技術(shù)對(duì)大數(shù)據(jù)的處理能力越來(lái)越無(wú)法勝任。伴隨著待處理數(shù)據(jù)越來(lái)越多，當(dāng)前已經(jīng)不可能將大數(shù)據(jù)存儲(chǔ)在一臺(tái)或有限數(shù)目的服務(wù)器內(nèi)，而且無(wú)法由數(shù)目有限的計(jì)算機(jī)來(lái)處理大數(shù)據(jù)的困境。因此，如何實(shí)現(xiàn)資源和計(jì)算能力的分布式共享以及如何應(yīng)對(duì)當(dāng)前數(shù)據(jù)量高速增長(zhǎng)的勢(shì)頭，是目前數(shù)據(jù)管理、數(shù)據(jù)處理領(lǐng)域亟待解決的問(wèn)題。

本文將大數(shù)據(jù)的特點(diǎn)描述為:大數(shù)據(jù)具有規(guī)模大、深度大、寬度大、處理時(shí)間短、硬件系統(tǒng)普通化、軟件系統(tǒng)開源化特點(diǎn)。在MapReduce［1］分布式環(huán)境下，原有傳統(tǒng)的關(guān)系運(yùn)算，特別是數(shù)據(jù)的連接運(yùn)算，在執(zhí)行過(guò)程中產(chǎn)生大量的中間結(jié)果，從而導(dǎo)致大量的系統(tǒng)開銷，執(zhí)行效率低下。這已經(jīng)成為影響大數(shù)據(jù)分析處理的瓶頸。

針對(duì)上述問(wèn)題，本文提出一種基于列存儲(chǔ)的MapReduce 并行連接算法，該算法在列存儲(chǔ)系統(tǒng)中結(jié)合基于規(guī)則及基于代價(jià)的方式優(yōu)化查詢，給出一種MapReduce 平臺(tái)上基于過(guò)濾器的多表連接算法，它能夠同時(shí)對(duì)多個(gè)關(guān)系表進(jìn)行連接，避免中間結(jié)果的產(chǎn)生，還能最大程度避免不必要的元組復(fù)制與數(shù)據(jù)傳輸。

2 相關(guān)工作

2.1 列存儲(chǔ)技術(shù)

列存儲(chǔ)［2］的概念可以追溯到20 世紀(jì)70 年代，早在1976 年，加拿大統(tǒng)計(jì)局開發(fā)實(shí)現(xiàn)了列存儲(chǔ)數(shù)據(jù)庫(kù)管理系統(tǒng)，并在80 年代廣泛應(yīng)用。這些系統(tǒng)對(duì)傳統(tǒng)DBMS 底層存儲(chǔ)進(jìn)行修改，對(duì)關(guān)系表進(jìn)行垂直分解，然而在查詢初始時(shí)將查詢涉及的列組裝成行，使用面向行的查詢執(zhí)行引擎進(jìn)行查詢執(zhí)行，其效率提高有限。隨著企業(yè)對(duì)分析型查詢需求的快速增長(zhǎng)，對(duì)列存儲(chǔ)的研究在近些年得到了快速提升。Monet DB［3］和C-Store［4］是其中有影響力的代表性成果。Monet DB 由荷蘭國(guó)家數(shù)學(xué)和計(jì)算機(jī)科學(xué)研究院(CWI)研 究 開 發(fā)。C-Store 由 美 國(guó) MIT，Yale，Brandeis 大學(xué)、Brown 大學(xué)以及UMass Boston 大學(xué)等多所大學(xué)聯(lián)合研究開發(fā)，在存儲(chǔ)結(jié)構(gòu)、查詢優(yōu)化、壓縮等各方面進(jìn)行技術(shù)創(chuàng)新。

2.2 面向大數(shù)據(jù)處理的MapReduce 模型

2004 年，Google 研究員Dean J 和Ghemawat S 通過(guò)對(duì)網(wǎng)頁(yè)數(shù)據(jù)存儲(chǔ)和并行分析處理研究后，提出了MapReduce 計(jì)算模型，此后在ACM 等多個(gè)期刊上轉(zhuǎn)載。MapReduce 計(jì)算模型為大數(shù)據(jù)分析處理問(wèn)題的提供了一個(gè)新的有效解決方法和途徑。

2008 年 底，Apache 的 Hadoop［5］項(xiàng) 目 作 為MapReduce 開源實(shí)現(xiàn)，迅速得到廣泛關(guān)注和使用。Hadoop 的HDFS(Hadoop Distributed File System)是一種專門為MapReduce 設(shè)計(jì)的大數(shù)據(jù)分布式文件系統(tǒng)，處理大數(shù)據(jù)性能優(yōu)越。

2.3 MapReduce 與數(shù)據(jù)庫(kù)技術(shù)的結(jié)合

在并行數(shù)據(jù)庫(kù)與MapReduce 模型相結(jié)合的理論研究方面，國(guó)外以耶魯大學(xué)的研究團(tuán)隊(duì)在近3 年SIGMOD，VLDB 上發(fā)表了多篇關(guān)于在數(shù)據(jù)庫(kù)領(lǐng)域的列存儲(chǔ)的論文，2009 年、2011 年發(fā)表在VLDB 上的HadoopDB［6］研究為代表，在Hadoop 基礎(chǔ)上提出了Hadapt［7］研究，它消除數(shù)據(jù)孤島，在云環(huán)境中使用現(xiàn)有的SQL 工具，組織分析大量的“多層結(jié)構(gòu)”數(shù)據(jù)。2011 年SIGMOD 上發(fā)表了新加坡國(guó)立大學(xué)和浙江大學(xué)研究的借助列存儲(chǔ)技術(shù)實(shí)現(xiàn)MapReduce 框架下可擴(kuò)展連接處理論文［8］。設(shè)計(jì)了Llama 這個(gè)在MapReduce 框架下的數(shù)據(jù)管理原型系統(tǒng)，在底層使用一個(gè)創(chuàng)新的文件存儲(chǔ)格式:CFiles。2011 年VLDB上發(fā)表了威斯康星麥迪遜大學(xué)和IBM 研究員聯(lián)合研發(fā)的基于列存儲(chǔ)技術(shù)的MapReduce 框架論文［9］，利用列存儲(chǔ)技術(shù)對(duì)MapReduce 的改進(jìn)，該論文闡述了列存儲(chǔ)格式兼容Hadoop 復(fù)制和調(diào)度約束機(jī)制，證明列存儲(chǔ)格式在實(shí)際工作負(fù)載條件下能加快MapReduce 任務(wù)處理速度;其次研究如何處理列存儲(chǔ)遇到的復(fù)雜的數(shù)據(jù)類型。

在國(guó)內(nèi)對(duì)于大數(shù)據(jù)分析應(yīng)用以及MapReduce 與數(shù)據(jù)庫(kù)技術(shù)相結(jié)合技術(shù)研究，相對(duì)起步較晚。文獻(xiàn)［10］指出面對(duì)大數(shù)據(jù)深度分析的挑戰(zhàn)，關(guān)系數(shù)據(jù)庫(kù)技術(shù)的擴(kuò)展性遇到了前所未有的困難。MapReduce 技術(shù)具有簡(jiǎn)潔的模型、良好的擴(kuò)展性、容錯(cuò)性和并行性，高性能。關(guān)系數(shù)據(jù)庫(kù)技術(shù)和MapReduce 技術(shù)相互競(jìng)爭(zhēng)、相互學(xué)習(xí)和相互滲透，促進(jìn)了數(shù)據(jù)分析新生態(tài)系統(tǒng)的浮現(xiàn)。文獻(xiàn)［11］提出了基于MapReduce 的關(guān)系型數(shù)據(jù)倉(cāng)庫(kù)并行查詢方法，并設(shè)計(jì)了基于MapReduce的分布式關(guān)系數(shù)據(jù)庫(kù):ChunkDB。

綜上所述，當(dāng)前列存儲(chǔ)系統(tǒng)在MapReduce 的分布式環(huán)境下的并行連接方向的研究還較少，對(duì)聚集運(yùn)算缺少深入分析，方法也很局限，本文提出基于列存儲(chǔ)的MapReduce 環(huán)境下數(shù)據(jù)查詢中的并行連接算法，該算法結(jié)合分片聚集和啟發(fā)式規(guī)則對(duì)連接進(jìn)行優(yōu)化，提高數(shù)據(jù)處理效率。

3 基本定義與符號(hào)

列存儲(chǔ)在MapReduce 分布式環(huán)境實(shí)現(xiàn)示意圖如圖1 所示。

圖1 列存儲(chǔ)在MapReduce 分布式環(huán)境實(shí)現(xiàn)示意圖

在MapReduce 并行計(jì)算環(huán)境下，列存儲(chǔ)與行存儲(chǔ)不同，其查詢處理的操作對(duì)象，由原來(lái)的行或者行組，轉(zhuǎn)變?yōu)榉植际酱鎯?chǔ)在每個(gè)節(jié)點(diǎn)上的列或水平劃分后的列組，因此，查詢執(zhí)行投影操作轉(zhuǎn)變?yōu)槊總€(gè)節(jié)點(diǎn)上的列的操作，效率很高。查詢中的每個(gè)操作都相對(duì)獨(dú)立，減少重復(fù)訪問(wèn)同表帶來(lái)的I/O 浪費(fèi)，這也為MapReduce 框架下查詢的并行執(zhí)行提供了必要條件。在行存儲(chǔ)中，下推的目標(biāo)對(duì)象是表，而在列存儲(chǔ)中，下推的目標(biāo)對(duì)象具體到某個(gè)列，每個(gè)列相當(dāng)于一個(gè)由(rowid，value)組成的小表。在MapReduce 分布式環(huán)境下，小表又是分隔后存儲(chǔ)在集群每臺(tái)機(jī)器上。因此，在列存儲(chǔ)的MapReduce 計(jì)算環(huán)境里，目標(biāo)對(duì)象是分片小表。傳統(tǒng)的集合運(yùn)算包括并、交、差、廣義笛卡爾積4 種運(yùn)算。在此基礎(chǔ)上，本文給出MapReduce 并行計(jì)算環(huán)境下，列存儲(chǔ)系統(tǒng)的專門關(guān)系代數(shù)。

定義1 在基于列存儲(chǔ)的MapReduce 并行環(huán)境下，設(shè)關(guān)系R 具有k 元屬性A1，A2，…，Ak而屬性Ai，i=1，2，…，k 分割后分布存儲(chǔ)在m 個(gè)節(jié)點(diǎn)上，那么屬性Ai 的分量就可以用Ai1，Ai2，…，Aim表示。即Ai的形式定義如下:

則關(guān)系R 的形式定義如下:

定義2(rowid) 為了重組列存儲(chǔ)的行數(shù)據(jù)，每一列都要附加偽列rowid，形如(rowid，value)。

定義3 分布存儲(chǔ)分量

設(shè)關(guān)系R 具有k 元屬性，有n 個(gè)元組。將每列分量Ai，i=1，2，…，k;存在m 個(gè)節(jié)點(diǎn)上，則除去最后一個(gè)分量的元組數(shù)為t=n%m，其他每個(gè)分量的元組數(shù)都為t=n/m，其數(shù)據(jù)記為aji，j=1，2，…，t;令bj為aij對(duì)應(yīng)的rowid 偽列，則這些切分后的數(shù)據(jù)分量的形式定義如下:

定義4 投影

由于是列存儲(chǔ)，沒(méi)有實(shí)際意義投影操作，只需把所有節(jié)點(diǎn)的列Ai1，Ai2，…，Aim并在一起就得到所需屬性。

定義5 選擇

屬性Ai關(guān)于公式F 的選擇操作的形式定義如下:

通過(guò)σi(R)可以得到滿足公式F 對(duì)屬性Ai的所有rowid。那么關(guān)系R 關(guān)于公式F 的選擇操作形式定義為:

定義6 自然連接

設(shè)有2 個(gè)關(guān)系R 和S，R 和S 的公共屬性是A1，A2，…，Ak，那么首先要把這些屬性的分量組合起來(lái)，計(jì)算R×S，那么自然連接操作的定義為:

4 面向大數(shù)據(jù)的分布式計(jì)算模型

本節(jié)針對(duì)大數(shù)據(jù)分析處理，在MapReduce 分布式環(huán)境下，設(shè)計(jì)了基于列的分布式文件存儲(chǔ)格式，數(shù)據(jù)的分布式加載以及利用協(xié)同定位方法對(duì)數(shù)據(jù)存儲(chǔ)進(jìn)行優(yōu)化。

4.1 MCF 存儲(chǔ)格式

針對(duì)MapReduce 分布式計(jì)算環(huán)境，本文在底層設(shè)計(jì)了一個(gè)新的文件存儲(chǔ)格式MCF(MapReduce Column-store File)，即基于MapReduce 的分布式列存儲(chǔ)格式，其示意圖如圖2 所示。對(duì)于Facebook 設(shè)計(jì)的Hive［12］文件存儲(chǔ)格式RCFile［13］，它采用行存儲(chǔ)，每個(gè)關(guān)系模式按照行組，存儲(chǔ)在RCFile 中，而本文提出MCF 采用列存儲(chǔ)，避免提取關(guān)系表中的無(wú)關(guān)屬性，相對(duì)RCFile，其大數(shù)據(jù)查詢效率提高明顯。

在MCF 中，每一列都附加一個(gè)偽列rowid，每個(gè)塊包含固定數(shù)量的記錄，稱為M 值。因?yàn)閷傩灶愋痛笮∈强勺兊?，每個(gè)邏輯塊的多少n 不同。塊存儲(chǔ)在緩沖區(qū)。緩沖區(qū)的大小通常為1 MB。當(dāng)緩沖區(qū)大小超出閾值或緩沖區(qū)中的記錄數(shù)達(dá)到m 個(gè)，緩沖區(qū)刷新到HDFS 中。每塊的起始偏移量被記錄下來(lái)。使用MCPage 代表在文件系統(tǒng)的分區(qū)單位。在文獻(xiàn)［15］中指出HDFS(Hadoop 分布式文件系統(tǒng))中，每個(gè)輸入的數(shù)據(jù)文件將切成塊(HDFS Block)，MCPage 存儲(chǔ)在HDFS Block 中，從而MCPage 在不同的數(shù)據(jù)節(jié)點(diǎn)復(fù)制。在HDFS，默認(rèn)MCPage 大小為64 MB。MCPage 包含多個(gè)數(shù)據(jù)塊，由記錄m 的值和每個(gè)記錄的大小確定。

MCF 在表掃描通過(guò)避免沒(méi)必要列值讀取來(lái)優(yōu)化讀取，它在分布式集群環(huán)境下優(yōu)于按行存儲(chǔ)結(jié)構(gòu)。同時(shí)，MCF 是基于列存儲(chǔ)的壓縮，因此，有很高的空間利用率。

4.2 數(shù)據(jù)分布式加載

本文提出按照MCF 文件格式，將數(shù)據(jù)通過(guò)分片方法構(gòu)造分布存儲(chǔ)分量A'ij，從而分別導(dǎo)入到每個(gè)MCPage 的數(shù)據(jù)塊中。

在HDFS 中默認(rèn)splitSize 等于HDFS blockSize的默認(rèn)值(64 MB)。而InputSplit 是MapReduce 對(duì)文件進(jìn)行處理和運(yùn)算的輸入單位，只是一個(gè)邏輯概念，每個(gè)InputSplit 并沒(méi)有對(duì)文件實(shí)際的切割，只是記錄了要處理的數(shù)據(jù)的位置和長(zhǎng)度。

如果按照默認(rèn)的順序數(shù)據(jù)加載方法，必然存在一行記錄被劃分到不同的Block，甚至不同的DataNode。根據(jù)定義3，通過(guò)分析FileInputFormat 里面的getSplits 方法，某一行記錄同樣也可能被劃分到不同的InputSplit。對(duì)輸入的文檔進(jìn)行預(yù)處理，讀取前N 行做為一個(gè)splits，通過(guò)重寫FileSplit，定義一個(gè)split 的大小是1 KB 個(gè)字節(jié)，這樣就可以將輸入的文檔進(jìn)行分片。最終實(shí)現(xiàn)A'ij的構(gòu)造。

4.3 協(xié)同定位優(yōu)化策略

本文提出數(shù)據(jù)存儲(chǔ)的協(xié)同定位策略，其示意圖如圖3 所示。對(duì)于那些數(shù)據(jù)量非常龐大的事實(shí)表，如lineorder 表，往往跨越許多的HDFS 塊，通常在每個(gè)節(jié)點(diǎn)上分割存儲(chǔ)，不做復(fù)制，而對(duì)于數(shù)據(jù)量相對(duì)較小的維表，如supplier，customer，part，date 表，協(xié)同定位優(yōu)化策略將其在每個(gè)節(jié)點(diǎn)都復(fù)制一份，使得可以分布連接和聚集運(yùn)算直接在本機(jī)運(yùn)算即可，因此，大大減少了節(jié)點(diǎn)之間網(wǎng)絡(luò)傳送次數(shù)和時(shí)間，提高了4.1 節(jié)分布聚集效率，查詢性能優(yōu)化明顯。

圖3 協(xié)同定位優(yōu)化策略示意圖

5 基于列存儲(chǔ)的MapReduce 并行連接算法

本節(jié)對(duì)與基于列存儲(chǔ)的MapReduce 并行連接算法從分片聚集和子連接的啟發(fā)式優(yōu)化2 個(gè)方面，闡述了算法的具體實(shí)現(xiàn)。

5.1 分片聚集方法

基于列存儲(chǔ)的MapReduce 并行連接算法，其示意圖如圖4 所示。為了充分調(diào)用集群所有機(jī)器的計(jì)算資源，實(shí)現(xiàn)數(shù)據(jù)的并行連接，在查詢計(jì)劃執(zhí)行的Map 階段，本文提出分片聚集方法。

圖4 并行連接查詢計(jì)劃示意圖

(1)抽取:按照定義6 并行連接操作，在集群中的多個(gè)機(jī)器上分別執(zhí)行完之后，得到子連接結(jié)果，傳給分片聚集階段。

(2)分片聚集:在這個(gè)階段，對(duì)每個(gè)子連接結(jié)果計(jì)算聚集。從而利用分片方法來(lái)減少數(shù)據(jù)量。提高并行計(jì)算能力。而且在多查詢?nèi)蝿?wù)時(shí)，分片聚集結(jié)果還可以重用。

(3)分布:對(duì)前階段的結(jié)果，按照查詢語(yǔ)句的分組條件，被重分配到各個(gè)分組中。這使所有具有相同的查詢字符串的結(jié)果分配到到同一個(gè)Map 任務(wù)。從而完成GROUP BY 字句要求的對(duì)查詢結(jié)果進(jìn)行分組實(shí)現(xiàn)。

(4)全聚集:每個(gè)分區(qū)即每個(gè)Map 任務(wù)，通過(guò)合并計(jì)算具有相同的查詢字符串的查詢結(jié)果，從而得到最終聚集結(jié)果。例如:得到count (*)結(jié)果。

(5)過(guò)濾:通過(guò)過(guò)濾掉HAVING 字句中的組條件，例如:count(*)＞50，計(jì)數(shù)小于50 的將不會(huì)傳入Reduce 階段。

(6)排序:調(diào)用hadoop 的排序算法，本文使用TeraSort 算法，對(duì)剩余的結(jié)果按照ORDER BY 字句的要求分別并行排序。

(7)合并:每個(gè)Reducer 進(jìn)行合并操作對(duì)所有分區(qū)排序的結(jié)果的合并在一起，輸出最終結(jié)果。

(8)輸出:最終的結(jié)果是輸出為MCF 文件。

5.2 子連接的啟發(fā)式優(yōu)化方法

在并行連接過(guò)程中，對(duì)于每個(gè)節(jié)點(diǎn)本地執(zhí)行的連接任務(wù)，本文利用前期研究成果［14］:啟發(fā)式優(yōu)先方法對(duì)關(guān)系運(yùn)算進(jìn)行優(yōu)化。

本文啟發(fā)式優(yōu)化的基本思想是:首先執(zhí)行最具限制性的選擇和連接操作。具體優(yōu)化策略為:盡可能早地執(zhí)行選擇操作;盡可能早地執(zhí)行投影操作;同列謂詞的下推能盡早減少所需處理的元組數(shù)目。而由于同表列的rowid 唯一且一致，優(yōu)先執(zhí)行同表列的連接能有效減少中間結(jié)果的規(guī)模，因此Map 階段產(chǎn)生的中間結(jié)果之和較小的計(jì)劃一般是最優(yōu)的?；趩l(fā)式優(yōu)化的查詢計(jì)劃示意圖如圖5 所示。

圖5 基于啟發(fā)式優(yōu)化的查詢計(jì)劃示意圖

6 實(shí)驗(yàn)驗(yàn)證

本文實(shí)驗(yàn)采用課題組開發(fā)的基于列存儲(chǔ)的MapReduce 大數(shù)據(jù)并行處理原型系統(tǒng) HCMS(Hadoop Column-store Management System)為算法測(cè)試平臺(tái)，采用國(guó)際通用的SSB 測(cè)試數(shù)據(jù)集，對(duì)算法進(jìn)行測(cè)試，從而驗(yàn)證其高效性和可擴(kuò)展性。

6.1 實(shí)驗(yàn)環(huán)境

本文系統(tǒng)驗(yàn)證要求與原有單機(jī)環(huán)境不同，對(duì)計(jì)算機(jī)數(shù)量有更高要求。實(shí)驗(yàn)系統(tǒng)運(yùn)行在課題組實(shí)驗(yàn)室選取的50 臺(tái)普通計(jì)算機(jī)組成測(cè)試集群，每個(gè)節(jié)點(diǎn):4 核CPU，4 GB 主存，1 塊500 GB SATA 硬盤，每臺(tái)機(jī)器的操作系統(tǒng)都是Redhat Linux 6.1。網(wǎng)絡(luò)環(huán)境為1 GB 以太網(wǎng)交換機(jī)組成的局域網(wǎng)。本文實(shí)驗(yàn)使用的軟件，如表1 所示。其中，DBMS3.0 為課題組前期列存儲(chǔ)數(shù)據(jù)庫(kù)研究成果。

表1 實(shí)驗(yàn)軟件環(huán)境

實(shí)驗(yàn)規(guī)劃每個(gè)Datanode 分配6 個(gè)map 任務(wù)和2 個(gè)reducer 任務(wù)。HDFS 數(shù)據(jù)塊大小設(shè)置為256 MB，MapReduce 查詢執(zhí)行器使用全局內(nèi)存大小設(shè)置為1 GB。

測(cè)試節(jié)點(diǎn)從10 個(gè)節(jié)點(diǎn)開始增加到50 個(gè)，記錄每個(gè)測(cè)試數(shù)據(jù)集合和測(cè)試查詢語(yǔ)句執(zhí)行時(shí)間和日志。每次測(cè)試完后，需要對(duì)集群HDFS 重新格式化。

6.2 測(cè)試數(shù)據(jù)集

實(shí)驗(yàn)采用國(guó)際通用的星型模式基準(zhǔn)SSB［15］中定義的測(cè)試數(shù)據(jù)集進(jìn)行大數(shù)據(jù)處理的實(shí)驗(yàn)驗(yàn)證，生成的星型模式下的真實(shí)數(shù)據(jù)集和基于MapReduce 的大數(shù)據(jù)并行處理原型系統(tǒng)考慮的大數(shù)據(jù)測(cè)試目標(biāo)相吻合。

實(shí)驗(yàn)將用SSB 提供的數(shù)據(jù)產(chǎn)生器DBgen 生成了SSB 的數(shù)據(jù)集實(shí)例。每個(gè)實(shí)例數(shù)據(jù)集的大小是用增量因子控制的，記為SF，選用SF=1，數(shù)據(jù)集大小為1 GB，初始lineorder 表數(shù)據(jù)量為6 000 000 行，如表2 所示。實(shí)驗(yàn)逐步增加SF，生成數(shù)據(jù)集從10 GB，100 GB 到1 TB。分別記錄每次測(cè)試結(jié)果。

表2 實(shí)驗(yàn)測(cè)試數(shù)據(jù)

6.3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)1 各個(gè)測(cè)試語(yǔ)句性能對(duì)比

選取SSB 的連接語(yǔ)句測(cè)試Q1.1，簡(jiǎn)單聚集任務(wù)測(cè)試Q2.1 以及復(fù)雜聚集任務(wù)測(cè)試Q3.1 和Q4.1 作為基礎(chǔ)測(cè)試語(yǔ)句，在全部節(jié)點(diǎn)都啟用的條件下，通過(guò)對(duì)100 GB 數(shù)據(jù)分別測(cè)試10 次，計(jì)算平均值，其結(jié)果如圖6 所示。

圖6 各個(gè)測(cè)試語(yǔ)句性能對(duì)比圖

由于采用了分片聚集算法，在聚集任務(wù)Q3.1 和Q4.1，特別是復(fù)雜聚集任務(wù)，本文算法優(yōu)化明顯。

實(shí)驗(yàn)2 數(shù)據(jù)量變化下性能對(duì)比

選取SSB 的Q2.2 作為基礎(chǔ)測(cè)試語(yǔ)句，在全部節(jié)點(diǎn)都啟用的條件下，通過(guò)對(duì)10 GB，100 GB 和1 TB數(shù)據(jù)分別測(cè)試10 次，計(jì)算平均值，其性能對(duì)比圖如圖7所示。測(cè)試系統(tǒng)，在大數(shù)據(jù)條件下的運(yùn)行負(fù)載能力。從圖7 中可看出，當(dāng)數(shù)據(jù)量增加時(shí)，DWMS 執(zhí)行時(shí)間增長(zhǎng)明顯，而Hive 和HCMS 則較平緩，充分驗(yàn)證了并行執(zhí)行的優(yōu)越性。當(dāng)負(fù)載增大到1 TB 時(shí)，HCMS性能比Hive 提高26.2%，由此充分驗(yàn)證了同時(shí)使用MCF 列存儲(chǔ)結(jié)構(gòu)和分片聚集能更大提升并行連接的有效性，使得查詢效率更高。

圖7 數(shù)據(jù)量變化下性能對(duì)比

實(shí)驗(yàn)3 集群數(shù)量變化下性能對(duì)比

選取SSB 的Q2.2 作為基礎(chǔ)測(cè)試語(yǔ)句，選擇100 GB數(shù)據(jù)，通過(guò)對(duì)集群Datanode 節(jié)點(diǎn)數(shù)從10 個(gè)、20 個(gè)、30 個(gè)、40 個(gè)，增加到50 個(gè)，重新格式化后，分別測(cè)試10 次，計(jì)算平均值，其性能對(duì)比如圖8 所示。列存儲(chǔ)數(shù)據(jù)倉(cāng)庫(kù)管理系統(tǒng)DWMS 不是并行分布式系統(tǒng)，本次測(cè)試實(shí)驗(yàn)中未使用。

圖8 集群數(shù)量變化下性能對(duì)比

由圖8 可以看出，隨著運(yùn)算節(jié)點(diǎn)數(shù)目的增加，HCMS 比Hive 執(zhí)行時(shí)間不斷減少，從10 個(gè)節(jié)點(diǎn)的相差15.8%，減少到50 個(gè)節(jié)點(diǎn)的26.3%。從而驗(yàn)證了算法性能優(yōu)化明顯。另一方面也證實(shí)了算法的可擴(kuò)展性。

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

基于列存儲(chǔ)的MapReduce 并行連接算法分析了MapReduce 并行環(huán)境列存儲(chǔ)連接與單機(jī)環(huán)境列存儲(chǔ)的區(qū)別，根據(jù)面向大數(shù)據(jù)的分布式計(jì)算模型“大而化小，分而治之”的設(shè)計(jì)思路，從而為大數(shù)據(jù)查詢分析處理提供了有效的解決方案。本文算法在面向大數(shù)據(jù)的分布式計(jì)算模型基礎(chǔ)上，利用協(xié)同定位實(shí)現(xiàn)存儲(chǔ)優(yōu)化。從分片聚集和子連接啟發(fā)式優(yōu)化2 個(gè)方面構(gòu)造了并行連接算法的具體實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果證明，該算法有效地減少了MapReduce 過(guò)程的中間數(shù)據(jù)和不必要的I/O 開銷。此外，由于利用了模型的可擴(kuò)展性特點(diǎn)，無(wú)論在執(zhí)行時(shí)間還是負(fù)載能力上，都有較好的性能表現(xiàn)，明顯提高了大數(shù)據(jù)運(yùn)算的效率。下一步的工作重點(diǎn)將轉(zhuǎn)向列存儲(chǔ)的MapReduce 連接索引技術(shù)的研究，對(duì)適用于列存儲(chǔ)的MapReduce 各種索引進(jìn)行分析，使MapReduce 大數(shù)據(jù)查詢性能得到進(jìn)一步的優(yōu)化。

［1］Dean J，Ghemawat S.MapReduce:Simplified Data Processing on Large Clusters［C］//Proc.of OSDI'04.San Francisco:［s.n.］，2004:137-150.

［2］Abadi D J，Madden S R，Hachem N.Column-stores vs.Row-stores:How Different Are They Really?［C］//Proc.of ACM SIGMOD'08.Vancouver，Canada:ACM Press，2008:967-980.

［3］Stonebraker M，Abadi D J，Batkin A，et al.C-store:A Column-oriented DBMS ［C］//Proc.of VLDB Conference.Trondheim，Norway:［s.n.］，2005:553-564.

［4］Boncz P，Zukowski M，Nes N.MonetDB/X100:Hyperpipelining Query Execution［C］//Proc.of CIDR'05.Asilomar，USA:ACM Press，2005:251-264.

［5］Blanas S，Patel J M，Ercegovac V，et al.A Comparison of Join Algorithms for Log Processing in MapReduce［C］//Proc.of ACM SIGMOD International Conference on Management of Data.Indianapolis，USA:ACM Press，2010:975-986.

［6］Abouzeid A，Bajda-Pawlikowski K，Abadi D J，et al.HadoopDB:An Architectural Hybrid of MapReduce and DBMS Technologies for Analytical Workloads［C］//Proc.of VLDB Conference.Lyon，F(xiàn)rance:［s.n.］，2009:922-933.

［7］Bajda-Pawlikowski K，Abadi D J，Silberschatz A，et al.Efficient Processing of Data Warehousing Queries［C］//Proc.of ACM SIGMOD International Conference on Management of Data.Athens，Greece:ACM Press，2011:1165-1176.

［8］Lin Yuting，Agrawal D，Chen Chun，et al.Llama:Leveraging Columnar Storage for Scalable Join Processing in the MapReduce Framework［C］//Proc.of ACM SIGMOD International Conference on Management of Data.Athens，Greece:ACM Press，2011:961-972.

［9］Floratou A，Patel J M，Shekita E J.Column-oriented Storage Techniques for MapReduce.The VLDB Journal，2011，4(7):419-429.

［10］覃雄派，王會(huì)舉，杜小勇，等.大數(shù)據(jù)分析——RDBMS與MapReduce 的競(jìng)爭(zhēng)與共生［J］.軟件學(xué)報(bào)，2012，23(1):32-45.

［11］師金鋼，鮑玉斌，冷芳玲，等.基于MapReduce 的關(guān)系型數(shù)據(jù)倉(cāng)庫(kù)并行查詢［J］.東北大學(xué)學(xué)報(bào):自然科學(xué)版，2011，32(5):626-629.

［12］Thusoo A，Sarma J S，Jain N，et al.Hive——A Warehousing Solution over a Map-reduce Framework［C］//Proc.of VLDB Conference.Lyon，F(xiàn)rance:［s.n.］，2009:1626-1629.

［13］He Yongqiang，Lee R，Yin Huai，et al.RCFile:A Fast and Space-efficient Data Placement Structure in MapReducebased Warehouse Systems［C］//Proc.of International Conference on Data Engineering.Hannover，Germany:IEEE Press，2011:1199-1208.

［14］嚴(yán)秋玲，孫 莉，王 梅，等.列存儲(chǔ)數(shù)據(jù)倉(cāng)庫(kù)中啟發(fā)式查詢優(yōu)化機(jī)制［J］.計(jì)算機(jī)學(xué)報(bào)，2011，10(34):2018-2026.

［15］O'Neil P，O' Neil B，Chen Xuedong.Star Schema Benchmark Revision3［EB/OL］.(2010-02-09).http://www.cs.umb.edu/～poneil.