Zum Inhalt springen
Deutsch

Sets (GSet, ORSet)

Zwei Set-CRDTs:

TypOperationenWann
GSet<E>nur addAppend-only-Collections — beobachtete Arten, gesehene User.
ORSet<E>add + removeMembership-Sets, deren Elemente kommen und gehen.

Beide konvergieren bei nebenläufigen Writes; der Spezial-Trick von ORSet ist die Auflösung von “nebenläufigem Add und Remove desselben Elements”, damit Removes nicht versehentlich ein noch gewolltes Item löschen.

import { GSet } from 'actor-ts/crdt';
let s = GSet.empty<string>();
s = s.add('apple');
s = s.add('banana');
s.value(); // → ['apple', 'banana']

Der State ist ein einfaches Set; Merge ist eine Vereinigung. Kann nicht entfernen — einmal hinzugefügt, bleibt ein Element für immer drin.

Nimm es für:

  • Beobachtete Event-Typen, die das System je gesehen hat.
  • User, die sich je eingeloggt haben (ein unique-users-ever-Set).
  • Tags, die auf eine Ressource angewendet und nicht wieder entfernt werden.

Wenn du Removes brauchst, ist GSet die falsche Form; greif zu ORSet.

let s = GSet.empty<UserSession>({ identity: (u) => u.id });
s = s.add({ id: 'user-42', name: 'Alice' });
s = s.add({ id: 'user-42', name: 'Alice updated' });
s.value().length; // → 1 (gleiche Identität)

Standardmäßig werden Elemente per JSON.stringify(element) dedupliziert. Übergib eine identity: (e) => string-Funktion für eigene Dedup-Logik — nützlich, wenn Elemente Objekte mit stabilen IDs, aber veränderlichen anderen Feldern sind.

import { ORSet } from 'actor-ts/crdt';
let s = ORSet.empty<string>();
s = s.add('node-a', 'apple');
s = s.add('node-b', 'banana');
s = s.remove('apple');
s.value(); // → ['banana']

Der Trick: jedes add stempelt das Element mit einem eindeutigen Tag; remove(e) entfernt nur die Tags, die für die entfernende Replika gerade sichtbar sind.

Damit löst sich der Fall “nebenläufig Add + Remove” zugunsten des Add auf:

let a0 = ORSet.empty<string>().add('a', 'apple');
let b0 = a0; // beide sehen 'apple' mit demselben Tag
let a1 = a0.remove('apple'); // A entfernt
let b1 = b0.add('b', 'apple'); // B fügt ein NEUES 'apple' hinzu (neuer Tag)
a1.merge(b1).value(); // → ['apple'] — Bs Add überlebt

Das ursprüngliche ‘apple’ hatte den Tag, den B nie sah, also führt Bs frisches Add einen neuen Tag ein. Beim Merge von A und B entfernte As Remove nur den ursprünglichen Tag; Bs Tag bleibt. Nettoergebnis: ‘apple’ ist im Set.

Diese “Add wins”-Semantik macht ORSet zur richtigen Wahl für Shopping-Carts, Presence-Sets, Subscription-Listen — Sets, in denen ein kurzzeitig von einer Partei entferntes Item nicht verschwinden sollte, wenn eine andere Partei es nebenläufig wieder hinzufügt.

Tags sind replicaId × 96 Zufallsbits, gezogen aus der kryptografischen Zufallsquelle der Plattform. Das macht sie eindeutig selbst innerhalb derselben Millisekunde und über den ganzen Cluster — und im Gegensatz zum abgelösten Per-Replika-Zähler lassen sie sich nicht im Voraus berechnen.

Diese zweite Eigenschaft ist eine Frage der Korrektheit, nicht nur der Härtung. Tombstones vetoen beim Merge anhand des Tags und werden nie aufgeräumt. Ein Peer, der die nächsten Tags einer Replika vorhersagen könnte, könnte sie also vorab tombstonen — die nächsten Writes dieser Replika verschwänden dann beim folgenden Merge, lautlos und ohne API, mit der sich ein Tombstone zurücknehmen ließe.

Du siehst und manipulierst Tags nicht direkt; sie sind intern.

const s = ORSet.empty<CartItem>({ identity: (i) => i.sku });
s.add('node-a', { sku: 'book-1', price: 10 });
s.add('node-b', { sku: 'book-1', price: 12 });
// → trotzdem ein Eintrag (gleiche SKU), aber zwei Tags
// — die Tags sind unabhängig von der Identität des Werts

Die Identity-Funktion bestimmt die Deduplikation; die Tag-Mechanik arbeitet pro Add unabhängig davon.

