Entitlement Evaluation at Request Time: Hierarchical Permission Graphs, Cache Invalidation, and the Stale-Grant Hazard

Most production authorization bugs are not injection attacks. They are stale grants — a user whose role was revoked still passing isAuthorized because a cached entitlement set hasn't expired yet. The root cause is almost always an architectural decision made too early: flatten permissions at write time, cache the flat result, and read it back at request time without a robust invalidation contract. At scale, that decision creates a correctness-vs-latency tradeoff that isn't recoverable through tuning alone.

This article treats entitlement evaluation as a distributed systems problem, not a framework configuration problem.

What the Permission Model Actually Stores

A permission graph for a multi-tenant system typically has three distinct node types: principals (users, service accounts), roles (logical collections of actions), and resources (tenant-scoped data objects). Edges encode membership, assignment, and constraint relationships. A single authorization question — "Can principal P perform action A on resource R in tenant T?" — requires graph traversal, not a point lookup.

The naive model flattens this into a per-user permission bitmap or a map[string]bool on login and stores it in the JWT or session. The failure mode is well-known: you revoke a role at 14:02, but the user's token doesn't expire until 15:00. The grant is stale for 58 minutes.

The slightly less naive model moves the flat set into a Redis hash keyed by user ID with a short TTL, typically 60–300 seconds. This is better, but the invalidation strategy is still TTL-based — which means the stale window is a tunable, not a guarantee.

Graph Traversal at Request Time

A strictly correct approach evaluates the graph on every request. For a tree-shaped role hierarchy this is cheap — O(depth × fanout) — but production graphs are not trees. They include:

• Role inheritance chains: Role B extends Role A, which inherits from Role C.
• Conditional edges: Role membership that applies only within a specific tenant or resource scope.
• Deny overrides: Explicit denials that shadow inherited grants.

Traversing this live on every request against a primary MongoDB document store is unacceptable at scale. A P99 graph read with two hops of population takes 4–12 ms per query; under load that compounds across multiple authorization checks per request.

The practical architecture is a materialized entitlement cache with event-driven invalidation rather than TTL-based expiry.

Materialized Entitlement Cache Design

For each principal-tenant pair, the cache stores a serialized entitlement set: the resolved list of (action, resource-pattern) tuples after full graph traversal. The key is ent:{tenantID}:{principalID}, and the value is a versioned, MessagePack-encoded struct.

type EntitlementSet struct {
    PrincipalID string              `msgpack:"pid"`
    TenantID    string              `msgpack:"tid"`
    Version     int64               `msgpack:"ver"`  // monotonic, from the permission store
    Grants      []Grant             `msgpack:"grants"`
    ComputedAt  time.Time           `msgpack:"computed_at"`
}

type Grant struct {
    Action          string `msgpack:"action"`
    ResourcePattern string `msgpack:"rp"`    // glob or prefix
}

The Version field is critical. It comes from the permission store's own write sequence number — a MongoDB change stream counter or an optimistic-lock version field on the role-assignment document. When the cache is read at request time, the authorizer compares the cached version against a lightweight version fence stored separately in Redis.

// versionFenceKey returns the Redis key holding the current permission-store
// version for a given tenant, updated on every mutation.
func versionFenceKey(tenantID string) string {
    return fmt.Sprintf("pfence:%s", tenantID)
}

func (a *Authorizer) Authorize(ctx context.Context, req AuthRequest) (bool, error) {
    fenceKey := versionFenceKey(req.TenantID)
    cacheKey  := fmt.Sprintf("ent:%s:%s", req.TenantID, req.PrincipalID)

    // Read fence and entitlement set in a single pipeline to avoid extra RTT.
    pipe := a.redis.Pipeline()
    fenceCmd := pipe.Get(ctx, fenceKey)
    entCmd   := pipe.Get(ctx, cacheKey)
    if _, err := pipe.Exec(ctx); err != nil && !errors.Is(err, redis.Nil) {
        return false, fmt.Errorf("cache read: %w", err)
    }

    currentFence, _ := strconv.ParseInt(fenceCmd.Val(), 10, 64)

    var ents EntitlementSet
    if raw := entCmd.Val(); raw != "" {
        if err := msgpack.Unmarshal([]byte(raw), &ents); err == nil {
            if ents.Version >= currentFence {
                return matchGrant(ents.Grants, req.Action, req.Resource), nil
            }
            // Version is behind fence: entitlement set is stale, fall through.
        }
    }

    // Cache miss or stale: recompute from the permission store.
    return a.recomputeAndCache(ctx, req)
}

The version fence is a single integer per tenant updated transactionally whenever any role assignment or role definition in that tenant changes. The fence read costs one extra Redis key access — absorbed into the pipeline — and prevents stale grants without polling the permission store on every request.

Invalidation Event Flow

