Create a gist now

Instantly share code, notes, and snippets.

Percentile Bucket Aggregation with Redis
// 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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment