MapReduce中Combine優(yōu)化機(jī)制的利用

賈歐陽(yáng) 阮樹(shù)驊 田興 楊峻興 李丹

摘 要： 由Apache軟件基金會(huì)開(kāi)發(fā)的Hadoop分布式系統(tǒng)基礎(chǔ)架構(gòu)，作為一個(gè)主流的云計(jì)算平臺(tái)，其核心框架之一的MapReduce性能已經(jīng)成為一個(gè)研究熱點(diǎn)，其中對(duì)于Shuffle階段的優(yōu)化，使用Combine優(yōu)化機(jī)制是關(guān)鍵。文章詳細(xì)介紹了MapReduce計(jì)算框架及Shuffle流程；分別從機(jī)理簡(jiǎn)介、執(zhí)行時(shí)機(jī)、運(yùn)行條件三方面詳細(xì)闡述了如何利用Combine優(yōu)化機(jī)制；通過(guò)搭建Hadoop集群，運(yùn)用MapReduce分布式算法測(cè)試實(shí)驗(yàn)數(shù)據(jù)。實(shí)驗(yàn)結(jié)果充分證明，正確地運(yùn)用Combine優(yōu)化機(jī)制能顯著提高M(jìn)apReduce框架的性能。

關(guān)鍵詞： 云計(jì)算； Hadoop； MapReduce； Shuffle； Combine

中圖分類號(hào)：TP393.2 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2013）09-01-04

0 引言

我們正處在一個(gè)數(shù)據(jù)爆炸的時(shí)代，數(shù)據(jù)生成速度之快令人驚訝：紐約證券交易所每天產(chǎn)生1TB的數(shù)據(jù)，F(xiàn)acebook存儲(chǔ)著約100億張照片占用了約1PB存儲(chǔ)容量[1]。由Apache軟件基金會(huì)開(kāi)發(fā)的Hadoop分布式系統(tǒng)基礎(chǔ)架構(gòu)，正是為了解決海量數(shù)據(jù)的存儲(chǔ)和計(jì)算問(wèn)題，并且由于其高可靠性、高可擴(kuò)展性、高效性和高容錯(cuò)性，已經(jīng)成為一種主流的云計(jì)算平臺(tái)[2]。Hadoop核心框架之一的MapReduce，在性能優(yōu)化和提高等方面的問(wèn)題已經(jīng)被學(xué)術(shù)界和工業(yè)界所關(guān)注，而其中很重要的一部分是對(duì)Shuffle階段的優(yōu)化。本文詳細(xì)介紹了MapReduce框架和Shuffle階段流程，研究分析了Shuffle優(yōu)化過(guò)程中利用Combine優(yōu)化機(jī)制存在的問(wèn)題，通過(guò)實(shí)驗(yàn)和理論分析找出了解決方案，提出了Combine優(yōu)化機(jī)制的執(zhí)行時(shí)機(jī)和運(yùn)行條件，并利用實(shí)例數(shù)據(jù)充分證明了正確地利用Combine優(yōu)化機(jī)制能顯著提高M(jìn)apReduce框架性能。

1 MapReduce框架

1.1 框架簡(jiǎn)介

MapReduce是一種能夠在普通配置計(jì)算機(jī)上并行處理大量數(shù)據(jù)的并行計(jì)算框架，使用這個(gè)框架，我們只需要編寫(xiě)我們想要執(zhí)行的簡(jiǎn)單運(yùn)算即可，寫(xiě)出的程序自動(dòng)在集群上并行執(zhí)行，而不必關(guān)心集群之間的調(diào)度、數(shù)據(jù)分布、負(fù)載均衡、容災(zāi)備份、通信等復(fù)雜細(xì)節(jié)，這些問(wèn)題都已經(jīng)被MapReduce框架封裝好了。

