Check answers one question: may this user do this to this object. A list page asks another: which objects may this user see, filtered, sorted and one page at a time. This page explains why the second question is harder, what the paper provides for it, and the three approaches that Zanzibar-style products document.
A different question from Check
Check starts at one object and walks the tuples until it finds the user or runs out of paths (§2.4.4, §3.2.3). The work is bounded by what hangs off that object. “Every document Anne can see” has no starting object. Answering it with Check means one Check per document in the system, most of them answered “no”.
The list also needs data that the authorization service does not hold. OpenFGA’s guide puts it this way: the service “does not store object metadata (names of files, creation dates, time of last update, etc)”, so search “will require data from your database” (OpenFGA, Search With Permissions). Filtering and sorting happen in your database; authorization happens in the other service; the answer is the intersection of the two.
The paper knows this use case well. Among the advantages it gives for a unified system is “a search index that respects access control and works across applications” (§1), and its latency goal singles out “serving search results, which often require tens to hundreds of checks” (§1).
What the paper offers, and what it does not
The paper’s API has five calls: Read, Write, Watch, Check and Expand (§2.4). None of them returns “all objects user U can see”.
- Read returns stored tuples only. With a tupleset keyed by user, clients can “look up all groups with a given user as a direct member” (§2.4.1). Direct: Read does not apply rewrite rules, so it does not follow
editortovieweror a folder to its documents. - Expand follows the rewrite rules, but in the other direction: it takes an ⟨object#relation⟩ pair and returns its “effective userset” as a userset tree whose leaves “are user IDs or usersets pointing to other ⟨object#relation⟩ pairs” (§2.4.5). The paper names the purpose: it lets clients “build efficient search indices for access-controlled content” (§2.4.5). Building the index is the client’s job.
- Watch streams tuple changes so that “clients maintain secondary indices of relation tuples” (§2.4.3).
- Leopard (§3.2.4) flattens nested groups: it answers whether a user is in a group with one set intersection. It is used inside Zanzibar to speed up Check for “selected namespaces”; the paper does not describe it as a listing API. See Leopard, the group index.
What does Expand return for the readme’s viewers, compared with the flat list a client actually wants?
Notice that the tree answers “who can see this document”, not “what can Anne see”. To list Anne’s documents from Expand alone, a client would expand every document, or, as §2.4.5 suggests, expand ahead of time and keep the result in its own index. SpiceDB’s docs describe the same gap: Expand “responds with a tree structure that can be awkward for applications to consume”, so SpiceDB added LookupResources and LookupSubjects, which “return a flattened list of results” (SpiceDB, Google Zanzibar).
Approach 1: a lookup API, then filter in the database
The authorization service computes the reverse question directly: SpiceDB’s LookupResources and OpenFGA’s ListObjects return the IDs of every object of a type on which the user has a permission. The application then passes those IDs into its database query (WHERE id = ANY(…)), which filters, sorts and pages as usual. SpiceDB calls this “the simplest approach from a bookkeeping perspective and is a good place to start” (SpiceDB, Protecting a List Endpoint).
The cost is that the full set of IDs comes back before the first row is shown, and computing it walks the graph backwards from the user.
- SpiceDB: “it’s a heavy request that can cause performance problems when more than 10k results are involved” (SpiceDB, Querying Data); it “can get slow quickly: with a sufficiently large relation dataset, a sufficiently complex schema, or a sufficiently large set of accessible results” (Protecting a List Endpoint). The request streams its results and supports cursors.
- OpenFGA:
ListObjects“will return the results found within the time allotted (listObjectsDeadline, default:3s) up to the maximum number of results configured (listObjectsMaxResults, default:1000)”, and is positioned for “access-aware filtering on small object collections” (OpenFGA, Relationship Queries). Its performance varies “drastically depending on the model complexity, number of tuples, and the relations it needs to evaluate”, and relations withandorbut not“are more expensive to evaluate than relations withor” (Search With Permissions).
A partial list is not enough for sorting: OpenFGA notes that “you won’t be able to sort using it” until the whole list is in hand (Search With Permissions).
Approach 2: query the database, then check in bulk
The other direction: let the database produce a page of candidates (filtered and sorted by the user’s query), check the page with one bulk call (SpiceDB CheckBulkPermissions, OpenFGA /batch-check), drop the denied rows, and repeat until the page is full. This is Check used the way §1 describes for search results, tens to hundreds at a time.
SpiceDB’s guide gives the loop and its constraints: “because we don’t know how many results are going to be accessible beforehand, we need to iterate until we have a full page of accessible results”; performance “will depend in part on choosing the size of the page of candidate results”; and it “works better with an API backed by cursor-based pagination than limit-offset pagination, since the database doesn’t know the offset associated with the last accessible result” (Protecting a List Endpoint). It also recommends running all bulk calls “at the same revision”: take the ZedToken (SpiceDB’s zookie) from the first call and send it with the rest, so one page is not assembled from two snapshots.
How do the two approaches order their calls when Anne opens her document list?
Notice where the cost moves. Pre-filtering pays once, in proportion to everything Anne can see. Post-filtering pays per round, in proportion to how many candidates she cannot see. OpenFGA’s guide turns this into a rule: search-then-check fits when the database query returns few rows or the user can see a high share of them; it fits badly when the user sees many objects that are still a small share of the total, its “Google Drive” case, because “you will be retrieving and checking against a lot of items and discarding most of them” (Search With Permissions).
Approach 3: a denormalized index fed by Watch
The third approach is the one §2.4.3 and §2.4.5 describe: keep your own index of who can see what, next to the data it protects, and keep it current from the change stream. A list query then becomes a join in your own database.
Where does each piece live, and what keeps the index current?
Notice the indexer box: it does the work Leopard does inside Zanzibar. One tuple can change many rows. Adding group:eng#member@user:beto adds a row for every document group:eng can view; adding a viewer to folder:A adds a row for every document in the folder. The paper reports the same fan-out for Leopard: “a single Zanzibar tuple addition or deletion may yield potentially tens of thousands of discrete Leopard tuple events” (§3.2.4).
Products document two ways to build this:
- Build it yourself from the change stream. OpenFGA’s option 2 consumes
GET /changes, flattens the changes for the model version in use (its example: “user:anne, writer, doc:planningbecomes two tuples”), and then calls/checkon the final results “to filter out any resource with permissions revoked but whose authorization data has not made it into your index yet” (Search With Permissions). With SpiceDB the stream isWatch; Keeping tuples in step with your data covers why that stream is not a durable queue. - Have the vendor compute it. AuthZed Materialize “takes inspiration from the Leopard index”, precomputes configured permissions, and its Event Streams feature lets you “keep your own copy of it — either colocated alongside the data it protects in your application database, or in a secondary index like a search engine” (AuthZed, What is Materialize?). It is a commercial feature: Event Streams is “currently in early access for AuthZed Dedicated users” (Protecting a List Endpoint), and its documented limitations include that “your application must be able to tolerate some lag” (Materialize limitations).
The three side by side
The scale limits are quoted from each product’s documentation. Latency and effort are relative, not measured.
| Lookup API, then query | Query, then bulk check | Index fed by Watch | |
|---|---|---|---|
| Latency | Grows with the number of accessible objects and schema depth; full set before first row | Grows with the number of rounds, that is with the share of candidates denied | A database join; independent of graph depth |
| Freshness | Same consistency options as Check (ZedToken in SpiceDB; MINIMIZE_LATENCY / HIGHER_CONSISTENCY in OpenFGA) |
Same as Check; use one token for every round of a page | Lags the stream; re-check the page to drop revoked rows |
| Scale limits in docs | SpiceDB: “performance problems when more than 10k results are involved”. OpenFGA: defaults 3s and 1000 results, “small object collections” |
SpiceDB: depends on “the size of the page of candidate results”. OpenFGA: poor when the user sees a small share of many objects | SpiceDB: “the greatest scalability of the three options” (via Materialize) |
| Effort | One call and an IN clause |
A loop, cursor pagination, a page-size choice | An indexer, flattening logic, a stored stream position, rebuilds; or a commercial service |
OpenFGA’s guide adds two ways to make post-filtering viable when a user sees few objects out of many: filter by tenant in the database query (“Duplicating logic from the authorization model is not ideal, but it can be a reasonable trade-off”), or list a coarser resource first, for example the folders a user can see, and filter documents by folder (Search With Permissions). In the running example, Chen’s access comes from folder:A, so “documents in folders Chen can view” covers him with a list of one folder.
An empty list also needs a decision. SpiceDB’s guide suggests that in fine-grained systems it “often makes sense to treat ‘there is no data’ and ‘there is nothing you’re authorized to see’ as the same, by returning a successful response with an empty result set” rather than a 403 (Protecting a List Endpoint).
Sources
- Ruoming Pang et al., Zanzibar: Google’s Consistent, Global Authorization System, USENIX ATC ’19, §1, §2.4.1, §2.4.3, §2.4.5, §3.2.4.
- AuthZed (vendor), Protecting a List Endpoint, SpiceDB docs.
- AuthZed (vendor), Querying Data, SpiceDB docs.
- AuthZed (vendor), Google Zanzibar, SpiceDB docs, section “Reverse Indices”.
- AuthZed (vendor), What is Materialize? and Limitations.
- AuthZed, Proposal: Lookup Watch API and Tiger Cache for fast ACL-aware filtering, spicedb issue #207, opened 2021-10-22.
- OpenFGA, Search With Permissions.
- OpenFGA, Relationship Queries: Check, Read, Expand, ListObjects and ListUsers.
- OpenFGA, Query Consistency Modes.