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

Register und Mengen: was "Hinzufügen gewinnt" heißt

Nach dieser Lektion: Ich kann zwei Replikate einer Observed-Remove-Menge zusammenführen.

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

Die Milch, die zurückkam

Ana und Ben teilen eine Einkaufsliste. Im Bus streicht Ana die Milch, weil sie welche gekauft hat. Zur selben Zeit fügt Ben Milch hinzu, weil der Kühlschrank leer aussieht.

Soll nach dem Abgleich Milch auf der Liste stehen? Es gibt keine einzig richtige Antwort, aber jedes Handy muss dieselbe geben.

Am Ende dieser Lektion

Notiz

Ich kann zwei Replikate einer Observed-Remove-Menge zusammenführen.

Schlüsselwörter

BegriffWas er bedeutetBeispiel
Registerein CRDT, das einen einzigen Wert hält
Nur wachsende Mengeeine Menge, zu der man hinzufügt, aus der man nie entferntG-Set
Tageine eindeutige Marke für ein Hinzufügen
OR-Seteine Observed-Remove-Menge: Entfernen löscht nur die gesehenen Tags
Hinzufügen gewinntein nebenläufiges Hinzufügen schlägt ein Entfernenadd wins

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

Ein Register behält den größeren Stempel

Lektion 1 hat das Last-Writer-Wins-Register gezeigt. Als CRDT ist sein Zustand ein Wert und ein Stempel aus Zeit und Replikatname. Beim Zusammenführen bleibt das Paar mit dem größeren Stempel.

Das Maximum ist ein Join, also stimmen Register immer überein. Sie stimmen aber überein, indem sie einen Wert wegwerfen. Bei einer Farbe ist das in Ordnung, bei einer Einkaufsliste schlecht.

Drei Arten, eine Menge zu teilen

Nur wachsende Menge: Zusammenführen ist Vereinigung. Entfernen geht nie. Zwei-Phasen-Menge: eine Menge der Hinzufügungen und eine der Entfernungen, beide vereinigt. Ein einmal entferntes Element kommt nie zurück. OR-Set: Jedes Hinzufügen bekommt ein neues Tag. Ein Entfernen löscht die Tags, die es gesehen hat. Ein Element ist drin, solange es ein lebendes Tag hat.

Probieren Sie es: eine Zwei-Phasen-Menge

Code: python
# Eine Zwei-Phasen-Menge: eine Menge der Hinzufügungen, eine der Entfernungen.
# Ein Element ist drin, wenn es hinzugefügt und nie entfernt wurde.
def mitglieder(stand):
    return sorted(stand["hinzu"] - stand["entfernt"])

def zusammenfuehren(a, b):
    return {"hinzu": a["hinzu"] | b["hinzu"],
            "entfernt": a["entfernt"] | b["entfernt"]}

ida = {"hinzu": {"Milch", "Eier"}, "entfernt": set()}
jan = {"hinzu": {"Milch", "Eier"}, "entfernt": set()}

ida["entfernt"].add("Milch")    # Ida streicht Milch, offline
jan["hinzu"].add("Milch")       # Jan fügt Milch erneut hinzu, offline

beide = zusammenfuehren(ida, jan)
print("nach dem Abgleich:", mitglieder(beide))
beide["hinzu"].add("Milch")     # noch einmal Milch hinzufügen
print("nach einem weiteren Hinzufügen:", mitglieder(beide))
# Kann jemals wieder Milch auf diese Liste kommen?

Warum das neue Hinzufügen überlebt

Anas Entfernen kann nur die Tags löschen, die Ana gesehen hat. Bens Hinzufügen hat ein neues Tag erzeugt, das Ana nie gesehen hat, also wird es nicht entfernt.

Nach dem Zusammenführen hat Milch noch ein lebendes Tag und bleibt auf der Liste. Diese Regel heißt "Hinzufügen gewinnt". Ein Entfernen, das alle Tags gesehen hat, entfernt das Element wirklich.

Mit einem OR-Set die Milch behalten

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.

Beispiel: was das Lab gedruckt hat

ZeitpunktAnaBen
Starteggs, milk (Tag ana:1)eggs, milk (Tag ana:1)
Offlinestreicht milk: ana:1 entferntfügt milk hinzu: Tag ben:1
Nach dem Abgleicheggs, milkeggs, milk
Ben streicht milk und sieht ben:1eggseggs

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

Ein häufiger Fehler

Warnung

Viele glauben, ein Entfernen lösche das Element, egal woher es kam. Im OR-Set löscht ein Entfernen nur die Tags, die sein Replikat gesehen hat. Ein gleichzeitiges Hinzufügen an anderer Stelle behält sein Tag, also bleibt das Element.

Drei Replikate nach vielen Änderungen abgleichen

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.

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