32北航云计算公开课06 Google Chubby

By邓侃Ph.D,朱小杰SmartClouder.com2/40/403ABtypedefstruct{intvalue;structprocess*L;}semaphore;wait(S){S.value--;if(S.value0){addthisprocesstoS.L;block;}}signal(S){S.value++;if(S.value=0){removeaprocessPfromS.L;wakeup(P);}}Process*L:waitinglistintvalue:Availableseats.initialvalue=33“semaphoreS”isasharedvariable/404BAtypedefstruct{intvalue;structprocess*L;}semaphore;wait(S){S.value--;if(S.value0){addthisprocesstoS.L;block;}}signal(S){S.value++;if(S.value=0){removeaprocessPfromS.L;wakeup(P);}}waitinglistS.L=nullAvailableseats.S.value=11Whenaseatisoccupied,S.value-1./405BAtypedefstruct{intvalue;structprocess*L;}semaphore;wait(S){S.value--;if(S.value0){addthisprocesstoS.L;block;}}signal(S){S.value++;if(S.value=0){removeaprocessPfromS.L;wakeup(P);}}waitinglistS.L={D,E}Availableseats.S.value=-2-2Whennoseatisavailable,thecominguserswillwait.CDE/406BDtypedefstruct{intvalue;structprocess*L;}semaphore;wait(S){S.value--;if(S.value0){addthisprocesstoS.L;block;}}signal(S){S.value++;if(S.value=0){removeaprocessPfromS.L;wakeup(P);}}waitinglistS.L={E}Availableseats.S.value=-1-1Whenoneuserfinishes,S.value+1.Onepersoninthewaitinglistwillbenotified.CEA/407BDsemaphoreS;voidhandler(){wait(S);{dosomethinginbathroom;}signal(S);terminate_thread();}main(){S=semaphore_init(3);/*Globalvariable*/threadA,B,C,D,E;A=creat_thread((void*)&handler);A.start_thread();/*ThesameforB,C,D,E*/}SemaphoreSisasharedvariable.Multiplethreadscompeteforthelock.-1TheusageofSemaphoreCEA/408BAtypedefstruct{intvalue;structprocess*L;}semaphore;wait(S){S.value--;if(S.value0){addthisprocesstoS.L;block;}}signal(S){S.value++;if(S.value=0){removeaprocessPfromS.L;wakeup(P);}}Noteveryonecanreceivesignal(S).Whensomeoneissignaled,hemaynotrespond.-2Semaphoredoesn’tworkwell,Indistributedsystemwithunstablecommunication.CDEHowtosyncSemaphorestoredoneveryone’sphone?StoreSemaphoreineveryone’sphonelocally?Orglobally?/409•Alockcontrolsaccessbymultiplethreads,toacommonresource.Alockisashareddatastruct,usuallyaglobalone,usedbyparalleledrunningthreads.•Semaphoreisanimplementationoflock,consistingofacounter,andawaitinglistofthreads.•Theinitialvalueofthecounterofsemaphoreindicatesthenumberofcommonresource.Whenonecommonresourceisoccupiedbyathread,thecounterdecreasesby1.Whenathreadfinishesitsjob,andreleasesonecommonresource,thecounterincreasesby1,andbycallingsignal(),thesemaphorewakesupthetopthreadinthewaitinglist.•Whenallcommonresourcesareoccupied,thecomingthreadswillwaitinthewaitinglist.Thecounter’svaluebecomesnegative,indicatingthelengthofthewaitinglist.•Semaphoredoesn’tworkwellindistributedsystem,wheretheunstablecommunicationmayfailsignal(),wheretheparticipantmaycrash,ormaynotrespondintime.10/40/4011LeslieLamport•Theinitialdeveloperof•Paxoswasproposedin1989,butnotpublishedinTOCSjournaluntil1998.TOCS:ACMTransactiononComputerScience.•RejectionofTOCS89:-ToomucharchaeologicalstoriesofGreekparliament.-Toofewscientificformula.•AnnotationofTOCS98journalpaper:-ThissubmissionwasrecentlydiscoveredbehindafilingcabinetintheTOCSeditorialoffice.-TheauthoriscurrentlydoingfieldworkintheGreekislesandcannotbereached....•Paxosmission:“Howtoreachconsensus/dataconsistencyindistributedsystemthatcantoleratenon-maliciousfailures?”./4012T2T1Whenacurrentuserleaves,he(T1)notifiesallusers,includingthecurrentusersandwaitingusers.Allusersrespondtheproposerwiththeearliestuserinthewaitinglist(T4),whoisthenextcandidatetousethewashroom.-3HomebrewPaxosT3Whenanewusercomes,hetellsthecurrentusershisphonenumberandtimestamp.Don’tneedtheglobalsemaphore.Butwithaglobalsupervisor,coordinationbecomeseasier.T4T6T5Theproposerselectsthecandidatewiththeearliesttimestamp,andnotifyall./4013T2T1Iftheearliestwaitinguser(T4),doesn’trespond,selectthesecondwaitinguser(T5).Ifthewaitinglistinalluser’srecordsarenotconsist,i.e.notalluseragreethatT4isthenextuser,selectthenextuserbythemajorityvotes.-3HomebrewPaxosT3IfT1notifiesallusers,buttoobusytomakedecision,T2orT3canactastheproposer.T4T6T5-3/4014HomebrewPaxosProposersAcceptorsT1T2T3T2T3T4T5T6Prepare(N)T4T4T4T6Prepare(N+1)Promise(N+1)Promise(N)T4T4T4T6Prepare(N+2)Promise(N+2)T5T5T5T6Accept(N+2,T5)“Official”Paxosmessageflow/4015•Roles:Client:auserrequest.Proposer:coordinator.Leader:distinguishedproposer.Acceptor:voterwithmemory.Quorum:acceptormajority.Learner:memoryreplica,oractionexecutors.•Twophases,Phase1a:prepare,Phase1b:promise.Phase2a:acceptrequest,Phase2b:accepted./4016GFSusesPaxos/Chubbyto:selectthePrimaryReplica.GoogleBigtableusesPaxos/Chubbyto:•Selectamaster.•Discoverwhichmastercontrolswhichservers.•Helptheclienttofinditsmaster.BothGFSandBigtableusesPaxos/Chubbyto:•Meta-datacentralstorage.•Therootoftheirdistributedstorageservers.•Partitioningjobsamongmultipleservers./4017•Semaphoredoesn’tworkwellindistributedsystem,wheretheunstablecommunicationmayfailsignal(),wheretheparticipantmaycrash,ormaynotrespondintime.•Paxosprotocolinvolvesin5roles,Client,ProposerswithaLeader,Acceptors,andLearners,Oneparticipantmaytakemultipleroles.•Paxosconsistsoftwophases,1a.Proposerleader“prepare”ap