基于MapReduce的大數(shù)據(jù)在線聚集優(yōu)化設(shè)計(jì)

李駿

(成都工業(yè)學(xué)院 教務(wù)處，四川 成都 611730)

大數(shù)據(jù)具備數(shù)據(jù)規(guī)模達(dá)到PB級(jí)別、數(shù)據(jù)組織形式多樣、數(shù)據(jù)增長(zhǎng)速率快、處理時(shí)間較為敏感等特征[1-3]. 伴隨互聯(lián)網(wǎng)應(yīng)用的飛速發(fā)展，大數(shù)據(jù)量呈現(xiàn)幾何式增長(zhǎng)態(tài)勢(shì)，在如此巨大的數(shù)據(jù)量中包含著具備極高價(jià)值度的信息資源，但是受到數(shù)據(jù)規(guī)模和內(nèi)存等因素限制，即使在云計(jì)算模式下，大數(shù)據(jù)的分析處理也無(wú)法滿足用戶實(shí)時(shí)交互需求. 為此快速、精準(zhǔn)挖掘大數(shù)據(jù)中潛在信息價(jià)值，對(duì)促進(jìn)各大行業(yè)進(jìn)步十分重要[4-5].

在線聚集具備快速、精準(zhǔn)獲取查詢估計(jì)結(jié)果的特點(diǎn)受到了學(xué)者的廣泛關(guān)注. 文獻(xiàn)[6]提出基于多維分層采樣的大數(shù)據(jù)在線聚集方法，解決了查詢出現(xiàn)小分組或低選擇率時(shí)產(chǎn)生的估計(jì)結(jié)果不準(zhǔn)確問(wèn)題；文獻(xiàn)[7]提出了基于POI的大數(shù)據(jù)在線聚集方法，利用興趣點(diǎn)為數(shù)據(jù)源，有效實(shí)現(xiàn)了數(shù)據(jù)的聚類.但這2種方法的大數(shù)據(jù)在線聚集執(zhí)行時(shí)間并不具備顯著優(yōu)勢(shì).

MapReduce是一種編程模型，其中心思想是“Map(映射)”和“Reduce(歸約)”，可用于大規(guī)模數(shù)據(jù)集的并行運(yùn)算. 為此本文提出基于MapReduce的大數(shù)據(jù)在線聚集優(yōu)化程序設(shè)計(jì)方法，進(jìn)一步提升大數(shù)據(jù)在線聚集執(zhí)行性能，更好地服務(wù)于大數(shù)據(jù)應(yīng)用，為大數(shù)據(jù)查詢處理的發(fā)展做出有益貢獻(xiàn).

1 基于MapReduce的大數(shù)據(jù)在線聚集優(yōu)化程序設(shè)計(jì)

1.1 基于列存儲(chǔ)的MapReduce大數(shù)據(jù)并行連接算法

通過(guò)分片聚集實(shí)現(xiàn)大數(shù)據(jù)的并行連接，并采用啟發(fā)式的優(yōu)化方法優(yōu)化各節(jié)點(diǎn)的子連接，綜合上述步驟實(shí)現(xiàn)了基于列存儲(chǔ)的MapReduce大數(shù)據(jù)并行連接. 在查詢計(jì)劃執(zhí)行的Map階段使用分片聚集方法，使集群中所有機(jī)器的計(jì)算資源得到充分調(diào)用，促使大數(shù)據(jù)的并行連接得以有效實(shí)現(xiàn)[8]，完成大數(shù)據(jù)在線聚集. 基于列存儲(chǔ)的MapReduce并行連接算法示意如圖1所示.

圖1 基于列存儲(chǔ)的MapReduce并行連接算法示意Fig.1 Schematic diagram of MapReduce parallel connection algorithm based on column storage

在并行連接算法中，分片聚集方法的查詢形式如下.

1)抽取：子連接結(jié)果是通過(guò)分別在集群之間的各機(jī)器上并行連接操作后得到，向分片聚集過(guò)程反饋?zhàn)舆B接結(jié)果.

