課程地址：MapReduce
官方文檔：MapReduce Tutorial
參考文獻(xiàn)：MapReduce原理與設(shè)計思想

目錄

0疟暖、什么樣的計算任務(wù)可進(jìn)行并行化計算？
1、MapReduce的原理
2俐巴、MapReduce運行原理
3骨望、上升到構(gòu)架-自動并行化并隱藏低層細(xì)節(jié)
4、MapReduce的主要設(shè)計思想和特征

0欣舵、什么樣的計算任務(wù)可進(jìn)行并行化計算擎鸠？

并行計算的第一個重要問題是如何劃分計算任務(wù)或者計算數(shù)據(jù)以便對劃分的子任務(wù)或數(shù)據(jù)塊同時進(jìn)行計算。但一些計算問題恰恰無法進(jìn)行這樣的劃分缘圈！

例如：Fibonacci函數(shù):  Fk+2 = Fk + Fk+1 

前后數(shù)據(jù)項之間存在很強(qiáng)的依賴關(guān)系劣光，只能串行計算！

結(jié)論：不可分拆的計算任務(wù)或相互間有依賴關(guān)系的數(shù)據(jù)無法進(jìn)行并行計算糟把！

大數(shù)據(jù)的并行化計算

一個大數(shù)據(jù)若可以分為具有同樣計算過程的數(shù)據(jù)塊绢涡，并且這些數(shù)據(jù)塊之間不存在數(shù)據(jù)依賴關(guān)系，則提高處理速度的最好辦法就是并行計算糊饱。

例如：假設(shè)有一個巨大的2維數(shù)據(jù)需要處理(比如求每個元素的開立方)垂寥，其中對每個元素的處理是相同的,并且數(shù)據(jù)元素間不存在數(shù)據(jù)依賴關(guān)系,可以考慮不同的劃分方法將其劃分為子數(shù)組,由一組處理器并行處理。

1另锋、MapReduce的原理：通過分散計算來分析大量數(shù)據(jù)

• 分：Map（大任務(wù)分成子任務(wù)）
• 治：Reduce（合并結(jié)果）

MapReduce合并了兩種經(jīng)典函數(shù)：

• 映射（Mapping）：對集合里的每個目標(biāo)應(yīng)用同一個操作滞项。
• 化簡（Reducing ）：遍歷集合中的元素來返回一個綜合的結(jié)果。

*Input Split（輸入分割） -> Map Task（各自統(tǒng)計） -> Shuffle（統(tǒng)計結(jié)果交換夭坪、規(guī)約） -> Reduce Task（統(tǒng)計合并結(jié)果） -> Output *

上升到抽象模型：Mapper與Reducer

MPI等并行計算方法缺少高層并行編程模型文判，為了克服這一缺陷，MapReduce借鑒了Lisp函數(shù)式語言中的思想室梅，用Map和Reduce兩個函數(shù)提供了高層的并行編程抽象模型

上升到構(gòu)架：統(tǒng)一構(gòu)架戏仓，為程序員隱藏系統(tǒng)層細(xì)節(jié)

MPI等并行計算方法缺少統(tǒng)一的計算框架支持，程序員需要考慮數(shù)據(jù)存儲亡鼠、劃分赏殃、分發(fā)、結(jié)果收集间涵、錯誤恢復(fù)等諸多細(xì)節(jié)仁热；為此，MapReduce設(shè)計并提供了統(tǒng)一的計算框架勾哩，為程序員隱藏了絕大多數(shù)系統(tǒng)層面的處理細(xì)節(jié)

關(guān)鍵思想：為大數(shù)據(jù)處理過程中的兩個主要處理操作提供一種抽象機(jī)制

MapReduce借鑒了函數(shù)式程序設(shè)計語言Lisp中的思想抗蠢，定義了如下的Map和Reduce兩個抽象的編程接口，由用戶去編程實現(xiàn):

• map: (k1; v1) → [(k2; v2)]
  輸入：鍵值對(k1; v1)表示的數(shù)據(jù)

處理：文檔數(shù)據(jù)記錄(如文本文件中的行思劳，或數(shù)據(jù)表格中的行)將以“鍵值對”形式傳入map函數(shù)迅矛；map函數(shù)將處理這些鍵值對，并以另一種鍵值對形式輸出處理的一組鍵值對中間結(jié)果[(k2; v2)]

