ORSet

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.

Annotations: @SerialVersionUID()

Linear Supertypes

Serializable, Serializable, OpCrdt[DeltaOp], AnyRef, Any

Type Hierarchy

Type Members

type D = DeltaOp
type T = ORSet[A]

Definition Classes
ORSet → OpCrdt

Value Members

final def !=(arg0: Any): Boolean

Definition Classes
AnyRef → Any
final def ##(): Int

Definition Classes
AnyRef → Any
def +(element: A): DeltaOp

Adds an element to the set
def -(element: A): DeltaOp

Removes an element from the set.
def ->[B](y: B): (ORSet[A], B)

Implicit information
This member is added by an implicit conversion from ORSet[A] to ArrowAssoc[ORSet[A]] performed by method ArrowAssoc in scala.Predef.
Definition Classes
ArrowAssoc
Annotations
@inline()
final def ==(arg0: Any): Boolean

Definition Classes
AnyRef → Any
def add(element: A): DeltaOp

Adds an element to the set
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.
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.
def applyOperation(thatDelta: DeltaOp): ORSet[A]

Definition Classes
ORSet → OpCrdt
final def asInstanceOf[T0]: T0

Definition Classes
Any
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.
def clone(): AnyRef

Attributes
protected[java.lang]
Definition Classes
AnyRef
Annotations
@throws( ... )
def contains(a: A): Boolean
def elements: Set[A]

Scala API
def ensuring(cond: (ORSet[A]) ⇒ Boolean, msg: ⇒ Any): ORSet[A]

Implicit information
This member is added by an implicit conversion from ORSet[A] to Ensuring[ORSet[A]] performed by method Ensuring in scala.Predef.
Definition Classes
Ensuring
def ensuring(cond: (ORSet[A]) ⇒ Boolean): ORSet[A]

Implicit information
This member is added by an implicit conversion from ORSet[A] to Ensuring[ORSet[A]] performed by method Ensuring in scala.Predef.
Definition Classes
Ensuring
def ensuring(cond: Boolean, msg: ⇒ Any): ORSet[A]

Implicit information
This member is added by an implicit conversion from ORSet[A] to Ensuring[ORSet[A]] performed by method Ensuring in scala.Predef.
Definition Classes
Ensuring
def ensuring(cond: Boolean): ORSet[A]

Implicit information
This member is added by an implicit conversion from ORSet[A] to Ensuring[ORSet[A]] performed by method Ensuring in scala.Predef.
Definition Classes
Ensuring
final def eq(arg0: AnyRef): Boolean

Definition Classes
AnyRef
def equals(o: Any): Boolean

Definition Classes
ORSet → AnyRef → Any
def finalize(): Unit

Attributes
protected[java.lang]
Definition Classes
AnyRef
Annotations
@throws( classOf[java.lang.Throwable] )
def formatted(fmtstr: String): String

Implicit information
This member is added by an implicit conversion from ORSet[A] to StringFormat[ORSet[A]] performed by method StringFormat in scala.Predef.
Definition Classes
StringFormat
Annotations
@inline()
final def getClass(): Class[_]

Definition Classes
AnyRef → Any
def getElements(): Set[A]

Java API
def hashCode(): Int

Definition Classes
ORSet → AnyRef → Any
def isEmpty: Boolean
final def isInstanceOf[T0]: Boolean

Definition Classes
Any
final def ne(arg0: AnyRef): Boolean

Definition Classes
AnyRef
final def notify(): Unit

Definition Classes
AnyRef
final def notifyAll(): Unit

Definition Classes
AnyRef
val originDc: DataCenter
def remove(element: A): DeltaOp

Removes an element from the set.
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.
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.
def size: Int
final def synchronized[T0](arg0: ⇒ T0): T0

Definition Classes
AnyRef
def toString(): String

Definition Classes
ORSet → AnyRef → Any
final def wait(): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )
final def wait(arg0: Long, arg1: Int): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )
final def wait(arg0: Long): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )
def →[B](y: B): (ORSet[A], B)

Implicit information
This member is added by an implicit conversion from ORSet[A] to ArrowAssoc[ORSet[A]] performed by method ArrowAssoc in scala.Predef.
Definition Classes
ArrowAssoc

Shadowed Implicit Value Members

def +(other: String): String
Implicit information
This member is added by an implicit conversion from ORSet[A] to any2stringadd[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

Related Docs: object ORSet | package crdt

final class ORSet[A] extends OpCrdt[DeltaOp] with Serializable

Type Members

type D = DeltaOp

type T = ORSet[A]

Value Members

final def !=(arg0: Any): Boolean

final def ##(): Int

def +(element: A): DeltaOp

def -(element: A): DeltaOp

def ->[B](y: B): (ORSet[A], B)

final def ==(arg0: Any): Boolean

def add(element: A): DeltaOp

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

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

def applyOperation(thatDelta: DeltaOp): ORSet[A]

final def asInstanceOf[T0]: T0

def clear(): DeltaOp

def clone(): AnyRef

def contains(a: A): Boolean

def elements: Set[A]

def ensuring(cond: (ORSet[A]) ⇒ Boolean, msg: ⇒ Any): ORSet[A]

def ensuring(cond: (ORSet[A]) ⇒ Boolean): ORSet[A]

def ensuring(cond: Boolean, msg: ⇒ Any): ORSet[A]

def ensuring(cond: Boolean): ORSet[A]

final def eq(arg0: AnyRef): Boolean

def equals(o: Any): Boolean

def finalize(): Unit

def formatted(fmtstr: String): String

final def getClass(): Class[_]

def getElements(): Set[A]

def hashCode(): Int

def isEmpty: Boolean

final def isInstanceOf[T0]: Boolean

final def ne(arg0: AnyRef): Boolean

final def notify(): Unit

final def notifyAll(): Unit

val originDc: DataCenter

def remove(element: A): DeltaOp

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

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

def size: Int

final def synchronized[T0](arg0: ⇒ T0): T0

def toString(): String

final def wait(): Unit

final def wait(arg0: Long, arg1: Int): Unit

final def wait(arg0: Long): Unit

def →[B](y: B): (ORSet[A], B)

Shadowed Implicit Value Members

def +(other: String): String

Inherited from Serializable

Inherited from Serializable

Inherited from OpCrdt[DeltaOp]

Inherited from AnyRef

Inherited from Any

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

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

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

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

Ungrouped