谷歌大规模排序实验的历史翻译

..ts-at-google作者：MarianDvorsky,软件工程师,谷歌云平台Thursday,February18,2016星期四,2016年2月18日We’vetestedMapReducebysortinglargeamountsofrandomdataeversincewecreatedthetool.Welikesorting,becauseit’seasytogenerateanarbitraryamountofdata,andit’seasytovalidatethattheoutputiscorrect.我们发明了MapReduce这个工具之后,对它进行了大规模随机数据的排序测试。我们喜欢排序,因为很容易产生任意规模的数据,也很容易验证排序的输出是否正确。Eventhe

originalMapReducepaper

reportsaTeraSortresult.Engineersrun1TBor10TBsortsasregressiontestsonaregularbasis,becauseobscurebugstendtobemorevisibleonalargescale.However,therealfunbeginswhenweincreasethescaleevenfurther.InthispostI’lltalkaboutourexperiencewithsomepetabyte-scalesortingexperimentswedidafewyearsago,includingwhatwebelievetobethelargestMapReducejobever:a50PBsort.我们最初的MapReduce论文就报道了一个TeraSort排序的结果。工程师在一定的规则基础上对1TB或10TB的数据进行排序测试,因为细小的错误更容易在大规模数据运行的时候被发现。然而,真正有趣的事情在我们进一步扩大数据规模后才开始。在这篇文章中,我将讲一讲我们在几年之前所做的一些PB级别的排序实验,包括我们认为是目前最大的MapReduce工作：50PB排序。Thesedays,GraySortisthelargescalesortingbenchmarkofchoice.InGraySort,youmustsortatleast100TBofdata<as100-byterecordswiththefirst10bytesbeingthekey>,lexicographically,asfastaspossible.Thesite

tracksofficialwinnersforthisbenchmark.Weneverenteredtheofficialcompetition.那时候,GraySort是大型排序基准的选择。在GraySort基准下,你必须按照尽快对至少100TB的数据<每100B数据用最前面的10B数据作为键>进行字典序排序。S这个网站追踪报道了这个基准的官方优胜者。而我们从未正式参加过比赛。MapReducehappenstobeagoodfitforsolvingthisproblem,becausethewayitimplementsreduceisbysortingthekeys.Withtheappropriate<lexicographic>shardingfunction,theoutputofMapReduceisasequenceoffilescomprisingthefinalsorteddataset.MapReduce是解决这个问题的一个不错选择,因为它实现减少<优化>的方法是对通过对键进行排序。结合适当的<字典>分区功能,MapReduce的输出是一组包含了最终排序数据的文件序列。Onceinawhile,whenanewclusterinadatacentercameup<typicallyforusebythesearchindexingteam>,weintheMapReduceteamgottheopportunitytoplayforafewweeksbeforetherealworkloadmovedin.Thisiswhenwehadachanceto"burnin"thecluster,stretchthelimitsofthehardware,destroysomeharddrives,playwithsomereallyexpensiveequipment,learnalotaboutsystemperformance,and,win<unofficially>thesortingbenchmark.偶尔,当一个新的cluster在一个数据中心出现时<通常被搜索索引团队所使用>,我们MapReduce团队就得到一个机会在真正的工作到来之前运行若干星期。这是我们有机会去"燃烧"这个cluster,延伸硬件的限制,放弃一些硬盘,而使用一些真正昂贵的设备,了解系统的性能,并赢得<非正式>排序基准。Figure1:GooglePetasortrecordsovertime.图1：谷歌Petasort时间记录20072007<1PB,12.13hours,1.37TB/min,2.9MB/s/worker><1PB,12.13小时,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>.20XX我们运行了第一个Petasort。在那个时候,我们最高兴的是这个程序最终完成了排序,尽管我们对排序的结果有一些疑问<我们没有验证排序结果的正确性>。如果不是我们取消了一定要某一个输出分区与备份完全相同的验证机制,这个排序便不会结束。我们怀疑这是因为我们用来存储输入和输出的文件是GFS格式<谷歌文件系统>的缘故。GFS文件没有足够校验和保护,有时会返回被污染的数据。不幸的是,这个基准所使用的文件格式没有任何嵌入式校验供MapReduce使用<谷歌使用的典型MapReduce的文件是有嵌入式校验的>。20082008<1PB,6.03hours,2.76TB/min,11.5MB/s/worker>1PB,6.03小时,2.76TB/min,11.5MB/s/worker2008wasthefirsttimewefocusedontuning.Wespentseveraldaystuningthenumberofshards,variousbuffersizes,prefetching/write-aheadstrategies,pagecacheusage,etc.We