輸出：鍵值對[(k2; v2)]表示的一組中間數(shù)據(jù)

• reduce: (k2; [v2]) → [(k3; v3)]
  輸入： 由map輸出的一組鍵值對[(k2; v2)] 將被進(jìn)行合并處理將同樣主鍵下的不同數(shù)值合并到一個列表[v2]中潜叛，故reduce的輸入為(k2; [v2])

處理：對傳入的中間結(jié)果列表數(shù)據(jù)進(jìn)行某種整理或進(jìn)一步的處理,并產(chǎn)生最終的某種形式的結(jié)果輸出[(k3; v3)] 秽褒。

輸出：最終輸出結(jié)果[(k3; v3)]

基于Map和Reduce的并行計算模型

• 各個map函數(shù)對所劃分的數(shù)據(jù)并行處理壶硅，從不同的輸入數(shù)據(jù)產(chǎn)生不同的中間結(jié)果輸出
• 各個reduce也各自并行計算，各自負(fù)責(zé)處理不同的中間結(jié)果數(shù)據(jù)集合?進(jìn)行reduce處理之前,必須等到所有的map函數(shù)做完震嫉，因此,在進(jìn)入reduce前需要有一個同步障(barrier);這個階段也負(fù)責(zé)對map的中間結(jié)果數(shù)據(jù)進(jìn)行收集整理(aggregation & shuffle)處理,以便reduce更有效地計算最終結(jié)
• 最終匯總所有reduce的輸出結(jié)果即可獲得最終結(jié)果

2森瘪、MapReduce運行原理

Job / Task / Tracker

• Job：作業(yè)，一個計算任務(wù)
  Task：一個作業(yè)拆分成多個task票堵，分為MapTask和ReduceTask

• 兩類結(jié)點：
  JobTracker：master管理節(jié)點扼睬；客戶端提交jobs，將job排到候選隊列悴势；對要處理的job拆分成MapTask窗宇，并分發(fā)給各個節(jié)點上的Map TaskTracker來做。
  作用是：（1）作業(yè)調(diào)度特纤；（2）分配任務(wù)給具體的TaskTracker军俊、監(jiān)控TaskTracker的執(zhí)行進(jìn)度；（3）監(jiān)控TaskTracker的狀態(tài)捧存。

TaskTracker：負(fù)責(zé)具體執(zhí)行計算任務(wù)粪躬，通常和要處理的DataNode處于同一個節(jié)點，這樣保證計算是跟著數(shù)據(jù)走的——“移動計算代替移動數(shù)據(jù)”昔穴；向JobTracker匯報任務(wù)狀態(tài)镰官。

MapReduce作業(yè)執(zhí)行過程

MapReduce作業(yè)執(zhí)行過程

（1）輸入數(shù)據(jù)、分片吗货；
（2）按照一定規(guī)則將分片的數(shù)據(jù)分給Map端的TaskTracker泳唠，分配map任務(wù)；
（3）map產(chǎn)生的中間結(jié)果：key-value對（中間結(jié)果寫入到本地磁盤）宙搬，根據(jù)映射規(guī)則進(jìn)行交換笨腥；
（4）將中間結(jié)果傳送到Reduce端的TaskTracker，執(zhí)行Reduce任務(wù)勇垛；
（5）將最終計算結(jié)果寫回HDFS脖母；

• 所有任務(wù)都由JobTracker進(jìn)行分配（Map任務(wù) / Reduce任務(wù)）

MapReduce的容錯機(jī)制

允許TaskTracker出錯、發(fā)生故障闲孤，但保證高可用性

• （1）重復(fù)執(zhí)行：默認(rèn)可重復(fù)執(zhí)行4次
• （2）推測執(zhí)行：正常情況下谆级，所有map任務(wù)執(zhí)行完成后Reduce才開始執(zhí)行，如果中間發(fā)現(xiàn)某個TaskTracker計算非常慢崭放，推測執(zhí)行將會：算的慢的TaskTracker A繼續(xù)計算哨苛，另外在啟動一個TaskTracker B執(zhí)行與A相同的task鸽凶，最后以A币砂、B中先計算完成的為準(zhǔn)。

