Zanzibar: How Google Made Authorization One String

Let me start with the number, because it's the whole reason this post exists.

Every time you open a Google Doc, a Drive file, a Calendar event, or a YouTube video, a permission check runs against a system holding 2 trillion access control entries. That system answers 10 million checks per second, and 95% of those checks come back in under 10 milliseconds.

You've probably built authorization before. An isAdmin boolean. A roles table. Maybe a can(user, action, resource) function with a pile of if-statements that grew for two years and nobody wants to touch anymore. Every engineer builds authorization, and almost every engineer builds it badly, because it looks like a small problem until your product has folders inside folders, teams inside orgs, and someone asks "can a user who's a viewer on a shared drive, which is owned by a group, which contains a folder shared with another group, read this specific file?"

Google hit that wall around 2010. Every product team was reinventing ACLs: Gmail had one system, Drive had another, Calendar had a third, YouTube had a fourth. They were all subtly different, all had bugs, and none of them could answer nested questions like the one above without deeply-nested, slow recursive queries.

Their fix became a paper: "Zanzibar: Google's Consistent, Global Authorization System" (Pang et al., USENIX ATC 2019). It's one of those papers where the core idea is almost embarrassingly simple once you see it, and the hard part is entirely in making that simple idea correct and fast at planetary scale. This post walks through that idea the way I'd explain it to a junior engineer sitting next to me — and then we'll look at a small TypeScript implementation I wrote, zanzibar-lite, that captures the core mechanics without the trillion rows.

Here's the idea. Every permission in Zanzibar — no matter the product, no matter how complex the relationship — is expressed as a single, uniform fact:

Copy
object#relation@user

Read it left to right: object has relation to user. A few concrete examples make this click immediately:

Copy
doc:readme#viewer@alice
doc:readme#owner@bob
folder:reports#editor@group:eng#member
group:eng#member@carol

That last one is the interesting one. The "user" on the right side of a tuple doesn't have to be a person — it can be another relation, like "everyone who is a member of the eng group." That's called a userset, and it's the mechanism that lets you express groups, nested groups, and inherited permissions using the exact same data structure as a direct grant.

This is the part that should stop you in your tracks: Google didn't build a different system for "user has direct access" versus "user has access through a group" versus "user has access through a group that's inside another group." It's the same tuple, recursively resolved. One schema. One storage format. One check algorithm. Every product — Drive, Calendar, Photos, Cloud IAM — writes tuples into the same store and asks the same question: does this tuple exist, directly or transitively?

That uniformity is the whole trick. Once authorization is "just a graph of relation tuples," the actual hard engineering problems — consistency, latency, scale — become problems you only have to solve once, centrally, instead of once per product team, forever.

A Check(object, relation, user) call is a graph traversal. Given doc:readme#viewer@carol, the engine doesn't just look for an exact tuple match — it expands:

