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

Zähler, die sich zusammenführen: G-Counter und PN-Counter

Nach dieser Lektion: Ich kann zwei Zähler-Replikate so zusammenführen, dass jedes Replikat dieselbe Summe hat.

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

Likes auf drei Handys zählen

Ein Beitrag bekommt Likes von Leuten auf drei Handys, und jedes Handy ist eine Weile offline. Beim Abgleich soll die Summe jedes Like genau einmal zählen. Keines darf fehlen, und keines darf doppelt zählen.

Eine gemeinsame Zahl allein schafft das nicht. Ein CRDT-Zähler schon.

Am Ende dieser Lektion

Notiz

Ich kann zwei Zähler-Replikate so zusammenführen, dass jedes Replikat dieselbe Summe hat.

Schlüsselwörter

BegriffWas er bedeutet
CRDTein Datentyp, dessen Replikate immer zum selben Zustand zusammenfinden
ZustandsbasiertReplikate senden ihren ganzen Zustand und führen ihn zusammen
Joinein Zusammenführen ohne feste Reihenfolge, das sich gefahrlos wiederholen lässt
G-Counterein Zähler, der nur steigt, ein Eintrag je Replikat
PN-Counterzwei G-Counter, einer für Plus und einer für Minus

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

Ein Zusammenführen, das nicht schiefgehen kann

Ein zustandsbasiertes CRDT sendet seinen ganzen Zustand, und das andere Replikat führt ihn ein. Dieses Zusammenführen muss ein Join sein, mit drei Eigenschaften:

Kommutativ: a mit b zusammengeführt ergibt dasselbe wie b mit a. Assoziativ: Drei Zusammenführungen ergeben in jeder Klammerung dasselbe. Idempotent: Denselben Zustand zweimal einzuführen ändert nichts.

Dann darf eine Nachricht spät, doppelt oder in falscher Reihenfolge kommen, und die Replikate stimmen trotzdem überein.

Ein G-Counter hat eine Zahl je Replikat

Jedes Replikat erhöht nur seinen eigenen Eintrag. Der Wert ist die Summe aller Einträge.

Beim Zusammenführen nimmt man für jedes Replikat die größere Zahl. Das Maximum zweier Zahlen ist kommutativ, assoziativ und idempotent, also ist das ganze Zusammenführen ein Join. Addieren statt Maximum ist nicht idempotent.

Drei G-Counter in zwei Reihenfolgen zusammenführen

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.

Beispiel: was das Lab gedruckt hat

ZeitpunktHandyLaptopTablet
Vor dem Abgleich352
Nach dem Abgleich, jede Reihenfolge101010
Handy führt den Laptop zweimal mehr ein101010
Einfache Zahl mit wiederholter Meldung19keinekeine

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

Probieren Sie es: sechs Reihenfolgen, eine Summe

Code: python
from itertools import permutations

def zusammenfuehren(a, b):
    neu = dict(a)
    for name, zahl in b.items():
        neu[name] = max(neu.get(name, 0), zahl)
    return neu

# Schritte, offline auf drei Handys gezählt
ida = {"ida": 4}
jan = {"jan": 7}
kim = {"kim": 2, "ida": 1}   # kim hat früher von ida gehört

for reihenfolge in permutations([ida, jan, kim]):
    stand = {}
    for replikat in reihenfolge:
        stand = zusammenfuehren(stand, replikat)
    print(sum(stand.values()), stand)
# Jede Reihenfolge ergibt dieselbe Summe. Ersetzen Sie max durch eine Addition.

Ein häufiger Fehler

Warnung

Viele glauben, beim Zusammenführen müsse man die beiden Zähler addieren. Dann zählt ein Zustand doppelt, wenn er zweimal ankommt, und Netze tun das. Nehmen Sie stattdessen je Replikat die größere Zahl, dann schadet ein wiederholtes Zusammenführen nicht.

Zum Herunterzählen braucht es einen zweiten Zähler

Ein G-Counter kann nicht sinken, weil eine kleinere Zahl jedes Zusammenführen verliert. Darum hat ein PN-Counter zwei G-Counter: Einer zählt das Plus, einer das Minus.

Beide werden mit der größeren Zahl je Replikat zusammengeführt. Der Wert ist Plus minus Minus.

Likes und zurückgenommene Likes zusammenführen

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