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

Vektoruhren, Operationen und Deltas

Nach dieser Lektion: Ich kann zwei Vektoruhren vergleichen und sagen, welche Änderung zuerst passiert ist.

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

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

BegriffWas er bedeutetBeispiel
Passiert vorhereine Änderung war bekannt, als die andere entstandhappened before
Vektoruhrein Zähler je Replikat, der mit jeder Änderung reist{"a": 1, "b": 2}
Operationsbasiertes CRDTReplikate senden Operationen statt ganzer Zustände
Kausale Zustellungeine Änderung gilt erst nach den Änderungen, die sie gesehen hat
Deltanur 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

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.

Beispiel: was das Lab gedruckt hat

UhrenVerglichenWarum
a {a: 1} und b {b: 1}nebenläufigjede ist an einem Platz größer
a {a: 1} und b {a: 1, b: 2}a vor bb hörte a und schrieb dann
c {a: 1, b: 2, c: 1} und ac nach ac hörte b, und b hörte a
a und eine Kopie von agleichjeder 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

Code: python
# 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

Befehl
docker exec jupyter python3 steps/delta.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.