8000 Batch composite-role expansion to avoid an N+1 of getChildRoles on the cache-miss path by hakdogan · Pull Request #50370 · keycloak/keycloak · GitHub
[go: up one dir, main page]

Skip to content

Batch composite-role expansion to avoid an N+1 of getChildRoles on the cache-miss path - #50370

Merged
ahus1 merged 10 commits into
keycloak:mainfrom
hakdogan:composite-role-n1-reduction-main
Jun 30, 2026
Merged

ahus1 merged 10 commits into
keycloak:mainfrom
hakdogan:composite-role-n1-reduction-main

Conversation

@hakdogan
Copy link
Copy Markdown
Contributor

Closes #50369

Problem

On the cache-miss path (realm/user cache disabled, cold cache, or after invalidation), resolving a user's effective roles dominates Keycloak CPU. Expanding the composite-role tree issues one getChildRoles query per role (an N+1), and under FlushMode.AUTO each query is preceded by a full persistence-context auto-flush, so the cost is O(roles in the tree) × auto-flush. Profiling shows the composite-expansion path accounting for the majority of CPU and a large multiplier on database queries (before/after numbers in #50369).

Cause

RoleUtils.expandCompositeRolesStream walks the tree node by node. On the JPA RoleAdapter every node runs the getChildRoles named query — composite nodes twice, once for isComposite() and once for getCompositesStream() — each preceded by an auto-flush. This is reached on the token/permission paths via TokenManager.getAccess, DefaultClientSessionContext, and the admin fine-grained RolePolicyProvider (through getDeepUserRoleMappings / expandCompositeRolesStream).

This is distinct from #46622, which addressed the startup / cache-warm scan; FlushMode.AUTO (#10411 / #10623) is intentional, so the fix targets the N+1 multiplier rather than the flush mode.

Fix

  1. Drop the redundant pre-query in expandCompositeRolesStream: fetch composites directly instead of gating on isComposite() first — getCompositesStream() already returns an empty stream for non-composite roles — removing one getChildRoles (and its auto-flush) per composite node.

  2. Batch the walk with a level-wise IN: a new default method RoleProvider.getCompositeRolesStream(RealmModel, Set<String> parentRoleIds), overridden in JpaRealmProvider with a single getChildRolesFromParentIds IN query (and delegated by RoleStorageManager); a new RoleUtils.expandCompositeRoles(KeycloakSession, RealmModel, Set<RoleModel>) expands one breadth-first level per query (O(tree depth) instead of O(tree size)), preserving cycle protection and de-duplication. The token/permission paths use the session-aware variants.

Kept intentionally compatible:

  • RoleProvider.getCompositeRolesStream is a default method — custom / non-JPA providers run unchanged (unbatched) and can opt in by overriding it;
  • RoleUtils additions are new overloads; existing methods are untouched;
  • TokenManager.getAccess keeps its existing (UserModel, ClientModel, Stream) signature (delegating to the per-node expansion); the batched path is a new (KeycloakSession, …) overload — no public API break;
  • no DB schema change (the added @NamedQuery is metadata only).

Testing

  • RoleUtilsCompositeExpansionTest (server-spi) — expansion result unchanged, isComposite() no longer called during the walk, cyclic graphs still terminate.
  • RoleProviderCompositeDefaultTest (server-spi) — a custom RoleProvider that does not override getCompositeRolesStream still resolves composites correctly (de-duplicated) via the interface default.
  • CompositeRoleExpansionQueryCountTest (testsuite/model, -Pjpa) — counts actual getChildRoles SQL executions: on a wide tree (31 roles, depth 3) the node-by-node walk issues 31 queries, the batched w 8000 alk 3, with the same resolved set.
  • Existing RoleModelTest and CompositeRolesModelTest remain green.

Hüseyin Akdoğan added 3 commits June 26, 2026 17:18
RoleUtils.expandCompositeRolesStream gated each node on isComposite()
before calling getCompositesStream(). On the JPA (cache-miss) path both
run the getChildRoles named query -- and a FlushMode.AUTO flush before
each -- so every composite node issued two getChildRoles round-trips
while expanding the tree. getCompositesStream() already yields an empty
stream for non-composite roles, making the pre-check redundant.

Fetch the composites directly instead. Behaviour is unchanged (verified
by RoleUtilsCompositeExpansionTest: identical expansion, isComposite()
no longer called, cycles still terminate). On a 10-node composite chain
the deterministic query-count model test (CompositeRoleExpansionQueryCountTest,
jpa profile) shows getChildRoles executions drop from 19 to 10 -- the
saving equals the number of composite nodes (C) per expansion.

