datatypes.crdt

datatypes.crdt provides Conflict-free Replicated Data Types (CRDTs) for distributed and concurrent applications.

CRDTs are data structures that can be replicated across multiple nodes in a network, where replicas can be updated independently and concurrently without coordination, and always converge to the same state when merged.

Available Types

Counters

GCounter (Grow-only Counter)

A state-based counter that only increases monotonically. Merging takes the maximum counter value for each replica identity.

import datatypes.crdt

mut c1 := crdt.new_gcounter_with_id('node_a')
mut c2 := crdt.new_gcounter_with_id('node_b')

c1.increment()
c1.increment_value(5)
c2.increment_value(3)

c1.merge(&c2)
println(c1.value()) // 9

PNCounter (Positive-Negative Counter)

A counter that supports both increments and decrements by pairing two G-Counters: one for positive increments and one for negative decrements.

import datatypes.crdt

mut pn := crdt.new_pncounter()
pn.increment_value(10)
pn.decrement_value(4)
println(pn.value()) // 6

Sets

GSet[T] (Grow-only Set)

A set where elements can only be added, never removed. Merge is a set union.

import datatypes.crdt

mut s := crdt.new_gset[string]()
s.add('apple')
println(s.lookup('apple')) // true

TwoPhaseSet[T] (2P-Set)

A two-phase set allowing additions and removals. An element once removed can never be re-added.

import datatypes.crdt

mut tps := crdt.new_two_phase_set[string]()
tps.add('item')
tps.remove('item')
println(tps.lookup('item')) // false

LWWESet[T] (Last-Write-Wins Element Set)

An element set where each addition and removal is associated with a timestamp. Elements can be re-added and re-removed repeatedly. Timestamp ties are resolved by configurable bias (.add_wins or .remove_wins).

import datatypes.crdt

mut lww := crdt.new_lwweset[string]()
lww.add('doc')
lww.remove('doc')
lww.add('doc') // Re-added with a newer timestamp
println(lww.lookup('doc')) // true

ORSet[T] (Observed-Removed Set / Add-Wins Set)

An observed-removed set that uniquely tracks additions with internal tags. Removing an element only removes the tags observed so far at that replica. Concurrent additions and removals result in additions winning (Add-Wins).

import datatypes.crdt

mut orset := crdt.new_orset[string]()
orset.add('doc')
orset.remove('doc')
orset.add('doc') // Re-added with a fresh unique tag
println(orset.lookup('doc')) // true

fn new_gcounter() GCounter

new_gcounter creates a new GCounter with a randomly generated unique identity.

fn new_gcounter_with_id(id string) GCounter

new_gcounter_with_id creates a new GCounter with a specified replica identity.

fn new_gset[T]() GSet[T]

new_gset creates a new empty GSet.

fn new_lwweset[T]() LWWESet[T]

new_lwweset creates a new empty LWWESet with the default add-wins bias.

fn new_lwweset_with_bias[T](bias LWWBias) LWWESet[T]

new_lwweset_with_bias creates a new empty LWWESet with the specified bias.

fn new_orset[T]() ORSet[T]

new_orset creates a new empty ORSet.

fn new_pncounter() PNCounter

new_pncounter creates a new PNCounter with randomly generated identities.

fn new_pncounter_with_id(id string) PNCounter

new_pncounter_with_id creates a new PNCounter with the specified replica identity.

fn new_two_phase_set[T]() TwoPhaseSet[T]

new_two_phase_set creates a new empty TwoPhaseSet.

fn LWWBias.from[W](input W) !LWWBias

from returns the LWWBias value of an integer or of a field name, or an error if there is none.

fn (mut g GSet[T]) add(elem T)

add adds an element to the GSet.

fn (g &GSet[T]) lookup(elem T) bool

lookup returns true if the element exists in the set, false otherwise.

fn (g &GSet[T]) len() int

len returns the number of elements in the set.

fn (g &GSet[T]) elements() []T

elements returns an array of all elements present in the set.

fn (l GSet[T]) == (r GSet[T]) bool

== checks whether two GSets contain the exact same elements.

fn (mut g GSet[T]) merge(other &GSet[T])

merge combines elements from another GSet into this set via set union.

fn (mut s LWWESet[T]) add(elem T)

add adds an element to the set with the current UTC timestamp.

fn (mut s LWWESet[T]) add_with_time(elem T, ts i64)

add_with_time adds an element to the set with a specified timestamp in nanoseconds.

fn (mut s LWWESet[T]) remove(elem T)

remove marks an element as removed with the current UTC timestamp.

fn (mut s LWWESet[T]) remove_with_time(elem T, ts i64)

remove_with_time marks an element as removed with a specified timestamp in nanoseconds.

fn (s &LWWESet[T]) lookup(elem T) bool

lookup checks whether an element is currently a member of the set.

fn (s &LWWESet[T]) elements() []T

elements returns an array of all active elements currently belonging to the set.

fn (s &LWWESet[T]) len() int

len returns the count of active elements currently belonging to the set.

fn (l LWWESet[T]) == (r LWWESet[T]) bool

== checks whether two LWWESets have identical state and configuration.

fn (mut s LWWESet[T]) merge(other &LWWESet[T])

merge combines state from another LWWESet, taking the maximum timestamp for each element.

