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
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Compactage | jeter les données dont personne ne pourra plus avoir besoin | |
| Stable | vu par toutes les répliques | |
| Ramasse-miettes | la libération de la mémoire que rien n’utilise | garbage collection |
| Automerge | une bibliothèque CRDT pour des documents de type JSON | |
| Yjs | une 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
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
docker exec jupyter python3 steps/tombstones.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é
| Document | Visibles | Pierres tombales | Jetées par le compactage |
|---|---|---|---|
| 200 tapés, les 190 derniers supprimés | 10 | 190 | 190 |
| 200 tapés, les 190 premiers supprimés | 10 | 190 | 0 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Lister les méthodes du CRDT de texte
docker exec jupyter grep -n "def " rga.pyAffiché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.