Bitmaps for Access Control: Scaling Notification Fan-Out with Redis ACL Checks

Most engineers spend most of their time with familiar data structures: arrays, queues, sets, and maps.

That makes sense. They solve everyday problems well.

Bitmaps are different. They feel lower-level, more specialized, and easy to ignore.

That is a mistake, because in the right problem they are extremely effective.

This post is about one of those problems: using bitmaps to route real-time notifications without hitting the database on every message.

The problem

In many software-as-a-service (SaaS) systems, access control is built on many-to-many relationships, where each user can belong to several groups and each group can contain several users.

Imagine something Slack-like with one more layer of permissioning.

You have:

• users U
• groups G
• teams T

And the rules look like this:

• a user belongs to one or more groups
• a group can access one or more teams
• a message sent to a team should only reach users who are allowed to see that team

That creates a routing problem.

Every notification must reach only the correct online recipients, even when multiple permission paths exist.

When the obvious solution stops being cheap

For a long time, normal database queries may be enough. With the right database indexes, that can work well.

The more interesting case is what happens when the system starts handling tens of thousands of notifications per second.

At that point, asking the database the same access-control question over and over gets expensive. Even if each query is acceptable on its own, the total cost starts to show up in latency, central processing unit (CPU) usage, memory pressure, and infrastructure size.

That is where a different representation helps.

How to know if you have this problem

Consider bitmaps when:

• the same access query runs on every notification
• the query result changes infrequently compared to how often it is asked
• user ids can be mapped to dense numeric indexes
• you need sub-millisecond routing decisions

Why bitmaps fit this problem

A bitmap is compact and optimized for binary state.

That makes it a good fit for questions like:

• does this user have access to this team?
• is this user online right now?
• which users satisfy both conditions?

These are yes-or-no questions, and that is where bitmaps shine.

The design

For each tenant, you can represent both access and presence with Redis bitmaps:

teams:<tenantId>:<teamId>
online-users:<tenantId>

Each bit position maps to a stable numeric user index. In some systems that can be the raw user id. In others it is a separate dense mapping.

• in teams:<tenantId>:<teamId>, bit 1 means that user can access the team
• in online-users:<tenantId>, bit 1 means that user is currently online

This assumes the relationship has already been denormalized—copied into a read-optimized format.

Instead of querying relational state for every notification, you can move the hot routing step into Redis.

Example

A relational version might look like this:

SELECT
  ug.user
FROM
  groups ug
WHERE
  ug.teams IN (<list of teams>)
  AND ug.tenantId = <tenantId>

With bitmaps, the same routing step can be done with bitmap operations.

Here is a simplified example written in Lua, the scripting language Redis supports:

local tenantId = ARGV[1]
local tmp_or_key = 'tmp:teams:' .. tenantId
local notify_key = 'tmp:notification:' .. tenantId
local online_key = 'online-users:' .. tenantId

redis.call('BITOP', 'OR', tmp_or_key, unpack(KEYS))
redis.call('BITOP', 'AND', notify_key, tmp_or_key, online_key)

local max_index = redis.call('STRLEN', notify_key) * 8
local notified_users = {}
for i = 0, max_index - 1 do
  local bit = redis.call('GETBIT', notify_key, i)
  if bit == 1 then
    table.insert(notified_users, i)
  end
end

redis.call('DEL', tmp_or_key)
redis.call('DEL', notify_key)

return notified_users

This script is meant to explain the idea, not to claim that bit-by-bit scanning is always the best extraction strategy for large bitmaps.

What happens here is simple:

1. combine all target team bitmaps with OR
2. intersect that result with the online-users bitmap using AND
3. the remaining set bits are users who both have access and are online

So the routing decision becomes a few in-memory bitmap operations instead of another database query on the hot path.

Why this can be faster

Before this kind of optimization, every notification could trigger another database read, with all the usual overhead: parsing, planning, execution, buffer checks, and sometimes disk access.

Under sustained fan-out load, where one notification produces deliveries to many users, that gets expensive.

With bitmaps, the hot path becomes a set of in-memory operations on compact structures. That usually means:

• lower latency
• more predictable routing cost
• less repetitive read pressure on the database
• more room for the database to focus on writes and less cacheable queries

Trade-offs

This approach is not free.

You need:

• dense numeric identifiers, or at least a stable mapping to bitmap positions
• update flows that keep access and online-state bitmaps current
• enough confidence that avoiding repeated reads of the same underlying data is worth the extra update bookkeeping

And if cardinality, the number of distinct users, grows far enough, it is worth studying Roaring Bitmaps as a more space-efficient representation.

Practical sizing

If you have 100,000 users, a single bitmap is about 12.5 KB. If you have 1,000 teams, that is roughly 12.5 MB of bitmap data per tenant. Redis handles that easily. But if you have millions of users and tens of thousands of teams, Roaring Bitmaps become worth evaluating.

Takeaways

1. Could you do something similar with normal Sets? Yes, but memory footprint and operation cost often look worse.
2. Bitmaps are great when the problem reduces to yes-or-no membership checks.
3. They are especially useful when the same access-control question is asked at very high frequency.
4. Redis can be an efficient routing engine when you model the state in a form it can process cheaply.

Bitmaps are not a general-purpose answer to every permission problem.

But for access-control-list (ACL)-heavy notification fan-out, they can be a very sharp tool.

Quick evaluation

Before adopting bitmaps for ACL, verify:

• Your user ids can be mapped to dense numeric indexes
• Team membership changes are infrequent compared to notification volume
• You have a way to keep online-state bitmaps current
• Your total bitmap size per tenant fits comfortably in memory