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)是通過簡(jiǎn)單的接口來實(shí)現(xiàn)自動(dòng)的并行化和大規(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ù)的輸入輸出，用戶在自己的代碼中對(duì)字符串進(jìn)行適當(dāng)這里還有一些有趣的簡(jiǎn)單例子，可以很容易的使用MapReduce分布式的Grep：Map函數(shù)輸出匹配某個(gè)模式的一行，Reduce函數(shù)是一個(gè)恒等函數(shù)，即把中間數(shù)據(jù)復(fù)制到計(jì)算URL訪問頻率：Map函數(shù)處理日志中web頁面請(qǐng)求的記錄，然后輸出(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)用來管理存儲(chǔ)在這些磁盤上的數(shù)據(jù)。文件系（taskMapM個(gè)數(shù)據(jù)片段的集合，Map調(diào)用被分布到多臺(tái)機(jī)器上執(zhí)行。輸Map調(diào)用產(chǎn)生的中間key值分成RR，Reduce系列動(dòng)作（1中的序號(hào)一一對(duì)應(yīng)：用戶程序首先調(diào)用的MapReduce庫將輸入文件分成M給一個(gè)空閑的worker。mapworkerkey/value緩存中的key/valuepair通過分區(qū)函數(shù)分成R個(gè)區(qū)域，之后周期性的寫入到本地磁盤上。緩存的key/valuepair在本地磁盤上的存儲(chǔ)位置將被回傳給mastermaster負(fù)責(zé)把這些存儲(chǔ)位置再傳送給Reduceworker。ReduceworkermasterRPC從Mapworker所在Reduceworkerkey進(jìn)行排序keykeyReduce任務(wù)上，keyvalue值的集合傳遞給用戶自定義的Reduce函數(shù)。Reduce函數(shù)的輸出被追MapReduce任務(wù)都完成之后，masterMapReduce在成功完成任務(wù)之后，MapReduce的輸出存放在R個(gè)輸出文件中（對(duì)應(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）開始啟動(dòng)另一個(gè)mastermaster進(jìn)程，master失效后再恢復(fù)是比較麻煩的，因此我們現(xiàn)在的實(shí)現(xiàn)是（alex注：原文為”semanticsinthepresenceoffailuresMapReduce操作是輸入確定性函數(shù)（即相同的輸入產(chǎn)生相同的輸出）時(shí)，我們的分布我們依賴對(duì)Map和Reduce任務(wù)的輸出是原子提交的來完成這個(gè)特性。每個(gè)工作中的任務(wù)把它的輸出寫ReduceMapR個(gè)這樣的文件（一則，master將這R個(gè)文件的名字記錄在數(shù)據(jù)結(jié)構(gòu)里。一個(gè)Reduce任務(wù)在多臺(tái)機(jī)器上執(zhí)行，針對(duì)同一個(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管理)存儲(chǔ)在集群中機(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ù)最終都會(huì)生成一個(gè)獨(dú)立的輸出文件。實(shí)際使M16M64M的輸入數(shù)據(jù)（這樣，上面描寫的輸入數(shù)據(jù)本地存儲(chǔ)優(yōu)化策略才最有效Rworker機(jī)器數(shù)量MapReduce長(zhǎng)的時(shí)間才完成最后幾個(gè)Map或ReduceMapReduce的一個(gè)問題是由于機(jī)器的初始化代碼有bug，導(dǎo)致關(guān)閉了的處理器的緩存：在這些機(jī)器上執(zhí)行任務(wù)的性能和5.344%的時(shí)間完成MapReduce函數(shù)提供的基本功能已經(jīng)能夠滿足大部分的計(jì)算需要，我們還是發(fā)掘出了一MapReduce的使用者通常會(huì)指定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ù)字。我們?cè)试S用戶指定一個(gè)可選Combiner函數(shù)在每臺(tái)執(zhí)行Map任務(wù)的機(jī)器上都會(huì)被執(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)行排序來存儲(chǔ)key/valuepair的序列。每種輸入類型的實(shí)現(xiàn)都必須能夠把輸入數(shù)據(jù)分割成數(shù)據(jù)片段，該數(shù)據(jù)片段能夠由單Map任務(wù)來進(jìn)行后續(xù)處理(例如，文本模式的范圍分割必須確保僅僅在每行的邊界進(jìn)行范圍分割)。雖然個(gè)簡(jiǎn)單的Reader接口實(shí)現(xiàn)就能夠支持一個(gè)新的輸入類型。ReaderReader，Reader。在某些情況下，MapReduce的使用者發(fā)現(xiàn)，如果在Map和/Reduce操作過程中增加輔助的輸出文件會(huì)rename重新命名這個(gè)臨時(shí)文件。3bg導(dǎo)致Mp或者ReuceahMReuce操作ug后再次執(zhí)行MpRducebugbugapeducea，errorMapReduce操作之前，MapReduce庫通過全局變量保存記錄序號(hào)。如果用戶程序觸發(fā)了一個(gè)系看到在處理某條特定記錄不止失敗一次時(shí)，master就標(biāo)志著條記錄需要被跳過，并且在下次重新執(zhí)行相關(guān)的MapReduce任務(wù)的時(shí)候跳過這條記錄。MapReducebug是非常困難的，因?yàn)閷?shí)際執(zhí)行操作時(shí)不但是分布在系統(tǒng)中執(zhí)行的，而且為了簡(jiǎn)化調(diào)試、profileMapReduce庫的本地實(shí)現(xiàn)版本，通過使用本地版本的用本地調(diào)試和測(cè)試工具（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庫自動(dòng)維持的，比如已經(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秒。這包括了大約一分鐘的初始啟動(dòng)階段。初始啟動(dòng)階段消耗的時(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ū)情況。通常對(duì)于排序程序來說，我們會(huì)MapReduce操作用于采樣key值的分布情況，通過采樣的數(shù)據(jù)來計(jì)算對(duì)最終排序處理的分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)完成，包括了初始啟動(dòng)時(shí)間（5%的時(shí)間。了輸入數(shù)據(jù)本地優(yōu)化、worker機(jī)器之間的動(dòng)態(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è)增長(zhǎng)到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]提供了更高級(jí)別的并行處理抽象，可以更容易寫出并行處理的程序。MapReduce和這些系統(tǒng)的關(guān)鍵不同之處在于，MapReduce利用限制性編程模式實(shí)現(xiàn)了用activedisks[12,15]activedisks中，計(jì)算任務(wù)是盡量推送到數(shù)據(jù)存儲(chǔ)的節(jié)點(diǎn)處理6IO子系統(tǒng)的吞吐量。我們?cè)趻燧d幾個(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在本地對(duì)數(shù)據(jù)進(jìn)行排序（盡可能在內(nèi)存中排序。當(dāng)然，NOW-SortMapReduce函數(shù)的機(jī)會(huì)，因此不具備MapReduce庫廣泛的實(shí)用性。River[2]提供了一個(gè)編程模型：處理進(jìn)程通過分布式隊(duì)列傳送數(shù)據(jù)的方式進(jìn)行互相通訊。和MapReduce類似，River系統(tǒng)嘗試在不對(duì)等的硬件環(huán)境下，或者在系統(tǒng)顛簸的情況下也能提供近似平均的性能。River是通過精心調(diào)度硬盤和網(wǎng)絡(luò)的通訊來平衡任務(wù)的完成時(shí)間。MapReduce庫采用了其它的方法。通過對(duì)編程模型56、9、136TACC[7]MapReduce一樣，它也依靠重新執(zhí)行機(jī)制來MapReduce編程模型在Google內(nèi)部成功應(yīng)用于多個(gè)領(lǐng)域。我們把這種成功歸結(jié)為幾個(gè)方面：首先，由于MapReduce簡(jiǎn)單的解決。比如，MapReduceGoogle的網(wǎng)絡(luò)搜索服務(wù)所需要的數(shù)據(jù)、用來MapReduce。這個(gè)實(shí)現(xiàn)使得有效利用這些豐富的計(jì)算資源變得非常簡(jiǎn)單，因此也適合用來解決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-