Eine Antwort, die vor der Frage ankommt
In einem Gruppenchat erscheint manchmal eine Antwort vor der Nachricht, auf die sie antwortet. Das Netz hat sie in falscher Reihenfolge zugestellt.
Replikate haben dasselbe Problem. Um gut zusammenzuführen, muss ein Replikat wissen, welche Änderung zuerst kam und welche zwei Änderungen niemand geordnet hat.
Am Ende dieser Lektion
Notiz
Ich kann zwei Vektoruhren vergleichen und sagen, welche Änderung zuerst passiert ist.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Passiert vorher | eine Änderung war bekannt, als die andere entstand | happened before |
| Vektoruhr | ein Zähler je Replikat, der mit jeder Änderung reist | {"a": 1, "b": 2} |
| Operationsbasiertes CRDT | Replikate senden Operationen statt ganzer Zustände | |
| Kausale Zustellung | eine Änderung gilt erst nach den Änderungen, die sie gesehen hat | |
| Delta | nur der Teil eines Zustands, der sich geändert hat |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Eine Vektoruhr zählt jedes Replikat
Jedes Replikat führt einen Zähler für jedes Replikat. Vor einer Änderung erhöht es den eigenen Zähler um eins. Hört es von einem anderen Replikat, nimmt es je Zähler das Größere.
Zwei Uhren vergleicht man Platz für Platz. Ist jeder Platz von a höchstens so groß wie bei b und einer kleiner, passierte a vor b. Ist jede irgendwo größer, sind sie nebenläufig.
Vektoruhren vergleichen
docker exec jupyter python3 steps/clocks.pyHier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.
Beispiel: was das Lab gedruckt hat
| Uhren | Verglichen | Warum |
|---|---|---|
| a {a: 1} und b {b: 1} | nebenläufig | jede ist an einem Platz größer |
| a {a: 1} und b {a: 1, b: 2} | a vor b | b hörte a und schrieb dann |
| c {a: 1, b: 2, c: 1} und a | c nach a | c hörte b, und b hörte a |
| a und eine Kopie von a | gleich | jeder Platz gleich |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Operationen statt Zustände senden
Ein zustandsbasiertes CRDT sendet seinen ganzen Zustand, und der kann groß sein. Ein operationsbasiertes CRDT sendet jede Operation, etwa "füge Milch hinzu", und die ist klein.
Dafür muss jede Operation genau einmal ankommen, und eine Änderung muss nach den Änderungen ankommen, die sie gesehen hat. Sonst kommt ein Entfernen vor dem Hinzufügen an, das es entfernen sollte.
Probieren Sie es: zwei vertauschte Operationen
# Operationsbasiert: Replikate senden Operationen, keine ganzen Zustände.
# Ida fügt Milch hinzu und entfernt sie dann. Kim empfängt beide Operationen.
def anwenden(dinge, operation):
art, ding = operation
if art == "hinzu":
return dinge | {ding}
return dinge - {ding}
erste = ("hinzu", "Milch")
zweite = ("entfernen", "Milch")
in_reihe = anwenden(anwenden(set(), erste), zweite)
vertauscht = anwenden(anwenden(set(), zweite), erste)
print("in Reihenfolge:", sorted(in_reihe))
print("vertauscht: ", sorted(vertauscht))
# Das Netz hat zwei Nachrichten vertauscht. Was hätte Kim mit dem
# Entfernen tun sollen, als es zuerst ankam?
Ein häufiger Fehler
Warnung
Viele glauben, ein Zeitstempel reiche, um Änderungen zu ordnen. Zwei Uhren auf zwei Geräten weichen voneinander ab, und eine Zeit kann nicht sagen, dass zwei Änderungen nebenläufig waren. Eine Vektoruhr kann das, weil sie festhält, was jedes Replikat gehört hatte.
Deltas: das Beste aus beiden
Ein Delta-CRDT sendet nur den Teil seines Zustands, der sich geändert hat, seit das andere Replikat zuletzt etwas gehört hat. Eingeführt wird es mit demselben Join wie ein ganzer Zustand.
Ein verlorenes oder doppeltes Delta schadet also nicht, wie bei einem Zustand, und die Nachricht bleibt klein, wie bei einer Operation. Eine Vektoruhr sagt, was das andere Replikat schon hat.
Ein Delta statt des ganzen Zustands senden
docker exec jupyter python3 steps/delta.pyHier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.