谷歌大規(guī)模排序?qū)嶒?yàn)的歷史翻譯

.word范文/blog/big-data/2016/02/history-of-massive-scale-sorting-experiments-at-google作者：MarianDvorsky，軟件工程師，谷歌云平臺(tái)Thursday,February18,2016星期四，2016年2月18日We’vetestedMapReducebysortinglargeamountsofrandomdataeversincewecreatedthetool.Welikesorting,becauseit’seasytogenerateanarbitraryamountofdata,andit’seasytovalidatethattheoutputiscorrect.我們發(fā)明了MapReduce這個(gè)工具之后，對(duì)它進(jìn)行了大規(guī)模隨機(jī)數(shù)據(jù)的排序測(cè)試。我們喜歡排序，因?yàn)楹苋菀桩a(chǎn)生任意規(guī)模的數(shù)據(jù)，也很容易驗(yàn)證排序的輸出是否正確。Eventhe

originalMapReducepaper

reportsaTeraSortresult.Engineersrun1TBor10TBsortsasregressiontestsonaregularbasis,becauseobscurebugstendtobemorevisibleonalargescale.However,therealfunbeginswhenweincreasethescaleevenfurther.InthispostI’lltalkaboutourexperiencewithsomepetabyte-scalesortingexperimentswedidafewyearsago,includingwhatwebelievetobethelargestMapReducejobever:a50PBsort.我們最初的MapReduce論文就報(bào)道了一個(gè)TeraSort排序的結(jié)果。工程師在一定的規(guī)則基礎(chǔ)上對(duì)1TB或10TB的數(shù)據(jù)進(jìn)行排序測(cè)試，因?yàn)榧?xì)小的錯(cuò)誤更容易在大規(guī)模數(shù)據(jù)運(yùn)行的時(shí)候被發(fā)現(xiàn)。然而，真正有趣的事情在我們進(jìn)一步擴(kuò)大數(shù)據(jù)規(guī)模后才開(kāi)始。在這篇文章中，我將講一講我們?cè)趲啄曛八龅囊恍㏄B級(jí)別的排序?qū)嶒?yàn)，包括我們認(rèn)為是目前最大的MapReduce工作：50PB排序。Thesedays,GraySortisthelargescalesortingbenchmarkofchoice.InGraySort,youmustsortatleast100TBofdata(as100-byterecordswiththefirst10bytesbeingthekey),lexicographically,asfastaspossible.Thesite

