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

Grundlagen der CRDTs

Die ganze Lektion ist kostenlos und interaktiv. Lesen Sie sie hier, oder drücken Sie „Lab starten“, um sie wirklich in einem Live-Lab auszuführen, ganz ohne Konto.

Container-Lab10 Min. Lesezeit6 Befehle

Im Zug bearbeiten, zu Hause abgleichen

Du änderst im Zug ohne Netz eine gemeinsame Notiz auf deinem Handy. Zu Hause hat jemand dieselbe Notiz auf einem Laptop geändert. Sobald das Handy wieder Netz hat, sollen beide Änderungen erhalten bleiben. Apps, die zuerst offline arbeiten und später abgleichen, heißen local-first, und die Datentypen, die das Zusammenführen sicher machen, heißen CRDTs.

Am Ende dieser Lektion

Notiz

Ich kann erklären, wie zwei Replikate, die dieselben Daten offline geändert haben, am Ende übereinstimmen.

Schlüsselwörter

  • Replikat: eine Kopie der Daten auf einem Gerät.
  • Abgleich: Änderungen zwischen Replikaten austauschen.
  • Zusammenführen: zwei Replikate zu einem Zustand vereinen.
  • CRDT: ein Datentyp, dessen Zusammenführen in jeder Reihenfolge dasselbe ergibt.
  • Nebenläufig: zwei Änderungen, von denen keine von der anderen wusste.
  • Tombstone: eine Markierung, die sagt, dass etwas gelöscht wurde.

Zum Einstieg: was du schon weißt

Notiz

Antworte im Kopf. 1. Du speicherst eine Datei auf zwei Computern. Welche Kopie stimmt? 2. Ist 3 + 5 dasselbe wie 5 + 3? 3. Was ist die größte Zahl von 4, 9 und 2? Antworten: Das hängt davon ab, was sich in jeder geändert hat; ja, die Reihenfolge spielt keine Rolle; 9. Auf den letzten beiden Ideen baut das Zusammenführen eines CRDTs auf.

Bevor du anfängst

Notiz

Klicke oben in der Leiste dieser Lektion auf Lab starten und warte, bis dort steht, dass es läuft. Es gibt einen Container, jupyter, und das Terminal erreicht sein Python mit docker exec jupyter, das einen Befehl darin ausführt. Der Link JupyterLab öffnet seine Webseite, Port 8888. Jede Schaltfläche Ausführen unten tippt ihren Befehl ins Terminal deines Labs, einen nach dem anderen in derselben Sitzung. Wenn du zuschauen oder eigene Befehle tippen willst, klicke in der Leiste auf Terminal öffnen (neuer Tab).

Ein naiver Abgleich verliert eine Änderung

Das Handy hat um 10:05 den Titel geändert, der Laptop um 10:07 den Text. Der naive Abgleich behält die ganze zuletzt gespeicherte Notiz, also geht die Titeländerung des Handys verloren: Das Skript druckt True. Feld für Feld zusammengeführt bleiben beide: der Titel "Trip to York" und der Text "Pack bags, book hotel". Das Skript druckt englische Wörter, wichtig ist, was erhalten bleibt.

Befehl
docker exec jupyter python3 steps/lostedit.py

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

Ein Zähler, der sicher zusammenführt

Drei Replikate zählen offline Seitenaufrufe: 3, 5 und 2. Ein G-Counter hat eine Zahl je Replikat und nimmt beim Zusammenführen jeweils die größere. Nach dem Abgleich in verschiedenen Reihenfolgen sieht jedes Replikat 10, und denselben Zustand noch zweimal einzuführen ergibt weiter 10. Eine einfache Zahl, die jede Meldung addiert, zählt eine wiederholte Nachricht doppelt und kommt auf 19.

Befehl
docker exec jupyter python3 steps/gcounter.py

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

In einer gemeinsamen Liste gewinnt ein gleichzeitiges Hinzufügen

Ana und Ben teilen eine Einkaufsliste mit milk (Milch) und eggs (Eier). Offline streicht Ana die Milch, während Ben sie wieder hinzufügt. Nach dem Abgleich stehen auf beiden Listen eggs und milk. Die Menge, ein OR-Set, gibt jedem Hinzufügen ein Tag, und ein Entfernen löscht nur die Tags, die es gesehen hat. Bens neues Tag hat Ana nie gesehen, also bleibt die Milch.

Befehl
docker exec jupyter python3 steps/orset.py

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

Prüfe dich

Tipp

