Sets (GSet, ORSet)
Este conteúdo não está disponível em sua língua ainda.
Two set CRDTs:
| Type | Operations | When |
|---|---|---|
GSet<E> | add only | Append-only collections — observed kinds, seen users. |
ORSet<E> | add + remove | Membership 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-everset). - Tags applied to a resource that don’t get untagged.
If you need removals, GSet is the wrong shape; reach for
ORSet.
Element identity
Section titled “Element identity”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.
ORSet (Observed-Remove Set)
Section titled “ORSet (Observed-Remove Set)”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 removeslet b1 = b0.add('b', 'apple'); // B adds a NEW 'apple' (new tag)
a1.merge(b1).value(); // → ['apple'] — B's add survivesThe 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.
Tag generation
Section titled “Tag generation”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.
Element identity (same as GSet)
Section titled “Element identity (same as GSet)”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 identityThe identity function determines deduplication; the tag mechanics work per-add regardless.
Identity inside DistributedData
Section titled “Identity inside DistributedData”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
updatefor a key is what teaches it. A key that arrived by gossip, or came back from adurableStoreafter a restart, stays on the default identity until then — so a baredd.get('cart-42')immediately after startup can hand you a set that deduplicates byJSON.stringify. Issue theupdatefirst if that matters. - Nesting stops at one level (#1421). An
ORMaprecovers 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 anORMapof carts recovers the tenant key and leaves every cart deduplicating byJSON.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 firstupdatewas decoded on the default identity, so it can already hold an element your callback refuses. Re-keying it on that firstupdatethen 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 laterupdates 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, sinceremovewould have to name it with the same callback that refuses it, means for as long as the key lives.
Picking between them
Section titled “Picking between them”| Question | Type |
|---|---|
| Do you ever need to remove elements? | ORSet |
| Otherwise | GSet |
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.
When ORSet isn’t right
Section titled “When ORSet isn’t right”Where to next
Section titled “Where to next”- Counters — for additive counts.
- Registers — for single-value writes.
- Maps — for keyed associations including ORMap.
- Designing data — the conceptual guide.
