Decentralized Hash Tables & Chord in P2P Networks

In P2P systems, decentralized hash tables play a crucial role in addressing challenges with peers joining and leaving. The evolution from centralized solutions like Napster to distributed hash tables like Chord highlights the importance of decentralization, load-balancing, scalability, and availability in P2P networks. Explore how Chord offers a scalable P2P lookup service and efficient routing geometries to enhance system properties.

• P2P Networks
• Decentralized Systems
• Distributed Hash Tables
• Chord Protocol
• Scalability

nix_ara Follow

Uploaded on Feb 15, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. P2P: Distributed Hash Tables Chord + Routing Geometries Nirvan Tyagi CS 6410 Fall16

2. Peer-to-peer (P2P)

3. Peer-to-peer (P2P) Decentralized! Hard to coordinate with peers joining and leaving

4. Peer-to-peer (P2P) Napster (1999)

5. Peer-to-peer (P2P) Napster (1999)

6. Peer-to-peer (P2P) Napster (1999) Problem -Centralized index server

7. Peer-to-peer (P2P) Napster (1999) Problem -Centralized index server Solution -Distributed hash table

8. Distributed Hash Tables (DHT) Hash table k0 v0 k1 k2 k3 k4 k5 v1 v2 v3 v4 v5

9. Distributed Hash Tables (DHT) Hash table k0 v0 k1 k2 k3 k4 k5 v1 v2 v3 v4 v5 k0 v0 k1 v1 k4 k5 v4 v5 k2 k3 v2 v3

10. Distributed Hash Tables (DHT) Desirable Properties Decentralization Load-balancing Scalability Availability k0 v0 k1 v1 k4 k5 v4 v5 k2 k3 v2 v3

11. Outline Chord Specific DHT protocol for P2P systems Simple, efficient DHT Routing Geometry Effect of different DHT protocols on desirable system properties

12. Chord A scalable P2P lookup service for internet applications Ion Stoica, Robert Morris, David Karger Frans Kaashoek, Hari Balakrishnan

13. Chord - Overview How to assign keys to peers? Hash table k0 v0 k1 k2 k3 k4 k5 v1 v2 v3 v4 v5 k0 v0 k1 v1 k4 k5 v4 v5 k2 k3 v2 v3

14. Chord - Overview Hash table k0 v0 k1 k2 k3 k4 k5 v1 v2 v3 v4 v5

15. k5 Chord - Overview k4 Hash table k0 v0 k1 k2 k3 k4 k5 v1 v2 v3 v4 v5 k0 k1 k3 k2

16. k5 Chord - Overview k0 v0 k4 k1 v1 Hash table k4 k5 v4 v5 k0 v0 k1 k2 k3 k4 k5 v1 v2 v3 v4 v5 k0 k1 k3 k2 k3 v2 v3 k2

17. Chord - Overview 0 2m-1 1 Identifier ring over hash space 2m 2m-1

18. Chord - Overview 0 2m-1 1 = node Identifier ring over hash space 2m = key node id = hash( node ) key id = hash( key ) 2m-1

19. Chord - Overview 0 2m-1 1 = node Identifier ring over hash space 2m = key node id = hash( node ) key id = hash( key ) successor(id) finger table for node at id i finger 1 2 j node id succ(i) succ(i+ 2) succ(i+ 2 j -1) 2m-1

20. Chord - Overview 0 = node Identifier ring = key 12 4 8

21. Chord - Overview 0 = node Identifier ring = key 12 4 8

22. Chord - Overview 0 = node Identifier ring = key finger 1 2 3 4 node id succ(i) succ(i+ 2) succ(i+ 22) succ(i+ 23) 12 4 8

23. Chord - Overview 0 = node Identifier ring = key finger 1 2 3 4 node id succ(4) succ(4 + 2) succ(4 + 22) succ(4 + 23) 12 4 8

24. Chord - Overview 0 = node Identifier ring = key finger 1 2 3 4 node id 5 8 8 1 12 4 8

25. find_successor(id): p = find_predecessor(id) return p.successor Chord - Lookup find_predecessor(id): n = self while id not between (n, n.successor]: n = n.closest_preceding_finger(id) return n 0 Identifier ring finger 1 2 3 4 node id 5 8 8 1 12 4 finger 1 2 3 4 node id 11 11 1 1 8

26. find_successor(id): p = find_predecessor(id) return p.successor Chord - Lookup find_predecessor(id): n = self while id not between (n, n.successor]: n = n.closest_preceding_finger(id) return n 0 Identifier ring finger 1 2 3 4 node id 5 8 8 1 12 4 lookup(10) finger 1 2 3 4 node id 11 11 1 1 8

27. find_successor(id): p = find_predecessor(id) return p.successor Chord - Lookup find_predecessor(id): n = self while id not between (n, n.successor]: n = n.closest_preceding_finger(id) return n 0 Identifier ring finger 1 2 3 4 node id 5 8 8 1 12 4 lookup(10) follow finger 3 to node id 8 finger 1 2 3 4 node id 11 11 1 1 8

28. find_successor(id): p = find_predecessor(id) return p.successor Chord - Lookup find_predecessor(id): n = self while id not between (n, n.successor]: n = n.closest_preceding_finger(id) return n 0 Identifier ring finger 1 2 3 4 node id 5 8 8 1 12 4 lookup(10) follow finger 3 to node id 8 node id 8 identifies as predecessor of id 10 finger 1 2 3 4 node id 11 11 1 1 8

29. find_successor(id): p = find_predecessor(id) return p.successor Chord - Lookup find_predecessor(id): n = self while id not between (n, n.successor]: n = n.closest_preceding_finger(id) return n 0 Identifier ring finger 1 2 3 4 node id 5 8 8 1 12 4 lookup(10) follow finger 3 to node id 8 node id 8 identifies as predecessor of id 10 complete lookup at successor of node id 8 finger 1 2 3 4 node id 11 11 1 1 8

