Table of Contents

RW-Set (Remove-Wins Observed-Remove Set)

tree.RwSet(key) -> RwSetAccessor, merge mode LatticeMergeMode.RwSet.

Semantics

An RW-Set is a set whose membership converges remove-wins: when a concurrent add and remove of the same element race, the remove wins and the element stays out. It is the set-granularity generalisation of the RW-Flag - an RW-Flag is a single-element RW-Set, exactly as an OR-Flag is to an OR-Set.

Each element carries three dot sets: add dots, remove dots, and observed-add tombstones that cancel removes. An element is a member only when it carries an add dot and no remove dot survives. A Remove that an add has not observed survives the merge and keeps the element out, so a revoke is never silently resurrected by a concurrent re-add.

Both Add and Remove take a replicaId (each side stamps its own dots). Use it for membership revocation lists and blocklists - any set where a removal must win the tie. When a concurrent add should instead win, reach for the add-wins OR-Set.

Behaviour

A concurrent RW-Set add and remove: remove wins. An order diagram shaped like a diamond, for the element user:88. At the bottom there are no dots, so user:88 is not a member. Cluster A adds it with dot A1, making it a member. Cluster B, at the same time, removes it with dot B1, having observed no add. Neither state is above the other. Merging keeps both dots, and because no add has observed and cancelled B1, user:88 is not a member at the join: remove wins.

Both clusters hold add A1 and remove B1, so user:88 is not a member. A surviving remove keeps the element out: remove-wins.

An element is a member only while it has an add dot and no remove dot survives, so the remove wins the race.

sequenceDiagram
    participant A as Cluster A
    participant B as Cluster B
    A->>A: Add("user:88", dot A1)
    B->>B: Remove("user:88", dot B1, observed: none)
    A-->>B: merge ships add A1
    B-->>A: merge ships remove B1
    Note over A,B: B1 was not observed by the add
    Note over A,B: converged = NOT a member (remove-wins)

Example

var members = tree.RwSet("tenant:7:members");

// Cluster A re-admits a user; cluster B concurrently revokes them.
await members.AddAsync(Encoding.UTF8.GetBytes("user:88"), "cluster-A", cancellationToken);
await members.RemoveAsync(Encoding.UTF8.GetBytes("user:88"), "cluster-B", cancellationToken);

// The revoke was not observed by the add, so it survives and the element
// converges OUT of the set - a revocation is never lost to a concurrent add.
bool stillMember = await members.ContainsAsync(Encoding.UTF8.GetBytes("user:88"), cancellationToken); // false

See also: its add-wins mirror OR-Set, the single-element RW-Flag, and the CRDT overview.