CAP douze ans plus tard : comment les "règles" ont changées

Cet article a été publié pour la première fois dans le magazine Computer et vous est présenté par InfoQ et IEEE Computer Society.

Le théorème CAP affirme que tout système à état partagé en réseau ne peut avoir que deux des trois propriétés désirables. Néanmoins, en gérant explicitement les partitions, les concepteurs peuvent optimiser la cohérence et la disponibilité, atteignant ainsi un compromis des trois.

Pendant la décennie suivant son apparition, les concepteurs et chercheurs ont utilisé (et parfois abusé) le théorème CAP comme d'un prétexte pour explorer un large panel de systèmes distribués. Le mouvement NoSQL l'a aussi utilisé comme un argument contre les bases de données traditionnelles.

Le théorème CAP déclare que tout système à état partagé en réseau ne peut avoir au plus que deux des trois propriétés désirées suivantes :

• cohérence (C), équivalent à n'avoir qu'une seule copie à jour des données ;
• haute disponibilité (A, NdT: Availability) des données (pour les mises à jour) ;
• tolérance au partitionnement en sous-réseaux (P, NdT: network Partition)

La formulation de CAP a rempli son objectif, qui était d'ouvrir les esprits des concepteurs à un éventail plus large de systèmes et de compromis; en effet, dans la décennie passée, une vaste panoplie de nouveaux systèmes ont émergé, ainsi que de nombreux débats sur les mérites relatifs de la cohérence et de la disponibilité. La formulation "deux des trois" a toujours été trompeuse parce qu'elle tend trop à simplifier les tensions entre ces propriétés alors que les nuances comptent. CAP ne restreint qu'une petite fraction des concepts possibles : disponibilité et cohérence parfaite en présence de partitions réseaux, qui sont rares.

Bien que les concepteurs doivent toujours choisir entre cohérence et disponibilité quand des partitions sont présentes, il existe une grande souplesse pour gérer les partitions et les restaurer. Les objectifs modernes de CAP devraient être d'optimiser les combinaisons de cohérence et de disponibilité qui sont pertinentes pour une application spécifique. Une telle approche intègre les plans d'exploitation au cours d'une partition réseau, aidant ainsi les concepteurs à penser CAP au delà de ses limites historiquement perçues.

Pourquoi "deux des trois" est trompeur

La façon la plus simple de comprendre CAP est de penser à deux noeuds dans des sections opposées d'une partition réseau. Autoriser au moins un noeud à modifier son état va conduire les noeud à être incohérents, par conséquent renoncer à C. De la même façon, si le choix est de maintenir la cohérence, une des partie de la partition doit agir comme si elle était indisponible, donc renoncer à P. La conviction générale est que pour des systèmes distribués très étendus, les concepteurs ne peuvent renoncer à P et doivent donc faire le choix difficile entre C et A. Dans un certain sens, le mouvement NoSQL consiste à faire des choix qui se concentrent sur la disponibilité en premier lieu, et la cohérence en second; les bases de données qui adhèrent aux propriétés ACID (Atomicité, Cohérence, Isolation, Durabilité) font l'inverse. Le paragraphe "ACID, BASE et CAP" explique cette différence plus en détails.

En fait, c'est cette discussion qui a mené au théorème CAP. Au milieu des années 90, mes collègues et moi-même construisions un ensemble de systèmes basés sur des clusters répartis sur de grandes zones (essentiellement du cloud computing primitif), incluant des moteurs de recherche, des proxys cache, et des systèmes de distribution de contenu. ¹ En raison des objectifs de chiffre d'affaire et des spécifications contractuelles, la disponibilité du système était très importante, nous nous trouvions souvent à choisir d'optimiser la disponibilité grâce à des stratégies comme employer des caches ou tracer les mises à jour pour une réconciliation ultérieure. Bien que ces stratégies améliorent la disponibilité, c'est au prix d'une cohérence diminuée.

La première version de ce débat 'cohérence contre disponibilité' est apparue avec ACID contre BASE, ² qui n'a pas été bien reçue à l'époque, principalement parce que les gens aiment les propriétés ACID et sont réticents à les abandonner. L'objectif du théorème CAP était de justifier les besoins d'explorer un plus large éventail de designs, d'où la formulation "deux des trois". Le théorème est apparu à l'automne 1998. Il a été publié en 1999 ³ et présenté lors du discours d'ouverture du Symposium on Principles of Distributed Computing en 2000,⁴ qui a conduit à sa preuve.

Comme la section "Confusion CAP" l'explique, la vue "deux des trois" est trompeuse sur plusieurs points. D'une part, parce que les partitions sont rares, il y a peu de raison d'abandonner C ou A quand le système n'est pas partitionné. D'autre part, le choix entre C et A peut intervenir plusieurs fois dans le même système à des granularités variables ; non seulement les sous systèmes peuvent faire des choix différents, mais le choix peut aussi changer en fonction des opérations, des données ou des utilisateurs impliqués. Enfin, les trois propriétés sont représentées par un domaine continu de valeurs plutôt que par des valeurs binaires. La disponibilité varie de 0 à 100%, il y a aussi de nombreux niveaux de cohérence, et de même les partitions en sous-réseaux ont leur nuances, incluant le désaccord au sein du système sur l'existence d'un partitionnement.

