Le théorème CAP, ACID et BASE : ce qu'on accepte de perdre

Le pont coupé par la crue

La ville tient sur deux rives. Un pont, la conduite d'eau qui passe sous le tablier, la ligne téléphonique qui suit la même travée. Tant que le pont tient, personne ne se demande combien de mairies possède la ville.

Un matin de crue, il cède. Les deux rives existent toujours, chacune avec son annexe, ses guichets et son registre. Elles ne se parlent plus.

Le maire a deux options, et pas une troisième. Fermer les guichets des deux côtés jusqu'au rétablissement, pour être certain qu'aucun acte ne sera inscrit deux fois. Ou les laisser ouverts, en sachant que la rive nord ignorera pendant des heures ce que la rive sud a enregistré.

Ce qu'il n'a pas comme option, c'est d'empêcher la crue. Le pont tombera, un jour ou l'autre. La seule décision qui lui appartient vraiment, c'est celle qu'il aura prise avant.

Le théorème CAP ne dit pas quoi choisir. Il dit qu'au moment où le pont cède, tu choisis, que tu l'aies écrit avant ou non.

Ce billet pose les trois propriétés une par une, montre pourquoi le slogan « deux sur trois » est trompeur, sépare les systèmes CP des systèmes AP, puis descend côté bases de données avec ACID d'un côté et BASE de l'autre. Il se termine sur une panne réelle où l'arbitrage a été fait en direct, et assumé publiquement.

C, A et P, une propriété à la fois

Trois mots, souvent récités et rarement définis. Ils méritent chacun leur phrase.

Cohérence. Toute lecture renvoie la dernière écriture validée, ou une erreur. Peu importe le nœud interrogé : le système se comporte comme s'il n'existait qu'une seule copie de la donnée. C'est une propriété forte, plus forte que ce que la plupart des gens ont en tête quand ils disent « cohérent ».

Disponibilité. Toute requête reçue par un nœud en état de fonctionner obtient une réponse, en temps fini, et cette réponse n'est pas une erreur. Un système qui répond « réessayez dans une minute » n'est pas disponible au sens de CAP.

Tolérance au partitionnement. Le système continue de fonctionner alors que des messages entre nœuds sont perdus ou arbitrairement retardés. Le réseau se coupe, le système ne s'arrête pas pour autant.

Un détail de vocabulaire mérite d'être posé tout de suite, parce qu'il fait perdre du temps à tout le monde : le C de CAP et le C d'ACID ne désignent pas la même chose. Le premier parle de l'accord entre plusieurs copies d'une même donnée. Le second parle du respect des contraintes d'intégrité à l'intérieur d'une base. On peut avoir l'un sans l'autre.

Voilà l'arbitrage, réduit à sa forme minimale.

Les trois propriétés ne sont pas trois options sur un formulaire. Deux sont des objectifs de conception, la troisième est la météo.

Pourquoi « deux sur trois » ne veut rien dire

Eric Brewer a présenté la conjecture en 2000, lors d'un exposé à la conférence PODC. Seth Gilbert et Nancy Lynch en ont publié une preuve formelle en 2002, dans un modèle de réseau asynchrone. Le résultat est solide, et depuis vingt ans on le résume par une phrase qui trahit son contenu : « choisissez deux propriétés sur trois ».

Le problème de cette formulation tient en une phrase. La partition n'est pas une case à cocher, c'est un événement qui t'arrive. Un câble sectionné par une pelleteuse, une règle de pare-feu poussée un vendredi soir, un commutateur qui perd la moitié de ses paquets sans tomber franchement.

Renoncer à P signifierait affirmer que le réseau entre tes nœuds ne se coupera jamais. Il n'y a qu'un système où cette affirmation tient : celui qui tourne sur une seule machine. Dès que la donnée existe en plusieurs copies sur plusieurs machines, P est imposé, et le choix se réduit à deux termes.

Brewer lui-même est revenu sur le sujet en 2012, dans un article d'IEEE Computer intitulé « CAP Twelve Years Later: How the "Rules" Have Changed ». Il y écrit que la formulation en deux sur trois a toujours été trompeuse, parce qu'elle simplifie à l'excès la tension entre les propriétés. Hors partition, rien n'oblige à sacrifier quoi que ce soit. La tension n'apparaît que pendant la partition, et le vrai travail de conception consiste à gérer cette période explicitement : détecter son début, entrer dans un mode dégradé où certaines opérations sont interdites, puis lancer une reprise qui réconcilie et compense.

