Access Control Tree

Hierarchical permissions

Design a tree of resources, like folders and files, where a permission granted on a folder applies to everything inside it unless a lower node says otherwise.

Overview

Picture a shared drive, where folders hold files and other folders. You grant a team WRITE on the folder /eng, and every file under /eng is writable by that team without a grant on each file. Then one file holds secrets, so you block the team there while one person keeps READ. The system must answer one question fast and correctly: what may this user do on this node?

The problem tests three things. First, a clear resolution rule: when grants at different levels, or for a user and a group, disagree, which one wins? Say the rule in one sentence before you write code. Second, the tree itself: finding a node by path, creating missing folders like mkdir -p, and moving a subtree without creating a cycle. Third, the cost of a check: walking up the tree on every check is simple and always correct; caching is faster but must be cleared when anything changes.

A strong answer states the rule, draws the tree with a worked example, writes the walk-up resolver, and then discusses caching, groups and persistence as follow-ups.

Scoping the problem

Ask these questions before you write code; each one changes the resolver.

Are permissions ordered levels, or independent rights? — Levels compare with >=; independent rights need a set or bit flags — Levels: NONE, READ, WRITE, DELETE, ADMIN
Can a lower node take away what a folder granted? — Needs an explicit block, not just a missing entry — Yes: an explicit NONE blocks
Are there groups? What if a user and their group disagree on one node? — Decides the tie-break at one node — Yes; the user's own entry wins
What if two of the user's groups disagree? — Most permissive or least permissive — The highest level wins
How often are grants changed compared with checks? — Decides between walking up and caching — Checks far outnumber changes
Can subtrees be moved? — A move changes what every node below inherits — Yes, with a cycle check

The resolution rule

One sentence: walk up from the node; the first node that has any entry for the user or one of their groups decides; at that node the user's own entry beats group entries, and among groups the highest level wins; if no node has an entry, the answer is NONE.

Levels are ordered, so 'may Bob write?' is effective >= WRITE. A higher level includes every lower one: DELETE implies WRITE, which implies READ.

Core entities

A principal is a string: user:ann or group:eng. Keeping both kinds in one entries dictionary means one lookup per node, and the prefix tells the resolver which kind won.

A worked example

The demo builds this tree. Ann and Bob are in group eng; Carl is in no group.

bob on /eng/frontend — frontend (no entry), eng (group:eng) — /eng — WRITE
bob on secrets.txt — secrets.txt (group:eng) — secrets.txt — NONE: blocked below the grant
ann on secrets.txt — secrets.txt (user:ann and group:eng) — secrets.txt — READ: the user entry beats the group
carl on /eng — eng, / (no entry for carl) — nowhere — NONE
root on /hr — hr, / (user:root) — / — ADMIN

Moving a subtree

A move re-parents one node. Nothing is copied: every node below simply starts inheriting from its new ancestors. Two checks come first: the root cannot move, and the destination must not be the node itself or anything inside it, or the tree would become a cycle with no root.

Checks, cache and the lock

A check costs one step per level of depth, O(d). The code keeps a cache of results keyed by node and user, so a repeated check is one dictionary lookup. Any change (grant, revoke, group membership, move) clears the whole cache. That is blunt, but it is obviously correct, and grants change far less often than checks run.

One lock guards the tree, the entries, the groups and the cache. A check takes it too, because it may fill the cache. Python's standard library has no readers-writer lock, and a check under the lock is a few dictionary lookups, so a single lock is the simple, correct choice here; the key questions cover what to do when that stops being enough.

What you will be able to do

State a resolution rule in one sentence and trace it on a small tree.
Explain why an explicit NONE is different from a missing entry.
Implement lookup by path, mkdir -p style creation, and a move with a cycle check.
Weigh walking up on every check against caching and eager propagation.
Store the tree in PostgreSQL and resolve a permission with a recursive query.

Functional requirements

Create nodes by path, creating missing parents like mkdir -p
Grant or revoke a permission level for a user or a group on any node
Resolve the effective permission: the nearest node with a matching entry decides; there the user entry beats groups, and the highest group level wins
An explicit NONE on a lower node blocks a grant from above
can(path, user, needed) answers effective >= needed
List the children of a node that a user may read
Move a subtree to a new parent, refusing moves of the root and moves under itself

Non-functional requirements

A check costs O(d) for depth d, or O(1) when the cached result is still valid
Every change clears the cache, so a check never sees a stale result
Safe with many threads: one lock guards the tree, entries, groups and cache
Adding a permission level is one enum member; the comparison code does not change

Interview questions

Why ordered levels instead of separate rights?
User and group entries disagree. Which one wins, and what do real systems do?
Checks walk up the tree every time. How would you make them faster?
How do you prevent a cycle when a folder is moved?
How would you store this in a database?
One lock guards everything. When is that not enough?