Explorer ces nuances requiert de revoir la manière traditionnelle de gestion des partitions, c'est l'enjeu fondamental. Puisque les partitions sont rares, CAP devrait permettre un C parfait et un A presque permanent, mais lorsqu'un partitionnement réseau est en cours, une stratégie qui détecte les partitions et les prends en compte est requise. Cette stratégie doit avoir trois étapes : détecter la partition, entrer dans un mode de partitionnement explicite qui peut limiter certaines opérations, et initier un processus de restauration de la cohérence et de compensation des erreurs faites durant la partition.

ACID, BASE et CAP

ACID et BASE représentent deux philosophies de conception aux extrémités opposées du spectre cohérence-disponibilité. Les propriétés ACID se concentrent sur la cohérence et sont l'approche traditionnelle des bases de données. Mes collègues et moi-même avons créé BASE à la fin des années 90 pour saisir les concepts émergents de la haute disponibilité et rendre explicite à la fois le choix et le spectre. Les systèmes étendus modernes et à grande échelle, y compris le cloud, utilisent une combinaison des deux approches.

Bien que les deux acronymes soient plus mnémoniques que précis, l'acronyme BASE (étant le second apparu) est un peu plus délicat : Basically Available, Soft state, Eventually consistent (NdT Simplement disponible, état souple, finalement consistant). Soft state et eventual consistency sont des techniques qui fonctionnent bien en présence de partitions réseau and donc améliorent la disponibilité.

La relation entre CAP et ACID est plus complexe et souvent incomprise, en partie parce que les C et A d'ACID représentent des concepts différents des mêmes lettres dans CAP et en partie parce que choisir la disponibilité affecte seulement certaines des garanties ACID. Les quatre propriétés ACID sont :

