The Chord protocol: a distributed hash space

In this discussion page, we'll focus on the Chord protocol itself. We'll describe what the protocol does and give certain details on how it achieves this.

At its core, the challenge faced with creating a distributed hash table can be described in two parts:

  • How can we distribute the hash table between multiple nodes?
  • How can we, from any one node, find the node that contains or should contain a key?

In this page, we'll mostly restrict ourselves to the former question. For details on the latter, visit the next discussion page.

Distributing a hash table

To begin with, we'll look at how Chord distributes a hash table to multiple systems. Chord refers to each system in the network as a node. Before anything else, we must recognize the need for node identifiers. If we can't tell nodes apart from each other, we'll find it much harder to determine which node should contain which data.

In a computer network, each system is identified by its address. As such, we already have a piece of information that is different between nodes.

The Chord protocol takes this a step further, by creating an additional identifier for each node. We'll call this the node ID. The interesting thing about node IDs is that they exist in the hash space! In other words, we create these IDs by hashing the address of the node. The resulting ID has certain properties, the usefulness of which will become apparent once we look at the way the protocol routes requests.

The Chord ring

Imagine taking a hash table's array and connecting the two ends of it. You now have a ring with the same properties as the hash table itself. The only difference is that the last spot lies directly next to the first one.

This is the idea behind Chord's hash space. To generalize, we won't think of it as a hash table. Instead, think of 2r points, arranged in a circle. Number those points from 0 to 2r - 1 in clockwise ascending order, starting at any one point. You'll notice point n has neighbors n - 1 and n + 1, with the exception of 2r - 1 and 0, which have each other as neighbors.

This virtual ring makes up Chord's hash space and is the basis for all operations in the Chord protocol.

Nodes as part of the hash space

To get an ID for a node, we use a hash function on the node's network address. The only requirement for the hash function is that it returns an integer in the range [0, 2r - 1], where r is the number of bits for each ID in the hash space.

This means the node gets an ID that falls somewhere on the ring, corresponding to one of the points in it. Therefore, the node itself becomes part of the hash space.

Distributing keys

Now that we have defined our hash space and placed our nodes inside of it, we can move on to determining a split of it between the existing nodes.

The Chord protocol states that any node is responsible for the range [p + 1, n] on the hash space, where n is the node's ID and p is the first node met if we traverse the ring counter-clockwise from n.

As a result, whenever we need to insert a new pair into our DHT, we hash the key. If the resulting hash k is in the range [p + 1, n], we store the pair on node n. More rigorously, we find the range [p + 1, n] into which k belongs and store the pair on n.

Similarly, if we want to retrieve a pair, we hash the key, get the hash value k and ask node n, such that k ∈ [p + 1, n].

In fact, this is the reason the protocol is called Chord. Each node in the network is responsible for a specific chord of the ring.

With this, we have answered the first question concerning the creation of a DHT.

Key distribution

When using a hash function, we prefer keys to be distributed evenly over the hash space. If this doesn't happen, it can cause collisions that result in operations being slower than expected.

With Chord, one such instance can be observed when the network consists of few nodes that are close to each other in hash space. Take, for instance, the sample execution from the adding data tutorial:

╔═══════════════╦═══════════════╦══════════╗
║   Successors  ║  Predecessors ║   Keys   ║
╠═══════════════╬═══════════════╬══════════╣
║  2503 -> 8230 ║ 15626 <- 8230 ║  2503: 1 ║
╠═══════════════╬═══════════════╬══════════╣
║ 8230 -> 15626 ║  8230 <- 2503 ║  8230: 1 ║
╠═══════════════╬═══════════════╬══════════╣
║ 15626 -> 2503 ║ 2503 <- 15626 ║ 15626: 7 ║
╚═══════════════╩═══════════════╩══════════╝
Total keys: 9
Stability: 100.00%

In this example, we use a ring with 14-bit IDs. This means there are 16,384 possible IDs in the network. As we saw, every node is responsible for the IDs between the previous node ID and its own node ID.

Let's calculate which ID ranges each of the nodes in this example is responsible for.

  • 2503: 15627 to 2503, total (16383 - 15626) + 2504 = 3261 IDs.
  • 8230: 2504 to 8230, total 8230 - 2503 = 5727 IDs.
  • 15626: 8231 to 15626, total 15626 - 8230 = 7396 IDs.

Notice that 15626 is responsible for a much larger number of IDs than the other two. Assuming the hash function is equally likely to output any ID, it is not surprising that more keys are stored in node 15626.

Yet, 7 as opposed to 1 for each of the others is still more disproportional than expected. If you'd like to get a better example, simply run E-Chord with many nodes and insert a large number of keys. Observe the nodes which are responsible for really small intervals, as opposed to those responsible for large ones. You'll find that the former store a significantly smaller number of IDs than the latter.