← All writing
Paper Breakdown
12 min readSystemsDistributed SystemsProductionAuthorizationBackend

Zanzibar: what Google's authorization paper actually says

Reading Pang et al. (Google, USENIX ATC 2019) while debugging why newly-added permissions weren't taking effect until the next page reload.

The bug report was specific: "I shared the document with my colleague but they got a permission denied for about 30 seconds." The sharing worked — the ACL was written, it showed up in the sender's UI. But access checks on the recipient's side returned denied. We were caching permission decisions and replicating them across regions, and a write to one region wasn't guaranteed to be visible to reads in another for several seconds.

The standard fix is TTL-based cache expiration. Set it short enough and the window shrinks. But short TTLs mean high backend load; long TTLs mean a bad user experience on permission changes. You're tuning a knob with two bad ends, and neither end is actually "correct."

Zanzibar — "Zanzibar: Google's Consistent, Global Authorization System", Pang et al., USENIX ATC 2019 — is Google's answer to this problem at a scale where "wait 30 seconds" is not an acceptable answer for any user, let alone billions of them. The paper describes a globally distributed authorization service that serves 10M QPS with 95th percentile latency under 3ms, and that provides a consistency model that solves the specific bug above without requiring you to either slow down writes or sacrifice cache hit rate.

The insight is called a zookie. Nobody talks about it. The data model gets all the attention.

The data model: what everyone already knows

The core primitive in Zanzibar is the relation tuple:

⟨object⟩#⟨relation⟩@⟨user⟩

doc:readme#owner@user:alice
doc:readme#viewer@group:eng#member
group:eng#member@user:bob

A relation tuple asserts that user has relation to object. Permissions are derived from these tuples, not stored directly. To check whether Alice can view doc:readme, Zanzibar traverses the relation graph: is Alice directly in the viewer set? Is she in the editor set, which may inherit viewer? Is she a member of a group that's in either set?

Each object type has a namespace config — a schema that defines what relations exist and how they compose:

name: "doc"
relation { name: "owner" }
relation { name: "editor"
  userset_rewrite {
    union {
      child { _this {} }                                  # direct editors
      child { computed_userset { relation: "owner" } }   # owners are also editors
    }
  }
}
relation { name: "viewer"
  userset_rewrite {
    union {
      child { _this {} }
      child { computed_userset { relation: "editor" } }  # editors are also viewers
    }
  }
}

Owners are editors; editors are viewers. You don't store separate tuples for each derived permission — you derive them at check time via graph traversal. The config is versioned: Zanzibar stores the full history of namespace config versions, because tuples written under old configs need to be evaluated against the schema version active at write time.

The other key primitive is the userset: instead of pointing to a specific user, a tuple can point to a group-as-a-set:

doc:readme#viewer@group:eng#member

Everyone who is a member of group:eng is a viewer of doc:readme. Membership in group:eng is itself a set of tuples — which may include other groups. The traversal recurses.

This is Relationship-Based Access Control (ReBAC). Permissions are derived from the graph of relationships between objects and subjects, rather than from flat role lists. This is why Zanzibar can express "the owner of a parent folder can view its children" or "members of a team can access that team's resources" without explicitly enumerating all implications every time group membership changes. The relation graph is the source of truth; the permissions are computed.

The consistency model: what nobody talks about

The data model is well-documented — SpiceDB, OpenFGA, and Ory Keto all implement it. The consistency model is what makes Zanzibar actually work in production, and it's underspecified in most open-source implementations.

The problem is the new enemy problem. It works like this:

  1. Alice creates a document and becomes its owner
  2. Alice writes a tuple: doc:readme#viewer@user:bob
  3. Bob immediately tries to access the document
  4. Bob's access check hits a replica that hasn't yet received the write
  5. Bob is denied

The naive response is "replicate faster" — but global replication across datacenters can't be reduced to zero latency. This is a physics constraint, not an engineering one.

Zanzibar's solution: zookies. A zookie is an opaque token encoding a timestamp, returned whenever you write a relation tuple. Clients store and thread this token through subsequent operations.

When Alice shares the document, the write API returns a zookie z. Alice's client stores this. When Bob accesses the document, the client sends the check request with at_least_as_fresh: z. Zanzibar's check service guarantees that the replica it reads from has processed all writes up to the timestamp encoded in z.

Concretely: if a replica hasn't yet applied the write that z references, the check service either waits for it to catch up or routes to a replica that's already current. Result: Bob's check always sees the write that added him as a viewer, even if he's in a different region and even if replication is behind.

