RBAC to ABAC to ReBAC, with Zanzibar tuples

What it is

Three models for answering "may this subject perform this action on this object," differing in what the decision is a function of:

RBAC:   decision = f(subject's ROLES, action)
        "editors may update documents"

ABAC:   decision = f(ATTRIBUTES of subject, object, action, environment)
        "a user may update a document if user.department == doc.department
         and the time is within business hours and the request is from a
         managed device"

ReBAC:  decision = f(the RELATIONSHIP GRAPH between subject and object)
        "a user may update a document if they are its owner, or an editor
         of it, or an editor of a folder that contains it, transitively"

	RBAC	ABAC	ReBAC
Decision input	Roles	Attributes	Graph traversal
"Who can access X?"	Easy	Hard (must evaluate every subject)	Easy
"What can X access?"	Easy	Hard	Easy
Fine-grained per object	Role explosion	Natural	Natural
Hierarchies and inheritance	Manual	Manual	Native
Latency	Fast (a set check)	Fast (policy evaluation)	Needs a purpose-built store

What this is confused with: treating these as a progression where later is better. They are different shapes for different problems. RBAC is correct and sufficient for most internal tools, and reaching for ReBAC because it is more expressive is a large amount of infrastructure for a decision that user.role == 'admin' answers.

The question that selects between them: does authorisation depend on the relationship between the subject and the specific object? If not, RBAC. If it depends on properties, ABAC. If it depends on a graph, ReBAC.

The problem it solves

RBAC's failure mode is role explosion, and it is arithmetic:

A document system with per-document permissions under RBAC:
  roles needed = documents x permission levels
  10,000 documents x 3 levels = 30,000 roles

Add teams:
  30,000 x (roles per team) -> unbounded

Roles stop describing job functions and start encoding individual grants, at which point the model has failed: doc-4471-editor is not a role, it is a tuple pretending to be one.

ABAC's failure mode is reverse queries. The policy is a function evaluated per request, so "may Alice edit document 4471" is fast and "who can edit document 4471" requires evaluating the policy against every user:

"Show me everyone who can access this document"  -> evaluate for 41,000 users
"Show me every document Alice can access"        -> evaluate for 2M documents

That matters more than it sounds, because those queries are product features: sharing dialogs, access reviews, compliance reports, and the search filter that shows only documents you can see. A search that must post-filter by an ABAC policy cannot paginate correctly, because you do not know how many results survive the filter until you evaluate them.

ReBAC's cost is that it needs a purpose-built store. The graph traversal is not something a relational database does well at low latency and high fan-out, which is why Zanzibar exists.

Mechanics

RBAC, and where it ends

-- The shape everyone starts with, and it is fine.
users(id, ...)
roles(id, name)                    -- 'admin', 'editor', 'viewer'
user_roles(user_id, role_id)
role_permissions(role_id, permission)  -- 'document:read', 'document:write'

def can(user, action, resource_type):
    return f"{resource_type}:{action}" in permissions_for(user.roles)

Note what is missing: the specific object. RBAC answers "may this user edit documents," not "may this user edit this document." Adding the object is where role explosion begins.

RBAC works well when: permissions are organisational rather than per-object, the role set is small and stable, and "everyone with this job function can do these things" is a true description of the policy. That covers most internal tooling and most admin surfaces.

ABAC

# Open Policy Agent / Rego
package authz

default allow = false

allow {
    input.action == "update"
    input.resource.type == "document"
    input.subject.department == input.resource.department
    input.subject.clearance >= input.resource.classification
    time.clock(time.now_ns())[0] >= 9
    time.clock(time.now_ns())[0] < 18
    input.context.device_managed == true
}

The policy is data and the decision is a pure function of the input, which is ABAC's real advantage: policies are versioned, tested, and deployed independently of the application.

# Testing a policy is testing a function.
def test_cross_department_denied():
    assert not evaluate(policy, {
        "subject": {"department": "eng", "clearance": 3},
        "resource": {"type": "document", "department": "finance", "classification": 2},
        "action": "update",
    })

The input is the hard part. Every attribute the policy references must be present at decision time, so the caller has to gather the subject's department and clearance, the resource's department and classification, and the device posture, before it can ask.

Attributes needed per decision:  6
Sources:                          user service, document metadata, device MDM
Latency if fetched per request:   3 network calls before the decision

That is why ABAC deployments cache attributes aggressively, and why stale attributes are ABAC's characteristic correctness problem: a user removed from a department retains access until the cache expires.

ReBAC and Zanzibar

Google's Zanzibar models authorisation as a graph of relationship tuples:

⟨object⟩#⟨relation⟩@⟨subject⟩

document:4471#owner@user:alice
document:4471#editor@user:bob
document:4471#parent@folder:engineering
folder:engineering#editor@group:eng-team#member
group:eng-team#member@user:carol

The last two lines are the mechanism that makes it powerful: a subject can be a userset (group:eng-team#member), so a relation can point at everyone with a relation to another object. That is how groups and inheritance work without special cases.

The schema defines how relations compose:

definition document {
    relation owner: user
    relation editor: user | group#member
    relation parent: folder

    permission edit  = owner + editor + parent->edit
    //                                   ^^^^^^^^^^^ INHERITANCE:
    //                                   anyone who can edit the parent folder
    permission view  = edit + viewer + parent->view
}

definition folder {
    relation editor: user | group#member
    relation parent: folder
    permission edit = editor + parent->edit          // recursive up the tree
}

Check(document:4471, edit, user:carol):
  1. Is carol a direct owner?         no
  2. Is carol a direct editor?        no
  3. Does carol have edit on the parent?
       folder:engineering#editor@group:eng-team#member
       group:eng-team#member@user:carol             -> YES
  -> allowed

The two operations that RBAC and ABAC do badly:

Expand(document:4471, edit)   -> every subject who can edit it
                                 (the sharing dialog, access review)
LookupResources(user:carol, edit, document)
                              -> every document carol can edit
                                 (the search filter, "my documents")

LookupResources is the one that makes search work. A search over documents can be filtered by a pre-computed set of accessible IDs rather than post-filtered by a policy evaluation, which is what allows correct pagination.

Consistency: the part Zanzibar spends most of its design on

A permission check that is even slightly stale is a security bug: removing someone from a document and having them still able to read it for thirty seconds is exactly the failure the system exists to prevent.

Zanzibar's answer is zookies: an opaque consistency token returned by writes and passed to checks.

# 1. Write the ACL change; get back a zookie.
resp = authz.write(tuple="document:4471#editor@user:bob", op="delete")
zookie = resp.zookie

# 2. Store the zookie with the CONTENT.
document.update(content=new_content, authz_zookie=zookie)

# 3. Every check for this document passes the zookie.
authz.check("document:4471", "view", "user:bob", consistency=at_least_as_fresh(zookie))
# -> guaranteed to reflect the ACL as of that write

The zookie binds the content version to the ACL version, which is what prevents the "new content, old ACL" window: if you show a user content written after their access was revoked, the check must reflect the revocation.

The consistency levels in practice (SpiceDB's naming):

minimize_latency      any replica, possibly stale. Fastest.
at_least_as_fresh(z)  at least as new as this zookie. The correct default.
at_exact_snapshot(z)  exactly this revision. For consistent multi-check reads.
fully_consistent      the leader. Slowest, and rarely necessary.

fully_consistent on every check is the mistake, because it forfeits the caching that makes the system fast. The zookie approach gives you correctness where it matters and cached reads everywhere else.

Latency and caching

Zanzibar's published latencies (p50 under 3 ms, p99 around 20 ms at millions of QPS) come from two things:

Leopard indexing: precomputed flattened set memberships for expensive recursive relations, so a deep group hierarchy is a set lookup rather than a traversal.

Aggressive caching with consistency tokens: a check result can be cached because the zookie tells you whether the cached result is fresh enough for this request.

Naive ReBAC without both is slow, and that is the honest cost: a graph traversal per permission check, at request rates, needs a purpose-built system.

A worked example: role explosion in a document platform

A document collaboration platform. About 2.4 million documents, 180,000 users, 40,000 organisations.

Baseline: RBAC with per-document roles.

roles table:                 1,847,203 rows
  of which 'org-level':            412
  of which 'doc-4471-editor':  1,846,791    <- roles that are actually grants
user_roles table:            14.2M rows
permission check latency:    p50 8 ms, p99 240 ms
"who can access this doc":   a join across 3 tables, p99 1.8 s
"documents I can access":    NOT IMPLEMENTED (a full scan)
search:                      post-filtered, so pagination was wrong

"Documents I can access" was not implemented, which is the tell: the model could not answer the question, so the product had shipped without the feature.

The search problem was the acute one:

# What they had:
results = search_index.query(q, limit=20)          # 20 results
visible = [r for r in results if can_access(user, r)]   # maybe 3 survive
# -> the user sees 3 results on "page 1" and the page count is wrong

Post-filtering breaks pagination, and the workarounds (over-fetching, then filtering) fail unpredictably: a user with access to 1 percent of documents needs 2,000 fetched to fill a page of 20.

Step 1: model the actual policy. They wrote down what the rules were, which nobody had done:

- A document owner can do anything.
- A document editor can read and write.
- A document viewer can read.
- Anyone who can edit the containing FOLDER can edit the document.
- Anyone in the owning ORGANISATION with the org 'admin' role can do anything.
- A share link grants view to anyone holding it.
- Folder permissions are inherited transitively up the tree.

Five of the seven rules are relationship-based and transitive, which is the ReBAC signature. RBAC could express none of the inheritance, which is why it had degenerated into per-object grants.

Step 2: the schema.

definition user {}

definition organization {
    relation admin: user
    relation member: user
    permission administer = admin
}

definition folder {
    relation parent: folder
    relation org: organization
    relation editor: user | organization#admin
    relation viewer: user

    permission edit = editor + parent->edit + org->administer
    permission view = viewer + edit + parent->view
}

definition document {
    relation parent: folder
    relation owner: user
    relation editor: user
    relation viewer: user
    relation share_link: user:*                    // a wildcard: anyone

    permission manage = owner + parent->edit
    permission edit   = editor + manage
    permission view   = viewer + share_link + edit + parent->view
}

Seven rules became a 24-line schema, and the transitive folder inheritance that RBAC could not express is parent->edit.

Step 3: migration, which was the actual project.

tuples written from existing roles:  9.1M
  document:X#owner@user:Y            2.4M
  document:X#editor@user:Y           4.1M
  document:X#viewer@user:Y           1.9M
  folder:X#editor@user:Y             0.4M
  organization:X#admin@user:Y        0.3M

roles DELETED:                       1.85M
user_roles rows deleted:             14.2M

The 1.85 million roles became 9.1 million tuples, which is more rows and a correct model: a tuple is a grant and a role was a grant wearing a role's name.

They ran both systems in parallel for six weeks, comparing every decision:

decisions compared:          410M
disagreements:               8,412
  of which RBAC was wrong:   8,401     <- inherited folder permissions
                                          the old system did not implement
  of which ReBAC was wrong:     11     <- schema bugs, all in share-link handling

Eight thousand four hundred cases where the old system denied access it should have granted, all folder inheritance, which users had been working around by requesting per-document grants. That is where 1.85 million roles came from.

Step 4: the features that became possible.

# "Who can access this document" - the sharing dialog.
subjects = authz.lookup_subjects("document:4471", "view")
# p99: 1.8 s -> 14 ms

# "Documents I can access" - now implementable.
doc_ids = authz.lookup_resources("user:alice", "view", "document")
# and search becomes a PRE-filter:
results = search_index.query(q, filter={"id": doc_ids}, limit=20)
# pagination is correct, because the filter is applied in the index

Search pagination was the change users noticed, and it had been impossible under the old model rather than merely slow.

Step 5: the consistency bug they shipped and fixed.

reported: a user removed from a document could still read it for ~20 seconds.

cause:    checks used minimize_latency (any replica), because it was fast.
          The revocation had not propagated.

# The fix: bind the ACL version to the content.
resp = authz.write_relationships(deletes=[...])
document.authz_zookie = resp.written_at              # store it WITH the doc
document.save()

# Every check for this document:
authz.check_permission(
    resource="document:4471", permission="view", subject="user:bob",
    consistency=Consistency(at_least_as_fresh=document.authz_zookie))

                          minimize_latency   at_least_as_fresh   fully_consistent
p50 check latency         1.2 ms             2.8 ms              14 ms
p99 check latency         6 ms               11 ms               52 ms
stale-permission window   up to ~30 s        none                none

at_least_as_fresh gives correctness at roughly twice the latency of the fastest option and a fifth of the strictest, which is the trade the zookie mechanism exists to make available.

Final:

                              before      after
roles                         1.85M       412 (org-level only)
authorization rows            14.2M       9.1M tuples
check latency p50             8 ms        2.8 ms
check latency p99             240 ms      11 ms
"who can access this"         1.8 s       14 ms
"what can I access"           unimplemented  18 ms
search pagination             incorrect   correct
inherited-permission bugs     8,401 known 0
stale-permission window       n/a         none (zookies)

The 8,401 disagreements were the finding that justified the project. They had been treated as user error and worked around with manual grants, which is what generated 1.85 million roles. The role explosion was a symptom of a model that could not express the policy, and adding roles was the workaround rather than the problem.

Production evidence

Google's Zanzibar paper (USENIX ATC 2019) describes the system behind Drive, YouTube, Cloud and others, reporting over 2 trillion tuples, more than 10 million QPS, and p95 under 10 ms. The zookie design and the Leopard index are the two parts that make those numbers possible.

SpiceDB (AuthZed), Ory Keto, OpenFGA (Auth0/Okta) and Permify are open implementations of the Zanzibar model, and their existence as a product category is evidence that per-object relationship authorisation is a common enough need to warrant purpose-built infrastructure.

Open Policy Agent is the reference ABAC implementation and is a CNCF graduated project. Its adoption for Kubernetes admission control (Gatekeeper) is the clearest case where ABAC fits: the decision is a function of the object's attributes and there is no relationship graph.

Airbnb, Carta, Netflix and Chef have published on Zanzibar-style migrations, and the recurring motivation is the same: per-object permissions with inheritance, and the reverse queries (who can access this, what can I access) that RBAC and ABAC cannot answer efficiently.

AWS IAM is a hybrid and instructive for it: policies are ABAC-like (conditions on attributes) attached to RBAC-like principals, with resource-based policies adding a relationship flavour. The complexity of reasoning about an effective IAM permission is a fair illustration of what happens when the models are mixed without a clear boundary.

The debate

When is RBAC enough? More often than the industry's enthusiasm suggests. If permissions describe job functions rather than per-object grants, and the role set is stable, RBAC is simpler, faster and easier to audit. The signal that you have outgrown it is roles whose names contain object identifiers: doc-4471-editor is a tuple, and once you have those you are doing ReBAC badly.

ABAC or ReBAC? Ask whether authorisation depends on properties or on relationships. Clearance levels, department matching, time windows and device posture are attributes: ABAC. Ownership, sharing, group membership and folder inheritance are relationships: ReBAC. Most real systems have both, and the practical arrangement is ReBAC for the object graph with an ABAC policy layer for contextual conditions on top.

Is Zanzibar-style infrastructure worth it? It is a database you now operate, with a schema language, a migration story and a consistency model. For a system where the reverse queries are product features, yes, because nothing else answers them efficiently and shipping without them (as the worked example did) is a visible product gap. For a system where authorisation is "admins can do admin things," it is enormous overkill.

What about doing ReBAC in your existing database? A recursive CTE over a permissions table works, and it will not meet a p99 latency budget under fan-out: a document in a folder tree eight deep, shared with three groups, is a traversal per check at request rates. The purpose-built systems exist because the traversal plus caching plus consistency is genuinely hard, and the honest advice is to use one rather than rebuild it.

How do you handle consistency? Not with fully_consistent everywhere, which forfeits the caching that makes it fast. Bind the ACL version to the content version with a zookie and use at_least_as_fresh for checks on that content: correctness where it matters, cached reads elsewhere. In the worked example that was 2.8 ms p50 against 14 ms for full consistency and 1.2 ms for stale reads.

Where does the policy live? Externalising authorisation into a service is the direction all three models are moving, and the trade is a network call per decision against policy that is versioned, testable and consistent across services. The failure mode of embedded authorisation is drift: twelve services each implementing "can this user edit this" slightly differently, which is the same shape as the twelve services each validating JWTs differently on the OAuth page.

Follow-up Q&A

"RBAC, ABAC or ReBAC: how do you choose?"

Ask what the decision is a function of. Roles and an action: RBAC, and it is sufficient for most internal tooling. Properties of the subject, object and environment: ABAC, which is what OPA and Kubernetes admission control do well. The relationship between the subject and the specific object, especially with inheritance: ReBAC. The signal that you have outgrown RBAC is roles whose names contain object identifiers, because doc-4471-editor is a tuple pretending to be a role.

"What is role explosion?"

RBAC answers "may this user edit documents," not "may this user edit this document." Adding the object means a role per object per permission level, so 10,000 documents at three levels is 30,000 roles. In one system it was 1.85 million roles of which 412 were genuine job functions and the rest were individual grants. The roles were a workaround for a model that could not express per-object inheritance.

"What can ReBAC do that ABAC cannot?"

Reverse queries efficiently. ABAC's policy is a function evaluated per request, so "may Alice edit this" is fast and "who can edit this" requires evaluating the policy against every user, and "what can Alice edit" against every object. Those are product features: sharing dialogs, access reviews, and the search filter that shows only what you can see. Post-filtering search by a policy also breaks pagination, because you do not know how many results survive until you evaluate them.

"Explain a Zanzibar tuple."

object#relation@subject, so document:4471#editor@user:bob. The subject can itself be a userset, like group:eng#member, which is how groups work without special cases. The schema then composes relations into permissions: permission edit = owner + editor + parent->edit, where parent->edit means anyone who can edit the containing folder, evaluated transitively. That transitive inheritance is what RBAC cannot express and what generates per-object grants when you try.

"What is a zookie and why does it exist?"

An opaque consistency token returned by a write and passed to subsequent checks. It exists because a permission check that is even slightly stale is a security bug: showing content written after someone's access was revoked, using a cached ACL from before the revocation. You store the zookie with the content and check with at_least_as_fresh, which guarantees the check reflects at least that ACL version while still allowing cached reads everywhere else. In one measurement it cost 2.8 ms p50 against 1.2 ms for stale and 14 ms for fully consistent.

"Could you implement ReBAC in Postgres?"

With a recursive CTE, yes, and it will not meet a request-rate latency budget under fan-out: a document eight folders deep, shared with several groups, is a graph traversal per check. The purpose-built systems exist because traversal plus caching plus a consistency model is genuinely hard, and Zanzibar's published p95 under 10 ms at 10 million QPS comes from a precomputed set index and consistency-token-aware caching rather than from a better query.

Common misconceptions

"ReBAC is the evolution of RBAC." They answer different questions. RBAC is correct and sufficient when permissions describe job functions, and reaching for ReBAC because it is more expressive is a large amount of infrastructure for a decision user.role == 'admin' answers.

"ABAC handles per-object permissions." It can express them and it cannot answer the reverse queries efficiently, because the policy is a function evaluated per subject-object pair.

"Role explosion means you need more roles." It means roles are being used as grants. The model cannot express the policy, and adding roles is the workaround.

"Authorisation checks can be cached freely." A stale allow is a security bug. Caching needs a consistency mechanism that binds the cached decision to a known ACL version, which is what zookies are for.

"You can build Zanzibar in a weekend." The tuple model is simple and the traversal, the caching, the consistency tokens and the set precomputation are what make it fast enough to sit in a request path. Use an implementation.

Interview delivery note

Say this verbatim: "The question is what the decision is a function of: roles, attributes, or a relationship graph. And the signal that you have outgrown RBAC is roles whose names contain object identifiers, because doc-4471-editor is a tuple pretending to be a role. In one system there were 1.85 million roles of which 412 were job functions." The selection criterion and a concrete, recognisable symptom.

The senior-versus-staff separator is the reverse queries. A senior engineer compares the models on expressiveness and per-check latency. A staff engineer points out that "who can access this" and "what can I access" are product features (sharing dialogs, access reviews, search filters), that ABAC answers them by evaluating a policy against every subject or object, and that post-filtering search by a permission check breaks pagination outright. That reframes the choice from a policy-expressiveness question into a product-capability one.

The second signal is consistency. Knowing that a stale allow is a security bug, that fully_consistent on every check forfeits the caching that makes the system viable, and that the zookie binds the content version to the ACL version, shows you have thought about the failure mode rather than the model.

The Staff & Team Lead Interview Reference