tracksofficialwinnersforthisbenchmark.Weneverenteredtheofficialcompetition.那時(shí)候，GraySort是大型排序基準(zhǔn)的選擇。在GraySort基準(zhǔn)下，你必須按照盡快對(duì)至少100TB的數(shù)據(jù)(每100B數(shù)據(jù)用最前面的10B數(shù)據(jù)作為鍵)進(jìn)行字典序排序。S這個(gè)網(wǎng)站追蹤報(bào)道了這個(gè)基準(zhǔn)的官方優(yōu)勝者。而我們從未正式參加過(guò)比賽。MapReducehappenstobeagoodfitforsolvingthisproblem,becausethewayitimplementsreduceisbysortingthekeys.Withtheappropriate(lexicographic)shardingfunction,theoutputofMapReduceisasequenceoffilescomprisingthefinalsorteddataset.MapReduce是解決這個(gè)問(wèn)題的一個(gè)不錯(cuò)選擇，因?yàn)樗鼘?shí)現(xiàn)減少(優(yōu)化)的方法是對(duì)通過(guò)對(duì)鍵進(jìn)行排序。結(jié)合適當(dāng)?shù)?字典)分區(qū)功能，MapReduce的輸出是一組包含了最終排序數(shù)據(jù)的文件序列。Onceinawhile,whenanewclusterinadatacentercameup(typicallyforusebythesearchindexingteam),weintheMapReduceteamgottheopportunitytoplayforafewweeksbeforetherealworkloadmovedin.Thisiswhenwehadachanceto“burnin”thecluster,stretchthelimitsofthehardware,destroysomeharddrives,playwithsomereallyexpensiveequipment,learnalotaboutsystemperformance,and,win(unofficially)thesortingbenchmark.偶爾，當(dāng)一個(gè)新的cluster在一個(gè)數(shù)據(jù)中心出現(xiàn)時(shí)(通常被搜索索引團(tuán)隊(duì)所使用)，我們MapReduce團(tuán)隊(duì)就得到一個(gè)機(jī)會(huì)在真正的工作到來(lái)之前運(yùn)行若干星期。這是我們有機(jī)會(huì)去“燃燒”這個(gè)cluster，延伸硬件的限制，放棄一些硬盤(pán)，而使用一些真正昂貴的設(shè)備，了解系統(tǒng)的性能，并贏得(非正式)排序基準(zhǔn)。Figure1:GooglePetasortrecordsovertime.圖1：谷歌Petasort時(shí)間記錄20072007(1PB,12.13hours,1.37TB/min,2.9MB/s/worker)(1PB,12.13小時(shí)，1.37TB/min，2.9MB/s/worker)WeranourveryfirstPetasortin2007.Atthattime,weweremostlyhappythatwegotittofinishatall,althoughtherearesomedoubtsthattheoutputwascorrect(wedidn’tverifythecorrectnesstoknowforsure).Thejobwouldn’tfinishunlesswedisabledthemechanismwhichchecksthattheoutputofamapshardanditsbackuparethesame.WesuspectthatthiswasalimitationofGFS(GoogleFileSystem),whichweusedforstoringtheinputandoutput.GFSdidn’thaveenoughchecksumprotection,andsometimesreturnedcorrupteddata.Unfortunately,thetextformatusedforthebenchmarkdoesn’thaveanychecksumsembeddedforMapReducetonotice(thetypicaluseofMapReduceatGoogleusesfileformatswithembeddedchecksums).2007年我們運(yùn)行了第一個(gè)Petasort。在那個(gè)時(shí)候，我們最高興的是這個(gè)程序最終完成了排序，盡管我們對(duì)排序的結(jié)果有一些疑問(wèn)(我們沒(méi)有驗(yàn)證排序結(jié)果的正確性)。如果不是我們?nèi)∠艘欢ㄒ骋粋€(gè)輸出分區(qū)與備份完全相同的驗(yàn)證機(jī)制，這個(gè)排序便不會(huì)結(jié)束。我們懷疑這是因?yàn)槲覀冇脕?lái)存儲(chǔ)輸入和輸出的文件是GFS格式(谷歌文件系統(tǒng))的緣故。GFS文件沒(méi)有足夠校驗(yàn)和保護(hù)，有時(shí)會(huì)返回被污染的數(shù)據(jù)。不幸的是，這個(gè)基準(zhǔn)所使用的文件格式?jīng)]有任何嵌入式校驗(yàn)供MapReduce使用(谷歌使用的典型MapReduce的文件是有嵌入式校驗(yàn)的)。20082008(1PB,6.03hours,2.76TB/min,11.5MB/s/worker)1PB,6.03小時(shí)，2.76TB/min，11.5MB/s/worker2008wasthefirsttimewefocusedontuning.Wespentseveraldaystuningthenumberofshards,variousbuffersizes,prefetching/write-aheadstrategies,pagecacheusage,etc.We

