Zanzibar verhindert das „New Enemy“-Problem mit zookies, und zookies funktionieren, weil Spanner jedem Schreibvorgang einen Zeitstempel gibt, der die Kausalität respektiert. Konsistenz, Snapshots und zookies erklärt beides, einschließlich der Frage, wie TrueTime und Commit-Wait diese Zeitstempel erzeugen. Fast niemand außerhalb von Google läuft auf TrueTime. Diese Seite fragt, was das zookie-Protokoll tatsächlich von einer Datenbank braucht und wie Produkte auf anderen Datenbanken es erhalten oder ohne es auskommen.
Was ein zookie vom Datenspeicher braucht
Das zookie-Protokoll beruht auf zwei Eigenschaften, die §2.2 von der Speicherschicht verlangt, “external consistency and snapshot reads with bounded staleness” (externe Konsistenz und Snapshot-Lesevorgänge mit begrenzter Veraltung):
- Die Commit-Reihenfolge folgt der Kausalität. Geschah Schreibvorgang
xvor Schreibvorgangy(zum Beispiel sah Annexgelingen und machte danny), dann giltT_x < T_y. In den Worten des Papers werden zwei kausal zusammenhängende Aktualisierungenx ≺ y“will be assigned timestamps that reflect the causal order:T_x < T_y” (§2.2) (Zeitstempel zugewiesen, die die kausale Reihenfolge widerspiegeln:T_x < T_y), und das zookie-Protokoll “ensures that all prior ACL writes have lower timestamps” (stellt sicher, dass alle vorherigen ACL-Schreibvorgänge niedrigere Zeitstempel haben). - Snapshot-Lesevorgänge zu oder nach einem gegebenen Punkt. Ein Lesevorgang zu
T“observes all updates with timestamps ≤ T” (§2.2) (beobachtet alle Aktualisierungen mit Zeitstempeln ≤ T), und eine Prüfung “is always evaluated at a consistent snapshot no earlier than the given zookie” (§2.4.4) (wird stets auf einem konsistenten Snapshot ausgewertet, der nicht früher liegt als der angegebene zookie).
Nichts in dieser Liste sagt „Zeitstempel“ im Sinne einer Uhrzeit. Der Wert in einem zookie kann jede Position in einer Historie sein, solange die beiden Eigenschaften für ihn gelten. Deshalb hat das Paper den zookie opak gemacht: “to discourage our clients from choosing arbitrary timestamps and to allow future extensions” (§2.4) (um unsere Clients davon abzuhalten, beliebige Zeitstempel zu wählen, und um zukünftige Erweiterungen zu ermöglichen).
Wie verhindern die beiden Eigenschaften zusammen, dass Chen das Readme sieht, nachdem er aus Ordner A entfernt wurde?
Eigenschaft ① betrifft Schreibvorgänge, die die Datenbank womöglich nie als zusammenhängend sieht. §2.2 verlangt eine Reihenfolge für “updates on different ACLs or objects and those coordinated via channels invisible to Zanzibar” (Aktualisierungen an verschiedenen ACLs oder Objekten und solche, die über für Zanzibar unsichtbare Kanäle koordiniert werden). In Beispiel A des Papers ist die Verbindung zwischen den beiden Schreibvorgängen Alice, die Charlie bittet, außerhalb jedes Systems. Die Datenbank muss die beiden Commits trotzdem richtig ordnen.
Drei Wege zu einer Reihenfolge
Spanner erhält Eigenschaft ① aus synchronisierten Uhren mit bekannter Fehlergrenze, bezahlt durch das Abwarten der Unsicherheit bei jedem Schreibvorgang (Spanner, OSDI ’12; gezeichnet auf der Konsistenzseite). Andere Datenbanken erhalten sie, oder den größten Teil davon, auf andere Weise. Woher kommt die Reihenfolge jeweils?
Datenbanken mit einem einzigen Primärserver erhalten Eigenschaft ① umsonst, weil ein Server jeden Commit in Reihenfolge sieht; was sie aufgeben, ist die globale Replikation des Papers. CockroachDB repliziert global, bietet Eigenschaft ① aber nur teilweise. Um diese Lücke geht es im nächsten Abschnitt.
CockroachDB: die Regel der überlappenden Schlüssel
CockroachDB hat kein TrueTime. Seine Knoten halten lose synchronisierte Uhren, und der Cluster hat einen maximalen Uhrenversatz, --max-offset, mit einem Standard von 500ms; “If observed clock offsets exceed this limit, servers will crash to minimize the likelihood of reading inconsistent data” (Überschreiten beobachtete Uhrenversätze diese Grenze, stürzen Server ab, um die Wahrscheinlichkeit inkonsistenter Lesevorgänge zu minimieren) (cockroach start). Der eigene Vergleich von Cockroach Labs mit Spanner sagt “CockroachDB only goes as far as to claim serializability” (CockroachDB beansprucht nur Serialisierbarkeit) und nennt die Anomalie, die es zulässt, “causal reverse” (kausale Umkehr): Kausal zusammenhängende Transaktionen können mit Zeitstempeln in falscher Reihenfolge committen (Living without atomic clocks, 2022-01-27).
AuthZed reproduzierte 2021 das „New Enemy“-Problem auf CockroachDB mit SpiceDB (The One Crucial Difference Between Spanner and CockroachDB, 2021-10-14). Die Zusammenfassung der Lücke im Beitrag: “Cockroach does not provide external consistency for transactions involving non-overlapping keys.” (Cockroach bietet keine externe Konsistenz für Transaktionen mit nicht überlappenden Schlüsseln.) Sein Test verwendete zwei Schreibvorgänge und eine Prüfung, ausgeführt “in sequence (not parallel)” (nacheinander, nicht parallel): ein Tupel excluded schreiben, ein Tupel direct schreiben, dann allowed = direct - excluded bei der Revision des zweiten Schreibvorgangs prüfen; “the check in 3 will succeed” (die Prüfung in 3 wird gelingen).
Wie sieht das mit dem durchgehenden Beispiel aus, wenn die Uhr eines Knotens vorgeht?
Beachten Sie den Pfeil „derselbe Schlüssel K“ im rechten Bild. Keine der Uhren wurde besser; geändert hat sich, dass die beiden Transaktionen nun in Konflikt stehen, und CockroachDB ordnet konfligierende Transaktionen korrekt. Die Zeitstempel in beiden Bildern dienen der Veranschaulichung; der Versatz liegt deutlich innerhalb des Standards von 500ms, also würde kein Server abstürzen.
AuthZed stellte fest, dass ein gemeinsamer Lesevorgang nicht genügte: “we needed both transactions to write to the same key” (beide Transaktionen mussten auf denselben Schlüssel schreiben). Der CockroachDB-Treiber von SpiceDB fügt Schreibvorgängen daher einen Überlappungsschlüssel hinzu, mit einer Strategie, die durch --datastore-tx-overlap-strategy gewählt wird (Datastores):
| Strategie | SpiceDB-Dokumentation |
|---|---|
static (Standard) |
“All writes overlap to guarantee safety at the cost of write throughput” (Alle Schreibvorgänge überlappen, um Sicherheit auf Kosten des Schreibdurchsatzes zu garantieren) |
prefix |
“Only writes that contain objects with same prefix overlap” (Nur Schreibvorgänge mit Objekten desselben Präfixes überlappen) |
request |
“Only writes with the same io.spicedb.requestoverlapkey header overlap” (Nur Schreibvorgänge mit demselben Header io.spicedb.requestoverlapkey überlappen) |
insecure |
“No writes overlap, providing the best write throughput, but possibly leaving you vulnerable to the New Enemy Problem” (Keine Schreibvorgänge überlappen; das bietet den besten Schreibdurchsatz, macht Sie aber möglicherweise anfällig für das „New Enemy“-Problem) |
Die Kosten, in den Worten von AuthZed: “This does add a small amount of latency to the write path, but it leaves the read paths performant.” (Das fügt dem Schreibpfad etwas Latenz hinzu, lässt die Lesepfade aber performant.) Jeder static-Schreibvorgang konkurriert um eine Zeile; das ist der Preis, den das Paper stattdessen mit Commit-Wait bezahlt hat.
Die Datastore-Dokumentation nennt noch einen Vorbehalt zu CockroachDB, auf der Leseseite: SpiceDB wählt eine Revision mit cluster_logical_timestamp(), “which can differ across nodes by up to the cluster’s” maximum offset (der sich zwischen Knoten um bis zum maximalen Versatz des Clusters unterscheiden kann), und “A read may not see a recently committed write if the reading node’s timestamp is behind the writing node’s.” (Ein Lesevorgang sieht einen kürzlich committeten Schreibvorgang möglicherweise nicht, wenn der Zeitstempel des lesenden Knotens hinter dem des schreibenden Knotens liegt.) Folglich “fully_consistent does not guarantee read-after-write consistency on CockroachDB.” (garantiert fully_consistent auf CockroachDB keine Read-after-Write-Konsistenz.) Ein ZedToken aus dem Schreibvorgang vermeidet das, weil es die eigene Revision des Schreibvorgangs nennt (Datastores).
PostgreSQL und MySQL: ein Primärserver entscheidet
Eine Datenbank mit einem einzigen Primärserver sieht bereits jeden Commit in Reihenfolge, also braucht Eigenschaft ① keine Uhren. Offen ist Eigenschaft ②: Lesevorgänge, die an ein Replikat gehen können, das im Rückstand ist.
Der PostgreSQL-Treiber von SpiceDB verwendet für die Reihenfolge überhaupt keine Zeit. Eine Revision ist die Transaktions-ID und der Snapshot aus pg_current_xact_id() und pg_current_snapshot(); ein Kommentar im Treiber sagt “timestamps cannot be used for ordering transactions in PG” (Zeitstempel können in PG nicht zum Ordnen von Transaktionen verwendet werden) und dass zwei Snapshots “mutually uncomparable” (gegenseitig unvergleichbar) sein können (postgres/revisions.go, v1.57.1). Ein Snapshot, der nach dem Commit von x aufgenommen wird, führt x als committet; das ist Eigenschaft ① in den eigenen Begriffen von PostgreSQL. Der MySQL-Treiber schreibt eine Zeile in eine Transaktionstabelle, deren id AUTO_INCREMENT ist, und verwendet diese ID als Revision (migrations, revisions.go). Ein Schreibvorgang, der beginnt, nachdem ein anderer committet hat, fügt seine Zeile später ein und erhält daher eine größere ID; diese Überlegung stammt von dieser Seite und steht nicht in der SpiceDB-Dokumentation.
Read Replicas bringen Verzögerung zurück. Wie hält SpiceDB eine Prüfung mindestens so aktuell wie ihr Token, wenn das Replikat im Rückstand ist?
Die Dokumentation beschreibt genau das: Replikationsverzögerung “would be problematic to SpiceDB’s ability to solve the new enemy problem” (wäre problematisch für die Fähigkeit von SpiceDB, das „New Enemy“-Problem zu lösen), daher prüft SpiceDB, “if the revision has been replicated into the target replica. If missing, it will fall back to the primary.” (ob die Revision in das Zielreplikat repliziert wurde. Fehlt sie, fällt es auf den Primärserver zurück.) Für MySQL “requires two roundtrips instead of one” (erfordert das zwei Round Trips statt einem), und die Dokumentation warnt vor einem Load Balancer vor MySQL-Replikaten, “because SpiceDB will not be able to maintain consistency guarantees” (weil SpiceDB dann keine Konsistenzgarantien aufrechterhalten kann) (Datastores).
Permify, das auf PostgreSQL läuft, baut sein Snap Token auf dieselbe Weise: Das Token enthält eine PostgreSQL-XID8 und einen Snapshot-String (snapshot/token.go, v1.7.6). Seine Dokumentation beschreibt das Token nur als “a token that consists of an encoded timestamp” (ein Token, das aus einem kodierten Zeitstempel besteht) (Snap Tokens).
Spanner ohne das Paper
SpiceDB läuft auch auf Cloud Spanner, das TrueTime hat. Dort “assumes the database is linearizable and skips the transaction overlap strategy” (nimmt der Treiber an, dass die Datenbank linearisierbar ist, und überspringt die Überlappungsstrategie für Transaktionen) (Datastores) und liest seine Revision mit SELECT CURRENT_TIMESTAMP() (spanner/revisions.go). Das ist die Konfiguration, die dem Paper am nächsten kommt.
Ganz ohne Token
OpenFGA hat keinen zookie; seine Dokumentation sagt, das Paper “has a feature called Zookies” (hat eine Funktion namens Zookies), und OpenFGA “is considering a similar feature in future releases” (erwägt eine ähnliche Funktion in zukünftigen Releases) (Konsistenz). Stattdessen wählt eine Abfrage MINIMIZE_LATENCY (Standard) oder HIGHER_CONSISTENCY, das “will skip the cache and query the database directly” (den Cache umgeht und die Datenbank direkt abfragt). Auf PostgreSQL mit konfiguriertem sekundärem Datenspeicher (datastore.secondaryUri, “for postgres only”, also nur für Postgres, Konfiguration) wählt HIGHER_CONSISTENCY auch den Primärserver: Der Code-Kommentar lautet “If we are using higher consistency, we need to use the write database” (Wenn wir höhere Konsistenz verwenden, müssen wir die Schreibdatenbank verwenden) (postgres.go, v1.22.1).
Das ergibt „so aktuell wie der Primärserver“, nicht „mindestens so aktuell wie mein Schreibvorgang“. Der Unterschied zählt für die Kosten: Ein zookie lässt die meisten Prüfungen einen Cache oder ein Replikat verwenden und nur aktuelle an den Primärserver gehen, während HIGHER_CONSISTENCY jede solche Abfrage dorthin schickt. Die OpenFGA-Seite zeichnet den Cache-Fall; die Dokumentation schlägt vor, den Modus pro Anfrage zu wählen, indem man den Zeitpunkt der letzten Änderung einer Ressource mit der Cache-TTL vergleicht, womit die Anwendung einen Teil der Information eines zookie selbst hält.
Andere Produkte:
- Ory Keto hat in seiner Check-API die Felder
snaptokenundlatest, jeweils mit dem Vermerk “This field is not implemented yet and has no effect” (Dieses Feld ist noch nicht implementiert und hat keine Wirkung) (check_service.proto). - Warrant liest einen Header
Warrant-Tokenund reagiert nur auf den Wertlatest, der den Lesevorgang an den Primärserver schickt; jeder andere Wert wird ignoriert, und der Open-Source-Server gibt kein Token zurück (wookie.go, Warrant). - Topaz dokumentiert kein Token; siehe die Vergleichsseite.
Tom MacWrights Lesenotizen zum Paper machen dieselbe Beobachtung von außen: OpenFGA hat nichts wie zookies, und “neither does Ory Keto” (Ory Keto auch nicht) (Reading Zanzibar, 2025-05-02).
Ohne Token hat eine Anwendung, die die Garantie des Papers braucht, zwei Möglichkeiten: aus einem Speicher lesen, der immer aktuell ist (ein Primärserver, kein Cache), oder ein Zeitfenster akzeptieren, in dem ein entfernter Benutzer noch erlaubt sein kann.
Mechanismus pro Produkt
| Produkt und Datenspeicher | Woher die Reihenfolge kommt | Token | Lesen zu oder nach dem Token |
|---|---|---|---|
| Paper (Spanner) | TrueTime + Commit-Wait | zookie | jedes Replikat; wartet bei Bedarf (§3.2.5) |
| SpiceDB auf Spanner | TrueTime; Überlappungsstrategie übersprungen | ZedToken | Spanner-Snapshot-Lesevorgang |
| SpiceDB auf CockroachDB | HLC-Zeitstempel; Überlappungsschlüssel bei Schreibvorgängen (standardmäßig static) |
ZedToken | AS OF SYSTEM TIME; fully_consistent kann einen Schreibvorgang auf einem anderen Knoten verpassen |
| SpiceDB auf PostgreSQL | Transaktions-ID und Snapshot des Primärservers | ZedToken | Replikat, wenn es die Revision hat, sonst Primärserver |
| SpiceDB auf MySQL | AUTO_INCREMENT-Transaktions-ID |
ZedToken | Replikat, wenn es die Revision hat, sonst Primärserver (zwei Round Trips) |
| Permify auf PostgreSQL | XID8 und Snapshot des Primärservers |
Snap Token | Snapshot aus dem Token |
| OpenFGA | keine offengelegt | keines | HIGHER_CONSISTENCY: Cache umgehen, Primärserver verwenden |
| Ory Keto | keine offengelegt | Feld snaptoken, nicht implementiert |
nicht verfügbar |
| Warrant | keine (es wird kein Token zurückgegeben) | Header Warrant-Token |
nur latest; andere Werte werden ignoriert |
Die Quellen für jede Zeile stehen in den Abschnitten oben. Der Lesepfad von Permify für ein Token wurde im Quellcode nicht nachverfolgt; die Zeile gibt nur den Inhalt des Tokens wieder.
Quellen
- Ruoming Pang et al., Zanzibar: Google’s Consistent, Global Authorization System, USENIX ATC ’19, §2.2, §2.4, §2.4.4, §3.2.5, §5.
- James C. Corbett et al., Spanner: Google’s Globally-Distributed Database, OSDI ’12.
- AuthZed, The One Crucial Difference Between Spanner and CockroachDB, 2021-10-14 (Hersteller-Blog).
- AuthZed, Enforcing Causal Ordering in Distributed Systems: The Importance of Permissions Checking, 2021-02-17 (Hersteller-Blog).
- AuthZed, Datastores, SpiceDB-Dokumentation.
- Quellcode von SpiceDB v1.57.1:
postgres/revisions.go,mysql/revisions.go,mysql-Anfangsschema,spanner/revisions.go. - Cockroach Labs,
cockroach start(--max-offset). - Spencer Kimball und Irfan Sharif, Living without atomic clocks: Where CockroachDB and Spanner diverge, Cockroach Labs, 2022-01-27 (Hersteller-Blog).
- OpenFGA, Query Consistency Modes und Configuring OpenFGA; Quellcode v1.22.1
pkg/storage/postgres/postgres.go. - Permify, Snap Tokens; Quellcode v1.7.6
snapshot/token.go. - Ory Keto,
check_service.proto. - Warrant,
pkg/wookie/wookie.go. - Tom MacWright, Reading Zanzibar, 2025-05-02.