2)分片聚集：每個(gè)子連接結(jié)果通過(guò)逐步計(jì)算實(shí)現(xiàn)聚集. 使得數(shù)據(jù)量通過(guò)分片方法得以減少，計(jì)算能力得以提高. 并且分片聚集結(jié)果可以在多查詢?nèi)蝿?wù)當(dāng)中重復(fù)使用.

3)分布：為了使有相同查詢字符串的結(jié)果能夠分到同一個(gè)Map任務(wù)，依照查詢語(yǔ)句的分組條件把之前的結(jié)果重新分到每個(gè)分組當(dāng)中. 查詢結(jié)果的分組實(shí)現(xiàn)也完成了GROUPBY字句要求.

4)全聚集：最終聚集結(jié)果中把每一個(gè)Map任務(wù)中具有相同查詢字符串的查詢結(jié)果進(jìn)行合并計(jì)算. 例如,得到count(*)結(jié)果.

5)過(guò)濾：過(guò)濾掉HAVING字句中的分組條件. 如,count(*)>50. Reduce階段不會(huì)輸入低于50的計(jì)算.

6)排序：剩余結(jié)果按照ORDER BY字句的要求，通過(guò)hadoop排序算法和TeraSort算法并行排序.

圖2 混合近似查詢框架Fig.2 hybrid approximate query framework

7)合并：最終結(jié)果是通過(guò)融合全部分區(qū)排序結(jié)果，以及各Reducer實(shí)現(xiàn)合并處理獲取.

8)輸出.

大數(shù)據(jù)在線聚集并行連接過(guò)程中，采用啟發(fā)式優(yōu)化方法來(lái)優(yōu)化各節(jié)點(diǎn)本地執(zhí)行連接任務(wù)關(guān)系運(yùn)算. 啟發(fā)式優(yōu)化的基本思想是：最具限制性的選擇和連接操作最先完成[9-10]. 優(yōu)化策略：優(yōu)先執(zhí)行選擇操作；優(yōu)先執(zhí)行投影操作；優(yōu)先采用同列謂詞的下推控制元組數(shù)目縮減. 中間結(jié)果的規(guī)模因?yàn)橥斜淼膔owid唯一又一致，被同表列連接的優(yōu)先執(zhí)行大大減少. 因此最優(yōu)的計(jì)劃是Map階段產(chǎn)生的中間結(jié)果之和較少的計(jì)劃[11-13].

1.2 大數(shù)據(jù)在線聚集動(dòng)態(tài)切換機(jī)制

以增強(qiáng)上述并行連接過(guò)程中大數(shù)據(jù)在線聚集有效性以及穩(wěn)定性，最大限度降低大數(shù)據(jù)在線聚集估計(jì)失效對(duì)度在線聚集執(zhí)行性能的干擾為出發(fā)點(diǎn)，利用引入動(dòng)態(tài)切換機(jī)制的混合近似查詢框架，對(duì)傳統(tǒng)在線聚集近似失效概率實(shí)施估計(jì)，完成2種近似查詢模式切換的同時(shí)，縮減因估計(jì)失效降低導(dǎo)致的執(zhí)行性能低下問(wèn)題以及非必須全局掃描[14-16]. 其中在線聚集動(dòng)態(tài)切換機(jī)制采用漸進(jìn)式近似估計(jì)方法，通過(guò)完善各輪估計(jì)所需樣本量，縮減動(dòng)態(tài)切換誤判率，實(shí)現(xiàn)在線聚集優(yōu)化設(shè)計(jì).

1.2.1 混合近似查詢框架

混合近似查詢框架主要包括3部分，分別為在線聚集執(zhí)行模式、近似查詢模式以及動(dòng)態(tài)切換機(jī)制， 如圖2所示.

1)在線聚集執(zhí)行模式