Signed-off-by: Hüseyin Akdoğan <huseyin@keymate.io>
The composite-role walk in RoleUtils issues one getChildRoles query per
role node. On a cache miss this is an N+1 over the whole role tree, each
query preceded by a FlushMode.AUTO flush.

Add a bulk primitive RoleProvider.getCompositeRolesStream(realm, parentIds)
-- default resolves each parent individually, JpaRealmProvider overrides it
with a single getChildRolesFromParentIds named query (IN clause) that
hydrates the child RoleEntity rows so the follow-up getRoleById calls are
served from the persistence context. RoleStorageManager delegates to local
storage.

RoleUtils.expandCompositeRoles(session, realm, roles) uses it to expand the
tree one breadth-first level at a time: one query per level instead of one
per node, while preserving the visited-set cycle protection and dedup.

CompositeRoleExpansionQueryCountTest (jpa profile) proves it on a 31-node
wide tree (root -> 5 -> 25): the per-node walk issues 31 getChildRoles
queries, level-wise batching issues 3 (one per depth), and both produce the
same expanded role set.

Signed-off-by: Hüseyin Akdoğan <huseyin@keymate.io>
Route the composite-role expansion on the token and permission paths through
the level-wise batched RoleUtils variants so the N+1 reduction reaches the
flows the load test exercises.

Add session-aware RoleUtils.getDeepUserRoleMappings(session, realm, user) and
expandCompositeRolesStream(session, realm, roles), and switch:
 - TokenManager.getAccess: add a session-aware overload; the existing
   (UserModel, ClientModel, Stream) signature is kept and delegates to the
   per-node expansion, so the public API is unchanged,
 - DefaultClientSessionContext client-scope role expansion and user roles,
 - RolePolicyProvider (admin fine-grained permissions) deep user role mappings.

The non-session methods are kept for callers without a session. Behaviour is
unchanged: the batched expansion returns the same role set as the per-node
walk (CompositeRoleExpansionQueryCountTest); a custom RoleProvider that does
not override getCompositeRolesStream still resolves composites via the
interface default (RoleProviderCompositeDefaultTest); RoleModelTest and
CompositeRolesModelTest pass.

Signed-off-by: Hüseyin Akdoğan <huseyin@keymate.io>
@hakdogan
hakdogan requested a review from a team as a code owner June 26, 2026 14:31
Copilot AI review requested due to automatic review settings June 26, 2026 14:31
@hakdogan
hakdogan requested review from a team as code owners June 26, 2026 14:31
Copilot AI left a comment
Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Pull request overview

This PR optimizes composite-role expansion on the cache-miss path by removing a redundant per-role isComposite() pre-query and introducing a breadth-first, level-wise batched expansion API that allows JPA to resolve composite children with an IN query per level (O(tree depth) queries) instead of one query per role (O(tree size)).