Warum zählt ein G-Counter nichts doppelt, wenn man ihn zweimal zusammenführt? Antwort: Das Zusammenführen nimmt für jedes Replikat die größere von zwei Zahlen, und die größere von 5 und 5 ist immer noch 5.

Zwei Änderungen an einer Textzeile

Beide Replikate beginnen mit "Hello". Offline hängt Ana " world" an, und Ben setzt "Oh, " an den Anfang und löscht das H. Nach dem Abgleich steht auf beiden "Oh, ello world". Jedes Zeichen hat eine Id und merkt sich, nach welchem Zeichen es getippt wurde, also bedeutet ein Einfügen auf jedem Replikat dasselbe. Das gelöschte H bleibt als ein Tombstone.

Befehl
docker exec jupyter python3 steps/text.py

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

Vektoruhren zeigen, was vorher passiert ist

Jedes Replikat zählt seine eigenen Änderungen in einer Vektoruhr. Replikat a schreibt, und b schreibt, ohne von a gehört zu haben: Die beiden Uhren sind concurrent (nebenläufig). Dann hört b von a und schreibt erneut, also liegt a jetzt before (vor) b. Eine Uhr, mit sich selbst verglichen, ist equal (gleich).

Befehl
docker exec jupyter python3 steps/clocks.py

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

Drei Replikate, viele Änderungen, eine Antwort

Ein Handy, ein Laptop und ein Tablet machen offline je 30 zufällige Änderungen an einer gemeinsamen Liste und einem Zähler. Dann gleichen sie sich in zufälliger Reihenfolge ab. Alle drei enden mit denselben fünf Einträgen und derselben Zahl, 28.

Befehl
docker exec jupyter python3 steps/offline.py

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

Ein häufiger Fehler

Warnung

Viele denken, die neueste Änderung solle immer gewinnen. Die Uhr eines Handys kann aber falsch gehen, und "die neueste" wirft die andere Änderung weg. Ein CRDT behält beide Änderungen, wo es kann, und wählt nur nach einer Regel eine aus, die jedes Replikat gleich anwendet.

Dieselbe Arbeit in einem Notebook

Öffne JupyterLab über die Leiste und doppelklicke auf start.ipynb. Es führt zwei Zähler, zwei Einkaufslisten und zwei Kopien einer Textzeile zusammen. Klicke auf eine Zelle und drücke Umschalt und Eingabe, um sie auszuführen. In die letzte Zelle gehört deine eigene Frage, und crdt.py ist kurz genug, um es ganz zu lesen.

Abschlusscheck

Tipp

Antworte, ohne zurückzublättern. 1. Was hat der naive Abgleich verloren? 2. Wie führt ein G-Counter zusammen? 3. Was passiert im OR-Set mit einem Hinzufügen, das die entfernende Person nie gesehen hat? 4. Was heißt concurrent bei zwei Vektoruhren? Antworten: die Titeländerung des Handys; er nimmt je Replikat die größere Zahl; es überlebt; keine der beiden Änderungen wusste von der anderen.

Für Lehrkräfte

Tipp

Diese Lektion ist ein kleines Beispiel für eine Lektion, die in einem Lab abläuft: Die Schritte und die Schaltflächen „Ausführen“ sind die Lektion, und das Lab ist die eigene Kopie jeder lernenden Person. Das Lab ist ein Dienst, JupyterLab mit CRDTs aus der Standardbibliothek von Python, und nichts hier bewertet sich selbst: Die Lernenden geben ein eigenes Notebook ab, aus JupyterLab heruntergeladen, und einen Satz dazu, was es gezeigt hat. Wichtigste Lernpunkte: 1. Ein naiver Abgleich nach Last Writer Wins verliert Änderungen. 2. Das Zusammenführen eines CRDTs ergibt in jeder Reihenfolge und bei Wiederholung dasselbe. 3. Vektoruhren unterscheiden vorher von nebenläufig. Häufiger Fehler: zu glauben, die neueste Änderung solle immer gewinnen. Im Lab läuft keine echte CRDT-Bibliothek: Automerge und Yjs erklärt das Hochschulmodul. Material: das Lab und ein Browser. Tipp: Lassen Sie zwei Lernende eine Papiernotiz bearbeiten und die beiden Kopien laut zusammenführen. Kopieren Sie die Lektion in Ihr eigenes Modul und ändern Sie sie, oder bauen Sie im Lektionseditor über das Menü Lab eine neue von Grund auf.

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

Sie unterrichten eine Klasse? Weisen Sie diese Lektionen Ihren Lernenden zu, mit Bewertung und einem Lab für jede lernende Person.