Bitmap indexing for authorization decisions: why data shape wins

At a glance

What this is: This is an engineering analysis of Cerbos' authorization index redesign, showing that bitmap-based rule indexing outperformed policy-shaped and roaring-bitmap approaches when the data structure matched the request path more closely.

Why it matters: IAM and authorization teams should care because request-path performance is often determined by how rules are represented and filtered, not just by the evaluation logic itself.

By the numbers:

• The rule table benchmark recorded 207 allocations per operation before the bitmap redesign.

Context

Authorization engines in the request path depend on two things at once: expressive policy semantics and fast candidate filtering. When the index is shaped around policies instead of queryable dimensions, each request has to do more work than the decision itself should require.

Cerbos uses this article to show how index shape, deduplication, and allocation behaviour changed the performance profile of its PDP. The issue is not authorization logic in the abstract, but how rule data is arranged so that a request can reach the correct decision with minimal scanning and memory churn.

For IAM teams, the lesson is that authorization is an architecture problem as much as a policy problem. If the data model forces repeated intersections, candidate copying, or allocator pressure, the request path becomes the bottleneck regardless of how elegant the policy language looks on paper.

Key questions

Q: How should teams decide whether authorization indexing needs a redesign?

A: Teams should redesign when rule lookup, candidate intersection, or temporary object creation becomes a material part of request-path latency. The test is not whether policy evaluation is elegant, but whether the index shape matches the real distribution of rules and avoids needless scanning and allocation. Production-like load testing is the deciding evidence.

Q: Why do authorization systems get slower even when the decision logic stays the same?

A: Because the cost often shifts into the data path around the decision. If the engine must build intermediate sets, intersect multiple maps, or allocate throwaway structures before it can evaluate a rule, latency rises even when the policy language itself has not changed. The bottleneck is usually representation, not semantics.

Q: What are the signs that an authorization index is failing in practice?

A: Look for rising allocation counts, garbage collector activity, and a large gap between microbenchmark results and sustained throughput. Those signals usually mean the index is creating too many temporary objects or carrying a representation that is too heavy for the real rule set. Tail latency is often the first place the problem shows up.

Q: When should teams prefer a simpler bitmap over a compressed bitmap structure?

A: Prefer a simpler bitmap when the candidate universe is modest, the bitmaps are not sparse in a way that benefits from container compression, and the overhead of a richer structure outweighs its gains. If the data fits in a small, predictable word array, the simpler representation often wins on both speed and memory.

Technical breakdown

Why policy-shaped indexing slows authorization

A policy-shaped index keeps rules attached to their parent policies, which is easy to reason about but awkward to query. Each request still has to find the subset of rules that might apply, then filter the survivors again, which creates duplication and intermediate data structures. The article shows why a table-like representation improved shape by making every rule a row with explicit dimensions. That made querying more uniform, but it also turned each request into repeated set operations and allocations. In authorization systems, this matters because the request path is latency-sensitive and highly repetitive.

Practical implication: favour queryable rule structures that minimise repeated intersections and throwaway candidate sets.

How bitmap indexing changes the candidate-selection step

Bitmap indexing replaces per-request map intersections with bit-level membership tests. Each dimension value maps to a bitmap whose bits mark the bindings that match, and a request intersects those bitmaps to produce candidates. That makes candidate selection a word-level operation instead of a map-walking operation, which reduces allocation and improves cache locality. The custom design in the article went further by adding a lightweight meta layer that tracks which 64-bit words are non-zero, allowing early skip of disjoint sections. This is a data-structure optimisation, not an algorithmic shortcut: the authorization rules still evaluate, but far fewer objects are created along the way.

Practical implication: use bitmaps when authorization filters are stable enough to benefit from dense, repeatable set intersections.

Why allocator behaviour matters more than microbenchmarks under load

The article distinguishes latency in a microbenchmark from behaviour under sustained traffic. Roaring bitmaps improved single-request timing, but the load test revealed garbage collector pressure because the implementation still allocated too often. Pooling and in-place operations reduced that pressure, then a simpler bitmap improved things again because the structure better matched the actual cardinality and sparsity of the data. The key technical point is that a faster algorithm can still lose in production if it creates more short-lived objects than the runtime can comfortably manage. In request-path authorization, allocation patterns are part of the performance model.

