Zanzibar speichert Berechtigungen als Relationstupel: ein Fakt pro Zeile, gelesen als „dieser Benutzer hat diese Relation zu diesem Objekt“. Alles Weitere auf dieser Seite, Umschreibregeln, Check und Expand, wird aus diesen Zeilen berechnet.
Das durchgehende Beispiel: Anne, Beto und Chen (user:anne, user:beto, user:chen); das Dokument doc:readme in folder:A; die Gruppe group:eng. Anne ist Eigentümerin des Readmes, Beto ist in eng, die Mitglieder von eng sehen das Readme, und Chen sieht Ordner A.
Die Grammatik
Das Paper (§2.1) gibt die Textnotation in vier Regeln an:
⟨tuple⟩ ::= ⟨object⟩ ‘#’ ⟨relation⟩ ‘@’ ⟨user⟩
⟨object⟩ ::= ⟨namespace⟩ ‘:’ ⟨object_id⟩
⟨user⟩ ::= ⟨user_id⟩ | ⟨userset⟩
⟨userset⟩ ::= ⟨object⟩ ‘#’ ⟨relation⟩
Ein Tupel hat drei Teile. Das Objekt ist ein Namespace plus eine ID, etwa doc:readme. Die Relation ist ein Name, den der Namespace definiert, etwa owner oder viewer. Der Benutzer ist entweder eine einzelne Benutzer-ID oder ein Userset. Im Paper ist eine Benutzer-ID eine ganze Zahl; diese Website schreibt user:anne, damit das Beispiel lesbar bleibt.
Was sagt ein einzelnes Tupel aus?
Es sagt genau eines: Anne hat die Relation owner zu doc:readme. Das Paper nennt die Primärschlüssel, die ein Tupel identifizieren: Namespace, Objekt-ID, Relation und Benutzer.
Usersets: ein Tupel, das auf eine Gruppe zeigt
Die vierte Grammatikregel ist die interessante. Ein Userset ist selbst ein Objekt plus eine Relation: group:eng#member bedeutet „jeder Benutzer, der die Relation member zu group:eng hat“. Ist der Benutzer eines Tupels ein Userset, gewährt eine einzige Zeile einer ganzen Menge von Benutzern etwas, und diese Menge wird durch andere Zeilen definiert.
Wie gibt ein einziges Tupel jedem Mitglied von eng Zugriff auf das Readme?
Keine Zeile nennt Beto und das Readme zusammen. Beto ist Betrachter, weil er in der Menge ist, auf die das zweite Tupel zeigt. Fügt man eng ein Mitglied hinzu, kann dieses Mitglied das Readme sehen, ohne dass sich die ACL des Readmes ändert.
Derselbe Kniff lässt sich verschachteln. Ein Mitglied einer Gruppe kann ein weiteres Userset sein, zum Beispiel group:eng#member@group:sre#member (ein hypothetisches Unterteam, nicht Teil des durchgehenden Beispiels), und die Mitgliedschaft reicht dann über so viele Ebenen, wie die Tupel beschreiben. Das Paper fasst es in einem Satz: “a ⟨userset⟩ allows ACLs to refer to groups and thus supports representing nested group membership” (§2.1) (ein ⟨userset⟩ erlaubt es ACLs, auf Gruppen zu verweisen, und unterstützt damit die Darstellung verschachtelter Gruppenmitgliedschaften). Es erklärt auch den Gewinn: Die Modellierung mit Tupeln statt mit ACLs pro Objekt “allows us to unify the concepts of ACLs and groups” (§2.1) (erlaubt es uns, die Konzepte von ACLs und Gruppen zu vereinheitlichen). Eine Gruppe ist nur ein Objekt, dessen Relation member eine ACL ist.
Tabelle 1 als ein Graph
Tabelle 1 des Papers listet vier Beispieltupel. Mit den Benutzern 10 und 11 umbenannt in Anne und Beto und einem zusätzlichen Tupel für Chen lauten sie:
| Tupel | Gelesen als |
|---|---|
doc:readme#owner@user:anne |
Anne ist eine Eigentümerin des Readmes |
group:eng#member@user:beto |
Beto ist ein Mitglied von eng |
doc:readme#viewer@group:eng#member |
Mitglieder von eng sind Betrachter des Readmes |
doc:readme#parent@folder:A#... |
Das Readme liegt in Ordner A |
folder:A#viewer@user:chen |
Chen ist ein Betrachter von Ordner A (nicht in Tabelle 1) |
Das #... in der vierten Zeile ist die Notation des Papers für “a relation that does not affect the semantics of the tuple” (Bildunterschrift von Tabelle 1) (eine Relation, die die Semantik des Tupels nicht beeinflusst): Das Tupel zeigt auf den Ordner selbst, nicht auf eine Menge seiner Benutzer.
Wie sehen alle fünf Zeilen zusammen aus?
Die Kante parent sagt nichts über Zugriff aus. Wie das Paper schreibt, definieren manche Relationen “only define abstract relations between objects. These abstract relations may indirectly affect access control given userset rewrite rules specified in namespace configs” (§2.1) (lediglich abstrakte Relationen zwischen Objekten. Diese abstrakten Relationen können die Zugriffskontrolle indirekt beeinflussen, sofern in Namespace-Konfigurationen Userset-Umschreibregeln spezifiziert sind). Ob Chen das Readme sehen kann, hängt von einer solchen Regel ab, und darum geht es im nächsten Abschnitt.
Namespace-Konfiguration
Bevor ein Client Tupel speichert, konfiguriert er einen Namespace wie doc oder folder (§2.3). Die Konfiguration listet die Relationen des Namespace auf, jede mit einem Namen und einer Relationskonfiguration, dazu Speicherparameter: Sharding-Einstellungen und eine Kodierung für Objekt-IDs.
Tupel allein definieren die effektive ACL nicht. Viele Clients wollen, dass jeder Bearbeiter auch Betrachter ist. Für jeden Bearbeiter jedes Objekts ein zusätzliches Tupel viewer zu speichern, wäre nach den Worten des Papers “wasteful and make it hard to make modifications across all objects” (§2.3.1) (verschwenderisch und würde Änderungen über alle Objekte hinweg erschweren). Stattdessen kann eine Relationskonfiguration eine Userset-Umschreibregel tragen: eine Funktion, die eine Objekt-ID nimmt und einen Userset-Ausdrucksbaum zurückgibt.
Dies ist Abbildung 1 des Papers, wörtlich:
name: "doc"
relation { name: "owner" }
relation {
name: "editor"
userset_rewrite {
union {
child { _this {} }
child { computed_userset { relation: "owner" } }
} } }
relation {
name: "viewer"
userset_rewrite {
union {
child { _this {} }
child { computed_userset { relation: "editor" } }
child { tuple_to_userset {
tupleset { relation: "parent" }
computed_userset {
object: $TUPLE_USERSET_OBJECT # parent folder
relation: "viewer"
} } }
} } }
Figure 1: Simple namespace configuration with concentric relations on documents. All owners are editors, and all editors are viewers. Further, viewers of the parent folder are also viewers of the document.
(Abbildung 1: Einfache Namespace-Konfiguration mit konzentrischen Relationen auf Dokumenten. Alle Eigentümer sind Bearbeiter, und alle Bearbeiter sind Betrachter. Darüber hinaus sind Betrachter des übergeordneten Ordners auch Betrachter des Dokuments.)
Die Blätter eines Umschreibbaums gibt es in drei Arten (§2.3.1):
| Blatt | Was es zurückgibt | In Abbildung 1 |
|---|---|---|
_this |
Die Benutzer in gespeicherten Tupeln für dieses Objekt und diese Relation, einschließlich der Usersets, auf die diese Tupel zeigen. Der Standard, wenn eine Relation keine Regel hat. | Die auf doc:readme gespeicherten Tupel viewer |
computed_userset |
Das Userset einer anderen Relation auf demselben Objekt. | editor auf demselben Dokument; für editor ist es owner |
tuple_to_userset |
Liest eine Tupelmenge vom Objekt und berechnet dann aus jedem gefundenen Tupel ein Userset. | Die Tupel parent des Dokuments lesen, dann viewer auf jedem übergeordneten Ordner nehmen |
Blätter werden mit Vereinigung, Schnittmenge und Ausschluss kombiniert (§2.3.1). Abbildung 1 verwendet nur die Vereinigung. Eine Schnittmenge würde verlangen, dass ein Benutzer in jedem Kind enthalten ist, zum Beispiel „Bearbeiter, die auch in eng sind“; ein Ausschluss würde eine Menge entfernen, zum Beispiel „Betrachter außer einer Sperrliste“. Diese beiden Beispiele dienen der Veranschaulichung und stammen nicht aus dem Paper.
Welchen Baum baut die Regel viewer für ein Dokument?
owner liegt zwei Ebenen tiefer: Eigentümer sind Bearbeiter, Bearbeiter sind Betrachter. Das meint die Bildunterschrift von Abbildung 1 mit “concentric relations” (konzentrischen Relationen). Der rechte Zweig ist der einzige, der das Dokument verlässt: Er folgt einer gespeicherten Kante parent zu einem anderen Objekt.
Check als Graphsuche
Eine Check-Anfrage nennt ein Userset ⟨object#relation⟩ und einen Benutzer und fragt, ob der Benutzer darin enthalten ist (§2.4.4). Ohne Umschreibregeln schreibt das Paper die Auswertung als rekursive Formel (§3.2.3): Der Benutzer ist in ⟨object#relation⟩, wenn ein Tupel ⟨object#relation@U⟩ existiert oder wenn ein Tupel ⟨object#relation@U′⟩ existiert, wobei U′ ein Userset ist und der Benutzer in U′ enthalten ist. Das Paper nennt diese Rekursion “pointer chasing” (Zeigerverfolgung). Umschreibregeln “are also translated to boolean expressions as part of check evaluation” (§3.2.3) (werden im Rahmen der Check-Auswertung ebenfalls in boolesche Ausdrücke übersetzt), sodass der Ausdrucksbaum oben zu einem ODER aus drei Zweigen wird.
Die Frage für die nächsten vier Abbildungen: Kann Chen doc:readme sehen? Jedes Bild verwendet denselben Graphen und hebt die Kanten hervor, die der aktuelle Zweig liest. Die Namespace-Konfiguration für folder steht nicht im Paper; diese Bilder nehmen an, dass folder#viewer keine Umschreibregel hat, also nur _this ist.
Schritt 1: _this
Enthält ein auf dem Readme gespeichertes Tupel viewer Chen?
Der einzige gespeicherte Betrachter ist ein Userset, also steigt Check rekursiv in group:eng#member ab. Dessen einziges Mitglied ist Beto. Dieser Zweig sagt nein.
Schritt 2: computed_userset editor, dann owner
Ist Chen Bearbeiter oder Eigentümer?
Die Umschreibung geht von viewer zu editor zu owner auf demselben Objekt. Für die ersten beiden Schritte ist kein gespeichertes Tupel nötig: Sie stammen aus der Konfiguration. Die einzige Eigentümerin ist Anne, also sagt auch dieser Zweig nein.
Schritt 3: tuple_to_userset, den übergeordneten Ordner finden
In welchem Ordner liegt das Readme?
Das Tupel parent ist die „abstrakte Relation“ aus Tabelle 1. Für sich gewährt es nichts; die Umschreibregel macht daraus eine neue Frage zu einem anderen Objekt.
Schritt 4: folder:A#viewer
Ist Chen ein Betrachter von Ordner A?
Der Pfad user:chen → folder:A → doc:readme beantwortet die Frage. Die Kanten zeigen in jedem Bild in dieselbe Richtung, die Suche lief aber vom Readme nach außen: Check beginnt bei ⟨object#relation⟩ und sucht den Benutzer.
Eine solche Zeigerverfolgung “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) (funktioniert gut für die meisten Arten von ACLs und Gruppen, kann aber teuer werden, wenn indirekte ACLs oder Gruppen tief oder breit sind). Für solche Namespaces verwendet Zanzibar den Leopard-Index, beschrieben auf der Leopard-Seite.
Read und Expand
Zwei API-Aufrufe betrachten dieselben Daten aus unterschiedlicher Höhe.
Read (§2.4.1) gibt nur gespeicherte Tupel zurück. Eine Anfrage nennt eine oder mehrere Tupelmengen: einen einzelnen Tupelschlüssel oder alle Tupel für eine Objekt-ID oder ein Userset in einem Namespace, optional auf eine Relation eingeschränkt. Das Paper sagt ausdrücklich: “Read results only depend on contents of relation tuples and do not reflect userset rewrite rules” (§2.4.1) (Read-Ergebnisse hängen nur vom Inhalt der Relationstupel ab und spiegeln keine Userset-Umschreibregeln wider). Ein Read von doc:readme mit der Relation viewer gibt im durchgehenden Beispiel eine Zeile zurück:
doc:readme#viewer@group:eng#member
Anne fehlt, obwohl jeder Eigentümer Betrachter ist, und Chen fehlt, obwohl er das Readme sehen kann.
Expand (§2.4.5) “follows indirect references expressed through userset rewrite rules” (folgt indirekten Verweisen, die durch Userset-Umschreibregeln ausgedrückt werden). Es gibt einen Userset-Baum zurück: Blätter sind Benutzer-IDs oder Usersets, die auf andere Paare ⟨object#relation⟩ zeigen, und innere Knoten sind Vereinigung, Schnittmenge oder Ausschluss.
Was gibt Expand für doc:readme#viewer zurück?
Beachten Sie die beiden gestrichelten Blätter. Nach §2.4.5 kann ein Blatt ein Userset sein, das auf anderes verweist; ein Client, der jede einzelne Person (Beto, Chen) will, expandiert diese Blätter seinerseits. Das Paper sagt nicht, wie tief ein einzelner Expand-Aufruf rekursiv absteigt; diese Abbildung endet bei den Usersets, die die eigenen Regeln des Dokuments erreichen. Das Paper nennt den Anwendungsfall: Expand erlaubt es Clients, “reason about the complete set of users and groups that have access to their objects, which allows them to build efficient search indices for access-controlled content” (§2.4.5) (die vollständige Menge der Benutzer und Gruppen nachzuvollziehen, die Zugriff auf ihre Objekte haben, was es ihnen ermöglicht, effiziente Suchindizes für zugriffskontrollierte Inhalte aufzubauen).
Quellen
- Ruoming Pang et al., “Zanzibar: Google’s Consistent, Global Authorization System”, USENIX ATC ’19, usenix.org/conference/atc19/presentation/pang