Eine Identity-Funktion ist ein Closure und reist deshalb nie über die Leitung. Eine Replika, die einen Key aus dem Gossip eines Peers, aus einer Quorum-Antwort oder aus ihrem Durable-Record materialisiert, muss also gesagt bekommen, welche sie nehmen soll — und der einzige Ort, an dem dieses Wissen liegt, ist die factory, die du update ohnehin schon übergibst:

const emptyCart = () => ORSet.empty<CartItem>({ identity: (i) => i.sku });
dd.update('cart-42', emptyCart, (c) => c.add(dd.selfReplicaId(), item));

Übergib dieselbe Factory bei jedem update für einen Key, und die Replika legt jeden Wert, den sie für diesen Key dekodiert, unter deiner Identität ab — einschließlich Einträgen, die ein Peer unter der Standard-Identität geschrieben hat. Die werden umgeschlüsselt und in den Eintrag gemergt, zu dem sie gehören, statt als Duplikate daneben stehen zu bleiben: jedenfalls jedes Element, das dein Callback benennen kann. Was mit einem passiert, das er nicht benennen kann, steht in der letzten Notiz weiter unten.

Zwei Grenzen sind es wert, bekannt zu sein (#766):

  • Das erste update für einen Key ist das, was sie beibringt. Ein Key, der per Gossip ankam oder nach einem Neustart aus einem durableStore zurückkam, bleibt bis dahin auf der Standard-Identität — ein blankes dd.get('cart-42') direkt nach dem Start kann dir also ein Set liefern, das per JSON.stringify dedupliziert. Setz das update vorher ab, wenn das eine Rolle spielt.
  • Verschachtelung endet nach einer Ebene (#1421). Eine ORMap stellt ihre eigene Key-Identität wieder her, die CRDTs in ihr aber nicht: weder der Frame noch ein leeres Template sagt, welche ihre sein soll — eine ORMap von Warenkörben stellt also den Tenant-Key wieder her und lässt jeden Warenkorb per JSON.stringify deduplizieren. Die äußere Funktion an das innere Set weiterzureichen ist nicht die fehlende Hälfte und wäre schlimmer als die Lücke — sie schlüsselt jedes Item nach einem Feld, das Items nicht haben, und klappt einen ganzen Warenkorb auf einen Eintrag zusammen —, deshalb ist die Grenze festgehalten statt geraten.

Beachte außerdem: deine Identity-Funktion läuft jetzt auch über Werte, die ein Peer geschickt hat, nicht nur über solche, die dein Prozess gebaut hat. Ein Callback, der die Form seines Arguments voraussetzt, sieht Daten, die er nicht erzeugt hat — und was eine Verweigerung kostet, hängt davon ab, wann das Element hineingekommen ist:

  • Ein Frame, der ankommt, wenn die Identität bereits bekannt ist, wird verworfen. Wirft der Callback bei irgendeinem Element darin, ist der ganze Wert nicht dekodierbar, und jede Wire-Aufrufstelle behandelt das als „diesen einen verwerfen“ — der Sender bietet ihn beim nächsten Gossip-Tick erneut an, es geht also nichts verloren, was je akzeptiert war.
  • Ein Element, das schon in der View liegt, behält den Key, unter dem es hereinkam. Ein Wert, der per Gossip ankam oder aus einem durableStore zurückgelesen wurde, bevor das erste update lief, wurde auf der Standard-Identität dekodiert und kann deshalb bereits ein Element enthalten, das dein Callback verweigert. Das Umschlüsseln beim ersten update schlüsselt dann jedes Element um, das der Callback benennen kann, und lässt das verweigerte genau dort, wo es ist. Das Element wird nicht verworfen, der Key verliert seine Identität nicht, und spätere updates deduplizieren wie gewohnt nach deiner Regel; die Replika loggt eine Warnung, die den Key nennt. Der einzige sichtbare Effekt ist, dass das Set gemischt geschlüsselt ist, bis dieses Element verschwindet — was, da remove es mit demselben Callback benennen müsste, der es verweigert, heißt: solange der Key lebt.
FrageTyp
Brauchst du jemals Removes?ORSet
SonstGSet

GSet ist kleiner (keine Tag-Buchhaltung) und einfacher. Nimm es, wenn “Item entfernen” nicht Teil des Workflows ist.

Die zusätzlichen Kosten von ORSet sind das Tag-Tracking — für Sets mit hoher Churn (häufige Add/Remove-Zyklen auf demselben Element) wächst der interne State. Siehe “Wann ORSet nicht passt” unten.

  • Counter — für additive Counts.
  • Register — für Einzelwert-Writes.
  • Maps — für keyed Assoziationen inklusive ORMap.
  • Daten gestalten — der konzeptionelle Leitfaden.

Die API-Referenzen GSet und ORSet decken die vollständige Oberfläche ab.