MapReduce可以讓沒(méi)有任何分布式、并行編程經(jīng)驗(yàn)的程序員很容易地利用分布式系統(tǒng)的資源[3]，用戶只需要自己定義map函數(shù)和reduce函數(shù)，這兩個(gè)函數(shù)的靈感來(lái)自Lisp和許多其他函數(shù)式語(yǔ)言的map和reduce原語(yǔ)[4]，map函數(shù)從輸入數(shù)據(jù)中獲取鍵/值對(duì)同時(shí)生成一個(gè)中間鍵值對(duì)集合，reduce函數(shù)合并有相同中間鍵的中間值，從而得到一個(gè)想要的結(jié)果。MapReduce框架會(huì)在任務(wù)運(yùn)行時(shí)關(guān)注調(diào)度任務(wù)，并監(jiān)視任務(wù)的執(zhí)行狀況，如果執(zhí)行失敗，將重新執(zhí)行該任務(wù)[5]。

1.2 實(shí)現(xiàn)機(jī)制

首先輸入文件會(huì)被用戶程序調(diào)用的MapReduce庫(kù)切分成若干64MB大小的數(shù)據(jù)塊，這些數(shù)據(jù)塊在框架中會(huì)被自動(dòng)地創(chuàng)建副本，然后調(diào)用fork原語(yǔ)創(chuàng)建數(shù)個(gè)子程序，在這些子程序中有一個(gè)特殊程序master，其他程序都被當(dāng)作worker程序，一個(gè)空閑的worker程序?qū)⑹盏接蒻aster分配的一個(gè)map任務(wù)和reduce任務(wù)。

worker程序從輸入的數(shù)據(jù)片段中解析出鍵值對(duì)，然后這些鍵值對(duì)被傳遞給用戶自定義實(shí)現(xiàn)的map函數(shù)，由map函數(shù)處理后，生成的中間鍵值對(duì)最終被寫(xiě)到本地磁盤(pán)上，master獲取到這些鍵值對(duì)在本地磁盤(pán)上的存儲(chǔ)位置并傳送給負(fù)責(zé)執(zhí)行reduce任務(wù)的worker節(jié)點(diǎn)。

reduce worker程序使用RPC從負(fù)責(zé)執(zhí)行map任務(wù)的worker節(jié)點(diǎn)所在主機(jī)的磁盤(pán)上讀取這些緩存數(shù)據(jù)，由于存在不同的key值映射到相同的reduce任務(wù)上，因此會(huì)進(jìn)行排序，如果中間數(shù)據(jù)太大無(wú)法在內(nèi)存中完成排序，那么就要進(jìn)行外排序[5]，最終使得具有相同key值的數(shù)據(jù)聚合在一起。

排序后的中間數(shù)據(jù)經(jīng)過(guò)reduce worker遍歷后，reduce worker程序?qū)⒚恳粋€(gè)惟一的中間key值和它相關(guān)的中間value值的集合傳遞給用戶自定義的reduce函數(shù)[5]。

當(dāng)所有的map、reduce任務(wù)完成后，用戶程序?qū)ap、reduce的調(diào)用才返回。

2 Shuffle過(guò)程

Shuffle過(guò)程可以理解為是從map映射輸出到reduce消化輸入的整個(gè)過(guò)程，整個(gè)過(guò)程被稱為MapReduce的“心臟”，關(guān)乎整個(gè)框架性能[1]，應(yīng)用開(kāi)發(fā)人員對(duì)MapReduce框架的改進(jìn)也主要集中在Shuffle階段。

MapReduce框架中Shuffle流程如圖1所示[1]。

2.1 Map端

⑴ 作業(yè)提交以后，Map端從輸入塊中讀取record，依次調(diào)用map函數(shù)進(jìn)行處理，并映射輸出（key，value）鍵值對(duì)。

⑵ 生成的鍵值對(duì)串行化的輸出到環(huán)形內(nèi)存緩沖區(qū)[7]，這期間如果應(yīng)用程序員沒(méi)有定制partitioner，那么系統(tǒng)會(huì)調(diào)用默認(rèn)的HashPartitioner把鍵值對(duì)劃分到對(duì)應(yīng)的partition分區(qū)。

