Die Begriffe stehen in alphabetischer Reihenfolge ihrer englischen Bezeichnung, wie sie im Paper vorkommt; die deutsche Entsprechung steht in Klammern. Codenamen aus der Konfigurationssprache des Papers (_this, computed_userset, tuple_to_userset) sind ohne ihre Unterstriche einsortiert. Die Beispiele verwenden das durchgehende Beispiel: Anne, Beto und Chen; doc:readme in folder:A; group:eng.
A–C
- ACL
- Access Control List (Zugriffskontrollliste): die Menge der Benutzer, die mit einem Objekt etwas tun dürfen. In Zanzibar wird eine ACL nicht als eine Liste gespeichert, sondern als viele Relationstupel. Mehr: Zugriffskontrollmodelle, §1, §2.1.
- aclserver
- Der wichtigste Servertyp von Zanzibar. Beantwortet Check, Read, Expand und Write und fächert Arbeit auf andere aclserver in seinem Cluster auf. Mehr: Architektur, §3.
- at-least-as-fresh (mindestens so aktuell)
- Die Regel für einen zookie: Zanzibar darf auf jedem Snapshot auswerten, der nicht älter ist als der Zeitstempel des zookie, nicht nur auf genau diesem. Diese Freiheit erlaubt es, die meisten Anfragen aus lokalen Replikaten zu bedienen. Mehr: Konsistenz, §2.2.
- bounded staleness (begrenzte Veraltung)
- Ein Snapshot-Lesevorgang darf älter sein als „jetzt“, aber nicht älter als eine Grenze. In Zanzibar ist die Grenze der zookie, den der Client mitsendet. Spanner bietet dies direkt an: Der Client gibt eine Obergrenze für die Veraltung an, und Spanner wählt den Zeitstempel (Spanner-Paper, §4.1). Mehr: Konsistenz, §2.2.
- cache stampede
- Viele gleichzeitige Anfragen nach demselben nicht gecachten Ergebnis gehen alle auf einmal an den Speicher, bevor sich der Cache füllt. Zanzibar verhindert das mit einer Sperrtabelle. Das Paper zitiert für den Begriff den Wikipedia-Artikel (Referenz [3]). Mehr: Architektur, §3.2.5.
- changelog
- Eine Spanner-Datenbank, die die Historie der Tupelaktualisierungen enthält und in derselben Transaktion wie jeder Tupel-Schreibvorgang geschrieben wird. Watch liest daraus. Mehr: Architektur, §3.1.2.
- Check
- Der API-Aufruf, der fragt, ob ein Benutzer in einem Userset ⟨object#relation⟩ enthalten ist, zum Beispiel „ist Chen ein Betrachter von
doc:readme?“. Wird auf einem Snapshot ausgewertet, der nicht früher liegt als der angegebene zookie. Mehr: Relationstupel, §2.4.4, §3.2.3. computed_userset- Ein Blatt einer Umschreibregel, das das Userset einer anderen Relation auf demselben Objekt nimmt, zum Beispiel „jeder Bearbeiter ist ein Betrachter“. Mehr: Relationstupel, §2.3.1.
- consistent hashing (konsistentes Hashing)
- Ein Verfahren, Schlüssel so auf Server zu verteilen, dass das Hinzufügen oder Entfernen eines Servers nur einen kleinen Teil der Schlüssel verschiebt. Zanzibar verwendet es, um Cache-Einträge über die Server eines Clusters zu verteilen. Eingeführt von Karger et al. (STOC 1997) für Web-Caches. Mehr: Architektur, §3.2.5.
- content-change check (Content-Change-Prüfung)
- Ein Check, der gesendet wird, wenn ein Benutzer gerade neue Inhalte speichern will. Er trägt keinen zookie, wird auf dem neuesten Snapshot ausgewertet und gibt einen zookie zurück, den der Client mit der neuen Inhaltsversion speichert. Mehr: Konsistenz, §2.2, §2.4.4.
D–H
- denormalization (Denormalisierung)
- Eine vorberechnete Kopie abgeleiteter Daten speichern, etwa abgeflachte Gruppe-zu-Gruppe-Mitgliedschaften, statt sie aus den ursprünglichen Zeilen zu berechnen. Zanzibar vermeidet das im Speicher und verwendet es nur in Leopard. Mehr: Leopard, §3.2.4, §3.2.5.
- exclusion (Ausschluss)
- Ein Operator einer Umschreibregel: die Benutzer, die in einem Userset enthalten sind, aber nicht in einem anderen. Mehr: Relationstupel, §2.3.1.
- Expand
- Der API-Aufruf, der das effektive Userset von ⟨object#relation⟩ als Baum zurückgibt und dabei den Umschreibregeln folgt. Blätter sind Benutzer-IDs oder Usersets; innere Knoten sind Vereinigung, Schnittmenge oder Ausschluss. Mehr: Relationstupel, §2.4.5.
- external consistency (externe Konsistenz)
- Wenn Aktualisierung x vor Aktualisierung y geschieht, erhält x einen kleineren Zeitstempel als y, auch wenn die beiden außerhalb des Systems koordiniert werden. Zanzibar erhält diese Eigenschaft von Spanner. Das Paper zitiert für den Begriff Giffords Stanford-Dissertation von 1981 (Referenz [18]); Spanner formuliert sie so: Wenn T1 committet, bevor T2 beginnt, ist der Commit-Zeitstempel von T1 kleiner als der von T2. Mehr: Konsistenz, §2.2.
- fan-out (Auffächerung)
- Eine Anfrage, die zu vielen Teilanfragen wird, zum Beispiel wenn ein aclserver Teile eines Checks an andere Server in seinem Cluster sendet. Mehr: Architektur, §3, §3.2.5.
- heartbeat zookie (Heartbeat-zookie)
- Ein zookie in jeder Watch-Antwort, der markiert, wie weit der Stream gekommen ist, damit der Client von dort aus fortsetzen kann. Mehr: §2.4.3.
- hedging (Request-Hedging)
- Dieselbe Anfrage an einen zweiten Server senden, sobald bekannt ist, dass der erste langsam ist, die zuerst eintreffende Antwort verwenden und die andere abbrechen. Zanzibar hedgt Aufrufe an Spanner und Leopard, nicht Aufrufe zwischen seinen eigenen Servern. Die Technik ist beschrieben in Dean und Barroso, „The Tail at Scale“ (CACM, 2013). Mehr: Architektur, §3.2.7.
- hot spot (Hotspot)
- Ein Schlüssel, ein Objekt oder eine Gruppe, die weit mehr Verkehr erhält als andere und den Server überlasten kann, der sie speichert, zum Beispiel eine beliebte Gruppe, die von vielen ACLs geteilt wird. Mehr: Architektur, §3.2.5.
I–N
- intersection (Schnittmenge)
- Ein Operator einer Umschreibregel: die Benutzer, die in jedem von mehreren Usersets enthalten sind. Mehr: Relationstupel, §2.3.1.
- Leopard
- Ein Indexierungssystem für tief verschachtelte oder sehr breite Gruppen. Es flacht Gruppenmitgliedschaften zu Mengen ganzer Zahlen ab, sodass eine Mitgliedschaftsprüfung zu einer Mengenschnittmenge wird, und hält sich über Watch aktuell. Mehr: Leopard, §3.2.4.
- lock table (Sperrtabelle)
- Eine Tabelle pro Server mit laufenden Lesevorgängen und Prüfungen. Von den Anfragen, die einen Cache-Schlüssel teilen, läuft nur eine; die übrigen warten auf ihr Ergebnis. Mehr: Architektur, §3.2.5.
- lock tuple (Lock-Tupel)
- Ein gewöhnliches Relationstupel, das Clients bei jedem Schreibvorgang auf ein Objekt per Touch aktualisieren, sodass ein Schreibvorgang davon abhängig gemacht werden kann, dass seit dem Lesevorgang niemand sonst geschrieben hat. Mehr: §2.4.2.
- namespace (Namespace)
- Eine vom Client definierte Art von Objekt, etwa
docoderfolder. Der Teil vor dem Doppelpunkt indoc:readme. Die Tupel jedes Namespace liegen in einer eigenen Datenbank. Mehr: Relationstupel, §2.1, §2.3, §3.1.1. - namespace config (Namespace-Konfiguration)
- Die Konfiguration eines Namespace: seine Relationen, jede mit einer optionalen Userset-Umschreibregel, dazu Speicherparameter wie das Sharding. Mehr: Relationstupel, §2.3, §3.1.3.
- new enemy problem („New Enemy“-Problem)
- Inhalte jemandem zeigen, der aus ihrer ACL entfernt wurde, weil die Prüfung die Reihenfolge zweier ACL-Änderungen ignoriert oder eine ACL angewendet hat, die älter ist als der Inhalt. Mehr: Konsistenz, §2.2.
O–R
- object (Objekt)
- Das, was geschützt wird, geschrieben ⟨namespace⟩:⟨object_id⟩, etwa
doc:readme. Mehr: Relationstupel, §2.1. - Paxos
- Ein Konsensprotokoll, mit dem sich eine Gruppe von Replikaten auf jeden Schreibvorgang einigen kann, auch wenn einige von ihnen ausfallen. Das Paper platziert die fünf stimmberechtigten Replikate des Zanzibar-Speichers innerhalb von 25 ms voneinander, damit Paxos-Transaktionen schnell committen. Siehe Lamport, „Paxos Made Simple“ (2001). Mehr: Architektur, §3.1.4.
- pointer chasing (Zeigerverfolgung)
- Einen Check beantworten, indem man Usersets Schritt für Schritt folgt: von den Betrachtern des Readmes zu
group:eng#member, dann zu den Mitgliedern dieser Gruppe und so weiter. Langsam, wenn Gruppen tief oder breit sind. Mehr: Relationstupel, Leopard, §3.2.3, §3.2.4. - Read
- Der API-Aufruf, der gespeicherte Tupel zurückgibt, die zu einer oder mehreren Tupelmengen passen. Er wendet keine Umschreibregeln an. Mehr: Relationstupel, §2.4.1.
- Recent request (Recent-Anfrage)
- Siehe Safe-/Recent-Anfragen. Mehr: Konsistenz, §4.1.
- relation (Relation)
- Eine benannte Beziehung zwischen einem Objekt und einem Benutzer oder zwischen zwei Objekten (so wie
parentein Dokument mit seinem Ordner verbindet), etwaowner,viewer,memberoderparent. Definiert in der Namespace-Konfiguration. Mehr: Relationstupel, §2.1, §2.3. - relation tuple (Relationstupel)
- Ein gespeicherter Fakt, ⟨object⟩#⟨relation⟩@⟨user⟩, etwa
doc:readme#owner@user:anne. Die einzige Art von Berechtigungsdaten, die Zanzibar speichert. Mehr: Relationstupel, §2.1. - replica (Replikat)
- Eine Kopie der Daten an einem Standort. Die Daten von Zanzibar werden an Dutzende Standorte repliziert, damit die meisten Lesevorgänge in der Nähe bedient werden können. Mehr: Architektur, §3.1.4.
S
- Safe / Recent requests (Safe-/Recent-Anfragen)
- Die Einteilung der Anfragen nach dem Alter des zookie im Paper. Safe-Anfragen tragen zookies, die älter als 10 Sekunden sind, und können meist innerhalb der Region bedient werden; Recent-Anfragen tragen neuere zookies und brauchen oft einen regionsübergreifenden Round Trip. Mehr: Konsistenz, §4.1.
- Ein Teil einer Datenbank oder eines Index, der getrennt gespeichert und bedient wird. Die Shard-ID eines Tupels ergibt sich meist aus seiner Objekt-ID, bei sehr großen Gruppen aus Objekt-ID und Benutzer. Mehr: Architektur, §3.1.1, §3.2.4.
- snapshot read (Snapshot-Lesevorgang)
- Ein Lesevorgang, der die Datenbank genau zu einem Zeitstempel sieht: jeden Schreibvorgang zu oder vor diesem Zeitpunkt und keinen danach. Zanzibar wertet jeden Check auf einem einzigen Snapshot aus. Spanner definiert ihn als “a read in the past that executes without locking” (einen Lesevorgang in der Vergangenheit, der ohne Sperren ausgeführt wird) (Spanner-Paper, §4.1). Mehr: Konsistenz, §2.2.
- Spanner
- Die global verteilte Datenbank von Google. Zanzibar speichert darin Tupel, Namespace-Konfigurationen und das Changelog und stützt sich für die Konsistenz auf ihre Zeitstempel. Beschrieben in Corbett et al., OSDI 2012. Mehr: Konsistenz, Architektur, §2.2, §3.
T
- tail latency (Tail-Latenz)
- Die Latenz der langsamsten Anfragen, etwa des 99. oder 99,9. Perzentils. Sie ist wichtig, weil eine Seite mit Suchergebnissen Dutzende bis Hunderte von Prüfungen erfordern kann. Siehe Dean und Barroso, „The Tail at Scale“ (CACM, 2013). Mehr: Architektur, §1, §3.2.7, §4.2, §4.5.
_this- Das Blatt einer Umschreibregel, das die Benutzer in gespeicherten Tupeln für dieses Objekt und diese Relation zurückgibt, einschließlich der Usersets, auf die diese Tupel zeigen. Der Standard, wenn eine Relation keine Regel hat. Mehr: Relationstupel, §2.3.1.
- timestamp quantization (Zeitstempel-Quantisierung)
- Auswertungszeitstempel auf einen groben Schritt aufrunden, etwa eine oder zehn Sekunden, sodass viele Anfragen einen Zeitstempel und damit Cache-Einträge teilen. Das schwächt die Konsistenz nicht: Ein zookie setzt nur eine Untergrenze, und ein Spanner-Snapshot-Lesevorgang zu einem zukünftigen Zeitstempel wartet, bis TrueTime ihn überschritten hat (§3.2.5). Mehr: Architektur, Konsistenz, §2.2, §3.2.5.
- TrueTime
- Der Uhrenmechanismus von Spanner, der jedem Schreibvorgang einen Zeitstempel mit Mikrosekundenauflösung gibt, der die kausale Reihenfolge widerspiegelt. Er macht die Zeitstempel von Zanzibar aussagekräftig.
TT.now()gibt ein Intervall zurück, das garantiert die wahre Zeit enthält; siehe das Spanner-Paper (OSDI 2012), §3. Mehr: Konsistenz, §2.2, §3.2.5. - tupleset (Tupelmenge)
- Ein Selektor für gespeicherte Tupel: ein einzelner Tupelschlüssel oder alle Tupel für eine Objekt-ID oder ein Userset, optional auf eine Relation beschränkt. Verwendet von Read und von
tuple_to_userset. Mehr: Relationstupel, §2.4.1. tuple_to_userset- Ein Blatt einer Umschreibregel, das einige Tupel des Objekts liest und aus jedem ein Userset berechnet, zum Beispiel „den übergeordneten Ordner des Readmes nachschlagen und dessen Betrachter nehmen“. Mehr: Relationstupel, §2.3.1.
U–W
- union (Vereinigung)
- Ein Operator einer Umschreibregel: die Benutzer, die in irgendeinem von mehreren Usersets enthalten sind. Alle drei Zweige von
viewerin Abbildung 1 des Papers sind durch eine Vereinigung verbunden. Mehr: Relationstupel, §2.3.1. - user (Benutzer)
- Der dritte Teil eines Tupels: entweder eine einzelne Benutzer-ID oder ein Userset. Mehr: Relationstupel, §2.1.
- userset (Userset)
- Ein Paar ⟨object⟩#⟨relation⟩, das für jeden Benutzer mit dieser Relation zu diesem Objekt steht, etwa
group:eng#member. Erlaubt es einem Tupel, einer Gruppe Zugriff zu gewähren, und Gruppen, Gruppen zu enthalten. Mehr: Relationstupel, §2.1. - userset rewrite rule (Userset-Umschreibregel)
- Teil einer Relationskonfiguration: eine Funktion von einer Objekt-ID auf einen Userset-Ausdrucksbaum, gebaut aus
_this,computed_usersetundtuple_to_userset, kombiniert durch Vereinigung, Schnittmenge und Ausschluss. Mehr: Relationstupel, §2.3.1. - userset tree (Userset-Baum)
- Das Ergebnis von Expand: Blätter sind Benutzer-IDs oder Usersets, innere Knoten sind Mengenoperatoren. Mehr: Relationstupel, §2.4.5.
- Watch
- Der API-Aufruf, der Tupeländerungen für einen oder mehrere Namespaces in Zeitstempelreihenfolge streamt, beginnend bei einem zookie. Wird verwendet, um sekundäre Indizes wie Leopard aktuell zu halten. Mehr: Architektur, §2.4.3.
- watchserver
- Der Servertyp, der Watch beantwortet, indem er das Changelog fortlaufend liest. Mehr: Architektur, §3.
- Write
- Der API-Aufruf, der Tupel hinzufügt oder entfernt. Clients, die alle Tupel eines Objekts neu schreiben, verwenden einen Lesevorgang und dann einen Schreibvorgang, der davon abhängt, dass das Lock-Tupel unverändert ist. Mehr: Architektur (was ein Schreibvorgang berührt), §2.4.2.
Z
- zookie
- Ein opakes Token, das einen Zeitstempel kodiert. Ein Client erhält es aus einer Content-Change-Prüfung (auch Read- und Write-Antworten tragen zookies), speichert es mit dem Inhalt und sendet es mit späteren Prüfungen mit, damit diese auf einem mindestens so aktuellen Snapshot ausgewertet werden. Mehr: Konsistenz, §2.2, §2.4.
Quellen
- J. C. Corbett et al., “Spanner: Google’s Globally-Distributed Database”, OSDI ’12, PDF
- D. Karger et al., “Consistent Hashing and Random Trees”, STOC ’97, PDF
- J. Dean und L. A. Barroso, “The Tail at Scale”, CACM 56(2), 2013, research.google
- L. Lamport, “Paxos Made Simple”, ACM SIGACT News 32(4), 2001, PDF
- D. K. Gifford, “Information Storage in a Decentralized Computer System”, Dissertation, Stanford University, 1981 (Referenz [18] des Papers; keine Online-Kopie geprüft)
- “Cache stampede”, Wikipedia, en.wikipedia.org (die Quelle, die das Paper zitiert)
- Ruoming Pang et al., “Zanzibar: Google’s Consistent, Global Authorization System”, USENIX ATC ’19, usenix.org/conference/atc19/presentation/pang