01-cluster-worker-2020.js

/*! Requires Node 12.5+ | License: Public domain. */

const cluster = require('cluster');
const WORK_TOTAL = 10_000_000;
const WORK_MILESTONE = 1_000_000;
const WORK_ASSIGN_CHUNK = 100_000;
const WORK_RESP_CHUNK = 1_000;

const ALGO = 'md5';

if (cluster.isMaster) {
	let assigned = 0;
	let assignedPerMilestone = 0;
	let received = 0;
	let receivedPerMilestone = 0;
	let concluded = false;

	const map = new Set();
	let found = 0;

	function mainLog(...args) {
		console.log(`[main]`, ...args);
	}

	function makeTask() {
		if (assigned === WORK_TOTAL) {
			concludeWork();
			return null;
		} else {
			const from = assigned;
			const to = Math.min(assigned + WORK_ASSIGN_CHUNK, WORK_TOTAL);
			assigned = to;

			assignedPerMilestone += (to - from);
			if (assignedPerMilestone >= WORK_MILESTONE) {
				mainLog(`… assigned work upto ${assigned.toLocaleString()}`);
				assignedPerMilestone = 0;
			}

			return { from, to };
		}
	}

	function receiveItems(items) {
		for (const item of items) {
			received++;
			receivedPerMilestone++;
			if (map.has(item)) {
				found++;
			} else {
				map.add(item);
			}
		}
		if (receivedPerMilestone >= WORK_MILESTONE) {
			mainLog(`… received work upto ${received.toLocaleString()}, with ${found} overlapping hashes so far`);
			receivedPerMilestone = 0;
		}
	}

	function concludeWork() {
		if (received >= WORK_TOTAL && !concluded) {
			concluded = true;
			mainLog(`Hashed ${received.toLocaleString()} items with algo ${ALGO} and found ${found} overlapping hashes`);
		}
	}

	let i = require('os').cpus().length;
	mainLog(`Creating ${i} workers`);
	while (i--) {
		cluster.fork();
	}

	cluster.on('online', (worker) => {
		// Send the first task
		const task = makeTask();
		if (task === null) {
			worker.disconnect();
		} else {
			worker.send(task);
		}
	});
	cluster.on('message', (worker, response) => {
		if (Array.isArray(response)) {
			receiveItems(response);
		} else if (response.done === true) {
			// Send the next task
			const task = makeTask();
			if (task === null) {
				worker.disconnect();
			} else {
				worker.send(task);
			}
		} else {
			mainLog(`Invalid response from worker #${worker.id}:`, response);
		}
	});
	cluster.on('exit', (worker, code, signal) => {
		mainLog(`worker #${worker.id} exited`, code, signal);
	});

} else {
	// Worker process
	const crypto = require('crypto');

	function workerLog(...args) {
		console.log(`[worker #${cluster.worker.id}`, ...args);
	}

	function computeItems(from, to, callback) {
		let buffer = [];
		for (let i = from; i < to; i++) {
			const hash = crypto.createHash(ALGO);
			hash.update(i.toString());
			const digest = hash.digest('hex');
			buffer.push(digest);
			if (buffer.length >= WORK_RESP_CHUNK) {
				callback(buffer);
				buffer = [];
			}
		}
		if (buffer.length) {
			callback(buffer);
			buffer = [];
		}
		callback({ done: true });
	}

	process.on('message', (task) => {
		computeItems(task.from, task.to, (response) => process.send(response));
	});
}

02-cluster-worker-2018.js

/*! Requires Node 10.0+ | License: Public domain. */

const cluster = require('cluster');
const crypto = require('crypto');

// Make individual tasks fairly large so that the workers spend more of their
// time doing work, instead of decoding/receiving/sending/encoding message objects.
const TASK_SIZE = 10 * 1000; // 10K
const MILESTONE = 10 * 1000 * 1000; // 10M

const RESPONSE_NOMATCH = 0;
const RESPONSE_MATCH = 1;

const MAX_LENGTH = 11; // 1-11 characters
const ALPHABET = '0123456789 abcdefghijklmnopqrstuvwxyz'.split('');
const ALPHABET_START = ALPHABET[0];
const ALPHABET_END = ALPHABET[ALPHABET.length - 1];

const NEEDLE = '1d183655789c74eacc95a75398e6d55c'; // md5("0ad") takes ~ 3 seconds
// const NEEDLE = 'edeb0733dca4583954973a7fe7483298'; // md5("the key") takes 25 minutes

