Transactions distribuées : 2PC, 3PC, SAGA et verrous

Chez le notaire, tout est signé le même jour

Une vente immobilière réunit le vendeur, l'acquéreur et la banque dans la même pièce, à la même heure. Personne ne signe seul dans son coin. À la fin de la séance, soit le bien a changé de mains et les fonds ont bougé, soit rien ne s'est passé. Il n'existe pas d'état intermédiaire officiel.

À trois rues de là, la même ville fonctionne autrement. Pour ouvrir un commerce, tu passes au guichet des enseignes, puis à celui de l'occupation du trottoir, puis à la caisse des cotisations. Chaque guichet tamponne immédiatement et te laisse repartir. Si le dernier refuse, tu reviens sur tes pas et tu fais annuler les tampons précédents, un par un.

Ces deux façons de faire tenir un dossier sont exactement les deux familles de réponses aux transactions distribuées. Le notaire, c'est la validation à deux phases. La chaîne de guichets, c'est la SAGA.

Tant que tout tient dans une seule base de données, la question ne se pose pas : le moteur fournit l'atomicité et l'isolation. Dès qu'une commande touche trois services avec trois bases, il n'y a plus ni gestionnaire de verrous commun, ni journal commun, ni point de validation commun.

Le billet suit cet ordre : d'abord ce qui se passe sous le capot d'une transaction, le verrouillage et les familles de contrôle de concurrence. Ensuite les protocoles coordonnés, 2PC puis 3PC, qui préservent l'atomicité au prix de la disponibilité. Enfin la SAGA, qui abandonne l'atomicité et la remplace par la compensation.

Une transaction distribuée tient sur un accord entre plusieurs machines qui peuvent tomber, ou se couper l'une de l'autre, entre deux messages. Le changement d'échelle est de nature, pas de taille.

ACID sur une base, et pourquoi ça ne se transpose pas

Sur un moteur unique, les quatre lettres tiennent parce qu'un seul processus contrôle tout : l'atomicité vient du journal d'écritures anticipées, la cohérence des contraintes déclarées, l'isolation du gestionnaire de verrous, la durabilité de l'écriture sur disque avant l'accusé de réception. Le détail de ces garanties et leur pendant BASE sont traités dans Le théorème CAP, ACID et BASE.

Trois de ces quatre propriétés reposent sur un composant partagé. Retire le composant partagé, il ne reste que la durabilité, locale à chaque base.

Le service Stock ne sait pas ce que le service Paiement a écrit. Le service Paiement ne peut pas poser un verrou sur une ligne de la base commandes. Aucun des deux ne peut annuler ce que l'autre a validé, parce qu'une transaction locale validée est validée pour de bon.

S'ajoute le pire des cas des systèmes répartis : la panne partielle. La première écriture a réussi, la deuxième est partie sur le réseau et personne ne sait si elle est arrivée. Un délai d'attente expiré ne dit pas si l'autre côté a travaillé ou non.

Le problème n'est pas d'écrire dans trois bases. C'est de savoir, après une coupure, laquelle des trois a réellement enregistré quoi.

Le verrouillage à deux phases

Dans un immeuble, la clé du local à vélos est prêtée à un seul occupant à la fois. Tant qu'elle n'est pas rendue, les autres attendent. Un occupant qui a besoin du local à vélos et de la buanderie prend d'abord les deux clés, fait ce qu'il a à faire, puis les rend ensemble.

C'est le verrouillage à deux phases, ou 2PL. Une transaction passe par une phase d'expansion où elle ne fait qu'acquérir des verrous, puis par une phase de contraction où elle ne fait que les relâcher. La règle tient en une ligne : après la première libération, plus aucune acquisition n'est permise.

Cette discipline suffit à garantir la sérialisabilité, c'est-à-dire un résultat identique à celui d'une exécution des transactions les unes après les autres. Le 2PL strict, qui conserve les verrous exclusifs jusqu'à la validation, y ajoute la protection contre les annulations en cascade : personne ne lit une donnée qu'une transaction pourrait encore annuler.

