search

3rd-Eden / node-hashring

hashring is a consistent hashing algorithm for Node.js that is compatible with libketama and python's hash_ring package
MIT License
352 stars 57 forks source link

readme

HashRing

The HashRing module provides consistent hashing that is compatible with the original libketama library that was developed at last.fm. In addition to beeing compatible with libketama it's also compatible with the hash_ring module for Python. See the compatiblity section of the API for more details on this.

Build status

BuildStatus

Installation

The advised installation of module is done through the Node package manager (npm).

npm install hashring --save

The --save parameter tells npm that it should automatically add the module to the dependencies field in your package.json.

Usage

var HashRing = require('hashring');

The HashRing constructor is designed to handle different argument types as a consistent hash ring can be use for different use cases. You can supply the constructor with:

String

A single server, possible, but pointless in most cases if you only use one server, then done use the HashRing at all, it only adds overhead.

var ring = new HashRing('127.0.0.1:11211');

Array

Multiple servers for the HashRing.

var ring = new HashRing(['127.0.0.1:11211', '127.0.0.2:11211']);

Object

An Object where the keys of the Object are the servers and the value can be a Number and it will be seen as weight for server. The value can also be an Object. Where the key can be a weight or a vnode.

Weights or vnodes are used to give servers a bigger distribution in the HashRing. For example you have 3 servers where you want to distribute your keys over but not all servers are equal in capacity as 2 of those machines have 200mb of memory and the other has 3.2 gig of memory. The last server is substantially bigger and there for should receive a greater distrubtion in the ring.

For a rule of thumb use the amount of memory as weight:

var HashRing = require('hashring');

var ring = new HashRing({
  '127.0.0.1:11211': 200,
  '127.0.0.2:11211': { weight: 200 }, // same as above
  '127.0.0.3:11211': 3200
});

If you want create a server with multiple vnodes (virtual nodes):

var HashRing = require('hashring');

var ring = new HashRing({
  '127.0.0.1:11211': { vnodes: 50 },
  '127.0.0.2:11211': { vnodes: 200 },
  '127.0.0.3:11211': { vnodes: 100 }
});

Algorithm

With the second argument you can configure the algorithm that is used to hash the keys. It defaults to md5 and can only contain values that are accepted in Node's crypto API. Alternatively you can supply it with a function for a custom hasher. But do note that the hashValue will be calculated on the result.

Options

'use strict';

// require the module, it returns a HashRing constructor
var HashRing = require('hashring');

// Setup hash rings with your servers, in this example I just assume that all
// servers are equal, and we want to bump the cache size to 10.000 items.
var ring = new HashRing([
    '127.0.0.1',
    '127.0.0.2',
    '127.0.0.3',
    '127.0.0.4'
  ], 'md5', {
    'max cache size': 10000
  });

// Now we are going to get some a server for a key
ring.get('foo bar banana'); // returns 127.0.0.x

// Or if you might want to do some replication scheme and store/fetch data from
// multiple servers
ring.range('foo bar banana', 2).forEach(function forEach(server) {
  console.log(server); // do stuff with your server
});

// Add or remove a new a server to the ring, they accept the same arguments as
// the constructor
ring.add('127.0.0.7').remove('127.0.0.1');

API's Table of Contents

HashRing.continuum()

Generates the continuum of server a.k.a as the Hash Ring based on their weights and virtual nodes assigned.

HashRing.get(key)

Find the correct node for which the key is closest to the point after what the given key hashes to.

returns: The matching server address.

HashRing.range(key, size, unique)

Returns a range of servers. Could be useful for replication.

returns: The array of servers that we found.

HashRing.swap(*from, to)

Hotswap identical servers with each other. This doesn't require the cache to be completely nuked and the hash ring distribution to be re-calculated.

Please note that removing the server and adding a new server could potentially create a different distribution.

HashRing.add(server)

Add a new server to ring without having to re-initialize the hashring. It accepts the same arguments as you can use in the constructor.

HashRing.remove(server)

Remove a server from the hash ring.

HashRing.has(server)

Checks if a given server exists in the hash ring.

HashRing.reset()

Reset the HashRing and clean up it's references.

HashRing.end()

Resets the HashRing and closes the ring.

HashRing.find(hashValue) (private)

Finds the correct position of the given hashValue in the hashring.

returns: Index of the value in the ring.

HashRing.hash(key) (private)

Generates the hash for the key.

returns: The hashed valued.

HashRing.digest(key) (private)

Digest hash so we can make a numeric representation from the hash. So it can be fed in to our hashValue.

returns: An array of charCodeAt(0) converted chars.

HashRing.hashValue(key) (private)

Get the hashed value of the given key, it does the digesting, hashing yo.

returns: The hash value of the key.

HashRing.points(servers)

Returns the points per server.

returns: A Object with server -> Array of points mapping

Upgrading from 0.0.x to 1.x.x

The 0.0.x releases had some serious flaws that causes it to be incompatible with the 1.0.0 release. These flaws are the reason that 1.0.0 got released. They are not backwards compatible as they change the way that keys are hashed. The following incompatible changes have been made for the sake of consistency: