final class ORSet[A] extends DeltaReplicatedData with ReplicatedDataSerialization with RemovedNodePruning with FastMerge

Implements a 'Observed Remove Set' 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 node -> 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 node -> 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.

Annotations
@SerialVersionUID()
Source
ORSet.scala
Linear Supertypes
FastMerge, RemovedNodePruning, ReplicatedDataSerialization, Serializable, DeltaReplicatedData, ReplicatedData, AnyRef, Any
Type Hierarchy
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. ORSet
  2. FastMerge
  3. RemovedNodePruning
  4. ReplicatedDataSerialization
  5. Serializable
  6. DeltaReplicatedData
  7. ReplicatedData
  8. AnyRef
  9. Any
Implicitly
  1. by any2stringadd
  2. by StringFormat
  3. by Ensuring
  4. by ArrowAssoc
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. Protected

Type Members

  1. type D = DeltaOp

    The type of the delta.

    The type of the delta. To be specified by subclass. It may be the same type as T or a different type if needed. For example GSet uses the same type and ORSet uses different types.

    Definition Classes
    ORSet → DeltaReplicatedData
  2. type T = ORSet[A]

    The type of the concrete implementation, e.g.

    The type of the concrete implementation, e.g. GSet[A]. To be specified by subclass.

    Definition Classes
    ORSet → ReplicatedData

Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##: Int
    Definition Classes
    AnyRef → Any
  3. def +(other: String): String
    Implicit
    This member is added by an implicit conversion from ORSet[A] toany2stringadd[ORSet[A]] performed by method any2stringadd in scala.Predef.
    Definition Classes
    any2stringadd
  4. def ->[B](y: B): (ORSet[A], B)
    Implicit
    This member is added by an implicit conversion from ORSet[A] toArrowAssoc[ORSet[A]] performed by method ArrowAssoc in scala.Predef.
    Definition Classes
    ArrowAssoc
    Annotations
    @inline()
  5. def :+(element: A)(implicit node: SelfUniqueAddress): ORSet[A]

    Adds an element to the set.

  6. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  7. def add(node: SelfUniqueAddress, element: A): ORSet[A]

    Adds an element to the set.

  8. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  9. def clear(node: SelfUniqueAddress): ORSet[A]

    Removes all elements from the set, but keeps the history.

    Removes all elements from the set, but keeps the history. This has the same result as using ORSet#remove(node:akka\.cluster\.ddata\.SelfUniqueAddress* for each element, but it is more efficient.

  10. def clone(): AnyRef
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.CloneNotSupportedException]) @HotSpotIntrinsicCandidate() @native()
  11. def contains(a: A): Boolean
  12. val delta: Option[DeltaOp]

    The accumulated delta of mutator operations since previous #resetDelta.

    The accumulated delta of mutator operations since previous #resetDelta. When the Replicator invokes the modify function of the Update message and the user code is invoking one or more mutator operations the data is collecting the delta of the operations and makes it available for the Replicator with the #delta accessor. The modify function shall still return the full state in the same way as ReplicatedData without support for deltas.

    Definition Classes
    ORSet → DeltaReplicatedData
  13. def elements: Set[A]

    Scala API

  14. def ensuring(cond: (ORSet[A]) => Boolean, msg: => Any): ORSet[A]
    Implicit
    This member is added by an implicit conversion from ORSet[A] toEnsuring[ORSet[A]] performed by method Ensuring in scala.Predef.
    Definition Classes
    Ensuring
  15. def ensuring(cond: (ORSet[A]) => Boolean): ORSet[A]
    Implicit
    This member is added by an implicit conversion from ORSet[A] toEnsuring[ORSet[A]] performed by method Ensuring in scala.Predef.
    Definition Classes
    Ensuring
  16. def ensuring(cond: Boolean, msg: => Any): ORSet[A]
    Implicit
    This member is added by an implicit conversion from ORSet[A] toEnsuring[ORSet[A]] performed by method Ensuring in scala.Predef.
    Definition Classes
    Ensuring
  17. def ensuring(cond: Boolean): ORSet[A]
    Implicit
    This member is added by an implicit conversion from ORSet[A] toEnsuring[ORSet[A]] performed by method Ensuring in scala.Predef.
    Definition Classes
    Ensuring
  18. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  19. def equals(o: Any): Boolean
    Definition Classes
    ORSet → AnyRef → Any
  20. final def getClass(): Class[_ <: AnyRef]
    Definition Classes
    AnyRef → Any
    Annotations
    @HotSpotIntrinsicCandidate() @native()
  21. def getElements(): Set[A]

    Java API

  22. def hashCode(): Int
    Definition Classes
    ORSet → AnyRef → Any
  23. def isEmpty: Boolean
  24. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  25. def merge(that: ORSet[A]): ORSet[A]

    When element is in this Set but not in that Set: Compare the "birth dot" of the present element to the version vector in the Set it is absent from.

    When element is in this Set but not in that Set: Compare the "birth dot" of the present element to the version vector in the Set it is absent from. If the element dot is not "seen" by other Set version vector, that means the other set has yet to see this add, and the element is to be in the merged Set. If the other Set version vector dominates the dot, that means the other Set has removed the element already, and the element is not to be in the merged Set.

    When element in both this Set and in that Set: Some dots may still need to be shed. If this Set has dots that the other Set does not have, and the other Set version vector dominates those dots, then we need to drop those dots. Keep only common dots, and dots that are not dominated by the other sides version vector

    Definition Classes
    ORSet → ReplicatedData
  26. def mergeDelta(thatDelta: DeltaOp): ORSet[A]

    When delta is merged into the full state this method is used.

    When delta is merged into the full state this method is used. When the type D of the delta is of the same type as the full state T this method can be implemented by delegating to merge.

    Definition Classes
    ORSet → DeltaReplicatedData
  27. def modifiedByNodes: Set[UniqueAddress]

    The nodes that have changed the state for this data and would need pruning when such node is no longer part of the cluster.

    The nodes that have changed the state for this data and would need pruning when such node is no longer part of the cluster.

    Definition Classes
    ORSet → RemovedNodePruning
  28. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  29. def needPruningFrom(removedNode: UniqueAddress): Boolean

    Does it have any state changes from a specific node, which has been removed from the cluster.

    Does it have any state changes from a specific node, which has been removed from the cluster.

    Definition Classes
    ORSet → RemovedNodePruning
  30. final def notify(): Unit
    Definition Classes
    AnyRef
    Annotations
    @HotSpotIntrinsicCandidate() @native()
  31. final def notifyAll(): Unit
    Definition Classes
    AnyRef
    Annotations
    @HotSpotIntrinsicCandidate() @native()
  32. def prune(removedNode: UniqueAddress, collapseInto: UniqueAddress): ORSet[A]

    When the removed node has been removed from the cluster the state changes from that node will be pruned by collapsing the data entries to another node.

    When the removed node has been removed from the cluster the state changes from that node will be pruned by collapsing the data entries to another node.

    Definition Classes
    ORSet → RemovedNodePruning
  33. def pruningCleanup(removedNode: UniqueAddress): ORSet[A]

    Remove data entries from a node that has been removed from the cluster and already been pruned.

    Remove data entries from a node that has been removed from the cluster and already been pruned.

    Definition Classes
    ORSet → RemovedNodePruning
  34. def remove(node: SelfUniqueAddress, element: A): ORSet[A]

    Java API Removes an element from the set.

  35. def remove(element: A)(implicit node: SelfUniqueAddress): ORSet[A]

    Scala API Removes an element from the set.

  36. def resetDelta: ORSet[A]

    Reset collection of deltas from mutator operations.

    Reset collection of deltas from mutator operations. When the Replicator invokes the modify function of the Update message the delta is always "reset" and when the user code is invoking one or more mutator operations the data is collecting the delta of the operations and makes it available for the Replicator with the #delta accessor. When the Replicator has grabbed the delta it will invoke this method to get a clean data instance without the delta.

    Definition Classes
    ORSet → DeltaReplicatedData
  37. def size: Int
  38. final def synchronized[T0](arg0: => T0): T0
    Definition Classes
    AnyRef
  39. def toString(): String
    Definition Classes
    ORSet → AnyRef → Any
  40. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])
  41. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException]) @native()
  42. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])

