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 ; 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 -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 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 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 nodes, ranging from to. Some of these nodes will map to machines or keys while others 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 ; however, normally there are "holes" in the sequence. For example, the successor of node 153 may be node 167 ; 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 is the first node whose ID equals to or follows in the identifier circle, denoted by. Every key is assigned to its successor node, so looking up a key is to query.
Since the successor of a node may disappear from the network, each node records a whole segment of the circle adjacent to it, i.e., the nodes preceding it and the 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, i.e. to find. 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 query time where 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 entries, recall that is the number of bits in the hash key. The entry of node will contain. The first entry of finger table is actually the node's immediate successor. Every time a node wants to look up a key, it will pass the query to the closest successor or predecessor of in its finger table, 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.

Node join

Whenever a new node joins, three invariants should be maintained :
  1. Each node's successor points to its immediate successor correctly.
  2. Each key is stored in.
  3. Each node's finger table should be correct.
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 :
  1. Initialize node .
  2. Notify other nodes to update their predecessors and finger tables.
  3. The new node takes over its responsible keys from its successor.
The predecessor of can be easily obtained from the predecessor of . As for its finger table, there are various initialization methods. The simplest one is to execute find successor queries for all entries, resulting in initialization time. A better method is to check whether entry in the finger table is still correct for the entry. This will lead to. The best method is to initialize the finger table from its immediate neighbours and make some updates, which is.

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:
With high probability, Chord contacts nodes to find a successor in an -node network.
Suppose node wishes to find the successor of key. Let be the predecessor of. We wish to find an upper bound for the number of steps it takes for a message to be routed from to. Node will examine its finger table and route the request to the closest predecessor of that it has. Call this node. If is the entry in 's finger table, then both and are at distances between and from along the identifier circle. Hence, the distance between and along this circle is at most. Thus the distance from to is less than the distance from to : the new distance to is at most half the initial distance.
This process of halving the remaining distance repeats itself, so after steps, the distance remaining to is at most ; in particular, after steps, the remaining distance is at most. 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 such nodes. Because the message always advances by at least one node, it takes at most steps for a message to traverse this remaining distance. The total expected routing time is thus.
If Chord keeps track of predecessors/successors, then with high probability, if each node has probability of 1/4 of failing, find_successor and find_predecessor will return the correct nodes
Simply, the probability that all nodes fail is, 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

;Definitions for 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
// Yes, that should be a closing square bracket to match the opening parenthesis.
// It is a half closed interval.
if id ∈
return n0.find_successor
// search the local table for the highest predecessor of id
n.closest_preceding_node
for i = m downto 1 do
if then
return finger
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
predecessor := nil
successor := n'.find_successor
// 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 ∈ then
successor := x
successor.notify
// n' thinks it might be our predecessor.
n.notify
if predecessor is nil or 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