假設(shè)來(lái)自于HDFS(Hadoop分布式文件系統(tǒng))的一組隨機(jī)樣本為S，在線聚集執(zhí)行模式利用近似估計(jì)方法，近似估計(jì)查詢結(jié)果[17-19]. 如果結(jié)果符合用戶對(duì)精度的要求則將結(jié)果直接輸出至用戶，如果結(jié)果不符合用戶對(duì)精度的要求，那么需要增加樣本量，構(gòu)建全新樣本集S′=S+ΔS，繼續(xù)采用近似估計(jì)方法對(duì)其展開近似估計(jì)，直至查詢結(jié)果符合用戶精度要求，完成查詢結(jié)果精度完善.

2)動(dòng)態(tài)切換機(jī)制

混合近似查詢框架的重點(diǎn)部分為動(dòng)態(tài)切換機(jī)制，可以有效監(jiān)控在線聚集執(zhí)行模式中各項(xiàng)查詢工作的執(zhí)行進(jìn)程并獲取近似估計(jì)失效概率的預(yù)測(cè)結(jié)果，并以此為依據(jù)，將在線聚集執(zhí)行模式動(dòng)態(tài)切換至近似查詢模式，解決估計(jì)失效問(wèn)題以及非必要全局掃描.

1.2.2 基于漸進(jìn)近似估計(jì)的動(dòng)態(tài)切換機(jī)制

混合近似查詢的執(zhí)行性能會(huì)受動(dòng)態(tài)切換的誤判率影響，是因?yàn)閎ootstrap近似查詢部分的執(zhí)行開銷高于在線聚集查詢部分. 只有通過(guò)降低查詢切換誤判率才能提高混合近似查詢的執(zhí)行性能. 在線聚集近似估計(jì)的有效結(jié)果，通過(guò)估計(jì)失效概率pf達(dá)到最大值前獲取估計(jì)結(jié)果是減少查詢切換誤判率的有效處理措施[23-25]，依據(jù)該種措施提出漸進(jìn)式的近似估計(jì)方法，調(diào)整各輪樣本量確保誤判率最小. 似估計(jì)次數(shù)利用改進(jìn)各輪近似估計(jì)樣本需求量的增多，使得額外進(jìn)行估計(jì)開銷與在線聚集查詢?cè)谕粫r(shí)間解決.

漸進(jìn)近似估計(jì)有以下幾個(gè)步驟：先把近似估計(jì)周期用n個(gè)固定大小的樣本量代表;將n分割成l個(gè)子區(qū)間，各子區(qū)間的樣本量是ni；ni個(gè)樣本需要在線聚集的第i輪近似估計(jì)采集，即ΔSi=ni. 劃分方式見公式(1).

當(dāng)前樣本統(tǒng)計(jì)量的結(jié)果E(ΔSi)，會(huì)在第i輪近似估計(jì)中對(duì)采集到的ΔSi個(gè)樣本實(shí)行統(tǒng)計(jì)獲取. 在樣本量擴(kuò)大到ΔSi+1時(shí)計(jì)算E(ΔSi+1)統(tǒng)計(jì)量，與之前E(ΔSi)統(tǒng)計(jì)量結(jié)果合并完成當(dāng)前樣本的近似估計(jì)，使結(jié)果達(dá)到用戶對(duì)樣本近似估計(jì)精度的需求.

2 實(shí)驗(yàn)分析

搭建Hadoop環(huán)境，選取40臺(tái)普通計(jì)算機(jī)構(gòu)建測(cè)試集群，在集群上部署本文方法設(shè)計(jì)的基于MapReduce的大數(shù)據(jù)在線聚集優(yōu)化程序，實(shí)現(xiàn)大數(shù)據(jù)在線聚集相關(guān)基本功能. 測(cè)試集群中節(jié)點(diǎn)CPU為4核，內(nèi)存大小為4GB，硬盤大小為500 GB機(jī)械硬盤. 同時(shí)設(shè)置漸進(jìn)近似估計(jì)參數(shù)n=1 000，l=3. 為驗(yàn)證本文方法設(shè)計(jì)優(yōu)化程序的有效性，選取基于多維分層采樣方法[6]、基于POI方法[7]作為本文方法對(duì)比方法，從不同角度驗(yàn)證本文方法優(yōu)勢(shì).

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

