Une preuve illustrée du théorème CAP

Le théorème CAP est un théorème fondamental dans les systèmes distribués qui stipule que tout système distribué peut avoir au plus deux des trois propriétés suivantes.

• Cohérence
• Disponibilité
• Tolérance de partition

Ce guide résumera la spécification et la preuve du théorème de CAP de Gilbert et Lynch avec des images!

Qu’est-ce que le théorème CAP ?

Le théorème de CAP stipule qu’un système distribué ne peut pas être simultanément cohérent, disponible et tolérant aux partitions. Cela semble assez simple, mais qu’est-ce que cela signifie d’être cohérent? disponible ? tolérant aux partitions ? Qu’entendez-vous exactement par système distribué ?

Dans cette section, nous allons présenter un système distribué simple et expliquer ce que signifie que ce système soit disponible, cohérent et tolérant aux partitions. Pour une description formelle du système et des trois propriétés, veuillez vous référer à l’article de Gilbert et Lynch.

Un système distribué

Considérons un système distribué très simple. Notre système est composé de deux serveurs,GG_1 and etGG_2$. Ces deux serveurs gardent une trace de la même variable,vv$, dont la valeur est initialementvv_0$. GG_1 and etGG_2 can peuvent communiquer entre eux et peuvent également communiquer avec des clients externes. Voici à quoi ressemble notre système.

Un client peut demander à écrire et à lire depuis n’importe quel serveur. Lorsqu’un serveur reçoit une requête, il effectue tous les calculs qu’il souhaite, puis répond au client. Par exemple, voici à quoi ressemble une écriture.

Et voici à quoi ressemble une lecture.

Maintenant que nous avons établi notre système, passons en revue ce que cela signifie pour que le système soit cohérent, disponible et tolérant aux partitions.

Cohérence

Voici comment Gilbert et Lynch décrivent la cohérence.

toute opération de lecture qui commence après la fin d’une opération d’écriture doit renvoyer cette valeur, ou le résultat d’une opération d’écriture ultérieure

Dans un système cohérent, une fois qu’un client écrit une valeur sur n’importe quel serveur et reçoit une réponse, il s’attend à récupérer cette valeur (ou une valeur plus fraîche) de n’importe quel serveur à partir duquel il lit.

Voici un exemple de système incohérent.

Notre client écrit $v_1$ à $G_1$ et $G_1$ reconnaît, mais quand il lit à partir de $G_2$, on obtient des données périmées: $v_0$.

D’autre part, voici un exemple de système cohérent.

Dans ce système,GG_1 repl réplique sa valeur enGG_2 before avant d’envoyer un accusé de réception au client. Ainsi, lorsque le client lit à partir de $G_2$, on obtient le plus à jour la valeur de $v$: $v_1$.

Disponibilité

Voici comment Gilbert et Lynch décrivent la disponibilité.

chaque requête reçue par un nœud non défaillant du système doit entraîner une réponse

Dans un système disponible, si notre client envoie une requête à un serveur et que le serveur ne s’est pas écrasé, le serveur doit éventuellement répondre au client. Le serveur n’est pas autorisé à ignorer les demandes du client.

Tolérance de partition

Voici comment Gilbert et Lynch décrivent les partitions.

le réseau sera autorisé à perdre arbitrairement de nombreux messages envoyés d’un nœud à un autre

Cela signifie que tous les messages sendG_1 and etGG_2 send envoyés entre eux peuvent être supprimés. Si tous les messages étaient supprimés, notre système ressemblerait à ceci.

Notre système doit pouvoir fonctionner correctement malgré des partitions réseau arbitraires afin d’être tolérant aux partitions.

La preuve

Maintenant que nous nous sommes familiarisés avec la notion de cohérence, de disponibilité et de tolérance de partition, nous pouvons prouver qu’un système ne peut pas avoir simultanément les trois.

Supposons pour contradiction qu’il existe un système cohérent, disponible et tolérant aux partitions. La première chose que nous faisons est de partitionner notre système. Ça ressemble à ça.

Ensuite, notre client demande quevv_1 be soit écrit dansGG_1$. Puisque notre système est disponible,GG_1 must doit répondre. Étant donné que le réseau est partitionné, cependant,GG_1 cannot ne peut pas répliquer ses données enGG_2$. Gilbert et Lynch appellent cette phase d’exécution\\alpha_1$.

Ensuite, nous demandons à notre client d’émettre une demande de lecture àGG_2$. Encore une fois, puisque notre système est disponible,GG_2 must doit répondre. Et puisque le réseau est partitionné,GG_2 cannot ne peut pas mettre à jour sa valeur à partir deGG_1$. Il renvoievv_0$. Gilbert et Lynch appellent cette phase d’exécution\\alpha_2$.

$G_2$ retourne $v_0$ pour notre client après que le client a déjà écrit $v_1$ à $G_1$. C’est incohérent.

Nous avons supposé qu’un système cohérent, disponible et tolérant aux partitions existait, mais nous venons de montrer qu’il existe une exécution pour un tel système dans lequel le système agit de manière incohérente. Ainsi, un tel système n’existe pas.