Design a file sharing permissions service

The file f9 has the parent folder legal. The folder legal has the viewer group legal-team. Bob is a member of the group backend, and backend is a member of legal-team. A subject can be a single user, the members of a group, or a special subject for links. Everything is the same shape, which makes storage, caching and sharding simple.

Rules instead of copies. For each type, a small schema says how a right is computed. For a file: a user can view it if they are a direct viewer, or can edit it, or can view its parent folder. A user can edit it if they are a direct editor, or an owner, or can edit the parent folder. So editors can view because the view rule includes the edit rule, with no extra tuples stored. This is how one share on a folder covers every file below it, to any depth.

Groups. A group's members can include other groups. A check follows membership through the levels, keeps a visited set so an accidental loop cannot run forever, and stops at a depth limit, about 20. Reaching the limit counts as denied and raises an alert.

Links. Sharing by link creates a hard-to-guess secret, and a tuple that gives a viewer relation to the subject holder of that secret. A request that carries the secret is checked as that subject. Revoking the link deletes the tuple. Public access is a special subject that stands for everyone.

Evaluating. A check starts at the object and the right, and expands each branch of the rule into a lookup, run in parallel. It returns allowed as soon as one branch succeeds. The latency is the depth of the walk, not the number of branches: 4 hops of 2 ms is about 8 ms. Changes to the schema are versioned, and every check says which version it used.

The alternative, an access list on each file, breaks down at once. Sharing a folder would mean writing the list of every file below it, and revoking would mean writing them all again.

The question is Bob an editor of the legal folder is asked for every file in it. Cache the sub-result, keyed by object, right, subject and the snapshot it was computed at. A folder with 2 million files then has a few shared entries, so the cost of a check does not grow with the folder. With 95% hits, 1,000,000 checks a second become 50,000 evaluations and about 200,000 tuple reads.

Snapshots, not invalidation. Each cache entry says which snapshot it reflects, and it can serve any request that needs a snapshot no newer than that. A request with no token accepts a recent snapshot, rounded to a few seconds ago, so many requests share entries. A request with a token needs an entry at least that new. A new write creates a newer snapshot, so no one has to hunt down and delete stale entries.

Flatten group membership. Following nested groups on every check is the slow part. Keep a flattened index that lists every group a user belongs to, directly or through nesting, usually about 20. Rebuild entries from the change log when a membership tuple changes. A check then asks whether any group on the object's access path is in the user's set. The index records the snapshot it reflects. If it lags behind what a request needs, fall back to walking the live tuples for that request.

Protect the store. Many callers may ask for one popular folder's rights at once, so allow only one fetch per key and let the rest wait for it. Give each check a deadline and send a second read to another replica if the first is slow, at about 5 ms. Limit depth and fan-out, and apply per-client quotas.

Batches. A folder listing needs checks for 50 children. Accept a batch, and share sub-results inside it: the 50 files have the same parent, so the folder's rights are computed once.

Moves. Moving a folder changes one parent tuple. Everything below it picks up its new access at once, with no rewriting. The cost is that a move makes cached results for that subtree stale, which the new snapshot handles.

At time 905 someone adds a confidential file to it. If a check for the new file reads from a replica or a cache that is still at time 850, it sees Mia as a viewer, and she can open a file that was never meant for her. Access that is merely a few seconds late is usually fine. Reading an old answer for new content is not.

Consistency tokens. The tuple store gives every write a commit time from one ordered clock, and it can read as of any recent time. Each write returns its commit time as a token. The app saves it with the object the write changed. When the file is created inside the folder, the write that records its parent returns time 905, and the app stores that with the file. Every later check for it says: evaluate at a snapshot at least as new as 905. The 900 removal is before 905, so it is included, and Mia is denied.

Enforcing the token. A replica knows the latest time it has applied. If it is behind the requested time, it waits a few milliseconds, or the read goes to a fresher replica. Cache entries computed before the token are ignored. Only requests with a token pay for freshness. Others read a snapshot from a few seconds ago, which bounds the lag for a normal revocation at about 10 seconds.

Shared with me. This is the check turned around. Scanning every file for every user is impossible, so keep a reverse index: a row for each share, keyed by the subject. Each write goes to the change log, an indexer reads it in order, and adds or removes rows. Index a group share under the group, not under each of its 5,000 members. A user's listing reads their own ranges plus one for each of their roughly 20 groups, 21 reads, and merges them.

Never trust the index. It is built after the fact, so it can lag, and a lagging entry might show a file that was just revoked. So the API re-checks each candidate at the request's snapshot before returning the page, and drops the ones that fail. The worst effect of lag is that a brand new share shows up a few seconds late. If the caller passes a token from its own share, the API waits for the indexer to reach that time, or merges the new tuple in by hand, so people see what they just did.