MapReduce編程模型、方法及應(yīng)用綜述

丁智　林治

MapReduce編程模型、方法及應(yīng)用綜述

丁智，林治

（揚(yáng)州市職業(yè)大學(xué) 信息工程學(xué)院，江蘇 揚(yáng)州 225009）

摘要：近年來，云計算作為一種新的互聯(lián)網(wǎng)應(yīng)用模式正在改變?nèi)藗儷@取信息和服務(wù)的方式。MapReduce作為大規(guī)模數(shù)據(jù)處理的分布式計算模型，吸引了來自學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注，并在云計算的發(fā)展中起著決定性的作用。該文介紹了MapReduce編程模型及運(yùn)行機(jī)制，并給出了基于MapReduce的一個典型應(yīng)用。另外，針對MapReduce技術(shù)存在的問題提出應(yīng)對措施，給MapReduce的研究人員及用戶提供一定的參考。

關(guān)鍵詞：MapReduce；云計算；云應(yīng)用

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）30-7060-05

Review on MapReduce Programming Model， Method and Application

DING Zhi

（Institute of Information Engineering， Yangzhou Polytechnic College， Yangzhou 225009， China）

Abstract： In recent years， cloud computing as a new Internet application pattern is changing the way people access information and services. MapReduce， as a large-scale data processing and distributed computing model， attracts wide attention from academia and industry， and plays a decisive role in the development of cloud computing. This paper describes the MapReduce programming model and operation mechanism， and gives a typical application based on MapReduce. On this basis， several challenges and ideas are proposed as references to researchers and users.

Key words： MapReduce； cloud computing； cloud application

隨著云計算技術(shù)[1]的快速發(fā)展，云計算應(yīng)用不斷增多，有效提升用戶的大規(guī)模數(shù)據(jù)處理能力和服務(wù)體驗。MapReduce 編程模型作為云計算的核心技術(shù)之一，實(shí)質(zhì)上是一種分布式編程模型，它的設(shè)計初衷與大規(guī)模數(shù)據(jù)處理有關(guān)。目前大規(guī)模數(shù)據(jù)處理常用的方法是并行計算，它將運(yùn)行于大規(guī)模集群上的并行計算抽象成Map和Reduce兩個過程，抽象過程簡單，但顯示出驚人的計算能力，通過從復(fù)雜的實(shí)現(xiàn)細(xì)節(jié)中提取簡單的業(yè)務(wù)處理邏輯，提供了一系列簡單強(qiáng)大的接口，通過這些接口大規(guī)模計算自發(fā)的并行和分布執(zhí)行，使得開發(fā)人員不需要并行計算或者分布式的開發(fā)經(jīng)驗就可以高效的利用分布式資源。MapReduce分布式編程模型被Yahoo、Amazon、淘寶等知名IT企業(yè)廣泛應(yīng)用于日志分析、廣告計算、科研實(shí)驗和搜索等。同時，中科院、清華大學(xué)國內(nèi)知名大學(xué)也進(jìn)行了深入的研究[2]。

1 MapReduce相關(guān)技術(shù)

1.1 MapReduce概述

Google 每次搜索的后臺數(shù)據(jù)處理量都是驚人的，而且隨著時間推移，數(shù)據(jù)規(guī)模越來越大，計算量也隨之增大[3]。開發(fā)人員編寫大量程序用于數(shù)據(jù)挖掘，如爬蟲、Web 請求、查詢請求等，這些操作都是基于海量的原始數(shù)據(jù)，如何有效利用海量數(shù)據(jù)是一筆巨大的財富。同時，處理海量不同類型的派生數(shù)據(jù)的成本和時間是受限的。大規(guī)模計算雖然在概念上容易理解，但實(shí)際操作隨著數(shù)據(jù)量的增長復(fù)雜度呈指數(shù)級增加，因此，需要分給大量的計算機(jī)共同執(zhí)行才能在有限的時間內(nèi)完成[4]。如何實(shí)現(xiàn)并行計算，分發(fā)數(shù)據(jù)，容錯和調(diào)度等操作，原本看似容易的計算變得異常困難，需要大量復(fù)雜的編程來實(shí)現(xiàn)，又由于簡單的計算在大規(guī)模數(shù)據(jù)時會變得復(fù)雜且難以控制。為了更加有效的處理此類問題，Google 提出了MapReduce 編程模型[5]，MapReduce 借鑒了函數(shù)式程序設(shè)計語言的設(shè)計思想，把處理并發(fā)、容錯、數(shù)據(jù)分布等細(xì)節(jié)抽象到一個庫里面，可以很好地處理并行化、容錯、數(shù)據(jù)分布、負(fù)載均衡等操作的融合。

1.2編程模型

MapReduce編程模型[6]是根據(jù)這個框架提供的兩個編程接口Map和Reduce來命名的，將數(shù)據(jù)處理分為Map和Reduce兩個階段，大大簡化數(shù)據(jù)處理過程，如圖1所示。一系列key/value作為每個階段的輸入和輸出，key/value類型由用戶自行確定，同時還需要指定Map函數(shù)和Reduce函數(shù)，在Map階段，程序處理大量的輸入數(shù)據(jù)并得到一系列的key/value，就是一個key名稱與一個value相對應(yīng)。而這些由Map階段得到的所有key/value，在Reduce階段中，會根據(jù)具體的Reduce方法，把與同一key對應(yīng)的所有value進(jìn)行一個自定義的聚合運(yùn)算，從而得到一個最終結(jié)果。

圖1 MapReduce模型

1.3 MapReduce 關(guān)鍵特性

1.3.1 推測執(zhí)行

推測執(zhí)行是指某個節(jié)點(diǎn)任務(wù)運(yùn)行比預(yù)期慢的時候，檢測執(zhí)行慢的任務(wù)，并啟動一個相同的任務(wù)作為備份。推測執(zhí)行在一個作業(yè)的所有任務(wù)啟動完后才啟動推測執(zhí)行的任務(wù)，并且只針對那些已經(jīng)運(yùn)行一段時間（至少一分鐘）且比作業(yè)中其他任務(wù)平均進(jìn)度慢的任務(wù)。一個任務(wù)完成后，任何正在運(yùn)行的重復(fù)任務(wù)都將被中止。

1.3.2 容錯機(jī)制

MapReduce 是被設(shè)計用于成千上百臺機(jī)器上的海量數(shù)據(jù)處理，因此，它的函數(shù)庫還要考慮機(jī)器故障的容錯問題。控制節(jié)點(diǎn)會定時ping每個工作機(jī)器，如果在一定時間內(nèi)沒有得到該機(jī)器響應(yīng)，則可認(rèn)為該機(jī)器失效。主控制程序需要把所有節(jié)點(diǎn)上的任務(wù)重新執(zhí)行一次，才能完成MapReduce 操作。客戶端可檢測到控制點(diǎn)失效，并根據(jù)需要重啟MapReduce操作。

1.3.3 存儲本地化

在MapReduce分布式計算過程中，網(wǎng)絡(luò)資源相對稀缺。MapReduce控制節(jié)點(diǎn)有輸入文件組的位置信息，并嘗試在包含相應(yīng)輸入數(shù)據(jù)塊的機(jī)器上分配Map任務(wù)。如果不能分配，它就嘗試分配Map任務(wù)到盡量靠近這個任務(wù)的輸入數(shù)據(jù)的機(jī)架上執(zhí)行，還是不能的話，就從不同的機(jī)架上檢索數(shù)據(jù)。當(dāng)在一個足夠大的集群上運(yùn)行MapReduce操作的時候，大部分輸入數(shù)據(jù)都是在本地機(jī)器讀取的，這一過程并不占用網(wǎng)絡(luò)帶寬。

1.3.4 Combine（本地化Reduce）

Combine操作對map映射操作后產(chǎn)生的中間結(jié)果key/value進(jìn)行初步處理，使之按實(shí)際的Reduce要求有序，能有效提高后續(xù)全局Reduce操作的速度。一般情況下，用戶都會提供一個自定義的Combiner類，這樣Map過程所產(chǎn)生的中間結(jié)果key/value不會馬上寫到輸出，而會在被收集到列表中，當(dāng)緩沖區(qū)內(nèi)的key/value達(dá)到一定數(shù)量時，緩沖區(qū)內(nèi)數(shù)據(jù)會被清空轉(zhuǎn)移到Combiner類的Reduce方法中，最后每個key對應(yīng)的value列表將會以key/value的形式輸出。

2 MapReduce實(shí)現(xiàn)

2.1 運(yùn)行機(jī)制

MapReduce的工作流程如圖2所示，整個模型的最上層有四個實(shí)體[7]：客戶端負(fù)責(zé)向MapReduce框架提交作業(yè)；作業(yè)追蹤器全權(quán)負(fù)責(zé)調(diào)度作業(yè)的運(yùn)行，作業(yè)追蹤器是一個java應(yīng)用程序；任務(wù)追蹤器，作業(yè)被分成多個切片，任務(wù)追蹤器負(fù)責(zé)運(yùn)行輸入切片數(shù)據(jù)，任務(wù)追蹤器是一個Java應(yīng)用程序，負(fù)責(zé)具體任務(wù)的執(zhí)行；分布式文件系統(tǒng)（HDFS）提供存儲功能，用于向所有的節(jié)點(diǎn)共享作業(yè)所需的資源。

圖2 MapReduece工作流程

MapReduce作業(yè)提交后，runJob（）方法會調(diào)用submitJob（）方法并將作業(yè)提交給作業(yè)追蹤器。然后runJob（）方法不斷循環(huán)了解作業(yè)的實(shí)時運(yùn)行情況（步驟1） ，如果發(fā)現(xiàn)作業(yè)運(yùn)行狀態(tài)有更新，便把狀態(tài)報告給作業(yè)追蹤器。通過JobTracker.getNewJobId（）方法向作業(yè)追蹤器請求當(dāng)前作業(yè)的ID（步驟2） ；在獲取各個路徑信息時會檢查作業(yè)的對應(yīng)路徑。如果輸入輸出目錄不存在，會將錯誤信息返回給MapReduce程序。計算作業(yè)的輸出劃分，并將劃分信息寫入分塊文件，如果無法寫入就返回錯誤信息給MapReduce程序；將運(yùn)行作業(yè)所需的資源，包括作業(yè)的JAR文件、配置文件和計算所得的輸入劃分，復(fù)制到作業(yè)對用的分布式文件系統(tǒng)HDFS中。（步驟3） ；通過調(diào)用JobTracker.submitJob（）方法來真正提交作業(yè)，并告知作業(yè)追蹤器準(zhǔn)備執(zhí)行作業(yè)（步驟4） ；作業(yè)調(diào)用JobTracker.submitJob（）方法后，作業(yè)追蹤器會將此調(diào)用放入內(nèi)部的變量中，然后采用先進(jìn)先出方式進(jìn)行調(diào)度，當(dāng)作業(yè)被調(diào)度執(zhí)行時，作業(yè)追蹤器會創(chuàng)建一個代表該正在運(yùn)行的作業(yè)的對象，并在對象中封裝任務(wù)和記錄信息，用于跟蹤任務(wù)的狀態(tài)和進(jìn)程（步驟5） ；作業(yè)追蹤器首先從HDFS中獲取作業(yè)對應(yīng)的分塊信息（步驟6） ，為分配Map任務(wù)做準(zhǔn)備，然后創(chuàng)建并初始化Map和Reduce任務(wù)，最后創(chuàng)建兩個任務(wù)初始化Map和Reduce任務(wù)，同時指定任務(wù)的ID；任務(wù)追蹤器作為單獨(dú)的JVM會執(zhí)行一個簡單的循環(huán)，主要任務(wù)是每隔一段時間向作業(yè)追蹤器發(fā)送心跳（heartbeat），告訴作業(yè)追蹤器此任務(wù)追蹤器是否存活是否準(zhǔn)備執(zhí)行新任務(wù)，如果有待分配的任務(wù)，作業(yè)追蹤器會為任務(wù)追蹤器分配一個任務(wù)，并將分配信息在心跳通信的返回值中返回給任務(wù)追蹤器，任務(wù)追蹤器從心跳的返回值中得知自己要做的事情（步驟7） ；在任務(wù)追蹤器分配到新任務(wù)后，就要在本地執(zhí)行任務(wù)。首先，通過localizeJob（）方法完成任務(wù)本地化（步驟8） ；然后，launchTask（）方法會為任務(wù)創(chuàng)建本地工作目錄，并把JAR文件中的內(nèi)容解壓到這個文件夾下（步驟9） ；最后，啟動TaskRunner來執(zhí)行任務(wù)；最后，TaskRunner又會啟動一個新的JVM來運(yùn)行每個任務(wù)（步驟10） ；所有任務(wù)追蹤器任務(wù)的執(zhí)行進(jìn)度都會匯總到作業(yè)追蹤器，當(dāng)作業(yè)追蹤器接收到最后一個任務(wù)完成的通知時，把作業(yè)狀態(tài)設(shè)置為成功，用戶也會被及時告知作業(yè)完成。

2.2 應(yīng)用實(shí)例

為了更清楚地描述MapReduce編程模型，圖3給出了計算每年的最高氣溫[8]的程序偽代碼。在圖3所示的map函數(shù)中，首先提取年份和氣溫信息，生成Key-Value對形式，并將它們發(fā)送到臨時空間，再通過MapReduce中間處理過程，這一處理過程中根據(jù)Key對Key-Value對進(jìn)行分組，使每一年份后緊跟一系列氣溫數(shù)據(jù)。而每一個Reduce函數(shù)則只需遍歷整個列表并找出最大的數(shù)，這個結(jié)果就是每年的最高氣溫[9]。