fn (mut o ORSet[T]) add(elem T) string

add inserts an element into the ORSet with a newly generated unique tag and returns that tag.

fn (mut o ORSet[T]) add_with_tag(elem T, tag string)

add_with_tag inserts an element into the ORSet with a specific unique tag.

fn (mut o ORSet[T]) remove(elem T)

remove marks all currently observed tags of the given element as removed.

fn (o &ORSet[T]) lookup(elem T) bool

lookup returns true if the element has at least one active tag that has not been removed.

fn (o &ORSet[T]) elements() []T

elements returns an array of all active elements currently belonging to the set.

fn (o &ORSet[T]) len() int

len returns the count of active elements currently belonging to the set.

fn (l ORSet[T]) == (r ORSet[T]) bool

== checks whether two ORSets have identical add-tags and remove-tags.

fn (mut o ORSet[T]) merge(other &ORSet[T])

merge combines state from another ORSet by taking the union of add-tags and remove-tags.

fn (mut t TwoPhaseSet[T]) add(elem T)

add inserts an element into the add-set.

fn (mut t TwoPhaseSet[T]) remove(elem T)

remove marks an element as removed by adding it to the remove-set.

fn (t &TwoPhaseSet[T]) lookup(elem T) bool

lookup returns true if the element is in the add-set and not in the remove-set.

fn (t &TwoPhaseSet[T]) elements() []T

elements returns an array of all active elements currently belonging to the set.

fn (t &TwoPhaseSet[T]) len() int

len returns the count of active elements currently belonging to the set.

fn (l TwoPhaseSet[T]) == (r TwoPhaseSet[T]) bool

== checks whether two TwoPhaseSets have identical add-sets and remove-sets.

fn (mut t TwoPhaseSet[T]) merge(other &TwoPhaseSet[T])

merge combines both the add-set and remove-set with another TwoPhaseSet.

enum LWWBias {
	add_wins
	remove_wins
}

LWWBias specifies the conflict resolution tie-breaker when add and remove timestamps are equal.

struct GCounter {
	// identity provides a unique identity for this replica.
	identity string
mut:
	// counter maps the identity of each replica to its observed counter value.
	counter map[string]int
}

GCounter represents a state-based grow-only counter (G-Counter) in CRDT. It only supports monotonic increments and converges across replicas by taking the maximum value observed for each replica identity.

fn (g &GCounter) id() string

id returns the replica identity of this counter.

fn (mut g GCounter) increment()

increment increments the counter of this replica by 1.

fn (mut g GCounter) increment_value(val int)

increment_value increments the counter of this replica by the given value. The value must be non-negative.

fn (g &GCounter) value() int

value returns the total accumulated value across all known replicas.

fn (mut g GCounter) merge(other &GCounter)

merge combines the state of another GCounter into this counter. For every replica, the maximum count between both counters is retained. This operation is commutative, associative, and idempotent.

struct GSet[T] {
mut:
	main_set map[T]u8
}

GSet represents a Grow-only Set (G-Set) in CRDT. Elements can only be added to the set; removals are not supported. Merging two G-Sets performs a mathematical set union.

struct LWWESet[T] {
pub:
	bias LWWBias = .add_wins
mut:
	add_map map[T]i64
	rm_map  map[T]i64
}

LWWESet represents a Last-Write-Wins Element Set (LWW-Element-Set) in CRDT. Each addition and removal associates a timestamp (nanoseconds) with the element. In contrasts to 2P-Set, elements can be repeatedly added and removed.

struct ORSet[T] {
mut:
	add_tags map[T]map[string]u8
	rm_tags  map[T]map[string]u8
}

ORSet represents an Observed-Removed Set (OR-Set / Add-Wins Set) in CRDT. Each addition generates a globally unique tag (ULID). A deletion of an element moves all tags currently observed for that element into a removal set. An element is present if there is at least one tag in the add-set that has not been removed. Concurrent add and remove operations result in the add winning (Add-Wins).

struct PNCounter {
mut:
	p_counter GCounter
	n_counter GCounter
}

PNCounter represents a state-based Positive-Negative Counter (PN-Counter) in CRDT. It consists of two G-Counters: one tracking increments and the other tracking decrements. It can both increase and decrease and converges across replicas.

fn (pn &PNCounter) id() string

id returns the replica identity of this PN-Counter.

fn (mut pn PNCounter) increment()

increment increments the counter value by 1.

fn (mut pn PNCounter) increment_value(incr int)

increment_value increments the counter value by the provided positive delta. The value must be non-negative.

fn (mut pn PNCounter) decrement()

decrement decrements the counter value by 1.

fn (mut pn PNCounter) decrement_value(decr int)

decrement_value decrements the counter value by the provided positive delta. The value must be non-negative.

fn (pn &PNCounter) value() int

value returns the current effective value of the PN-Counter (positive minus negative).

fn (mut pn PNCounter) merge(other &PNCounter)

merge combines both the positive and negative G-Counters of two PNCounters.

struct TwoPhaseSet[T] {
mut:
	add_set GSet[T]
	rm_set  GSet[T]
}

TwoPhaseSet represents a Two-Phase Set (2P-Set) in CRDT. It consists of two Grow-only Sets (GSets): one for additions and one for removals. An element can be added, and subsequently removed. Once removed, an element cannot be re-added.