Changes:

  • Remove isComposite() gating during per-node expansion to avoid an extra getChildRoles query (and associated auto-flush) per composite role.
  • Add a bulk composite expansion path (RoleProvider#getCompositeRolesStream + new RoleUtils overloads) and wire it into token/scope/access resolution and admin authz role policy evaluation.
  • Add tests validating expansion correctness and (for JPA) reduced query counts.

Reviewed changes

Copilot reviewed 12 out of 12 changed files in this pull request and generated 2 comments.

Show a summary per file
File Description
testsuite/model/src/test/java/org/keycloak/testsuite/model/role/CompositeRoleExpansionQueryCountTest.java Adds a JPA/Hibernate-statistics-based test to assert query-count reduction for batched expansion.
services/src/main/java/org/keycloak/services/util/DefaultClientSessionContext.java Switches client-scope role expansion and access resolution to session/realm-aware bulk expansion.
services/src/main/java/org/keycloak/services/resources/account/AccountConsole.java Uses the new TokenManager.getAccess(session, ...) overload for bulk expansion.
services/src/main/java/org/keycloak/protocol/oidc/TokenManager.java Adds a session-aware getAccess overload and factors expansion via an injected function.
server-spi/src/test/java/org/keycloak/models/utils/RoleUtilsCompositeExpansionTest.java Adds unit coverage asserting expansion correctness and that isComposite() is not called.
server-spi/src/test/java/org/keycloak/models/RoleProviderCompositeDefaultTest.java Adds unit coverage for RoleProvider#getCompositeRolesStream default behavior (dedupe across parents).
server-spi/src/main/java/org/keycloak/models/utils/RoleUtils.java Removes redundant isComposite() pre-check and adds bulk expansion APIs for session/realm-aware batching.
server-spi/src/main/java/org/keycloak/models/RoleProvider.java Introduces default bulk API getCompositeRolesStream(realm, parentRoleIds) for batched child-role lookup.
model/storage-private/src/main/java/org/keycloak/storage/RoleStorageManager.java Delegates the new bulk composite lookup API to local storage.
model/jpa/src/main/java/org/keycloak/models/jpa/JpaRealmProvider.java Overrides bulk composite lookup with a single IN named query per level.
model/jpa/src/main/java/org/keycloak/models/jpa/entities/RoleEntity.java Adds getChildRolesFromParentIds named query for batched child-role resolution.
authz/policy/common/src/main/java/org/keycloak/authorization/policy/provider/role/RolePolicyProvider.java Switches deep role mapping resolution to the new bulk session/realm-aware API.

- CompositeRoleExpansionQueryCountTest: require JpaConnectionProvider so the
  test is skipped rather than failing with an NPE on non-JPA backends (it
  reads Hibernate statistics via JpaConnectionProvider).
- RoleProviderCompositeDefaultTest: pass a non-null RealmModel (honoring the
  getCompositeRolesStream contract) instead of null.

Signed-off-by: Hüseyin Akdoğan <huseyin@keymate.io>
@ahus1 ahus1 self-assigned this Jun 28, 2026
ahus1 added 4 commits June 29, 2026 02:33
Signed-off-by: Alexander Schwartz <alexander.schwartz@ibm.com>
Signed-off-by: Alexander Schwartz <alexander.schwartz@ibm.com>
…er Keycloak strategy

Signed-off-by: Alexander Schwartz <alexander.schwartz@ibm.com>
Signed-off-by: Alexander Schwartz <alexander.schwartz@ibm.com>
Copilot AI review requested due to automatic review settings June 29, 2026 00:43
@ahus1
ahus1 requested a review from a team as a code owner June 29, 2026 00:43
Copilot AI left a comment
Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Pull request overview

Copilot reviewed 10 out of 10 changed files in this pull request and generated 7 comments.

Copilot AI and others added 2 commits June 29, 2026 03:19
- RoleUtils.expandCompositeRoles: guard against null KeycloakSession by
  falling back to per-role stack expansion when no session context is
  available (fixes r3488823474)
- RoleStorageManager.getCompositeRolesStream: split parent IDs into local
  and external; external (federated) IDs fall back to per-role
  getRoleById + getCompositesStream instead of being silently dropped
  (fixes r3488823485)
- RealmCacheSession.getCompositeRolesStream: prefix cache key with
  realm ID to prevent cross-realm key collisions; use String.join for
  a more predictable key format (fixes r3488823491)
- RealmCacheSession.getCompositeRolesStream: null-check the result of
  cache.get(parentId, CachedRole.class) before dereferencing it to
  prevent NPE on evicted entries (fixes r3488823493)
- CompositeRoleExpansionQueryCountTest.countQueries: save and restore
  Hibernate statistics enabled state to avoid affecting other tests
  (fixes r3488823497)
- CompositeRoleExpansionQueryCountTest: rename
  droppingIsCompositePreQueryHalvesGetChildRolesOnCompositeNodes to
  chainWalkIssuesOneQueryPerBreadthFirstLevel (fixes r3488823503)
Signed-off-by: Alexander Schwartz <alexander.schwartz@ibm.com>
@ahus1
ahus1 commented Jun 29, 2026
Copy link
Copy Markdown
Member

@hakdogan - thank you for this PR! I like the approach.

In some additional commits, I've rolled back some of the API changes to keep the original API where possible, and to pull the session from the context.

I've also moved the integration test to the new testsuite. We usually rely on integration tests, when testing models, so I remove one of the unit tests that tested models once it didn't work any more when I started to use the session.

We try to no longer add new model tests. Due to that, I moved the model test to the new testsuite.

I've also added caching to the newly added method, so that it does not touch the database all the time.

Let's see what the CI reports about this. Let me know if think these changes are valid.

Thanks!

@hakdogan
Copy link
Copy Markdown
Contributor Author

Thanks @ahus1, I really appreciate you taking this forward. I went through the changes and from our side they are valid and a clear improvement over what I opened. Keeping the original API and adding the caching layer make the result stronger, the cache-miss N+1 stays resolved, and the reworked integration test is a solid regression guard.

Thanks again for the careful review and the extra work on it.

@ahus1
ahus1 commented Jun 29, 2026
Copy link
Copy Markdown
Member

@shawkins / @pedroigor - I would like to merge this PR for the upcoming 26.7 release. Do you have any second thoughts on this or other review comments before I merge? Thanks!

@ahus1
ahus1 merged commit 5d2008e into keycloak:main Jun 30, 2026
89 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Composite-role expansion does an N+1 of getChildRoles queries (each with an auto-flush) that dominates Keycloak CPU on the cache-miss path

4 participants

0