guide:check@de

Leitfäden

Ein Check von innen

Wie Zanzibar einen Check in einen Baum von Teilproblemen verwandelt, die Blätter gleichzeitig auswertet, früh abbricht, das Gelernte zu einem Snapshot cacht, und was Produkte hinzufügen, das im Paper fehlt, etwa Tiefenlimits.

Fakten geprüft am Abschnitte im Paper §3.2.3, §3.2.4, §3.2.5

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?“?

Der Baum der Teilprobleme für einen Check1: doc:readme#viewer, ein ODER-Knoten, hat drei Kinder. 2: _this, die viewer-Tupel des Readmes. 3: editor, ein ODER-Knoten mit zwei Kindern, 4a: die editor-Tupel des Readmes, und 4b: owner, die owner-Tupel des Readmes. 5: tuple_to_userset über parent; 6 liest die parent-Tupel des Readmes und findet folder:A, dann fragt 7, ob Chen in folder:A#viewer ist. Schritt 7 ist wahr, und der hervorgehobene Pfad 1, 5, 6, 7 antwortet mit Ja.① doc:readme#viewerODER② _thisviewer-Tupel③ editorODER⑤ tuple_to_usersetparent → viewer④a _thiseditor-Tupel④b ownerowner-Tupel⑥ readme#parent lesen→ folder:A⑦ folder:A#viewer@user:chen: wahrneue Teilprüfung
Check(user:chen, viewer, doc:readme). Gestrichelte Kästen sind Operatoren, einfache Kästen sind Tupel-Lesevorgänge. Nur Zweig ⑤ erreicht Chen.

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?

Blätter laufen gleichzeitig; ein entschiedenes ODER bricht den Rest abZu Beginn startet die Wurzel alle Blätter gleichzeitig: die viewer-Tupel des Readmes, seine editor- und owner-Tupel und seine parent-Tupel. Die viewer-Tupel kommen ohne Chen zurück, also ist dieses Blatt falsch. Der parent-Lesevorgang findet folder:A, und eine Teilprüfung auf folder:A#viewer wird gesendet. Bevor die editor- und owner-Lesevorgänge fertig sind, gibt die Ordner-Teilprüfung wahr zurück. Das ODER an der Wurzel ist nun als wahr entschieden, antwortet und bricht die editor- und owner-Lesevorgänge ab.Zeit① viewer (ODER)② viewer-Tupel③④ editor, owner⑤⑥⑦ Elternordnerfalschwahrabbrechenalle Blätter startenTupel lesenTupel lesenparent lesenkein Chen: falschfolder:A →Teilprüfungliest nochChen istviewer: wahrentschieden: wahrabgebrochen
Ein wahres Kind entscheidet ein ODER. Die falsche Antwort von ② ändert nichts; die wahre Antwort von ⑦ beendet den ganzen Baum.

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?

Vereinigung endet beim ersten WahrEin Vereinigungsknoten mit den Kindern A und B. B antwortet zuerst mit wahr, was die Vereinigung als wahr entscheidet, also wird A abgebrochen.A ∪ BA: läuft→ abgebrochenB: wahrentscheidet
Vereinigung: Ein Wahr genügt. Falsch braucht jedes Kind.
Schnittmenge endet beim ersten FalschEin Schnittmengenknoten mit den Kindern A und B. B antwortet zuerst mit falsch, was die Schnittmenge als falsch entscheidet, also wird A abgebrochen.A ∩ BA: läuft→ abgebrochenB: falschentscheidet
Schnittmenge: Ein Falsch genügt. Wahr braucht jedes Kind.
Ausschluss endet bei falscher Basis oder wahrem AusgeschlossenemEin Ausschlussknoten, A minus B. Die ausgeschlossene Seite B antwortet zuerst mit wahr, was den Ausschluss als falsch entscheidet, also wird die Basis A abgebrochen. Eine falsche Basis würde ihn ebenfalls entscheiden.A − BA (Basis):läuft→ abgebrochenB (ausgeschl.):wahrentscheidet
Ausschluss: Eine falsche Basis oder eine wahre ausgeschlossene Seite genügt. Wahr braucht beide Antworten.

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?

Teilergebnisse werden pro Snapshot gecachtEine Prüfung für Chen auf dem Readme, ausgewertet bei T=13 s, speichert das Teilergebnis folder:A#viewer@user:chen bei 13 s, wahr. Eine zweite Prüfung im selben Fenster, ebenfalls auf 13 s gerundet, trifft diesen Eintrag. Eine dritte Prüfung, ausgewertet nach der nächsten Grenze bei T=14 s, verwendet einen anderen Schlüssel, verfehlt den Cache und liest die folder-Tupel erneut aus Spanner.Chens PrüfungT = 13 sgleiche Prüfung,0,4 s späterT = 13 sgleiche Prüfung,1,2 s späterT = 14 sSchlüssel: folder:A#viewer@user:chen @ 13 s= wahrSchlüssel: … @ 14 s(noch nicht gecacht)folder-Tupel(Spanner)füllenTrefferFehltrefferlesen bei 14 s
Der Eintrag für 13 s wird nie invalidiert und nie bei 14 s wiederverwendet. Die Zeitstempel dienen der Veranschaulichung.

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-interval festgelegt werden, Standard 5s (dsconfig/config.go, v1.57.1), und umhüllt seinen Dispatcher mit einer singleflight-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.enabled ist false, TTL 10s, wenn eingeschaltet) (Konfiguration). Seine Einträge laufen nach einer TTL ab, statt zu einem Snapshot zu gehören; deshalb braucht OpenFGA einen Modus HIGHER_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?

Ein Zyklus in verschachtelten GruppenEine hypothetische Fehlkonfiguration: group:all#member enthält group:eng#member, und group:eng#member enthält group:all#member. Eine Prüfung für Anne auf doc:readme#viewer erreicht group:eng#member, dann group:all#member, dann wieder group:eng#member und so weiter. SpiceDB dispatcht weiter bis zum Tiefenlimit von 50 und gibt einen Fehler zurück. OpenFGA merkt sich die besuchten Tupelschlüssel, erkennt die Wiederholung und behandelt den Zweig als nicht erlaubt; unabhängig davon gibt es bei einer Tiefe von 25 einen Fehler zurück.doc:readme#viewergroup:eng#membergroup:all#memberSpiceDB: Schritt 50→ FehlerOpenFGA: Schlüsselschon gesehen → Zyklus,nicht erlaubtSchritt 1Schritt 2, 3, 4 …
Die beiden Gruppentupel sind hypothetisch und nicht Teil des durchgehenden Beispiels. Die Pfeile folgen der Richtung, in der die Prüfung sucht.

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