failure-detector.js

// Based on http://bit.ly/215MBZ

function FailureDetector(ws) {
  // ws stands for window size.
  // How many heartbeat intervals we keep track of.
  this.ws = ws || 100;
  this.window = [];
  this.last = null;
}
exports.FailureDetector = FailureDetector;


// Call this every time a heartbeat is received.
FailureDetector.prototype.report = function(when) {
  if (!when) when = Date.now();

  if (this.last) {
    var interval = when - this.last;
    this.window.push(interval);
    if (this.window.length > this.ws) {
      this.window.shift();
    }
  }

  this.last = when;

  if (this.window.length) {
    // calculate mean and variance of intervals in our window.
    // This could be done more efficiently. Whatever.
    var sum = 0;
    for (var i = 0; i < this.window.length; i++) {
      sum += this.window[i];
    }
    this.mean = sum / this.window.length;

    sum = 0;
    for (var i = 0; i < this.window.length; i++) {
      var x = this.window[i] - this.mean;
      sum += x * x;
    }
    this.variance = sum / this.window.length;
  }
};


function log10(x) {
  return Math.log(x) / Math.LN10;
}


// Use this function to determine failure.
// Using 1 as a threshold means the likeliness of mistaken failure is 10%
// Using 2 as a threshold means the likeliness of mistaken failure is 1%
// Using 3 as a threshold means the likeliness of mistaken failure is 0.1%
FailureDetector.prototype.phi = function(when) {
  if (!this.last) return 0;

  var t = (when || Date.now()) - this.last;
  // Took this approximation from casandra. Don't know where they got it.
  // suspect.
  var probability = Math.pow(Math.E, -1 * t / this.mean);

  var log = (-1) * log10(probability);

  return log;
};

test-failure-detector.js

var FailureDetector = require('./failure-detector').FailureDetector;
var assert = require('assert');

var d = new FailureDetector();

for (var i = 0; i < 100; i ++ ) {
  d.report(Date.now() + i * 1000);
}

// mean should be almost exactly one second
console.log("mean = ", d.mean);
assert.ok(999 <=  d.mean && d.mean <= 1001);
// should be pretty certain everything is fine.
console.log("phi = ", d.phi());
assert.ok(d.phi() <= 0.01);



// test stolen from casandra

var d = new FailureDetector(4);
d.report(111);
d.report(222);
d.report(333);
d.report(444);
d.report(555);

var expected = 0.4342;
var actual = d.phi(666);
console.log("mean = ", d.mean);
console.log("phi = ", actual);
assert.ok(expected - 0.01 <= actual && actual <= expected + 0.01);

//oh noes, a much higher timestamp, something went wrong!
expected = 9.566;
actual = d.phi(3000);
console.log("mean = ", d.mean);
console.log("phi = ", actual);
assert.ok(expected - 0.01 <= actual && actual <= expected + 0.01);