guide:consistency@fr

Guides

Cohérence, instantanés et zookies

Pourquoi un système d’autorisation doit respecter l’ordre des modifications d’ACL et de contenu, et comment Zanzibar y parvient avec les horodatages de Spanner et les zookies.

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

Une vérification d’ACL répond à la question « cet utilisateur peut-il faire ceci, maintenant ? ». Dans un système répliqué à l’échelle mondiale, c’est le « maintenant » qui pose difficulté : des serveurs différents ont vu des écritures différentes. Cette page explique quel ordre Zanzibar s’engage à respecter, comment Spanner rend cet engagement peu coûteux à tenir, et comment le zookie permet à un client de fixer la fraîcheur minimale dont une vérification a besoin.

Le problème du « nouvel ennemi »

L’article ouvre le §2.2 par une règle : « ACL checks must respect the order in which users modify ACLs and object contents to avoid unexpected sharing behaviors. » (Les vérifications d’ACL doivent respecter l’ordre dans lequel les utilisateurs modifient les ACL et le contenu des objets afin d’éviter des comportements de partage inattendus.) Il appelle cette défaillance le problème du « nouvel ennemi » : un utilisateur qui vient d’être retiré d’une ACL voit encore le contenu que ce retrait devait lui cacher.

L’article donne deux exemples. Pour ces deux exemples, cette page conserve les noms de l’article, Alice, Bob et Charlie, afin que vous puissiez les lire en regard du §2.2 ; partout ailleurs, elle utilise l’exemple suivi d’Anne, Beto et Chen.

Que peut-il se passer si une vérification voit la seconde modification mais pas la première ? Le cadre de gauche montre un système sans ordonnancement ; le cadre de droite, la même histoire sous Zanzibar.

Exemple A sans ordonnancementAlice retire Bob de l’ACL du dossier (A1), puis sollicite Charlie, qui déplace de nouveaux documents dans le dossier (A2). La vérification de Bob est évaluée sur des données qui incluent A2 mais pas A1 ; Bob est donc autorisé à lire les nouveaux documents. C’est la violation.tempsT_A1T_A2AliceCharlieBobdemandeA1 : retirer Bobdu dossierA2 : déplacer lesdocs dans le dossierla vérification voitA2 mais pas A1Bob voit lesnouveaux docs
Violation : la vérification applique A2 sans A1, et Bob lit les nouveaux documents.
Exemple A sous ZanzibarA1 et A2 reçoivent des horodatages T_A1 inférieur à T_A2. Une vérification sur un instantané antérieur à T_A2 ne voit pas les documents dans le dossier. Une vérification sur un instantané égal ou postérieur à T_A2 voit aussi A1 ; Bob est donc refusé dans les deux cas.tempsT_A1T_A2AliceCharlieBobdemandeA1 : retirer Bobdu dossierA2 : déplacer lesdocs dans le dossiervérification àT < T_A2docs pas encoredans le dossiervérification àT ≥ T_A2voit A1 :Bob refusé
Zanzibar : tout instantané qui contient A2 contient aussi A1.

Remarquez qu’aucun instantané ne contient A2 sans A1. C’est là toute la garantie : le §2.2 explique que si une vérification s’exécute à T < T_A2, « the document ACLs will not include the folder ACL » (les ACL des documents n’incluront pas l’ACL du dossier), et que si elle s’exécute à T ≥ T_A2 > T_A1, elle « will observe update A1, which removed Bob from the folder ACL » (observera la mise à jour A1, qui a retiré Bob de l’ACL du dossier).

L’exemple B diffère sur un point : la seconde modification porte sur le contenu du document, qui réside dans le stockage de l’application cliente et non dans Zanzibar. Zanzibar ne voit jamais cette écriture. Comment peut-il savoir qu’une vérification portant sur le nouveau contenu doit être suffisamment fraîche ?

