Authorization Is a Graph Problem (And Most Teams Solve It Like a Table Problem)

The if Statement That Ate Your Architecture

It always starts the same way.

You’re building a SaaS product. Users belong to organizations. Organizations have admins and members. Members can view documents, admins can edit them. Simple. You write an if statement. Maybe two.

Six months later, someone asks: “Can we let users share a document with people outside their org?” Then: “Can we have view-only links?” Then: “Can we make admins for just one project, not the whole org?”

Your authorization code is now sprayed across 40 endpoints, lives in three languages (because microservices), and the one engineer who understood the permission inheritance model left in January. When a customer asks “why can’t I see this document?”, the honest answer is: nobody knows.

This is the authorization problem. And it’s not a security problem. It’s a data modeling problem disguised as an access control problem. The question isn’t “how do I check permissions?” The question is: what is the shape of the data that determines who can do what?

That question has a surprisingly deep answer, and the last seven years of industry evolution have produced a taxonomy of structural approaches that most teams never see, because they’re too busy wrestling with their if statements.

What You Probably Believe vs. What’s Actually True

Before diving into the systems, let’s clear the table. Authorization carries more accumulated misconceptions than almost any other infrastructure concern, because every team builds it from scratch and most teams only build it once.

A Structural Taxonomy: Three Shapes of Authorization

Every authorization system in production today maps to one of three structural approaches, or a hybrid. The differences aren’t about features. They’re about the underlying data structure each system uses to represent permissions.

Tables: Role-based and attribute-based systems. The authorization data lives in rows. A user has roles (RBAC) or attributes (ABAC), and a policy engine evaluates rules against those flat properties. The canonical systems here are NIST RBAC (2001) and XACML/OPA for ABAC. Authorization checks are predicate evaluation: “does this user’s set of properties satisfy this rule?”

Graphs: Relationship-based systems. The authorization data is a directed graph of relationships between entities. A user is a member of a team, the team owns a project, the project contains a document. “Can this user view this document?” becomes a graph traversal. Google Zanzibar (2019) is the foundational system. SpiceDB, OpenFGA, and Permify are open-source implementations.

Trees: Policy-language systems. The authorization logic is expressed as a structured policy language with formal semantics. AWS Cedar is the exemplar: policies are evaluated against a request context, with formal guarantees about determinism and analyzability. The authorization “data” is the policy itself, not a separate store.

These aren’t marketing categories. They’re structural differences in how the system answers the fundamental question: “given this request, is it allowed?” Tables do a lookup. Graphs do a traversal. Trees do an evaluation.

Most real systems are hybrids. Google’s internal Zanzibar uses relationship graphs for the core model but allows computed usersets (essentially policy rules embedded in the graph schema). Cedar supports entity hierarchies alongside flat policies. But understanding the primary data structure tells you where the system will be strong and where it’ll struggle.

