Skip to content

Instantly share code, notes, and snippets.

@assaf
Created August 12, 2015 00:30
Show Gist options
  • Save assaf/a81e57fd589ef00faac1 to your computer and use it in GitHub Desktop.
Save assaf/a81e57fd589ef00faac1 to your computer and use it in GitHub Desktop.
Time challenge
labnotes.org
example.com
mathforum.org
slack.com
github.com
facebook.com
twitter.com
'use strict';
const assert = require('assert');
const HTTP = require('http');
const File = require('fs');
const Util = require('util');
// This file lists all the servers we're going to consult
const HOSTNAMES_FILENAME = 'hostnames.txt';
// To consider a result, it must arrive from that many servers
const QUORUM = 3;
// Maximum deviation (in ms) for us to consider the values correct.
const MAX_DEVIATION = 2000;
// If it takes more than half a second to respond, we're not sure what the time
// is any more, so we discard the late response
const RESPONSE_TIMEOUT = 500;
// Useful information, run with NODE_DEBUG=time to see it all
const debug = Util.debuglog('time');
// -> promise(date)
//
// Resolves the the date as ISO 8601 string
function getISODateAsync() {
const hostnames = getHostnames();
const timesPromise = getAvailableTimesAsync(hostnames);
const meanPromise = findMeanAsync(timesPromise);
const isoDatePromise = meanPromise
.then(function(time) {
const date = new Date(time);
const iso = date.toISOString();
return iso;
});
return isoDatePromise;
}
// -- Collect responses from servers --
// Returns the list of hostnames we're going to query
function getHostnames() {
const contents = File.readFileSync(HOSTNAMES_FILENAME, 'utf8');
const lines = contents.split('\n');
const hostnames = lines.filter(function(host) { return host.trim(); });
return hostnames;
}
// hostnames -> promise([ time ])
//
// Not all servers return a time value we can use, this promsie resolves to only
// valid time values
function getAvailableTimesAsync(hostnames) {
const maybeTimePromises = hostnames
.map( getServerResponseAsync )
.map( getServerTimeAsync )
.map( logAndIgnoreError );
const availableTimesPromise = Promise.all(maybeTimePromises)
.then( filterTime )
.then(function(times) {
debug('Got results from %d servers', times.length);
return times;
});
return availableTimesPromise;
}
// hostname -> promise(response)
function getServerResponseAsync(hostname) {
return new Promise(function(resolve, reject) {
const request = HTTP.get({ hostname });
request
.on('response', resolve)
.on('response', function() {
request.abort();
})
.on('error', reject);
const timeout = setTimeout(function() {
request.abort();
reject(new Error(`Timeout talking to ${hostname}`));
}, RESPONSE_TIMEOUT);
timeout.unref();
});
}
// promise(response) -> promise(time)
function getServerTimeAsync(responsePromise) {
const maybeTimePromise = responsePromise
.then(function(response) {
const date = response.headers.date;
const time = Date.parse(date);
// If the header isn't there, or not a valid date string, Date.parse
// returns NaN.
if (Number.isInteger(time)) {
debug('Date: %s', date);
return time;
} else
throw new Error(`Server respond with Date header that is not a valid date`);
});
return maybeTimePromise;
}
// promise(value) -> promise(value | undefined)
function logAndIgnoreError(promise) {
return promise.catch(function(error) {
debug('ERROR: %s', error.message);
return undefined;
});
}
// [ time | undefined | NaN ] -> [ time ]
function filterTime(values) {
return values.filter(function(value) { return Number.isInteger(value); });
}
// -- Statistical analysis: mean --
// promise([ time ]) -> promise(time)
function findMeanAsync(timesPromise) {
return timesPromise
.then( trimOutliers )
.then( checkDeviation )
.then( checkQuorum )
.then( mean );
}
// [ value ] -> [ value ]
//
// Used for calculating trim mean, see
// http://mathforum.org/library/drmath/view/52794.html
function trimOutliers(values) {
const n = values.length;
const sorted = values.slice().sort();
const lq = sorted[ Math.round(n * 0.25) ];
const hq = sorted[ Math.round(n * 0.75) ];
const iqr = hq - lq;
const min = lq - (1.5 * iqr);
const max = hq + (1.5 * iqr);
const trimmed = values.filter(function(value) { return value >= min && value <= max; });
debug('Trimmed outliers %d => %d', n, trimmed.length);
return trimmed;
}
// [ value ] -> [ value ]
function checkDeviation(values) {
const max = Math.max.apply(null, values);
const min = Math.min.apply(null, values);
const deviation = max - min;
debug('Deviation between minimum and maximum times: %d ms', deviation);
assert(deviation <= MAX_DEVIATION, 'Expected maximum time deviation to be 2 seconds');
return values;
}
// [ value ] -> [ value ]
function checkQuorum(values) {
const n = values.length;
assert(n >= QUORUM, `Will only consider results from at least ${QUORUM} servers`);
return values;
}
// [ value ] -> value
function mean(values) {
const n = values.length;
const result = values.reduce(sum) / n;
debug('Mean of %j is %d', values, result);
return result;
}
function sum(a, b) {
return a + b;
}
// main
getISODateAsync()
.then(console.log)
.catch(function(error) {
console.error(error.stack);
process.exit(1);
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment