↑ arvau

Wikipedia / 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. The 2001 Chord paper won an ACM SIGCOMM Test of Time award in 2011.

Subsequent research by Pamela Zave has shown that the original Chord protocol (as specified in the 2001 SIGCOMM paper, the 2001 Technical report, the 2002 PODC paper, and the 2003 TON paper ) can mis-order the ring, produce several rings, and break the ring. A corrected version of the protocol prevents these errors, without imposing additional overhead.

Overview

-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.

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; 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.

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

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), 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. (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):

  1. Each node's successor points to its immediate successor correctly.

  2. .

  3. Each node's finger table should be correct.

To satisfy these invariants, a predecessor:

  1. (the predecessor and the finger table).

  2. Notify other nodes to update their predecessors and finger tables.

  3. The new node takes over its responsible keys from its successor.

.

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:

  • Stabilize(): n asks its successor for its predecessor p and decides whether p should be ns successor instead (this is the case if p recently joined the system).

  • Notify(): notifies ns successor of its existence, so it can change its predecessor to n

  • Fix_fingers(): updates finger tables

Potential uses

  • Cooperative Mirroring: A load balancing mechanism by a local network hosting information available to computers outside of the local network. This scheme could allow developers to balance the load between many computers instead of a central server to ensure availability of their product.

  • Time-shared storage: In a network, once a computer joins the network its available data is distributed throughout the network for retrieval when that computer disconnects from the network. As well as other computers' data is sent to the computer in question for offline retrieval when they are no longer connected to the network. Mainly for nodes without the ability to connect full-time to the network.

  • Distributed Indices: Retrieval of files over the network within a searchable database. e.g. P2P file transfer clients.

  • Large scale combinatorial searches: Keys being candidate solutions to a problem and each key mapping to the node, or computer, that is responsible for evaluating them as a solution or not. e.g. Code Breaking

  • Also used in wireless sensor networks for reliability

Proof sketches

-node network.

is at most half the initial distance.

.

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

, 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

  1. Definitions for pseudocode

    1. successor: the next node from the node in question on the identifier ring

    2. predecessor: the previous node from the node in question on the identifier ring

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
    finger[next] := find_successor(n+2next-1);

// called periodically. checks whether predecessor has failed.
n.check_predecessor()
    if predecessor has failed then
        predecessor := nil

See also

References