Théorème CAP - CAP theorem

En informatique théorique , le théorème CAP , également nommé théorème de Brewer d' après l'informaticien Eric Brewer , stipule que tout magasin de données distribué ne peut fournir que deux des trois garanties suivantes :

Cohérence
Chaque lecture reçoit l'écriture la plus récente ou une erreur.
Disponibilité
Chaque requête reçoit une réponse (sans erreur), sans la garantie qu'elle contienne l'écriture la plus récente.
Tolérance de partition
Le système continue de fonctionner malgré un nombre arbitraire de messages abandonnés (ou retardés) par le réseau entre les nœuds.

Lorsqu'une panne de partition réseau se produit, il faut décider s'il faut

  • annuler l'opération et donc diminuer la disponibilité mais assurer la cohérence ou
  • procéder à l'opération et ainsi assurer la disponibilité mais risquer l'incohérence.

Ainsi, s'il existe une partition réseau, il faut choisir entre cohérence et disponibilité. Notez que la cohérence telle que définie dans le théorème CAP est assez différente de la cohérence garantie dans les transactions de la base de données ACID .

Eric Brewer soutient que le concept souvent utilisé « deux sur trois » peut être quelque peu trompeur car les concepteurs de systèmes n'ont besoin de sacrifier la cohérence ou la disponibilité qu'en présence de partitions, mais que dans de nombreux systèmes, les partitions sont rares.

Explication

Aucun système distribué n'est à l'abri des pannes de réseau, c'est pourquoi le partitionnement du réseau doit généralement être toléré. En présence d'une partition, on se retrouve alors avec deux options : cohérence ou disponibilité . Lors du choix de la cohérence plutôt que de la disponibilité, le système renvoie une erreur ou un délai d'attente s'il n'est pas possible de garantir la mise à jour d'informations particulières en raison du partitionnement du réseau. Lors du choix de la disponibilité plutôt que de la cohérence, le système traitera toujours la requête et essaiera de renvoyer la version disponible la plus récente des informations, même s'il ne peut pas garantir qu'elle est à jour en raison du partitionnement du réseau.

La PAC est souvent mal comprise comme un choix à tout moment dont l'une des trois garanties à abandonner. En fait, le choix est entre cohérence et disponibilité uniquement lorsqu'une partition réseau ou une panne se produit. Lorsqu'il n'y a pas de panne de réseau, la disponibilité et la cohérence peuvent être satisfaites.

CAP a été utilisé par de nombreux fournisseurs de bases de données NoSQL comme justification pour ne pas fournir de cohérence ACID transactionnelle, affirmant que le théorème CAP "prouve" qu'il est impossible de fournir en même temps l'évolutivité et la cohérence ACID. Cependant, un examen plus attentif du théorème CAP et, en particulier, la formalisation de Gilbert & Lynch, révèle que le théorème CAP ne fait pas du tout référence à l'évolutivité, mais seulement à la disponibilité (le A dans CAP).

Les systèmes de base de données conçus avec les garanties ACID traditionnelles à l'esprit, tels que les SGBDR, privilégient la cohérence à la disponibilité, tandis que les systèmes conçus autour de la philosophie BASE , courante dans le mouvement NoSQL par exemple, privilégient la disponibilité à la cohérence.

Le théorème PACELC s'appuie sur CAP en affirmant que même en l'absence de partitionnement, il existe un autre compromis entre la latence et la cohérence.

Histoire

Selon l' informaticien Eric Brewer de l' Université de Californie à Berkeley , le théorème est apparu pour la première fois à l'automne 1998. Il a été publié en tant que principe CAP en 1999 et présenté comme une conjecture par Brewer au Symposium 2000 sur les principes de l'informatique distribuée (PODC). En 2002, Seth Gilbert et Nancy Lynch du MIT ont publié une preuve formelle de la conjecture de Brewer, ce qui en fait un théorème .

En 2012, Brewer a clarifié certaines de ses positions, notamment pourquoi le concept souvent utilisé « deux sur trois » peut être quelque peu trompeur, car les concepteurs de systèmes n'ont besoin de sacrifier la cohérence ou la disponibilité qu'en présence de partitions ; il existe des techniques de gestion de partition et de récupération. Brewer a également noté la différence de définition de la cohérence utilisée dans le théorème CAP par rapport à la définition utilisée dans ACID .

Un théorème similaire indiquant le compromis entre cohérence et disponibilité dans les systèmes distribués a été publié par Birman et Friedman en 1996. Le résultat de Birman et Friedman a restreint cette limite inférieure aux opérations sans commutation.

La technologie Blockchain sacrifie la cohérence pour la disponibilité et la tolérance de partition, mais est obtenue grâce à la validation entre les nœuds au fil du temps avec l'impression résultante que le théorème n'est pas valide.

Voir également

Les références

Liens externes