3玻侥、上升到構(gòu)架-自動并行化并隱藏低層細(xì)節(jié)

如何提供統(tǒng)一的計算框架

MapReduce提供一個統(tǒng)一的計算框架决摧，可完成：

• 計算任務(wù)的劃分和調(diào)度
• 數(shù)據(jù)的分布存儲和劃分
• 處理數(shù)據(jù)與計算任務(wù)的同步
• 結(jié)果數(shù)據(jù)的收集整理(sorting, combining, partitioning,…)
• 系統(tǒng)通信、負(fù)載平衡、計算性能優(yōu)化處理
• 處理系統(tǒng)節(jié)點出錯檢測和失效恢復(fù)

MapReduce最大的亮點：

• 通過抽象模型和計算框架把需要做什么(what need to do)與具體怎么做(how to do)分開了掌桩，為程序員提供一個抽象和高層的編程接口和框架
• 程序員僅需要關(guān)心其應(yīng)用層的具體計算問題边锁，僅需編寫少量的處理應(yīng)用本身計算問題的程序代碼
• 如何具體完成這個并行計算任務(wù)所相關(guān)的諸多系統(tǒng)層細(xì)節(jié)被隱藏起來,交給計算框架去處理：從分布代碼的執(zhí)行，到大到數(shù)千小到單個節(jié)點集群的自動調(diào)度使用

MapReduce提供的主要功能

• 任務(wù)調(diào)度：提交的一個計算作業(yè)(job)將被劃分為很多個計算任務(wù)(tasks), 任務(wù)調(diào)度功能主要負(fù)責(zé)為這些劃分后的計算任務(wù)分配和調(diào)度計算節(jié)點(map節(jié)點或reducer節(jié)點); 同時負(fù)責(zé)監(jiān)控這些節(jié)點的執(zhí)行狀態(tài), 并負(fù)責(zé)map節(jié)點執(zhí)行的同步控制(barrier); 也負(fù)責(zé)進(jìn)行一些計算性能優(yōu)化處理, 如對最慢的計算任務(wù)采用多備份執(zhí)行波岛、選最快完成者作為結(jié)果

• 數(shù)據(jù)/代碼互定位：為了減少數(shù)據(jù)通信茅坛，一個基本原則是本地化數(shù)據(jù)處理(locality)，即一個計算節(jié)點盡可能處理其本地磁盤上所分布存儲的數(shù)據(jù)则拷，這實現(xiàn)了代碼向數(shù)據(jù)的遷移贡蓖；當(dāng)無法進(jìn)行這種本地化數(shù)據(jù)處理時，再尋找其它可用節(jié)點并將數(shù)據(jù)從網(wǎng)絡(luò)上傳送給該節(jié)點(數(shù)據(jù)向代碼遷移)煌茬，但將盡可能從數(shù)據(jù)所在的本地機(jī)架上尋找可用節(jié)點以減少通信延遲

• 出錯處理：以低端商用服務(wù)器構(gòu)成的大規(guī)模MapReduce計算集群中,節(jié)點硬件(主機(jī)斥铺、磁盤、內(nèi)存等)出錯和軟件有bug是常態(tài)坛善，因此,MapReducer需要能檢測并隔離出錯節(jié)點晾蜘，并調(diào)度分配新的節(jié)點接管出錯節(jié)點的計算任務(wù)

• 分布式數(shù)據(jù)存儲與文件管理：海量數(shù)據(jù)處理需要一個良好的分布數(shù)據(jù)存儲和文件管理系統(tǒng)支撐,該文件系統(tǒng)能夠把海量數(shù)據(jù)分布存儲在各個節(jié)點的本地磁盤上,但保持整個數(shù)據(jù)在邏輯上成為一個完整的數(shù)據(jù)文件；為了提供數(shù)據(jù)存儲容錯機(jī)制,該文件系統(tǒng)還要提供數(shù)據(jù)塊的多備份存儲管理能力

