Chord (peer-to-peer)

In computing, Chord is a protocol and algorithm for a peer-to-peer distributed hash table. A distributed hash table stores key-value pairs by assigning keys to different computers (known as "nodes"); a node will store the values for all the keys for which it is responsible. Chord specifies how keys are assigned to nodes, and how a node can discover the value for a given key by first locating the node responsible for that key.
Chord is one of the four original distributed hash table protocols, along with CAN, Tapestry, and Pastry. It was introduced in 2001 by Ion Stoica, Robert Morris, David Karger, Frans Kaashoek, and Hari Balakrishnan, and was developed at MIT.
Overview.
Nodes and keys are assigned an formula_1-bit "identifier" using "consistent hashing". The SHA-1 algorithm is the base hashing function for consistent hashing. Consistent hashing is integral to the robustness and performance of Chord because both keys and nodes (in fact, their IP addresses) are uniformly distributed in the same identifier space with a negligible possibility of collision. Thus, it also allows nodes to join and leave the network without disruption. In the protocol, the term "node" is used to refer to both a node itself and its identifier (ID) without ambiguity. So is the term "key".
Using the Chord lookup protocol, nodes and keys are arranged in an identifier circle that has at most formula_2 nodes, ranging from formula_3 to formula_4. (formula_1 should be large enough to avoid collision.) Some of these nodes will map to machines or keys while others (most) will be empty.
Each node has a "successor" and a "predecessor". The successor to a node is the next node in the identifier circle in a clockwise direction. The predecessor is counter-clockwise. If there is a node for each possible ID, the successor of node 0 is node 1, and the predecessor of node 0 is node formula_4; however, normally there are "holes" in the sequence. For example, the successor of node 153 may be node 167 (and nodes from 154 to 166 do not exist); in this case, the predecessor of node 167 will be node 153.
The concept of successor can be used for keys as well. The "successor node" of a key formula_7 is the first node whose ID equals to formula_7 or follows formula_7 in the identifier circle, denoted by formula_10. Every key is assigned to (stored at) its successor node, so looking up a key formula_7 is to query formula_10.
Since the successor (or predecessor) of a node may disappear from the network (because of failure or departure), each node records a whole segment of the circle adjacent to it, i.e., the formula_13 nodes preceding it and the formula_13 nodes following it. This list results in a high probability that a node is able to correctly locate its successor or predecessor, even if the network in question suffers from a high failure rate.
Protocol details.
Basic query.
The core usage of the Chord protocol is to query a key from a client (generally a node as well), i.e. to find formula_10. The basic approach is to pass the query to a node's successor, if it cannot find the key locally. This will lead to a formula_16 query time where formula_17 is the number of machines in the ring.
Finger table.
To avoid the linear search above, Chord implements a faster search method by requiring each node to keep a "finger table" containing up to formula_1 entries, recall that formula_1 is the number of bits in the hash key. The formula_20 entry of node formula_21 will contain formula_22. The first entry of finger table is actually the node's immediate successor (and therefore an extra successor field is not needed). Every time a node wants to look up a key formula_7, it will pass the query to the closest successor or predecessor (depending on the finger table) of formula_7 in its finger table (the "largest" one on the circle whose ID is smaller than formula_7), until a node finds out the key is stored in its immediate successor.
With such a finger table, the number of nodes that must be contacted to find a successor in an "N"-node network is formula_26. (See proof below.)
Node join.
Whenever a new node joins, three invariants should be maintained (the first two ensure correctness and the last one keeps querying fast):
To satisfy these invariants, a "predecessor" field is maintained for each node. As the successor is the first entry of the finger table, we do not need to maintain this field separately any more. The following tasks should be done for a newly joined node formula_21:
The predecessor of formula_21 can be easily obtained from the predecessor of formula_31 (in the previous circle). As for its finger table, there are various initialization methods. The simplest one is to execute find successor queries for all formula_1 entries, resulting in formula_33 initialization time. A better method is to check whether formula_20 entry in the finger table is still correct for the formula_35 entry. This will lead to formula_36. The best method is to initialize the finger table from its immediate neighbours and make some updates, which is formula_26.
Stabilization.
To ensure correct lookups, all successor pointers must be up to date. Therefore, a stabilization protocol is running periodically in the background which updates finger tables and successor pointers.
The stabilization protocol works as follows:
Proof sketches.
With high probability, Chord contacts formula_26 nodes to find a successor in an formula_17-node network.
Suppose node formula_21 wishes to find the successor of key formula_7. Let formula_42 be the predecessor of formula_7. We wish to find an upper bound for the number of steps it takes for a message to be routed from formula_21 to formula_42. Node formula_21 will examine its finger table and route the request to the closest predecessor of formula_7 that it has. Call this node formula_48. If formula_48 is the formula_20 entry in formula_21's finger table, then both formula_48 and formula_42 are at distances between formula_54 and formula_55 from formula_21 along the identifier circle. Hence, the distance between formula_48 and formula_42 along this circle is at most formula_54. Thus the distance from formula_48 to formula_42 is less than the distance from formula_21 to formula_48: the new distance to formula_42 is at most half the initial distance.
This process of halving the remaining distance repeats itself, so after formula_65 steps, the distance remaining to formula_42 is at most formula_67; in particular, after formula_68 steps, the remaining distance is at most formula_69. Because nodes are distributed uniformly at random along the identifier circle, the expected number of nodes falling within an interval of this length is 1, and with high probability, there are fewer than formula_68 such nodes. Because the message always advances by at least one node, it takes at most formula_71 steps for a message to traverse this remaining distance. The total expected routing time is thus formula_26.
If Chord keeps track of formula_73 predecessors/successors, then with high probability, if each node has probability of 1/4 of failing, find_successor (see below) and find_predecessor (see below) will return the correct nodes
Simply, the probability that all formula_13 nodes fail is formula_75, which is a low probability; so with high probability at least one of them is alive and the node will have the correct pointer.
Pseudocode.
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)
 // Yes, that should be a closing square bracket to match the opening parenthesis.
 // It is a half closed interval.
 if id ∈ (n, successor] then
 return successor
 else
 // forward the query around the circle
 n0 := closest_preceding_node(id)
 return n0.find_successor(id)
 // search the local table for the highest predecessor of id
 n.closest_preceding_node(id)
 for i = m downto 1 do
 if (finger[i] ∈ (n, id)) then
 return finger[i]
 return n
The pseudocode to stabilize the chord ring/circle after node joins and departures is as follows:
 // create a new Chord ring.
 n.create()
 predecessor := nil
 successor := n
 // join a Chord ring containing node n'.
 n.join(n')
 predecessor := nil
 successor := n'.find_successor(n)
 // called periodically. n asks the successor
 // about its predecessor, verifies if n's immediate
 // successor is consistent, and tells the successor about n
 n.stabilize()
 x = successor.predecessor
 if x ∈ (n, successor) then
 successor := x
 successor.notify(n)
 // n' thinks it might be our predecessor.
 n.notify(n')
 if predecessor is nil or n'∈(predecessor, n) then
 predecessor := n'
 // called periodically. refreshes finger table entries.
 // next stores the index of the finger to fix
 n.fix_fingers()
 next := next + 1
 if next > m then
 next := 1
 
 // called periodically. checks whether predecessor has failed.
 n.check_predecessor()
 if predecessor has failed then
 predecessor := nil