Ein Check stellt eine Frage: Ist dieser Benutzer in diesem Userset zu diesem Snapshot? Die Antwort kann Dutzende von Lesevorgängen auf mehreren Servern erfordern. Diese Seite verfolgt einen Check von innen: den booleschen Ausdruck, zu dem er wird, die Reihenfolge, in der seine Teile laufen, wann er früh aufhören kann, was er im Cache hinterlässt und wo er aufgibt.
Zwei andere Seiten decken das angrenzende Gebiet ab. Relationstupel und Usersets geht dieselbe Frage Zweig für Zweig als Graphsuche durch. Architektur verfolgt die Anfrage über die Server hinweg: konsistentes Hashing, Cache-Bäume, die Sperrtabelle, das Bündeln von Lesevorgängen und Hedging. Diese Seite bleibt innerhalb der Auswertung.
Ein Check ist ein boolescher Ausdruck
Das Paper beginnt mit dem Fall ohne Umschreibregeln: “Zanzibar evaluates ACL checks by converting check requests to boolean expressions” (§3.2.3) (Zanzibar wertet ACL-Prüfungen aus, indem es Check-Anfragen in boolesche Ausdrücke umwandelt). Für einen Benutzer U und ein Userset ⟨object#relation⟩ lautet die Formel des Papers:
CHECK(U, ⟨object#relation⟩) = ∃ tuple ⟨object#relation@U⟩
∨ ∃ tuple ⟨object#relation@U′⟩, where
U′ = ⟨object′#relation′⟩ s.t. CHECK(U, U′)
Die erste Zeile ist ein direkter Treffer: Ein gespeichertes Tupel nennt den Benutzer. Die zweite Zeile ist die Rekursion: Ein gespeichertes Tupel nennt ein anderes Userset, und der Benutzer ist in diesem enthalten. Das Paper nennt das Verfolgen dieser Verweise “pointer chasing” (Zeigerverfolgung) und merkt an, dass es “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) (für die meisten Arten von ACLs und Gruppen gut funktioniert, aber teuer werden kann, wenn indirekte ACLs oder Gruppen tief oder breit sind). Umschreibregeln gehen in denselben Ausdruck ein: “Userset rewrite rules are also translated to boolean expressions as part of check evaluation.” (Userset-Umschreibregeln werden im Rahmen der Check-Auswertung ebenfalls in boolesche Ausdrücke übersetzt.)
Nehmen Sie die Konfiguration für doc aus Abbildung 1 des Papers (§2.3.1). viewer ist die Vereinigung seiner eigenen Tupel, von editor und der Betrachter des übergeordneten Ordners; editor ist die Vereinigung seiner eigenen Tupel und von owner. Ausgeschrieben für Chen und das Readme, unter der Annahme, wie auf den anderen Seiten, dass folder#viewer keine Umschreibregel hat:
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)
Jedes this(…) ist ein Tupel-Lookup, und jedes ∨ ist ein Knoten in einem Baum. In welche Teilprobleme zerfällt „darf Chen doc:readme sehen?“?
Die Nummern bezeichnen Teilprobleme, keine Abfolge. Die Blätter ②, ④a, ④b und ⑥ brauchen nur die eigenen Tupel des Readmes; deshalb verwendet das Paper bei der Weiterleitung das Objekt als Schlüssel (§3.2.5): Sie können alle von dem Server beantwortet werden, dem doc:readme gehört. Schritt ⑦ ist ein neuer Check auf einem anderen Objekt, wird also an den Server für folder:A weitergeleitet und ist selbst ein Baum, hier ein einzelner _this-Lookup.
Alle Blätter gleichzeitig und Abbruch
In welcher Reihenfolge laufen die Blätter? Das Paper durchläuft den Baum nicht: “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) (Um die Latenz von Prüfungen zu minimieren, werten wir alle Blattknoten des booleschen Ausdrucksbaums gleichzeitig aus. Wenn das Ergebnis eines Knotens das Ergebnis eines Teilbaums bestimmt, wird die Auswertung der anderen Knoten im Teilbaum abgebrochen.)
Wie sieht das für Chens Prüfung über die Zeit aus?
Die Latenz wird durch den schnellsten Pfad zu einer entscheidenden Antwort bestimmt, nicht durch das langsamste Blatt. Wäre der parent-Zweig langsam gewesen und Chen kein Betrachter, hätte die Wurzel warten müssen, bis jedes Kind falsch meldet.
Der Abbruch spart Arbeit, hinterlässt aber eine Lücke. Eine abgebrochene Teilprüfung schreibt ihr Ergebnis nie in den Cache, und andere Anfragen warten womöglich in der Sperrtabelle auf genau dieses Ergebnis. Das Paper stieß genau darauf: “indirect ACL checks are frequently cancelled when the result of the parent ACL check is already determined. This leaves the cache key unpopulated.” (indirekte ACL-Prüfungen werden häufig abgebrochen, wenn das Ergebnis der übergeordneten ACL-Prüfung bereits feststeht. Dadurch bleibt der Cache-Schlüssel leer.) Seine Lösung: “we delay eager cancellation when there are waiters on the corresponding lock table entry” (§3.2.5) (wir verzögern den frühzeitigen Abbruch, wenn auf den entsprechenden Eintrag der Sperrtabelle gewartet wird).
Wann jeder Operator früh aufhören kann
Das Paper nennt drei Arten, Teilausdrücke zu kombinieren, “union, intersection, and exclusion” (§2.3.1) (Vereinigung, Schnittmenge und Ausschluss), und gibt für alle eine einzige Abbruchregel an. Wann ein Teilbaum „bestimmt“ ist, hängt vom Operator ab. Welche einzelne Antwort reicht jeweils aus?
Beachten Sie die Asymmetrie. Jeder Operator hat eine Antwort, die früh eintreffen kann, und eine, die jedes Kind braucht. Bei einer Vereinigung ist die frühe Antwort ja; bei Schnittmenge und Ausschluss ist sie nein. Eine als Vereinigung geschriebene Berechtigung antwortet „erlaubt“ also so schnell wie ihr schnellster Pfad, während eine Berechtigung mit Schnittmenge oder Ausschluss „erlaubt“ nur so schnell beantwortet wie ihr langsamster erforderlicher Teil. Die Tabelle schlüsselt es auf:
| Operator | Früh entschieden durch | Braucht von jedem Kind |
|---|---|---|
Vereinigung A ∪ B |
ein Kind wahr → wahr | falsch, um falsch zu antworten |
Schnittmenge A ∩ B |
ein Kind falsch → falsch | wahr, um wahr zu antworten |
Ausschluss A − B |
Basis falsch oder Ausgeschlossenes wahr → falsch | Basis wahr und Ausgeschlossenes falsch, um wahr zu antworten |
Produkte folgen derselben Logik. In OpenFGAs check.go (v1.22.1) kehrt der Reducer für Vereinigungen beim ersten erlaubten Ergebnis zurück (“Short-circuit success”), der Reducer für Schnittmengen beim ersten nicht erlaubten Ergebnis (“Short-circuit failure”), und der Reducer für Ausschlüsse führt Basis und abgezogene Seite gleichzeitig aus und gibt „nicht erlaubt“ zurück, wenn “base is false” (die Basis falsch ist) oder wenn “subtract is true” (die abgezogene Seite wahr ist). Der Beitrag von AuthZed über Schnittmengen und Ausschlüsse (2022-03-03) sagt, dass bei diesen Operatoren “SpiceDB can only partially short-circuit the subproblems” (SpiceDB die Teilprobleme nur teilweise kurzschließen kann), und in seinem Beispiel “SpiceDB was able to cancel the other check immediately” (konnte SpiceDB den anderen check sofort abbrechen), sobald ein Zweig einer Schnittmenge nein sagte. Für Vereinigungen formuliert es der frühere Beitrag (2021-03-17) einfach: “any path found suffices to grant permission!” (jeder gefundene Pfad genügt, um die Berechtigung zu gewähren!)
Teilergebnisse zu einem Snapshot cachen
Jeder Knoten im Baum ist eine Frage mit einer Antwort, und das Paper cacht sie alle: Die Server “form a distributed cache for both reads and check evaluations, including intermediate check results evaluated during pointer chasing” (§3.2.5) (bilden einen verteilten Cache sowohl für Lesevorgänge als auch für Check-Auswertungen, einschließlich Zwischenergebnissen von Prüfungen, die bei der Zeigerverfolgung ausgewertet werden). Schritt ⑦ oben, „ist Chen in folder:A#viewer“, ist ein solches Zwischenergebnis. Jede spätere Prüfung, die dieselbe Frage erreicht, kann es wiederverwenden.
Was macht die Wiederverwendung sicher? Ein Ergebnis ist nur zu einem Snapshot wahr. Das Paper legt den Snapshot in den Schlüssel: “We avoid reusing results evaluated from a different snapshot by encoding snapshot timestamps in cache keys.” (Wir vermeiden die Wiederverwendung von Ergebnissen, die auf einem anderen Snapshot ausgewertet wurden, indem wir Snapshot-Zeitstempel in Cache-Schlüssel kodieren.) Dann rundet es Auswertungszeitstempel auf, “to a coarse granularity, such as one or ten seconds, while respecting staleness constraints from request zookies” (auf eine grobe Granularität, etwa eine oder zehn Sekunden, unter Beachtung der Veraltungsgrenzen aus den zookies der Anfragen), sodass die meisten Prüfungen auf denselben wenigen Zeitstempeln landen (§3.2.5; die Rundung ist auf der Konsistenzseite gezeichnet).
Wann hilft ein gecachtes Teilergebnis, und wann ist es ein Fehltreffer?
Es gibt keinen Invalidierungsschritt. Ein Eintrag mit dem Snapshot im Schlüssel kann nie falsch werden, weil sich die Daten bei 13 s nie ändern; er wird einfach nicht mehr abgefragt, sobald die Auswertung zu späteren Zeitstempeln weiterzieht. Der Beitrag von AuthZed über die SpiceDB-Version davon (2023-05-10) formuliert dieselbe Idee: “For any given problem or sub-problem, at a specified time, the result to the check is immutable” (Für jedes gegebene Problem oder Teilproblem ist das Ergebnis der Prüfung zu einem bestimmten Zeitpunkt unveränderlich), und “if we were to change the evaluation timestamp, the cache keys would change as well” (würden wir den Auswertungszeitstempel ändern, würden sich auch die Cache-Schlüssel ändern).
Zwei weitere Mechanismen aus §3.2.5 umgeben diesen Cache, und beide sind auf der Architekturseite gezeichnet: die Cache-Bäume, die durch Caching “at both the caller and the callee of internal RPCs” (sowohl beim Aufrufer als auch beim Aufgerufenen interner RPCs) entstehen, und die Sperrtabelle, bei der “Among requests sharing the same cache key only one request will begin processing; the rest block until the cache is populated.” (von den Anfragen, die denselben Cache-Schlüssel teilen, nur eine mit der Verarbeitung beginnt; die übrigen blockieren, bis der Cache gefüllt ist.)
In Produkten:
- SpiceDB rundet Revisionen in Fenster, die durch
--datastore-revision-quantization-intervalfestgelegt werden, Standard5s(dsconfig/config.go, v1.57.1), und umhüllt seinen Dispatcher mit einersingleflight-Schicht, die “dispatch requests that were single flighted” (Dispatch-Anfragen, die per Single-Flight zusammengefasst wurden) zählt und damit die Rolle der Sperrtabelle spielt. - Der Check-Cache von OpenFGA ist standardmäßig ausgeschaltet (
checkQueryCache.enabledistfalse, TTL10s, wenn eingeschaltet) (Konfiguration). Seine Einträge laufen nach einer TTL ab, statt zu einem Snapshot zu gehören; deshalb braucht OpenFGA einen ModusHIGHER_CONSISTENCY, um ihn zu umgehen (Konsistenz; siehe Reihenfolge ohne TrueTime).
Lesevorgänge werden pro Prüfung gebündelt
Die Blätter ②, ④a, ④b und ⑥ lesen alle Zeilen von doc:readme. Statt jeden Lesevorgang einzeln zu senden, gilt: “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) (Wir wenden einen Pooling-Mechanismus an, um Lesevorgänge für dieselbe ACL-Prüfung zu gruppieren und so die Zahl der Lese-RPCs an Spanner zu minimieren). Über diesen Satz hinaus beschreibt das Paper den Mechanismus nicht. Die Architekturseite zeichnet die vier Lesevorgänge, wie sie sich auf einem Server treffen; die nach Objekt und Relation sortierte Speicheranordnung (§3.1.1) ist es, die daraus Bereichs-Lesevorgänge über benachbarte Zeilen machen kann.
Wie tief es gehen kann
Die Rekursion in CHECK(U, U′) hat keine eingebaute Grenze: Eine Gruppe kann eine Gruppe enthalten, die eine Gruppe enthält, und nichts im Datenmodell verbietet einen Zyklus. Was tut eine Prüfung, wenn sie auf einen trifft?
Das Paper legt keine Zahl fest. Tiefe und breite Verschachtelung behandelt es mit Leopard für “selected namespaces that exhibit such structure” (§3.2.4; siehe die Leopard-Seite) (ausgewählte Namespaces, die eine solche Struktur aufweisen), und §5 beansprucht “safe pointer chasing despite potentially deep recursion (e.g. membership checks on hierarchical groups)” (sichere Zeigerverfolgung trotz potenziell tiefer Rekursion, z. B. Mitgliedschaftsprüfungen auf hierarchischen Gruppen), ohne darüber hinaus zu sagen, was sie sicher macht. Die Limits pro Client aus §3.2.6 begrenzen CPU und ausstehende RPCs, nicht die Tiefe. Produkte wählen explizite Limits:
| System | Limit | Standard | Wenn erreicht | Quelle |
|---|---|---|---|---|
| Paper | keines genannt | keiner | nicht beschrieben | §3.2.4, §5 |
| SpiceDB | --dispatch-max-depth |
50 | Fehler: “the check request has exceeded the allowable maximum depth of 50” | Cyclical relationships and traversal limits, serve.go |
| OpenFGA | resolveNodeLimit |
25 | Fehler; Zyklen werden vorher erkannt und mit „nicht erlaubt“ beantwortet | Konfiguration, check.go |
| OpenFGA | resolveNodeBreadthLimit |
10 | begrenzt, “how many nodes on a given level can be evaluated concurrently” (wie viele Knoten auf einer Ebene gleichzeitig ausgewertet werden können) | Konfiguration |
| Ory Keto | limit.max_read_depth |
5 | das globale Maximum; eine Anfrage kann es nur senken | config.schema.json |
Laut Dokumentation hat SpiceDB keinen separaten Zykluserkenner: Ein Zyklus läuft, bis er das Tiefenlimit erreicht, und gibt denselben Fehler zurück wie eine sehr tiefe Hierarchie; die Dokumentation erklärt, dass auf das Verfolgen besuchter Objekte aus Gründen der Semantik und der Performance verzichtet wurde (Rekursion und maximale Tiefe). Der LocalChecker von OpenFGA führt pro Anfrage eine Menge besuchter Tupelschlüssel und gibt „nicht erlaubt“ mit CycleDetected zurück, wenn sich einer wiederholt (check.go, hasCycle). Beide Limits zählen Schritte entlang eines Pfads, also die Tiefe des Baums in der ersten Abbildung; resolveNodeBreadthLimit ist als einziges dieser Limits eine Grenze für das “evaluate all leaf nodes … concurrently” (alle Blattknoten … gleichzeitig auswerten) des Papers.
Quellen
- 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 (Hersteller-Blog).
- AuthZed, Check it out #2: How intersections and exclusions are computed in SpiceDB and Authzed, 2022-03-03 (Hersteller-Blog).
- AuthZed, Hotspot Caching in Google Zanzibar and SpiceDB, 2023-05-10 (Hersteller-Blog).
- AuthZed, Cyclical Relationships and Traversal Limits, SpiceDB-Dokumentation.
- SpiceDB-Quellcode v1.57.1:
pkg/cmd/serve.go,pkg/cmd/datastore/dsconfig/config.go,internal/dispatch/singleflight/singleflight.go. - OpenFGA, Configuring OpenFGA und Query Consistency Modes.
- OpenFGA-Quellcode v1.22.1:
internal/graph/check.go. - Ory Keto,
.schema/config.schema.json(limit.max_read_depth).