Grove.Set.DVVSet (Grove v0.1.1)

View Source

An optimized Observed-Remove Set using Dotted Version Vectors.

Unlike the standard OR-Set which creates a new tag per add operation (O(operations) metadata), DVVSet stores one dot per actor per element (O(replicas) metadata).

Metadata Comparison

Element "apple" added 100 times from 3 nodes:

  • Standard ORSet: 100 tags
  • DVVSet: 3 dots (~97% reduction!)

Semantics

  • Add-wins: Concurrent add and remove results in element present
  • Per-actor dots: Each actor has at most one dot per element
  • Causal context: Tracks which dots have been observed

Structure

  • actor: The local actor/replica ID
  • clock: %{actor => counter} - local logical clock
  • entries: %{element => %{actor => counter}} - dots per element
  • context: %{actor => counter} - observed events (for removes)

Example

iex> set = Grove.Set.DVVSet.new(:node_a)
iex> set = Grove.Set.DVVSet.add(set, "apple")
iex> Grove.Set.DVVSet.member?(set, "apple")
true

References

Based on "Scalable and Accurate Causality Tracking for Eventually Consistent Stores" and Riak's implementation.

Summary

Types

actor()
counter()
dot()
dots()
t()

Functions

add(set, element)

Adds an element to the set.

delta(dvv_set)

Returns the accumulated delta since the last reset.

gc_info(dvv_set)

Returns GC info about the set.

member?(dvv_set, element)

Checks if an element is in the set.

merge(set1, set2)

Merges two DVVSets.

new(actor)

Creates a new DVVSet for the given actor.

remove(set, element)

Removes an element from the set.

reset_delta(set)

Resets the delta buffer after synchronization.

size(set)

Returns the number of elements in the set.

to_list(set)

Returns the elements as a list.

value(dvv_set)

Returns the current elements as a MapSet.

Types

actor()

@type actor() :: term()

counter()

@type counter() :: non_neg_integer()

dot()

@type dot() :: {actor(), counter()}

dots()

@type dots() :: %{required(actor()) => counter()}

t()

@type t() :: %Grove.Set.DVVSet{
  actor: actor(),
  clock: %{required(actor()) => counter()},
  context: %{required(actor()) => counter()},
  delta_buffer: t() | nil,
  entries: %{required(term()) => dots()}
}

Functions

add(set, element)

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

Adds an element to the set.

Increments the local clock and adds a dot for this actor. If the element already has a dot for this actor, it's updated.

delta(dvv_set)

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

Returns the accumulated delta since the last reset.

gc_info(dvv_set)

@spec gc_info(t()) :: map()

Returns GC info about the set.

member?(dvv_set, element)

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

Checks if an element is in the set.

Returns true if the element has at least one dot that hasn't been dominated by the context.

merge(set1, set2)

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

Merges two DVVSets.

For each element:

  1. Take union of dots from both sets
  2. Remove dots that are dominated by either context
  3. Merge contexts

new(actor)

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

Creates a new DVVSet for the given actor.

remove(set, element)

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

Removes an element from the set.

Records all observed dots in the context and removes the element. Concurrent adds (dots not yet observed) will survive after merge. Generates a delta with the updated context for replication.

reset_delta(set)

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

Resets the delta buffer after synchronization.

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

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

Returns the current elements as a MapSet.