Create a gist now

Instantly share code, notes, and snippets.

Ultra fast Metrics with Node.js & Redis's bitmaps
var EventEmitter = require("events").EventEmitter,
redis = require("redis"),
dateformat = require("dateformat");
function population32(x)
{
x -= ((x >> 1) & 0x55555555);
x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
x = (((x >> 4) + x) & 0x0f0f0f0f);
x += (x >> 8);
x += (x >> 16);
return(x & 0x0000003f);
}
function populationBuffer( value ) {
var pop = 0;
var int32 = 0;
for (var i = 0; i < value.length ; i+=4) {
int32 = value[i];
int32 += value[i+1] << 8;
int32 += value[i+2] << 16;
int32 += value[i+3] << 24;
pop += population32(int32);
}
return pop;
}
metrics = function( options ) {
if ( !(this instanceof metrics) ) {
return new metrics( options );
}
EventEmitter.call(this);
this.options = options || {};
this.init();
}
metrics.prototype.init = function() {
this.redisClient = redis.createClient(
this.options.port || 6379,
this.options.host || '0.0.0.0',
{return_buffers:true}
);
this.redisClient.on("error", function (err) {
this.emit("error", err);
});
}
metrics.prototype.count = function( metric, userIndex, date ) {
date = date || new Date();
var timebucket = dateformat(date, this.options.precision);
var metricUnique = metric+".unique."+timebucket;
var metricCount = metric+".count."+timebucket;
var m = this.redisClient.multi();
m.setbit(metricUnique, userIndex, 1);
m.incr(metricCount);
m.exec();
}
metrics.prototype.get = function( metric, date, callback ) {
if ( callback ) {
date = date || new Date();
} else {
callback = date;
date = new Date();
}
var timebucket = dateformat(date, this.options.precision);
var metricUnique = metric+".unique."+timebucket;
var metricCount = metric+".count."+timebucket;
var unique, count;
this.redisClient.get(metricUnique, function(err, value) {
if( callback && err ) callback( err ), callback = null;
unique = populationBuffer(value);
if( callback && count !== undefined ) callback( err, unique, count ), callback = null;
});
this.redisClient.get(metricCount, function(err, value) {
if( callback && err ) callback( err ), callback = null;
count = parseInt(value.toString());
if( callback && unique !== undefined ) callback( err, unique, count ), callback = null;
});
}
exports.metrics = metrics
/*
var met = new metrics({precision:'yyyymmddhh'});
met.count('dau', 1);
met.count('dau', 2);
met.count('dau', 3);
met.count('dau', 1);
met.count('dau', 2);
met.get('dau', function( err, unique, count ) {
console.log(
'unique users:', unique,
'login count:', count,
'login/user:', count/unique
);
process.exit();
});
*/
// Proof of concept from Spool article
// http://blog.getspool.com/2011/11/29/fast-easy-realtime-metrics-using-redis-bitmaps/
function population32(x)
{
x -= ((x >> 1) & 0x55555555);
x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
x = (((x >> 4) + x) & 0x0f0f0f0f);
x += (x >> 8);
x += (x >> 16);
return(x & 0x0000003f);
}
//TEST to see our counter works
console.log( 'count population of 32bit integers' );
var tests = [
0x55555555, //binary: 0101...
0x33333333, //binary: 00110011..
0x0f0f0f0f, //binary: 4 zeros, 4 ones ...
0x00ff00ff, //binary: 8 zeros, 8 ones ...
0x0000ffff, //binary: 16 zeros, 16 ones ...
0x00000000, //binary: 32 zeros, 32 ones
0xffffffff, //binary: all ones
0x01010101, //the sum of 256 to the power of 0,1,2,3...
]
for( var i in tests ) {
console.log(tests[i].toString(16), population32(tests[i]))
}
// count population of each octet of a buffer
function populationBuffer1( value ) {
var pop = 0;
for (var i = 0; i < value.length ; i++) {
pop += population32(value[i]);
}
return pop;
}
// Buffer up 4octets in a row for about a nice performance boost
function populationBuffer2( value ) {
var pop = 0;
var int32 = 0;
for (var i = 0; i < value.length ; i+=4) {
int32 = value[i];
int32 += value[i+1] << 8;
int32 += value[i+2] << 16;
int32 += value[i+3] << 24;
pop += population32(int32);
}
return pop;
}
var redis = require("redis"),
client = redis.createClient(6379, '0.0.0.0', {return_buffers:true});
client.on("error", function (err) {
console.log("Error " + err);
});
console.log( "Setting bits. This may take a while..." );
for( var i=200000; i<600000; i++ ) {
client.setbit('dailyusers', i , 1);
}
//TEST
console.time('getbit');
client.get('dailyusers', function( err, value ){
console.timeEnd('getbit');
console.time('count');
console.log('populationBuffer1', populationBuffer1(value));
console.timeEnd('count');
console.time('count2');
console.log('populationBuffer2', populationBuffer2(value));
console.timeEnd('count2');
process.exit();
});
@FugueNation
Owner

So I just read this awesome article from Spool (http://blog.getspool.com/2011/11/29/fast-easy-realtime-metrics-using-redis-bitmaps/) about their metrics system, so I decided to give it a try with Node.js.
Counting 600k entries takes 2ms, not bad!

@FugueNation
Owner

Oh right forgot the output...

robert:fn robert$ node hamming.js
count population of 32bit integers
55555555 16
33333333 16
f0f0f0f 16
ff00ff 16
ffff 16
0 0
ffffffff 32
1010101 4
getbit: 6540ms
populationBuffer1 400000
count: 5ms
populationBuffer2 400000
count2: 2ms

@cpatni

Good stuff. Thanks for the shout out for the blog post.

@HenrikJoreteg

Sweet, have you thought about bundling this up and submitting it to NPM?

@FugueNation
@HenrikJoreteg

Sweet, I'd totally use it.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment