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
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Arrivé avant | un changement était connu quand l’autre a été fait | |
| Horloge vectorielle | un compteur par réplique, transporté avec chaque changement | {"a": 1, "b": 2} |
| CRDT par opérations | les répliques envoient des opérations au lieu d’états entiers | |
| Livraison causale | un changement n’est appliqué qu’après ceux qu’il a vus | |
| Delta | seulement 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
docker exec jupyter python3 steps/clocks.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é
| Horloges | Comparaison | Pourquoi |
|---|---|---|
| a {a: 1} et b {b: 1} | concurrent | chacune 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 a | c 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
# 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
docker exec jupyter python3 steps/delta.pyAffichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.