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 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.
[1] The 2001 Chord paper[1] won an ACM SIGCOMM Test of Time award in 2011.
[2] Subsequent research by Pamela Zave has shown that the original Chord algorithm (as specified in the 2001 SIGCOMM paper,[1] the 2001 Technical report,[3] the 2002 PODC paper,[4] and the 2003 TON paper [5]) can mis-order the ring, produce several rings, and break the ring.
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.
Using the Chord lookup protocol, nodes and keys are arranged in an identifier circle that has at most
Some of these nodes will map to machines or keys while others (most) will be empty.
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.
The core usage of the Chord protocol is to query a key from a client (generally a node as well), i.e. to find
The basic approach is to pass the query to a node's successor, if it cannot find the key locally.
To avoid the linear search above, Chord implements a faster search method by requiring each node to keep a finger table containing up to
, it will pass the query to the closest successor or predecessor (depending on the finger table) of
in its finger table (the "largest" one on the circle whose ID is smaller than
), 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
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 simplest one is to execute find successor queries for all
The best method is to initialize the finger table from its immediate neighbours and make some updates, which is
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
We wish to find an upper bound for the number of steps it takes for a message to be routed from
will examine its finger table and route the request to the closest predecessor of
This process of halving the remaining distance repeats itself, so after
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
steps for a message to traverse this remaining distance.
