Class ORSet<E>

java.lang.Object
com.loomcache.server.datastructures.crdt.ORSet<E>
public class ORSet<E> extends Object
Observed-Remove Set CRDT (OR-Set).

An OR-Set is a state-based CRDT that represents a set where elements can be added and removed concurrently. In case of concurrent add/remove, the add wins. This is implemented using unique tags for each add operation. When removing, all currently visible tags are marked for removal.

Key properties:

  • Each add operation receives a unique identifier (UUID tag)
  • Remove removes all known tags for an element
  • Concurrent add/remove: add wins (element stays if new add after remove)
  • Merge: union of all elements and their tags
  • lookup(x): x is in the set if it has at least one tag
  • Convergent: all nodes reach the same state given the same history
Since:
1.3

  • Constructor Details

    • ORSet

      public ORSet(String name, String nodeId, int instanceNumber)

  • Method Details

    • add

      public void add(E element)
      Add an element to the set. Each add operation receives a unique UUID tag.
      Parameters:
      element - the element to add
      Throws:
      NullPointerException - if element is null

    • remove

      public void remove(E element)
      Remove an element from the set. This removes all currently visible tags for the element. If the element is added again after this removal, it will reappear.
      Parameters:
      element - the element to remove
      Throws:
      NullPointerException - if element is null

    • contains

      public boolean contains(E element)
      Check if an element is in the set. An element is in the set if it has at least one tag.
      Parameters:
      element - the element to check
      Returns:
      true if the element is in the set

    • size

      public int size()
      Get the number of elements currently in the set.
      Returns:
      the set size

    • elements

      public Set<E> elements()
      Get an immutable copy of all elements currently in the set. Only elements with at least one tag are included.
      Returns:
      a snapshot of the current set

    • toSnapshot

      public HashMap<String,Object> toSnapshot()
      Export the full OR-Set state for Raft snapshots.

      Visible members are not enough for safe recovery: the add tags and removed-tag tombstones are the CRDT state. Dropping tombstones lets stale replicas resurrect elements during the next merge.

    • restoreFromSnapshot

      public void restoreFromSnapshot(Map<?,?> snapshot)
      Restore full OR-Set state captured by toSnapshot().

    • isEmpty

      public boolean isEmpty()
      Check if the set is empty.
      Returns:
      true if no elements are in the set

    • merge

      public void merge(ORSet<E> other)
      Merge another OR-Set into this one (anti-entropy). Merge operation is a union of all elements and their tags. If an element exists in both sets, tags are merged (union). Merge is idempotent and commutative.
      Parameters:
      other - the other OR-Set to merge
      Throws:
      IllegalArgumentException - if names don't match

    • reset

      public void reset()
      Reset is NOT supported for OR-Sets. Clearing elements and tombstones is non-monotonic: a stale replica can replay pre-reset add tags, and previously removed elements can resurrect because the tombstones were erased.
      Throws:
      UnsupportedOperationException - always — reset violates CRDT merge invariants

    • compactTombstones

      public int compactTombstones()
      Compact tombstones once removal metadata is causally stable across replicas.

      Until replica progress vectors are tracked, compaction is intentionally disabled to avoid resurrecting removed elements during stale-replica merges. Safe to call concurrently — acquires the lock.

      Returns:
      the number of tombstone tags removed

    • getTombstoneCount

      public int getTombstoneCount()
      Get the number of tombstone entries (for diagnostics/monitoring).
      Returns:
      the number of elements with tombstone entries

    • getTagCount

      public int getTagCount(E element)
      Get the number of tags for an element (for diagnostics).
      Parameters:
      element - the element to check
      Returns:
      the number of tags for that element