Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
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
Owner
@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
Something went wrong with that request. Please try again.