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

Pierres tombales, compactage et vraies bibliothèques CRDT

Après cette leçon: Je peux décider quelles pierres tombales toutes les répliques ont vues et peuvent jeter sans risque.

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

Un document plus lourd que ses mots

Un mémoire partagé affiche 2 000 mots à l’écran. En coulisses, il garde peut-être chaque lettre jamais tapée puis effacée.

Le texte supprimé est gardé pour que les fusions restent sûres. Cette leçon demande quand il peut partir, et comment les vraies bibliothèques local-first s’en occupent.

À la fin de cette leçon

Remarque

Je peux décider quelles pierres tombales toutes les répliques ont vues et peuvent jeter sans risque.

Mots-clés

MotCe que ça veut direExemple
Compactagejeter les données dont personne ne pourra plus avoir besoin
Stablevu par toutes les répliques
Ramasse-miettesla libération de la mémoire que rien n’utilisegarbage collection
Automergeune bibliothèque CRDT pour des documents de type JSON
Yjsune bibliothèque CRDT de types partagés pour les éditeurs

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

Pourquoi une pierre tombale reste

Dans RGA, chaque caractère retient le caractère après lequel il a été tapé. Une réplique qui n’a pas encore appris une suppression peut taper après le caractère supprimé.

Quand cette insertion arrive, le caractère supprimé doit encore être là pour l’y accrocher. Une pierre tombale reste donc jusqu’à ce que chaque réplique ait vu la suppression.

À vous : une heure d’édition

Code: python
import random

rng = random.Random(3)
stockes = 0      # tous les caractères tapés, gardés comme entrées
visibles = 0     # les caractères encore dans le texte

for minute in range(60):        # une heure d’édition
    tapes = rng.randint(20, 40)
    supprimes = min(visibles + tapes, rng.randint(10, 35))
    stockes += tapes
    visibles += tapes - supprimes

pierres = stockes - visibles
print("caractères visibles :", visibles)
print("entrées stockées :   ", stockes)
print("pierres tombales :   ", pierres)
print("part de pierres tombales :", round(100 * pierres / stockes), "%")
# Passez les suppressions à rng.randint(25, 40). Que devient la part ?

Deux règles pour en jeter une

Stable : chaque réplique a vu la suppression. Prenez le plus petit de chaque place dans les horloges vectorielles de toutes les répliques. Une pierre tombale est stable quand son compteur est au plus cette valeur.

Rien n’y est accroché : aucun caractère gardé dans le texte n’a été tapé après elle. Sinon, ce caractère perdrait sa place.

Compacter deux documents

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

DocumentVisiblesPierres tombalesJetées par le compactage
200 tapés, les 190 derniers supprimés10190190
200 tapés, les 190 premiers supprimés101900

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

Lister les méthodes du CRDT de texte

Commande
docker exec jupyter grep -n "def " rga.py

Affichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.

Ce qu’ajoutent les vraies bibliothèques

Automerge traite un document comme du JSON : des dictionnaires, des listes, du texte et des compteurs. Il garde l’historique des changements, donc on voit qui a changé quoi. Les répliques échangent leurs changements par un protocole de synchro.

Yjs propose des types partagés, comme du texte, des tableaux et des dictionnaires, pensés pour les éditeurs. Une réplique envoie un vecteur d’état, un compte par réplique proche d’une horloge vectorielle, et ne reçoit que les mises à jour manquantes.

Le jouet, Automerge et Yjs côte à côte

Comme le rga.py du labo, les deux bibliothèques donnent un identifiant à chaque élément inséré. Elles gardent aussi les éléments supprimés, pour que les fusions restent sûres. Yjs peut jeter le contenu d’un texte supprimé en gardant une petite marque.

Elles diffèrent du jouet par la vitesse et la taille : des formats binaires compacts, de longues suites de frappe stockées ensemble, et du code testé. Le labo n’a aucune des deux, car son image épinglée n’en contient pas : on les compare avec des mots.

Erreur fréquente

Attention

On croit souvent qu’une suppression libère de la place tout de suite. Dans un CRDT, une suppression ajoute en général une marque, et le document grossit. La place ne revient que quand le compactage peut prouver que chaque réplique a vu la suppression.

À 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.