Module 2 - Student Background Knowledge

©SpinnakerLabs,Inc.GoogleClusterComputingFacultyTrainingWorkshopModuleII:StudentBackgroundKnowledgeThispresentationincludescoursecontent©UniversityofWashingtonRedistributedundertheCreativeCommonsAttribution3.0license.Allothercontents:©SpinnakerLabs,Inc.BackgroundTopics•ProgrammingLanguages•Systems:–OperatingSystems–FileSystems–Networking•Databases©SpinnakerLabs,Inc.ProgrammingLanguages•MapReduceisbasedonfunctionalprogrammingmapandfold•FPistaughtinonequarter,butnotreinforced–“Crashcourse”necessary–Worksheetstoposeshortproblemsintermsofmapandfold–Immutabledataakeyconcept©SpinnakerLabs,Inc.Multithreadedprogramming•TaughtinOScourseatWashington–Notaprerequisite!•Studentsneedtounderstandmultiplecopiesofsamemethodrunninginparallel©SpinnakerLabs,Inc.FileSystems•NecessarytounderstandGFS•ComparisontoNFS,otherdistributedfilesystemsrelevant©SpinnakerLabs,Inc.Networking•TCP/IP•Conceptsof“connection,”networksplits,otherfailuremodes•Bandwidthissues©SpinnakerLabs,Inc.OtherSystemsTopics•ProcessScheduling•Synchronization•Memorycoherency©SpinnakerLabs,Inc.Databases•Conceptofsharedconsistencymodel•Consensus•ACIDcharacteristics–Journaling–Multi-phasecommitprocesses©SpinnakerLabs,Inc.Parallelization&Synchronization©SpinnakerLabs,Inc.ParallelizationIdea•Parallelizationis“easy”ifprocessingcanbecleanlysplitintonunits:workw1w2w3Partitionproblem©SpinnakerLabs,Inc.ParallelizationIdea(2)w1w2w3threadthreadthreadSpawnworkerthreads:Inaparallelcomputation,wewouldliketohaveasmanythreadsaswehaveprocessors.e.g.,afour-processorcomputerwouldbeabletorunfourthreadsatthesametime.©SpinnakerLabs,Inc.ParallelizationIdea(3)threadthreadthreadWorkersprocessdata:w1w2w3©SpinnakerLabs,Inc.ParallelizationIdea(4)resultsReportresultsthreadthreadthreadw1w2w3©SpinnakerLabs,Inc.ParallelizationPitfallsButthismodelistoosimple!•Howdoweassignworkunitstoworkerthreads?•Whatifwehavemoreworkunitsthanthreads?•Howdoweaggregatetheresultsattheend?•Howdoweknowalltheworkershavefinished?•Whatiftheworkcannotbedividedintocompletelyseparatetasks?Whatisthecommonthemeofalloftheseproblems?©SpinnakerLabs,Inc.ParallelizationPitfalls(2)•Eachoftheseproblemsrepresentsapointatwhichmultiplethreadsmustcommunicatewithoneanother,oraccessasharedresource.•Goldenrule:Anymemorythatcanbeusedbymultiplethreadsmusthaveanassociatedsynchronizationsystem!©SpinnakerLabs,Inc.WhatisWrongWithThis?Thread1:voidfoo(){x++;y=x;}Thread2:voidbar(){y++;x++;}Iftheinitialstateisy=0,x=6,whathappensafterthesethreadsfinishrunning?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];inceax;mem[x]=eax;}•Manythingsthatlooklike“onestep”operationsactuallytakeseveralstepsunderthehood:©SpinnakerLabs,Inc.Multithreaded=UnpredictabilityThisappliestomorethanjustintegers:•Pullingworkunitsfromaqueue•Reportingworkbacktomasterunit•Tellinganotherthreadthatitcanbeginthe“nextphase”ofprocessing…Allrequiresynchronization!©SpinnakerLabs,Inc.SynchronizationPrimitives•Asynchronizationprimitiveisaspecialsharedvariablethatguaranteesthatitcanonlybeaccessedatomically.•HardwaresupportguaranteesthatoperationsonsynchronizationprimitivesonlyevertakeonestepSemaphores•Asemaphoreisaflagthatcanberaisedorloweredinonestep•SemaphoreswereflagsthatrailroadengineerswouldusewhenenteringasharedtrackSet:Reset:Onlyonesideofthesemaphorecaneverbered!(Canbothbegreen?)©SpinnakerLabs,Inc.Semaphores•set()andreset()canbethoughtofaslock()andunlock()•Callstolock()whenthesemaphoreisalreadylockedcausethethreadtoblock.•Pitfalls:Must“bind”semaphorestoparticularobjects;mustremembertounlockcorrectly©SpinnakerLabs,Inc.The“Corrected”ExampleThread1:voidfoo(){sem.lock();x++;y=x;sem.unlock();}Thread2:voidbar(){sem.lock();y++;x++;sem.unlock();}Globalvar“Semaphoresem=newSemaphore();”guardsaccesstox&y©SpinnakerLabs,Inc.ConditionVariables•Aconditionvariablenotifiesthreadsthataparticularconditionhasbeenmet•Informanotherthreadthataqueuenowcontainselementstopullfrom(orthatit’sempty–requestmoreelements!)•Pitfall:Whatifnobody’slistening?ThefinalexampleThread1:voidfoo(){sem.lock();x++;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.•Barrierwakesupallregisteredthreadswhentotalcountiscorrect•Pitfall:Whathappensifathreadtakesalongtime?©SpinnakerLabs,Inc.TooMuchSynchronization?DeadlockSynchronizationbecomesevenmorecomplicatedwhenmultiplelockscanbeusedCancauseentiresystemto“getstuck”ThreadA:semaphore1.lock();semaphore2.lock();/*usedataguardedbysemaphores*/semaphore1.unlock();semaphore2.unlock();ThreadB:semaphore2.lock();semaphore1.lock();/*usedataguardedb