第六章+大規(guī)模數(shù)據(jù)處理編程模型-20121025

1CloudComputingAutumn,2012Chapter6ProgrammingModelforMassiveDataProcessingXuJungang1202-2月-23CloudComputing,

GUCAS2提綱1.大規(guī)模數(shù)據(jù)處理2.并行編程3.MapReduce基本原理4.MapReduce的實(shí)現(xiàn)3數(shù)據(jù)的爆炸性增長(zhǎng)Source:IDC,“TheExpandingDigitalUniverse,”SponsoredbyEMC,updatedonMarch‘082005200620072008200920105年內(nèi)10倍增長(zhǎng)每年復(fù)合增長(zhǎng)≈60%全球：5年內(nèi)10倍增長(zhǎng)中國：5年內(nèi)30倍增長(zhǎng)4互聯(lián)網(wǎng)應(yīng)用飛速發(fā)展搜索引擎Google百度必應(yīng)…SNS網(wǎng)站Facebook人人網(wǎng)Linkedin開心網(wǎng)…...電子商務(wù)淘寶京東Amazon…微博Twitter新浪微博騰訊微薄…已經(jīng)產(chǎn)生和正在產(chǎn)生大規(guī)模的海量的數(shù)據(jù)5云計(jì)算應(yīng)用的迅速開展Google（GAE）Microsoft（WindowsAzure)Amazon（EC2,S3）IBM（BlueCloud）Salesforce(CRM）中國移動(dòng)（BigCloud)……預(yù)期產(chǎn)生規(guī)模更大的海量數(shù)據(jù)6物聯(lián)網(wǎng)未來應(yīng)用無處不在流通環(huán)保農(nóng)業(yè)工業(yè)個(gè)人生活……預(yù)期產(chǎn)生級(jí)數(shù)級(jí)增長(zhǎng)的海量數(shù)據(jù)7大規(guī)模數(shù)據(jù)的特點(diǎn)V3Volume（量大）Varity（種類多）Velocity（變化快，即數(shù)據(jù)新增速度快）8大規(guī)模數(shù)據(jù)存儲(chǔ)和處理要求和方案存儲(chǔ)和管理存儲(chǔ)PB級(jí)的處理存儲(chǔ)多種多樣的數(shù)據(jù)支持分布式處理處理PB級(jí)的多種數(shù)據(jù)低延遲讀寫速度成本較低的軟硬件成本較低的人力成本分布式文件系統(tǒng)NoSQL數(shù)據(jù)庫NoSQL數(shù)據(jù)庫并行編程模型云計(jì)算開源軟件902-2月-23CloudComputing,

GUCAS9提綱1.大規(guī)模數(shù)據(jù)處理2.并行編程3.MapReduce基本原理4.MapReduce的實(shí)現(xiàn)10ParallelcomputingParallelcomputingisaformofcomputationinwhichmanycalculationsarecarriedoutsimultaneously,operatingontheprinciplethatlargeproblemscanoftenbedividedintosmallerones,whicharethensolvedconcurrently("inparallel").Thereareseveraldifferentformsofparallelcomputing:bit-level,instructionlevel,data,andtaskparallelism.11ParallelprogrammingmodelAparallelprogrammingmodelisaconceptthatenablestheexpressionofparallelprogramswhichcanbecompiledandexecuted.Thevalueofaprogrammingmodelisusuallyjudgedonitsgenerality:howwellarangeofdifferentproblemscanbeexpressedandhowwelltheyexecuteonarangeofdifferentarchitectures.Theimplementationofaprogrammingmodelcantakeseveralformssuchaslibrariesinvokedfromtraditionalsequentiallanguages,languageextensions,orcompletenewexecutionmodels.12并行編程的原因加快速度即在更短的時(shí)間內(nèi)解決相同的問題或在相同的時(shí)間內(nèi)解決更多更復(fù)雜的問題特別是對(duì)一些新出現(xiàn)的巨大的挑戰(zhàn)問題，不使用并行計(jì)算是根本無法解決的1213并行編程的原因節(jié)省投入并行計(jì)算可以以較低的投入完成串行計(jì)算才能夠完成的任務(wù)物理極限的約束光速是不可逾越的速度極限，設(shè)備和材料也不可能做得無限小，只有通過并行才能夠不斷提高速度1314并行編程的概念并行編程是指同時(shí)使用多種計(jì)算資源解決計(jì)算問題的過程，是提高計(jì)算機(jī)系統(tǒng)計(jì)算速度和處理能力的一種有效手段。它的基本思想是用多個(gè)處理器來協(xié)同求解同一問題，即將被求解的問題分解成若干個(gè)部分，各部分均由一個(gè)獨(dú)立的處理機(jī)來進(jìn)行計(jì)算。并行編程系統(tǒng)既可以是專門設(shè)計(jì)的、含有多個(gè)處理器的超級(jí)計(jì)算機(jī)，也可以是以某種方式互連的若干臺(tái)獨(dú)立計(jì)算機(jī)構(gòu)成的集群。1415并行編程的分類目前最主要的并行編程模型：共享內(nèi)存線程數(shù)據(jù)并行消息傳遞混合模型16共享內(nèi)存模型在共享內(nèi)存編程模型中，任務(wù)間共享統(tǒng)一的可以異步讀寫的內(nèi)存地址空間。一般僅需指定可以并行執(zhí)行的循環(huán)，而不需考慮計(jì)算與數(shù)據(jù)如何劃分，以及如何進(jìn)行任務(wù)間通信，編譯器會(huì)自動(dòng)完成上述功能。這個(gè)模型的優(yōu)點(diǎn)是對(duì)于程序員來說數(shù)據(jù)沒有身份的區(qū)分，不需要特別清楚任務(wù)間的數(shù)據(jù)通信。程序開發(fā)也相應(yīng)的得以簡(jiǎn)化。典型代表是OpenMP編程模型。17線程模型在線程模型中，單個(gè)處理器可以有多個(gè)并行的執(zhí)行路徑。典型代表是Unix操作系統(tǒng)中基于POSIX接口的編程線程模型的構(gòu)成如下：1.操作系統(tǒng)調(diào)度主程序a.out開始運(yùn)行，a.out加載所有必要的系統(tǒng)資源和用戶資源開始執(zhí)行。2.a.out完成一些串行工作，然后創(chuàng)建一些可以被操作系統(tǒng)調(diào)度的并行任務(wù)（線程）去執(zhí)行。3.每次線程都有自己的數(shù)據(jù)，而且共享整個(gè)a.out的資源。這樣就節(jié)省了拷貝程序資源給每個(gè)線程的開銷。這樣線程之間可以并行執(zhí)行子程序。4.線程之間通過全局內(nèi)存進(jìn)行通信。這個(gè)需要同步構(gòu)造來確保多個(gè)線程不會(huì)同時(shí)更新同一塊全局內(nèi)存。5.線程執(zhí)行完了就自動(dòng)銷毀，但是主程序a.out在應(yīng)用程序完成之前一直存在，維護(hù)必要的共享資源。18數(shù)據(jù)并行編程模型數(shù)據(jù)并行即將相同的操作同時(shí)作用于不同的數(shù)據(jù)，數(shù)據(jù)并行編程模型提供給編程者一個(gè)全局的地址空間，一般這種形式的語言本身就提供并行執(zhí)行的語義對(duì)于編程者來說，只需要簡(jiǎn)單地指明執(zhí)行什么樣的并行操作和并行操作的對(duì)象，就實(shí)現(xiàn)了數(shù)據(jù)并行的編程比如對(duì)于數(shù)組運(yùn)算，使得數(shù)組B和C的對(duì)應(yīng)元素相加后送給A，則通過語句