bloggedabouttheresulthere.Thebottleneckendedupbeingwritingthethree-wayreplicatedoutputGFS,whichwasthestandardweusedatGoogleatthetime.Anythinglesswouldcreateahighriskofdataloss.2008年我們第一次把注意力集中于調(diào)整。我們花費(fèi)幾天的時(shí)間來(lái)調(diào)整分區(qū)的數(shù)量，緩沖區(qū)的大小，預(yù)取/預(yù)寫(xiě)策略，頁(yè)面緩存使用等。我們?cè)?jīng)在這個(gè)博客里記錄過(guò)結(jié)果。最終的瓶頸是寫(xiě)三路復(fù)制的GFS輸出文件，這是當(dāng)時(shí)我們?cè)诠雀枋褂玫臉?biāo)準(zhǔn)。任何事情的缺失都會(huì)造成數(shù)據(jù)丟失的高風(fēng)險(xiǎn)。20102010(1PB,2.95hours,5.65TB/min,11.8MB/s/worker)1PB,2.95小時(shí),5.65TB/min,11.8MB/s/workerForthistest,weusedthenewversionoftheGraySortbenchmarkthatusesincompressibledata.Inthepreviousyears,whilewewerereading/writing1PBfrom/toGFS,theamountofdataactuallyshuffledwasonlyabout300TB,becausetheASCIIformatusedthepreviousyearscompresseswell.在這個(gè)測(cè)試中，我們使用了一種新的不可壓縮的GraySort基準(zhǔn)的數(shù)據(jù)版本。在前幾年，當(dāng)我們讀/寫(xiě)1PBGFS文件時(shí)，實(shí)際上混排的數(shù)據(jù)只有300TB，因?yàn)榍皫啄甑臄?shù)據(jù)是用ASCII格式壓縮好的。ThiswasalsotheyearofColossus,thenextgenerationdistributedstoragesystematGoogle,thesuccessortoGFS.WenolongerhadthecorruptionissuesweencounteredbeforewithGFS.WealsousedReed-Solomonencoding(anewColossusfeature)foroutputthatallowedustoreducethetotalamountofdatawrittenfrom3petabytes(forthree-wayreplication)toabout1.6petabytes.Forthefirsttime,wealsovalidatedthattheoutputwascorrect.這也是谷歌使用Colossus的一年，新一代的分布式存儲(chǔ)方式取代了GFS。我們不再有我們遇到過(guò)的GFS文件污染的問(wèn)題。我們還使用了Reed-Solomon編碼(Colossus新特征)作為輸出，這種編碼允許我們減少數(shù)據(jù)的總量，三路復(fù)制數(shù)據(jù)從3字節(jié)減少到了大約1.6字節(jié)。這也是第一次，我們驗(yàn)證了輸出的結(jié)果是正確的。Toreducetheimpactofstragglers,weusedadynamicshardingtechniquecalledreducesubsharding.Thisistheprecursortofullydynamicshardingusedin

Dataflow.為了減少人的影響，我們采用了一種叫做減少殘余碎片的動(dòng)態(tài)分區(qū)技術(shù)。這也是數(shù)據(jù)流采用全動(dòng)態(tài)分區(qū)的先兆。20112011(1PB,0.55hours,30.3TB/min,63.1MB/s/worker)1PB,0.55小時(shí),30.3TB/min,63.1MB/s/workerThisyearweenjoyedfasternetworkingandstartedtopaymoreattentiontoper-machineefficiency,particularlyinI/O.WemadesurethatallourdiskI/Osoperationswereperformedinlarge2MBblocksversussometimesassmallas64kBblocks.WeusedSSDsforpartofthedata.ThatgotusthefirstPetasortinunderanhour—33minutes,tobeexact—andwe

blogged

