Cohérence (données)

Le modèle de cohérence sans synchronisation le plus contraignant est celui qui correspond exactement à la "vue idéale" des données. Les modèles de cohérence exposés vont du plus contraignant au plus rapide (en temps d’exécution).

On parle de cohérence atomique, indivisible, stricte ou non-interruptible quand une lecture renvoie toujours le résultat de la dernière écriture effectuée, ce qui implique l'existence d'une base de temps globale. Ce modèle de cohérence est le plus fort qui soit[1].

On dit qu'il y a cohérence forte si à tout instant (i.e. en tout point d'observation) toutes les copies de données sont identiques. Une application concrète serait :

• Chaque requête de modification est estampillée et diffusée à tous.
• Les requêtes sont exécutées dans l'ordre des estampilles.

Hélas ce modèle de cohérence est très coûteux en ressource. La cohérence est assurée en toutes circonstances, même quand ce n'est pas nécessaire.

Le résultat de toute exécution est le même que si les opérations de tous les processus étaient exécutées dans un ordre séquentiel quelconque, et les opérations de chaque processus apparaîtraient dans cette séquence dans l'ordre spécifié par leur programme. En résumé il existe un ordre global (total) sur tous les accès à la mémoire qui préserve l'ordre programme[2].

• On impose un ordre total sur les écritures.
• Les lectures locales à chaque processus lisent la dernière valeur écrite.

La cohérence immédiate est opposée à la cohérence à la longue. L’opération d’écriture est finalisée seulement lorsque tous les processus ou nœuds ont été synchronisés. Exposant cette nouvelle valeur au même moment. Il existe deux grandes solutions de cohérence immédiate :

• (en) Two phase commit protocol (2PC) sur wikipédia en anglais
• Read Your Writes (RYW)

Modèle plus faible que la cohérence séquentielle, car on ne considère que des évènements reliés par une relation de causalité[3]. Un modèle de cohérence est causal s'il garantit les deux conditions suivantes :

• Les opérations d'écriture potentiellement causalement liées doivent être perçues par tous les processus dans le même ordre.
• Les opérations d'écriture non causalement liées peuvent être perçues dans des ordres différents, sur des processus différents.

Considérons l'exemple suivant. On suppose que le processus P1 écrit dans la variable X. Ensuite P2 lit X et écrit Y. Ici, la lecture de X et l’écriture de Y par P2 sont potentiellement liée causalement car l'écriture de Y peut dépendre de la valeur de X.

La cohérence causale peut encore être affaiblie, si on ne considère la causalité qu'à l'intérieur d'un seul processus, non entre processus différents. La cohérence PRAM (pipelined RAM due à Lipton et Sandberg) spécifie quant à elle que les écritures d'un même processus sont vues par les autres dans l'ordre où elles sont faites. En revanche, il n'y a pas de contrainte sur l'ordre dans lequel apparaissent celles de processus différents[4].

Si les écritures sur un même objet (dans une base de données) ou à un même emplacement en mémoire sont vues dans un même ordre par tous les acteurs ; on parle respectivement de cohérence objet et de cohérence cache – c'est une cohérence « naturelle » lorsqu'on utilise un protocole de cohérence de cache. Lorsque ce modèle est associé à la cohérence PRAM, on parle de cohérence processeur.

Le modèle de cohérence à terme (anglais: eventual consistency) requiert, d'une part que les écritures d'un processus soient vues par les autres inéluctablement, mais sans date limite ni contrainte d'ordre ; et d'autre part que lorsque les mises à jour s'arrêtent, tous les processus observent le même état. C'est le modèle de cohérence le plus faible utilisé en pratique.

Comme cette approche permet les écritures concurrentes, le système doit résoudre les conflits. Pour cela il y a trois solutions:

• Réparation à la lecture : la résolution d'un conflit a lieu lors d'un accès en lecture qui constate le conflit. Cela ralentit les opérations de lecture.
• Réparation à l’écriture : la résolution d'un conflit prend place lors d'une écriture qui constate le conflit. Cela ralentit les opérations d’écriture.
• Réparation asynchrone : résolution par un processus de fond interne, ne faisant pas partie d'une opération de lecture ou d'écriture d'un client.

En fait, il n'est pas toujours nécessaire d'assurer la cohérence à tout instant. D'où l'idée de la forcer uniquement lorsqu'elle est nécessaire, à l'aide de variables et d'opérations de synchronisation. Dans ces modèles, des instructions de synchronisation permettent d'appliquer temporairement une cohérence plus forte. Ces instructions sont généralement des « barrières », qui assurent que les accès précédents ont été rendus visibles de tous les acteurs. Ceci permet de spécifier de manière fine les variables à protéger, en utilisant des informations sur les accès prévus. La motivation est de réduire le nombre d'opérations de mise en cohérence.

En cohérence faible, on distingue les accès normaux et les opérations de synchronisation. Les accès non synchronisés n'imposent pas de contraintes particulières. En revanche, les synchronisations imposent que tous les accès précédents se soient terminés (que les lectures soient faites et que les écritures aient été rendues visibles à tous les acteurs), et que de nouveaux accès attendent la fin des instructions de synchronisation qui, elles, suivent un modèle de cohérence séquentielle [5].

Le programmeur ou le compilateur a la charge de placer des instructions de synchronisation pour assurer la cohérence lorsqu'elle est nécessaire.

La cohérence au relâchement est similaire à la cohérence faible, mais elle est sujet a deux opérations : le verrouillage et déverrouillage pour la synchronisation. Avant de modifier un objet en mémoire il faut acquérir celui-ci par verrouillage, pour ensuite le déverrouiller. Les modifications qui se situent entre ces deux opérations sont effectuées en "région critique"[6].

