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

Des compteurs qui fusionnent : G-Counter et PN-Counter

Après cette leçon: Je peux fusionner deux répliques d’un compteur pour que chaque réplique ait le même total.

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

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

MotCe que ça veut direExemple
CRDTun type de données dont les répliques fusionnent toujours vers le même état
À base d’étatsles répliques envoient leur état entier et le fusionnent
Borne supérieureune fusion qui ignore l’ordre et qu’on peut répéter sans risquejoin
G-Counterun compteur qui ne fait que monter, une entrée par réplique
PN-Counterdeux 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

Commande
docker exec jupyter python3 steps/gcounter.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é

MomentTéléphone (phone)Portable (laptop)Tablette (tablet)
Avant la synchro352
Après la synchro, dans n’importe quel ordre101010
Le téléphone fusionne encore deux fois le portable101010
Un simple nombre avec un rapport répété19aucunaucun

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

À vous : six ordres, un total

Code: python
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

Commande
docker exec jupyter python3 steps/pncounter.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.