if (cluster.isMaster) {
	const tasks = makeTaskIterator();

	let i = require('os').cpus().length;
	console.log(`[master] Creating ${i} workers`);
	while (i--) {
		cluster.fork();
	}

	cluster.on('online', (worker) => {
		// Assign the new worker its first task
		const task = tasks.next();
		if (task === false) {
			worker.disconnect();
		} else {
			worker.send(task);
		}
	});
	cluster.on('message', (worker, message) => {
		// Worker finished a task
		if (message.code === RESPONSE_NOMATCH) {
			// Assign the next task
			const task = tasks.next();
			if (task === false) {
				worker.disconnect();
			} else {
				worker.send(task);
			}
		} else if (message.code === RESPONSE_MATCH) {
			console.log('[master] Found match for phrase: ' + JSON.stringify(message.phrase));
			tasks.stop();
			worker.disconnect();
		} else {
			console.log('[master] Invalid worker response:', message);
		}
	});
	cluster.on('exit', (worker, code, signal) => {
		console.log(`[master] worker process ${worker.process.pid} exited`, code, signal);
	});
} else {
	// Worker process
	process.on('message', (message) => {
		process.send(handleTask(message.phrases, NEEDLE));
	});
}

/**
 * @param {string} phrase
 * @return {string} The next phrase in the alphabet
 */
function nextPhrase(phrase) {
	let trimmed = 0;
	// For example:
	// * "z" to "00" and "zz" to "000" (trim END, return trimmed+1 STARTs)
	// * "0z" to "10" (trim END, increment new END, append trimmed STARTs).
	while (phrase[phrase.length - 1] === ALPHABET_END) {
		phrase = phrase.slice(0, -1);
		trimmed++;
	}
	if (phrase.length === 0) {
		if (trimmed === MAX_LENGTH) {
			return null;
		}
		// "zz" to "" (trimmed 2), to "000"
		return ALPHABET_START.repeat(trimmed + 1);
	}
	const lastIdx = ALPHABET.indexOf(phrase[phrase.length - 1]);
	// Shift from e.g. "0" to "1", or "00a" to "00b".
	phrase = phrase.slice(0, -1) + ALPHABET[lastIdx + 1];
	// Replace trimmed ENDs with STARTs
	return phrase + ALPHABET_START.repeat(trimmed);
}

function makeTaskIterator() {
	let progress = 0;
	let next = ALPHABET_START;

	return {
		next: function () {
			if (next === null) {
				return false;
			}

			if (progress >= MILESTONE) {
				console.log('[master] ... distributed ' + progress.toLocaleString() + ' phrases. Now at: ' + JSON.stringify(next));
				progress = 0;
			}

			const task = { phrases: [] };
			let i = TASK_SIZE;
			while (i--) {
				task.phrases.push(next);
				progress++;

				next = nextPhrase(next);
			}

			//console.log('[master] distributed task', task);
			return task;
		},
		stop: function () {
			next = null;
			console.log('[master] stop distributing tasks');
		}
	};
}

/**
 * @param {string} phrase
 * @param {string} Hash
 */
function hashPhrase(phrase) {
	return crypto.createHash('md5').update(phrase).digest('hex');
}

/**
 * @param {string[]} phrases
 * @param {string} needle
 * @return {Object} response
 */
function handleTask(phrases, needle) {
	var i = phrases.length;
	while (i--) {
		if (hashPhrase(phrases[i]) === needle) {
			return { code: RESPONSE_MATCH, phrase: phrases[i] };
		}
	}
	return { code: RESPONSE_NOMATCH };
}

2020

[main] Creating 8 workers
[main] … assigned work upto 1,000,000
[main] … received work upto 1,000,000, with 0 overlapping hashes so far
...
[main] … assigned work upto 9,000,000
[main] … received work upto 9,000,000, with 0 overlapping hashes so far
[main] … assigned work upto 10,000,000
[main] worker #4 exited 0 null
[main] worker #5 exited 0 null
[main] worker #6 exited 0 null
[main] worker #7 exited 0 null
[main] worker #3 exited 0 null
[main] worker #8 exited 0 null
[main] worker #1 exited 0 null
[main] … received work upto 10,000,000, with 0 overlapping hashes so far
[main] Hashed 10,000,000 items with algo md5 and found 0 overlapping hashes

2018

$ node crack-the-hash.js 
[master] Creating 8 workers
[master] ... distributed 10,000,000 phrases. Now at: "4adk "
[master] ... distributed 10,000,000 phrases. Now at: "9mt6j"
...
[master] ... distributed 10,000,000 phrases. Now at: "th2e1rv"
[master] ... distributed 10,000,000 phrases. Now at: "th7qgd5"
[master] ... distributed 10,000,000 phrases. Now at: "thc2vze"
[master] Found match for phrase: "the key"
[master] stop distributing tasks

2018 / Node 6

See Krinkle/perfect-numbers.js.