The fence update must be atomic with the permission-store write. In a Go service backed by MongoDB:

1. A role-assignment mutation executes as a MongoDB transaction that increments the permVersion field on the tenant document and writes the role-assignment change.
2. A change stream consumer reads the updated permVersion and writes it to the Redis fence key using SET pfence:{tenantID} {version} with a long TTL (e.g., 24 hours — this is a fence, not a TTL-eviction mechanism).
3. The next request for any principal in that tenant sees the cache version is behind the fence, triggers recomputeAndCache, and writes a fresh EntitlementSet with the new version.

The stale window is now bounded by the change stream propagation latency — typically under 100 ms on a healthy replica set — not by a cache TTL that might be minutes long.

The Thundering Herd on Tenant-Wide Revocations

A critical edge case: an administrator revokes a shared role from 10,000 principals simultaneously. Every subsequent request by any of those principals triggers recomputeAndCache. If those requests arrive in a burst, the permission store receives 10,000 concurrent graph-traversal reads — a thundering herd.

The mitigation is a per-principal recompute lock using Redis SET NX PX:

func (a *Authorizer) recomputeAndCache(ctx context.Context, req AuthRequest) (bool, error) {
    lockKey  := fmt.Sprintf("entlock:%s:%s", req.TenantID, req.PrincipalID)
    lockToken := uuid.NewString()

    acquired, err := a.redis.SetNX(ctx, lockKey, lockToken, 2*time.Second).Result()
    if err != nil {
        return false, err
    }

    if !acquired {
        // Another goroutine is recomputing. Wait briefly and re-read the cache.
        time.Sleep(15 * time.Millisecond)
        return a.readCacheOnly(ctx, req) // returns false on continued miss
    }
    defer a.releaseLock(ctx, lockKey, lockToken)

    ents, err := a.buildEntitlementSet(ctx, req.TenantID, req.PrincipalID)
    if err != nil {
        return false, err
    }
    return a.writeCache(ctx, ents, req.Action, req.Resource)
}

This serializes recompute work per principal without blocking all principals on a global lock. The brief sleep and cache re-read handles the case where a concurrent recompute completes while the current request waits — an acceptable latency cost (15–30 ms) against the alternative of a DB storm.

Deny Semantics and Graph Ordering

When role hierarchies include explicit denials, traversal order matters. The standard model — deny overrides grant, evaluated depth-first — must be encoded into buildEntitlementSet explicitly. A flat grant list without deny markers is insufficient; you need to carry negative grants through the serialized cache.

A Grant struct should carry a Deny bool field. The matchGrant function must apply denials after all grants are collected:

func matchGrant(grants []Grant, action, resource string) bool {
    var allowed bool
    for _, g := range grants {
        if !globMatch(g.ResourcePattern, resource) {
            continue
        }
        if g.Action == action || g.Action == "*" {
            if g.Deny {
                return false // explicit deny always wins
            }
            allowed = true
        }
    }
    return allowed
}

If deny grants are not materialized into the cache, a revocation implemented as a deny override on a parent role will not propagate correctly on cache hits.

Operational Tradeoffs

Cache size: An EntitlementSet for a principal with 50 grants serializes to roughly 800–1200 bytes. At 100,000 active principals per tenant, that's 80–120 MB in Redis per tenant — within normal bounds, but worth budgeting.

Version fence durability: The fence lives in Redis. If Redis restarts without persistence, fences reset to zero. Every cached entitlement set will appear current (version ≥ 0). The mitigation is to either enable Redis AOF persistence on the fence keyspace or to treat a missing fence as a forced cache miss.

Cross-region replication: In a multi-region deployment, the fence must be written to the authoritative region's Redis and replicated before serving requests in other regions. An async replica may serve stale fence values. The safe default is to read fences from the authoritative region on security-sensitive paths and accept the cross-region RTT.

Decision Framework

Condition	Recommended Approach
Low-volume, single-tenant	Evaluate graph per request; skip cache entirely
Multi-tenant, <1K active principals/tenant	Short TTL (60s) cache; accept stale window
Multi-tenant, >10K active principals/tenant	Materialized cache + version fence + event-driven invalidation
Hierarchical roles with deny overrides	Materialize deny grants; never flatten to a pure boolean set
Cross-region, high-security	Authoritative-region fence reads on sensitive operations
Revocation SLA < 1 minute	Event-driven fence mandatory; TTL approach insufficient

Entitlement evaluation is a consistency problem dressed in security clothing. The stale-grant hazard is not closed by shortening TTLs — it is closed by replacing TTL-based expiry with version-fenced invalidation backed by an event stream. The architecture is more complex, but the correctness guarantee is qualitatively different: revocations propagate in milliseconds, not minutes, and the proof of correctness lives in the fence protocol rather than in operational hope.