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
Akka.DistributedData.FastMerge<ORSet<T>>
ORSet<T>
Implements
Inherited Members
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

| Improve this Doc View Source

ORSet()

Declaration
public ORSet()
| Improve this Doc View Source

ORSet(ImmutableDictionary<T, VersionVector>, VersionVector)

Declaration
public ORSet(ImmutableDictionary<T, VersionVector> elementsMap, VersionVector versionVector)
Parameters
Type Name Description
System.Collections.Immutable.ImmutableDictionary<T, VersionVector> elementsMap
VersionVector versionVector

Fields

| Improve this Doc View Source

Empty

Declaration
public static readonly ORSet<T> Empty
Field Value
Type Description
ORSet<T>

Properties

| Improve this Doc View Source

Count

Declaration
public int Count { get; }
Property Value
Type Description
Int32
| Improve this Doc View Source

Delta

Declaration
public ORSet<T>.IDeltaOperation Delta { get; }
Property Value
Type Description
ORSet.IDeltaOperation<>
| Improve this Doc View Source

Elements

Declaration
public IImmutableSet<T> Elements { get; }
Property Value
Type Description
System.Collections.Immutable.IImmutableSet<T>
| Improve this Doc View Source

IsEmpty

Declaration
public bool IsEmpty { get; }
Property Value
Type Description
Boolean
| Improve this Doc View Source

ModifiedByNodes

Declaration
public ImmutableHashSet<UniqueAddress> ModifiedByNodes { get; }
Property Value
Type Description
System.Collections.Immutable.ImmutableHashSet<UniqueAddress>
| Improve this Doc View Source

SetType

Declaration
public Type SetType { get; }
Property Value
Type Description
Type

Methods

| Improve this Doc 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>
| Improve this Doc 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>
| Improve this Doc 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>
| Improve this Doc 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>
| Improve this Doc View Source

Contains(T)

Declaration
public bool Contains(T elem)
Parameters
Type Name Description
T elem
Returns
Type Description
Boolean
| Improve this Doc View Source

Equals(ORSet<T>)

Declaration
public bool Equals(ORSet<T> other)
Parameters
Type Name Description
ORSet<T> other
Returns
Type Description
Boolean
| Improve this Doc View Source

Equals(Object)

Declaration
public override bool Equals(object obj)
Parameters
Type Name Description
Object obj
Returns
Type Description
Boolean
Overrides
| Improve this Doc View Source

GetEnumerator()

Declaration
public IEnumerator<T> GetEnumerator()
Returns
Type Description
IEnumerator<T>
| Improve this Doc View Source

GetHashCode()

Declaration
public override int GetHashCode()
Returns
Type Description
Int32
Overrides
| Improve this Doc 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
Akka.DistributedData.FastMerge<Akka.DistributedData.ORSet<T>>.Merge(Akka.DistributedData.ORSet<T>)
| Improve this Doc View Source

MergeDelta(ORSet<T>.IDeltaOperation)

Declaration
public ORSet<T> MergeDelta(ORSet<T>.IDeltaOperation delta)
Parameters
Type Name Description
ORSet.IDeltaOperation<> delta
Returns
Type Description
ORSet<T>
| Improve this Doc View Source

NeedPruningFrom(UniqueAddress)

Declaration
public bool NeedPruningFrom(UniqueAddress removedNode)
Parameters
Type Name Description
UniqueAddress removedNode
Returns
Type Description
Boolean
| Improve this Doc View Source

Prune(UniqueAddress, UniqueAddress)

Declaration
public ORSet<T> Prune(UniqueAddress removedNode, UniqueAddress collapseInto)
Parameters
Type Name Description
UniqueAddress removedNode
UniqueAddress collapseInto
Returns
Type Description
ORSet<T>
| Improve this Doc View Source

PruningCleanup(UniqueAddress)

Declaration
public ORSet<T> PruningCleanup(UniqueAddress removedNode)
Parameters
Type Name Description
UniqueAddress removedNode
Returns
Type Description
ORSet<T>
| Improve this Doc 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>
| Improve this Doc 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>
| Improve this Doc View Source

ResetDelta()

Declaration
public ORSet<T> ResetDelta()
Returns
Type Description
ORSet<T>
| Improve this Doc View Source

ToString()

Declaration
public override string ToString()
Returns
Type Description
String
Overrides

Explicit Interface Implementations

| Improve this Doc View Source

IDeltaReplicatedData.Delta

Declaration
IReplicatedDelta IDeltaReplicatedData.Delta { get; }
Returns
Type Description
IReplicatedDelta
| Improve this Doc View Source

IDeltaReplicatedData.MergeDelta(IReplicatedDelta)

Declaration
IReplicatedData IDeltaReplicatedData.MergeDelta(IReplicatedDelta delta)
Parameters
Type Name Description
IReplicatedDelta delta
Returns
Type Description
IReplicatedData
| Improve this Doc View Source

IDeltaReplicatedData.ResetDelta()

Declaration
IReplicatedData IDeltaReplicatedData.ResetDelta()
Returns
Type Description
IReplicatedData
| Improve this Doc View Source

IRemovedNodePruning.Prune(UniqueAddress, UniqueAddress)

Declaration
IReplicatedData IRemovedNodePruning.Prune(UniqueAddress removedNode, UniqueAddress collapseInto)
Parameters
Type Name Description
UniqueAddress removedNode
UniqueAddress collapseInto
Returns
Type Description
IReplicatedData
| Improve this Doc View Source

IRemovedNodePruning.PruningCleanup(UniqueAddress)

Declaration
IReplicatedData IRemovedNodePruning.PruningCleanup(UniqueAddress removedNode)
Parameters
Type Name Description
UniqueAddress removedNode
Returns
Type Description
IReplicatedData
| Improve this Doc View Source

IEnumerable.GetEnumerator()

Declaration
IEnumerator IEnumerable.GetEnumerator()
Returns
Type Description
IEnumerator

Implements

Extension Methods