搜索
Pastry:Scalable,decentralizedobjectlocationandroutingforlarge-scalepeer-to-peersystems?AntonyRowstron1andPeterDruschel2??1MicrosoftResearchLtd,St.GeorgeHouse,1GuildhallStreet,Cambridge,CB23NH,UK.antr@microsoft.com2RiceUniversityMS-132,6100MainStreet,Houston,TX77005-1892,USA.druschel@cs.rice.eduAbstract.ThispaperpresentsthedesignandevaluationofPastry,ascalable,distributedobjectlocationandroutingsubstrateforwide-areapeer-to-peerap-plications.Pastryperformsapplication-levelroutingandobjectlocationinapo-tentiallyverylargeoverlaynetworkofnodesconnectedviatheInternet.Itcanbeusedtosupportavarietyofpeer-to-peerapplications,includingglobaldatastorage,datasharing,groupcommunicationandnaming.EachnodeinthePastrynetworkhasauniqueidentifier(nodeId).Whenpresentedwithamessageandakey,aPastrynodeefficientlyroutesthemessagetothenodewithanodeIdthatisnumericallyclosesttothekey,amongallcurrentlylivePastrynodes.EachPastrynodekeepstrackofitsimmediateneighborsinthenodeIdspace,andnotifiesapplicationsofnewnodearrivals,nodefailuresandrecoveries.Pastrytakesintoaccountnetworklocality;itseekstominimizethedistancemessagestravel,accordingtoatoscalarproximitymetriclikethenumberofIProutinghops.Pastryiscompletelydecentralized,scalable,andself-organizing;itautomaticallyadaptstothearrival,departureandfailureofnodes.Experimentalresultsobtainedwithaprototypeimplementationonanemulatednetworkofupto100,000nodesconfirmPastry’sscalabilityandefficiency,itsabilitytoself-organizeandadapttonodefailures,anditsgoodnetworklocalityproperties.1IntroductionPeer-to-peerInternetapplicationshaverecentlybeenpopularizedthroughfilesharingapplicationslikeNapster,GnutellaandFreeNet[1,2,8].Whilemuchoftheattentionhasbeenfocusedonthecopyrightissuesraisedbytheseparticularapplications,peer-to-peersystemshavemanyinterestingtechnicalaspectslikedecentralizedcontrol,self-organization,adaptationandscalability.Peer-to-peersystemscanbecharacterizedasdistributedsystemsinwhichallnodeshaveidenticalcapabilitiesandresponsibilitiesandallcommunicationissymmetric.?AppearsinProc.ofthe18thIFIP/ACMInternationalConferenceonDistributedSystemsPlat-forms(Middleware2001).Heidelberg,Germany,November2001.??WorkdoneinpartwhilevisitingMicrosoftResearch,Cambridge,UK.Therearecurrentlymanyprojectsaimedatconstructingpeer-to-peerapplicationsandunderstandingmoreoftheissuesandrequirementsofsuchapplicationsandsys-tems[1,2,5,8,10,15].Oneofthekeyproblemsinlarge-scalepeer-to-peerapplicationsistoprovideefficientalgorithmsforobjectlocationandroutingwithinthenetwork.ThispaperpresentsPastry,agenericpeer-to-peerobjectlocationandroutingscheme,basedonaself-organizingoverlaynetworkofnodesconnectedtotheInternet.Pastryiscompletelydecentralized,fault-resilient,scalable,andreliable.Moreover,Pastryhasgoodroutelocalityproperties.Pastryisintendedasgeneralsubstratefortheconstructionofavarietyofpeer-to-peerInternetapplicationslikeglobalfilesharing,filestorage,groupcommunicationandnamingsystems.SeveralapplicationhavebeenbuiltontopofPastrytodate,includingaglobal,persistentstorageutilitycalledPAST[11,21]andascalablepublish/subscribesystemcalledSCRIBE[22].Otherapplicationsareunderdevelopment.Pastryprovidesthefollowingcapability.EachnodeinthePastrynetworkhasauniquenumericidentifier(nodeId).Whenpresentedwithamessageandanumerickey,aPastrynodeefficientlyroutesthemessagetothenodewithanodeIdthatisnumeri-callyclosesttothekey,amongallcurrentlylivePastrynodes.TheexpectednumberofroutingstepsisO(logN),whereNisthenumberofPastrynodesinthenetwork.AteachPastrynodealongtheroutethatamessagetakes,theapplicationisnotifiedandmayperformapplication-specificcomputationsrelatedtothemessage.Pastrytakesintoaccountnetworklocality;itseekstominimizethedistancemes-sagestravel,accordingtoascalarproximitymetriclikethenumberofIProutinghops.EachPastrynodekeepstrackofitsimmediateneighborsinthenodeIdspace,andno-tifiesapplicationsofnewnodearrivals,nodefailuresandrecoveries.BecausenodeIdsarerandomlyassigned,withhighprobability,thesetofnodeswithadjacentnodeIdisdiverseingeography,ownership,jurisdiction,etc.Applicationscanleveragethis,asPastrycanroutetooneofknodesthatarenumericallyclosesttothekey.AheuristicensuresthatamongasetofnodeswiththekclosestnodeIdstothekey,themessageislikelytofirstreachanode“near”thenodefromwhichthemessageoriginates,intermsoftheproximitymetric.Applicationsusethesecapabilitiesindifferentways.PAST,forinstance,usesafileId,computedasthehashofthefile’snameandowner,asaPastrykeyforafile.ReplicasofthefilearestoredonthekPastrynodeswithnodeIdsnumericallyclosesttothefileId.AfilecanbelookedupbysendingamessageviaPastry,usingthefileIdasthekey.Bydefinition,thelookupisguaranteedtoreachanodethatstoresthefileaslongasoneoftheknodesislive.Moreover,itfollowsthatthemessageislikelytofirstreachanodeneartheclient,amongtheknodes;thatnodedeliversthefileandconsumesthemessage.Pastry’snotificationmechanismsallowPASTtomaintainreplicasofafileontheknodesclosesttothekey,despitenodefailureandnodearrivals,andusingonlylocalcoordinationamongnodeswithadjacentnodeIds.DetailsonPAST’suseofPastrycanbefoundin[11,21].As