google云计算系列课程第一讲：介绍PPT课件.ppt

DistributedComputingSeminar Lecture1 IntroductiontoDistributedComputing SystemsBackground ChristopheBisciglia AaronKimball SierraMichels SlettvetSummer2007 Exceptwhereotherwisenoted thecontentsofthispresentationare Copyright2007UniversityofWashingtonandarelicensedundertheCreativeCommonsAttribution2 5License 1 CourseOverview 5lectures1Introduction2TechnicalSide MapReduce GFS2Theoretical AlgorithmsfordistributedcomputingReadings QuestionsnightlyReadings 2 Outline IntroductiontoDistributedComputingParallelvs DistributedComputingHistoryofDistributedComputingParallelizationandSynchronizationNetworkingBasics 3 ComputerSpeedup Moore sLaw Thedensityoftransistorsonachipdoublesevery18months forthesamecost 1965 Image Tom sHardwareandnotsubjecttotheCreativeCommonslicenseapplicabletotherestofthiswork Image Tom sHardware 4 Scopeofproblems Whatcanyoudowith1computer Whatcanyoudowith100computers Whatcanyoudowithanentiredatacenter 5 Distributedproblems Renderingmultipleframesofhigh qualityanimation Image DreamWorksAnimationandnotsubjecttotheCreativeCommonslicenseapplicabletotherestofthiswork 6 Distributedproblems Simulatingseveralhundredorthousandcharacters HappyFeet KingdomFeatureProductions LordoftheRings NewLineCinema neitherimageissubjecttotheCreativeCommonslicenseapplicabletotherestofthework 7 Distributedproblems Indexingtheweb Google SimulatinganInternet sizednetworkfornetworkingexperiments PlanetLab Speedingupcontentdelivery Akamai Whatisthekeyattributethatalltheseexampleshaveincommon 8 Parallelvs Distributed Parallelcomputingcanmean VectorprocessingofdataMultipleCPUsinasinglecomputerDistributedcomputingismultipleCPUsacrossmanycomputersoverthenetwork 9 ABriefHistory 1975 85 ParallelcomputingwasfavoredintheearlyyearsPrimarilyvector basedatfirstGraduallymorethread basedparallelismwasintroduced Image ComputerPicturesDatabaseandCrayResearchCorpandisnotsubjecttotheCreativeCommonslicenseapplicabletotherestofthiswork 10 Massivelyparallelarchitectures startrisinginprominenceMessagePassingInterface MPI andotherlibrariesdevelopedBandwidthwasabigproblem ABriefHistory 1985 95 11 ABriefHistory 1995 Today Cluster gridarchitectureincreasinglydominantSpecialnodemachineseschewedinfavorofCOTStechnologiesWeb wideclustersoftwareCompanieslikeGoogletakethistotheextreme 12 Parallelization Synchronization 13 ParallelizationIdea Parallelizationis easy ifprocessingcanbecleanlysplitintonunits 14 ParallelizationIdea 2 Inaparallelcomputation wewouldliketohaveasmanythreadsaswehaveprocessors e g afour processorcomputerwouldbeabletorunfourthreadsatthesametime 15 ParallelizationIdea 3 16 ParallelizationIdea 4 17 ParallelizationPitfalls Butthismodelistoosimple Howdoweassignworkunitstoworkerthreads Whatifwehavemoreworkunitsthanthreads Howdoweaggregatetheresultsattheend Howdoweknowalltheworkershavefinished Whatiftheworkcannotbedividedintocompletelyseparatetasks Whatisthecommonthemeofalloftheseproblems 18 ParallelizationPitfalls 2 Eachoftheseproblemsrepresentsapointatwhichmultiplethreadsmustcommunicatewithoneanother oraccessasharedresource Goldenrule Anymemorythatcanbeusedbymultiplethreadsmusthaveanassociatedsynchronizationsystem 19 WhatisWrongWithThis Thread1 voidfoo x y x Thread2 voidbar y x 3 Iftheinitialstateisy 0 x 6 whathappensafterthesethreadsfinishrunning 20 Multithreaded Unpredictability Whenwerunamultithreadedprogram wedon tknowwhatorderthreadsrunin nordoweknowwhentheywillinterruptoneanother Thread1 voidfoo eax mem x inceax mem x eax ebx mem x mem y ebx Thread2 voidbar eax mem y inceax mem y eax eax mem x addeax 3 mem x eax Manythingsthatlooklike onestep operationsactuallytakeseveralstepsunderthehood 21 Multithreaded Unpredictability Thisappliestomorethanjustintegers PullingworkunitsfromaqueueReportingworkbacktomasterunitTellinganotherthreadthatitcanbeginthe nextphase ofprocessing Allrequiresynchronization 22 SynchronizationPrimitives Asynchronizationprimitiveisaspecialsharedvariablethatguaranteesthatitcanonlybeaccessedatomically Hardwaresupportguaranteesthatoperationsonsynchronizationprimitivesonlyevertakeonestep 23 Semaphores AsemaphoreisaflagthatcanberaisedorloweredinonestepSemaphoreswereflagsthatrailroadengineerswouldusewhenenteringasharedtrack Onlyonesideofthesemaphorecaneverbered Canbothbegreen 24 Semaphores set andreset canbethoughtofaslock andunlock Callstolock whenthesemaphoreisalreadylockedcausethethreadtoblock Pitfalls Must bind semaphorestoparticularobjects mustremembertounlockcorrectly 25 The corrected example Thread1 voidfoo sem lock x y x sem unlock Thread2 voidbar sem lock y x 3 sem unlock Globalvar Semaphoresem newSemaphore guardsaccesstox y 26 ConditionVariables AconditionvariablenotifiesthreadsthataparticularconditionhasbeenmetInformanotherthreadthataqueuenowcontainselementstopullfrom orthatit sempty requestmoreelements Pitfall Whatifnobody slistening 27 Thefinalexample Thread1 voidfoo sem lock x y x fooDone true sem unlock fooFinishedCV notify Thread2 voidbar sem lock if fooDone fooFinishedCV wait sem y x 3 sem unlock Globalvars Semaphoresem newSemaphore ConditionVarfooFinishedCV newConditionVar booleanfooDone false 28 TooMuchSynchronization Deadlock SynchronizationbecomesevenmorecomplicatedwhenmultiplelockscanbeusedCancauseentiresystemto getstuck ThreadA semaphore1 lock semaphore2 lock usedataguardedbysemaphores semaphore1 unlock semaphore2 unlock ThreadB semaphore2 lock semaphore1 lock usedataguardedbysemaphores semaphore1 unlock semaphore2 unlock Image RPICSCI 4210OperatingSystemsnotes 29 TheMoral BeCareful SynchronizationishardNeedtoconsiderallpossiblesharedstateMustkeeplocksorganizedandusethemconsistentlyandcorrectlyKnowingtherearebugsmaybetricky fixingthemcanbeevenworse Keepingsharedstatetoaminimumreducestotalsystemcomplexity 30 FundamentalsofNetworking 31 Sockets TheInternet tubes AsocketisthebasicnetworkinterfaceProvidesatwo way pipe abstractionbetweentwoapplicationsClientcreatesasocket andconnectstotheserver whoreceivesasocketrepresentingtheotherside 32 Ports WithinanIPaddress aportisasub addressidentifyingalisteningprogramAllowsmultipleclientstoconnecttoaserveratonce 33 Whatmakesthiswork UnderneaththesocketlayerareseveralmoreprotocolsMostimportantareTCPandIP whichareusedhand in handsooften they reoftenspokenofasoneprotocol TCP IP Evenmorelow