⑶ 當(dāng)緩沖區(qū)的內(nèi)容達(dá)到設(shè)定的閾值時(shí)，一個(gè)后臺(tái)spill線程便開(kāi)始把這些內(nèi)容溢寫(xiě)到磁盤(pán)[1]，spill線程在把緩沖區(qū)數(shù)據(jù)寫(xiě)到磁盤(pán)前，會(huì)對(duì)它進(jìn)行一個(gè)二次快速排序，首先根據(jù)所屬的partition排序，然后在每個(gè)partition內(nèi)再按key排序[8]。

⑷ 當(dāng)緩沖區(qū)的數(shù)據(jù)輸出到磁盤(pán)后，可能會(huì)出現(xiàn)多個(gè)spill文件，這時(shí)候就進(jìn)入Map端的合并（merge）階段，會(huì)對(duì)這些文件做一個(gè)歸并排序，最后輸出一個(gè)index文件和一個(gè)數(shù)據(jù)文件，index文件記錄了不同的key在數(shù)據(jù)文件中偏移量[7]。

2.2 Reduce端

⑴ Copy Phase：在Map端，只要有一個(gè)任務(wù)完成，Reduce任務(wù)就開(kāi)始通過(guò)http方式復(fù)制其輸出，而不是等所有Map端任務(wù)都結(jié)束之后再進(jìn)行[1]。

⑵ Sort Phase：Map端輸出在被取回的同時(shí)，被合并成多個(gè)文件，并按鍵排序，這個(gè)階段更恰當(dāng)?shù)卣f(shuō)，應(yīng)該只進(jìn)行了合并，因?yàn)榕判颍⊿ort）是在Map端進(jìn)行的[1]。

⑶ Merge Phase：歸并過(guò)程中的數(shù)據(jù)可能既有在內(nèi)存中的也有在磁盤(pán)上的，如果都在內(nèi)存中，則會(huì)直接被復(fù)制到Reduce端而省去向磁盤(pán)寫(xiě)這一步[8]，然后通過(guò)歸并得到最終的文件。

3 Combine優(yōu)化

3.1 Combine優(yōu)化機(jī)制簡(jiǎn)介

MapReduce框架的運(yùn)作基于鍵值對(duì)，即數(shù)據(jù)的輸入是鍵值對(duì)，生成的結(jié)果也是存放在集合里的鍵值對(duì)，其中鍵值對(duì)的值也是一個(gè)集合，一個(gè)MapReduce任務(wù)的執(zhí)行過(guò)程以及數(shù)據(jù)輸入輸出的類型如下所示，這里我們定義list表示集合：

map（K1， V1） -> list（K2， V2）

combine（K2， list（V2）） -> list（K2， V2）

reduce（K2， list（V2）） -> list（K3， V3）

map函數(shù)操作所產(chǎn)生的鍵值對(duì)會(huì)作為combine函數(shù)的輸入，經(jīng)combine函數(shù)處理后再送到reduce函數(shù)進(jìn)行處理，減少了寫(xiě)入磁盤(pán)的數(shù)據(jù)量，同時(shí)也減少了網(wǎng)絡(luò)中鍵值對(duì)的傳輸量。在Map端，用戶自定義實(shí)現(xiàn)的Combine優(yōu)化機(jī)制類Combiner在執(zhí)行Map端任務(wù)的節(jié)點(diǎn)本身運(yùn)行，相當(dāng)于對(duì)map函數(shù)的輸出做了一次reduce[8]。

