火龙果软件-MapReduce课件

MapReduce课件 Outline MapReduceoverviewDiscussionQuestionsMapReduce Motivation 200 processors200 terabytedatabase1010totalclockcycles0 1secondresponsetime5 averageadvertisingrevenue From www cs cmu edu bryant presentations DISC FCRC07 ppt Motivation LargeScaleDataProcessing Wanttoprocesslotsofdata 1TB Wanttoparallelizeacrosshundreds thousandsofCPUs Wanttomakethiseasy GoogleEarthuses70 5TB 70TBfortherawimageryand500GBfortheindexdata From MapReduce Automaticparallelization distributionFault tolerantProvidesstatusandmonitoringtoolsCleanabstractionforprogrammers ProgrammingModel BorrowsfromfunctionalprogrammingUsersimplementinterfaceoftwofunctions map in key in value out key intermediate value listreduce out key intermediate valuelist out valuelist map Recordsfromthedatasource linesoutoffiles rowsofadatabase etc arefedintothemapfunctionaskey valuepairs e g filename line map producesoneormoreintermediatevaluesalongwithanoutputkeyfromtheinput reduce Afterthemapphaseisover alltheintermediatevaluesforagivenoutputkeyarecombinedtogetherintoalistreduce combinesthoseintermediatevaluesintooneormorefinalvaluesforthatsameoutputkey inpractice usuallyonlyonefinalvalueperkey Parallelism map functionsruninparallel creatingdifferentintermediatevaluesfromdifferentinputdatasetsreduce functionsalsoruninparallel eachworkingonadifferentoutputkeyAllvaluesareprocessedindependentlyBottleneck reducephasecan tstartuntilmapphaseiscompletelyfinished Example Countwordoccurrences map Stringinput key Stringinput value input key documentname input value documentcontentsforeachwordwininput value EmitIntermediate w 1 reduce Stringoutput key Iteratorintermediate values output key aword output values alistofcountsintresult 0 foreachvinintermediate values result ParseInt v Emit AsString result Example Page1 theweatherisgoodPage2 todayisgoodPage3 goodweatherisgood Mapoutput Worker1 the1 weather1 is1 good1 Worker2 today1 is1 good1 Worker3 good1 weather1 is1 good1 ReduceInput Worker1 the1 Worker2 is1 is1 is1 Worker3 weather1 weather1 Worker4 today1 Worker5 good1 good1 good1 good1 ReduceOutput Worker1 the1 Worker2 is3 Worker3 weather2 Worker4 today1 Worker5 good4 SomeOtherRealExamples TermfrequenciesthroughthewholeWebrepositoryCountofURLaccessfrequencyReverseweb linkgraph ImplementationOverview Typicalcluster 100s 1000sof2 CPUx86machines 2 4GBofmemoryLimitedbisectionbandwidthStorageisonlocalIDEdisksGFS distributedfilesystemmanagesdata SOSP 03 Jobschedulingsystem jobsmadeupoftasks schedulerassignstaskstomachinesImplementationisaC librarylinkedintouserprograms Architecture Execution TaskGranularity Finegranularitytasks manymoremaptasksthanmachinesMinimizestimeforfaultrecoveryBetterdynamicloadbalancingOftenuse200 000map 5000reducetasksw 2000machines Locality Masterprogramdividesuptasksbasedonlocationofdata AsksGFSforlocationsofreplicasofinputfileblocks triestohavemap tasksonsamemachineasphysicalfiledata oratleastsamerack Effect Thousandsofmachinesreadinputatlocaldiskspeed FaultTolerance Onworkerfailure DetectfailureviaperiodicheartbeatsRe executecompletedandin progressmaptasksRe executeinprogressreducetasksTaskcompletioncommittedthroughmasterMasterfailure Couldhandle butdon tyet masterfailureunlikely Robust lost1600of1800machinesonce butfinishedfine Optimizations Noreducecanstartuntilmapiscomplete Asingleslowdiskcontrollercanrate limitthewholeprocessMasterredundantlyexecutes slow moving maptasks usesresultsoffirstcopytofinish onefinishesfirst wins Whyisitsafetoredundantlyexecutemaptasks Wouldn tthismessupthetotalcomputation SlowworkerssignificantlylengthencompletiontimeOtherjobsconsumingresourcesonmachineBaddiskswithsofterrorstransferdataveryslowlyWeirdthings processorcachesdisabled Optimizations Combiner functionscanrunonsamemachineasamapperCausesamini reducephasetooccurbeforetherealreducephase tosavebandwidth Performance Testsrunonclusterof1800machines 4GBofmemoryDual processor2GHzXeonswithHyperthreadingDual160GBIDEdisksGigabitEthernetpermachineBisectionbandwidthapproximately100Gbps Twobenchmarks MR GrepScan1010100 byterecordstoextractrecordsmatchingararepattern 92Kmatchingrecords MR SortSort1010100 byterecords modeledafterTeraSortbenchmark MR Grep Localityoptimizationhelps 1800machinesread1TBofdataatpeakof 31GB sWithoutthis rackswitcheswouldlimitto10GB sStartupoverheadissignificantforshortjobs MR Sort BackuptasksreducejobcompletiontimesignificantlySystemdealswellwithfailures Normal NoBackupTasks 200processeskilled MoreandmoreMapReduce MapReduceProgramsInGoogleSourceTree Exampleuses distributedgrepdistributedsortweblink graphreversalterm vectorperhostwebaccesslogstatsinvertedindexconstructiondocumentclusteringmachinelearningstatisticalmachinetranslation MapReduceConclusions MapReducehasproventobeausefulabstractionGr