March Docs

CRDT

CRDT: state-based conflict-free replicated data types.

All CRDTs share the same contract: merge(a, b) -- commutative, associative, idempotent join equal(a, b) -- structural equality on the internal state

Sub-modules: CRDT.GCounter -- grow-only counter CRDT.PNCounter -- increment/decrement counter (two GCounters) CRDT.LWWRegister -- last-write-wins register (uses VectorClock) CRDT.ORSet -- observed-remove set (add/remove with UUID tags)

All values are immutable; every operation returns a new CRDT.

Types

ptypeTT = GCounter(Map(String, Int))#

Internal: map from actor IDs to non-negative counts.

ptypeTT = PNCounter(Map(String, Int), Map(String, Int))#

Internal: two per-actor count maps (P = increments, N = decrements).

typeTT(a) = LWWRegister(a, VectorClock)#

LWWRegister(value, clock_at_write)

ptypeTT(a) = ORSet(Map(String, (a, List(String))))#

Internal: map from to_key(elem) to (elem, surviving_tags).

Functions

fnaddadd(s : T(a), elem : a, to_key : a -> String, tag : String) : T(a)#

Add elem under the key to_key(elem), recording tag (which should be unique per add, e.g. UUID.v4()). Adding an element already present adds another tag and replaces the stored element with elem.

Examples

march> CRDT.ORSet.elements(CRDT.ORSet.add(CRDT.ORSet.new(), 1, int_to_string, "t1"))
[1]
fnaddadd(c : T, actor_id : String, n : Int) : T#

Add n to actor_id's slot. n must be >= 0 for the counter to stay a valid CRDT; a negative n is not checked and breaks the merge (the max of the slots would discard the decrease).

Examples

march> CRDT.GCounter.entries(CRDT.GCounter.add(CRDT.GCounter.new(), "a", 5))
[("a", 5)]
fnclockclock(r : T(a)) : VectorClock#

The vector clock of the last write.

Examples

march> VectorClock.entries(CRDT.LWWRegister.clock(CRDT.LWWRegister.new("draft", VectorClock.new())))
[]
fncontainscontains(s : T(a), elem : a, to_key : a -> String) : Bool#

True when to_key(elem) is present with at least one tag.

Examples

march> CRDT.ORSet.contains(CRDT.ORSet.new(), 1, int_to_string)
false

let s = CRDT.ORSet.add(CRDT.ORSet.new(), 1, int_to_string, "t1")
CRDT.ORSet.contains(s, 1, int_to_string)   -- true
fndecrementdecrement(c : T, actor_id : String) : T#

Decrement the counter by 1 on behalf of actor_id (bumps its N slot). The value may go negative.

Examples

march> CRDT.PNCounter.value(CRDT.PNCounter.decrement(CRDT.PNCounter.new(), "a"))
-1
fnelementselements(s : T(a)) : List(a)#

All elements currently in the set, in the underlying map's hash-traversal order.

Examples

march> CRDT.ORSet.elements(CRDT.ORSet.add(CRDT.ORSet.new(), "x", fn s -> s, "t1"))
["x"]
fnentriesentries(c : T) : List((String, Int))#

All (actor_id, count) pairs, in the underlying map's hash-traversal order.

Examples

march> CRDT.GCounter.entries(CRDT.GCounter.new())
[]
fnequalequal(a : T(x), b : T(x)) : Bool#

True when both sets have the same NUMBER of elements. Only the sizes are compared, not the elements themselves, so a set holding 1 and a set holding 2 count as equal; compare elements yourself when membership matters.

Examples

march> CRDT.ORSet.equal(CRDT.ORSet.new(), CRDT.ORSet.new())
true
march> CRDT.ORSet.equal(CRDT.ORSet.new(), CRDT.ORSet.add(CRDT.ORSet.new(), 1, int_to_string, "t1"))
false
fnequalequal(a : T(x), b : T(x)) : Bool#

True when both registers carry equal clocks. Values are not compared, so two registers created with different values at the same clock are equal.

Examples

march> CRDT.LWWRegister.equal(CRDT.LWWRegister.new("left", VectorClock.new()), CRDT.LWWRegister.new("right", VectorClock.new()))
true
fnequalequal(a : T, b : T) : Bool#

True when both counters have the same TOTAL of increments and the same total of decrements. This compares sums only, not per-actor state: two replicas that each counted one increment for different actors are equal although merging them gives 2.

Examples

march> CRDT.PNCounter.equal(CRDT.PNCounter.new(), CRDT.PNCounter.increment(CRDT.PNCounter.new(), "a"))
false
march> CRDT.PNCounter.equal(CRDT.PNCounter.increment(CRDT.PNCounter.new(), "a"), CRDT.PNCounter.increment(CRDT.PNCounter.new(), "b"))
true
fnequalequal(a : T, b : T) : Bool#

True when both counters hold the same count for every actor (an absent slot counts as 0, so a slot explicitly at 0 equals a missing one).

Examples

march> CRDT.GCounter.equal(CRDT.GCounter.new(), CRDT.GCounter.new())
true

CRDT.GCounter.equal(CRDT.GCounter.increment(CRDT.GCounter.new(), "a"),
                    CRDT.GCounter.increment(CRDT.GCounter.new(), "b"))   -- false
fngetget(r : T(a)) : a#

The register's current value.

Examples

march> CRDT.LWWRegister.get(CRDT.LWWRegister.set(CRDT.LWWRegister.new("draft", VectorClock.new()), "final", "n1"))
"final"
fnincrementincrement(c : T, actor_id : String) : T#

Increment the counter by 1 on behalf of actor_id (bumps its P slot).

Examples

march> CRDT.PNCounter.value(CRDT.PNCounter.increment(CRDT.PNCounter.new(), "a"))
1
fnincrementincrement(c : T, actor_id : String) : T#

Increment actor_id's slot by 1 (creating it at 1 when absent).

Examples

march> CRDT.GCounter.entries(CRDT.GCounter.increment(CRDT.GCounter.new(), "a"))
[("a", 1)]
fnmergemerge(a : T(x), b : T(x)) : T(x)#

Union of two sets: every key from either side, with the tag lists of a key present in both appended (duplicates are kept, so tag lists grow on repeated merges). On a shared key the element stored in a is kept.

Examples

march> CRDT.ORSet.size(CRDT.ORSet.merge(CRDT.ORSet.add(CRDT.ORSet.new(), 1, int_to_string, "t1"), CRDT.ORSet.add(CRDT.ORSet.new(), 2, int_to_string, "t2")))
2
fnmergemerge(a : T(x), b : T(x)) : T(x)#

Keep b when a's clock happened before b's; otherwise keep a. That includes concurrent and equal clocks, so concurrent writes resolve to the LEFT argument and merge(a, b) and merge(b, a) can differ.

Examples

march> CRDT.LWWRegister.get(CRDT.LWWRegister.merge(CRDT.LWWRegister.new("left", VectorClock.new()), CRDT.LWWRegister.new("right", VectorClock.new())))
"left"

let r0 = CRDT.LWWRegister.new("v0", VectorClock.new())
let r1 = CRDT.LWWRegister.set(r0, "v1", "n1")
CRDT.LWWRegister.get(CRDT.LWWRegister.merge(r0, r1))   -- "v1"
fnmergemerge(a : T, b : T) : T#

The CRDT join: the per-actor maximum of the increment (P) maps and, independently, of the decrement (N) maps.

Examples

march> CRDT.PNCounter.value(CRDT.PNCounter.merge(CRDT.PNCounter.increment(CRDT.PNCounter.new(), "a"), CRDT.PNCounter.decrement(CRDT.PNCounter.new(), "b")))
0
fnmergemerge(a : T, b : T) : T#

The CRDT join: the per-actor maximum of the two counters' slots, keeping every actor present in either. Commutative, associative and idempotent.

Examples

march> CRDT.GCounter.value(CRDT.GCounter.merge(CRDT.GCounter.add(CRDT.GCounter.new(), "a", 2), CRDT.GCounter.add(CRDT.GCounter.new(), "b", 3)))
5

Merging two replicas that both counted for the same actor keeps the larger count rather than adding them:

let x = CRDT.GCounter.add(CRDT.GCounter.new(), "a", 2)
let y = CRDT.GCounter.add(CRDT.GCounter.new(), "a", 3)
CRDT.GCounter.value(CRDT.GCounter.merge(x, y))   -- 3
fnnewnew() : T(a)#

An empty set.

Examples

march> CRDT.ORSet.elements(CRDT.ORSet.new())
[]
fnnewnew(value : a, clock : VectorClock) : T(a)#

A register holding value, written at vector clock clock.

Examples

march> CRDT.LWWRegister.get(CRDT.LWWRegister.new("draft", VectorClock.new()))
"draft"
fnnewnew() : T#

An empty increment/decrement counter with value 0.

Examples

march> CRDT.PNCounter.value(CRDT.PNCounter.new())
0
fnnewnew() : T#

An empty grow-only counter: every actor's count is 0.

Examples

march> CRDT.GCounter.value(CRDT.GCounter.new())
0
fnremoveremove(s : T(a), elem : a, to_key : a -> String) : T(a)#

Remove elem (by to_key(elem)) together with all its tags. Removing an absent element is a no-op. The entry is dropped without a tombstone, so a later merge with a replica that still has the element restores it.

let s = CRDT.ORSet.add(CRDT.ORSet.new(), 1, int_to_string, "t1")
CRDT.ORSet.size(CRDT.ORSet.remove(s, 1, int_to_string))   -- 0

Examples

march> CRDT.ORSet.size(CRDT.ORSet.remove(CRDT.ORSet.new(), 1, int_to_string))
0
fnsetset(r : T(a), new_val : a, actor_id : String) : T(a)#

Write new_val on behalf of actor_id: the stored clock is the previous one with actor_id's slot incremented, so the new write is causally after the old one.

Examples

march> VectorClock.entries(CRDT.LWWRegister.clock(CRDT.LWWRegister.set(CRDT.LWWRegister.new("draft", VectorClock.new()), "final", "n1")))
[("n1", 1)]
fnsizesize(s : T(a)) : Int#

Number of elements with at least one tag. O(n).

Examples

march> CRDT.ORSet.size(CRDT.ORSet.add(CRDT.ORSet.add(CRDT.ORSet.new(), 1, int_to_string, "t1"), 2, int_to_string, "t2"))
2
fnvaluevalue(c : T) : Int#

Current value: the sum of all increments minus the sum of all decrements.

Examples

march> CRDT.PNCounter.value(CRDT.PNCounter.decrement(CRDT.PNCounter.increment(CRDT.PNCounter.new(), "a"), "b"))
0
fnvaluevalue(c : T) : Int#

The counter's value: the sum of all actor slots.

Examples

march> CRDT.GCounter.value(CRDT.GCounter.add(CRDT.GCounter.increment(CRDT.GCounter.new(), "a"), "b", 4))
5