Chord A Scalable Peer to peer Lookup Service for Internet Applications Ion Stoica Robert Morris David Karger M Frans Kaashoek Hari Balakrishnan from Bo Han for CMSC 818T Fall 06 based on Robert Morris s talk on SIGCOMM 2001 Introduction z z z z Core operation in peer to peer systems is to efficiently locate the node that stores a particular data item Chord is a scalable distributed protocol for lookup in a dynamic peer to peer system with frequent node arrivals and departures Only one operation given a key it maps the key onto a node Simplicity provable correctness and provable performance The lookup problem N1 N2 Internet Key title Value MP3 data Publisher N4 N5 N3 N6 Client Lookup title Centralized lookup Napster N1 N2 SetLoc title N4 Publisher N 4 Key title Value MP3 data N3 DB N9 N6 N7 Client Lookup title N8 Simple but O N states and a single point of failure Flooded queries Gnutella N1 Publisher N N2 N3 Lookup title Client 4 Key title Value MP3 data N6 N7 N8 N9 Robust but worst case O N messages per lookup Routed queries Freenet Chord etc N1 Publisher N2 N3 N4 Client Lookup title Key title Value MP3 data N6 N7 N9 N8 Related Work z Freenet Clarke Sandberg Wiley Hong z CAN Ratnasamy Francis Handley Karp Shenker z Pastry Rowstron Druschel z Tapestry Zhao Kubiatowicz Joseph z Chord emphasizes simplicity Design Objectives z z z z z Load Balance Distributed hash function spreads keys evenly over the nodes Consistent hashing Decentralization Fully distributed Robustness Scalability Lookup grows as a log of number of nodes Availability Automatically adjusts internal tables to reflect changes Flexible Naming No constraints on key structure Applications z z z Lookup key algorithm that yields the IP address of the node responsible for the key Notify the application of changes in the set of keys that the node is responsible for Example applications Cooperative Mirroring Time shared storage Distributed indexes Large Scale combinatorial search Routing challenges z Define a useful key nearness metric z Keep the hop count small z Keep the routing tables small z Stay robust despite rapid changes Chord properties z Efficient O log N messages per lookup z Scalable O log N states per node z z Robust survives massive failures join or leave O log2 N messages An Nth node joins or leaves only an O 1 N keys are moved to a different location Proofs are in paper tech report Assuming no malicious participants Chord overview z Provides peer to peer hash lookup Lookup key IP address Chord does not store the data z How does Chord route lookups z How does Chord maintain routing tables z How does Chord cope with changes in membership Chord IDs z m bit identifier space for both keys and nodes z Key identifier SHA 1 key z Node identifier SHA 1 IP address z Both are uniformly distributed z How to map key IDs to node IDs Consistent hashing Karger 97 Key 5 Node 105 K5 K20 N105 Circular 7 bit ID space N32 N90 K80 A key is stored at its successor node with next higher ID Basic lookup N120 N10 Where is key 80 N105 N90 has K80 K80 N90 N60 N32 Simple lookup algorithm Lookup my id key id n my successor if my id n key id call Lookup id on node n next hop else return my successor done Correctness depends only on successors Finger table allows log N time lookups 1 8 1 16 1 32 1 64 1 128 N80 Every node knows m other nodes in the ring Finger i points to successor of n 2i 1 N120 112 1 8 1 16 1 32 1 64 1 128 N80 Each node knows more about portion of circle close to it Lookup with fingers Lookup my id key id look in local finger table for highest node n s t my id n key id if n exists call Lookup id on node n next hop else return my successor done Lookups take O log N hops N5 N10 N110 K19 N20 N99 N32 Lookup K19 N80 N60 Joining linked list insert N25 N36 1 Lookup 36 N40 K30 K38 1 Each node s successor is correctly maintained 2 For every key k node successor k is responsible for k Join 2 N25 2 N36 sets its own successor pointer N36 N40 K30 K38 Initialize the new node finger table Join 3 N25 3 Set N25 s successor pointer N36 N40 K30 K38 Update finger pointers of existing nodes Join 4 N25 4 Copy keys 26 36 from N40 to N36 N36 K30 N40 K38 Transferring keys Stabilization Protocol z z z z z To handle concurrent node joins fails leaves Keep successor pointers up to date then verify and correct finger table entries Incorrect finger pointers may only increase latency but incorrect successor pointers may cause lookup failure Nodes periodically run stabilization protocol Won t correct a Chord system that has split into multiple disjoint cycles or a single cycle that loops multiple times around the identifier space Failures might cause incorrect lookup N120 N113 N10 N102 N85 Lookup 90 N80 N80 doesn t know correct successor so incorrect lookup Solution successor lists z Each node knows r immediate successors z After failure will know first live successor z Correct successors guarantee correct lookups z Guarantee is with some probability Can choose r to make probability of lookup failure arbitrarily small Choosing the successor list length z Assume 1 2 of nodes fail z P successor list all dead 1 2 r I e P this node breaks the Chord ring Depends on independent failure z P no broken nodes 1 1 2 r N r 2log N makes prob 1 1 N Lookup with fault tolerance Lookup my id key id look in local finger table and successor list for highest node n s t my id n key id if n exists call Lookup id on node n next hop if call failed remove n from finger table return Lookup my id key id else return my successor done Simulation overview z Quick lookup in large systems z Low variation in lookup costs z Robust despite massive failure z Iterative implementation z 10 000 nodes No of keys range from 105 to 106 Experiments confirm theoretical results No of Keys per Node Chord lookup cost is O log N Constant is 1 2 Failed Lookups Failed Nodes Failed Lookups as function of Fail Join Rate Chord Summary z Chord provides peer to peer hash lookup z Efficient O log n messages per lookup z Robust as nodes fail and join z Good primitive for peer to peer systems http www pdos lcs mit edu chord Misc z z Sound theoretical work about 1173 citations Has been used in CFS SOSP 2001 and Ivy OSDI 2002 z Ring Partitions might pose a problem z Scalability of Stabilization protocol How often does the stabilization procedure need to run How to balance consistence and network overhead z Virtualized ID space lacks locality characteristics Physical topology of the underlying …