Comprendre PACELC

Je me souviens très bien du moment où j’ai commencé à vouloir devenir architecte.

J’ai eu la chance d’avoir des bons mentors et l’une des premières choses qu’ils m’ont dites c’est :

• “Concentre-toi déjà sur les bases”
• “Si tu veux devenir bon en archi, il faut que tu apprennes à faire les bons compromis, commence par des choses comme PAC/PACELC”

Les théorèmes de CAP et PACELC sont une bonne porte d’entrée pour comprendre ces compromis.

Il en formalise un en particulier, sans doute le plus important dans les systèmes distribués.

Mais avant d’attaquer le théorème, il faut poser des bases solides sur trois concepts qu’on entend partout, souvent mal définis : Consistency, Availability, et Partition tolerance.

C’est quoi la consistency (cohérence) ?

Imaginez une base de données répliquée sur trois serveurs. Vous écrivez une donnée sur le serveur A. La consistency, c’est la garantie que si vous lisez cette donnée immédiatement après sur le serveur B ou C, vous obtenez bien la dernière valeur écrite.

Autrement dit : tous les nœuds voient la même donnée au même moment.

⚠️ Attention à ne pas confondre avec le “C” de ACID (transactions) qui parle d’autre chose : le respect des contraintes de la base. Ici, on parle de cohérence entre les nœuds d’un système distribué.

C’est quoi l’availability (disponibilité) ?

L’availability, c’est la garantie que chaque requête reçoit une réponse, sans erreur, dans un délai raisonnable. Pas forcément la réponse la plus à jour, mais une réponse. Un système hautement disponible, c’est un système qui répond toujours, même si certains nœuds sont en difficulté.

C’est quoi la partition tolerance ?

Un partitionnement réseau, c’est quand la communication entre certains nœuds est rompue, un câble coupé, une zone AWS qui tombe, un switch défaillant. La partition tolerance (tolérance au partitionnement), c’est la capacité du système à continuer de fonctionner malgré ces ruptures, sans s’effondrer.

Spoiler : dans un système distribué, les partitions réseau vont arriver. Ce n’est pas une option, ça va arriver.

Qu’est-ce que le théorème de CAP ?

Formulé par Eric Brewer lors de sa keynote « Towards Robust Distributed Systems » à PODC 2000, le théorème de CAP dit qu’un système distribué ne peut garantir que deux propriétés sur trois parmi Consistency, Availability et Partition tolerance. À l’origine, ce n’est qu’une conjecture ; Seth Gilbert et Nancy Lynch la démontrent en 2002 (« Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services », ACM SIGACT News). C’est cette preuve qui en fait un théorème, pas un simple slogan. Autrement dit : quand le réseau casse, votre système doit choisir ce qu’il sacrifie.

La formulation « choisis-en deux » est trompeuse.

Brewer l’a d’ailleurs reconnu douze ans plus tard dans « CAP Twelve Years Later: How the “Rules” Have Changed » (IEEE Computer, 2012) : le « 2 sur 3 » induit en erreur, parce que le compromis n’apparaît que quand une partition se produit vraiment.

En réalité, comme les partitions réseau sont inévitables, P n’est pas un choix. Le vrai compromis arrive quand une partition se produit : choisir entre la Consistency ou l’Availability.

• CP : en cas de partition, le système refuse les requêtes plutôt que de retourner une donnée potentiellement obsolète.
• AP : en cas de partition, le système répond toujours, quitte à servir des données pas à jour.

C’est déjà pas mal. Mais il y a une grosse limite.

Pourquoi CAP ne suffit-il pas ?

CAP ne dit rien sur ce qui se passe quand tout va bien. Or, 99 % du temps, il n’y a pas de partition. Et pourtant, même dans ces conditions normales, un système distribué doit faire un compromis : entre la latence et la consistency.

Pour qu’une écriture soit cohérente sur tous les nœuds, il faut attendre que tous (ou un quorum) confirment l’écriture. Ça prend du temps. Si on veut aller plus vite, on accepte qu’il y ait un léger décalage entre les nœuds.

C’est ce que PACELC ajoute.

C’est quoi PACELC ?

Daniel Abadi l’esquisse sur son blog en 2010, puis le formalise dans « Consistency Tradeoffs in Modern Distributed Database System Design: CAP is Only Part of the Story » (IEEE Computer, vol. 45, n°2, février 2012, le même numéro que le mea culpa de Brewer). PACELC étend le théorème de CAP : en cas de partition (P), le système arbitre entre availability (A) et consistency (C) ; sinon (E, else), même quand tout va bien, il arbitre entre latency (L) et consistency (C). C’est ce second compromis qui fait toute la valeur du théorème.