Un modèle de cohérence est au relâchement s'il garantit les trois propriétés suivantes :

• Les opérations de synchronisation (verrouillage et déverrouillage) se font selon un modèle de cohérence processeur.
• Les opérations de lecture et d'écriture ne peuvent se faire que si toutes les opérations d'acquisition précédentes sont terminées sur tous les sites.
• L'opération de relâchement ne peut se terminer que si toutes les opérations d'écriture et de lecture sont terminées sur tous les sites.

La cohérence à l'entrée est voisine de la cohérence au relâchement. La différence est que toute variable modifiée indépendamment doit être associée à un verrou spécifique. Lors de l’opération de verrouillage, seules les variables associées au verrou utilisé sont mises à jour [7].

Formellement, une cohérence à l'entrée nécessite trois conditions :

• Le verrouillage d'une variable de synchronisation n'est permis que lorsque toutes les modifications sur la section gardée ont été effectuées.
• Avant le verrouillage d'une variable de synchronisation, aucune autre entité ne doit manipuler la variable.
• Après le déverrouillage d'une variable de synchronisation, les prochains accès devront respecter les deux étapes précédentes.

La cohérence delta synchronise l’ensemble du système à intervalle de temps régulier. Autrement dit, le résultat d'une lecture mémoire est cohérent à l'exception d'un courte période de temps où la synchronisation n'a pas encore été effectuée. Donc si un espace mémoire a été modifié, pendant une courte période les accès en lecture seront inconsistants. Il faudra attendre que la synchronisation soit effectuée.

Ce modèle de cohérence est conçu pour minimiser le temps d’accès vers les données proches d'une source. Typiquement il peut être utilisé dans un environnement tel qu'un jeu vidéo pour minimiser la bande passante[8]. En effet les joueurs ont besoin de connaitre certaines informations de façon plus rapide et fiable au fur et à mesure que se rapproche la position ciblée. Cela nécessite un schéma multidimensionnel basé sur un champ de vecteurs utilisés pour maintenir la cohérence. La cohérence par champ de vecteur émane de champs générateurs couplés à des pivots (le joueur). L’intensité du champ diminuant au fur et à mesure de l’accroissement de la distance.

• (en) David Mosberger, « Memory Consistency Models », ACM SIGOPS Operating Systems Review,‎ 1993, p. 18-26 (DOI 10.1145/160551.160553)
• (en) Sarita V. Adve et Kourosh Gharachorloo, « Shared Memory Consistency Models: A Tutorial », Research Report 95/7,‎ septembre 1995, p. 28 (DOI 10.1109/2.546611)
• (en) Ali Sezgin, Formalization and verification of shared memory, The University of Utah, 2004, p. 120
• (en) Haifeng Yu et Amin Vahdat, « Design and Evaluation of a Continuous Consistency Model for Replicated Services », OSDI'00 Proceedings of the 4th conference on Symposium on Operating System Design & Implementation - Volume 4,‎ 2000, p. 21 (DOI 10.1145/566340.566342)
• (en) Robert C. Steinke et Gary J. Nutt, « A Unified Theory of Shared Memory Consistency », Journal of the ACM, vol. 51, n^o 5,‎ 2002, p. 50 (DOI 10.1145/1017460.1017464)
• (en) Suiping Zhou et Haifeng Shen, « A Consistency Model for Highly Interactive Multi-player Online Game », dans Simulation Symposium, 2007. ANSS '07. 40th Annual, IEEE, 28 mars 2007 (DOI 10.1109/ANSS.2007.5), p. 318-323
• (en) Zhiyuan Zhan, Mustaque Ahamad et Micheal Raynal, « Mixed Consistency Model: Meeting Data Sharing Needs of Heterogeneous Users », dans Distributed Computing Systems, 2005. ICDCS 2005. Proceedings. 25th IEEE International Conference on, IEEE, juin 2005 (DOI 10.1109/ICDCS.2005.49), p. 209-218
• (en) Leslie Lamport, « How to make a multiprocessor computer that correctly executes », IEEE Transactions on Computers, C-28(9),‎ 1979, p. 690–691
• (en) P. W. Hutto et M. Ahamad, « Weakening consistency to enhance concurrency in distributed shared memories », In Proceedings of the 10th International Conference on Distributed Computing Systems,‎ 1990, p. 302–311
• (en) R. J. Lipton et J. S. Sandberg, « A scalable shared memory », Technical Report CS-TR-180-88, Princeton University,‎ 1988
• (en) James R. Goodman, « Cache consistency and sequential consistency », Technical Report 61, SCI Committee,‎ 1989
• (en) M. Dubois, C. Scheurich et F.A. Briggs, « Memory access buffering in multiprocessors », In Proceedings of the Thirteenth Annual International Symposium on Computer Architecture,‎ 1986, p. 434–442
• (en) K. Gharachorloo, D. Lenoski et J. Laudon, « Memory consistency and event ordering in scalable shared-memory multiprocessors », Computer Architecture News,‎ 1990, p. 15–26
• (en) N. Bershad et J. Zekauskas, « Midway: Shared memory parallel programming with entry consistency for distributed memory multiprocessors », Technical Report CMU-CS-91-170, CarnegieMellon University,‎ 1991

• Modèles de cohérence, Stéphane Drapeau
• Modèles et protocoles de cohérence des données en environnement volatil, Loïc Cudennec

• Portail de l’informatique
• Portail des bases de données