A=B+C（或其它的表達(dá)方式）

就能夠?qū)崿F(xiàn)上述功能，使并行機(jī)對(duì)B、C的對(duì)應(yīng)元素并行相加，并將結(jié)果并行賦給A。數(shù)據(jù)并行的表達(dá)是相對(duì)簡(jiǎn)單和簡(jiǎn)潔的，它不需要編程者關(guān)心并行機(jī)是如何對(duì)該操作進(jìn)行并行執(zhí)行的。1819數(shù)據(jù)并行編程模型20數(shù)據(jù)并行編程模型數(shù)據(jù)并行模型有以下特性：并行工作主要是操縱數(shù)據(jù)集。數(shù)據(jù)集一般都是像數(shù)組一樣典型的通用的數(shù)據(jù)結(jié)構(gòu)。任務(wù)集都使用相同的數(shù)據(jù)結(jié)構(gòu)，但是，每個(gè)任務(wù)都有自己的數(shù)據(jù)。每個(gè)任務(wù)的工作都是相同的。21消息傳遞并行編程模型消息傳遞即各個(gè)并行執(zhí)行的部分之間通過傳遞消息來交換信息、協(xié)調(diào)步伐、控制執(zhí)行。消息傳遞一般是面向分布式內(nèi)存的，但是它也可適用于共享內(nèi)存的并行機(jī)。消息傳遞為編程者提供了更靈活的控制手段和表達(dá)并行的方法，一些用數(shù)據(jù)并行方法很難表達(dá)的并行算法，都可以用消息傳遞模型來實(shí)現(xiàn)，靈活性和控制手段的多樣化，是消息傳遞并行程序能提供高的執(zhí)行效率的重要原因。消息傳遞模型一方面為編程者提供了靈活性，另一方面，它也將各個(gè)并行執(zhí)行部分之間復(fù)雜的信息交換和協(xié)調(diào)、控制的任務(wù)交給了編程者，這在一定程度上增加了編程者的負(fù)擔(dān)，這也是消息傳遞編程模型編程級(jí)別低的主要原因。2122消息傳遞并行編程模型23消息傳遞并行編程模型消息傳遞模型有以下三個(gè)特征：計(jì)算時(shí)任務(wù)集可以用他們自己的內(nèi)存。多任務(wù)可以在相同的物理處理器上，同時(shí)可以訪問任意數(shù)量的處理器。任務(wù)之間通過接收和發(fā)送消息來進(jìn)行數(shù)據(jù)通信。數(shù)據(jù)傳輸通常需要每個(gè)處理器協(xié)調(diào)操作來完成。24消息傳遞與數(shù)據(jù)并行的對(duì)比2425消息傳遞與數(shù)據(jù)并行的對(duì)比數(shù)據(jù)并行編程模型的編程級(jí)別比較高，編程相對(duì)簡(jiǎn)單，但它僅適用于數(shù)據(jù)并行問題消息傳遞編程模型的編程級(jí)別相對(duì)較低，但消息傳遞編程模型可以有更廣泛的應(yīng)用范圍。數(shù)據(jù)并行的主要特征是以數(shù)據(jù)為中心，通過對(duì)數(shù)據(jù)的劃分和并行處理來解決問題消息傳遞當(dāng)然也可以實(shí)現(xiàn)上述功能，但是消息傳遞在問題的表述上更具體，更低級(jí)，可以解決的問題相對(duì)于數(shù)據(jù)并行模型來說也更廣泛。在一定程度上，可以把數(shù)據(jù)并行看作是消息傳遞的一種特殊形式。26消息傳遞與數(shù)據(jù)并行的對(duì)比2627混合模型這個(gè)模型中，通常是由兩個(gè)或多個(gè)模型組合在一起實(shí)現(xiàn)的。當(dāng)前通用的混合模型的例子就是：由消息傳遞模型（MPI）和線程模型（POSIX）或者共享內(nèi)存模型（OpenMP）組成而成?；旌夏Ｐ椭衅渌容^通用的模型是：將數(shù)據(jù)并行和消息傳遞組合起來。正如我們上面在數(shù)據(jù)并行模型部分提到的那樣，在分布式體系結(jié)構(gòu)上實(shí)現(xiàn)數(shù)據(jù)并行模型實(shí)際上是用消息傳遞的方法來為任務(wù)間傳遞數(shù)據(jù)的，對(duì)程序員是透明的。28現(xiàn)有主要編程模型OpenMPMPIDryadMapReduce2829OpenMP概述OpenMP應(yīng)用編程接口API是在共享內(nèi)存體系結(jié)構(gòu)上的一個(gè)編程模型包含編譯制導(dǎo)(CompilerDirective)、運(yùn)行庫例程(RuntimeLibrary)和環(huán)境變量(EnvironmentVariables)等組件。支持C/C++和Fortan等編程語言已經(jīng)被大多數(shù)計(jì)算機(jī)硬件和軟件廠家所標(biāo)準(zhǔn)化30OpenMP的歷史1994年，第一個(gè)ANSIX3H5草案提出，被否決1997年，OpenMP標(biāo)準(zhǔn)規(guī)范代替原先被否決的ANSIX3H5，被人們認(rèn)可1997年10月公布了與Fortran語言捆綁的第一個(gè)標(biāo)準(zhǔn)規(guī)范FORTRANversion1.0