Dans la formulation d’origine du papier :

If Partition (P), how does the system trade off Availability (A) and Consistency (C)? Else (E), how does it trade off Latency (L) and Consistency (C)?

Ou en deux temps :

• PA/PC : en cas de partition, on privilégie l’Availability ou la Consistency ?
• EL/EC : en temps normal, on privilégie la Latency ou la Consistency ?

La première partie (PA/PC) est juste une reformulation de CAP. C’est la deuxième (EL/EC) qui est la vraie nouveauté.

Pourquoi ce compromis existe-t-il quand tout va bien ?

Parce que la réplication prend du temps. Pour garantir la cohérence, une écriture doit être confirmée par tous les nœuds (ou un quorum) avant de répondre au client : c’est sûr, mais lent. Pour répondre vite, il faut répliquer en arrière-plan et accepter un décalage temporaire entre les nœuds.

Imaginons une écriture sur un système répliqué à trois nœuds.

Pour garantir la cohérence, le nœud qui reçoit l’écriture doit attendre que les deux autres confirment avant de répondre au client. Le client attend donc la latence du réseau plus le temps de réplication. C’est sûr, mais c’est lent.

Si on veut aller plus vite, on répond au client dès que le nœud principal a écrit, et on réplique en arrière-plan. Le client est servi rapidement, mais pendant quelques millisecondes, les autres nœuds ont une donnée obsolète. Une lecture sur un de ces nœuds peut renvoyer l’ancienne valeur.

Ce n’est pas qu’un cas d’école. Le papier Dynamo (DeCandia et al., SOSP 2007) raconte qu’Amazon dimensionne ses services sur un SLA de latence au 99,9ᵉ percentile : répondre en moins de 300 ms à 99,9 % des requêtes. Et c’est cette contrainte qui a poussé Dynamo vers la cohérence éventuelle. Le choix EL est là, chiffré, dès le papier fondateur.

C’est ça le compromis EL vs EC :

• EL (Latency) : on répond vite, on accepte un décalage temporaire entre les nœuds
• EC (Consistency) : on attend la confirmation de tous les nœuds, on accepte une latence plus élevée

Ce choix est fait à chaque écriture, dans des conditions parfaitement normales. Pas besoin d’attendre une panne, pas besoin de partition. C’est le day-to-day d’un système distribué.

Quelles sont les quatre combinaisons de PACELC ?

En croisant les deux axes, on obtient quatre profils : PA/EL, PA/EC, PC/EL, PC/EC.

Abadi prononce l’acronyme « pass-elk ». Dans son papier, il range Dynamo, Cassandra et Riak en PA/EL, PNUTS de Yahoo en PC/EL, et les bases ACID synchrones en PC/EC. Le profil PC/EL, marqué « rare » dans le tableau ci-dessus, a donc bel et bien existé en production.

Aucun de ces choix n’est “meilleur”. Tout dépend de ce que vous construisez. Un panier d’achat tolère bien la cohérence éventuelle. Un système de paiement, beaucoup moins.

En résumé

Avec le temps, j’ai compris pourquoi on m’avait dit de commencer par là.

PACELC, c’est la base. C’est une façon de réfléchir à tes systèmes avant même d’écrire la première ligne de code.

• Quel niveau de cohérence mes lectures exigent-elles ?
• Mon SLA tolère-t-il une indisponibilité temporaire en cas de partition ?
• Quel budget de latence, j’ai sur mes écritures ?

Ces questions n’ont pas de réponse universelle. Mais si tu ne te les poses pas, le système va trancher à ta place, au pire moment, en production.

Sources

• Eric Brewer, Towards Robust Distributed Systems, keynote PODC, 2000
• Seth Gilbert & Nancy Lynch, Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services, ACM SIGACT News 33(2), 2002
• Daniel Abadi, Consistency Tradeoffs in Modern Distributed Database System Design: CAP is Only Part of the Story, IEEE Computer 45(2), 2012
• Eric Brewer, CAP Twelve Years Later: How the « Rules » Have Changed, IEEE Computer 45(2), 2012
• Giuseppe DeCandia et al., Dynamo: Amazon’s Highly Available Key-value Store, SOSP, 2007