Time challenge

hostnames.txt

labnotes.org
example.com
mathforum.org
slack.com
github.com
facebook.com
twitter.com

time.js

'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);
  });