1998年11月9日公布了支持C和C++的標(biāo)準(zhǔn)規(guī)范C/C++version1.0

2000年11月推出FORTRANversion2.0

2002年3月推出C/C++version2.0

2005年5月OpenMP2.5將原來的Fortran和C/C++標(biāo)準(zhǔn)規(guī)范相結(jié)合相關(guān)的規(guī)范在/drupal/node/view/831OpenMP程序結(jié)構(gòu)基于Fortran語言的OpenMP程序的結(jié)構(gòu)

PROGRAMHELLO

INTEGERVAR1,VAR2,VAR3

!Serialcode

…

!Beginningofparallelsection.Forkateamofthreads.

!Specifyvariablescoping

!$OMPPARALLELPRIVATE(VAR1,VAR2)SHARED(VAR3)

!Parallelsectionexecutedbyallthreads

…

!Allthreadsjoinmasterthreadanddisband

!$OMPENDPARALLEL

!Resumeserialcode

…

END

32OpenMP程序結(jié)構(gòu)基于C/C++語言的OpenMP程序的結(jié)構(gòu)

#include<omp.h> main(){ intvar1,var2,var3;

/*Serialcode*/ … /*Beginningofparallelsection.Forkateamofthreads*/ /*Specifyvariablescoping*/

#pragmaompparallelprivate(var1,var2)shared(var3)

{ /*Parallelsectionexecutedbyallthreads*/ … /*Allthreadsjoinmasterthreadanddisband*/ } /*Resumeserialcode*/ … }33MPIMPI是一種消息傳遞編程模型，并成為這種編程模型的代表和事實(shí)上的標(biāo)準(zhǔn)MPI是一種標(biāo)準(zhǔn)或規(guī)范的代表，而不特指某一個(gè)對(duì)它的具體實(shí)現(xiàn)MPI是一個(gè)庫，而不是一門語言MPI庫可以被FORTRAN77/C/Fortran90/C++調(diào)用。從語法上說它遵守所有對(duì)庫函數(shù)/過程的調(diào)用規(guī)則，和一般的函數(shù)/過程沒有什么區(qū)別。最終目的是服務(wù)于進(jìn)程間通信這一目標(biāo)。目前已經(jīng)有MPI1和MPI2的標(biāo)準(zhǔn)。3334MPI發(fā)展歷史3435典型MPI的實(shí)現(xiàn)典型的MPI實(shí)現(xiàn)包括：開源的MPICH、LAMMPI不開源的INTELMPI36MPICHMPICH是影響最大、用戶最多的MPI實(shí)現(xiàn)由美國的Argonne國家實(shí)驗(yàn)室開發(fā)MPICH的特點(diǎn)：開放源碼；與MPI標(biāo)準(zhǔn)同步發(fā)展；支持多程序多數(shù)據(jù)（MPMD）編程和異構(gòu)集群系統(tǒng)；支持C/C++、Fortran77和Fortran90的綁定,支持類Unix和WindowsNT平臺(tái)；支持環(huán)境非常廣泛，包括多核、SMP、集群和大規(guī)模并行計(jì)算系統(tǒng)。37IntelMPI由Intel公司推出的符合MPI-2標(biāo)準(zhǔn)的MPI實(shí)現(xiàn)IntelMPI提供了名為DirectAccessProgrammingLibrary（DAPL）的中間層來支持多架構(gòu)，兼容多種網(wǎng)絡(luò)硬件及協(xié)議，優(yōu)化網(wǎng)絡(luò)互聯(lián)IntelMPI透明地支持TCP/IP、Myrinet、共享內(nèi)存，并基于DAPL有效支持多種高性能互聯(lián)系統(tǒng)IntelMPI在通信協(xié)議的選擇上無需進(jìn)行額外設(shè)置，可自動(dòng)選擇MPI進(jìn)程間最快的傳輸協(xié)議。38MPI程序的優(yōu)點(diǎn)用戶可以控制并行開發(fā)支持?jǐn)?shù)據(jù)分布通信實(shí)現(xiàn)完全控制39MPI程序的缺點(diǎn)要求程序員顯式地處理通信問題,如,消息傳遞調(diào)用的位置,數(shù)據(jù)移動(dòng),數(shù)據(jù)復(fù)制,數(shù)據(jù)操作,數(shù)據(jù)的一致性等等.

對(duì)大多數(shù)科學(xué)計(jì)算程序來說,消息傳遞模型的真正困難還在于顯式的數(shù)據(jù)分解無法以漸進(jìn)的方式、通過逐步將串行代碼轉(zhuǎn)換成并行代碼而開發(fā)出來406個(gè)基本函數(shù)組成的MPI子集#include"mpi.h"/*MPI頭函數(shù)，提供了MPI函數(shù)和數(shù)據(jù)類型定義*/intmain(intargc,char**argv){intrank,size,tag=1;intsenddata,recvdata;MPI_Statusstatus;MPI_Init(&argc,&argv);/*MPI的初始化函數(shù)*/MPI_Comm_rank(MPI_COMM_WORLD,&rank);/*該進(jìn)程編號(hào)*/MPI_Comm_size(MPI_COMM_WORLD,&size);/*總進(jìn)程數(shù)目*/416個(gè)基本函數(shù)組成的MPI子集if(rank==0){senddata=9999;MPI_Send(&senddata,1,MPI_INT,1,tag,MPI_COMM_WORLD);/*發(fā)送數(shù)據(jù)到進(jìn)程1*/}if(rank==1)MPI_Recv(&recvdata,1,MPI_INT,0,tag,MPI_COMM_WORLD,&status);/*從進(jìn)程0接收數(shù)據(jù)*/MPI_Finalize();/*MPI的結(jié)束函數(shù)*/return(0);}426個(gè)基本函數(shù)組成的MPI子集MPI初始化：通過MPI_Init函數(shù)進(jìn)入MPI環(huán)境并完成所有的初始化工作。intMPI_Init(int*argc,char***argv)MPI結(jié)束：通過MPI_Finalize函數(shù)從MPI環(huán)境中退出。intMPI_Finalize(void)436個(gè)基本函數(shù)組成的MPI子集獲取進(jìn)程的編號(hào)：調(diào)用MPI_Comm_rank函數(shù)獲得當(dāng)前進(jìn)程在指定通信域中的編號(hào)，將自身與其他程序區(qū)分。intMPI_Comm_rank(MPI_Commcomm,int*rank)獲取指定通信域的進(jìn)程數(shù)：調(diào)用MPI_Comm_size函數(shù)獲取指定通信域的進(jìn)程個(gè)數(shù)，確定自身完成任務(wù)比例。intMPI_Comm_size(MPI_Commcomm,int*size)446個(gè)基本函數(shù)組成的MPI子集消息發(fā)送：MPI_Send函數(shù)用于發(fā)送一個(gè)消息到目標(biāo)進(jìn)程。intMPI_Send(void*buf,intcount,MPI_Datatypedataytpe,intdest,inttag,MPI_Commcomm)消息接受:MPI_Recv函數(shù)用于從指定進(jìn)程接收一個(gè)消息intMPI_Recv(void*buf,intcount,MPI_Datatypedatatyepe,intsource,inttag,MPI_Commcomm,MPI_Status*status)45MPI消息一個(gè)消息好比一封信消息的內(nèi)容,即信的內(nèi)容，在MPI中稱為消息緩沖(MessageBuffer)消息的接收/發(fā)送者,即信的地址，在MPI中稱為消息信封(MessageEnvelop)46MPI消息MPI中，消息緩沖由三元組<起始地址，數(shù)據(jù)個(gè)數(shù)，數(shù)據(jù)類型>標(biāo)識(shí)消息信封由三元組<源/目標(biāo)進(jìn)程，消息標(biāo)簽，通信域>標(biāo)識(shí)三元組的方式使得MPI可以表達(dá)更為豐富的信息，功能更強(qiáng)大47Dryad微軟于2010年12月21日發(fā)布了分布式并行計(jì)算基礎(chǔ)平臺(tái)——Dryad測(cè)試版，成為谷歌MapReduce分布式數(shù)據(jù)計(jì)算平臺(tái)的競(jìng)爭(zhēng)對(duì)手。它可以使開發(fā)人員能夠在Windows或者.Net平臺(tái)上編寫大規(guī)模的并行應(yīng)用程序模型，并使在單機(jī)上所編寫的程序很輕易的運(yùn)行在分布式并行計(jì)算平臺(tái)上程序員可以利用數(shù)據(jù)中心的服務(wù)器集群對(duì)數(shù)據(jù)進(jìn)行并行處理，當(dāng)程序開發(fā)人員在操作數(shù)千臺(tái)機(jī)器時(shí)，而無需關(guān)心分布式并行處理系統(tǒng)方面的細(xì)節(jié)。4748Dryad4849DryadDryad同MapReduce一樣，它不僅僅是一種編程模型，同時(shí)也是一種高效的任務(wù)調(diào)度模型。Dryad這種編程模型并不僅適用于云計(jì)算，在多核和多處理器以及異構(gòu)機(jī)群上同樣有良好的性能。Dryad可以對(duì)計(jì)算機(jī)和它們的CPU進(jìn)行調(diào)度，不同的是Dryad被設(shè)計(jì)為伸縮于各種規(guī)模的集群計(jì)算平臺(tái)，無論是單臺(tái)多核計(jì)算機(jī)還是到由多臺(tái)計(jì)算機(jī)組成的集群，甚至擁有數(shù)千臺(tái)計(jì)算機(jī)的數(shù)據(jù)中心，可以從任務(wù)隊(duì)列中創(chuàng)建的策略建模來實(shí)現(xiàn)分布式并行計(jì)算的編程框架。02-2月-23CloudComputing,

