'Can Jane open this file?' asked millions of times a second, across nested groups. How Google's Zanzibar answers it fast

Every product with a share button asks the same question constantly: can this user see this thing? When you open a file in a shared drive, something has to decide, right then, whether you belong to the set of people allowed to read it. Grant access to one person and the check is trivial: look for a row that says Jane can view this file.

Most systems don’t hand out access one person at a time. You share a file with a team, that team sits inside a department, and the department sits inside the org. The question becomes whether Jane sits anywhere in that tree of groups, directly or several levels up. Answering it means walking the hierarchy one hop at a time, and the deeper the nesting, the more lookups every check costs.

Google runs a single authorization system behind Drive, YouTube, Photos, Calendar, Maps and Cloud, called Zanzibar. It stores more than two trillion ACLs, serves millions of permission checks per second, and answers more than 95% of them within 10 milliseconds. At that scale the group-membership walk becomes a latency problem on its own, and the part of Zanzibar built to remove it is an index called Leopard. Everything else in Zanzibar is fairly standard distributed-systems machinery: Spanner underneath, consistent hashing across aclserver instances, caching, request hedging. Leopard is the piece this post is about.

The problem: pointer chasing

Zanzibar models everything as relation tuples. A tuple says “this user has this relation to this object”:

doc:readme#owner@10           # user 10 owns doc:readme
group:eng#member@11           # user 11 is a member of group:eng

The important detail is that the user position is not restricted to a user ID. It can also be a userset, written <object>#<relation>. That single feature is what gives Zanzibar nested groups:

group:payments-team#member@jane              # jane is a direct member of payments-team
group:backend#member@group:payments-team#member  # payments-team is nested inside backend
group:engg#member@group:backend#member           # backend is nested inside engg

Now ask the question a permission check has to answer: is Jane a member of engg?

The paper states check evaluation as a boolean expression:

