tl;dr (a.k.a “take aways”) :
Pourquoi un talk sur un théorème ? Parce que même si un théorème est quelque chose de très formel, très précis et souvent ardu, il y a donc des choses à en tirer.
De nos jours “distributed is becoming the norm” : tout le monde veut de l’élasticité, de la haute disponibilité et de la résilience (à défaut d’avoir besoin). Les systèmes distribués – bien que complexes – sont donc de plus en plus répandus.
Le théorème CAP est historiquement parti d’une conjecture par Eric Brewer : un système ne peut être à la fois cohérent (“Consistent”), disponible (“Available”) et tolérant à la partition réseau (“Partition tolerant”). Il est possible de n’avoir que deux de ces propriétés en même temps.
Le théorème a été formellement prouvé par la suite par Gilbert et Lynch.
Cohérence (linéarisabilité) : toute lecture qui suit une écriture doit renvoyer la valeur de cette dernière, ou une valeur plus récente.
Disponibilité : les noeuds disponibles du système doivent répondre à toute requête.
Tolérance à la partition réseau : le système doit tolérer les partitions réseau (lorsque deux sous parties du système ne peuvent plus se coordonner).
L’impossibilité prouvée par le théorème CAP ne s’applique que dans le cadre d’un réseau asynchrone, c’est-à-dire sans limite de temps pour l’acheminement des messages.
En 2012, Brewer revient sur son travail dans un article “CAP twelve years later. How the rules have changed.” (autre article intéressant qui apporte une perspective plus rigoureuse de la perspective sur CAP, en 2015 par Martin Kleppmann “A critique of the cap theorem”).
Le théorème CAP à quelques limites :
Si vous construisez un système distribué, concrètement, quelles sont les questions que vous devez vous poser :
BOTTOM LINE => ce sont des questions business
Git : dans git il y a partition dès que deux branches sont tirées en parallèle et modifient la même valeur. Git est tout à fait capable de résoudre les conflits, et lorsqu’il n’y parvient pas il fait appel à un être humain pour décider (c’est la résolution de conflits pendant un merge).
Bases de données relationnelles : elles gèrent les partitions d’une manière différente, via des stratégies de concurrence qui peuvent être soit optimistes soit pessimistes.
Autres exemples : un répertoire partagé, édition partagée de documents, blockchain…
Voir la présentation complète du talk sur slideshare.
Un article est vendu mais s’avère en réalité indisponible. Que faire ? On pose la question au métier : si on est en période de rush, le métier peut considérer que l’erreur de stock est acceptable, et on peut proposer un bon d’achat au client dont la commande n’a pas été honorée.
Ce que vous voyez sur votre mur est une liste d’évènements, et Facebook veut être absolument certain que les évènements qui s’affichent devant vos yeux sont ceux que vous devez voir (ex. : votre grand mère ne voit pas vos photos de soirées étudiantes). C’est une autre manière de dire qu’ils préfèrent la cohérence (consistency) à la fraicheur et donc la disponibilité (availability) de l’information.
Les choses sont différentes car les tweets ont une forme de durée de vie, et Twitter préfère qu’un tweet soit disponible rapidement pour qu’il puisse être partagé, tant pis si un tweet n’aurait pas dû être publié (offensant etc.). Ils se sont dotés de mesures pour gérer les tweets problématiques après leur publication. C’est une autre manière de dire que Twitter préfère la fraîcheur (une forme de disponibilité) à la cohérence.
Les CRDTs sont une approche élégante pour éviter les conflits de partitions.
Spanner propose un service proche de contredire le théorème CAP, pas de manière parfaite car c’est impossible, mais de manière si parfaite que vous ne pouvez pas le remarquer (ceci n’est possible que parce que Google possède la maîtrise de son réseau et des horloges de très haute précision à l’échelle du globe)