guide:glossary@fr

Guides

Glossaire

Chaque terme que le lecteur rencontre dans l’article sur Zanzibar, en mots simples, avec un renvoi à la page du guide et à la section de l’article qui l’expliquent.

Faits vérifiés le

Les termes sont classés par ordre alphabétique de leur forme anglaise, indiquée entre parenthèses lorsque le terme français diffère. Les noms de code du langage de configuration de l’article (_this, computed_userset, tuple_to_userset) sont classés sans leurs tirets bas. Les exemples reprennent l’exemple suivi : Anne, Beto et Chen ; doc:readme dans folder:A ; group:eng.

A–C

ACL
Liste de contrôle d’accès (access control list) : l’ensemble des utilisateurs autorisés à effectuer une action sur un objet. Dans Zanzibar, une ACL n’est pas stockée sous la forme d’une liste unique, mais sous la forme de nombreux tuples de relation. Pour en savoir plus : Modèles de contrôle d’accès, §1, §2.1.
aclserver
Le principal type de serveur de Zanzibar. Il répond aux requêtes Check, Read, Expand et Write, et répartit le travail sur d’autres aclservers de son cluster. Pour en savoir plus : Architecture, §3.
au moins aussi frais (at-least-as-fresh)
La règle associée à un zookie : Zanzibar peut évaluer à n’importe quel instantané qui n’est pas plus ancien que l’horodatage du zookie, et pas seulement à cet horodatage précis. C’est cette liberté qui lui permet de servir la plupart des requêtes à partir de répliques locales. Pour en savoir plus : Cohérence, §2.2.
obsolescence bornée (bounded staleness)
Une lecture d’instantané peut être plus ancienne que « maintenant », mais pas plus ancienne qu’une borne. Dans Zanzibar, la borne est le zookie envoyé par le client. Spanner l’offre directement : le client fournit une borne supérieure d’obsolescence et Spanner choisit l’horodatage (article sur Spanner, §4.1). Pour en savoir plus : Cohérence, §2.2.
ruée sur le cache (cache stampede)
De nombreuses requêtes simultanées portant sur le même résultat absent du cache s’adressent toutes en même temps au stockage avant que le cache ne soit rempli. Zanzibar l’empêche au moyen d’une table de verrous. L’article cite l’article de Wikipédia pour ce terme (référence [3]). Pour en savoir plus : Architecture, §3.2.5.
journal des modifications (changelog)
Une base de données Spanner qui contient l’historique des mises à jour de tuples, écrite dans la même transaction que chaque écriture de tuple. Watch lit à partir de celle-ci. Pour en savoir plus : Architecture, §3.1.2.
Check
L’appel d’API qui demande si un utilisateur appartient à un userset ⟨object#relation⟩, par exemple « Chen est-il lecteur de doc:readme ? ». Il est évalué à un instantané qui n’est pas antérieur au zookie fourni. Pour en savoir plus : Tuples de relation, §2.4.4, §3.2.3.
computed_userset
Une feuille de règle de réécriture qui prend le userset d’une autre relation sur le même objet, par exemple « tout éditeur est lecteur ». Pour en savoir plus : Tuples de relation, §2.3.1.
hachage cohérent (consistent hashing)
Une manière d’attribuer des clés à des serveurs de sorte que l’ajout ou le retrait d’un serveur ne déplace qu’une petite fraction des clés. Zanzibar l’utilise pour répartir les entrées de cache sur les serveurs d’un cluster. Introduit par Karger et al. (STOC 1997) pour les caches web. Pour en savoir plus : Architecture, §3.2.5.
vérification de modification de contenu (content-change check)
Une requête Check envoyée lorsqu’un utilisateur est sur le point d’enregistrer un nouveau contenu. Elle ne porte aucun zookie, est évaluée au dernier instantané et renvoie un zookie que le client stocke avec la nouvelle version du contenu. Pour en savoir plus : Cohérence, §2.2, §2.4.4.

D–H

