Chord project
|
|
"The Chord project aims to build a scalable, symmetric and robust distributed systems using peer-to-peer ideas. The basis for much of our work is the Chord distributed hash table lookup primitive. Chord is completely decentralized and can find data using only <math>log(N)<math> messages, where N is the number of nodes in the system. Chord's lookup mechanism is probably robust in the face of frequent node failures and re-joins."
Chord is being developed at MIT and the current Chord source code can be downloaded and used under the MIT license.
Overview
Chord_ring.GIF
Using the Chord lookup protocol, node keys are arranged in a circle. The circle cannot have more than <math>2^m<math> nodes. The ring can have ids/keys ranging from 0 to <math>2^m - 1<math>. In the above diagram <math>m = 3<math>.
In the above diagram the green circles represent nodes. The black points represent keys. IDs and keys are assigned using what is known as consistent hashing. The SHA-1 algorithm is the base hashing function for consistent hashing.
Each node has a successor and a predecessor. The successor to a node or key is the next node in the identifier circle when you move clockwise. The predecessor of a node or key is the next node in the id circle when you move counter-clockwise. For example, the successor of node 1 is node 3, and the predecessor of node 1 is node 0.
The pseudocode to find the successor node of an id is given below:
// ask node n to find the successor of id n.find_successor(id) if (id <math>\in<math> (n, successor]) return successor; else // forward the query around the circle return successor.find_successor(id);
The pseudocode to stabilize the chord ring/circle after node joins and departures is a follows:
// create a new Chord ring. n.create() predecessor = nil; successor = n; // join a Chord ring containing node n0. n.join(n') predecessor = nil; successor = n'.find_successor(n); // called periodically. verifies n’s immediate // successor, and tells the successor about n. n.stabilize() x = successor.predecessor; if (x <math>\in<math>(n, successor)) successor = x; successor.notify(n); // n' thinks it might be our predecessor. n.notify(n') if (predecessor is nil or n'<math>\in<math>(predecessor, n)) predecessor = n';
External links
- The Chord Project (http://www.pdos.lcs.mit.edu/chord)
- Paper proposing Chord: "Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications" (http://www.pdos.lcs.mit.edu/papers/chord:sigcomm01/)it:Progetto Chord