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是一個(gè)編程模型，也是一個(gè)處理和生成超大數(shù)據(jù)集的算法模型的相關(guān)實(shí)現(xiàn)。用戶首先創(chuàng)建一Map函數(shù)處理一個(gè)基于key/valuepairkey/valuepairMpedueapeuceMapReduceMapReduceTB計(jì)算的數(shù)據(jù)。程序員發(fā)現(xiàn)這個(gè)系統(tǒng)非常好用：已經(jīng)實(shí)現(xiàn)了數(shù)以百計(jì)MapReduce程序，在Google1000MapReduce程序在執(zhí)行。5年里，包括本文作者在內(nèi)的Google的很多程序員，為了處理海量的原始數(shù)據(jù)，已經(jīng)實(shí)現(xiàn)了數(shù)pairkeyvalueReduce \h（re-這個(gè)工作(實(shí)現(xiàn)一個(gè)MapReduce框架模型)的主要貢獻(xiàn)是通過簡單的接口來實(shí)現(xiàn)自動的并行化和大規(guī)模的分布式計(jì)算，通過使用MapReduce模型接口實(shí)現(xiàn)在大量普通的PC機(jī)上高性能計(jì)算。MapReduce實(shí)現(xiàn)。第四部分描述我們認(rèn)為在MapReduce編程模型中一些實(shí)用的技巧。GoogleMapReduce作為基礎(chǔ)重寫我們的索引系統(tǒng)產(chǎn)品，包括其它一些MapReduce的經(jīng)驗(yàn)。MapReducekey/valuepairkey/valuepairMapReduce庫的用戶用兩個(gè)函數(shù)表達(dá)這個(gè)計(jì)算：Map和Reduce用戶自定義的Mapkey/valuepair值，然后產(chǎn)生一個(gè)中間key/valuepairMapReducekeyIvaluereduce用戶自定義的ReducekeyIvalueReduce函數(shù)合并這些value值，形成一個(gè)較小的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++實(shí)現(xiàn))。附錄A包含了這個(gè)實(shí)例的全部程序代碼。map(k1,v1)map(k1,v1)-keyvaluekeyvaluekeyC++中使用字符串類型作為用戶自定義函數(shù)的輸入輸出，用戶在自己的代碼中對字符串進(jìn)行適當(dāng)這里還有一些有趣的簡單例子，可以很容易的使用MapReduce分布式的Grep：Map函數(shù)輸出匹配某個(gè)模式的一行，Reduce函數(shù)是一個(gè)恒等函數(shù)，即把中間數(shù)據(jù)復(fù)制到計(jì)算URL訪問頻率：Map函數(shù)處理日志中web頁面請求的記錄，然后輸出(URL,1)。Reduce2domainHadoop、KFS等實(shí)現(xiàn)，mapreducedomain翻譯詞。Map函數(shù)為每一個(gè)輸入文檔輸出(主機(jī)名,檢索詞向量)，其中主機(jī)名來自文檔的URL。Reduce函數(shù)接收給分布式排序：Mapkey，輸出(key,record)。Reduce函數(shù)不改變?nèi)魏蔚闹怠＿@個(gè)運(yùn)算依賴分區(qū)機(jī)制(4.1描述)和排序?qū)傩?4.2描述)。MapReduce模型可以有多種不同的實(shí)現(xiàn)方式。如何正確選擇取決于具體的環(huán)境。例如，一種實(shí)現(xiàn)方式適IDE硬盤。一個(gè)內(nèi)部分布式文件系統(tǒng)用來管理存儲在這些磁盤上的數(shù)據(jù)。文件系（taskMapM個(gè)數(shù)據(jù)片段的集合，Map調(diào)用被分布到多臺機(jī)器上執(zhí)行。輸Map調(diào)用產(chǎn)生的中間key值分成RR，Reduce系列動作（1中的序號一一對應(yīng)：用戶程序首先調(diào)用的MapReduce庫將輸入文件分成M給一個(gè)空閑的worker。mapworkerkey/value緩存中的key/valuepair通過分區(qū)函數(shù)分成R個(gè)區(qū)域，之后周期性的寫入到本地磁盤上。緩存的key/valuepair在本地磁盤上的存儲位置將被回傳給mastermaster負(fù)責(zé)把這些存儲位置再傳送給Reduceworker。ReduceworkermasterRPC從Mapworker所在Reduceworkerkey進(jìn)行排序keykeyReduce任務(wù)上，keyvalue值的集合傳遞給用戶自定義的Reduce函數(shù)。Reduce函數(shù)的輸出被追MapReduce任務(wù)都完成之后，masterMapReduce在成功完成任務(wù)之后，MapReduce的輸出存放在R個(gè)輸出文件中（對應(yīng)每個(gè)Reduce任務(wù)產(chǎn)生一個(gè)輸出MapReduce的輸入，或者在另外一個(gè)可以處理多個(gè)分割文件的分布式應(yīng)用中使用。MasterMasterMapReduce。因此，workerworkerworkerMap任務(wù)被重設(shè)為初始的空閑狀態(tài)，之后這些worker。同樣的，workerMapReduce任務(wù)也將被重新置為Map因此必須重新執(zhí)行。而已經(jīng)完成的ReduceMapworkerA執(zhí)行，之后由于workerA失效了又被調(diào)度到workerB執(zhí)行，這個(gè)“重workerB讀取數(shù)據(jù)。workerMapReduce操作。mastermaster周期性的將上面描述的數(shù)據(jù)結(jié)構(gòu)（alex3.2節(jié)）的寫入磁盤，即檢查點(diǎn)（checkpointmaster任務(wù)失效了，可以從最后一個(gè)檢查點(diǎn)（checkpoint）開始啟動另一個(gè)mastermaster進(jìn)程，master失效后再恢復(fù)是比較麻煩的，因此我們現(xiàn)在的實(shí)現(xiàn)是（alex注：原文為”semanticsinthepresenceoffailuresMapReduce操作是輸入確定性函數(shù)（即相同的輸入產(chǎn)生相同的輸出）時(shí)，我們的分布我們依賴對Map和Reduce任務(wù)的輸出是原子提交的來完成這個(gè)特性。每個(gè)工作中的任務(wù)把它的輸出寫ReduceMapR個(gè)這樣的文件（一則，master將這R個(gè)文件的名字記錄在數(shù)據(jù)結(jié)構(gòu)里。一個(gè)Reduce任務(wù)在多臺機(jī)器上執(zhí)行，針對同一個(gè)最終的輸出文件將有多個(gè)重命名操作執(zhí)行。我們依賴底層文件系統(tǒng)提供的重命名操作的原子性來保證最終的文件系統(tǒng)狀態(tài)僅僅包含一個(gè)Reduce任務(wù)產(chǎn)生的數(shù)據(jù)。使用MapReduceMap和的輸出也許符合一個(gè)不同的非確定順序程序執(zhí)行產(chǎn)生的R2MapMReduceR1、R2e(Ri)Ri已經(jīng)提交的執(zhí)行過程（有且僅有在我們的計(jì)算運(yùn)行環(huán)境中，網(wǎng)絡(luò)帶寬是一個(gè)相當(dāng)匱乏的資源。我們通過盡量把輸入數(shù)據(jù)(GFS管理)存儲在集群中機(jī)器的本地磁盤上來節(jié)省網(wǎng)絡(luò)帶寬。GFS64MBBlockBlock保存MapMReduce拆分成R個(gè)片段執(zhí)行。理想情況下，M和R應(yīng)當(dāng)Map任務(wù)都可以分布到所有其他的workerMap任務(wù)/Reduce1個(gè)字節(jié)就可以了。更進(jìn)一步，R值通常是由用戶指定的，因?yàn)槊總€(gè)Reduce任務(wù)最終都會生成一個(gè)獨(dú)立的輸出文件。實(shí)際使M16M64M的輸入數(shù)據(jù)（這樣，上面描寫的輸入數(shù)據(jù)本地存儲優(yōu)化策略才最有效Rworker機(jī)器數(shù)量MapReduce長的時(shí)間才完成最后幾個(gè)Map或ReduceMapReduce的一個(gè)問題是由于機(jī)器的初始化代碼有bug，導(dǎo)致關(guān)閉了的處理器的緩存：在這些機(jī)器上執(zhí)行任務(wù)的性能和5.344%的時(shí)間完成MapReduce函數(shù)提供的基本功能已經(jīng)能夠滿足大部分的計(jì)算需要，我們還是發(fā)掘出了一MapReduce的使用者通常會指定Reduce任務(wù)和Reduce任務(wù)輸出文件的數(shù)量（Rkey上使hash方法(比如，hash(key)modR)進(jìn)行分區(qū)。hashkeykeyURLs，我們希望每個(gè)主機(jī)的所有條目保持在同一個(gè)輸出文MapReducehash(Hostname(urlkey))modR”作為分區(qū)函數(shù)就可以把所有來自同一個(gè)主機(jī)的URLs保存在同一個(gè)輸出文件中。key/valuepair數(shù)據(jù)的處理順序是按照key值增量順序處理的。這樣的順key值隨機(jī)存取的應(yīng)用非常有意義，Combiner布)Map任務(wù)將產(chǎn)生成千上萬個(gè)這樣的記錄<the,1>。所有的這些記錄將通過網(wǎng)絡(luò)被發(fā)送到一個(gè)單獨(dú)的ReduceReduce任務(wù)把所有這些記錄累加起來產(chǎn)生一個(gè)數(shù)字。我們允許用戶指定一個(gè)可選Combiner函數(shù)在每臺執(zhí)行Map任務(wù)的機(jī)器上都會被執(zhí)行一次。一般情況下，CombinerReduce函數(shù)是一樣的。Combiner函數(shù)和Reduce函數(shù)之間唯一的區(qū)別是MapReduce庫怎樣控制函數(shù)的輸出。Reduce函數(shù)的CombinerReduce任務(wù)。MapReduceAcombiner函數(shù)MapReduce庫支持幾種不同的格式的輸入數(shù)據(jù)。比如，文本模式的輸入數(shù)據(jù)的每一行被視為是一個(gè)key/valuepair。key是文件的偏移量，valuekey進(jìn)行排序來存儲key/valuepair的序列。每種輸入類型的實(shí)現(xiàn)都必須能夠把輸入數(shù)據(jù)分割成數(shù)據(jù)片段，該數(shù)據(jù)片段能夠由單Map任務(wù)來進(jìn)行后續(xù)處理(例如，文本模式的范圍分割必須確保僅僅在每行的邊界進(jìn)行范圍分割)。雖然個(gè)簡單的Reader接口實(shí)現(xiàn)就能夠支持一個(gè)新的輸入類型。ReaderReader，Reader。在某些情況下，MapReduce的使用者發(fā)現(xiàn)，如果在Map和/Reduce操作過程中增加輔助的輸出文件會rename重新命名這個(gè)臨時(shí)文件。3bg導(dǎo)致Mp或者ReuceahMReuce操作ug后再次執(zhí)行MpRducebugbugapeducea，errorMapReduce操作之前，MapReduce庫通過全局變量保存記錄序號。如果用戶程序觸發(fā)了一個(gè)系看到在處理某條特定記錄不止失敗一次時(shí)，master就標(biāo)志著條記錄需要被跳過，并且在下次重新執(zhí)行相關(guān)的MapReduce任務(wù)的時(shí)候跳過這條記錄。MapReducebug是非常困難的，因?yàn)閷?shí)際執(zhí)行操作時(shí)不但是分布在系統(tǒng)中執(zhí)行的，而且為了簡化調(diào)試、profileMapReduce庫的本地實(shí)現(xiàn)版本，通過使用本地版本的用本地調(diào)試和測試工具（gdbmasterHTTP服務(wù)器（Jetty）顯示一組狀態(tài)信息頁面，用戶可以監(jiān)控各種執(zhí)行狀態(tài)。狀workerMap和MapReduce庫使用計(jì)數(shù)器統(tǒng)計(jì)不同事件發(fā)生次數(shù)。比如，用戶可能想統(tǒng)計(jì)已經(jīng)處理了多少個(gè)單詞、已經(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操作完成之后，返回給用戶代碼。的值的時(shí)候，masterMapReduce任務(wù)，避免重復(fù)累加（之前提到的備用任務(wù)和失效有些計(jì)數(shù)器的值是由MapReduce庫自動維持的，比如已經(jīng)處理的輸入的key/valuepairkey/valuepairkeyvaluepairkeyvaluepair，或者處理的German文檔數(shù)量在處理的整個(gè)文檔數(shù)本節(jié)我們用在一個(gè)大型集群上運(yùn)行的兩個(gè)計(jì)算來衡量MapReduce1TB的數(shù)據(jù)中1TB的數(shù)據(jù)進(jìn)行排序。這兩個(gè)程序在大量的使用MapReduce等部署1毫秒。CPU、磁盤和網(wǎng)絡(luò)基本上處于空閑狀態(tài)。Block（M=15000（R=1圖2顯示了這個(gè)運(yùn)算隨時(shí)間的處理過程。其中Y軸表示輸入數(shù)據(jù)的處理速度。處理速度隨著參與MapReduce1764worker30GB/s。當(dāng)150秒。這包括了大約一分鐘的初始啟動階段。初始啟動階段消耗的時(shí)間包括了是把這個(gè)程序傳送到各排序程序處理10的10次方個(gè)100個(gè)字節(jié)組成的記錄（大概1TB的數(shù)據(jù)。這個(gè)程序模仿TeraSort50行代碼組成。只有三行的Map10key值作為排序的keykeykey/valuepair值輸出。我們使用了一個(gè)內(nèi)置的恒等函數(shù)作為Reducekey/valuepair值不作任何改變輸出。最終排序結(jié)果輸出到兩路復(fù)制的GFS文件系統(tǒng)（2TB的數(shù)據(jù)。Block（M=15000（R=4000benchmarkkey的分區(qū)情況。通常對于排序程序來說，我們會MapReduce操作用于采樣key值的分布情況，通過采樣的數(shù)據(jù)來計(jì)算對最終排序處理的分grep程序的中間結(jié)果輸出幾乎可以忽略不計(jì)。Reduce任務(wù)有些完成了，我們開始執(zhí)行剩下的Reduce600秒后結(jié)束。左下圖表示Reduce850891秒。這個(gè)速度和TeraSortbenchmark[18]1057秒相差不多?！?GS是底層文件系統(tǒng)的保證數(shù)據(jù)可靠性和可用性的實(shí)現(xiàn)機(jī)制。如果底層文件系統(tǒng)使用類似容錯(cuò)編碼14esuecodngbackup5Reduce3001283kill了，機(jī)器本身還在工作。圖三（c）Map任務(wù)丟失了（由于相應(yīng)的執(zhí)行Map任務(wù)的worker進(jìn)程被kill了Map任務(wù)很快就被重新執(zhí)行了。933秒內(nèi)完成，包括了初始啟動時(shí)間（5%的時(shí)間。了輸入數(shù)據(jù)本地優(yōu)化、worker機(jī)器之間的動態(tài)負(fù)載均衡等等。從那以后，我們驚喜的發(fā)現(xiàn)，MapReduce庫能廣泛應(yīng)用于我們?nèi)粘９ぷ髦杏龅降母黝悊栴}。它現(xiàn)在在Google內(nèi)部各個(gè)領(lǐng)域得到廣泛應(yīng)用，包括：GoogleNewsFroogle從公眾查詢產(chǎn)品（比如GoogleZeitgeist）年早些時(shí)候的0個(gè)增長到2004年9月份的差不多900MapReduce的成功取決于采用MapReduce在每個(gè)任務(wù)結(jié)束的時(shí)候，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)的計(jì)算步驟分開處理，而不是混在4rawcontentshtml標(biāo)記后的內(nèi)容、pdfword可以通過把N個(gè)元素的數(shù)組的前綴在NogN915。MpRduceBulkSynchronousProgramming[17]MPI原語[11]提供了更高級別的并行處理抽象，可以更容易寫出并行處理的程序。MapReduce和這些系統(tǒng)的關(guān)鍵不同之處在于，MapReduce利用限制性編程模式實(shí)現(xiàn)了用activedisks[12,15]activedisks中，計(jì)算任務(wù)是盡量推送到數(shù)據(jù)存儲的節(jié)點(diǎn)處理6IO子系統(tǒng)的吞吐量。我們在掛載幾個(gè)硬盤的普通機(jī)器上執(zhí)行我們的備用任務(wù)機(jī)制和CharlotteSystem[3]eagerEager調(diào)度機(jī)制的一個(gè)缺點(diǎn)是MapReduce的實(shí)現(xiàn)依賴于一個(gè)內(nèi)部的集群管理系統(tǒng)，這個(gè)集群管理系統(tǒng)負(fù)責(zé)在一個(gè)超大的、共享機(jī)器的Condor[16]是一樣。MapReduceNOW-Sort[1]的操作上很類似。讀取輸入源的機(jī)器（mapworkers）把待排序R個(gè)Reduceworker中的一個(gè)進(jìn)行處理。每個(gè)Reduceworker在本地對數(shù)據(jù)進(jìn)行排序（盡可能在內(nèi)存中排序。當(dāng)然，NOW-SortMapReduce函數(shù)的機(jī)會，因此不具備MapReduce庫廣泛的實(shí)用性。River[2]提供了一個(gè)編程模型：處理進(jìn)程通過分布式隊(duì)列傳送數(shù)據(jù)的方式進(jìn)行互相通訊。和MapReduce類似，River系統(tǒng)嘗試在不對等的硬件環(huán)境下，或者在系統(tǒng)顛簸的情況下也能提供近似平均的性能。River是通過精心調(diào)度硬盤和網(wǎng)絡(luò)的通訊來平衡任務(wù)的完成時(shí)間。MapReduce庫采用了其它的方法。通過對編程模型56、9、136TACC[7]MapReduce一樣，它也依靠重新執(zhí)行機(jī)制來MapReduce編程模型在Google內(nèi)部成功應(yīng)用于多個(gè)領(lǐng)域。我們把這種成功歸結(jié)為幾個(gè)方面：首先，由于MapReduce簡單的解決。比如，MapReduceGoogle的網(wǎng)絡(luò)搜索服務(wù)所需要的數(shù)據(jù)、用來MapReduce。這個(gè)實(shí)現(xiàn)使得有效利用這些豐富的計(jì)算資源變得非常簡單，因此也適合用來解決Google遇到的其他很多需要大量計(jì)算的問題。我們也從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-scaledataprocessing.IEEEComputer,pages68.74,June2001.DouglasThain,ToddTannenbaum,andMironLivny.Distributedcomputinginpractice:TheCondorexperience.ConcurrencyandComputation:PracticeandExperience,2004.L.G.Valiant.Abridgingmodelforparallelcomputation.CommunicationsoftheACM,33(8):103.111,JimWyllie.Spsort:Howtosortaterabytequickly.\h#include#include//User’smapclassWordCounter:publicMapper{virtualvoidMap(constMapInput&input){conststring&text=input.value();constintn=text.size();for(inti=0;i<n;){//Skippastleadingwhitespacewhile((i<n)&&isspace(text[i]))//Findwordendintstart=i;while((i<n)&&if(start<//User’sreduceclassAdder:publicReducervirtualvoidReduce(ReduceInput*input)//Iterateoverallentrieswith//samekeyandaddtheint64value=while(!input->done())//Emitsumforinput-intmain(intargc,char**argv)//Storelistofinputfilesintofor(inti=1;i<argc;i++)MapReduceInput*input=//Specifytheoutput//MapReduceOutput*out=//Optional:dopartialsumswithin//taskstosavenetwork//Tuningparameters:useatmost//machinesand100MBofmemoryper//NowrunitMapReduceResult//NowrunitMapReduceResultresult;if(!MapReduce(spec,&result))//Done:‘result’structurecontains//aboutcounters,timetaken,number//machinesused,etc.return0;GoogleFileSystem中文版目錄TOC\o"1-2"\h\u3008 1251201. 132572. 174783. 1119231 158722 265772.1 2272202.2 321502.3 3282052原文：well- 3279182.4Master 5202852.5 5322362.6 6238318Chunk 6320362.6.2Chunk 799232.6.3 7134610 71168012 7100252.7 82664517Master 9195622.7.2 10233163 10105673.1 1021813.2 12921020ChunkChunk 1287033.3 137523.4 14108944Master 145334.1 15182524.2 15121464.3 16158934.4 171269924metadata 17232104.5 18283635 18301915.1 184135.2 20307725.3 2142866 21139886.1 2123246.2 23197926.3工作負(fù)荷分析(Workload 263024629 26252026.3.2Chunk 27212026.3.3vs. 28258156.3.4Master 29154997 2998778 3014649 31GoogleFileSystem我們設(shè)計(jì)并實(shí)現(xiàn)了GoogleGFSGFS雖然運(yùn)行在廉價(jià)的普遍硬件設(shè)備上，但是它依然了提供災(zāi)難冗余的能力，為大量客戶機(jī)提供了高性能的GFS的設(shè)計(jì)目標(biāo)與許多傳統(tǒng)的分布式文件系統(tǒng)有很多相同之處，但是，我們的設(shè)計(jì)還是以我們對自己的應(yīng)用的負(fù)載情況和技術(shù)環(huán)境的分析為基礎(chǔ)的，不管現(xiàn)在還是將來，GFS和早期的分布式文件系統(tǒng)的設(shè)GFS完全滿足了我們對存儲的需求。GFSGoogle內(nèi)部，存儲我們的利用數(shù)千臺機(jī)器的數(shù)千個(gè)硬盤，提供了數(shù)百TB的存儲空間，同時(shí)為數(shù)百個(gè)客戶機(jī)服務(wù)。D43—DGoogleGoogle文件系統(tǒng)(GoogleFileSystem–GFS和早期文件系統(tǒng)的假設(shè)都有明顯的不同。所以我們重新審視了傳統(tǒng)文件系統(tǒng)在設(shè)計(jì)上的折衷選擇，衍生GoogleGoogleFileSystem1.0GoogleGoogleFileSystem1.0GSubugGS中。webTB的數(shù)據(jù)KB大小的小文件的方式是非常不明智的，盡管有些文件系統(tǒng)支持這樣的管理方式。I/OBlock的尺寸都需要重新考慮。性模型的要求，這樣就減輕了文件系統(tǒng)對應(yīng)用程序的苛刻要求，大大簡化了GFS的設(shè)計(jì)。我們引入了原子性GoogleGFS1000KB數(shù)據(jù)。3.43.3節(jié)分別討論。GFSMaster節(jié)點(diǎn)3Chunk2原文：well-3MasterGFSMasterMaster節(jié)點(diǎn)復(fù)制，MasterMaster節(jié)點(diǎn)包括兩臺物理主機(jī)Chunk服務(wù)器和客戶端都放在同一臺機(jī)器上，前提是機(jī)器資源允許，并且我們能夠接受不可靠的應(yīng)用程GFS存儲的文件都被分割成固定大小的ChunkChunk創(chuàng)建的時(shí)候，MasterChunk分64位的Chunk標(biāo)識。Chunk服務(wù)器把ChunkLinux文件的形式保存在本地硬盤Chunk標(biāo)識和字節(jié)范圍來讀寫塊數(shù)據(jù)。出于可靠性的考慮，每個(gè)塊都會復(fù)制到多個(gè)塊服3個(gè)存儲復(fù)制節(jié)點(diǎn)，不過用戶可以為不同的文件命名空間設(shè)定不同的復(fù)制級MasterChunk的映Chunk5ChunkChunk服務(wù)器之間的遷移。MasterChunk服務(wù)器通訊，發(fā)送指令到各個(gè)Chunk服務(wù)器并接收Chunk服務(wù)器的狀態(tài)信息。GFSGFSAPI接口函數(shù)、Master節(jié)點(diǎn)和ChunkMaster節(jié)點(diǎn)的通信只獲取能，因此，GFSAPILinuxvnode級別。4BDBlease5原文：orphaned6Master單一的Master節(jié)點(diǎn)的策略大大簡化了我們的設(shè)計(jì)。單一的Master節(jié)點(diǎn)可以通過全局的信息精確定位ChunkMaster節(jié)點(diǎn)的讀寫，避免Master節(jié)點(diǎn)成為系統(tǒng)的瓶MasterMaster節(jié)點(diǎn)詢問它應(yīng)該聯(lián)系的Chunk服務(wù)器。Chunk服務(wù)器進(jìn)行數(shù)據(jù)讀寫操作。1解釋一下一次簡單讀取的流程。首先，客戶端把文件名和程序指定的字節(jié)偏移，根據(jù)固定ChunkChunkChunkMaster節(jié)點(diǎn)。Master節(jié)Chunk標(biāo)識和副本的位置信息發(fā)還給客戶端?？蛻舳擞梦募虲hunkkey緩存這些信Chunk的標(biāo)識和字節(jié)范圍。在對這個(gè)ChunkMaster節(jié)點(diǎn)通訊了，除非緩存的元數(shù)據(jù)信息過期或Chunk信息，Master節(jié)點(diǎn)的回應(yīng)也可能包含了緊跟著這些被請求的Chunk后面的Chunk的信息。在實(shí)際應(yīng)用中，這些額外的信息在沒有任何代價(jià)的情Master節(jié)點(diǎn)未來可能會發(fā)生的幾次通訊。64MB每個(gè)Chunk的副本都以普通Linux文件的形式保存在Chunk服務(wù)器上，只有在需要的時(shí)候才擴(kuò)大。惰性空間Chunk尺寸最具爭議一點(diǎn)。ChunkMaster節(jié)點(diǎn)通訊的需求，因?yàn)橹恍枰淮魏蚆ater節(jié)點(diǎn)的通信就可以獲取Chunk的位置信息，之后就可以對同一個(gè)Chunk進(jìn)行多次的讀寫操ChunkTB的工作數(shù)據(jù)集所有的ChunkChunk尺寸，客戶端能夠?qū)σ粋€(gè)塊進(jìn)行多次操作，這樣就可以Chunk。當(dāng)有許多的客戶端對同一個(gè)小文件進(jìn)行多次的訪問時(shí)，存儲這些Chunk的ChunkChunk的大文件，熱點(diǎn)還不是主GFS用于批處理隊(duì)列系統(tǒng)的時(shí)候，熱點(diǎn)的問題還是產(chǎn)生了：一個(gè)可執(zhí)行文件在GFSsingle-chunk文件，之后這個(gè)可執(zhí)行文件在數(shù)百臺機(jī)器上同時(shí)啟動。存放這個(gè)可執(zhí)行文件的幾Chunk服務(wù)器被數(shù)百個(gè)客戶端的并發(fā)請求訪問導(dǎo)致系統(tǒng)局部過載。我們通過使用更大的復(fù)制參數(shù)來保存可Mser7存儲3ChukChukChukMser8同時(shí)也制到其它的遠(yuǎn)程MserMseraeraer服務(wù)器不會持久保存hukaer服務(wù)器在啟動時(shí)，或者有新的Chuk服務(wù)器加入時(shí)，向各個(gè)Chuk服務(wù)器輪詢它們所存儲的Chunk的信息。服務(wù)器失效的時(shí)重新復(fù)制數(shù)據(jù)、通過Chunk的遷移實(shí)現(xiàn)跨Chunk服務(wù)器的負(fù)載均衡以及磁盤使用狀況統(tǒng)計(jì)等功能。4.34.4章節(jié)將深入討論這些行為。Chunk64Master服務(wù)器增加額外內(nèi)存的費(fèi)用是很少的，而通過增加有限的7MasterMasterMaster服務(wù)器的行為，如存儲、內(nèi)存等等，因8ChunkGoogleGoogleFileSystem1.0GoogleGoogleFileSystem1.0ChunkMaster服務(wù)器并不保存持久化保存哪個(gè)ChunkChunk的副本的信息。Master服務(wù)器只是Chunk服務(wù)器以獲取這些信息。Master服務(wù)器能夠保證它持有的信息始終是最新的，因?yàn)镃hunk位置的分配，而且通過周期性的心跳信息監(jiān)控Chunk服務(wù)器的狀態(tài)。時(shí)候輪詢Chunk服務(wù)器，之后定期輪詢更新的方式更簡單。這種設(shè)計(jì)簡化了在有Chunk服務(wù)器加入集群、離開集群、更名、失效、以及重啟的時(shí)候，MasterChunk服務(wù)器數(shù)據(jù)同步的問題。在一個(gè)擁有數(shù)百臺Chunk服務(wù)器才能最終確定一個(gè)Chunk是否在它的硬盤Chunk自動消失(比如，硬盤損壞了或者無法訪問了)，亦或者操作人員可能會重命名一個(gè)Chunk服務(wù)器。操作日志包含了關(guān)鍵的元數(shù)據(jù)變更歷史記錄。這對GFS非常重要。這不僅僅是因?yàn)椴僮魅罩臼窃獢?shù)據(jù)唯一的持久化存儲記錄，它也作為判斷同步操作順序的邏輯時(shí)間基線9。文件和Chunk，連同它們的版本(參考4.5節(jié))，都由它們創(chuàng)建的邏輯時(shí)間唯一的、永久的標(biāo)識。Chunk本身沒有出現(xiàn)任何問題，我們?nèi)杂锌赡軄G失整個(gè)文件系統(tǒng)，或者丟失客戶機(jī)器的硬盤后，才會響應(yīng)客戶端的操作請求。Master服務(wù)器會收集多個(gè)日志記錄后批量處理，以減少寫入磁有的狀態(tài)數(shù)據(jù)寫入一個(gè)Checkpoint文件12。在災(zāi)難恢復(fù)的時(shí)候，Master服務(wù)器就通過從磁盤上讀取這個(gè)CheckpointCheckpoint之后的有限個(gè)日志文件就能夠恢復(fù)系統(tǒng)。CheckpointB-樹91011Checkpoint12CheckpointMaster服務(wù)器的內(nèi)部狀態(tài)被組織為一種格式，這Checkpoint過程中不會阻塞正在進(jìn)行的修改操作。Master服務(wù)器使用獨(dú)立的線程切換到新的日志文件和創(chuàng)建新的Checkpoint文件。新的Checkpoint文件包括切換前所有的修改。對于一個(gè)包含數(shù)百萬個(gè)Checkpoint1分鐘左右的時(shí)間。創(chuàng)建完成后，Checkpoint文件會被寫入在本MasterCheckpoint文件和后續(xù)的日志文件。舊的Checkpoint文件和日志文件可Checkpoint文件。GFS支持一個(gè)寬松的一致性模型，這個(gè)模型能夠很好的支撐我們的高度分布的應(yīng)用，同時(shí)還保持了相對簡單且容易實(shí)現(xiàn)的優(yōu)點(diǎn)。本節(jié)我們討論GFS的一致性的保障機(jī)制，以及對應(yīng)用程序的意義。我們也著重描述GFS如何管理這些一致性保障機(jī)制，但是實(shí)現(xiàn)的細(xì)節(jié)將在本論文的其它部分討論。GFS原子性和正確性（4.1章）的保障；Master節(jié)點(diǎn)的操作日志定義了這些操作在全局的順序（2.6.3章。數(shù)據(jù)修改后文件region141總結(jié)了各種操作如果所有客戶端，無論從哪個(gè)副本讀取，讀到的數(shù)據(jù)都一樣，那么我們認(rèn)為文件regionregion就是13catastrophes14regionregionregion處于regionregion的不同類型。另外，GFSregion被認(rèn)定是不一致的，經(jīng)過了一系列的成功的修改操作之后，GFSregion是已定義的，并且包含最后一次修（a）（b）而導(dǎo)致其失效。失效的副本不會再進(jìn)行任何修改操作，MasterChunk副本的位置信息由于ChunkChunk位置信息。而且，由于我們的文件大多數(shù)都是只進(jìn)行追加操作的，所以，一個(gè)失效的副Chunk位置信息。即使在修改操作成功執(zhí)行很長時(shí)間之后，組件的失效也可能損壞或者刪除數(shù)據(jù)。GFSMaster服務(wù)ChunkChunkChecksum來校驗(yàn)數(shù)據(jù)是否損壞（5.2章。一旦發(fā)現(xiàn)問題，數(shù)據(jù)要盡快利用有效的副本進(jìn)行恢復(fù)（4.3章Chunk的所有副本GFSChunkGFS的16本文中將用到兩個(gè)專有名詞，ReaderWriterGFS17Master使用GFS的應(yīng)用程序可以利用一些簡單技術(shù)實(shí)現(xiàn)這個(gè)寬松的一致性模型，這些技術(shù)也用來實(shí)現(xiàn)一些其它包含程序級別的校驗(yàn)和。Readers僅校驗(yàn)并處理上個(gè)Checkpoint之后產(chǎn)生的文件regionregion的狀對應(yīng)用程序的失敗處理更具有彈性。CheckpointWriterReader者是一個(gè)生產(chǎn)者-Writer的輸出。Readers使用下面的方法來處理偶然性的填充數(shù)據(jù)和重復(fù)內(nèi)容。Writers在每條寫入的記錄中都包含了額外的信息，例如Checksum，用來驗(yàn)證它的有效性。ReaderChecksum識別和拋棄額外的填充數(shù)據(jù)和記錄片段。如果們的程序共享的庫中，并且適用于Google內(nèi)部的其它的文件接口實(shí)現(xiàn)。所以，相同序列的記錄，加上一些偶Reader了。帶著這樣的設(shè)計(jì)理念，我們現(xiàn)在描述一下客戶機(jī)、MasterChunk服務(wù)器如何進(jìn)行交互，以實(shí)現(xiàn)變更是一個(gè)會改變Chunk18ThesefunctionalitiesforrecordI/O19leaseChunkChunkChunk的所有更改操作進(jìn)行序列化。Master節(jié)點(diǎn)選擇的租約的順序決定，然后由租約中主Chunk分配的序列號決定。Master60秒。不過，只要ChunkChunkMaster節(jié)點(diǎn)的確認(rèn)并收到租約延長的時(shí)間。Master節(jié)點(diǎn)和Chunk服務(wù)器之間的心跳消息中來傳遞。有時(shí)Master節(jié)點(diǎn)會試圖提前取消租約（例如，Master節(jié)點(diǎn)想取消在一個(gè)已經(jīng)被改名的文件上的修改操作。即使Master節(jié)點(diǎn)和主ChunkChunk副本簽訂新的租約。MasterChunkMasterChunk的標(biāo)識符以及其它副本（secondary副本、二級副本）的位置返回給客戶Chunk不可用，或者主Chunk回復(fù)信息表明它已不再持Master節(jié)點(diǎn)聯(lián)系。客戶機(jī)把數(shù)據(jù)推送到所有的副本上?？蛻魴C(jī)可以以任意的順序推送數(shù)據(jù)。Chunk服務(wù)器接收到數(shù)據(jù)并保Chunk服務(wù)器保存了主Chunk。3.2章節(jié)會進(jìn)一步討論這點(diǎn)。Chunk服務(wù)器。這個(gè)請求標(biāo)識了早前推送到Chunk為接收到的所有操作分配連續(xù)的序列號，這些操作可能來自不同的客戶機(jī)，序列ChunkChunk分配的序列號以相同的順序執(zhí)行所有的二級副本回復(fù)主ChunkChunk服務(wù)器20回復(fù)客戶機(jī)。任何副本產(chǎn)生的任何錯(cuò)誤都會返回給客戶機(jī)。在出現(xiàn)錯(cuò)誤的情況下，寫Chunk（Chunk上失敗了，操作就不會被分配序列region的尾部可能包含來自不同客戶機(jī)的數(shù)據(jù)片段，盡管如此，由于這些分解后的寫入操Chunk、然后再Chunk服務(wù)器鏈推送。我們的目標(biāo)為了盡可能的避免出現(xiàn)網(wǎng)絡(luò)瓶頸和高延遲的鏈接（eg，inter-switch最有可能出現(xiàn)類似問題，每臺機(jī)器S4S2。同樣的，S2S3和S4之間更近的機(jī)器，依次類推推送下去。我們IPTCP連接的、管道式數(shù)據(jù)推送方式來最小化延遲。Chunk服務(wù)器接收到數(shù)據(jù)后，20ChunkChunk立刻向前推送不會降低接收的速度。在沒有網(wǎng)絡(luò)擁塞的情況下，傳送B字節(jié)的數(shù)據(jù)到R（T，LGFS提供了一種原子的數(shù)據(jù)追加操作–記錄追加。傳統(tǒng)方式的寫入操作，客戶程序會指定數(shù)據(jù)寫入的偏使用記錄追加，客戶機(jī)只需要指定要寫入的數(shù)據(jù)。GFS保證至少有一次原子的寫入操作成功執(zhí)行（即寫入一byte流GFS指定的偏移位置上，之后GFS返回這個(gè)偏移量給客戶機(jī)。這類似UnixO_APPEND模式打開的文件，多個(gè)并發(fā)寫操作在沒有競態(tài)條件時(shí)的行3.1Chunk有些額外的控制邏輯?？虲hunk的所有副本，之后發(fā)送請求給主ChunkChunk會檢查這次記錄追（64MBChunk重新進(jìn)行記錄追加操）ChunkChunk把數(shù)據(jù)追加到自己的副本內(nèi)，然后通知二級副本把數(shù)據(jù)寫在跟主Chunk一樣的位置上，最后回復(fù)客戶機(jī)操作成功。同一個(gè)ChunkGFS并不保證ChunkChunk的所有副本的相同偏移位置上。這之Chunk上，即使其它的Chunk副本被Master節(jié)點(diǎn)選為了主Chunk。就我們的一致性保障模型而言，記錄追加）就像AFS（alex注：AFSAndrewFileSystem，一種分布式文件系統(tǒng)copy-on-write保證了后續(xù)對這些ChunkMasterMaster節(jié)點(diǎn)一個(gè)率先創(chuàng)建Chunk的新拷貝的機(jī)會。和源文件指向完全相同的Chunk地址。Master節(jié)點(diǎn)注意到ChunkC122Master節(jié)點(diǎn)不會馬上回復(fù)客戶機(jī)的請求，而是選擇一個(gè)新的Chunk句柄C`。之后，MasterChunkCChunk服務(wù)器創(chuàng)建一C`的新ChunkChunk所在Chunk服務(wù)器上創(chuàng)建新的Chunk，我們確保數(shù)據(jù)在本地而不是通沒什么不同：MasterChunkC`的一個(gè)副本擁有租約，之后回復(fù)客戶機(jī)，客戶機(jī)得到回復(fù)后就可以正常的寫這個(gè)Chunk，而不必理會它是從一個(gè)已存在的Chunk克隆出來的。MasterMasterChunkChunk21COW221.SnapshotMasterChunk服務(wù)器上快照所涉及的所有region上的鎖來保證執(zhí)行的正確順序。支持文件或者目錄的鏈接（Unix術(shù)語中的硬鏈接或者符號鏈接。在邏輯上，GFS的名稱空間就是一個(gè)全每個(gè)Master節(jié)點(diǎn)的操作在開始之前都要獲得一系列的鎖。通常情況下，如果一個(gè)操作涉及意，根據(jù)操作的不同，leaf可以是一個(gè)文件，也可以是一個(gè)目錄?，F(xiàn)在，我們演示一下在/home/user被快照到/save/user的時(shí)候，鎖機(jī)制如何防止創(chuàng)建文件/home/user/foo?？煺詹僮鳙@取/home和/save的讀取鎖，以及/home/user和/save/user的寫入鎖。文件創(chuàng)建操作獲得/home和GFS集群是高度分布的多層布局結(jié)構(gòu)，而不是平面結(jié)構(gòu)。典型的拓?fù)浣Y(jié)構(gòu)是有數(shù)百個(gè)Chunk服務(wù)器安裝在許多機(jī)架上。Chunk服務(wù)器被來自同一或者不同機(jī)架上的數(shù)百個(gè)客戶機(jī)輪流訪問。不同機(jī)架上的兩臺機(jī)器Chunk副本位置選擇的策略服務(wù)兩大目標(biāo)：最大化數(shù)據(jù)可靠性和可用性，最大化網(wǎng)絡(luò)帶寬利用率。為了ChunkChunkChunk的讀操作，能夠有效利用多個(gè)機(jī)架的Master節(jié)點(diǎn)創(chuàng)建一個(gè)Chunk時(shí)，它會選擇在哪里放置初始的空的副本。MasterChunkChunk創(chuàng)建操作的次數(shù)。雖然創(chuàng)建操作本身是廉價(jià)的，但是創(chuàng)建操作也意味著隨之會有大量的寫入數(shù)據(jù)的操作，因?yàn)镃hunkWriter真正寫入數(shù)據(jù)的時(shí)候才被創(chuàng)建，而在我們的“追加一次，讀取多次”的工作模式下，Chunk一旦寫入成功之后就會變?yōu)橹蛔x的了。Chunk的有效副本數(shù)量少于用戶指定的復(fù)制因數(shù)的時(shí)候，Master節(jié)點(diǎn)會重新復(fù)制它。這可能是由幾個(gè)Chunk服務(wù)器不可用了，Chunk服務(wù)器報(bào)告它所存儲的一個(gè)副本損壞了，Chunk服務(wù)器的一個(gè)磁盤因?yàn)殄e(cuò)誤不可用了，或者Chunk副本的復(fù)制因數(shù)提高了。每個(gè)需要被重新復(fù)制的Chunk都會根據(jù)幾個(gè)因素進(jìn)行排序。一個(gè)因素是Chunk現(xiàn)有副本數(shù)量和復(fù)制因數(shù)相差多少。例如，丟失兩個(gè)副本的Chunk比丟Chunk有更高的優(yōu)先級。另外，我們優(yōu)先重新復(fù)制活躍（live）Chunk而不是最近剛被刪除的文件的Chunk（4.4節(jié)Chunk對正在運(yùn)行的應(yīng)用程序的影響，我們提Chunk的優(yōu)先級。Chunk服務(wù)器上的正在進(jìn)行的克隆操作的數(shù)量、在機(jī)架間分布副本。為了防止克隆產(chǎn)生的網(wǎng)絡(luò)流量大大超過客戶機(jī)的流量，Master節(jié)點(diǎn)對Chunk服務(wù)器上的同時(shí)進(jìn)行的克隆操作的數(shù)量都進(jìn)行了限制。另外，Chunk服務(wù)器通過調(diào)節(jié)Chunk服務(wù)器讀請求的頻率來限制它用于克隆操作的帶寬。MasterChunk填滿它，以至于過載。新副本的存儲位置選擇策略和上面討論的相當(dāng)一個(gè)文件被應(yīng)用程序刪除時(shí)，Master節(jié)點(diǎn)象對待其它修改操作一樣，立刻把刪除操作以日志的方式記錄下來。但是，Master節(jié)點(diǎn)并不馬上回收資源，而是把文件名改為一個(gè)包含刪除時(shí)間戳的、隱藏的名字。當(dāng)Master節(jié)點(diǎn)對文件系統(tǒng)命名空間做常規(guī)掃描的時(shí)候，它會刪除所有三天前的隱藏文件（這個(gè)時(shí)間間隔是可以元數(shù)據(jù)才會被刪除。這也有效的切斷了文件和它包含的所有Chunk的連接23。Chunk名字空間做類似的常規(guī)掃描時(shí)，MasterChunk（Chunk）并刪除它們的元數(shù)據(jù)。ChunkMasterChunk子集的信息，Master節(jié)點(diǎn)回復(fù)Chunk服務(wù)器哪些Chunk在MasterChunk服務(wù)器可以任Chunk的副本。GFS系統(tǒng)中是非常ChunkMaster服務(wù)器上的文件到塊的映射表中。我們也可以很輕易的得到所有ChunkLinux文件的形式存儲在Chunk服務(wù)器的指定目錄下。Master垃圾回收方式簡單可靠。ChunkChunk服務(wù)器創(chuàng)建成功，某些Chunk服務(wù)器上創(chuàng)建失敗，失敗的副本處于無法被MasterMaster節(jié)點(diǎn)必須重新發(fā)送失敗的刪除消息，包括自身的和Chunk服務(wù)器的24。垃圾回收提供了一致的、可靠的清除無用副本的方法。第二，垃圾回收把Master節(jié)點(diǎn)規(guī)律性的后臺活動中，比如，例行掃描和與Chunk服務(wù)器握手等。因此，操作被批量的執(zhí)行，開銷會被分散。另外，垃圾回收在Master節(jié)點(diǎn)相對空閑的時(shí)候完成。這樣Master23原文：Thiseffectivelyseversitslinkstoallits24metadataChunk服務(wù)器失效時(shí)，Chunk的副本有可能因錯(cuò)失了一些修改操作而過期失效。Master節(jié)點(diǎn)保存了每Chunk的版本號，用來區(qū)分當(dāng)前的副本和過期副本。副本。Master節(jié)點(diǎn)和這些副本都把新的版本號記錄在它們持久化存儲的狀態(tài)信息中。這個(gè)動作發(fā)生在任何客Chunk開始寫之前。如果某個(gè)副本所在的Chunk服務(wù)器正好處于失效狀態(tài)，那么副本的版本號就不會被增加。Master節(jié)點(diǎn)在這個(gè)ChunkMaster節(jié)點(diǎn)報(bào)告它Chunk的集合以及相應(yīng)的版本號的時(shí)候，就會檢測出它包含過期的ChunkMaster節(jié)點(diǎn)看到一個(gè)比它記錄的版本號更高的版本號，Master節(jié)點(diǎn)會認(rèn)為它和Chunk服務(wù)器簽訂租約的操作失敗了，因此會選擇Master節(jié)點(diǎn)在例行的垃圾回收過程中移除所有的過期失效副本。在此之前，Master節(jié)點(diǎn)在回復(fù)客戶機(jī)的Chunk信息請求的時(shí)候，簡單的認(rèn)為那些過期的塊根本就不存在。另外一重保障措施是，Master節(jié)點(diǎn)在通知ChunkChunk服務(wù)器從哪個(gè)Chunk服務(wù)器進(jìn)行克隆時(shí)，消息中都附帶我們在設(shè)計(jì)GFS時(shí)遇到的最大挑戰(zhàn)之一是如何處理頻繁發(fā)生的組件失效。組件的數(shù)量和質(zhì)量讓這些問題些挑戰(zhàn)，以及當(dāng)組件失效不可避免的發(fā)生時(shí)，用GFS自帶工具診斷系統(tǒng)故障。Master服務(wù)器和Chunk服務(wù)器是如何關(guān)閉的，它們都被設(shè)計(jì)為可以在數(shù)秒鐘內(nèi)恢復(fù)它們的狀態(tài)并重kill掉進(jìn)程來關(guān)閉服務(wù)器?？蛻糁卦囘@個(gè)請求。6.6.2章節(jié)記錄了實(shí)測的啟動時(shí)間。Chunk正如之前討論的，每個(gè)ChunkChunk服務(wù)器上。用戶可以為文件命名空節(jié)）發(fā)現(xiàn)了已經(jīng)損壞的數(shù)據(jù)，MasterChunk都被完整復(fù)制26ChunkMaster為了保證Master服務(wù)器的可靠性，Master服務(wù)器的狀態(tài)也要復(fù)制。Master服務(wù)器所有的操作日志和checkpointMaster服務(wù)器狀態(tài)的修改操作能夠提交成功的前提是，操作日志程所在的機(jī)器或者磁盤失效了，處于GFS系統(tǒng)外部的監(jiān)控進(jìn)程會在其它的存有完整操作日志的機(jī)器上啟動一MasterMaster節(jié)點(diǎn)。供文件系統(tǒng)的只讀訪問。它們是影子，而不是鏡像，所以它們的數(shù)據(jù)可能比“主”Master服務(wù)器更新要慢，125aminor26Chunk27ErasurecodesbufferMasterChunk服務(wù)器上讀取的，因此，應(yīng)用程序不“影子”Master服務(wù)器為了保持自身狀態(tài)是最新的，它會讀取一份當(dāng)前正在進(jìn)行的操作的日志副本，并MasterMasterMasterChunk服務(wù)器輪詢數(shù)據(jù)（之后定期拉數(shù)據(jù)Chunk副本的位置信MasterChunkMaster服務(wù)器因創(chuàng)建MasterMaster服務(wù)器通信來更新自身狀態(tài)。每個(gè)Chunk服務(wù)器都使用Checksum來檢查保存的數(shù)據(jù)是否損壞?？紤]到一個(gè)GFS集群通常都有好幾百臺機(jī)器、幾千塊硬盤，磁盤損壞導(dǎo)致數(shù)據(jù)在讀寫過程中損壞或者丟失是非常常見的（7節(jié)講了一個(gè)原因。我們可以通過別的Chunk副本來解決數(shù)據(jù)損壞問題，但是跨越Chunk服務(wù)器比較副本來檢查數(shù)據(jù)是否損壞很不實(shí)際。另外，GFS允許有歧義的副本存在：GFS修改操作的語義，特別是早先討論過的原子紀(jì)錄追加的操作，并不保證副本完全相同(alexbyte-wise完全一致的)Chunk服務(wù)器必須獨(dú)立維Checksum來校驗(yàn)自己的副本的完整性。Chunk64KB32Checksum。和其它元數(shù)據(jù)一樣，Checksum與其它的用戶數(shù)據(jù)是分開的，并且保存在內(nèi)存和硬盤上，同時(shí)也記錄操作日志。Chunk服務(wù)器之前，Chunk服務(wù)器會校驗(yàn)讀取操作ChecksumChunk服務(wù)器不會把錯(cuò)誤數(shù)據(jù)傳遞到其它的機(jī)器上。如果發(fā)生某個(gè)塊的Checksum不正確，ChunkMaster服務(wù)器這個(gè)錯(cuò)誤。作為回應(yīng)，請求者應(yīng)當(dāng)從其它副本讀取數(shù)據(jù)，MasterMaster服務(wù)器通知副本錯(cuò)誤的Chunk服務(wù)器刪掉錯(cuò)誤的副本。幾個(gè)塊，而我們只需要讀取一小部分額外的相關(guān)數(shù)據(jù)進(jìn)行校驗(yàn)。GFS客戶端代碼通過每次把讀取操作都對齊ChecksumblockChunk服務(wù)器上，ChecksumI/O操作，ChecksumI/O操作同時(shí)進(jìn)行。ChecksumChunk（與之對應(yīng)的是覆蓋現(xiàn)有數(shù)據(jù)的寫入操作Checksum，并且用所有的追加來的新Checksum塊來計(jì)算新的ChecksumChecksumChunk，我們必須讀取和校驗(yàn)被覆蓋的第一個(gè)和最后一個(gè)塊，然后再執(zhí)行寫操作；操作完成之后再重新計(jì)算和寫入新的Checksum。如果我們不校驗(yàn)第一個(gè)和最Checksum可能會隱藏沒有被覆蓋區(qū)域內(nèi)的數(shù)據(jù)錯(cuò)誤。Chunk服務(wù)器空閑的時(shí)候，它會掃描和校驗(yàn)每個(gè)不活動的Chunk的內(nèi)容。這使得我們能夠發(fā)現(xiàn)很少被同時(shí)也只需要很小的開銷。沒有日志的幫助，我們很難理解短暫的、不重復(fù)的機(jī)器之間的消息交互。GFS的RPC日志包含了網(wǎng)絡(luò)上發(fā)生的所有請求和響應(yīng)的詳細(xì)記錄，但是不包括讀寫的文件數(shù)據(jù)。通過匹配請求本節(jié)中，我們將使用一些小規(guī)模基準(zhǔn)測試來展現(xiàn)GFSGoogle內(nèi)部使用的真實(shí)的GFS1Master服務(wù)器，2Master服務(wù)器復(fù)制節(jié)點(diǎn)，16臺Chunk16個(gè)客戶機(jī)組GFSGFS集群有數(shù)百個(gè)Chunk服務(wù)器和數(shù)百個(gè)客戶機(jī)。HP2524交換機(jī)。GFS1916臺1Gbps的線路連接。N個(gè)客戶機(jī)從GFS320GB4MBregion的32GB10%Linux的文件系統(tǒng)緩沖。我們的測試結(jié)95%的可靠性，因?yàn)橛袝r(shí)候測量會不夠精確。3（a）N1Gbps的鏈125MB/S12.5MB/s10MB/s，也80%1694MB/s，大約是理論整體讀取速度極限值的75%6MB/s80%降低到了75%，主要Chunk服務(wù)器的幾率也增加了，導(dǎo)致整體的讀取效N個(gè)客戶機(jī)同時(shí)向N1MB1GB的數(shù)據(jù)。3（b）67MB/s，因?yàn)槲覀冃枰衙恳籦yte16個(gè)Chunk3個(gè)上，而每個(gè)Chunk12.5MB/s。Chunk服務(wù)器時(shí)采用的管道模式不相適應(yīng)。從一個(gè)副本到另一個(gè)副本的數(shù)據(jù)傳輸2.2MB/sChunk服務(wù)器的幾率也增加了。而且，1616個(gè)客戶機(jī)并行讀取要大得多，因?yàn)槊總€(gè)寫入都會3（c）顯示了記錄追加操作的性能。N個(gè)客戶機(jī)同時(shí)追加數(shù)據(jù)到一個(gè)文件。記錄追加操作的性能受限Chunk的Chunk服務(wù)器的帶寬，而與客戶機(jī)的數(shù)量無關(guān)。記錄追加的速度由一個(gè)客戶機(jī)N個(gè)客戶機(jī)同時(shí)追加數(shù)據(jù)到M個(gè)共享文件中，這里NM都是數(shù)十或者數(shù)百以上。所以，在我們的實(shí)際應(yīng)用中，Chunk服務(wù)器的網(wǎng)絡(luò)擁塞并沒有成為一個(gè)Chunk服務(wù)器的某個(gè)文件正在寫入，客戶機(jī)會去寫另外一個(gè)文件。MBTB的數(shù)據(jù)，之后進(jìn)行轉(zhuǎn)化或者分析，最后把結(jié)果寫回到集群中。集群BB的TB的數(shù)據(jù)集。在這兩個(gè)案例中，一ChunkTB的硬盤空間；兩個(gè)集群雖18TB52TB的文件數(shù)據(jù)。B上有大量的死文件。所謂“死文件”是指文件被刪除了B存儲的文件較大，因此它的Chunk數(shù)量也比較多。ChunkGB的元數(shù)據(jù)，大多數(shù)是來自用戶數(shù)據(jù)的、64KBChecksum。Chunk服務(wù)器上其它的元數(shù)據(jù)是Chunk4.5節(jié)描述過。據(jù)。這和我們設(shè)想的是一樣的，Master服務(wù)器的內(nèi)存大小在實(shí)際應(yīng)用中并不會成為GFS系統(tǒng)容量的瓶頸。大多數(shù)文件的元數(shù)據(jù)都是以前綴壓縮模式存放的文件名。Master服務(wù)器上存放的其它元數(shù)據(jù)包括了文件的所有者和權(quán)限、文件到Chunk的映射關(guān)系，以及每一個(gè)ChunkChunk，我們都保存了當(dāng)前的副本位置以及對它的引用計(jì)數(shù)，這個(gè)引用計(jì)數(shù)用于實(shí)現(xiàn)寫時(shí)拷貝（COW，copy-on-writeMaster服務(wù)器，并獲取到所有Chunk近都因?yàn)樯壭掳姹镜腉FS重新啟動過了。100MB/sChunk300MB/s。A80Bs的網(wǎng)絡(luò)配置可以支持7MBsB支持的峰值讀取速度是100B，0MB。Master3的數(shù)據(jù)顯示了發(fā)送到Master200500個(gè)。Master服務(wù)器可以輕松Master服務(wù)器的處理能力不是系統(tǒng)的瓶頸。Chunk服務(wù)器失效了，一些Chunk副本的數(shù)量可能會低于復(fù)制因子指定的數(shù)量，我們必須通過克ChunkChunk副本所花費(fèi)的時(shí)間取決于資源的數(shù)量。B上的一個(gè)ChunkKillChunk15000個(gè)Chunk，600GBGFS調(diào)度決策提供修正空間，91個(gè)（Chunk40%，每個(gè)克隆操作最多允6.25MB/s（50mbpsChunk23.2440MB/s。KillChunkChunk16000Chunk，共2分鐘內(nèi)恢復(fù)到至少有兩個(gè)副本；現(xiàn)在集群被帶入到另外一個(gè)狀態(tài)，在這個(gè)狀態(tài)下，系統(tǒng)可以容忍另Chunk服務(wù)器失效而不丟失數(shù)據(jù)。工作負(fù)荷分析(WorkloadGFS6.2節(jié)中的類似，但是不完全相同。集群X用于研究和開發(fā)，集群Y用于生產(chǎn)數(shù)據(jù)處理。GFS文件系統(tǒng)產(chǎn)生的全部工作負(fù)載。它們不包含那些為了實(shí)現(xiàn)客戶端請求而在服務(wù)器間交互的請求，也不包GFS內(nèi)部的后臺活動相關(guān)的請求，比如前向轉(zhuǎn)發(fā)的寫操作，或者重新負(fù)載均衡等操作。GFSRPCIO操作的統(tǒng)計(jì)信息。例如，GFS客RPCRPC請求推導(dǎo)出原始的讀應(yīng)該避免從我們的工作負(fù)荷數(shù)據(jù)中過度的歸納出普遍的結(jié)論29Google完全控制著GFS和使用GFS28原文：Sinceouraccesspatternsarehighlystylized,weexpectanyerrortobeinthe29Chunk表4顯示了操作按涉及的數(shù)據(jù)量大小的分布情況。讀取操作按操作涉及的數(shù)據(jù)量大小呈現(xiàn)了雙峰分布。小的讀取操作（64KB）一般是由查找操作的客戶端發(fā)起的，目的在于從巨大的文件中查找小塊的數(shù)據(jù)。大的讀取操作（512KB）一般是從頭到尾順序的讀取整個(gè)文件。Y上，有相當(dāng)數(shù)量的讀操作沒有返回任何的數(shù)據(jù)。在我們的應(yīng)用中，尤其是在生產(chǎn)系統(tǒng)中，經(jīng)常X通常用于短暫的數(shù)據(jù)分析任務(wù)，而不是長時(shí)間運(yùn)行的分布式應(yīng)用，因此，集群X很少出現(xiàn)這種情況。寫操作按數(shù)據(jù)量大小也同樣呈現(xiàn)為雙峰分布。大的寫操作（256KB）Writer使用了緩存（64KB）的數(shù)據(jù)量(alex注：即匯集多次小的寫入操作，當(dāng)數(shù)據(jù)量達(dá)到一個(gè)閾值，一次寫入)，之后批量Y中大的記錄追加操作所占比例比集群X多的多，這是因?yàn)榧篩用于我們的生產(chǎn)系統(tǒng)，針對GFS做了更全面的調(diào)優(yōu)。表5顯示了按操作涉及的數(shù)據(jù)量的大小統(tǒng)計(jì)出來的總數(shù)據(jù)傳輸量。在所有的操作中，大的操作（超過Seek的工作負(fù)荷而導(dǎo)致的。vs.X，記錄追加操作和普通寫操作的比例按照字節(jié)108:1X，buffer的X.001.003。Y.05Master（FindLocationLocker重新寫入的模式打開時(shí)，隱式的被刪除了（類似UNIXopen函數(shù)中的“w”模式。namespaceY的這類請求要多一在建造和部署GFS研究和開發(fā)任務(wù)的支持。我們開始增加一些小的功能，比如權(quán)限和配額，到了現(xiàn)在，GFS已經(jīng)初步支持了這Linux2.2fsync()的效率問題。它的效率與文件Linux相關(guān)的問題是單個(gè)讀寫鎖的問題，也就是說，在某一個(gè)地址空間的任意一個(gè)線程都必須pagein（讀鎖）holdmmap()調(diào)用（寫鎖）的時(shí)候改寫地址空間。我們發(fā)現(xiàn)即pread()mmap()copy動作來解決這個(gè)問題。和其它的大型分布式文件系統(tǒng)，比如AFS[5]類似，GFS提供了一個(gè)與位置無關(guān)的名字空間，這使得數(shù)據(jù)可以為了負(fù)載均衡或者災(zāi)難冗余等目的在不同位置透明的遷移。不同于AFS的是，GFS把文件分布存儲到不Xfs[1]Swift[3]，這是為了提高整體性能以及災(zāi)難冗余的能力。xFSSwift占用更多的裸存儲空間(alex注：Rawstorage，裸盤的空間)。Cache機(jī)制。我們主要的工作在單個(gè)應(yīng)用程序執(zhí)行的時(shí)候幾乎不會重復(fù)讀取數(shù)據(jù)，因?yàn)樗鼈兊墓ぷ鞣绞組asterHarp[7]primary-copy方案，從而提供比我們現(xiàn)在的方案更嚴(yán)格的一致性保證。Lustre[8]在如何在有大量客戶端時(shí)保障系統(tǒng)整體性能遇到的問題。不過，我們通過只關(guān)注我們的應(yīng)用程序的需求，而不是提供一個(gè)兼容POSIX的文件系統(tǒng)，從而達(dá)到了簡化問GFS很類似NASD架構(gòu)[4]。NASDGFSChunk服式，而不是分配變長的對象存儲空間。此外，GFS實(shí)現(xiàn)了諸如重新負(fù)載均衡、復(fù)制、恢復(fù)機(jī)制等等在生產(chǎn)環(huán)不同于與Minnesota’sGFS和NASDModel30。我們只關(guān)注用普通的設(shè)備來解生產(chǎn)者并發(fā)追加記錄的持久化的文件的方式實(shí)現(xiàn)。Riverm-到-n的分布式隊(duì)列，但是缺少由持久化Google文件系統(tǒng)展示了一個(gè)使用普通硬件支持大規(guī)模數(shù)據(jù)處理的系統(tǒng)的特質(zhì)。雖然一些設(shè)計(jì)要點(diǎn)都是針我們系統(tǒng)通過持續(xù)監(jiān)控，復(fù)制關(guān)鍵數(shù)據(jù)，快速和自動恢復(fù)提供災(zāi)難冗余。Chunk復(fù)制使得我們可以對Chunk服務(wù)器的失效進(jìn)行容錯(cuò)。高頻率的組件失效要求系統(tǒng)具備在線修復(fù)機(jī)制，能夠周期性的、透明的修復(fù)ChecksumIDE子系統(tǒng)級別30ModelmodelGoogleGoogleFileSystem1.0GFSGoogle內(nèi)部，無論是作為研究和開發(fā)的存儲平臺，還是作為GoogleBigtable中文版目錄TOC\o"1-3"\h\u261971 1175822 127988 212833 2130563.1 330973.2 3207523.3 4258814 4177045BigTable 5168106 7252186.1 7142226.2 8249946.3 10143226