Exemple B sans ordonnancementAlice retire Bob de l’ACL du document (B1), puis sollicite Charlie, qui ajoute du nouveau contenu (B2). La vérification de Bob est évaluée sur un instantané obsolète antérieur à B1 ; elle autorise donc encore Bob, qui lit le nouveau contenu. C’est la violation.tempsT_B1T_B2AliceCharlieBobdemandeB1 : retirer Bobde l’ACL du docB2 : ajouter dunouveau contenuvérification àT < T_B1 obsolèteBob voit lenouveau contenu
Violation : une ancienne ACL est appliquée à un nouveau contenu.
Exemple B sous ZanzibarAlice retire Bob (B1). La modification de contenu de Charlie reçoit un zookie encodant son horodatage T_B2, stocké avec le nouveau contenu. La vérification de Bob transporte ce zookie ; elle est donc évaluée sur un instantané égal ou postérieur à T_B2, qui inclut B1, et Bob est refusé.tempsT_B1T_B2AliceCharlieBobdemandezookieB1 : retirer Bobde l’ACL du docB2 + zookie(T_B2)la vérificationporte le zookievoit B1 :Bob refusé
Zanzibar : le zookie stocké avec B2 impose un instantané égal ou postérieur à T_B2.

La flèche en pointillés est la solution. Le zookie accompagne le contenu ; la vérification portant sur B2 ne peut donc pas s’exécuter sur un instantané antérieur à B2, et tout instantané de ce type contient déjà B1. La suite de la page explique les deux propriétés sur lesquelles cela repose et le protocole qui fait circuler le zookie.

Des horodatages porteurs de sens causal

Le §2.2 nomme deux propriétés : la cohérence externe et les lectures d’instantané à obsolescence bornée. Pour la cohérence externe, l’article cite la thèse de Gifford de 1981. L’article sur Spanner énonce la même propriété pour les transactions : « if a transaction T1 commits before another transaction T2 starts, then T1’s commit timestamp is smaller than T2’s » (si une transaction T1 est validée avant qu’une autre transaction T2 ne commence, l’horodatage de validation de T1 est inférieur à celui de T2), et note que c’est « equivalently, linearizability » (de manière équivalente, la linéarisabilité), en citant Herlihy et Wing (1990).

Selon les termes de Zanzibar (§2.2), deux mises à jour causalement liées x ≺ y reçoivent des horodatages tels que T_x < T_y. Une lecture d’instantané à l’horodatage T « observes all updates with timestamps ≤ T » (observe toutes les mises à jour dont l’horodatage est ≤ T). En combinant les deux : si une lecture voit y, elle voit aussi tout ce qui s’est produit avant y. Cela fonctionne parce que le stockage est multiversion : Spanner définit une lecture d’instantané comme « a read in the past that executes without locking » (une lecture dans le passé qui s’exécute sans verrouillage) (Spanner §4.1), et dans un stockage multiversion « each write on a data item produces a new copy (or version) » (chaque écriture sur une donnée produit une nouvelle copie (ou version)) (Bernstein et Goodman, 1983).

Que voit un lecteur sous cette règle, et que peut voir le lecteur d’une réplique à cohérence à terme ? Dans cette variante, le readme se trouve initialement hors de folder:A. Anne retire d’abord Chen en tant que lecteur de folder:A (x, validée à T=10), puis déplace doc:readme dans folder:A (y, à T=20).

Lectures d’instantané face à une réplique à cohérence à termeL’écriture x retire Chen de folder:A à l’horodatage 10 ; l’écriture y déplace doc:readme dans folder:A à l’horodatage 20, et x se produit avant y. Une lecture d’instantané à T=15 ne voit que x ; une lecture d’instantané à T=25 voit x et y. Une réplique à cohérence à terme applique y avant x, et dans cet intervalle Chen peut voir le readme.tempsT=10T=20écritures d’ACLlecture d’instantanéréplique à termex ≺ yx : retirer Chende folder:Ay : déplacer readmedans folder:Ainstantané à T=15 :voit x seulementla réplique a y,pas encore xinstantané à T=25 :voit x et yChen voit le readme(x non appliqué)
Un instantané, quel que soit T, est un préfixe de l’ordre causal. Une réplique à terme peut exposer y sans x tant qu’elle n’a pas rattrapé son retard.

Remarquez que les deux lectures d’instantané diffèrent par la quantité de ce qu’elles voient, jamais par l’ordre : chacune est un préfixe de l’historique. La réplique à terme finira elle aussi par converger, mais d’ici là elle peut montrer un état qui n’a jamais existé. L’article établit lui-même ce contraste au §5 : TAO « offers eventual global consistency with asynchronous replication » (offre une cohérence globale à terme avec une réplication asynchrone), tandis que Zanzibar « provides external consistency and snapshot reads with bounded staleness » (fournit la cohérence externe et des lectures d’instantané à obsolescence bornée).

D’où viennent les horodatages : TrueTime

Zanzibar ne calcule pas lui-même ces horodatages. Il stocke les ACL dans Spanner, dont le « TrueTime mechanism assigns each ACL write a microsecond-resolution timestamp, such that the timestamps of writes reflect the causal ordering between writes » (mécanisme TrueTime attribue à chaque écriture d’ACL un horodatage à la résolution de la microseconde, de sorte que les horodatages des écritures reflètent l’ordre causal entre les écritures) (§2.2). Les grandes lignes de ce fonctionnement figurent aux §3, §4.1.2 et §4.2.1 de l’article sur Spanner (OSDI ’12).

  • TT.now() renvoie un intervalle [earliest, latest] dont il est garanti qu’il contient le temps absolu auquel l’appel a eu lieu. L’incertitude ε vaut la moitié de la largeur de l’intervalle ; dans l’environnement de production de Google, elle était « typically a sawtooth function of time, varying from about 1 to 7 ms over each poll interval » (typiquement une fonction du temps en dents de scie, variant d’environ 1 à 7 ms sur chaque intervalle d’interrogation).
  • Démarrage : le leader attribue à une écriture un horodatage de validation s au moins égal à TT.now().latest.
  • Attente de validation (commit wait) : les clients ne peuvent pas voir l’écriture tant que TT.after(s) n’est pas vrai, c’est-à-dire tant que s n’est pas passé de façon certaine partout. Spanner note que « the expected wait is at least 2 ∗ ε̄ » (l’attente prévue est d’au moins 2 ∗ ε̄), où ε̄ est la borne d’erreur moyenne (§4.2.1).

Comment l’attente rend-elle les horodatages causaux ?

L’attente de validation dans SpannerUne écriture arrive au leader, qui appelle TT.now() et obtient un intervalle allant de earliest à latest, de largeur 2 epsilon. Le leader choisit s égal à latest. Il attend ensuite que TT.after(s) soit vrai, ce qui prend environ 2 epsilon, et seulement alors rend l’écriture visible et répond. Toute transaction qui commence après la réponse appelle TT.now() plus tard ; son latest, et donc son horodatage, est donc supérieur à s.earliestlatestl’écriture arriveTT.now()s = latestTT.after(s)est vraiécriture visible,client informéécriture suivante :horodatage > sincertitude : 2εrègle de démarragechoisir sattente de validationcause
Le temps s’écoule de gauche à droite, puis vers le bas jusqu’à l’écriture suivante. Laisser passer l’incertitude garantit que s appartient au passé avant que quiconque puisse agir sur l’écriture.

Remarquez la dernière étape : tout ce que l’écriture provoque commence après que le client a été informé, donc après que s est passé de façon certaine ; son propre TT.now().latest, et donc son horodatage, est ainsi supérieur à s. C’est la cohérence externe, payée par quelques millisecondes d’attente par écriture. Le §5 de l’article sur Zanzibar le résume : Zanzibar « builds on Spanner’s TrueTime abstraction » (s’appuie sur l’abstraction TrueTime de Spanner) pour « provide linearizable commit timestamps encoded as zookies » (fournir des horodatages de validation linéarisables encodés sous forme de zookies).

