2024谷歌Map Reduce中文說明

GoogleMapReduce中文版目錄TOC\o"1-3"\h\u8395 158681 121713 219126 2268762 287642.1 2159862.2 3177572.3 3173163 4242353. 479893.1 4284573.2Master 6141483.3 6125463.4 881383.5 822643.6 843994 9170464.1 9205504.2 9322514.3Combiner 9315544.4 1041374.5 1029333 1028134.6 1166074.7 11245874.8 1193294.9 1211215 12178825.1 13254765.2 1347235.3 1390355.4backup 15142165.5 1519116 1538181. 15135245. 16143996.1 17229867 17320526 1862768 1973899 19618310 201119411 21GoogleGoogleMapReduce1.0GoogleMapReduceMapReduce是一個編程模型，也是一個處理和生成超大數(shù)據(jù)集的算法模型的相關(guān)實現(xiàn)。用戶首先創(chuàng)建一Map函數(shù)處理一個基于key/valuepairkey/valuepairMpedueapeuceMapReduceMapReduceTB計算的數(shù)據(jù)。程序員發(fā)現(xiàn)這個系統(tǒng)非常好用：已經(jīng)實現(xiàn)了數(shù)以百計MapReduce程序，在Google1000MapReduce程序在執(zhí)行。5年里，包括本文作者在內(nèi)的Google的很多程序員，為了處理海量的原始數(shù)據(jù)，已經(jīng)實現(xiàn)了數(shù)pairkeyvalueReduce \h（re-這個工作(實現(xiàn)一個MapReduce框架模型)的主要貢獻是通過簡單的接口來實現(xiàn)自動的并行化和大規(guī)模的分布式計算，通過使用MapReduce模型接口實現(xiàn)在大量普通的PC機上高性能計算。MapReduce實現(xiàn)。第四部分描述我們認為在MapReduce編程模型中一些實用的技巧。GoogleMapReduce作為基礎(chǔ)重寫我們的索引系統(tǒng)產(chǎn)品，包括其它一些MapReduce的經(jīng)驗。MapReducekey/valuepairkey/valuepairMapReduce庫的用戶用兩個函數(shù)表達這個計算：Map和Reduce用戶自定義的Mapkey/valuepair值，然后產(chǎn)生一個中間key/valuepairMapReducekeyIvaluereduce用戶自定義的ReducekeyIvalueReduce函數(shù)合并這些value值，形成一個較小的value值的集合。一般的，每次Reduce01value值。通value值的集合。map(Stringmap(Stringkey,String//key:document//value:documentcontentsforeachwordwinvalue:EmitIntermediate(w,reduce(Stringreduce(Stringkey,Iterator//key:a//values:alistofcountsintresult=0;foreachvinvalues:result+=ParseInt(v);(C++實現(xiàn))。附錄A包含了這個實例的全部程序代碼。map(k1,v1)map(k1,v1)-keyvaluekeyvaluekeyC++中使用字符串類型作為用戶自定義函數(shù)的輸入輸出，用戶在自己的代碼中對字符串進行適當(dāng)這里還有一些有趣的簡單例子，可以很容易的使用MapReduce分布式的Grep：Map函數(shù)輸出匹配某個模式的一行，Reduce函數(shù)是一個恒等函數(shù)，即把中間數(shù)據(jù)復(fù)制到計算URL訪問頻率：Map函數(shù)處理日志中web頁面請求的記錄，然后輸出(URL,1)。Reduce2domainHadoop、KFS等實現(xiàn)，mapreducedomain翻譯詞。Map函數(shù)為每一個輸入文檔輸出(主機名,檢索詞向量)，其中主機名來自文檔的URL。Reduce函數(shù)接收給分布式排序：Mapkey，輸出(key,record)。Reduce函數(shù)不改變?nèi)魏蔚闹?。這個運算依賴分區(qū)機制(4.1描述)和排序?qū)傩?4.2描述)。MapReduce模型可以有多種不同的實現(xiàn)方式。如何正確選擇取決于具體的環(huán)境。例如，一種實現(xiàn)方式適IDE硬盤。一個內(nèi)部分布式文件系統(tǒng)用來管理存儲在這些磁盤上的數(shù)據(jù)。文件系（taskMapM個數(shù)據(jù)片段的集合，Map調(diào)用被分布到多臺機器上執(zhí)行。輸Map調(diào)用產(chǎn)生的中間key值分成RR，Reduce系列動作（1中的序號一一對應(yīng)：用戶程序首先調(diào)用的MapReduce庫將輸入文件分成M給一個空閑的worker。mapworkerkey/value緩存中的key/valuepair通過分區(qū)函數(shù)分成R個區(qū)域，之后周期性的寫入到本地磁盤上。緩存的key/valuepair在本地磁盤上的存儲位置將被回傳給mastermaster負責(zé)把這些存儲位置再傳送給Reduceworker。ReduceworkermasterRPC從Mapworker所在Reduceworkerkey進行排序keykeyReduce任務(wù)上，keyvalue值的集合傳遞給用戶自定義的Reduce函數(shù)。Reduce函數(shù)的輸出被追MapReduce任務(wù)都完成之后，masterMapReduce在成功完成任務(wù)之后，MapReduce的輸出存放在R個輸出文件中（對應(yīng)每個Reduce任務(wù)產(chǎn)生一個輸出MapReduce的輸入，或者在另外一個可以處理多個分割文件的分布式應(yīng)用中使用。MasterMasterMapReduce。因此，workerworkerworkerMap任務(wù)被重設(shè)為初始的空閑狀態(tài)，之后這些worker。同樣的，workerMapReduce任務(wù)也將被重新置為Map因此必須重新執(zhí)行。而已經(jīng)完成的ReduceMapworkerA執(zhí)行，之后由于workerA失效了又被調(diào)度到workerB執(zhí)行，這個“重workerB讀取數(shù)據(jù)。workerMapReduce操作。mastermaster周期性的將上面描述的數(shù)據(jù)結(jié)構(gòu)（alex3.2節(jié)）的寫入磁盤，即檢查點（checkpointmaster任務(wù)失效了，可以從最后一個檢查點（checkpoint）開始啟動另一個mastermaster進程，master失效后再恢復(fù)是比較麻煩的，因此我們現(xiàn)在的實現(xiàn)是（alex注：原文為”semanticsinthepresenceoffailuresMapReduce操作是輸入確定性函數(shù)（即相同的輸入產(chǎn)生相同的輸出）時，我們的分布我們依賴對Map和Reduce任務(wù)的輸出是原子提交的來完成這個特性。每個工作中的任務(wù)把它的輸出寫ReduceMapR個這樣的文件（一則，master將這R個文件的名字記錄在數(shù)據(jù)結(jié)構(gòu)里。一個Reduce任務(wù)在多臺機器上執(zhí)行，針對同一個最終的輸出文件將有多個重命名操作執(zhí)行。我們依賴底層文件系統(tǒng)提供的重命名操作的原子性來保證最終的文件系統(tǒng)狀態(tài)僅僅包含一個Reduce任務(wù)產(chǎn)生的數(shù)據(jù)。使用MapReduceMap和的輸出也許符合一個不同的非確定順序程序執(zhí)行產(chǎn)生的R2MapMReduceR1、R2e(Ri)Ri已經(jīng)提交的執(zhí)行過程（有且僅有在我們的計算運行環(huán)境中，網(wǎng)絡(luò)帶寬是一個相當(dāng)匱乏的資源。我們通過盡量把輸入數(shù)據(jù)(GFS管理)存儲在集群中機器的本地磁盤上來節(jié)省網(wǎng)絡(luò)帶寬。GFS64MBBlockBlock保存MapMReduce拆分成R個片段執(zhí)行。理想情況下，M和R應(yīng)當(dāng)Map任務(wù)都可以分布到所有其他的workerMap任務(wù)/Reduce1個字節(jié)就可以了。更進一步，R值通常是由用戶指定的，因為每個Reduce任務(wù)最終都會生成一個獨立的輸出文件。實際使M16M64M的輸入數(shù)據(jù)（這樣，上面描寫的輸入數(shù)據(jù)本地存儲優(yōu)化策略才最有效Rworker機器數(shù)量MapReduce長的時間才完成最后幾個Map或ReduceMapReduce的一個問題是由于機器的初始化代碼有bug，導(dǎo)致關(guān)閉了的處理器的緩存：在這些機器上執(zhí)行任務(wù)的性能和5.344%的時間完成MapReduce函數(shù)提供的基本功能已經(jīng)能夠滿足大部分的計算需要，我們還是發(fā)掘出了一MapReduce的使用者通常會指定Reduce任務(wù)和Reduce任務(wù)輸出文件的數(shù)量（Rkey上使hash方法(比如，hash(key)modR)進行分區(qū)。hashkeykeyURLs，我們希望每個主機的所有條目保持在同一個輸出文MapReducehash(Hostname(urlkey))modR”作為分區(qū)函數(shù)就可以把所有來自同一個主機的URLs保存在同一個輸出文件中。key/valuepair數(shù)據(jù)的處理順序是按照key值增量順序處理的。這樣的順key值隨機存取的應(yīng)用非常有意義，Combiner布)Map任務(wù)將產(chǎn)生成千上萬個這樣的記錄<the,1>。所有的這些記錄將通過網(wǎng)絡(luò)被發(fā)送到一個單獨的ReduceReduce任務(wù)把所有這些記錄累加起來產(chǎn)生一個數(shù)字。我們允許用戶指定一個可選Combiner函數(shù)在每臺執(zhí)行Map任務(wù)的機器上都會被執(zhí)行一次。一般情況下，CombinerReduce函數(shù)是一樣的。Combiner函數(shù)和Reduce函數(shù)之間唯一的區(qū)別是MapReduce庫怎樣控制函數(shù)的輸出。Reduce函數(shù)的CombinerReduce任務(wù)。MapReduceAcombiner函數(shù)MapReduce庫支持幾種不同的格式的輸入數(shù)據(jù)。比如，文本模式的輸入數(shù)據(jù)的每一行被視為是一個key/valuepair。key是文件的偏移量，valuekey進行排序來存儲key/valuepair的序列。每種輸入類型的實現(xiàn)都必須能夠把輸入數(shù)據(jù)分割成數(shù)據(jù)片段，該數(shù)據(jù)片段能夠由單Map任務(wù)來進行后續(xù)處理(例如，文本模式的范圍分割必須確保僅僅在每行的邊界進行范圍分割)。雖然個簡單的Reader接口實現(xiàn)就能夠支持一個新的輸入類型。ReaderReader，Reader。在某些情況下，MapReduce的使用者發(fā)現(xiàn)，如果在Map和/Reduce操作過程中增加輔助的輸出文件會rename重新命名這個臨時文件。3bg導(dǎo)致Mp或者ReuceahMReuce操作ug后再次執(zhí)行MpRducebugbugapeducea，errorMapReduce操作之前，MapReduce庫通過全局變量保存記錄序號。如果用戶程序觸發(fā)了一個系看到在處理某條特定記錄不止失敗一次時，master就標(biāo)志著條記錄需要被跳過，并且在下次重新執(zhí)行相關(guān)的MapReduce任務(wù)的時候跳過這條記錄。MapReducebug是非常困難的，因為實際執(zhí)行操作時不但是分布在系統(tǒng)中執(zhí)行的，而且為了簡化調(diào)試、profileMapReduce庫的本地實現(xiàn)版本，通過使用本地版本的用本地調(diào)試和測試工具（gdbmasterHTTP服務(wù)器（Jetty）顯示一組狀態(tài)信息頁面，用戶可以監(jiān)控各種執(zhí)行狀態(tài)。狀workerMap和MapReduce庫使用計數(shù)器統(tǒng)計不同事件發(fā)生次數(shù)。比如，用戶可能想統(tǒng)計已經(jīng)處理了多少個單詞、已經(jīng)索引的多少篇German文檔等等。Counter*uppercase=GetCounter(“uppercase”);map(Stringname,Stringcontents):forCounter*uppercase=GetCounter(“uppercase”);map(Stringname,Stringcontents):foreachwordwincontents:if(IsCapitalized(w)):EmitIntermediate(w,mastrMap和ReduceMapReduce操作完成之后，返回給用戶代碼。的值的時候，masterMapReduce任務(wù)，避免重復(fù)累加（之前提到的備用任務(wù)和失效有些計數(shù)器的值是由MapReduce庫自動維持的，比如已經(jīng)處理的輸入的key/valuepairkey/valuepairkeyvaluepairkeyvaluepair，或者處理的German文檔數(shù)量在處理的整個文檔數(shù)本節(jié)我們用在一個大型集群上運行的兩個計算來衡量MapReduce1TB的數(shù)據(jù)中1TB的數(shù)據(jù)進行排序。這兩個程序在大量的使用MapReduce等部署1毫秒。CPU、磁盤和網(wǎng)絡(luò)基本上處于空閑狀態(tài)。Block（M=15000（R=1圖2顯示了這個運算隨時間的處理過程。其中Y軸表示輸入數(shù)據(jù)的處理速度。處理速度隨著參與MapReduce1764worker30GB/s。當(dāng)150秒。這包括了大約一分鐘的初始啟動階段。初始啟動階段消耗的時間包括了是把這個程序傳送到各排序程序處理10的10次方個100個字節(jié)組成的記錄（大概1TB的數(shù)據(jù)。這個程序模仿TeraSort50行代碼組成。只有三行的Map10key值作為排序的keykeykey/valuepair值輸出。我們使用了一個內(nèi)置的恒等函數(shù)作為Reducekey/valuepair值不作任何改變輸出。最終排序結(jié)果輸出到兩路復(fù)制的GFS文件系統(tǒng)（2TB的數(shù)據(jù)。Block（M=15000（R=4000benchmarkkey的分區(qū)情況。通常對于排序程序來說，我們會MapReduce操作用于采樣key值的分布情況，通過采樣的數(shù)據(jù)來計算對最終排序處理的分grep程序的中間結(jié)果輸出幾乎可以忽略不計。Reduce任務(wù)有些完成了，我們開始執(zhí)行剩下的Reduce600秒后結(jié)束。左下圖表示Reduce850891秒。這個速度和TeraSortbenchmark[18]1057秒相差不多?！?GS是底層文件系統(tǒng)的保證數(shù)據(jù)可靠性和可用性的實現(xiàn)機制。如果底層文件系統(tǒng)使用類似容錯編碼14esuecodngbackup5Reduce3001283kill了，機器本身還在工作。圖三（c）Map任務(wù)丟失了（由于相應(yīng)的執(zhí)行Map任務(wù)的worker進程被kill了Map任務(wù)很快就被重新執(zhí)行了。933秒內(nèi)完成，包括了初始啟動時間（5%的時間。了輸入數(shù)據(jù)本地優(yōu)化、worker機器之間的動態(tài)負載均衡等等。從那以后，我們驚喜的發(fā)現(xiàn)，MapReduce庫能廣泛應(yīng)用于我們?nèi)粘９ぷ髦杏龅降母黝悊栴}。它現(xiàn)在在Google內(nèi)部各個領(lǐng)域得到廣泛應(yīng)用，包括：GoogleNewsFroogle從公眾查詢產(chǎn)品（比如GoogleZeitgeist）年早些時候的0個增長到2004年9月份的差不多900MapReduce的成功取決于采用MapReduce在每個任務(wù)結(jié)束的時候，MapReduce120048到目前為止，MapReduce最成功的應(yīng)用就是重寫了Googleindex系統(tǒng)。索引系統(tǒng)的輸入數(shù)據(jù)是網(wǎng)絡(luò)爬蟲抓取回來的海量的文檔，這些文檔數(shù)據(jù)都保存在GFS文件系統(tǒng)里。這些文檔原始內(nèi)容420TBMapReduce操作（510次）來建立索引。使用MapReduce庫的性能已經(jīng)足夠好了，因此我們可以把在概念上不相關(guān)的計算步驟分開處理，而不是混在4rawcontentshtml標(biāo)記后的內(nèi)容、pdfword可以通過把N個元素的數(shù)組的前綴在NogN915。MpRduceBulkSynchronousProgramming[17]MPI原語[11]提供了更高級別的并行處理抽象，可以更容易寫出并行處理的程序。MapReduce和這些系統(tǒng)的關(guān)鍵不同之處在于，MapReduce利用限制性編程模式實現(xiàn)了用activedisks[12,15]activedisks中，計算任務(wù)是盡量推送到數(shù)據(jù)存儲的節(jié)點處理6IO子系統(tǒng)的吞吐量。我們在掛載幾個硬盤的普通機器上執(zhí)行我們的備用任務(wù)機制和CharlotteSystem[3]eagerEager調(diào)度機制的一個缺點是MapReduce的實現(xiàn)依賴于一個內(nèi)部的集群管理系統(tǒng)，這個集群管理系統(tǒng)負責(zé)在一個超大的、共享機器的Condor[16]是一樣。MapReduceNOW-Sort[1]的操作上很類似。讀取輸入源的機器（mapworkers）把待排序R個Reduceworker中的一個進行處理。每個Reduceworker在本地對數(shù)據(jù)進行排序（盡可能在內(nèi)存中排序。當(dāng)然，NOW-SortMapReduce函數(shù)的機會，因此不具備MapReduce庫廣泛的實用性。River[2]提供了一個編程模型：處理進程通過分布式隊列傳送數(shù)據(jù)的方式進行互相通訊。和MapReduce類似，River系統(tǒng)嘗試在不對等的硬件環(huán)境下，或者在系統(tǒng)顛簸的情況下也能提供近似平均的性能。River是通過精心調(diào)度硬盤和網(wǎng)絡(luò)的通訊來平衡任務(wù)的完成時間。MapReduce庫采用了其它的方法。通過對編程模型56、9、136TACC[7]MapReduce一樣，它也依靠重新執(zhí)行機制來MapReduce編程模型在Google內(nèi)部成功應(yīng)用于多個領(lǐng)域。我們把這種成功歸結(jié)為幾個方面：首先，由于MapReduce簡單的解決。比如，MapReduceGoogle的網(wǎng)絡(luò)搜索服務(wù)所需要的數(shù)據(jù)、用來MapReduce。這個實現(xiàn)使得有效利用這些豐富的計算資源變得非常簡單，因此也適合用來解決Google遇到的其他很多需要大量計算的問題。我們也從MapReduce（alex，JoshLevenberghasbeeninstrumentalinrevisingandextendingtheuser-levelMapReduceAPIwithanumberofnewfeaturesbasedonhisexperiencewithusingMapReduceandotherpeople’ssuggestionsforenhancements.MapReducereadsitsinputfromandwritesitsoutputtotheGoogleFileSystem[8].WewouldliketothankMohitAron,HowardGobioff,MarkusGutschke,DavidKramer,Shun-TakLeung,andJoshRedstonefortheirworkindevelopingGFS.WewouldalsoliketothankPercyLiangandOlcanSercinoglufortheirworkindevelopingtheclustermanagementsystemusedbyMapReduce.MikeBurrows,WilsonHsieh,JoshLevenberg,SharonPerl,RobPike,andDebbyWallachprovidedhelpfulcommentsonearlierdraftsofthispaper.TheanonymousOSDIreviewers,andourshepherd,EricBrewer,providedmanyusefulsuggestionsofareaswherethepapercouldbeimproved.Finally,wethankalltheusersofMapReducewithinGoogle’sengineeringorganizationforprovidinghelpfulfeedback,suggestions,andbugreports.AndreaC.Arpaci-Dusseau,RemziH.Arpaci-Dusseau,DavidE.Culler,JosephM.Hellerstein,andDavidA.Patterson.High-performancesortingonnetworksofworkstations.InProceedingsofthe1997ACMSIGMODInternationalConferenceonManagementofData,Tucson,Arizona,May1997.RemziH.Arpaci-Dusseau,EricAnderson,NoahTreuhaft,DavidE.Culler,JosephM.Hellerstein,DavidPatterson,andKathyYelick.ClusterI/OwithRiver:Makingthefastcasecommon.InProceedingsoftheSixthWorkshoponInput/OutputinParallelandDistributedSystems(IOPADS’99),pages10.22,Atlanta,Georgia,MayArashBaratloo,MehmetKaraul,ZviKedem,andPeterWyckoff.Charlotte:Metacomputingontheweb.InProceedingsofthe9thInternationalConferenceonParallelandDistributedComputingSystems,1996.[4]LuizA.Barroso,JeffreyDean,andUrsH¨olzle.Websearchforaplanet:TheGoogleclusterarchitecture.IEEEMicro,23(2):22.28,April2003.JohnBent,DouglasThain,AndreaC.Arpaci-Dusseau,RemziH.Arpaci-Dusseau,andMironLivny.Explicitcontrolinabatch-awaredistributedfilesystem.InProceedingsofthe1stUSENIXSymposiumonNetworkedSystemsDesignandImplementationNSDI,March2004.GuyE.Blelloch.Scansasprimitiveparalleloperations.IEEETransactionsonComputers,C-38(11),November1989.ArmandoFox,StevenD.Gribble,YatinChawathe,EricA.Brewer,andPaulGauthier.Cluster-basedscalablenetworkservices.InProceedingsofthe16thACMSymposiumonOperatingSystemPrinciples,pages78.91,Saint-Malo,France,1997.SanjayGhemawat,HowardGobioff,andShun-TakLeung.TheGooglefilesystem.In19thSymposiumonOperatingSystemsPrinciples,pages29.43,LakeGeorge,NewYork,2003.ToappearinOSDI200412S.Gorlatch.Systematicefficientparallelizationofscanandotherlisthomomorphisms.InL.Bouge,P.Fraigniaud,A.Mignotte,andY.Robert,editors,Euro-Par’96.ParallelProcessing,LectureNotesinComputerScience1124,pages401.408.Springer-Verlag,1996.JimGray.Sortbenchmarkhomepage.\hWilliamGropp,EwingLusk,andAnthonySkjellum.UsingMPI:PortableParallelProgrammingwiththeMessage-PassingInterface.MITPress,Cambridge,MA,1999.L.Huston,R.Sukthankar,R.Wickremesinghe,M.Satyanarayanan,G.R.Ganger,E.Riedel,andA.Ailamaki.Diamond:Astoragearchitectureforearlydiscardininteractivesearch.InProceedingsofthe2004USENIXFileandStorageTechnologiesFASTConference,AprilRichardE.LadnerandMichaelJ.Fischer.Parallelprefixcomputation.JournaloftheACM,27(4):831.838,MichaelO.Rabin.Efficientdispersalofinformationforsecurity,loadbalancingandfaulttolerance.JournaloftheACM,36(2):335.348,1989.ErikRiedel,ChristosFaloutsos,GarthA.Gibson,andDavidNagle.Activedisksforlarge-