Created
October 19, 2016 12:52
-
-
Save cybermaxs/f587b3e1ad92b055bc13a6e2482dfc9d to your computer and use it in GitHub Desktop.
Percentile Bucket Aggregation with Redis
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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