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

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

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

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

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

M apReduce；M i nM apReduce；負(fù)載均衡

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

收錄日期：2016年9月13日

一、引言

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

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

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

二、M i nM apReduce算法的定義

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

（1）最小占有空間：每個(gè)機(jī)器始終使用O（m）的存儲(chǔ)空間。

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

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

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

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

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

滑動(dòng)聚合，輸入包含：

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

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

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

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

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

圖1　Sl i di ng aggregat es

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

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

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

三、技術(shù)概括

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

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

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

四、相關(guān)工作

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

算法的簡(jiǎn)化。我們把Map和Shuffle合并，這個(gè)簡(jiǎn)化只是邏輯層面的，物理上我們的算法還是按標(biāo)準(zhǔn)的MapReduce模式。

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

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

五、結(jié)論

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

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

主要參考文獻(xiàn)：

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

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

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

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

［5］孔祥勇，高立群.求解大規(guī)模可靠性問題的改進(jìn)差分進(jìn)化算法［J］.東北大學(xué)學(xué)報(bào)，2014.35.3.

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

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

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

F49

A