apache / apache/gravitino

[Improvement] Use per-role policy index on JCasbin authorization hot path to avoid O(total_policies) enforce

Open
#12,173 0 comments 0 reactions 0 assignees View on GitHub
improvement
Dominant language
Java
Stars
3.2k
Forks
935
Avg merge
1d 16h
Merged PRs (30d)
298

Description

### What would you like to be improved?

The JCasbin authorization hot path calls `enforcer.enforce(...)` for every privilege probe (`JcasbinAuthorizer#authorizeByJcasbin`, `enforceNarrowed`, `hasDenyPolicy`). In jcasbin 1.99.0, `enforce` **linearly scans every `p` policy line** loaded in the enforcer and evaluates the aviator matcher per line — there is no index by subject/object. Cost is therefore `O(total_policies_in_enforcer)` per probe, and the enforcer accumulates policies for up to `GRAVITINO_AUTHORIZATION_ROLE_CACHE_SIZE` (default 10000) roles across all metalakes on a node.

A standalone benchmark against the real `jcasbin_model.conf` (a single user holding one role, targeting one object) confirms the scan is over **all** policies regardless of the user's role bindings:

| roles | p-rules | `enforce` avg | indexed lookup |
|---|---|---|---|
| 100 | 6,000 | ~1.0 ms | 0.06 us |
| 1,000 | 60,000 | ~12.8 ms | 0.015 us |
| 5,000 | 300,000 | ~51 ms | 0.015 us |
| 10,000 | 600,000 | **~106 ms** | 0.015 us |

One `authorize` call can trigger many probes (schema inheritance chain, per-object list checks, allow + deny enforcers, per-active-role narrowing), multiplying the cost.

### How should we improve?

Use a per-role policy index on the hot path instead of `enforce`, reducing per-probe cost from `O(total_policies)` to `O(roles_per_user)` hash probes. The same approach was previously demonstrated in #10908 / #10930.

Concretely, on the current architecture:

- Extend the `loadedRoles` cache value to carry, alongside the `role_meta.updated_at` version sentinel, a `Map` index (`PolicyKey = type + metadataId + privilege`), built in `loadPolicyByRoleEntity` with DENY-beats-ALLOW within a role.
- Replace the three `enforce` call sites (`authorizeByJcasbin`, `enforceNarrowed`, `hasDenyPolicy`) with index lookups over the user's / active roles; keep cross-role DENY precedence and the OWNER short-circuit to the owner cache.
- Preserve the current version-validation (`role_meta.updated_at`) and active-role narrowing semantics.
- Add a regression/benchmark test guarding the complexity.

Related: #10907, #10908, #10930.

Contributor guide

Open the contributing guide

Research direction

Start with JcasbinAuthorizer#authorizeByJcasbin, enforceNarrowed, and hasDenyPolicy, then trace loadPolicyByRoleEntity and the loadedRoles cache. Review jcasbin_model.conf and the behavior described in #10908 and #10930, including version validation, active-role narrowing, and OWNER handling. Done means indexed authorization replaces the hot-path scans while precedence is preserved and regression or benchmark coverage guards the complexity.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
authorization, performance
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.