Le même article explique pourquoi Zanzibar ne peut pas utiliser une horloge logique à la place : les horloges de Lamport « require explicit participation of all ‘processes’, where in Zanzibar’s use cases some of the ‘processes’ can be external clients or even human users » (exigent la participation explicite de tous les “processus”, alors que dans les cas d’usage de Zanzibar certains de ces “processus” peuvent être des clients externes, voire des utilisateurs humains) (§5). Dans l’exemple A, la flèche « demande » représente Alice qui parle à Charlie, un canal qu’aucune horloge ne voit.

Le protocole zookie

Des lectures d’instantané à un horodatage bien ordonné résolvent l’exemple A. L’exemple B exige en outre que la vérification soit suffisamment fraîche. Une possibilité serait d’évaluer chaque vérification sur le dernier instantané, mais le §2.2 l’écarte : cela « would require global data synchronization with high-latency round trips and limited availability » (nécessiterait une synchronisation globale des données, avec des allers-retours à forte latence et une disponibilité limitée). C’est plutôt le client qui transporte lui-même la fraîcheur requise, sous forme de zookie : « an opaque byte sequence encoding a globally meaningful timestamp that reflects an ACL write, a client content version, or a read snapshot » (une séquence d’octets opaque encodant un horodatage ayant un sens global, qui reflète une écriture d’ACL, une version de contenu d’un client ou un instantané de lecture) (§2.4).

Qui détient le zookie à chaque étape ? Dans la figure, Anne enregistre une modification de doc:readme, puis Beto l’ouvre plus tard.

Le protocole zookie1. Anne enregistre une modification ; l’application cliente envoie à Zanzibar une vérification de modification de contenu, que Zanzibar évalue sur le dernier instantané dans Spanner. 2. Zanzibar répond « autorisé » avec un zookie dont l’horodatage est postérieur à toutes les écritures d’ACL antérieures. 3. L’application écrit le nouveau contenu et le zookie dans son propre stockage en une seule écriture atomique. 4. Plus tard, Beto ouvre le readme ; l’application charge le contenu et son zookie. 5. L’application envoie une vérification qui transporte le zookie. 6. Zanzibar l’évalue sur un instantané au moins aussi frais que le zookie et renvoie la réponse.tempsapp clientestockage clientZanzibarSpannersans zookiezookie zatomiquecharger v2, ztransporte zAnne enregistrevérification demodif. de contenuévaluer sur ledernier instantanédernier instantanéautorisé +zookie zreçoit zécrire v2 + zreadme v2, zBeto ouvrele readmecheck(Beto, z)évaluer surinstantané ≥ zlecture àT ≥ zréponse surcet instantanéafficher oumasquer v2
Le zookie est émis par la vérification de modification de contenu, stocké à côté du contenu et renvoyé avec chaque vérification ultérieure de cette version.

Étape par étape, d’après le §2.2 et le §2.4.4 :

  1. Vérification de modification de contenu. Lorsqu’un utilisateur est sur le point d’enregistrer une modification, le client envoie une vérification de modification de contenu. Elle « does not carry a zookie and is evaluated at the latest snapshot » (ne transporte pas de zookie et est évaluée sur le dernier instantané) (§2.4.4).
  2. Émission du zookie. Si la modification est autorisée, la réponse inclut un zookie. Zanzibar « encodes a current global timestamp in the zookie and ensures that all prior ACL writes have lower timestamps » (encode un horodatage global courant dans le zookie et garantit que toutes les écritures d’ACL antérieures ont des horodatages inférieurs) (§2.2).
  3. Stockage avec le contenu. « The client stores the zookie with the content change in an atomic write to the client storage » (Le client stocke le zookie avec la modification du contenu, au moyen d’une écriture atomique dans le stockage du client) (§2.2). La vérification elle-même n’a pas besoin de faire partie de la même transaction que l’écriture du contenu.
  4. Transport par les vérifications ultérieures. Chaque vérification ultérieure de cette version du contenu envoie le zookie stocké.
  5. Évaluation au moins aussi fraîche. « A check is always evaluated at a consistent snapshot no earlier than the given zookie » (Une vérification est toujours évaluée sur un instantané cohérent qui n’est pas antérieur au zookie fourni) (§2.4.4).