graph LR
  A["Authorization
Request"] --> B{"Primary
Data Structure?"}
  B -->|"Rows"| C["Table Systems
(RBAC/ABAC)"]
  B -->|"Edges"| D["Graph Systems
(ReBAC/Zanzibar)"]
  B -->|"Rules"| E["Policy Systems
(Cedar/OPA)"]
  C --> F["Predicate
evaluation"]
  D --> G["Graph
traversal"]
  E --> H["Policy
evaluation"]

Inside Zanzibar: The Graph That Guards Google

The 2019 Zanzibar paper is one of those rare systems papers that spawned an entire ecosystem. Understanding its core design choices explains why every open-source Zanzibar clone works the way it does.

The data model is relation tuples. Everything in Zanzibar is a tuple: object#relation@user. “Document X’s viewer is User Y” becomes doc:X#viewer@user:Y. “Document X’s viewer is anyone who’s a member of Team Z” becomes doc:X#viewer@team:Z#member. That second form, where the user position references another relation, is what makes Zanzibar a graph, not a table. Permissions compose through these references.

Namespace configurations define the schema. Each resource type (document, folder, team) has a namespace config that declares which relations exist and how they compose. This is where you express “editors are also viewers” or “a document inherits its folder’s permissions.” The schema is the type system for your permission graph.

Two APIs do all the work. Check(object, relation, user) answers “can this user do this?” by traversing the graph from the object through its relations. Expand(object, relation) returns the full tree of users who have a given relation, useful for debugging and UI.

Consistency is the hard part. This is what separates Zanzibar from a naive graph database with permission tuples. Zanzibar provides external consistency: if a user removes a collaborator and then uploads a secret document, the system guarantees the removed collaborator cannot see the document, even if the permission change hasn’t fully propagated. This is the New Enemy Problem, and solving it required Google’s investment in Spanner’s TrueTime.

graph LR
  U1["user:alice"] -->|"member"| T1["team:engineering"]
  T1 -->|"owner"| P1["project:atlas"]
  P1 -->|"parent"| D1["doc:design-spec"]
  D1 -.->|"viewer = parent.owner
(computed)"| U1

  U2["user:bob"] -->|"viewer"| D1
  U3["user:carol"] -->|"editor"| D1
  D1 -.->|"viewer = editor
(implied)"| U3

The Open-Source Zanzibar Family

The Zanzibar paper launched an entire category. Here’s how the major implementations differ, not in features, but in architectural bets.

graph LR
  Z["Google Zanzibar
(2019 paper)"] --> S["SpiceDB
(AuthZed)"]
  Z --> O["OpenFGA
(Okta/Auth0)"]
  Z --> P["Permify
(FusionAuth)"]
  Z --> K["Ory Keto"]
  S -.-> S1["Closest to paper
ZedTokens for consistency"]
  O -.-> O1["CNCF Incubating
Broadest SDK ecosystem"]
  P -.-> P1["Visual playground
YAML schema"]
  K -.-> K1["Part of Ory ecosystem
Self-hosted identity stack"]

Cedar: The Formally Verified Alternative

Cedar represents a fundamentally different structural bet. Where Zanzibar says “authorization is a graph problem,” Cedar says “authorization is a logic problem, and logic should be provable.”

Developed by AWS and published in 2024, Cedar is an authorization policy language designed for three properties that Zanzibar doesn’t prioritize:

Formal verification. Cedar policies can be mechanically analyzed for properties like “no policy in this set ever grants admin access to users outside the org.” The Cedar team formalized the language in Lean and proved correctness properties. They found 25 bugs during the verification process: 4 in the policy validator and 21 through differential random testing. That’s not a QA win; that’s a statement about the limits of testing alone for authorization logic.

Analyzability. Because Cedar’s semantics are deterministic (default deny, forbid wins, no policy ordering), you can answer questions like: “Are these two policy sets equivalent?” “Does adding this policy change who can access what?” “Is there any request that this policy would deny that the old set would allow?” Zanzibar-style systems can’t answer these questions because the authorization logic is entangled with the runtime graph state.

Readability. Cedar policies read like structured English:

A Cedar policy granting view access to engineers on a project folder

permit(
  principal in Group::"engineering",
  action == Action::"view",
  resource in Folder::"project-atlas"
);

Compare that to Zanzibar’s schema definitions, which require understanding userset rewrites and computed relations.

Cedar’s tradeoff is that it doesn’t natively handle deeply nested relationship traversals. If your permission model is “user is a member of a team that owns a project that contains a folder that holds a document,” Cedar needs the application to resolve that hierarchy before evaluation. Zanzibar handles that traversal natively.

graph LR
  R["Request
{principal, action,
resource, context}"] --> E["Cedar
Evaluation"]
  P["Policy Store
(analyzable)"] --> E
  S["Entity Store
(hierarchy)"] --> E
  E --> D{"Default Deny"}
  D -->|"permit matches
no forbid"| A["ALLOW"]
  D -->|"forbid matches
OR no permit"| B["DENY"]

OPA: The Swiss Army Knife (And Why That’s a Problem)

Open Policy Agent occupies an interesting position in the taxonomy. It’s not an authorization system. It’s a general-purpose policy engine that people use for authorization because nothing better existed when they needed it.

OPA’s strength is exactly its generality. Rego (its policy language, a Datalog descendant) can express any computable policy. Kubernetes admission control? OPA. API rate limiting? OPA. Authorization? Also OPA. This generality made it the default choice for teams that already ran it for infrastructure policies.

But OPA’s generality is also its authorization weakness:

No relationship model. OPA evaluates policies against JSON input. If your authorization requires graph traversal (team membership, folder hierarchies, inherited permissions), your application must resolve the graph and feed it as input. OPA doesn’t traverse; it evaluates.

Rego’s learning curve. Rego is based on Datalog, which is powerful but unfamiliar to most application developers. Cedar was explicitly designed as a reaction to this: “a policy language that developers can read without learning logic programming.”

Performance at policy scale. OPA works well with fewer than 10,000 policies. Above that, evaluation latency and memory usage scale in ways that Zanzibar-style systems (which scale with relationships, not rules) avoid. Real-world deployments see 1-5ms for simple evaluations, but complex policy bundles can push p99 latency significantly higher.

OPA remains the right choice for infrastructure policy (Kubernetes admission, Terraform plan validation, CI/CD gate checks) where policies are relatively few and the input is a single JSON document. For application authorization with millions of resources and complex permission hierarchies, purpose-built systems outperform it.

The Real Hard Problem: Where Does the Data Live?

We’ve covered three structural approaches (graphs, policies, general rules). None of them answer the question that actually keeps engineers up at night: where does the authorization data live relative to the application data?

This is the Venn diagram problem. Authorization data and application data overlap. “User X belongs to Organization Y” is both an application fact (shown in the UI, used for billing) and an authorization fact (determines what X can access). When you centralize authorization in an external service, you must decide what happens to this overlapping data.

Option 1: Duplicate it. Send all authorization-relevant data to the authorization service. This is what Zanzibar-style systems expect. You write tuples to SpiceDB/OpenFGA whenever your application state changes. The cost is the synchronization burden: every application write that affects permissions must also write to the authorization store, and you need to handle failures in either write without creating inconsistency.

Option 2: Query it at decision time. The authorization service calls back into your application for data it needs. This avoids duplication but introduces latency (network round-trips) and circular dependencies (your app calls the auth service, which calls your app back).

Option 3: Keep it embedded. Don’t externalize authorization. Evaluate permissions in-process using your application’s own database. Oso’s “local authorization” model takes this approach. The trade-off is that you lose the centralization benefits (unified audit logs, cross-service consistency) and your authorization logic is tightly coupled to your data layer.

There’s no clean answer. Airbnb (Himeji) chose option 1 and invested heavily in synchronization infrastructure. Carta chose option 1 with a custom tuple store. Teams using Cedar often lean toward option 3 with periodic policy analysis.

The structural insight: your choice of authorization system constrains which option is practical. Zanzibar systems assume option 1. Policy systems (Cedar, OPA) can work with options 2 or 3. Embedded systems (Oso local, Cerbos sidecar) default to option 3.

graph TD
  subgraph "Application Layer"
    APP["Application
Database"]
    SVC["Application
Service"]
  end

  subgraph "Authorization Layer"
    AUTH["Authorization
Service"]
    STORE["Authorization
Data Store"]
  end

  SVC -->|"1. Check permission"| AUTH
  AUTH -->|"2. Evaluate"| STORE
  SVC -.->|"Sync: write tuples
on state change"| STORE
  APP -.->|"The overlap:
app data that's
also auth data"| STORE

The Problem Nobody Warns You About: Listing Authorized Resources

Every authorization system’s marketing page shows the check API: Check(user, permission, resource) → bool. That’s the easy part.

The hard problem is the reverse: “Show me all documents this user can access.” This is the list API, and it’s where the structural differences between authorization models become performance-critical.

In table systems (RBAC): This is a SQL query with a JOIN. Fast, well-understood, and your database already has indexes for it. It’s one reason RBAC persists despite its limitations. Listing resources is trivially efficient.

In graph systems (Zanzibar): This requires LookupResources, essentially traversing the permission graph in reverse to find all resources reachable from a given user. SpiceDB’s LookupResources shows ~100ms latency for systems with 100-250K relationships and 3-5 levels of graph nesting. That latency grows with relationship volume and graph depth.

In policy systems (Cedar/OPA): This is essentially unsolvable without pre-computation. You’d need to evaluate every policy against every resource for a given user. Nobody does this in real time. Instead, you maintain materialized views or use the application database for listing and the policy engine only for individual checks.

The practical implication: if your product’s primary UI is a resource list (think Google Drive, Notion, GitHub), the list API’s performance determines your user experience. Checking permissions on a click is table stakes. Rendering a filtered, permission-aware list of 10,000 resources in under 200ms is the real engineering challenge.

graph LR
  Q["'Show me
my documents'"] --> A{"Authorization
Model?"}
  A -->|"Table
(RBAC)"| B["SQL JOIN
~5ms"]
  A -->|"Graph
(ReBAC)"| C["LookupResources
~100ms"]
  A -->|"Policy
(Cedar/OPA)"| D["Materialized view
or post-filter"]
  C --> C1["Grows with
graph depth"]
  D --> D1["Stale by
design"]

Production War Stories: What Breaks and Why

The clearest signal about where authorization systems struggle comes from the teams that have deployed them at scale. Here are the failure patterns that appear repeatedly.

Graph depth explosions. Reddit’s ads platform needed multi-level permission inheritance: ad accounts contain campaigns contain ad groups. Deeply nested hierarchies turn a simple check into a multi-hop graph traversal. SpiceDB defaults to max depth 50, but even 5-6 levels deep with wide fan-out (a team with 500 members owns 200 projects each containing 1,000 documents) can push check latency above acceptable thresholds. The fix is schema design discipline: keeping inheritance shallow and preferring direct relationships where possible.

The 65,000-query catastrophe. Apache Polaris hit 30+ second latency on permission checks because the authorization layer performed 65,000 sequential database scans, reading 13.7 billion rows without proper indexing. The lesson isn’t “indexing matters” (everyone knows that). The lesson is that authorization’s query patterns are different from your application’s patterns. If you’re using your application database for authorization checks, your indexes are probably optimized for application queries, not permission traversals.

The Auth0 cascade. In April 2021, Auth0’s feature flag service went down, and cache invalidation caused all API nodes to fall back to direct database queries simultaneously. Authentication latency spiked 100x. The lesson for authorization: every caching layer in your permission pipeline is a consistency trade-off. When the cache fails, the thundering herd against your permission store can cascade into a full outage.

Denial latency asymmetry. Teams commonly optimize the allow path (permission granted, proceed) but ignore the deny path. In graph-based systems, denials can be slower than allows because the system must traverse the entire reachable graph before concluding “no path exists.” If denied users (who might be attackers probing your system) create more load than permitted users, you have a denial-of-service vector hiding in your authorization system.

Choosing Your Authorization Architecture: A Decision Framework

Enough theory. Here’s how to pick.

The decision isn’t “which system is best.” It’s “which structural approach matches the shape of your authorization problem.” And that shape is determined by three questions:

How complex is your permission hierarchy? If your permissions are flat (users have roles, roles have permissions), RBAC works and you should use it. If your permissions are relational (users belong to teams that own projects that contain resources), you need a graph system. If your permissions involve arbitrary conditions (allow if attribute X AND context Y AND NOT exception Z), you need a policy system.

Is your primary query check or list? If your application mostly checks individual permissions (“can this user edit this document?”), any system works. If your application primarily lists authorized resources (“show me all documents I can see”), you need either co-located data (RBAC with SQL joins) or materialized permission views.

Can you afford the data synchronization overhead? Centralizing authorization means duplicating authorization-relevant data into a separate store. If you’re a small team with a monolith, this overhead may exceed the benefit. If you’re running 20+ microservices with shared authorization rules, centralization pays for itself.

graph LR
  A{"Permission
hierarchy?"} -->|"Flat roles"| B["RBAC
+ SQL"]
  A -->|"Nested
relationships"| C{"Primary
query?"}
  A -->|"Arbitrary
conditions"| D["Cedar / OPA"]
  C -->|"Mostly
checks"| E["Zanzibar
(SpiceDB/OpenFGA)"]
  C -->|"Mostly
listing"| F{"Can afford
sync overhead?"}
  F -->|"Yes"| G["Zanzibar +
Materialized views"]
  F -->|"No"| H["Embedded ReBAC
(Oso / Cerbos)"]

The Convergence Thesis: Authorization Is Becoming Infrastructure

Here’s the interesting structural observation that most comparisons miss.

Authorization is following the exact trajectory of databases, queues, and observability. It starts as application code (hand-rolled if statements), matures into libraries (role middleware), becomes a service (SpiceDB, OpenFGA), and will eventually become infrastructure you don’t think about, like how most teams don’t think about their database engine’s B-tree implementation.

Three signals suggest we’re in the “becoming a service” phase with infrastructure on the horizon:

Signal 1: CNCF gravity. OpenFGA reaching CNCF Incubation (October 2025) is the same stage that Prometheus, Envoy, and Helm passed through before becoming standard infrastructure. Authorization is joining the cloud-native stack, not as an application concern but as a platform layer.

Signal 2: Standards emergence. The OpenID AuthZEN working group is defining interoperability standards for authorization APIs. When Cerbos, Permit.io, and Topaz all pass the same interop tests, we’re approaching the “authorization interface” that lets you swap implementations, the same way S3 compatibility lets you swap object stores.

Signal 3: Formal methods going mainstream. Cedar’s verification-guided development isn’t just an academic exercise. It’s AWS telling the market that authorization logic should be provable, not just testable. When the provability tooling matures (and the Cedar Analysis tools are a first step), authorization policies become auditable artifacts rather than opaque code.

The convergence point is a system that combines Zanzibar’s relationship model, Cedar’s analyzability, and co-located evaluation that avoids the data sync tax. Nobody has built this yet. But the components exist, and the economic pressure (62% of teams still building custom solutions) suggests the market is waiting for it.

Key Takeaways

• Authorization is a data modeling problem, not a security feature. The shape of your permission data (flat, relational, conditional) determines which structural approach works. Tables for flat roles, graphs for nested relationships, policy trees for arbitrary conditions.

• Zanzibar solved the graph problem at Google scale. Its relation-tuple model and consistency guarantees (via zookies/ZedTokens) are replicated by SpiceDB, OpenFGA, and Permify. But the Zanzibar paper’s hardest innovations (Leopard indexing, TrueTime-backed consistency) don’t fully translate to open-source implementations.

• Cedar solved the provability problem. Formal verification for authorization policies is a genuine breakthrough, not marketing. The 25 bugs found during verification-guided development could not have been caught by testing.

• The list API is the real battleground. Every system can check a single permission quickly. Listing all resources a user can access is where architectures diverge and performance falls apart.

• Data synchronization is the hidden cost of centralization. Externalizing authorization means duplicating application data in the authorization store. The sync pipeline is the most operationally expensive and failure-prone part of any centralized authorization deployment.

• Authorization is becoming infrastructure. CNCF adoption, interop standards, and formal methods are moving authorization from “application concern” to “platform layer.” The 62% of teams still building custom solutions will eventually migrate, just as most teams eventually migrated from hand-rolled job queues to dedicated message brokers.

Further Reading

Start here:

• The original Zanzibar paper — surprisingly readable for a USENIX paper, and understanding it makes every open-source implementation more comprehensible.
• Oso’s “Why Authorization Is Hard” — the best non-vendor-biased framing of the problem space.

Go deeper:

• The Cedar paper — formal methods applied to authorization, with real bug-finding results.
• AuthZed’s “New Enemy Problem” post — the consistency challenge that separates toy authorization from production authorization.
• Airbnb’s Himeji writeup — the most honest account of what centralizing authorization actually costs at scale.