Google Zanzibar

Zanzibar is the system that decides whether you can open a Google Doc, a Photos album, a Calendar event, or a YouTube video. One backend answers authorization for Calendar, Cloud, Drive, Maps, Photos, and YouTube. The 2019 USENIX ATC paper by Ruoming Pang, Lea Kissner, and others describes a system holding more than 2 trillion permission records and serving over 10 million queries per second, with 95th-percentile latency under 10ms and availability above 99.999% across the three years before publication. The interesting part is not the scale. It is that the correctness core of the design exists to close one subtle bug that eventually-consistent permission systems are prone to.

Permissions as relationship tuples

Zanzibar throws out roles and per-object access lists. It stores one primitive: a relation tuple, written ⟨object⟩#⟨relation⟩@⟨user⟩ and read as “user has relation to object.” doc:readme#viewer@user:bob means Bob can view the readme. The @user half can itself be a set of users, a userset, written the same way: doc:readme#viewer@group:eng#member means every member of the engineering group is a viewer of the readme. This makes permissions a graph, and a check becomes a graph reachability question. The general name for this model is relationship-based access control (ReBAC).

Storing a tuple for every user-object pair would not scale, so namespaces carry a config with userset rewrite rules that compute relations from other relations. Three operations do most of the work: computed_userset (anyone who is an owner is also an editor), tuple_to_userset (anyone who can view the parent folder can view this document), and union (combine several sources). Folder inheritance, ownership hierarchies, and group nesting all fall out of composing these. The client writes the leaf tuples; the config expands them at check time.

The new enemy problem

The reason Zanzibar is hard is a bug the paper names the “new enemy problem.” Two versions:

Alice removes Bob from a folder’s ACL, then asks Charlie to move new documents into that folder, where document permissions inherit from the folder. Bob should not see the new documents. He will if the check ignores the ordering of the two ACL changes.
Alice removes Bob from a document, then adds new content to it. Bob should not see the new content. He will if the check runs against a stale copy of the ACL from before his removal.

Both are the same failure: applying an old permission decision to newer content. A cache that is merely “eventually consistent” produces exactly this leak. Preventing it requires the system to respect the causal ordering between permission changes and content changes, even when those changes hit different objects in different regions. This is a causal-ordering problem, and the fix is a leverage point in the structure of the system rather than a policy patch: get the ordering primitive right and the leak class disappears.

Zookies: buying freedom with a token

The naive fix is to evaluate every check against the freshest possible data with full global consistency. That would mean cross-region round trips on every permission check and would destroy the latency budget. Zanzibar’s move is to make consistency a per-request contract instead of a global mode.

Permissions live in Spanner, whose TrueTime clock stamps every write with a microsecond timestamp that reflects causal order. When a client saves content, it asks Zanzibar for a zookie (portmanteau of Zanzibar and cookie): an opaque token encoding a global timestamp guaranteed to be at least as fresh as every ACL write so far. The client stores that zookie atomically alongside the content. Later, a check for that content passes its zookie back, and Zanzibar evaluates at a snapshot no older than the token. Bob’s removal has a lower timestamp than the new content’s zookie, so the check that reads the content must also see the removal. The leak is closed by construction.

The token is opaque on purpose, to stop clients from inventing arbitrary timestamps and to leave room for future encodings. Its real value is the “at least as fresh” semantics: it pins down the one ordering constraint that matters and grants Zanzibar freedom to choose any timestamp fresher than the token. That freedom is what makes the system fast.

The guarantee is opt-in per request, which is the honest limit of the design. A client that saves content without threading a fresh zookie, or issues a check with no token, drops straight back into the leak. Zanzibar closes the bug by construction only when every calling application does its part, so the correctness burden is pushed out to hundreds of client teams. And “Safe” checks deliberately trade freshness for locality, accepting up to about 10 seconds of staleness to stay in-region.

Serving it fast: caching, quantization, Leopard

Zanzibar spends that freedom on cache reuse. It rounds evaluation timestamps up to a coarse grain, typically 1 or 10 seconds, so a flood of near-simultaneous checks lands on the same snapshot and shares cached results. The snapshot timestamp is baked into the cache key, so a stale snapshot is never mistaken for a fresh one. This is the same discipline as prompt caching: reuse is only safe when the key captures everything the result depended on, here a timestamp instead of a token prefix. The paper splits traffic into “Safe” requests (zookie more than 10 seconds old, servable from the local region) and “Recent” ones (under 10 seconds, often needing inter-region round trips); Safe requests outnumber Recent by roughly two orders of magnitude, which is why the coarse-grained cache works.

Checks fan out into internal “delegated” RPCs, and both the caller and callee cache results, forming cache trees; hot keys are spread across servers with Slicer. At peak Zanzibar runs 22 million delegated RPCs per second and roughly 200 million in-memory cache lookups per second. Spanner reads themselves take 0.5ms at the median and 2ms at the 95th percentile.

Deeply nested groups defeat caching, because checking membership means chasing pointers through group after group. A group of a million users nested five levels deep is a recursive walk on every check. Zanzibar offloads these to Leopard, a specialized index that stores flattened set membership as sorted integer lists in skip-list form, so a set intersection between sets A and B costs O(min(|A|,|B|)) seeks rather than a recursive traversal. Leopard rebuilds from periodic ACL snapshots and takes a live stream of updates in between. It serves 1.56 million queries per second at the median and answers in under 150 microseconds.

Scale, and what it spawned

The December 2018 sample in the paper: Check requests peak near 4.2M QPS, Reads at 8.2M, Expands at 760K, Writes at 25K. Reads outnumber writes by two orders of magnitude, which justifies pushing all the cost into read-side caching. The data sits in more than 30 replicas worldwide across over 10,000 servers in several dozen clusters. The median namespace holds around 15,000 tuples; the largest holds a trillion.

Zanzibar stayed internal, but the paper became a template. SpiceDB (from AuthZed) keeps closest to the paper’s schema language and adds a Watch API for cache invalidation. OpenFGA, now a CNCF sandbox project hosted by the Linux Foundation, came out of Auth0. Ory Keto, Permify, and Warrant round out the open-source field. All inherit the same bet: model permissions as a relationship graph, and treat consistency as a token you carry rather than a mode you pay for on every call.

Try it

Reproduce the new enemy leak (1-2 hours, SpiceDB via Docker). Run docker run -p 50051:50051 authzed/spicedb serve --grpc-preshared-key devkey and load a schema with a folder and a document whose viewer inherits from folder#viewer. Write folder:a#viewer@user:bob, then remove it, then add document:x#parent@folder:a. Run Check with minimize_latency / no consistency token versus at_least_as_fresh with the token (a “ZedToken”, SpiceDB’s zookie) returned by the removal write. The point is to see the two calls disagree: the token-bound check refuses to leak document:x to Bob, the latency-minimizing one can. That divergence is the entire reason the token exists.

Watch cache quantization (an afternoon). Fire a burst of identical checks and log the snapshot timestamp each resolves against. Group them and confirm they collapse onto a small number of rounded timestamps rather than a unique one per request. That collapse is what lets one Spanner read amortize across thousands of checks.

Sources

Zanzibar: Google’s Consistent, Global Authorization System — the original USENIX ATC 2019 paper (Pang et al.). Source for every number here.
An Introduction to Google Zanzibar — AuthZed’s walkthrough of the model and the new enemy problem.
Enforcing Causal Ordering: The New Enemy Problem — deeper treatment of why ordering, not freshness, is the real constraint.
Top 5 Zanzibar open-source implementations — the ecosystem the paper spawned.