Zanzibar beantwortet einen Check normalerweise, indem es Tupeln vom Objekt zum Benutzer folgt, ein Nachschlagen nach dem anderen. Für die meisten Daten ist das schnell. Für Gruppen, die über viele Ebenen verschachtelt sind, ist es das nicht, und Zanzibar übergibt solche Prüfungen an Leopard, einen Index, der die Verschachtelung vorab berechnet.
Warum Verschachtelung langsam ist
Erweitern wir das durchgehende Beispiel. group:eng liegt nun in group:product, das in group:all liegt, und das Readme ist mit ganz group:all geteilt. Wie viele Nachschlagevorgänge braucht es, um herauszufinden, dass Beto das Readme sehen kann?
Die Tupel hinter der Abbildung sind:
doc:readme#viewer@group:all#member
group:all#member@group:product#member
group:product#member@group:eng#member
group:eng#member@user:beto
Schritt n kann erst beginnen, wenn Schritt n − 1 ein Ergebnis geliefert hat. Das Paper nennt das Zeigerverfolgung (pointer chasing) und sagt, sie “can be expensive when indirect ACLs or groups are deep or wide” (§3.2.3) (kann teuer werden, wenn indirekte ACLs oder Gruppen tief oder breit sind). Breite schadet ebenfalls: Enthielte group:all hundert Untergruppen, würde sich Schritt 2 hundertfach verzweigen. Daher: “Recursive pointer chasing during check evaluation has difficulty maintaining low latency with groups that are deeply nested or have a large number of child groups. For selected namespaces that exhibit such structure, Zanzibar handles checks using Leopard, a specialized index that supports efficient set computation.” (§3.2.4) (Rekursive Zeigerverfolgung während der Check-Auswertung hat Mühe, bei tief verschachtelten Gruppen oder Gruppen mit sehr vielen Untergruppen eine niedrige Latenz zu halten. Für ausgewählte Namespaces, die eine solche Struktur aufweisen, behandelt Zanzibar Prüfungen mit Leopard, einem spezialisierten Index, der effiziente Mengenberechnungen unterstützt.)
Zwei Arten von Mengen
Leopard speichert “a collection of named sets using (T, s, e) tuples, where T is an enum representing the set type and s and e are 64-bit integers representing the set ID and the element ID” (§3.2.4) (eine Sammlung benannter Mengen mithilfe von Tupeln (T, s, e), wobei T ein Enum ist, das den Mengentyp darstellt, und s und e 64-Bit-Ganzzahlen sind, die die Mengen-ID und die Element-ID darstellen). Gruppenmitgliedschaft verwendet zwei Mengentypen:
GROUP2GROUP(s): die Gruppen, die “directly or indirectly” (direkt oder indirekt) Untergruppen der Vorfahrengruppe s sind.MEMBER2GROUP(s): die Gruppen, in denen Benutzer s “direct” (direktes) Mitglied ist.
Was enthalten die Mengen im Beispiel?
Beachten Sie die Asymmetrie. Die gesamte Verschachtelung steckt in GROUP2GROUP, sodass die Seite eines Benutzers nur festhalten muss, wo der Benutzer direkt hinzugefügt wurde. In den Worten des Papers: “Flattening group-to-group paths allows reachability to be efficently evaluated by Leopard” (§3.2.4) (Das Abflachen von Gruppe-zu-Gruppe-Pfaden erlaubt es Leopard, die Erreichbarkeit effizient auszuwerten).
Mitgliedschaft ist eine nicht leere Schnittmenge
“To evaluate whether user U is a member of group G, we check whether” (§3.2.4) (Um auszuwerten, ob Benutzer U Mitglied der Gruppe G ist, prüfen wir, ob)
(MEMBER2GROUP(U) ∩ GROUP2GROUP(G)) ≠ ∅
Das heißt: Liegt irgendeine Gruppe, zu der der Benutzer direkt hinzugefügt wurde, auch irgendwo unter G? Was ergibt das für Beto und Anne gegenüber group:all?
Aus den vier aufeinanderfolgenden Lesevorgängen der ersten Abbildung wurden zwei Mengen-Lookups und eine Schnittmenge. Um die ursprüngliche Frage zu beantworten, liest Zanzibar weiterhin das Tupel des Readmes, das group:all#member nennt; die Tiefe darunter ist das, was Leopard beseitigt. Das Paper schlüsselt nicht auf, wie ein Check zwischen gewöhnlicher Auswertung und Leopard-Abfragen aufgeteilt wird; diese Aufteilung ist also eine Lesart von §3.2.4, kein Zitat.
Schnittmenge auf sortierten Listen
Wie günstig ist die Schnittmenge? “Index tuples are stored as ordered lists of integers in a structure such as a skip list, thus allowing for efficient union and intersections among sets. For example, evaluating the intersection between two sets, A and B, requires only O(min(|A|, |B|)) skip-list seeks.” (§3.2.4) (Indextupel werden als geordnete Listen von Ganzzahlen in einer Struktur wie einer Skip-Liste gespeichert, was effiziente Vereinigungen und Schnittmengen zwischen Mengen erlaubt. Zum Beispiel erfordert die Auswertung der Schnittmenge zweier Mengen A und B nur O(min(|A|, |B|)) Skip-Listen-Suchschritte.)
Die Arbeit richtet sich nach der kürzeren Liste. Ist ein Benutzer direktes Mitglied nur weniger Gruppen, ist MEMBER2GROUP(U) kurz, und der Test bleibt günstig, auch wenn GROUP2GROUP(G) riesig ist. Das Paper nennt keine Mengengrößen; dieser Fall ist eine Annahme. Der Index “is sharded by element IDs” (ist nach Element-IDs geshardet), und Shards “are usually served entirely from memory” (§3.2.4) (werden meist vollständig aus dem Arbeitsspeicher bedient).
Drei Teile
“The Leopard system consists of three discrete parts: a serving system capable of consistent and low-latency operations across sets; an offline, periodic index building system; and an online real-time layer capable of continuously updating the serving system as tuple changes occur.” (§3.2.4) (Das Leopard-System besteht aus drei getrennten Teilen: einem Serving-System, das konsistente Operationen mit niedriger Latenz über Mengen ausführen kann; einem periodischen Offline-System zum Aufbau des Index; und einer Online-Echtzeitschicht, die das Serving-System fortlaufend aktualisieren kann, während Tupeländerungen auftreten.) Wie hängen sie zusammen?
- Offline-Index-Builder. Er “generates index shards from a snapshot of Zanzibar relation tuples and configs, and replicates the shards globally. It respects userset rewrite rules and recursively expands edges in an ACL graph to form Leopard index tuples.” (erzeugt Index-Shards aus einem Snapshot von Zanzibar-Relationstupeln und -Konfigurationen und repliziert die Shards global. Er respektiert Userset-Umschreibregeln und expandiert Kanten in einem ACL-Graphen rekursiv, um Leopard-Indextupel zu bilden.) Server “swap old shards with new ones when they become available” (tauschen alte Shards gegen neue aus, sobald diese verfügbar werden).
- Inkrementelle Schicht. Der Offline-Index allein “cannot do so at a fresh and consistent snapshot” (kann das nicht auf einem aktuellen und konsistenten Snapshot leisten), daher halten Server “an incremental layer that indexes all updates since the offline snapshot” (eine inkrementelle Schicht, die alle Aktualisierungen seit dem Offline-Snapshot indexiert), jede Aktualisierung ein Tupel
(T, s, e, t, d), “where t is the timestamp of the update and d is a deletion marker” (wobei t der Zeitstempel der Aktualisierung und d eine Löschmarkierung ist). “Updates with timestamps less than or equal to the query timestamp are merged on top of the offline index during query processing.” (Aktualisierungen mit Zeitstempeln kleiner oder gleich dem Abfragezeitstempel werden während der Abfrageverarbeitung über den Offline-Index gelegt.) - Einspeisung. “the Leopard incremental indexer calls Zanzibar’s Watch API to receive a temporally ordered stream of Zanzibar tuple modifications and transforms the updates into a temporally ordered stream of Leopard tuple additions, updates, and deletions.” (der inkrementelle Indexer von Leopard ruft die Watch-API von Zanzibar auf, um einen zeitlich geordneten Stream von Zanzibar-Tupeländerungen zu empfangen, und wandelt die Aktualisierungen in einen zeitlich geordneten Stream von Hinzufügungen, Aktualisierungen und Löschungen von Leopard-Tupeln um.)
Alle Zitate in dieser Liste stammen aus §3.2.4. Weil Aktualisierungen Zeitstempel tragen und bis zum Abfragezeitstempel zusammengeführt werden, kann eine Leopard-Antwort denselben Snapshot widerspiegeln wie der Rest des Checks; der vom Paper genannte Zweck der inkrementellen Schicht ist “To support consistent ACL evaluation” (konsistente ACL-Auswertung zu unterstützen).
Der Preis: ein Schreibvorgang, viele Indexaktualisierungen
Das Abflachen wird beim Schreiben bezahlt. Gehen Sie zurück zu der Zeit, bevor eng zu product hinzugefügt wurde, und nehmen Sie an, dass group:eng selbst zwei Untergruppen hat, group:infra und group:web. Nun fügt jemand eng zu product hinzu. Wie viele Indextupel ändern sich?
Die Anzahl ist die Zahl der Vorfahren auf der einen Seite mal die Zahl der Nachfahren auf der anderen, wächst also mit Tiefe und Breite. Um sie zu berechnen, gilt: “Generating updates for the GROUP2GROUP tuples requires the incremental indexer to maintain group-to-group membership for denormalizing the effects of a relation tuple update to potentially multiple index updates.” (Das Erzeugen von Aktualisierungen für die GROUP2GROUP-Tupel erfordert, dass der inkrementelle Indexer Gruppe-zu-Gruppe-Mitgliedschaften pflegt, um die Auswirkungen einer Relationstupel-Aktualisierung auf potenziell mehrere Indexaktualisierungen zu denormalisieren.) Im Maßstab von Google: “In practice, a single Zanzibar tuple addition or deletion may yield potentially tens of thousands of discrete Leopard tuple events.” (§3.2.4) (In der Praxis kann ein einziges Hinzufügen oder Löschen eines Zanzibar-Tupels potenziell Zehntausende einzelner Leopard-Tupelereignisse erzeugen.)
Das Löschen ist heikler, als die Abbildung zeigt: Ein Indextupel darf nur entfernt werden, wenn kein anderer Pfad die beiden Gruppen noch verbindet. Das Paper beschreibt nicht, wie der Indexer das entscheidet.
Deshalb ist Leopard auch die Ausnahme. Anderswo “Zanzibar avoids storage denormalization and relies only on normalized data (except for the cases described in §3.2.4)” (§3.2.5) (vermeidet Zanzibar Denormalisierung im Speicher und stützt sich nur auf normalisierte Daten (mit Ausnahme der in §3.2.4 beschriebenen Fälle)), und Leopard wird nur für ausgewählte Namespaces verwendet, “that exhibit such structure” (§3.2.4) (die eine solche Struktur aufweisen).
Im Produktivbetrieb
Aus §4.4, über 7 Tage: “The Leopard index is performing 1.56M QPS at the median, or 2.22M QPS at the 99th percentile” (Der Leopard-Index verarbeitet 1,56 Mio. QPS im Median bzw. 2,22 Mio. QPS im 99. Perzentil), und “Leopard servers respond in fewer than 150 μsec at the median, or under 1 msec at the 99th percentile.” (Leopard-Server antworten im Median in weniger als 150 μs bzw. im 99. Perzentil in unter 1 ms.) Die inkrementelle Schicht “writes roughly 500 index updates per second at the median, and approximately 1.5K updates per second at the 99th percentile.” (schreibt im Median etwa 500 Indexaktualisierungen pro Sekunde und im 99. Perzentil etwa 1.500 Aktualisierungen pro Sekunde.) Aufrufe an Leopard werden wie Aufrufe an Spanner gehedgt (§3.2.7).
Quellen
- Pang et al., “Zanzibar: Google’s Consistent, Global Authorization System”, USENIX ATC ’19, §3.2.3, §3.2.4, §3.2.5, §3.2.7, §4.4: https://www.usenix.org/conference/atc19/presentation/pang