Copy
Check(doc:readme#viewer@carol)
  -> does tuple doc:readme#viewer@carol exist directly? no
  -> what usersets does doc:readme#viewer include?
       doc:readme#viewer@group:eng#member
  -> is carol a member of group:eng?
       Check(group:eng#member@carol)
         -> does tuple group:eng#member@carol exist directly? yes
  -> so carol IS a viewer, via group:eng

This is naturally recursive, and in a real org chart it can get deep — groups inside groups inside groups, five or six levels down isn't unusual at a large company. Naively, that means a single permission check can fan out into dozens of recursive lookups. At Google's scale, "naive" isn't an option. That's where two of Zanzibar's more clever pieces come in: zookies and the Leopard index. Neither one is about correctness — the recursive tuple model I just described is already correct. They exist purely to make correctness fast and safe under concurrency at global scale.

Here's a scenario that sounds paranoid until you think about it for ten seconds.

1. Alice removes Bob from a shared folder.
2. A fraction of a second later, Bob uploads a sensitive file to that folder using a cached, stale view of his permissions.
3. Because Zanzibar is a globally replicated system, the "Bob was removed" write hasn't propagated to every replica yet.
4. A background job in a datacenter that hasn't seen the removal checks "can Bob write here?" — and says yes.

Google calls this the New Enemy Problem. It's not a hypothetical edge case, it's the default failure mode of any globally distributed, eventually-consistent system doing security checks. If your authorization system can say "yes" using data that's a few hundred milliseconds stale, you have a real security bug, not a UX inconvenience.

Zanzibar's answer is a token called a zookie (yes, that's the real name — a nod to Google's Zookeeper/Chubby lineage and Spanner's TrueTime). A zookie is a consistency token that encodes "as of this point in time." The flow looks like this:

Copy
1. Client writes: Bob removed from folder → gets back zookie Z1
2. Client stores Z1 alongside the folder's content version
3. Later, any check against that folder is made "at least as fresh as Z1"
4. The check engine waits (bounded) for replication to catch up to Z1,
   or serves from a replica already past it

This is built on Spanner underneath, which gives Zanzibar globally consistent timestamps via TrueTime. The zookie essentially says: "don't answer my question using data older than the moment I made this change." It converts "eventually consistent" into "consistent enough for the specific causal chain that matters," without forcing every single check in the world to pay for full linearizability — that would collapse throughput. Most checks that don't need a fresh guarantee get to run against whatever replica is nearest and fastest, using the last fully-evaluated zookie. It's a nice pattern in general: don't ask the whole system to be as strict as your strictest caller, ask each caller to say how strict it needs to be.

In zanzibar-lite, I model the same idea without Spanner, using plain MVCC. Every write bumps a monotonically increasing revision number and stores an immutable snapshot of the whole tuple set at that revision. A zookie is nothing more than that revision number, base64-encoded:

typescript
Copy
1export function encodeZookie(revision: number): string {
2  return Buffer.from(`zookie:${revision}`).toString("base64url")
3}
4
5export function decodeZookie(value: string): number {
6  const decoded = Buffer.from(value, "base64url").toString("utf8")
7  const match = /^zookie:(\d+)$/.exec(decoded)
8  if (!match) throw new Error("invalid zookie")
9  return Number(match[1])
10}

check() always resolves a zookie to a specific, frozen snapshot before it evaluates anything:

typescript
Copy
1check(object: string, relation: string, user: string, zookie?: string): CheckResult {
2  const snapshot = this.store.snapshot(zookie) // pins to a specific revision
3  const allowed = this.evaluate(object, relation, user, snapshot, 0, new Set())
4  return { allowed, revision: snapshot.revision, zookie: encodeZookie(snapshot.revision) }
5}

That's the New Enemy Problem solved in miniature. One of the tests in the repo makes it concrete: Alice is granted viewer on folder:shared, which is captured in a zookie from before doc:readme is linked to that folder as its parent. Checking against the current state says Alice can view the doc (the parent link now exists). Checking against the old zookie says she can't — because, from that snapshot's point of view, the parent link never happened yet:

typescript
Copy
1const parent = engine.write({ object: "folder:shared", relation: "viewer", subject: "user:alice" })
2engine.write({ object: "doc:readme", relation: "parent", subject: "folder:shared" })
3
4expect(engine.check("doc:readme", "viewer", "user:alice").allowed).toBe(true)
5expect(engine.check("doc:readme", "viewer", "user:alice", parent.zookie).allowed).toBe(false)

Same contract as the real system, much smaller mechanism: a zookie is just a pointer into a totally-ordered history, and every check is required to say which point in that history it trusts.

Zookies solve correctness. The other half of the problem is raw speed on deeply nested groups.

Recall the recursive check I walked through earlier. Now imagine "group:eng#member" isn't 3 people — it's an org with 50,000 employees spread across 200 sub-teams, each of which is itself a group tuple pointing at other groups. A naive recursive check has to walk that entire graph, live, on every single request. At 10 million checks per second, you cannot afford live graph traversal through a 50,000-node membership tree for a huge fraction of your traffic.

The Leopard index is Zanzibar's answer: a precomputed, flattened index of transitive group membership. Instead of resolving "is carol in group:eng, which might contain groups that contain groups" at request time, Leopard periodically walks the whole group graph offline and materializes the flattened answer:

Copy
Live graph:              Leopard flattened index:
group:eng                group:eng#member includes:
  └─ group:backend          {alice, bob, carol, dave, ...}
       └─ group:payments    (every transitive member,
            └─ carol         computed once, looked up in O(1))

This trades a small amount of staleness (the index is refreshed on an interval, not instantaneously) for a massive win in check latency — a deep membership question collapses from "traverse a tree" to "look up a set." It's the same fundamental trade every good systems design makes: precompute what changes slowly, compute live only what changes fast. Group membership at a company changes far less often than "did carol just get access to this specific doc," so it's exactly the right thing to cache aggressively.

Combine zookies (correctness under replication lag) with Leopard (speed on deep nesting), and you get the headline numbers: peak Check throughput around 4.2 million QPS, Read throughput around 8.2 million QPS, both served with 99.999% availability over 3 years, and the vast majority of checks landing under 10ms even against a 2-trillion-tuple store.

Zanzibar wasn't open-sourced, but the paper described the model in enough detail that the industry rebuilt it. SpiceDB and OpenFGA are both direct, open-source implementations of the same relation-tuple model — object#relation@user, recursive usersets, consistency tokens, the works. If you've heard of "ReBAC" (relationship-based access control) as the successor to RBAC, this paper is where that term's modern usage comes from. The pitch is the same one Google made internally: stop letting every team hand-roll authorization logic, and instead let every team express permissions as data in one shared graph, checked by one shared, heavily-optimized engine.

Reading the paper is one thing; the ideas only really land once you implement the recursive check yourself. I built zanzibar-lite in TypeScript — an AuthorizationEngine, a revision-based TupleStore, and a GroupIndex that does the Leopard-style flattening. You can clone it and read the code directly; here's the shape of it, straight from src/types.ts, src/store.ts, and src/engine.ts.

A tuple is exactly the paper's object#relation@subject, as data:

typescript
Copy
1export type RelationTuple = {
2  object: string   // e.g. "doc:readme"
3  relation: string // e.g. "viewer"
4  subject: string  // e.g. "user:alice", or a userset like "group:eng#member"
5}

The interesting part isn't the tuple shape, it's the policy. Zanzibar's real power comes from userset rewrite rules — the definition of "viewer" on a document isn't just "whoever has a direct viewer tuple," it can be a boolean-ish expression over other relations. zanzibar-lite models that directly as a Policy:

typescript
Copy
1export type RelationRule =
2  | { kind: "direct" }
3  | { kind: "computed"; relation: string }
4  | { kind: "tupleToUserset"; tupleset: string; computedRelation: string }
5
6const policy: Policy = {
7  namespaces: {
8    doc: {
9      relations: {
10        owner: [{ kind: "direct" }],
11        editor: [
12          { kind: "direct" },
13          { kind: "computed", relation: "owner" }, // every owner is also an editor
14          { kind: "tupleToUserset", tupleset: "parent", computedRelation: "editor" }
15        ],
16        viewer: [
17          { kind: "direct" },
18          { kind: "computed", relation: "editor" }, // every editor is also a viewer
19          { kind: "tupleToUserset", tupleset: "parent", computedRelation: "viewer" }
20        ]
21      }
22    }
23  }
24}

Read editor out loud: a user is an editor of a doc if they have a direct editor tuple, or they're an owner (computed), or they're an editor of the doc's parent folder (tupleToUserset — walk the parent tuple, then re-check editor on whatever it points at). That third rule is exactly how Drive lets a folder's permissions cascade down to every file inside it, expressed as data instead of a special case in code.

check() evaluates that policy recursively, snapshot-pinned, with cycle protection via a visited-path set:

typescript
Copy
1check(object: string, relation: string, user: string, zookie?: string): CheckResult {
2  const snapshot = this.store.snapshot(zookie)
3  const allowed = this.evaluate(object, relation, user, snapshot, 0, new Set())
4  return { allowed, revision: snapshot.revision, zookie: encodeZookie(snapshot.revision) }
5}
6
7private evaluateRule(rule: RelationRule, object: string, relation: string, user: string, snapshot: Snapshot, depth: number, path: Set<string>): boolean {
8  if (rule.kind === "direct") {
9    if (object.startsWith("group:") && relation === "member" && this.groupIndex.has(object, user, snapshot.revision)) {
10      return true // fast path: flattened membership, no recursion
11    }
12    return this.tuplesFor(snapshot, object, relation)
13      .some((tuple) => this.subjectMatches(tuple.subject, user, snapshot, depth + 1, path))
14  }
15  if (rule.kind === "computed") {
16    return this.evaluate(object, rule.relation, user, snapshot, depth + 1, path)
17  }
18  // tupleToUserset: follow tuple.subject as an object, recheck computedRelation there
19  return this.tuplesFor(snapshot, object, rule.tupleset).some((tuple) => {
20    const target = this.objectReference(tuple.subject)
21    return target !== undefined && this.evaluate(target, rule.computedRelation, user, snapshot, depth + 1, path)
22  })
23}

Notice the direct branch: before it falls back to walking tuples one by one and recursing into any userset it finds, it checks this.groupIndex.has(...) first. That's the Leopard optimization wired directly into the hot path, not bolted on separately.

GroupIndex is the flattening step. On every write, it rebuilds a map from each group:X#member to the complete transitive set of users in it — following group:a contains group:b contains group:c all the way down, once, instead of on every check:

typescript
Copy
1export class GroupIndex {
2  private readonly snapshots = new Map<number, Map<string, Set<string>>>()
3
4  rebuild(snapshot: Snapshot): void {
5    // ...collects direct { user } members and { group } edges from group:*#member tuples...
6    const resolve = (group: string, visiting: Set<string>): Set<string> => {
7      const cached = flattened.get(group)
8      if (cached) return new Set(cached)
9      if (visiting.has(group)) return new Set() // cycle guard
10      const users = new Set(memberships.get(group) ?? [])
11      for (const child of groupRelations.get(group) ?? []) {
12        for (const user of resolve(child, new Set([...visiting, group]))) users.add(user)
13      }
14      flattened.set(group, users)
15      return new Set(users)
16    }
17    for (const group of memberships.keys()) resolve(group, new Set())
18    this.snapshots.set(snapshot.revision, flattened)
19  }
20
21  has(group: string, user: string, revision: number): boolean {
22    return this.snapshots.get(revision)?.get(group)?.has(user) ?? false
23  }
24}

Once that index exists, "is carol in a group nested five levels deep" stops being a five-level recursive walk and becomes one Set.has call. The test in the repo shows the whole chain end to end — Alice in group:platform, which is a member of group:engineering, which has viewer on a doc:

typescript
Copy
1engine.write({ object: "group:platform", relation: "member", subject: "user:alice" })
2engine.write({ object: "group:engineering", relation: "member", subject: "group:platform#member" })
3engine.write({ object: "doc:readme", relation: "viewer", subject: "group:engineering#member" })
4
5expect(engine.check("doc:readme", "viewer", "user:alice").allowed).toBe(true)
6expect(engine.check("doc:readme", "viewer", "user:bob").allowed).toBe(false)

Alice never appears anywhere near doc:readme. The engine gets there by resolving viewer → the group:engineering#member userset → the flattened index, which already knows Alice is a transitive member through group:platform. That's the whole paper — rewrite rules, recursive resolution, a flattened membership index, and a revision-pinned consistency token — in a few hundred lines you can actually read in one sitting. Clone the repo and run the test suite yourself; test/engine.test.ts is the fastest fifteen-minute tour of how Zanzibar actually thinks.

If you're early in your career and you've only ever built authorization as scattered if-checks, the lesson from Zanzibar isn't "rewrite your auth system to look like Google's." It's smaller and more useful than that:

Authorization is a graph problem, not a boolean-flag problem. The moment your product has "shared with a team," "owned by an org," or "inherited from a parent folder," you already have a graph, whether you modeled it as one or not. Modeling it explicitly — as tuples plus rewrite rules, however small — buys you a system where "can nested-group access flow through three levels" is a traversal you can reason about, instead of a special case you bolt on and hope doesn't break.

And the two hard problems that show up once you take that graph seriously — staying correct while data is changing underneath you (zookies), and staying fast when the graph gets deep (Leopard) — are the same two problems you'll eventually hit in any system that caches derived state. Zanzibar is a great case study not because you'll ever operate at 2 trillion tuples, but because it shows both problems solved cleanly, in isolation, in a system small enough to actually read the paper on.

Build the toy version yourself. It's the fastest way to understand why the real one needed a decade of Google infrastructure behind it.