dénormalisation (denormalization)
Le fait de stocker une copie précalculée de données dérivées, telles que les appartenances aplaties de groupe à groupe, au lieu de les calculer à partir des lignes d’origine. Zanzibar l’évite dans le stockage et ne l’utilise que dans Leopard. Pour en savoir plus : Leopard, §3.2.4, §3.2.5.
exclusion
Un opérateur de règle de réécriture : les utilisateurs qui appartiennent à un userset mais pas à un autre. Pour en savoir plus : Tuples de relation, §2.3.1.
Expand
L’appel d’API qui renvoie le userset effectif de ⟨object#relation⟩ sous la forme d’un arbre, en suivant les règles de réécriture. Les feuilles sont des identifiants d’utilisateurs ou des usersets ; les nœuds intérieurs sont des unions, des intersections ou des exclusions. Pour en savoir plus : Tuples de relation, §2.4.5.
cohérence externe (external consistency)
Si la mise à jour x se produit avant la mise à jour y, x reçoit un horodatage inférieur à celui de y, même lorsque les deux sont coordonnées en dehors du système. Zanzibar obtient cette propriété de Spanner. L’article cite la thèse de Gifford soutenue à Stanford en 1981 pour ce terme (référence [18]) ; Spanner l’énonce ainsi : si T1 est validée avant que T2 ne commence, l’horodatage de validation de T1 est inférieur à celui de T2. Pour en savoir plus : Cohérence, §2.2.
éventail de requêtes (fan-out)
Une requête qui se transforme en de nombreuses sous-requêtes, par exemple un aclserver qui envoie des parties d’une requête Check à d’autres serveurs de son cluster. Pour en savoir plus : Architecture, §3, §3.2.5.
zookie de pulsation (heartbeat zookie)
Un zookie présent dans chaque réponse Watch, qui indique jusqu’où le flux est parvenu, afin que le client puisse reprendre à partir de ce point. Pour en savoir plus : §2.4.3.
requêtes de couverture (hedging)
Le fait d’envoyer la même requête à un second serveur dès que l’on sait que le premier est lent, d’utiliser la réponse qui arrive en premier et d’annuler l’autre. Zanzibar applique cette technique aux appels vers Spanner et Leopard, mais pas aux appels entre ses propres serveurs. La technique est décrite dans Dean et Barroso, « The Tail at Scale » (CACM, 2013). Pour en savoir plus : Architecture, §3.2.7.
point chaud (hot spot)
Une clé, un objet ou un groupe qui reçoit beaucoup plus de trafic que les autres et peut surcharger le serveur qui le stocke, par exemple un groupe populaire partagé par de nombreuses ACL. Pour en savoir plus : Architecture, §3.2.5.

I–N

intersection
Un opérateur de règle de réécriture : les utilisateurs qui appartiennent à chacun de plusieurs usersets. Pour en savoir plus : Tuples de relation, §2.3.1.
Leopard
Un système d’indexation destiné aux groupes profondément imbriqués ou très larges. Il aplatit l’appartenance aux groupes en ensembles d’entiers, de sorte qu’une vérification d’appartenance devient une intersection d’ensembles, et se tient à jour grâce à Watch. Pour en savoir plus : Leopard, §3.2.4.
table de verrous (lock table)
Une table, propre à chaque serveur, des lectures et vérifications en cours. Parmi les requêtes qui partagent une clé de cache, une seule s’exécute ; les autres attendent son résultat. Pour en savoir plus : Architecture, §3.2.5.
tuple de verrou (lock tuple)
Un tuple de relation ordinaire que les clients modifient à chaque écriture sur un objet, afin qu’une écriture puisse être conditionnée au fait que personne d’autre n’a écrit depuis la lecture. Pour en savoir plus : §2.4.2.
espace de noms (namespace)
Un type d’objet défini par le client, tel que doc ou folder. C’est la partie qui précède les deux-points dans doc:readme. Les tuples de chaque espace de noms résident dans leur propre base de données. Pour en savoir plus : Tuples de relation, §2.1, §2.3, §3.1.1.
configuration d’espace de noms (namespace config)
La configuration d’un espace de noms : ses relations, chacune dotée d’une règle de réécriture de userset facultative, ainsi que des paramètres de stockage tels que la fragmentation. Pour en savoir plus : Tuples de relation, §2.3, §3.1.3.
problème du « nouvel ennemi » (new enemy problem)
Le fait de montrer un contenu à une personne qui a été retirée de son ACL, parce que la vérification a ignoré l’ordre de deux modifications d’ACL ou a appliqué une ACL plus ancienne que le contenu. Pour en savoir plus : Cohérence, §2.2.

O–R

