public final class ORSet<A> extends java.lang.Object implements OpCrdt<ORSet.DeltaOp>, scala.Serializable
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.
| Modifier and Type | Class and Description |
|---|---|
static class |
ORSet.AddDeltaOp<A>
INTERNAL API
|
static class |
ORSet.AddDeltaOp$ |
static class |
ORSet.AtomicDeltaOp<A>
INTERNAL API
|
static class |
ORSet.DeltaGroup<A>
INTERNAL API
|
static class |
ORSet.DeltaGroup$ |
static interface |
ORSet.DeltaOp |
static class |
ORSet.FullStateDeltaOp<A>
INTERNAL API: Used for `clear` but could be used for other cases also
|
static class |
ORSet.FullStateDeltaOp$ |
static class |
ORSet.RemoveDeltaOp<A>
INTERNAL API
|
static class |
ORSet.RemoveDeltaOp$ |
| Constructor and Description |
|---|
ORSet(java.lang.String originDc,
scala.collection.immutable.Map<A,VersionVector> elementsMap,
VersionVector vvector) |
| Modifier and Type | Method and Description |
|---|---|
ORSet.DeltaOp |
$minus(A element)
Removes an element from the set.
|
ORSet.DeltaOp |
$plus(A element)
Adds an element to the set
|
ORSet.DeltaOp |
add(A element)
Adds an element to the set
|
ORSet.DeltaOp |
addAll(java.util.Set<A> elems)
Java API: Add several elements to the set.
|
ORSet.DeltaOp |
addAll(scala.collection.immutable.Set<A> elems)
Scala API: Add several elements to the set.
|
static <A> ORSet<A> |
apply(java.lang.String originDc) |
ORSet<A> |
applyOperation(ORSet.DeltaOp thatDelta) |
ORSet.DeltaOp |
clear()
Removes all elements from the set, but keeps the history.
|
boolean |
contains(A a) |
static <A> ORSet<A> |
create(java.lang.String originDc)
Java API
|
scala.collection.immutable.Set<A> |
elements()
Scala API
|
scala.collection.immutable.Map<A,VersionVector> |
elementsMap() |
static <A> ORSet<A> |
empty(java.lang.String originDc) |
boolean |
equals(java.lang.Object o) |
java.util.Set<A> |
getElements()
Java API
|
int |
hashCode() |
boolean |
isEmpty() |
static <A> scala.collection.immutable.Map<A,VersionVector> |
mergeCommonKeys(scala.collection.immutable.Set<A> commonKeys,
ORSet<A> lhs,
ORSet<A> rhs)
INTERNAL API
|
static <A> scala.collection.immutable.Map<A,VersionVector> |
mergeDisjointKeys(scala.collection.immutable.Set<A> keys,
scala.collection.immutable.Map<A,VersionVector> elementsMap,
VersionVector vvector,
scala.collection.immutable.Map<A,VersionVector> accumulator)
INTERNAL API
|
java.lang.String |
originDc() |
ORSet.DeltaOp |
remove(A element)
Removes an element from the set.
|
ORSet.DeltaOp |
removeAll(java.util.Set<A> elems)
Java API: Remove several elements from the set.
|
ORSet.DeltaOp |
removeAll(scala.collection.immutable.Set<A> elems)
Scala API: Remove several elements from the set.
|
int |
size() |
static VersionVector |
subtractDots(VersionVector dot,
VersionVector vvector)
INTERNAL API
Subtract the
vvector from the dot. |
java.lang.String |
toString() |
static <A> scala.Option<scala.collection.immutable.Set<A>> |
unapply(ORSet<A> s)
Extract the
elements(). |
VersionVector |
vvector() |
public ORSet(java.lang.String originDc,
scala.collection.immutable.Map<A,VersionVector> elementsMap,
VersionVector vvector)
public static <A> ORSet<A> empty(java.lang.String originDc)
public static <A> ORSet<A> apply(java.lang.String originDc)
public static <A> ORSet<A> create(java.lang.String originDc)
originDc - (undocumented)public static <A> scala.Option<scala.collection.immutable.Set<A>> unapply(ORSet<A> s)
elements().s - (undocumented)public static VersionVector subtractDots(VersionVector dot, VersionVector vvector)
vvector from the dot.
What this means is that any (dc, version) pair in
dot that is <= an entry in vvector is removed from dot.
Example [{a, 3}, {b, 2}, {d, 14}, {g, 22}] -
[{a, 4}, {b, 1}, {c, 1}, {d, 14}, {e, 5}, {f, 2}] =
[{b, 2}, {g, 22}]dot - (undocumented)vvector - (undocumented)public static <A> scala.collection.immutable.Map<A,VersionVector> mergeCommonKeys(scala.collection.immutable.Set<A> commonKeys, ORSet<A> lhs, ORSet<A> rhs)
commonKeys - (undocumented)lhs - (undocumented)rhs - (undocumented)ORSet#mergepublic static <A> scala.collection.immutable.Map<A,VersionVector> mergeDisjointKeys(scala.collection.immutable.Set<A> keys, scala.collection.immutable.Map<A,VersionVector> elementsMap, VersionVector vvector, scala.collection.immutable.Map<A,VersionVector> accumulator)
keys - (undocumented)elementsMap - (undocumented)vvector - (undocumented)accumulator - (undocumented)ORSet#mergepublic java.lang.String originDc()
public scala.collection.immutable.Map<A,VersionVector> elementsMap()
public VersionVector vvector()
public scala.collection.immutable.Set<A> elements()
public java.util.Set<A> getElements()
public boolean contains(A a)
public boolean isEmpty()
public int size()
public ORSet.DeltaOp $plus(A element)
element - (undocumented)public ORSet.DeltaOp add(A element)
element - (undocumented)public ORSet.DeltaOp addAll(java.util.Set<A> elems)
elems must not be empty.elems - (undocumented)public ORSet.DeltaOp addAll(scala.collection.immutable.Set<A> elems)
elems must not be empty.elems - (undocumented)public ORSet.DeltaOp $minus(A element)
element - (undocumented)public ORSet.DeltaOp remove(A element)
element - (undocumented)public ORSet.DeltaOp removeAll(java.util.Set<A> elems)
elems must not be empty.elems - (undocumented)public ORSet.DeltaOp removeAll(scala.collection.immutable.Set<A> elems)
elems must not be empty.elems - (undocumented)public ORSet.DeltaOp clear()
remove(A) for each
element, but it is more efficient.public ORSet<A> applyOperation(ORSet.DeltaOp thatDelta)
applyOperation in interface OpCrdt<ORSet.DeltaOp>public java.lang.String toString()
toString in class java.lang.Objectpublic boolean equals(java.lang.Object o)
equals in class java.lang.Objectpublic int hashCode()
hashCode in class java.lang.Object