Les verrous se déclinent en partagés pour la lecture, compatibles entre eux, et exclusifs pour l'écriture, incompatibles avec tout le reste. Une demande explicite ressemble à ceci :

BEGIN;
SELECT quantite FROM stock WHERE article_id = 4711 FOR UPDATE;
UPDATE stock SET quantite = quantite - 1 WHERE article_id = 4711;
COMMIT;

Le prix se paie en attente. Deux transactions qui prennent les mêmes verrous dans l'ordre inverse s'attendent mutuellement pour toujours : c'est l'interblocage. Les moteurs le traitent de deux façons, par graphe d'attente dont on cherche les cycles, ou par simple délai d'attente. InnoDB fait les deux : il détecte les cycles et annule la transaction la moins coûteuse, et coupe de toute façon au bout de innodb_lock_wait_timeout, réglé à 50 secondes par défaut.

Un verrou ne ralentit pas la transaction qui le tient. Il ralentit toutes celles qui voulaient la même ligne, et c'est invisible dans les métriques de la première.

Optimiste, pessimiste, multiversion

Le 2PL est pessimiste : il suppose le conflit et l'empêche avant qu'il arrive. Le contrôle optimiste, formalisé par Kung et Robinson en 1981, fait l'hypothèse inverse. La transaction lit et travaille sans rien bloquer, puis vérifie au moment de valider que personne n'a modifié ce qu'elle a lu. Si quelqu'un l'a fait, elle est rejetée et rejouée.

En pratique, cela prend la forme d'une colonne de version et d'une écriture conditionnelle :

UPDATE stock
SET quantite = 41, version = version + 1
WHERE article_id = 4711 AND version = 17;
-- 0 ligne affectée = quelqu'un est passé avant, il faut relire et recommencer

Le contrôle de concurrence multiversion est la troisième voie, celle de PostgreSQL et d'InnoDB. Chaque écriture crée une nouvelle version de la ligne, chaque lecture voit un instantané cohérent pris au début de la transaction. Les lecteurs ne bloquent plus les écrivains, ni l'inverse.

Attention au piège classique : l'isolation par instantané n'est pas la sérialisabilité. Deux transactions qui lisent le même état et modifient chacune une ligne différente peuvent violer ensemble une contrainte qu'aucune ne viole seule. PostgreSQL traite ce cas dans son niveau SERIALIZABLE, au prix d'annulations à la validation.

Le bon mécanisme se choisit sur le taux de conflit réel, mesuré, pas sur la réputation d'un moteur.

Le 2PC, quand tout le monde signe le même jour

La validation à deux phases reproduit la séance chez le notaire. Un coordinateur mène la séance, les participants sont les bases concernées.

Phase de vote : le coordinateur demande à chacun de se préparer. Chaque participant exécute son travail, écrit durablement un enregistrement de préparation, garde ses verrous, puis répond OUI ou NON. Un participant qui a répondu OUI s'engage : il n'a plus le droit d'annuler tout seul.

Phase de validation : si tous ont dit OUI, le coordinateur écrit la décision dans son propre journal, puis l'annonce. Chaque participant applique et relâche ses verrous. Un seul NON suffit à faire annuler tout le monde.

Ce protocole existe pour de vrai. La spécification X/Open XA le normalise, JTA l'expose côté Java, et PostgreSQL fournit ses deux moitiés avec PREPARE TRANSACTION puis COMMIT PREPARED. La documentation prévient d'ailleurs : le paramètre max_prepared_transactions vaut 0 par défaut, donc la fonctionnalité est désactivée, et une transaction laissée préparée conserve ses verrous et gêne le nettoyage.

Le défaut est structurel. Un participant qui a voté OUI et n'a pas reçu la décision est en doute. Il ne peut ni valider ni annuler, et il tient ses verrous pendant tout ce temps. Si le coordinateur tombe entre les deux phases, tous les participants restent dans cet état jusqu'à son retour.