objet (object)
La chose protégée, notée ⟨namespace⟩:⟨object_id⟩, par exemple doc:readme. Pour en savoir plus : Tuples de relation, §2.1.
Paxos
Un protocole de consensus qui permet à un groupe de répliques de s’accorder sur chaque écriture même si certaines d’entre elles tombent en panne. L’article place les cinq répliques votantes du stockage de Zanzibar à moins de 25 ms les unes des autres afin que les transactions Paxos soient validées rapidement. Voir Lamport, « Paxos Made Simple » (2001). Pour en savoir plus : Architecture, §3.1.4.
poursuite de pointeurs (pointer chasing)
Le fait de répondre à une requête Check en suivant les usersets un saut à la fois : des lecteurs du readme vers group:eng#member, puis vers les membres de ce groupe, et ainsi de suite. Lent lorsque les groupes sont profonds ou larges. Pour en savoir plus : Tuples de relation, Leopard, §3.2.3, §3.2.4.
Read
L’appel d’API qui renvoie les tuples stockés correspondant à un ou plusieurs ensembles de tuples. Il n’applique pas les règles de réécriture. Pour en savoir plus : Tuples de relation, §2.4.1.
requête Recent (Recent request)
Voir requêtes Safe / Recent. Pour en savoir plus : Cohérence, §4.1.
relation
Une relation nommée entre un objet et un utilisateur, ou entre deux objets (comme parent relie un document à son dossier), par exemple owner, viewer, member ou parent. Définie dans la configuration d’espace de noms. Pour en savoir plus : Tuples de relation, §2.1, §2.3.
tuple de relation (relation tuple)
Un fait stocké, ⟨object⟩#⟨relation⟩@⟨user⟩, par exemple doc:readme#owner@user:anne. C’est le seul type de données de permission que Zanzibar stocke. Pour en savoir plus : Tuples de relation, §2.1.
réplique (replica)
Une copie des données en un lieu donné. Les données de Zanzibar sont répliquées dans des dizaines de lieux afin que la plupart des lectures puissent être servies à proximité. Pour en savoir plus : Architecture, §3.1.4.

S

requêtes Safe / Recent (Safe / Recent requests)
La répartition des requêtes selon l’âge de leur zookie, telle que la propose l’article. Les requêtes Safe portent des zookies datant de plus de 10 secondes et peuvent généralement être servies dans la région ; les requêtes Recent portent des zookies plus récents et nécessitent souvent un aller-retour entre régions. Pour en savoir plus : Cohérence, §4.1.
fragment (shard)
Une tranche d’une base de données ou d’un index, stockée et servie séparément. L’identifiant de fragment d’un tuple provient généralement de son identifiant d’objet et, pour les très grands groupes, de l’identifiant d’objet et de l’utilisateur. Pour en savoir plus : Architecture, §3.1.1, §3.2.4.
lecture d’instantané (snapshot read)
Une lecture qui voit la base de données exactement telle qu’elle était à un horodatage donné : toutes les écritures effectuées à cet horodatage ou avant, et aucune après. Zanzibar évalue chaque requête Check à un instantané unique. Spanner la définit comme « a read in the past that executes without locking » (une lecture dans le passé qui s’exécute sans verrouillage) (article sur Spanner, §4.1). Pour en savoir plus : Cohérence, §2.2.
Spanner
La base de données de Google distribuée à l’échelle mondiale. Zanzibar y stocke les tuples, les configurations d’espaces de noms et le journal des modifications, et s’appuie sur ses horodatages pour la cohérence. Décrite dans Corbett et al., OSDI 2012. Pour en savoir plus : Cohérence, Architecture, §2.2, §3.

T

