Percentile Bucket Aggregation with Redis

index.js

// npm install native-hdr-histogram prob.js redis

var prob = require('prob.js');
var redis = require("redis");
var Histogram = require('native-hdr-histogram');

//generate fake response times
var random = prob.lognormal(0, 1.0); // μ = 0, σ = 1.0 
var histogram = new Histogram(1, 120 * 1000);
var client = redis.createClient({ host: 'localhost', port: 6379 });
client.on("error", function (err) {
    console.log("Error " + err);
});
client.flushdb();

var NbMaxSamples = 500;
var keyPrefix = 'redispercentiles#';
for (var i = 0; i < NbMaxSamples; i++) {
    var sample = value = Math.ceil(random() * 1000);

    // keep an hdr histogram
    histogram.record(sample);

    // increment hashes
    client.HINCRBY(keyPrefix + 'constant', constantScale(sample, 50), 1);
    client.HINCRBY(keyPrefix + 'expo', expoScale(sample), 1);
    client.HINCRBY(keyPrefix + 'hdr', hdrScale(sample), 1);
}


console.log('in-memory 90 percentile is', histogram.percentile(90)) //expected
//calculate percentiles in various ways
redisPercentile(keyPrefix + 'constant', 90, function (err, length, value) {
    console.log('90 percentile for constant scale is', value, 'with #field', length)
});
redisPercentile(keyPrefix + 'expo', 90, function (err, length, value) {
    console.log('90 percentile for expo scale is', value, 'with #field', length)
});
redisPercentile(keyPrefix + 'hdr', 90, function (err, length, value) {
    console.log('90 percentile for hdr scale is', value, 'with #field', length)
});

function redisPercentile(key, centile, callback) {
    client.hgetall(key, function (err, object) {
        if (err) return callback(err);
        var count = 0; // number of samples
        var fields = [];
        for (var i in object) {
            fields.push(parseInt(i));
            count += parseInt(object[i]);
        }
        // sort field names (number)
        fields.sort(function sortNumber(a, b) {
            return a - b;
        });
        // number of samples to get the requested percentile
        var target = parseInt(count * centile / 100);
        var aggregate = 0;
        for (var idx in fields) {
            var bucket = fields[idx];
            aggregate += parseInt(object[bucket]);
            if (aggregate > target) {
                callback(null, fields.length, bucket);
                break;
            }
        }
    });
}


// helpers methods
function constantScale(value, roundFactor) {
    return Math.floor(value / roundFactor) * roundFactor;
}

function expoScale(value) {
    var s = Math.ceil(Math.sqrt(value));
    return s * s;
}

function hdrScale(value) {
    var d = Math.floor(value / 128) + 1;
    var step = previousPowerOf2(Math.floor(d));
    return constantScale(value, step);
}

function previousPowerOf2(x) {
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    return x - (x >> 1);
}