Et quand le réseau va bien ?

Même sans partition, la cohérence a un prix, et ce prix est de la latence. Daniel Abadi a formalisé ce prolongement sous le nom de PACELC : en cas de partition, on arbitre entre disponibilité et cohérence ; sinon, on arbitre entre latence et cohérence.

Rien d'abstrait là-dedans : la contrainte est physique. Une écriture synchrone entre deux continents attend l'acquittement du continent d'en face, et cet acquittement voyage dans une fibre.

Distance Paris - New York (grand cercle)  :     5 800 km
Vitesse dans une fibre (indice ~1,5)      :   200 000 km/s
Trajet aller     5 800 / 200 000          =     0,029 s  soit  29 ms
Aller-retour     29 x 2                   =                    58 ms
Écritures séquentielles   1 / 0,058       =    environ 17 par seconde

Cinquante-huit millisecondes, plancher théorique, avant même de toucher un disque ou de prendre un verrou. Le trajet réel n'étant pas une ligne droite, on mesure plutôt 70 à 90 ms sur cette liaison. Une chaîne d'écritures séquentielles qui attend chaque acquittement plafonne donc autour de dix-sept opérations par seconde. Aucun réglage logiciel ne rattrape ça.

La cohérence forte entre continents ne se paie pas en euros, elle se paie en millisecondes, et la facture est adressée par la vitesse de la lumière.

CP ou AP : ce que voit l'utilisateur pendant la partition

Reviens à la rive nord et à la rive sud. Guichets fermés d'un côté, ou guichets ouverts partout : dans les deux cas la ville tient debout, mais ses habitants n'y vivent pas la même journée.

Un système CP préserve la cohérence et sacrifie la disponibilité. Concrètement, le côté qui se retrouve minoritaire cesse d'accepter les écritures, parfois même les lectures. C'est le comportement des systèmes de coordination à quorum majoritaire : etcd et ZooKeeper n'élisent pas de chef sans majorité, et un cluster de base relationnelle à primaire unique refuse d'écrire tant qu'un nouveau primaire n'est pas promu.

Un système AP préserve la disponibilité et sacrifie la cohérence. Chaque côté continue de servir, avec la donnée qu'il possède, et les divergences seront réconciliées plus tard. Le DNS fonctionne exactement comme ça depuis toujours : un enregistrement modifié met le temps de son TTL à se propager, et pendant ce temps deux résolveurs répondent deux choses différentes.

Le point à retenir n'est pas qu'une famille vaut mieux que l'autre. C'est que le comportement en mode dégradé fait partie des spécifications du produit, au même titre qu'un écran de connexion. Un utilisateur qui reçoit une erreur claire est mieux traité qu'un utilisateur à qui on affiche un solde faux sans le lui dire.

Écris noir sur blanc, avant la mise en production, ce que ton système répond pendant une partition. Sinon quelqu'un décidera à ta place, à trois heures du matin, sous pression.

ACID : ce que garantit une transaction

Descendons d'un étage, jusqu'à la base de données. L'acronyme ACID a été fixé par Theo Härder et Andreas Reuter en 1983, à partir des travaux de Jim Gray sur les transactions. Quatre garanties, quatre phrases.

Atomicité. Une transaction s'applique en entier ou pas du tout. Aucun état intermédiaire n'est visible ni persisté.

Cohérence. Une transaction fait passer la base d'un état valide à un autre état valide, au regard des contraintes déclarées : clés étrangères, unicité, contraintes de vérification.

Isolation. Deux transactions concurrentes se comportent comme si elles s'exécutaient l'une après l'autre. C'est l'idéal ; en pratique les moteurs proposent plusieurs niveaux, du plus permissif au plus strict, et le niveau par défaut n'est presque jamais le plus strict.

Durabilité. Une transaction validée survit à une coupure de courant immédiate.

Le virement bancaire reste l'illustration la plus lisible, parce que l'atomicité y est visible à l'œil nu.

BEGIN;
UPDATE comptes SET solde = solde - 100 WHERE id = 'A';
UPDATE comptes SET solde = solde + 100 WHERE id = 'B';
COMMIT;

