The Chord protocol: locating the right node

Perhaps the hardest part of creating a DHT is being able to locate data that isn't saved locally, but rather on a different node. Each node needs to be able to determine the correct location of a key in the network, so that a pair can be saved to or retrieved from the network from anywhere.

One simple solution for this would be to keep information about all nodes at a central location. However, this would make the system centralized and introduce a single point of failure. Here, we instead look for a solution that is decentralized, meaning no specific node's failure can cause the entire system to collapse.

In order to be able to locate different nodes when necessary, nodes on the Chord network keep routing information. This consists of information about certain other nodes in the network.

Specifically, each node keeps information about its successor, as well as an additional set of nodes, called the finger table. To create the finger table for a node n, we make a total of r clockwise jumps from n. The length of jump i is 2i - 1.

As such, each jump will end up at a specific ID on the ring. We then find the node responsible for that ID. That node is either the node with the same ID, if it exists, or the next clockwise node after the ID, if it doesn't. We keep that node as finger i.

The purpose of the finger table will be described later. Here, we should point out that the finger table allows for jumps of exponentially increasing size. This means that each node is likely to have information about other nodes that are roughly on the opposite side of the ring. Such information will allow us to shorten the total search steps required during routing.

Each node also retains information about its predecessor.

Searching for a key

Consider an active Chord network, consisting of various nodes. We know the address of some random node in the network, and we'd like to add some new data, or search for some existing data. In both cases, we first need to ask the node to locate the correct node for the ID of our data.

We contact our node and provide it with the key and value we'd like to search for. The node hashes the key and gets an ID in hash space. Once the node has the ID, how can it determine which node in the network is responsible for that ID?

The node responsible for the ID will be the ID's successor. That is, the first node met if we move clockwise from the ID. To find this successor, we need to first find its predecessor and then ask it for its successor. Since nodes keep information about successors, finding the predecessor is equivalent to finding the node in question.

To find the predecessor, we use the following algorithm.

  1. Set the current node to this node.
  2. Check if the ID is contained between the current node and the current node's successor on the ring. If it is, return the current node.
  3. If it is not, find the node pointed to by the longest finger in the finger table of the current node, which appears to the left of our ID (counter-clockwise) on the ring. Set that node as the current node. Return to step 2.

With this algorithm, we can determine which node is the predecessor to an ID. Once we have this, we simply ask that node for its successor. That node is the one responsible for the ID. We can then ask that node to either save the data, or return any data it might already have.

Joining the network as a new node

You might assume that joining the network is a difficult process, because you'd need to accurately create the successor and finger table pointers. Yet, it turns out that when a node initially joins the network, there are only a few actions that must be completed.

As with searching, to join the network, we must first know the address of some node in the network. This problem is solved by the seed server. Its purpose is to give us the address of some random node when asked. Once we obtain that address, we execute the following algorithm.

  1. Hash this computer's network address to get a node ID.
  2. Ask the seed node for the successor to that node ID.
  3. Set the node's successor to this node. Initialize the finger table, so they all point to this node.
  4. Inform the successor that this node is now its predecessor and ask it to move appropriate keys (those with an ID smaller than or equal to this node's) to this node.

These steps are initially adequate. Although there are still various pointers that are now incorrect or have been invalidated, those will be fixed in time. How this happens is described in the next part.

Network stabilization

The previous protocol works great if every node already has correct pointers for its successor and finger table. However, Chord is a distributed system with nodes joining and leaving constantly. Therefore, a process by which these pointers are kept up to date is necessary.

To keep all pointers up to date, Chord uses a few periodic stabilization routines. These are functions that run every few seconds and ensure that some of the node's pointers are correct, or fix them if they aren't.

These routines can vary based on implementation details. In general, there two main types. The first one corrects successor and predecessor pointers, while the second one corrects finger table pointers.

The general idea for the former is that each node periodically asks its successor for its predecessor. If its predecessor is different than the node itself, we know a new node has joined between this node and its successor. In that case, we simply update this node's successor to that node.

When it comes to keeping fingers up to date, there are various methods. The best ones periodically check for the successor to n + 2i, where i represents the i-th finger, and update the finger table accordingly.

Here, it should be noted that there is a version of Chord that does not use stabilization routines. Instead, when a node joins, the protocol attempts to correctly update all pointers for all existing nodes.

This, however, causes massive network overhead for join operations and also cannot account for abrupt node failures. For this reason, most implementations will instead opt for the stabilization routine approach.

Node failures

The advantage stabilization routines provide becomes even more obvious when dealing with node failures. Since nodes periodically check their pointers, if a node dies, others in the network will sooner or later determine this and update their pointers on their own.

This means that we don't need to do anything else to deal with node failures. The network is self-stabilizing, so we only need to give it time to return to a stable state after nodes fail.

Abrupt node failures, of course, will cause all data stored on a node to be lost. To avoid this, it is necessary to implement some sort of backup system, such that certain keys are not only stored on the successor node to their ID, but also on a few others, thus reducing the probability of data loss in case of node failure.