Relationship-Based Access Control (ReBAC) and Google Zanzibar
1. Overview
Definition: Relationship-Based Access Control (ReBAC) is an authorization model that uses the "relation" existing between a subject (user) and an object (resource) as the primary basis for authorization decisions, and Google Zanzibar is the canonical design of an authorization system that implements this model consistently at global scale.
Early access control began with the ACL (Access Control List), which attaches a list of permissions directly to resources, and as organizations grew it evolved into RBAC (Role-Based Access Control), which binds permissions to roles. RBAC works well under the assumption that "people who do the same job hold the same permissions," but modern collaboration services are dominated by cases where permissions are determined by a specific relationship between a resource and a user, such as "the person who created this document," "the person with whom this folder was shared," or "a member of this organization who was also invited to a particular project." Trying to express such requirements by inflating the number of RBAC roles leads to "role explosion," where roles grow in proportion to the number of resources.
ReBAC reduces permission to a graph query: "Does user U have relation Rel to resource R?" For example, "Can Alice view the document doc:readme?" becomes a relationship traversal: "Is Alice a viewer of doc:readme, or an editor/owner, or a viewer of the folder that doc:readme belongs to?" This perspective naturally models fine-grained authorization in services like Google Drive, GitHub, and Slack that handle hundreds of millions of users and billions of objects.
Another reason ReBAC draws attention is that it aligns with the trend of externalizing and centralizing authorization logic. In the past, each application scattered permission decisions throughout its internal code, but as microservices multiplied, the same permission question was reimplemented across services and interpreted inconsistently, widening discrepancies. By consolidating the permission model and data into a single dedicated service and having each service merely call a Check API, policy consistency, auditing, and change management all converge in one place. ReBAC has a structural advantage in that it provides a unified data model (relation tuples) well suited for such a central authorization service to handle.
Google published Zanzibar in a 2019 USENIX ATC paper. Zanzibar handles authorization for many services including Google Drive, Calendar, Cloud, YouTube, and Photos, and per the paper it manages trillions of relation tuples and millions of authorization checks per second while achieving a 95th-percentile latency under 10ms and availability above 99.999%. The core of this topic is not simply "viewing permissions through relationships" but the design techniques that simultaneously satisfy correctness (especially consistency of permission revocation) and low latency in a globally distributed environment. In a Professional Engineer answer, you must address the model, data structure, consistency mechanism, and operational trade-offs together.
2. The Evolution of Access Control Models and ReBAC's Place
2.1 ACL → RBAC → ABAC → ReBAC
Access control models are distinguished by "what permission is bound to." ACL enumerates (subject, allowed-action) pairs per resource. It is intuitive to express but hard to manage as users grow, and the reverse query of "all resources this user can access" is expensive. RBAC reduced management burden with a three-tier user-role-permission structure, but it struggles to express fine-grained sharing that varies per resource.
ABAC (Attribute-Based Access Control) gains flexibility through attributes of user, resource, and environment plus policy rules (e.g., "department = finance AND time = business hours"), but as policies grow complex it becomes hard to trace "why this permission was allowed/denied" and hard to guarantee large-scale query performance. ReBAC reduces permission to a reachability problem on a relationship graph, obtaining both fine granularity and explainability at once. In practice, hybrids that keep ReBAC as the base skeleton and reinforce it with ABAC-style conditions (contextual tuple, caveat) are increasingly common.
| Model | Binding target | Strengths | Limits |
|---|---|---|---|
| ACL | Subject list per resource | Intuitive, fine-grained | Reverse queries, large-scale management difficulty |
| RBAC | Roles | Simple management, easy org mapping | Role explosion, hard to express per-resource sharing |
| ABAC | Attributes, policy expressions | Flexible, dynamic conditions | Debugging, performance, consistency difficulty |
| ReBAC | Object relationship graph | Fine-grained + explainable, hierarchical inheritance | Graph traversal cost, implementation complexity |
What matters in this comparison is not the superiority of a model but the application context. Enterprise-wide permissions centered on org structure favor RBAC, dynamic regulation-based judgments favor ABAC, and product permissions centered on sharing and collaboration favor ReBAC. Zanzibar can be seen as a design that keeps ReBAC at the center while absorbing RBAC via group membership and ABAC elements via conditional tuples.
2.2 The Relation Tuple as a Data Model
In Zanzibar, every permission is stored in the single form of a relation tuple. The notation is ⟨object⟩#⟨relation⟩@⟨user⟩; for example, doc:readme#viewer@user:alice means "the viewer of the readme document is alice." The user position can hold not only an individual user but also a userset pointing to another set. doc:readme#viewer@group:eng#member expresses, in a single tuple, "all members of the eng group are viewers of readme."
This "userset rewrite" capability creates ReBAC's expressiveness. Group membership, folder inheritance, and role hierarchy are all unified into the form of "a relation referencing another relation." A permission check ultimately becomes the problem of traversing the directed graph formed by these tuples to determine "whether the user node can reach the (object, relation) node." Because a tuple is a simple row, horizontal scaling is easy, and since adding/removing a relation is itself granting/revoking a permission, it is also advantageous for auditing.
2.3 A Concrete Example of Role Explosion
Why role explosion is fatal becomes clear in numbers. Suppose a collaboration tool with 10,000 projects, each requiring three levels of access: viewer, editor, and admin. To express this with RBAC you would need roles like project-1-viewer, project-1-editor, …, that is number of projects × number of permissions = 30,000 roles, and if projects grow to 100,000 the roles become 300,000. Since the roles themselves grow in proportion to the number of resources, the management, search, and auditing of the role directory all collapse.
ReBAC expresses the same requirement with a single tuple like project:123#editor@user:alice. Instead of replicating the intermediate concept of a role per resource, it directly describes the relationship between resource and user. If inheritance is needed, declaring a namespace rule once like project:123#viewer: editor or admin applies to all projects. This separation of "declare once, data as relationships" is the most practical reason ReBAC is chosen for large-scale fine-grained authorization.
3. Zanzibar Architecture and Operating Principles
flowchart LR
App["Client service (Drive, etc.)"] -->|"Check/Read/Write/Expand"| ACL["aclserver (permission check)"]
ACL -->|"relation tuple lookup"| SP["Spanner (global distributed DB)"]
ACL -->|"cache lookup"| LH["Leopard (set index)"]
SP -->|"change log stream"| LH
App -->|"content version on write"| ACL
ACL -->|"return zookie (consistency token)"| App
SP -->|"TrueTime timestamp"| ACL
In this structure, the client service registers its permission policy with Zanzibar as a namespace config, actual permission changes insert or remove tuples via Write, and permission judgments query via the Check API. There are four core APIs. Check ("does U have the relation to R") returns allow/deny, Read retrieves stored tuples as is, Expand unfolds the full user set of a specific (object, relation) into a tree for debugging and permission viewing, and Write changes tuples.
The storage layer is Google Spanner. Thanks to Spanner's external consistency and the TrueTime global clock, every tuple change can be stamped with a globally comparable timestamp. This timestamp is the foundation of the consistency token (zookie) explained below. Since permission checks are overwhelmingly read-heavy, a separate set-index system called Leopard asynchronously materializes frequently queried (object, relation) sets, lowering the traversal cost of deep group nesting.
3.1 The Permission Check Evaluation Process
sequenceDiagram
participant C as Client
participant A as aclserver
participant S as Spanner
C->>A: "Check(doc:readme#viewer@alice, zookie)"
A->>A: "interpret namespace rule (viewer = viewer ∪ editor ∪ parent.viewer)"
A->>S: "look up doc:readme#viewer tuples"
S-->>A: "no editor@alice, parent=folder:eng"
A->>S: "look up folder:eng#viewer (recursive)"
S-->>A: "matches group:eng#member@alice"
A-->>C: "allowed, cache the evaluation result"
A permission check expands relations according to the rules defined in the namespace config. For example, if there is a rule "viewer includes editor and inherits the parent folder's viewer," then a doc:readme#viewer check is performed as a directed graph traversal proceeding direct tuple → editor tuple → parent folder viewer. Because this process can grow deep, Zanzibar parallelizes sub-queries, caches frequently used intermediate results, and applies request deduplication and cache-key sharding to mitigate "hotspots" where traffic concentrates on popular objects.
To process deep nesting quickly without harming the correctness of the evaluation result, Zanzibar splits each sub-problem into an independently cacheable unit. For instance, the member set of group:eng#member is referenced repeatedly across many document checks, so it is computed once and reused. In addition, when the same (object, relation, user) query floods in within a short time (e.g., a popular public document), "request hedging and deduplication" merges duplicate requests into a single evaluation to reduce backend load.
3.2 Consistency and zookie — Balancing "Applying New Permissions" and "Immediate Revocation"
In an authorization system, the most dangerous error is a permission revocation being reflected late. If a document whose sharing has already been removed can still be viewed due to caching, that is a serious information leak. Conversely, performing every check always on the latest data with strong consistency causes latency and cost to explode. Zanzibar resolves this tension with a consistency token called a zookie.
When a client stores content, it keeps the zookie (internally a Spanner timestamp) issued by Zanzibar together with it. Thereafter, a Check on that content is guaranteed to be evaluated on a snapshot at or after the point the zookie indicates. This prevents the inversion of "judging with an ACL older than the content change," thereby preventing the new-enemy problem (content newly added after a permission revocation being exposed under old permissions, or sharing changing but being judged in the old order). In normal operation, Check uses a slightly past consistent snapshot to raise cache hit rate and lower latency, while placing a lower bound via zookie where correctness is required. This is a textbook case of guaranteeing by design "as fresh as needed" rather than "always the latest."
Looking at the new-enemy problem concretely, there are two scenarios. First, right after Alice removes Bob from a document she adds secret content, but if the permission check is evaluated on a snapshot from before the removal, Bob gets to see the new content. Second, Alice raises Bob's permission and immediately moves a sensitive document into that folder, but if the order of the two changes is evaluated in reverse, exposure contrary to intent occurs. The zookie blocks such order inversion at the source by enforcing "at or after the ACL point that produced the current state of the content." That is, the key is to ensure that cache and snapshot optimizations for performance never sacrifice the safety of permission revocation.
4. Implementation Ecosystem and Comparison
Since Zanzibar was published only as a paper, open-source and commercial implementations form the ecosystem. Representative examples include OpenFGA (led by Auth0/Okta) in the CNCF Sandbox, SpiceDB (AuthZed), Ory Keto, and managed services like Auth0 FGA and AuthZed Cloud. Each implementation shares Zanzibar's concepts of tuples, namespaces, and Check/Expand, but differs in consistency model and operational convenience.
| Implementation | Led by | Features | Note |
|---|---|---|---|
| OpenFGA | Okta (Auth0) | DSL-based model, CNCF Sandbox | Active community, multi-language SDKs |
| SpiceDB | AuthZed | zookie-like ZedToken, caveat (conditional) support | Most faithful to Zanzibar, Postgres/Spanner backends |
| Ory Keto | Ory | Go-based, Ory ecosystem integration | Lightweight, self-hostable |
| Google Zanzibar | Google internal | Original, Spanner+Leopard | Private (paper only) |
The most important practical difference between implementations is the consistency control method. How the mechanism corresponding to zookie is exposed—like SpiceDB's ZedToken or OpenFGA's consistency option—determines application correctness. For instance, when immediacy of revocation matters, such as a change to an approval chain in a financial service, one chooses a "fully consistent" query, whereas when a slight delay is acceptable, such as exposing a public post, one chooses a "minimize latency" query—designing a consistency tier per resource.
4.1 An Example of Migrating Legacy Permissions to ReBAC
Suppose a hypothetical document collaboration service previously managed permissions with a relational table (doc_permissions(doc_id, user_id, role)). The first step of migration is to map these rows directly to relation tuples. A single row doc_permissions(42, alice, editor) becomes one tuple doc:42#editor@user:alice. If there are tens of millions of rows, batch-Write them in bulk, but since new permission changes continue to occur during migration, synchronize the post-migration delta via change data capture (CDC).
The second step is the task of replacing the scattered permission-decision logic in application code (if user.role in (...) spread across multiple services) with a single Check call. Here, rather than switching over at once, run the existing logic and the ReBAC decision simultaneously and compare the results (shadow mode). For example, if out of 100 million permission decisions per day the discrepancy converges to below 0.001%, only then promote ReBAC to the authoritative decision point. If this gradual transition is skipped, modeling errors translate directly into operational incidents, which is why in real large-scale migrations the most time is invested in this verification step.
Another practical consideration is schema (model) design. In the OpenFGA DSL you declare relations and inheritance like define viewer: [user] or editor or viewer from parent, and if this modeling is wrong the graph becomes excessively deep, raising latency, or unintended permission leaks occur. In actual adoption cases, the most common failures are modeling errors and tuple-sync omissions, and the migration design for porting an existing system's permission data into tuples determines project success or failure.
5. Deep Dive — Adoption Patterns and Recent Trends
Field adoption generally proceeds in three stages. The first is defining a central permission model, converging scattered if-statement-based permission logic into an OpenFGA/SpiceDB model. The second is dual-operation (shadow) verification, running the existing permission judgment and the ReBAC judgment simultaneously and comparing discrepancies via logs to transition safely. The third is full cutover, where the application calls only the Check API and permission changes are unified via Write. In this process, it is important to prevent inconsistencies by binding data changes (share/revoke) and tuple writes to the same transaction boundary.
As for recent trends: first, the spread of conditional permissions (caveat/contextual tuple). ABAC-style conditions such as "only during business hours" or "only from a specific IP range" are combined into tuples, fusing ReBAC and ABAC. Second, authorization for AI agents and non-standard workloads. When an agent accesses a resource on behalf of a user, attempts to express the "user-agent-resource" delegation relationship as tuples are increasing. Third, standardization discussions: the trend of externalizing and centralizing fine-grained authorization is spreading in tandem with the policy decision point (PDP) concept of zero trust. Fourth, with OpenFGA's elevation in CNCF and the launch of managed FGA by each cloud, the model of "consuming authorization as a service" is taking hold.
In particular, domestically the demand for fine-grained access control in the public and financial sectors is coupled with the obligations to manage access privileges and retain access records under personal information protection law, making the traceability and evidencing of permission grants/revocations increasingly important. A relation-tuple-based model records as data "who obtained access permission, when, and through which relation," so it naturally combines with audit logs and access-control evidence. In contrast, complex ABAC-style policy expressions alone are hard to explain after the fact.
Likely exam directions include ① comparison of ReBAC with RBAC/ABAC and criteria for application, ② explanation of Zanzibar's zookie and consistency-guarantee mechanism, ③ the concepts of relation tuples and userset rewrite and permission graph traversal, and ④ the implications of externalizing fine-grained authorization for zero-trust and microservices architectures. In an answer, it is best to narrate "why ReBAC is needed at scale (role explosion)" and "how the correctness-latency trade-off was solved by design (zookie)" as the core axes.
6. Considerations and Implications
First, the correctness-latency trade-off must be designed per resource tier. Making every Check fully consistent causes excessive latency and cost, while making all cache-first risks missing revocations. Separate consistency tiers (fully consistent vs. minimize latency) according to resource sensitivity, and explicitly place a zookie lower bound for resources where revocation is critical.
Second, the synchronization of permission data and business data must be guaranteed transactionally. If share removal succeeds but tuple deletion fails, a ghost permission remains. Use a change-event-based approach (outbox pattern) or a two-phase write strategy to structurally eliminate "data-tuple inconsistency," and include periodic consistency audits and Expand-based verification in operations.
Third, model design and governance simultaneously determine performance and security. If the relationship graph is excessively deep or cyclic, latency grows, and if inheritance rules are ambiguous, over-permissioning arises. Operate review, version management, and impact analysis (which users' permissions does this change alter) for model changes, combined with Policy as Code.
Fourth, externalizing authorization must go together with organizational and architectural strategy. Separating fine-grained authorization into a central service makes consistency and auditing easier, but since all services depend on Check, it becomes a single critical point for availability and latency. Regional replication, a cache layer, a fail-safe (default deny) policy on failure, and SLO management of the authorization service itself must be premised, and it must be designed consistently with the PDP/PEP separation principle of zero trust.
Fifth, vendor/implementation dependency and portability must be considered. The Zanzibar model is common, but the consistency token, conditional tuples, and schema DSL differ per implementation. Placing the model behind an abstraction layer and designing so that core permission logic is not excessively coupled to a specific product's API reduces future switching cost.
Sixth, performance and cost observability must be managed as operational metrics. Fine-grained authorization calls Check on every request path, so the number of calls, p95/p99 latency, cache hit rate, and graph traversal depth govern service quality. Observe these constantly on a dashboard, refactor models with excessive depth, and preemptively respond to resources with many set queries using materialized indexes. Since authorization enters the critical path of every request, it is desirable to treat capacity planning and cost (FinOps) management of the authorization service as a separate initiative.
References
- Google, "Zanzibar: Google's Consistent, Global Authorization System", USENIX ATC 2019: https://research.google/pubs/pub48190/
- USENIX ATC '19 presentation (Zanzibar): https://www.usenix.org/conference/atc19/presentation/pang
- OpenFGA (official docs): https://openfga.dev/docs
- AuthZed SpiceDB (official docs): https://authzed.com/docs
- Ory Keto: https://www.ory.sh/keto/
In one line: ReBAC uses the "relationship" between a user and a resource as the axis of permission decisions to solve the role explosion of large-scale fine-grained authorization, and Google Zanzibar is the canonical design that simultaneously achieves low latency and revocation correctness at global scale via relation tuples, userset rewrite, and the zookie consistency token.