Modèles de cohérence, CAP et PACELC

Ce que « cohérent » veut dire une fois les données copiées

Dès qu’un système conserve plus d’une copie d’une donnée, sur des répliques situées dans différentes zones, dans des caches ou dans d’autres services, les copies peuvent diverger pendant un certain temps. Un modèle de cohérence est le contrat qui indique quelles divergences les clients peuvent observer. C’est une promesse sur ce que les lectures peuvent renvoyer compte tenu des écritures qui ont eu lieu, et donc une promesse sur les surprises que le code applicatif doit gérer.

Attention à ce mot aux sens multiples. Le C d’ACID (section 0.5) signifie qu’une transaction fait passer la base de données d’un état valide à un autre, en respectant des règles comme « un solde ne descend jamais en dessous de zéro ». Le C de CAP signifie quelque chose de différent et de plus restreint : chaque lecture se comporte comme s’il existait une copie unique et à jour. Les niveaux d’isolation des bases de données, comme sérialisable ou read committed, forment une troisième famille, qui concerne les transactions concurrentes ; ils sont traités dans transactions et isolation. Cette section porte sur les garanties des données répliquées.

Les modèles de cohérence, du plus fort au plus faible

La linéarisabilité, définie par Maurice Herlihy et Jeannette Wing en 1990, est le modèle à objet unique le plus fort. Chaque opération semble prendre effet instantanément à un moment situé entre son début et sa fin, et tous les clients voient le même ordre, qui respecte le temps réel : une fois qu’une écriture est terminée, chaque lecture qui commence ensuite la voit, ou voit une valeur plus récente. Le système se comporte comme s’il n’y avait qu’une seule copie. Exemple de livraison de repas : deux clients tentent d’utiliser le dernier code de réduction ; avec un stockage linéarisable, un seul des deux réussit et l’autre constate que le code n’est plus disponible, quelle que soit la réplique qu’il atteint.

La cohérence séquentielle, définie par Leslie Lamport en 1979 pour les multiprocesseurs, conserve l’ordre global unique et conserve les opérations de chaque client dans l’ordre où ce client les a émises, mais abandonne l’exigence de temps réel. Un client peut lire une valeur légèrement périmée, tant que tout le monde s’accorde sur l’ordre de toutes les écritures. Elle est rarement proposée sous ce nom dans les bases de données distribuées, mais elle explique l’écart entre « un ordre convenu » et « un ordre convenu qui correspond à l’horloge ».

La cohérence causale exige seulement que les opérations liées causalement soient vues dans le même ordre par tout le monde : si l’écriture de B dépendait du fait d’avoir vu A, personne ne doit voir B sans A. Des écritures concurrentes et sans lien peuvent être vues dans des ordres différents par différents clients. Exemple : un restaurant répond « Oui, c’est sans gluten » à la question d’un client dans la messagerie de la commande ; personne ne doit jamais voir la réponse sans la question. La cohérence causale est intéressante, car la carte des modèles de cohérence de Jepsen, très utilisée, la classe comme atteignable avec une disponibilité dite sticky : elle peut continuer à fonctionner pendant une partition, tant que chaque client reste sur la même réplique.

Les garanties de session, décrites par Douglas Terry et ses collègues en 1994, sont des promesses plus faibles, propres à chaque client, qui éliminent les anomalies les plus déroutantes. Lecture de ses propres écritures (read-your-writes) : après qu’un client a modifié l’adresse de livraison, la lecture suivante de ce client affiche la nouvelle adresse, même si d’autres utilisateurs la voient plus tard. Lectures monotones : une fois qu’un client a vu l’état de commande « en cours de livraison », il ne voit jamais plus tard « en préparation » parce qu’une lecture ultérieure a atteint une réplique en retard. (Deux autres garanties, les écritures monotones et les écritures qui suivent les lectures, contraignent l’ordre dans lequel les écritures d’un client sont appliquées.)

La cohérence à terme (eventual consistency), popularisée par Werner Vogels en 2008, est la plus faible des garanties utiles : si aucune nouvelle écriture n’arrive, toutes les répliques finissent par converger vers la même valeur. Elle ne dit rien du temps que cela prend ni de ce qui peut être lu entre-temps, et une implémentation de base qui résout les écritures en conflit en gardant celle qui a l’horodatage le plus récent, appelée last write wins (la dernière écriture l’emporte), écarte silencieusement l’autre. Des formes plus fortes, comme la cohérence à terme forte avec des types de données répliqués sans conflit (CRDT), garantissent que les répliques qui ont reçu les mêmes mises à jour ont le même état, en utilisant des types de données dont les mises à jour concurrentes fusionnent toujours, comme les compteurs et les ensembles.