CHECK(U, <object#relation>) =
    ∃ tuple <object#relation@U>
  ∨ ∃ tuple <object#relation@U'>, where
    U' = <object'#relation'> such that CHECK(U, U')

That second clause is recursive. Jane is not a direct member of engg, so the check expands to every userset that engg contains, then every userset those contain, and so on. The paper calls this “pointer chasing,” and it does not oversell it:

This kind of “pointer chasing” works well for most types of ACLs and groups, but can be expensive when indirect ACLs or groups are deep or wide.

Two things make this expensive, and they compound. Depth means more sequential hops, and every hop is a round trip to Spanner. Width means each hop fans out across servers; Zanzibar delegates subrequests by consistent hashing, so a wide group turns one check into many RPCs. A search results page needs tens to hundreds of checks before it can render, and every one of them pays this.

Leopard’s answer: precompute both halves, intersect at read time

Leopard sidesteps the walk entirely. Instead of traversing the membership graph on every check, it keeps a denormalized index of the graph’s transitive closure, built ahead of time.

The index stores (T, s, e) tuples, where T is an enum for the set type, and s and e are 64-bit integers for the set ID and the element ID. Group membership uses two of these set types:

• GROUP2GROUP(s) → {e} where s is an ancestor group and e is a descendant group nested under it, directly or indirectly.
• MEMBER2GROUP(s) → {e} where s is a user and e is a group the user is a direct member of.

For our example:

MEMBER2GROUP(jane) = { payments-team }
GROUP2GROUP(engg)   = { engg, backend, payments-team }

MEMBER2GROUP is deliberately shallow. It records only direct memberships, which is exactly what the raw tuples already say. GROUP2GROUP is where the expansion lives: it flattens every group-to-group path into a single hop. (GROUP2GROUP(engg) has to contain engg itself, otherwise a user who is a direct member of engg would fail the check below.)

The check is then one line:

CHECK(U, G) = (MEMBER2GROUP(U) ∩ GROUP2GROUP(G)) ≠ ∅

Both sets share payments-team, so the answer is yes. Two lookups and one intersection, and the number of hops between Jane and engg never enters the calculation.

Reframed, group membership is a reachability problem on a graph where nodes are users and groups and edges are direct memberships. Materializing the transitive closure turns each reachability query into a lookup. That is what Leopard does.

Why the intersection is cheap

“Set intersection” is only a win if the intersection itself is fast. Leopard stores each set as an ordered list of integers in a structure such as a skip list, which makes both union and intersection efficient:

# Both posting lists are sorted, so intersection is a merge walk.
# A skip list lets the larger list seek forward instead of stepping,
# so the work is bounded by the smaller list.
def intersects?(small, large)
  small.each do |id|
    return true if large.seek(id) == id   # O(log n) seek, not a scan
  end
  false
end

The paper puts the bound at O(min(|A|, |B|)) skip-list seeks. Sit with that bound for a second and the split between depth and breadth falls out of it. Depth is gone completely. Breadth has not disappeared, it has moved: a group with a million descendants still produces a million-element GROUP2GROUP set. But the cost is now min of the two set sizes, and MEMBER2GROUP(U) is small for essentially every user, since people belong to tens of groups directly. The huge set is the one you get to skip through.

The index is sharded by element ID and distributed across servers. Shards usually live entirely in memory, though they can also be served from a mix of hot and cold data across memory and remote SSDs.

Keeping a precomputed index fresh

A materialized transitive closure is only useful if it reflects reality, and authorization is the domain where a stale read is a security bug. Revoking someone’s group membership has to take effect. Leopard handles this by splitting into three parts.

An offline index builder generates shards from a snapshot of Zanzibar’s relation tuples and configs. It respects userset rewrite rules and recursively expands edges in the ACL graph, then replicates shards globally. Serving instances watch for new shards and swap the old ones out.

That alone would leave the index stale between rebuilds, which is unacceptable for an authorization decision. So each serving instance also maintains an incremental layer holding every update since the offline snapshot. These updates carry two extra fields: (T, s, e, t, d), where t is the update timestamp and d is a deletion marker. At query time, updates with a timestamp less than or equal to the query timestamp are merged on top of the base index. That is what lets Leopard answer at a consistent snapshot despite being built from a stale one, and the deletion marker is what makes a revocation take effect immediately.

The incremental layer is fed by Zanzibar’s Watch API, which streams tuple modifications in timestamp order. The indexer transforms that into a stream of Leopard tuple additions, updates and deletions, and every serving instance consumes the complete stream.

Trade-off: the cost lands on writes

This is a read-optimized denormalization, so the bill arrives on the write side. The paper is blunt about the size of it:

In practice, a single Zanzibar tuple addition or deletion may yield potentially tens of thousands of discrete Leopard tuple events.

Nesting one group inside another does not add one edge. It adds the cross product: every ancestor of the parent now gains every descendant of the child as a GROUP2GROUP entry. Nest a 5,000-group subtree under a group that already has 10 ancestors and you have generated 50,000 index entries from a single write.

Generating those updates is also not stateless. The incremental indexer has to maintain its own view of group-to-group membership to know what a single relation tuple change denormalizes into.

For authorization, this is a straightforwardly good trade. Permission checks outnumber membership changes by orders of magnitude, and the production numbers show the asymmetry directly:

Roughly three million queries for every write. Sub-millisecond reads at the 99th percentile, against an index that absorbs writes at a rate a single Postgres instance would find unremarkable.

Zanzibar does not route everything through Leopard. The paper says it handles checks this way “for selected namespaces that exhibit such structure.” Zanzibar otherwise deliberately avoids storage denormalization and relies on normalized data for consistency, handling hot spots with caching and request deduplication instead. Leopard is a targeted exception for the namespaces where pointer chasing hurts.

When this pattern applies to your system

Strip away the Google scale and the shape is general: when a read path needs the answer to a reachability question over a graph that changes slowly, precompute the reachability and intersect instead of walking.

The conditions that make it worth doing:

• Reads dominate writes by orders of magnitude. Leopard’s ratio is about 3,000:1. If yours is 2:1, the write amplification will eat you.
• The bottleneck is the traversal itself. If your nesting is two levels deep, a recursive CTE is fine, and you should write the recursive CTE.
• The graph mutates slowly relative to how often it is queried. Org charts, group hierarchies, category trees, folder structures. Not shopping carts.
• You can tolerate the write-side fan-out. Measure the worst case: the expensive write is the one that nests a large subtree under a well-connected ancestor.

The conditions that should make you stop:

• Writes need to be fast and synchronous. A single membership change touching tens of thousands of rows will not fit in a request-response cycle.
• Stale answers are not acceptable and you cannot build the incremental layer. The offline rebuild alone is not enough; the incremental layer with its deletion markers carries the correctness burden, and it is the harder half to build.
• Your fan-out has no ceiling. A closure over a densely connected graph can approach the size of the full cross product.

If you are running Postgres, the pattern maps onto a closure table maintained by triggers or an outbox consumer: one table for direct memberships, one for the transitive closure, and a check that becomes a join with an existence predicate instead of a WITH RECURSIVE. The Zanzibar-inspired open source systems have converged on the same idea. SpiceDB tracks a Leopard-style index as issue #129, and AuthZed ships a commercial query accelerator built on the same premise.

Conclusion

Leopard is a small idea carried out carefully: replace a recursive graph walk with two sorted sets and an intersection, then spend the engineering effort on keeping those sets fresh. Building the index is the straightforward part. The incremental layer, its timestamped deletion markers, and the snapshot merge are what make the result safe for an authorization decision.

The transferable lesson is the trade, not the implementation. If you have a slow graph walk sitting on a hot read path and writes are rare, precomputing the answer is usually available to you, and it is usually cheaper than you expect.

References

• Zanzibar: Google’s Consistent, Global Authorization System - Pang et al., USENIX ATC 2019. Leopard is §3.2.4; production numbers are §4.4.
• Zanzibar paper PDF
• An Introduction to Google Zanzibar and Relationship-Based Access Control - AuthZed
• SpiceDB issue #129: Leopard indexing system