In Spanner, TrueTime & Le théorème CAP , Eric Brewer écrit:
Une chose subtile à propos de Spanner est quil obtient la sérialisabilité des verrous, mais il obtient cohérence externe (similaire à linéarisation ) de TrueTime [ emphase ajoutée ].
Quelle est la définition de la cohérence externe , et en quoi diffère-t-elle de la linéarisation ?
Commentaires
- Cest une excellente question, et jaurais aimé quEric lait élaboré un peu ici. Est-ce linéarisable ou non? 🙂
Réponse
La cohérence externe na pas de signification fixe. Dans ce contexte, elle a le signifiant apparaissant dans la phrase suivante du document:
Pour deux transactions quelconques, $ T_1 $ et $ T_2 $ (même si sur les côtés opposés du globe): si $ T_2 $ commence à valider après que $ T_1 $ ait fini de valider, alors lhorodatage de $ T_2 $ est supérieur à lhorodatage de $ T_1 $.
Commentaires
- Plus jy pense, cela ressemble beaucoup à la linéarisation pour moi car toutes les transactions sont ordonnées. Malheureusement, ces termes sont parfois subtils. .. Quelquun nest pas daccord? Je veux dire, les transactions sont sérialisables, et elles sont totalement ordonnées en fonction de lheure de validation. Peut-être que la subtilité réside dans la façon dont 2PC est implémenté dans Spanner?
- @Bminer La linéarisation est un modèle de cohérence qui sapplique uniquement aux objets uniques, où les transactions peuvent impliquer plusieurs o bjects.
- @LorinHochstein – Ha! Cela sent les mots hachés. Lintérêt de la terminologie est daider de vraies personnes à conceptualiser les garanties quelles obtiennent, en particulier en ce qui concerne les transactions. La linéarisation + la sérialisation est la meilleure garantie, et je pense que ' est ce à quoi la documentation Spanner fait référence avec le terme " cohérence externe. " Mais, cela pose la question: est-ce que quelquun sait vraiment quelle " cohérence externe " moyens? 🙂
Réponse
Vous pouvez penser à la cohérence externe à partir de lisolement des transactions (Tx) et du point de vue de lordre . Dans lisolement Tx, la cohérence externe est équivalente à lisolation sérialisable stricte, où « strict » est la partie contrainte en temps réel (comme dans la linéarisation).
Cela signifie encore une fois que pour un client système Tx observable Les effets secondaires sont équivalents à un système, où tous les Tx se déroulent de manière isolée sans aucune concurrence et où leur ordre en temps réel, tel que vu par le client, est préservé. Plus important encore, ce même ordre est vu par tout autre client indépendant.
En savoir plus sur la distinction sur ce blog .
Réponse
En mentionnant " cohérence externe " , Brewer fait référence à B. Liskov. Utilisations pratiques des horloges synchronisées dans les systèmes distribués . Principes ACM du calcul distribué (PODC). Montréal, Canada, août 1991.
Liskov, en terme, fait référence à Gifford D.K. Stockage dinformations dans un système informatique décentralisé . Rapport technique CSL-81-8, Xerox Corporation, mars 1983
Voici comment Gifford définit la cohérence externe:
Externe la cohérence garantit quune transaction recevra toujours les informations actuelles. En utilisant les concepts que nous venons dintroduire, nous pouvons fournir une définition formelle de la cohérence externe. Lordre temporel réel dans lequel les transactions se terminent définit un programme de série unique. Ce programme de série est appelé calendrier externe . On dit quun système fournit une cohérence externe sil garantit que le calendrier quil utilisera pour traiter un ensemble de transactions est équivalent à son calendrier externe.
Comme le mentionne @Oleg, cela ressemble à sérialisation stricte .