Перейти к содержимому
Русский

Sets (GSet, ORSet)

Это содержимое пока не доступно на вашем языке.

Two set CRDTs:

TypeOperationsWhen
GSet<E>add onlyAppend-only collections — observed kinds, seen users.
ORSet<E>add + removeMembership sets that come and go.

Both converge under concurrent writes; ORSet’s special trick is resolving “concurrent add and remove of the same element” so removes don’t accidentally delete a still-wanted item.

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

State is a plain set; merge is a union. Cannot remove — once added, an element stays forever.

Use for:

  • Observed event types the system has ever seen.
  • Users that ever logged in (a unique-users-ever set).
  • Tags applied to a resource that don’t get untagged.

If you need removals, GSet is the wrong shape; reach for 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 (same identity)

By default elements are deduplicated by JSON.stringify(element). Pass an identity: (e) => string function for custom dedup — useful when elements are objects with stable IDs but mutable other fields.

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']

The trick: every add stamps the element with a unique tag; remove(e) removes only the tags currently visible to the removing replica.

This makes the “concurrent add + remove” case resolve toward add:

let a0 = ORSet.empty<string>().add('a', 'apple');
let b0 = a0; // both see 'apple' with same tag
let a1 = a0.remove('apple'); // A removes
let b1 = b0.add('b', 'apple'); // B adds a NEW 'apple' (new tag)
a1.merge(b1).value(); // → ['apple'] — B's add survives

The original ‘apple’ had the tag B never saw, so B’s fresh add introduces a new tag. When A and B merge, A’s remove only removed the original tag; B’s tag remains. Net result: ‘apple’ is in the set.

This “add wins” semantics is what makes ORSet the right choice for shopping carts, presence sets, subscription lists — sets where an item briefly removed by one party shouldn’t disappear if another party concurrently re-added it.

Tags are replicaId × 96 random bits, drawn from the platform’s cryptographic random source. That makes them unique even within the same millisecond, across the cluster — and, unlike the per-replica counter they replaced, impossible to compute ahead of being issued.

That second property is a correctness matter, not just a hardening one. Tombstones veto by tag on merge and are never pruned, so a peer able to predict a replica’s next tags could tombstone them in advance and make that replica’s next writes disappear on the following merge — silently, and with no API to take a tombstone back.

You don’t see or manipulate tags directly; they’re internal.

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 });
// → still one entry (same SKU), but two tags
// — the tags are independent of the value's identity

The identity function determines deduplication; the tag mechanics work per-add regardless.

An identity function is a closure, so it never travels on the wire. A replica that materialises a key from a peer’s gossip, from a quorum reply or from its durable record therefore has to be told which one to use — and the only place that knowledge lives is the factory you already hand to update:

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

Pass the same factory on every update for a key, and the replica files every value it decodes for that key under your identity — entries a peer wrote under the default one included. Those are re-keyed and merged into the entry they belong with, rather than kept alongside it as duplicates: every element your callback can name, at any rate. What happens to one it cannot is the last note below.

Two limits are worth knowing (#766):

  • The first update for a key is what teaches it. A key that arrived by gossip, or came back from a durableStore after a restart, stays on the default identity until then — so a bare dd.get('cart-42') immediately after startup can hand you a set that deduplicates by JSON.stringify. Issue the update first if that matters.
  • Nesting stops at one level (#1421). An ORMap recovers its own key identity, but the CRDTs stored inside it do not: neither the frame nor an empty template says what theirs should be, so an ORMap of carts recovers the tenant key and leaves every cart deduplicating by JSON.stringify. Handing the outer function to the inner set is not the missing half and would be worse than the gap — it keys each item by a field items do not have, collapsing a whole cart onto one entry — so the boundary is written down rather than guessed at.

Note also that your identity function now runs over values a peer sent, not only over ones your process built. A callback that assumes its argument’s shape will see data it did not produce, and what a refusal costs depends on when the element got in:

  • A frame that arrives once the identity is known is dropped. The callback throwing on any element in it makes the whole value undecodable, and every wire call site treats that as “drop this one” — the sender re-offers it on its next gossip tick, so nothing that was ever accepted is lost.
  • An element already in the view keeps the key it came in under. A value gossiped, or read back from a durableStore, before the first update was decoded on the default identity, so it can already hold an element your callback refuses. Re-keying it on that first update then re-keys every element the callback can name and leaves the refused one exactly where it is. The element is not dropped, the key does not lose its identity, and later updates deduplicate by your rule as normal; the replica logs a warning naming the key. The one visible effect is that the set is mixed-keyed until that element goes away — which, since remove would have to name it with the same callback that refuses it, means for as long as the key lives.
QuestionType
Do you ever need to remove elements?ORSet
OtherwiseGSet

GSet is smaller (no tag bookkeeping) and simpler. Use when “remove an item” isn’t part of the workflow.

ORSet’s extra cost is the tag tracking — for sets with high churn (frequent add/remove cycles on the same element), the internal state grows. See “When ORSet isn’t right” below.

The GSet and ORSet API references cover the full surface.