• Combiner和Partitioner:為了減少數(shù)據(jù)通信開銷,中間結(jié)果數(shù)據(jù)進(jìn)入reduce節(jié)點前需要進(jìn)行合并(combine)處理,把具有同樣主鍵的數(shù)據(jù)合并到一起避免重復(fù)傳送; 一個reducer節(jié)點所處理的數(shù)據(jù)可能會來自多個map節(jié)點, 因此, map節(jié)點輸出的中間結(jié)果需使用一定的策略進(jìn)行適當(dāng)?shù)膭澐?partitioner)處理剔交，保證相關(guān)數(shù)據(jù)發(fā)送到同一個reducer節(jié)點

4、MapReduce的主要設(shè)計思想和特征

（1）向“外”橫向擴(kuò)展组力，而非向“上”縱向擴(kuò)展（Scale “out", not “up”）

即MapReduce集群的構(gòu)筑選用價格便宜省容、易于擴(kuò)展的大量低端商用服務(wù)器，而非價格昂貴燎字、不易擴(kuò)展的高端服務(wù)器（SMP）腥椒。低端服務(wù)器市場與高容量Desktop PC有重疊的市場，因此候衍，由于相互間價格的競爭笼蛛、可互換的部件、和規(guī)模經(jīng)濟(jì)效應(yīng)蛉鹿，使得低端服務(wù)器保持較低的價格滨砍。基于TPC-C在2007年底的性能評估結(jié)果,一個低端服務(wù)器平臺與高端的共享存儲器結(jié)構(gòu)的服務(wù)器平臺相比,其性價比大約要高4倍;如果把外存價格除外,低端服務(wù)器性價比大約提高12倍妖异。對于大規(guī)模數(shù)據(jù)處理惋戏，由于有大量數(shù)據(jù)存儲需要，顯而易見他膳，基于低端服務(wù)器的集群遠(yuǎn)比基于高端服務(wù)器的集群優(yōu)越响逢，這就是為什么MapReduce并行計算集群會基于低端服務(wù)器實現(xiàn)。

（2）失效被認(rèn)為是常態(tài)（Assume failures are common）

MapReduce集群中使用大量的低端服務(wù)器(Google目前在全球共使用百萬臺以上的服務(wù)器節(jié)點),因此棕孙，節(jié)點硬件失效和軟件出錯是常態(tài)舔亭，因而：一個良好設(shè)計些膨、具有容錯性的并行計算系統(tǒng)不能因為節(jié)點失效而影響計算服務(wù)的質(zhì)量，任何節(jié)點失效都不應(yīng)當(dāng)導(dǎo)致結(jié)果的不一致或不確定性钦铺；任何一個節(jié)點失效時订雾，其它節(jié)點要能夠無縫接管失效節(jié)點的計算任務(wù)；當(dāng)失效節(jié)點恢復(fù)后應(yīng)能自動無縫加入集群矛洞，而不需要管理員人工進(jìn)行系統(tǒng)配置洼哎。MapReduce并行計算軟件框架使用了多種有效的機(jī)制，如節(jié)點自動重啟技術(shù)沼本，使集群和計算框架具有對付節(jié)點失效的健壯性谱净，能有效處理失效節(jié)點的檢測和恢復(fù)。

（3）把處理向數(shù)據(jù)遷移（Moving processing to the data）

傳統(tǒng)高性能計算系統(tǒng)通常有很多處理器節(jié)點與一些外存儲器節(jié)點相連擅威，如用區(qū)域存儲網(wǎng)絡(luò)(SAN,Storage Area Network)連接的磁盤陣列壕探，因此，大規(guī)模數(shù)據(jù)處理時外存文件數(shù)據(jù)I/O訪問會成為一個制約系統(tǒng)性能的瓶頸郊丛。為了減少大規(guī)模數(shù)據(jù)并行計算系統(tǒng)中的數(shù)據(jù)通信開銷李请，代之以把數(shù)據(jù)傳送到處理節(jié)點(數(shù)據(jù)向處理器或代碼遷移)，應(yīng)當(dāng)考慮將處理向數(shù)據(jù)靠攏和遷移厉熟。MapReduce采用了數(shù)據(jù)/代碼互定位的技術(shù)方法，計算節(jié)點將首先將盡量負(fù)責(zé)計算其本地存儲的數(shù)據(jù),以發(fā)揮數(shù)據(jù)本地化特點(locality),僅當(dāng)節(jié)點無法處理本地數(shù)據(jù)時揍瑟，再采用就近原則尋找其它可用計算節(jié)點绢片，并把數(shù)據(jù)傳送到該可用計算節(jié)點。

