Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Ion Stoica, Robert Morris, David Karger,M. Frans Kaashoek, Hari BalakrishnanMIT and Berkeleypresented by Daniel FigueiredoChord: A Scalable Peer-to-peer Lookup Service for Internet ApplicationsChord: A Scalable Peer-to-peer Lookup Service for Internet Applications presentation based on slides by Robert Morris (SIGCOMM’01)OutlineOutline Motivation and background Consistency caching Chord Performance evaluation Conclusion and discussionMotivationMotivationHow to find data in a distributed file sharing system? Lookup is the key problemInternetPublisherKey=“LetItBe”Value=MP3 dataLookup(“LetItBe”)N1N2N3N5N4Client?Centralized SolutionCentralized Solution Requires O(M) state Single point of failureInternetPublisherKey=“LetItBe”Value=MP3 dataLookup(“LetItBe”)N1N2N3N5N4ClientDB Central server (Napster)Distributed Solution (1)Distributed Solution (1) Worst case O(N) messages per lookupInternetPublisherKey=“LetItBe”Value=MP3 dataLookup(“LetItBe”)N1N2N3N5N4Client Flooding (Gnutella, Morpheus, etc.)Distributed Solution (2)Distributed Solution (2) Routed messages (Freenet, Tapestry, Chord, CAN, etc.)InternetPublisherKey=“LetItBe”Value=MP3 dataLookup(“LetItBe”)N1N2N3N5N4Client Only exact matchesRouting ChallengesRouting Challenges Define a useful key nearness metric Keep the hop count small Keep the routing tables “right size” Stay robust despite rapid changes in membershipAuthors claim: Chord: emphasizes efficiency and simplicityChord OverviewChord Overview Provides peer-to-peer hash lookup service: Lookup(key) IP address Chord does not store the data How does Chord locate a node? How does Chord maintain routing tables? How does Chord cope with changes in membership?Chord propertiesChord properties Efficient: O(Log N) messages per lookup N is the total number of servers Scalable: O(Log N) state per node Robust: survives massive changes in membership Proofs are in paper / tech report Assuming no malicious participantsChord IDsChord IDs m bit identifier space for both keys and nodes Key identifier = SHA-1(key)Key=“LetItBe” ID=60SHA-1IP=“198.10.10.1”ID=123SHA-1 Node identifier = SHA-1(IP address) Both are uniformly distributed How to map key IDs to node IDs?Consistent Hashing [Karger 97]Consistent Hashing [Karger 97] A key is stored at its successor: node with next higher IDN32N90N123 K20K5Circular 7-bitID space0IP=“198.10.10.1”K101K60Key=“LetItBe”Consistent HashingConsistent Hashing Every node knows of every other node requires global information Routing tables are large O(N) Lookups are fast O(1)N32N90N1230Hash(“LetItBe”) = K60N10N55Where is “LetItBe”? “N90 has K60”K60Chord: Basic LookupChord: Basic LookupN32N90N1230Hash(“LetItBe”) = K60N10N55Where is “LetItBe”? “N90 has K60”K60 Every node knows its successor in the ring requires O(N) time“Finger Tables”“Finger Tables” Every node knows m other nodes in the ring Increase distance exponentiallyN8080 + 20N112N96N1680 + 2180 + 2280 + 2380 + 2480 + 2580 + 26“Finger Tables”“Finger Tables” Finger i points to successor of n+2iN120N8080 + 20N112N96N1680 + 2180 + 2280 + 2380 + 2480 + 2580 + 26Lookups are FasterLookups are Faster Lookups take O(Log N) hopsN32N10N5N20N110N99N80N60Lookup(K19)K19Joining the RingJoining the Ring Three step process: Initialize all fingers of new node Update fingers of existing nodes Transfer keys from successor to new node Less aggressive mechanism (lazy finger update): Initialize only the finger to successor node Periodically verify immediate successor, predecessor Periodically refresh finger table entriesJoining the Ring - Step 1Joining the Ring - Step 1 Initialize the new node finger table Locate any node p in the ring Ask node p to lookup fingers of new node N36 Return results to new nodeN361. Lookup(37,38,40,…,100,164)N60N40N5N20N99N80Joining the Ring - Step 2Joining the Ring - Step 2 Updating fingers of existing nodes new node calls update function on existing nodes existing nodes can recursively update fingers of other nodesN36N60N40N5N20N99N80Joining the Ring - Step 3Joining the Ring - Step 3 Transfer keys from successor node to new node only keys in the range are transferred Copy keys 21..36from N40 to N36K30K38N36N60N40N5N20N99N80K30K38Handing FailuresHanding Failures Failure of nodes might cause incorrect lookupN120N113N102N80N85N10Lookup(90) N80 doesn’t know correct successor, so lookup fails Successor fingers are enough for correctnessHandling FailuresHandling Failures Use successor list Each node knows r immediate successors After failure, will know first live successor Correct successors guarantee correct lookups Guarantee is with some probability Can choose r to make probability of lookup failure arbitrarily smallEvaluation OverviewEvaluation Overview Quick lookup in large systems Low variation in lookup costs Robust despite massive failure Experiments confirm theoretical resultsCost of lookupCost of lookup Cost is O(Log N) as predicted by theory constant is 1/2Number of NodesAverage Messages per LookupRobustnessRobustness Simulation results: static scenario Failed lookup means original node with key failed (no replica of keys) Result implies good balance of keys among nodes!RobustnessRobustness Simulation results: dynamic scenario Failed lookup means finger path has a failed node 500 nodes initially average stabilize( ) call 30s 1 lookup per second (Poisson) x join/fail per second (Poisson)Current implementationCurrent implementation Chord library: 3,000 lines of C++ Deployed in small Internet testbed Includes: Correct concurrent join/fail Proximity-based routing for low delay (?) Load control for heterogeneous nodes (?) Resistance to spoofed node IDs (?)StrengthsStrengths Based on theoretical work (consistent hashing) Proven performance in many different aspects “with high probability” proofs Robust (Is it?)WeaknessWeakness NOT that simple (compared to CAN) Member joining
View Full Document
Unlocking...