Le théorème CAP et les modèles de cohérence

Le théorème CAP stipule qu'un système de stockage de données distribué confronté à une partition réseau doit sacrifier soit la cohérence, soit la disponibilité, et les modèles de cohérence spécifient précisément les garanties qu'un système offre concernant la visibilité et l'ordonnancement des mises à jour.

Definition

Le théorème CAP affirme qu'un système de données partagées en réseau ne peut garantir simultanément au plus que deux des trois propriétés suivantes : la cohérence, la disponibilité et la tolérance aux partitions ; un modèle de cohérence est un contrat spécifiant ce qu'une application peut observer concernant l'ordre et la visibilité des lectures et des écritures sur les répliques.

Scope

Ce sujet aborde le théorème CAP et sa formalisation, l'interprétation pratique selon laquelle le véritable compromis n'apparaît qu'en cas de partitions réseau, et le raffinement PACELC qui en découle. Il couvre le spectre des modèles de cohérence — depuis la cohérence forte (linéarisable) en passant par la cohérence causale jusqu'à la cohérence éventuelle — ainsi que le style BASE qui contraste avec ACID. Il traite de la manière dont ces modèles guident la conception des systèmes de stockage de données répliqués. Il exclut les protocoles de consensus et de validation utilisés pour implémenter la cohérence forte, qui sont traités dans le cadre des bases de données distribuées.

Core questions

• Que signifient exactement la cohérence, la disponibilité et la tolérance aux partitions dans le cadre du théorème CAP ?
• Pourquoi le véritable choix entre cohérence et disponibilité n'est-il imposé qu'en cas de partition ?
• En quoi la cohérence forte, causale et éventuelle diffèrent-elles dans leurs garanties ?
• Que promet la cohérence éventuelle, et que ne promet-elle pas ?
• Comment la philosophie BASE contraste-t-elle avec ACID ?

Key concepts

• cohérence, disponibilité, tolérance aux partitions
• partition réseau
• linéarisabilité / cohérence forte
• cohérence causale
• cohérence éventuelle
• PACELC
• BASE versus ACID
• résolution des conflits

Key theories

Le théorème CAP

Formalisé par Gilbert et Lynch, le théorème CAP montre que lorsque le réseau est partitionné, un système de stockage répliqué doit choisir entre retourner des données potentiellement obsolètes (disponibilité) et refuser le service pour préserver une valeur unique et cohérente (cohérence) ; la tolérance aux partitions n'est pas facultative dans les réseaux réels.

Le spectre de la cohérence

Les modèles de cohérence vont de la cohérence forte (linéarisable), où les lectures voient toujours la dernière écriture, en passant par la cohérence causale, qui préserve l'ordre de cause à effet, jusqu'à la cohérence éventuelle, où les répliques convergent au fil du temps en l'absence de nouvelles écritures.

BASE versus ACID

Les systèmes hautement disponibles adoptent souvent un style BASE — basiquement disponible, état souple, éventuellement cohérent — relâchant délibérément les garanties fortes d'ACID pour rester réactifs en cas de partitions et à grande échelle.

Clinical relevance

Le théorème CAP et les modèles de cohérence encadrent le choix de conception central dans les systèmes de données distribués : si un système de stockage privilégie de toujours répondre (disponibilité) ou de toujours répondre correctement (cohérence) lorsque le réseau est défaillant, une décision qui façonne le comportement et les garanties de chaque application distribuée globalement.

History

Eric Brewer a émis l'hypothèse du compromis CAP vers 2000 ; Gilbert et Lynch l'ont prouvé formellement en 2002. Dynamo d'Amazon (2007) et l'essai de Vogels de 2009 ont popularisé la cohérence éventuelle en pratique. La rétrospective de Brewer de 2012 a clarifié que le CAP interdit une cohérence et une disponibilité parfaites uniquement pendant les partitions, et la formulation PACELC a ensuite ajouté le compromis latence-cohérence dans le cas sans partition.

Debates

Le caractère fondamental du compromis cohérence-disponibilité

Les premières interprétations considéraient le CAP comme imposant un choix permanent entre cohérence et disponibilité ; des analyses ultérieures, y compris la rétrospective de Brewer, soutiennent que le compromis n'intervient que pendant les partitions et que les systèmes peuvent être largement cohérents et disponibles autrement, reconfigurant ainsi la rigueur avec laquelle le CAP contraint la conception.

Key figures

• Eric Brewer
• Seth Gilbert
• Nancy Lynch
• Werner Vogels

Seminal works

• gilbert2002
• brewer2012
• vogels2009

Frequently asked questions

Le théorème CAP signifie-t-il que je ne peux avoir que deux des trois propriétés ?

La formulation populaire 'choisir deux' est trompeuse. La tolérance aux partitions n'est pas réellement facultative dans un système distribué, donc le véritable choix se situe entre la cohérence et la disponibilité, et ce choix ne doit être fait que lorsqu'une partition est effectivement en cours. Lorsque le réseau est sain, un système peut offrir à la fois cohérence et disponibilité.

Que garantit réellement la cohérence éventuelle ?

Elle garantit que si aucune nouvelle mise à jour n'est effectuée sur un élément de données, toutes les répliques finiront par converger vers la même valeur. Elle ne garantit ni le moment où cela se produira, ni qu'une lecture reflétera la dernière écriture, les applications utilisant la cohérence éventuelle doivent donc tolérer des lectures temporairement obsolètes ou conflictuelles et souvent gérer elles-mêmes la résolution des conflits.