Redis Bitset operations in Node.js / Express.js

I'm very new to Node.js and Redis. I read this article, and want to use a bitset to store all the user information for my Express.js app, as mentioned in this article: http://blog.getspool.com/2011/11/29/fast-easy-realtime-metrics-using-redis-bitmaps/

I'm having a bit of a trouble. In my function, I get the current year, month, and date, and then use client.setbit() to set appropriate key and value. But how can I count all the keys? I'm on Redis 2.4*, and the BITCOUNT command is in 2.6. Is there any other way? The article uses a Java bitset, so that's a different thing. I don't quite understand it.

How could I use, for example, a for loop, to count all the bits set to 1? Is there any operation to count the size of the bitset, so I could do something like this:

for (var i = initial_offset; i < bitset_length; i++){
    if (i == 1){
        total_users++;
    }
}

Or am I going about it in a totally wrong way?

You need to count the number of bits of a given string stored in Redis. There are basically two ways to do this:

  • you can try to do it on server-side with Redis 2.6 and the new BITCOUNT/BITOP operations.

  • you can retrieve the whole string (containing all the bits) and process the data on client side. In the original article, the author retrieves the Redis string and converts it to a Java bitset on which bit-level algorithms can be applied. The same strategy can be applied with any client, any language: you just have to find a good library to deal with arrays of bits, or implement one by yourself (it is not that hard). It would work with Redis 2.2 or higher.

A strategy that would not work very well is to iterate on client-side and check each individual bits by executing the GETBIT command. It would be really inefficient.

With node.js, here are a few resources you may want to use to implement the second option:

Node.js is not a very good environment to implement CPU consuming operations, but in the worst case, should you have very large bitsets, you can still rely on an efficient C++ implementation to be called from Node.js. You have a good one in boost::dynamic_bitset.

Here is a Node.js example with a very simple (and probably inefficient) counting algorithm:

var redis = require('redis')
var rc = redis.createClient(6379, 'localhost', {return_buffers:true} );

var bitcnt = [ 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8]

function count(b)
{
  var cnt = 0
  for (i=0; i<b.length; ++i ) {
    cnt += bitcnt[ b[i] ]
  }
  return cnt
}

function fetch( callback )
{
  rc.get( 'mybitset', function(err,reply) {
     callback(reply)
  });
}

function fill( callback )
{
   rc.setbit( 'mybitset', 0, 1 )
   rc.setbit( 'mybitset', 10, 1 )
   rc.setbit( 'mybitset', 20, 1 )
   rc.setbit( 'mybitset', 60, 1, function(err,reply) {
      callback()
   });
}

rc.flushall( function(err,rr) {
   fill( function() {
      fetch( function(b) {
        console.log( "Count = ",count(b) );
      });
   })
})

Please note the {return_buffers:true} option is used to be sure Redis output is processed as binary data (ignoring possible character conversion).