Le théorème CAP revient dès que l'on parle de big data. Et comme on va beaucoup parler de la grosse donnée dans les semaines à venir...

A chaque entretien qu'on fait passer en big data, la mention du théorème CAP provoque chez la personne en face un réflexe mécanique: "on ne peut pas avoir en même temps la cohérence des données (C), la disponibilité (A pour availability) et la tolérance aux partitionnements (P)". Merveilleux. Mais quant à comprendre ce que ça veut dire...

C, A et P

Sur un SGBDR classique, vous avez la possibilité, dès que vous validez vos données, de voir la mise à jour prise en compte dans tous les accès suivants. C'est ce qu'on appelle la cohérence (si un changement est valide, il est accepté par le SGBDR immédiatement, il n'y a pas d'état incohérent entre les deux), et la durabilité (si le changement est accepté, il l'est pour toujours). Si vous requêtez un SGBDR, il vous répondra une réponse cohérente, et (sauf problème technique), sa réponse est immédiate. C'est valable aussi bien pour les lectures que pour les écritures. Quand vous réalisez un update, le SGBDR ne vous impose pas 30 secondes d'attente "le temps de prévenir tous les disques". La (haute) disponibilité est la faculté d'un système à traiter correctement (et immédiatement) une requête qui lui est soumise. 

Pour parler de la tolérance aux partitions, c'est un peu plus complexe. En première approximation, la tolérance aux partitions est la faculté d'un réseau à marcher correctement, c'est à dire à répondre aux requêtes des utilisateurs, même si deux sous réseaux n'arrivent plus à communiquer l'un avec l'autre pendant une longue période. Par exemple, vous avez mis en place un réseau qui lie la France et les USA. Suite à un incident causé par un technicien du GCHQ qui a eu la main un peu lourde sur les câbles sous marins de l'Atlantique, les deux pays ne s'échangent plus rien (imaginons). Si chaque sous réseau est pleinement opérationnel, et continue d'avoir la possibilité technique de répondre, alors le réseau est tolérant aux partitions. Si tout le réseau s'effondre, il ne l'est pas. Ce n'est pas d'ailleurs impensable de forcer le réseau entier à ne plus répondre : si une mise à jour est réalisée aux USA, comment la répercuter en France? Vaut il mieux ne pas répondre que ne répondre que la dernière version connue de la donnée par le réseau Français? Ça se discute

Le théorème CAP

Prenons un exemple simple : vous avez un cluster de 2000 nœuds, en Chine, USA, France, et Russie. Un utilisateur russe envoie une requête de modification de valeur au serveur de son pays. Il ne vous aura pas échappé que la propagation de l'information à tous les nœuds n'est pas immédiate. Pendant ce temps là, si on requête un serveur aux USA, que doit il répondre? Doit il dire "alors, laissez moi du temps pour que je demande l'avis à tout le réseau pour être bien sûr qu'on dira tous pareil?" (pas de haute disponibilité), ou doit il dire "je vous donne la dernière valeur que je connais, mais vous savez moi, je ne suis pas au courant des mises à jour chez les autres" (pas de cohérence). Le CAP explique notamment que ce genre de situation est une fatalité: si on part sur un réseau tolérant à la partition, il est censé répondre à une question qu'on lui pose. Si deux sous réseaux ne communiquent plus, il n'y a pas de solution magique, une mise à jour dans l'un ne peut pas être perçue de l'autre. Et donc, si on demande à l'un la valeur d'une variable, soit il vous répond "je ne sais pas" (pas de haute disponibilité), soit il vous donne une réponse qui n'est pas a priori identique à celle que l'autre sous réseau connait...

Oui mais en fait, c'est plus compliqué

Tout ça pour ça? Non, c'est un peu plus compliqué. Dans un réseau à N noeuds, le temps de mise à jour n'est pas instantané, il faut donc en tenir compte. On définit donc des algorithmes et des niveaux de validation de l'information différents:

  • Paxos est un algorithme qui garantit une réponse cohérente, mais pas de temps de réponse incompressible. C'est une solution pour une solution valide.
  • Cassandra définit des niveaux de cohérence à la charge de l'utilisateur, qui vont de "je réponds toujours, avec l'information sur le noeud interrogé" (rapide, mais incohérent au possible) à "je prends l'avis de tout le monde. Ne quittez pas. Je prends l'avis de tout le monde, ne quittez pas" (dommage pour la haute disponibilité).
  • Applicativement, c'est au métier de définir les conséquences d'une incohérence. Si vous postez un tweet et que dans la seconde, le compteur n'est pas mis à jour, ce n'est pas grave (pas à notre connaissance en tous cas). Sur une réservation, deux personnes qui peuvent prendre le même bien au même moment est un risque discutable. L'approche est d'en mesurer la probabilité, et de décider en fonction.

 

 

Comments are closed.

Set your Twitter account name in your settings to use the TwitterBar Section.