Chord a scalable peer to-peer lookup service for internet applications
1 like445 views
CHORD is a peer-to-peer lookup protocol that allows nodes in a distributed system to locate the node responsible for a given key in logarithmic time. It uses a distributed hash table where each node is assigned responsibility for a partition of the key space, and nodes store routing information for other nodes in the system in a "finger table" to efficiently route lookup requests. CHORD provides scalability, fault tolerance and load balancing as the number of nodes grows while requiring only O(log N) messages to perform lookups.
Chord a scalable peer to-peer lookup service for internet applications
- 1. CHORD: A SCALABLE PEER-TO-PEER LOOKUP SERVICE FOR INTERNET CSCI-565: DISTRIBUTED COMPUTING Henri M.B. van den Bulk 1
- 2. CHORD: A SCALABLE PEER-TO-PEER LOOKUP SERVICE FOR INTERNET APPLICATIONS 2 ABOUT CHORD node = lookup(key), IP address Variant of Distributed consistent Hashing Table (DHT) Its a protocol and algorithm Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan ACM SIGCOMM 2001, San Deigo, CA, August 2001
- 3. CHORD: A SCALABLE PEER-TO-PEER LOOKUP SERVICE FOR INTERNET APPLICATIONS 3 WHATS DIFFERENT ABOUT CHORD? Nodes dont know all other nodes, only routing info about a few nodes In a steady state only maintain O(log N) other nodes (routing table), but its table is dynamic P (join/leave messages) = High => O(log 2 N) messages (lookup) Simplicity = O(log N), counting to other nodes Provable Correctness, Provable Performance - Degrades gracefully when topology changes No need for dedicated nodes or hierarchy, e.g. like DNS
- 4. CHORD: A SCALABLE PEER-TO-PEER LOOKUP SERVICE FOR INTERNET APPLICATIONS 4 CORE PROPERTIES The distributed hash function spreads keys evenly, which provides natural load balancing There are no speci鍖c roles for nodes which makes it decentralized When the number (N) of nodes grow its scalable as the cost is O(log N) The dynamic nature of adjusting the the internal tables causes an increased availability of the system. The key-space is 鍖at and does not impose a naming scheme, which provides for a 鍖exible naming approach
- 5. CHORD: A SCALABLE PEER-TO-PEER LOOKUP SERVICE FOR INTERNET APPLICATIONS 5 HASH TABLE GENERAL HUX FINN BB-8 LUKE SKYWALKER HAN SOLO Hash = f(key)Keys COROLLIA ARTORIAS JAKKU STARKILLER BASE 19 BBY Values
- 6. CHORD: A SCALABLE PEER-TO-PEER LOOKUP SERVICE FOR INTERNET APPLICATIONS 6 DISTRIBUTED HASH TABLE key mod n, n: number of buckets identi鍖es the bucket KEY SPACE BUCKET 1 BUCKET 2 BUCKET 3 K1 KnKn/3 K2n/3 value = hash(key) 1 2 Costly when we change the buckets
- 7. CHORD: A SCALABLE PEER-TO-PEER LOOKUP SERVICE FOR INTERNET APPLICATIONS 7 CHORDS CONSISTENT HASHING ALGORITHM 0 1 2 3 module 2m m=2 0-(2m - 1) HASH(IP) SUCCESSOR(3)=0 K(1) SUCCESSOR(1)=1 SUCCESSOR(2)=3 K(2) K(3) ID: M-BIT INTEGER KEY DOMAIN
- 8. CHORD: A SCALABLE PEER-TO-PEER LOOKUP SERVICE FOR INTERNET APPLICATIONS 8 FINGER TABLE 0 1 4 6 3 2 5 7 ID IP Inter val succ 2 1.2.3.4 [2,3) 3 3 2.3.4.5 [3,5) 3 5 6.7.8.9 [5,1) 0 0 6.9.1.1 1 A A B C D B C D
- 9. CHORD: A SCALABLE PEER-TO-PEER LOOKUP SERVICE FOR INTERNET APPLICATIONS 9 LOOKUP 1 8 42 62 32 21 51 75 K(73) LOOKUP(73)
- 10. CHORD: A SCALABLE PEER-TO-PEER LOOKUP SERVICE FOR INTERNET APPLICATIONS 10 NODE JOINING & STABILIZING 0 1 4 6 3 2 5 7 N 1 2 1 2 3 3 4 4 5 5
- 11. CHORD: A SCALABLE PEER-TO-PEER LOOKUP SERVICE FOR INTERNET APPLICATIONS 11 CHALLENGES Stabilization rate is critical and can be an issue when there is a signi鍖cant amount of churn in joining/leaving Network latency and topology are not taking into account, e.g. distance between nodes
- 12. CHORD: A SCALABLE PEER-TO-PEER LOOKUP SERVICE FOR INTERNET APPLICATIONS 12 REAL WORLD APPLICATIONS Cooperative File System (CFS) OverCite UsenetDHT
- 13. QUESTIONS? Audience 13CHORD: A SCALABLE PEER-TO-PEER LOOKUP SERVICE FOR INTERNET APPLICATIONS