Ultra fast Metrics with Node.js & Redis's bitmaps

almost a module

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();
});
*/

gistfile1.js

// 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();
});

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!

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

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

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

Actually should do that. Ok will do it this weekend :) @iphone

…

On Jan 27, 2012, at 18:23, Henrik ***@***.*** wrote: Sweet, have you thought about bundling this up and submitting it to NPM? --- Reply to this email directly or view it on GitHub: https://gist.github.com/1455345

Sweet, I'd totally use it.