為驗(yàn)證數(shù)據(jù)量大小對(duì)大數(shù)據(jù)在線聚集時(shí)間的影響，選擇數(shù)據(jù)量大小分別為15 GB、150 GB、1.5 TB數(shù)據(jù)，統(tǒng)計(jì)3種方法的大數(shù)據(jù)聚集時(shí)間，在節(jié)點(diǎn)全部使用情況下，分別采用了不同的數(shù)據(jù)對(duì)3種方法各測(cè)試15次，算出平均值，3種方法大數(shù)據(jù)聚集時(shí)間對(duì)比結(jié)果見圖3.

圖3 大數(shù)據(jù)聚集時(shí)間對(duì)比Fig.3 Comparison of big data aggregation time

從圖3 中可以看出，數(shù)據(jù)量的數(shù)值變化對(duì)3種方法聚集時(shí)間有明顯影響. 隨著數(shù)據(jù)量的增加，基于多維分層采樣方法的執(zhí)行時(shí)間不穩(wěn)定，呈現(xiàn)大幅度增加趨勢(shì)；基于POI方法的執(zhí)行時(shí)間相對(duì)穩(wěn)定；而隨著數(shù)據(jù)量的增加本文方法的執(zhí)行時(shí)間變化最平穩(wěn)，且顯著低于2種對(duì)比方法. 因此實(shí)驗(yàn)充分證明了本文方法在大數(shù)據(jù)聚集時(shí)間方面具備顯著穩(wěn)定性和性能優(yōu)越性.

2.2 基本頻繁查詢性能對(duì)比

為驗(yàn)證3種方法的基本頻繁查詢性能，在用戶查詢?nèi)蝿?wù)集合中選取連接語(yǔ)句測(cè)試數(shù)據(jù)P1、簡(jiǎn)單聚集任務(wù)測(cè)試數(shù)據(jù)P2、復(fù)雜聚集任務(wù)測(cè)試數(shù)據(jù)P3和P4作為查詢測(cè)試樣本，設(shè)置查詢次數(shù)為30次，頻繁查詢周期為5，統(tǒng)計(jì)節(jié)點(diǎn)數(shù)量為60個(gè)，數(shù)據(jù)量大小為150 GB條件下，3種方法的計(jì)算執(zhí)行時(shí)間均值，結(jié)果如圖4所示.

圖4 3種方法基本頻繁查詢性能對(duì)比Fig.4 Performance comparison of three methods for basic frequent query

分析圖4可知，本文方法的計(jì)算執(zhí)行均值優(yōu)勢(shì)較為顯著，尤其是在復(fù)雜聚集任務(wù)P3和P4條件下，本文方法相比基于多維分層采樣方法的計(jì)算執(zhí)行時(shí)間均值節(jié)省25.3%，相比基于POI方法節(jié)省48.3%. 實(shí)驗(yàn)結(jié)果充分體現(xiàn)了本文方法的基本頻繁查詢性能優(yōu)勢(shì).

3 結(jié)論

本文從MapReduce并行連接和在線聚集動(dòng)態(tài)切換機(jī)制2個(gè)角度對(duì)大數(shù)據(jù)在線聚集進(jìn)行了優(yōu)化設(shè)置，實(shí)現(xiàn)了大數(shù)據(jù)的快速在線聚集，提升了大數(shù)據(jù)在線聚集性能,并通過(guò)一系列實(shí)驗(yàn)驗(yàn)證了本文方法的性能優(yōu)勢(shì).今后可以從簡(jiǎn)化構(gòu)造方法入手，使本文方法更加完善，并且結(jié)合其他的理論方法，擴(kuò)大研究對(duì)象的范圍，以便更好地應(yīng)對(duì)大數(shù)據(jù)時(shí)代，為促進(jìn)各行業(yè)發(fā)展奠定基礎(chǔ).