Calculating expected finger table entries for virtual ring distributed systems like Chord and Cassandra

Here’s a block of code I wrote to print out finger tables for Chord-like distributed hash tables. Just update the ‘nodes’ variable and the m-value to adjust to any system. Runs happily in Node.js 4.4.0.

// calculating finger tables for Chord-like distributed hash table.

// the size of the ring, as 2^m;
var m=9, ringSize = Math.pow(2,m);

// the nodes we know about
var nodes = [1, 12, 123, 234, 345, 456, 501]; 

// just make sure it's sorted
nodes = nodes.sort( (a,b) => a-b );

console.log('the finger tables for a ', ringSize,'-virtual-node system');
console.log('========');
console.log('nodes: ', nodes);

// calculate the finger table for each node
nodes.forEach(n => {

 var fingerTable = [];
 i = 1;
 for(var x = 0; x < m; x++) {
 var nodeId = (n + i) % ringSize;
 // find the node after nodeId; 
 var ftEntry = nodes.filter(x => x > nodeId).concat(nodes)[0];
 fingerTable.push(ftEntry);
 i = i << 1;
 }
 
 console.log(n + ':', fingerTable);
});
Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s