latence de queue (tail latency)
La latence des requêtes les plus lentes, par exemple au 99e ou au 99.9e centile. Elle compte parce qu’une seule page de résultats de recherche peut nécessiter des dizaines à des centaines de vérifications. Voir Dean et Barroso, « The Tail at Scale » (CACM, 2013). Pour en savoir plus : Architecture, §1, §3.2.7, §4.2, §4.5.
_this
La feuille de règle de réécriture qui renvoie les utilisateurs figurant dans les tuples stockés pour cet objet et cette relation, y compris les usersets vers lesquels ces tuples pointent. C’est le comportement par défaut lorsqu’une relation n’a pas de règle. Pour en savoir plus : Tuples de relation, §2.3.1.
quantification des horodatages (timestamp quantization)
Le fait d’arrondir vers le haut les horodatages d’évaluation à un pas grossier, par exemple une ou dix secondes, afin que de nombreuses requêtes partagent un horodatage et donc des entrées de cache. Cela n’affaiblit pas la cohérence : un zookie ne fixe qu’une borne inférieure, et une lecture d’instantané Spanner à un horodatage futur attend que TrueTime l’ait dépassé (§3.2.5). Pour en savoir plus : Architecture, Cohérence, §2.2, §3.2.5.
TrueTime
Le mécanisme d’horloge de Spanner, qui attribue à chaque écriture un horodatage à la résolution de la microseconde reflétant l’ordre causal. C’est ce qui donne un sens aux horodatages de Zanzibar. TT.now() renvoie un intervalle dont il est garanti qu’il contient l’heure réelle ; voir l’article sur Spanner (OSDI 2012), §3. Pour en savoir plus : Cohérence, §2.2, §3.2.5.
ensemble de tuples (tupleset)
Un sélecteur de tuples stockés : une seule clé de tuple, ou tous les tuples d’un identifiant d’objet ou d’un userset, éventuellement restreints à une relation. Utilisé par Read et par tuple_to_userset. Pour en savoir plus : Tuples de relation, §2.4.1.
tuple_to_userset
Une feuille de règle de réécriture qui lit certains tuples de l’objet et calcule un userset à partir de chacun, par exemple « rechercher le dossier parent du readme et prendre ses lecteurs ». Pour en savoir plus : Tuples de relation, §2.3.1.

U–W

union
Un opérateur de règle de réécriture : les utilisateurs qui appartiennent à l’un quelconque de plusieurs usersets. Les trois branches de viewer dans la figure 1 de l’article sont réunies par une union. Pour en savoir plus : Tuples de relation, §2.3.1.
utilisateur (user)
La troisième partie d’un tuple : soit un identifiant d’utilisateur unique, soit un userset. Pour en savoir plus : Tuples de relation, §2.1.
userset
Une paire ⟨object⟩#⟨relation⟩ qui représente tous les utilisateurs ayant cette relation avec cet objet, par exemple group:eng#member. Elle permet à un tuple d’accorder un accès à un groupe, et aux groupes de contenir des groupes. Pour en savoir plus : Tuples de relation, §2.1.
règle de réécriture de userset (userset rewrite rule)
Une partie d’une configuration de relation : une fonction qui associe à un identifiant d’objet un arbre d’expression de userset, construit à partir de _this, computed_userset et tuple_to_userset combinés par union, intersection et exclusion. Pour en savoir plus : Tuples de relation, §2.3.1.
arbre de userset (userset tree)
Le résultat d’Expand : les feuilles sont des identifiants d’utilisateurs ou des usersets, les nœuds intérieurs sont des opérateurs ensemblistes. Pour en savoir plus : Tuples de relation, §2.4.5.
Watch
L’appel d’API qui diffuse en flux les modifications de tuples d’un ou plusieurs espaces de noms dans l’ordre des horodatages, à partir d’un zookie. Il sert à tenir à jour des index secondaires, tels que Leopard. Pour en savoir plus : Architecture, §2.4.3.
watchserver
Le type de serveur qui répond aux requêtes Watch en suivant le journal des modifications. Pour en savoir plus : Architecture, §3.
Write
L’appel d’API qui ajoute ou supprime des tuples. Les clients qui réécrivent tous les tuples d’un objet effectuent une lecture, puis une écriture conditionnée au fait que le tuple de verrou n’a pas changé. Pour en savoir plus : Architecture (ce qu’une écriture touche), §2.4.2.

Z

zookie
Un jeton opaque qui encode un horodatage. Un client en obtient un au moyen d’une vérification de modification de contenu (les réponses Read et Write portent également des zookies), le stocke avec le contenu et l’envoie avec les vérifications ultérieures afin qu’elles soient évaluées à un instantané au moins aussi frais. Pour en savoir plus : Cohérence, §2.2, §2.4.

Sources

  • 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 et 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 », thèse de doctorat, Stanford University, 1981 (référence [18] de l’article ; aucune copie en ligne vérifiée)
  • « Cache stampede », Wikipédia, en.wikipedia.org (la source citée par l’article)
  • Ruoming Pang et al., « Zanzibar: Google’s Consistent, Global Authorization System », USENIX ATC ’19, usenix.org/conference/atc19/presentation/pang