Check beantwortet eine Frage: Darf dieser Benutzer dies mit diesem Objekt tun? Eine Listenseite fragt etwas anderes: Welche Objekte darf dieser Benutzer sehen, gefiltert, sortiert und seitenweise? Diese Seite erklärt, warum die zweite Frage schwieriger ist, was das Paper dafür bereitstellt und welche drei Ansätze Produkte im Zanzibar-Stil dokumentieren.
Eine andere Frage als Check
Check beginnt bei einem Objekt und läuft die Tupel ab, bis es den Benutzer findet oder keine Pfade mehr hat (§2.4.4, §3.2.3). Die Arbeit ist durch das begrenzt, was an diesem Objekt hängt. „Jedes Dokument, das Anne sehen kann“ hat kein Startobjekt. Es mit Check zu beantworten heißt, einen Check pro Dokument im System auszuführen, die meisten mit der Antwort „nein“.
Die Liste braucht außerdem Daten, die der Autorisierungsdienst nicht hält. Der Leitfaden von OpenFGA sagt es so: Der Dienst “does not store object metadata (names of files, creation dates, time of last update, etc)” (speichert keine Objektmetadaten (Dateinamen, Erstellungsdaten, Zeitpunkt der letzten Aktualisierung usw.)), also wird die Suche Daten aus Ihrer Datenbank benötigen (“will require data from your database”) (OpenFGA, Search With Permissions). Filtern und Sortieren geschieht in Ihrer Datenbank; Autorisierung im anderen Dienst; die Antwort ist die Schnittmenge aus beiden.
Das Paper kennt diesen Anwendungsfall gut. Zu den Vorteilen, die es für ein einheitliches System nennt, gehört “a search index that respects access control and works across applications” (§1) (einen Suchindex, der die Zugriffskontrolle respektiert und anwendungsübergreifend funktioniert), und sein Latenzziel hebt “serving search results, which often require tens to hundreds of checks” (§1) (die Auslieferung von Suchergebnissen, die oft Dutzende bis Hunderte von Prüfungen erfordern) hervor.
Was das Paper bietet und was nicht
Die API des Papers hat fünf Aufrufe: Read, Write, Watch, Check und Expand (§2.4). Keiner gibt „alle Objekte, die Benutzer U sehen kann“ zurück.
- Read gibt nur gespeicherte Tupel zurück. Mit einer Tupelmenge, die den Benutzer als Schlüssel angibt, können Clients “look up all groups with a given user as a direct member” (§2.4.1) (alle Gruppen nachschlagen, in denen ein gegebener Benutzer direktes Mitglied ist). Direkt: Read wendet keine Umschreibregeln an, folgt also weder von
editorzuviewernoch von einem Ordner zu seinen Dokumenten. - Expand folgt den Umschreibregeln, aber in die andere Richtung: Es nimmt ein Paar ⟨object#relation⟩ und gibt dessen “effective userset” (effektives Userset) als Userset-Baum zurück, dessen Blätter “are user IDs or usersets pointing to other ⟨object#relation⟩ pairs” (§2.4.5) (Benutzer-IDs oder Usersets sind, die auf andere Paare ⟨object#relation⟩ zeigen). Das Paper nennt den Zweck: Es erlaubt Clients, “build efficient search indices for access-controlled content” (§2.4.5) (effiziente Suchindizes für zugriffskontrollierte Inhalte aufzubauen). Den Index aufzubauen ist Aufgabe des Clients.
- Watch streamt Tupeländerungen, damit “clients maintain secondary indices of relation tuples” (§2.4.3) (Clients sekundäre Indizes von Relationstupeln pflegen).
- Leopard (§3.2.4) flacht verschachtelte Gruppen ab: Es beantwortet mit einer einzigen Schnittmengenbildung, ob ein Benutzer in einer Gruppe ist. Es wird innerhalb von Zanzibar verwendet, um Check für “selected namespaces” (ausgewählte Namespaces) zu beschleunigen; das Paper beschreibt es nicht als Listen-API. Siehe Leopard, der Gruppenindex.
Was gibt Expand für die Betrachter des Readmes zurück, verglichen mit der flachen Liste, die ein Client eigentlich will?
Der Baum beantwortet „wer kann dieses Dokument sehen“, nicht „was kann Anne sehen“. Um Annes Dokumente allein mit Expand aufzulisten, müsste ein Client jedes Dokument expandieren oder, wie §2.4.5 nahelegt, im Voraus expandieren und das Ergebnis in seinem eigenen Index halten. Die SpiceDB-Dokumentation beschreibt dieselbe Lücke: Expand “responds with a tree structure that can be awkward for applications to consume” (antwortet mit einer Baumstruktur, die für Anwendungen umständlich zu verarbeiten sein kann), daher fügte SpiceDB LookupResources und LookupSubjects hinzu, die “return a flattened list of results” (eine abgeflachte Ergebnisliste zurückgeben) (SpiceDB, Google Zanzibar).
Ansatz 1: eine Lookup-API, dann in der Datenbank filtern
Der Autorisierungsdienst berechnet die umgekehrte Frage direkt: LookupResources von SpiceDB und ListObjects von OpenFGA geben die IDs aller Objekte eines Typs zurück, auf denen der Benutzer eine Berechtigung hat. Die Anwendung gibt diese IDs dann in ihre Datenbankabfrage (WHERE id = ANY(…)), die wie gewohnt filtert, sortiert und paginiert. SpiceDB nennt dies “the simplest approach from a bookkeeping perspective and is a good place to start” (den aus Sicht der Buchführung einfachsten Ansatz und einen guten Ausgangspunkt) (SpiceDB, Protecting a List Endpoint).
Der Preis ist, dass die vollständige Menge von IDs zurückkommt, bevor die erste Zeile angezeigt wird, und dass ihre Berechnung den Graphen vom Benutzer aus rückwärts durchläuft.
- SpiceDB: “it’s a heavy request that can cause performance problems when more than 10k results are involved” (es ist eine schwere Anfrage, die Performance-Probleme verursachen kann, wenn mehr als 10.000 Ergebnisse beteiligt sind) (SpiceDB, Querying Data); es “can get slow quickly: with a sufficiently large relation dataset, a sufficiently complex schema, or a sufficiently large set of accessible results” (kann schnell langsam werden: bei einem hinreichend großen Beziehungsdatensatz, einem hinreichend komplexen Schema oder einer hinreichend großen Menge zugänglicher Ergebnisse) (Protecting a List Endpoint). Die Anfrage streamt ihre Ergebnisse und unterstützt Cursor.
- 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)” (gibt die innerhalb der zugeteilten Zeit (listObjectsDeadline, Standard:3s) gefundenen Ergebnisse bis zur konfigurierten Höchstzahl an Ergebnissen (listObjectsMaxResults, Standard:1000) zurück) und ist für “access-aware filtering on small object collections” (zugriffsbewusstes Filtern auf kleinen Objektsammlungen) vorgesehen (OpenFGA, Relationship Queries). Seine Performance schwankt “drastically depending on the model complexity, number of tuples, and the relations it needs to evaluate” (drastisch je nach Komplexität des Modells, Zahl der Tupel und den auszuwertenden Relationen), und Relationen mitandoderbut not“are more expensive to evaluate than relations withor” (sind teurer auszuwerten als Relationen mitor) (Search With Permissions).
Eine Teilliste genügt zum Sortieren nicht: OpenFGA merkt an, dass “you won’t be able to sort using it” (Sie damit nicht sortieren können), solange die ganze Liste nicht vorliegt (Search With Permissions).
Ansatz 2: die Datenbank abfragen, dann gebündelt prüfen
Die andere Richtung: Die Datenbank liefert eine Seite von Kandidaten (gefiltert und sortiert nach der Abfrage des Benutzers), die Seite wird mit einem gebündelten Aufruf geprüft (SpiceDB CheckBulkPermissions, OpenFGA /batch-check), die abgewiesenen Zeilen werden verworfen, und das wird wiederholt, bis die Seite voll ist. So wird Check verwendet, wie §1 es für Suchergebnisse beschreibt: Dutzende bis Hunderte auf einmal.
Der Leitfaden von SpiceDB nennt die Schleife und ihre Randbedingungen: “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” (weil wir vorher nicht wissen, wie viele Ergebnisse zugänglich sein werden, müssen wir iterieren, bis wir eine volle Seite zugänglicher Ergebnisse haben); die Performance “will depend in part on choosing the size of the page of candidate results” (hängt zum Teil von der gewählten Größe der Kandidatenseite ab); und es “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” (funktioniert besser mit einer API mit cursorbasierter Paginierung als mit Limit-Offset-Paginierung, da die Datenbank den Offset des letzten zugänglichen Ergebnisses nicht kennt) (Protecting a List Endpoint). Er empfiehlt außerdem, alle gebündelten Aufrufe “at the same revision” (in derselben Revision) auszuführen: das ZedToken (der zookie von SpiceDB) aus dem ersten Aufruf nehmen und mit den übrigen mitsenden, damit eine Seite nicht aus zwei Snapshots zusammengesetzt wird.
In welcher Reihenfolge rufen die beiden Ansätze auf, wenn Anne ihre Dokumentliste öffnet?
Beachten Sie, wohin sich die Kosten verschieben. Vorfiltern zahlt einmal, proportional zu allem, was Anne sehen kann. Nachfiltern zahlt pro Runde, proportional dazu, wie viele Kandidaten sie nicht sehen kann. Der Leitfaden von OpenFGA macht daraus eine Regel: Suchen-dann-Prüfen passt, wenn die Datenbankabfrage wenige Zeilen liefert oder der Benutzer einen hohen Anteil davon sehen kann; es passt schlecht, wenn der Benutzer viele Objekte sieht, die dennoch ein kleiner Anteil des Ganzen sind, sein „Google Drive“-Fall, weil “you will be retrieving and checking against a lot of items and discarding most of them” (Sie viele Elemente abrufen und prüfen und die meisten davon verwerfen werden) (Search With Permissions).
Ansatz 3: ein denormalisierter Index, gespeist von Watch
Der dritte Ansatz ist der, den §2.4.3 und §2.4.5 beschreiben: einen eigenen Index darüber halten, wer was sehen kann, neben den Daten, die er schützt, und ihn aus dem Änderungsstream aktuell halten. Eine Listenabfrage wird dann zu einem Join in Ihrer eigenen Datenbank.
Wo liegt jedes Teil, und was hält den Index aktuell?
Beachten Sie den Indexer-Kasten: Er leistet die Arbeit, die Leopard innerhalb von Zanzibar leistet. Ein Tupel kann viele Zeilen ändern. group:eng#member@user:beto hinzuzufügen fügt eine Zeile für jedes Dokument hinzu, das group:eng sehen kann; einen Betrachter zu folder:A hinzuzufügen fügt eine Zeile für jedes Dokument im Ordner hinzu. Das Paper berichtet dieselbe Auffächerung für Leopard: “a single Zanzibar tuple addition or deletion may yield potentially tens of thousands of discrete Leopard tuple events” (§3.2.4) (ein einziges Hinzufügen oder Löschen eines Zanzibar-Tupels kann potenziell Zehntausende einzelner Leopard-Tupelereignisse erzeugen).
Produkte dokumentieren zwei Wege, das aufzubauen:
- Selbst aus dem Änderungsstream aufbauen. Option 2 von OpenFGA konsumiert
GET /changes, flacht die Änderungen für die verwendete Modellversion ab (ihr Beispiel: “user:anne, writer, doc:planningbecomes two tuples”, also: wird zu zwei Tupeln) und ruft dann/checkauf den Endergebnissen auf, “to filter out any resource with permissions revoked but whose authorization data has not made it into your index yet” (um jede Ressource herauszufiltern, deren Berechtigungen entzogen wurden, deren Autorisierungsdaten es aber noch nicht in Ihren Index geschafft haben) (Search With Permissions). Bei SpiceDB ist der StreamWatch; Tupel mit Ihren Daten im Gleichschritt halten behandelt, warum dieser Stream keine dauerhafte Queue ist. - Den Hersteller berechnen lassen. AuthZed Materialize “takes inspiration from the Leopard index” (ist vom Leopard-Index inspiriert), berechnet konfigurierte Berechtigungen vorab, und seine Funktion Event Streams lässt Sie “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” (Ihre eigene Kopie davon halten, entweder neben den Daten, die sie schützt, in Ihrer Anwendungsdatenbank oder in einem sekundären Index wie einer Suchmaschine) (AuthZed, What is Materialize?). Es ist eine kommerzielle Funktion: Event Streams ist “currently in early access for AuthZed Dedicated users” (derzeit im Early Access für Benutzer von AuthZed Dedicated) (Protecting a List Endpoint), und zu den dokumentierten Einschränkungen gehört, dass “your application must be able to tolerate some lag” (Ihre Anwendung eine gewisse Verzögerung tolerieren können muss) (Materialize limitations).
Die drei nebeneinander
Die Skalierungsgrenzen sind aus der Dokumentation des jeweiligen Produkts zitiert. Latenz und Aufwand sind relativ, nicht gemessen.
| Lookup-API, dann Abfrage | Abfrage, dann gebündelte Prüfung | Von Watch gespeister Index | |
|---|---|---|---|
| Latenz | Wächst mit der Zahl zugänglicher Objekte und der Schematiefe; vollständige Menge vor der ersten Zeile | Wächst mit der Zahl der Runden, also mit dem Anteil abgewiesener Kandidaten | Ein Datenbank-Join; unabhängig von der Graphtiefe |
| Aktualität | Dieselben Konsistenzoptionen wie Check (ZedToken in SpiceDB; MINIMIZE_LATENCY / HIGHER_CONSISTENCY in OpenFGA) |
Wie bei Check; ein Token für jede Runde einer Seite verwenden | Hinkt dem Stream hinterher; die Seite erneut prüfen, um entzogene Zeilen zu verwerfen |
| Skalierungsgrenzen laut Doku | SpiceDB: “performance problems when more than 10k results are involved”. OpenFGA: Standards 3s und 1000 Ergebnisse, “small object collections” |
SpiceDB: hängt von “the size of the page of candidate results” ab. OpenFGA: schlecht, wenn der Benutzer einen kleinen Anteil vieler Objekte sieht | SpiceDB: “the greatest scalability of the three options” (über Materialize) |
| Aufwand | Ein Aufruf und eine IN-Klausel |
Eine Schleife, Cursor-Paginierung, eine Wahl der Seitengröße | Ein Indexer, Abflachungslogik, eine gespeicherte Stream-Position, Neuaufbauten; oder ein kommerzieller Dienst |
Der Leitfaden von OpenFGA nennt zwei weitere Wege, Nachfiltern tragfähig zu machen, wenn ein Benutzer wenige von vielen Objekten sieht: in der Datenbankabfrage nach Mandant filtern (“Duplicating logic from the authorization model is not ideal, but it can be a reasonable trade-off”, also: Logik aus dem Autorisierungsmodell zu duplizieren ist nicht ideal, kann aber ein vernünftiger Kompromiss sein) oder zuerst eine gröbere Ressource auflisten, zum Beispiel die Ordner, die ein Benutzer sehen kann, und die Dokumente nach Ordner filtern (Search With Permissions). Im durchgehenden Beispiel stammt Chens Zugriff von folder:A, also deckt „Dokumente in Ordnern, die Chen sehen kann“ ihn mit einer Liste aus einem Ordner ab.
Auch eine leere Liste braucht eine Entscheidung. Der Leitfaden von SpiceDB schlägt vor, dass es in feingranularen Systemen “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” (oft sinnvoll ist, „es gibt keine Daten“ und „es gibt nichts, was Sie sehen dürfen“ gleich zu behandeln, indem eine erfolgreiche Antwort mit leerer Ergebnismenge zurückgegeben wird), statt eines 403 (Protecting a List Endpoint).
Quellen
- 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 (Hersteller), Protecting a List Endpoint, SpiceDB-Dokumentation.
- AuthZed (Hersteller), Querying Data, SpiceDB-Dokumentation.
- AuthZed (Hersteller), Google Zanzibar, SpiceDB-Dokumentation, Abschnitt „Reverse Indices“.
- AuthZed (Hersteller), What is Materialize? und Limitations.
- AuthZed, Proposal: Lookup Watch API and Tiger Cache for fast ACL-aware filtering, spicedb-Issue #207, eröffnet 2021-10-22.
- OpenFGA, Search With Permissions.
- OpenFGA, Relationship Queries: Check, Read, Expand, ListObjects and ListUsers.
- OpenFGA, Query Consistency Modes.