GUCAS4950Dryad02-2月-23CloudComputing,

GUCAS5051Dryad02-2月-23CloudComputing,

GUCAS5152Dryad優(yōu)缺點(diǎn)優(yōu)點(diǎn)：DryadLINQ具有聲明式編程并將操作的對(duì)象封裝為.NET類方便數(shù)據(jù)操作自動(dòng)序列化和任務(wù)圖的優(yōu)化對(duì)Join進(jìn)行了優(yōu)化，得到了比BigTable+MapReduee更快的Join速率和更易用的數(shù)據(jù)操作方式

缺點(diǎn)它更適用于批處理任務(wù)，而不適用于需要快速響應(yīng)的任務(wù)這個(gè)數(shù)據(jù)模型更適用于處理流式訪問，而不是隨機(jī)訪問Dryad還是測(cè)試階段尚未大規(guī)模普及，但是微軟已經(jīng)在AdCenter的生產(chǎn)系統(tǒng)中使用Dryad02-2月-23CloudComputing,

GUCAS5253MapReduce02-2月-23CloudComputing,

GUCAS53GoogleMapreduce架構(gòu)設(shè)計(jì)師JefferyDeanJefferyDean設(shè)計(jì)一個(gè)新的抽象模型，使我們只要執(zhí)行簡(jiǎn)單計(jì)算，而將并行化、容錯(cuò)、數(shù)據(jù)分布、負(fù)載均衡等雜亂細(xì)節(jié)放在一個(gè)庫里，使并行編程時(shí)不必關(guān)心它們54MapReduceMapReduce是由Google公司的JeffreyDean和SanjayGhemawat開發(fā)的一個(gè)針對(duì)大規(guī)模群組中的海量數(shù)據(jù)處理的分布式編程模型。Map/Reduce是Hadoop的核心計(jì)算模型，它將復(fù)雜的運(yùn)行于大規(guī)模集群上的并行計(jì)算過程高度的抽象到了兩個(gè)函數(shù)，Map和Reduce

02-2月-23CloudComputing,

GUCAS5455MapReduceHistoryofMapReduceandHadoopFeb2003—FirstMapReduceLibrarywrittenatGoogleDec2004—GooglepaperpublishedJuly2005—DougCuttingreportsthatNutchnowusesnewMapReduceimplementationJan2006—DougCuttingjoinsYahoo!Feb2006—HadoopcodemovesoutofNutchintonewLucenesubprojectApr2007—Yahoo!runningHadoopon1000-nodeClusterJan2008—HadoopmadeanApacheTopLevelProjectFeb2008—Yahoo!GenerateproductionsearchindexwithHadoopJuly2008—HadoopWinsTerabyteSortBenchmarkJuly2009—NewHadoopSubprojects02-2月-23CloudComputing,

GUCAS5556MapReduce的應(yīng)用在Google，MapReduce用在非常廣泛的應(yīng)用程序中，包括“分布排序，web連接圖反轉(zhuǎn)，每臺(tái)機(jī)器的詞矢量，web訪問日志分析，反向索引構(gòu)建，文檔聚類,機(jī)器學(xué)習(xí)，基于統(tǒng)計(jì)的機(jī)器翻譯"等.02-2月-23CloudComputing,

