Class ORSet<T>

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.

Inheritance

object

FastMerge<ORSet<T>>

ORSet<T>

Implements

IReplicatedDataSerialization

IRemovedNodePruning<ORSet<T>>

IRemovedNodePruning

IEquatable<ORSet<T>>

IEnumerable<T>

IEnumerable

IDeltaReplicatedData<ORSet<T>, ORSet<T>.IDeltaOperation>

IDeltaReplicatedData

IReplicatedData<ORSet<T>>

IReplicatedData

Inherited Members

object.Equals(object, object)

object.GetType()

object.ReferenceEquals(object, object)

Namespace: Akka.DistributedData

Assembly: Akka.DistributedData.dll

Syntax

[Serializable]
public sealed class ORSet<T> : FastMerge<ORSet<T>>, IReplicatedDataSerialization, IRemovedNodePruning<ORSet<T>>, IRemovedNodePruning, IEquatable<ORSet<T>>, IEnumerable<T>, IEnumerable, IDeltaReplicatedData<ORSet<T>, ORSet<T>.IDeltaOperation>, IDeltaReplicatedData, IReplicatedData<ORSet<T>>, IReplicatedData

Type Parameters

Name	Description
T

Constructors

| Edit this page View Source

ORSet()

Declaration

public ORSet()

| Edit this page View Source

ORSet(ImmutableDictionary<T, VersionVector>, VersionVector)

Declaration

public ORSet(ImmutableDictionary<T, VersionVector> elementsMap, VersionVector versionVector)

Parameters

Type	Name	Description
ImmutableDictionary<T, VersionVector>	elementsMap
VersionVector	versionVector

Fields

| Edit this page View Source

Empty

Declaration

public static readonly ORSet<T> Empty

Field Value

Type	Description
ORSet<T>

Properties

| Edit this page View Source

Count

Declaration

public int Count { get; }

Property Value

Type	Description
int

| Edit this page View Source

Delta

The accumulated delta of mutator operations since previous ResetDelta(). When the Akka.DistributedData.Replicator invokes the modify function of the Update message and the user code is invoking one or more mutator operations the data is collecting the delta of the operations and makes it available for the Akka.DistributedData.Replicator with the Delta accessor. The modify function shall still return the full state in the same way as IReplicatedData<T> without support for deltas.

Declaration

public ORSet<T>.IDeltaOperation Delta { get; }

Property Value

Type	Description
ORSet<T>.IDeltaOperation

| Edit this page View Source

Elements

Declaration

public IImmutableSet<T> Elements { get; }

Property Value

Type	Description
IImmutableSet<T>

| Edit this page View Source

IsEmpty

Declaration

public bool IsEmpty { get; }

Property Value

Type	Description
bool

| Edit this page View Source

ModifiedByNodes

The nodes that have changed the state for this data and would need pruning when such node is no longer part of the cluster.

Declaration

public ImmutableHashSet<UniqueAddress> ModifiedByNodes { get; }

Property Value

Type	Description
ImmutableHashSet<UniqueAddress>

| Edit this page View Source

SetType

Declaration

public Type SetType { get; }

Property Value

Type	Description
Type

Methods

| Edit this page View Source

Add(Cluster, T)

Adds an element to the set

Declaration

public ORSet<T> Add(Cluster cluster, T element)

Parameters

Type	Name	Description
Cluster	cluster
T	element

Returns

Type	Description
ORSet<T>

| Edit this page View Source

Add(UniqueAddress, T)

Adds an element to the set

Declaration

public ORSet<T> Add(UniqueAddress node, T element)

Parameters

Type	Name	Description
UniqueAddress	node
T	element

Returns

Type	Description
ORSet<T>

| Edit this page View Source

Clear(Cluster)

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

Declaration

public ORSet<T> Clear(Cluster node)

Parameters

Type	Name	Description
Cluster	node

Returns

Type	Description
ORSet<T>

| Edit this page View Source

Clear(UniqueAddress)

Removes all elements from the set, but keeps the history. This has the same result as using Remove(UniqueAddress, T) for each element, but it is more efficient.

