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

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.