Le parcours : faire converger un tableau de contributions

En AP7, un serveur comptait toutes les contributions. Aujourd’hui, chaque poste doit pouvoir continuer à compter pendant une coupure des échanges : il garde sa propre copie de l’état, sa réplique, et la modifie sans attendre les autres. Comment réunir ensuite les comptes sans perdre ni compter deux fois un ajout ?

Le diagramme pas à pas permet de suivre les trois copies et les messages, puis de rejouer un doublon ou un ancien état.

Commencer par le souci de fusion

Téléchargez le squelette compteur-replique et ouvrez son dossier dans l’éditeur. Il fournit une application Mix, les API et des tests par paliers ; vous écrivez d’abord les fonctions du compteur, puis les réponses des répliques. Il n’est pas nécessaire d’avoir terminé compteur-local : le démarrage et la supervision sont fournis.

Si Alice et Bob partent d’un total commun de 5 et ajoutent chacun une contribution, ils obtiennent tous les deux 6. Comment fusionner ces deux copies, c-à-d. calculer un état qui contient ce que chacune sait ? Prendre le maximum donne 6, alors que le total attendu est 7 ; additionner les copies donne 12. Le nombre total ne contient pas assez d’information pour décider : il ne dit pas qui a déjà été compté.

Conserver une composante par poste

Nous utilisons une map : %{alice: 2, bob: 1} représente deux contributions enregistrées par Alice et une par Bob. Chaque réplique incrémente uniquement la composante qui porte son identifiant. Pour fusionner deux maps, on garde le maximum pour chaque identifiant ; une composante absente vaut zéro.

Le schéma reprend la seconde ligne du tableau. À gauche, la copie d’Alice connaît trois contributions d’Alice et une de Bob ; au milieu, celle de Bob en connaît deux d’Alice et deux de Bob. Les deux totaux valent 4, mais ce ne sont pas les mêmes contributions. La fusion compare ligne par ligne, max(3, 2) pour Alice et max(1, 2) pour Bob, puis additionne : 5. Pourquoi le maximum, et non la somme ? Parce qu’une composante ne diminue jamais : la plus grande valeur connue est aussi la plus récente, et la recevoir deux fois ne change rien.

Ce G-Counter (grow-only counter) est un compteur qui ne fait qu’augmenter. Il appartient aux CRDT, des structures répliquées dont les règles de fusion assurent la convergence : les répliques finissent par porter le même état dès qu’elles ont reçu les mêmes mises à jour. Le texte de Preguiça, Baquero et Shapiro situe cette propriété et les familles de CRDT.

Prédire puis éprouver la fusion

Les tests vous font vérifier trois propriétés : fusionner deux fois le même état ne change plus rien, inverser deux états ne change pas le résultat, et regrouper autrement trois fusions donne le même état. Ce sont respectivement l’idempotence, la commutativité et l’associativité. Chacune répond à une incertitude sur les messages : un doublon, deux livraisons dans l’ordre inverse, un état déjà fusionné chez un relais. max possède ces trois lois sur les entiers ; appliquées composante par composante, elles passent aux maps.

Nous plaçons ensuite cette brique pure dans trois GenServers, tous dans la même VM. Nous simulons une coupure en retenant les échanges de snapshots, c’est-à-dire les copies des maps à un instant donné : une map immuable, qui ne suit pas les modifications faites ensuite chez son auteur. Les processus restent actifs : aucune connexion réseau n’est ouverte ou fermée.

Faites avancer Alice et Bob séparément, conservez un ancien snapshot, puis réconciliez les trois postes. Réinjectez cet ancien état et un doublon. Le README donne une trace à reproduire, puis vous demande de construire la vôtre.

Dans ce schéma, les composantes sont dans l’ordre Alice, Bob, Carol. Au départ, Alice connaît [2, 0, 0], Bob [0, 1, 0] et Carol [0, 0, 0]. Alice envoie sa copie à Bob, qui connaît alors [2, 1, 0], puis Bob envoie un nouveau snapshot à Carol : elle reçoit les deux contributions d’Alice sans jamais lui avoir parlé. Enfin, Bob envoie sa copie à Alice, et les trois postes portent [2, 1, 0]. Que se serait-il passé si Bob avait transmis à Carol un snapshot pris avant de recevoir Alice ? Carol n’aurait connu que Bob : un snapshot est une copie figée, pas une fenêtre sur l’état vivant.

Ici, l’état local connaît alice: 3 et bob: 2. Il reçoit un doublon de ce même état, puis un ancien snapshot alice: 2, bob: 1. Le maximum par composante conserve 3 et 2 : le total reste 5, et aucun ajout n’est compté deux fois. Le total ne compte pas les messages reçus ; il additionne les composantes connues.

Les limites font partie du résultat

La convergence exige que les mises à jour finissent par atteindre les répliques encore actives. Elle ne signifie pas que tous les postes affichent le même total pendant une coupure. Les maps sont en mémoire : une mise à jour perdue avant d’être copiée n’est pas sauvée par le CRDT.

Chaque identifiant appartient à un seul écrivain. Réutiliser un identifiant avec un compteur remis à zéro peut faire ignorer les nouveaux ajouts : si Bob connaît déjà alice: 2, une nouvelle Alice qui repart de zéro et ajoute 1 envoie alice: 1, dominé par l’ancien 2. Le projet ne permet donc ni remise à zéro ni décrément ; la comparaison avec le compteur d’AP7 est volontaire.

Et un éditeur de texte concurrent ?

Nous terminerons par deux insertions faites sur le même texte. Une position numérique se décale quand l’autre personne écrit : les lois de notre compteur ne suffisent pas à résoudre ce souci. La transformation opérationnelle adapte les opérations au contexte ; les CRDT de séquence s’appuient sur une autre représentation, avec des identifiants et des règles d’ordre.

Notre objectif en AP8 est de comprendre ce nouveau souci et de le relier à la réplication. Vous pourrez le reprendre en AP9 dans un sujet au choix pour le projet noté : trois fonctions pour insérer, supprimer et fusionner un texte, puis deux répliques affichées dans une interface locale fournie. Le parcours de la séquence, les GenServers et tout le code web seront prêts : aucune connaissance de HTML, CSS ou JavaScript n’est demandée. Curseurs partagés et reprise après panne constitueraient d’autres projets. Le texte Local-first software donne des exemples d’applications et de compromis pour poursuivre.

Si une forme de GenServer ou de Map vous manque pendant le travail, le poly en donne le gabarit avec ses sorties : Map au chapitre 3, GenServer au chapitre 10.