Access Management System

Role-based access control

Design a role-based access control system: users hold roles, roles hold permissions and inherit from other roles, and one check answers whether a user may do an action on a resource.

Overview

An access management system answers one question many times a second: may this user do this action on this resource? Role-based access control (RBAC) answers it in two hops. Permissions are attached to roles, and roles are given to users. Changing what a job title may do means editing one role, not thousands of users.

RBAC was formalized at NIST; the NIST model became the American National Standard INCITS 359 in 2004 (revised in 2012). The standard splits into Core RBAC (users, roles, permissions and the two assignments between them), Hierarchical RBAC (roles that inherit from other roles) and separation-of-duty constraints. The interview problem covers the first two.

Interviewers use this problem to see how you model a small graph (roles inheriting from roles), how you resolve permissions through it without cycles or repeated work, and how you make the check both fast and safe to call from many threads. A strong answer draws the role graph, writes the resolution as a graph walk with a visited set, caches the result, and explains when the cache is thrown away.

Scoping the problem

Can a user hold several roles? — The check becomes a union over roles — Yes
Do roles inherit from other roles? — Adds a graph walk and cycle detection — Yes; one or more parents
What is a permission: an action, or an action on a named resource? — Decides the key: (resource, action) — Action on a resource, with a wildcard resource
Are there deny rules? — Changes resolution from 'any allow' to 'no deny, then any allow' — Not in the core; a follow-up
Ratio of checks to changes? — Justifies caching the resolved set — Checks far outnumber changes
Many threads? — Needs a lock around role and assignment changes — Yes

The role graph

Inheritance points from the more powerful role to the roles it includes. editor inherits viewer, so every viewer permission is an editor permission too. A role may have more than one parent, so the structure is a directed graph, not a tree; it must not contain a cycle.

Resolving a role means walking up from it and collecting permissions from every role reached. The walk keeps a visited set, so a role reachable by two paths (here viewer from admin) is counted once and the walk is O(roles + edges).

viewer — read:docs — none — read:docs
editor — write:docs — viewer — read:docs, write:docs
billing — read:invoices, write:invoices — viewer — read:docs, read:invoices, write:invoices
admin — delete:* — editor, billing, viewer (once) — all of the above plus delete on any resource

Caching and invalidation

The walk is cheap, but a service does it on every request, so cache each role's effective set. The hard part is knowing when the cache is wrong.

Grant or revoke a permission on role R — R and every role that inherits from R, directly or not — Clear the whole cache
Add a parent to R — R and every role that inherits from R — Clear the whole cache
Assign or unassign a role to a user — none; the user's set is a union computed at check time — Nothing
Create a role with no children — only the new role — Nothing

Clearing everything on any role change is correct and simple, and it is what the code below does. Role changes are rare; the next check on each role rebuilds its set once. A targeted invalidation (follow the parent edges backwards and evict only the roles that inherit from the changed one) is an optimization to describe, not to write first.

Cycle detection

A cycle in the parent graph would make the walk loop forever without a visited set, and with one it would give every role in the cycle the same permissions, which is never intended. Refuse the edge when it is added: before making P a parent of R, check whether R is already reachable from P.

Thread safety

One lock protects every change (create, grant, revoke, assign) and every check. Python's threading module has Lock and RLock but no reader-writer lock, so a real read-mostly optimization needs a third-party lock or a copy-on-write design: build the new role graph and cache off to the side, then swap one reference under the lock. The code keeps one Lock; the check's critical section is a dict lookup and a set scan, so contention is low.

One Lock (this code) — serialized — serialized — simplest; fine while the check is a few dict lookups
Reader-writer lock — parallel — exclusive — not in the standard library
Copy-on-write snapshot — lock-free; read one reference — build a new snapshot, swap it — reads never see a half-applied change

Real systems to name

NIST / INCITS 359 — Core, Hierarchical, Static and Dynamic separation of duty — The standard behind the interview problem
Kubernetes RBAC — Role and ClusterRole hold rules; RoleBinding and ClusterRoleBinding attach them to subjects — Permissions are purely additive; there are no deny rules
AWS IAM — Policies, not roles alone — Everything is implicitly denied; an explicit deny overrides any allow

What you will be able to do

Model users, roles and permissions so that a permission change touches one role, not every user.
Resolve a role's effective permissions through a graph with a visited set, and refuse cycles when edges are added.
Cache the resolved sets and say exactly which changes invalidate them.
Make the manager safe for many threads with one lock, and describe the read-mostly alternatives.
Extend the design to deny rules and wildcards, and name the systems that made each choice.

Functional requirements

Create roles; a role may inherit from one or more parent roles
Grant and revoke permissions, each an action on a resource, on a role
Assign and unassign roles to users; a user may hold several roles
check(user, resource, action) returns whether any of the user's roles, directly or through inheritance, holds a covering permission
A wildcard resource (*) covers every resource for that action
Every check is recorded in an audit list with its decision

Non-functional requirements

A check is a few dict lookups after the first resolution of each role; the graph walk is cached
Any change to roles or permissions invalidates the cache before the change becomes visible
Cycles in the role graph are refused when the edge is added
All changes and checks are safe under concurrent access from many threads
Unknown users fail closed: the check returns False

Interview questions

How would you add deny rules?
Resolve permissions on every check, or precompute them per user?
How do resource-level permissions work at scale? Listing every document is not possible.
What happens when a role or a permission is removed while requests are in flight?
Why is AccessManager not a Singleton, as in many sample solutions?