Zanzibar prévient le problème du « nouvel ennemi » au moyen des zookies, et les zookies fonctionnent parce que Spanner attribue à chaque écriture un horodatage qui respecte la causalité. La page Cohérence, instantanés et zookies explique ces deux points, y compris la manière dont TrueTime et l’attente de validation (commit wait) produisent ces horodatages. Presque personne en dehors de Google ne fonctionne avec TrueTime. Cette page examine ce que le protocole zookie exige réellement d’une base de données, et comment les produits construits sur d’autres bases de données l’obtiennent ou s’en passent.
Ce qu’un zookie exige du stockage de données
Le protocole zookie repose sur deux propriétés que le §2.2 demande à la couche de stockage, « external consistency and snapshot reads with bounded staleness » (la cohérence externe et les lectures d’instantané à obsolescence bornée) :
- L’ordre de validation suit la causalité. Si l’écriture
xs’est produite avant l’écriturey(par exemple, Anne a vuxréussir puis a effectuéy), alorsT_x < T_y. Selon les termes de l’article, deux mises à jour causalement liéesx ≺ y« will be assigned timestamps that reflect the causal order:T_x < T_y» (se voient attribuer des horodatages qui reflètent l’ordre causal :T_x < T_y) (§2.2), et le protocole zookie « ensures that all prior ACL writes have lower timestamps » (garantit que toutes les écritures d’ACL antérieures ont des horodatages inférieurs). - Des lectures d’instantané à un point donné ou après celui-ci. Une lecture à
T« observes all updates with timestamps ≤ T » (observe toutes les mises à jour dont l’horodatage est ≤ T) (§2.2), et une vérification « is always evaluated at a consistent snapshot no earlier than the given zookie » (est toujours évaluée sur un instantané cohérent qui n’est pas antérieur au zookie fourni) (§2.4.4).
Rien dans cette liste ne parle d’« horodatage » au sens de l’heure d’horloge. La valeur contenue dans un zookie peut être n’importe quelle position dans un historique, pourvu que les deux propriétés soient vérifiées pour elle. C’est pourquoi l’article a rendu le zookie opaque : « to discourage our clients from choosing arbitrary timestamps and to allow future extensions » (afin de dissuader nos clients de choisir des horodatages arbitraires et de permettre des extensions futures) (§2.4).
Comment les deux propriétés se combinent-elles pour empêcher Chen de voir le readme après qu’il a été retiré de folder A ?
Remarquez que la propriété ① porte sur des écritures que la base de données peut ne jamais percevoir comme liées. Le §2.2 exige l’ordonnancement pour les « updates on different ACLs or objects and those coordinated via channels invisible to Zanzibar » (mises à jour portant sur des ACL ou des objets différents et celles coordonnées par des canaux invisibles pour Zanzibar). Dans l’exemple A de l’article, le lien entre les deux écritures est le fait qu’Alice s’adresse à Charlie, en dehors de tout système. La base de données doit malgré tout ordonner correctement les deux validations.
Trois manières d’obtenir un ordre
Spanner obtient la propriété ① grâce à des horloges synchronisées dont la borne d’erreur est connue, au prix d’une attente qui couvre l’incertitude à chaque écriture (Spanner, OSDI ’12 ; illustré sur la page consacrée à la cohérence). D’autres bases de données l’obtiennent, entièrement ou en grande partie, de manières différentes. D’où vient l’ordre dans chacune d’elles ?
Remarquez que les bases de données à primaire unique obtiennent la propriété ① gratuitement, car un seul serveur voit toutes les validations dans l’ordre ; ce à quoi elles renoncent, c’est la réplication mondiale de l’article. CockroachDB réplique à l’échelle mondiale mais ne fournit qu’en partie la propriété ①. La section suivante porte sur cet écart.
CockroachDB : la règle des clés qui se recouvrent
CockroachDB n’a pas TrueTime. Ses nœuds maintiennent des horloges approximativement synchronisées, et le cluster dispose d’un décalage d’horloge maximal, --max-offset, dont la valeur par défaut est 500ms ; « If observed clock offsets exceed this limit, servers will crash to minimize the likelihood of reading inconsistent data » (si les décalages d’horloge observés dépassent cette limite, les serveurs s’arrêtent brutalement afin de réduire au minimum la probabilité de lire des données incohérentes) (cockroach start). La comparaison avec Spanner publiée par Cockroach Labs elle-même indique que « CockroachDB only goes as far as to claim serializability » (CockroachDB se limite à revendiquer la sérialisabilité) et nomme l’anomalie qu’elle autorise « causal reverse » (inversion causale) : des transactions causalement liées peuvent être validées avec des horodatages dans le mauvais ordre (Living without atomic clocks, 2022-01-27).
AuthZed a reproduit le problème du « nouvel ennemi » sur CockroachDB avec SpiceDB en 2021 (The One Crucial Difference Between Spanner and CockroachDB, 2021-10-14). Le billet résume ainsi l’écart : « Cockroach does not provide external consistency for transactions involving non-overlapping keys. » (Cockroach ne fournit pas la cohérence externe pour les transactions portant sur des clés qui ne se recouvrent pas.) Son test utilisait deux écritures et une vérification, exécutées « in sequence (not parallel) » (en séquence (pas en parallèle)) : écrire un tuple excluded, écrire un tuple direct, puis vérifier allowed = direct - excluded à la révision de la seconde écriture ; « the check in 3 will succeed » (la vérification de l’étape 3 réussira).
À quoi cela ressemble-t-il avec l’exemple suivi, si l’horloge d’un nœud est en avance ?
Remarquez la flèche intitulée « même clé K » dans le cadre de droite. Aucune des deux horloges ne s’est améliorée ; ce qui a changé, c’est que les deux transactions sont désormais en conflit, et CockroachDB ordonne correctement les transactions en conflit. Les horodatages des deux cadres sont donnés à titre d’illustration ; le décalage reste largement inférieur à la valeur par défaut de 500ms, si bien qu’aucun serveur ne s’arrêterait.
AuthZed a constaté qu’une lecture partagée ne suffisait pas : « we needed both transactions to write to the same key » (il fallait que les deux transactions écrivent sur la même clé). Le pilote CockroachDB de SpiceDB ajoute donc une clé de recouvrement aux écritures, selon une stratégie choisie par --datastore-tx-overlap-strategy (datastores) :
| Stratégie | Documentation de SpiceDB |
|---|---|
static (par défaut) |
« All writes overlap to guarantee safety at the cost of write throughput » (toutes les écritures se recouvrent, ce qui garantit la sûreté au détriment du débit d’écriture) |
prefix |
« Only writes that contain objects with same prefix overlap » (seules les écritures contenant des objets de même préfixe se recouvrent) |
request |
« Only writes with the same io.spicedb.requestoverlapkey header overlap » (seules les écritures portant le même en-tête io.spicedb.requestoverlapkey se recouvrent) |
insecure |
« No writes overlap, providing the best write throughput, but possibly leaving you vulnerable to the New Enemy Problem » (aucune écriture ne se recouvre, ce qui offre le meilleur débit d’écriture mais peut vous laisser exposé au problème du « nouvel ennemi ») |
Le coût, selon les termes d’AuthZed : « This does add a small amount of latency to the write path, but it leaves the read paths performant. » (Cela ajoute un peu de latence au chemin d’écriture, mais laisse les chemins de lecture performants.) Chaque écriture static entre en contention sur une même ligne : c’est le prix que l’article payait à la place par l’attente de validation.
La documentation des stockages de données ajoute une autre réserve concernant CockroachDB, côté lecture : SpiceDB choisit une révision au moyen de cluster_logical_timestamp(), « which can differ across nodes by up to the cluster’s » décalage maximal (« qui peut différer d’un nœud à l’autre jusqu’à hauteur du décalage maximal du cluster »), et « A read may not see a recently committed write if the reading node’s timestamp is behind the writing node’s. » (une lecture peut ne pas voir une écriture récemment validée si l’horodatage du nœud qui lit est en retard sur celui du nœud qui écrit). Par conséquent, « fully_consistent does not guarantee read-after-write consistency on CockroachDB. » (fully_consistent ne garantit pas la cohérence lecture-après-écriture sur CockroachDB). Un ZedToken issu de l’écriture évite ce problème, car il désigne la révision propre à cette écriture (datastores).
PostgreSQL et MySQL : un seul primaire décide
Une base de données à primaire unique voit déjà toutes les validations dans l’ordre, si bien que la propriété ① ne nécessite aucune horloge. La question ouverte est la propriété ② : des lectures susceptibles d’aller vers une réplique en retard.
Le pilote PostgreSQL de SpiceDB n’utilise pas du tout le temps pour ordonner. Une révision est l’identifiant de transaction et l’instantané issus de pg_current_xact_id() et pg_current_snapshot() ; un commentaire du pilote indique que « timestamps cannot be used for ordering transactions in PG » (les horodatages ne peuvent pas servir à ordonner les transactions dans PG), et que deux instantanés peuvent être « mutually uncomparable » (mutuellement incomparables) (postgres/revisions.go, v1.57.1). Un instantané pris après la validation de x répertorie x comme validée, ce qui est la propriété ① exprimée dans les termes propres à PostgreSQL. Le pilote MySQL écrit une ligne dans une table de transactions dont l’id est AUTO_INCREMENT et utilise cet identifiant comme révision (migrations, revisions.go). Une écriture qui commence après la validation d’une autre insère sa ligne plus tard et obtient donc un identifiant plus grand ; ce raisonnement est celui de cette page, et n’est pas énoncé dans la documentation de SpiceDB.
Les répliques en lecture réintroduisent du retard. Comment SpiceDB maintient-il une vérification au moins aussi fraîche que son jeton lorsque la réplique est en retard ?
La documentation décrit exactement ceci : le retard de réplication « would be problematic to SpiceDB’s ability to solve the new enemy problem » (compromettrait la capacité de SpiceDB à résoudre le problème du “nouvel ennemi”), aussi SpiceDB vérifie-t-il « if the revision has been replicated into the target replica. If missing, it will fall back to the primary. » (si la révision a été répliquée dans la réplique cible. Si elle est absente, il se replie sur le primaire.). Pour MySQL, cela « requires two roundtrips instead of one » (nécessite deux allers-retours au lieu d’un), et la documentation déconseille de placer un répartiteur de charge devant des répliques MySQL « because SpiceDB will not be able to maintain consistency guarantees » (car SpiceDB ne pourra pas maintenir les garanties de cohérence) (datastores).
Permify, qui fonctionne sur PostgreSQL, construit son Snap Token de la même manière : le jeton contient un XID8 PostgreSQL et une chaîne d’instantané (snapshot/token.go, v1.7.6). Sa documentation décrit seulement le jeton comme « a token that consists of an encoded timestamp » (un jeton constitué d’un horodatage encodé) (snap tokens).
Spanner sans l’article
SpiceDB fonctionne aussi sur Cloud Spanner, qui dispose de TrueTime. Là, le pilote « assumes the database is linearizable and skips the transaction overlap strategy » (suppose que la base de données est linéarisable et ignore la stratégie de recouvrement des transactions) (datastores), et lit sa révision au moyen de SELECT CURRENT_TIMESTAMP() (spanner/revisions.go). C’est la configuration la plus proche de l’article.
Sans aucun jeton
OpenFGA n’a pas de zookie ; sa documentation indique que l’article « has a feature called Zookies » (comporte une fonctionnalité appelée Zookies) et qu’OpenFGA « is considering a similar feature in future releases » (envisage une fonctionnalité similaire dans de futures versions) (consistency). À la place, une requête choisit MINIMIZE_LATENCY (la valeur par défaut) ou HIGHER_CONSISTENCY, qui « will skip the cache and query the database directly » (contourne le cache et interroge directement la base de données). Sur PostgreSQL avec un stockage de données secondaire configuré (datastore.secondaryUri, « for postgres only » (pour postgres uniquement), configuration), HIGHER_CONSISTENCY sélectionne aussi le primaire : le commentaire du code indique « If we are using higher consistency, we need to use the write database » (si nous utilisons une cohérence plus forte, nous devons utiliser la base de données d’écriture) (postgres.go, v1.22.1).
On obtient ainsi « aussi frais que le primaire », et non « au moins aussi frais que mon écriture ». La différence compte pour le coût : un zookie permet à la plupart des vérifications d’utiliser un cache ou une réplique et n’envoie au primaire que les vérifications récentes, alors que HIGHER_CONSISTENCY y envoie chacune de ces requêtes. La page OpenFGA illustre le cas du cache ; la documentation suggère de choisir le mode pour chaque requête en comparant la date de dernière modification d’une ressource avec la durée de vie (TTL) du cache, ce qui oblige l’application à conserver elle-même une partie de l’information que porte un zookie.
Autres produits :
- Ory Keto comporte les champs
snaptokenetlatestdans son API Check, chacun marqué « This field is not implemented yet and has no effect » (ce champ n’est pas encore implémenté et n’a aucun effet) (check_service.proto). - Warrant lit un en-tête
Warrant-Tokenet n’agit que sur la valeurlatest, qui envoie la lecture vers le primaire ; toute autre valeur est ignorée, et le serveur open source ne renvoie aucun jeton (wookie.go, Warrant). - Topaz ne documente aucun jeton ; voir la page de comparaison.
Les notes de lecture de Tom MacWright sur l’article font le même constat de l’extérieur : OpenFGA n’a rien de comparable aux zookies, et « neither does Ory Keto » (Ory Keto non plus) (Reading Zanzibar, 2025-05-02).
Sans jeton, une application qui a besoin de la garantie de l’article dispose de deux options : lire depuis un stockage toujours à jour (un seul primaire, pas de cache), ou accepter une fenêtre pendant laquelle un utilisateur retiré peut encore être autorisé.
Mécanisme par produit
| Produit et stockage de données | Origine de l’ordre | Jeton | Lectures au jeton ou après |
|---|---|---|---|
| Article (Spanner) | TrueTime + attente de validation | zookie | n’importe quelle réplique ; attend si nécessaire (§3.2.5) |
| SpiceDB sur Spanner | TrueTime ; stratégie de recouvrement ignorée | ZedToken | lecture d’instantané Spanner |
| SpiceDB sur CockroachDB | horodatages HLC ; clé de recouvrement sur les écritures (static par défaut) |
ZedToken | AS OF SYSTEM TIME ; fully_consistent peut manquer une écriture faite sur un autre nœud |
| SpiceDB sur PostgreSQL | identifiant de transaction et instantané du primaire | ZedToken | réplique si elle dispose de la révision, sinon primaire |
| SpiceDB sur MySQL | identifiant de transaction AUTO_INCREMENT |
ZedToken | réplique si elle dispose de la révision, sinon primaire (deux allers-retours) |
| Permify sur PostgreSQL | XID8 et instantané du primaire |
Snap Token | instantané issu du jeton |
| OpenFGA | aucune exposée | aucun | HIGHER_CONSISTENCY : contourner le cache, utiliser le primaire |
| Ory Keto | aucune exposée | champ snaptoken, non implémenté |
non disponible |
| Warrant | aucune (aucun jeton n’est renvoyé) | en-tête Warrant-Token |
latest uniquement ; autres valeurs ignorées |
Les sources de chaque ligne figurent dans les sections ci-dessus. Le chemin de lecture de Permify pour un jeton n’a pas été suivi dans son code source ; la ligne ne reflète que le contenu du jeton.
Sources
- 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 (blog d’éditeur).
- AuthZed, Enforcing Causal Ordering in Distributed Systems: The Importance of Permissions Checking, 2021-02-17 (blog d’éditeur).
- AuthZed, Datastores, documentation de SpiceDB.
- Code source de SpiceDB v1.57.1 :
postgres/revisions.go,mysql/revisions.go, schéma initialmysql,spanner/revisions.go. - Cockroach Labs,
cockroach start(--max-offset). - Spencer Kimball et Irfan Sharif, Living without atomic clocks: Where CockroachDB and Spanner diverge, Cockroach Labs, 2022-01-27 (blog d’éditeur).
- OpenFGA, Query Consistency Modes et Configuring OpenFGA ; code source v1.22.1
pkg/storage/postgres/postgres.go. - Permify, Snap Tokens ; code source v1.7.6
snapshot/token.go. - Ory Keto,
check_service.proto. - Warrant,
pkg/wookie/wookie.go. - Tom MacWright, Reading Zanzibar, 2025-05-02.