Plus facile à lire avec un fond crème, une teinte, plus de contraste ou un texte plus grand ? Choisissez vos couleurs et votre texte, une fois pour toutes les pages.

Leçon gratuite

Registres et ensembles : quand l’ajout gagne

Après cette leçon: Je peux fusionner deux répliques d’un ensemble à retrait observé.

Leçon de 65 min2 commandesLab CRDT : synchro local-first, compteurs et texte en Python

Le lait qui revient

Ana et Ben partagent une liste de courses. Dans le bus, Ana retire le lait, parce qu’elle vient d’en acheter. Au même moment, Ben ajoute du lait, parce que le frigo a l’air vide.

Quand leurs téléphones se synchronisent, le lait doit-il être sur la liste ? Il n’y a pas une seule bonne réponse, mais chaque téléphone doit donner la même.

À la fin de cette leçon

Remarque

Je peux fusionner deux répliques d’un ensemble à retrait observé.

Mots-clés

MotCe que ça veut direExemple
Registreun CRDT qui contient une seule valeur
Ensemble croissantun ensemble où l’on ajoute sans jamais retirerG-Set
Étiquetteune marque unique donnée à un ajout
OR-setun ensemble à retrait observé : un retrait n’efface que les étiquettes qu’il a vues
L’ajout gagneun ajout concurrent l’emporte sur un retrait

Les cellules que les étudiants remplissent restent vides dans cet aperçu.

Un registre garde le plus grand tampon

La leçon 1 a présenté le registre où le dernier écrit gagne. Vu comme un CRDT, son état est une valeur et un tampon fait d’une heure et d’un nom de réplique. La fusion garde la paire au plus grand tampon.

Prendre le plus grand est une borne supérieure : les registres s’accordent toujours. Mais ils s’accordent en jetant une valeur, ce qui va pour une couleur et pas pour une liste de courses.

Trois façons de partager un ensemble

Ensemble croissant : la fusion est l’union. On ne peut jamais rien retirer. Ensemble à deux phases : un ensemble des ajouts et un ensemble des retraits, tous deux fusionnés par union. Un article retiré une fois ne revient jamais. OR-set : chaque ajout reçoit une nouvelle étiquette. Un retrait efface les étiquettes qu’il a vues. Un article reste présent tant qu’il garde une étiquette vivante.

À vous : un ensemble à deux phases

Code: python
# Un ensemble à deux phases : un ensemble des ajouts, un des retraits.
# Un article est présent s’il a été ajouté et jamais retiré.
def membres(etat):
    return sorted(etat["ajoutes"] - etat["retires"])

def fusion(a, b):
    return {"ajoutes": a["ajoutes"] | b["ajoutes"],
            "retires": a["retires"] | b["retires"]}

ana = {"ajoutes": {"lait", "oeufs"}, "retires": set()}
ben = {"ajoutes": {"lait", "oeufs"}, "retires": set()}

ana["retires"].add("lait")       # Ana retire le lait, hors ligne
ben["ajoutes"].add("lait")       # Ben rajoute le lait, hors ligne

les_deux = fusion(ana, ben)
print("après synchro :", membres(les_deux))
les_deux["ajoutes"].add("lait")  # on essaie de rajouter le lait
print("après un nouvel ajout :", membres(les_deux))
# Quelqu’un pourra-t-il un jour remettre du lait sur cette liste ?

Pourquoi le nouvel ajout survit

Le retrait d’Ana ne peut effacer que les étiquettes qu’Ana a vues. L’ajout de Ben a créé une nouvelle étiquette qu’Ana n’a jamais vue : elle n’est donc pas retirée.

Après la fusion, le lait garde une étiquette vivante et reste sur la liste. Cette règle s’appelle « l’ajout gagne ». Un retrait fait après avoir vu toutes les étiquettes retire bien l’article.

Garder le lait avec un OR-set

Commande
docker exec jupyter python3 steps/orset.py

Affichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.

Exemple travaillé : ce que le labo a affiché

MomentAnaBen
Départeggs, milk (étiquette ana:1)eggs, milk (étiquette ana:1)
Hors ligneretire milk : ana:1 retiréeajoute milk : étiquette ben:1
Après la synchroeggs, milkeggs, milk
Ben retire milk en voyant ben:1eggseggs

Les cellules que les étudiants remplissent restent vides dans cet aperçu.

Erreur fréquente

Attention

On croit souvent qu’un retrait efface l’élément, d’où qu’il vienne. Dans un OR-set, un retrait n’efface que les étiquettes que sa réplique a vues. Un ajout fait ailleurs, au même moment, garde son étiquette : l’élément reste.

Synchroniser trois répliques après beaucoup de changements

Commande
docker exec jupyter python3 steps/offline.py

Affichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.

À propos de ce labo et de sa source: Lab CRDT : synchro local-first, compteurs et texte en Python

Vous enseignez à une classe ? Proposez ce module à vos étudiants avec un guide de l'enseignant, des devoirs corrigés et un laboratoire pour chaque étudiant.