Quel est le raisonnement derrière le théorème de la PAC?

21

http://en.wikipedia.org/wiki/CAP_theorem

http://www.cs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf

Je pense que ce n'est pas très simple pourquoi seulement deux des

  1. Cohérence
  2. Disponibilité
  3. Tolérance de partition

peut contenir pour tout système de base de données distribué donné. Cette conjecture a été prouvée, mais existe-t-il un moyen plus simple de comprendre pourquoi cela pourrait probablement se vérifier ?

Je ne cherche pas de preuve, juste un bon moyen de comprendre pourquoi ce théorème pourrait avoir du sens. Quel est le raisonnement?

Lazer
la source

Réponses:

23

OK, imaginons que vous ayez une base de données distribuée. Disons que vous avez un nœud en Oregon et un en Californie. La théorie du CAP dit que vous rencontrerez des problèmes lors de la configuration de ce type de base de données.

Par exemple, si vous interrogez des données d'une base de données, elles doivent être identiques aux données de l'autre base de données. Cela garantit que la valeur que vous avez dans une base de données est garantie d'être dans l'autre ( cohérence de la théorie CAP). Cela vous permet de mettre à jour les données dans une base de données et de les interroger dans une autre, pour obtenir les mêmes résultats.

Un ordinateur mettant à jour les données dans l'Oregon transfère les données en Californie

Lorsque nous mettons à jour les données dans le nœud Oregon, les données sont envoyées au nœud Californie afin que les bases de données soient cohérentes. Afin de maintenir vraiment la cohérence, nous devons nous assurer que les deux bases de données obtiennent la mise à jour avant que l'une ou l'autre ne soit vraiment autorisée à sauvegarder les données (validation en deux phases à l'aide de transactions distribuées). En d'autres termes, si la base de données de Californie ne peut pas enregistrer les données pour une raison quelconque (par exemple, une panne de disque dur), la base de données de l'Oregon n'enregistrera pas les données et échouera la transaction.

Le problème avec les transactions distribuées comme celle ci-dessus survient lorsque nous voulons avoir une haute disponibilité. Dans ce scénario ci-dessus, le processus consistant à essayer de synchroniser les deux bases de données est un processus très, très lent. (Imaginez, nous devons envoyer les données de l'Oregon à la Californie, assurez-vous qu'elles y arrivent, assurez-vous que les deux bases de données ont des verrous sur les données, etc.) Cela provoque des problèmes majeurs lorsque nous voulons un système rapide et réactif même pendant en période de forte demande. (Ceci est la disponibilité du théorème CAP.)

Généralement, ce que nous faisons pour assurer une haute disponibilité, c'est que nous utilisons la réplication au lieu des transactions distribuées. Ainsi, au lieu de garantir que la Californie peut accepter les données, nous allons simplement les stocker dans le nœud Oregon, puis envoyer les données en Californie lorsque nous y arriverons. Cela garantit que nous pouvons toujours stocker les données, que la Californie soit prête ou non à les stocker.

Le nœud Oregon met à jour les données pendant que la Californie lit les données.  Plus tard, les données sont déplacées vers la Californie

Cela améliore la disponibilité, mais au détriment de la cohérence. Voyez, si quelqu'un met à jour les données dans l'Oregon et que quelqu'un (en même temps) lit les données en Californie, il n'obtient pas les nouvelles données - les bases de données ne sont plus cohérentes. En fait, ils ne seront cohérents que lorsque l'Oregon enverra les données à la Californie!

C'est donc le compromis Disponibilité -vs- Cohérence.

La tolérance de partition est le troisième aspect de la théorie CAP. Le partitionnement est, dans ce contexte, l'idée qu'une base de données (ou un autre système distribué) peut se diviser en sections distinctes et toujours fonctionner correctement.

La question devient, que se passe-t-il lorsque les deux bases de données fonctionnent correctement, mais que le lien entre l'Oregon et la Californie est rompu?

L'Oregon est mis à jour pendant la lecture du nœud californien.  Le réseau entre les nœuds est coupé.

Si nous mettons à jour la base de données dans l'Oregon, nous devons acheminer les données vers la Californie d'une manière ou d'une autre (transaction distribuée ou réplication). Cependant, si le lien entre les deux est rompu, le système est devenu partitionné et les bases de données ne sont plus liées entre elles.

Lorsque cela se produit, vos choix sont d'arrêter d'autoriser les mises à jour (pour maintenir la cohérence) au détriment de la disponibilité ou d'autoriser les mises à jour (pour maintenir la disponibilité) au détriment de la cohérence.

Comme vous pouvez le voir, la tolérance de partition crée des compromis directs entre cohérence et disponibilité.


Il y a évidemment plus que cela, mais ce sont quelques exemples sur la façon dont ces trois aspects majeurs des systèmes distribués fonctionnent les uns pour les autres. L' explication de Julian Browne sur la théorie de la PAC est un excellent endroit pour en savoir plus.

Richard
la source
Réponse connexe de Remus Rusanu.
Nick Chammas
Avec une image bien plus jolie à ça!
Richard