□文/楊茂保（九江學(xué)院江西·九江）

大數(shù)據(jù)信息處理的MinMapReduce算法

□文/楊茂保
（九江學(xué)院江西·九江）

［提要］M apReduce對于大數(shù)據(jù)來說是主要的并行計算模型，理想情況下，M apReduce系統(tǒng)要在機器之間實現(xiàn)高度的負載均衡，并且最小化空間使用、CPU和I/O時間和每個機器上的網(wǎng)絡(luò)傳輸。本文提出最小算法的概念，也就是算法能保證同一時間在多個方面的最好并行化，對于一組基本數(shù)據(jù)庫問題來說，我們說明了最小算法的存在，通過實驗我們證明了良好的性能。

M apReduce；M i nM apReduce；負載均衡

原標題：大數(shù)據(jù)信息處理的M i nM apReduce算法設(shè)計與實現(xiàn)

收錄日期：2016年9月13日

一、引言

隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)以空前的速度在積累，對大數(shù)據(jù)信息處理提出了迫切的需求，級別達到T字節(jié)或者更高規(guī)模的巨大數(shù)據(jù)庫、大數(shù)據(jù)具有規(guī)模巨大、分布廣泛、動態(tài)演變、模態(tài)多樣、關(guān)聯(lián)復(fù)雜、真?zhèn)坞y辨等特性。對復(fù)雜數(shù)據(jù)的直觀理解為挖掘出可靠而更有價值的信息，當前處理有限規(guī)模數(shù)據(jù)的計算體系已然失效。近年來，數(shù)據(jù)庫研究人員對這一挑戰(zhàn)做出來回應(yīng)：構(gòu)建巨大的并行計算平臺，其使用數(shù)百甚至數(shù)千臺商用機器，吸引了大量研究人員注意的著名的平臺是MapReduce。MinMapReduce算法是一種新興的有極大發(fā)展?jié)摿Φ乃惴?，MinMapReduce算法與許多傳統(tǒng)數(shù)學(xué)分支相比具有很強的實時性，將其應(yīng)用于大數(shù)據(jù)處理具備一定的理論和實踐意義。

在一個高的級別，一個MapReduce系統(tǒng)包含很多無共享的機器，它們只通過在網(wǎng)絡(luò)上發(fā)送消息來進行通信，一個MapReduce算法命令這些機器協(xié)作地來執(zhí)行一個計算任務(wù)。最初，輸入數(shù)據(jù)集被分布在這些機器上，主要是以非復(fù)制的方式，也就是，每個對象在一個機器上，算法以循環(huán)（有時在一些文獻中稱為jobs）的方式執(zhí)行，每一個都有三個階段：map，shuffle，和refuce，前兩個使機器來交換數(shù)據(jù)：在map階段，每個機器準備把消息傳遞給其他機器，在shuffle階段，進行實際的數(shù)據(jù)傳輸，在reduce階段沒有網(wǎng)絡(luò)通信發(fā)生，在此階段每個機器執(zhí)行來自本地存儲的計算，在reduce階段完成后，當前循環(huán)結(jié)束，如果計算任務(wù)沒有結(jié)束，另一個循環(huán)開始。

MapReduce的目標是高的負載均衡，最小化空間、CPU、I/O和每個機器的網(wǎng)絡(luò)開銷，以前的做法相對少地關(guān)注在不同的性能指標上執(zhí)行嚴格的限制，本文旨在研究算法，在多方面同時來突出效率。

二、M i nM apReduce算法的定義

最小MapReduce算法（MinMapReduce算法），S表示相關(guān)問題的輸入對象的集合，n表示問題基數(shù)，即S中的對象個數(shù)，t表示系統(tǒng)中使用的機器數(shù)，定義m=n/t，即m表示每個機器上的對象個數(shù)（S均勻地分布在機器上），考慮解決S上的一個問題的算法，如果一個算法具有如下特性我們就說這個算法是最小的。

（1）最小占有空間：每個機器始終使用O（m）的存儲空間。

（2）有限的網(wǎng)絡(luò)通信：在每一個循環(huán)中，每個機器通過網(wǎng)絡(luò)最多發(fā)送或者接收O（m）個字。

（3）常數(shù)個循環(huán)：算法必須在常數(shù)個循環(huán)之后終止。

