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

Horloges vectorielles, opérations et deltas

Après cette leçon: Je peux comparer deux horloges vectorielles et dire quel changement a eu lieu en premier.

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

Une réponse arrivée avant la question

Dans une discussion de groupe, une réponse s’affiche parfois avant le message auquel elle répond. Le réseau les a livrés dans le mauvais ordre.

Les répliques ont le même problème. Pour bien fusionner, une réplique doit savoir quel changement est venu en premier, et quels deux changements personne n’a ordonnés.

À la fin de cette leçon

Remarque

Je peux comparer deux horloges vectorielles et dire quel changement a eu lieu en premier.

Mots-clés

MotCe que ça veut direExemple
Arrivé avantun changement était connu quand l’autre a été fait
Horloge vectorielleun compteur par réplique, transporté avec chaque changement{"a": 1, "b": 2}
CRDT par opérationsles répliques envoient des opérations au lieu d’états entiers
Livraison causaleun changement n’est appliqué qu’après ceux qu’il a vus
Deltaseulement la partie d’un état qui a changé

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

Une horloge vectorielle compte chaque réplique

Chaque réplique garde un compteur pour chaque réplique. Avant un changement, elle ajoute un à son propre compteur. Quand elle reçoit des nouvelles d’une autre réplique, elle prend le plus grand de chaque compteur.

On compare deux horloges place par place. Si chaque place de a est au plus celle de b, et qu’une est plus petite, a est arrivé avant b. Si chacune est plus grande quelque part, elles sont concurrentes.

Comparer des horloges vectorielles

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

HorlogesComparaisonPourquoi
a {a: 1} et b {b: 1}concurrentchacune est plus grande à une place
a {a: 1} et b {a: 1, b: 2}a avant b (before)b a entendu a, puis a écrit
c {a: 1, b: 2, c: 1} et ac après a (after)c a entendu b, qui avait entendu a
a et une copie de aégales (equal)chaque place est la même

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

Envoyer des opérations au lieu d’états

Un CRDT à base d’états envoie son état entier, qui peut être gros. Un CRDT par opérations envoie chaque opération, comme « ajouter du lait », qui est petite.

Mais chaque opération doit arriver exactement une fois, et un changement doit arriver après ceux qu’il a vus. Sinon, un retrait peut arriver avant l’ajout qu’il retirait.

À vous : deux opérations inversées

Code: python
# Par opérations : les répliques envoient des opérations, pas des états.
# Ana ajoute du lait, puis le retire. Sami reçoit les deux opérations.
def appliquer(articles, op):
    genre, article = op
    if genre == "ajouter":
        return articles | {article}
    return articles - {article}

premiere = ("ajouter", "lait")
seconde = ("retirer", "lait")

dans_l_ordre = appliquer(appliquer(set(), premiere), seconde)
inversees = appliquer(appliquer(set(), seconde), premiere)
print("arrivées dans l’ordre :", sorted(dans_l_ordre))
print("arrivées inversées :   ", sorted(inversees))
# Le réseau a inversé deux messages. Qu’aurait dû faire Sami
# du retrait arrivé en premier ?

Erreur fréquente

Attention

On croit souvent qu’un horodatage suffit à ordonner les changements. Deux horloges sur deux appareils ne s’accordent pas, et une heure ne peut pas dire que deux changements étaient concurrents. Une horloge vectorielle le peut, car elle note ce que chaque réplique avait entendu.

Les deltas : le meilleur des deux

Un CRDT à deltas n’envoie que la partie de son état qui a changé depuis les dernières nouvelles de l’autre réplique. Il la fusionne avec la même borne supérieure qu’un état entier.

Un delta perdu ou répété est donc sans danger, comme un état, et le message reste petit, comme une opération. Une horloge vectorielle dit ce que l’autre réplique a déjà.

Envoyer un delta au lieu de l’état entier

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