Compter les « j’aime » sur trois téléphones
Une publication reçoit des « j’aime » depuis trois téléphones, et chacun reste hors ligne un moment. À la synchro, le total doit compter chaque « j’aime » une fois. Il ne doit en manquer aucun, ni en compter deux fois.
Un simple nombre partagé n’y arrive pas seul. Un compteur CRDT, si.
À la fin de cette leçon
Remarque
Je peux fusionner deux répliques d’un compteur pour que chaque réplique ait le même total.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| CRDT | un type de données dont les répliques fusionnent toujours vers le même état | |
| À base d’états | les répliques envoient leur état entier et le fusionnent | |
| Borne supérieure | une fusion qui ignore l’ordre et qu’on peut répéter sans risque | join |
| G-Counter | un compteur qui ne fait que monter, une entrée par réplique | |
| PN-Counter | deux G-Counters, un pour les hausses et un pour les baisses |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Une fusion qui ne peut pas se tromper
Un CRDT à base d’états envoie son état entier, et l’autre réplique le fusionne. La fusion doit être une borne supérieure, avec trois propriétés :
Commutative : a fusionné avec b égale b fusionné avec a. Associative : trois fusions donnent le même résultat, quel que soit le regroupement. Idempotente : fusionner deux fois le même état ne change rien.
Un message peut alors arriver en retard, en double ou dans le désordre, et les répliques s’accordent quand même.
Un G-Counter garde un nombre par réplique
Chaque réplique n’ajoute qu’à sa propre entrée. La valeur est la somme de toutes les entrées.
Pour fusionner, on prend le plus grand nombre pour chaque réplique. Prendre le plus grand de deux nombres est commutatif, associatif et idempotent : toute la fusion est donc une borne supérieure. Additionner à la place n’est pas idempotent.
Fusionner trois G-Counters dans deux ordres
docker exec jupyter python3 steps/gcounter.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 | Téléphone (phone) | Portable (laptop) | Tablette (tablet) |
|---|---|---|---|
| Avant la synchro | 3 | 5 | 2 |
| Après la synchro, dans n’importe quel ordre | 10 | 10 | 10 |
| Le téléphone fusionne encore deux fois le portable | 10 | 10 | 10 |
| Un simple nombre avec un rapport répété | 19 | aucun | aucun |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À vous : six ordres, un total
from itertools import permutations
def fusion(a, b):
res = dict(a)
for nom, compte in b.items():
res[nom] = max(res.get(nom, 0), compte)
return res
# Des pas comptés par trois téléphones, hors ligne
lea = {"lea": 4}
hugo = {"hugo": 7}
sami = {"sami": 2, "lea": 1} # sami a eu des nouvelles de lea plus tôt
for ordre in permutations([lea, hugo, sami]):
etat = {}
for replique in ordre:
etat = fusion(etat, replique)
print(sum(etat.values()), etat)
# Chaque ordre donne le même total. Remplacez max par une addition.
Erreur fréquente
Attention
On croit souvent qu’une fusion doit additionner les deux compteurs. Elle compte alors deux fois un état qui arrive deux fois, ce que font les réseaux. Prenez plutôt le plus grand nombre pour chaque réplique : répéter une fusion devient sans danger.
Descendre demande un second compteur
Un G-Counter ne peut pas descendre, car un nombre plus petit perdrait chaque fusion. Un PN-Counter garde donc deux G-Counters : l’un compte les hausses, l’autre les baisses.
Chacun fusionne en prenant le plus grand nombre par réplique. La valeur vaut les hausses moins les baisses.
Fusionner des « j’aime » et des retraits
docker exec jupyter python3 steps/pncounter.pyAffichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.