（4）優(yōu)化計算：每個機器總共只執(zhí)行O（Tseq/t）數(shù)量的計算（也就是所有的循環(huán)求和），其中Tseq是在一個序列機上解決相同問題的時間。首先，每個機器總是占有數(shù)據(jù)集S的O（1/t），這可以有效地防止分區(qū)傾斜，分區(qū)傾斜會使一些機器被迫處理超過m個對象，這是在MapReduce中低效率的一個主要原因；其次，有限網(wǎng)絡(luò)通信時間保證，每個循環(huán)的shuffle階段轉(zhuǎn)移至多O（mt）=O（n）個字，這個階段的持續(xù)時間大致等于一個機器發(fā)送或者接收O（m）個字的時間，因為機器間的數(shù)據(jù)傳送是并行的；第三，常數(shù)循環(huán)，這個不是新的性質(zhì)，因為這也是先前的MapReduce算法的目標，優(yōu)化技術(shù)重復(fù)了最初的MapReduce動機，t時間完成一個計算任務(wù)，比使用單個機器要快。

本文的核心包括最小算法的兩個問題：

排序：輸入是取自一個有序域的n個對象的一個集合S，當這個算法結(jié)束，所有的對象必須按排序的方式分布在t個機器上，也就是，我們可以從1到t來命令機器，以使機器i上的對象領(lǐng)先于機器j上的對象，其中，1≤i≤j≤t。

滑動聚合，輸入包含：

——來自一個有序域的n個對象的一個集合S，其中每個對象o∈S與一個數(shù)值權(quán)重有關(guān)

——一個整數(shù)ι≤n

——一個分布聚合函數(shù)AGG（比如，sum，max，min）

用window（o）表示S中ι個不超過o的最大對象的集合，o的window聚合是將AGG應(yīng)用于window（o）中的對象權(quán)值，滑動聚合是用來報告S中的每一個對象的window聚合。

在圖1中，ι=5，黑點表示S中的對象，黑點上面的數(shù)值表示與對象相關(guān)的權(quán)值，圖中的window（o），對于AGG=sum和max，window聚合分別為55和20。（圖1）

圖1　Sl i di ng aggregat es

排序的重要性是很明顯的：這個問題的一個最小算法可以導(dǎo)致幾個基本數(shù)據(jù)庫問題（包括排名、分組、半連接和分類屬性）的最小算法。

第二個問題的重要性需要一點解釋，滑動聚合在時間序列的研究中很重要，例如，考慮記錄納斯達克股市的歷史指標中，需要每分鐘一個數(shù)值，用來檢驗動態(tài)統(tǒng)計很有意義，也就是，匯總來自于一個滑動窗口的統(tǒng)計。例如，關(guān)于某一天的一個6個月的平均/最大值等于正好在那一天結(jié)束的6個月期間的平均/最大納斯達克指標，6個月的所有天的平均/最大值可以通過解決一個滑動聚合來獲得（注意，一個平均值可以通過使用周期長度ι來除以window sum來得到）。

作為排序，在MapReduce的發(fā)展中已經(jīng)取得了一些進展，目前最先進的是TeraSort，當一個重要的參數(shù)設(shè)置適當，Tera－Sort接近于最小，這個算法需要人工調(diào)節(jié)這個參數(shù)，一個不當?shù)倪x擇可能導(dǎo)致嚴重的性能代價，Beyer等人在MapReduce中已經(jīng)研究過滑動聚合，然而這個算法遠沒有達到最優(yōu)，只有當window的長度ι很短時，這個算法才是有效的，有作者評論到，這個問題“非常困難”。

三、技術(shù)概括

首先，本文從理論上證明TeraSort為什么使用2個循環(huán)能實現(xiàn)優(yōu)良的排序時間，在第一個循環(huán)中，算法從S中取一個隨機樣本集Ssamp，然后選擇t-1個抽樣對象作為邊界對象，概念上，這些邊界對象把S分成t段。在第二個循環(huán)中，t個機器中的每一個取得一個不同分段中的每一個對象，然后對它們進行排序，Ssamp的大小是效率的關(guān)鍵，如果Ssamp太小，邊界對象可能不夠分散，這可能會在第二個循環(huán)中引起分區(qū)傾斜，相反，如果Ssamp過大，會導(dǎo)致昂貴的抽樣開銷，在TeraSort的標準實現(xiàn)中，樣本大小被留作一個參數(shù)，雖然它似乎總是承認一個不錯的選擇，提供了優(yōu)異的性能。

本文中，我們對上面的現(xiàn)象給出了嚴格的說明，我們的理論分析闡明了如何設(shè)置Ssamp的大小來保證TeraSort的最小化，同時我們還彌補了TeraSort的一個概念上的缺陷，嚴格地說，這個算法在MapReduce中不很適合，因為它要求，（除了網(wǎng)絡(luò)消息之外）機器應(yīng)當能夠通過讀/寫一個普通（分布）文件來進行通信，一旦一個循環(huán)失效，算法需要另一個循環(huán)。我們給出了一個解決辦法，以使這個算法仍然能在2個循環(huán)內(nèi)解決，即使是最嚴格的MapReduce?？紤]到在MapReduce程序中排序的重要作用，我們的TeraSort調(diào)查結(jié)果有直接的實踐意義。

