fash

fash: consistent hashing library for node.js

This module provides a consistent hashing library. Notably, this module the ability to deterministically generate the same hash ring topology across a set of distributed hosts. Fash also handles collisions of nodes on the ring and ensures no two nodes will share the same spot on the ring. Additionally, fash provides the ability to add, remove, or remap physical nodes on the ring -- useful when a particular physical node has hit its scaling bottleneck.

Design

Fash consists of a mapping of a set of fixed virtual nodes (vnodes) -- usually a large number, say 1000000 -- distributed across the hash ring. It is then possible to map these virtual nodes to a set of physical nodes (pnodes). In practice, pnodes are usually physical shards or servers in a distributed system. This gives the flexibility of mutating the hashspace of pnodes and the number of pnodes by re-mapping the vnode assignments.

Backends

As of version 2, Fash supports both a leveldb backend as well as an in-memory backend. The leveldb backend has several advantages over the in-memory backend. Notably, performance at scale should be faster since the ring is no longer in v8. Also the ring can be persisted on disk via leveldb, removing the need to load the ring into memory when the process is restarted.

To select a backend, simply pass in a backend object like so to fash.create();

    var fash = require('fash');
    var Logger = require('bunyan');

    var LOG = new Logger({
        name: 'fash',
        level: 'info'
    });

    fash.create({
        log: LOG, // optional [bunyan](https://github.com/trentm/node-bunyan) log object.
        algorithm: 'sha-256', // Can be any algorithm supported by openssl.
        pnodes: ['A', 'B', 'C', 'D', 'E'], // The set of physical nodes to insert into the ring.
        vnodes: 1000000 // The virtual nodes to place onto the ring. Once set, this can't be changed for the lifetime of the ring.
        backend: fash.BACKEND.LEVEL_DB,
        location: '/tmp/chash'
    }, function(err, chash) {
        console.log('chash created');
    });

Or from, the command line:

./bin/fash.js create -v 1000000 -b leveldb -l {filepath/to/hash_ring} -p '{pnodename}''

Example

Most examples can be found in the unit tests. Here are a few.

Boostrapping a New Hash Ring

var fash = require('fash');
var Logger = require('bunyan');

var LOG = new Logger({
    name: 'fash',
    level: 'info'
});

var chash = fash.create({
    log: LOG, // optional [bunyan](https://github.com/trentm/node-bunyan) log object.
    algorithm: 'sha-256', // Can be any algorithm supported by openssl.
    pnodes: ['A', 'B', 'C', 'D', 'E'], // The set of physical nodes to insert into the ring.
    vnodes: 1000000 // The virtual nodes to place onto the ring. Once set, this can't be changed for the lifetime of the ring.
    backend: fash.BACKEND.IN_MEMORY
});

var node = chash.getNode('someKeyToHash');
console.log('key hashes to pnode', node);

If the config used to bootstrap fash is the same across all clients, then the ring toplogy will be the same as well. By default, fash will evenly distribute vnodes across the set of pnodes. If you wish to have a custom mapping of pnodes to vnodes, see the later section on serialization.

Remapping Pnodes in the Ring

Fash gives you the ability to add and rebalance the pnodes in the ring by using the remapNode() function, which returns an optional callback.

You can also remove pnodes from the ring, but you must first rebalance the ring by reassigning its vnodes to other pnodes via remapVnode(). Then you can invoke removeNode(), which will return an optional callback.

You can assign an arbitrary number of vnodes to the new pnode -- also -- the pnode can be a new node, or an existing one. Again, as long as the order of removes and remaps is consistent across all clients, the ring toplogy will be consistent as well.

var fash = require('fash');
var Logger = require('bunyan');

var LOG = new Logger({
    name: 'fash',
    level: 'info'
});

var chash = fash.create({
    log: LOG,
    algorithm: 'sha256',
    pnodes: ['A', 'B', 'C', 'D', 'E'],
    backend: fash.BACKEND.IN_MEMORY,
    vnodes: 100000
});

// get vnodes from A
var aVnodes = chash.getVnodes('A');
aVnodes = aVnodes.slice(aVnodes.length / 2);