Si la machine tombe entre les deux mises à jour, le moteur annule la première au redémarrage. Cent euros ne peuvent pas disparaître entre deux lignes de code.

Cette garantie a un périmètre : une base. Dès que les deux comptes vivent dans deux services avec deux bases, plus rien de tout ceci ne s'applique automatiquement, et il faut reconstruire l'équivalent à la main. C'est le sujet de Transactions distribuées : 2PC, 3PC, SAGA et verrous.

ACID est une propriété locale. Elle ne traverse pas la frontière d'une base, et surtout pas celle d'un service.

BASE : ce qu'on obtient quand on renonce

L'acronyme BASE a été construit en miroir d'ACID, avec l'humour de chimiste qui va avec, et popularisé par l'article « BASE: An Acid Alternative » de Dan Pritchett, publié dans ACM Queue en 2008.

Basiquement disponible. Le système répond, y compris en mode dégradé, y compris quand une partie de ses nœuds est injoignable.

État souple. L'état peut changer sans écriture entrante, simplement parce que la réplication progresse en arrière-plan.

Cohérence à terme. En l'absence de nouvelle écriture, toutes les copies finissent par converger vers la même valeur.

Le mot « terme » est le seul qui compte, et c'est celui qu'on ne quantifie jamais. En régime normal, la réplication asynchrone entre deux nœuds proches se compte en millisecondes. Sous charge, avec un réplica qui prend du retard, elle se compte parfois en minutes. La définition ne promet aucune borne.

Côté utilisateur, ça donne cette scène, familière à qui a déjà changé sa photo de profil.

L'écriture a réussi. Le système est parfaitement fonctionnel. Et l'utilisatrice conclut que son envoi a échoué, parce qu'elle a relu sur un réplica qui n'était pas encore à jour.

La parade porte un nom, « lire ses propres écritures », et se met en œuvre de plusieurs façons : router les lectures d'une session vers le nœud qui a reçu son écriture, servir l'utilisateur depuis le primaire pendant quelques secondes, ou renvoyer la valeur écrite depuis le client sans relire. Aucune n'est gratuite, et toutes vivent dans le code applicatif plutôt que dans la base.

La cohérence à terme ne déplace pas le problème dans le futur. Elle le déplace dans ton code applicatif, où il faudra gérer les conflits, les rejeux et les affichages transitoires.

Le choix se fait par fonctionnalité, pas par produit

La tentation est permanente : classer les bases en deux camps, coller une étiquette ACID sur l'un, BASE sur l'autre, et choisir son camp au début du projet. Les moteurs modernes ont rendu ce classement caduc. Beaucoup de magasins réputés « BASE » proposent des lectures et des écritures à quorum, donc une cohérence forte au cas par cas. Beaucoup de moteurs relationnels tournent par défaut à un niveau d'isolation qui autorise des anomalies.

La bonne granularité de décision, c'est la fonctionnalité. Un même produit héberge sans difficulté les deux régimes, à condition d'avoir écrit lequel s'applique où.

Le débit et l'affichage du solde portent sur la même donnée, et n'appellent pas le même arbitrage. C'est exactement là que se joue la qualité d'une conception.

Pour la question voisine, celle du choix du magasin lui-même, le billet SQL ou NoSQL : choisir son magasin de données traite le sujet en entier. Ce billet ne le refait pas.

Un système sérieux n'est ni ACID ni BASE. Il possède une liste, écrite quelque part, des fonctionnalités qui relèvent de l'un et de celles qui relèvent de l'autre.

Scénario B : la panne GitHub du 21 octobre 2018

Le rapport public de GitHub, publié le 30 octobre 2018, montre un arbitrage CAP se jouer en direct sur une infrastructure de production, puis être assumé par écrit.

Le 21 octobre 2018 à 22h52 UTC, une opération de maintenance sur un équipement optique 100 Gbit/s coupe la liaison entre le hub réseau de la côte est des États-Unis et le centre de données principal, situé lui aussi sur la côte est. La connectivité revient au bout de 43 secondes.

Quarante-trois secondes. Le pont a cédé le temps d'un café.

