大规模数据处理云计算北大闫宏飞PPT课件.ppt

大规模数据处理 云计算Lecture3 MapReduceBasics 闫宏飞北京大学信息科学技术学院7 12 2011 ThisworkislicensedunderaCreativeCommonsAttribution Noncommercial ShareAlike3 0UnitedStatesSeehttp creativecommons org licenses by nc sa 3 0 us fordetails JimmyLinUniversityofMaryland 课程建设 SEWMGroup 1 Howdowescaleup 2 Source Wikipedia IBMRoadrunner 3 DivideandConquer Work w1 w2 w3 r1 r2 r3 Result worker worker worker Partition Combine 4 ParallelizationChallenges Howdoweassignworkunitstoworkers Whatifwehavemoreworkunitsthanworkers Whatifworkersneedtosharepartialresults Howdoweaggregatepartialresults Howdoweknowalltheworkershavefinished Whatifworkersdie Whatisthecommonthemeofalloftheseproblems 5 CommonTheme Parallelizationproblemsarisefrom Communicationbetweenworkers e g toexchangestate Accesstosharedresources e g data Thus weneedasynchronizationmechanism 6 Source RicardoGuimar esHerrmann 7 ManagingMultipleWorkers DifficultbecauseWedon tknowtheorderinwhichworkersrunWedon tknowwhenworkersinterrupteachotherWedon tknowtheorderinwhichworkersaccessshareddataThus weneed Semaphores lock unlock Conditionalvariables wait notify broadcast BarriersStill lotsofproblems Deadlock livelock raceconditions Diningphilosophers sleepybarbers cigarettesmokers Moralofthestory becareful 8 CurrentTools ProgrammingmodelsSharedmemory pthreads Messagepassing MPI DesignPatternsMaster slavesProducer consumerflowsSharedworkqueues 9 Wheretherubbermeetstheroad ConcurrencyisdifficulttoreasonaboutConcurrencyisevenmoredifficulttoreasonaboutAtthescaleofdatacenters evenacrossdatacenters InthepresenceoffailuresIntermsofmultipleinteractingservicesNottomentiondebugging Thereality Lotsofone offsolutions customcodeWriteyouowndedicatedlibrary thenprogramwithitBurdenontheprogrammertoexplicitlymanageeverything 10 Source Wikipedia FlatTire 11 Source MITOpenCourseware 12 Source MITOpenCourseware 13 Source Harper s Feb 2008 14 What sthepoint It sallabouttherightlevelofabstractionThevonNeumannarchitecturehasserveduswell butisnolongerappropriateforthemulti core clusterenvironmentHidesystem leveldetailsfromthedevelopersNomoreraceconditions lockcontention etc SeparatingthewhatfromhowDeveloperspecifiesthecomputationthatneedstobeperformedExecutionframework runtime handlesactualexecution Thedatacenteristhecomputer 15 BigIdeas Scale out not up LimitsofSMPandlargeshared memorymachinesMoveprocessingtothedataClusterhavelimitedbandwidthProcessdatasequentially avoidrandomaccessSeeksareexpensive diskthroughputisreasonableSeamlessscalabilityFromthemythicalman monthtothetradablemachine hour 16 MapReduce g g g g g f f f f f Map Fold RootsinFunctionalProgramming TypicalLarge DataProblem IterateoveralargenumberofrecordsExtractsomethingofinterestfromeachShuffleandsortintermediateresultsAggregateintermediateresultsGeneratefinaloutput Keyidea provideafunctionalabstractionforthesetwooperations Map Reduce DeanandGhemawat OSDI2004 19 MapReduce Programmersspecifytwofunctions map k v reduce k v AllvalueswiththesamekeyaresenttothesamereducerTheexecutionframeworkhandleseverythingelse 20 map map map map ShuffleandSort aggregatevaluesbykeys reduce reduce reduce 21 MapReduce Programmersspecifytwofunctions map k v reduce k v AllvalueswiththesamekeyaresenttothesamereducerTheexecutionframeworkhandleseverythingelse What s everythingelse 22 MapReduce Runtime HandlesschedulingAssignsworkerstomapandreducetasksHandles datadistribution MovesprocessestodataHandlessynchronizationGathers sorts andshufflesintermediatedataHandleserrorsandfaultsDetectsworkerfailuresandrestartsEverythinghappensontopofadistributedFS later 23 MapReduce Programmersspecifytwofunctions map k v reduce k v AllvalueswiththesamekeyarereducedtogetherTheexecutionframeworkhandleseverythingelse Notquite usually programmersalsospecify partition k numberofpartitions partitionfork Oftenasimplehashofthekey e g hash k modnDividesupkeyspaceforparallelreduceoperationscombine k v Mini reducersthatruninmemoryafterthemapphaseUsedasanoptimizationtoreducenetworktraffic 24 combine combine combine combine partition partition partition partition map map map map ShuffleandSort aggregatevaluesbykeys reduce reduce reduce 25 Twomoredetails BarrierbetweenmapandreducephasesButwecanbegincopyingintermediatedataearlierKeysarriveateachreducerinsortedorderNoenforcedorderingacrossreducers 26 HelloWorld WordCount Map Stringdocid Stringtext foreachwordwintext Emit w 1 Reduce Stringterm Iteratorvalues intsum 0 foreachvinvalues sum v Emit term sum 27 MapReducecanreferto TheprogrammingmodelTheexecutionframework aka runtime Thespecificimplementation Usageisusuallyclearfromcontext 28 MapReduceImplementations GooglehasaproprietaryimplementationinC BindingsinJava PythonHadoopisanopen sourceimplementationinJavaAnApacheprojectLargecontributionofdevelopmentledbyYahoo usedinproductionRapidlyexpandingsoftwareecosystemLotsofcustomresearchimplementationsForGPUs cellprocessors etc 29 split0 split1 split2 split3 split4 worker worker worker worker worker Master UserProgram outputfile0 outputfile1 1 submit 2 schedulemap 2 schedulereduce 3 read 4 localwrite 5 remoteread 6 write Inputfiles Mapphase Intermediatefiles onlocaldisk Reducephase Outputfiles Adaptedfrom DeanandGhemawat OSDI2004 30 Howdowegetdatatotheworkers ComputeNodes NAS SAN What stheproblemhere 31 DistributedFileSystem Don tmovedatatoworkers moveworkerstothedata StoredataonthelocaldisksofnodesintheclusterStartuptheworkersonthenodethathasthedatalocalWhy NotenoughRAMtoholdallthedatainmemoryDiskaccessisslow butdiskthroughputisreasonableAdistributedfilesystemistheanswerGFS GoogleFileSystem forGoogle sMapReduceHDFS HadoopDistributedFileSystem forHadoop 32 GFS Assumptions Commodityhardwareover exotic hardwareScale out not up HighcomponentfailureratesInexpensivecommoditycomponentsfailallthetime Modest numberofhugefilesMulti gigabytefilesarecommon ifnotencouragedFilesarewrite once mostlyappendedtoPerhapsconcurrentlyLargestreamingreadsoverrandomaccessHighsustainedthroughputoverlowlatency GFSslidesadaptedfrommaterialby Ghemawatetal SOSP2003 33 GFS DesignDecisions FilesstoredaschunksFixedsize 64MB ReliabilitythroughreplicationEachchunkreplicatedacross3 chunkserversSinglemastertocoordinateaccess keepmetadataSimplecentralizedmanagementNodatacachingLittlebenefitduetolargedatasets streamingreadsSimplifytheAPIPushsomeoftheissuesontotheclient e g datalayout HDFS GFSclone samebasicideas 34 FromGFStoHDFS Terminologydifferences GFSmaster HadoopnamenodeGFSchunkservers HadoopdatanodesFunctionaldifferences NofileappendsinHDFS plannedfeature HDFSperformanceis likely slower Forthemostpart we llusetheHadoopterminology 35 Adaptedfrom Ghemawatetal SOSP2003 filename blockid blockid blocklocation instructionstodatanode datanodestate blockid byterange blockdata HDFSnamenode Filenamespace foo bar block3df2 Application HDFSClient HDFSArchitecture 36 NamenodeResponsibilities Managi