集群上的可用帶寬往往是有限的，產(chǎn)生的中間臨時(shí)數(shù)據(jù)量很大時(shí)就會(huì)出現(xiàn)性能瓶頸，因此盡量避免Map端任務(wù)和Reduce端任務(wù)之間大量的數(shù)據(jù)傳輸是很重要的。使用Combine機(jī)制的意義就在于使Map端輸出更緊湊，使得寫(xiě)到本地磁盤(pán)和傳給Reduce端的數(shù)據(jù)更少[1]。

選用Combine機(jī)制下的Combiner雖然減少了IO，但是等于多做了一次reduce，所以應(yīng)該查看作業(yè)日志來(lái)判斷combine函數(shù)的輸出記錄數(shù)是否明顯少于輸入記錄的數(shù)量，以確定這種減少和花費(fèi)額外的時(shí)間來(lái)運(yùn)行Combiner相比是否值得[8]。

在具體的分布式應(yīng)用中，應(yīng)用開(kāi)發(fā)人員需要自己定制map函數(shù)和reduce函數(shù)，在本文實(shí)驗(yàn)中用到的具體算法如下：

Algorithm 1是分割映射鍵值對(duì)的map算法。map函數(shù)的輸入分別為文本數(shù)據(jù)中行偏移量key、每行文本內(nèi)容text和上下文對(duì)象context，算法第1行將輸入的每行文檔內(nèi)容數(shù)據(jù)text分割成單個(gè)的單詞k，放入集合K中，第2-3行對(duì)K中的每個(gè)k，映射輸出鍵值對(duì)（k，1），這里每個(gè)鍵k對(duì)應(yīng)的值是1。

Algorithm 2是對(duì)中間鍵值對(duì)合并的combine算法。combine函數(shù)的輸入為經(jīng)map函數(shù)分割后的每個(gè)單詞k、單詞k及其統(tǒng)計(jì)次數(shù)存放的集合K1和上下文對(duì)象context，其中鍵值對(duì)的輸入鍵midsum為經(jīng)過(guò)combine算法后分發(fā)出的一類鍵名，用以標(biāo)識(shí)鍵值對(duì)已經(jīng)經(jīng)過(guò)combine算法處理。算法第1行首先判斷輸入鍵是否為midsum，如果不是，則第2-4行對(duì)K1集合中的統(tǒng)計(jì)次數(shù)進(jìn)行累加，輸出鍵值對(duì)midsum作為鍵，累加結(jié)果sum作為值；第5-7行因?yàn)檩斎腈I是midsum，則直接映射輸出，避免輪詢?cè)斐筛蟮拈_(kāi)銷。

Algorithm 3是規(guī)約reduce算法。reduce函數(shù)的輸入可能是combine函數(shù)的輸出（midsum，sum）（存放于集合K2中），也可能是沒(méi)有經(jīng)過(guò)combine函數(shù)合并的map函數(shù)的輸出（k，1） （仍然存放于集合K1中），還有上下文對(duì)象context，算法第1-2行對(duì)K1/K2集合中每個(gè)k進(jìn)行累加求和，第3行輸出最終的鍵值對(duì)（endsum，sum），sum即為最終的求和結(jié)果。

算法1至3如圖2所示。