aboutithere.Wegotreallyclose(within2x)towhatthehardwarewascapableofgivenMapReduce’sarchitecture:input/outputonadistributedstorage,persistingintermediatedatatodiskforfaulttolerance(andfaulttolerancewasimportant,becauseitwouldbecommonthatsomedisksorevenwholemachinesfailduringanexperimentatthisscale).這一年，我們有了更快的網(wǎng)絡(luò)，并開(kāi)始更加注重每臺(tái)機(jī)器的效率，特別是I/O的效率。我們確保我們所有的I/O操作都在大于2MB的空間內(nèi)進(jìn)行，而以前有時(shí)候會(huì)小到64kB。對(duì)于部分?jǐn)?shù)據(jù)我們使用固態(tài)硬盤(pán)。這使得我們第一個(gè)在一小時(shí)之內(nèi)完成Petasort——更確切地說(shuō)是33分鐘——我之前在博客中有講到。我們真的非常接近(兩倍)給定MapReduce’s體系結(jié)構(gòu)的硬件極限：輸入/輸出分布式存儲(chǔ)，為容錯(cuò)保留中間數(shù)據(jù)(容錯(cuò)是非常重要的，因?yàn)樗枪灿械模@個(gè)試驗(yàn)中一些磁盤(pán)甚至整個(gè)機(jī)器都會(huì)引起這個(gè)規(guī)模的失敗)。Wealsoscaledhigher,andran10PBin6hours27minutes(26TB/min).我們還運(yùn)行了更大的數(shù)據(jù)，10PB數(shù)據(jù)在6小時(shí)27分鐘(26TB/min)。20122012(50PB,23hours,36.2TB/min,50MB/s/worker)50PB,23小時(shí),36.2TB/min,50MB/s/workerForthistest,weshiftedourattentiontorunningatalargerscale.WiththelargestclusteratGoogleunderourcontrol,weranwhatwebelievetobethelargestMapReducejobeverintermsofamountofdatashuffled.Unfortunately,theclusterdidn’thaveenoughdiskspacefora100PBsort,sowelimitedoursortto“only”50PB.Weranitasingletimeanddidsowithoutspecifictuningandweusedthesettingsfromourprevious10PBexperiment.Itfinishedin23hours,5minutes.對(duì)于這個(gè)測(cè)試，我們將注意力轉(zhuǎn)移到更大規(guī)模的數(shù)據(jù)。谷歌我們控制的最大cluster之下，我們運(yùn)行了我們認(rèn)為是最大MapReduce工作，甚至在數(shù)據(jù)混排規(guī)模方面也是最大。不幸的是，這個(gè)cluster沒(méi)有足夠的磁盤(pán)空間來(lái)排序100PB的數(shù)據(jù)，因而限制我們的排序“只有”50PB。我們只運(yùn)行了一次，并沒(méi)有進(jìn)行專(zhuān)門(mén)的調(diào)整，只是使用了我們之前10PB實(shí)驗(yàn)時(shí)候的設(shè)置。這次實(shí)驗(yàn)在23小時(shí)5分鐘之后運(yùn)行結(jié)束。Notethatthissortwas500timeslargerthantheGraySortlarge-scalerequirementandtwiceasfastinthroughputasthecurrent2015officialGraySortwinner.需要注意的是，這次排序的規(guī)模是GraySort大規(guī)模的要求的500倍，計(jì)算速率是2015年GraySort官方優(yōu)勝者的兩倍。Lessonslearned經(jīng)驗(yàn)總結(jié)Theseexperimentstaughtusalotaboutthechallengesofrunningatthescaleof10,000machines,andabouthowtotunetorunatspeedsclosetowhatthehardwareiscapableof.這些實(shí)驗(yàn)教會(huì)了我們很多關(guān)于運(yùn)行超過(guò)10000臺(tái)機(jī)器的挑戰(zhàn)，以及如何調(diào)整使得運(yùn)行速度接近于硬件的極限。Whilethesesortingexperimentsarefun,theyhaveseveraldrawbacks:雖然這些排序?qū)嶒?yàn)室是有趣的，它們?nèi)匀挥袔讉€(gè)缺點(diǎn)：1.Nobodyreallywantsahugegloballysortedoutput.Wehaven’tfoundasingleusecasefortheproblemasstated.1.沒(méi)有人真的想要一個(gè)巨大的全球范圍內(nèi)的排序輸出。我們還沒(méi)有找到解決這個(gè)問(wèn)題的單一使用方案。T