關(guān)于滑動聚合，困難在于，ι不是一個常數(shù)，但是可以是任何值，直到n，直觀地，當ι?m，window（o）非常大，以至于window（o）中的對象不能在最小占有空間限制下在一個機器上發(fā)現(xiàn)，反而window（o）可能跨越很多機器，這必須要明斷地進行機器搜索，以避免災(zāi)難性的開銷放大，實際上，這個缺陷已經(jīng)引出了的現(xiàn)有算法，它的主要思想是確保，每一個滑動窗口被發(fā)送到一個機器來進行聚合（不同的窗口可能到達不同的機器），當window的長度很長的時候，這會遭受到高昂的通信和處理成本，但是，我們的算法使用新的想法（在機器之間完美地均衡輸入對象，同時保持它們的順序）實現(xiàn)了最小化。

四、相關(guān)工作

Map階段產(chǎn)生一系列的key-value對（k，v）；Shuffle階段把key-value對分布在各個機器上；Reduce階段合并得到的所有key-value對。

算法的簡化。我們把Map和Shuffle合并，這個簡化只是邏輯層面的，物理上我們的算法還是按標準的MapReduce模式。

無狀態(tài)容錯。一些MapReduce實現(xiàn)（比如，Hadoop）要求，循環(huán)結(jié)束后，每個機器應(yīng)當把它的存儲中的所有數(shù)據(jù)傳送給分布式文件系統(tǒng)（DFS），在我們這里可以理解為“磁盤在云中”，保證一致性存儲（也就是，從來都這樣），目標是，在算法執(zhí)行中一個機器崩潰的情況下，來提高系統(tǒng)的魯棒性，在這種情況下，系統(tǒng)會用另一個機器來代替這個機器，在前一個循環(huán)結(jié)束的時候，會要求這個新機器來下載舊機器上的所有存儲，重新做當前的循環(huán)（發(fā)生故障的那個機器的），這樣的一個系統(tǒng)被稱為無狀態(tài)，因為直觀上沒有機器負責(zé)記住算法的任何狀態(tài)。

在定義的四個最小化條件保證無狀態(tài)的高效執(zhí)行，特別是最小化占用空間保障了，在每一個循環(huán)，每一個機器發(fā)送O（m）個單詞給DFS，這與有限的通信是一致的，MapReduce的研究分為兩類，提高框架的內(nèi)部工作，和應(yīng)用MapReduce來解決具體問題，S是來自一個有序域的n個對象的一個集合，S分布在t個機器上，每個機器排序O（m）個對象，其中m=n/t，排序結(jié)束后，機器i上的對象領(lǐng)先于機器j上的對象，其中，1≤i≤j≤t。

五、結(jié)論

雖然有很多的MapReduce的算法提出，但是很少能夠?qū)崿F(xiàn)理想的并行化的目標：機器間的負載均衡、線性于機器數(shù)量的一個順序算法上的加速比，特別是，當且在概念層級上，關(guān)于什么是一個“好的”MapReduce算法，還是一個空白。

我們用一個新的概念“MinMapReduce算法”填充了上述的空白，最小化的條件似乎相對嚴格，然而，我們證明了簡單而高超算法的存在性，它最低程度地解決了一些重要的數(shù)據(jù)庫問題，我們的實驗說明了通過最小化帶來了直接效果。

主要參考文獻：

［1］李建江，崔健，王聃，嚴林，黃義雙.M apReduce并行編程模型研究綜述［J］.電子學(xué)報，2011.11.

［2］秦軍，童毅，戴新華，林巧民.基于M apReduce數(shù)據(jù)密集型負載調(diào)度策略研究［J］.計算機技術(shù)與發(fā)展，2015.4.

［3］李士剛，胡長軍，王玨，李建江.異構(gòu)多核上多級并行模型支持及性能優(yōu)化［J］.軟件學(xué)報，2013.12.

［4］劉義，陳犖，景寧，熊偉.利用M apReduce進行批量遙感影像瓦片金字塔構(gòu)建［J］.武漢大學(xué)學(xué)報（信息科學(xué)版），2013.3.

［5］孔祥勇，高立群.求解大規(guī)?？煽啃詥栴}的改進差分進化算法［J］.東北大學(xué)學(xué)報，2014.35.3.

［6］常耀輝，隋莉莉，汪傳建.一種基于M apReduce可公開驗證數(shù)據(jù)來源的水印算法［J］.電子技術(shù)與軟件工程，2015.6.

［7］畢曉君，張永建.高維多目標多方向協(xié)同進化算法［J］.控制與決策，2014.29.10.

九江學(xué)院校級科研課題（2014K JY B030）；江西省高校省級教改項目（JX JG-14-17-10）；江西省高等學(xué)校大學(xué)生創(chuàng)新創(chuàng)業(yè)計劃項目（8891209）

F49

A