（4）順序處理數(shù)據(jù)巢株、避免隨機(jī)訪問數(shù)據(jù)（Process data sequentially and avoid random access）

大規(guī)模數(shù)據(jù)處理的特點決定了大量的數(shù)據(jù)記錄不可能存放在內(nèi)存阁苞、而只可能放在外存中進(jìn)行處理祠挫。磁盤的順序訪問和隨即訪問在性能上有巨大的差異等舔。

例：100億(1010)個數(shù)據(jù)記錄(每記錄100B,共計1TB)的數(shù)據(jù)庫软瞎，更新1%的記錄(一定是隨機(jī)訪問)需要1個月時間；而順序訪問并重寫所有數(shù)據(jù)記錄僅需1天時間鳖藕！

MapReduce設(shè)計為面向大數(shù)據(jù)集批處理的并行計算系統(tǒng)著恩，所有計算都被組織成很長的流式操作喉誊，以便能利用分布在集群中大量節(jié)點上磁盤集合的高傳輸帶寬伍茄。

（5）為應(yīng)用開發(fā)者隱藏系統(tǒng)層細(xì)節(jié)（Hide system-level details from the application developer）

軟件工程實踐指南中敷矫，專業(yè)程序員認(rèn)為之所以寫程序困難汉额，是因為程序員需要記住太多的編程細(xì)節(jié)(從變量名到復(fù)雜算法的邊界情況處理)蠕搜，這對大腦記憶是一個巨大的認(rèn)知負(fù)擔(dān),需要高度集中注意力妓灌。而并行程序編寫有更多困難，如需要考慮多線程中諸如同步等復(fù)雜繁瑣的細(xì)節(jié)俱萍，由于并發(fā)執(zhí)行中的不可預(yù)測性枪蘑，程序的調(diào)試查錯也十分困難岳颇；大規(guī)模數(shù)據(jù)處理時程序員需要考慮諸如數(shù)據(jù)分布存儲管理颅湘、數(shù)據(jù)分發(fā)、數(shù)據(jù)通信和同步瞻鹏、計算結(jié)果收集等諸多細(xì)節(jié)問題新博。MapReduce提供了一種抽象機(jī)制將程序員與系統(tǒng)層細(xì)節(jié)隔離開來，程序員僅需描述需要計算什么(what to compute), 而具體怎么去做(how to compute)就交由系統(tǒng)的執(zhí)行框架處理原献，這樣程序員可從系統(tǒng)層細(xì)節(jié)中解放出來姑隅，而致力于其應(yīng)用本身計算問題的算法設(shè)計倔撞。

（6）平滑無縫的可擴(kuò)展性（Seamless scalability）

主要包括兩層意義上的擴(kuò)展性：數(shù)據(jù)擴(kuò)展和系統(tǒng)規(guī)模擴(kuò)展。理想的軟件算法應(yīng)當(dāng)能隨著數(shù)據(jù)規(guī)模的擴(kuò)大而表現(xiàn)出持續(xù)的有效性叮盘，性能上的下降程度應(yīng)與數(shù)據(jù)規(guī)模擴(kuò)大的倍數(shù)相當(dāng)柔吼。在集群規(guī)模上愈魏，要求算法的計算性能應(yīng)能隨著節(jié)點數(shù)的增加保持接近線性程度的增長想际。絕大多數(shù)現(xiàn)有的單機(jī)算法都達(dá)不到以上理想的要求胡本；把中間結(jié)果數(shù)據(jù)維護(hù)在內(nèi)存中的單機(jī)算法在大規(guī)模數(shù)據(jù)處理時很快失效侧甫；從單機(jī)到基于大規(guī)模集群的并行計算從根本上需要完全不同的算法設(shè)計。奇妙的是咒锻，MapReduce幾乎能實現(xiàn)以上理想的擴(kuò)展性特征惑艇。 多項研究發(fā)現(xiàn)基于MapReduce的計算性能可隨節(jié)點數(shù)目增長保持近似于線性的增長滨巴。