Chord

Chord is a DHT (see previous post). The basic idea is that it provides a single function: lookup(key). The keys are generated from the SHA-1 hash function, which more or less guarantees their randomness. Each node is also given a key using the SHA-1 hash function. The nodes are arranged in a circle by hash value, and each node "stores" all keys that are larger than its own hash value, but smaller than the hash values of all other nodes (with wrapping).

The way queries are distributed through the network is with pointers from one node to various neighbors. Each node has a successor, as well as a list of "fingers". The fingers point to nodes that are halfway around the DHT, a quarter of the way around, an eighth, and so forth. To process a query, a node chooses the finger with the greatest hash value that does not exceed the value of the requested key, and forwards the request to that node. The request then propagates through the chain until it reaches the correct node.

Note that in order to maintain correctness, the fingers need not exist, and only the successor pointers need to be accurate. The successors and fingers are updated by a periodic stabilization process.

They tested the network in simulation, with 1000 nodes, and then again in practice, with 10. In both cases, they found that it helped to have several virtual nodes at each real machine, as a way of spreading out the keys across more nodes. They found that the number of hops that a query required was indeed O(log(n)), and that the network was indeed resilient to massive numbers of node failures.

The main complaint I have about Chord is that they expect applications to build redundancy on top of this system, probably by creating n keys for each piece of data that they want to store (where n is the number of copies), and then either 1) looking them up one at a time until one lookup succeeds or 2) looking them all up at once, and taking the first result. The first one wastes a lot of the application's time in the case of a failure, and the second one wastes a lot of bandwidth.

I think it would be interesting to implement Chord with redundancy built in to it. Not only would applications not have to worry about implementing this on top of Chord, but there might be good performance characteristics as well. Instead of searching for the one and only copy of a given key, you could search for the copy of the key that can be found by searching the "closest" finger. Alternatively, you could store link quality data, and transmit your query over the link with the lowest latency. Or, if there is data being stored at the nodes, perhaps you wish to find the copy of the data with the highest bandwidth to the origin of the request. But all of these would need some sort of built-in redundancy.