Redis Bitmaps: Storing state in small places

Redis is a popular open source in-memory data store that supports all kinds of abstract data structures. In this post and in an accompanying example Java project, I am going to explore two great use cases for one of those data structures: bitmaps. The two use cases: determining “done” in an asynchronous system and collecting distinct activity metrics.

The source code for the example Java project is available on GitHub here:

What is a bitmap?

In a bitmap each individual bit in a bit array (0 or 1) is used to represent state. This unlocks the potential to represent a lot of state in an extremely little amount of space (something really worth exploring when space is at a premium and there is a large amount of state to represent).

For Redis Bitmaps, Redis uses strings to store this binary data and provides a set of commands that treat these binary strings as bitmaps. These commands make it possible to set and get any bit in a Redis string with constant time complexity (another appealing reason to explore the following potential use cases).

First use case: done in an asynchronous system

First, suppose there is an asynchronous task made up of a fixed number of steps. Each step processes in parallel and you must track when each step completes to determine when the task is “done”.

With a Redis Bitmap, keyed by the string task id, you can track the state of each step by flipping a bit (from 0 to 1) at the offset corresponding to each step number when the step is done. If the bit where the offset equals the total number of steps in the task is flipped first, then the task as a whole is done when all bits before that end offset bit have been flipped as well.

For instance, if a task has 4 steps, then flipping the bit at offset 4 (from 0 to 1) results in the following initial state:
(in this example offsets and step numbers are zero-based)

Now, when step number 2 is done, the state looks like this:

When steps 0 and 3 are done, the state looks like this:

And finally when step number 1 is done, the state looks like this: 
(and because all bits before the end bit at offset 4 have been flipped – the task is done)

Now, let’s check out the example Java project I mentioned ( For both use cases it all begins in the trigger-app. In the trigger-app there is a triggerDone method (and API definition) in that will trigger an example task. The count request parameter represents the number of steps in the triggered example task.

The first time the project interacts with the Redis Bitmap (via the Jedis client) is in that triggerDone method. This is where the bit offset equaling the total number of steps in the task is flipped (just as described above):

// set "last" bit to true, initializing an end of steps marker for this task
// before this task is considered done, all bits before this "last" bit must also be set to true
Jedis jedis = new Jedis(redisConnectionInfo);
jedis.setbit(taskId, count, true);

Then the method goes on to issue requests for each individual step in parallel to the API defined in done-app. In the example step by step state walkthrough above, there was one important bit of logic I glossed over: how exactly do you determine all bits before our end bit have been flipped?

That logic is in the isDone method in and it looks like this:

private static boolean isDone(Jedis jedis, String task) {
    // get the index of the smallest false bit for use in determining if the task on the whole is done
    Long leftMostZero = jedis.bitpos(task, false);
    // count the number of true bits aka the number of steps that are done
    long count = jedis.bitcount(task);
    // check if done
    boolean done = (leftMostZero == null || leftMostZero < 0 || leftMostZero == count);
    if (done) {"Done with all {} steps for task: {}", count - 1, task);
    return done;

Three things make this determination possible:

  1. The Redis BITPOS command that will return the position of the first bit set to 0
  2. The Redis BITCOUNT command that will count the number of set bits
  3. The fact that in the trigger-app the first bit flipped was the bit where the offset equals the total number of steps

Put all three of those things together and you know if you do not find a BITPOS 0 or if that BITPOS 0 equals the BITCOUNT, the task is done.

Let’s take a final look at that initial example step by step state walkthrough:

In the initial state, BITPOS 0 is 0 and BITCOUNT is 1 (the task is not done):

When steps 0, 2, and 3 are done, BITPOS 0 is 1 and BITCOUNT is 4 (the task is still not done):

But finally, when step number 1 is done, BITPOS 0 and BITCOUNT both equal 5 (the task is done!):

Second use case: collecting distinct activity metrics

On to the second use case: collecting distinct activity metrics. The first use case outlined how to flip a bit at a unique position given an identifier (bits were flipped when each step was done) and the BITCOUNT command was used for the isDone check for the task as a whole. Those two commands are all you will need to count and track the number of unique users in this use case.

Let’s take a look at from the example project in the distinct-app. This example is rather simple, our API takes in the int userId and we set the corresponding bit like so:

// set bit to true, which accounts for the distinct user
jedis.setbit(REDIS_KEY, userId, true);

And if the bit was already flipped at this userId offset (i.e. this user is not new/unique) the count logged below stays the same:

// count the number of true bits aka the number of distinct users
long count = jedis.bitcount(REDIS_KEY);"{} distinct users", count);

Just like in the prior use case, if you want to try this use case out for yourself, look in The triggerDistinct method (and API definition) will trigger a variable amount of “userId” activity and the distinct-app will track the number of unique users accordingly.

In conclusion

I want to emphasize that Redis Bitmaps don’t fit every problem, but I do think it is a clever tool to have in the toolbox when time and space (especially space) is at a premium and you have a lot of state to track. Hopefully this post, the provided example Java project ( and a couple mock use cases was enough to illustrate that.

About the Author

Aaron Burk profile.

Aaron Burk

Director of Technology

Aaron Burk is a Director of Technology at Object Partners/Improving located in Minneapolis, MN. He is passionate about building and designing highly scalable and available distributed software systems and is currently working with technologies like Java, Apache Kafka, Spring Boot, Kubernetes, Terraform, to name a few.

Leave a Reply

Your email address will not be published.

Related Blog Posts
Natively Compiled Java on Google App Engine
Google App Engine is a platform-as-a-service product that is marketed as a way to get your applications into the cloud without necessarily knowing all of the infrastructure bits and pieces to do so. Google App […]
Building Better Data Visualization Experiences: Part 2 of 2
If you don't have a Ph.D. in data science, the raw data might be difficult to comprehend. This is where data visualization comes in.
Unleashing Feature Flags onto Kafka Consumers
Feature flags are a tool to strategically enable or disable functionality at runtime. They are often used to drive different user experiences but can also be useful in real-time data systems. In this post, we’ll […]
A security model for developers
Software security is more important than ever, but developing secure applications is more confusing than ever. TLS, mTLS, RBAC, SAML, OAUTH, OWASP, GDPR, SASL, RSA, JWT, cookie, attack vector, DDoS, firewall, VPN, security groups, exploit, […]