30. find_successor(id): p = find_predecessor(id) return p.successor Chord - Lookup find_predecessor(id): n = self while id not between (n, n.successor]: n = n.closest_preceding_finger(id) return n 0 Identifier ring Hops? finger 1 2 3 4 node id 5 8 8 1 Each finger lookup halves distance to key O(log N) 12 4 lookup(10) follow finger 3 to node id 8 node id 8 identifies as predecessor of id 10 complete lookup at successor of node id 8 finger 1 2 3 4 node id 11 11 1 1 8

31. Chord - Joins + Stabilization 0 Identifier ring join(): self.predecessor = null self.successor = find_successor(self) stabilize(): p = self.successor.predecessor if p between (self, self.successor): self.successor = p self.successor.notify(self) notify(n): if self.predecessor == null || n between (self.predecessor, self): self.predecessor = n 12 4 8

32. Chord - Joins + Stabilization 0 Identifier ring join(): self.predecessor = null self.successor = find_successor(self) stabilize(): p = self.successor.predecessor if p between (self, self.successor): self.successor = p self.successor.notify(self) notify(n): if self.predecessor == null || n between (self.predecessor, self): self.predecessor = n 12 4 predecessor = 4 successor = 8 predecessor = 5 successor = 11 8

33. Chord - Joins + Stabilization 0 Identifier ring join(): self.predecessor = null self.successor = find_successor(self) stabilize(): p = self.successor.predecessor if p between (self, self.successor): self.successor = p self.successor.notify(self) notify(n): if self.predecessor == null || n between (self.predecessor, self): self.predecessor = n 12 4 predecessor = 4 successor = 8 join(), self = 6 predecessor = 5 successor = 11 predecessor = null successor = 8 8

34. Chord - Joins + Stabilization 0 Identifier ring join(): self.predecessor = null self.successor = find_successor(self) stabilize(): p = self.successor.predecessor if p between (self, self.successor): self.successor = p self.successor.notify(self) notify(n): if self.predecessor == null || n between (self.predecessor, self): self.predecessor = n 12 4 predecessor = 4 successor = 8 stabilize() predecessor = 5 6 successor = 11 predecessor = null successor = 8 8

35. Chord - Joins + Stabilization 0 Identifier ring join(): self.predecessor = null self.successor = find_successor(self) stabilize(): p = self.successor.predecessor if p between (self, self.successor): self.successor = p self.successor.notify(self) notify(n): if self.predecessor == null || n between (self.predecessor, self): self.predecessor = n 12 4 predecessor = 4 successor = 8 6 stabilize() predecessor = 5 6 successor = 11 predecessor = null 5 successor = 8 8

36. Chord - Joins + Stabilization 0 Identifier ring join(): self.predecessor = null self.successor = find_successor(self) stabilize(): p = self.successor.predecessor if p between (self, self.successor): self.successor = p self.successor.notify(self) notify(n): if self.predecessor == null || n between (self.predecessor, self): self.predecessor = n 12 4 predecessor = 4 successor = 6 Outcomes of incomplete stabilization: 1. Lookup unaffected 2. Fingers out-dated, successors correct -> lookup slow but correct 3. Successors in lookup region still stabilizing -> lookup fails predecessor = 5 successor = 8 predecessor = 6 successor = 11 8

37. Chord - Failure + Replication 0 Identifier ring Maintain list of k successors Keys replicated on all k successors 12 4 predecessor = [4, 1] successor = [6, 8] predecessor = [5, 4] successor = [8, 11] predecessor = [6, 5] successor = [11, 1] 8

38. Load balance Failure resilience Lookup path length Lookup latency

39. Load balance Failure resilience Lookup path length Lookup latency

40. Load balance Failure resilience Lookup path length Lookup latency

41. Load balance Failure resilience Thoughts on Chord performance? Lookup path length Lookup latency

42. Load balance Failure resilience Lookup path length Lookup latency

43. Load balance Improvements to Chord routing and failure resilience in future works Pastry + Bamboo Failure resilience Lookup path length Lookup latency

44. The Impact of DHT Routing Geometry on Resilience and Proximity K. Gummadi, R. Gummadi, S. Gribble S. Ratnasamy, S. Shenker, I. Stoica

45. DHT Routing Geometries Ring (Chord) Tree (Tapestry, PRR) Hypercube (CAN) Butterfly (Viceroy) XOR (Kademlia) Hybrid (Pastry, Bamboo)

46. Proximity + Resilience Proximity -Pick routes through physically nearby peers, reducing latency Resilience -Continue to route requests despite network churn and failure

47. Proximity + Resilience Proximity -Pick routes through physically nearby peers, reducing latency Resilience -Continue to route requests despite network churn and failure Flexibility Neighbor selection -options in selecting which peers to keep in routing table Route selection -options in selecting where to route to given a destination

48. Proximity + Resilience Proximity -Pick routes through physically nearby peers, reducing latency Resilience -Continue to route requests despite network churn and failure Flexibility Neighbor selection -options in selecting which peers to keep in routing table Route selection -options in selecting where to route to given a destination Flexibility in neighbor selection -> good proximity Flexibility in route selection -> good resilience

49. DHT Routing Geometries Ring (Chord) Tree (Tapestry, PRR) Hypercube (CAN) Butterfly (Viceroy) XOR (Kademlia) Hybrid (Pastry, Bamboo)

50. DHT Routing Geometries - Tree XXX 0XX 00X 000 001 010 011 100 101 110 111

Load More ...