akka.persistence.multidc.crdt

Class ORSet<A>

java.lang.Object

akka.persistence.multidc.crdt.ORSet<A>

All Implemented Interfaces:

OpCrdt<ORSet.DeltaOp>, java.io.Serializable

public final class ORSet<A>
extends java.lang.Object
implements OpCrdt<ORSet.DeltaOp>, scala.Serializable

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.

See Also:

Serialized Form

Nested Class Summary

Nested Classes

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 Summary

Constructors

Constructor and Description
ORSet(java.lang.String originDc, scala.collection.immutable.Map<A,VersionVector> elementsMap, VersionVector vvector)

Method Summary

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()

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

ORSet

public ORSet(java.lang.String originDc,
             scala.collection.immutable.Map<A,VersionVector> elementsMap,
             VersionVector vvector)

Method Detail

empty

public static <A> ORSet<A> empty(java.lang.String originDc)

apply

public static <A> ORSet<A> apply(java.lang.String originDc)

create

public static <A> ORSet<A> create(java.lang.String originDc)

Java API

Parameters:

originDc - (undocumented)

Returns:

(undocumented)

unapply

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

Extract the elements().

Parameters:

s - (undocumented)

Returns:

(undocumented)

subtractDots

public static VersionVector subtractDots(VersionVector dot,
                                         VersionVector vvector)

INTERNAL API Subtract the vvector from the dot. What this means is that any (dc, version) pair in dot that is &lt;= 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}]

Parameters:

dot - (undocumented)

vvector - (undocumented)

Returns:

(undocumented)

mergeCommonKeys

public static <A> scala.collection.immutable.Map<A,VersionVector> mergeCommonKeys(scala.collection.immutable.Set<A> commonKeys,
                                                                                  ORSet<A> lhs,
                                                                                  ORSet<A> rhs)

INTERNAL API

Parameters:

commonKeys - (undocumented)

lhs - (undocumented)

rhs - (undocumented)

Returns:

(undocumented)

See Also:

ORSet#merge

mergeDisjointKeys

public 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

Parameters:

keys - (undocumented)

elementsMap - (undocumented)

vvector - (undocumented)

accumulator - (undocumented)

Returns:

(undocumented)

See Also:

ORSet#merge

originDc

public java.lang.String originDc()

elementsMap

public scala.collection.immutable.Map<A,VersionVector> elementsMap()

vvector

public VersionVector vvector()

elements

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

Scala API

Returns:

(undocumented)

getElements

public java.util.Set<A> getElements()

Java API

Returns:

(undocumented)

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

Parameters:

element - (undocumented)

Returns:

(undocumented)

add

public ORSet.DeltaOp add(A element)

Adds an element to the set

Parameters:

element - (undocumented)

Returns:

(undocumented)

addAll

public ORSet.DeltaOp addAll(java.util.Set<A> elems)

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

Parameters:

elems - (undocumented)

Returns:

(undocumented)

addAll

public ORSet.DeltaOp addAll(scala.collection.immutable.Set<A> elems)

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

Parameters:

elems - (undocumented)

Returns:

(undocumented)

$minus

public ORSet.DeltaOp $minus(A element)

Removes an element from the set.

Parameters:

element - (undocumented)

Returns:

(undocumented)

remove

public ORSet.DeltaOp remove(A element)

Removes an element from the set.

Parameters:

element - (undocumented)

Returns:

(undocumented)

removeAll

public ORSet.DeltaOp removeAll(java.util.Set<A> elems)

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

Parameters:

elems - (undocumented)

Returns:

(undocumented)

removeAll

public ORSet.DeltaOp removeAll(scala.collection.immutable.Set<A> elems)

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

Parameters:

elems - (undocumented)

Returns:

(undocumented)

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.

Returns:

(undocumented)

applyOperation

public ORSet<A> applyOperation(ORSet.DeltaOp thatDelta)

Specified by:

applyOperation in interface OpCrdt<ORSet.DeltaOp>

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

equals

public boolean equals(java.lang.Object o)

Overrides:

equals in class java.lang.Object

hashCode

public int hashCode()

Overrides:

hashCode in class java.lang.Object