// remap some of A's vnodes to B
chash.remapVnode('B', aVnodes, function(ring, pnodes) {
    console.log('new ring topology', ring);
    console.log('changed pnode->vnode mappings', pnodes);
});

Adding More Pnodes to the Ring

You can add additional pnodes to the ring after fash has been initialized by invoking remapVnode(), which optionally returns a callback. Note that adding the callback will cause fash to create a new copy of the ring topology across each invocation -- do not do this if you have millions of vnodes, as this is quite slow and may consume all available memory, bringing the operation to a standstill and locking up other resources.

var fash = require('fash');
var Logger = require('bunyan');

var LOG = new Logger({
    name: 'fash',
    level: 'info'
});

var chash = fash.create({
    log: LOG,
    algorithm: 'sha256',
    pnodes: ['A', 'B', 'C', 'D', 'E'],
    backend: fash.BACKEND.IN_MEMORY,
    vnodes: 100000
});
// specify the set of virtual nodes to assign to the new physical node.
var vnodes = [0, 1, 2, 3, 4];

// add the physical node 'F' to the ring.
chash.remapVnode('F', vnodes, function(ring, changedNodes) {
    console.log('ring topology updated', ring);
    console.log('removed mappings', changedNodes);
});

Fash will remove the vnodes from their previously mapped physical nodes, and map them to the new pnode.

Removing Pnodes from the Ring

You can remove physical nodes from the ring by first remapping the pnode's vnodes to another pnode, and then removing the pnode.

var fash = require('fash');
var Logger = require('bunyan');

var LOG = new Logger({
  name: 'fash',
  level: 'info'
});

var chash = fash.create({
    log: LOG,
    algorithm: 'sha256',
    pnodes: ['A', 'B', 'C', 'D', 'E'],
    backend: fash.BACKEND.IN_MEMORY,
    vnodes: 10000
});

// get the vnodes that map to B
var vnodes = chash.getVnodes('B');
// rebalance them to A
chash.remapVnode('A', vnodes, function(ring, removedMap) {
    // remove B
    chash.removePnode('B', function(ring, pnode) {
        if (!err) {
            console.log('removed pnode %s', pnode);
        }
    });
});

Adding Optional Data to a Virtual Node

Sometimes, it might be helpful to associate state with a set of vnodes. An example of this would be during routine system maintenance, an administrator may want to set a certain set of vnodes to read only, and then set them back to write mode after the maintenance has completed.

Fash gives enables you to add arbitrary objects to vnodes by invoking the addData function.

chash.addData(10, 'foo');

Subsequence chash.getNode() invocations which map to vnode 10 will return:

{
    pnode: 'A',
    vnode: 10,
    data: 'foo'
}

The data associated with a virtual node is persistent across serializations and remaps.

Serializing and Persisting the Ring Toplogy

At any time, the ring toplogy can be accessed by:

chash.serialize();

Which returns the ring topology, which is a JSON serialized object string which looks like

{
    pnodeToVnodeMap: {
        A: {0, 1, 2},
        ...
    }, // the pnode to vnode mapings.
    vnode // the total number of vnodes in the ring.
}

Additionally, anytime remapVnode() is invoked, it can return a cb which contains an updated version of this object that is not JSON serialized. Fash can be instantiated given a topology object instead of a list of nodes. This also allows you to specify a custom pnode to vnode topology -- as mentioned in the earlier bootstrapping section.

var fash = require('fash');
var Logger = require('bunyan');

var LOG = new Logger({
    name: 'fash',
    level: 'info'
});

var chash = fash.create({
   log: LOG,
   algorithm: 'sha256',
   pnodes: ['A', 'B', 'C', 'D', 'E'],
   backend: fash.BACKEND.IN_MEMORY,
   vnodes: 10000
});

var topology = chash.serialize();

var chash2 = fash.deserialize({
    log: LOG,
    topology: topology
});

That's it, chash and chash2 now contain the same ring toplogy.

Running Tests

Just run make test, first exporting the DB_LOCATION variable for the load test file to give it the location of your hash ring.

Copyright (c) 2017, Joyent, Inc.

This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/.