资源描述：
《paxos_made_live.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、PaxosMadeLive-AnEngineeringPerspectiveTusharChandraRobertGriesemerJoshuaRedstoneJune26,2007AbstractWedescribeourexperiencebuildingafault-tolerantdata-baseusingthePaxosconsensusalgorithm.Despitetheexistingliteratureinthefield,buildingsuchadatabaseprovedtobenon-trivial.W
2、edescribeselectedalgorithmicandengineeringproblemsencountered,andthesolutionswefoundforthem.Ourmeasurementsindicatethatwehavebuiltacompetitivesystem.1IntroductionItiswellknownthatfault-toleranceoncommodityhardwarecanbeachievedthroughreplication[17,18].Acommonapproachi
3、stouseaconsensusalgorithm[7]toensurethatallreplicasaremutuallyconsistent[8,14,17].Byrepeatedlyapplyingsuchanalgorithmonasequenceofinputvalues,itispossibletobuildanidenticallogofvaluesoneachreplica.Ifthevaluesareoperationsonsomedatastructure,applicationofthesamelogonal
4、lreplicasmaybeusedtoarriveatmutuallyconsistentdatastructuresonallreplicas.Forinstance,ifthelogcontainsasequenceofdatabaseoperations,andifthesamesequenceofoperationsisappliedtothe(local)databaseoneachreplica,eventuallyallreplicaswillendupwiththesamedatabasecontent(prov
5、idedthattheyallstartedwiththesameinitialdatabasestate).Thisgeneralapproachcanbeusedtoimplementawidevarietyoffault-tolerantprimitives,ofwhichafault-tolerantdatabaseisjustanexample.Asaresult,theconsensusproblemhasbeenstudiedextensivelyoverthepasttwodecades.Therearesever
6、alwell-knownconsensusalgorithmsthatoperatewithinamultitudeofsettingsandwhichtolerateavarietyoffailures.ThePaxosconsensusalgorithm[8]hasbeendiscussedinthetheoretical[16]andappliedcommunity[10,11,12]foroveradecade.WeusedthePaxosalgorithm(“Paxos”)asthebaseforaframeworkth
7、atimplementsafault-tolerantlog.Wethenreliedonthatframeworktobuildafault-tolerantdatabase.Despitetheexistingliteratureonthesubject,buildingaproductionsystemturnedouttobeanon-trivialtaskforavarietyofreasons:•WhilePaxoscanbedescribedwithapageofpseudo-code,ourcompleteimpl
8、ementationcontainsseveralthousandlinesofC++code.Theblow-upisnotduesimplytothefactthatweusedC++insteadofpseudonotation,norbec