Ce coût se chiffre. D'abord la disponibilité, qui suit la même arithmétique que les composants en série vue dans Haute disponibilité, puisque la transaction échoue dès qu'un participant manque à l'appel.

Un service disponible à 99,9 %          -> 0,999
Quatre participants, tous nécessaires   -> 0,999 x 0,999 x 0,999 x 0,999 = 0,996006
Indisponibilité de la transaction       -> 1 - 0,996006 = 0,003994, soit 0,4 %
Sur une année de 8 760 heures           -> 0,003994 x 8 760 = 35 heures
Le même calcul pour un service seul     -> 0,001 x 8 760 = 8,8 heures

Ensuite le débit. Sur une ligne chaude, le stock d'un article en promotion par exemple, le nombre d'écritures par seconde vaut l'inverse de la durée pendant laquelle le verrou est tenu. Hypothèses posées : 5 ms de travail local avec écriture du journal, 2 ms d'aller-retour réseau dans un centre de données, 80 ms entre deux régions éloignées, et deux allers-retours pour le protocole.

Débit maximal sur la ligne = 1 / durée de détention du verrou
Transaction locale seule   :  5 ms                 -> 1 / 0,005 = 200 écritures par seconde
2PC dans un centre         :  5 + 2 x 2   =   9 ms -> 1 / 0,009 = 111 écritures par seconde
2PC entre deux régions     :  5 + 2 x 80  = 165 ms -> 1 / 0,165 =   6 écritures par seconde

Le 2PC ne se paie pas en quelques millisecondes de latence. Sur une ligne disputée, il divise le débit d'écriture par plus de trente dès que le protocole traverse un océan.

Le 3PC, la phase de plus qu'on ne voit jamais

La validation à trois phases, proposée par Dale Skeen en 1981, intercale une étape entre le vote et la validation. Après l'unanimité, le coordinateur diffuse un message de pré-validation, attend les accusés de réception, et seulement ensuite ordonne la validation.

L'intérêt est précis. Un participant qui a reçu la pré-validation sait que tout le monde a voté OUI. Si le coordinateur disparaît à ce moment, un participant peut prendre le relais et trancher, puisque la décision est déterminée. Le protocole devient non bloquant face aux pannes de processus.

Deux raisons expliquent son absence quasi totale en production. La première tient à ses hypothèses : le 3PC suppose un réseau aux délais bornés, sans partition. Face à une coupure réseau, deux moitiés du groupe peuvent aboutir à des décisions différentes, ce qui est pire que d'attendre. La seconde est le troisième aller-retour, ajouté à un protocole déjà lent.

L'industrie a pris une autre route : garder deux phases, et rendre le coordinateur lui-même tolérant aux pannes en répliquant son journal par un protocole de consensus comme Paxos ou Raft. C'est exactement ce que décrit le scénario B plus bas.

Le 3PC répond à la mauvaise question. Ce qui coince dans le 2PC tient à un seul processus qui détient la décision, pas au nombre de phases.

La SAGA, la chaîne de guichets et ses annulations

Retour au commerce à ouvrir. Chaque guichet tamponne pour de bon, sans attendre les autres, et le dossier avance par étapes visibles. Si la caisse des cotisations refuse à la fin, on ne fait pas disparaître les tampons précédents : on émet des annulations qui les neutralisent.

Une SAGA, telle que Hector Garcia-Molina et Kenneth Salem la définissent dans leur papier « Sagas » (SIGMOD 1987), est une suite de transactions locales T1 à Tn, chacune associée à une transaction de compensation C1 à Cn. La garantie n'est plus l'atomicité : soit T1 à Tn s'exécutent toutes, soit un début de séquence T1 à Tj s'exécute puis est compensé en sens inverse, de Cj à C1.

