Chord
9/Mar 2006
As part of another assignment for the Distributed System course at the University of Sussex we have been doing some research on Chord, a distributed hash lookup primitive, and, in the end, implement part of what is called a chord ring in java.
The idea behind Chord is a research paper in which a distributed protocol for adding nodes to the system, insert data into it, retreive it and drop from the system is described. The way in which nodes lookups and inserts are done is O(log n), so it’s quite efficient. Chord could be look as a layer over which p2p-like applications could be built. One example of this is CFS, the Cooperative File System, a distributed read-only file system.
What we had to do is, basically, implement a simple Ring protocol and a Chord protocol:
Ring protocol: Each node in the system has a pointer to the next one in the ring, so, for instance, if any node wants to do a lookup on some data, it would ask the next one in the ring. If such node does not have it, it would forward that question to the next node in the ring and so forth. This would be O(n)
Chord Protocol: In this version of the protocol, each node not only has a pointer to the next node in the ring, but it also has a pointer to a number of other nodes, not necessarily in a row, so when any node wants to do a lookup, depending on a hash function and the list of pointers to other nodes, it would forward the question to a closer node, where the information is more likely to be stored. This is the way we get a O(log n) algorithm. In fact, there is more than this going on, so I recommend you to have a look at the chord paper again if you are interested.
So, all we had to do is implement both protocols in java and run it in a simulator, as implementing a working solution was too much for an university assignment due in two weeks.
What happens is that using the simulator and programming the whole thing is harder than it sounds, as the simulator itself is lacking some good documentation and have some bugs. In any case, doing it has been fun and interesting as well, as it has let me understand how a distributed system, such as a p2p system, works. So, I recommend anyone interested to have a look at how the protocol works (ie, by reading the Chord paper ;) )
The idea behind Chord is a research paper in which a distributed protocol for adding nodes to the system, insert data into it, retreive it and drop from the system is described. The way in which nodes lookups and inserts are done is O(log n), so it’s quite efficient. Chord could be look as a layer over which p2p-like applications could be built. One example of this is CFS, the Cooperative File System, a distributed read-only file system.
What we had to do is, basically, implement a simple Ring protocol and a Chord protocol:
Ring protocol: Each node in the system has a pointer to the next one in the ring, so, for instance, if any node wants to do a lookup on some data, it would ask the next one in the ring. If such node does not have it, it would forward that question to the next node in the ring and so forth. This would be O(n)
Chord Protocol: In this version of the protocol, each node not only has a pointer to the next node in the ring, but it also has a pointer to a number of other nodes, not necessarily in a row, so when any node wants to do a lookup, depending on a hash function and the list of pointers to other nodes, it would forward the question to a closer node, where the information is more likely to be stored. This is the way we get a O(log n) algorithm. In fact, there is more than this going on, so I recommend you to have a look at the chord paper again if you are interested.
So, all we had to do is implement both protocols in java and run it in a simulator, as implementing a working solution was too much for an university assignment due in two weeks.
What happens is that using the simulator and programming the whole thing is harder than it sounds, as the simulator itself is lacking some good documentation and have some bugs. In any case, doing it has been fun and interesting as well, as it has let me understand how a distributed system, such as a p2p system, works. So, I recommend anyone interested to have a look at how the protocol works (ie, by reading the Chord paper ;) )