Why does explicit deny override explicit allow in ACL evaluation?

Deny-override semantics prevent accidental permission grants from overriding intentional restrictions. If a user belongs to multiple groups and one group is explicitly denied access, that denial must hold regardless of other group memberships. This is the behavior of AWS IAM, Azure RBAC, and most enterprise authorization systems.

How deep can a role hierarchy be before causing performance issues?

A recursive CTE resolves any DAG depth in a single query, but deep hierarchies (more than 10 levels) can slow resolution. In practice, well-designed role trees stay under 5 levels. The recursive CTE result can be cached per user at login time and invalidated only on role membership changes, making depth a one-time cost rather than a per-request cost.

How should cache invalidation work when a role's permissions change?

When a role's ACL entries change, all users who hold that role (directly or via inheritance) must have their cached decisions invalidated. The system queries RoleMembership to find affected user IDs, then deletes all cache keys for those subjects. For very large role memberships, a background job processes invalidation asynchronously while the TTL provides a bounded staleness window.

How do wildcard resource permissions interact with specific resource entries?

Wildcard entries (resource_id = '*') apply to all resource instances but are overridden by specific entries at the same or higher subject tier. A user-level specific allow beats a role-level wildcard deny. If both a specific and a wildcard entry exist at the same subject tier, the specific entry takes precedence to support exception-to-the-rule patterns.

How does deny override allow in ACL evaluation?

The evaluator collects all applicable ACL entries for the subject-resource-action tuple. An explicit DENY from any entry immediately returns denied, regardless of ALLOW entries from other roles or groups.

How is role hierarchy traversal implemented efficiently?

A recursive CTE walks the parent_role_id chain to collect all ancestor roles; the full set of inherited permissions is resolved in a single query without application-side recursion.

How is the permission cache invalidated when roles change?

On any change to RoleMembership or AclEntry, all cache keys matching the affected subject are deleted using a Redis key prefix scan (SCAN + DEL pipeline), ensuring stale decisions are never served.

How are wildcard resource permissions represented?

A NULL resource_id in AclEntry matches any resource of the given type; the evaluator checks for exact-match entries first, then wildcard entries, applying deny-override across both sets.

Access Control List System Low-Level Design: Permission Checks, Role Hierarchy, and Policy Evaluation

⏱ 7 min read

What Is an Access Control List System?

An Access Control List (ACL) system determines whether a given subject is permitted to perform a specific action on a specific resource. It is the foundational mechanism behind file system permissions, cloud IAM policies, API gateway authorization, and multi-tenant SaaS authorization layers. At low level, it must handle role hierarchies, explicit deny overrides, and high-throughput permission lookups with minimal latency.

Permission Model

Every permission check resolves three components:

Subject: the actor — a User, Group, or Role identified by (subject_type, subject_id).
Resource: the object being accessed — identified by (resource_type, resource_id). A wildcard resource_id of * applies to all instances of a type.
Action: the operation — read, write, delete, admin, or a domain-specific verb like publish.

The decision is binary: allow or deny. The evaluation engine collects all ACL entries matching the triple and applies a precedence rule.

Role Hierarchy and Permission Inheritance

Roles are organized in a directed acyclic graph. A child role inherits all permissions granted to its parent roles. This allows an editor role to inherit from viewer without duplicating entries.

Transitive role resolution is done with a recursive CTE:

-- Resolve all ancestor roles for a given user
WITH RECURSIVE role_tree AS (
  SELECT rm.role_id
  FROM RoleMembership rm
  WHERE rm.user_id = :user_id

  UNION ALL

  SELECT r.parent_role_id
  FROM Role r
  JOIN role_tree rt ON r.id = rt.role_id
  WHERE r.parent_role_id IS NOT NULL
)
SELECT DISTINCT role_id FROM role_tree;

This query returns the full set of roles applicable to a user, including transitive ancestors. The result feeds into the ACL entry lookup.

ACL Entry Structure

Each entry records a permission grant or denial:

CREATE TABLE AclEntry (
  id             BIGSERIAL PRIMARY KEY,
  subject_type   VARCHAR(16) NOT NULL,  -- 'user', 'group', 'role'
  subject_id     BIGINT      NOT NULL,
  resource_type  VARCHAR(64) NOT NULL,
  resource_id    VARCHAR(64) NOT NULL,  -- '*' for wildcard
  action         VARCHAR(32) NOT NULL,
  effect         VARCHAR(8)  NOT NULL   -- 'allow' or 'deny'
);

CREATE INDEX idx_acl_lookup ON AclEntry (subject_type, subject_id, resource_type, resource_id, action);

Entries exist at user, group, or role level. A user's effective ACL is the union of entries for that user directly plus all groups they belong to plus all roles (and ancestor roles) they hold.

Supporting Schema

CREATE TABLE Role (
  id             BIGSERIAL PRIMARY KEY,
  name           VARCHAR(64) UNIQUE NOT NULL,
  parent_role_id BIGINT REFERENCES Role(id)
);

