Skip to content
A Golang implementation of CRDTs.
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.gitignore Avoid including test coverage and other results in the repo Aug 15, 2015
.travis.yml Add travis integration Aug 22, 2015
LICENSE Initial commit Jul 27, 2015
README.md Add report card Jan 28, 2016
g_counter.go Add documentation for G-Counter and PN-Counter Aug 22, 2015
g_counter_test.go Add G and PN Counters Aug 22, 2015
g_set.go Add serialization for persistence Nov 1, 2015
g_set_test.go
lww_e_set.go
lww_e_set_test.go Add serialization for persistence Nov 1, 2015
or_set.go Add tests for ORSet Aug 3, 2015
or_set_test.go Add travis integration Aug 22, 2015
pn_counter.go
pn_counter_test.go Add G and PN Counters Aug 22, 2015
set.go Initial phase of crdt impl Jul 27, 2015
twophase_set.go Add serialization for persistence Nov 1, 2015
twophase_set_test.go

README.md

CRDT Build Status Coverage Status GoDoc Report card

This is an implementation of Convergent and Commutative Replicated Data Types in Go.

The following state-based counters and sets have currently been implemented.

Counters

G-Counter

A grow-only counter (G-Counter) can only increase in one direction. The increment operation increases the value of current replica by 1. The merge operation combines values from distinct replicas by taking the maximum of each replica.

gcounter := crdt.NewGCounter()

// We can increase the counter monotonically by 1.
gcounter.Inc()

// Twice.
gcounter.Inc()

// Or we can pass in an arbitrary delta to apply as an increment.
gcounter.IncVal(2)

// Should print '4' as the result.
fmt.Println(gcounter.Count())

PN-Counter

A positive-negative counter (PN-Counter) is a CRDT that can both increase or decrease and converge correctly in the light of commutative operations. Both .Inc() and .Dec() operations are allowed and thus negative values are possible as a result.

pncounter := crdt.NewPNCounter()

// We can increase the counter by 1.
pncounter.Inc()

// Or more.
pncounter.Inc(100)

// And similarly decrease its value by 1.
pncounter.Dec()

// Or more.
pncounter.DecVal(100)

// End result should equal '0' here.
fmt.Println(pncounter.Count())

Sets

G-Set

A grow-only (G-Set) set to which element/s can be added to. Removing element from the set is not possible.

obj := "dummy-object"
gset := crdt.NewGSet()

gset.Add(obj)

// Should always print 'true' as `obj` exists in the g-set.
fmt.Println(gset.Contains(obj))

2P-Set

Two-phase set (2P-Set) allows both additions and removals to the set. Internally it comprises of two G-Sets, one to keep track of additions and the other for removals.

obj := "dummy-object"

ppset := crdt.NewTwoPhaseSet()

ppset.Add(obj)

// Remove the object that we just added to the set, emptying it.
ppset.Remove(obj)

// Should return 'false' as the obj doesn't exist within the set.
fmt.Println(ppset.Contains(obj))

LWW-e-Set

Last-write-wins element set (LWW-e-Set) keeps track of element additions and removals but with respect to the timestamp that is attached to each element. Timestamps should be unique and have ordering properties.

obj := "dummy-object"
lwwset := crdt.NewLWWSet()

// Here, we remove the object first before we add it in. For a
// 2P-set the object would be deemed absent from the set. But for
// a LWW-set the object should be present because `.Add()` follows
// `.Remove()`.
lwwset.Remove(obj); lwwset.Add(obj)

// This should print 'true' because of the above.
fmt.Println(lwwset.Contains(obj))

OR-Set

An OR-Set (Observed-Removed-Set) allows deletion and addition of elements similar to LWW-e-Set, but does not surface only the most recent one. Additions are uniquely tracked via tags and an element is considered member of the set if the deleted set consists of all the tags present within additions.

// object 1 == object 2
obj1, obj2 := "dummy-object", "dummy-object"

orset := crdt.NewORSet()

orset.Add(obj1); orset.Add(obj2)

// Removing any one of the above two objects should remove both
// because they contain the same value.
orset.Remove(obj1)

// Should return 'false'.
fmt.Println(orset.Contains(obj2))
You can’t perform that action at this time.