Le virement de cent euros illustre la nuance. Débiter le compte A réussit, créditer le compte B échoue. La compensation recrédite cent euros sur A. Le solde final est correct, mais le relevé de compte porte deux lignes au lieu de zéro, et pendant quelques centaines de millisecondes l'argent n'existait nulle part.

Deux mises en œuvre coexistent. En chorégraphie, chaque service publie un événement et les autres réagissent, sans chef. En orchestration, un composant dédié appelle les étapes dans l'ordre et déclenche les compensations, comme dans le schéma ci-dessus.

Dans les deux cas, chaque étape publie et consomme des messages, ce qui suppose une file fiable et le motif de la boîte d'envoi transactionnelle pour ne jamais valider en base sans publier : le sujet est traité dans Files de messages et Kafka.

Une compensation avance dans le sens inverse plutôt que de revenir en arrière : elle ajoute une écriture qui neutralise la précédente, et les deux restent au registre.

Ce que la SAGA fait perdre

Le I d'ACID disparaît. Entre la première étape et la dernière, les états intermédiaires sont visibles par tout le monde : une commande existe alors que son paiement n'est pas acquis. La parade usuelle est le verrou sémantique, ce statut EN_ATTENTE que les autres lectures doivent savoir interpréter au lieu de le confondre avec un état définitif.

Ensuite, la compensation peut échouer à son tour. Elle doit donc être rejouable indéfiniment, donc idempotente, et surveillée par une file d'attente d'échecs qu'un humain finit par regarder. C'est le prolongement direct de Limitation de débit et idempotence : chaque étape et chaque compensation doit supporter d'être reçue deux fois.

Certaines actions n'ont pas de compensation. Un courriel parti est parti, et un virement interbancaire exécuté ne se rattrape pas. D'où le classement des étapes que Chris Richardson pose dans Microservices Patterns pour le motif SAGA : les étapes compensables d'abord, l'étape pivot au milieu, celle qui décide du sort de l'ensemble, et les étapes rejouables ensuite, celles qui finissent forcément par réussir.

Enfin, une SAGA est une machine à états répartie. Sans identifiant de corrélation propagé de bout en bout et sans trace consultable, personne ne sait dire où un dossier s'est arrêté ni dans quel sens il repart.

Une SAGA sans supervision se comporte très bien en démonstration et devient une enquête policière au premier incident de production.

Choisir, et surtout éviter de choisir

La meilleure transaction distribuée reste celle qu'on n'a pas créée. Avant les protocoles, il y a une question de découpage : les deux entités qui doivent changer ensemble ont-elles une raison d'être dans deux services différents ? Regrouper deux agrégats derrière une même base supprime le problème d'un coup, ce que rappelle Microservices, Event Sourcing et CQRS quand il traite des frontières de services. Le même raisonnement vaut pour le choix d'une clé de partition, traité dans Sharding et hachage cohérent.

Quand le regroupement est impossible, le tableau suivant résume l'arbitrage.

Une règle simple pour trancher : si un état intermédiaire visible pendant deux secondes constitue une faute vis-à-vis du métier ou du régulateur, il faut la coordination. Sinon, la SAGA coûte moins cher à exploiter.

Le choix ne se fait pas par système entier, mais par cas d'usage. Le même produit peut compenser une réservation et coordonner un mouvement comptable.

Scénario B : Spanner, le 2PC posé sur Paxos

Le papier « Spanner: Google's Globally-Distributed Database », présenté par Corbett et ses collègues à OSDI 2012, décrit une base répartie à l'échelle planétaire qui assume des transactions en lecture-écriture sur plusieurs partitions. Le protocole retenu n'a rien d'exotique : c'est bien un verrouillage à deux phases pour l'isolation et une validation à deux phases pour l'atomicité.

La différence tient à l'endroit où vit chaque rôle. Les données sont réparties en groupes, et chaque groupe est répliqué par Paxos. Le meneur de chaque groupe tient la table de verrous et le gestionnaire de transactions. Pour une transaction qui traverse plusieurs groupes, l'un des meneurs devient coordinateur, et son état de coordination est lui aussi répliqué par le consensus de son groupe.