Practical implication: benchmark authorization engines under sustained load, not only in isolated latency tests.

NHI Mgmt Group analysis

Authorization performance is often a data-shape problem before it is an algorithm problem. The article shows that the request path slowed when rule data had to be intersected through policy-shaped or overly general indexes. Once the binding data was reorganised around queryable dimensions, the system could short-circuit more work and spend less time on allocator overhead. The practitioner conclusion is that authorization design should start with how candidate rules are represented, not only how they are evaluated.

Bitmap indexing is a structural fit for high-repeat authorization lookups. Bitmaps turn membership tests into word-level operations, which is exactly what repeated request-path filtering needs when many requests ask the same kinds of questions. The custom bitmap in the article worked because it matched the scale and density of the actual dataset, not because bitmaps are universally superior. The practitioner conclusion is to choose the simplest representation that preserves fast intersection for the real rule shape.

Allocation pressure is a governance signal, not just a performance nuisance. The article makes clear that a design can look fast in microbenchmarks while still burning CPU in garbage collection under load. That means authorization teams should treat allocations per request as part of service quality, because every throwaway map or bitmap raises tail latency. The practitioner conclusion is to measure memory churn alongside p95 and p99 response time.

Custom indexing logic creates a maintenance trade-off that must be managed deliberately. The article describes a progression from a general index, to roaring bitmaps, to a simpler in-house bitmap after the team learned more about its data. That path improved performance, but it also shows that infrastructure decisions in authorization can evolve quickly as usage patterns become clearer. The practitioner conclusion is to keep the index shape adaptable enough to replace one optimisation with a better-fitting one when production evidence demands it.

What this signals

Authorization infrastructure should be treated as a latency-sensitive control surface. Teams that place policy checks in the request path need to watch not only policy correctness, but also how rule representation affects CPU, memory, and tail latency. When the index becomes the bottleneck, the control plane is effectively governing performance as much as access.

Rule-shape awareness is the named design concept this article makes concrete. The index improved only when the storage model matched the shape of the authorization query, which is a reminder that policy engines need data structures built for filtering, not just for expression. Practitioners should review whether their authorization stack is optimised for evaluation or for retrieval, because those are not the same problem.

For practitioners

• Profile the authorization hot path Measure where time is spent in candidate selection, intersection, and evaluation so the team can distinguish policy logic cost from data-structure cost.
• Reduce throwaway allocations in the request path Track per-decision allocation counts and remove intermediate maps or temporary bitmaps that are created and discarded on every lookup.
• Test the index against real policy shape Benchmark using production-like rule cardinality, tenant overlap, and dimension density so the chosen structure reflects actual data, not an assumed worst case.
• Use simpler bitmaps when cardinality is small Prefer a compact bitmap with predictable word-level operations when the rule universe is modest and the overhead of container hierarchies outweighs their compression benefits.

Key takeaways

• Authorization performance depends heavily on how rules are indexed, not just on how policies are written.
• The article shows that bitmap-based filtering and simpler in-memory structures reduced both latency and memory pressure compared with the earlier index designs.
• Practitioners should benchmark authorization systems with production-like policy shapes and sustained load before choosing an indexing strategy.

Key terms

• Authorization Index: A data structure that narrows the set of rules or entitlements a request must evaluate before a decision is made. In practice, it exists to make authorization fast enough for the request path while preserving correct matching across roles, resources, actions, and other dimensions.
• Bitmap Index: A bitmap index represents matching records as bits in a compact array. In authorization systems, each bit can stand for a binding or entitlement, allowing fast set operations that reduce candidates before the engine evaluates rule payloads.
• Allocation Pressure: The performance cost created when a system repeatedly creates temporary objects during request processing. In authorization engines, allocation pressure often drives garbage collection activity, which can matter more than the raw speed of the decision logic itself once traffic becomes sustained.
• Candidate Set: A candidate set is the subset of rules that still might apply after an initial filter. Authorization engines shrink this set before checking conditions, and the efficiency of that shrink step often determines whether the evaluator stays usable at scale.

Deepen your knowledge

NHI governance, agentic AI identity, and machine identity lifecycle are core topics in our NHI Foundation Level course, the industry's only accredited NHI security programme. If you are responsible for identity security strategy or NHI governance in your organisation, it is worth exploring.