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
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Registre | un CRDT qui contient une seule valeur | |
| Ensemble croissant | un ensemble où l’on ajoute sans jamais retirer | G-Set |
| Étiquette | une marque unique donnée à un ajout | |
| OR-set | un ensemble à retrait observé : un retrait n’efface que les étiquettes qu’il a vues | |
| L’ajout gagne | un 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
# 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
docker exec jupyter python3 steps/orset.pyAffiché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é
| Moment | Ana | Ben |
|---|---|---|
| Départ | eggs, milk (étiquette ana:1) | eggs, milk (étiquette ana:1) |
| Hors ligne | retire milk : ana:1 retirée | ajoute milk : étiquette ben:1 |
| Après la synchro | eggs, milk | eggs, milk |
| Ben retire milk en voyant ben:1 | eggs | eggs |
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
docker exec jupyter python3 steps/offline.pyAffichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.