bloggedabouttheresulthere.Thebottleneckendedupbeingwritingthethree-wayreplicatedoutputGFS,whichwasthestandardweusedatGoogleatthetime.Anythinglesswouldcreateahighriskofdataloss.20XX我们第一次把注意力集中于调整。我们花费几天的时间来调整分区的数量,缓冲区的大小,预取/预写策略,页面缓存使用等。我们曾经在这个博客里记录过结果。最终的瓶颈是写三路复制的GFS输出文件,这是当时我们在谷歌使用的标准。任何事情的缺失都会造成数据丢失的高风险。20102010<1PB,2.95hours,5.65TB/min,11.8MB/s/worker>1PB,2.95小时,5.65TB/min,11.8MB/s/workerForthistest,weusedthenewversionoftheGraySortbenchmarkthatusesincompressibledata.Inthepreviousyears,whilewewerereading/writing1PBfrom/toGFS,theamountofdataactuallyshuffledwasonlyabout300TB,becausetheASCIIformatusedthepreviousyearscompresseswell.在这个测试中,我们使用了一种新的不可压缩的GraySort基准的数据版本。在前几年,当我们读/写1PBGFS文件时,实际上混排的数据只有300TB,因为前几年的数据是用ASCII格式压缩好的。ThiswasalsotheyearofColossus,thenextgenerationdistributedstoragesystematGoogle,thesuccessortoGFS.WenolongerhadthecorruptionissuesweencounteredbeforewithGFS.WealsousedReed-Solomonencoding<anewColossusfeature>foroutputthatallowedustoreducethetotalamountofdatawrittenfrom3petabytes<forthree-wayreplication>toabout1.6petabytes.Forthefirsttime,wealsovalidatedthattheoutputwascorrect.这也是谷歌使用Colossus的一年,新一代的分布式存储方式取代了GFS。我们不再有我们遇到过的GFS文件污染的问题。我们还使用了Reed-Solomon编码<Colossus新特征>作为输出,这种编码允许我们减少数据的总量,三路复制数据从3字节减少到了大约1.6字节。这也是第一次,我们验证了输出的结果是正确的。Toreducetheimpactofstragglers,weusedadynamicshardingtechniquecalledreducesubsharding.Thisistheprecursortofullydynamicshardingusedin

Dataflow.为了减少人的影响,我们采用了一种叫做减少残余碎片的动态分区技术。这也是数据流采用全动态分区的先兆。20112011<1PB,0.55hours,30.3TB/min,63.1MB/s/worker>1PB,0.55小时,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>.这一年,我们有了更快的网络,并开始更加注重每台机器的效率,特别是I/O的效率。我们确保我们所有的I/O操作都在大于2MB的空间内进行,而以前有时候会小到64kB。对于部分数据我们使用固态硬盘。这使得我们第一个在一小时之内完成Petasort——更确切地说是33分钟——我之前在博客中有讲到。我们真的非常接近<两倍>给定MapReduce’s体系结构的硬件极限：输入/输出分布式存储,为容错保留中间数据<容错是非常重要的,因为它是共有的,而这个试验中一些磁盘甚至整个机器都会引起这个规模的失败>。Wealsoscaledhigher,andran10PBin6hours27minutes<26TB/min>.我们还运行了更大的数据,10PB数据在6小时27分钟<26TB/min>。20122012<50PB,23hours,36.2TB/min,50MB/s/worker>50PB,23小时,36.2TB/min,50MB/s/workerForthistest,weshiftedourattentiontorunningatalargerscale.WiththelargestclusteratGoogleunderourcontrol,weranwhatwebelievetobethelargestMapReducejobeverintermsofamountofdatashuffled.Unfortunately,theclusterdidn’thaveenoughdiskspacefora100PBsort,sowelimitedoursortto"only"50PB.Weranitasingletimeanddidsowithoutspecifictuningandweusedthesettingsfromourprevious10PBexperiment.Itfinishedin23hours,5minutes.对于这个测试,我们将注意力转移到更大规模的数据。谷歌我们控制的最大cluster之下,我们运行了我们认为是最大MapReduce工作,甚至在数据混排规模方面也是最大。不幸的是,这个cluster没有足够的磁盘空间来排序100PB的数据,因而限制我们的排序"只有"50PB。我们只运行了一次,并没有进行专门的调整,只是使用了我们之前10PB实验时候的设置。这次实验在23小时5分钟之后运行结束。Notethatthissortwas500timeslargerthantheGraySortlarge-scalerequirementandtwiceasfastinthroughputasthecurrent2015officialGraySortwinner.需要注意的是,这次排序的规模是GraySort大规模的要求的500倍,计算速率是2015年GraySort官方优胜者的两倍。Lessonslearned经验总结Theseexperimentstaughtusalotaboutthechallengesofrunningatthescaleof10,000machines,andabouthowtotunetorunatspeedsclosetowhatthehardwareiscapableof.这些实验教会了我们很多关于运行超过10000台机器的挑战,以及如何调整使得运行速度接近于硬件的极限。Whilethesesortingexperimentsarefun,theyhaveseveraldrawbacks:虽然这些排序实验室是有趣的,它们仍然有几个缺点：1.Nobodyreallywantsahugegloballysortedoutput.Wehaven’tfoundasingleusecasefortheproblemasstated.1.没有人真的想要一个巨大的全球范围内的排序输出。我们还没有找到解决这个问题的单一使用方案。Theys