MapReduce海量數(shù)據(jù)并行處理ch.02

Ch.2.MapReduce簡(jiǎn)介南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系主講人：黃宜華2011年春季學(xué)期MapReduce海量數(shù)據(jù)并行處理鳴謝：本課程得到Google公司(北京）中國(guó)大學(xué)合作部精品課程計(jì)劃資助Ch.2.

MapReduce簡(jiǎn)介1.對(duì)付大數(shù)據(jù)處理-分而治之2.構(gòu)建抽象模型-Map和Reduce3.上升到構(gòu)架-自動(dòng)并行化并隱藏低層細(xì)節(jié)4.MapReduce的主要設(shè)計(jì)思想和特征大規(guī)模數(shù)據(jù)處理時(shí)，MapReduce在三個(gè)層面上的基本構(gòu)思如何對(duì)付大數(shù)據(jù)處理：分而治之

對(duì)相互間不具有計(jì)算依賴關(guān)系的大數(shù)據(jù)，實(shí)現(xiàn)并行最自然的辦法就是采取分而治之的策略上升到抽象模型：Mapper與Reducer

MPI等并行計(jì)算方法缺少高層并行編程模型，為了克服這一缺陷，MapReduce借鑒了Lisp函數(shù)式語言中的思想，用Map和Reduce兩個(gè)函數(shù)提供了高層的并行編程抽象模型上升到構(gòu)架：統(tǒng)一構(gòu)架，為程序員隱藏系統(tǒng)層細(xì)節(jié)

MPI等并行計(jì)算方法缺少統(tǒng)一的計(jì)算框架支持，程序員需要考慮數(shù)據(jù)存儲(chǔ)、劃分、分發(fā)、結(jié)果收集、錯(cuò)誤恢復(fù)等諸多細(xì)節(jié)；為此，MapReduce設(shè)計(jì)并提供了統(tǒng)一的計(jì)算框架，為程序員隱藏了絕大多數(shù)系統(tǒng)層面的處理細(xì)節(jié)什么樣的計(jì)算任務(wù)可進(jìn)行并行化計(jì)算？

并行計(jì)算的第一個(gè)重要問題是如何劃分計(jì)算任務(wù)或者計(jì)算數(shù)據(jù)以便對(duì)劃分的子任務(wù)或數(shù)據(jù)塊同時(shí)進(jìn)行計(jì)算。

但一些計(jì)算問題恰恰無法進(jìn)行這樣的劃分！

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

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

結(jié)論：不可分拆的計(jì)算任務(wù)或相互間有依賴關(guān)系的數(shù)據(jù)無法進(jìn)行并行計(jì)算！1.如何對(duì)付大數(shù)據(jù)處理：分而治之大數(shù)據(jù)的并行化計(jì)算一個(gè)大數(shù)據(jù)若可以分為具有同樣計(jì)算過程的數(shù)據(jù)塊，并且這些數(shù)據(jù)塊之間不存在數(shù)據(jù)依賴關(guān)系，則提高處理速度的最好辦法就是并行計(jì)算例如：假設(shè)有一個(gè)巨大的2維數(shù)據(jù)需要處理(比如求每個(gè)元素的開立方)，其中對(duì)每個(gè)元素的處理是相同的,并且數(shù)據(jù)元素間不存在數(shù)據(jù)依賴關(guān)系,可以考慮不同的劃分方法將其劃分為子數(shù)組,由一組處理器并行處理

如何對(duì)付大數(shù)據(jù)處理：分而治之大數(shù)據(jù)的并行化計(jì)算

如何對(duì)付大數(shù)據(jù)處理：分而治之合并Master：負(fù)責(zé)劃分和分配任務(wù)Workder：負(fù)責(zé)數(shù)據(jù)塊計(jì)算大數(shù)據(jù)任務(wù)劃分和并行計(jì)算模型

如何對(duì)付大數(shù)據(jù)處理：分而治之大數(shù)據(jù)計(jì)算任務(wù)子任務(wù)子任務(wù)子任務(wù)子任務(wù)……任務(wù)劃分計(jì)算結(jié)果結(jié)果合并借鑒函數(shù)式設(shè)計(jì)語言Lisp的設(shè)計(jì)思想函數(shù)式程序設(shè)計(jì)(functionalprogramming)語言Lisp是一種列表處理語言(Listprocessing)，是一種應(yīng)用于人工智能處理的符號(hào)式語言，由MIT的人工智能專家、圖靈獎(jiǎng)獲得者JohnMcCarthy于1958年設(shè)計(jì)發(fā)明。Lisp定義了可對(duì)列表元素進(jìn)行整體處理的各種操作，如：

如：(add#(1234)#(4321))將產(chǎn)生結(jié)果：

#(5555)Lisp中也提供了類似于Map和Reduce的操作

如:(map‘vector#+#(12345)#(1011121314))

通過定義加法map運(yùn)算將2個(gè)向量相加產(chǎn)生結(jié)果#(1113151719)

(reduce#’+#(1113151719))通過加法歸并產(chǎn)生累加結(jié)果75

2.構(gòu)建抽象模型：Map與ReduceMap:對(duì)一組數(shù)據(jù)元素進(jìn)行某種重復(fù)式的處理Reduce:對(duì)Map的中間結(jié)果進(jìn)行某種進(jìn)一步的結(jié)果整理MPI中的數(shù)據(jù)規(guī)約操作ReduceMPI規(guī)約操作編程示例—計(jì)算積分(參見Ch.1)

for(i=myid;i<N;i=i+numprocs)/*根據(jù)節(jié)點(diǎn)數(shù)目將N個(gè)矩形分為圖示的多個(gè)顏色組*/

{/*每個(gè)節(jié)點(diǎn)計(jì)算一個(gè)顏色組的矩形面積并累加*/

x=a+i*dx+dx/2;/*以每個(gè)矩形的中心點(diǎn)x值計(jì)算矩形高度*/local+=x*x*dx;/*矩形面積=高度x寬度=y*dx*/}

MPI_Reduce(&local,&inte,1,MPI_DOUBLE,MPI_SUM,0,MPI_COMM_WORLD);

if(myid==0)/*規(guī)約所有節(jié)點(diǎn)上的累加和并送到主節(jié)點(diǎn)0*/

{/*主節(jié)點(diǎn)打印累加和*/

printf("Theintegalofx*xinregion[%d,%d]=%16.15f\n",a,b,inte);

}

MPI_Finalize();

}Theintegal

ofx*xinregion[0,10]=33.33345構(gòu)建抽象模型：Map與Reduce構(gòu)建抽象模型：Map與ReduceMPI中的數(shù)據(jù)規(guī)約操作Reduce

將一組進(jìn)程的數(shù)據(jù)按照指定的操作方式規(guī)約到一起并傳送給一個(gè)進(jìn)程

MPI_Reduce(sendbuf,recvbuf,count,datatype,op,root,comm)其中規(guī)約操作op可設(shè)為下表定義的操作之一：MPI_MAX 求最大值 MPI_MIN 求最小值MPI_SUM 求和 MPI_PROD 求積MPI_LAND 邏輯與 MPI_BAND 按位與MPI_LOR 邏輯或 MPI_BOR 按位或MPI_LXOR 邏輯異或 MPI_BXOR 按位異或MPI_MAXLOC最大值和位置 MPI_MINLOC 最小值和位置不足：僅能處理以上規(guī)定的規(guī)約操作，

不能實(shí)現(xiàn)靈活復(fù)雜的規(guī)約操作！構(gòu)建抽象模型：Map與Reduce

關(guān)系數(shù)據(jù)庫中的聚合函數(shù)

對(duì)一個(gè)查詢操作的結(jié)果列表中的字段表達(dá)式進(jìn)行聚合操作

selectOrder_ID,Payment=SUM(Price*Quantity)groupbyOrder_ID

Sum() 計(jì)算表達(dá)式所有值之和 Avg() 計(jì)算表達(dá)式的平均值 Count(*) 計(jì)算某字段中所有值的個(gè)數(shù) Min() 計(jì)算表達(dá)式的最小值 Max() 計(jì)算表達(dá)式的最大值Order_IDItemPriceQuantity1電腦500021打印機(jī)400011硬盤80032電腦600012硬盤6002查詢結(jié)果：Orde_IDPayment

116400

(5000*2+4000*1+800*3)

27200(6000*1+600*2)數(shù)據(jù)庫中的這些聚合函數(shù)類似于對(duì)表格數(shù)據(jù)進(jìn)行的Reduce操作典型的流式大數(shù)據(jù)問題的特征大量數(shù)據(jù)記錄/元素進(jìn)行重復(fù)處理對(duì)每個(gè)數(shù)據(jù)記錄/元素作感興趣的處理、獲取感興趣的中間結(jié)果信息排序和整理中間結(jié)果以利后續(xù)處理收集整理中間結(jié)果產(chǎn)生最終結(jié)果輸出構(gòu)建抽象模型：Map與ReduceMapReduce關(guān)鍵思想：為大數(shù)據(jù)處理過程中的兩個(gè)主要處理操作

提供一種抽象機(jī)制MapReduce中的Map和Reduce操作的抽象描述

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

[(k2;v2)]輸入：鍵值對(duì)(k1;v1)表示的數(shù)據(jù)處理：文檔數(shù)據(jù)記錄(如文本文件中的行，或數(shù)據(jù)表格中的行)將以“鍵值對(duì)”形式傳入map函數(shù)；map函數(shù)將處理這些鍵值對(duì)，并以另一種鍵值對(duì)形式輸出處理的一組鍵值對(duì)中間結(jié)果[(k2;v2)]輸出：鍵值對(duì)[(k2;v2)]表示的一組中間數(shù)據(jù)構(gòu)建抽象模型：Map與ReduceMapReduce中的Map和Reduce操作的抽象描述

reduce:(k2;[v2])

[(k3;v3)]輸入：

由map輸出的一組鍵值對(duì)[(k2;v2)]將被進(jìn)行合并處理將同樣主鍵下的不同數(shù)值合并到一個(gè)列表[v2]中，故reduce的輸入為(k2;[v2])處理：對(duì)傳入的中間結(jié)果列表數(shù)據(jù)進(jìn)行某種整理或進(jìn)一步的處理,并產(chǎn)生最終的某種形式的結(jié)果輸出[(k3;v3)]。輸出：最終輸出結(jié)果[(k3;v3)]Map和Reduce為程序員提供了一個(gè)清晰的操作接口抽象描述構(gòu)建抽象模型：Map與Reduce基于Map和Reduce的并行計(jì)算模型構(gòu)建抽象模型：Map與Reduce海量數(shù)據(jù)存儲(chǔ)……數(shù)據(jù)劃分MapMapMapMap初始kv鍵值對(duì)初始kv鍵值對(duì)初始kv鍵值對(duì)初始kv鍵值對(duì)中間結(jié)果(k1,val)(k2,val)(k3,val)(k1,val)(k3,val)(k2,val)(k3,val)(k1,val)(k2,val)(k3,val)Barrier：AggregationandShuffleReduceReduceReduce(k1,values)(k2,values)(k3,values)計(jì)算結(jié)果(K1,val)(K2,val)(K3,val)基于Map和Reduce的并行計(jì)算模型各個(gè)map函數(shù)對(duì)所劃分的數(shù)據(jù)并行處理，從不同的輸入數(shù)據(jù)產(chǎn)生不同的中間結(jié)果輸出各個(gè)reduce也各自并行計(jì)算，各自負(fù)責(zé)處理不同的中間結(jié)果數(shù)據(jù)集合進(jìn)行reduce處理之前,必須等到所有的map函數(shù)做完，因此,在進(jìn)入reduce前需要有一個(gè)同步障(barrier);這個(gè)階段也負(fù)責(zé)對(duì)map的中間結(jié)果數(shù)據(jù)進(jìn)行收集整理(aggregation&shuffle)處理,以便reduce更有效地計(jì)算最終結(jié)果最終匯總所有reduce的輸出結(jié)果即可獲得最終結(jié)果構(gòu)建抽象模型：Map與Reduce基于MapReduce的處理過程示例--文檔詞頻統(tǒng)計(jì)：WordCount設(shè)有4組原始文本數(shù)據(jù)：Text1:theweatherisgoodText2:todayisgoodText3:goodweatherisgoodText4:today

hasgoodweather傳統(tǒng)的串行處理方式(Java)：

String[]text=newString[]{“helloworld”,“helloeveryone”,“sayhellotoeveryoneintheworld”｝;HashTableht=newHashTable();for(i=0;i<3;++i){StringTokenizerst=newStringTokenizer(text[i]);while(st.hasMoreTokens()){Stringword=st.nextToken();if(!ht.containsKey(word)){ht.put(word,newInteger(1));}else{intwc=((Integer)ht.get(word)).intValue()+1;//計(jì)數(shù)加1ht.put(word,newInteger(wc));}}}for(Iteratoritr=ht.KeySet().iterator();itr.hasNext();){Stringword=(String)itr.next();System.out.print(word+“:”+(Integer)ht.get(word)+“;”);}構(gòu)建抽象模型：Map與Reduce輸出：good:5;has:1;is:3;the:1;today:2;weather:3基于MapReduce的處理過程示例--文檔詞頻統(tǒng)計(jì)：WordCountMapReduce處理方式使用4個(gè)map節(jié)點(diǎn)：map節(jié)點(diǎn)1:

輸入：(text1,“theweatherisgood”)

輸出：(the,1),(weather,1),(is,1),(good,1)map節(jié)點(diǎn)2:

輸入：(text2,“todayisgood”)

輸出：(today,1),(is,1),(good,1)map節(jié)點(diǎn)3:

輸入：(text3,“goodweatherisgood”)

輸出：(good,1),(weather,1),(is,1),(good,1)map節(jié)點(diǎn)4:

輸入：(text3,“todayhasgoodweather”)

輸出：(today,1),(has,1),(good,1),(weather,1)構(gòu)建抽象模型：Map與Reduce基于MapReduce的處理過程示例--文檔詞頻統(tǒng)計(jì)：WordCountMapReduce處理方式使用3個(gè)reduce節(jié)點(diǎn)：reduce節(jié)點(diǎn)1:

輸入：(good,1),(good,1),(good,1),(good,1),(good,1)

輸出：(good,5)reduce節(jié)點(diǎn)2:

輸入：(has,1),(is,1),(is,1),(is,1),

輸出：(has,1),(is,3)reduce節(jié)點(diǎn)3:

輸入：(the,1),(today,1),(today,1)(weather,1),(weather,1),(weather,1)

輸出：(the,1),(today,2),(weather,3)構(gòu)建抽象模型：Map與Reduce輸出：good:5is:3has:1the:1today:2weather:3基于MapReduce的處理過程示例--文檔詞頻統(tǒng)計(jì)：WordCountMapReduce處理方式MapReduce偽代碼(實(shí)現(xiàn)Map和Reduce兩個(gè)函數(shù))：構(gòu)建抽象模型：Map與ReduceClassMappermethodmap(Stringinput_key,Stringinput_value):

//input_key:textdocumentname//input_value:documentcontents

foreachwordwininput_value:

EmitIntermediate(w,"1");ClassReducermethodreduce(Stringoutput_key,Iteratorintermediate_values):

//output_key:aword//output_values:alistofcounts

intresult=0;

foreachvinintermediate_values:result+=ParseInt(v);

Emit(AsString(result));如何提供統(tǒng)一的計(jì)算框架主要需求和目標(biāo)：實(shí)現(xiàn)自動(dòng)并行化計(jì)算為程序員隱藏系統(tǒng)層細(xì)節(jié)需要考慮的細(xì)節(jié)技術(shù)問題：如何管理和存儲(chǔ)數(shù)據(jù)？如何劃分?jǐn)?shù)據(jù)？如何調(diào)度計(jì)算任務(wù)并分配map和reduce節(jié)點(diǎn)？如果節(jié)點(diǎn)間需要共享或交換數(shù)據(jù)怎么辦？如何考慮數(shù)據(jù)通信和同步？如何掌控節(jié)點(diǎn)的執(zhí)行完成情況？如何收集中間和最終的結(jié)果數(shù)據(jù)？節(jié)點(diǎn)失效如何處理？如何恢復(fù)數(shù)據(jù)？如何恢復(fù)計(jì)算任務(wù)？節(jié)點(diǎn)擴(kuò)充后如何保證原有程序仍能正常運(yùn)行并保證系統(tǒng)性能提升？問題：我們能把這些細(xì)節(jié)和復(fù)雜性交給系統(tǒng)去負(fù)責(zé)處理嗎？3.上升到構(gòu)架:自動(dòng)并行化并隱藏底層細(xì)節(jié)如何提供統(tǒng)一的計(jì)算框架答案：MapReduce之前的并行計(jì)算方法都未能做到

但MapReduce做到了！MapReduce提供一個(gè)統(tǒng)一的計(jì)算框架，可完成：計(jì)算任務(wù)的劃分和調(diào)度數(shù)據(jù)的分布存儲(chǔ)和劃分處理數(shù)據(jù)與計(jì)算任務(wù)的同步結(jié)果數(shù)據(jù)的收集整理(sorting,combining,partitioning,…)系統(tǒng)通信、負(fù)載平衡、計(jì)算性能優(yōu)化處理處理系統(tǒng)節(jié)點(diǎn)出錯(cuò)檢測(cè)和失效恢復(fù)上升到構(gòu)架：自動(dòng)化并行并隱藏低層細(xì)節(jié)如何提供統(tǒng)一的計(jì)算框架MapReduce最大的亮點(diǎn)通過抽象模型和計(jì)算框架把需要做什么(whatneedtodo)與具體怎么做(howtodo)分開了，為程序員提供一個(gè)抽象和高層的編程接口和框架程序員僅需要關(guān)心其應(yīng)用層的具體計(jì)算問題，僅需編寫少量的處理應(yīng)用本身計(jì)算問題的程序代碼如何具體完成這個(gè)并行計(jì)算任務(wù)所相關(guān)的諸多系統(tǒng)層細(xì)節(jié)被隱藏起來,交給計(jì)算框架去處理：從分布代碼的執(zhí)行，到大到數(shù)千小到單個(gè)節(jié)點(diǎn)集群的自動(dòng)調(diào)度使用上升到構(gòu)架：自動(dòng)化并行并隱藏低層細(xì)節(jié)如何提供統(tǒng)一的計(jì)算框架MapReduce提供的主要功能*任務(wù)調(diào)度：提交的一個(gè)計(jì)算作業(yè)(job)將被劃分為很多個(gè)計(jì)算任務(wù)(tasks),任務(wù)調(diào)度功能主要負(fù)責(zé)為這些劃分后的計(jì)算任務(wù)分配和調(diào)度計(jì)算節(jié)點(diǎn)(map節(jié)點(diǎn)或reducer節(jié)點(diǎn));同時(shí)負(fù)責(zé)監(jiān)控這些節(jié)點(diǎn)的執(zhí)行狀態(tài),并負(fù)責(zé)map節(jié)點(diǎn)執(zhí)行的同步控制(barrier);也負(fù)責(zé)進(jìn)行一些計(jì)算性能優(yōu)化處理,如對(duì)最慢的計(jì)算任務(wù)采用多備份執(zhí)行、選最快完成者作為結(jié)果數(shù)據(jù)/代碼互定位：為了減少數(shù)據(jù)通信，一個(gè)基本原則是本地化數(shù)據(jù)處理(locality)，即一個(gè)計(jì)算節(jié)點(diǎn)盡可能處理其本地磁盤上所分布存儲(chǔ)的數(shù)據(jù)，這實(shí)現(xiàn)了代碼向數(shù)據(jù)的遷移；當(dāng)無法進(jìn)行這種本地化數(shù)據(jù)處理時(shí)，再尋找其它可用節(jié)點(diǎn)并將數(shù)據(jù)從網(wǎng)絡(luò)上傳送給該節(jié)點(diǎn)(數(shù)據(jù)向代碼遷移)，但將盡可能從數(shù)據(jù)所在的本地機(jī)架上尋找可用節(jié)點(diǎn)以減少通信延遲上升到構(gòu)架：自動(dòng)化并行并隱藏低層細(xì)節(jié)*CitefromJimmyLin,University

ofMaryland,Data-IntensiveTextprocessingwithMapReduce如何提供統(tǒng)一的計(jì)算框架MapReduce提供的主要功能出錯(cuò)處理：以低端商用服務(wù)器構(gòu)成的大規(guī)模MapReduce計(jì)算集群中,節(jié)點(diǎn)硬件(主機(jī)、磁盤、內(nèi)存等)出錯(cuò)和軟件有bug是常態(tài)，因此,MapReducer需要能檢測(cè)并隔離出錯(cuò)節(jié)點(diǎn)，并調(diào)度分配新的節(jié)點(diǎn)接管出錯(cuò)節(jié)點(diǎn)的計(jì)算任務(wù)分布式數(shù)據(jù)存儲(chǔ)與文件管理：海量數(shù)據(jù)處理需要一個(gè)良好的分布數(shù)據(jù)存儲(chǔ)和文件管理系統(tǒng)支撐,該文件系統(tǒng)能夠把海量數(shù)據(jù)分布存儲(chǔ)在各個(gè)節(jié)點(diǎn)的本地磁盤上,但保持整個(gè)數(shù)據(jù)在邏輯上成為一個(gè)完整的數(shù)據(jù)文件；為了提供數(shù)據(jù)存儲(chǔ)容錯(cuò)機(jī)制,該文件系統(tǒng)還要提供數(shù)據(jù)塊的多備份存儲(chǔ)管理能力Combiner和Partitioner:為了減少數(shù)據(jù)通信開銷,中間結(jié)果數(shù)據(jù)進(jìn)入reduce節(jié)點(diǎn)前需要進(jìn)行合并(combine)處理,把具有同樣主鍵的數(shù)據(jù)合并到一起避免重復(fù)傳送;一個(gè)reducer節(jié)點(diǎn)所處理的數(shù)據(jù)可能會(huì)來自多個(gè)map節(jié)點(diǎn),因此,map節(jié)點(diǎn)輸出的中間結(jié)果需使用一定的策略進(jìn)行適當(dāng)?shù)膭澐?partitioner)處理，保證相關(guān)數(shù)據(jù)發(fā)送到同一個(gè)reducer節(jié)點(diǎn)上升到構(gòu)架：自動(dòng)化并行并隱藏低層細(xì)節(jié)Barrier(good,1)(good,1)(good,2)(good,1)PartitionerPartitionerPartitionerPartitioner(is,1)(is,1)(is,1)(has,1)(weather,1)(weather,1)(weather,1)(the,1)(today,1)(today,1)基于Map和Reduce的并行計(jì)算模型構(gòu)建抽象模型：Map與Reduce海量數(shù)據(jù)存儲(chǔ)計(jì)算結(jié)果……數(shù)據(jù)劃分Map初始kv鍵值對(duì)初始kv鍵值對(duì)初始kv鍵值對(duì)初始kv鍵值對(duì)MapMapMap中間結(jié)果(the,1)(weather,1)(is,1)(good,1)CombinerCombinerCombinerCombiner(the,1)(weather,1)(is,1)(good,1)(today,1)(is,1)(good,1)(good,1)(weather,1)(is,1)(good,1)(today,1)(has,1)(good,1)(weather,1)(today,1)(is,1)(good,1)(good,2)(weather,1)(is,1)(today,1)(has,1)(good,1)(weather,1)ReduceReduceReduce(good,5)(is,3)(has,1)(weather,3)(the,1)(today,2)Combiner和Partitioner4.MapReduce的主要設(shè)計(jì)思想與特點(diǎn)*

向“外”橫向擴(kuò)展，而非向“上”縱向擴(kuò)展

Scale“out",not“up”

即MapReduce集群的構(gòu)筑選用價(jià)格便宜、易于擴(kuò)展的大量低端商用服務(wù)器，而非價(jià)格昂貴、不易擴(kuò)展的高端服務(wù)器（SMP）低端服務(wù)器市場(chǎng)與高容量DesktopPC有重疊的市場(chǎng)，因此，由于相互間價(jià)格的競(jìng)爭(zhēng)、可互換的部件、和規(guī)模經(jīng)濟(jì)效應(yīng)，使得低端服務(wù)器保持較低的價(jià)格基于TPC-C在2007年低的性能評(píng)估結(jié)果,一個(gè)低端服務(wù)器平臺(tái)與高端的共享存儲(chǔ)器結(jié)構(gòu)的服務(wù)器平臺(tái)相比,其性價(jià)比大約要高4倍;如果把外存價(jià)格除外,低端服務(wù)器性價(jià)比大約提高12倍對(duì)于大規(guī)模數(shù)據(jù)處理，由于有大量數(shù)據(jù)存儲(chǔ)需要，顯而易見，基于低端服務(wù)器的集群遠(yuǎn)比基于高端服務(wù)器的集群優(yōu)越，這就是為什么MapReduce并行計(jì)算集群會(huì)基于低端服務(wù)器實(shí)現(xiàn)*CitefromJimmyLin,University

ofMaryland,Data-IntensiveTextprocessingwithMapReduceMapReduce的主要設(shè)計(jì)思想與特點(diǎn)

失效被認(rèn)為是常態(tài)

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

把處理向數(shù)據(jù)遷移

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

順序處理數(shù)據(jù)、避免隨機(jī)訪問數(shù)據(jù)

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

例：100億(1010)個(gè)數(shù)據(jù)記錄(每記錄100B,共計(jì)1TB)的數(shù)據(jù)庫

更新1%的記錄(一定是隨機(jī)訪問)需要1個(gè)月時(shí)間；

而順序訪問并重寫所有數(shù)據(jù)記錄僅需1天時(shí)間！MapReduce設(shè)計(jì)為面向大數(shù)據(jù)集批處理的并行計(jì)算系統(tǒng)，所有計(jì)算都被組織成很長(zhǎng)的流式操作，以便能利用分布在集群中大量節(jié)點(diǎn)上磁盤集合的高傳輸帶寬。MapReduce的主要設(shè)計(jì)思想與特點(diǎn)

為應(yīng)用開發(fā)者隱藏系統(tǒng)層細(xì)節(jié)

Hidesystem-leveldetailsfromtheapplicationdeveloper軟件工程實(shí)踐指南中，專業(yè)程序員認(rèn)為之所以寫程序困難，是因?yàn)槌绦騿T需要記住太多的編程細(xì)節(jié)(從變量