bnoguchi/node-hash-ring

A Consistent Hashing C++ add-on for node.js

node-hash-ring - Consistent Hashing C++ Add-on for node.js

---

See this blog post for more information.

Installation

Via npm:

$ npm install hash_ring

Via git:

$ git clone http://github.com/bnoguchi/node-hash-ring.git
$ cd node-hash-ring
$ npm run build

Example

var HashRing = require("hash_ring");

// Create a cluster of 3 servers weighted so that 127.0.0.2:8080 stores twice as many 
// keys as 127.0.0.1:8080, and 127.0.0.3:8080 stores 4x as many keys as 127.0.0.1:8080
// and 2x as many keys as 127.0.0.2:8080

var ring = new HashRing({"127.0.0.1:8080": 1, "127.0.0.2:8080": 2, "127.0.0.3:8080":4});
console.log(ring.getNode("users:102") ); // Should be 127.0.0.3:8080

See ./test/test_distribution.js for another example:

$ node test/test_distribution.js

Key Hashing

By default, MD5 is used to hash keys. You can choose another hasher.

var HashRing = require("hash_ring");

var ring = new HashRing({"127.0.0.1:8080": 1, "127.0.0.2:8080": 2, "127.0.0.3:8080":4}, "murmur");

Supported hashers are:

• md5 - the default
• murmur - MurmurHash3

Tests

To run the tests:

$ npm test

License

MIT License

---

Author

Brian Noguchi

node-hash-ring's Issues

Segmentation fault if all weights are set to 0

Run this code:

var HashRing = require('hash_ring');
var obj = {};
obj["A"] = 0;
obj["B"] = 0;
obj["C"] = 0;
var ring = new HashRing(obj);
var instance = ring.getNode("hi to the world");
console.log(instance);

The result will be:

node hashRingTest.js
Segmentation fault

Easily rectified by changing all of the "0"'s to "1"'s but tough to determine the cause. Figured I'd post.

Segmentation fault when node name >= 29 chars

I can reproduce this segmentation fault 100% on Mac OSX

var hash_ring = require("hash_ring");
var ring = new hash_ring({"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa": 1});

i get the following when running node in GDB

Program received signal EXC_BAD_ACCESS, Could not access memory.
Reason: KERN_INVALID_ADDRESS at address: 0x0000000104000000
0x00000001009e61f5 in HashRing::HashRing (this=0x1020004b0, weight_hash=
        {<v8::Handle<v8::Object>> = {val_ = 0x7fff5fbfdf70}, <No data fields>})
    at hash_ring.cc:81

Consistent values of node HashRing and python HashRing

Is there any chance that nodejs hash ring could return exactly the same mapping as python-hashring (http://pypi.python.org/pypi/hash_ring/) module?

I have tested this case and results from each code differs :(

I am badly in need of consistent way doing of hashring in nodejs and python at the same time. I would appreciate any help.

EDIT: So here is how I test it

from nodejs

var HashRing = require("hash_ring");

var ring = new HashRing({
    '0.0.0.1':1,
    '0.0.0.2':2,
    '0.0.0.3':3,
    '0.0.0.4':4,
    '0.0.0.5':5

 });

for (var i=0; i < 1000; i++){
    console.log(i + ' ' + ring.getNode(i ));
}

from python

from hash_ring import HashRing

weights = {
    '0.0.0.1': 1,
    '0.0.0.2': 2,
    '0.0.0.3': 3,
    '0.0.0.4': 4,
    '0.0.0.5': 5
}

ring = HashRing(weights.keys(), weights)

for i in xrange(1000):
    print i, ring.get_node(str(i))

The result set differs in 1/3 keys

$ diff -U 0 test_js.txt test_py.txt | grep -v ^@ | wc -l
     364

Increase node version requirement

Hi Brian,

Could you update the 'package.json' file to allow for node version greater than 0.4.x, the git version is `v0.5.0-pre' and don't pass. Something like

"engines": { "node": ">= 0.4.x" }

should work.

Thanks

Changing precision?

We've been using node-hash-ring very successfully for many years, so thank you for writing this library.

One thing we noticed was that the distributions, while even enough for balancing servers, often aren't even enough for statistical purposes. The use case is using it to distribute millions of user identifiers into a few buckets, and when doing so we sometimes see up to 5% differences in group sizes.

Would you be interested in a PR for an optional argument for tuning the number of rings, to trade off some cpu/memory for more even distribution?

Wrong npm install behavior

$ sudo npm install hash_ring --save
npm http GET https://registry.npmjs.org/hash_ring
npm http 200 https://registry.npmjs.org/hash_ring
npm http GET https://registry.npmjs.org/hash_ring/-/hash_ring-0.2.1.tgz
npm http 200 https://registry.npmjs.org/hash_ring/-/hash_ring-0.2.1.tgz
[email protected] node_modules/hash_ring
$ node
> require('hash_ring')
Error: Cannot find module './build/Release/hash_ring'
$ cat node_modules/hash_ring/index.js 
module.exports = require("./build/Release/hash_ring").HashRing;
$ ls node_modules/hash_ring/
index.js  Makefile  package.json  README.md  src  test  wscript

There is no some build directory,
Need I some manual install actions after npm install or after npm link?
If yes - what actions and why npm install not do it?

undefined symbol: ev_default_loop_ptr on node 0.10

On node 0.10.5 require('hash_ring') fails with

module.js:356
  Module._extensions[extension](this, filename);
                               ^
Error: /tmp/hr/node_modules/hash_ring/build/Release/hash_ring.node: undefined symbol: ev_default_loop_ptr
    at Module.load (module.js:356:32)
    at Function.Module._load (module.js:312:12)
    at Module.require (module.js:364:17)
    at require (module.js:380:17)
    at Object.<anonymous> (/tmp/hr/node_modules/hash_ring/index.js:1:80)
    at Module._compile (module.js:456:26)
    at Object.Module._extensions..js (module.js:474:10)
    at Module.load (module.js:356:32)
    at Function.Module._load (module.js:312:12)
    at Module.require (module.js:364:17)

Works fine with 0.8.23

Latest npm install index.js has the wrong path

currently reads: module.exports = require("./build/default/hash_ring").HashRing;

had to modify it to: module.exports = require("./build/Release/hash_ring").HashRing;