Packages

final class ORSet[A] extends OpCrdt[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 -> 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 -> 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.

Source
ORSet.scala
Linear Supertypes
OpCrdt[DeltaOp], AnyRef, Any
Type Hierarchy
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. ORSet
  2. OpCrdt
  3. AnyRef
  4. 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
  2. type T = ORSet[A]
    Definition Classes
    ORSet → OpCrdt

Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##: Int
    Definition Classes
    AnyRef → Any
  3. def +(element: A): DeltaOp

    Adds an element to the set

  4. def -(element: A): DeltaOp

    Removes an element from the set.

  5. 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()
  6. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  7. def add(element: A): DeltaOp

    Adds an element to the set

  8. def addAll(elems: Set[A]): DeltaOp

    Scala API: Add several elements to the set.

    Scala API: Add several elements to the set. elems must not be empty.

  9. def addAll(elems: Set[A]): DeltaOp

    Java API: Add several elements to the set.

    Java API: Add several elements to the set. elems must not be empty.

  10. def applyOperation(thatDelta: DeltaOp): ORSet[A]
    Definition Classes
    ORSet → OpCrdt
  11. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  12. def clear(): DeltaOp

    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 #remove for each element, but it is more efficient.

  13. def clone(): AnyRef
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.CloneNotSupportedException]) @HotSpotIntrinsicCandidate() @native()
  14. def contains(a: A): Boolean
  15. def elements: Set[A]

    Scala API

  16. 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
  17. 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
  18. 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
  19. 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
  20. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  21. def equals(o: Any): Boolean
    Definition Classes
    ORSet → AnyRef → Any
  22. final def getClass(): Class[_ <: AnyRef]
    Definition Classes
    AnyRef → Any
    Annotations
    @HotSpotIntrinsicCandidate() @native()
  23. def getElements(): Set[A]

    Java API

  24. def hashCode(): Int
    Definition Classes
    ORSet → AnyRef → Any
  25. def isEmpty: Boolean
  26. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  27. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  28. final def notify(): Unit
    Definition Classes
    AnyRef
    Annotations
    @HotSpotIntrinsicCandidate() @native()
  29. final def notifyAll(): Unit
    Definition Classes
    AnyRef
    Annotations
    @HotSpotIntrinsicCandidate() @native()
  30. val originReplica: String
  31. def remove(element: A): DeltaOp

    Removes an element from the set.

  32. def removeAll(elems: Set[A]): DeltaOp

    Scala API: Remove several elements from the set.

    Scala API: Remove several elements from the set. elems must not be empty.

  33. def removeAll(elems: Set[A]): DeltaOp

    Java API: Remove several elements from the set.

    Java API: Remove several elements from the set. elems must not be empty.

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

Shadowed Implicit Value Members

  1. 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.
    Shadowing
    This implicitly inherited member is shadowed by one or more members in this class.
    To access this member you can use a type ascription:
    (oRSet: any2stringadd[ORSet[A]]).+(other)
    Definition Classes
    any2stringadd

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 OpCrdt[DeltaOp]

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