[Algorithm 1：分割鍵值對(duì)map算法

輸入：key， text， context

輸出：中間鍵值對(duì)（k，v）

步驟：

1 list（K） ← split text

2 foreach k ∈ K

3 emit intermediate（k，1）；][Algorithm 3：規(guī)約reduce算法

輸入：key， K1/K2， context

輸出：求和結(jié)果

步驟：

1 foreach k ∈ K1/K2

2 compute the sum of v

3 emit （endsum，sum）；＼&][Algorithm 2：合并中間鍵值對(duì)combine算法

輸入：key， K1， context

輸出：中間鍵值對(duì)（k，v）

步驟：

1 if k does not start with midsum

2 foreach k ∈ K1

3 compute the sum of v

4 emit intermediate（midsum，sum）；

5 else

6 foreach k ∈ K1

7 emit intermediate（k，v）；

3.2 Combine優(yōu)化機(jī)制執(zhí)行時(shí)機(jī)

⑴ Map端spill的時(shí)候

在Map端內(nèi)存緩沖區(qū)進(jìn)行溢寫(xiě)的時(shí)候，數(shù)據(jù)會(huì)被劃分成相應(yīng)分區(qū)，后臺(tái)線程在每個(gè)partition內(nèi)按鍵進(jìn)行內(nèi)排序。這時(shí)如果指定了Combiner，并且溢寫(xiě)次數(shù)最少為3（min.num.spills.for.combine屬性的取值）時(shí)，Combiner就會(huì)在排序后輸出文件寫(xiě)到磁盤(pán)之前運(yùn)行[1]。

⑵ Map端merge的時(shí)候

在Map端寫(xiě)磁盤(pán)完畢前，這些中間的輸出文件會(huì)合并成一個(gè)已分區(qū)且已排序的輸出文件，按partition循環(huán)處理所有文件，合并會(huì)分多次，這個(gè)過(guò)程也會(huì)伴隨著Combiner的運(yùn)行[7]。

⑶ Reduce端merge的時(shí)候

從Map端復(fù)制過(guò)來(lái)數(shù)據(jù)后，Reduce端在進(jìn)行merge合并數(shù)據(jù)時(shí)也會(huì)調(diào)用Combiner來(lái)壓縮數(shù)據(jù)。Combiner通常被看作是一個(gè)Map端的本地reduce函數(shù)的實(shí)現(xiàn)類Reducer，這個(gè)實(shí)驗(yàn)[9]也驗(yàn)證了這一理論的不足，但是在很多情況下Combiner在Reduce端的作用是有限的。

3.3 Combine優(yōu)化機(jī)制運(yùn)行條件

⑴ 滿足交換和結(jié)合律[10]

結(jié)合律：

（1）+（2+3）+（4+5+6）==（1+2）+（3+4）+（5）+（6）== ...

交換律：

1+2+3+4+5+6==2+4+6+1+2+3== ...

應(yīng)用程序在滿足如上的交換律和結(jié)合律的情況下，combine函數(shù)的執(zhí)行才是正確的，因?yàn)榍笃骄祮?wèn)題是不滿足結(jié)合律和交換律的，所以這類問(wèn)題不能運(yùn)用Combine優(yōu)化機(jī)制來(lái)求解。

例如：mean（10，20，30，40，50）=30

但mean（mean（10，20），mean（30，40，50））=22.5

這時(shí)在求平均氣溫等類似問(wèn)題的應(yīng)用程序中使用Combine優(yōu)化機(jī)制就會(huì)出錯(cuò)。

另外需注意，在撰寫(xiě)含有Combiner的應(yīng)用時(shí)，對(duì)于所有map函數(shù)的輸出，并非一定都經(jīng)過(guò)Combiner，有些會(huì)直接進(jìn)入Reducer。

如果我們?cè)诔绦蛑卸ㄖ屏艘粋€(gè)Combiner，MapReduce框架使用它的次數(shù)可能是0次也可能是多次，為了保證Combine機(jī)制的正確運(yùn)用，Combiner在數(shù)據(jù)的轉(zhuǎn)換上必須與Reducer等價(jià)，如果我們?nèi)サ鬋ombiner，Reducer的輸出也應(yīng)保持不變，而且，當(dāng)Combiner被應(yīng)用于中間數(shù)據(jù)的任意子集時(shí)，仍需保持等價(jià)的轉(zhuǎn)換特性[9]。

⑵ Combine優(yōu)化機(jī)制中存在的輪詢問(wèn)題

在開(kāi)發(fā)過(guò)程中，使用Combine優(yōu)化機(jī)制會(huì)存在輪詢問(wèn)題，即一個(gè)combine函數(shù)的輸出結(jié)果可能會(huì)成為其自身的輸入[11]，經(jīng)過(guò)combine函數(shù)處理的數(shù)據(jù)會(huì)再次進(jìn)入combine函數(shù)，但輪詢問(wèn)題是不可避免的，所以要保證combine函數(shù)的輸入類型和輸出類型必須一致，若不一致，要增加判斷的邏輯。

