Redis Bitset operations in Node.js / Express.js

Question

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?

If your redis version doesn't support it, there's really very little you can do — ControlAltDel, Jun 25 '12 at 14:12
Thanks anyways guys. Guess I'll have to switch to 2.6 and figure this stuff out. — Manish Gill, Jun 25 '12 at 14:37

score 2 · Accepted Answer · edited May 23 '17 at 11:58

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).

Could you please explain how bitcnt is working? Why is it needed at all? How could I use something like https://github.com/tdegrunt/bitset to add the same functionality? — Manish Gill, Jun 26 '12 at 12:33
bitcnt is just an array[0..255] whose each value is the number of bits of the index. For instance bitcnt[3] = 2 because byte 3 has only 2 bits on. It is just a simple way to calculate the number of bits without relying on complex logical bitwise operations. Use whatever method you are the most comfortable with ... — Didier Spezia, Jun 26 '12 at 13:05
github.com/tdegrunt/bitset looks even less efficient since it counts bit per bit. Furthermore, you would need to find a way to convert the bitset from Redis output to a suitable representation for this package (no Buffer -> bitset conversion provided). — Didier Spezia, Jun 26 '12 at 13:08
Ah, finally understood. Yes, I was stuck at converting from the redis bitset to the js module linked above. Thanks again. You really helped me in understanding this. :) — Manish Gill, Jun 26 '12 at 14:53
For really fast bit counting, you can check https://github.com/lemire/FastBitSet.js — Daniel Lemire, Sep 29 '15 at 15:14

Redis Bitset operations in Node.js / Express.js

1 Answers1