Chord: A Scalable Peer-to-peer Lookup Protocol for ...

1 Chord: A ScalablePeer-to-peerLookupProtocolforInt ernetApplicationsIonStoicay, RobertMorrisz, DavidLiben-Nowellz, , , FrankDabekz,HariBalakrishnanzAbstract Afundamentalproblemthatconfrontspeer-to- peerapplicationsistheefficientlocationof thenodethatstoresa , a :givena key, it mapsthekeyontoa keywitheachdataitem, thesystem,andcananswerqueriesevenif thesystemis contin-uouslychanging. INTRODUCTIONPeer-to-peersystemsandapplic ationsaredistributedsystemswithoutany centralizedcontrolorhierarchicalorganiza tion, longlist:redundantstorage,permanence,sel ectionofnearbyservers,anonymity, search,authentication, , a scalableprotocolforlookupina protocolsupportsjustoneoperation:givena key,it mapsthekey ontoa ,thatnodemightberesponsibleforstoringa valueassoci-atedwiththekey.

2 Chordusesconsistenthashing[12] ,sinceeachnodereceivesroughlythesamenumb erofkeys,andrequiresrelativelylittlemove mentofkeyswhennodesjoinandleave awareofmostoftheothernodesinthesystem, ,eachChordnodeneeds routing informationaboutonlya ,aChordnodecommunicateswithothernodesino rdertoperforma ,inanN-nodesystem,eachnodemaintainsinfor mationaboutonlyO(logN)othernodes,andre-s olvesalllookupsviaO(logN)messagesto (DARPA)andtheSpaceandNaval WarfareSystemsCenter, SanDiego, (logN)othernodesforefficientrouting,butp erformancedegradesgracefullywhenthatinfo rmationis importantinprac-ticebecausenodeswilljoin andleave arbitrarily, andconsis-tency ofevenO(logN)statemaybehardto orderforChordtoguaranteecorrect(thoughpo ssiblyslow)routingofqueries;Chordhasa simplealgorithmformaintainingthisinforma tionina ,theproofofitscorrectness, alsoreportsomeinitialresultsonhow theChordroutingprotocolcanbeextendedtota ke intoaccountthephysicalnetworktopology.

3 ReadersinterestedinanapplicationofChorda ndhow Chordbehavesona smallInternettestbedarereferredtoDabeket al.[9].TheresultsreportedbyDabeket presentssimulationssupportingourclaimsab outChord , RELATEDWORKT hreefeaturesthatdistinguishChordfrommany otherpeer-to-peerlookupprotocolsareitssi mplicity, provablecorrectness, clarifycomparisonswithrelatedwork,wewill assumeinthissectiona ,a document, chord -basedapplicationwouldstoreandfinde achvalueat thenodetowhichthevalue s key lookupservice,withhostnamesaskeysandIPad dresses(andotherhostinformation) a key [7]. chord -basedDNSwouldrequirenospecials ervers,whileordi-naryDNSreliesona (NSrecords)thatallowsclientstonavigateth enameserverhierarchy; boundaries; specializedtothetaskoffindingnamedhostso rservices, [5],[6],like chord ,is decentralizedandsymmetricandautomaticall yadaptswhenhostsleave ;instead,itslookupstake , butpreventsit fromguaranteeingretrievalofexistingdocum entsorfromprovidinglow , butitslookupoper-ationrunsinpredictablet imeandalwaysresultsinsuccessordefinitive consistenthashing-like algorithmmapdocumentstonodes,andFreenet- stylequeryrouting[20].

4 Asa result, [4].TheGlobesystem[2]hasa wide-arealocationserviceto hierarchyofgeographical,topologi-cal,ora dministrative domains,effectivelyconstructinga staticworld-widesearchtree,muchlike storedina particularleafdomain,andpointercachespro videsearchshortcuts[25].TheGlobesystemha ndleshighloadonthelogicalrootbypartition ingobjectsamongmulti-plephysicalrootserv ersusinghash-like canachieve scala-bilitywithoutalsoinvolvingany hierarchy, [21]is [26],usedinOceanStore[13],isa chord ,it guaranteesthatqueriesmake nomorethana s mainadvantageoverChordis thatit ensures,subjecttoassumptionsaboutnetwork topology, thatqueriesnevertravel furtherinnet-workdistancethanthenodewher ethekey ,ontheotherhand,is [23]is a prefix-basedlookupprotocolthathaspropert iessimilarto , Pastrytakesintoaccountnetworktopologytor educetheroutinglatency.

5 However, Pastryachievesthisat thecostofa moreelaboratedjoinprotocolwhichinitializ estheroutingta-bleofthenew (forsomefixedd) toimplementa distributedhashtablethatmapskeysontovalu es[22].EachnodemaintainsO(d)state,andthe lookupcostisO(dN1=d). Thus,incontrasttoChord,thestatemaintaine dbya CANnodedoesnotdependonthenetworksizeN, but thelookupcostincreasesfasterthanlogN. Ifd= logN,CANlookuptimesandstorageneedsmatchC hord s. However,CANis notdesignedtovarydasN(andthuslogN) varies,sothismatchwillonlyoccurforthe right Ncorrespondingtothefixedd. robustin s routingproceduremaybethoughtofasa one-dimensionalanalogueoftheGridlocation system(GLS)[15].GLSreliesonreal-worldgeo graphiclocationinformationtorouteitsquer ies;Chordmapsitsnodestoanartificialone-d imensionalspacewithinwhichroutingis carriedoutbyanal-gorithmsimilartoGrid [18]andGnutella[11]providea lookupoperationtofinddataina searchbasedonuser-suppliedkeywords, centralindex, resultingina , basisfora FileSystem(CFS)storesfilesandmeta-datain a peer -to-peersystem,usingChordtolo-catest orageblocks[9].