Declaration

public ORSet<T> Clear(UniqueAddress node)

Parameters

Type	Name	Description
UniqueAddress	node

Returns

Type	Description
ORSet<T>

| Edit this page View Source

Contains(T)

Declaration

public bool Contains(T elem)

Parameters

Type	Name	Description
T	elem

Returns

Type	Description
bool

| Edit this page View Source

Equals(ORSet<T>)

Declaration

public bool Equals(ORSet<T> other)

Parameters

Type	Name	Description
ORSet<T>	other

Returns

Type	Description
bool

| Edit this page View Source

Equals(object)

Declaration

public override bool Equals(object obj)

Parameters

Type	Name	Description
object	obj

Returns

Type	Description
bool

Overrides

object.Equals(object)

| Edit this page View Source

GetEnumerator()

Declaration

public IEnumerator<T> GetEnumerator()

Returns

Type	Description
IEnumerator<T>

| Edit this page View Source

GetHashCode()

Declaration

public override int GetHashCode()

Returns

Type	Description
int

Overrides

object.GetHashCode()

| Edit this page View Source

Merge(ORSet<T>)

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

Declaration

public override ORSet<T> Merge(ORSet<T> other)

Parameters

Type	Name	Description
ORSet<T>	other

Returns

Type	Description
ORSet<T>

Overrides

FastMerge<ORSet<T>>.Merge(ORSet<T>)

| Edit this page View Source

MergeDelta(IDeltaOperation)

When delta is merged into the full state this method is used. When the type ORSet<T>.IDeltaOperation of the delta is of the same type as the full state ORSet<T> this method can be implemented by delegating to Merge(T).

Declaration

public ORSet<T> MergeDelta(ORSet<T>.IDeltaOperation delta)

Parameters

Type	Name	Description
ORSet<T>.IDeltaOperation	delta

Returns

Type	Description
ORSet<T>

| Edit this page View Source

NeedPruningFrom(UniqueAddress)

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

Declaration

public bool NeedPruningFrom(UniqueAddress removedNode)

Parameters

Type	Name	Description
UniqueAddress	removedNode

Returns

Type	Description
bool

| Edit this page View Source

Prune(UniqueAddress, UniqueAddress)

When the removedNode node has been removed from the cluster the state changes from that node will be pruned by collapsing the data entries to another node.

Declaration

public ORSet<T> Prune(UniqueAddress removedNode, UniqueAddress collapseInto)

Parameters

Type	Name	Description
UniqueAddress	removedNode
UniqueAddress	collapseInto

Returns

Type	Description
ORSet<T>

| Edit this page View Source

PruningCleanup(UniqueAddress)

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

Declaration

public ORSet<T> PruningCleanup(UniqueAddress removedNode)

Parameters

Type	Name	Description
UniqueAddress	removedNode

Returns

Type	Description
ORSet<T>

| Edit this page View Source

Remove(Cluster, T)

Removes an element from the set.

Declaration

public ORSet<T> Remove(Cluster node, T element)

Parameters

Type	Name	Description
Cluster	node
T	element

Returns

Type	Description
ORSet<T>

| Edit this page View Source

Remove(UniqueAddress, T)

Removes an element from the set.

Declaration

public ORSet<T> Remove(UniqueAddress node, T element)

Parameters

Type	Name	Description
UniqueAddress	node
T	element

Returns

Type	Description
ORSet<T>

| Edit this page View Source

ResetDelta()

Reset collection of deltas from mutator operations. When the Akka.DistributedData.Replicator invokes the modify function of the Update message the delta is always "reset" and when the user code is invoking one or more mutator operations the data is collecting the delta of the operations and makes it available for the Akka.DistributedData.Replicator with the Delta accessor. When the Akka.DistributedData.Replicator has grabbed the Delta it will invoke this method to get a clean data instance without the delta.

Declaration

public ORSet<T> ResetDelta()

Returns

Type	Description
ORSet<T>

| Edit this page View Source

ToString()

Declaration

public override string ToString()

Returns

Type	Description
string