Published on June 19, 2007
Chord - A Distributed Hash Table: Chord - A Distributed Hash Table Yimei Liao Outline: Outline Lookup problem in Peer-to-Peer systems and Solutions Chord Algorithm Consistent Hashing Scalable Key Location Node joins Stabilization Summary Peer-to-Peer Systems: Peer-to-Peer Systems Peer-to-Peer System: self-organizing system of equal, autononous entities (peers) decentralized resource usage decentraliced self-organization where to store? where to get? Solutions centralized servers flooding search distributed Hash Tables Solutions to lookup problem: Solutions to lookup problem centralized servers Maintain the current location of data items in a central server Search complexity O(1) Central server becomes crucial Best for simple and small applications flooding search Broadcast a request for an item among the nodes No additional routing informations High bandwidth consumption Search complexity O(N2) Results are not guaranteed Solutions to lookup problem: Solutions to lookup problem distributed hash tables A global view of data distributed among many nodes. Mapping nodes and data items into a common address space Each DHT node manages a small number of references to other nodes Queries are routed via a small number of nodes to the target node Load for retrieving items should be balanced equally among all nodes Robust against random failure and attacks Provides a definitive answer about results Chord Algorithm – Consistent Hashing: Chord Algorithm – Consistent Hashing supports just one operation: given a key, it maps the key onto a node. Consistent Hashing Assign each node and key an m-bit identifier using a base hash function such as SHA-1 Identifiers are ordered in an identifier circle modulo 2m (Chord ring) Key k is assigned to the first node whose identifier is equal to or follows k. Chord Algorithm – Consistent Hashing: Chord Algorithm – Consistent Hashing identifier space : m=3 node key 0 1 3 1 2 6 1 identifier circle Chord Algorithm – Simple Key Lookup: Chord Algorithm – Simple Key Lookup Simple Key Lookup 1 2 6 Queries are passed around the circle via successor pointers Requires traversing all Nodes to find the appropriate mapping successor(1) = 3 successor(3) = 6 successor(6) = 0 successor(0) = 1 Node 0 sends a query for key 6 Chord Algorithm – Scalable Key Location: Chord Algorithm – Scalable Key Location Finger Table Each node n maintains a routing table with up to m entries The ith entry in the table at node n contains the identifier of the first node s that succeeds n by at least 2i-1 on the identifier circle.(s = successor(n+2i-1)). s is called the ith finger of node n. Definition of variables for node n Chord Algorithm – Scalable Key Location: Chord Algorithm – Scalable Key Location Finger table m = 3, each node n maintains at most 3 entries finger table keys 0+20 0+21 0+22 1 2 4 [1,2) 3 3 6 [2,4) [4,0) finger table keys 3+20 3+21 3+22 4 5 7 [4,5) 6 6 0 [5,7) [7,3) 1 2 finger table keys 6+20 6+21 6+22 7 0 2 [7,0) 0 0 3 [0,2) [2,6) 5 Chord Algorithm – Scalable Key Location: Chord Algorithm – Scalable Key Location Pseudocode to find the successor node of an identifier Walk clockwise to find the node which precedes id and whose successor succeeds id Start with the mth finger of node n See if it comes between node n and the id, if not, check the m-1th finger until we find one wich does. This is the closest node preceding id among all the fingers of n Find id’s successor by finding the immediate predecessor of the id Chord Algorithm – Scalable Key Location: Chord Algorithm – Scalable Key Location id=5 n=7 finger table keys finger table keys 1 2 finger table keys 6 4 Successor 0 Predecessor 4 3 Successor 3 Predecessor 7 Successor Predecessor 0 finger table keys Successor Predecessor 3 7 4 7 7 successor(5) = 7 4 O(logN) Chord Algorithm - Node joins: Chord Algorithm - Node joins Invariants to be preserve Each node’s successor is correctly maintained For every key k, node successor(k) is responsible for k It is desirable for the finger tables to be correct Tasks to be performed by Chord Initialize the predecessor and fingers of node n Update the fingers and predecessor of existing nodes to reflect the addition of n Notify the higher layer software so that it can transfer state associated with keys that node n is now responsible for Chord Algorithm - Node joins: Chord Algorithm - Node joins finger table keys finger table keys 1 2 finger table keys 6 4 Successor 0 Predecessor 3 5 Successor 3 Predecessor 6 Successor 6 Predecessor 0 finger table keys 7 7 3 Successor Predecessor 7 3 Initializing fingers and predecessor find_successor(6); Chord Algorithm - Node joins: Chord Algorithm - Node joins finger table keys 5 finger table keys 5 1 2 finger table keys 6 4 Successor 0 Predecessor 3 5 Successor 3 Predecessor 6 Successor 7 Predecessor 0 5 finger table keys 7 7 3 Successor Predecessor 7 3 5 Updating fingers of existing nodes 3 3 P = find_predecessor(n-2i-1) i = 1, P = find_predecessor(4) i = 2, P = find_predecessor(3) i = 3, P = find_predecessor(1) 3 O(log2N) Chord Algorithm - Node joins: Chord Algorithm - Node joins finger table keys 6 finger table keys 5 1 2 finger table keys 6 4 Successor 0 Predecessor 3 5 Successor 3 Predecessor 6 Successor 6 Predecessor 0 5 finger table keys 7 7 3 Successor Predecessor 7 3 5 Transferring Keys Chord Algorithm – node joins: Chord Algorithm – node joins Pseudocode for the node join operation Chord Algorithm - Stabilization: Chord Algorithm - Stabilization Stabilization Correctness and performance Keep node‘s successor pointers up to date Use successor pointers to verify correct finger table entries Chord Algorithm - Stabilization: Chord Algorithm - Stabilization Pseudocode for stabilization Join does not make the rest of the network aware of n Every node runs stabilize periodically, to verify the successor Use successor pointers to update finger tables. Node n asks its successor for the successor’s predecessor x. See if x should be n’s successor instead. (happens if x recently joined the system) Notify n’s successor of n’s exist. Successor changes its predecessor to n if it knows no closer predecessor than n. Chord Algorithm – Node Failure: Chord Algorithm – Node Failure Node Failure Successor-list If successor fails, replaces it with the first live entry in the list Later run stabilize to correct finger table and successor-list Summary: Summary Characteristics of Chord Load balance distributed hash table Decentralization fully distributed Scalability cost of lookup grows logarithmic Availability automatically adjusts internal tables Flexible naming no constrains on the structure of the keys References: References I. Stoica, R. Morris, D. Karger, F. Kaashoek, and H. Balakrishnan. Chord: A scalable Peer-To-Peer lookup service for internet applications. In Proceedings of the 2001 ACM SIGCOMM Conference, pages 149–160, 2001. R. Steinmetz, K. Wehrle (Edt.): 'Peer-to-Peer Systems and Applications', LNCS 3485, Springer, Chapter 7-8, 2005. http://www.wikipedia.org http://www.google.com Slide23: Thank You Questions?