Ein Dokument, schwerer als seine Wörter
Ein gemeinsamer Aufsatz zeigt 2.000 Wörter auf dem Bildschirm. Im Hintergrund speichert er vielleicht jeden Buchstaben, der je getippt und gelöscht wurde.
Gelöschter Text bleibt, damit das Zusammenführen sicher bleibt. Diese Lektion fragt, wann er gehen darf und wie echte Local-first-Bibliotheken damit umgehen.
Am Ende dieser Lektion
Notiz
Ich kann entscheiden, welche Tombstones jedes Replikat gesehen hat und sicher wegfallen dürfen.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Kompaktierung | Daten entfernen, die niemand mehr brauchen kann | |
| Stabil | von jedem Replikat gesehen | |
| Speicherbereinigung | Speicher freigeben, den nichts mehr nutzt | Garbage Collection |
| Automerge | eine CRDT-Bibliothek für JSON-artige Dokumente | |
| Yjs | eine CRDT-Bibliothek gemeinsamer Typen für Editoren |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Warum ein Tombstone bleibt
In RGA merkt sich jedes Zeichen, nach welchem Zeichen es getippt wurde. Hat ein Replikat von einer Löschung noch nichts gehört, kann es hinter dem gelöschten Zeichen tippen.
Kommt dieses Einfügen an, muss das gelöschte Zeichen noch da sein, damit es dort hängen kann. Darum bleibt ein Tombstone, bis jedes Replikat die Löschung gesehen hat.
Probieren Sie es: eine Stunde Bearbeitung
import random
rng = random.Random(3)
gespeichert = 0 # alle je getippten Zeichen, als Einträge behalten
sichtbar = 0 # Zeichen, die noch im Text stehen
for minute in range(60): # eine Stunde Bearbeitung
getippt = rng.randint(20, 40)
geloescht = min(sichtbar + getippt, rng.randint(10, 35))
gespeichert += getippt
sichtbar += getippt - geloescht
tombstones = gespeichert - sichtbar
print("sichtbare Zeichen: ", sichtbar)
print("gespeicherte Einträge:", gespeichert)
print("Tombstones: ", tombstones)
print("Anteil Tombstones:", round(100 * tombstones / gespeichert), "%")
# Ändern Sie das Löschen in rng.randint(25, 40). Was passiert mit dem Anteil?
Zwei Regeln, bevor einer wegfällt
Stabil: Jedes Replikat hat die Löschung gesehen. Nehmen Sie je Platz das Kleinste über die Vektoruhren aller Replikate. Ein Tombstone ist stabil, wenn sein Zähler höchstens so groß ist.
Nichts hängt daran: Kein Zeichen, das im Text bleibt, wurde dahinter getippt. Sonst verlöre dieses Zeichen seinen Platz.
Zwei Dokumente kompaktieren
docker exec jupyter python3 steps/tombstones.pyHier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.
Beispiel: was das Lab gedruckt hat
| Dokument | Sichtbar | Tombstones | Durch Kompaktierung entfernt |
|---|---|---|---|
| 200 getippt, die letzten 190 gelöscht | 10 | 190 | 190 |
| 200 getippt, die ersten 190 gelöscht | 10 | 190 | 0 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Auflisten, was das Text-CRDT des Labs kann
docker exec jupyter grep -n "def " rga.pyHier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.
Was echte Bibliotheken hinzufügen
Automerge behandelt ein Dokument wie JSON: Maps, Listen, Text und Zähler. Es behält den Verlauf der Änderungen, man sieht also, wer was geändert hat. Replikate tauschen Änderungen über ein Abgleichsprotokoll aus.
Yjs bietet gemeinsame Typen wie Text, Arrays und Maps, gebaut für Editoren. Ein Replikat sendet einen Zustandsvektor, eine Zahl je Replikat ähnlich einer Vektoruhr, und bekommt nur die fehlenden Updates.
Spielzeug, Automerge und Yjs nebeneinander
Wie rga.py im Lab geben beide Bibliotheken jedem eingefügten Element eine Id und behalten gelöschte Elemente, damit das Zusammenführen sicher bleibt. Yjs kann den Inhalt gelöschten Textes verwerfen und behält eine kleine Markierung.
Vom Spielzeug unterscheiden sie sich in Tempo und Größe: kompakte Binärformate, lange Tippfolgen gemeinsam gespeichert, getesteter Code. Das Lab hat keine der beiden, weil sein festgelegtes Image keine enthält, also vergleichen wir in Worten.
Ein häufiger Fehler
Warnung
Viele glauben, eine Löschung gebe sofort Platz frei. In einem CRDT fügt eine Löschung meist eine Markierung hinzu, das Dokument wächst also. Platz kommt erst zurück, wenn die Kompaktierung belegen kann, dass jedes Replikat die Löschung gesehen hat.