Le coordinateur unique qui bloque tout le monde en tombant disparaît de l'équation : sa machine peut mourir, un autre membre du groupe reprend la décision déjà enregistrée. Le papier précise également que les lectures des transactions en lecture-écriture recourent à la technique dite wound-wait pour éviter les interblocages.

Le second pilier est TrueTime, une interface qui ne rend pas une date mais un intervalle assorti d'une incertitude bornée, alimentée par des récepteurs GPS et des horloges atomiques installés dans les centres de données. Le papier rapporte une incertitude de l'ordre de quelques millisecondes, variant en dents de scie entre les synchronisations. Avant de valider, le coordinateur attend que cette incertitude soit écoulée, ce que le papier nomme l'attente de validation. Google documente ce mécanisme et la garantie de cohérence externe qui en découle dans la documentation TrueTime de Cloud Spanner.

Le papier décrit enfin la migration vers cette base du back-end publicitaire F1, jusque-là posé sur un MySQL partitionné à la main.

Ce que Spanner apporte ici tient en deux points. Le 2PC n'est pas mort : il redevient praticable dès que le coordinateur cesse d'être un point unique. Mais le prix reste visible, puisque chaque écriture paie l'attente de validation en plus des allers-retours du protocole, et que l'infrastructure d'horloge qui rend l'ensemble tenable n'est pas à la portée du commun des exploitants.

Spanner affiche le tarif de la coordination à l'échelle planétaire : des groupes Paxos sous chaque partition, et une horloge juste à quelques millisecondes près.

Points clés

• Sur une base unique, l'atomicité et l'isolation viennent d'un composant partagé. Réparties sur plusieurs bases, elles doivent être reconstruites par un protocole, et ce protocole se paie.
• Le verrouillage à deux phases garantit la sérialisabilité au prix de l'attente. Le débit d'écriture sur une ligne chaude vaut l'inverse de la durée de détention du verrou : 200 par seconde en local, 6 par seconde quand le protocole traverse un océan.
• Le 2PC préserve l'atomicité mais laisse les participants bloqués, verrous tenus, si le coordinateur disparaît entre le vote et la décision. Quatre participants à 99,9 % donnent une transaction disponible à 99,6 %, soit 35 heures par an.
• Le 3PC lève ce blocage sur le papier, échoue face aux partitions réseau et ajoute un aller-retour. L'industrie a préféré répliquer le coordinateur par consensus.
• La SAGA échange l'atomicité contre la compensation. Elle exige des étapes idempotentes, un ordre pensé autour de l'étape pivot, et une supervision sans laquelle plus personne ne sait où un dossier s'est arrêté.

Dans la série

Palier 3 : Tenir les registres. Domaine : Données.

• Précédent : L'indexation : ce qui se passe vraiment sous une requête
• Suivant : Concevoir un raccourcisseur d'URL
• Vue d'ensemble : System design : par où commencer

Pour aller plus loin

• Limitation de débit et idempotence : encaisser les rejeux, parce qu'une étape de SAGA rejouée est la règle, pas l'exception.
• Le théorème CAP, ACID et BASE : ce qu'on accepte de perdre, pour la contrainte théorique dont découle tout cet arbitrage.
• Microservices, Event Sourcing et CQRS, pour le découpage en services qui fabrique le problème en amont.
• Le motif SAGA sur microservices.io, pour le catalogue des variantes et des contre-mesures d'isolation.
• PREPARE TRANSACTION dans la documentation PostgreSQL, pour voir à quoi ressemble une validation à deux phases côté moteur, avertissements compris.
• Le papier « Sagas » de Hector Garcia-Molina et Kenneth Salem (SIGMOD 1987) et le papier « Spanner: Google's Globally-Distributed Database » (OSDI 2012) pour les deux sources d'origine citées ici.