CAP : ce qu’il dit vraiment

Eric Brewer a présenté l’idée de CAP sous forme de conjecture lors de sa conférence plénière au ACM Symposium on Principles of Distributed Computing (PODC) en 2000. En 2002, Seth Gilbert et Nancy Lynch en ont publié une démonstration formelle, ce qui en a fait un théorème pour leurs définitions précises. La cohérence (consistency) désignait la linéarisabilité. La disponibilité (availability) signifiait que chaque requête reçue par un nœud qui n’est pas tombé en panne doit donner lieu à une réponse. La tolérance aux partitions (partition tolerance) signifiait que le système tient ses promesses même quand le réseau perd un nombre arbitraire de messages entre les nœuds.

Lu attentivement, le théorème CAP a une portée étroite. Il dit que, lorsqu’une partition réseau se produit, de sorte que certains nœuds ne peuvent pas en joindre d’autres, un système répliqué doit choisir, pour chaque requête, entre cohérence et disponibilité. Un nœud coupé des écritures les plus récentes peut soit refuser de répondre (ou attendre que la partition soit résorbée), ce qui préserve la cohérence, soit répondre avec ce qu’il a, ce qui préserve la disponibilité au risque de renvoyer des données périmées ou d’accepter des écritures conflictuelles. Le diagramme montre ce dilemme pour un système de billetterie qui vend le siège 14C.

Plusieurs lectures répandues sont fausses. « Choisissez-en deux sur trois » suggère que la tolérance aux partitions est facultative, mais dans tout système qui communique à travers un réseau, les partitions se produisent, que vous les choisissiez ou non ; le seul vrai choix est la façon de se comporter quand elles surviennent. Un système dit « CA » est un système qui n’a pas décidé quoi faire lorsqu’une partition survient ; ce n’est défendable que là où les partitions sont pratiquement impossibles, comme sur un nœud unique. « Notre base de données est CP (ou AP) » est généralement imprécis : la disponibilité au sens de CAP est une propriété très forte que beaucoup de systèmes présentés comme hautement disponibles n’ont pas, et beaucoup de systèmes dits CP ne sont pas non plus linéarisables. Martin Kleppmann a soutenu en 2015 qu’il ne faudrait pas du tout qualifier les bases de données de CP ou d’AP, car la plupart ne correspondent à aucune des deux définitions et leur comportement dépend de leur configuration. « CAP explique notre latence » est faux également : CAP ne dit rien de ce qui se passe en l’absence de partition, c’est-à-dire la plupart du temps.

CAP, douze ans après

En 2012, dans un article d’IEEE Computer intitulé « CAP Twelve Years Later: How the Rules Have Changed », Brewer lui-même a expliqué que la formule « deux sur trois » avait induit les gens en erreur. Les partitions sont rares : un système peut donc offrir à la fois la cohérence et la disponibilité presque tout le temps ; le choix ne s’applique que pendant une partition, et seulement aux opérations concernées. Le choix n’a pas non plus à être global : des opérations différentes et des données différentes peuvent faire des choix différents.

Brewer recommandait de concevoir explicitement pour les partitions en trois étapes : détecter la partition, entrer dans un mode partition explicite dans lequel certaines opérations sont limitées (par exemple, accepter les commandes mais reporter les remboursements), et lancer ensuite un processus de rétablissement qui fusionne l’état et compense les erreurs commises pendant la partition. Il notait aussi que le C de CAP est la cohérence à copie unique, un sous-ensemble plus strict de ce que protège le C d’ACID, et que des invariants comme « ne jamais survendre » peuvent devoir être réparés après coup. Ce cadre mène directement aux compensations au niveau métier des sagas : une compagnie aérienne qui survend un vol dédommage le passager plutôt que de refuser toutes les réservations pendant une panne réseau.

PACELC : le compromis que vous payez chaque jour

