Comment le verrouillage à deux phases empêche vos transactions bancaires concurrentes de corrompre vos données

Un client appuie sur « envoyer » pour un virement de 100. À la même milliseconde, à l'autre bout du monde, un second virement arrive sur le même compte. Les deux lisent le solde, les deux ajoutent leur montant, les deux réécrivent. Si la base de données laisse ces deux opérations s'entrelacer naïvement, un des deux paiements est silencieusement effacé. À l'échelle d'un processeur de paiement qui règle des millions de transactions par heure, ce n'est pas un bug, c'est un trou financier.

C'est la pointe acérée d'une idée profonde : le contrôle de concurrence. Cet article est né d'un entretien technique avec Djamo, une banque mobile, où exactement cette classe de question s'est posée : comment garder un registre correct quand de nombreux virements frappent le même compte à la fois ? Le cadrage ici est donc l'argent, là où la correction n'est pas optionnelle. L'édition collaborative de documents a une saveur voisine, mais elle est généralement coordonnée au niveau applicatif par des protocoles comme WOPI, pas par la base. On va donc droit là où la concurrence est réellement résolue : au cœur du moteur de base de données, et concrètement dans PostgreSQL.

Le cauchemar des accès simultanés

Le compte X démarre avec un solde de 1000. La transaction T1 dépose 100. Au même instant, T2 dépose 200. Chaque virement se fait en réalité en trois étapes : lire le solde, calculer solde + montant, réécrire. Entrelacez-les maladroitement et observez :

Le solde final est 1200. Il devrait être 1300. Le dépôt de T1 s'est évaporé parce que T2 a lu le solde avant que T1 n'écrive son résultat, donc T2 l'a écrasé. C'est la mise à jour perdue (lost update). Aucune des deux transactions n'est fausse en soi. C'est l'entrelacement qui est le bug, et aucun code applicatif soigné ne le corrige, car les deux requêtes peuvent tourner sur des serveurs différents qui s'ignorent. Seul le composant partagé en dessous, la base de données, peut arbitrer.

L'abstraction : le modèle de transaction

Pour raisonner là-dessus sans se noyer dans les pages disque et les B-trees, on utilise le modèle de transaction. Le système traite chaque donnée comme une entité opaque (une ligne, une page, une clé) et réduit toute transaction à deux actions primitives : lire (read) et écrire (write). On note r1[X] pour « T1 lit X » et w2[X] pour « T2 écrit X ».

Une transaction Ti n'est alors qu'une séquence ordonnée de telles opérations, terminée par un commit c_i ou un abandon a_i. Notre mise à jour perdue devient une chaîne compacte :

r1[X]  r2[X]  w1[X]  w2[X]

Voilà tout le problème, réduit à son squelette. Deux lectures de X précèdent les deux écritures, donc la seconde écriture écrase la première. Le contrôle de concurrence est la discipline qui décide quels entrelacements sont légaux.

Formellement, un ordonnancement (schedule) S sur un ensemble de transactions est un entrelacement de toutes leurs opérations qui préserve l'ordre interne de chaque transaction. Si T1 fait r1[X] avant w1[X], tout ordonnancement doit garder cet ordre. Ce qu'il peut choisir, c'est où insérer les opérations de T2 entre les deux.

Les maths : la conflit-sérialisabilité

Il nous faut une définition précise de « correct », et l'exécution sérielle en force brute donne le point de référence.

Un ordonnancement sériel exécute chaque transaction jusqu'au bout avant de démarrer la suivante : T1 en entier, puis T2, puis T3. Il est trivialement correct, car rien ne se chevauche, donc aucune anomalie n'est possible. Le prix est un parallélisme nul, qu'aucun système de paiement ne peut se permettre. On veut donc un ordonnancement qui s'exécute en parallèle tout en se comportant comme si il était sériel. Cette propriété est la sérialisabilité, et voici comment la rendre vérifiable.

Deux opérations sont en conflit quand elles appartiennent à des transactions différentes, touchent la même entité, et qu'au moins l'une est une écriture. Donc r/w, w/r et w/w sur la même entité sont en conflit, mais deux lectures ne le sont jamais. Formellement, pour un ordonnancement S :

conflit(op_i, op_j)  ⇔  entité(op_i) = entité(op_j)
                         ∧ Ti ≠ Tj
                         ∧ (op_i est une écriture ∨ op_j est une écriture)

