akka.cluster.ddata

Class ORSet<A>

java.lang.Object

akka.cluster.ddata.ORSet<A>

All Implemented Interfaces:

FastMerge, RemovedNodePruning, ReplicatedData, ReplicatedDataSerialization, java.io.Serializable

public final class ORSet<A>
extends java.lang.Object
implements ReplicatedData, ReplicatedDataSerialization, RemovedNodePruning, 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.

See Also:

Serialized Form

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
ORSet<A>	add(Cluster node, A element) Adds an element to the set
ORSet<A>	add(UniqueAddress node, A element) INTERNAL API
static void	akka$cluster$ddata$FastMerge$$ancestor_$eq(FastMerge x$1)
static FastMerge	akka$cluster$ddata$FastMerge$$ancestor()
static ORSet<java.lang.Object>	apply()
static FastMerge	assignAncestor(akka.cluster.ddata.ReplicatedData.T newData)
ORSet<A>	clear(Cluster node) Removes all elements from the set, but keeps the history.
ORSet<A>	clear(UniqueAddress node) INTERNAL API
static FastMerge	clearAncestor()
boolean	contains(A a)
static <A> ORSet<A>	create() Java API
scala.collection.immutable.Set<A>	elements() Scala API
scala.collection.immutable.Map<A,VersionVector>	elementsMap()
static <A> ORSet<A>	empty()
boolean	equals(java.lang.Object o)
java.util.Set<A>	getElements() Java API
int	hashCode()
static boolean	isAncestorOf(akka.cluster.ddata.ReplicatedData.T that)
boolean	isEmpty()
ORSet<A>	merge(ORSet<A> that) 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.
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
boolean	needPruningFrom(UniqueAddress removedNode) Does it have any state changes from a specific node, which has been removed from the cluster.
ORSet<A>	prune(UniqueAddress removedNode, UniqueAddress collapseInto) 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.
ORSet<A>	pruningCleanup(UniqueAddress removedNode) Remove data entries from a node that has been removed from the cluster and already been pruned.
ORSet<A>	remove(Cluster node, A element) Removes an element from the set.
ORSet<A>	remove(UniqueAddress node, A element) INTERNAL API
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().
static scala.Option<scala.collection.immutable.Set<java.lang.Object>>	unapply(ReplicatedData a) Extract the elements() of an ORSet.
VersionVector	vvector()

Methods inherited from class java.lang.Object

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

Methods inherited from interface akka.cluster.ddata.ReplicatedData

merge

Methods inherited from interface akka.cluster.ddata.FastMerge

assignAncestor, clearAncestor, isAncestorOf

Constructor Detail

ORSet

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

Method Detail

empty

public static <A> ORSet<A> empty()

apply

public static ORSet<java.lang.Object> apply()

create

public static <A> ORSet<A> create()

Java API

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)

unapply

public static scala.Option<scala.collection.immutable.Set<java.lang.Object>> unapply(ReplicatedData a)

Extract the elements() of an ORSet.

Parameters:

a - (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 (node, 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:

merge(akka.cluster.ddata.ORSet<A>)

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:

merge(akka.cluster.ddata.ORSet<A>)

akka$cluster$ddata$FastMerge$$ancestor

public static FastMerge akka$cluster$ddata$FastMerge$$ancestor()

akka$cluster$ddata$FastMerge$$ancestor_$eq

public static void akka$cluster$ddata$FastMerge$$ancestor_$eq(FastMerge x$1)

assignAncestor

public static FastMerge assignAncestor(akka.cluster.ddata.ReplicatedData.T newData)

isAncestorOf

public static boolean isAncestorOf(akka.cluster.ddata.ReplicatedData.T that)

clearAncestor

public static FastMerge clearAncestor()

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

add

public ORSet<A> add(Cluster node,
                    A element)

Adds an element to the set

Parameters:

node - (undocumented)

element - (undocumented)

Returns:

(undocumented)

add

public ORSet<A> add(UniqueAddress node,
                    A element)

INTERNAL API

Parameters:

node - (undocumented)

element - (undocumented)

Returns:

(undocumented)

remove

public ORSet<A> remove(Cluster node,
                       A element)

Removes an element from the set.

Parameters:

node - (undocumented)

element - (undocumented)

Returns:

(undocumented)

remove

public ORSet<A> remove(UniqueAddress node,
                       A element)

INTERNAL API

Parameters:

node - (undocumented)

element - (undocumented)

Returns:

(undocumented)

clear

public ORSet<A> clear(Cluster node)

Removes all elements from the set, but keeps the history. This has the same result as using remove(akka.cluster.Cluster, A) for each element, but it is more efficient.

Parameters:

node - (undocumented)

Returns:

(undocumented)

clear

public ORSet<A> clear(UniqueAddress node)

INTERNAL API

Parameters:

node - (undocumented)

Returns:

(undocumented)

merge

public ORSet<A> merge(ORSet<A> that)

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

Parameters:

that - (undocumented)

Returns:

(undocumented)

needPruningFrom

public boolean needPruningFrom(UniqueAddress removedNode)

Description copied from interface: RemovedNodePruning

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

Specified by:

needPruningFrom in interface RemovedNodePruning

Parameters:

removedNode - (undocumented)

Returns:

(undocumented)

prune

public ORSet<A> prune(UniqueAddress removedNode,
                      UniqueAddress collapseInto)

Description copied from interface: RemovedNodePruning

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.

Specified by:

prune in interface RemovedNodePruning

Parameters:

removedNode - (undocumented)

collapseInto - (undocumented)

Returns:

(undocumented)

pruningCleanup

public ORSet<A> pruningCleanup(UniqueAddress removedNode)

Description copied from interface: RemovedNodePruning

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

Specified by:

pruningCleanup in interface RemovedNodePruning

Parameters:

removedNode - (undocumented)

Returns:

(undocumented)

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