The key tradeoff: zookies increase check latency when replication lags. In the normal case, the zookie is near-zero overhead — you just need to verify the replica is current, which it usually is. In the lag case, the check blocks waiting for replication. The paper reports this is infrequent in practice, but it means your p99 latency on check requests depends on replication velocity in a way that your p50 doesn't.

Critically, zookies require application-level discipline. If Alice's client shares the document but doesn't forward the zookie to Bob's client, Bob experiences the classic denial. This is an application contract, not an infrastructure guarantee. The infrastructure provides the mechanism; your code has to use it.

Leopard: when group sizes exceed what traversal can handle

Standard Zanzibar check: traverse the relation graph from the subject back to the object. For a user with membership in a few groups, each with a few hundred members, this is fast — a few recursive lookups, some batching, a cache hit on common subproblems.

For groups with millions of members — "all Google employees," "all users in an enterprise tenant" — naive traversal is untenable. Enumerating members on every check doesn't scale.

Leopard is Zanzibar's secondary index for large groups. It maintains a precomputed mapping: for each (userset, namespace) pair, which concrete users are members? When a check involves a large group, Zanzibar routes to Leopard instead of traversing the full membership graph.

The tradeoff is explicit in the paper: Leopard is updated asynchronously. When a user joins a large group, Leopard's index isn't immediately updated. The staleness window is seconds to minutes (the paper doesn't give a firm SLA). During this window, a check can return stale results — even with a valid zookie — because the zookie guarantees you see the tuple write, but the Leopard index update is a separate async process.

This is a real failure mode. It's especially visible during bulk user additions: onboard a new employee to "all employees" group, and for a window of time they may be denied access to resources that group membership should grant. The error is transient and self-resolving, which makes it harder to attribute and easy to dismiss as flakiness.

What the performance numbers actually show

From the paper (2019 data, Google production usage):

  • ~10M QPS total across all Zanzibar APIs at peak
  • 95th percentile check latency: ~3ms
  • 99th percentile check latency: ~15ms
  • Hundreds of billions of ACL tuples stored globally

The 3ms p95 is the number people cite, and it's real — but it covers the common case: a check that hits the in-request cache (Zanzibar caches partial traversal results within a single check request) or a replica that's already current. The 15ms p99 is more operationally relevant. Zookie staleness events, Leopard updates in flight, and cross-region routing anomalies are all p99 phenomena.

The Watch API (for streaming tuple changes) and the Read API (for listing tuples) have higher latency profiles than the check API. The paper focuses on check performance because checks are ~70% of the API surface by volume.

Production tradeoffs no one mentions in the benchmark post

Zookie threading requires application-level consistency you'll likely not achieve on day one. You have ten microservices. The one that writes permissions returns the zookie. It passes the zookie to the next service in the chain. But service 4 doesn't forward it to service 5, because nobody realized service 5 also makes permission checks. Service 5 hits a stale replica. This class of bug is invisible in development — your single-region dev environment replicates so fast that zookies are never needed. It surfaces in production under actual replication lag, which peaks during high write load and cross-region failovers, exactly when you can least afford it. There's no static analysis that catches missing zookie propagation; it's a code review concern that spans service boundaries.

Namespace config schema changes are operationally irreversible once you have tuples. Because Zanzibar stores config versions and tuples reference the version under which they were written, changing a namespace config requires handling tuples written under old versions correctly. The safe migration path — add new relations without removing old, migrate tuples to new semantics, deprecate old relations — takes weeks in a running system. Teams that treat namespace config changes like a database ALTER TABLE are right about the sequencing but wrong about the timeline. Any change to how permissions are derived is a production change that requires a migration plan.

Cycle detection isn't free. Namespace configs can express recursive relationships — group:eng#member can include group:backend#member which includes group:eng#member. Zanzibar has cycle detection in the traversal, but it requires tracking visited nodes per request, which adds per-request state. Deep graphs with many relation levels have higher traversal cost. If your authorization model has deeply nested inheritance chains (5+ relation levels deep), you'll see it in latency under load.

Open-source implementations don't all implement Leopard. SpiceDB, OpenFGA, and Ory Keto implement the core data model and check semantics well. Leopard is a performance optimization specific to Google's scale. At smaller scales you don't need it. But at the scale where large-group traversal becomes your bottleneck, you're likely building custom solutions on top of the open-source base — the ecosystem diverges from the paper at exactly the point where the paper's performance guarantees become important.

The Watch API requires non-trivial operational investment to use correctly. Watch delivers tuple change events as a stream with variable latency ("typically seconds") and ordering guarantees only within a namespace. If your authorization model has cross-namespace dependencies — which ReBAC models almost always do — you need to handle event ordering across streams carefully. If your Watch subscriber goes down, you miss events and need a backfill mechanism. Most teams end up using short TTL caching for the common case and reserving Watch for high-sensitivity paths where they're willing to pay the operational cost.

Failure modes in practice

The most common production failure: dropped zookies in a multi-service call chain. A write happens in service A, which forwards the zookie to service B, which doesn't forward it to service C's permission check. Service C hits a stale replica. The denial is transient — it resolves when replication catches up — which means it looks like flakiness rather than a code bug. Investigation is hard because the failure appears in the calling service (C), not where the zookie was dropped (B). You find it by adding zookie propagation logging to every service and auditing which requests carry them.

Leopard staleness during high-volume group changes. When you add a large number of users to a large group — a company acquisition, a department reorg — Leopard has a backlog. During the lag window, affected users receive denials for resources the group membership should grant. The window is self-resolving but can be minutes under high write volume. If your product has an explicit "group membership effective immediately" guarantee, Leopard's async model violates it for large groups.

Namespace config version skew during rolling deployment. If your Zanzibar deployment uses rolling updates with canary replicas, you can briefly have replicas running different config versions evaluating the same check. Zanzibar's own deployment handles this by fully propagating config changes globally before activating them. If your open-source implementation or self-hosted version doesn't replicate this behavior, you can end up in a state where different replicas apply different policy to the same request. This is rare, but when it happens, it's confusing: some users can access a resource, others can't, and the variance is load-balancer routing, not user state.

When not to use Zanzibar

If your authorization model is flat RBAC with a small number of roles. Five roles, each user has exactly one role per resource type, no inheritance between resource types. Zanzibar can express this, but so can a database table. Use the database table. The relation graph, namespace configs, and zookie machinery add operational complexity that you don't need and will spend engineering time maintaining.

If your resources are independent and permissions don't inherit across objects. The core value of ReBAC is deriving permissions from cross-object relationships: you can access this file because you own the folder it's in. If your resources are flat and self-contained, you're not using the primary capability Zanzibar provides. You're paying the complexity cost without getting the benefit.

If you can't treat authorization as a first-class distributed system. Running Zanzibar (or a compatible system) puts a stateful, globally-distributed service in the critical path of every user request. Incidents in your authorization service block your entire product. The operational maturity required — reliable deployment, graceful degradation modes, latency SLAs that feed into your product SLA — is significant. For teams that can't own this operationally, simpler authorization middleware (reads a permissions table, caches locally) is often the right choice, even if it doesn't scale to 10M QPS, which you probably don't have.

If your write volume is high enough that replication lag is chronic. The zookie model works when replication lag is occasional. If your authorization write rate is so high that replication is perpetually behind, the zookie path becomes the hot path — most checks are blocking on replication. This is usually a signal that your authorization model is too fine-grained: you're writing new tuples too frequently (e.g., a tuple per user session rather than per resource), not a sign that Zanzibar can't handle the load. Fix the model first.

What the paper actually gives you

Zanzibar's lasting contribution isn't the 10M QPS — that's a consequence of Google's infrastructure, not the algorithm. The contributions are the relation tuple data model (now an industry standard with multiple open-source implementations) and the zookie consistency model (underimplemented in most open-source versions, but the key insight for correctness in production).

The relation tuple model resolves a real tension in authorization system design. RBAC requires enumerating every permission explicitly; ABAC requires evaluation engines that are hard to audit; permission tables scale poorly with large object counts. Relation tuples give you a compact representation that scales with relationships, not with the combinatorial product of users and resources, and that expresses inheritance hierarchies without explicit enumeration. When the group membership changes, the derived permissions automatically update — because they're computed from the graph, not stored directly.

The zookie model resolves the unexamined assumption that "eventual consistency is fine for authorization." It turns out that "fine" depends entirely on your write workload. If users never change permissions on their own resources, eventual consistency has no user-visible consequences. If users share content with each other and expect sharing to take immediate effect, the new enemy problem is a real UX issue. Zookies are the mechanism that makes strong consistency practical without blocking writes globally — but they require application-level contract enforcement that's easy to implement incorrectly.

The 30-second permission delay that started this post? We implemented zookies — our write API returns a timestamp token, and our frontend threads it through subsequent read requests. The staleness window collapsed to replication latency for the specific replica handling the read, roughly 150ms in our setup. Not zero, but imperceptible.

Zanzibar: Google's Consistent, Global Authorization System — Pang, Beaumont, Calder, Saito, Schlichting, Gruner. USENIX Annual Technical Conference (ATC) 2019.