CREATE TABLE RoleMembership (
  user_id  BIGINT NOT NULL,
  role_id  BIGINT NOT NULL REFERENCES Role(id),
  PRIMARY KEY (user_id, role_id)
);

CREATE TABLE GroupMembership (
  user_id  BIGINT NOT NULL,
  group_id BIGINT NOT NULL,
  PRIMARY KEY (user_id, group_id)
);

CREATE TABLE Permission (
  id           BIGSERIAL PRIMARY KEY,
  role_id      BIGINT NOT NULL REFERENCES Role(id),
  resource_type VARCHAR(64) NOT NULL,
  resource_id   VARCHAR(64) NOT NULL,
  action        VARCHAR(32) NOT NULL
);

Policy Evaluation Order

After collecting all applicable ACL entries for a (subject, resource, action) triple, the engine applies this precedence chain:

Explicit deny at user level — highest priority, terminates evaluation immediately.
Explicit allow at user level.
Explicit deny at group level.
Explicit allow at group level.
Deny/allow inherited through role hierarchy — traversed from child to ancestor.
Default deny — if no entry matches, access is denied.

This mirrors AWS IAM semantics: an explicit deny always wins, regardless of where the allow originates.

Python Implementation

import redis
import json
from db import get_db

cache = redis.Redis(host='localhost', port=6379, db=0)
CACHE_TTL = 60  # seconds

def get_effective_roles(user_id: int) -> list[int]:
    """Return all role IDs applicable to user_id via recursive CTE."""
    db = get_db()
    rows = db.execute("""
        WITH RECURSIVE role_tree AS (
          SELECT rm.role_id FROM RoleMembership rm WHERE rm.user_id = %s
          UNION ALL
          SELECT r.parent_role_id FROM Role r
          JOIN role_tree rt ON r.id = rt.role_id
          WHERE r.parent_role_id IS NOT NULL
        )
        SELECT DISTINCT role_id FROM role_tree
    """, (user_id,)).fetchall()
    return [r['role_id'] for r in rows]

def get_group_ids(user_id: int) -> list[int]:
    db = get_db()
    rows = db.execute(
        "SELECT group_id FROM GroupMembership WHERE user_id = %s", (user_id,)
    ).fetchall()
    return [r['group_id'] for r in rows]

def evaluate_acl(entries: list[dict]) -> str:
    """Apply precedence: explicit deny > explicit allow > inherited deny > inherited allow > deny."""
    for effect_priority in ['deny', 'allow']:
        for entry in entries:
            if entry['effect'] == effect_priority:
                return effect_priority
    return 'deny'

def check_permission(
    subject_id: int,
    resource_type: str,
    resource_id: str,
    action: str
) -> bool:
    cache_key = f"acl:{subject_id}:{resource_type}:{resource_id}:{action}"
    cached = cache.get(cache_key)
    if cached:
        return json.loads(cached) == 'allow'

    db = get_db()
    role_ids = get_effective_roles(subject_id)
    group_ids = get_group_ids(subject_id)

    entries = db.execute("""
        SELECT subject_type, subject_id, effect
        FROM AclEntry
        WHERE action = %s
          AND resource_type = %s
          AND (resource_id = %s OR resource_id = '*')
          AND (
            (subject_type = 'user'  AND subject_id = %s) OR
            (subject_type = 'group' AND subject_id = ANY(%s)) OR
            (subject_type = 'role'  AND subject_id = ANY(%s))
          )
        ORDER BY
          CASE subject_type WHEN 'user' THEN 0 WHEN 'group' THEN 1 ELSE 2 END,
          CASE effect WHEN 'deny' THEN 0 ELSE 1 END
    """, (action, resource_type, resource_id, subject_id, group_ids, role_ids)).fetchall()

    decision = evaluate_acl([dict(e) for e in entries])
    cache.setex(cache_key, CACHE_TTL, json.dumps(decision))
    return decision == 'allow'

def invalidate_permission_cache(subject_id: int):
    """Call after any ACL or role membership change for this subject."""
    pattern = f"acl:{subject_id}:*"
    for key in cache.scan_iter(pattern):
        cache.delete(key)

Hot-Path Caching Strategy

Permission checks sit on the hot path of every API request. Evaluating recursive CTEs and multi-table joins on every call is too slow. The cache layer stores the final allow/deny decision keyed by (subject_id, resource_type, resource_id, action) in Redis with a 60-second TTL.

Invalidation is triggered by any write to AclEntry, RoleMembership, or GroupMembership. Rather than fine-grained key tracking, the system scans and deletes all cache keys matching the affected subject_id. This is acceptable because role/permission changes are rare compared to read frequency.

For very large deployments, a pub/sub channel broadcasts invalidation messages to all application servers, each of which maintains a local in-process LRU cache on top of Redis. The two-tier cache (local LRU + Redis) reduces Redis round-trips for the most frequently checked permissions.

Wildcard Resource Permissions

An AclEntry with resource_id = * applies to all instances of that resource_type. The lookup query checks both the specific resource_id and *. Specific entries take precedence over wildcards by applying user-level > group-level > role-level ordering first, then deny > allow within each tier.