4 實(shí)驗(yàn)結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境

本文通過(guò)部署一個(gè)Hadoop偽分布環(huán)境，通過(guò)實(shí)驗(yàn)對(duì)比和分析來(lái)驗(yàn)證文中關(guān)于利用Combine優(yōu)化機(jī)制理論的正確性。在實(shí)驗(yàn)搭建的集群中，NameNode和DataNode都在本機(jī)中。

硬件環(huán)境：Intel? Core? i5 CPU M 480 @ 2.67GHz×4，3.7GB內(nèi)存，500GB硬盤(pán)。

軟件環(huán)境：Fedora16，Hadoop 0.21.0，Jdk-6u27-linux-i586。

4.2 實(shí)驗(yàn)結(jié)果及分析

本文采用數(shù)字求和程序作為實(shí)驗(yàn)測(cè)試程序，采用文本文檔作為實(shí)驗(yàn)數(shù)據(jù)集，文本中數(shù)據(jù)隨機(jī)生成，正負(fù)相間，以防數(shù)據(jù)全正或全負(fù)致使計(jì)算結(jié)果溢出。

⑴ 實(shí)驗(yàn)一

采用418.9MB文本文檔數(shù)據(jù)集進(jìn)行多次實(shí)驗(yàn)，分析實(shí)驗(yàn)日志，取其中三組實(shí)驗(yàn)結(jié)果列表，利用Combine機(jī)制優(yōu)化前后，框架中各部分的輸入輸出和耗時(shí)對(duì)比如表1所示。

作業(yè)結(jié)束后，查看日志，利用Combine機(jī)制優(yōu)化前后作業(yè)都分別共執(zhí)行了12個(gè)map任務(wù)和1個(gè)reduce任務(wù)，表1中詳細(xì)記錄了作業(yè)執(zhí)行完成后map函數(shù)、combine函數(shù)和reduce函數(shù)的輸入輸出數(shù)量和耗時(shí)，通過(guò)表1的數(shù)據(jù)對(duì)比可以看出：一方面，使用Combine優(yōu)化機(jī)制優(yōu)化后，作業(yè)執(zhí)行時(shí)間明顯減少；另一方面，從實(shí)驗(yàn)數(shù)據(jù)中可以看到combine函數(shù)輸入的數(shù)量要明顯大于map函數(shù)輸出的數(shù)量，而且combine函數(shù)輸出的數(shù)量要明顯大于reduce函數(shù)輸入的數(shù)量，所以可以驗(yàn)證在使用Combine優(yōu)化過(guò)程中存在明顯的輪詢問(wèn)題，但由于實(shí)驗(yàn)中輸入輸出數(shù)據(jù)類型相同，所以輪詢并不影響實(shí)驗(yàn)的最終輸出結(jié)果，Combiner的輸出結(jié)果被寫(xiě)到中間文件，并被發(fā)送到reduce任務(wù)中，經(jīng)reduce函數(shù)處理后直接被寫(xiě)到最終的輸出文件中，保存在HDFS文件系統(tǒng)上。

⑵ 實(shí)驗(yàn)二

分別采用41.9MB、83.8MB、167.6MB、335.1MB、418.9MB文本文檔作為測(cè)試數(shù)據(jù)集。

圖3為利用Combine優(yōu)化機(jī)制優(yōu)化前后作業(yè)執(zhí)行總耗時(shí)對(duì)比，在圖3中可以看到，隨著數(shù)據(jù)集增大，利用Combine機(jī)制優(yōu)化過(guò)的作業(yè)在總耗時(shí)方面時(shí)間減少明顯，性能平均提高43%，可以充分驗(yàn)證使用Combine優(yōu)化機(jī)制會(huì)大量減少M(fèi)ap端最后寫(xiě)到磁盤(pán)的數(shù)據(jù)量，同時(shí)也減少了網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)量，大幅提高系統(tǒng)性能。