Pendant cette coupure, Orchestrator, l'outil de gestion de topologie MySQL de GitHub, fait ce pour quoi il a été écrit. S'appuyant sur un consensus Raft, il constate que le centre de données de la côte est n'est plus joignable et promeut des primaires situés sur la côte ouest. Le trafic d'écriture bascule.

Quand le lien revient, les deux côtes détiennent chacune des écritures que l'autre n'a pas. Le primaire de la côte est a accepté, pendant les 43 secondes, des écritures qui n'ont jamais été répliquées vers l'ouest. Le nouveau primaire de la côte ouest, lui, a accumulé tout ce que le service a écrit depuis la bascule.

Aucun retour en arrière n'est possible sans perdre des données de l'un des deux côtés. GitHub écrit avoir choisi de privilégier l'intégrité des données sur la disponibilité complète du service.

Le service reste accessible, en mode dégradé, pendant que les équipes reconstruisent un état cohérent. Le rapport dit pourquoi laisser la côte est écrire vers un primaire de la côte ouest n'était pas tenable : la couche applicative ne supporte pas la latence d'un aller-retour transcontinental sur la majorité de ses appels à la base. Les sauvegardes MySQL, prises toutes les quatre heures et conservées à distance dans un stockage objet, servent à une partie de la restauration, et transférer puis recharger plusieurs téraoctets prend des heures.

Rétablissement complet : 24 heures et 11 minutes après le début de l'incident.

Ce que le cas enseigne tient en trois points. Une partition de 43 secondes suffit à produire une journée entière de dégradation, parce que le coût n'est pas dans la coupure mais dans la réconciliation. Le basculement automatique a fait exactement ce qu'on lui demandait, et c'est précisément pour cette raison qu'il a créé la divergence. Enfin, l'arbitrage entre cohérence et disponibilité a été tranché en faveur de la cohérence, et écrit noir sur blanc. N'importe quelle équipe devrait pouvoir en faire autant sur sa propre architecture, avant l'incident plutôt qu'après.

Le rapport de GitHub vaut d'être lu en entier. Il transforme le théorème CAP en décision d'exploitation, avec ses heures et ses conséquences.

Points clés

• Le C de CAP (toutes les copies s'accordent) et le C d'ACID (les contraintes d'intégrité sont respectées) sont deux notions différentes. Les confondre fait dérailler la discussion en trois minutes.
• « Deux sur trois » est une formulation trompeuse : la partition n'est pas un choix mais un événement. Le seul arbitrage réel porte sur cohérence ou disponibilité pendant la partition.
• Hors partition, la cohérence forte se paie en latence. Entre Paris et New York, l'aller-retour coûte 58 ms au minimum, soit environ dix-sept écritures séquentielles par seconde.
• ACID garantit tout ou rien à l'intérieur d'une base ; BASE garantit une réponse et remet la convergence à plus tard, en déplaçant la difficulté dans le code applicatif.
• L'arbitrage se décide fonctionnalité par fonctionnalité, pas produit par produit. Le même service peut afficher un solde en cohérence à terme et débiter un compte en transaction stricte.

Dans la série

Palier 1 : Dimensionner la ville. Domaine : Fondamentaux.

• Précédent : De zéro à un million d'utilisateurs, étape par étape
• Suivant : Répartiteur de charge, proxy et proxy inverse
• Vue d'ensemble : System design : par où commencer

Pour aller plus loin

• Le rapport d'incident GitHub du 21 octobre 2018, le scénario B de ce billet, à lire jusqu'aux mesures correctives.
• Théorème CAP pour l'énoncé formel et la preuve de Gilbert et Lynch (2002). L'article d'Eric Brewer « CAP Twelve Years Later: How the "Rules" Have Changed » a paru dans IEEE Computer en février 2012, et l'article de Dan Pritchett « BASE: An Acid Alternative » dans ACM Queue en 2008.
• SQL ou NoSQL : choisir son magasin de données pour la question du choix de la base, que ce billet ne traite volontairement pas.
• Transactions distribuées : 2PC, 3PC, SAGA et verrous pour ce qui remplace ACID quand une transaction traverse plusieurs services.
• Concevoir un magasin clé-valeur pour voir l'arbitrage CAP se traduire en quorum de lecture et d'écriture sur un système complet.
• Jepsen pour les rapports de tests de cohérence menés sur des bases distribuées réelles, sous partition provoquée.