consistent hash ring in node.js
- Posted: 8 months ago
- Tags:consistent, hashring, node.js
- 0 comments
If you ever need to create a consistent hash ring in node.js, this may help you. This is compatible with redis-rb's dht algorithm. This is not well tested yet, but in preliminary tests it is working good. Thanks to this stackoverflow post for the crc32 algo. Future improvements may include parts of this re-done as a c module for added speed. Currently I am not using this per inbound request, only once per server start, so speed is less of an immediate priority. Enjoy!
this.ring = {};
this.sorted_keys = [];
this.generateRing = function(servers) {
for(var j = 0; j < servers.length; j++) {
this.addServerToRing(servers[j]);
}
}
this.addServerToRing = function(server) {
for(r = 0; r < 160; r++) {
key = this.crc32("redis://"+server+"/0:"+r);
this.ring[key] = server;
this.sorted_keys.push(key);
}
this.sorted_keys.sort(function (a, b) {
return a-b;
});
}
this.getServer = function(key_query) {
key = this.crc32(key_query);
index = this.ringSearch(key);
return this.ring[this.sorted_keys[index]];
}
this.ringSearch = function(val) {
var upper = this.sorted_keys.length - 1;
var begin = upper;
var lower = 0;
var k = 0;
while(lower <= upper) {
k = parseInt(((lower + upper) / 2),10);
idx = this.sorted_keys[k];
if(idx == val) {
return k;
} else if ( idx > val ) {
upper = k - 1;
} else {
lower = k + 1;
}
}
if(upper < 0) {
upper = begin;
}
return upper;
}
this.crc32 = (function() {
function utf8encode(str) {
var utf8CharCodes = [];
for (var i = 0, len = str.length, c; i < len; ++i) {
c = str.charCodeAt(i);
if (c < 128) {
utf8CharCodes.push(c);
} else if (c < 2048) {
utf8CharCodes.push((c >> 6) | 192, (c & 63) | 128);
} else {
utf8CharCodes.push((c >> 12) | 224, ((c >> 6) & 63) | 128, (c & 63) | 128);
}
}
return utf8CharCodes;
}
var cachedCrcTable = null;
function buildCRCTable() {
var table = [];
for (var i = 0, j, crc; i < 256; ++i) {
crc = i;
j = 8;
while (j--) {
if ((crc & 1) == 1) {
crc = (crc >>> 1) ^ 0xEDB88320;
} else {
crc >>>= 1;
}
}
table[i] = crc >>> 0;
}
return table;
}
function getCrcTable() {
if (!cachedCrcTable) {
cachedCrcTable = buildCRCTable();
}
return cachedCrcTable;
}
return function(str) {
var utf8CharCodes = utf8encode(str), crc = -1, crcTable = getCrcTable();
for (var i = 0, len = utf8CharCodes.length, y; i < len; ++i) {
y = (crc ^ utf8CharCodes[i]) & 0xFF;
crc = (crc >>> 8) ^ crcTable[y];
}
return (crc ^ -1) >>> 0;
};
})();
I have been hearing about 