圖4為利用Combine優(yōu)化機(jī)制優(yōu)化前后Map端計(jì)算耗時(shí)對(duì)比，可以看到，利用Combine優(yōu)化機(jī)制優(yōu)化后，計(jì)算機(jī)壓力雖然大部分在Map端，但是Map端耗時(shí)隨著數(shù)據(jù)集增大而減少也很明顯。

圖5為利用Combine優(yōu)化機(jī)制優(yōu)化前后Reduce端耗時(shí)對(duì)比，因?yàn)閿?shù)據(jù)求和的實(shí)驗(yàn)在利用Combine優(yōu)化機(jī)制優(yōu)化后，計(jì)算壓力大部分都在Map端，所以可以看到當(dāng)數(shù)據(jù)集增大時(shí)，Reduce端執(zhí)行時(shí)間基本都維持在4秒左右。

5 結(jié)束語(yǔ)

本文通過(guò)對(duì)Shuffle流程的詳細(xì)分析，指出Combine機(jī)制在Shuffle流程中的具體執(zhí)行位置，并詳細(xì)分析了Combine優(yōu)化機(jī)制執(zhí)行所需條件和執(zhí)行過(guò)程中存在的問(wèn)題。通過(guò)實(shí)驗(yàn)分析，可以看到Combine機(jī)制對(duì)性能的提升確實(shí)很大，但在實(shí)際開(kāi)發(fā)應(yīng)用中應(yīng)該結(jié)合文中所述和實(shí)際開(kāi)發(fā)需要，評(píng)測(cè)是否需要利用Combine優(yōu)化機(jī)制，只有在網(wǎng)絡(luò)帶寬資源有限，對(duì)系統(tǒng)的瓶頸比較大時(shí)才應(yīng)該考慮使用Combine機(jī)制，以減少數(shù)據(jù)在網(wǎng)絡(luò)中的傳輸量，降低系統(tǒng)對(duì)網(wǎng)絡(luò)帶寬的需求。

參考文獻(xiàn)：

[1] Tom White.Hadoop權(quán)威指南[M].清華大學(xué)出版社，2011.

[2] 周一可.云計(jì)算下MapReduce 編程模型可用性研究與優(yōu)化[D].上海交通大學(xué)，2011.

[3] Jeffrey Dean， Sanjay Ghemawat. MapReduce： Simplified Data Processing on Large Clusters[C]，2004.

[4] Wikipedia. MapReduce介紹.2012年09月22日引自http：//zh.wikipedia.org/wiki/MapReduce

[5] 王凱.MapReduce集群多用戶作業(yè)調(diào)度方法的研究與實(shí)現(xiàn)[D].國(guó)防科學(xué)技術(shù)大學(xué)，2010.11.

[6] 徐強(qiáng)，王振江.云計(jì)算應(yīng)用開(kāi)發(fā)實(shí)踐[M].機(jī)械工業(yè)出版社，2012.

[7] gaobotian. Hadoop源代碼分析（完整版）. 2012年09月22日引自http：//wenku.baidu.com/view/ffc10130eefdc8d376ee32ec.html

[8] 皮冰鋒等.Hadoop開(kāi)發(fā)者第一期.2012年9月22日引自http：//www.hadoopor.com/

[9] Lam， C著，韓冀中譯.Hadoop實(shí)戰(zhàn)[M].人民郵電出版社，2011.

[10] StackOverFlow. "Combiner" Class in a mapreduce job. 2012年9月23日引自http：//stackoverflow.com/questions/10220371/Combiner-class-in-a-mapreduce-job

[11] 何忠育等.Hadoop開(kāi)發(fā)者第四期.2012年9月23日引自 http：//www.hadoopor.com/