Deprecated Value Members

  1. def finalize(): Unit
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.Throwable]) @Deprecated
    Deprecated

    (Since version 9)

  2. def formatted(fmtstr: String): String
    Implicit
    This member is added by an implicit conversion from ORSet[A] toStringFormat[ORSet[A]] performed by method StringFormat in scala.Predef.
    Definition Classes
    StringFormat
    Annotations
    @deprecated @inline()
    Deprecated

    (Since version 2.12.16) Use formatString.format(value) instead of value.formatted(formatString), or use the f"" string interpolator. In Java 15 and later, formatted resolves to the new method in String which has reversed parameters.

  3. def →[B](y: B): (ORSet[A], B)
    Implicit
    This member is added by an implicit conversion from ORSet[A] toArrowAssoc[ORSet[A]] performed by method ArrowAssoc in scala.Predef.
    Definition Classes
    ArrowAssoc
    Annotations
    @deprecated
    Deprecated

    (Since version 2.13.0) Use -> instead. If you still wish to display it as one character, consider using a font with programming ligatures such as Fira Code.

Inherited from FastMerge

Inherited from RemovedNodePruning

Inherited from ReplicatedDataSerialization

Inherited from Serializable

Inherited from DeltaReplicatedData

Inherited from ReplicatedData

Inherited from AnyRef

Inherited from Any

Inherited by implicit conversion any2stringadd fromORSet[A] to any2stringadd[ORSet[A]]

Inherited by implicit conversion StringFormat fromORSet[A] to StringFormat[ORSet[A]]

Inherited by implicit conversion Ensuring fromORSet[A] to Ensuring[ORSet[A]]

Inherited by implicit conversion ArrowAssoc fromORSet[A] to ArrowAssoc[ORSet[A]]

Ungrouped