Grove.Set.ORSet (Grove v0.1.1)

View Source

An Observed-Remove Set (OR-Set) CRDT, also known as Add-Wins Set (AWSet).

Unlike 2P-Set, elements can be removed and re-added. This is achieved by tagging each add operation with a unique identifier (actor + counter). Remove only removes the tags that were observed at removal time.

Semantics

  • Add-wins: Concurrent add and remove results in the element being present
  • Re-addition: Elements can be added again after removal
  • Unique tags: Each add creates a new tag {actor, counter}

Delta-State Support

This CRDT supports delta-state replication:

  • delta/1 - Returns accumulated changes since last reset
  • reset_delta/1 - Clears the delta buffer after synchronization

Example

iex> set = Grove.Set.ORSet.new(:node_a)
iex> set = Grove.Set.ORSet.add(set, "apple")
iex> set = Grove.Set.ORSet.remove(set, "apple")
iex> set = Grove.Set.ORSet.add(set, "apple")  # Can re-add!
iex> Grove.Set.ORSet.member?(set, "apple")
true

Summary

Types

actor()
t()
tag()

Functions

add(set, element)

Adds an element to the set.

delta(or_set)

Returns the accumulated delta since the last reset.

member?(or_set, element)

Checks if an element is in the set.

merge(set1, set2)

Merges two OR-Sets.

new(actor)

Creates a new OR-Set for the given actor.

remove(set, element)

Removes an element from the set.

reset_delta(set)

Resets the delta buffer after synchronization.

size(or_set)

Returns the number of elements in the set.

to_list(set)

Returns the elements as a list.

value(or_set)

Returns the current elements as a MapSet.

Types

actor()

@type actor() :: term()

t()

@type t() :: %Grove.Set.ORSet{
  actor: actor(),
  counter: non_neg_integer(),
  delta_buffer: t() | nil,
  entries: %{required(term()) => MapSet.t(tag())},
  tombstones: MapSet.t(tag())
}

tag()

@type tag() :: {actor(), non_neg_integer()}

Functions

add(set, element)

@spec add(t(), term()) :: t()

Adds an element to the set.

Creates a new unique tag for this add operation.

delta(or_set)

@spec delta(t()) :: t()

Returns the accumulated delta since the last reset.

member?(or_set, element)

@spec member?(t(), term()) :: boolean()

Checks if an element is in the set.

Returns true if the element has at least one tag.

merge(set1, set2)

@spec merge(t(), t()) :: t()

Merges two OR-Sets.

For each element, takes the union of all tags.

new(actor)

@spec new(actor()) :: t()

Creates a new OR-Set for the given actor.

remove(set, element)

@spec remove(t(), term()) :: t()

Removes an element from the set.

Only removes the tags currently observed for this element. Concurrent adds with new tags will still be present after merge. Generates a delta with tombstones for proper replication.

reset_delta(set)

@spec reset_delta(t()) :: t()

Resets the delta buffer after synchronization.

size(or_set)

@spec size(t()) :: non_neg_integer()

Returns the number of elements in the set.

to_list(set)

@spec to_list(t()) :: [term()]

Returns the elements as a list.

value(or_set)

@spec value(t()) :: MapSet.t()

Returns the current elements as a MapSet.