Deux ordonnancements sont conflit-équivalents quand ils contiennent les mêmes opérations et ordonnent de la même façon chaque paire d'opérations en conflit. Un ordonnancement est conflit-sérialisable quand il est conflit-équivalent à un ordonnancement sériel. Les opérations sans conflit peuvent être librement réordonnées, donc seul compte l'ordre relatif des paires en conflit.

L'outil qui tranche cela est le graphe de précédence (aussi appelé graphe de sérialisation) SG(S) :

• un nœud par transaction commitée,
• une arête orientée Ti → Tj dès qu'une opération de Ti est en conflit avec, et précède, une opération de Tj dans S.

Voici maintenant le résultat fondateur de tout le domaine :

Théorème de sérialisabilité. Un ordonnancement S est conflit-sérialisable si et seulement si son graphe de précédence SG(S) est acyclique.

L'intuition est limpide. Une arête Ti → Tj signifie « Ti doit précéder Tj dans tout ordre sériel équivalent ». Si le graphe est acyclique, un tri topologique produit exactement cet ordre sériel. S'il y a un cycle Ti → Tj → ... → Ti, alors Ti doit précéder strictement lui-même, ce qui est impossible, donc aucun ordre sériel équivalent n'existe. Notre mise à jour perdue a les arêtes T1 → T2 (via r1[X] avant w2[X]) et T2 → T1 (via r2[X] avant w1[X]), formant un cycle de longueur 2. Cycle signifie non sérialisable, ce qui est l'empreinte formelle du bug.

Vérifier l'acyclicité d'un graphe est peu coûteux. Le hic, c'est que construire SG(S) exige de connaître l'ordonnancement entier, or une base chargée exécute des milliers de transactions par seconde sans savoir ce qui arrive ensuite. Il nous faut une règle qui garantisse l'acyclicité pendant que l'ordonnancement se produit encore, sans jamais construire le graphe. Cette règle, c'est le verrouillage.

Les verrous et leurs deux modes

Un verrou est une revendication qu'une transaction pose sur une entité avant d'y toucher. Il y a crucialement deux modes, et la distinction est ce qui permet le moindre parallélisme.

• Un verrou partagé (S), ou verrou de lecture : « je lis ceci, d'autres peuvent le lire aussi, mais personne ne peut l'écrire ». Plusieurs transactions peuvent le détenir sur la même entité à la fois.
• Un verrou exclusif (X), ou verrou d'écriture : « j'écris ceci, personne d'autre ne peut le lire ni l'écrire ». Un seul détenteur, et aucun verrou partagé ne peut coexister.

Cela se résume à une matrice de compatibilité. Une demande de verrou n'est accordée que si elle est compatible avec tous les verrous déjà détenus sur cette entité :

Deux lecteurs coexistent, un rédacteur exclut tout le monde. C'est pourquoi les charges à dominante lecture passent à l'échelle sous verrouillage, et pas la contention en écriture. Une demande incompatible se bloque jusqu'à la libération du verrou conflictuel.

La règle d'or : le verrouillage à deux phases

Les verrous seuls ne garantissent pas la sérialisabilité. On peut les acquérir et les relâcher dans un ordre qui produit encore la mise à jour perdue. La discipline qui corrige cela est le verrouillage à deux phases (2PL), une règle sur le moment où l'on peut acquérir et relâcher, qui scinde chaque transaction en deux phases :

• Phase de croissance (acquisition). La transaction peut acquérir des verrous dans n'importe quel ordre, mais n'en relâche aucun.
• Phase de décroissance (libération). À l'instant où elle relâche son premier verrou, elle bascule en décroissance. Dès lors, elle ne peut plus que relâcher, jamais acquérir.

Traçez le nombre de verrous détenus au fil du temps. Il monte de façon monotone jusqu'à un sommet, puis redescend de façon monotone. Ce sommet est le point de verrou LP(Ti), l'instant où la transaction possède tout ce dont elle aura besoin.

verrous
détenus |          /\
        |         /  \
        |        /    \
        |       /      \___
        |______/           \____
        +--------------------------> temps
         croissance | point | décroissance
                     | verrou|

Pourquoi accepter une règle qui tient clairement les verrous plus longtemps que nécessaire ? À cause du gain :

Théorème du 2PL. Si toute transaction respecte la règle des deux phases, tout ordonnancement produit par le système est conflit-sérialisable.

Voici l'esquisse de preuve, qui vaut le détour car elle montre pourquoi la règle marche. Supposons que le graphe de précédence ait une arête Ti → Tj. Cette arête existe parce qu'une opération de Ti est entrée en conflit avec une opération ultérieure de Tj sur une entité partagée. Pour que les deux touchent cette entité en conflit, Ti doit avoir relâché son verrou et Tj en avoir acquis un après. Relâcher signifie que Ti était déjà en décroissance, donc LP(Ti) a précédé l'acquisition de Tj. Acquérir signifie que Tj était encore en croissance, donc cette acquisition a précédé LP(Tj). En chaînant :

Ti → Tj  dans SG(S)   ⇒   LP(Ti) < LP(Tj)

Chaque arête du graphe de précédence fait strictement croître le point de verrou. Un cycle Ti → ... → Ti forcerait donc LP(Ti) < LP(Ti), une contradiction. Le graphe est donc sans cycle, et par le théorème de sérialisabilité, l'ordonnancement est conflit-sérialisable. Les points de verrou eux-mêmes donnent l'ordre sériel équivalent : trions les transactions par LP(Ti).

Voilà toute la magie. On a remplacé une analyse de graphe impossible à l'exécution par une règle purement locale, « croître puis décroître », et obtenu la sérialisabilité globale comme théorème.

Pessimiste contre optimiste

Le 2PL est le porte-drapeau de la stratégie pessimiste : supposer que le conflit est probable, donc verrouiller la donnée avant d'y toucher et faire attendre tous les autres. C'est le bon défaut quand la contention est forte, exactement le cas d'un compte chaud que de nombreux virements frappent en même temps.

La philosophie opposée est optimiste : supposer que le conflit est rare, laisser les transactions tourner sans blocage, et ne vérifier les conflits qu'au moment du commit, en abandonnant le perdant si deux se sont réellement heurtées. Elle gagne quand la contention est faible, car elle ne paie aucun coût de verrouillage sur le chemin courant. Les vraies bases offrent les deux, et PostgreSQL en est l'exemple le plus clair, comme on va le voir. Il faut d'abord corriger un défaut du 2PL simple.

Pourquoi le 2PL simple ne suffit pas : le 2PL strict

Le 2PL de base garantit la sérialisabilité mais autorise encore les lectures sales (dirty reads) et les abandons en cascade. Supposons que T1 entre en décroissance, relâche le verrou sur X, puis abandonne plus tard seulement. Dans l'intervalle, T2 a lu la valeur non commitée de X. Quand T1 est annulée, T2 est bâtie sur une donnée qui n'a jamais officiellement existé, T2 doit donc abandonner aussi, et tout ce qui a lu depuis T2 abandonne à son tour. Un seul échec se propage en cascade.

Pour un registre bancaire c'est intolérable, donc les moteurs réels retardent la libération des verrous :

• 2PL strict (S2PL). Garder tout verrou exclusif jusqu'au commit ou à l'abandon. Les verrous partagés peuvent encore tomber en décroissance. Cela suffit à tuer les abandons en cascade : personne ne peut lire vos écritures tant que vous ne les avez pas commitées.
• 2PL rigoureux. Garder tous les verrous, partagés et exclusifs, jusqu'au commit. Un peu moins de concurrence, mais plus simple à raisonner.

Quand une base dit « verrouillage à deux phases », elle désigne presque toujours le 2PL strict ou rigoureux. Le commit devient le seul instant où toutes les écritures deviennent visibles et où tous les verrous tombent, ce qui est exactement la visibilité « tout ou rien » attendue d'une transaction.

Le prix : les interblocages

Garder les verrous jusqu'au commit introduit l'interblocage (deadlock). Deux virements touchant deux comptes dans l'ordre inverse suffisent :

T1 détient A et veut B, T2 détient B et veut A. Aucune ne cède. Il y a deux réponses.

Détection. Le moteur tient un graphe d'attente (wait-for graph) : une arête Ti → Tj signifie que Ti attend un verrou détenu par Tj. Un cycle est un interblocage. Le moteur choisit une victime (typiquement la moins coûteuse à défaire), l'abandonne, relâche ses verrous, et laisse la survivante finir. La victime réessaie plus tard. PostgreSQL fait exactement cela et remonte une erreur deadlock detected, donc votre code applicatif doit être prêt à la réessayer.

Prévention. Les schémas à timestamps empêchent les cycles de se former. Donnez à chaque transaction un timestamp de naissance TS(Ti), où plus ancien signifie plus petit. Quand Ti demande un verrou détenu par Tj :

