Skip to content

Instantly share code, notes, and snippets.

@Krinkle

Krinkle/01-cluster-worker-2020.js

Last active June 9, 2021 21:43
Show Gist options
  • Save Krinkle/29ed4ca1217fd43b52e6966e69ebc107 to your computer and use it in GitHub Desktop.
Save Krinkle/29ed4ca1217fd43b52e6966e69ebc107 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
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));
});
}
Raw
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 };
}
@Krinkle
Copy link
Author

Krinkle commented Mar 18, 2019 •
edited

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment