I have decided to write down reviews of all the papers I read from now on. This is for the sole purpose of improving my understanding of the paper, help me put my thoughts down in a coherent fashion and improve my writing skills.
This paper was published in SIGCOMM 2001 and has been cited more than 9000 times. I will go over the basic algorithm and system model first and finally note down my evaluation.
Lets get down some definitions first:
successor(k) - the successor node of key k is the node whose identifier is equal to or follows k in identifier space.
n.successor - successor of a node n is the next node in the identifier space. successor(0) = 1, successor(1) = 3, successor(3) = 0. Similarly we have n.predecessor
In the figure the green dots represent nodes.
m - number of bits in the key/node identifier. Both nodes and keys are mapped to the same identifier space.
Each node maintains m entries in a routing table called finger table.
The ith finger of node n or the ith entry in the finger table of node n is denoted by n.finger[i].node
The ith entry in the finger table of node n = s = successor(n + 2i-1) where 1 <= i <= m.
n.successor = n.finger[1].node
n.finger[i].start = (n + 2i-1) mod m
n.finger[i].interval = [n.finger[i].start, n.finger[i+1].start)
In the right figure, m = 3. The finger table of node 0 will have:
1st entry: 0.finger[1].start = (0 + 20) mod m = 1 => successor(1) = 1
2nd entry: 0.finger[2].start = (0 + 21) mod m = 2 => successor(2) = 3
3rd entry: 0.finger[3].start = (0 + 22) mod m = 4 => successor(4) = 0
0.finger[4].start = (0 + 23) mod 8 = 0
1st interval: [1, 2)
2nd interval: [2, 4)
3rd interval: [4, 0)
See the paper for pseudocode for routing and joining.
The finger table also contains the keys that the node is responsible for storing and the node's successor and predecessor. The finger table entry include both the Chord identifier and the IP address, port number of the node.
Here is how the finger table is updated:
Node 6 joins -
Node 1 leaves -
See the stabilization algorithm in this ppt
Here is how I envision Chord will work in a P2P system:
When a new node joins a system it contacts a well known server to help it find its successor. When the node has been integrated into the system it must allocate some space for storing the key value store. If it wants to share something, the cryptographic hash (SHA-1, HMAC) of the file name it wants to share must be stored in the system as a key. The value corresponding to this key will be its IP address and port number. The system should store multiple copies of this (key, value) pair for high availability. This might be done using a different hash function. You can have multiple Chord networks using a different hash functions. You can also simply store each (key, value) pair in designated node and it k successors.
If someone wishes to download this file they must calculate a hash of the search query to get the key and see if it exists in the system. If it does, the value will tell them the node IP address which has the data. If they download the file, their own IP address should get added to all the copies of the (key, value) pair.
I suppose this is how magnet links work too. Though Bittorrents are based on a different DHT model called Kademlia which uses a different routing algorithm but is also based on consistent hashing like Chord. I will be posting about it soon.
An obvious disadvantage of this way of storing data is that we cannot perform a widcard searches like *.mp3. I don't know how that might be done.
For a system with N nodes Chord proves that it can resolve all lookups via O(log N) messages by maintaining information about O(log N) other nodes (in a finger table). It also requires O(log^2 N) messages to re-establish the routing invariants and finger tables in case any node joins or leaves the system.
P2P systems have very high churn rates. The large number of messages that need to be exchanged and the changes required in finger table every time a node joins or leaves the system, in my opinion, makes it infeasible in practice. It would be better to use Chord for the Ultrapeer network only, since they have low churn rate.
This paper was published in SIGCOMM 2001 and has been cited more than 9000 times. I will go over the basic algorithm and system model first and finally note down my evaluation.
Lets get down some definitions first:
successor(k) - the successor node of key k is the node whose identifier is equal to or follows k in identifier space.
n.successor - successor of a node n is the next node in the identifier space. successor(0) = 1, successor(1) = 3, successor(3) = 0. Similarly we have n.predecessor
In the figure the green dots represent nodes.
m - number of bits in the key/node identifier. Both nodes and keys are mapped to the same identifier space.
Each node maintains m entries in a routing table called finger table.
The ith finger of node n or the ith entry in the finger table of node n is denoted by n.finger[i].node
The ith entry in the finger table of node n = s = successor(n + 2i-1) where 1 <= i <= m.
n.successor = n.finger[1].node
n.finger[i].start = (n + 2i-1) mod m
n.finger[i].interval = [n.finger[i].start, n.finger[i+1].start)
In the right figure, m = 3. The finger table of node 0 will have:
1st entry: 0.finger[1].start = (0 + 20) mod m = 1 => successor(1) = 1
2nd entry: 0.finger[2].start = (0 + 21) mod m = 2 => successor(2) = 3
3rd entry: 0.finger[3].start = (0 + 22) mod m = 4 => successor(4) = 0
0.finger[4].start = (0 + 23) mod 8 = 0
1st interval: [1, 2)
2nd interval: [2, 4)
3rd interval: [4, 0)
See the paper for pseudocode for routing and joining.
The finger table also contains the keys that the node is responsible for storing and the node's successor and predecessor. The finger table entry include both the Chord identifier and the IP address, port number of the node.
Here is how the finger table is updated:
Node 6 joins -
Node 1 leaves -
See the stabilization algorithm in this ppt
Here is how I envision Chord will work in a P2P system:
When a new node joins a system it contacts a well known server to help it find its successor. When the node has been integrated into the system it must allocate some space for storing the key value store. If it wants to share something, the cryptographic hash (SHA-1, HMAC) of the file name it wants to share must be stored in the system as a key. The value corresponding to this key will be its IP address and port number. The system should store multiple copies of this (key, value) pair for high availability. This might be done using a different hash function. You can have multiple Chord networks using a different hash functions. You can also simply store each (key, value) pair in designated node and it k successors.
If someone wishes to download this file they must calculate a hash of the search query to get the key and see if it exists in the system. If it does, the value will tell them the node IP address which has the data. If they download the file, their own IP address should get added to all the copies of the (key, value) pair.
I suppose this is how magnet links work too. Though Bittorrents are based on a different DHT model called Kademlia which uses a different routing algorithm but is also based on consistent hashing like Chord. I will be posting about it soon.
An obvious disadvantage of this way of storing data is that we cannot perform a widcard searches like *.mp3. I don't know how that might be done.
For a system with N nodes Chord proves that it can resolve all lookups via O(log N) messages by maintaining information about O(log N) other nodes (in a finger table). It also requires O(log^2 N) messages to re-establish the routing invariants and finger tables in case any node joins or leaves the system.
P2P systems have very high churn rates. The large number of messages that need to be exchanged and the changes required in finger table every time a node joins or leaves the system, in my opinion, makes it infeasible in practice. It would be better to use Chord for the Ultrapeer network only, since they have low churn rate.
It make me understand the finger table!! Thanks!!
ReplyDelete