大數據信息處理的MinMapReduce算法

□文/楊茂保（九江學院江西·九江）

大數據信息處理的MinMapReduce算法

□文/楊茂保
（九江學院江西·九江）

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

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

原標題：大數據信息處理的M i nM apReduce算法設計與實現

收錄日期：2016年9月13日

一、引言

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

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

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

二、M i nM apReduce算法的定義

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

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

（2）有限的網絡通信：在每一個循環中，每個機器通過網絡最多發送或者接收O（m）個字。

（3）常數個循環：算法必須在常數個循環之后終止。

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

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

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

滑動聚合，輸入包含：

——來自一個有序域的n個對象的一個集合S，其中每個對象o∈S與一個數值權重有關

——一個整數ι≤n

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

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

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

圖1　Sl i di ng aggregat es

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

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

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

三、技術概括

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

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

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

四、相關工作

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

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

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

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

五、結論

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

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

主要參考文獻：

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

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

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

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

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

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

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

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

F49

A