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
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Register | ein CRDT, das einen einzigen Wert hält | |
| Nur wachsende Menge | eine Menge, zu der man hinzufügt, aus der man nie entfernt | G-Set |
| Tag | eine eindeutige Marke für ein Hinzufügen | |
| OR-Set | eine Observed-Remove-Menge: Entfernen löscht nur die gesehenen Tags | |
| Hinzufügen gewinnt | ein nebenläufiges Hinzufügen schlägt ein Entfernen | add 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
# 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
docker exec jupyter python3 steps/orset.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 |
|---|---|---|
| Start | eggs, milk (Tag ana:1) | eggs, milk (Tag ana:1) |
| Offline | streicht milk: ana:1 entfernt | fügt milk hinzu: Tag ben:1 |
| Nach dem Abgleich | eggs, milk | eggs, milk |
| Ben streicht milk und sieht ben:1 | eggs | eggs |
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
docker exec jupyter python3 steps/offline.pyHier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.