Zwei Personen, ein Satz
Zwei Studierende schreiben einen Gruppenbericht in einem gemeinsamen Dokument. Die eine korrigiert ein Wort am Anfang, der andere ergänzt einen Satz am Ende, beide offline.
Text lässt sich am schwersten zusammenführen. Jedes Zeichen hat einen Platz, und Plätze verschieben sich, sobald jemand tippt.
Am Ende dieser Lektion
Notiz
Ich kann zwei Replikate eines Textes zusammenführen, dessen Zeichen Positionen tragen.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Sequenz-CRDT | ein CRDT für eine geordnete Liste, etwa Text | |
| Index | der Platz eines Zeichens, vom Anfang gezählt | 0, 1, 2 |
| Zeichen-Id | ein Name, den kein anderes Zeichen hat | (6, 'ben') |
| Tombstone | ein gelöschtes Zeichen, das als Markierung bleibt | |
| Verschränkung | zwei gleichzeitig getippte Wörter, Buchstabe für Buchstabe vermischt |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein Index bedeutet Verschiedenes
Am einfachsten sendet man eine Änderung als "füge S an Index 0 ein" oder "lösche Index 2". Ein Index zählt aber vom Anfang eines Textes, der sich auf dem anderen Replikat schon geändert hat.
Fügt Ida am Anfang etwas ein, rückt jedes spätere Zeichen einen Platz weiter. Jans "lösche Index 2" zeigt jetzt auf ein anderes Zeichen.
Probieren Sie es: zwei Änderungen per Index
def anwenden(text, aenderung):
art, index, zeichen = aenderung
if art == "einfuegen":
return text[:index] + zeichen + text[index:]
return text[:index] + text[index + 1:]
start = "Hut"
ida = ("einfuegen", 0, "S") # Ida tippt S an den Anfang: "SHut"
jan = ("loeschen", 2, "") # Jan löscht das t an Index 2: "Hu"
# Jedes Replikat wendet zuerst die eigene Änderung an, dann die andere.
bei_ida = anwenden(anwenden(start, ida), jan)
bei_jan = anwenden(anwenden(start, jan), ida)
print("Ida sieht:", bei_ida)
print("Jan sieht:", bei_jan)
# Welches Zeichen wollte Jan löschen? Welches hat Idas Kopie gelöscht?
Idee 1: eine Position zwischen Nachbarn
Jedes Zeichen bekommt eine Positionszahl, und sortiert wird danach. Um zwischen 0.4 und 0.5 zu tippen, nimmt man 0.45. Nichts anderes verschiebt sich.
Echte Systeme nutzen eine Liste ganzer Zahlen wie [4, 5], damit immer Platz für eine weitere bleibt. Der Replikatname entscheidet bei Gleichstand. Das ist die Idee hinter Logoot.
Idee 2: eine Id und ein Elternzeichen
RGA gibt jedem Zeichen eine Id aus Zähler und Replikatname und merkt sich, nach welchem Zeichen es getippt wurde. Gelesen wird der Text vom Anfang aus, neuere Kinder zuerst.
Eine Löschung markiert das Zeichen nur als Tombstone, weil ein anderes Replikat noch dahinter tippen kann. Die Datei rga.py des Labs arbeitet so.
Zwei Änderungen an einer Zeile zusammenführen
docker exec jupyter python3 steps/text.pyHier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.
Beispiel: was das Lab gedruckt hat
| Zeitpunkt | Ana | Ben |
|---|---|---|
| Gemeinsam | Hello | Hello |
| Offline | Hello world | Oh, ello (H gelöscht) |
| Nach dem Abgleich | Oh, ello world | Oh, ello world |
| Gespeichert | ein Tombstone, das H | ein Tombstone, das H |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Wenn zwei Wörter sich vermischen
Ana tippt "cat" und Ben "dog", an derselben Stelle und zur selben Zeit. Bei Positionen zwischen Nachbarn wählen beide dieselben Zahlen, und der Replikatname sortiert jedes Paar.
Die Buchstaben wechseln sich ab. RGA hängt jeden Buchstaben an den vorigen, also bleibt jedes Wort ganz.
Zwei Wörter beim Verschränken beobachten
docker exec jupyter python3 steps/interleave.pyHier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.
Ein häufiger Fehler
Warnung
Viele glauben, ein Zusammenführen sei richtig, wenn alle Replikate denselben Text haben. "cdaotg" steht auf jedem Replikat gleich da, und niemand hat es getippt. Übereinstimmung ist Pflicht, aber ein gutes Text-CRDT hält auch zusammen, was jede Person getippt hat.