Dans l’exemple B, le zookie stocké avec le nouveau contenu encode T_B2, et T_B2 > T_B1 ; la vérification de Bob à l’étape 5 doit donc voir son retrait.

Le zookie est opaque à dessein. L’article utilise « an opaque cookie instead of the actual timestamp to discourage our clients from choosing arbitrary timestamps and to allow future extensions » (un cookie opaque plutôt que l’horodatage réel afin de dissuader nos clients de choisir des horodatages arbitraires et de permettre des extensions futures) (§2.4). Le §5 ajoute que le protocole « does not let clients read or evaluate ACLs at an arbitrary snapshot » (ne permet pas aux clients de lire ou d’évaluer des ACL sur un instantané arbitraire), ce qui laisse le choix à Zanzibar.

Pourquoi « au moins aussi frais » et non « exactement à »

Un zookie est une borne inférieure. Zanzibar peut évaluer une vérification à l’horodatage du zookie ou à n’importe quel horodatage ultérieur. Le §2.2 appelle cela la « at-least-as-fresh semantics » (sémantique “au moins aussi frais”) du protocole et indique qu’elle « allow[s] Zanzibar to choose any timestamp fresher than the one encoded in a zookie » (permet à Zanzibar de choisir n’importe quel horodatage plus frais que celui encodé dans un zookie). Cette liberté est exploitée de trois manières.

  • Obsolescence par défaut (§3.2.1). En l’absence de zookie, le serveur choisit « a default staleness chosen to ensure that all transactions are evaluated at a timestamp that is as recent as possible without impacting latency » (une obsolescence par défaut choisie pour garantir que toutes les transactions sont évaluées à un horodatage aussi récent que possible sans affecter la latence). Chaque serveur suit la fréquence à laquelle les lectures à une obsolescence donnée ont dû sortir de la zone, et déplace la valeur par défaut vers « the lowest ‘safe’ value » (la plus basse valeur “sûre”). L’article note que cela « is purely a performance optimization » (est purement une optimisation des performances), car « Zanzibar always respects zookies when provided » (Zanzibar respecte toujours les zookies lorsqu’ils sont fournis).
  • Quantification (§3.2.5). Les horodatages d’évaluation sont « rounded up to a coarse granularity, such as one or ten seconds, while respecting staleness constraints from request zookies » (arrondis vers le haut à une granularité grossière, comme une ou dix secondes, tout en respectant les contraintes d’obsolescence issues des zookies des requêtes). Arrondir vers le haut ne viole jamais une borne inférieure.
  • Caches partagés (§3.2.5). Les clés de cache contiennent l’horodatage de l’instantané ; des résultats issus d’instantanés différents ne sont donc jamais mélangés. Grâce à l’arrondi, « the vast majority of recent checks and reads » (la grande majorité des vérifications et lectures récentes) sont évaluées aux mêmes horodatages et « share cache results » (partagent les résultats en cache).

Que gagne-t-on à arrondir vers le haut lorsque trois vérifications arrivent avec des zookies espacés de quelques centaines de millisecondes ?

Arrondir vers le haut les horodatages d’évaluationTrois vérifications, pour Anne, Beto et Chen sur doc:readme, transportent des zookies dont les horodatages en microsecondes diffèrent mais tombent dans la même seconde. Zanzibar arrondit chacun vers le haut au même horodatage grossier T_q, qui est au moins égal à chaque zookie ; les trois sont donc évaluées sur un seul instantané et partagent les entrées de cache indexées par T_q. Tout horodatage ultérieur, jusqu’aux données les plus récentes chez le leader, serait également autorisé.vérif. d’Annezookie 12.104 svérif. de Betozookie 12.380 svérif. de Chenzookie 12.911 sévaluer àT_q = 13 sla clé de cacheinclut T_qdonnées les plusrécentes (leader)arrondiarrondipartagéaussi autorisé
Les trois zookies sont des bornes inférieures ; 13 s les satisfait toutes. Les horodatages sont illustratifs et ne proviennent pas de l’article.