GUCAS5657MapReduce的應(yīng)用基于Map/Reduce的Hadoop，被用到了facebook、twitter等著名網(wǎng)站中，國內(nèi)的百度、淘寶、中移動(dòng)也開展了對(duì)其的研究。02-2月-23CloudComputing,

GUCAS575802-2月-23CloudComputing,

GUCAS58提綱1.大規(guī)模數(shù)據(jù)處理2.并行編程3.MapReduce基本原理4.MapReduce的實(shí)現(xiàn)59MapReduce02-2月-23CloudComputing,

GUCAS5960MapReduce產(chǎn)生背景據(jù)相關(guān)統(tǒng)計(jì)，每使用一次Google搜索引擎，Google的后臺(tái)服務(wù)器就要進(jìn)行1011次運(yùn)算，如果沒有好的負(fù)載均衡機(jī)制，有些服務(wù)器的利用率會(huì)很低，有些則會(huì)負(fù)荷太重，有些甚至可能死機(jī)，這些都會(huì)影響系統(tǒng)對(duì)用戶的服務(wù)質(zhì)量使用MapReduce這種編程模式，保持了服務(wù)器之間的均衡，提高了整體效率.02-2月-23CloudComputing,

GUCAS6061MapReduce產(chǎn)生背景MapReduce這種并行編程模式思想最早是在1995年提出的，當(dāng)時(shí)提出的兩個(gè)概念“map”和“fold”，與現(xiàn)在Google所使用“Map”和“Reduce”思想是吻合的。與傳統(tǒng)的分布式程序設(shè)計(jì)相比，MapReduce封裝了并行處理、容錯(cuò)處理、本地化計(jì)算、負(fù)載均衡等細(xì)節(jié)，還提供了一個(gè)簡(jiǎn)單而強(qiáng)大的接口。通過這個(gè)接口，可以把大尺度的計(jì)算自動(dòng)地并發(fā)好分布執(zhí)行，從而使編程變得非常容易02-2月-23CloudComputing,

GUCAS6162MapReduce編程原理利用一個(gè)輸入key/valuepair集合產(chǎn)生一個(gè)輸出的key/valuepair集合需用戶定義兩個(gè)函數(shù)：Map和ReduceMap函數(shù)接受一個(gè)輸入的Key/valuepair值，產(chǎn)生一個(gè)中間key/valuepair值MapReduce庫把所有具有相同中間key值的中間value值集合在一起傳遞給reduce函數(shù)02-2月-23CloudComputing,

GUCAS6263MapReduce原理的要點(diǎn)一種簡(jiǎn)單化的并行編程模型，借用函數(shù)式編程中的Map和Reduce函數(shù)，將復(fù)雜的運(yùn)行于大規(guī)模集群上的并行計(jì)算過程高度的抽象到了兩個(gè)階段數(shù)據(jù)分割、任務(wù)調(diào)度、故障處理等細(xì)節(jié)對(duì)程序員透明利用資源無關(guān)性的原理，提高處理效率合理的任務(wù)力度，優(yōu)化容錯(cuò)處理和整體效率本地計(jì)算：充分利用數(shù)據(jù)的空間局部性來減少網(wǎng)絡(luò)傳輸，節(jié)省寬帶資源減少中間數(shù)據(jù)的產(chǎn)生，優(yōu)化網(wǎng)絡(luò)傳輸02-2月-23CloudComputing,

GUCAS6364MapReduce計(jì)算模型適合用MapReduce來處理的數(shù)據(jù)集（或任務(wù)）有一個(gè)基本要求：待處理的數(shù)據(jù)集可以分解成許多小的數(shù)據(jù)集，而且每一個(gè)小數(shù)據(jù)集都可以完全并行地進(jìn)行處理。MapReduce的計(jì)算模型如下：Map：（K1，V2）→list（K2，V2）Reduce：（K2，list（V2））→list（K3，V3）計(jì)算模型的核心是Map和Reduce兩個(gè)函數(shù)，這兩個(gè)函數(shù)由用戶負(fù)責(zé)實(shí)現(xiàn)，功能是按一定的映射規(guī)則將輸入的<key,value>對(duì)轉(zhuǎn)換成另一個(gè)或一批<key,value>對(duì)輸出02-2月-23CloudComputing,

GUCAS6465MapReduce計(jì)算過程MapReduce的計(jì)算過程就是將大數(shù)據(jù)集分解為成百上千的小數(shù)據(jù)集，每個(gè)（或若干個(gè)）數(shù)據(jù)集分別由集群中的一個(gè)節(jié)點(diǎn)（一般就是一臺(tái)普通的計(jì)算機(jī)）進(jìn)行處理并生成中間結(jié)果，然后這些中間結(jié)果又由大量的結(jié)點(diǎn)進(jìn)行合并，形成最終結(jié)果02-2月-23CloudComputing,

GUCAS6566MapReduce計(jì)算過程對(duì)于程序員基于MapReduce計(jì)算模型編寫分布式并行程序非常簡(jiǎn)單，程序員的主要工作就是實(shí)現(xiàn)Map和Reduce函數(shù)，其他的并行編程中的種種復(fù)雜問題，如分布式存儲(chǔ)、工作調(diào)度、負(fù)載平衡、容錯(cuò)處理、網(wǎng)絡(luò)通信等，均有MapReduce框架（比如Hadoop）負(fù)責(zé)處理，程序員完全不用操心。02-2月-23CloudComputing,

