Théorème CAP : comprendre cohérence, disponibilité et partition

Deux caisses affichent le dernier exemplaire d'un produit. La première le vend, puis la connexion entre elles se coupe. La seconde peut-elle encore garantir que son stock est à jour ? Le théorème CAP explique pourquoi, pendant cette coupure, un système ne peut pas garantir à la fois des réponses cohérentes et une réponse à chaque demande. Pour comprendre ce choix, suivons les deux caisses.

Deux copies du stock peuvent donner des réponses différentes

Chaque caisse possède une copie du stock. Tant que les échanges fonctionnent, la vente enregistrée sur la caisse A peut être communiquée à la caisse B. Le problème apparaît quand A a confirmé la vente, mais que B ne peut plus recevoir cette information.

Un second client se présente devant B. Elle indique encore un exemplaire disponible. Elle ignore si A l'a vendu, si le message de mise à jour a été perdu ou si ce message est simplement en retard.

Le théorème CAP décrit les garanties qu'un système de ce type peut tenir. Il concerne les systèmes qui partagent des données par le réseau, au-delà des seules bases de données.

La cohérence : lire un état compatible avec les opérations terminées

Dans CAP, la cohérence signifie que les opérations se comportent comme si elles portaient sur une seule copie des données. Le terme précis est linéarisabilité : chaque opération paraît prendre effet à un instant situé entre son début et sa fin.

Pour nos caisses, cela donne une règle simple. Si A a terminé la vente du dernier exemplaire, une lecture du stock qui commence ensuite sur B doit tenir compte de cette vente, ou d'une modification plus récente.

Si la lecture et la vente se déroulent en même temps, plusieurs ordres sont possibles. Le résultat doit néanmoins correspondre à un ordre valide des opérations. Leur chevauchement ne permet pas de répondre n'importe quoi.

Cette définition vient des travaux de Maurice Herlihy et Jeannette Wing sur la linéarisabilité. Elle est plus précise que « les données sont correctes » : deux copies peuvent chacune contenir des valeurs plausibles sans respecter cette garantie.

La disponibilité : chaque demande finit par recevoir une réponse

La disponibilité, au sens de CAP, impose qu'une requête reçue par une machine qui fonctionne finisse par obtenir une réponse conforme à l'opération demandée. Attendre indéfiniment la reconnexion ne satisfait pas cette exigence. Renvoyer systématiquement une erreur ne suffit pas non plus.

La définition ne fixe cependant pas de délai maximal. Dans leur preuve de 2002, Seth Gilbert et Nancy Lynch précisent cette absence de borne. Une réponse qui arrive après une longue attente peut donc satisfaire la définition théorique tout en étant inutilisable à une caisse.

Votre application a besoin d'une exigence supplémentaire : combien de temps le client peut-il attendre ? Ce délai relève de la conception du service.

La partition : certaines machines ne peuvent plus échanger

Une partition réseau sépare des parties du système en empêchant leurs messages de passer. Les caisses peuvent continuer à fonctionner chacune de leur côté alors que leur liaison est indisponible.

Dans un réseau asynchrone, une machine ne peut pas toujours distinguer un message perdu d'un message très lent. En pratique, l'application fixe donc un délai d'attente. Quand il est dépassé, elle doit décider de la conduite à tenir sans disposer de toutes les informations.

La tolérance aux partitions consiste à prévoir le comportement du système malgré ces pertes de communication. Elle ne signifie pas que le réseau devient fiable, ni que toutes les opérations continueront comme avant.

La caisse isolée doit choisir ce qu'elle peut encore promettre

Revenons au second client. B ne peut plus vérifier le stock auprès de A. Elle peut attendre une information fiable, ou répondre à partir de sa copie locale. Chaque option renonce à une garantie différente.

Une autre expérience utilisateur est possible : enregistrer la demande du client et annoncer qu'elle reste à confirmer. Le système rend un service, mais il promet autre chose qu'une vente immédiatement garantie.

Eric Brewer décrit cette possibilité : conserver l'intention, puis l'exécuter lorsque la communication revient. Il faudra alors vérifier le stock et traiter les demandes qui ne peuvent pas être satisfaites.

Pourquoi « choisir deux propriétés sur trois » aide peu à concevoir

La formule résume une impossibilité, mais laisse croire qu'une application pourrait simplement choisir de ne jamais subir de coupure. Une liaison réseau ne donne pas cette garantie. La décision utile porte sur ce que chaque opération fait lorsque la communication échoue.

Elle peut différer selon le besoin. Afficher une disponibilité indicative et confirmer une vente n'engagent pas la même promesse. Je recommande d'écrire ces engagements avant de classer tout un système comme « cohérent » ou « disponible ».

Lorsque les communications fonctionnent, CAP n'impose pas de renoncer à l'une de ces deux propriétés. Et dans un service réel, vous pouvez ajuster la fraîcheur des données, le délai acceptable ou les opérations accessibles pendant une panne. Ces choix pratiques ne changent pas les définitions strictes du théorème.

Brewer a proposé la conjecture, présentée notamment à PODC en 2000 ; Gilbert et Lynch l'ont démontrée en 2002. Son retour de 2012 insiste sur ces possibilités de conception que le raccourci « deux sur trois » fait facilement oublier.

Pour votre application, partez d'une opération précise : quelle information lui manque si le réseau se coupe, et que peut-elle encore promettre sans cette information ? La suite sur CAP développe cette limite ; le traitement des demandes en attente devra aussi prévoir ce qui se passe lorsque les machines se reconnectent.

Sources

• S. Gilbert & N. Lynch, Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services, ACM SIGACT News, 2002.
• E. Brewer, CAP Twelve Years Later: How the "Rules" Have Changed, IEEE Computer, 2012.
• M. Herlihy & J. Wing, Linearizability: A Correctness Condition for Concurrent Objects, ACM TOPLAS 12(3), juillet 1990.