Distributed Consistent Hashing

poc.js

const { EventEmitter } = require('events');
// const jumphash = require('jumphash');

const _jumphash = require('@ceejbot/jumphash'),
    crypto = require('crypto');

function jumphash(key, buckets, algo='md5') {
	const buffer = crypto
		.createHash(algo)
		.update(key)
		.digest();
	return _jumphash(buffer, buckets);
}

function generateId() {
	return Date.now().toString(16) + '.' + (Math.random() * 10e16).toString(16);
}

class Worker extends EventEmitter {
	constructor(supervisor, uid = generateId()) {
		super();
		this.uid = uid;
		this.supervisor = supervisor;

		supervisor.on('job', this.job.bind(this));
		this.jobs = 0;
	}

	report() {
		this.emit('report', this);
	}

	job(name, task) {
		if (this.evaluate(name)) {
			console.log('Worker', this.uid, 'task', name);
			this.jobs++;
		}
	}

	evaluate(name) {
		const nodes = this.supervisor.nodes();
		const index = nodes.indexOf(this.uid);
		const buckets = nodes.length;

		if (index < 0) return;

		const partition = jumphash(name, buckets, 'md5'); // sha256 sha1 md5
		// 50, 2000
		// md5 - 4s, sha1 - 4s, 256 - 4s

		// node bindings
		// sha256 - 3s, md5 - 2.94, sha1 - 3s

		const accept = partition === index;
		if (accept) {
			// console.log('buckets', buckets, 'index', index);
			console.log('partition', partition);
		}
		return accept;
	}
}

class Supervisor extends EventEmitter {
	constructor(count) {
		super();
		const workers = new Map();
		for (let i = 0; i < count; i++) {
			let worker = new Worker(this)
			workers.set(worker.uid, worker);
		}

		this.workers = workers;
	}

	job(name, task) {
		// supervisor does not need to know who to distribute task too
		// workers are "self-organizing""
		this.emit('job', name, task);
	}

	nodes() {
		return [...this.workers.keys()].sort();
	}

	printjobs() {
		console.log('----------------------')
		for (let worker of this.workers.values()) {
			console.log('worker', worker.uid, 'jobs', worker.jobs);
		}
	}
}

supervisor = new Supervisor(50);

for (i = 0; i < 2000; i++) {
	supervisor.job('hello' + i, 123);
}

supervisor.printjobs();

🤔.md

Algorithms

1. Rendezvous or highest random weight (HRW) hashing https://en.wikipedia.org/wiki/Rendezvous_hashing
2. Jump Consistent Hash https://research.googleblog.com/2017/04/consistent-hashing-with-bounded-loads.html
3. Ring Hash

Load Balancing Distributed Tasks

hello service discovery. joining service (i'm host + port)

watch service, list nodes.

• sum buckets
• sort them (host + port)
• find index

accepting requests

- shard key (eg. account)
- jumphash(key, buckets) = partition
- is partition === mine? serve request.

on nodes update after serving request

- update buckets sum
- run through running keys
- rehash
- same partition? continue running
- different partition? stop running

Links

https://www.npmjs.com/package/jumphash https://github.com/ceejbot/jumphash

https://medium.com/vimeo-engineering-blog/improving-load-balancing-with-a-new-consistent-hashing-algorithm-9f1bd75709ed https://akshatm.svbtle.com/consistent-hash-rings-theory-and-implementation https://eng.uber.com/intro-to-ringpop/ https://github.com/gholt/ring/blob/master/BASIC_HASH_RING.md http://www.paperplanes.de/2011/12/9/the-magic-of-consistent-hashing.html https://www.toptal.com/big-data/consistent-hashing http://www.tom-e-white.com/2007/11/consistent-hashing.html