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

李駿

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8)輸出.

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

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

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

1.2.1 混合近似查詢框架

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

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

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

2)動態(tài)切換機制

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

1.2.2 基于漸進近似估計的動態(tài)切換機制

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

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

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

2 實驗分析

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

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

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

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

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

2.2 基本頻繁查詢性能對比

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

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

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

3 結(jié)論

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