GUCAS6667并行編程模型大多數(shù)分布式運(yùn)算可以抽象為任務(wù)分解和結(jié)果匯總（MapReduce）操作將復(fù)雜的運(yùn)行于大規(guī)模集群上的并行計(jì)算過程高度的抽象到了兩個(gè)階段借用了Lisp中相似功能的名稱，將這兩個(gè)階段分別用Map函數(shù)和Reduce函數(shù)命名，并將此計(jì)算模型命名為MapReduce自動(dòng)分步到一個(gè)由普通機(jī)器組成超大集群上并發(fā)執(zhí)行02-2月-23CloudComputing,

GUCAS6768MapReduce并行編程模型02-2月-23CloudComputing,

GUCAS6869MapReduce運(yùn)行模型02-2月-23CloudComputing,

GUCAS69MapReduce的運(yùn)行模型下圖所示，圖中有M個(gè)Map操作和R個(gè)Reduce操作70MapReduce運(yùn)行模型02-2月-23CloudComputing,

GUCAS70一個(gè)Map函數(shù)就是對(duì)一部分原始數(shù)據(jù)進(jìn)行指定的操作。每個(gè)Map操作都針對(duì)不同的原始數(shù)據(jù)，因此Map與Map之間是互相獨(dú)立的，這就使得它們可以充分并行化。一個(gè)Reduce操作就是對(duì)每個(gè)Map所產(chǎn)生的一部分中間結(jié)果進(jìn)行合并操作，每個(gè)Reduce所處理的Map中間結(jié)果是互不交叉的，所有Reduce產(chǎn)生的最終結(jié)果經(jīng)過簡(jiǎn)單連接就形成了完整的結(jié)果集，因此Reduce也可以在并行環(huán)境下執(zhí)行。

71借用函數(shù)式中的Map和Reduce函數(shù)02-2月-23CloudComputing,

GUCAS71輸入和輸出：都是鍵值對(duì)集合用戶指定一個(gè)映射函數(shù)處理一個(gè)鍵/值對(duì)來產(chǎn)生中間的鍵/值對(duì)集合，還指定一個(gè)縮減函數(shù)來合并所有的與同一中間鍵相關(guān)的中間值Map（in_key，in_value）→

list(out_key,intermediate_value)reduce(out_key,list(intermediate_value))→list(out_value)72MapReduce執(zhí)行流程02-2月-23CloudComputing,

GUCAS7273MapReduce執(zhí)行流程02-2月-23CloudComputing,

GUCAS73用戶程序中的MapReduce函數(shù)庫首先把輸入文件分成M塊，每塊大概16M～64MB（可以通過參數(shù)決定），接著在集群的機(jī)器上執(zhí)行處理程序。74MapReduce執(zhí)行流程02-2月-23CloudComputing,

GUCAS74總共有M個(gè)Map任務(wù)和R個(gè)Reduce任務(wù)需要分派，Master選擇空閑的Worker來分配這些Map或者Reduce任務(wù)。75MapReduce執(zhí)行流程02-2月-23CloudComputing,

GUCAS75分配了Map任務(wù)的Worker讀取并處理相關(guān)的輸入塊。它處理輸入的數(shù)據(jù)并傳遞給用戶定義的Map函數(shù)。Map函數(shù)產(chǎn)生的中間結(jié)果<key,value>對(duì)暫時(shí)緩沖到內(nèi)存。76MapReduce執(zhí)行流程02-2月-23CloudComputing,

GUCAS76緩沖到內(nèi)存的中間結(jié)果將被定時(shí)寫到MapWorker本地硬盤，這些數(shù)據(jù)通過分區(qū)函數(shù)分成R個(gè)區(qū)。中間結(jié)果在本地硬盤的位置信息將被發(fā)送回Master，然后Master負(fù)責(zé)把這些位置信息傳送給ReduceWorker。77MapReduce執(zhí)行流程02-2月-23CloudComputing,

GUCAS77當(dāng)Master通知Reduce的Worker關(guān)于中間結(jié)果的位置時(shí)，它調(diào)用遠(yuǎn)程過程來從MapWorker的本地硬盤上讀取緩沖的中間數(shù)據(jù)。當(dāng)ReduceWorker讀到所有的中間數(shù)據(jù)，它將對(duì)數(shù)據(jù)進(jìn)行排序。78MapReduce執(zhí)行流程02-2月-23CloudComputing,

GUCAS78ReduceWorker處理排序后的中間數(shù)據(jù)，并將處理得到的中間結(jié)果值集合傳遞給用戶定義的Reduce函數(shù)。Reduce函數(shù)的結(jié)果輸出到一個(gè)最終的輸出文件。79MapReduce案例：?jiǎn)卧~計(jì)數(shù)案例：?jiǎn)卧~計(jì)數(shù)問題（Wordcount)給定一個(gè)巨大的文本（如1TB），如何計(jì)算單詞出現(xiàn)的數(shù)目?02-2月-23CloudComputing,

