Le théorème CAP

Le chapitre précédent a réparti les données sur des machines qui tombent en panne, et a réglé la question de la durabilité : avec trois copies, rien n'est perdu. Il a laissé de côté une question plus difficile. Quand une donnée existe en trois exemplaires et qu'une écriture arrive, que lit celui qui interroge la deuxième copie avant qu'elle ne soit à jour ?

Cette question n'a pas de bonne réponse universelle. Elle a des réponses, chacune payée d'un prix connu, et le rôle du concepteur est de choisir lequel.

Ce que garantit une transaction

Ces quatre propriétés sont l'acquis du chapitre sur les transactions du parcours Bases de données, et elles ont un coût qui ne se voit pas sur une machine unique : elles exigent une coordination. L'isolation impose des verrous ou un contrôle de version ; la durabilité impose une écriture réellement descendue sur le disque avant de répondre.

Cette coordination se voit sur la dernière place d'un spectacle. Deux guichets la vendent au même moment : chacun lit le nombre de places restantes, trouve 1, vend un billet et écrit ce qu'il a lu moins un. Dans la figure, écrire places = lu - 1 écrit la dernière valeur que le guichet a lue, moins un, comme le double retrait du chapitre sur les transactions ; toute écriture pose sur places un verrou tenu jusqu'à la validation.

Entrelacées, les deux ventes laissent places à 0 : deux billets vendus, un seul décompté. Une contrainte qui interdit un nombre de places négatif, le C d'ACID, n'y voit rien, puisque 0 la respecte ; c'est en série qu'elle aurait servi, en refusant la seconde vente, celle qui écrit -1. Ce qui protège ici est l'isolation à son niveau le plus strict : le refus de la validation de B, ou, sous MySQL, l'interblocage qui annule B. L'un comme l'autre supposent une base unique, qui voit les deux ventes. Que les deux guichets écrivent sur deux copies séparées par une coupure du réseau, et chaque copie lit 1 sans pouvoir apprendre que l'autre vend : pour ne vendre qu'un billet, l'une des deux doit attendre le retour du réseau ou refuser la vente, donc renoncer à répondre ; pour répondre tout de suite, chacune vend, et la place part deux fois. Ce choix entre attendre et répondre est celui que pose le théorème CAP, plus bas, et l'exercice type 4 dit comment le trancher pour une réservation.

Ce qu'est une partition

Le mot sert aussi, dans d'autres chapitres, à désigner un morceau de données : la part qu'une règle de répartition confie à une machine, au chapitre sur la répartition du stockage, ou la part d'une table rangée à part, que le chapitre sur l'interrogation apprend à choisir. Ici, une partition est toujours une coupure du réseau.

Une partition ne se distingue pas d'une lenteur. Une machine qui ne répond pas peut être arrêtée, saturée, ou séparée par le réseau. De l'extérieur, les trois cas sont identiques : il ne se passe rien.

Le système doit pourtant décider, après un délai qu'il fixe lui-même, si l'autre est morte ou seulement injoignable. Attendre plus longtemps améliore la justesse de la décision et dégrade le temps de réponse pour tout le monde.

C'est pourquoi une partition n'est pas un événement rare et exceptionnel : à l'échelle d'un cluster, un délai d'attente dépassé est une partition, et cela arrive tous les jours.

Le théorème CAP, énoncé correctement

BASE, et la cohérence à terme

L'acronyme est un jeu de mots, acide contre base, et il ne faut pas y voir un modèle rigoureux. Il désigne une famille de compromis, dont le plus important est la cohérence à terme.

Les quorums, ou comment acheter la cohérence

La cohérence n'est pas un interrupteur mais un réglage, et ce réglage se calcule. Une donnée est écrite sur N copies ; une écriture est confirmée quand W copies ont répondu ; une lecture interroge R copies et retient la plus récente.

R + W > N garantit de lire la dernière écriture. Si le nombre de copies lues plus le nombre de copies écrites dépasse le nombre total de copies, alors les deux ensembles se recoupent forcément : la lecture touche au moins une copie à jour, et la reconnaît à son horodatage.

Sous cette condition, la garantie tient, à trois réserves près. Les W et les R copies doivent être prises parmi les N copies désignées de la donnée : certains systèmes, pour rester disponibles, écrivent sur une autre machine quand une copie manque, et l'intersection n'est plus assurée. La version la plus récente doit se reconnaître sans dépendre d'horloges décalées. Et la garantie porte sur une lecture, pas sur un « lire puis écrire » que deux clients feraient en même temps. En dessous de la condition, aucune configuration ne rattrape la garantie.

La figure suivante écrit une version nouvelle sur W copies, puis lit R copies choisies dans le pire cas : les moins à jour parmi celles qui répondent. Une machine se coupe et se rétablit d'un clic ; vue du client, une machine arrêtée, saturée ou séparée par le réseau ne se distinguent pas, d'où le mot « injoignable ».

Trois réglages méritent un nom, parce qu'ils correspondent à des choix courants.

Quand deux copies divergent

Un système qui accepte des écritures des deux côtés d'une partition se retrouve, à la réconciliation, avec deux versions d'une même donnée. Il faut trancher, et trois stratégies existent.

Trois façons de réconcilier, de la plus simple à la plus juste. La dernière écriture gagne. On compare les horodatages et on garde le plus récent. Simple, et destructeur par construction : de deux écritures concurrentes, une seule survit, même avec des horloges parfaites. Des horloges décalées, ce qui est toujours le cas, ajoutent un second défaut : la version gardée n'est pas forcément la plus récente. Dans les deux cas, une écriture est perdue silencieusement.

Le conflit est signalé. Le système conserve les deux versions et les rend toutes les deux à la lecture suivante, à charge pour l'application de choisir. Honnête, et exigeant.

La structure absorbe le conflit. Certaines structures de données sont conçues pour fusionner sans ambiguïté : un compteur où chaque copie retient ses propres incréments, un ensemble où l'on ne fait qu'ajouter, ou un ensemble où un élément retiré ne revient jamais. La fusion devient alors un calcul, et non une décision.

Le rapprochement avec le chapitre sur le découpage du calcul est direct, à une exigence près. Une donnée qui se fusionne sans arbitrage a une opération de fusion associative et commutative, comme une réduction qui se recolle : dans les deux cas, il s'agit de recombiner des résultats partiels sans savoir dans quel ordre ils sont arrivés. Entre copies, la fusion doit aussi être idempotente : deux copies échangent leur état encore et encore, la même fusion est rejouée, et la rejouer ne doit rien changer. C'est pourquoi un compteur se fusionne en prenant, copie par copie, le plus grand des deux nombres d'incréments connus, et non en les additionnant.

Mettre en pratique

Un quorum est un réglage à deux nombres, et une seule inégalité décide de ce qu'il garantit. Elle se vérifie en une soustraction.

L'inégalité, et ce qu'elle achète. La garantie de lire la dernière écriture repose sur $W + R > N$, quorums pris parmi les N réplicas désignés. Elle assure que l'ensemble des réplicas écrits et l'ensemble des réplicas lus ont au moins un élément commun, donc qu'au moins un répondant connaît la dernière valeur.
Le réglage se paie des deux côtés. Augmenter $W$ ralentit l'écriture et réduit le nombre de pannes tolérées en écriture ; augmenter $R$ ralentit la lecture. Un système à lectures fréquentes choisit donc un $R$ petit et un $W$ grand, et l'inverse pour un système à écritures fréquentes.