Lässt es sich mit cremefarbenem Papier, einer Tönung, mehr Kontrast oder größerer Schrift besser lesen? Wählen Sie Ihre Farben und Ihre Schrift, einmalig für alle Seiten.

Kostenlose Lektion

Tombstones, Kompaktierung und echte CRDT-Bibliotheken

Nach dieser Lektion: Ich kann entscheiden, welche Tombstones jedes Replikat gesehen hat und sicher wegfallen dürfen.

Lektion, 65 Min.2 BefehleCRDT-Lab: Local-first-Abgleich mit Zählern, Mengen, Vektoruhren und Text in Python

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

BegriffWas er bedeutetBeispiel
KompaktierungDaten entfernen, die niemand mehr brauchen kann
Stabilvon jedem Replikat gesehen
SpeicherbereinigungSpeicher freigeben, den nichts mehr nutztGarbage Collection
Automergeeine CRDT-Bibliothek für JSON-artige Dokumente
Yjseine 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

Code: python
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

Befehl
docker exec jupyter python3 steps/tombstones.py

Hier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.

Beispiel: was das Lab gedruckt hat

DokumentSichtbarTombstonesDurch Kompaktierung entfernt
200 getippt, die letzten 190 gelöscht10190190
200 getippt, die ersten 190 gelöscht101900

Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.

Auflisten, was das Text-CRDT des Labs kann

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

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

Über dieses Lab und seinen Quellcode: CRDT-Lab: Local-first-Abgleich mit Zählern, Mengen, Vektoruhren und Text in Python

Sie unterrichten eine Gruppe? Weisen Sie dieses Modul Ihren Studierenden zu, mit Handbuch für Lehrende, automatisch geprüften Aufgaben und einem Lab für jede Person.