[1：map（String input_key， String input_value）： ＼&2： // input_key： document name＼&3： // input_value： document contents＼&4： for each year y and temperature t in input_value：＼&5： EmitIntermediate（y， t）；＼&6：reduce（String output_key， Interator intermediate_values）：＼&7： // output_key： year＼&8： // intermediate_values： a list of temperature＼&9： int maxValue = Interger.MIN_VALUE；＼&10： for each t in intermediate_values：＼&11： maxValue =Math.max（t）；＼&12： Emit（year， maxValue）；＼&]

圖3 基于MapReduce的每年最高氣溫程序舉例

MapReduce執(zhí)行過程分為Map和Reduce兩個階段，如圖4所示。Map和Reduce之間包含分類階段，主要作用是將相同的key的中間結(jié)果交給同一個Reduce函數(shù)執(zhí)行。

圖4 MapReduce處理的執(zhí)行過程

3 MapReduce應(yīng)用研究現(xiàn)狀

自Google MapReduce發(fā)表以來，業(yè)界和學(xué)術(shù)界掀起了MapReduce研究的熱潮[10]。Tyson等對數(shù)據(jù)傳輸進(jìn)行了改進(jìn)，使MapReduce內(nèi)部數(shù)據(jù)流水線傳輸，這種改進(jìn)的MapReduce框架可以減少任務(wù)完成時間和提高系統(tǒng)的可用性，其他研究機(jī)構(gòu)也對MapReduce的應(yīng)用進(jìn)行了深入的探討和開發(fā)，下面針對大規(guī)模數(shù)據(jù)處理、并行計算、大規(guī)模數(shù)據(jù)的統(tǒng)計分析、數(shù)據(jù)挖掘、信息檢索等進(jìn)行分類闡述。

在大規(guī)模數(shù)據(jù)處理方面，Jaliya等利用MapReduce對高能物理數(shù)據(jù)進(jìn)行分析，實(shí)現(xiàn)了基于MapReduce的Kmeans聚類，最后提出了數(shù)據(jù)流式處理模型CGL-MapReduce，有利于基于MapReduce的數(shù)據(jù)密集型科學(xué)計算；Michal等在語義標(biāo)注解決方案Ontea的基礎(chǔ)上，引入MapReduce架構(gòu)對大規(guī)模網(wǎng)頁進(jìn)行自動語義標(biāo)注，實(shí)驗取得很好的性能表現(xiàn)，這種模式還可以用于網(wǎng)頁地圖的地理信息標(biāo)注；Liu等提出了基于MapReduce的分布式非負(fù)矩陣分解用于分析網(wǎng)頁二元數(shù)據(jù)，結(jié)果表明基于MapReduce分解有數(shù)十億非零值的一億個矩陣是可行的；Gaggero等利用MapReduce處理生物信息學(xué)數(shù)據(jù)，分別是計算相對簡單的大規(guī)模數(shù)據(jù)，和數(shù)據(jù)量稍小的復(fù)雜計算，結(jié)果都是可行的。

在并行計算方面，Andrew等提出基于MapReduce的并行粒子群優(yōu)化MRPSO，結(jié)果表明粒子群優(yōu)化可以很好的適應(yīng)MapReduce編程模型；Daniel等提出了基于MapReduce的XML處理管道并行化，通過一些新的策略把XML管道編譯到MapReduce網(wǎng)絡(luò)中，結(jié)果表明XML管道的執(zhí)行時間大大縮短； Jin等提出了基于MapReduce的兩層reduce階段的模型MRPGA，可以自動并行化遺傳算法，為迭代類算法使用MapReduce有了新的認(rèn)識。

在數(shù)據(jù)統(tǒng)計分析方面， Abouzeid等提出的HadoopDB通過結(jié)合MapReduce和并行數(shù)據(jù)庫系統(tǒng)用于大規(guī)模數(shù)據(jù)處理，利用MapReduce的可擴(kuò)展性、容錯性和靈活性的優(yōu)勢，再利用并行數(shù)據(jù)庫性能和效率上的優(yōu)勢；Facebook的數(shù)據(jù)倉庫Hive、Yahoo的Pig和Turn的Cheetah都是運(yùn)行在Hadoop上開源系統(tǒng)，支持類SQL的數(shù)據(jù)查詢，類SQL語言有HiveQL和Pig Latin，它們的編譯器會把類SQL的數(shù)據(jù)分析請求轉(zhuǎn)換為一系列經(jīng)過優(yōu)化處理的MapReduce運(yùn)算，來簡化MapReduce處理大規(guī)模數(shù)據(jù)的編程。

在數(shù)據(jù)挖掘方面，Liu等提出了基于MapReduce的BP神經(jīng)網(wǎng)絡(luò)MBNN用來處理大規(guī)模移動設(shè)備數(shù)據(jù)的聚類，還引入Adaboosting機(jī)制改善聚類性能； Zhao等提出基于MapReduce的并行Kmeans聚類算法，通過speedup， scaleup， sizeup來評估性能，結(jié)果顯示可以在普通計算機(jī)上有效地處理大數(shù)據(jù)集； White等把MapReduce用于圖像處理，包括分類器訓(xùn)練、背景提取和圖像配準(zhǔn)等，為MapReduce用于可視化數(shù)據(jù)處理奠定了基礎(chǔ)。

在國內(nèi)，基于Mapreduce的研究基本上可以分為高性能MapReduce、基于MapReduce框架的優(yōu)化和基于MapReduce的數(shù)據(jù)挖掘算法；復(fù)旦大學(xué)把MapReduce用于具有重要現(xiàn)實(shí)意義的科學(xué)計算，并對科學(xué)計算中遇到的一些典型問題提出相應(yīng)的優(yōu)化方案；中國科學(xué)技術(shù)大學(xué)提出的HPMR（High Performance MapReduce）是專為高性能計算，尤其是并行科學(xué)計算而設(shè)計開發(fā)的，通過MapReduce模型隱藏了與并行有關(guān)的繁瑣技術(shù)細(xì)節(jié)，程序員只需編寫計算代碼，所有與數(shù)據(jù)組織、任務(wù)并行和通信有關(guān)的功能都交給HPMR的運(yùn)行時系統(tǒng)去完成；浙江大學(xué)和中山大學(xué)等對基于MapReduce的數(shù)據(jù)挖掘算法進(jìn)行了研究；上海交通大學(xué)和北京郵電大學(xué)等對MapReduce框架進(jìn)行了改進(jìn)，實(shí)現(xiàn)MapReduce框架的通用性或用于具體的某一方面的數(shù)據(jù)處理。

4 MapReduce 挑戰(zhàn)與對策

目前，對于云計算中研究基本集中在MapReduce模型改進(jìn)，在MapReduce模型總體架構(gòu)的研究較少，而MapReduce編程模型的瓶頸主要在于架構(gòu)上過多地依賴于任務(wù)節(jié)點(diǎn)，從而導(dǎo)致整個系統(tǒng)的穩(wěn)定性和可用性受到限制[11]。目前 MapReduce 僅適用于內(nèi)部松耦合且可以高度并行化的應(yīng)用程序，如何使這種模式高效的運(yùn)行在緊耦合應(yīng)用程序的情況，是這種編程模式以后的發(fā)展趨勢。表1給出了主要存在的一些挑戰(zhàn)問題及克服相應(yīng)問題的對策。

表1 MapReduce的挑戰(zhàn)及對策

[挑戰(zhàn)＼&主要內(nèi)容＼&改進(jìn)＼&單jobtracker （任務(wù)管理節(jié)點(diǎn)）＼&架構(gòu)上過多地依賴于jobtracker節(jié)點(diǎn)的執(zhí)行效率，從而受限于jobtracker節(jié)點(diǎn)＼&多jobtracker；

把一些處理任務(wù)轉(zhuǎn)移到tasktracker節(jié)點(diǎn)＼&不適合處理緊耦合應(yīng)用＼&Map和Reduce任務(wù)之間都不能通信，更不用說兩種任務(wù)相互通信，不適合處理緊耦合的科學(xué)計算＼&Map任務(wù)、Reduce任務(wù)和Map任務(wù)、Reduce任務(wù)之間可以協(xié)同處理＼&不適合處理大量小文件＼&小文件產(chǎn)生的元數(shù)據(jù)會占用主節(jié)點(diǎn)的大量內(nèi)存，過量時主節(jié)點(diǎn)會遇到內(nèi)存瓶頸問題；如果訪問大量小文件，需要不斷的從一個jobtracker跳到另一個tasktracker，處理大量小文件速度遠(yuǎn)遠(yuǎn)小于處理同等大小的大文件的速度。其次，每一個小文件要占用一個任務(wù)，而任務(wù)啟動將耗費(fèi)大量時間甚至大部分時間都耗費(fèi)在啟動任務(wù)和釋放任務(wù)上。＼&把小文件合并成大文件再處理，比如Sequencefile，Mapfile＼&蠻力算法＼&MapReduce沒有索引，在處理存取操作時使用蠻力算法，效率很低，DBMS使用散列或者B樹索引加速數(shù)據(jù)存取。＼&應(yīng)用索引策略，如B樹，散列，多級索引等＼&不適合實(shí)時應(yīng)用＼&一個主搜索引擎可能每秒鐘處理成千上萬次查詢，用戶需要低延遲、高可靠的反饋。MapReduce很難滿足需求。＼&數(shù)據(jù)進(jìn)行流式處理，還可參考分布式數(shù)據(jù)處理系統(tǒng)Percolator＼&]

5 總結(jié)與展望

MapReduce 分布式計算模型在眾多應(yīng)用領(lǐng)域具有較好的性能表現(xiàn)，如何在這種編程模式上進(jìn)一步提高系統(tǒng)的處理能力已成為當(dāng)前業(yè)界非常關(guān)注的問題。比如MapReduce的單jobtracker節(jié)點(diǎn)的問題，需要MapReduce的jobtracker徹底改革，以解決其可擴(kuò)展性，內(nèi)存消耗，線程模型，可靠性和性能的幾個缺陷，Yahoo也已經(jīng)開始重構(gòu)MapReduce來解決瓶頸；由于Map、Reduce任務(wù)之間不能通信，MapReduce不適合處理緊耦合的科學(xué)計算，適合并行處理一些松耦合的簡單計算，可以通過改進(jìn)框架來實(shí)現(xiàn)Map、Reduce任務(wù)之間的協(xié)同處理；由于小文件產(chǎn)生的元數(shù)據(jù)會占用主節(jié)點(diǎn)的大量內(nèi)存，而且每一個小文件要占用一個任務(wù)，而任務(wù)啟動和釋放將耗費(fèi)大量時間，可以采用Sequencefile方式等把小文件合并成大文件再處理；DBMS都使用散列或者B樹索引加速數(shù)據(jù)存取[12]，如果要尋找記錄的某個子集，使用索引可以有效地將搜索范圍縮小一到兩個數(shù)量級，而且，還有查詢優(yōu)化器來確定是使用索引還是執(zhí)行蠻力順序搜索，MapReduce沒有索引，因此，處理時只有蠻力一種選擇，在存取數(shù)據(jù)時，MapReduce表現(xiàn)出很多的不足，結(jié)合Hive和Pig等技術(shù)可以很好地解決這個問題。

當(dāng)前，云計算中使用的分布式計算模型基本上是MapReduce編程模型[13]，MapReduce應(yīng)用研究較多，在分析MapReduce編程模型的基礎(chǔ)上，提出了如下的研究內(nèi)容：

1） 研究MapReduce架構(gòu)算法，通過重構(gòu)MapReduce模型來解決內(nèi)存瓶頸，優(yōu)化存取機(jī)制，適用緊耦合科學(xué)計算等；

2） 將MapReduce模型應(yīng)用于遺傳算法，蟻群算法，神經(jīng)網(wǎng)絡(luò)等智能算法；并將MapReduce模型應(yīng)用到數(shù)據(jù)挖掘算法中，比如k-means，SVM，樸素貝葉斯算法等；

3） 將MapReduce應(yīng)用到數(shù)據(jù)的統(tǒng)計分析中，提高數(shù)據(jù)存取效率，采用高級語言來執(zhí)行數(shù)據(jù)處理。

4） 將MapReduce模型應(yīng)用到一些緊耦合的數(shù)值計算中，先前通過高性能計算來完成的應(yīng)用，比如氣象，核模擬，生物信息學(xué)等。

參考文獻(xiàn)：

[1] Michael Armbrust，Armando Fox.Above the Clouds： A Berkeley View of Cloud Computing[M].UC Berkeley Reliable Adaptive Distributed Systems Laboratory，2009.

[2] Jeffrey Dean，Sanjay Ghemawat.MapReduce：a flexible data processing tool[J].Communications of the ACM， 2010，53（1）：72-77.

[3] 王鵬.云計算的關(guān)鍵技術(shù)與應(yīng)用實(shí)例[M].北京：人民郵電出版社，2010.

[4] Jeffrey Dean，Sanjay Ghemawat.MapReduce：Simpli?ed Data Processing on Large Clusters[J]. Communications of the ACM， 2008，51（1）： 107-113.

[5] 劉鵬.云計算[M].2版.北京：電子工業(yè)出版社，2011.

[6] Ralf L?mmel.Googles MapReduce programming model — Revisited[J].Science of Computer Programming， 2008，70（1）：1-30.

[7] Tom White. Hadoop權(quán)威指南[M].北京：清華大學(xué)出版社，2010.

[8] 常濤.改進(jìn)型 MapReduce 框架的研究與設(shè)計[D].北京：北京郵電大學(xué)，2011.

[9] 方巍，文學(xué)志.云計算：概念、技術(shù)及應(yīng)用研究綜述[J].南京信息工程大學(xué)學(xué)報：自然科學(xué)版，2012，4（4）： 351-361.

[10] 陳康，鄭緯民.云計算： 系統(tǒng)實(shí)例與研究現(xiàn)狀[J].軟件學(xué)報， 2009，20（5）：1337-1348.

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

[12] 王晟，趙壁芳.云計算中MapReduce 技術(shù)研究[J].通信技術(shù)，2012，44（12）：59-161.

[13] Tyson Condie， Neil Conway， et al. Hellerstein. Mapreduce online[C].USENIX Symposium on Networked Systems Designand Implementation，2010：21-35.endprint

5 總結(jié)與展望

MapReduce 分布式計算模型在眾多應(yīng)用領(lǐng)域具有較好的性能表現(xiàn)，如何在這種編程模式上進(jìn)一步提高系統(tǒng)的處理能力已成為當(dāng)前業(yè)界非常關(guān)注的問題。比如MapReduce的單jobtracker節(jié)點(diǎn)的問題，需要MapReduce的jobtracker徹底改革，以解決其可擴(kuò)展性，內(nèi)存消耗，線程模型，可靠性和性能的幾個缺陷，Yahoo也已經(jīng)開始重構(gòu)MapReduce來解決瓶頸；由于Map、Reduce任務(wù)之間不能通信，MapReduce不適合處理緊耦合的科學(xué)計算，適合并行處理一些松耦合的簡單計算，可以通過改進(jìn)框架來實(shí)現(xiàn)Map、Reduce任務(wù)之間的協(xié)同處理；由于小文件產(chǎn)生的元數(shù)據(jù)會占用主節(jié)點(diǎn)的大量內(nèi)存，而且每一個小文件要占用一個任務(wù)，而任務(wù)啟動和釋放將耗費(fèi)大量時間，可以采用Sequencefile方式等把小文件合并成大文件再處理；DBMS都使用散列或者B樹索引加速數(shù)據(jù)存取[12]，如果要尋找記錄的某個子集，使用索引可以有效地將搜索范圍縮小一到兩個數(shù)量級，而且，還有查詢優(yōu)化器來確定是使用索引還是執(zhí)行蠻力順序搜索，MapReduce沒有索引，因此，處理時只有蠻力一種選擇，在存取數(shù)據(jù)時，MapReduce表現(xiàn)出很多的不足，結(jié)合Hive和Pig等技術(shù)可以很好地解決這個問題。

當(dāng)前，云計算中使用的分布式計算模型基本上是MapReduce編程模型[13]，MapReduce應(yīng)用研究較多，在分析MapReduce編程模型的基礎(chǔ)上，提出了如下的研究內(nèi)容：

1） 研究MapReduce架構(gòu)算法，通過重構(gòu)MapReduce模型來解決內(nèi)存瓶頸，優(yōu)化存取機(jī)制，適用緊耦合科學(xué)計算等；

2） 將MapReduce模型應(yīng)用于遺傳算法，蟻群算法，神經(jīng)網(wǎng)絡(luò)等智能算法；并將MapReduce模型應(yīng)用到數(shù)據(jù)挖掘算法中，比如k-means，SVM，樸素貝葉斯算法等；

3） 將MapReduce應(yīng)用到數(shù)據(jù)的統(tǒng)計分析中，提高數(shù)據(jù)存取效率，采用高級語言來執(zhí)行數(shù)據(jù)處理。

4） 將MapReduce模型應(yīng)用到一些緊耦合的數(shù)值計算中，先前通過高性能計算來完成的應(yīng)用，比如氣象，核模擬，生物信息學(xué)等。

參考文獻(xiàn)：

[1] Michael Armbrust，Armando Fox.Above the Clouds： A Berkeley View of Cloud Computing[M].UC Berkeley Reliable Adaptive Distributed Systems Laboratory，2009.

[2] Jeffrey Dean，Sanjay Ghemawat.MapReduce：a flexible data processing tool[J].Communications of the ACM， 2010，53（1）：72-77.

[3] 王鵬.云計算的關(guān)鍵技術(shù)與應(yīng)用實(shí)例[M].北京：人民郵電出版社，2010.

[4] Jeffrey Dean，Sanjay Ghemawat.MapReduce：Simpli?ed Data Processing on Large Clusters[J]. Communications of the ACM， 2008，51（1）： 107-113.

[5] 劉鵬.云計算[M].2版.北京：電子工業(yè)出版社，2011.

[6] Ralf L?mmel.Googles MapReduce programming model — Revisited[J].Science of Computer Programming， 2008，70（1）：1-30.

[7] Tom White. Hadoop權(quán)威指南[M].北京：清華大學(xué)出版社，2010.

[8] 常濤.改進(jìn)型 MapReduce 框架的研究與設(shè)計[D].北京：北京郵電大學(xué)，2011.

[9] 方巍，文學(xué)志.云計算：概念、技術(shù)及應(yīng)用研究綜述[J].南京信息工程大學(xué)學(xué)報：自然科學(xué)版，2012，4（4）： 351-361.

[10] 陳康，鄭緯民.云計算： 系統(tǒng)實(shí)例與研究現(xiàn)狀[J].軟件學(xué)報， 2009，20（5）：1337-1348.

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

[12] 王晟，趙壁芳.云計算中MapReduce 技術(shù)研究[J].通信技術(shù)，2012，44（12）：59-161.

[13] Tyson Condie， Neil Conway， et al. Hellerstein. Mapreduce online[C].USENIX Symposium on Networked Systems Designand Implementation，2010：21-35.endprint

5 總結(jié)與展望

MapReduce 分布式計算模型在眾多應(yīng)用領(lǐng)域具有較好的性能表現(xiàn)，如何在這種編程模式上進(jìn)一步提高系統(tǒng)的處理能力已成為當(dāng)前業(yè)界非常關(guān)注的問題。比如MapReduce的單jobtracker節(jié)點(diǎn)的問題，需要MapReduce的jobtracker徹底改革，以解決其可擴(kuò)展性，內(nèi)存消耗，線程模型，可靠性和性能的幾個缺陷，Yahoo也已經(jīng)開始重構(gòu)MapReduce來解決瓶頸；由于Map、Reduce任務(wù)之間不能通信，MapReduce不適合處理緊耦合的科學(xué)計算，適合并行處理一些松耦合的簡單計算，可以通過改進(jìn)框架來實(shí)現(xiàn)Map、Reduce任務(wù)之間的協(xié)同處理；由于小文件產(chǎn)生的元數(shù)據(jù)會占用主節(jié)點(diǎn)的大量內(nèi)存，而且每一個小文件要占用一個任務(wù)，而任務(wù)啟動和釋放將耗費(fèi)大量時間，可以采用Sequencefile方式等把小文件合并成大文件再處理；DBMS都使用散列或者B樹索引加速數(shù)據(jù)存取[12]，如果要尋找記錄的某個子集，使用索引可以有效地將搜索范圍縮小一到兩個數(shù)量級，而且，還有查詢優(yōu)化器來確定是使用索引還是執(zhí)行蠻力順序搜索，MapReduce沒有索引，因此，處理時只有蠻力一種選擇，在存取數(shù)據(jù)時，MapReduce表現(xiàn)出很多的不足，結(jié)合Hive和Pig等技術(shù)可以很好地解決這個問題。

當(dāng)前，云計算中使用的分布式計算模型基本上是MapReduce編程模型[13]，MapReduce應(yīng)用研究較多，在分析MapReduce編程模型的基礎(chǔ)上，提出了如下的研究內(nèi)容：

1） 研究MapReduce架構(gòu)算法，通過重構(gòu)MapReduce模型來解決內(nèi)存瓶頸，優(yōu)化存取機(jī)制，適用緊耦合科學(xué)計算等；

2） 將MapReduce模型應(yīng)用于遺傳算法，蟻群算法，神經(jīng)網(wǎng)絡(luò)等智能算法；并將MapReduce模型應(yīng)用到數(shù)據(jù)挖掘算法中，比如k-means，SVM，樸素貝葉斯算法等；

3） 將MapReduce應(yīng)用到數(shù)據(jù)的統(tǒng)計分析中，提高數(shù)據(jù)存取效率，采用高級語言來執(zhí)行數(shù)據(jù)處理。

4） 將MapReduce模型應(yīng)用到一些緊耦合的數(shù)值計算中，先前通過高性能計算來完成的應(yīng)用，比如氣象，核模擬，生物信息學(xué)等。

參考文獻(xiàn)：

[1] Michael Armbrust，Armando Fox.Above the Clouds： A Berkeley View of Cloud Computing[M].UC Berkeley Reliable Adaptive Distributed Systems Laboratory，2009.

[2] Jeffrey Dean，Sanjay Ghemawat.MapReduce：a flexible data processing tool[J].Communications of the ACM， 2010，53（1）：72-77.

[3] 王鵬.云計算的關(guān)鍵技術(shù)與應(yīng)用實(shí)例[M].北京：人民郵電出版社，2010.

[4] Jeffrey Dean，Sanjay Ghemawat.MapReduce：Simpli?ed Data Processing on Large Clusters[J]. Communications of the ACM， 2008，51（1）： 107-113.

[5] 劉鵬.云計算[M].2版.北京：電子工業(yè)出版社，2011.

[6] Ralf L?mmel.Googles MapReduce programming model — Revisited[J].Science of Computer Programming， 2008，70（1）：1-30.

[7] Tom White. Hadoop權(quán)威指南[M].北京：清華大學(xué)出版社，2010.

[8] 常濤.改進(jìn)型 MapReduce 框架的研究與設(shè)計[D].北京：北京郵電大學(xué)，2011.

[9] 方巍，文學(xué)志.云計算：概念、技術(shù)及應(yīng)用研究綜述[J].南京信息工程大學(xué)學(xué)報：自然科學(xué)版，2012，4（4）： 351-361.

[10] 陳康，鄭緯民.云計算： 系統(tǒng)實(shí)例與研究現(xiàn)狀[J].軟件學(xué)報， 2009，20（5）：1337-1348.

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

[12] 王晟，趙壁芳.云計算中MapReduce 技術(shù)研究[J].通信技術(shù)，2012，44（12）：59-161.

[13] Tyson Condie， Neil Conway， et al. Hellerstein. Mapreduce online[C].USENIX Symposium on Networked Systems Designand Implementation，2010：21-35.endprint