wait-die :    si TS(Ti) < TS(Tj)  alors Ti attend      (l'ancien attend)
              sinon                    Ti abandonne     (le jeune meurt)

wound-wait :  si TS(Ti) < TS(Tj)  alors Tj abandonne    (l'ancien blesse le jeune)
              sinon                    Ti attend         (le jeune attend)

Les deux sont sans interblocage car chaque arête d'attente pointe de façon cohérente de l'ancien vers le jeune (wait-die) ou du jeune vers l'ancien (wound-wait), ce qui ne peut jamais former de cycle. Comme une transaction relancée garde son TS d'origine, elle vieillit avec le temps et finit par gagner, donc aucune transaction ne meurt de faim. Un cousin plus grossier est le simple délai d'expiration (lock timeout) : abandonner après N secondes d'attente. Imprécis, mais il ne demande ni graphe ni timestamps.

PostgreSQL dans le monde réel

PostgreSQL vaut la peine d'être ancré ici car il offre le chemin pessimiste et le chemin optimiste dans un seul moteur.

Le chemin pessimiste. Vous prenez les verrous explicitement. SELECT ... FOR UPDATE acquiert un verrou exclusif de ligne, ce qui est précisément l'outil qui corrige notre bug de virement du début :

BEGIN;
SELECT balance FROM accounts WHERE id = 'X' FOR UPDATE;  -- verrou exclusif de ligne
UPDATE accounts SET balance = balance + 100 WHERE id = 'X';
COMMIT;  -- 2PL strict : verrou relâché seulement ici

Avec FOR UPDATE, T2 ne peut même pas lire X tant que T1 n'a pas commité, donc la mise à jour perdue est impossible. C'est du 2PL strict manuel, appliqué là où vous savez la contention forte.

Le chemin optimiste. Pour les lectures courantes, PostgreSQL ne prend aucun verrou de lecture. Il utilise le contrôle de concurrence multiversion (MVCC) : un rédacteur crée une nouvelle version d'une ligne plutôt que d'écraser l'ancienne, donc les lecteurs voient un instantané cohérent et ne se bloquent jamais sur les rédacteurs, et les rédacteurs ne se bloquent jamais sur les lecteurs. Les écritures prennent quand même des verrous exclusifs de ligne, donc les conflits écriture-écriture restent sérialisés, mais le chemin de lecture courant est sans verrou.

Au niveau d'isolation SERIALIZABLE, PostgreSQL ajoute par-dessus l'isolation d'instantané sérialisable (SSI). Plutôt que tenir de longs verrous de lecture comme le 2PL, SSI laisse les transactions tourner de façon optimiste, guette les motifs lecture-écriture dangereux qui créeraient un cycle dans le graphe de précédence, et abandonne une transaction avec une erreur de sérialisation s'il en détecte un. C'est la même garantie d'acyclicité de notre théorème, imposée de façon optimiste au lieu de pessimiste. Votre code réessaie la transaction abandonnée, exactement comme il réessaie une victime d'interblocage.

Les quatre niveaux d'isolation SQL (read uncommitted, read committed, repeatable read, serializable) sont en réalité une molette réglant quelle part de cette mécanique est engagée. SERIALIZABLE est le seul qui promet un vrai comportement conflit-sérialisable, et vous pouvez l'atteindre dans PostgreSQL soit de façon pessimiste avec des verrous explicites, soit de façon optimiste avec SSI. Les moteurs à base de verrous comme MySQL InnoDB et SQL Server penchent plus fort du côté 2PL de ce spectre.

Conclusion

Le contrôle de concurrence est invisible pour l'utilisateur final et absolument central pour tout système où la donnée est de l'argent. Le verrouillage à deux phases est l'idée qui l'a rendu praticable : il remplace un contrôle impossible à l'exécution, « le graphe de précédence est-il acyclique », par une simple règle locale, « croître puis décroître », et le théorème prouve que les deux sont équivalents. Le 2PL strict le durcit contre les abandons en cascade, la détection et la prévention par timestamps l'empêchent de se figer, et MVCC avec SSI offrent l'alternative optimiste pour le cas courant à dominante lecture.

Grâce à cette mécanique, le virement de 100 qui s'évaporait dans notre premier exemple ne s'évapore jamais vraiment. Une règle que vous ne voyez jamais, imposée pessimistiquement par un verrou ou optimistiquement par une vérification de version, refuse de laisser faire.