• Atomicité (A). Tout système bénéficie d'opérations atomiques. Quand l'objectif est la disponibilité, toutes les parties de la partition doivent toujours utiliser des opérations atomiques. De plus, des opérations atomiques de plus haut niveau (celles qu'impliquent ACID) simplifient la restauration.

• Cohérence (C). Dans ACID, le C signifie qu'une transaction préserve toutes les règles des bases de données, telles que les clés uniques. En comparaison, le C de CAP ne se réfère qu'a une cohérence de copie unique, un sous-ensemble strict de la cohérence ACID. Plus généralement, maintenir des invariants durant les partitions peut être impossible, d'où le besoin de bien choisir quelles opérations interdire et comment ensuite restaurer les invariants.

• Isolation (I). L'isolation est au coeur du théorème CAP : si un système nécessite l'isolation ACID, il peut opérer sur au plus une partie durant une partition réseau. La possibilité de sérialiser les transactions nécessite des communications en général et échoue durant les séparations réseau. Des définitions plus faibles de l'exactitude sont viables durant les partitions en compensant durant la phase de restauration.

• Durabilité (D). Comme pour l'atomicité, il n'y a pas de raison d'abandonner la durabilité, bien que le développeur puisse choisir d'éviter d'en avoir besoin grâce à un état flexible (dans le style de BASE) à cause de son coût. Un subtilité est que durant la restauration il est possible d'inverser les opérations durables qui violent un invariant pendant l'opération. Néanmoins, au moment de la restauration, avec un historique durable de toutes les parties de la partition, de telles opération peuvent êtres détectées et corrigées. En général, effectuer des transactions ACID dans chaque partie de la partition rend la restauration plus simple et fourni un cadre pour compenser les transaction qui peut être utilisé pour récupérer d'une partition.

Connexion entre CAP et latence

Dans son interprétation classique, le théorème CAP ignore la latence, bien qu'en pratique, la latence et les partitions soient profondément liées. D'un point de vue opérationnel, l'essence de CAP prend place durant un timeout, un instant où le programme doit faire une décision fondamentale, la décision de partition :

• annuler l'opération et donc diminuer la disponibilité ou
• effectuer l'opération et donc risquer l'inconsistance.

Retenter la communication pour atteindre la cohérence, par exemple, via Paxos ou un two-phase commit, ne fait que repousser le moment de prise de décision. A un moment, le programme doit prendre la décision ; retenter la communication indéfiniment est en essence choisir C par rapport à A.

Donc, pragmatiquement, une partition réseau est à un moment liée à la communication. Échouer à atteindre la cohérence durant le même laps de temps implique une partition et donc un choix entre C et A pour cette opération. Ces concepts saisissent l'essence du principal problème concernant la latence : est ce que les deux parties progressent sans communication ?

Cette vue pragmatique amène plusieurs conséquences importantes. La première est qu'il n'y a pas de notion globale de partition réseau, puisque certains noeuds peuvent détecter une partition, et certains peuvent ne pas la détecter. La seconde est que les noeuds peuvent détecter une partition et entrer dans un mode partition - une part centrale de l'optimisation de C et A.

Enfin, cette façon de voir les choses signifie que les concepteurs peuvent définir des limites de timeout intentionnellement en fonction des temps de réponses cibles ; les systèmes avec des limites plus étroites vont probablement entrer en mode partition plus souvent et à des périodes où le réseau est simplement lent et pas réellement partitionné.

Parfois, il est sensé d'abandonner un C fort pour éviter la haute latence requise pour maintenir la cohérence sur une zone étendue. Le système PNUTS de Yahoo s'expose à l'incohérence en maintenant des copies distantes de façon asynchrone ⁵ Néanmoins, il rend la copie maîtresse locale, ce qui diminue la latence. Cette stratégie fonctionne bien en pratique parce que les données d'un utilisateur sont naturellement réparties en fonction de la localisation (habituelle) de l'utilisateur. Idéalement, la copie maîtresse des données de chaque utilisateur est proche.

Facebook utilise la stratégie inverse: ⁶ la copie maîtresse est toujours à un seul endroit, donc un utilisateur distant obtient une copie plus proche mais potentiellement périmée. Néanmoins, quand un utilisateur met à jour ses pages, la mise à jour est faite directement sur la copie maîtresse de même que toutes les lectures de l'utilisateur pendant une courte période, malgré la latence plus élevée induite. Après 20 secondes, le trafic de l'utilisateur revient sur la copie la plus proche, qui doit avoir durant cette période reproduit les mises à jour.

Confusion CAP

Certains aspects du théorème CAP sont souvent mal compris, en particulier la portée de la disponibilité et de la cohérence, qui peuvent mener à des résultats indésirables. Si les utilisateurs ne peuvent pas du tout atteindre le service, il n'y a pas de choix particulier entre C et A à part quand une partie du service tourne sur le client. Cette exception, communément connue comme opération déconnectée ou mode hors ligne, ⁷ devient de plus en plus importante. Certaines particularités de HTML5 - en particulier, le stockage persistant coté client, rendent les opérations déconnectées plus simples à mettre en place. Ces systèmes choisissent normalement A plutôt que C et donc doivent récupérer des longues partitions.

La portée de la cohérence reflète l'idée que, dans certaines limites, l'état est cohérent, mais en dehors de ces limites les paris sont ouverts. Par exemple, dans une partition primaire, il est possible d'assurer la cohérence complète et la disponibilité, alors qu'en dehors de la partition, le service est indisponible. Paxos et les systèmes de multicast atomiques correspondent typiquement à ce scénario. ⁸ Chez Google, la partition primaire réside dans un seul datacenter ; pourtant, Paxos est utilisé pour assurer le consensus global, comme dans Chubby, ⁹ et le stockage durable avec haute disponibilité, comme Megastore ¹⁰.

Des sous ensembles indépendants et cohérents dans leur périmètre peuvent évoluer durant une partition réseau, bien qu'il ne soit pas possible d'assurer d'invariants globaux. Par exemple, avec le sharding, dans lequel les concepteurs pré-partitionnent les données sur les noeuds, il est hautement probable que chaque shard évolue durant une partition. A l'inverse, si l'état pertinent est réparti sur les membres d'une partition ou si des invariants globaux sont nécessaires, alors au plus une seule partition peut évoluer et au pire, aucune évolution n'est possible.

Est ce que choisir la cohérence et la disponibilité (CA) comme les "deux des trois" à un sens ? Comme certains chercheurs le font remarquer, ce à quoi correspond d'abandonner P n'est pas clair. ^11,12 Un concepteur peut il choisir de ne pas avoir de partition réseau ? Si le choix est CA, et qu'il y a une partition, le choix doit retomber sur C ou A. Il vaut mieux y réfléchir de façon probabiliste : choisir CA doit signifier que la probabilité d'une partition réseau est très inférieure aux autres pannes du système, tels que les désastre ou des pannes multiples et simultanées.

Une telle vue à un sens parce que les systèmes réels perdent à la fois C et A dans certains scénarios de pannes, donc les trois propriétés sont une question de degré. En pratique, la plupart des groupes partent du principe qu'un datacenter (sur un seul site) n'a pas de partition réseau interne, et donc conçoivent pour CA à l'intérieur d'un datacenter, ils abandonnent la cohérence parfaite sur les larges zones pour de meilleures performances.

Un autre aspect de la confusion autour de CAP est le coût caché de l'abandon de la cohérence, qui est le besoin de connaître les invariants du système. La beauté subtile d'un système cohérent est que les invariant tendent à tenir même quand le concepteur ne sait pas qu'ils en sont. Par conséquence, une large gamme d'invariants raisonnables fonctionnera correctement. A l'inverse, quand les concepteurs choisissent A, qui requiert de restaurer les invariants après une partition réseau, ils doivent êtres explicites sur tous les invariants, ce qui est à la fois un défi et sujet à erreur. Au coeur, c'est le même problème de mises à jour concurrentes qui rend le multithreading plus difficile que la programmation séquentielle.

Gérer les partitions

Le cas stimulant pour les concepteurs est d'atténuer les effets d'une partition réseau sur la cohérence et la disponibilité. L'idée clé est de gérer les partitions de manière très explicite, incluant non seulement la détection, mais aussi un processus spécifique de restauration et un plan pour tous les invariants qui peuvent êtres violés durant une partition. Cette approche a trois étapes.

• détecter le début d'une partition,
• entrer dans un mode explicite de partition qui peut limiter certaines opération, et
• initier la restauration de l'état de partition quand la communication est restaurée.

La dernière étape vise à restaurer la cohérence et compenser les erreurs que le programme a fait pendant que le système était partitionné.

La figure 1 montre l'évolution d'une partition. Les opérations normales sont une séquences d'opérations atomiques, et donc les partitions commencent toujours entre des opérations. Une fois que le système subit un timeout, il détecte une partition et le membre détectant la partition entre dans le mode approprié. Si une partition existe réellement, chaque membre va entrer dans ce mode, mais des partitions d'un seul coté sont possibles. Dans de tels cas, l'autre partie communique comme habituellement, et soit ce membre répond correctement, soit aucune communication n'a été requise ; dans tous les cas, les opérations restent cohérentes. Néanmoins, puisque le membre détectant la partition peut avoir des opérations incohérentes, il doit entrer dans le mode de partition. Les systèmes qui utilisent un quorum sont un exemple de cette partition d'un sous-ensemble. Un sous-ensemble va avoir un quorum et peut continuer à opérer, mais les autres ne le peuvent. Les systèmes qui supportent les opérations déconnectées ont clairement une notion de mode partition, comme certains systèmes de multicast atomique, tels que les JGroup de Java.

Une fois que le système entre en mode de partition, deux stratégies sont possibles. La première est de limiter certaines opération, réduisant ainsi la disponibilité. La seconde est d'enregistrer des informations supplémentaires sur les opérations qui seront utiles durant la restauration. Continuer à tenter de communiquer va permettre au système de détecter quand la partition est terminée.

Quelles opérations doivent continuer ?

Décider quelles opérations doivent êtres limitées dépend principalement des invariants que le système doit maintenir. Étant donné un ensemble d'invariants, le concepteur doit décider de maintenir ou non un invariant particulier durant une partition ou risquer de le violer en le restaurant pendant la restauration. Par exemple, pour l'invariant d'unicité des clés dans une table, les concepteurs décident typiquement de risquer cet invariant et d'autoriser les clés dupliquées durant une partition. Les clé dupliquées sont simples à détecter durant la restauration, et en supposant que les clés peuvent êtres fusionnées, le concepteur peut facilement restaurer l'invariant.

Pour un invariant qui doit être maintenu durant une partition, le concepteur doit interdire ou modifier les opérations qui pourraient le violer. (En général, il n'y a pas de moyen de savoir si l'opération va vraiment violer l'invariant, puisque l'état de l'autre membre n'est pas connu.) Les évènements externalisées, comme charger une carte de crédit fonctionnent souvent de cette manière. Dans ce cas, la stratégie est d'enregistrer l'action et l'exécuter après la restauration. De telles transactions font typiquement parti d'un workflow plus large qui a un état explicite de gestion des demandes, et il y a peu de défauts à retarder l'opération jusqu'a la fin de la partition réseau. Le concepteur abandonne A d'une façon que l'utilisateur ne voit pas. L'utilisateur sait seulement qu'il a placé un ordre et que le système va l'exécuter plus tard.

Plus généralement, le mode partition amène un défi fondamental pour l'interface utilisateur, qui est de lui communiquer que des tâches sont en cours mais non terminées. Les chercheurs ont exploré ce problème en détail pour les opérations déconnectés, qui est simplement une longue partition. L'application calendrier de Bayou, par exemple, montre les entrées potentiellement incohérentes dans une couleur différente. ¹³ De telles notifications sont régulièrement visibles à la fois dans les applications avec un workflow, comme le commerce avec notifications par email, et dans les services cloud avec un mode hors ligne, comme Google Docs.

Une raison de se concentrer explicitement sur les opérations atomiques, plutôt que simplement les lectures et écritures, est qu'il est beaucoup plus simple d'analyser l'impact des opérations de haut niveau sur les invariants. Fondamentalement, le concepteur doit construire une table qui croise toutes les opérations et tout les invariants et décide pour chaque entrée si cette opération peut violer l'invariant. Si c'est le cas, le concepteur doit décider d'interdire, repousser ou modifier l'opération. En pratique, cette décision peut aussi dépendre de l'état connu, des arguments ou des deux. Par exemple dans les systèmes avec un noeud hébergeant certaines données, cinq opérations peuvent typiquement êtres effectuées sur le noeud hébergeant mais pas sur les autres.

La meilleure façon de suivre l'historique des opérations de chaque coté est d'utiliser des vecteurs de versions, qui vont stocker les dépendances de cause entre les opérations. Les éléments du vecteurs sont une paire (noeud, temps logique), avec une entrée pour chaque noeud qui a mis à jour l'objet et le moment de sa dernière mise à jour. Étant donné deux versions d'un objet, A et B, A est plus récent que B si, pour chaque noeud en commun de leur vecteur, les dates de A sont plus récentes que celles de B et au moins une des dates de A est plus récente.

S'il est impossible d'ordonner les vecteurs, alors les mises à jour ont été concurrentes et potentiellement incohérentes. Donc, étant donné les vecteurs de versions de chaque coté, le système peut facilement dire quelles opération sont déjà dans un ordre connu et lesquelles ont été exécutés en concurrence. Des travaux récents ¹⁴ ont prouvé que ce type de dépendance de causalité est en général la meilleure issue possible si le concepteur choisi de se concentrer sur la disponibilité.

Restauration après une partition réseau

A un instant donné, la communication reprend et la partition termine. Durant la partition, chaque membre a été disponible et a donc évolué, mais la partition a retardé certaines opération et violé certains invariant. A ce moment, le système connaît l'état et l'historique de chaque membre puisqu'il a gardé un journal durant la partition. L'état est moins utile que l'historique, à partir duquel le système peut déduire quelles opérations ont vraiment violé les invariants et quelles résultats ont été externalisés, en incluant les réponses envoyées aux utilisateurs. Le concepteur doit résoudre deux problèmes complexes durant la restauration :

• l'état de chaque membre doit devenir cohérent et
• il doit y avoir une compensation pour les erreurs effectuées durant le mode partition.

Il est en général plus simple de corriger l'état courant en partant de l'état au moment de la partition et ré-exécuter chaque ensemble d'opération en maintenant la cohérence de l'état en cours de route. Bayou a fait ça de façon explicite en rollbackant la base de données vers un état correct et en rejouant l'ensemble complet des opération dans un ordre bien défini et déterministe de façon à ce que tous les noeuds atteignent le même état.¹⁵ De façon similaire, les systèmes de gestion de version tels que Concurrent Versioning System (CVS) partent d'une état partagé cohérent et appliquent les mises à jour pour fusionner les branches.

La plupart des systèmes ne peuvent pas toujours fusionner les conflits. Par exemple, CVS a parfois des conflits que l'utilisateur doit résoudre manuellement, et le mode hors ligne des systèmes de wiki laisse typiquement les conflits dans le document final qui nécessite une édition manuelle. ¹⁶

A l'inverse, certains systèmes peuvent toujours fusionner les conflits en choisissant certaines opérations. Un exemple spécifique est l'édition de texte dans Google Docs ¹⁷, qui limite les opérations à appliquer à un style et ajouter ou supprimer du texte. Bien que le problème général de la résolution de conflit soit insoluble, en pratique les concepteurs peuvent choisir de limiter l'utilisation de certaines opérations durant la partition de façon à ce que le système puisse automatiquement fusionner l'état pendant la restauration. Retarder les opérations risquées est une implémentation relativement simple de cette stratégie.

Utiliser des opérations commutatives est la meilleure façon d'approcher d'un framework général pour la convergence automatique d'état. Le système concatène les logs, les tri dans un certain ordre, et les exécutes. La commutativité implique la possibilité de réarranger les opérations dans un ordre global consistent et préférable. Malheureusement, utiliser uniquement des opérations commutatives est plus complexe qu'il n'y parait ; par exemple, l'addition est commutative, mais l'addition avec vérification de conditions ne l'est pas (par exemple un solde à l'équilibre).

Des travaux récents par Marc Shapiro et ses collègues à l'INRIA ^18,19 ont grandement améliorés l'utilité des opérations commutatives pour la convergence d'états. L'équipe a développé des structures de données répliquées commutatives (Ndt : commutative replicated data types - CRDTs), une classe de structures de données qui convergent de façon déterministe après une partition réseau, et décrit comment utiliser ces structures pour :

• assurer que toutes les opérations durant une partition sont commutatives,
• ou représentent des valeurs sur une lattice et assurent que toutes les opérations durant une partition réseau sont incrémentés de façon monotone en ce qui concerne cette lattice.

Cette approche fait converger les états en utilisant la valeur maximale des différentes parties. C'est une formalisation et une amélioration de ce qu'Amazon fait avec son panier d'achat ²⁰ après une partition réseau, la valeur après convergence est l'union des deux paniers, l'union étant une opération ensembliste monotone. La conséquence de ce choix est que des éléments supprimés peuvent réapparaître.

Néanmoins, les CRDTs peuvent aussi implémenter des ensembles qui peuvent ajouter et supprimer des éléments tout en tolérant les partitions. L'essence de cette approche est de maintenir deux ensembles, un pour les éléments ajoutés et un pour les éléments supprimés, la différence étant la présence dans un des ensembles ou dans l'autre. Chaque ensemble simplifié converge, et en conséquence la différence converge aussi. Le système peut faire le ménage simplement en enlevant les éléments supprimés. Cependant, de telles opération de nettoyage sont généralement possibles uniquement quand le système n'est pas en partition. En d'autres mots, le concepteur doit interdire ou retarder certaines opération durant une partition, mais celles-ci sont des opérations de nettoyage qui ne limitent pas la disponibilité perçue. Donc, en implémentant l'état avec des CRDTs, le concepteur peut choisir A et toujours assurer que l'état converge automatiquement après une partition.

Compenser les erreurs

En plus de calculer l'état post-partition, il y a aussi le problème plus complexe de corriger les erreurs faites durant le partitionnement. Le suivi et la limitation des opérations en mode partition permet de savoir quels invariants peuvent avoir été violés, ce qui va à son tour permettre au concepteur de créer une stratégie de restauration pour chacun de ces invariants. Typiquement, le système découvre les violation durant la restauration et doit implémenter les correctifs à cet instant.

Il y a plusieurs façons de corriger les invariants, y compris les manières triviales telles que "le dernier à écrire gagne" (qui ignore certaines mises à jour), des approches plus intelligentes de fusion des opérations, et l'escalade humaine. Un exemple de ce dernier est le surbookage des avions : l'embarquement est en un certain sens une restauration de partition avec un invariant étant qu'il doit y avoir autant de sièges que de passagers. Si il y a trop de passagers, certains vont perdre leur sièges, et idéalement le service client va donner des compensations à ces clients.

L'exemple de l'avion montre aussi une erreur externalisée : si l'avion n'avait pas précisé que le passager aura un siège, corriger le problème serait beaucoup plus simple. Il y a une autre raison pour retarder les opérations risquées : au moment de la restauration, la vérité est connue. L'idée de la compensation est vraiment au coeur de la correction d'erreur, le concepteur doit créer des opérations de compensations qui vont à la fois restaurer un invariant et de façon plus générale corriger les erreurs externalisées.

Techniquement, les CRDTs permettent uniquement des invariants localement vérifiables - une limitation qui rend la compensation non nécessaire mais diminue la puissance de l'approche. Cependant, une solution qui utilise les CRDTs pour la convergence d'état peut autoriser la violation temporaire d'un invariant global, faire converger l'état après la partition, et ensuite exécuter les compensations nécessaires.

Récupérer d'erreurs externalisées requiert typiquement un peu d'historique sur les sorties. En prenant l'exemple d'une personne ivre composant des numéros, dans lequel cette personne ne se rappelle pas avoir effectué divers appels téléphoniques sous l'emprise de l'alcool la nuit précédente. L'état de cette personne à la lumière du jour peut être clair, mais le journal d'appel montre une liste d'appels, dont certains peuvent avoir été des erreurs. Les appels sont les effets extérieurs de l'état de la personne (l'ébriété). Puisque cette personne ne peut pas se rappeler des appels, il peut être complexe de compenser les problèmes qu'ils peuvent avoir causés.

Dans un contexte automatisé, un ordinateur peut exécuter des ordres en double pendant une partition. Si le système peut distinguer deux ordres intentionnels de deux ordres dupliqués, il peut annuler un des duplicats. Si les conséquences sont externalisés, une stratégie de compensation serait de générer automatiquement un email au client expliquant que le système à accidentellement exécuté l'ordre en double mais que l'erreur à été corrigée et attacher un bon pour une remise sur la prochaine commande. Sans un historique correct, la charge de détection de l'erreur est pour le client.

Des chercheurs ont exploré de façon formelle la compensation de transactions comme une façon de gérer les transactions de longue durée. ^{21, 22}. Les transactions de longue durée font face à une variante de la décision de partition : est-il préférable de conserver les locks pour une longue période pour assurer la cohérence, ou de les libérer tôt et exposer des données non commités à d'autres transactions pour permettre une meilleure concurrence ? Un exemple typique est d'essayer de mettre à jour tous les enregistrements des employés comme une seule transaction. Sérialiser cette transaction de la façon classique bloque tous les enregistrements et empêche la concurrence. Compenser les transactions prend une approche différente en découpant la grande transaction en une saga, qui consiste en de multiples sous transactions, chacune d'entre elle étant commité au fur et à mesure. Donc, pour interrompre la grande transaction, le système doit défaire chacune des sous-transactions déjà commité en créant une nouvelle transaction qui corrige ses effets - la transaction de compensation.

En général, le but est d'éviter d'annuler les autres transactions qui ont utilisées les données commités de manière erronées (pas d'annulation en cascade). La validité de cette approche ne dépend pas de la possibilité de sérialiser ou de l'isolation, mais plutôt de l'effet net que la séquence de transactions sur l'état et les sorties. C'est à dire, après compensation, essentiellement, est ce que la base de données se trouve dans un état équivalent à celui dans lequel elle aurait été si les sous transactions n'avaient jamais été exécutées ? L'équivalence doit inclure les actions externalisées ; par exemple, rembourser un achat dupliqué n'est pas exactement la même chose que n'avoir pas facturé le client en premier lieu, mais on peut considérer que c'est équivalent. La même idée est maintenue dans une restauration de partition. Un fournisseur de service ou produit ne peut pas toujours annuler les erreurs directement, mais il doit chercher à les admettre et prendre de nouvelles actions compensatrices. Comment appliquer ces idées au mieux à une restauration de partition est un problème ouvert. La partie "Compenser les problèmes pour un distributeur de billets" décrit certains des problèmes pour une certaine zone d'application.

Les concepteurs de systèmes ne devraient pas aveuglément sacrifier la cohérence ou la disponibilité quand une partition existe. En utilisant l'approche proposée, ils peuvent optimiser chacune de ces propriétés grâce à une gestion soigneuse des invariants durant les partitions. Avec de nouvelles techniques, comme les vecteurs de versions et les CRDTs, introduites dans des frameworks qui simplifient leur utilisation, de telles optimisations devraient devenir plus courantes. Néanmoins, à la différence des transactions ACID, cette approche requiert davantage de réflexion en amont du déploiement par rapport aux stratégies passées, et le meilleure solution dépendra fortement de détails sur les invariants et opérations du service.

Compenser les problèmes pour un distributeur de billets

Dans la conception d'un distributeur de billets, la cohérence forte pourrait sembler le choix logique, mais en pratique A est un meilleur atout que C. La raison est suffisamment évidente : une meilleure disponibilité signifie de meilleurs revenus. Quoi qu'il en soit, le design des distributeurs de billets est un bon contexte pour revoir certains des challenges impliqués dans la compensation des violations d'invariant durant une partition.

Les opérations essentielles d'un distributeur de billets sont le dépôt, le retrait et la vérification du solde. L'invariant clé est que le solde doit être positif ou nul. Puisque un seul retrait peut violer cet invariant, il nécessite un traitement spécial, mais les deux autres opérations peuvent toujours êtres effectuées.

Le concepteur d'un système de distributeur de billets peut choisir d'interdire les retraits durant une partition, puisque qu'il est impossible de connaître le vrai solde à cet instant, mais cela compromettrait la disponibilité. A la place, en utilisant un mode stand-in (mode de partition), les distributeurs de billets modernes limitent le retrait net à au plus k, avec k pouvant être $200. En dessous de cette limite, les retraits fonctionnent complètement ; quand le solde atteint la limite, le système interdit le retrait. Le distributeur choisit une limite sophistiquée sur la disponibilité qui permet le retrait mais limite le risque.

Quand la partition prend fin, il doit y avoir un moyen de restaurer la consistance et compenser les erreurs effectuées pendant que le système était partitionné. Restaurer l'état est simple puisque les opérations sont commutatives, mais la compensation peut prendre plusieurs formes. Un solde final négatif viole l'invariant. Dans le cas normal, le distributeur a fourni les billets, ce qui rend l'erreur externe. La banque compense en facturant des frais et attendant un remboursement. Étant donné que le risque est limité, le problème n'est pas grave. Cependant, supposons que le solde ait été négatif à un moment donné durant la partition (inconnu du distributeur), mais qu'un dépôt ultérieur l'ai rendu à nouveau créditeur. Dans ce cas, la banque peut toujours facturer des frais de découvert rétroactivement, ou elle peut l'ignorer, puisque le client a déjà effectué le paiement nécessaire.

En général, en raison des délais de communication, le système bancaire ne dépend pas de la cohérence pour la validité, mais plutôt sur l'audit et la compensation. Un autre exemple de cela est le "check kiting", dans lequel un client effectue des retraits dans plusieurs branches avant qu'elles ne puissent communiquer et ensuite s'enfuit. Le découvert sera détecté plus tard, conduisant éventuellement à des compensations sous la forme d'actions légales.

Remerciements

Je remercie Mike Dahlin, Hank Korth, Marc Shapiro, Justin Sheehy, Amin Vahdat, Ben Zhao, et les volontaires de l'IEEE Computer Society pour leurs retours sur ce travail.

A propos de l'auteur Eric Brewer est professeur d'informatique à l'Université de Californie, Berkeley, et vice président de l'infrastructure pour Google. Ses sujets de recherche incluent le cloud computing, les serveurs scalables, les réseaux de capteurs, et la technologie pour les pays en développement. Il a aussi participé à la création de USA.gov, le portail officiel du gouvernement fédéral. Brewer a un PhD en ingéniérie electrique et en informatique du MIT. Il est membre de la National Academy of Engineering. Contactez le à brewer@cs.berkeley.edu

Computer, la publication phare de l'IEEE Computer Society, publie des articles enscencés et revus par des pairs, écris par et pour des professionels représentant le spectre complet des technologies informatiques, du matériel au logiciel et des recherches actuelles aux nouvelles applications. Fournissant une substance plus technique que les magazines spécialisés et plus pratique que les journaux de recherche, Computer propose des informations utiles applicables aux environnements de travails.

Références

1. E. Brewer, "Lessons from Giant-Scale Services," IEEE Internet Computing, Jui/Aou 2001, pp. 46-55.
2. A. Fox et al., "Cluster-Based Scalable Network Services," Proc. 16th ACM Symp. Operating Systems Principles (SOSP 97), ACM, 1997, pp. 78-91.
3. A. Fox and E.A. Brewer, "Harvest, Yield and Scalable Tolerant Systems," Proc. 7th Workshop Hot Topics in Operating Systems (HotOS 99), IEEE CS, 1999, pp. 174-178.
4. E. Brewer, "Towards Robust Distributed Systems," Proc. 19th Ann. ACM Symp.Principles of Distributed Computing (PODC 00), ACM, 2000, pp. 7-10 ; resource en ligne.
5. B. Cooper et al., "PNUTS: Yahoo!’s Hosted Data Serving Platform," Proc. VLDB Endowment (VLDB 08), ACM, 2008, pp. 1277-1288.
6. J. Sobel, "Scaling Out,"_ Facebook Engineering Notes_, 20 Aou. 2008 ; ressources en ligne.
7. J. Kistler and M. Satyanarayanan, "Disconnected Operation in the Coda File System" ACM Trans. Computer Systems, Fev. 1992, pp. 3-25.
8. K. Birman, Q. Huang, and D. Freedman, "Overcoming the ‘D’ in CAP: Using Isis2 to Build Locally Responsive Cloud Services," Computer, Fev. 2011, pp. 50-58.
9. M. Burrows, "The Chubby Lock Service for Loosely-Coupled Distributed Systems," Proc. Symp. Operating Systems Design and Implementation (OSDI 06), Usenix, 2006, pp. 335-350.
10. J. Baker et al., "Megastore: Providing Scalable, Highly Available Storage for Interactive Services," Proc. 5th Biennial Conf. Innovative Data Systems Research (CIDR 11), ACM, 2011, pp. 223-234.
11. D. Abadi, "Problems with CAP, and Yahoo’s Little Known NoSQL System," DBMS Musings, blog, 23 Apr. 2010 ; ressource en ligne.
12. C. Hale, "You Can’t Sacrifice Partition Tolerance," 7 Oct. 2010 ; ressource en ligne.
13. W. K. Edwards et al., "Designing and Implementing Asynchronous Collaborative Applications with Bayou," Proc. 10th Ann. ACM Symp. User Interface Software and Technol ogy (UIST 97), ACM, 1999, pp. 119-128.
14. P. Mahajan, L. Alvisi, and M. Dahlin, Consistency, Availability, and Convergence, tech. report UTCS TR-11-22, Univ. of Texas at Austin, 2011.
15. D.B. Terry et al., "Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System," Proc. 15th ACM Symp. Operating Systems Principles (SOSP 95), ACM, 1995, pp. 172-182.
16. B. Du and E.A. Brewer, "DTWiki: A Disconnection and Intermittency Tolerant Wiki," Proc. 17th Int’l Conf. World Wide Web (WWW 08), ACM, 2008, pp. 945-952.
17. "What’s Different about the New Google Docs: Conflict Resolution" blog.
18. M. Shapiro et al., "Conflict-Free Replicated Data Types," Proc. 13th Int’l Conf. Stabilization, Safety, and Security of Distributed Systems (SSS 11), ACM, 2011, pp. 386-400.
19. M. Shapiro et al., "Convergent and Commutative Replicated Data Types," Bulletin of the EATCS, no. 104, Juin 2011, pp. 67-88.
20. G. DeCandia et al., "Dynamo: Amazon’s Highly Available Key-Value Store," Proc. 21st ACM SIGOPS Symp. Operating Systems Principles (SOSP 07), ACM, 2007, pp. 205-220.
21. H. Garcia-Molina and K. Salem, "SAGAS," Proc. ACM SIGMOD Int’l Conf. Management of Data (SIGMOD 87), ACM, 1987, pp. 249-259.
22. H. Korth, E. Levy, and A. Silberschatz, "A Formal Approach to Recovery by Compensating Transactions," Proc. VLDB Endowment (VLDB 90), ACM, 1990, pp. 95-106