Skip to content

Instantly share code, notes, and snippets.

@ry
Created December 23, 2011 23:07
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save ry/454b33101532a2e43340 to your computer and use it in GitHub Desktop.
// Copyright Joyent, Inc. All rights reserved.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to
// deal in the Software without restriction, including without limitation the
// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
// sell copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
// IN THE SOFTWARE.
// Based on http://bit.ly/215MBZ
var assert = require('assert').ok;
function FailureDetector(ws) {
// ws stands for window size.
// How many heartbeat intervals we keep track of.
this.ws = ws || 100;
this.window = [];
this.last = Date.now();
}
exports.FailureDetector = FailureDetector;
// Call this every time a heartbeat is received.
FailureDetector.prototype.report = function(when) {
if (!when) when = Date.now();
assert(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) {
assert(this.last);
var t = (when || Date.now()) - this.last;
// If it's only 5 seconds from the start - let's give the system some
// slack and allow it to fuck up.
if (this.window.length < 3) {
if (t < 5 * 1000) {
return 0;
}
}
// 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;
};
var FailureDetector = require('../lib/failure-detector').FailureDetector;
var assert = require('assert');
var d = new FailureDetector();
for (var i = 1; 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);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment