guide:without-truetime@fr

Guides

Ordonner sans TrueTime

Ce qu’un zookie exige de la base de données sous-jacente, comment les produits de type Zanzibar l’obtiennent de CockroachDB, PostgreSQL, MySQL et Spanner, et ce qui se passe lorsque rien ne le fournit.

Faits vérifiés le Sections de l’article §2.2, §2.4, §2.4.4, §3.2.5, §5

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) :

  1. L’ordre de validation suit la causalité. Si l’écriture x s’est produite avant l’écriture y (par exemple, Anne a vu x réussir puis a effectué y), alors T_x < T_y. Selon les termes de l’article, deux mises à jour causalement liées x ≺ 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).
  2. 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 ?

Les deux propriétés sur lesquelles repose un zookieL’écriture x retire Chen de folder:A. L’écriture y, effectuée après l’acquittement de x, déplace doc:readme dans folder:A. La propriété 1 dit que la position de validation de x est inférieure à celle de y. Le jeton renvoyé pour y désigne la position de y. Une vérification ultérieure transporte le jeton. La propriété 2 dit que la vérification lit un instantané situé au jeton ou après lui, qui contient donc y et, en raison de la propriété 1, également x. L’accès est refusé à Chen.x : retirer Chende folder:Ay : déplacer readmedans folder:Atoken = pos(y)vérification àinstantané ≥ jetonvoit x et y :Chen refusé① x ≺ y ⇒ pos(x) < pos(y)renvoyétransporté② tout ≤ instantané
Si ① est rompue, l’instantané peut contenir y sans x. Si ② est rompue, la vérification peut s’exécuter avant y. Dans les deux cas, Chen voit le readme.

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 ?

D’où vient l’ordre de validationTrois sources d’ordre. Spanner : les horodatages TrueTime et l’attente de validation donnent à chaque validation un horodatage causal, entre régions. CockroachDB : les horloges logiques hybrides donnent des horodatages qui respectent la causalité seulement entre transactions touchant les mêmes clés, aussi SpiceDB fait-il en sorte que les écritures touchent une clé commune. PostgreSQL et MySQL : un seul primaire décide de l’ordre de validation, si bien qu’un identifiant de transaction ou un instantané issu de ce primaire respecte déjà la causalité.SpannerTrueTime + commit waitCockroachDBhorloge logique hybridePostgreSQL, MySQLun seul primairetoute validationordonnéeordonnée seulement siles clés se recouvrenttoute validationordonnée, un seul site
La colonne du milieu est celle qui a besoin de l’aide de la couche applicative.

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 ?

Décalage d’horloge sans clés qui se recouvrentAu temps réel 10.000, l’application d’Anne retire Chen de folder:A. Le nœud 1, dont l’horloge avance de 250 ms, la valide à l’horodatage 10.250. Après l’acquittement, au temps réel 10.100, l’application déplace le readme dans folder:A. Le nœud 2, dont l’horloge est exacte, valide cette écriture à l’horodatage 10.100 et la renvoie comme jeton. La vérification de Chen s’exécute à l’instantané 10.100. Elle voit le déplacement mais pas le retrait, qui a l’horodatage le plus élevé : Chen est donc autorisé. C’est le problème du « nouvel ennemi ».temps réel10.00010.100application d’Annenœud 1 (+250 ms)nœud 2 (à l’heure)vérification de Chenackjeton 10.100x : retirer Chenvalide xà 10.250y : déplacer readmevalide yà 10.100vérification àinstantané 10.100voit y, pas x :Chen autorisé
Violation : y s’est produit après x, mais T_y < T_x. L’instantané à T_y n’est pas un préfixe de ce qui s’est passé.
Décalage d’horloge avec une clé de recouvrementLes deux mêmes écritures, mais chaque écriture écrit aussi une clé de recouvrement partagée K. Le nœud 1 valide x, y compris K, à 10.250. Lorsque le nœud 2 valide y, il écrit aussi K, si bien que CockroachDB doit donner à y un horodatage supérieur à celui de l’écriture de x sur K, ici 10.251. Le jeton vaut 10.251, la vérification de Chen s’exécute à cet instantané, voit x et y, et l’accès est refusé à Chen.temps réel10.00010.100application d’Annenœud 1 (+250 ms)nœud 2 (à l’heure)vérification de Chenackmême clé Kjeton 10.251x : retirer Chenvalide x + Kà 10.250y : déplacer readmevalide y + Kà 10.251vérification àinstantané 10.251voit x et y :Chen refusé
Correction : deux écritures sur une même clé sont ordonnées par la clé, et non par les horloges.

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 ?

Repli sur le primaire lorsqu’une réplique est en retardL’application retire Chen de folder:A. Le primaire valide cette écriture comme révision r105 et SpiceDB renvoie un ZedToken pour r105. Plus tard, une vérification arrive avec at_least_as_fresh r105. SpiceDB demande à la réplique si r105 a été répliquée ; la réplique n’a atteint que r103, aussi SpiceDB envoie-t-il plutôt la lecture au primaire, qui répond à r105 ou au-delà. L’accès est refusé à Chen.tempsapplicationSpiceDBprimairerépliquewritten_ata r105 ?retirer Chenvalide r105ZedToken r105vérif., jeton r105rejoué jusqu’à r103r105 absente :utiliser le primairelecture à ≥ r105Chen refusé
Les numéros de révision sont donnés à titre d’illustration. Une vérification sans jeton récent a plus de chances d’obtenir sa réponse de la réplique.

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 snaptoken et latest dans 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-Token et n’agit que sur la valeur latest, 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