[Improvement] Use per-role policy index on JCasbin authorization hot path to avoid O(total_policies) enforce
- 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
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