Google云计算课程-Module2-StudentBackgroundKnowledge.ppt

SpinnakerLabs,Inc.,GoogleClusterComputingFacultyTrainingWorkshop,ModuleII:StudentBackgroundKnowledge,ThispresentationincludescoursecontentUniversityofWashingtonRedistributedundertheCreativeCommonsAttribution3.0license.Allothercontents:,SpinnakerLabs,Inc.,BackgroundTopics,ProgrammingLanguagesSystems:OperatingSystemsFileSystemsNetworkingDatabases,SpinnakerLabs,Inc.,ProgrammingLanguages,MapReduceisbasedonfunctionalprogrammingmapandfoldFPistaughtinonequarter,butnotreinforced“Crashcourse”necessaryWorksheetstoposeshortproblemsintermsofmapandfoldImmutabledataakeyconcept,SpinnakerLabs,Inc.,Multithreadedprogramming,TaughtinOScourseatWashingtonNotaprerequisite!Studentsneedtounderstandmultiplecopiesofsamemethodrunninginparallel,SpinnakerLabs,Inc.,FileSystems,NecessarytounderstandGFSComparisontoNFS,otherdistributedfilesystemsrelevant,SpinnakerLabs,Inc.,Networking,TCP/IPConceptsof“connection,”networksplits,otherfailuremodesBandwidthissues,SpinnakerLabs,Inc.,OtherSystemsTopics,ProcessSchedulingSynchronizationMemorycoherency,SpinnakerLabs,Inc.,Databases,ConceptofsharedconsistencymodelConsensusACIDcharacteristicsJournalingMulti-phasecommitprocesses,SpinnakerLabs,Inc.,Parallelizationy=x;,Thread2:voidbar()y+;x+;,Iftheinitialstateisy=0,x=6,whathappensafterthesethreadsfinishrunning?,Multithreaded=Unpredictability,Whenwerunamultithreadedprogram,wedontknowwhatorderthreadsrunin,nordoweknowwhentheywillinterruptoneanother.,Thread1:voidfoo()eax=memx;inceax;memx=eax;ebx=memx;memy=ebx;,Thread2:voidbar()eax=memy;inceax;memy=eax;eax=memx;inceax;memx=eax;,Manythingsthatlooklike“onestep”operationsactuallytakeseveralstepsunderthehood:,SpinnakerLabs,Inc.,Multithreaded=Unpredictability,Thisappliestomorethanjustintegers:PullingworkunitsfromaqueueReportingworkbacktomasterunitTellinganotherthreadthatitcanbeginthe“nextphase”ofprocessingAllrequiresynchronization!,SpinnakerLabs,Inc.,SynchronizationPrimitives,Asynchronizationprimitiveisaspecialsharedvariablethatguaranteesthatitcanonlybeaccessedatomically.Hardwaresupportguaranteesthatoperationsonsynchronizationprimitivesonlyevertakeonestep,Semaphores,AsemaphoreisaflagthatcanberaisedorloweredinonestepSemaphoreswereflagsthatrailroadengineerswouldusewhenenteringasharedtrack,Onlyonesideofthesemaphorecaneverbered!(Canbothbegreen?),SpinnakerLabs,Inc.,Semaphores,set()andreset()canbethoughtofaslock()andunlock()Callstolock()whenthesemaphoreisalreadylockedcausethethreadtoblock.Pitfalls:Must“bind”semaphorestoparticularobjects;mustremembertounlockcorrectly,SpinnakerLabs,Inc.,The“Corrected”Example,Thread1:voidfoo()sem.lock();x+;y=x;sem.unlock();,Thread2:voidbar()sem.lock();y+;x+;sem.unlock();,Globalvar“Semaphoresem=newSemaphore();”guardsaccesstoxx+;y=x;fooDone=true;sem.unlock();fooFinishedCV.notify();,Thread2:voidbar()sem.lock();while(!fooDone)fooFinishedCV.wait(sem);y+;x+;sem.unlock();,Globalvars:Semaphoresem=newSemaphore();ConditionVarfooFinishedCV=newConditionVar();booleanfooDone=false;,SpinnakerLabs,Inc.,Barriers,Abarrierknowsinadvancehowmanythreadsitshouldwaitfor.Threads“register”withthebarrierwhentheyreachit,andfallasleep.BarrierwakesupallregisteredthreadswhentotalcountiscorrectPitfall:Whathappensifathreadtakesalongtime?,SpinnakerLabs,Inc.,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),SpinnakerLabs,Inc.,AndifyouthoughtIwasjoking,SpinnakerLabs,Inc.,TheMoral:BeCareful!,SynchronizationishardNeedtoconsiderallpossiblesharedstateMustkeeplocksorganizedandusethemconsistentlyandcorrectlyKnowingtherearebugsmaybetricky;fixingthemcanbeevenworse!Keepingsharedstatetoaminimumreducestotalsystemcomplexity,SpinnakerLabs,Inc.,FundamentalsofNetworking,SpinnakerLabs,Inc.,Sockets:TheInternet=tubes?,AsocketisthebasicnetworkinterfaceProvidesatwo-way“pipe”abstractionbetweentwoapplicationsClientcreatesasocket,andconnectstotheserver,whoreceivesasocketrepresentingtheotherside,SpinnakerLabs,Inc.,Ports,WithinanIPaddress,aportisasub-addressidentifyingalisteningprogramAllowsmultipleclientstoconnecttoaserveratonce,SpinnakerLabs,Inc.,Example:WebServer(1/3),Theservercreatesalistenersocketattachedtoaspecificport.80istheagreed-uponportnumberforwebtraffic.,SpinnakerLabs,Inc.,Example:WebServer(2/3),Theclient-sidesocketisstillconnectedtoaport,buttheOSchoosesarandomunusedportnumberWhentheclientrequestsaURL(e.g.,“”),itsOSusesasystemcalledDNStofinditsIPaddress.,SpinnakerLabs,Inc.,Example:WebServer(3/3),Serverchoosesarandomly-numberedporttohandlethisparticularclientListenerisreadyformoreincomingconnections,whileweprocessthecurrentconnectioninparallel,Whatmakesthiswork?,UnderneaththesocketlayerareseveralmoreprotocolsMostimportantareTCPandIP(whichareusedhand-in-handsooften,theyreoftenspokenofasoneprotocol:TCP/IP),Evenmorelow-levelprotocolshandlehowdataissentoverEthernetwires,orhowbitsaresentthroughtheairusing802.11wireless,SpinnakerLabs,Inc.,IP:TheInternetProtocol,DefinestheaddressingschemeforcomputersEncapsulatesinternaldataina“packet”DoesnotprovidereliabilityJustincludesenoughinformationforthedatatotellrouterswheretosendit,SpinnakerLabs,Inc.,TCP:TransmissionControlProtocol,BuiltontopofIPIntroducesconceptof“connection”Providesreliabilityandordering,SpinnakerLabs,Inc.,WhyisThisNecessary?,Notactuallytube-like“underneaththehood”Unlikephonesystem(circuitswitched),thepacketswitchedInternetusesmanyroutesatonce,SpinnakerLabs,Inc.,NetworkingIssues,Ifapartytoasocketdisconnects,howmuchdatadidtheyreceive?Didtheycrash?Ordidamachineinthemiddle?Cansomeoneinthemiddleintercept/modifyourdata?Trafficcongestionmakesswitch/routertopologyimportantforefficientthroughput,SpinnakerLabs,Inc.,FinalThoughts,VariousbackgroundtopicsfitintothiscourseTwoexampleshighlightedOtherbackgroundtopicsmaybenefitfromexpansion,worksheets,reinforcement,