A Check asks one question: is this user in this userset at this snapshot. Answering it can take dozens of reads spread over several servers. This page follows one Check from the inside: the boolean expression it becomes, the order in which its parts run, when it can stop early, what it leaves in the cache, and where it gives up.
Two other pages cover the neighbouring ground. Relation tuples and usersets walks the same question one branch at a time as a graph search. Architecture follows the request across servers: consistent hashing, cache trees, the lock table, read pooling and hedging. This page stays inside the evaluation.
A Check is a boolean expression
The paper starts from the case without rewrite rules: “Zanzibar evaluates ACL checks by converting check requests to boolean expressions” (§3.2.3). For a user U and a userset ⟨object#relation⟩, the paper’s formula reads:
CHECK(U, ⟨object#relation⟩) = ∃ tuple ⟨object#relation@U⟩
∨ ∃ tuple ⟨object#relation@U′⟩, where
U′ = ⟨object′#relation′⟩ s.t. CHECK(U, U′)
The first line is a direct hit: a stored tuple names the user. The second line is the recursion: a stored tuple names another userset, and the user is in that one. The paper calls following those references “pointer chasing” and notes that it “works well for most types of ACLs and groups, but can be expensive when indirect ACLs or groups are deep or wide” (§3.2.3). Rewrite rules join the same expression: “Userset rewrite rules are also translated to boolean expressions as part of check evaluation.”
Take the paper’s Figure 1 config for doc (§2.3.1). viewer is the union of its own tuples, editor, and the viewers of the parent folder; editor is the union of its own tuples and owner. Written out for Chen and the readme, assuming as the other pages do that folder#viewer has no rewrite rule:
viewer(readme, chen) = this(readme#viewer, chen)
∨ editor(readme, chen)
∨ ∃ parent tuple readme#parent@folder:X : viewer(folder:X, chen)
editor(readme, chen) = this(readme#editor, chen)
∨ this(readme#owner, chen)
Each this(…) is a tuple lookup, and each ∨ is a node in a tree. Which sub-problems does “can Chen view doc:readme?” split into?
Notice that the numbers name sub-problems, not a sequence. Leaves ②, ④a, ④b and ⑥ need only the readme’s own tuples, which is why the paper keys forwarding on the object (§3.2.5): they can all be answered by the server that owns doc:readme. Step ⑦ is a new Check on a different object, so it is forwarded to the server for folder:A, and it is itself a tree, here a single _this lookup.
All leaves at once, and cancellation
In what order do the leaves run? The paper does not walk the tree: “To minimize check latency, we evaluate all leaf nodes of the boolean expression tree concurrently. When the outcome of one node determines the result of a subtree, evaluation of other nodes in the subtree is cancelled.” (§3.2.3)
What does that look like over time for Chen’s check?
Notice that latency is set by the fastest path to a decisive answer, not by the slowest leaf. Had the parent branch been slow and Chen not been a viewer, the root would have had to wait for every child to say false.
Cancellation saves work, but it leaves a gap. A cancelled sub-check never writes its result to the cache, and other requests may be waiting for that result in the lock table. The paper ran into exactly this: “indirect ACL checks are frequently cancelled when the result of the parent ACL check is already determined. This leaves the cache key unpopulated.” Its fix: “we delay eager cancellation when there are waiters on the corresponding lock table entry” (§3.2.5).
When can each operator stop early
The paper lists three ways to combine sub-expressions, “union, intersection, and exclusion” (§2.3.1), and states one cancellation rule for all of them. When a subtree is “determined” depends on the operator. Which single answer is enough for each?
Notice the asymmetry. Each operator has one answer that can arrive early and one that needs every child. For a union the early answer is yes; for intersection and exclusion it is no. So a permission written as a union answers “allowed” as fast as its quickest path, while a permission with an intersection or exclusion answers “allowed” only as fast as its slowest required part. The table spells it out:
| Operator | Decided early by | Needs every child to say |
|---|---|---|
Union A ∪ B |
any child true → true | false, to answer false |
Intersection A ∩ B |
any child false → false | true, to answer true |
Exclusion A − B |
base false, or excluded true → false | base true and excluded false, to answer true |
Products follow the same logic. In OpenFGA’s check.go (v1.22.1), the union reducer returns on the first allowed result (“Short-circuit success”), the intersection reducer on the first not-allowed result (“Short-circuit failure”), and the exclusion reducer runs base and subtracted side concurrently and returns not-allowed when “base is false” or when “subtract is true”. AuthZed’s post on intersections and exclusions (2022-03-03) says that for these operators “SpiceDB can only partially short-circuit the subproblems”, and in its example “SpiceDB was able to cancel the other check immediately” once one branch of an intersection said no. For unions, its earlier post (2021-03-17) puts it simply: “any path found suffices to grant permission!”
Caching sub-results at a snapshot
Every node in the tree is a question with an answer, and the paper caches them all: the servers “form a distributed cache for both reads and check evaluations, including intermediate check results evaluated during pointer chasing” (§3.2.5). Step ⑦ above, “is Chen in folder:A#viewer”, is such an intermediate result. Any later check that reaches the same question can reuse it.
What makes reuse safe? A result is only true at a snapshot. The paper puts the snapshot in the key: “We avoid reusing results evaluated from a different snapshot by encoding snapshot timestamps in cache keys.” It then rounds evaluation timestamps up, “to a coarse granularity, such as one or ten seconds, while respecting staleness constraints from request zookies”, so that most checks land on the same few timestamps (§3.2.5; the rounding is drawn on the consistency page).
When does a cached sub-result help, and when is it a miss?
Notice that there is no invalidation step. An entry keyed by snapshot can never become wrong, because the data at 13 s never changes; it just stops being asked for once evaluation moves to later timestamps. AuthZed’s post on SpiceDB’s version of this (2023-05-10) states the same idea: “For any given problem or sub-problem, at a specified time, the result to the check is immutable”, and “if we were to change the evaluation timestamp, the cache keys would change as well”.
Two more mechanisms from §3.2.5 sit around this cache, and both are drawn on the architecture page: the cache trees formed by caching “at both the caller and the callee of internal RPCs”, and the lock table, where “Among requests sharing the same cache key only one request will begin processing; the rest block until the cache is populated.”
In products:
- SpiceDB rounds revisions into windows set by
--datastore-revision-quantization-interval, default5s(dsconfig/config.go, v1.57.1), and wraps its dispatcher in asingleflightlayer that counts “dispatch requests that were single flighted”, which plays the lock table’s role. - OpenFGA’s check cache is off by default (
checkQueryCache.enabledisfalse, TTL10swhen on) (configuration). Its entries expire after a TTL rather than belonging to a snapshot, which is why OpenFGA needs aHIGHER_CONSISTENCYmode to skip it (consistency; see Ordering without TrueTime).
Reads are pooled per check
The leaves ②, ④a, ④b and ⑥ all read rows of doc:readme. Rather than send each read on its own, “We apply a pooling mechanism to group reads for the same ACL check to minimize the number of read RPCs to Spanner” (§3.2.3). The paper does not describe the mechanism beyond that sentence. The architecture page draws the four reads meeting on one server; the storage layout, sorted by object and relation (§3.1.1), is what lets them become range reads over adjacent rows.
How deep can it go
The recursion in CHECK(U, U′) has no built-in bound: a group can contain a group that contains a group, and nothing in the data model forbids a cycle. What does a check do when it meets one?
The paper sets no number. It handles deep and wide nesting with Leopard for “selected namespaces that exhibit such structure” (§3.2.4; see the Leopard page), and §5 claims “safe pointer chasing despite potentially deep recursion (e.g. membership checks on hierarchical groups)” without saying what makes it safe beyond that. The per-client limits of §3.2.6 cap CPU and outstanding RPCs, not depth. Products choose explicit limits:
| System | Limit | Default | When reached | Source |
|---|---|---|---|---|
| Paper | none stated | none | not described | §3.2.4, §5 |
| SpiceDB | --dispatch-max-depth |
50 | error: “the check request has exceeded the allowable maximum depth of 50” | Cyclical relationships and traversal limits, serve.go |
| OpenFGA | resolveNodeLimit |
25 | error; cycles are detected first and answer not allowed | configuration, check.go |
| OpenFGA | resolveNodeBreadthLimit |
10 | caps “how many nodes on a given level can be evaluated concurrently” | configuration |
| Ory Keto | limit.max_read_depth |
5 | the global maximum; a request may only lower it | config.schema.json |
SpiceDB’s docs say it has no separate cycle detector: a cycle runs until it hits the depth limit and returns the same error as a very deep hierarchy, and the docs explain that tracking visited objects was avoided for reasons of semantics and performance (recursion and max depth). OpenFGA’s LocalChecker keeps a set of visited tuple keys per request and returns not allowed with CycleDetected when one repeats (check.go, hasCycle). Both limits count hops along one path, which is the depth of the tree in the first figure; resolveNodeBreadthLimit is the only one of these that bounds the paper’s “evaluate all leaf nodes … concurrently”.
Sources
- Ruoming Pang et al., Zanzibar: Google’s Consistent, Global Authorization System, USENIX ATC ’19, §2.3.1, §3.1.1, §3.2.3, §3.2.4, §3.2.5, §3.2.6, §5.
- AuthZed, Check it out: How permissions are answered in SpiceDB and Authzed, 2021-03-17 (vendor blog).
- AuthZed, Check it out #2: How intersections and exclusions are computed in SpiceDB and Authzed, 2022-03-03 (vendor blog).
- AuthZed, Hotspot Caching in Google Zanzibar and SpiceDB, 2023-05-10 (vendor blog).
- AuthZed, Cyclical Relationships and Traversal Limits, SpiceDB docs.
- SpiceDB v1.57.1 source:
pkg/cmd/serve.go,pkg/cmd/datastore/dsconfig/config.go,internal/dispatch/singleflight/singleflight.go. - OpenFGA, Configuring OpenFGA and Query Consistency Modes.
- OpenFGA v1.22.1 source:
internal/graph/check.go. - Ory Keto,
.schema/config.schema.json(limit.max_read_depth).