Package org.apache.pekko.persistence.typed.crdt

Class ORSet<A>

java.lang.Object
org.apache.pekko.persistence.typed.crdt.ORSet<A>
All Implemented Interfaces:
OpCrdt<ORSet.DeltaOp>
public final class ORSet<A> extends Object implements OpCrdt<ORSet.DeltaOp>
Implements a 'Observed Remove Set' operation based CRDT, also called a 'OR-Set'. Elements can be added and removed any number of times. Concurrent add wins over remove.

It is not implemented as in the paper A comprehensive study of Convergent and Commutative Replicated Data Types. This is more space efficient and doesn't accumulate garbage for removed elements. It is described in the paper An optimized conflict-free replicated set The implementation is inspired by the Riak DT riak_dt_orswot.

The ORSet has a version vector that is incremented when an element is added to the set. The DC -&gt; count pair for that increment is stored against the element as its "birth dot". Every time the element is re-added to the set, its "birth dot" is updated to that of the DC -&gt; count version vector entry resulting from the add. When an element is removed, we simply drop it, no tombstones.

When an element exists in replica A and not replica B, is it because A added it and B has not yet seen that, or that B removed it and A has not yet seen that? In this implementation we compare the dot of the present element to the version vector in the Set it is absent from. If the element dot is not "seen" by the Set version vector, that means the other set has yet to see this add, and the item is in the merged Set. If the Set version vector dominates the dot, that means the other Set has removed this element already, and the item is not in the merged Set.

This class is immutable, i.e. "modifying" methods return a new instance.

  • Method Details

    • empty

      public static <A> ORSet<A> empty(ReplicaId originReplica)

    • apply

      public static <A> ORSet<A> apply(ReplicaId originReplica)

    • create

      public static <A> ORSet<A> create(ReplicaId originReplica)
      Java API

    • unapply

      public static <A> scala.Option<scala.collection.immutable.Set<A>> unapply(ORSet<A> s)
      Extract the elements().

    • originReplica

      public String originReplica()

    • elements

      public scala.collection.immutable.Set<A> elements()
      Scala API

    • getElements

      public Set<A> getElements()
      Java API

    • contains

      public boolean contains(A a)

    • isEmpty

      public boolean isEmpty()

    • size

      public int size()

    • $plus

      public ORSet.DeltaOp $plus(A element)
      Adds an element to the set

    • add

      public ORSet.DeltaOp add(A element)
      Adds an element to the set

    • addAll

      public ORSet.DeltaOp addAll(Set<A> elems)
      Java API: Add several elements to the set. elems must not be empty.

    • addAll

      public ORSet.DeltaOp addAll(scala.collection.immutable.Set<A> elems)
      Scala API: Add several elements to the set. elems must not be empty.

    • $minus

      public ORSet.DeltaOp $minus(A element)
      Removes an element from the set.

    • remove

      public ORSet.DeltaOp remove(A element)
      Removes an element from the set.

    • removeAll

      public ORSet.DeltaOp removeAll(Set<A> elems)
      Java API: Remove several elements from the set. elems must not be empty.

    • removeAll

      public ORSet.DeltaOp removeAll(scala.collection.immutable.Set<A> elems)
      Scala API: Remove several elements from the set. elems must not be empty.

    • clear

      public ORSet.DeltaOp clear()
      Removes all elements from the set, but keeps the history. This has the same result as using remove(A) for each element, but it is more efficient.

    • applyOperation

      public ORSet<A> applyOperation(ORSet.DeltaOp thatDelta)
      Specified by:
      applyOperation in interface OpCrdt<A>

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • equals

      public boolean equals(Object o)
      Overrides:
      equals in class Object

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object