Daniel Abadi a souligné, dans un billet de blog de 2010 puis dans un article d’IEEE Computer de 2012, « Consistency Tradeoffs in Modern Distributed Database System Design: CAP is Only Part of the Story », que CAP ignore le compromis auquel les concepteurs sont réellement confrontés la plupart du temps. PACELC se lit ainsi : s’il y a une Partition, choisir entre Availability (disponibilité) et Consistency (cohérence) ; Else (sinon), en fonctionnement normal, choisir entre Latency (latence) et Consistency (cohérence).

La moitié « else » (sinon) est l’ajout important. Pour qu’une lecture soit cohérente, un système répliqué doit se coordonner : envoyer l’écriture aux autres répliques et attendre leurs accusés de réception, ou diriger chaque lecture vers un leader, ou contacter plusieurs répliques et comparer. Chacune de ces options coûte des allers-retours réseau, et entre régions, un aller-retour peut coûter des dizaines, voire des centaines de millisecondes. Un système qui répond depuis la réplique la plus proche sans se coordonner est plus rapide, mais ses données peuvent être périmées. Ce compromis se paie à chaque requête, qu’il y ait partition ou non.

Des classifications PACELC sont souvent citées, comme PA/EL pour les systèmes réglés pour la vitesse et la disponibilité, et PC/EC pour les systèmes qui préfèrent toujours la cohérence. Considérez-les comme la description d’une configuration, pas d’un produit : la même base de données peut être PA/EL dans un déploiement et PC/EC dans un autre, selon des paramètres choisis par table, par requête ou par appel.

Les quorums : régler la cohérence par l’arithmétique

Les stockages répliqués sans leader, dans le style de l’article Dynamo d’Amazon (2007), permettent à chaque opération de choisir combien de répliques impliquer. Avec N répliques d’un élément, une écriture est confirmée quand W répliques l’ont stockée, et une lecture recueille les réponses de R répliques et renvoie la version la plus récente parmi elles. Si R + W > N, chaque ensemble de lecture recoupe chaque ensemble d’écriture sur au moins une réplique : une lecture inclura donc au moins une copie de la dernière écriture confirmée.

Le choix de R et de W arbitre entre cohérence, latence et disponibilité. Des valeurs plus basses signifient attendre moins de répliques, et les plus rapides, et tolérer davantage de pannes, au prix de lectures éventuellement périmées. Des valeurs plus élevées signifient l’inverse. Les écritures sont généralement envoyées de toute façon aux N répliques ; W décide seulement combien d’accusés de réception le client attend.

Le recouvrement des quorums est nécessaire pour des lectures à jour, mais il ne constitue pas, à lui seul, la linéarisabilité. Des écritures concurrentes peuvent être ordonnées par des horodatages issus d’horloges en désaccord, si bien qu’une écriture plus tardive peut perdre avec last-write-wins. Une écriture qui a échoué après avoir atteint certaines répliques peut rester visible sur celles-ci. Les quorums « sloppy » (approximatifs), qui acceptent des écritures sur des nœuds de remplacement pendant les pannes, brisent le recouvrement. Et deux lectures qui recoupent une écriture encore en cours peuvent voir la nouvelle valeur puis l’ancienne, à moins que le lecteur ne répare les répliques en retard avant de répondre. Les stockages qui ont besoin d’une véritable sémantique compare-and-set ajoutent un protocole de consensus, comme les lightweight transactions d’Apache Cassandra, fondées sur Paxos, pour ces seules opérations.

Comment configurer des bases de données bien connues

Les produits réels se situent rarement en un point unique de l’échelle. Ils exposent des paramètres, et la bonne description est « comment ce déploiement est configuré ». Quatre exemples courants suivent ; consultez la documentation actuelle de la version que vous utilisez, car les valeurs par défaut changent d’une version à l’autre.

Choisir la cohérence selon le cas d’usage

L’habitude la plus utile est de cesser de demander « notre système est-il cohérent ? » et de demander, pour chaque donnée et chaque opération : que se passe-t-il de travers si un client voit une valeur périmée ou réordonnée, et combien cela coûte-t-il ? Les mouvements d’argent, les ressources uniques et les invariants justifient généralement une cohérence forte et sa latence. Les compteurs, les fils d’actualité, les recommandations et l’analytique, généralement pas. Beaucoup d’anomalies visibles par les utilisateurs disparaissent avec les seules garanties de session, qui sont peu coûteuses : dirigez les lectures d’un utilisateur vers le primaire pendant quelques secondes après que cet utilisateur a écrit, ou transportez un jeton de version dans la session et attendez que la réplique l’ait rattrapé.