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
| Begriff | Was er bedeutet |
|---|---|
| CRDT | ein Datentyp, dessen Replikate immer zum selben Zustand zusammenfinden |
| Zustandsbasiert | Replikate senden ihren ganzen Zustand und führen ihn zusammen |
| Join | ein Zusammenführen ohne feste Reihenfolge, das sich gefahrlos wiederholen lässt |
| G-Counter | ein Zähler, der nur steigt, ein Eintrag je Replikat |
| PN-Counter | zwei 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
docker exec jupyter python3 steps/gcounter.pyHier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.
Beispiel: was das Lab gedruckt hat
| Zeitpunkt | Handy | Laptop | Tablet |
|---|---|---|---|
| Vor dem Abgleich | 3 | 5 | 2 |
| Nach dem Abgleich, jede Reihenfolge | 10 | 10 | 10 |
| Handy führt den Laptop zweimal mehr ein | 10 | 10 | 10 |
| Einfache Zahl mit wiederholter Meldung | 19 | keine | keine |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Probieren Sie es: sechs Reihenfolgen, eine Summe
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
docker exec jupyter python3 steps/pncounter.pyHier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.