6 Newanalysistechniqueshave shownthatChord s stabilizationalgorithms(withminormodific ations)maintaingoodlookupperformancedesp itecontinuousfailureandjoiningofnodes[16 ].Chordhasbeenevaluatedasa tooltoserve DNS[7]andtomaintaina distributedpublickey databaseforsecurenameresolution[1].III. SYSTEMMODELC hordsimplifiesthedesignofpeer-to-peersys temsandap-plicationsbasedonit byaddressingthesedifficultproblems: Loadbalance:Chordactsasa distributedhashfunction,spreadingkeyseve nlyoverthenodes;thisprovidesa de-greeofnaturalloadbalance. Decentralization:Chordisfullydistributed :nonodeismoreimportantthanany other. ThisimprovesrobustnessandmakesChordappro priateforloosely-organizedpeer-to-peerap plications.

7 Scalability:Thecostofa Chordlookupgrowsasthelogofthenumberofnod es, requiredto achieve thisscaling. Availability:Chordautomaticallyadjustsit sinternalta-blestoreflectnewlyjoinednode saswellasnodefailures,ensuringthat,barri ngmajorfailuresintheunderlyingnet-work,t henoderesponsiblefora key trueevenif thesystemisina continuousstateofchange. Flexiblenaming:Chordplacesnoconstraintso nthestruc-tureofthekeysit largeamountofflexibilityinhowthey ,theChordlibraryprovidesalookup(key)func tionthatyieldstheIPaddressofthenoderespo nsibleforthekey. Second,theChordsoftwareoneachnodenotifie stheapplicationofchangesinthesetofkeysth atthenodeis responsiblefor. Thisallowstheapplicationsoftwareto,forex ample,move correspondingvaluestotheirnew homeswhena new responsibleforprovidinganydesiredauthent ication,caching,replication,anduser-frie ndly3 ChordChordChordServerFile SystemBlock StoreBlock StoreBlock s ,anapplicationcouldau-thenticatedatabyst oringit undera Chordkey , anapplicationcouldreplicatedatabystoring it undertwo distinctChordkeysderivedfromthedata s application-level goodfoundation.

8 Cooperative mirroring,inwhichmultipleprovidersofcont entcooperatetostoreandserve eachothers ,forexample,bea setofsoftwaredevel-opmentprojects, hostslowersthetotalcostofthesystem,since eachparticipantneedprovidecapacityonlyfo rtheaverageload,notforthatparticipant s realizationofthisideathatusesChordto mapdatablocksontoservers;theapplicationi nteractswithChordachieve loadbalance,datareplication,andlatency-b asedserverselection[9].Time-sharedstorag efornodeswithintermittentconnectiv-ity. If someonewishestheirdatato bealwaysavailable,buttheirserver is onlyoccasionallyavailable,they canoffertostoreothers datawhilethey areconnected,inreturnforhavingtheirdatas toredelsewherewhenthey s namecanserve asa key toidentifythe(live)Chordnoderesponsiblef orstoringthedataitematany ofthesameissuesariseasinthecooperative mirroringapplication, key inthisapplicationcouldbederivedfromthede siredkeywords, , (suchascryptographickeys).

9 Have typicalapplicationis general-purposedistributedhashtablethatm ultipleapplicationsusetoinsertandretriev e ,caching, block, ,hownewnodesjointhesystem,andhow torecover fromthefailure(orplanneddeparture) bothsymmetric(ifAcanroutetoB, thenBcanroutetoA), andtransitive (ifAcanroutetoBandBcanroutetoC, thenAcanroutetoC). ,Chordprovidesfastdistributedcomputation ofa [12],[14], (allnodesreceive roughlythesamenumberofkeys).Alsowithhigh probability, whenanNthnodejoins(orleaves)thenetwork,o nlyaO(1=N)fractionofthekeysaremovedtoa differentlocation thisis clearlytheminimumnecessarytomaintaina Chordnodeneedsonlya smallamountof rout-ing ,a ,eachnodemaintainsinformationaboutonlyO( logN)othernodes,anda lookupre-quiresO(logN) anm-bitidentifierusingSHA-1[10]asa node sidentifierischosenbyhashingthenode s IPaddress,whileakey identifieris producedbyhashingthekey.

10 We willusetheterm key torefertoboththeoriginalkey anditsimageunderthehashfunction, , theterm node theprobabilityoftwo Keykisassignedtothefirstnodewhoseidentif ieris equaltoorfollows(theidentifierof ) calledthesuccessornodeofkeyk, denotedbysuccessor(k). If iden-tifiersarerepresentedasa circleofnumbersfrom0to2m 1,thensuccessor(k)is thefirstnodeclockwisefromk. Inthere-mainderofthispaper, wewillalsorefertotheidentifiercircleasth eChord showsa Chordringwithm= 6. TheChordringhas10nodesandstoresfive ,sokey 10wouldbelocatedat , keys24and30wouldbelocatedatnode32,key 38at node38,andkey 54at (ring)consistingof10nodesstoringfi ve maintaintheconsistenthashingmappingwhena nodenjoinsthenetwork,certainkeysprevious lyassignedton s successornowbecomeassignedton.