Remarquez que T_q peut même se situer légèrement dans le futur. Le §3.2.5 traite ce cas : Spanner « ensures that a snapshot read at timestamp T will observe all writes up to T—this holds even if T is in the future, in which case the read will wait until TrueTime has moved past T. » (garantit qu’une lecture d’instantané à l’horodatage T observera toutes les écritures jusqu’à T ; cela vaut même si T est dans le futur, auquel cas la lecture attendra que TrueTime ait dépassé T.)

Requêtes Safe et Recent

Le prix de la fraîcheur, c’est la distance. « When a zookie timestamp is higher than that of the most recent data replicated to the region, the storage reads require cross-region round trips to the leader replica » (Lorsque l’horodatage d’un zookie est supérieur à celui des données les plus récentes répliquées dans la région, les lectures du stockage nécessitent des allers-retours entre régions vers la réplique leader) (§4.1). Le stockage réplique avec des « replication heartbeats with 8-second intervals » (pulsations de réplication à intervalles de 8 secondes) ; le §4.1 sépare donc les requêtes au seuil de 10 secondes :

  • Les requêtes Safe « have zookies more than 10 seconds old and can be served within the region most of time » (ont des zookies de plus de 10 secondes et peuvent être servies dans la région la plupart du temps).
  • Les requêtes Recent « have zookies less than 10 seconds old and often require inter-region round trips » (ont des zookies de moins de 10 secondes et nécessitent souvent des allers-retours entre régions).

Les 8 secondes correspondent à l’article sur Spanner, où « a leader by default advances MinNextTS() values every 8 seconds » (un leader fait avancer par défaut les valeurs de MinNextTS() toutes les 8 secondes), de sorte que les répliques « can serve reads at timestamps greater than 8 seconds old in the worst case » (peuvent servir, dans le pire des cas, des lectures à des horodatages datant de plus de 8 secondes) (Spanner §4.2.1).

Le tableau 2 de l’article (§4.2) donne la latence de chaque type, en millisecondes, sous forme de moyenne (écart type) sur une période de 7 jours en décembre 2018 :

API 50e centile 95e centile 99e centile
Safe Check 3.0 (0.091) 9.46 (0.3) 15.0 (1.19)
Safe Read 2.18 (0.031) 3.71 (0.094) 8.03 (3.28)
Safe Expand 4.27 (0.313) 8.84 (0.586) 34.1 (4.35)
Recent Check 2.86 (0.087) 60.0 (2.1) 76.3 (2.59)
Recent Read 2.21 (0.054) 40.1 (2.03) 86.2 (3.84)
Recent Expand 5.79 (0.224) 45.6 (3.44) 121.0 (2.38)
Recent Write 127.0 (3.65) 233.0 (23.0) 401.0 (133.0)

Les médianes sont proches ; les queues ne le sont pas. Le 95e centile d’un Check Recent est de 60.0 ms contre 9.46 ms pour un Check Safe : c’est le coût de l’aller-retour entre régions. Les écritures sont les plus lentes parce qu’elles « always require distributed coordination among Spanner servers » (nécessitent toujours une coordination distribuée entre les serveurs Spanner) (§4.2) ; dans Spanner, cette coordination inclut l’attente de validation. D’après le §4.1 et la figure 3, les requêtes Safe sont plus nombreuses que les requêtes Recent d’« about two orders of magnitude » (environ deux ordres de grandeur), « which allows Zanzibar to serve the vast majority of ACL checks locally » (ce qui permet à Zanzibar de servir localement la grande majorité des vérifications d’ACL). La plupart des requêtes peuvent être Safe parce qu’un zookie n’est qu’une borne inférieure : une vérification portant sur un contenu plus ancien peut utiliser des données plus anciennes, déjà répliquées.

Sources