GUCAS79輸入數(shù)據(jù)：文件所包含的信息輸出數(shù)據(jù)：?jiǎn)卧~所出現(xiàn)的頻率Hello:3World:2Bye:3Hadoop:4HelloWorldByeWorldHelloHadoopByeHadoopByeHadoopHelloHadoopMapReduce80MapReduce案例：?jiǎn)卧~計(jì)數(shù)使用MapReduce來解決該問題Step1：自動(dòng)對(duì)文本進(jìn)行分割

對(duì)文本分割HelloWorldByeWorldHelloHadoopByeHadoopByeHadoopHelloHadoopsplitsplitsplitHelloWorldByeWorldHelloHadoopByeHadoopByeHadoopHelloHadoop(K,V)(K,V)(K,V)81MapReduce案例：?jiǎn)卧~計(jì)數(shù)使用MapReduce來解決該問題Step2：在分割之后的每一對(duì)<key,value>進(jìn)行用戶定義的Map處理，再生成新的<key,value>對(duì)Split輸出HelloWoldByeWoldHelloHadoopByeHadoopByeHadoopHelloHadoop<Hello,1><World,1><Bye,1><World,1><Hello,1><Hadoop,1><Bye,1><Hadoop,1><Bye,1><Hadoop,1><Hello,1><Hadoop,1>MapMapMapMap輸出82MapReduce案例：?jiǎn)卧~計(jì)數(shù)02-2月-23CloudComputing,

GUCAS82使用MapReduce來解決該問題Step3：對(duì)輸出的結(jié)果集排序、歸攏（系統(tǒng)自動(dòng)完成）Map輸出<Hello,1><World,1><Bye,1><World,1><Hello,1><Hadoop,1><Bye,1><Hadoop,1><Bye,1><Hadoop,1><Hello,1><Hadoop,1><Hello,1><Hello,1><Hello,1><World,1><World,1><Bye,1><Bye,1><Bye,1><Hadoop,1><Hadoop,1><Hadoop,1><Hadoop,1>FoldFold輸出83MapReduce案例：?jiǎn)卧~計(jì)數(shù)02-2月-23CloudComputing,

GUCAS83使用MapReduce來解決該問題Step4：對(duì)輸出的結(jié)果集縮減，得出輸出結(jié)果。Fold輸出<Hello,1><Hello,1><Hello,1><World,1><World,1><Bye,1><Bye,1><Bye,1><Hadoop,1><Hadoop,1><Hadoop,1><Hadoop,1><Hello,3><World,2><Bye,3><Hadoop,4>ReduceReduce輸出84并行執(zhí)行02-2月-23CloudComputing,

GUCAS8485數(shù)據(jù)分割、任務(wù)調(diào)度、故障處理運(yùn)行時(shí)系統(tǒng)負(fù)責(zé)：分割輸入數(shù)據(jù)，在一系列機(jī)器之間調(diào)度程序的執(zhí)行，處理機(jī)器故障，管理機(jī)器內(nèi)部通信沒有任何并行和分布式系統(tǒng)經(jīng)驗(yàn)的程序員也能夠容易地利用分布式系統(tǒng)的資源進(jìn)行計(jì)算MapReduce包括三個(gè)不同類型的服務(wù)器：master、mapservers、reduceserversMaster分配用戶給mapservers和reduceservers。它也跟蹤任務(wù)的狀態(tài)Mapservers接收用戶輸入，在它們上面執(zhí)行映射操作，結(jié)果寫入中間文件Reduceservers服務(wù)器接收由映射服務(wù)器產(chǎn)生的中間文件并在它們上面實(shí)行化簡(jiǎn)操作02-2月-23CloudComputing,

GUCAS8586本地計(jì)算Master根據(jù)數(shù)據(jù)的位置來分解任務(wù)使map任務(wù)和相關(guān)文件盡可能在同一機(jī)器上，或者至少在同一機(jī)架上，以減少網(wǎng)絡(luò)傳輸Map（）任務(wù)的輸入被分解為大小64KB的塊和GFS的文件塊相同，能夠保證一個(gè)小數(shù)據(jù)集位于一臺(tái)計(jì)算機(jī)上，便于本地計(jì)算02-2月-23CloudComputing,

GUCAS8687任務(wù)粒度Map任務(wù)的個(gè)數(shù)要遠(yuǎn)遠(yuǎn)大于機(jī)器的數(shù)量好處MinimizestimeforfaultrecoveryBetterdynamicloadbalancingE.g.MapReducecomputationswithMap=200000andReduce=5000,using2000workermachines02-2月-23CloudComputing,

GUCAS8788MapReduce的容錯(cuò)Worker故障Master周期性的ping每個(gè)worker。如果master在一個(gè)確定的時(shí)間范圍內(nèi)沒有收到worker返回的信息，master將把這個(gè)worker標(biāo)記為失效將這個(gè)worker所執(zhí)行的Map任務(wù)重新分配給其它的worker重新執(zhí)行該節(jié)點(diǎn)未完成的Reduce任務(wù)，已完成的不再執(zhí)行Master故障定期寫入檢查點(diǎn)數(shù)據(jù)從檢查點(diǎn)回復(fù)02-2月-23CloudComputing,

GUCAS8889MapReduce的優(yōu)化任務(wù)備份機(jī)制慢的workers會(huì)