Modèles de cohérence et théorème CAP

Les modèles de cohérence définissent les garanties qu'un système répliqué offre quant aux valeurs renvoyées par les lectures, et le théorème CAP délimite lesquelles de ces garanties peuvent coexister avec la disponibilité en présence de partitions réseau.

Definition

Un modèle de cohérence est un contrat entre un magasin de données répliqué et ses clients, spécifiant les résultats admissibles des lectures et écritures concurrentes ; le théorème CAP stipule qu'en présence d'une partition réseau, un magasin de données distribué ne peut pas offrir à la fois une cohérence linéarisable et une disponibilité.

Scope

Ce sujet aborde les modèles de cohérence formels — linéarisabilité, cohérence séquentielle, cohérence causale et cohérence éventuelle — et leur classement par force ; le théorème CAP, son énoncé précis et sa preuve ; ainsi que des raffinements tels que PACELC qui tiennent également compte du compromis latence-cohérence en l'absence de partitions. Il fournit le vocabulaire nécessaire pour spécifier et comparer les garanties des systèmes répliqués.

Core questions

• En quoi la linéarisabilité, la cohérence séquentielle, causale et éventuelle diffèrent-elles en termes de force ?
• Que proscrit exactement le théorème CAP, et que permet-il ?
• Comment les considérations de latence affinent-elles le compromis de cohérence en l'absence de partition ?

Key theories

Linéarisabilité et cohérence séquentielle

La linéarisabilité exige que chaque opération semble prendre effet atomiquement à un instant donné entre son invocation et sa réponse, en accord avec le temps réel ; la cohérence séquentielle abandonne l'exigence de temps réel, ne demandant qu'un seul entrelacement légal respectant l'ordre de chaque processus.

Le théorème CAP

Gilbert et Lynch ont prouvé qu'aucun magasin de données répliqué ne peut garantir à la fois une cohérence linéarisable et une disponibilité lorsque le réseau peut perdre des messages entre les répliques, imposant un choix lors des partitions.

Raffinement PACELC

PACELC étend le théorème CAP en notant que même sans partition, un système échange la latence contre la cohérence ; ainsi, les conceptions sont caractérisées par leur comportement à la fois pendant les partitions et en fonctionnement normal.

Clinical relevance

Chaque base de données distribuée et service de stockage doit déclarer un modèle de cohérence, et les compromis CAP et PACELC expliquent pourquoi certains systèmes privilégient la disponibilité tandis que d'autres privilégient la cohérence ; leur compréhension est essentielle pour le choix et l'exploitation des infrastructures de données.

History

Lamport a défini la cohérence séquentielle en 1979 et Herlihy et Wing ont formalisé la linéarisabilité en 1990 ; Brewer a conjecturé le compromis CAP en 2000, Gilbert et Lynch l'ont prouvé en 2002, et le recadrage PACELC d'Abadi en 2012 a clarifié que la latence, et non seulement les partitions, influence les choix de cohérence.

Debates

Le théorème CAP est-il souvent mal interprété ?

Le théorème CAP est fréquemment résumé par « choisissez deux des trois », mais le résultat précis n'impose un choix cohérence-disponibilité qu'en cas de partition ; les critiques soutiennent que cette simplification excessive masque le compromis latence-cohérence quotidien plus pertinent, capturé par PACELC.

Key figures

• Eric Brewer
• Seth Gilbert
• Nancy Lynch
• Maurice Herlihy
• Jeannette Wing
• Leslie Lamport

Seminal works

• gilbert2002
• herlihy1990
• lamport1979

Frequently asked questions

Le théorème CAP signifie-t-il qu'un système ne peut jamais avoir que deux des trois propriétés : cohérence, disponibilité et tolérance aux partitions ?

Pas tout à fait. Les partitions sont une réalité des réseaux, non un choix de conception ; la véritable décision est donc de savoir quoi faire pendant une partition : sacrifier une forte cohérence pour rester disponible, ou sacrifier la disponibilité pour rester cohérent. En l'absence de partition, un système peut être à la fois cohérent et disponible.